Functional Maps Representation On Product Manifolds
M. M. Bronstein
USI Lugano, Switzerland
Imperial College London, London, UK
Intel, Haifa, Israel
Search for more papers by this authorM. M. Bronstein
USI Lugano, Switzerland
Imperial College London, London, UK
Intel, Haifa, Israel
Search for more papers by this authorAbstract
We consider the tasks of representing, analysing and manipulating maps between shapes. We model maps as densities over the product manifold of the input shapes; these densities can be treated as scalar functions and therefore are manipulable using the language of signal processing on manifolds. Being a manifold itself, the product space endows the set of maps with a geometry of its own, which we exploit to define map operations in the spectral domain; we also derive relationships with other existing representations (soft maps and functional maps). To apply these ideas in practice, we discretize product manifolds and their Laplace–Beltrami operators, and we introduce localized spectral analysis of the product manifold as a novel tool for map processing. Our framework applies to maps defined between and across 2D and 3D shapes without requiring special adjustment, and it can be implemented efficiently with simple operations on sparse matrices.
References
- [ADK16] Aflalo Y., Dubrovina A., Kimmel R.: Spectral generalized multi-dimensional scaling. IJCV 118, 3 (2016), 380–392.
- [BBL*17] Bronstein M. M., Bruna J., LeCun Y., Szlam A., Vandergheynst P.: Geometric deep learning: Going beyond Euclidean data. IEEE Signal Processing Magazine 34, 4 (July 2017), 18–42.
- [Ber98] Bertsekas D. P.: Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.
- [BGM71] Berger M., Gauduchon P., Mazet E.: Le spectre d'une variété Riemannienne. Lecture Notes in Mathematics. Springer-Verlag, Berlin, Germany, 1971.
- [Bre03] Brenier Y.: Extended monge-kantorovich theory. In Optimal Transportation and Applications. L. A. Caffarelli and S. Salsa (Eds.). Springer, Berlin, Germany, 2003, pp. 91–121.
10.1007/978-3-540-44857-0_4 Google Scholar
- [Cha84] Chavel I.: Eigenvalues in Riemannian Geometry (2nd edition). Academic Press, Cambridge, MA, 1984.
- [Cox48] Coxeter H. S. M.: Regular Polytopes. Dover Publications, New York, NY, 1948.
- [CRA*17] Cosmo L., Rodolà E., Albarelli A., Mémoli F., Cremers D.: Consistent partial matching of shape collections via sparse modeling. Computer Graphics Forum 36, 1 (2017), 209–221.
- [CRM*16] Cosmo L., Rodolà E., Masci J., Torsello A., Bronstein M. M.: Matching deformable objects in clutter. In Proceedings - 2016 4th International Conference on 3D Vision, 3DV 2016 (Stanford, 2016), IEEE, pp. 1–10.
10.1109/3DV.2016.10 Google Scholar
- [CSBK17] Choukroun Y., Shtern A., Bronstein A., Kimmel R.: Hamiltonian operator for spectral shape analysis. arXiv:1611.01990v2 (2017).
- [Duf59] Duffin R. J.: Distributed and lumped networks. Journal of Mathematics and Mechanics 8, 5 (1959), 793–826.
- [EBC17] Ezuz D., Ben-Chen M.: Deblurring and denoising of maps between shapes. Computer Graphics Forum 36, 5 (2017), 165–174.
- [ERGB16] Eynard D., Rodolà E., Glashoff K., Bronstein M. M.: Coupled functional maps. In Proceedings - 2016 4th International Conference on 3D Vision, 3DV 2016 (Stanford, 2016), IEEE, pp. 399–407.
10.1109/3DV.2016.49 Google Scholar
- [Fie73] Fiedler M.: Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23, 98 (1973), 298–305.
10.21136/CMJ.1973.101168 Google Scholar
- [GO17] Glashoff K., Ortlieb C. P.: Composition operators, matrix representation, and the finite section method: A theoretical framework for maps between shapes. arXiv:1705.00325 (2017).
- [GP10] Guillemin V., Pollack A.: Differential Topology. AMS Chelsea Publishing Series. American Mathematical Society, Providence, RI, 2010.
10.1090/chel/370 Google Scholar
- [GRS10] Gröchenig K., Rzeszotnik Z., Strohmer T.: Convergence analysis of the finite section method and Banach algebras of matrices. Integral Equations and Operator Theory 67, 2 (2010), 183–202.
- [HIK11] Hammack R., Imrich W., Klavzar S.: Handbook of Product Graphs (2nd edition). CRC Press, Boca Raton, FL, 2011.
10.1201/b10959 Google Scholar
- [HO17] Huang R., Ovsjanikov M.: Adjoint map representation for shape analysis and matching. Computer Graphics Forum 36, 5 (2017), 151–163.
- [HWG14] Huang Q., Wang F., Guibas L.: Functional map networks for analyzing and exploring large shape collections. ACM Transactions on Graphics (TOG) 33, 4 (2014), 36.
- [KBB*13] Kovnatsky A., Bronstein M. M., Bronstein A. M., Glashoff K., Kimmel R.: Coupled quasi-harmonic bases. Computer Graphics Forum 32, 2 (2013), 439–448.
- [KBBV15] Kovnatsky A., Bronstein M. M., Bresson X., Vandergheynst P.: Functional correspondence by matrix completion. In Proceedings/CVPR (Boston, 2015), IEEE, pp. 905–914.
10.1109/CVPR.2015.7298692 Google Scholar
- [KGB16] Kovnatsky A., Glashoff K., Bronstein M. M.: MADMM: a generic algorithm for non-smooth optimization on manifolds. In Proceedings/ECCV (Amsterdam, 2016), Springer.
10.1007/978-3-319-46454-1_41 Google Scholar
- [Lav17] Lavenant H.: Harmonic mappings valued in the Wasserstein space. arXiv:1712.07528 (2017).
- [LRB*16] Litany O., Rodolà E., Bronstein A. M., Bronstein M. M., Cremers D.: Non-rigid puzzles. Computer Graphics Forum 35, 5 (2016), 135–143.
- [LRR*17] Litany O., Remez T., Rodolà E., Bronstein A. M., Bronstein M. M.: Deep functional maps: Structured prediction for dense shape correspondence. In Proceedings of the IEEE International Conference on Computer Vision (Venice, 2017), vol. 2, IEEE, pp. 5660–5668.
10.1109/ICCV.2017.603 Google Scholar
- [LRS*16] Lähner Z., Rodolà E., Schmidt F. R., Bronstein M. M., Cremers D.: Efficient globally optimal 2D-to-3D deformable shape matching. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Las Vegas, 2016), IEEE, pp. 2185–2193.
10.1109/CVPR.2016.240 Google Scholar
- [MCSK*17] Mandad M., Cohen-Steiner D., Kobbelt L., Alliez P., Desbrun M.: Variance-minimizing transport plans for inter-surface mapping. ACM Transactions on Graphics 36, 4 (2017), 39:1–39:14.
- [Mém11] Mémoli F.: Gromov–Wasserstein Distances and the Metric Approach to Object Matching. Foundations of Computational Mathematics 11, 4 (2011), 417–487.
- [MRCB18] Melzi S., Rodolà E., Castellani U., Bronstein M.: Localized manifold harmonics for spectral shape analysis. Computer Graphics Forum 37, 6 (2018), 20–34.
- [NBH18] Nasikun A., Brandt C., Hildebrandt K.: Fast approximation of laplace–beltrami eigenproblems. Computer Graphics Forum 37, 5 (2018), 121–134.
- [NMR*18] Nogneng D., Melzi S., Rodolà E., Castellani U., Bronstein M., Ovsjanikov M.: Improved functional mappings via product preservation. Computer Graphics Forum 37, 2 (2018), 179–190.
- [NO17] Nogneng D., Ovsjanikov M.: Informative descriptor preservation via commutativity for shape matching. Computer Graphics Forum 36, 2 (2017), 259–267.
- [OBCS*12] Ovsjanikov M., Ben-Chen M., Solomon J., Butscher A., Guibas L.: Functional maps: A flexible representation of maps between shapes. ACM Transactions on Graphphics 31, 4 (July2012), 30:1–30:11.
- [OCB*17] Ovsjanikov M., Corman E., Bronstein M., Rodolà E., Ben-Chen M., Guibas L., Chazal F., Bronstein A.: Computing and processing correspondences with functional maps. In ACM SIGGRAPH 2017 Courses (2017), pp. 5:1–5:62.
- [PBB*13] Pokrass J., Bronstein A. M., Bronstein M. M., Sprechmann P., Sapiro G.: Sparse modeling of intrinsic correspondences. Computer Graphics Forum 32, 2 (2013), 459–468.
- [PM90] Perona P., Malik J.: Scale-space and edge detection using anisotropic diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 7 (July 1990), 629–639.
- [RCB*17] Rodolà E., Cosmo L., Bronstein M. M., Torsello A., Cremers D.: Partial functional correspondence. Computer Graphics Forum 36, 1 (2017), 222–236.
- [Sch83] Schlegel V.: Theorie der homogen zusammengesetzten Raumgebilde. Nova Acta, Ksl. Leop.-Carol. Deutsche Akademie der Naturforscher, Band XLIV, Nr. 4, Druck von E. Blochmann und Sohn, Dresden, 1883.
- [SGB13] Solomon J., Guibas L., Butscher A.: Dirichlet energy for analysis and synthesis of soft maps. Computer Graphics Forum 32, 5 (2013), 197–206.
- [SK17] Shamai G., Kimmel R.: Geodesic distance descriptors. In Proceedings/CVPR (Honolulu, 2017), IEEE.
10.1109/CVPR.2017.386 Google Scholar
- [SNB*12] Solomon J., Nguyen A., Butscher A., Ben-Chen M., Guibas L.: Soft maps between surfaces. Computer Graphics Forum 31, 5 (2012), 1617–1626.
- [SPKS16] Solomon J., Peyré G., Kim V. G., Sra S.: Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (TOG) 35, 4 (2016), 72:1–72:13.
- [Tu11] Tu L. W.: An Introduction to Manifolds (2nd edition). Springer-Verlag New York, 2011.
10.1007/978-1-4419-7400-6 Google Scholar
- [VLB*17] Vestner M., Lähner Z., Boyarski A., Litany O., Slossberg R., Remez T., Rodolà E., Bronstein A., Bronstein M., Kimmel R., Cremers D.: Efficient deformable shape correspondence via kernel matching. In Proceedings - 2017 International Conference on 3D Vision, 3DV 2017 (Qingdao, 2017), IEEE, pp. 517–526.
10.1109/3DV.2017.00065 Google Scholar
- [VLR*17] Vestner M., Litman R., Rodolà E., Bronstein A., Cremers D.: Product manifold filter: Non-rigid shape correspondence via kernel density estimation in the product space. In Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017 (Honolulu, 2017), IEEE, pp. 6681–6690.
10.1109/CVPR.2017.707 Google Scholar
- [WGBS18] Wang L., Gehre A., Bronstein M. M., Solomon J.: Kernel functional maps. Computer Graphics Forum 37, 5 (2018), 27–36.
- [Wit83] Witkin A. P.: Scale-space filtering. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence - Volume 2 (San Francisco, CA, USA, 1983), IJCAI'83, Morgan Kaufmann Publishers Inc., pp. 1019–1022.
- [WSSC11] Windheuser T., Schlickewei U., Schmidt F. R., Cremers D.: Geometrically consistent elastic matching of 3d shapes: A linear programming solution. In Proceedings/ICCV (Barcelona, 2011), IEEE.
10.1109/ICCV.2011.6126489 Google Scholar
- [ZWW*10] Zeng Y., Wang C., Wang Y., Gu X., Samaras D., Paragios N.: Dense non-rigid surface registration using high-order graph matching. In Proceedings/CVPR (San Francisco, 2010), IEEE.
10.1109/CVPR.2010.5540189 Google Scholar