A Comparative Study ofRegion Matching Based on Shape Descriptors
for Coloring Hand-drawn Animation
Yoshihiro Kanamori
University of Tsukuba
Email: kanamori@cs.tsukuba.ac.jp
Abstract—The work of coloring hand-drawn animation is doneby manually specifying and painting each closed region in line
drawings. To make this process more efficient, this researchcreates associations between closed regions in line drawingsof adjacent frames, which need to be colored with the samecolor. Feature values are first computed from the shape of eachclosed region, and a cost of associating pairs of closed regions
is computed from these feature values. The combination of
associations that minimizes the total cost is then computed basedon these costs. Three shape descriptors for computing feature
values for each closed region are examined: ellipses, Fourier
descriptors, and shape context; and the accuracy of making
associations using each of them is studied.

I.

I NTRODUCTION

Since the advent of hand-drawn 2D animation, people havebeen fascinated with it. However, even now with the appearance of production-support software, production of handdrawn animation is very labor-intensive and requires many
hours of work. This production includes the following processes: drawing line drawings on paper and scanning themfor each frame, cleaning up the scanned line drawings, andmanually selecting and coloring each of the closed regions in
the line drawings. The work of coloring regions holds promise
for automation because it is simpler than other processes.
To automate the coloring process, we find associations between closed regions in adjacent frames of the animation, andthen can propagate colors to corresponding regions in adjacentframes. Most existing such methods use feature values derived
from characteristic points on the outlines of closed regions tofind associations between closed regions [1], [2]. Examples of
the characteristic points include intersection points and points
where the curvature changes significantly. However, such characteristic points on outlines are quite susceptible to changes
in shape due to motion in the animation, and this reduces theaccuracy of finding associations. In this research, the following
three shape descriptors, which are less susceptible to changes
in outline shape, are compared.
1)
2)
3)

Ellipses roughly approximating the shapes of closed
regions [3],Fourier descriptors expressing low-frequency components of closed-region shape [4], andShape context, representing closed region shape inpolar coordinates and then as a 2D histogram of logdistance and angle [5].

Of these, the method in [3] was originally proposed for
associating closed regions in line drawings of hand-drawn
animation. To associate closed regions, we should consider
the position and scale of each region to differentiate the region
from others within the same frame. On the other hand, Fourier
descriptors [4] and shape context [5] were developed to findshapes similar to a single input shape, such as a logo or roadmarker, so they provide for invariance under transformations
such as translation, scaling and rotation. We thus modify thesedescriptors to take into account geometric transformations infinding associations for the purposes of this research. The
cost of associating two closed regions is derived using theseshape descriptors, and the best matching of closed regions
between two adjacent frames is computed using bipartite graphmatching.
This paper reports on the results of experiments comparing
the accuracy of these methods using real, hand-drawn animation image data.
II.

R ELATED W ORK

A simple method for painting closed regions on multiple
frames all at once is to use an “Onion fill tool”. With thisfunction multiple frames are stacked and all of the closed
regions that include a coordinate specified by the user arecolored with the same color. Such tools are not often usedin practice, because the multiple closed regions to be painted
must be overlapping, and it is not easy to specifying how topaint correctly in one try.
Existing methods make links between closed regions using
outline shapes [1], [2]. Examples of outline shape descriptors
used include coding the outline shape as a text string, orusing an array of so-called dominant points. However, thesemethods are not effective when the shape of the outline
changes significantly.
Another method uses the skeletal structure of objects in theline drawing to find associations between closed regions [6],but skeletal structure can only be applied to articulated characters that have joints.
Sýkora et al. [7] proposed a method of applying color andtexture to hand-drawn animation by matching the positionsof images between successive frames. They also proposed
LazyBrush [8], which they used for coloration. However, their
method uses rigid shape matching [9], so it requires several
seconds to match positions for each successive frame and hasdifficulty find associations when shapes change in a non-rigid
manner.
Generally, there has been much research in the computer
vision field on feature values used for finding such associationsin natural images. However, the images used in this research
are line drawings, which do not contain the kind of shading
information found in natural images, and only shape feature
values obtainable from line drawings are considered applicable. Details on shape feature values can be found in referencessuch as [10]. This research compares the accuracy of finding
associations using shape feature values computed from ellipsebased shape descriptors proposed recently [3], from Fourier
descriptors [4], and from shape context [5].
III.

BASIC P ROCESS OF ATTACHING C ORRESPONDENCES

Regarding the input, line drawings are of course required,but with only the line drawings, there is no way to check if
the coloring was done correctly. Thus, we take colored images
as input and perform a region partitioning by color to obtain
both the correct coloration data and the closed-region data,assuming that each closed region is colored with a single color.
Line drawings are extracted as the lines marking the outlinesof the regions (mainly drawn in black) in the input images.
This research compares three shape descriptors within thesame framework. After region partitioning, associations linking
pairs of closed regions in successive frames are calculated.
Once these associations have been made for all frames, they
are used to create chains of closed regions between frames.
When a color is assigned to a single closed region, the color
is propagated to adjacent frames by following these chains ofassociations.
The following describes in detail how these associations are
made. Let Nf and Nf+1 denote the number of closed regionsin each of two successive frames, f and f + 1. A cost matrix,
A = {aij } is computed. Each element, aij , of this cost matrix
is the cost of associating the closed region i in frame f with theclosed region j in the frame f + 1 (Note i = 1, 2, · · · Nf and
j = 1, 2, · · · Nf +1 ). For A obtained in this way, the Hungarianalgorithm [11] is used to solve for a bipartite graph matching.
If the numbers of closed regions in the two frames are not
the same (i.e., Nf ̸= Nf+1 ), then one or more closed regions
are left without associations. This is understood to mean thata closed region has newly appeared or disappeared in one of
the frames.
This research compares methods that compute the elements, aij , in the cost matrix, A = {aij }, using three different
shape descriptors. These shape descriptors are described below.
IV.

E LLIPTICAL D ESCRIPTOR

The method in reference [3] approximates each closed
region using an ellipse (Fig. 1). The ellipse i approximatingclosed region i is computed from the centroid, ti , and covariance matrix, Ci of the positions of each pixel in closed regioni. Here, the largest and smallest eigenvalues of the covariancematrix, Ci , are designated λmax
and λmin, and their associatediimineigenvectors are emaxande(assumed
to be unit vectors),iirespectively.
Then
the
major
and
minor
axes
of ellipse i are√√max
min emin respectively.
λgiven by λmax
e
and
i
i
i
i

Fig. 1.
Elliptic shape descriptors. In the method from reference [3],associations between closed regions in consecutive frames are made basedon ellipses (red) approximating each closed region.

The association cost, aij , is derived from the orientation,
size and position of the ellipses approximating the two closed
regions, i and j, as follows.
aij = wangle aangle+ wscale ascale+ wpos apos
ij
ij
ij ,

(1)

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

(2)

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

(3)

√
ascale=ij√

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

2
apos
ij = ∥ti − tj ∥ ,(4)where wangle , wscale , and wpos are weightings. Coordinates
ti and tj are normalized by the image size. The values ofscale, and apos
aangleij each approach zero if the orientation,ij , aijsize, and position respectively, of the ellipses approximatingclosed regions i and j approach each other. To increase theaccuracy of associations further, information regarding regions
adjacent to regions i and j is also added to cost aij . This isdone by computing the centroid of the regions adjacent toeach of regions i and j and adding the distances they movethe association cost. The centroid, ni , of the regions adjacent
to closed region i is computed as follows.
()∑∥tk −ti ∥2
α
β
exp
−
tk
2
k
k
k∈{Oi ,i}σi()
ni = ∑,(5)∥tk −ti ∥2k∈{Oi ,i} αk βk exp −σ2iσi = σ0 max ∥tk − ti ∥,
k∈Oi

(6)

where Oi is the set of closed regions adjacent to closed regioni. αk is the area of closed region k. If the area of closed
region k is large, then region k has a greater effect on theposition of the centroid. However, if region k has only small
contact with region i, it is desirable to give region k a smaller
weighting so that the centroid position is not overly affectedby movement of region k. For this reason, we multiply theweighting by a contact rate, βk ∈ [0, 1]. The contact ration
is a value expressing what proportion of the total length ofthe outline of region i is in contact with region k. Further,background regions tend to be large, so if region k is part ofthe background, the computation is done setting αk = αi andtk = ti to reduce its effect. The effects of closed region kalso must be reduced if the position of its centroid is far fromthat of closed region i, so the distance between the centroidsof the two regions is also used as a weighting, with σ0 asthe coefficient. Finally, the association cost aij is computedby adding the term aneighbor
multiplied by the weightingijwneighbor , as in the following equations.
aneighbor= ∥ni − nj ∥2 ,
ij

V.

(8)

F OURIER D ESCRIPTORSThere are many variations of Fourier descriptors. Reference [4] reports on experiments using the following three
Fourier descriptors to search for similar shapes.
•

Centroid distance: computes the distance between the
shape centroid and a point moving along the outline.

•

Changes in curvature: computes changes in the curvature of the outline.

•

Cumulative angle: accumulates the angle between the
shape outline and a tangent.

It finds that the centroid distance produces the best results,
so this research uses a Fourier descriptor based on centroid
distance.
The Fourier descriptor based on centroid distance fromreference [4] is described as follows. The shape outline is first
converted to a polygonal curve line with N segments of equal
length. The distance from each vertex, t (t = 0, 1, . . . , N − 1),to the centroid is rt . Then the n-th Fourier coefficient, un(n = 0, 1, . . . , N − 1) is computed as follows.
(
)
N −1
1 ∑
−j2πntun =rt exp
,
(9)
N t=0
N
where j is the imaginary unit. The DC component, u0 , hasonly a real part, and depends on the scale of the shape. In
reference [4], the following shape feature vector, f , is used toprovide invariance over translation, scaling, and rotation.
()|u1 | |u2 ||uN −1 |f=,,··· ,.
(10)|u0 | |u0 ||u0 |When comparing shapes, the initial K (0 ≤ K ≤ N ) elementsof the feature vector f are selected, and the Euclidean distance
between them is calculated as a degree of similarity.
Computation used in this research: This research also
computes the distance between centroids of two closed regions
to take their relative positions into consideration. The terms inEquation (10) are divided by |u0 | to achieve scaling invariance,
but in this research, relative size is also a consideration, so thisdivision is omitted. As a result, the feature vector, fi , for closed
region i is computed as follows.
fi = (|u0 |, |u1 |, · · · , |uK−1 |) ,(11)

This is the vector of absolute values of K Fourier coefficients.
The association cost, aij for closed regions i and j is computed
as follows.
f ourieraij = wtrans∥ti − tj ∥ + ∥fi − fj ∥,

VI.

(7)

aij = wangle aangle+ wscale ascale+ wpos apos
ij
ij
ij
+wneighbor aneighbor.
ijvalue. The parameter values used were N = 64, K = 4, thef ouriersame as in reference [4], and wtrans= 0.5.

(12)

where ti and tj are the centroids of closed regions i and jf ourier(normalized by the image size), and wtransis a weighting

S HAPE CONTEXT

Shape context [5] is a two-dimensional histogram of thepositions of points relative to one point, in terms of logdistance and angle. For invariance to scaling, each distanceis divided by the average distance before computing the log
distance. Using log distance captures the distribution in moredetail close to the origin, and in less detail farther away.
Log distances and angles are divided into Ndist and Nrad
partitions respectively, producing a histogram with a totalof Nbin = Ndist Nrad bins. To compute the similarity, Cij ,between two histograms, i and j, a χ2 is used.
bin|hi (b) − hj (b)|21 ∑,2hi (b) + hj (b)

N

Cij =

(13)

b=1

where hi (b) and hj (b) are the values in the b-th bins of thenormalized histograms for i and j.
Computation used in this research: As with the Fourier
descriptor case, this research also takes into consideration the
distances between centroids of closed regions and changes
in scale, so distances from the centroid for each region are
not divided by the average distance. The association cost, aij ,between closed regions i and j is calculated by the following
equation.
shape
aij = wtrans∥ti − tj ∥ + Cij ,
(14)
shape
where wtransis a weighting factor.

Parameter values used were number of log-distance partitions, Ndist = 5, number of angle partitions, Nrad = 12, theshapesame as in reference [5], and wtrans
= 4.
VII.

E XPERIMENTAL R ESULTS

The comparison program was implemented in C++ using
OpenGL, GLUT and GLUI and was run on a notebook PC witha 2.3 GHz Intel Core i7-2820QM CPU and 3.2 GB of memory.
The coloring for each region obtained from already colored
images was used as correct data. In experiments, associations
were first created using each of the shape descriptors. Color
was then applied to a single frame, propagated automaticallyto adjacent frames, and the extent to which color was appliedcorrectly was evaluated quantitatively. The frame with the mostclosed regions was selected as the frame to begin coloring.
When new closed regions appear in a frame, those regions
remain without associations, so a frame with as many regions
as possible was selected to minimize the number of regions
left without color.
Experimental results are shown in Figs. 3 and 4. The
images are trimmed to accommodate available space. Associations were applied using the ellipse, Fourier, and shape context
descriptors. Closed regions that were assigned the wrong color
are shown in red, and regions that had no association andwere not assigned a color are shown in green. The numbersof errors and unassociated regions is shown. For these results,
the correctness rate is defined as the proportion of the number
closed regions that are colored correctly, and this is graphedin Fig. 2. For each of Figs. 3 and 4, the Fourier and shapeTABLE I.

C OMPUTATION TIMES ( S ) FOR MAKING ASSOCIATIONS FOR
DIFFERENT IMAGE SIZES AND NUMBERS OF FRAMES . C OMPUTATIONTIMES INDICATE TIME REQUIRED TO MAKE ASSOCIATIONS FOR ALL
FRAMES .
Fig. (Image size, no. of frames) Elliptic Fourier descriptor Shape context
Fig. 3 (3614×2053, 14 images) 0.11
0.056
0.032
Fig. 4 (3614×2053, 57 images) 0.51
0.32
0.19

methods only support one-to-one associations between closed
regions, so cases requiring one-to-many associations, in which
new closed regions appear due to screening, cannot be handled.
Accuracy drops quickly for cases when such screening occurs
often. In the future, methods that handle the effects of such
screening well need to be developed.
ACKNOWLEDGMENT

context descriptors produced slightly higher accuracy than theellipse descriptor.
Computation times are shown in Table I. Region partitioning was implemented with the same process for all threemethods and required 2.3 s and 8.1 s respectively for each of
the figures. Although the time required for region partitioning
increased with the image size, making the associations wasvery fast in all cases. Results also showed that the Fourier
descriptor and shape context were both faster than the ellipse
method .
Considering the graphs in Fig. 2, all of the results showeda rapid drop in correctness in the frames before and after
the frame to which color was applied, which had the mostclosed regions. The frames with the most regions tend to be
cut up by objects like hair, hands, or arms, which increase
the number of closed regions. Such multiple closed regions
caused by screening should really be handled by making theassociation with a single closed region before partitioning. In
other words, one-to-many associations are needed for closed
regions. However, the current framework with bipartite graphmatching cannot handle one-to-many associations and leaves
closed regions without associations. This results in a drop incolorization accuracy. This result shows that making one-toone associations between closed regions a limitation in theapproach itself.
VIII.

C ONCLUSION AND F UTURE I SSUESThis research has studied a method toward automating thework of coloring frames in the current production of 2D handdrawn animations. Three shape descriptors for closed regions
were used, based on ellipses, Fourier descriptors, and shapecontext. The cost of making associations between regions
based on each of these was computed, and the associations
were made using bipartite graph matching. Experimental results showed that both the Fourier and shape context descriptors produced better results than the ellipse descriptor, bothfor accuracy and computation speed. However, the current

The author would like to express sincere gratitude to theanimation company that provided the real animation data usedin this paper. The copyright of the image data is reserved by
the animation company.
R EFERENCES[1] J. S. Madeira, A. Stork, and M. H. Gross, “An approach to computersupported cartooning,” The Visual Computer, vol. 12, no. 1, pp. 1–17,
1996.
[2] P. Garcia Trigo, H. Johan, T. Imagire, and T. Nishita, “Interactive region
matching for 2D animation coloring based on feature’s variation,” IEICE
Transactions (E92-D), no. 6, pp. 1289–1295, 2009.
[3] Y. Kanamori, “Region matching with proxy ellipses for coloring
hand-drawn animations,” in SIGGRAPH Asia 2012 Technical
Briefs, ser. SA ’12, 2012, pp. 4:1–4:4. [Online]. Available:
http://doi.acm.org/10.1145/2407746.2407750[4] D. Zhang and G. Lu, “A comparative study of fourier descriptors forshape representation and retrieval,” in Proc. of 5th Asian Conference
on Computer Vision (ACCV). Springer, 2002, pp. 646–651.
[5] S. Belongie, J. Malik, and J. Puzicha, “Shape matching and object
recognition using shape contexts,” IEEE Trans. Pattern Anal. Mach.
Intell., vol. 24, no. 4, pp. 509–522, Apr. 2002.
[6] J. Qiu, H. S. Seah, and F. Tian, “Auto coloring with character registration,” in Proceedings of the 2006 international conference on Game
research and development, ser. CyberGames ’06, 2006, pp. 25–32.
[7] D. Sýkora, M. Ben-Chen, M. Čadı́k, B. Whited, and
M. Simmons, “Textoons: practical texture mapping for handdrawn cartoon animations,” in Proceedings of the ACM
SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation
and Rendering, ser. NPAR ’11, 2011, pp. 75–84. [Online]. Available:
http://doi.acm.org/10.1145/2024676.2024689[8] D. Sýkora, J. Dingliana, and S. Collins, “LazyBrush: Flexible painting
tool for hand-drawn cartoons,” Computer Graphics Forum, vol. 28,
no. 2, pp. 599–608, 2009.
[9] D. Sýkora, J. Dingliana, and S. Collins, “As-rigid-as-possible image
registration for hand-drawn cartoon animations,” in Proceedings ofthe 7th International Symposium on Non-Photorealistic Animation and
Rendering, ser. NPAR ’09, 2009, pp. 25–33. [Online]. Available:
http://doi.acm.org/10.1145/1572614.1572619[10] M. Yang, K. Kpalma, and J. Ronsin, “A Survey of Shape Feature
Extraction Techniques,” in Pattern Recognition, 2008, pp. 43–90.
[11] C. Papadimitriou and K. Stieglitz, Combinatorial optimization : algorithms and complexity. Prentice-Hall, 1982.

85

Fourier descriptor

75

Shape context

65

Correctness rate (%)

Correctness rate (%)

Elliptic

95

98

Elliptic
Fourier descriptor
Shape context

88
78
68
58
48

55
38

45
28

35

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

6

11

16

21

26

31

36

41

Frame number

46

51

56

Frame number(a) Correctness rates for Fig. 3(b) Correctness rates for Fig. 4

Fig. 2. Graphs of correctness rates (%) for the examples of automatic coloring in Figs. 3 and 4. The frames with the most closed regions in each were the
3-rd, and 13-th, respectively, so the correctness rate for those frames is 100%.

2-nd frame

4-th frame

14-th frame

68 regions

59 regions

66 regions

50 regions

23 errors (13 unassociated)

15 errors (4 unassociated)

13 errors (4 unassociated)

28 errors (3 unassociated)

24 errors (4 unassociated)

13 errors (0 unassociated)

5 errors (0 unassociated)

26 errors (0 unassociated)

17 errors (8 unassociated)

9 errors (0 unassociated)

3 errors (0 unassociated)

26 errors (2 unassociated)

Shape context

Fourier descriptor

Elliptic

Input images

1-st frameFig. 3. Results of experiments using a 14-frame sequence. Red indicates closed regions where an incorrect color was assigned, and green indicates closed
regions where no association was made, so no color was assigned. Color was assigned to the 3-rd frame, and the results from the 1-st, 2-nd, 4-th, and 14-thcframes only are shown here. ⃝2006
Nibariki/GNDHDDT.

11-th frame

12-th frame

14-th frame

15-th frame

57-th frame

70 regions

101 regions

107 regions

119 regions

98 regions

84 regions

Elliptic

Input images

1-st frame

11 errors (0 unassociated) 56 errors (0 unassociated) 24 errors (0 unassociated) 29 errors (0 unassociated) 57 errors (11 unassociated)

30 errors (0 unassociated)

47 errors (0 unassociated) 47 errors (0 unassociated) 20 errors (0 unassociated) 19 errors (0 unassociated)

22 errors (2 unassociated)

32 errors (0 unassociated) 35 errors (0 unassociated) 16 errors (0 unassociated) 19 errors (0 unassociated) 49 errors (27 unassociated)

Fourier descriptor

40 errors (0 unassociated)

Shape context

48 errors (5 unassociated)

Fig. 4. Results of experiments using a 57-frame sequence. Red indicates closed regions where an incorrect color was assigned, and green indicates closed
regions where no association was made, so no color was assigned. Color was assigned to the 13-th frame, and the results from the 1-st, 11-th, 12-th, 14-th,c
15-th, and 57-th frames only are shown here. ⃝2010
GNDHDDTW.