# CAST: Character labeling in Animation using Self-supervision by Tracking

Oron Nir
Reichman University , Israel
Microsoft Corporation
Gal Rapoport
Reichman University , Israel
Ariel Shamir
Reichman University , Israel

###### Abstract

Cartoons and animation domain videos have very different characteristics
compared to real-life images and videos. In addition, this domain carries a
large variability in styles. Current computer vision and deep-learning
solutions often fail on animated content because they were trained on natural
images. In this paper we present a method to refine a semantic representation
suitable for specific animated content. We first train a neural network on a
large-scale set of animation videos and use the mapping to deep features as an
embedding space. Next, we use self-supervision to refine the representation
for any specific animation style by gathering many examples of animated
characters in this style, using a multi-object tracking. These examples are
used to define triplets for contrastive loss training. The refined semantic
space allows better clustering of animated characters even when they have
diverse manifestations. Using this space we can build dictionaries of
characters in an animation videos, and define specialized classifiers for
specific stylistic content (e.g., characters in a specific animation series)
with very little user effort. These classifiers are the basis for
automatically labeling characters in animation videos. We present results on a
collection of characters in a variety of animation styles.
Code and resources are available at: https://github.com/oronnir/CAST.

_K_ eywords Representation Learning $\cdot$ Contrastive Learning $\cdot$
Multi-Object Tracking $\cdot$ Animation

##  1 Introduction

Recognizing and labeling characters in a given video is an important task for
many applications. It can empower media companies to search, analyze, and
reuse content in videos. Many current solutions for real-life videos are based
on face detection or people detection. However, in the animation and cartoon
domain this task is more challenging. First, there is a wide diversity of
styles and genres in animation such as Manga, hand-drawn and CGI movies that
can have significant differences in appearance. In addition, they are all very
different from real-life videos. Trying to build one semantic representation
for all animation styles or relying on representations constructed for real-
life videos is problematic. Second, characters in animation videos could be
anything from a person to an animal or even an object like a talking
candelabra. Relying on face or people detectors is insufficient. Third, the
same character can change color, texture, style, and shape, even in the very
same scene (see Figure 1). Such variability means that the semantic
representation of a character cannot be based on appearance alone, cannot use
natural images learned representations and must include several possible
instance variations of the same character.

Figure 1: The same character in animation can change color, appearance and
even shape. Our challenge is to build a representation that can maintain its
semantics and map all visual depictions to the same identity.

In this paper we suggest learning a semantic representation suitable for
character identification and labeling specific to a given animation style
using self supervision. As a first step towards generalization, we label an
animated video dataset in various styles and leverage it to refine an object
detector and to define a base latent representation for animation by refining
a classifier in a supervised setup. This step is performed once to better
capture the characteristics of animated media as opposed to natural videos for
detection. On the other hand, character labeling demands precision for
identification, and therefore a more style-specific representation. To adapt
the representation towards specific animation styles and move different
instances of the same character closer in the semantic space we introduce a
self-supervised learning method. The method takes an input video (e.g., one
episode of a series or a full feature film), segments its shots, and runs the
base object detector on this video. A multi-object tracker (MOT) is later
applied per shot to follow all characters in the shot through changes in
appearance and shape. Next, triplets of examples are sampled based on the
characters’ tracklets, and are leveraged to refine the learned representation
using contrastive loss. The underlying hypothesis is that two detected
characters within the same tracklet share identity while two that appears in
the same frame do not. This alters the semantic space towards representing the
specific animated style, where distances convey the identity of characters and
not simply appearance differences.

To illustrate the effectiveness of the new representation space we use
clustering to build more coherent and meaningful clusters of examples for each
character. We demonstrate the application of this space for long-tail
dictionary building of characters in a video, where many characters, even if
they appear sparsely, populate the dictionary. We also use this representation
to define more effective animated character classifiers, and demonstrate their
use for dense identification and labeling of characters on unseen test-videos.
Hence, we call our method CAST: Character labeling in Animation using Self-
supervision by Tracking.

##  2 Related Work

Recent advancements in deep neural networks applications for various computer
vision tasks like object detection and facial recognition have matured to
solve problems at an industrial scale. However, specific domains with less
available data, like animation and art, many times require a different
approach [1, 2, 3].

Animated character recognition has been addressed with machine learning models
before. Yu et al. [4] have suggested a fuzzy diffusion distance as a cartoon
similarity metric for recognition and clustering purposes achieving up-to 77%
accuracy, using Kuhn-Munkres algorithm, on a proprietary dataset with 60
classes. Zhang et al. [5] aimed at detecting IP violations and piracy with
Scalable-Shape Context and Hough Voting. Nguyen et al. [6] suggested a
convolutional neural network-based (CNN) comic characters detector for a comic
book recognition problem. They focus on a binary task of character detection
and have reported 92% precision. They have based their detector on the YOLO-V2
detector by Redmon & Farhadi [7]. Our work identifies characters in video,
that introduces higher character variance compared to static comic books. Chu
et al. [8] have suggested a CNN based model for detecting Magna faces in grey
scale. They have addressed this challenge and taken the approach of using a
joint CNN for bounding box regression and non/character classification on
candidate regions extracted using selective search. Their method reached 66%
F1 score on the Magna109 dataset [9]. Ogawa et al. [1] have used an SSD300
architecture for the same detection problem on this dataset and reached an
average precision of 67% and 79% on face and body, respectively.

Landmark detection in art was also addressed by [2, 10] and emotion
recognition in animation by [11, 12]. Caricature recognition was benchmarked
by Huo et al. [13] suggesting that the artistic aspects embedded in a
caricature challenges the approach of augmenting real-life images as they
impose a significant domain difference.

Figure 2: CAST self-supervised representation learning pipeline includes:
automatic shot segmentation, detection, multi-object tracking, and
contrastive-based refinement to define the unique semantic embedding for an
animation style.

Human character identification that works on realistic videos usually rely on
detection and clustering of faces or humans [14, 15, 16, 17]. Naming of
characters is usually done by searching the web or using social media. Since
animation resources and datasets are less common, the only manual part in our
method is naming characters for identification.

Clustering of real-life faces is yet another well researched field. Zhu et al.
[18] have suggested a rank order distance to group similar instances of the
same person. Schroff et al. [19] have introduced FaceNet and the triplet-loss
for projecting images onto a latent space that quantifies similarity in a
supervised-learning manner. Recently, Somandepalli et al. [20] used tracking
of faces in a photo-realistic video, followed by clustering and verification
using MvCorr[21] and Improved Triplet [22] to adapt available face
representation data to perform better on racially diverse images following
[23]. Aneja et al. [24] have suggested DeepExpr model for facial expression
recognition for multiple styles. Tsubota et al. [3] have used the Manga109
dataset for manga face clustering. The approach they took for generalization
of deep embeddings adaptation on the inferred manga comics was based on deep
metric learning (DML) inspired by the work of Zhang et al. [25]. They reached
a normalized mutual information (NMI) of 71% and accuracy of 64% based on
manga domain specific priors e.g., co-occurrence per comic scene. The ‘k’
number of characters was assumed to be given and was not estimated. The
underlying CNN architecture was ResNet50 [26]. An ablation study suggested
that without the page information the NMI drops to 67% and the accuracy to
58%. This indicates the importance of a temporal analysis in our challenge.
Shen et al. [27] have addressed a similar problem, discovering visual patterns
in art collections with spatially consistent feature learning also known as
ArtMiner. They have suggested a similarity metric based on ResNet18 for
artwork elements to automatically recognize copied pieces of work created in
different styles e.g., oil, pastel, water-color, etc. They have reported 88.5%
accuracy on LTLL [28] and 85.7% mAP on Oxford5k [29]. Recently, [30] have
published iCartoonFace dataset for face detection and identification in
animated images. While anthropomorphized faces tend to have the same facial
features people have, an animated character’s body shares less common
attributes and perhaps makes the generalization a more challenging task.

The closest prior work to ours is [31] who built a system that aims at finding
the main cast of a given movie which is termed ‘unsupervised discovery of
character dictionaries’ . Our work not only builds the dictionary but allows
to create classifiers that can recognize and index characters at frame-level
and generalize to additional episodes of a given series. Their work applied
the MultiBox detector on uniformly sampled frames followed by an object
tracker, ImageNet FC7 layer for embeddings and Afinity Propagation for
clustering. Their overall dictionary F1-Score is 72% and 70% cluster purity on
a dataset of eight videos of SAIL AMCD. To evaluate the over/under clustering
performance they’ve measured the median number of clusters per character which
was 3. We consider this paper as our baseline for dictionary building and
compare our results. Kim et al. [32] have addressed the same task. Their main
contribution was a character detector that adapts the animation style with a
region-based Faster R-CNN following the work of [33]. The rest of their
algorithm aligns with [31]. However, since their ABCD data set is proprietary
and they do not report cluster purity and median clusters per character it was
difficult to compare to.

##  3 Representation Learning

An overview of the CAST representation pipeline is represented in Figure 2.
First, the video is segmented to shots according to the method of Hua et al.
[34]. Next, frames are sampled consistently on which our character detector is
applied, providing character bounding box proposals. These proposals are then
tracked while those who share a tracklet should appear closer in the embedding
space than other proposals in the same shot for they belong to different
characters. A set of triplets examples are then sampled and used to further
refine the basic mapping network for the specific style of animation. This
representation is later used for clustering, dictionary discovery and
classifier definition of characters in this animation style.

DATASET ROLE | STYLES[#] | VIDEOS[#] | KEYFRAMES[#] | HOURS | CHARACTERS[#] | BOXES[#]
---|---|---|---|---|---|---
Training | 61 | 174 | 118,751 | 65.6 | 549 | 257,706
Test | 50 | 50 | 38,821 | 24.1 | 681 | 90,325
Evaluation | 7 | 14 | 17,583 | 11.0 | 49 | 50,300
Table 1: Statistics for the Training, Test, and Evaluation CAST datasets.

###  3.1 Data Acquisition

Building a CNN-based semantic representation must address both the scale and
diversity of the data in the domain. Thus, we gathered data sets of cartoon
and animated content from various sources such as media companies and the web.
For the basic Training dataset, we collected 174 videos in 61 different styles
including Anime, CGI, 2D cartoons, and more (see the Appendix). Examples of
series collections in this dataset are: Blender (3D CGI), legacy Looney-toons
videos published under public domain (2D hand drawn in color as well as gray-
scale), Manga of various styles, Indian/Korean animated films, and more. From
these videos more than 118K frames were extracted and annotated manually.
Characters in each frame were marked with a bounding-box and named (using
Microsoft’s UHRS - like [35]). This resulted in more than 250K ground-truth
bounding-box instances of 549 distinct characters.

We used this basic Training dataset to define two neural networks: the first
was trained to detect basic proposals for animated characters in animation
videos while the second was trained as the basic mapping of proposals into a
semantic embedding space, which is later refined using self-supervision for
each specific animation style representation.

For testing the domain-adapted detector and selecting a clustering algorithm,
we used a second Test data set. This set contained 50 videos with a total
length of 24 hours and 681 characters. This dataset was collected from YouTube
with various styles e.g. Gaming, amateur and professional productions content,
and various other genres.

For evaluating the dense character identification application, presented
later, we collected a third, Evaluation, dataset from seven different cartoon
series, two episodes each. One episode was used to guide the self-supervision
and train classifiers, and the other was manually labeled and used for testing
the classification results based on the first episode. This data set is 11
hours long and includes 49 characters. More details on the three sets can be
found in Table 1. Note that the three datasets do not contain any overlap
i.e., no character, episode or series appears in more than one dataset. We
plan to publish a labeled dataset for future work comparison.

We also used the SAIL AMCD dataset [31] to evaluate CAST for unsupervised
discovery of character dictionaries and compare our results to [31]. This set
contains eight evaluation videos that are full-length feature films of
different animation styles. The videos were trans-coded to standard HD and
sampled at 4 FPS.

###  3.2 Basic Animated Character Detection

Due to the high variance in characters’ appearance, and the fact that animated
characters are not necessarily humans, a simple person detector for character
proposals will not suffice. Our base detector is the YOLO V2 generic object-
detector architecture [7] which was originally trained on ImageNet [36] with
millions of images. We use our Training set to fine-tune YOLO’s Person class
for 20 epochs and use it as a binary classifier, character vs. non-character.
The person detector was chosen as many animation characters still tend to have
a human-like attributes. Data augmentation methods were applied to avoid
overfitting randomizing both vertical and horizontal flip as well as resize
with factor range $[0.5,2.0]$. We also tried to fine-tune a different
architecture based on Faster-RCNN [37], which is a two-pass CNN. However, we
found our architecture, based on YOLO’s fast low compute one-pass detector, to
be faster and produced higher average precision. We compare this detector to
the following alternatives: using the YOLO V2 single class person detector,
and using all combinations of the classes: Person, Animal, Mammal, and Toy as
a detector. The detectors’ effectiveness was evaluated in terms of Average
Precision (AP) at a 50% Intersection over Union (IoU) using the Test dataset.
Our basic character detector has reached an AP of 61% significantly
outperforming the YOLO V2 person detector (AP=50%) and the combined classes
version (AP=50%) in a wide range of animation styles.

###  3.3 Base Embedding Network

Feature maps in deep layers of networks such as VGG [38] and ResNet18 [26]
have been shown to represent high-level semantic meaning in many previous
works. However, such models were trained mostly on natural images, therefore
could misinterpret animated content. Similar to the above approaches, to learn
a representation suited for our domain, we use our Training dataset to fine-
tune classification networks and use the feature map of its deepest hidden
layer as the representation of the base embedding space. The Training set
containing 549 different characters was heavily long tailed: 40% of the
characters have less than 50 samples. Therefore, we have balanced the dataset
during training by repeating rare characters’ images, such that per epoch,
each character has at least 50 samples. To avoid overfitting, data
augmentation transformations have been applied on the training data at random
using the following methods: crop resize, Affine transform, color jitter, and
horizontal flip.

We compared different configurations of three different architectures:
ResNet18 [26], SEResNeXt [39] and ArtMiner [27]. SEResNeXt was found to
perform best and therefore the last average pooling layer was used ($20^{th}$
squeeze and excitation block). Yielding vectors of size 2,048, as the basic
semantic representation for animation characters bounding boxes.

To evaluate this representation, we measured how well this representation
conveys semantic similarity. We built a test-set by creating a balanced
dataset of 600k pairs of similar and dis-similar images of characters from the
Test dataset. We defined a similarity measure for such pairs to be the cosine
similarity of our embeddings of the extracted boxes. The pairs were ordered
according to their similarity and addressed in a binary classification design
with a RoC curve. In Figure 3 we plot the curves of the various tested
alternative representations. Our representation, using an SEResNeXt back-bone,
has outperformed all alternatives on the test data. We further found that
training the network for more than 40 epochs does not provide much gain.

Figure 3: RoC curve per basic semantic embedding backbone architecture:
ResNet18, ResNet50, ArtMiner, SEResNeXt22k (the original network), our network
fine-tuned for 40 epochs as well as a further trained version to illustrate
the convergence.

###  3.4 Self-Supervision

Similar to previous works, e.g. [32], we strive to refine the semantic space
for each specific animation style. Given a specific animation style (for
instance, an episode of an animation series), we fine-tune the base embedding
network towards this style, using a novel self-supervised approach which
combines multi-object tracking with contrastive learning (triplet margin loss
[19, 40] with margin=1.0). Our main hypothesis is that two samples from a
single tracklet can be used as positive and anchor examples (coming from the
same character but in different frames), while another character proposal from
the anchor’s frame can be used as a negative example (coming from the same
frame but different character).

Figure 4: Triplets examples illustrates the Positive, Anchor, and Negative
triplets. The method aims for trivial and non-trivial examples while it is
still resilient for erroneous and non-character examples.

We sample 10k triplets and refine the base embedding network for 10 epochs
using AdamW [41] ($LR=2\cdot 10^{-5}$, batch size=20, $\lambda=10^{-4}$,
$\gamma=0.1$, $\hat{m_{t}}=0.9$). This setup applies for any specific
animation style in PyTorch [42]. Tracking is performed with a classic multi-
object tracking (MOT) approach of max-flow-min-weight algorithm inspired by
the works of Zheng et al. [43] and Wang et al. [44]. A sparse network based on
detection is constructed, Next, an optimization algorithm finds the optimal
flow in the graph that maximizes its MAP representation. Lastly, the tracks
are derived from the flow function using a greedy shortest weighted path
algorithm as described next.

To construct the network we include an artificial source and sink nodes, and
each detected bounding box is considered as two nodes (‘in’ and ‘out’) with a
linking edge weighted by its detection confidence. Skip connections are added
every FPS frames to overcome temporary occlusions. The edge weight between
detections of neighbor (or skip) frames is weighted by the following six
factors: (1) Time gap proximity w.r.t. the sample FPS, (2)
$P_{IoU}=0.5(IoU+1)$ so disjoint boxes could potentially be linked, (3) Scale
difference ratio, (4) Euclidean distance in pixels of their centers, (5)
semantic similarity using the original embeddings, and (6) scale-weighted
center distance as characters which are closer to the camera may have higher
relative angular velocity. The six factors above are aggregated together using
a geometric weighted average into a match likelihood measure. Their
corresponding weights are (1.0, 1.5, 1.5, 2.0, 3.5, 4.5). Each edge in this
network is considered as a unit capacity network and solved with the interior-
point algorithm as a Linear Programming (LP) representation [45]. Since the
constraints matrix is totally unimodular the LP solution is also a valid
integer programming solution [43]. Each tracklet solution per shot is greedily
derived from the flow function using a weighted DAG shortest path algorithm
and its MAP tracklet probability is considered to be its significance. Tracks
significance filter threshold per shot is defined to be 10% of the shot’s most
significant tracklet.

The triplets gathering is performed by sampling a shot with at least two
tracklets, out of which a frame is picked, with at least two proposals
(bounding boxes). The first is used as an anchor while the second is used as
the negative example. Then, from the anchor’s tracklet, a third proposal is
randomly picked as the positive example. Figure 4 illustrates the some
triplets types. Many standard triplets are gathered using this method where a
character preserves its appearance in the positive pair and contrasted with a
different character. However, this method also captures non-trivial examples
in which the character itself changes its appearance or shape. The two right
columns in Figure 4 illustrate erroneous triplets that can also be gathered
using our method: the first is the results of errors in tracking causing a
wrong positive pair, and the second is an error in the detector where non-
characters (objects) are considered characters. However, due to the large
amount of triplets gathered our mapping is resilience to such errors.

##  4 Semantic Clustering

Figure 5: Visualizing the first two principal components projection of our
semantic embedding space before and after the Self-Supervision. We demonstrate
the effectiveness of our method as a representation learning technique.

A strong indicator for a meaningful representation is the ability to cluster
items in the semantic embedding space. Instances of the same animated
character, even visually different, should all map to a relatively close
position in the embedding space, while instances of different animated
characters, even if they are visually similar, should be placed further away
in the embedding space. Therefore, if we cluster the bounding boxes in the
embedding space, the results should be coherent clusters of characters.

First, we demonstrate the effectiveness of our base embedding network. We
conducted an experiment, where we split the Test dataset to six subsets of
various characters and used k-means clustering in the embedding space. We use
cluster purity [46] as our measure as opposed to clustering evaluation
measures like NMI and F-score, and evaluate the performance of the clustering
quality as a function of the number of clusters. We compared our embedding
with SEResNeXt22, ResNet18, ResNet50, and ArtMiner for different values of
‘k’. This comparison highlighted the superiority of our base embedding over
the alternatives as for every value of ‘k’, the purity of clusters in our base
embedding was significantly higher. The full details of this experiment can be
found in the Appendix.

Next, we compared several clustering algorithms, namely k-means, mean-shift,
modularity maximization, affinity propagation, DBSCAN agglomerative
clustering, and spectral clustering on our Test dataset. We use purity [46]
and K-metric, which is the geometric mean of the class purity and the cluster
purity over the contingency matrix [47]. The two best performing were DBSCAN
and agglomerative clustering. They yielded a median cluster purity of 96% and
K-metric of 40%. We selected DBSCAN as the basic clustering algorithm as it
handles noisy character proposals filtering inherently. The hyper parameters
that govern the confidence score for filtering were determined by grid search
using the Test dataset to be $\lambda_{1}=0.275,\lambda_{2}=0.4$. To optimize
clusters purity, we binary search for the $\varepsilon$ parameter of DBSCAN so
that it maximizes the Silhouette times the non-noisy proposals in the range
$25\leq k\leq 60$. This unsupervised criterion balances purity and cluster
size.

Since we optimized for _recall_ during the proposal detection stage, there are
still many outliers that are non-characters among the proposals. We remove
outliers inside each cluster and remove low-confidence clusters altogether.
This filtering is based on a confidence score that was calculated as a product
of the detection’s confidence and a squared exponential kernel of the sample’s
distance to the cluster center:

$k_{\textrm{SE}}(x,\mu)=\exp\left(-\frac{(x-\mu)^{2}}{\lambda_{1}^{2}}\right)$

where $\mu$ is the cluster’s median, $x$ is the sample, and $\lambda_{1}$ is a
hyper parameter. A sample is considered an outlier when its confidence score
is less than the cluster’s $Q_{25}-\lambda_{2}\cdot IQR$ where $Q_{25}$ is the
$25^{th}$ percentile, $IQR$ is the interquartile range and $\lambda_{2}$ is
another hyper parameter. Finally, clusters with average centers that are up-to
0.7 cosine-similarity are merged back together.

Table 2: Clustering ablation study on our Evaluation dataset. The better algorithm has less Clusters to label, higher Pure percentage, more Characters per video, and as many Labeled boxes per video. Self- | Clusters | Pure | Characters | Labeled boxes
---|---|---|---|---
Supervision | [#]$\downarrow$ | [%]$\uparrow$ | per video[#]$\uparrow$ | per video[#]$\uparrow$
Before | 28.7 | 70 | 7.0 | 396.2
After | 20.0 | 90 | 13.1 | 599.3
Self-Supervision |  #1 |  #2 |  #3 |  #4 |  #5 |  #6 |  #7 |  Avg.
---|---|---|---|---|---|---|---|---
Before |  0.156 |  0.258 |  0.166 |  0.285 |  0.231 |  0.382 |  0.247 |  0.246
After |  0.320 |  0.423 |  0.364 |  0.601 |  0.248 |  0.520 |  0.332 |  0.401
Silhouette gain$\uparrow$ |  0.164 |  0.166 |  0.199 |  0.317 |  0.017 |  0.137 |  0.085 |  0.155
Table 3: Self-Supervision introduces a significant gain of 0.155
($P$-val=0.0047) to the Silhouette score on our Evaluation dataset.

Our combined MOT and contrastive-loss based self-supervision allowed further
representation enhancement. The performance analysis using the Evaluation
dataset shows that 90% of clusters created after the fine-tune stage were
totally pure across all styles, while each character has a median of 1.2
clusters (lower is better). This demonstrates a significant improvement over
the base-embedding as the clustering algorithm has yielded 30% less clusters
for the same video i.e., lower over segmentation. These clusters captures 13.1
characters per video instead of 7.0 i.e., 87% better while these clusters have
higher purity. (See Table 2 and an illustrative example in Figure 5). As can
be seen in Table 3, for all different style of videos in our Evaluation set,
the clustering quality measured using silhouette increases as a result of our
self-supervision refinement.

##  5 Applications

###  5.1 Long-Tail Dictionary Construction

The first step towards automatic labeling of characters in animation movies is
automatic characters cast discovery. In this task, the goal is to build a
dictionary of characters appearing in the movie. For any given animation
style, we first use our automatic method to learn the refined mapping tuned to
this style. Then, for each new episode or movie in this style we use our
detection pipeline to gather character proposals and map them to the semantic
space. We then cluster and filter the proposals in this representation space.
This representation promotes purity so that each cluster will contain
proposals belonging to a single character and encourages only a small number
of clusters (preferably one) representing the same character. Then, to build
the dictionary we create an entry for each significant cluster.

Proposals Creation: To reduce the chance of a miss-detection, the character
proposal detector is tuned to be recall oriented as False-Positive detection
is recoverable downstream while False-Negative is not. Only bounding boxes
with less than 20% confidence or having a size smaller than 2.5% of the frame
are filtered out at this stage. This causes repetitions of semi-identical
proposals, i.e., bounding boxes with highly similar content. Hence, we apply a
screening procedure to remove duplicate proposal. Each proposal is represented
by an Edge Directional Histogram (EDH) feature vector of size 116 [48]. The
64-dimensional color and texture features ensures global similarity between
two proposal and the $4\cdot 13$ EDH features ensures spatial similarity with
detailed constrains by edge. The EDH was computed using a Canny edge detector
with a $7\times 7$ Gaussian convolution kernel. Next, the cosine-similarity
was computed between all pairwise proposals, and an undirected graph was built
with proposals as nodes and cosine-similarity as edge weight. Edges of weight
lower than $0.995$ were pruned. Finally, cliques were found in this graph
using [49, 50], and each clique was aggregated into a single proposal.

Characters Selection: To build the dictionary we first cluster all candidate
bounding boxes and filter them as described in Section 4. Next, we select
every cluster and compute the median vector of all proposals in the cluster.
We pick the proposal closest to the median as the representative and insert it
to the dictionary. We report the performance of our algorithm for unsupervised
discovery of character dictionaries both on our Evaluation dataset and on
SAIL-AMCD, comparing our results to [31]. Although [32] reported similar
results to ours, their dataset was not available and they did not report the
aggregated purity of their clusters.

SAIL AMCD Video /Method avg. score |  Precision
[%]$\uparrow$ |  Recall
[%]$\uparrow$ |  F1
[%]$\uparrow$ |  Purity
[%]$\uparrow$ |  Med.
exemplars per character$\downarrow$ |  Avg.
exemplars per character$\downarrow$ |  Additional
characters [#]$\uparrow$
---|---|---|---|---|---|---|---
Cars 2 |  76.9 |  75.0 |  75.9 |  98.1 |  1.00 |  1.286 |  13
Free Birds |  100.0 |  90.0 |  94.7 |  98.6 |  1.00 |  1.360 |  15
Frozen |  96.0 |  100.0 |  98.0 |  99.5 |  2.00 |  2.000 |  9
Dragon 2 |  95.0 |  91.7 |  93.3 |  94.7 |  1.00 |  1.444 |  6
Shrek Forever After |  89.7 |  90.0 |  89.8 |  90.5 |  1.00 |  1.679 |  18
Tangled |  86.4 |  77.8 |  81.8 |  84.2 |  1.00 |  1.714 |  5
The Lego Movie |  85.2 |  100.0 |  92.0 |  95.0 |  1.00 |  1.522 |  11
Toy Story 3 |  93.5 |  77.8 |  84.9 |  99.8 |  1.00 |  1.483 |  11
CAST (ours) |  90.3 |  87.8 |  88.8 |  95.1 |  1.125 |  1.561 |  11.0
Somandepalli et al. |  81.0 |  65.2 |  72.2 |  70.3 |  3.00 |  N/A |  N/A
Table 4: Unsupervised Discovery of Character Dictionaries comparison on the
SAIL AMCD test videos.

On our CAST Evaluation dataset, yields 16.8 clusters per video, when the
average number of characters per video is 13. On average the cluster purity
was 98.5%. The precision, recall and F1-score of these dictionaries are 91.8%,
83.1%, and 86.6%. A visual illustration of the power of self-supervision
refinement can be seen in Figure 1. Not only that all the different
manifestation of this character (including kid/toaster/cat/broccoli) were
mapped to the same cluster, but this cluster, including 94 bounding boxes, was
100% pure.

Comparing CAST with the work of Somandepalli et al. [31] on the SAIL AMCD test
set (see Table 4). CAST outperforms the state of the art in all metrics and
indicates 16.6% improvement in F1 as well as 24.8% in purity. Moreover, CAST
allows to build a much larger dictionary containing twice as many characters
that were not chosen in the original evaluation as lead characters (see
examples of dictionaries in the Appendix).

###  5.2 Defining Classifiers for Characters

The second step towards automatic labeling of characters in animation movies
is the construction of dedicated classifiers for each character in the movies.
The key idea is to gather enough examples that are diverse enough for each
character to build a training set for effective learning. Using CAST, the
dictionary is presented to the user for naming. This allows us to use all the
proposals in every named cluster as training data for classifiers. This also
allows us to merge clusters when the same character is found more than once in
the dictionary. Lastly, this also allows us to filter noisy clusters, where
several characters appear in the cluster. We do this by presenting a number of
examples from each cluster to the user and validating that they are all
examples of the same character.

Using this method, a specialized training set for each character can be
constructed with minimal user effort. These training sets are then used to
train specialized classifiers as needed. Moreover, when processing a new
video, the user can choose to apply the existing classifier model for
automatic identification of some characters or add additional new characters
by further naming clusters of unidentified characters.

Training Classifiers: All the named clusters are merged into one training-set
that allows training a multi-class image classifier for the specific animation
styles. In our experiments we fine-tune a state-of-the-art CNN classifier
SEResNeXt [39] for 40 epochs using typical augmentation operations such as
rotations and mirroring.

To best train a mutli-class classifier, it is important to introduce an
additional class of negative examples which comes from the same animation
style. Typically, these examples are cropped from the background of processed
images. Since our model is aimed at working in the wild on new series and new
animation styles, we devised a method to create negative examples
automatically per animation style. The base detector that marks characters
bounding boxes on keyframes is biased for recall. Hence, our hypothesis is
that all other pixels can be considered background. The challenge is to find
large enough sub-frames that do not intersect with the characters’ bounding
boxes (examples available in the Appendix). Finding the largest empty
rectangle (LER) is a known problem [51]. In practice, we devised a recursive
algorithm that extracts more than a single empty rectangle per keyframe, not
necessarily the largest ones, but with some minimal width, height, and area at
a runtime of $O(n^{2})$ where $n$ is the number of proposals. For the
algorithm and the proof see the Appendix. The resulting classifier can then be
used on other videos of the same style (e.g., other episodes of the same
animation series) to classify known characters. Still, new characters can
appear in such videos, as well as some known characters with different
appearances. In such cases, our method can be applied again with the same
procedure of clustering and naming but only on the unknown proposals of any
new video processed, to create new training examples and re-train the
classifier further.

|  Detected |  Clusters |  Number of |  Clusters per |  Boxes per |  Relevant |  General
---|---|---|---|---|---|---|---
Series (credit ©) |  proposals |  to name |  characters |  character |  character |  Purity[%] |  Purity[%]
1\. Bob the builder (HIT) |  2,648 |  20 |  10 |  1.7 |  26.3 |  95.5 |  95.5
2\. Fairly odd parents
(Nickelodeon) |  4,215 |  17 |  18 |  1.0 |  44.3 |  99.1 |  99.1
3\. Fireman Sam (HIT) |  4,633 |  14 |  14 |  1.5 |  35.4 |  97.2 |  79.1
4\. Floogals (Jellyfish Pic.) |  4,163 |  4 |  4 |  1.0 |  92.8 |  99.2 |  99.2
5\. Garfield (Mediatoon) |  4,959 |  13 |  4 |  1.4 |  53.5 |  99.5 |  99.5
6\. Southpark (Viacom) |  5,639 |  25 |  21 |  1.0 |  16.6 |  100.0 |  93.8
7\. Land before time
(NBCU) |  4,795 |  11 |  8 |  1.5 |  54.5 |  98.8 |  98.8
Table 5: Training videos statistics of seven different animation styles in our Evaluation set that were used for building the classifiers. CAST brings down user effort bounding boxes naming by two orders of magnitude, while still creating a sufficient training-set.  Series name |  Characters [#] |  Precision [%] |  Recall [%] |  Accuracy [%] |  F1 [%] |  Support [#]
---|---|---|---|---|---|---
1\. Bob the builder |  6 |  97.4 |  97.4 |  97.4 |  97.4 |  230
2\. Fairly odd parents |  6 |  93.8 |  92.3 |  92.3 |  91.9 |  246
3\. Fireman Sam |  14 |  73.1 |  66.6 |  70.1 |  66.7 |  490
4\. Floogals |  4 |  94.7 |  92.6 |  93.9 |  92.6 |  163
5\. Garfield |  4 |  93.7 |  87.3 |  87.3 |  88.0 |  165
6\. Southpark |  7 |  94.5 |  94.1 |  94.1 |  94.2 |  104
7\. Land before time |  8 |  92.2 |  91.3 |  91.3 |  91.3 |  344
Total |  49 |  91.3 |  88.8 |  89.5 |  88.9 |  1742
Table 6: Results on test videos per style of our Evaluation dataset.  Figure
6: ‘Bob the builder’ confusion matrix (normalized rows).

Experiments: To evaluate the effectiveness of CAST to define specialized
classifiers for animated characters identification, we use the Evaluation set
that combines two episodes of seven different animation series. The animation
styles include CGI, 2D, and Cutout techniques, with characters including
humans, animals, dinosaurs, cars and tractors. For each series, we denote one
training episode to create the dataset and train a classifier using CAST, and
one test-episode, where several character proposals were manually selected and
named for evaluation.

Statistics on CAST results for the seven train-episodes can be found in Table
5 and the Appendix. As can be seen, CAST allows defining classifiers for
animation characters by naming (or discarding) just a few clusters from the
dictionary instead of manual labeling and filtering thousands of proposal
bounding boxes. Cluster Purity is reported both before and after the noisy
cluster filtering under ‘General Purity’ and ‘Relevant Purity’ respectively.
‘Fireman Sam’, staring four firemen figures which wear the same uniform
sometimes clustered together and damage the general purity.

The results on the test-episode of each animation style can be found in Table
6. There are differences in the number of appearances of the different
characters in the seven test-episodes. We randomly picked, on average, 22
instances of each character in the test-episodes, creating 1,742 characters of
ground-truth test data. The total results yielded a mAP, F1-Score, and
Accuracy of 92%, 88%, 89% respectively. The best performing image classifier
was created for the series ‘Bob the builder’ with Accuracy and F1-score of
97.4% and 97.4% (see the confusion matrix in Figure 6, and the matrices of all
series in the Appendix). The least performing image classifier was created for
the series ‘The Land Before Time’, still achieving mAP and F1-score of 82.4%
and 74.2% on 8 characters.

We further tested two series by annotating _all_ proposal bounding boxes in
the test-episodes of the series as ground truth. In this case, many proposals
do not contain one of the characters and are marked as ‘unknown’. In the
Appendix we show the confusion matrices in these cases. The matrices show
almost no confusion among characters, but there are some mis-classification
between characters and non-characters. There are fewer false-positive examples
where non-character proposals are classified as characters and more false-
negative examples. Error analysis on the false-negative cases revealed that
many of them contain character parts such as hands, legs etc. These proposals
were identified and annotated as characters by the human annotator but are
still a challenge for automatic classifiers. This may be an avenue of future
research on identifying partial and occluded animated characters.

We confirmed an underlying assumption that training a classifier on different
animations, consist of different characteristics, such as style, texture,
colors, geometry as well as coarser and fine-grained characteristics, would
yield different classifiers. By allowing a self-supervised training per
animation, we demonstrated an overall improvement. Introducing a novel
animation specific classifier framework, has significantly improved the
classifier’s quality metrics (Purity, F1-Score, etc.). Moreover, it resulted a
substantial reduction of $56.6\%$ in the number of clusters per character.
That is, significant reduction in the annotations process.

Class-per-cluster vs. Class-per-character: The method we used above aggregates
all clusters that share the same label into a unified class for training. An
alternative design can create a class per cluster to train the multi-class
classifier and consolidates the class name results after the prediction. For
instance, if the character Bob from the series ‘Bob the builder’ has two
dictionary entries, then their clusters will be used separately in the
classifier training as Bob-1 and Bob-2, but both will be mapped to Bob after
the prediction. The hypothesis behind this alternative design is that the
feature space might not be connected in terms of the label distribution in the
high dimensional space. Consolidating all labeled data into the same class may
introduce an unnecessary error. Alternatively, the clusters themselves encode
connected (or convex) similarity regions that can represent the character in
some particular settings like wearing specific clothes. To test this
hypothesis a two-tail paired t-Test was conducted to compare the F1-score
change in the class-per-character baseline design vs. the class-per-cluster
alternative hypothesis. The unit of analysis was a character using the
Evaluation dataset (N=49). We found that the our choice of merging clusters
performed 5.5% better (higher) than the alternative (P-value=3.4%). To
conclude, our learned embedding-model seemed to encode coherent regions in a
way that a consolidated class design would leverage better than separated
classes per cluster.

###  5.3 Dense Character Labeling and Statistical Analysis

Once classifiers are defined for a specific animation style (e.g., series),
any new video with the same style can be densely annotated using the
classifiers on every frame. Some results showing these examples are shown in
the supplemental video. Note that these were created without temporal
coherency for tracking - only running the classifiers on every frame and
automatically labeling each character classified.

Using CAST, creative studios and media companies can benefit from a service
that can automatically index and expose information both at a video and series
level. Labeling each frame in the video with the characters that appear allows
to gather important statistics on episodes as well as whole series. This can
assist animation productions in data management especially as more and more
animation content is being created. For example, gender bias has become an
important topic which affects us daily. By knowing the characters’ gender and
running a dense identification we can tell what is the screen time of each
character and indicate, for instance, that the ‘Cars 2’ movie introduces a
gender bias of 78% Male screen time.

##  6 Discussion

We have presented a method to learn a style-specific semantic representation
more suitable for animated content using self-supervision. The self-
supervision is based on multi-object tracking and building a dataset of
triplets to refine a base mapping to the specific style.

Using clustering in the semantic representation space allows us to
automatically build character dictionaries for animation movies, to gather
training sets for multi-class classifiers of characters, and eventually to
automatically perform dense labeling of characters in animation videos. Such a
solution allows users and media companies to analyze, reuse, search, and
monetize animation content much more easily.

Limitations and Suggestions for Further Research: One limitation of CAST is
that it relies on the initial detector for proposals. Although we tuned the
detector for _recall_ , if the detector fails to mark the bounding box of a
character as a proposal, the following steps cannot correct this.

Figure 7: Limitation in clustering characters that wear uniform. The four
firemen cause over 80% of the error.

An underlying assumption of this research is that different animated
characters proposals could be distinguished in the embedding space. However,
since the network embedding still depends on visual features, when a subset of
characters share common visual features, the embedding may still confuse
between them. As a result, the classifiers can also be confused. An example
can be seen in ‘Fireman Sam’ series videos. 14 characters were recognized in
this series, while only four of them are responsible for over 80% of the
classification error. These characters are the firefighters, and the obvious
reason for confusion is their similar uniform (see the confusion matrix in
Figure 7).

Our final character labeling did not take advantage of the temporal coherency
of the video, but rather treated each frame separately. A more elaborate
solution can be defined using smoothing and inference along with tracking.

Style variation in animated content is still extremely large. We refine our
basic representation towards specific animation styles using embedding.
Another possibility would be to combine such representation with domain
adaptation techniques for specialized types of animation (see e.g., Tsubota et
al. [3] on manga comics).

In terms of building the classifiers, our evaluation tested only the two
alternatives of class-per-character and class-per-cluster for building the
training set. There is a whole range of possibilities between these two
extremes that can combine clusters based on some cluster similarity measures
to create the training set for characters.

## Acknowledgements

This research was partly supported by the Israel Science Foundation (grant No.
1390/19) and The Ministry of Innovation, Science and Technology (grant number
16470-3). The authors would like to thank Maria Zontak, Apar Singhal, Lei
Zhang, and Ohad Jassin (Microsoft) for their support of this research [52, 53,
54, 55].

## References

  * [1] Toru Ogawa, Atsushi Otsubo, Rei Narita, Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa.  Object detection for comics using manga109 annotations.  arXiv preprint arXiv:1803.08670, 2018.
  * [2] Jordan Yaniv, Yael Newman, and Ariel Shamir.  The face of art: landmark detection and geometric style in portraits.  ACM Transactions on Graphics (TOG), 38(4):1–15, 2019.
  * [3] Koki Tsubota, Toru Ogawa, Toshihiko Yamasaki, and Kiyoharu Aizawa.  Adaptation of manga face representation for accurate clustering.  In SIGGRAPH Asia 2018 Posters, pages 1–2. Association for Computing Machinery New York NY United States, 2018.
  * [4] Jun Yu and Hock-Soon Seah.  Fuzzy diffusion distance learning for cartoon similarity estimation.  Journal of computer science and technology, 26(2):203–216, 2011\.
  * [5] Tiejun Zhang, Qi Han, Ahmed A Abd El-Latif, Xuefeng Bai, and Xiamu Niu.  2-d cartoon character detection based on scalable-shape context and hough voting.  Inf Technol J, 12(12):2342–2349, 2013.
  * [6] Nhu-Van Nguyen, Christophe Rigaud, and Jean-Christophe Burie.  Comic characters detection using deep learning.  In 2017 14th IAPR international conference on document analysis and recognition (ICDAR), volume 3, pages 41–46. IEEE, 2017.
  * [7] Joseph Redmon and Ali Farhadi.  Yolo9000: better, faster, stronger.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7263–7271, 2017.
  * [8] Wei-Ta Chu and Wei-Wei Li.  Manga facenet: Face detection in manga based on deep neural network.  In Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, pages 412–415, 2017.
  * [9] Azuma Fujimoto, Toru Ogawa, Kazuyoshi Yamamoto, Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa.  Manga109 dataset and creation of metadata.  In Proceedings of the 1st international workshop on comics analysis, processing and understanding, pages 1–5, 2016.
  * [10] Saurav Jha, Nikhil Agarwal, and Suneeta Agarwal.  Bringing cartoons to life: Towards improved cartoon face detection and recognition systems.  arXiv preprint arXiv:1804.01753, 2018.
  * [11] Luke Stark.  Facial recognition, emotion and race in animated social media.  First Monday, 23(9), 2018.
  * [12] Zhengyuan Yang, Yixuan Zhang, and Jiebo Luo.  Human-centered emotion recognition in animated gifs.  In 2019 IEEE International Conference on Multimedia and Expo (ICME), pages 1090–1095. IEEE, 2019.
  * [13] Jing Huo, Wenbin Li, Yinghuan Shi, Yang Gao, and Hujun Yin.  Webcaricature: a benchmark for caricature recognition.  arXiv preprint arXiv:1703.03230, 2017.
  * [14] Y. Zhang, C. Xu, H. Lu, and Y. Huang.  Character identification in feature-length films using global face-name matching.  IEEE Transactions on Multimedia, 11(7):1276–1288, 2009.
  * [15] Rahaf Aljundi, Punarjay Chakravarty, and Tinne Tuytelaars.  Who’s that actor? automatic labelling of actors in tv series starting from imdb images.  In Shang-Hong Lai, Vincent Lepetit, Ko Nishino, and Yoichi Sato, editors, Proceedings of the Asian Conference on Computer Vision - ACCV, pages 467–483, 2016.
  * [16] Mahmoud Azab, Mingzhe Wang, Max Smith, Noriyuki Kojima, Jia Deng, and Rada Mihalcea.  Speaker naming in movies.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2206–2216, 2018.
  * [17] Zhineng Chen, Wei Zhang, Bin Deng, Hongtao Xie, and Xiaoyan Gu.  Name-face association with web facial image supervision.  Multimedia Systems, 25:1––20, 2019.
  * [18] Chunhui Zhu, Fang Wen, and Jian Sun.  A rank-order distance based clustering algorithm for face tagging.  In CVPR 2011, pages 481–488. IEEE, 2011.
  * [19] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823, 2015.
  * [20] Krishna Somandepalli, Rajat Hebbar, and Shrikanth Narayanan.  Robust character labeling in movie videos: Data resources and self-supervised feature adaptation.  IEEE Transactions on Multimedia, 2021.
  * [21] Krishna Somandepalli, Naveen Kumar, Arindam Jati, Panayiotis G Georgiou, and Shrikanth Narayanan.  Multiview shared subspace learning across speakers and speech commands.  In INTERSPEECH, pages 2320–2324, 2019.
  * [22] Shun Zhang, Yihong Gong, and Jinjun Wang.  Deep metric learning with improved triplet loss for face clustering in videos.  In Pacific Rim Conference on Multimedia, pages 497–508. Springer, 2016.
  * [23] Vivek Sharma, Makarand Tapaswi, M Saquib Sarfraz, and Rainer Stiefelhagen.  Self-supervised learning of face representations for video face clustering.  In 2019 14th IEEE International Conference on Automatic Face & Gesture Recognition (FG 2019), pages 1–8. IEEE, 2019.
  * [24] Deepali Aneja, Alex Colburn, Gary Faigin, Linda Shapiro, and Barbara Mones.  Modeling stylized character expressions via deep learning.  In Asian conference on computer vision, pages 136–153. Springer, 2016.
  * [25] Zhanpeng Zhang, Ping Luo, Chen Change Loy, and Xiaoou Tang.  Joint face representation adaptation and clustering in videos.  In European conference on computer vision, pages 236–251. Springer, 2016.
  * [26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778. IEEE, 2016.
  * [27] Xi Shen, Alexei A Efros, and Mathieu Aubry.  Discovering visual patterns in art collections with spatially-consistent feature learning.  In Proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pages 9278–9287, 2019.
  * [28] Basura Fernando, Tatiana Tommasi, and Tinne Tuytelaars.  Location recognition over large time lags.  Computer Vision and Image Understanding, 139:21–28, 2015.
  * [29] James Philbin.  Oxford buildings dataset.  http://www. robots. ox. ac. uk/~ vgg/data/oxbuildings/, 2007\.
  * [30] Yi Zheng, Yifan Zhao, Mengyuan Ren, He Yan, Xiangju Lu, Junhui Liu, and Jia Li.  Cartoon face recognition: A benchmark dataset.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 2264–2272, 2020.
  * [31] K. Somandepalli, N. Kumar, T. Guha, and S. S. Narayanan.  Unsupervised discovery of character dictionaries in animation movies.  IEEE Transactions on Multimedia, 20(3):539–551, 2018.
  * [32] Hayeon Kim, Eun-Cheol Lee, Yongseok Seo, Donghyuck Im, and In-Kwon Lee.  Character detection in animation movies using multi-style adaptation and visual attention.  IEEE Transactions on Multimedia, 2020.
  * [33] Xudong Wang, Zhaowei Cai, Dashan Gao, and Nuno Vasconcelos.  Towards universal object detection by domain attention.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7289–7298, 2019.
  * [34] Xian-Sheng Hua, Lie Lu, and Hong-Jiang Zhang.  Optimization-based automated home video editing system.  IEEE Transactions on circuits and systems for video technology, 14(5):572–583, 2004.
  * [35] Daniel Y Fu, Will Crichton, James Hong, Xinwei Yao, Haotian Zhang, Anh Truong, Avanika Narayan, Maneesh Agrawala, Christopher Ré, and Kayvon Fatahalian.  Rekall: Specifying video events using compositions of spatiotemporal labels.  arXiv preprint arXiv:1910.02993, 2019.
  * [36] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [37] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [38] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In International Conference on Learning Representations, 2015.
  * [39] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7132–7141, 2018.
  * [40] Vassileios Balntas, Edgar Riba, Daniel Ponsa, and Krystian Mikolajczyk.  Learning local feature descriptors with triplets and shallow convolutional neural networks.  In Bmvc, volume 1, page 3, 2016.
  * [41] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In International Conference on Learning Representations, 2019.
  * [42] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  In NIPS-W, 2017.
  * [43] Li Zhang, Yuan Li, and Ramakant Nevatia.  Global data association for multi-object tracking using network flows.  In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2008.
  * [44] Congchao Wang, Yizhi Wang, Yinxue Wang, Chiung-Ting Wu, and Guoqiang Yu.  mussp: Efficient min-cost flow algorithm for multi-object tracking.  Advances in Neural Information Processing Systems, 32:425–434, 2019\.
  * [45] Erling D Andersen and Knud D Andersen.  The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm.  In High performance optimization, pages 197–232. Springer, 2000\.
  * [46] Christopher D Manning, Prabhakar Raghavan, and Hinrich Schütze.  Introduction to information retrieval.  Cambridge university press, 2008.
  * [47] Denilson Alves Pereira, Berthier Ribeiro-Neto, Nivio Ziviani, Alberto HF Laender, and Marcos André Gonçalves.  A generic web-based entity resolution framework.  Journal of the American Society for Information Science and Technology, 62(5):919–932, 2011.
  * [48] Xin-Jing Wang, Lei Zhang, and Wei-Ying Ma.  Duplicate-search-based image annotation using web-scale data.  Proceedings of the IEEE, 100(9):2705–2721, 2012.
  * [49] Coenraad Bron and Joep Kerbosch.  Finding all cliques of an undirected graph (algorithm 457).  Commun. ACM, 16(9):575–576, 1973.
  * [50] F. Cazals and C. Karande.  A note on the problem of reporting maximal cliques.  Theoretical Computer Science, 407(1):564–568, 2008.
  * [51] Mikhail J Atallah and Greg N Frederickson.  A note on finding a maximum empty rectangle.  Discrete Applied Mathematics, 13(1):87–91, 1986.
  * [52] Oron Nir, Maria Zontak, Tucker C. Burns, Apar Singhal, Lei Zhang, Avner Levi, Haim Sabo, Ika Bar-Menachem, Eylon Ami, Ella BenTov, and Anika Zaman.  Semi supervised animated character recognition in video, Apr 2020.
  * [53] Oron Nir, Maria Zontak, Tucker C. Burns, Apar Singhal, Lei Zhang, Avner Levi, Haim Sabo, Ika Bar-Menachem, Eylon Ami, Ella BenTov, and Anika Zaman.  Negative sampling algorithm for enhanced image classification, Apr 2020\.
  * [54] Ohad Jassin, Avner Levi, Oron Nir, and Ori Ziv.  Video segmentation and searching by segmentation dimensions, Apr 2017\.
  * [55] Oron Nir, Royi Ronen, Ohad Jassin, Milan M. Gada, and Mor Geva Pipek.  Training set sufficiency for image analysis, May 2018.

## Appendix

Visualizing the challenge of generalization across animation styles using
semantic learning representations on Figure8 showing characters from our CAST
Evaluation dataset with both dinosaurs, aliens, and tractors produced in CG,
Cutout, and other animation technologies.

Figure 8: All characters of our CAST Evaluation data-set from the series ‘Bob
the Builder’, ‘Fairly Odd Parents’, ’Fireman Sam’, ‘Floogals’, ‘Garfield’,
‘Southpark’, and ‘The Land Before Time’.

##  7 Proposal Clustering

We have analyzed the different alternatives for semantic embedding networks by
evaluating their gain to cluster purity. As stated in the paper, the main goal
of clustering is to reduce the load of user interaction in naming characters
as much as possible. Hence, we prefer cluster purity over other measures. In
Figure 11 we compare the performance of SEResNeXt, ResNet18, and ArtMiner for
cluster purity. We show that our network based on a SEResNeXt backbone with 40
epochs of refinement converge to the top performance. This analysis does not
include the CAST refinement.

Figure 9: Our method’s dictionary output on the SAIL AMCD Evaluation video -
‘Cars 2’. Figure 10: Our method’s dictionary extraction over the CAST
Evaluation video - ‘Southpark’.

##  8 Unsupervised discovery of character dictionaries

To complete the visual picture of dictionary discovery by our method, on both
CAST and SAIL datasets, the ‘Southpark’ dictionary could be seen in Figure 10.
Our method discovers 13 additional characters and considered relevant
exemplars. Another example for a dictionary discovery could be seen in Figure
10

Figure 11: Comparison of various network architectures for cluster purity on
six different character subsets or as named in the figure - datasets. These
character subsets were selected at random from the CAST Test data-set. Each
graph shows the clustering purity measure as a function of the number of
clusters for the different embedding network configurations. The red vertical
line indicates the true number of characters (i.e. the number of clusters
needed if they were all pure). Our network with a SEResNeXt architecture
yields the best results across all data-sets, and this network seems to
converge after 40 epochs.

##  9 Character Identification

We include all of the confusion matrices of the seven test-episodes’
characters from CAST Evaluation data-set in Figure 12.

Figure 12: The Evaluation dataset full Confusion Matrices Figure 13: Negative
examples sampling from a video frame using our algorithm to find largest
rectangles not including character proposals (‘Southpark’).

###  9.1 Negative examples sampling algorithm analysis

Algorithm 1 LER($frame,boxes,min\\_size$)

0: character boxes

0: empty boxes Initialisation : boxes are consolidated and validated

1: if $\neg frame.is\\_valid(min\\_size)$ then

2: return $\\{\\}$

3: end if

4: if $|boxes|==0$ then

5: return $\\{frame\\}$

6: end if

7: $\Theta\leftarrow\\{\\}$

8: $center\leftarrow get\\_centered\\_bbox(boxes)$

9: $subframes\leftarrow split\\_by\\_box(frame,center)$

10: for $\sigma\in subframes$ do

11: $\Theta\leftarrow\Theta\cup LER(\sigma,boxes,min\\_size)$

12: end for

13: return $\Theta$

The suggested method $LER()$ in Algorithm 13 is claimed to have a time
complexity of $O(n^{2})$. The proof is straight forward using the Master
method. As illustrated in the pseudo code, the recursion has four splits into
the top, bottom, left, and right parts of the frame where each is bounded by
approximately one half of the frame size. On each call, the recursion handles
the remaining boxes while filtering those who are outside the sub-frame area
and cropping those that intersect with it. This operation is done in $O(n)$
time. Thus, the recursive work is bounded by the following function:
$T(n)=4T(n/2)+O(n)$ which fits the first case of the Master method:
$n^{\log_{b}a}$ where $a=4;b=2;d=1;$ which puts us in a complexity of
$O(n^{2})$. QED. See a visualization of the resulting output on Figure 13.

###  9.2 Error analysis

We further tested our detector by annotating _all_ proposal bounding boxes in
the test-episodes of the series as ground truth. In this case, many proposals
do not contain one of the characters and are marked as ‘unknown’. Error
analysis on the false-negative cases revealed that many of them contained
character parts such as hands, legs etc. These proposals were identified and
annotated as characters by the human annotator, but are still a challenge for
automatic classifiers (see Figure 14). This may be an avenue of future
research on identifying partial and occluded animated characters and the human
factors in a setup of consistent data annotation in scale.

Figure 14: False-negative examples include many character sub-parts
(Floogals).