“ZoomOut: spectral upsampling for efficient shape correspondence” by Melzi, Ren, Rodolà, Sharma, Wonka, et al. …
Conference:
Type(s):
Title:
- ZoomOut: spectral upsampling for efficient shape correspondence
Session/Category Title: Geometry Brekkie
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present a simple and efficient method for refining maps or correspondences by iterative upsampling in the spectral domain that can be implemented in a few lines of code. Our main observation is that high quality maps can be obtained even if the input correspondences are noisy or are encoded by a small number of coefficients in a spectral basis. We show how this approach can be used in conjunction with existing initialization techniques across a range of application scenarios, including symmetry detection, map refinement across complete shapes, non-rigid partial shape matching and function transfer. In each application we demonstrate an improvement with respect to both the quality of the results and the computational speed compared to the best competing methods, with up to two orders of magnitude speed-up in some applications. We also demonstrate that our method is both robust to noisy input and is scalable with respect to shape complexity. Finally, we present a theoretical justification for our approach, shedding light on structural properties of functional maps.
References:
1. Yonathan Aflalo, Anastasia Dubrovina, and Ron Kimmel. 2016. Spectral generalized multi-dimensional scaling. International Journal of Computer Vision 118, 3 (2016), 380–392.Google ScholarDigital Library
2. Yonathan Aflalo and Ron Kimmel. 2013. Spectral multidimensional scaling. PNAS 110, 45 (2013), 18052–18057.Google ScholarCross Ref
3. Dragomir Anguelov, Praveen Srinivasan, Daphne Koller, Sebastian Thrun, Jim Rodgers, and James Davis. 2005. SCAPE: Shape Completion and Animation of People. ACM Transactions on Graphics 24, 3 (July 2005), 408–416.Google ScholarDigital Library
4. Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on. IEEE, 1626–1633.Google ScholarCross Ref
5. 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
6. 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
7. Federica Bogo, Javier Romero, Matthew Loper, and Michael J. Black. 2014. FAUST: Dataset and evaluation for 3D mesh registration. In Proc. CVPR. IEEE, Columbus, Ohio, 3794–3801.Google Scholar
8. Alex Bronstein, Michael Bronstein, and Ron Kimmel. 2008. Numerical Geometry of Non-Rigid Shapes. Springer, New York, NY.Google Scholar
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. Qifeng Chen and Vladlen Koltun. 2015. Robust Nonrigid Registration by Convex Optimization. In International Conference on Computer Vision (ICCV). IEEE, 2039–2047.Google ScholarDigital Library
11. Etienne Corman, Maks Ovsjanikov, and Antonin Chambolle. 2015. Continuous matching via vector field flow. Computer Graphics Forum 34, 5 (2015), 129–139.Google ScholarCross Ref
12. Luca Cosmo, Emanuele Rodolà, Michael Bronstein, Andrea Torsello, Daniel Cremers, and Yusuf Sahillioğlu. 2016a. Partial Matching of Deformable Shapes. In Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval (3DOR ’16). Eurographics Association, 61–67. Google ScholarCross Ref
13. Luca Cosmo, Emanuele Rodolà, Jonathan Masci, Andrea Torsello, and Michael Bronstein. 2016b. Matching deformable objects in clutter. In Proc. 3D Vision (3DV). 1–10.Google ScholarCross Ref
14. Anastasia Dubrovina and Ron Kimmel. 2010. Matching shapes by eigendecomposition of the Laplace-Beltrami operator. In Proc. 3DPVT, Vol. 2.Google Scholar
15. Anastasia Dubrovina and Ron Kimmel. 2011. Approximately isometric shape correspondence by matching pointwise spectral features and global geodesic structures. Advances in Adaptive Data Analysis 3, 01n02 (2011), 203–228.Google ScholarCross Ref
16. Nadav Dym and Yaron Lipman. 2017. Exact recovery with symmetries for Procrustes matching. SIAM Journal on Optimization 27, 3 (2017), 1513–1530.Google ScholarCross Ref
17. 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
18. 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
19. 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
20. Philipp Gunz and Philipp Mitteroecker. 2013. Semilandmarks: a method for quantifying curves and surfaces. Hystrix, the Italian Journal of Mammalogy 24, 1 (2013), 103–109.Google Scholar
21. 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
22. Ruqi Huang and Maks Ovsjanikov. 2017. Adjoint Map Representation for Shape Analysis and Matching. Computer Graphics Forum 36, 5 (2017), 151–163.Google ScholarDigital Library
23. Alec Jacobson et al. 2018. gptoolbox: Geometry Processing Toolbox. http://github.com/alecjacobson/gptoolbox.Google Scholar
24. Varun Jain and Hao Zhang. 2006. Robust 3D shape correspondence in the spectral domain. In Shape Modeling and Applications, 2006. SMI 2006. IEEE International Conference on. IEEE, 19–19.Google Scholar
25. 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
26. Martin Kilian, Niloy J Mitra, and Helmut Pottmann. 2007. Geometric modeling in shape space. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 64.Google ScholarDigital Library
27. 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
28. 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
29. Artiom Kovnatsky, Klaus Glashoff, and Michael M Bronstein. 2016. MADMM: a generic algorithm for non-smooth optimization on manifolds. In European Conference on Computer Vision. Springer, 680–696.Google ScholarCross Ref
30. Zorah Lähner, Emanuele Rodolà, Michael Bronstein, Daniel Cremers, Oliver Burghard, Luca Cosmo, Alexander Dieckmann, Reinhard Klein, and Yusuf Sahillioğlu. 2016. Matching of Deformable Shapes with Topological Noise. In Proc. 3DOR. 55–60.Google Scholar
31. Or Litany, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein. 2017. Fully spectral partial shape matching. Computer Graphics Forum 36, 2 (2017), 247–258.Google ScholarDigital Library
32. Matthew Loper, Naureen Mahmood, Javier Romero, Gerard Pons-Moll, and Michael J. Black. 2015. SMPL: A Skinned Multi-person Linear Model. TOG 34, 6 (2015), 248:1–248:16.Google Scholar
33. 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
34. Riccardo Marin, Simone Melzi, Emanuele Rodolà, and Umberto Castellani. 2018. FARM: Functional Automatic Registration Method for 3D Human Bodies.Google Scholar
35. 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
36. 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
37. Simone Melzi, Riccardo Marin, Emanuele Rodolà, Umberto Castellani, Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. 2019. SHREC 2019: Matching Humans with Different Connectivity. In Eurographics Workshop on 3D Object Retrieval. The Eurographics Association.Google Scholar
38. Simone Melzi, Emanuele Rodolà, Umberto Castellani, and Michael Bronstein. 2016. Shape Analysis with Anisotropic Windowed Fourier Transform. In International Conference on 3D Vision (3DV).Google Scholar
39. Simone Melzi, Emanuele Rodolà, Umberto Castellani, and Michael Bronstein. 2018. Localized Manifold Harmonics for Spectral Shape Analysis. Computer Graphics Forum 37, 6 (2018), 20–34.Google ScholarCross Ref
40. Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbor Algorithms for High Dimensional Data. Pattern Analysis and Machine Intelligence, IEEE Transactions on 36 (2014).Google Scholar
41. Rajendra Nagar and Shanmuganathan Raman. 2018. Fast and Accurate Intrinsic Symmetry Detection. In The European Conference on Computer Vision (ECCV).Google Scholar
42. Dorian Nogneng, Simone Melzi, Emanuele Rodolà, Umberto Castellani, Michael Bronstein, and Maks Ovsjanikov. 2018. Improved Functional Mappings via Product Preservation. Computer Graphics Forum 37, 2 (2018), 179–190.Google ScholarCross Ref
43. 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
44. 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
45. 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
46. 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
47. Ulrich Pinkall and Konrad Polthier. 1993. Computing Discrete Minimal Surfaces and their Conjugates. Experimental mathematics 2, 1 (1993), 15–36.Google Scholar
48. Adrien Poulenard, Primoz Skraba, and Maks Ovsjanikov. 2018. Topological Function Optimization for Continuous Shape Matching. Computer Graphics Forum 37, 5 (2018), 13–25.Google ScholarCross Ref
49. 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
50. 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
51. 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
52. Emanuele Rodolà, Samuel Rota Bulò, Thomas Windheuser, Matthias Vestner, and Daniel Cremers. 2014. Dense non-rigid shape correspondence using random forests. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 4177–4184.Google ScholarDigital Library
53. Jean-Michel Roufosse, Abhishek Sharma, and Maks Ovsjanikov. 2018. Unsupervised Deep Learning for Structured Shape Matching. arXiv preprint arXiv:1812.03794 (2018).Google Scholar
54. Raif M Rustamov, Maks Ovsjanikov, Omri Azencot, Mirela Ben-Chen, Frédéric Chazal, and Leonidas Guibas. 2013. Map-based exploration of intrinsic shape differences and variability. ACM Transactions on Graphics (TOG) 32, 4 (2013), 72.Google ScholarDigital Library
55. Yusuf Sahillioğlu and Yücel Yemez. 2012. Minimum-distortion isometric shape correspondence using EM algorithm. IEEE transactions on pattern analysis and machine intelligence 34, 11 (2012), 2203–2215.Google ScholarDigital Library
56. Guy L Scott and Hugh Christopher Longuet-Higgins. 1991. An algorithm for associating the features of two images. Proc. R. Soc. Lond. B 244, 1309 (1991), 21–26.Google ScholarCross Ref
57. Meged Shoham, Amir Vaxman, and Mirela Ben-Chen. 2019. Hierarchical Functional Maps between Subdivision Surfaces. Computer Graphics Forum (2019). Google ScholarCross Ref
58. 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
59. Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Computer graphics forum 28, 5 (2009), 1383–1392.Google Scholar
60. 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
61. Federico Tombari, Samuele Salti, and Luigi Di Stefano. 2010. Unique signatures of histograms for local surface description. In Proc. ECCV. Springer, 356–369.Google Scholar
62. Shinji Umeyama. 1988. An eigendecomposition approach to weighted graph matching problems. IEEE transactions on pattern analysis and machine intelligence 10, 5 (1988), 695–703.Google ScholarDigital Library
63. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. Computer Graphics Forum 30, 6 (2011), 1681–1707.Google ScholarCross Ref
64. Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolà, Alex Bronstein, Michael Bronstein, and Ron Kimmel. 2017a. Efficient deformable shape correspondence via kernel matching. In 3D Vision (3DV), 2017 International Conference on. IEEE, 517–526.Google Scholar
65. 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
66. Fan Wang, Qixing Huang, and Leonidas J. Guibas. 2013. Image Co-segmentation via Consistent Functional Maps. In Proc. ICCV. 849–856.Google Scholar
67. 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
68. Larry Wang, Anne Gehre, Michael Bronstein, and Justin Solomon. 2018a. Kernel Functional Maps. Computer Graphics Forum 37, 5 (2018), 27–36.Google ScholarCross Ref
69. 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
70. 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
