“MapTree: recovering multiple solutions in the space of maps” by Ren, Melzi, Ovsjanikov and Wonka
Conference:
Type(s):
Title:
- MapTree: recovering multiple solutions in the space of maps
Session/Category Title: Shape Analysis
Presenter(s)/Author(s):
Abstract:
In this paper we propose an approach for computing multiple high-quality near-isometric dense correspondences between a pair of 3D shapes. Our method is fully automatic and does not rely on user-provided landmarks or descriptors. This allows us to analyze the full space of maps and extract multiple diverse and accurate solutions, rather than optimizing for a single optimal correspondence as done in most previous approaches. To achieve this, we propose a compact tree structure based on the spectral map representation for encoding and enumerating possible rough initializations, and a novel efficient approach for refining them to dense pointwise maps. This leads to a new method capable of both producing multiple high-quality correspondences across shapes and revealing the symmetry structure of a shape without a priori information. In addition, we demonstrate through extensive experiments that our method is robust and results in more accurate correspondences than state-of-the-art for shape matching and symmetry detection.
References:
1. Yonathan Aflalo and Ron Kimmel. 2013. Spectral multidimensional scaling. PNAS 110, 45 (2013), 18052–18057.Google ScholarCross Ref
2. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Transactions on Graphics 35, 6 (Nov. 2016), 217:1–217:14.Google ScholarDigital Library
3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Transactions on Graphics (TOG) 34, 4, Article Article 72 (July 2015), 13 pages.Google ScholarDigital Library
4. Marc Arnaudon, Anton Thalmaier, and Feng-Yu Wang. 2017. Gradient Estimates on Dirichlet Eigenfunctions. arXiv preprint arXiv:1710.10832 (2017).Google Scholar
5. Omri Azencot, Anastasia Dubrovina, and Leonidas Guibas. 2019. Consistent Shape Matching via Coupled Optimization. Computer Graphics Forum 38, 5 (2019), 13–25.Google ScholarCross Ref
6. Mikhail Belkin, Jian Sun, and Yusu Wang. 2009. Constructing Laplace Operator from Point Clouds in Rd. In Proc. Symposium on Discrete Algorithms (SODA). 1031–1040.Google Scholar
7. Silvia Biasotti, Andrea Cerri, Alex Bronstein, and Michael Bronstein. 2016. Recent trends, applications, and perspectives in 3D shape similarity assessment. Computer Graphics Forum 35, 6 (2016), 87–119.Google ScholarDigital Library
8. Alex Bronstein, Michael Bronstein, and Ron Kimmel. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences 103, 5 (2006), 1168–1172.Google ScholarCross Ref
9. Oliver Burghard, Alexander Dieckmann, and Reinhard Klein. 2017. Embedding shapes with Green’s functions for global shape matching. Computers & Graphics 68 (2017), 1–10.Google ScholarCross Ref
10. Harold Donnelly. 2006. Eigenfunctions of the Laplacian on compact Riemannian manifolds. Asian Journal of Mathematics 10, 1 (2006), 115–126.Google ScholarCross Ref
11. Nadav Dym, Haggai Maron, and Yaron Lipman. 2017. DS++: a flexible, scalable and provably tight relaxation for matching problems. ACM Transactions on Graphics (TOG) 36, 6 (2017), 184.Google ScholarDigital Library
12. Marvin Eisenberger, Zorah Lähner, and Daniel Cremers. 2019. Divergence-Free Shape Correspondence by Deformation. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 1–12.Google Scholar
13. D. Eynard, E. Rodolà, K. Glashoff, and M. M. Bronstein. 2016. Coupled Functional Maps. In 2016 Fourth International Conference on 3D Vision (3DV). 399–407.Google Scholar
14. Danielle Ezuz and Mirela Ben-Chen. 2017. Deblurring and Denoising of Maps between Shapes. Computer Graphics Forum 36, 5 (2017), 165–174.Google ScholarDigital Library
15. Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen. 2019. Reversible Harmonic Maps Between Discrete Surfaces. ACM Trans. Graph. 38, 2 (2019), 15:1–15:12.Google ScholarDigital Library
16. Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d’Aspremont. 2013. Convex relaxations for permutation problems. In Advances in Neural Information Processing Systems. 1016–1024.Google Scholar
17. Anne Gehre, Michael Bronstein, Leif Kobbelt, and Justin Solomon. 2018. Interactive curve constrained functional maps. Computer Graphics Forum 37, 5 (2018), 1–12.Google Scholar
18. Oshri Halimi, Or Litany, Emanuele Rodola, Alex M Bronstein, and Ron Kimmel. 2019. Unsupervised learning of dense shape correspondence. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 4370–4379.Google ScholarCross Ref
19. Kai Hormann and Günther Greiner. 2000. MIPS: An efficient global parametrization method. Technical Report. ERLANGEN-NUERNBERG UNIV (GERMANY) COMPUTER GRAPHICS GROUP.Google Scholar
20. Qixing Huang, Fan Wang, and Leonidas Guibas. 2014. Functional map networks for analyzing and exploring large shape collections. ACM Transactions on Graphics (TOG) 33, 4 (2014), 36.Google ScholarDigital Library
21. Qi-Xing Huang, Bart Adams, Martin Wicke, and Leonidas J Guibas. 2008. Non-rigid registration under isometric deformations. Computer Graphics Forum 27, 5 (2008), 1449–1457.Google ScholarDigital Library
22. Varun Jain, Hao Zhang, and Oliver van Kaick. 2007. Non-rigid spectral correspondence of triangle meshes. International Journal of Shape Modeling 13, 01 (2007), 101–124.Google ScholarCross Ref
23. Itay Kezurer, Shahar Z Kovalsky, Ronen Basri, and Yaron Lipman. 2015. Tight relaxation of quadratic matching. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 115–128.Google Scholar
24. Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended intrinsic maps. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 79.Google ScholarDigital Library
25. Yanir Kleiman and Maks Ovsjanikov. 2018. Robust Structure-Based Shape Correspondence. In Computer Graphics Forum. Wiley Online Library.Google Scholar
26. Johannes Kobler, Uwe Schöning, and Jacobo Torán. 2012. The graph isomorphism problem: its structural complexity. Springer Science & Business Media.Google Scholar
27. Artiom Kovnatsky, Michael Bronstein, Alex Bronstein, Klaus Glashoff, and Ron Kimmel. 2013. Coupled quasi-harmonic bases. Computer Graphics Forum 32, 2pt4 (2013), 439–448.Google Scholar
28. Marius Leordeanu and Martial Hebert. 2005. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, Vol. 2. IEEE, 1482–1489.Google ScholarDigital Library
29. Yaron Lipman, Xiaobai Chen, Ingrid Daubechies, and Thomas Funkhouser. 2010. Symmetry factored embedding and distance. In ACM Transactions on Graphics (TOG), Vol. 29. ACM, 103.Google ScholarDigital Library
30. Yaron Lipman and Thomas Funkhouser. 2009. MÖBius Voting for Surface Correspondence. ACM Trans. Graph. 28, 3, Article 72 (July 2009), 12 pages.Google ScholarDigital Library
31. Or Litany, Tal Remez, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein. 2017a. Deep Functional Maps: Structured Prediction for Dense Shape Correspondence. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 5659–5667.Google ScholarCross Ref
32. Or Litany, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein. 2017b. Fully spectral partial shape matching. Computer Graphics Forum 36, 2 (2017), 247–258.Google ScholarDigital Library
33. Xiuping Liu, Shuhua Li, Risheng Liu, Jun Wang, Hui Wang, and Junjie Cao. 2015. Properly Constrained Orthonormal Functional Maps for Intrinsic Symmetries. Computer and Graphics 46, C (Feb. 2015), 198–208.Google Scholar
34. Yanxi Liu, Hagit Hel-Or, Craig Kaplan, and Luc Van Gool. 2010. Computational Symmetry in Computer Vision and Computer Graphics. Foundations and Trends in Computer Graphics and Vision 5 (01 2010), 1–199.Google Scholar
35. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-Minimizing Transport Plans for Inter-surface Mapping. ACM Transactions on Graphics 36 (2017), 14.Google ScholarDigital Library
36. Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman. 2016. Point registration via efficient convex relaxation. ACM Transactions on Graphics (TOG) 35, 4 (2016), 73.Google ScholarDigital Library
37. Diana Mateus, Radu Horaud, David Knossow, Fabio Cuzzolin, and Edmond Boyer. 2008. Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration. In Proc. CVPR. 1–8.Google ScholarCross Ref
38. R Mathon. 1979. A note on the graph isomorphism counting problem. Inf. Process. Lett. 8, 3 (1979), 131–132.Google ScholarCross Ref
39. Simone Melzi, Riccardo Marin, Emanuele Rodolà, Umberto Castellani, Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. 2019a. SHREC 2019: Matching Humans with Different Connectivity. In Eurographics Workshop on 3D Object Retrieval. The Eurographics Association.Google Scholar
40. Simone Melzi, Jing Ren, Emanuele Rodolà, Abhishek Sharma, Peter Wonka, and Maks Ovsjanikov. 2019b. ZoomOut: Spectral Upsampling for Efficient Shape Correspondence. ACM Transactions on Graphics (TOG) 38, 6, Article 155 (Nov. 2019), 14 pages. Google ScholarDigital Library
41. Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H Barr. 2003. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In Visualization and mathematics III. Springer, New York, NY, 35–57.Google Scholar
42. Niloy J Mitra, Leonidas J Guibas, and Mark Pauly. 2006. Partial and approximate symmetry detection for 3D geometry. ACM Transactions on Graphics (TOG) 25, 3 (2006), 560–568.Google ScholarDigital Library
43. Niloy J. Mitra, Mark Pauly, Michael Wand, and Duygu Ceylan. 2013. Symmetry in 3D Geometry: Extraction and Applications. Computer Graphics Forum 32, 6 (2013), 1–23.Google ScholarDigital Library
44. Rajendra Nagar and Shanmuganathan Raman. 2018. Fast and Accurate Intrinsic Symmetry Detection. In The European Conference on Computer Vision (ECCV).Google Scholar
45. Dorian Nogneng and Maks Ovsjanikov. 2017. Informative Descriptor Preservation via Commutativity for Shape Matching. Computer Graphics Forum 36, 2 (2017), 259–267.Google ScholarDigital Library
46. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 30:1–30:11.Google ScholarDigital Library
47. Maks Ovsjanikov, Etienne Corman, Michael Bronstein, Emanuele Rodolà, Mirela Ben-Chen, Leonidas Guibas, Frederic Chazal, and Alex Bronstein. 2017. Computing and Processing Correspondences with Functional Maps. In ACM SIGGRAPH 2017 Courses. Article 5, 5:1–5:62 pages.Google Scholar
48. Maks Ovsjanikov, Quentin Merigot, Facundo Memoli, and Leonidas Guibas. 2010. One Point Isometric Matching with the Heat Kernel. CGF 29, 5 (2010), 1555–1564. Google ScholarCross Ref
49. Maks Ovsjanikov, Jian Sun, and Leo Guibas. 2008. Global intrinsic symmetries of shapes. Comp. Graph. Forum 27, 5 (2008), 1341–1348.Google ScholarDigital Library
50. Dan Raviv, Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. 2010. Full and Partial Symmetries of Non-rigid Shapes. International Journal of Computer Vision 89 (July 2010), 18–39.Google ScholarDigital Library
51. Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. 2018. Continuous and Orientation-preserving Correspondences via Functional Maps. ACM Transactions on Graphics (TOG) 37, 6 (2018).Google ScholarDigital Library
52. Emanuele Rodolà, Luca Cosmo, Michael Bronstein, Andrea Torsello, and Daniel Cremers. 2017. Partial functional correspondence. Computer Graphics Forum 36, 1 (2017), 222–236.Google ScholarDigital Library
53. Emanuele Rodolà, Michael Moeller, and Daniel Cremers. 2015. Point-wise Map Recovery and Refinement from Functional Correspondence. In Proc. Vision, Modeling and Visualization (VMV).Google Scholar
54. Jean-Michel Roufosse, Abhishek Sharma, and Maks Ovsjanikov. 2019. Unsupervised deep learning for structured shape matching. In Proceedings of the IEEE International Conference on Computer Vision. 1617–1627.Google ScholarCross Ref
55. Raif M Rustamov. 2007. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proc. SGP. Eurographics Association, 225–233.Google Scholar
56. Yusuf Sahillioğlu. 2018. A genetic isometric shape correspondence algorithm with adaptive sampling. ACM Transactions on Graphics (TOG) 37, 5 (2018), 1–14.Google ScholarDigital Library
57. Yusuf Sahillioğlu and Yücel Yemez. 2013. Coarse-to-fine isometric shape correspondence by tracking symmetric flips. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 177–189.Google Scholar
58. Nicholas Sharp and Keenan Crane. 2020. A Laplacian for Nonmanifold Triangle Meshes. In Proc. SGP.Google ScholarCross Ref
59. Meged Shoham, Amir Vaxman, and Mirela Ben-Chen. 2019. Hierarchical Functional Maps between Subdivision Surfaces. Computer Graphics Forum (2019).Google Scholar
60. Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. 2012. Soft Maps Between Surfaces. Computer Graphics Forum 31, 5 (2012), 1617–1626.Google ScholarDigital Library
61. Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. 2016. Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (TOG) 35, 4 (2016), 72.Google ScholarDigital Library
62. Min-Hyuk Sung and Junho Kim. 2013. Finding the M-best consistent correspondences between 3D symmetric objects. Computers & graphics 37, 1–2 (2013), 81–92.Google Scholar
63. Gary KL Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank C Langbein, Yonghuai Liu, David Marshall, Ralph R Martin, Xian-Fang Sun, and Paul L Rosin. 2013. Registration of 3D point clouds and meshes: a survey from rigid to nonrigid. IEEE TVCG 19, 7 (2013), 1199–1217.Google Scholar
64. Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolà, Alex Bronstein, Michael Bronstein, and Ron Kimmel. 2017a.Google Scholar
65. Efficient deformable shape correspondence via kernel matching. In 3D Vision (3DV), 2017 International Conference on. IEEE, 517–526.Google Scholar
66. Matthias Vestner, Roee Litman, Emanuele Rodolà, Alex Bronstein, and Daniel Cremers. 2017b. Product Manifold Filter: Non-rigid Shape Correspondence via Kernel Density Estimation in the Product Space. In Proc. CVPR. 6681–6690.Google ScholarCross Ref
67. Fan Wang, Qixing Huang, and Leonidas J. Guibas. 2013. Image Co-segmentation via Consistent Functional Maps. In Proc. ICCV. 849–856.Google Scholar
68. Hui Wang and Hui Huang. 2017. Group representation of global intrinsic symmetries. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 51–61.Google Scholar
69. Larry Wang, Anne Gehre, Michael Bronstein, and Justin Solomon. 2018a. Kernel Functional Maps. Computer Graphics Forum 37, 5 (2018), 27–36.Google ScholarCross Ref
70. Lanhui Wang and Amit Singer. 2013. Exact and stable recovery of rotations for robust synchronization. Information and Inference: A Journal of the IMA 2, 2 (2013), 145–193.Google ScholarCross Ref
71. Tuanfeng Y. Wang, Tianjia Shao, Kai Fu, and Niloy J. Mitra. 2019. Learning an intrinsic garment space for interactive authoring of garment animation. ACM Transactions on Graphics (TOG) 38, 6 (2019), 220:1–220:12. Google ScholarDigital Library
72. Y Wang, B Liu, K Zhou, and Y Tong. 2018b. Vector Field Map Representation for Near Conformal Surface Correspondence. Computer Graphics Forum 37, 6 (2018), 72–83.Google ScholarCross Ref
73. Kai Xu, Hao Zhang, Wei Jiang, Ramsay Dyer, Zhiquan Cheng, Ligang Liu, and Baoquan Chen. 2012. Multi-scale partial intrinsic symmetry detection. ACM Transactions on Graphics (TOG) 31, 6 (2012), 181.Google ScholarDigital Library
74. Kai Xu, Hao Zhang, Andrea Tagliasacchi, Ligang Liu, Guo Li, Min Meng, and Yueshan Xiong. 2009. Partial intrinsic reflectional symmetry of 3D shapes. ACM Transactions on Graphics (TOG) 28, 5 (2009), 138.Google ScholarDigital Library
