×

Sparse models for intrinsic shape correspondence. (English) Zbl 1380.68404

Breuß, Michael (ed.) et al., Perspectives in shape analysis. Based on the presentations at a seminar, Dagstuhl, Germany, February 2014. Cham: Springer (ISBN 978-3-319-24724-3/hbk; 978-3-319-24726-7/ebook). Mathematics and Visualization, 211-230 (2016).
Summary: We present a novel sparse modeling approach to non-rigid shape matching using only the ability to detect repeatable regions. As the input to our algorithm, we are given only two sets of regions in two shapes; no descriptors are provided so the correspondence between the regions is not know, nor do we know how many regions correspond in the two shapes. We show that even with such scarce information, it is possible to establish very accurate correspondence between the shapes by using methods from the field of sparse modeling, being this, the first non-trivial use of sparse models in shape correspondence. We formulate the problem of permuted sparse coding, in which we solve simultaneously for an unknown permutation ordering the regions on two shapes and for an unknown correspondence in functional representation. We also propose a robust variant capable of handling incomplete matches. Numerically, the problem is solved efficiently by alternating the solution of a linear assignment and a sparse coding problem. The proposed methods are evaluated qualitatively and quantitatively on standard benchmarks containing both synthetic and scanned objects.
For the entire collection see [Zbl 1355.68011].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

SCAPE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 1.Aflalo, Y., Bronstein, A., Kimmel, R.: On convex relaxation of graph isomorphism. Proc. Nat. Acad. Sci. 112 (10), 2942-2947 (2015) · Zbl 1355.05237 · doi:10.1073/pnas.1401651112
[2] 2.Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., Davis, J.: Scape: shape completion and animation of people. In: Proceedings of the SIGGRAPH Conference, Los Angeles (2005) · doi:10.1145/1186822.1073207
[3] 3.Aubry, M., Schlickewei, U., Cremers, D.: The wave kernel signature: a quantum mechanical approach to shape analysis. In: Proceeding of Workshop on Dynamic Shape Capture and Analysis, Barcelona (2011)
[4] 4.Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Img. Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[5] 5.Besl, P.J., McKay, N.D.: A method for registration of 3D shapes. Trans. PAMI 14, 239-256 (1992) · Zbl 05110721 · doi:10.1109/34.121791
[6] 6.Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. PNAS 103 (5), 1168-1172 (2006) · Zbl 1160.65306 · doi:10.1073/pnas.0508601103
[7] 7.Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Numerical Geometry of Non-rigid Shapes. Springer, New York (2008) · Zbl 1178.68608
[8] 8.Bronstein, A.M., Bronstein, M.M., Kimmel, R., Mahmoudi, M., Sapiro, G.: A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching. IJCV 89 (2-3), 266-286 (2010) · Zbl 1477.68334 · doi:10.1007/s11263-009-0301-6
[9] 9.Bronstein, M.M., Bustos, B., Darom, T., Horaud, R., Hotz, I., Keller, Y., Keustermans, J., Kovnatsky, A., Litman, R., Reininghaus, J., Sipiran, I., Smeets, D., Suetens, P., Vandermeulen, D., Zaharescu, A., Zobel, V., Boyer, E., Bronstein, A.M.: Shrec 2011: robust feature detection and description benchmark. In: EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), Llandudno (2011)
[10] 10.Chen, Y., Medioni, G.: Object modeling by registration of multiple range images. In: Proceeding of Conference on Robotics and Automation, Sacramento (1991) · doi:10.1109/ROBOT.1991.132043
[11] 11.Digne, J., Morel, J.M., Audfray, N., Mehdi-Souzani, C.: The level set tree on meshes. In: Proceeding 3DPVT, Paris (2010)
[12] 12.Elad, M.: Sparse and redundant representations: from theory to applications in signal and image processing. Springer, New York (2010) · Zbl 1211.94001 · doi:10.1007/978-1-4419-7011-4
[13] 13.Elad, A., Kimmel, R.: Bending invariant representations for surfaces. In: Proceedings of CVPR, Colorado, pp. 168-174 (2001)
[14] 14.Gebal, K., Bærentzen, J.A., Aanæs, H., Larsen, R.: Shape analysis using the auto diffusion function. Comput. Graph. Forum 28 (5), 1405-1413 (2009) · Zbl 05650608 · doi:10.1111/j.1467-8659.2009.01517.x
[15] 15.Golovinskiy, A., Funkhouser, T.: Consistent segmentation of 3d models. Comput. Graph. 33 (3), 262-269 (2009) · doi:10.1016/j.cag.2009.03.010
[16] 16.Huang, Q., Koltun, V., Guibas, L.: Joint shape segmentation with linear programming. TOG 30, 125 (2011)
[17] 17.Kaick, O.V., Zhang, H., Hamarneh, G., Cohen-Or, D.: A survey on shape correspondence. Comput. Graph. Forum 20, 1-23 (2010)
[18] 18.Kim, V.G., Lipman, Y., Funkhouser, T.: Blended intrinsic maps. TOG 30 (4), 79 (2011) · doi:10.1145/2010324.1964974
[19] 19.Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Quart. 2, 83-97 (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[20] 20.Lipman, Y., Funkhouser, T.: Mobius voting for surface correspondence. ACM Trans. Graph. (Proc. SIGGRAPH) 28 (3), 72 (2009)
[21] 21.Litman, R., Bronstein, A.M., Bronstein, M.M.: Diffusion-geometric maximally stable component detection in deformable shapes. Comput. Graph. 35 (3), 549-560 (2011) · doi:10.1016/j.cag.2011.03.011
[22] 22.Mateus, D., Horaud, R., Knossow, D., Cuzzolin, F., Boyer, E.: Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In: Proceeding CVPR, Anchorage (2008) · doi:10.1109/CVPR.2008.4587538
[23] 23.Memoli, F., Sapiro, G.: A theoretical and computational framework for isometry invariant recognition of point cloud data. Found. Comput. Math. 5 (3), 313-347 (2005) · Zbl 1101.53022 · doi:10.1007/s10208-004-0145-y
[24] 24.Nesterov, Y.: Gradient methods for minimizing composite objective function. In: CORE Discussion Paper 2007/76, Center for Operations Research and Econometrics (CORE). Catholic University of Louvain, Louvain-la-Neuve (2007)
[25] 25.Nguyen, A., Ben-Chen, M., Welnicka, K., Ye, Y., Guibas, L.: An optimization approach to improving collections of shape maps. Comput. Graph. Forum 30, 1481-1491 (2011) · doi:10.1111/j.1467-8659.2011.02022.x
[26] 26.Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., Guibas, L.: Functional maps: a flexible representation of maps between shapes. TOG 31 (4), 129-139 (2012) · doi:10.1145/2185520.2185526
[27] 27.Ovsjanikov, M., Mérigot, Q., Mémoli, F., Guibas, L.: One point isometric matching with the heat kernel. Comput. Graph. Forum 29, 1555-1564 (2010) · doi:10.1111/j.1467-8659.2010.01764.x
[28] 28.Pokrass, J., Bronstein, A.M., Bronstein, M.M.: A correspondence-less approach to matching of deformable shapes. In: Proceeding SSVM, Ein-Gedi (2011)
[29] 29.Raviv, D., Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Symmetries of non-rigid shapes. In: Proceeding of Workshop on Non-rigid Registration and Tracking Through Learning (NRTL), Stony Brook (2005) · Zbl 1289.68188
[30] 30.Rustamov, R.M.: Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In: Proceeding of SGP, Barcelona, pp. 225-233 (2007)
[31] 31.Sahillioglu, Y., Yemez, Y.: Coarse-to-fine combinatorial matching for dense isometric shape correspondence. Comput. Graph. Forum 32, 177-189 (2012) · doi:10.1111/cgf.12007
[32] 32.Sprechmann, P., Bronstein, A.M., Sapiro, G.: Learning efficient structured sparse models. In: Proceedings of ICML, Edinburgh (2012)
[33] 33.Sun, J., Ovsjanikov, M., Guibas, L.J.: A concise and provably informative multi-scale signature based on heat diffusion. In: Proceedings of SGP, Berlin (2009)
[34] 34.Tevs, A., Berner, A., Wand, M., Ihrke, I., Seidel, H.P.: Intrinsic shape matching by planned landmark sampling. Comput. Graph. Forum 30, 543-552 (2011) · doi:10.1111/j.1467-8659.2011.01879.x
[35] 35.Tibshirani, R.: Regression shrinkage and selection via the LASSO. J. R. Stat. Soc. Ser. B 58 (1), 267-288 (1996) · Zbl 0850.62538
[36] 36.Van Kaick, O., Tagliasacchi, A., Sidi, O., Zhang, H., Cohen, D.-Or, Wolf, L., Hamarneh, G.: Prior knowledge for part correspondence. Comput. Graph. Forum 30, 553-562 (2011)
[37] 37.Zaharescu, A., Boyer, E., Varanasi, K., Horaud, R.: Surface feature detection and description with applications to mesh matching. In: Proceedings of CVPR, Miami (2009) · doi:10.1109/CVPR.2009.5206748
[38] 38.Zeng, Y., Wang, C., Wang, Y., Gu, X., Samaras, D., Paragios, N.: Dense non-rigid surface registration using high-order graph matching. In: Proceedings of CVPR, San Francisco (2010) · doi:10.1109/CVPR.2010.5540189
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.