Shape correspondence for cel animation based on a shape association graph and spectral matching
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
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.
Madeira, J. S.; Stork, A.; Groß, M. H. An approach to computer-supported cartooning. The Visual Computer Vol. 12, No. 1, 1–17, 1996.
Kanamori, Y. Region matching with proxy ellipses for coloring hand-drawn animations. In: Proceedings of the SIGGRAPH Asia Technical Briefs, Article No. 4, 2012.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Kort, A. Computer aided inbetweening. In: Proceedings of the 2nd International Symposium on Non-photorealistic Animation and Rendering, 125–132, 2002.
Sýkora, D.; Buriánek, J.; Žára, J. Unsupervised colorization of black-and-white cartoons. In: Proceedings of the 3rd International Symposium on Non-photorealistic Animation and Rendering, 121–127, 2004.
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.
Miyauchi, R.; Fukusato, T.; Xie, H. R.; Miyata, K. Stroke correspondence by labeling closed areas. In: Proceedings of the Nicograph International, 34–41, 2021.
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.
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.
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.
Casey, E.; Pérez, V.; Li, Z. R. The animation transformer: Visual correspondence via segment matching. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, 11303–11312, 2021.
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.
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.
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.
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.
Lasseter, J. Principles of traditional animation applied to 3D computer animation. ACM SIGGRAPH Computer Graphics Vol. 21, No. 4, 35–44, 1987.
Kendall, D. G. Shape manifolds, procrustean metrics, and complex projective spaces. Bulletin of the London Mathematical Society Vol. 16, No. 2, 81–121, 1984.
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.
Dryden, I. L.; Mardia, K. V. Statistical Shape Analysis, with Applications in R. Wiley, 2016.
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.
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.
Zhou, F.; De la Torre, F. Factorized graph matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 127–134, 2012.
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.
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.