Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (6): 1178-1191.doi: 10.1007/s11390-018-1880-x

Special Issue: Computer Graphics and Multimedia

• Computer Graphics and Multimedia • Previous Articles     Next Articles

Isometric 3D Shape Partial Matching Using GD-DNA

Guo-Guang Du, Cong-Li Yin, Ming-Quan Zhou*, Member, CCF, Zhong-Ke Wu, Member, CCF Ya-Chun Fan, Member, CCF, Fu-Qing Duan*, Member, CCF, Peng-Bo Zhou   

  1. College of Information Science and Technology, Beijing Normal University, Beijing 100875, China Engineering Research Center of Virtual Reality and Applications, Ministry of Education, Beijing 100875, China
  • Received:2017-06-20 Revised:2018-08-10 Online:2018-11-15 Published:2018-11-15
  • Contact: Ming-Quan Zhou,;Fu-Qing Duan,;
  • About author:Guo-Guang Du received his M.S. degree in computer science from Beijing Normal University, Beijing, in 2013. Now he is a Ph.D. candidate in Beijing Normal University, Beijing. His current research interests include 3D shape partial matching, 3D reconstruction, virtual reality, and the application areas mainly focusing on the digital protection of cultural heritage.
  • Supported by:
    This work was supported by the National Key Technology Research and Development Program of China under Grant No. 2017YFB1002804, and the National Natural Science Foundation of China under Grant Nos. 61672103, 61731015, 61572078 and 61402042.

Isometric 3D shape partial matching has attracted a great amount of interest, with a plethora of applications ranging from shape recognition to texture mapping. In this paper, we propose a novel isometric 3D shape partial matching algorithm using the geodesic disk Laplace spectrum (GD-DNA). It transforms the partial matching problem into the geodesic disk matching problem. Firstly, the largest enclosed geodesic disk extracted from the partial shape is matched with geodesic disks from the full shape by the Laplace spectrum of the geodesic disk. Secondly, Generalized Multi-Dimensional Scaling algorithm (GMDS) and Euclidean embedding are conducted to establish final point correspondences between the partial and the full shape using the matched geodesic disk pair. The proposed GD-DNA is discriminative for matching geodesic disks, and it can well solve the anchor point selection problem in challenging partial shape matching tasks. Experimental results on the Shape Retrieval Contest 2016 (SHREC'16) benchmark validate the proposed method, and comparisons with isometric partial matching algorithms in the literature show that our method has a higher precision.

Key words: isometric; partial matching; geodesic disk; Laplace spectrum;

[1] Bronstein A M, Bronstein M, Kimmel R. Generalized multidimensional scaling:A framework for isometry-invariant partial surface matching. Processings of National Academy of Sciences of the United States of America, 2006, 103(5):1168-1172.
[2] Sahillioğlu Y, Yemez Y. Scale normalization for isometric shape matching. Computer Graphics Forum, 2012, 31(7):2233-2240.
[3] Sahillioğlu Y, Yemez Y. Partial 3-D correspondence from shape extremities. Computer Graphics Forum, 2014, 33(6):63-76.
[4] Rodolà E, Cosmo L, Bronstein M M, Torsello A, Cremers D. Partial functional correspondence. Computer Graphics Forum, 2017, 36(1):222-236.
[5] Litany O, Rodolà E, Bronstein A M, Bronstein M M, Cremers D. Non-rigid puzzles. Computer Graphics Forum, 2016, 35(5):135-143.
[6] Litany O, Rodolà E, Bronstein A M, Bronstein M M. Fully spectral partial shape matching. Computer Graphics Forum, 2017, 36(2):247-258.
[7] Belongie S J, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002, 24(4):509-522.
[8] Sun J, Ovsjanikov M, Guibas L. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum, 2010, 28(5):1383-1392.
[9] Aubry M, Schlickewei U, Cremers D. The wave kernel signature:A quantum mechanical approach to shape analysis. In Proc. IEEE International Conference on Computer Vision Workshops, Nov. 2011, pp.1626-1633.
[10] van Kaick O, Zhang H, Hamarneh G, Cohen-Or D. A survey on shape correspondence. Computer Graphics Forum, 2011, 30(6):1681-1707.
[11] Masci J, Boscaini D, Bronstein M M, Vandergheynst P. Geodesic convolutional neural networks on Riemannian manifolds. In Proc. the 2015 IEEE International Conference on Computer Vision Workshop, Dec. 2015, pp.832-840.
[12] Masci J, Rodolà, Emanuele, Boscaini D, Bronstein M M, Li H. Geometric deep learning. In Proc. SIGGRAPH Asia 2016 Courses, Dec. 2016, Article No. 1.
[13] Borg I, Groenen P J F. Modern Multidimensional Scaling. Springer-Verlag New York, 2005.
[14] Lipman Y, Funkhouser T. Möbius voting for surface correspondence. ACM Transactions on Graphics, 2009, 28(3):Article No. 72.
[15] Rodolà E, Bronstein A M, Albarelli A, Bergamasco F. A game-theoretic approach to deformable shape matching. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2012, pp.182-189.
[16] Rodolà E, Torsello A, Harada T, Kuniyoshi Y, Cremers D. Elastic net constraints for shape matching. In Proc. IEEE International Conference on Computer Vision, Dec. 2013, pp.1169-1176.
[17] Ovsjanikov M, Ben-Chen M, Solomon J, Butscher A, Guibas L. Functional maps:A flexible representation of maps between shapes. ACM Transactions on Graphics, 2012, 31(4):Article No. 30.
[18] Kovnatsky A, Bronstein M M, Bresson X, Vandergheynst P. Functional correspondence by matrix completion. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2015, pp.905-914.
[19] Zaharescu A, Boyer E, Varanasi K, Horaud R. Surface feature detection and description with applications to mesh matching. In Proc. IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2009, pp.373-380.
[20] Pokrass J, Bronstein A M, Bronstein M M. Partial shape matching without point-wise correspondence. Numerical Mathematics:Theory Methods & Applications, 2013, 6(1):223-244.
[21] Brunton A, Wand M, Wuhrer S, Seidel H P, Weinkauf T. A low-dimensional representation for robust partial isometric correspondences computation. Graphical Models, 2014, 76(2):70-85.
[22] van Kaick O, Zhang H, Hamarneh G. Bilateral maps for partial matching. Computer Graphics Forum, 2013, 32(6):189-200.
[23] Ovsjanikov M, Mérigot Q, Mémoli F, Guibas L. One point isometric matching with the heat kernel. Computer Graphics Forum, 2010, 29(5):1555-1564.
[24] Reuter M, Wolter F E, Peinecke N. Laplace-Beltrami spectra as ‘Shape-DNA’ of surfaces and solids. Computer-Aided Design, 2006, 38(4):342-366.
[25] Reuter M, Wolter F E, Shenton M, Niethammer M. Laplace-Beltrami eigenvalues and topological features of eigenfunctions for statistical shape analysis. ComputerAided Design, 2009, 41(10):739-755.
[26] Reuter M, Spagnuolo M. Discrete Laplace-Beltrami operators for shape analysis and segmentation. In Proc. IEEE International Conference on Shape Modeling and Applications, June 2009, pp.381-390.
[27] Mémoli F, Sapiro G. A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics, 2005, 5(3):313-347.
[28] Cosmo L, Rodolà E, Bronstein M, Torsello A, Cremers D, Sahillioğlu Y. SHREC'16:Partial matching of deformable shapes. In Proc. Eurographics Workshop on 3D Object Retrieval, May 2016, pp.61-67.
[29] Bronstein A M, Bronstein M M, Kimmel R. Numerical Geometry of Non-Rigid Shapes. Springer-Verlag, New York, 2009.
[30] Kim V G, Lipman Y, Funkhouser T. Blended intrinsic maps. ACM Transactions on Graphics, 2011, 30(4):Article No. 79.
[31] Mitchell J S B, Mount D M, Papadimitriou C H. The discrete geodesic problem. SIAM Journal on Computing, 1987, 16(4):647-668.
[1] Zeinab Hmedeh, Harry Kourdounakis, Vassilis Christophides, Cédric du Mouza, et al. Content-Based Publish/Subscribe System for Web Syndication [J]. , 2016, 31(2): 359-380.
Full text



[1] Xu Zhiming;. Discrete Interpolation Surface[J]. , 1990, 5(4): 329 -332 .
[2] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 .
[3] Zhang Yaoxue; Chen Hua; Zhang Yue; Liu Guoli;. SDL-TRAN-An Interactive Generator for Formal Description Language SDL[J]. , 1996, 11(1): 49 -60 .
[4] WU Jie;. Reliable Communication on Cube-Based Multicomputers[J]. , 1996, 11(3): 208 -221 .
[5] Yan Zongfu; Liu Mingye;. The RTL Binding and Mapping Approach of VHDL High-Level Synthesis System HLS/BIT[J]. , 1996, 11(6): 562 -569 .
[6] wang Xuejun; Shi Chunyi;. A Multiagent Dynamic interaction Testbed:Theoretic Framework, System Architecture and Experimentation[J]. , 1997, 12(2): 121 -132 .
[7] Xue Jinyun;. Unified Approach for Developing EfficientAlgorithmic Programs[J]. , 1997, 12(4): 314 -329 .
[8] Zhang Yongyue; Peng Zhenyun; You Suya; Xu Guangyou;. A Multi-View Face Recognition System[J]. , 1997, 12(5): 400 -407 .
[9] Yu Huiqun; Song Guoxin; Sun Yongqiang;. Completeness of the Accumulation Calculus[J]. , 1998, 13(1): 25 -31 .
[10] Wu Junsheng; Wu Guangmao;. Element-Partition-Based Methods for Visualization of 3D Unstructured Grid Data[J]. , 1998, 13(5): 417 -425 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved