Region Matching with Proxy Ellipses for Coloring Hand-Drawn Animations
Yoshihiro Kanamori∗
University of Tsukuba

Abstract
Hand-drawn animations are fascinating due to their expressiveness.
In the production pipeline, manual coloring of line drawings is tedious and labor-intensive. We propose a method for accelerating
the coloring step by matching corresponding regions in successiveframes and propagating the same color to the regions. We derive amatching cost between two regions based on ellipses that approximate the orientations, scales and positions of regions. Such ellipses
are insensitive to frequent changes of the region-contour shape unlike contour-based features used in previous methods. Our methodfinds an optimal matching that minimizes the total matching costquickly. We demonstrate the speed and the matching accuracy of
our method with comparisons.
CR Categories:
I.3.3 [Computer Graphics]: Picture/Image
Generation—Bitmap and framebuffer operations
Keywords: cartoon animation, colorization, region tracking, bipartite graph matching1

Introduction

Hand-drawn 2D cartoon animations have fascinated and inspired
people over the decades. Unfortunately, making a hand-drawn animation film is still quite time-consuming and labor-intensive evenafter assisting software tools appeared. Such making process includes the following steps; a line drawing is manually drawn on asheet of paper and scanned for each frame. The scanned frames arecleaned up, and then colorized by manually painting each closed
region in the line drawing with an appropriate color selected froma predefined color palette. Because the coloring step requires little
creativity, automating the step is highly demanded.
A common strategy for automating the coloring step is to find thecorrespondence of regions between successive frames, and thenpropagate the same color to the corresponding regions. We follow this strategy as well. Many existing techniques attempt tofind region-wise correspondence using the contour of each region [Madeira et al. 1996; Garcia Trigo et al. 2009]. However, contour-based features become inaccurate frequently due tochanges on the contour shapes, which decreases the efficiency ofcontour-based methods. Instead we propose an alternative region
descriptor insensitive to contours’ changes; we use an ellipse thatapproximate the orientation, scale and position of each region. The
ellipse is calculated via the centroid and the covariance matrix ofpixel positions in each region. We calculate a matching cost foreach pair of regions in successive frames, and find an optimal
matching that minimizes the total matching cost by solving a bipartite graph matching.
∗ e-mail:kanamori@cs.tsukuba.ac.jp

The advantages of our method are as follows: 1) better matching accuracy to reduce the number of regions that must be coloredmanually, 2) no additional user input to be integrated in the existing production pipeline seamlessly, and 3) quick response so thatthe user can correct matching misses interactively. We demonstratethese advantages through several experiments and comparisons.

2 Related WorkA simple approach to color regions in multiple frames simultaneously is the classical onion fill, where semi-transparent frames arestacked and the user specifies a seed point contained in all the regions that the user wants to color. This requires that all regions to
be colored to have a common overlapping area. The fact that this iserror-prone and not easy in general makes animation studios avoid
this method.
Several methods such as [Madeira et al. 1996; Garcia Trigo et al.
2009] attempt to find region-wise correspondences between two
successive frames. Contour descriptors such as the string encodingof gradients and dominant points are often used in these methods,
but they are not effective when the region contours change largely
from one frame to the next one. Skeletons extracted from regionsor specified manually [Qiu et al. 2006] can also be used for matching regions. However, skeletons limit the matching to articulatedcharacters.
Sýkora et al. [2011] proposed a method for coloring and texturing a
cartoon animation sequence by registering a pair of frames followedby painting with LazyBrush [Sýkora et al. 2009b]. However, theiras-rigid-as-possible shape matching method [Sýkora et al. 2009a]needs several seconds for each pair of frames and also suffers fromanimations where regions undergo non-rigid motions.
Our method employs region-wise matching using proxy ellipses as
shape descriptors that are insensitive to changes of contour shapes.
The calculation of ellipses and matching is very fast for the wholeframes, providing instant feedback to the user. Our method does not
require any other user input than those in the traditional pipeline,i.e., click-and-paint operations, and thus can be seamlessly integrated into the production process.
In computer vision, elliptical descriptors are also used for matching
to describe Affine transforms together with high-dimensional feature vectors including SIFT. An example is [Sivic and Zisserman2003]. Such ellipses and feature vectors are calculated from therich texture information, which is not available in 2D cartoon animations. We thus propose new methods for calculating ellipses andmatching costs.

3 Our Region Matching Method
Given frames of line drawings (bitmap images), we first extract
regions by applying a seed fill algortihm. In case that a region
is not closed, it is fixed manually or filled using a sophisticatedmethod [Sýkora et al. 2009b]. Our method then finds the correspondence between a pair of regions in two successive frames. Specifically, we solve the matching problem as a bipartite graph matching
to minimize the total cost for matching. The key idea of our algorithm is to derive a cost function using an ellipse that approximatesthe orientation, scale and position of each region (Figure 1).

Table 1: Computational times (seconds) with different image sizes(pixel) and numbers of frames. Segmentation includes analysis ofneighboring regions.
ImagesFig. 2 (320×280)
Fig. 3 (410×240)
Fig. 4 (1024×768)# Frames
5
4
8

Segmentation
0.017
0.045
0.86

Matching
0.010
0.017
0.038

Total
0.027
0.062
0.89

added to the matching cost aij .
aneighbor= ∥ni − nj ∥2 .
ij
Figure 1: Region-wise matching between two successive frames iscalculated based on a proxy ellipse (red) for each region.

Ellipse i of region i is calculated via the centroid ti and the covariance matrix Ci of pixel positions in region i. Let the larger
and smaller eigenvalues of Ci be λmax
and λmin, and the correi
i
max
min
sponding eigenvectors be√ei
and ei . √The longer and shorter
axes of ellipse i are then λmax
emax
and λminemin. Note thatiiiieigenvalues and eigenvectors can be calculated easily in 2D case.
Suppose two successive frames f and f + 1 have Nf and Nf+1
regions, respectively. To find the correspondence, we calculate acost matrix A = {aij } where each element aij corresponds to amatching cost between region i in frame f and region j in frame
f +1 (where i ∈ {1, 2, · · · , Nf } and j ∈ {1, 2, · · · , Nf+1 }). We
derive a matching cost aij from the differences between regions iand j in terms of the orientations, scales and positions as follows.
aij = wangle aangle+ wscale ascale+ wpos apos
ij
ij
ij ,

(1)

aangle= cos−1 (emax· emax
),
i
j
ij

(2)

√
ascale=ij

max{λmax
,λmax
}
i
j
min{λmax
,λmax
}
i
j

√

+

max{λmin
,λmin
}
i
j
min{λmin
,λmin
}
i
j

2
apos
ij = ∥ti − tj ∥ ,− 2, (3)(4)

where wangle , wscale , and wpos are weights. The positions ti andtj are normalized with the image size. We design the terms aangle
ij ,pos
ascale
and
a
so
that
they
becomezero
ifregions
i
and
j
share
ij
ij
ellipses with the same orientation, scale and position.
To improve the matching accuracy, we also integrate the neighborhood information of regions i and j into the matching cost aij . We
simply consider a centroid of neighboring regions and measure thedistance between centroids in two successive frames. Neighboring
centroid ni for region i is calculated as follows.
∑k∈{Oi ,i} αk βk exp{−

ni = ∑∥tk −ti ∥2
} tk
σi2

k∈{Oi ,i} αk βk exp{−∥tk −ti ∥2}σi2σi = σ0 max ∥tk − ti ∥,
k∈Oi

,

(5)
(6)

where Oi denotes the adjacent (one-ring) neighbors of region i. αkis the area of region k. To reduce the influence of neighboring region k that is large but contacting with region i only slightly, we
multiply contact ratio βk ∈ [0, 1] which represents how much theboundary of region i contacts with region k. If region k is the background, we set αk = αi and tk = ti . We also consider the distance
between regions k and i as a weight. σ0 is a coefficient. Finally,
the following term aneighbor
multiplied by a weight wneighbor isij(7)With the cost matrix A, we solve a bipartite graph matching using the Hungarian algorithm. If the numbers of regions are not thesame, i.e., Nf ̸= Nf+1 , some regions are left unmatched, whichmeans that the regions do not have correspondence because they
appear or disappear in either frame.
After matching among all frames is done, each region is connected
in a chain of correspondence between frames. When the user assigns a color to a region, the color is propagated to the regions insubsequent frames, using chains as in [Garcia Trigo et al. 2009].
Although the user has an option to edit the chains of wrong correspondence easily as done in [Garcia Trigo et al. 2009], we justcolor each region independently as usual in the current production
pipeline to avoid additional manipulation of chains.

4 Results
We implemented our prototype using C++ and OpenGL, and conducted experiments on a laptop with an Intel Core i7-2820QM CPU
2.30GHz and 3.2GB RAM. The computational times are summarized in Table 1. For quantitative evaluations, we count the minimum number of regions that were assigned manually because of
first appearance or incorrect matching; with better matching, moreregions would be assigned with correct colors automatically. In theexperimental results, each region was initially assumed as background and chains were not modified during manual coloring.
Figure 2 shows our result with the girl example of [Garcia Trigoet al. 2009]. After manual coloring of the first frame (14 regions except for background), colors were propagated along chains.
Whereas about seven color assignments per frame were requiredwith [Garcia Trigo et al. 2009]’s matching result, ours required
for just three regions per frame. Considering that assignments for
newly appeared regions such as the mouth in the second frame andthe eyes in the third frame were mandatory, our matching quality is
high.
Figure 3 shows our result with the tiger example of [Qiu et al. 2006].
Whereas [Qiu et al. 2006] require manual specification of a skeleton, our method does not require operations other than color assignments. The numbers of regions are 37, 36, 40 and 34 except
for background. More than 80% of regions in each frame were assigned with correct colors.
Figure 4 shows our result with a more practical example. Fromthe second frame, more than 82% of regions in each frame wereassigned with correct colors.

5 Conclusion
In this work, we have proposed a method for semi-automating thecoloring step in the current production pipeline of 2D cartoon animations. Our method constructs region-wise correspondence between two successive frames based on a cost function derived from

Figure 2: Coloring of the girl example of Garcia Trigo et al. Top row: our matching result. Regions in the same pseudo color are in the same
chain. Middle row: our coloring result. From the second to the fifth frame, the numbers of regions assigned with colors manually were 3, 4,
3 and 3 (highlighted in red). Bottom row: Garcia Trigo et al.’s matching result. 7, 9, 9 and 3 regions were manually colored, respectively.

References
G ARCIA T RIGO , P., J OHAN , H., I MAGIRE , T., AND N ISHITA ,T. 2009. Interactive region matching for 2D animation coloring
based on feature’s variation. IEICE Transactions (E92-D), 6,
1289–1295.
M ADEIRA , J. S., S TORK , A., AND G ROSS , M. H. 1996. An approach to computer-supported cartooning. The Visual Computer12, 1, 1–17.
Q IU , J., S EAH , H. S., AND T IAN , F. 2006. Auto coloring withcharacter registration. In Proceedings of the 2006 international
conference on Game research and development, CyberGames’06, 25–32.
S IVIC , J., AND Z ISSERMAN , A. 2003. Video Google: A text retrieval approach to object matching in videos. In Proceedings ofthe International Conference on Computer Vision, vol. 2, 1470–
1477.
Figure 5: Blue and red lines to specify highlighted and shadowed
regions (image by courtesy of CELSYS Inc.)a proxy ellipse that approximates the orientation, size and positionof each region. Our method yields good matching results quickly
without requiring additional operations other than click-and-paintoperations in the current production pipeline.

In future work, we would like to enhance the matching accuracy.
One option is to manage topological changes of regions, i.e., split
and fusion, mainly caused by occlusions. We also would like tohandle blue and red lines that are used in production to specify
highlighted and shadowed regions in line drawings (Figure 5).

S ÝKORA , D., D INGLIANA , J., AND C OLLINS , S. 2009. Asrigid-as-possible image registration for hand-drawn cartoon animations. In Proceedings of the 7th International Symposium on
Non-Photorealistic Animation and Rendering, NPAR ’09, 25–
33.
S ÝKORA , D., D INGLIANA , J., AND C OLLINS , S. 2009. LazyBrush: Flexible painting tool for hand-drawn cartoons. Computer Graphics Forum 28, 2, 599–608.
S ÝKORA , D., B EN -C HEN , M., Č AD ÍK , M., W HITED , B., ANDS IMMONS , M. 2011. Textoons: practical texture mapping forhand-drawn cartoon animations. In Proceedings of the ACM
SIGGRAPH/Eurographics Symposium on Non-Photorealistic
Animation and Rendering, NPAR ’11, 75–84.

Figure 3: Coloring of the tiger example of Qiu et al. Top row: our matching result. Whereas Qiu et al. require manual specification of askeleton, our method does not. Bottom row: our coloring result with manual color assignments (highlighted in red). From the second to thefourth frame, the numbers of manual color assignments were 5, 8 and 7. Each frame is trimmed for display.

frame #1 (35 regions)frame #2 (40 regions)frame #3 (45 regions)frame #4 (46 regions)frame #5 (38 regions)frame #6 (42 regions)frame #7 (42 regions)frame #8 (43 regions)frame #1 (35 regions, 32 assigned)

frame #2 (40 regions, 7 assigned)

frame #3 (45 regions, 8 assigned)

frame #4 (46 regions, 4 assigned)

frame #5 (38 regions, 3 assigned)

frame #6 (42 regions, 6 assigned)

frame #7 (42 regions, 3 assigned)

frame #8 (43 regions, 0 assigned)

Figure 4: Coloring of a boy sequence (images by courtesy of CELSYS Inc.) First and second rows: our matching result. Third and fourthrows: our coloring results. The numbers of regions as well as manual color assignments are listed in each frame.