skip to main content
10.1145/3084873.3084877acmconferencesArticle/Chapter ViewAbstractPublication PagessiggraphConference Proceedingsconference-collections
course

Computing and processing correspondences with functional maps

Published: 30 July 2017 Publication History

Abstract

Notions of similarity and correspondence between geometric shapes and images are central to many tasks in geometry processing, computer vision, and computer graphics. The goal of this course is to familiarize the audience with a set of recent techniques that greatly facilitate the computation of mappings or correspondences between geometric datasets, such as 3D shapes or 2D images by formulating them as mappings between functions rather than points or triangles.
Methods based on the functional map framework have recently led to state-of-the-art results in problems as diverse as non-rigid shape matching, image co-segmentation and even some aspects of tangent vector field design. One challenge in adopting these methods in practice, however, is that their exposition often assumes a significant amount of background in geometry processing, spectral methods and functional analysis, which can make it difficult to gain an intuition about their performance or about their applicability to real-life problems. In this course, we try to provide all the tools necessary to appreciate and use these techniques, while assuming very little background knowledge. We also give a unifying treatment of these techniques, which may be difficult to extract from the individual publications and, at the same time, hint at the generality of this point of view, which can help tackle many problems in the analysis and creation of visual content.
This course is structured as a half day course. We will assume that the participants have knowledge of basic linear algebra and some knowledge of differential geometry, to the extent of being familiar with the concepts of a manifold and a tangent vector space. We will discuss in detail the functional approach to finding correspondences between non-rigid shapes, the design and analysis of tangent vector fields on surfaces, consistent map estimation in networks of shapes and applications to shape and image segmentation, shape variability analysis, and other areas.

Supplementary Material

Part 1 of 3 (courses-0055-a.mp4)
Part 2 of 3 (courses-0055-d.mp4)
Part 3 of 3 (courses-0055-h.mp4)

References

[1]
[ABCCO13] O. Azencot, M. Ben-Chen, F. Chazal Chazal, and M. Ovsjanikov. An operator approach to tangent vector field processing. Computer Graphics Forum, 32(5):73--82, 2013.
[2]
[ACBCO17] Omri Azencot, Etienne Corman, Mirela Ben-Chen, and Maks Ovsjanikov. Consistent functional cross field design for mesh quadrangulation. ACM Trans. Graph., 36(4):92:1--92:13, 2017.
[3]
[AMH11] A. H. Al-Mohy and N. J. Higham. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Scientific Computing, 33(2):488--511, 2011.
[4]
[AMS09] P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
[5]
[ASC11] M. Aubry, U. Schlickewei, and D. Cremers. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proc. Workshop on Dynamic Shape Capture and Analysis, 2011.
[6]
[ASK+05] D. Anguelov, P. Srinivasan, D. Koller, S. Thrun, J. Rodgers, and J. Davis. SCAPE: shape completion and animation of people. ACM Trans. Graphics, 24(3):408--416, 2005.
[7]
[AVBC16] O. Azencot, O. Vantzos, and M. Ben-Chen. Advection-Based Function Matching on Surfaces. Computer Graphics Forum, 2016.
[8]
[AVW+15] O. Azencot, O. Vantzos, M. Wardetzky, M. Rumpf, and M. Ben-Chen. Functional thin films on surfaces. In Proc. Symp. Computer Animation, 2015.
[9]
[AWO+14] O. Azencot, S. Weißmann, M. Ovsjanikov, M. Wardetzky, and M. Ben-Chen. Functional fluids on surfaces. Computer Graphics Forum, 33(5):237--246, 2014.
[10]
[BB08] A. M. Bronstein and M. M. Bronstein. Not only size matters: regularized partial matching of nonrigid shapes. In Proc. NORDIA, 2008.
[11]
[BBK08] A. M. Bronstein, M. M. Bronstein, and R. Kimmel. Numerical Geometry of Non-Rigid Shapes. Springer, 2008.
[12]
[BEKB15] D. Boscaini, D. Eynard, D. Kourounis, and M. M. Bronstein. Shape-from-operator: Recovering shapes from intrinsic operators. Computer Graphics Forum, 34(2):265--274, 2015.
[13]
[Ber98] D. P. Bertsekas. Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.
[14]
[BLP+13] David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. Quad-mesh generation and processing: A survey. In Computer Graphics Forum, volume 32, pages 51--76. Wiley Online Library, 2013.
[15]
[BM92] P. J. Besl and N. D. McKay. A method for registration of 3-D shapes. Trans. PAMI, 14:239--256, 1992.
[16]
[BZK09] David Bommes, Henrik Zimmer, and Leif Kobbelt. Mixed-integer quadrangulation. ACM Transactions On Graphics (TOG), 28(3):77, 2009.
[17]
[CLMW11] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM, 58(3):1--37, 2011.
[18]
[COC14] E. Corman, M. Ovsjanikov, and A. Chambolle. Supervised descriptor learning for non-rigid shape matching. In Proc. NORDIA, 2014.
[19]
[COC15] E. Corman, M. Ovsjanikov, and A. Chambolle. Continuous matching via vector field flow. Computer Graphics Forum, 34(5):129--139, 2015.
[20]
[CR09] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6):717--772, 2009.
[21]
[CRB+16] L. Cosmo, E. Rodolà, M. M. Bronstein, et al. SHREC'16: Partial matching of deformable shapes. In Proc. 3DOR, 2016.
[22]
[CRM+16] L. Cosmo, E. Rodolà, J. Masci, A. Torsello, and M. Bronstein. Matching deformable objects in clutter. In Proc. 3DV, 2016.
[23]
[CSBC+16] E. Corman, J. Solomon, M. Ben-Chen, L. J. Guibas, and M. Ovsjanikov. Functional characterization of intrinsic and extrinsic geometry. ACM Trans. Graphics, 2016. under review.
[24]
[EBCK13] Hans-Christian Ebke, David Bommes, Marcel Campen, and Leif Kobbelt. QEx: robust quad mesh extraction. ACM Transactions on Graphics (TOG), 32(6):168, 2013.
[25]
[EKB+15] D. Eynard, A. Kovnatsky, M. M. Bronstein, K. Glashoff, and A. M. Bronstein. Multimodal manifold analysis by simultaneous diagonalization of Laplacians. Trans. PAMI, 37(12):2505--2517, 2015.
[26]
[ERGB16] D. Eynard, E. Rodolà, K. Glashoff, and M. M. Bronstein. Coupled functional maps. In Proc. 3DV, 2016.
[27]
[GB16] K. Glashoff and M. M. Bronstein. Optimization on the biorthogonal manifold. arXiv:1609.04161, 2016.
[28]
[HG13] Q. Huang and L. J. Guibas. Consistent shape maps via semidefinite programming. Computer Graphics Forum, 32(5):177--186, 2013.
[29]
[HO10] M. Hochbruck and A. Ostermann. Exponential integrators. Acta Numerica, 19:209--286, 2010.
[30]
[HWG14] Q. Huang, F. Wang, and L. J. Guibas. Functional map networks for analyzing and exploring large shape collections. ACM Trans. Graphics, 33(4):36:1--36:11, July 2014.
[31]
[JZvK07] V. Jain, H. Zhang, and O. van Kaick. Non-rigid spectral correspondence of triangle meshes. International J. Shape Modeling, 13(1):101--124, 2007.
[32]
[Kat95] T. Kato. Perturbation Theory for Linear Operators. Springer, 1995.
[33]
[KBB+12] A. Kovnatsky, M. Bronstein, A. Bronstein, K. Glashoff, and R. Kimmel. Coupled quasi-harmonic bases. Computer Graphics Forum, 32:439--448, 2012.
[34]
[KBBV14] V. Kalofolias, X. Bresson, M. M. Bronstein, and P. Vandergheynst. Matrix completion on graphs. arXiv:1408.1717, 2014.
[35]
[KBBV15] A. Kovnatsky, M. Bronstein, X. Bresson, and P. Vandergheynst. Functional correspondence by matrix completion. In Proc. CVPR, 2015.
[36]
[KGB16] A. Kovnatsky, K. Glashoff, and M. M. Bronstein. MADMM: A generic algorithm for non-smooth optimization on manifolds. In Proc. ECCV, 2016.
[37]
[KLF11] V. G. Kim, Y. Lipman, and T. Funkhouser. Blended intrinsic maps. ACM Trans. Graphics, 30(4), 2011.
[38]
[Kuh55] H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1--2):83--97, March 1955.
[39]
[LBB11] R. Litman, A. M. Bronstein, and M. M. Bronstein. Diffusion-geometric maximally stable component detection in deformable shapes. Computers & Graphics, 35(3):549 -- 560, 2011.
[40]
[LBB12] O. Litany, A. M. Bronstein, and M. M. Bronstein. Putting the pieces together: Regularized multi-part shape matching. In Proc. NORDIA, 2012.
[41]
[LRB+16] O. Litany, E. Rodolà, A. M. Bronstein, M. M. Bronstein, and D. Cremers. Non-rigid puzzles. Computer Graphics Forum, 35(5), 2016.
[42]
[LRBB17] O. Litany, E. Rodolà, A. M. Bronstein, and M. M. Bronstein. Fully spectral partial shape matching. Computer Graphics Forum, 36(2), 2017.
[43]
[MDSB02] M. Meyer, M. Desbrun, P. Schröder, and A. H. Barr. Discrete differential geometry operators for triangulated 2-manifolds. In Proc. VisMath, 2002.
[44]
[MHK+08] D. Mateus, R. P. Horaud, D. Knossow, F. Cuzzolin, and E. Boyer. Articulated shape matching using laplacian eigenfunctions and unsupervised point registration. In Proc. CVPR, 2008.
[45]
[MS10] A. Myronenko and X. Song. Point set registration: Coherent point drift. Trans. PAMI, 32(12):2262--2275, 2010.
[46]
[NO17] Dorian Nogneng and Maks Ovsjanikov. Informative Descriptor Preservation via Commutativity for Shape Matching. Computer Graphics Forum (Proc. Eurographics), 2017.
[47]
[OBCS+12] M. Ovsjanikov, M. Ben-Chen, J. Solomon, A. Butscher, and L. J. Guibas. Functional maps: a flexible representation of maps between shapes. ACM Trans. Graphics, 31(4):30:1--30:11, 2012.
[48]
[OLCO13] V. Ozolinš, R. Lai, R. Caflisch, and S. Osher. Compressed modes for variational problems in mathematics and physics. PNAS, 110(46):18368--18373, 2013.
[49]
[OMMG10] M. Ovsjanikov, Q. Merigot, F. Memoli, and L. J. Guibas. One point isometric matching with the heat kernel. Computer Graphics Forum, 29(5):1555--1564, 2010.
[50]
[OMPG13] Maks Ovsjanikov, Quentin Mérigot, Viorica Pă;trăucean, and Leonidas Guibas. Shape matching via quotient spaces. In Computer Graphics Forum, volume 32, pages 1--11. Wiley Online Library, 2013.
[51]
[OSG08] M. Ovsjanikov, J. Sun, and L. J. Guibas. Global intrinsic symmetries of shapes. Computer Graphics Forum, 27(5):1341--1348, 2008.
[52]
[PBB+13] J. Pokrass, A. M. Bronstein, M. M. Bronstein, P. Sprechmann, and G. Sapiro. Sparse modeling of intrinsic correspondences. Computer Graphics Forum, 32:459--468, 2013.
[53]
[PP93] U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1):15--36, 1993.
[54]
[RCB+16] E. Rodolà, L. Cosmo, M. M. Bronstein, A. Torsello, and D. Cremers. Partial functional correspondence. Computer Graphics Forum, 2016.
[55]
[RMC] E. Rodolà, M. Moeller, and D. Cremers. Regularized point-wise map recovery from functional correspondence. Computer Graphics Forum. to appear.
[56]
[RMC15] E. Rodolà, M. Moeller, and D. Cremers. Point-wise map recovery and refinement from functional correspondence. In Proc. VMV, 2015.
[57]
[ROA+13] R. M. Rustamov, M. Ovsjanikov, O. Azencot, M. Ben-Chen, F. Chazal, and L. J. Guibas. Map-based exploration of intrinsic shape differences and variability. ACM Trans. Graphics, 32(4):72:1--72:12, July 2013.
[58]
[Rus07] R. M. Rustamov. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proc. SGP, 2007.
[59]
[SOCG10] P. Skraba, M. Ovsjanikov, F. Chazal, and L. J. Guibas. Persistence-based segmentation of deformable shapes. In Proc. NORDIA, pages 45--52, June 2010.
[60]
[SOG09] J. Sun, M. Ovsjanikov, and L. J. Guibas. A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion. Computer Graphics Forum, 28(5), 2009.
[61]
[SRJ04] N. Srebro, J. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization. In Proc. NIPS, 2004.
[62]
[SY11] Y. Sahillioǧlu and Y. Yemez. Coarse-to-fine combinatorial matching for dense isometric shape correspondence. Computer Graphics Forum, 30(5):1461--1470, 2011.
[63]
[VLR+17] M. Vestner, R. Litman, E. Rodolà, A. M. Bronstein, and D. Cremers. Product manifold filter: Non-rigid shape correspondence via kernel density estimation in the product space. In Proc. CVPR, 2017.
[64]
[WHOG14] F. Wang, Q. Huang, M. Ovsjanikov, and L. J. Guibas. Unsupervised multi-class joint image segmentation. In Proc. CVPR, 2014.
[65]
[WS13] L. Wang and A. Singer. Exact and stable recovery of rotations for robust synchronization. Information and Inference, 2(2):145--193, 2013.
[66]
[YL06] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. J. Royal Statistical Society B, 68:49--67, 2006.
[67]
[ZGLG12] W. Zeng, R. Guo, F. Luo, and X. Gu. Discrete heat kernel determines discrete Riemannian metric. Graph. Models, 74(4):121--129, 2012.

Cited By

View all
  • (2025)Leveraging descriptor learning and functional map‐based shape matching for automated anatomical Landmarking in mouse mandiblesJournal of Anatomy10.1111/joa.14196Online publication date: 15-Jan-2025
  • (2024)Deformation Recovery: Localized Learning for Detail-Preserving DeformationsACM Transactions on Graphics10.1145/368796843:6(1-16)Online publication date: 19-Dec-2024
  • (2024)Multiscale Spectral Manifold Wavelet Regularizer for Unsupervised Deep Functional MapsComputer Graphics Forum10.1111/cgf.1523043:7Online publication date: 4-Nov-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGGRAPH '17: ACM SIGGRAPH 2017 Courses
July 2017
2467 pages
ISBN:9781450350143
DOI:10.1145/3084873
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2017

Check for updates

Qualifiers

  • Course

Conference

SIGGRAPH '17
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)51
  • Downloads (Last 6 weeks)11
Reflects downloads up to 03 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Leveraging descriptor learning and functional map‐based shape matching for automated anatomical Landmarking in mouse mandiblesJournal of Anatomy10.1111/joa.14196Online publication date: 15-Jan-2025
  • (2024)Deformation Recovery: Localized Learning for Detail-Preserving DeformationsACM Transactions on Graphics10.1145/368796843:6(1-16)Online publication date: 19-Dec-2024
  • (2024)Multiscale Spectral Manifold Wavelet Regularizer for Unsupervised Deep Functional MapsComputer Graphics Forum10.1111/cgf.1523043:7Online publication date: 4-Nov-2024
  • (2024)Neural Semantic Surface MapsComputer Graphics Forum10.1111/cgf.1500543:2Online publication date: 17-Apr-2024
  • (2024)Task-Informed Grasping of Partially Observed ObjectsIEEE Robotics and Automation Letters10.1109/LRA.2024.34456339:10(8394-8401)Online publication date: Oct-2024
  • (2024)Pedicle Drilling Planning Transfer for Spine Surgery Using Functional Map Correspondences2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS58592.2024.10802159(6947-6952)Online publication date: 14-Oct-2024
  • (2024)Memory-Scalable and Simplified Functional Map Learning2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00387(4041-4050)Online publication date: 16-Jun-2024
  • (2024)Unsupervised Representation Learning for Diverse Deformable Shape Collections2024 International Conference on 3D Vision (3DV)10.1109/3DV62453.2024.00158(1594-1604)Online publication date: 18-Mar-2024
  • (2024)Bijective upsampling and learned embedding for point clouds correspondencesComputers & Graphics10.1016/j.cag.2024.103985122(103985)Online publication date: Aug-2024
  • (2023)Shape Non-rigid Kinematics (SNK)Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669190(70012-70032)Online publication date: 10-Dec-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media