Journal Home > Volume 9 , Issue 3
Computational Visual Media 2023, 9(3): 633-656 https://doi.org/10.1007/s41095-022-0298-0
Research Article | Open Access | Issue | Published: 29 April 2023

Shape correspondence for cel animation based on a shape association graph and spectral matching

Show Author's Information Shaolong Liu1,  Xingce Wang1,  Xiangyuan Liu1,  Zhongke Wu1( ),  Hock Soon Seah2
Beijing Normal University, Beijing 100875, China
Nanyang Technological University, Singapore 639798, Singapore
Keywords:
cel animation, shape correspondence, shape association graph (SAG), spectral matching, quadratic assignment, Kendall shape space
Cite this article:
Liu S, Wang X, Liu X, et al. Shape correspondence for cel animation based on a shape association graph and spectral matching. Computational Visual Media, 2023, 9(3): 633-656. https://doi.org/10.1007/s41095-022-0298-0
Download citation
EndNote(RIS)
BibTeX

592

Views

28

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes. We formulate the correspondence problem as an adapted quadratic assignment problem, which comprehensively considers both the intrinsic geometric and topology of regions to find the globally optimal correspondence. To simultaneously represent the geometric and topological similarities between regions, we propose a shape association graph (SAG), whose node attributes indicate the geometric distance between regions, and whose edge attributes indicate the topological distance between combined region pairs. We convert topological distance to geometric distance between geometric objects with topological features of the pairs, and introduce Kendall shape space to calculate the intrinsic geometric distance. By utilizing the spectral properties of the affinity matrix induced by the SAG, our approach can efficiently extract globally optimal region correspondences, even if shapes have inconsistent topology and severe deformation. It is also robust to shapes undergoing similarity transformations, and compatible with parallel computing techniques.


menu
Abstract
Full text
Outline
About this article

Shape correspondence for cel animation based on a shape association graph and spectral matching

Show Author's information Shaolong Liu1, Xingce Wang1, Xiangyuan Liu1, Zhongke Wu1( ), Hock Soon Seah2
Beijing Normal University, Beijing 100875, China
Nanyang Technological University, Singapore 639798, Singapore

Abstract

We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes. We formulate the correspondence problem as an adapted quadratic assignment problem, which comprehensively considers both the intrinsic geometric and topology of regions to find the globally optimal correspondence. To simultaneously represent the geometric and topological similarities between regions, we propose a shape association graph (SAG), whose node attributes indicate the geometric distance between regions, and whose edge attributes indicate the topological distance between combined region pairs. We convert topological distance to geometric distance between geometric objects with topological features of the pairs, and introduce Kendall shape space to calculate the intrinsic geometric distance. By utilizing the spectral properties of the affinity matrix induced by the SAG, our approach can efficiently extract globally optimal region correspondences, even if shapes have inconsistent topology and severe deformation. It is also robust to shapes undergoing similarity transformations, and compatible with parallel computing techniques.

Keywords: cel animation, shape correspondence, shape association graph (SAG), spectral matching, quadratic assignment, Kendall shape space

References(35)

[1]
Jiang, J. E.; Seah, H. S.; Liew, H. Z.; Chen, Q. A. Challenges in designing and implementing a vector-based 2D animation system. In: The Digital Gaming Handbook. CRC Press, 245–274, 2020.
DOI
[2]
Madeira, J. S.; Stork, A.; Groß, M. H. An approach to computer-supported cartooning. The Visual Computer Vol. 12, No. 1, 1–17, 1996.
DOI Google Scholar
[3]
Kanamori, Y. Region matching with proxy ellipses for coloring hand-drawn animations. In: Proceedings of the SIGGRAPH Asia Technical Briefs, Article No. 4, 2012.
DOI
[4]
Kanamori, Y. A comparative study of region matching based on shape descriptors for coloring hand-drawn animation. In: Proceedings of the 28th International Conference on Image and Vision Computing, 483–488, 2013.
DOI
[5]
Trigo, P. G.; Johan, H.; Imagire, T.; Nishita, T. Interactive region matching for 2D animation coloring based on feature’s variation. IEICE TRANSACTIONS on Information and Systems Vol. E92-D, No. 6, 1289–1295, 2009.
DOI Google Scholar
[6]
Qiu, J.; Seah, H. S.; Tian, F.; Chen, Q.; Melikhov, K. Computer-assisted auto coloring by region matching. In: Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, 175–184, 2003.
[7]
Qiu, J.; Soon Seah, H.; Tian, F.; Chen, Q.; Wu, Z. Enhanced auto coloring with hierarchical region matching. Computer Animation and Virtual Worlds Vol. 16, Nos. 3–4, 463–473, 2005.
DOI Google Scholar
[8]
Sato, K.; Matsui, Y.; Yamasaki, T.; Aizawa, K. Reference-based manga colorization by graph correspondence using quadratic programming. In: Proceedings of the SIGGRAPH Asia Technical Briefs, Article No. 15, 2014.
DOI
[9]
Sýkora, D.; Ben-Chen, M.; Čadík, M.; Whited, B.; Simmons, M. TexToons: Practical texture mapping for hand-drawn cartoon animations. In: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation and Rendering, 75–84, 2011.
DOI
[10]
Liu, S. L.; Wang, X. C.; Wu, Z. K.; Seah, H. S. Shape correspondence based on Kendall shape space and RAG for 2D animation. The Visual Computer: International Journal of Computer Graphics Vol. 36, Nos. 10–12, 2457–2469, 2020.
DOI Google Scholar
[11]
Zhu, H. C.; Liu, X. T.; Wong, T. T.; Heng, P. A. Globally optimal toon tracking. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 75, 2016.
DOI Google Scholar
[12]
Qiu, J.; Seah, H. S.; Tian, F.; Chen, Q.; Wu, Z. K.; Melikhov, K. Auto coloring with enhanced character registration. International Journal of Computer Games Technology Vol. 2008, Article No. 2, 2008.
DOI Google Scholar
[13]
Chang, C. W.; Lee, S. Y. Automatic cel painting in computer-assisted cartoon production using similarity recognition. The Journal of Visualization and Computer Animation Vol. 8, No. 3, 165–185, 1997.
DOI
[14]
Alexa, M.; Cohen-Or, D.; Levin, D. As-rigid-as-possible shape interpolation. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 157–164, 2000.
DOI
[15]
Kort, A. Computer aided inbetweening. In: Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering, 125–132, 2002.
DOI
[16]
Sýkora, D.; Buriánek, J.; Žára, J. Unsupervised colorization of black-and-white cartoons. In: Procee-dings of the 3rd International Symposium on Non-photorealistic Animation and Rendering, 121–127, 2004.
DOI
[17]
Zhang, L.; Huang, H.; Fu, H. B. EXCOL: An EXtract-and-COmplete layering approach to cartoon animation reusing. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 7, 1156–1169, 2012.
DOI Google Scholar
[18]
Miyauchi, R.; Fukusato, T.; Xie, H. R.; Miyata, K. Stroke correspondence by labeling closed areas. In: Proceedings of the Nicograph International, 34–41, 2021.
DOI
[19]
Maejima, A.; Kubo, H.; Funatomi, T.; Yotsukura, T.; Nakamura, S.; Mukaigawa, Y. Graph matching based anime colorization with multiple references. In: Proceedings of the ACM SIGGRAPH Posters, Article No. 13, 2019.
DOI
[20]
Liu, X. T.; Wu, W. L.; Li, C. Z.; Li, Y. F.; Wu, H. S. Reference-guided structure-aware deep sketch colorization for cartoons. Computational Visual Media Vol. 8, No. 1, 135–148, 2022.
DOI Google Scholar
[21]
Li, X. Y.; Zhang, B.; Liao, J.; Sander, P. V. Deep sketch-guided cartoon video inbetweening. IEEE Transactions on Visualization and Computer Graphics Vol. 28, No. 8, 2938–2952, 2022.
DOI Google Scholar
[22]
Casey, E.; Pérez, V.; Li, Z. R. The animation transformer: Visual correspondence via segment matching. In: Proceedings of the IEEE/CVF Inter-national Conference on Computer Vision, 11303–11312, 2021.
DOI
[23]
Liu, X. T.; Li, C. Z.; Wong, T. T. Boundary-aware texture region segmentation from manga. Computational Visual Media Vol. 3, No. 1, 61–71, 2017.
DOI Google Scholar
[24]
Mao, X. Y.; Liu, X. T.; Wong, T. T.; Xu, X. M. Region-based structure line detection for cartoons. Computational Visual Media Vol. 1, No. 1, 69–78, 2015.
DOI Google Scholar
[25]
Trémeau, A.; Colantoni, P. Regions adjacency graph applied to color image segmentation. IEEE Transactions on Image Processing Vol. 9, No. 4, 735–744, 2000.
DOI Google Scholar
[26]
Egenhofer, M. A mathematical framework for the definition of topological relations. In: Proceedings of the 4th International Symposium on Spatial Data Handing, 803–813, 1990.
[27]
Lasseter, J. Principles of traditional animation applied to 3D computer animation. ACM SIGGRAPH Computer Graphics Vol. 21, No. 4, 35–44, 1987.
DOI Google Scholar
[28]
Kendall, D. G. Shape manifolds, procrustean metrics, and complex projective spaces. Bulletin of the London Mathematical Society Vol. 16, No. 2, 81–121, 1984.
DOI Google Scholar
[29]
Lv, C.; Wu, Z.; Wang, X.; Zhou, M.; Toh, K.-A. Nasal similarity measure of 3D faces based on curve shape space. Pattern Recognition Vol. 88, 458–469, 2019.
DOI Google Scholar
[30]
Dryden, I. L.; Mardia, K. V. Statistical Shape Analysis, with Applications in R. Wiley, 2016.
DOI
[31]
Leordeanu, M.; Hebert, M. A spectral technique for correspondence problems using pairwise constraints. In: Proceedings of the 10th IEEE International Conference on Computer Vision, 1482–1489, 2005.
DOI
[32]
Cho, M.; Lee, J.; Lee, K. M. Reweighted random walks for graph matching. In: Computer Vision – ECCV 2010. Lecture Notes in Computer Science, Vol. 6315. Daniilidis, K.; Maragos, P.; Paragios, N. Eds. Springer Berlin Heidelberg, 492–505, 2010.
DOI
[33]
Zhou, F.; De la Torre, F. Factorized graph matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 127–134, 2012.
DOI
[34]
Yang, W.; Seah, H.-S.; Chen, Q.; Liew, H.-Z.; Sýkora, D. Ftp-sc: Fuzzy topology preserving stroke correspondence. Computer Graphics Forum Vol. 37, No. 8, 125–135, 2018.
DOI Google Scholar
[35]
Belongie, S.; Malik, J.; Puzicha, J. Shape context: A new descriptor for shape matching and object recognition. In: Proceedings of the 13th International Conference on Neural Information Processing Systems, 798–804, 2000.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 24 December 2021
Accepted: 15 June 2022
Published: 29 April 2023
Issue date: September 2023

Copyright

© The Author(s) 2023.

Acknowledgements

This research was partially supported by the National Key R&D Program of China (2020YFC1523302), and the National Natural Science Foundation of China (61972041, 62072045). Additionally we give many thanks to Jiang jie and Liew Hongze for their instructive advice and useful suggestions.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return