Graph Matching based Anime Colorization
with Multiple References
Akinobu Maejima∗

Hiroyuki Kubo

Takuya Funatomi

Tatsuo Yotsukura

OLM Digital, Inc.
IMAGICA GROUP, Inc.

NAIST

NAIST

OLM Digital, Inc.
IMAGICA GROUP, Inc.

Satoshi Nakamura

Yasuhiro Mukaigawa

NAIST

NAISTline drawings

referencescolorized results©Nintendo, Creatures, GAME FREAK, TV Tokyo, ShoPro, JR Kikaku, ©Pokémon

Figure 1: Example of automatic colorization for line drawings using two reference images.

ABSTRACT
We propose a graph matching-based anime-colorization methodfrom line drawings using multiple reference images. A graph structure of each frame in an input line drawing sequence helps to findcorrespondences of regions to be colorized between frames. However, it is difficult to find precise correspondences of whole frames
only from a single reference image, because the graph structure
tends to change drastically during the sequence. Therefore, ourmethod first finds an optimal image from multiple reference images
according to a cost function that represents shape similarity between nodes and compatibility of node pairs. While it is necessaryto prepare several manually colored reference images, our method
is still effective in reducing the effort required for colorization inanime production. We demonstrate the effectiveness of our method
using actual images from our production.

CCS CONCEPTS• Computing methodologies → Image processing;∗ e-mail: akinobu.maejima@olm.co.jp

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, orrepublish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
Conference’17, July 2017, Washington, DC, USA© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
https://doi.org/http://dx.doi.org/10.1145/8888888.7777777

KEYWORDS
anime, colorization, graph matching, multiple references
ACM Reference Format:
Akinobu Maejima, Hiroyuki Kubo, Takuya Funatomi, Tatsuo Yotsukura,Satoshi Nakamura, and Yasuhiro Mukaigawa. 2019. Graph Matching based
Anime Colorization with Multiple References. In Proceedings of ACM Conference (Conference’17). ACM, New York, NY, USA, Article 1, 2 pages. https://doi.org/http://dx.doi.org/10.1145/8888888.7777777

1

INTRODUCTION

Traditional manual colorization process in 2D anime production isa tedious work even under the support of software such as [CELSYS2008]. Thus, automatic colorization for line drawings is required tostreamline a process of anime production. Previous work for automatic colorization can be categorized into two approaches; deeplearning based [Furusawa et al. 2017; Ramassamy et al. 2018] andreference graph matching approach [Sato et al. 2014]. For the former, collecting a large dataset extracting from previously released
manually created animation is a reasonable option, however, it is
not very practical to collect larger dataset including sub characterswhich rarely appear in the animation. For the latter approach, nolarge amount of data collection is required, however, colorization often fails in case the graph structure changes drastically according to
the character animation. Therefore, it is difficult to find precise correspondences of whole frames only from a single reference image.
Thus, we propose an algorithm which allows multiple reference
images. In this method, regions to be colorized are represented
as nodes in a graph structure. To find an optimal image to be thereference for each line drawing sketches of an input sequence frommultiple reference images, we utilize the cost function which represents similarity between nodes and edge pairs of two graphs fromConference’17, July 2017, Washington, DC, USA

Maejima, et al.
Where, σ1 represents a standard deviation of Ci, j . We also define theqedge affinity matrix Kq whose element kk,l represents similarity
rtof edge pair from Gm and Gn as follows.
q

Target line drawing

Score = 0.66

0.76

0.82

kk,l = exp(−ground truth

Target line drawing

Score = 0.55

0.89

0.95

ground truth

Target line drawingScore = 0.66

0.82

0.84

ground truth©Nintendo, Creatures, GAME FREAK, TV Tokyo, ShoPro, JR Kikaku, ©Pokémon

Figure 2: Result of Colorization. Each score for the selectedreference exhibits colorization accuracy well.

reference and target images. In Fig. 1, a part of the automatic colorized images by our method from multiple reference images aredisplayed. In this sequence, the graph structures of the odd number
frames and even number frames are lightly difference. Therefore,
more than two reference images are necessary to find the better
correspondence. Since our method allows to be used multiple images as reference images, this figure demonstrates the efficiency of
our method for a practical anime-production pipeline.

2COLORIZATION PROCEDUREr } has already conAssuming that a reference graph collection {Gmr } is composed by nodes
structed beforehand. Each graph in {Gmcorresponding regions acquired from reference images of a target
character via segmentation algorithm [Zhang et al. 2009] and edges
connecting between nodes. Given a target image sequence, a target
graph collection {Gnt } for this sequence are constructed by thesame manner for the reference graph construction. Then, the graphmatching problem for all pair of reference and target graphs in bothcollections is solved to choose an optimal reference graph for eachtarget image. Finally, colorization is performed by filling regionswith colors assigned to nodes on the optimal reference graph frameby frame.

3OPTIMAL REFERENCE SELECTION

To find an optimal reference graph, we need to define a cost function
so that it exhibit the performance of colorization, and optimize it. Letr and aus consider an affinity matrix K between a reference graph Gm
target graph Gnt in the same fashion as [Zhou and De la Torre 2016].
pWe design a node affinity matrix Kp whose element ki, j representsrshape similarity between regions corresponding i-th node on Gm
and j-th node on Gnt using Shape Context Ci, j [Belongie et al. 2001].
Ci,2 jpki, j = exp(− 2 )σ1(1)2dk,l2ak,l2σ2

2σ32

−2)

(2)

Where dk,l = (dk − dl )/max(dk , dl ). dk means length of the edge kr and d is that of the edge l on the Gt . Also, we introduce
on the Gmlnmagnitude relationship of areas between nodes connecting edgek and edge l (Each edge stars from node s to terminating node e.);ak,l = (ask ale − als ake )/max(ask ale , als ake ) as same manner [Sato et al.
2014]. σ2 and σ3 represents a standard deviation of dk,l and ak,lrespectively. We solve this graph matching problem by Spectral
Matching [Leordeanu and Hebert 2005] with affinity matrix K.
A score can be obtained from the quadratic form xT Kx with thematching result x. Note that, we set σ1 = σ2 = 0.5 and σ3 = 1 forall experiments. According to score for each reference, the optimalreference can be selected for each frame of the target sequence.
The relationship between the scores and the colorized results isshown in Fig. 2. The figure clearly shows that the method colorizes
more precisely, the scores gets closer to 1.0. Therefore, the score
should presents the confidence of the colorized results.

4RESULT AND DISCUSSIONAs shown in Fig. 1, our method works for line drawings from an
actual production pipeline. In case of rigid or nearly rigid transformation, only a single reference image is to be used. However,under the large deformation or missing/appearing parts, the performance obviously degrades because the graph structure is drasticallychanged compared with a reference. Thanks to the multiple reference images, our method can find an optimal reference image
even in such situation. In the future, by introducing a latest graphmatching technique like [Zhou and De la Torre 2016], colorization
performance would be improved.

REFERENCES
Serge Belongie, Jitendra Malik, and Jan Puzicha. 2001. Shape Context: A New Descriptorfor Shape Matching and Object Recognition. In Advances in Neural Information
Processing Systems 13, T. K. Leen, T. G. Dietterich, and V. Tresp (Eds.). 831–837.
Inc. CELSYS. 2008. PaintMan. http://www.retasstudio.net/products/paintman/. (2008).
Chie Furusawa, Kazuyuki Hiroshiba, Keisuke Ogaki, and Yuri Odagiri. 2017. Comicolorization: Semi-automatic Manga Colorization. In SIGGRAPH Asia 2017 TechnicalBriefs (SA ’17). 12:1–12:4.
Marius Leordeanu and Martial Hebert. 2005. A Spectral Technique for Correspondence
Problems Using Pairwise Constraints. In Proceedings of the Tenth IEEE International
Conference on Computer Vision - Volume 2 (ICCV ’05). 1482–1489.
Sophie Ramassamy, Hiroyuki Kubo, Takuya Funatomi, Daichi Ishii, Akinobu Maejima,
Satoshi Nakamura, and Yasuhiro Mukaigawa. 2018. Pre- and Post-processes for
Automatic Colorization Using a Fully Convolutional Network. In SIGGRAPH Asia
2018 Posters (SA ’18). 70:1–70:2.
Kazuhiro Sato, Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. 2014.
Reference-based Manga Colorization by Graph Correspondence Using Quadratic
Programming. In SIGGRAPH Asia 2014 Technical Briefs (SA ’14). 15:1–15:4.
Song-Hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, and Ralph R. Martin. 2009.
Vectorizing Cartoon Animations. IEEE Transactions on Visualization and Computer
Graphics 15, 4 (2009), 618–629.
Feng Zhou and Fernando De la Torre. 2016. Factorized Graph Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 38, 9 (2016), 1774–1789.