AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (25.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

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

Beijing Normal University, Beijing 100875, China
Nanyang Technological University, Singapore 639798, Singapore
Show Author Information

Graphical Abstract

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 animationshape correspondenceshape association graph (SAG)spectral matchingquadratic assignmentKendall shape space

References

[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[15]
Kort, A. Computer aided inbetweening. In: Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering, 125–132, 2002.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[30]
Dryden, I. L.; Mardia, K. V. Statistical Shape Analysis, with Applications in R. Wiley, 2016.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Computational Visual Media
Volume 9 Issue 3,
September 2023
Pages 633-656
DOI: 10.1007/s41095-022-0298-0
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

1000

Views

47

Downloads

2

Crossref

1

Web of Science

3

Scopus

0

CSCD

Altmetrics
Received: 24 December 2021
Accepted: 15 June 2022
Published: 29 April 2023
© The Author(s) 2023.

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