Maks Ovsjanikov
Mirela Ben-Chen
Justin Solomon
Abstract
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.
Supplemental Material
- 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 Scholar
Digital Library
- 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
- Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE TPAMI 14, 239--256. Google ScholarDigital Library
- 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
- Bronstein, A., Bronstein, M., and Kimmel, R. 2008. Numerical Geometry of Non-Rigid Shapes. Springer. Google ScholarDigital Library
- Çela, E. 1998. The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers.Google Scholar
- 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
- Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Computers and Graphics (Proc. SMI) 33, 3, 262--269. Google ScholarDigital Library
- 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
- 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
- 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
- Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D Mesh Segmentation and Labeling. ACM Transactions on Graphics 29, 3. Google ScholarDigital Library
- Kato, T. 1995. Perturbation Theory for Linear Operators. Springer-Verlag GmbH.Google Scholar
- Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. In Proc. SIGGRAPH, 79:1--79:12. Google ScholarDigital Library
- 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
- Lipman, Y., and Funkhouser, T. 2009. Möbius voting for surface correspondence. In Proc. SIGGRAPH, 72:1--72:12. Google ScholarDigital Library
- 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
- 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
- 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
- Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. Comp. Graph. Forum 27, 5, 1341--1348. Google ScholarDigital Library
- 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
- 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
- Rustamov, R. M. 2007. Laplace-beltrami eigenfunctions for deformation invariant shape representation. In Proc. SGP, 225--233. Google ScholarDigital Library
- 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
- 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
- Singer, A., and Wu, H. 2011. Vector diffusion maps and the connection laplacian. Arxiv preprint arXiv:1102.0075.Google Scholar
- 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
- 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
- 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
- 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
- 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
- Weyl, H. 1946. The Classical Groups: Their Invariants and Representations. Princeton University Press.Google Scholar
- 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
- 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
- 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
Recommendations
Iterative Closest Spectral Kernel Maps
3DV '14: Proceedings of the 2014 2nd International Conference on 3D Vision - Volume 01An important operation in geometry processing is finding the correspondences between pairs of shapes. Measures of dissimilarity between surfaces, has been found to be highly useful for nonrigid shape comparison. Here, we analyze the applicability of the ...
Reversible Harmonic Maps between Discrete Surfaces
Information transfer between triangle meshes is of great importance in computer graphics and geometry processing. To facilitate this process, a smooth and accurate map is typically required between the two meshes. While such maps can sometimes be ...
An optimization approach for extracting and encoding consistent maps in a shape collection
We introduce a novel approach for computing high quality point-to-point maps among a collection of related shapes. The proposed approach takes as input a sparse set of imperfect initial maps between pairs of shapes and builds a compact data structure ...
Comments