Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-26T06:03:25.808Z Has data issue: false hasContentIssue false
  • English
  • Français

Partial Shape Matching Without Point-Wise Correspondence

Published online by Cambridge University Press:  28 May 2015

Jonathan Pokrass ,
Alexander M. Bronstein  and
Michael M. Bronstein
Jonathan Pokrass*
Affiliation:
School of Electrical Engineering, Tel Aviv University, Israel
Alexander M. Bronstein*
Affiliation:
School of Electrical Engineering, Tel Aviv University, Israel
Michael M. Bronstein*
Affiliation:
Institute of Computational Science, Faculty of Informatics, Università della Svizzera Italiana (USI), Lugano, Switzerland
*
Corresponding author.Email address:[email protected]
Corresponding author.Email address:[email protected]
Corresponding author.Email address:[email protected]
Get access

Abstract

Partial similarity of shapes is a challenging problem arising in many important applications in computer vision, shape analysis, and graphics, e.g. When one has to deal with partial information and acquisition artifacts. The problem is especially hard when the underlying shapes are non-rigid and are given up to a deformation. Partial matching is usually approached by computing local descriptors on a pair of shapes and then establishing a point-wise non-bijective correspondence between the two, taking into account possibly different parts. In this paper, we introduce an alternative correspondence-less approach to matching fragments to an entire shape undergoing a non-rigid deformation. We use region-wise local descriptors and optimize over the integration domains on which the integral descriptors of the two parts match. The problem is regularized using the Mumford-Shah functional. We show an efficient discretization based on the Ambrosio-Tortorelli approximation generalized to triangular point clouds and meshes, and present experiments demonstrating the success of the proposed method.

Keywords

65D1868U05Deformable shapespartial matchingpartial correspondencepartial similaritydiffusion geometry Laplace-Beltrami operatorshape descriptorsheat kernel signatureMumford-Shah regularization
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 6 , Issue 1 , February 2013 , pp. 223 - 244
Copyright
Copyright © Global Science Press Limited 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aflalo, J., Bronstein, A. M., Bronstein, M. M., and Kimmel, R.. Deformable shape retrieval by learning diffusion kernels. In Proc. SSVM, 2011.Google Scholar
[2] Ambrosio, L. and Tortorelli, V.M.. Approximation of functionals depending on jumps by elliptic functionals via-convergence. Comm. Pure Appl. Math, 43(8):999–1036, 1990.Google Scholar
[3] Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J.. Scape: shape completion and animation of people. In Proceedings of the SIGGRAPH Conference, 2005.Google Scholar
[4] Aubry, M., Schlickewei, U., and Cremers, D.. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proc. Workshop 4DMOD, 2011.Google Scholar
[5] Belkin, M. and Niyogi, P.. Towards a theoretical foundation for laplacian-based manifold methods. COLT, pages 486–500, 2005.Google Scholar
[6] Belkin, M., Sun, J., and Wang, Y.. Constructing laplace operator from point clouds in rd . In 20th ACM-SIAM Sympos. Discrete Algorithms, pages 1031–1040. ACM-SIAM, 2009.Google Scholar
[7] Besl, P. J. and McKay, N. D.. A method for registration of 3D shapes. Trans. PAMI, 14:239–256, 1992.CrossRefGoogle Scholar
[8] Bronstein, A. M.. Spectral descriptors for deformable shapes. Technical Report arXiv:1110.5015v1, 2011.Google Scholar
[9] Bronstein, A. M. and Bronstein, M. M.. Not only size matters: regularized partial matching of nonrigid shapes. In Prof. NORDIA, 2008.CrossRefGoogle Scholar
[10] Bronstein, A. M. and Bronstein, M. M.. Regularized partial matching of rigid shapes. In Proc. ECCV, pages 143–154, 2008.Google Scholar
[11] Bronstein, A. M., Bronstein, M. M., Carmon, Y., and Kimmel, R.. Partial similarity of shapes using a statistical significance measure. IPSJ Trans. Computer Vision and Applications, 1:105–114, 2009.Google Scholar
[12] Bronstein, A. M., Bronstein, M. M., Guibas, L. J., and Ovsjanikov, M.. Shape google: geometric words and expressions for invariant shape retrieval. ACM Transactions on Graphics (TOG), 30(1):1, 2011.Google Scholar
[13] Bronstein, A. M., Bronstein, M. M., and Kimmel, R.. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc. National Academy of Science (PNAS), 103(5):1168–1172, 2006.CrossRefGoogle ScholarPubMed
[14] Bronstein, A. M., Bronstein, M. M., and Kimmel, R.. Robust expression-invariant face recognition from partially missing data. In Proc. European Conf. Computer Vision (ECCV), pages 396–408, 2006.Google Scholar
[15] Bronstein, A. M., Bronstein, M. M., and Kimmel, R.. Numerical geometry of non-rigid shapes. Springer-Verlag New York Inc, 2008.Google Scholar
[16] Bronstein, A.M., Bronstein, M.M., Carmon, Y., and Kimmel, R.. Partial similarity of shapes using a statistical significance measure. Trans. Computer Vision and Applications, 1(0):105–114, 2009.Google Scholar
[17] Bronstein, M. M. and Kokkinos, I.. Scale-invariant heat kernel signatures for non-rigid shape recognition. In Proc. CVPR, 2010.CrossRefGoogle Scholar
[18] Luo, C., Sun, J., and Wang, Y. Integral estimation from point cloud in d-dimensional space: A geometric view.Google Scholar
[19] Chan, T. F. and Vese, L. A.. Active contours without edges. IEEE Trans. Image Processing, 10(2):266–277, 2001.Google Scholar
[20] Chen, Y. and Medioni, G.. Object modeling by registration of multiple range images. In Proc. Conf. Robotics and Automation, 1991.Google Scholar
[21] Clarenz, U., Rumpf, M., and Telea, A.. Robust feature detection and local classification for surfaces based on moment analysis. Trans. Visualization and Computer Graphics, 10(5):516–524, 2004.CrossRefGoogle ScholarPubMed
[22] Domokos, C. and Kato, Z.. Affine Puzzle: Realigning Deformed Object Fragments without Correspondences. In Proc. ECCV, pages 777–790, 2010.Google Scholar
[23] Dutagaci, Helin, Godil, Afzal, Cheung, Chun Pan, Furuya, Takahiko, Hillenbrand, Ulrich, and Ohbuchi, Ryutarou. Shrec’10 track: Range scan retrieval. In 3DOR, pages 109–115, 2010.Google Scholar
[24] Gatzke, Timothy, Grimm, Cindy, Garland, Michael, and Zelinka, Steve. Curvature maps for local shape comparison. In In Shape Modeling International, pages 244–256, 2005.Google Scholar
[25] Gebal, K., Bærentzen, J.A., Aanæs, H., and Larsen, R.. Shape analysis using the auto diffusion function. In Computer Graphics Forum, volume 28, pages 1405–1413, 2009.Google Scholar
[26] Gromov, M.. Structures Métriques Pour les Variétés Riemanniennes. Number 1 in Textes Mathématiques. 1981.Google Scholar
[27] Har-Peled, S. and Varadarajan, K. R.. Projective clustering in high dimensions using core-sets. In 18th Annu. ACM Sympos. Comput. Geom., pages 312–318. ACM, 2002.Google Scholar
[28] Huang, Q.X., Flöry, S., Gelfand, N., Hofer, M., and Pottmann, H.. Reassembling fractured objects by geometric matching. ACM Trans. Graphics, 25(3):569–578, 2006.Google Scholar
[29] Jacobs, D., Weinshall, D., and Gdalyahu, Y.. Class representation and image retrieval with non-metric distances. Trans. PAMI, 22(6):583–600, 2000.Google Scholar
[30] Johnson, A. E. and Hebert, M.. Using spin images for efficient object recognition in cluttered 3D scenes. Trans. PAMI, 21(5):433–449, 1999.Google Scholar
[31] Jones, P. W., Maggioni, M., and Schul, R.. Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels. PNAS, 105(6):1803, 2008.Google Scholar
[32] Kovnatsky, A., Bronstein, M. M., Bronstein, A. M., and Kimmel, R.. Photometric heat kernel signature. In Proc. Scale Space and Variational Methods (SSVM), 2011.Google Scholar
[33] Latecki, L. J., Lakaemper, R., and Wolter, D.. Optimal Partial Shape Similarity. Image and Vision Computing, 23:227–236, 2005.Google Scholar
[34] Lévy, B.. Laplace-Beltrami eigenfunctions towards an algorithm that “understands” geometry. In Proc. Shape Modeling and Applications, 2006.Google Scholar
[35] Luo, Chuanjiang, Safa, Issam, and Wang, Yusu. Approximating gradients for meshes and point clouds via diffusion metric. In Eurographics Symposium on Geometry Processing, 2009.Google Scholar
[36] Manay, S., Hong, B.W., Yezzi, A.J., and Soatto, S.. Integral invariant signatures. Lecture Notes in Computer Science, pages 87–99, 2004.Google Scholar
[37] Mémoli, F. and Sapiro, G.. A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics, 5:313–346, 2005.Google Scholar
[38] Mitra, N. J., Guibas, L. J., Giesen, J., and Pauly, M.. Probabilistic fingerprints for shapes. In Proc. SGP, 2006.Google Scholar
[39] Mumford, D. and Shah, J.. Optimal approximations by piecewise smooth functions and associated variational problems. Communications on pure and applied mathematics, 42(5):577–685, 1989.Google Scholar
[40] Ovsjanikov, M., Bronstein, A.M., Guibas, L.J., and Bronstein, M.M.. Shape Google: a computer vision approach to invariant shape retrieval. In Proc. NORDIA. Citeseer, 2009.Google Scholar
[41] Pauly, M., Keiser, R., and Gross, M.. Multi-scale feature extraction on point-sampled surfaces. In Computer Graphics Forum, volume 22, pages 281–289, 2003.Google Scholar
[42] Pokrass, J., Bronstein, A. M., and Bronstein, M. M.. A correspondence-less approach to matching of deformable shapes. In Proc. SSVM, 2011.Google Scholar
[43] Reuter, M., Wolter, F.-E., and Peinecke, N.. Laplace-spectra as fingerprints for shape matching. In Proc. ACM Symp. Solid and Physical Modeling, pages 101–106, 2005.Google Scholar
[44] Rusu, Radu Bogdan, Blodow, Nico, and Beetz, Michael. Fast Point Feature Histograms (FPFH) for 3D Registration. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 12-17 2009.Google Scholar
[45] Sipiran, I. and Bustos, B.. A robust 3D interest points detector based on Harris operator. In Proc. 3DOR, pages 7–14. Eurographics, 2010.Google Scholar
[46] Sivic, J. and Zisserman, A.. Video Google: a text retrieval approach to object matching in videos. In Proc. CVPR, 2003.Google Scholar
[47] Strecha, C., Bronstein, A. M., Bronstein, M. M., and Fua, P.. LDAHash: improved matching with smaller descriptors. 35(1):66–78, 2012.Google Scholar
[48] Sun, J., Ovsjanikov, M., and Guibas, L.. A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion. In Computer Graphics Forum, volume 28, pages 1383–1392, 2009.Google Scholar
[49] Toldo, R., Castellani, U., and Fusiello, A.. Visual vocabulary signature for 3D object retrieval and partial matching. In Proc. 3DOR, 2009.Google Scholar
[50] Wahl, E., Hillenbrand, U., and Hirzinger, G.. Surflet-pair-relation histograms: A statistical 3d-shape representation for rapid classification. In 3DIM03, pages 474–481, 2003.Google Scholar
[51] Zaharescu, A., Boyer, E., Varanasi, K., and R Horaud. Surface feature detection and description with applications to mesh matching. In Proc. CVPR, 2009.Google Scholar
[52] Zhang, C. and Chen, T.. Efficient feature extraction for 2D/3D objects in mesh representation. In Proc. ICIP, volume 3, 2001.Google Scholar