“Functional maps: a flexible representation of maps between shapes” by Ovsjanikov, Ben-Chen, Solomon, Butscher and Guibas

We present a novel representation of maps between pairs of shapes that allows for efficient inference and manipulation. Key to our approach is a generalization of the notion of map that puts in correspondence real-valued functions rather than points on the shapes. By choosing a multi-scale basis for the function space on each shape, such as the eigenfunctions of its Laplace-Beltrami operator, we obtain a representation of a map that is very compact, yet fully suitable for global inference. Perhaps more remarkably, most natural constraints on a map, such as descriptor preservation, landmark correspondences, part preservation and operator commutativity become linear in this formulation. Moreover, the representation naturally supports certain algebraic operations such as map sum, difference and composition, and enables a number of applications, such as function or annotation transfer without establishing point-to-point correspondences. We exploit these properties to devise an efficient shape matching method, at the core of which is a single linear solve. The new method achieves state-of-the-art results on an isometric shape matching benchmark. We also show how this representation can be used to improve the quality of maps produced by existing shape matching methods, and illustrate its usefulness in segmentation transfer and joint analysis of shape collections.

1. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. SCAPE: Shape completion and animation of people. In Proc. SIGGRAPH, 408–416. Google ScholarDigital Library
2. Aubry, M., Schlickewei, U., and Cremers, D. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proc. ICCV – 4DMOD Workshop.Google Scholar
3. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE TPAMI 14, 239–256. Google ScholarDigital Library
4. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. PNAS 103, 5, 1168–1172.Google ScholarCross Ref
5. Bronstein, A., Bronstein, M., and Kimmel, R. 2008. Numerical Geometry of Non-Rigid Shapes. Springer. Google ScholarDigital Library
6. Çela, E. 1998. The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers.Google Scholar
7. Dubrovina, A., and Kimmel, R. 2011. Approximately isometric shape correspondence by matching pointwise spectral features and global geodesic structures. Advances in Adaptive Data Analysis, 203–228.Google Scholar
8. Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Computers and Graphics (Proc. SMI) 33, 3, 262–269. Google ScholarDigital Library
9. Huang, Q.-X., Adams, B., Wicke, M., and Guibas, L. J. 2008. Non-rigid registration under isometric deformations. CGF (Proc. SGP) 27, 5, 1449–1457. Google ScholarDigital Library
10. Huang, Q., Koltun, V., and Guibas, L. 2011. Joint shape segmentation with linear programming. ACM TOG (Proc. SIGGRAPH Asia) 30, 6, 125:1–125:12. Google ScholarDigital Library
11. Jain, V., Zhang, H., and van Kaick, O. 2007. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling 13, 1, 101–124.Google ScholarCross Ref
12. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D Mesh Segmentation and Labeling. ACM Transactions on Graphics 29, 3. Google ScholarDigital Library
13. Kato, T. 1995. Perturbation Theory for Linear Operators. Springer-Verlag GmbH.Google Scholar
14. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. In Proc. SIGGRAPH, 79:1–79:12. Google ScholarDigital Library
15. Kin-Chung Au, O., Tai, C.-L., Cohen-Or, D., Zheng, Y., and Fu, H. 2010. Electors voting for fast automatic shape correspondence. Computer Graphics Forum 29, 2, 645–654.Google ScholarCross Ref
16. Lipman, Y., and Funkhouser, T. 2009. Möbius voting for surface correspondence. In Proc. SIGGRAPH, 72:1–72:12. Google ScholarDigital Library
17. Mateus, D., Horaud, R. P., Knossow, D., Cuzzolin, F., and Boyer, E. 2008. Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In Proc. CVPR, 1–8.Google Scholar
18. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Proc. VisMath, 35–57.Google Scholar
19. Nguyen, A., Ben-Chen, M., Welnicka, K., Ye, Y., and Guibas, L. 2011. An optimization approach to improving collections of shape maps. In Proc. SGP, 1481–1491.Google Scholar
20. Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. Comp. Graph. Forum 27, 5, 1341–1348. Google ScholarDigital Library
21. Ovsjanikov, M., Merigot, Q., Memoli, F., and Guibas, L. 2010. One point isometric matching with the heat kernel. CGF 29, 5, 1555–1564.Google ScholarCross Ref
22. Pokrass, J., Bronstein, A. M., and Bronstein, M. M. 2011. A correspondence-less approach to matching of de-formable shapes. In SSVM, 592–603. Google ScholarDigital Library
23. Rustamov, R. M. 2007. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In Proc. SGP, 225–233. Google ScholarDigital Library
24. Sahillioglu, Y., and Yemez, Y. 2011. Coarse-to-fine combinatorial matching for dense isometric shape correspondence. Computer Graphics Forum 30, 5, 1461–1470.Google ScholarCross Ref
25. Sharma, A., and Horaud, R. P. 2010. Shape matching based on diffusion embedding and on mutual isometric consistency. In Proc. CVPR — NORDIA Workshop, 29–36.Google Scholar
26. Singer, A., and Wu, H. 2011. Vector diffusion maps and the connection laplacian. Arxiv preprint arXiv:1102.0075.Google Scholar
27. Skraba, P., Ovsjanikov, M., Chazal, F., and Guibas, L. 2010. Persistence-based segmentation of deformable shapes. In Proc. CVPR — NORDIA Workshop, 45–52.Google Scholar
28. Sun, J., Ovsjanikov, M., and Guibas, L. 2009. A concise and provably informative multi-scale signature based on heat diffusion. In Proc. SGP, 1383–1392. Google ScholarDigital Library
29. Tevs, A., Berner, A., Wand, M., Ihrke, I., and Seidel, H.-P. 2011. Intrinsic shape matching by planned landmark sampling. CGF (Proc. Eurographics) 30, 2, 543–552.Google ScholarCross Ref
30. van Kaick, O., Tagliasacchi, A., Sidi, O., Zhang, H., Cohen-Or, D., Wolf, L., and Hamarneh, G. 2011. Prior knowledge for part correspondence. CGF (Proc. Eurographics) 30, 2, 553–562.Google ScholarCross Ref
31. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2011. A survey on shape correspondence. Computer Graphics Forum 30, 6, 1681–1707.Google ScholarCross Ref
32. Weyl, H. 1946. The Classical Groups: Their Invariants and Representations. Princeton University Press.Google Scholar
33. Xu, K., Li, H., Zhang, H., Cohen-Or, D., Xiong, Y., and Cheng, Z. 2010. Style-content separation by anisotropic part scales. ACM TOG (Proc. SIGGRAPH Asia) 29, 5, 184:1–184:10. Google ScholarDigital Library
34. Yeh, I.-C., Lin, C.-H., Sorkine, O., and Lee, T.-Y. 2010. Template-based 3d model fitting using dual-domain relaxation. IEEE Transactions on Visualization and Computer Graphics 99. Google ScholarDigital Library
35. Zhang, H., Sheffer, A., Cohen-Or, Zhou, Q., van Kaick, O., and Tagliasacchi, A. 2008. Deformation-driven shape correspondence. In Proc. SGP, 1431–1439. Google ScholarDigital Library