“ENIGMA: evolutionary non-isometric geometry Matching” by Edelstein, Ezuz and Ben-Chen
Conference:
Type:
Title:
- ENIGMA: evolutionary non-isometric geometry Matching
Session/Category Title: Motion and Matching
Presenter(s)/Author(s):
Abstract:
In this paper we propose a fully automatic method for shape correspondence that is widely applicable, and especially effective for non isometric shapes and shapes of different topology. We observe that fully-automatic shape correspondence can be decomposed as a hybrid discrete/continuous optimization problem, and we find the best sparse landmark correspondence, whose sparse-to-dense extension minimizes a local metric distortion. To tackle the combinatorial task of landmark correspondence we use an evolutionary genetic algorithm, where the local distortion of the sparse-to-dense extension is used as the objective function. We design novel geometrically guided genetic operators, which, when combined with our objective, are highly effective for non isometric shape matching. Our method outperforms state of the art methods for automatic shape correspondence both quantitatively and qualitatively on challenging datasets.
References:
1. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM TOG 34 (2015).Google Scholar
2. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM TOG 35 (2016).Google Scholar
3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless surface mappings. ACM TOG 34, 4 (2015), 72.Google ScholarDigital Library
4. Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. 2011. The Wave Kernel Signature: A Quantum Mechanical Approach to Shape Analysis. In International Conference on Computer Vision Workshops (ICCV Workshops). IEEE.Google ScholarCross Ref
5. Surapong Auwatanamongkol. 2007. Inexact graph matching using a genetic algorithm for image recognition. Pattern Recognition Letters 28, 12 (2007), 1428–1437.Google ScholarDigital Library
6. Thomas Back. 1996. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press.Google Scholar
7. Bir Bhanu, Sungkee Lee, and John Ming. 1995. Adaptive image segmentation using a genetic algorithm. IEEE Trans on systems, man, and cybernetics 25, 12 (1995), 1543–1567.Google ScholarCross Ref
8. Davide Boscaini, Jonathan Masci, Emanuele Rodolà, and Michael Bronstein. 2016. Learning shape correspondence with anisotropic convolutional neural networks. In Advances in Neural Information Processing Systems. 3189–3197.Google Scholar
9. Mario Botsch, Mark Pauly, Markus H Gross, and Leif Kobbelt. 2006. PriMo: coupled prisms for intuitive surface modeling. In Proc. Eurographics SGP. 11–20.Google Scholar
10. Alexandru Horia Brie and Philippe Morignot. 2005. Genetic Planning Using Variable Length Chromosomes.. In ICAPS. 320–329.Google Scholar
11. Xiuyuan Cheng, Gal Mishne, and Stefan Steinerberger. 2018. The geometry of nodal sets and outlier detection. Journal of Number Theory 185 (2018), 48–64.Google ScholarCross Ref
12. Chi Kin Chow, Hung Tat Tsui, and Tong Lee. 2004. Surface registration using a dynamic genetic algorithm. Pattern recognition 37, 1 (2004), 105–117.Google Scholar
13. Andrew DJ Cross, Richard C Wilson, and Edwin R Hancock. 1997. Inexact graph matching using genetic search. Pattern Recognition 30, 6 (1997), 953–970.Google ScholarCross Ref
14. Maya de Buhan, Charles Dapogny, Pascal Frey, and Chiara Nardoni. 2016. An optimization method for elastic shape matching. C. R. Math. Acad. Sci. Paris 354, 8 (2016), 783–787.Google ScholarCross Ref
15. Roberto Dyke, Caleb Stride, Yu-Kun Lai, and Paul L. Rosin. 2019. SHREC 2019. https://shrec19.cs.cf.ac.uk/.Google Scholar
16. Nadav Dym, Haggai Maron, and Yaron Lipman. 2017. DS++: A Flexible, Scalable and Provably Tight Relaxation for Matching Problems. ACM TOG 36, 6 (2017).Google Scholar
17. Davide Eynard, Emanuele Rodola, Klaus Glashoff, and Michael M Bronstein. 2016. Coupled functional maps. In 2016 Fourth 3DV. IEEE, 399–407.Google Scholar
18. Danielle Ezuz and Mirela Ben-Chen. 2017. Deblurring and denoising of maps between shapes. In CGF, Vol. 36. Wiley Online Library, 165–174.Google ScholarDigital Library
19. Danielle Ezuz, Behrend Heeren, Omri Azencot, Martin Rumpf, and Mirela Ben-Chen. 2019a. Elastic Correspondence between Triangle Meshes. In CGF, Vol. 38.Google ScholarCross Ref
20. Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen. 2019b. Reversible Harmonic Maps between Discrete Surfaces. ACM Transactions on Graphics (2019).Google Scholar
21. Danielle Ezuz, Justin Solomon, Vladimir G Kim, and Mirela Ben-Chen. 2017. Gwcnn: A metric alignment layer for deep shape analysis. In CGF, Vol. 36. 49–57.Google ScholarDigital Library
22. Anne Gehre, M Bronstein, Leif Kobbelt, and Justin Solomon. 2018. Interactive curve constrained functional maps. In CGF, Vol. 37. Wiley Online Library, 1–12.Google ScholarCross Ref
23. Daniela Giorgi, Silvia Biasotti, and Laura Paraboschi. 2007. SHREC: Shape Retrieval Contest: Watertight Models Track.Google Scholar
24. 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
25. Behrend Heeren, Martin Rumpf, Peter Schröder, Max Wardetzky, and Benedikt Wirth. 2014. Exploring the Geometry of the Space of Shells. CGF 33, 5 (2014), 247–256.Google ScholarDigital Library
26. Behrend Heeren, Martin Rumpf, Max Wardetzky, and Benedikt Wirth. 2012. Time-Discrete Geodesics in the Space of Shells. CGF 31, 5 (2012), 1755–1764.Google ScholarDigital Library
27. John H Holland. 1992. Genetic algorithms. Scientific american 267, 1 (1992), 66–73.Google Scholar
28. Haibin Huang, Evangelos Kalogerakis, Siddhartha Chaudhuri, Duygu Ceylan, Vladimir G Kim, and Ersin Yumer. 2017. Learning local shape descriptors from part correspondences with multiview convolutional networks. ACM TOG 37, 1 (2017), 1–14.Google Scholar
29. Ruqi Huang and Maks Ovsjanikov. 2017. Adjoint Map Representation for Shape Analysis and Matching. In Computer Graphics Forum, Vol. 36. 151–163.Google ScholarDigital Library
30. José A. Iglesias, Martin Rumpf, and Otmar Scherzer. 2018. Shape-Aware Matching of Implicit Surfaces Based on Thin Shell Energies. Found. Comput. Math. 18, 4 (2018), 891–927.Google ScholarDigital Library
31. Itay Kezurer, Shahar Z Kovalsky, Ronen Basri, and Yaron Lipman. 2015. Tight relaxation of quadratic matching. In Computer Graphics Forum, Vol. 34. 115–128.Google ScholarCross Ref
32. Vladimir G Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended Intrinsic Maps. ACM TOG 30 (2011).Google Scholar
33. Isaak Lim, Alexander Dielen, Marcel Campen, and Leif Kobbelt. 2018. A simple approach to intrinsic correspondence learning on unstructured 3d meshes. In Proceedings of the European Conference on Computer Vision (ECCV). 0–0.Google Scholar
34. Or Litany, Tal Remez, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein. 2017. Deep functional maps: Structured prediction for dense shape correspondence. In Proceedings of the IEEE International Conference on Computer Vision. 5659–5667.Google ScholarCross Ref
35. Nathan Litke, Mark Droske, Martin Rumpf, and Peter Schröder. 2005. An Image Processing Approach to Surface Matching. In Proc. Eurographics SGP. 207–216.Google Scholar
36. Roee Litman and Alexander Bronstein. 2014. Learning spectral descriptors for deformable shape correspondence. Pattern Analysis and Machine Intelligence, IEEE Transactions on 36, 1 (2014), 171–180.Google ScholarDigital Library
37. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-Minimizing Transport Plans for Inter-surface Mapping. ACM TOG 36 (2017), 14.Google ScholarDigital Library
38. Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman. 2016. Point Registration via Efficient Convex Relaxation. ACM TOG 35, 4 (2016).Google Scholar
39. Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. 2015. Geodesic convolutional neural networks on riemannian manifolds. In The IEEE International Conference on Computer Vision (ICCV). 37–45.Google ScholarDigital Library
40. Ujjwal Maulik and Sanghamitra Bandyopadhyay. 2000. Genetic algorithm-based clustering technique. Pattern recognition 33, 9 (2000), 1455–1465.Google Scholar
41. Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. 2017. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5115–5124.Google ScholarCross Ref
42. Brent C Munsell, Pahal Dalal, and Song Wang. 2008. Evaluating shape correspondence for statistical shape analysis: A benchmark study. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 11 (2008), 2023–2039.Google ScholarDigital Library
43. Dorian Nogneng and Maks Ovsjanikov. 2017. Informative descriptor preservation via commutativity for shape matching. In Computer Graphics Forum, Vol. 36. 259–267.Google ScholarDigital Library
44. IM Oliver, DJd Smith, and John RC Holland. 1987. Study of permutation crossover operators on the traveling salesman problem. In Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.Google Scholar
45. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: a flexible representation of maps between shapes. ACM TOG 31, 4 (2012).Google ScholarDigital Library
46. Maks Ovsjanikov, Etienne Corman, Michael Bronstein, Emanuele Rodolà, Mirela Ben-Chen, Leonidas Guibas, Frederic Chazal, and Alex Bronstein. 2016. Computing and processing correspondences with functional maps. In SIGGRAPH ASIA 2016 Courses. ACM, 9.Google ScholarDigital Library
47. Ender Ozcan and Chilukuri K Mohan. 1997. Partial shape matching using genetic algorithms. Pattern Recognition Letters 18, 10 (1997), 987–992.Google ScholarDigital Library
48. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted averages on surfaces. ACM TOG 32, 4 (2013), 60.Google ScholarDigital Library
49. P Victer Paul, A Ramalingam, R Baskaran, P Dhavachelvan, K Vivekanandan, R Subramanian, and VSK Venkatachalapathy. 2013. Performance analyses on population seeding techniques for genetic algorithms. International Journal of Engineering and Technology (IJET) 5, 3 (2013), 2993–3000.Google Scholar
50. Adrien Poulenard and Maks Ovsjanikov. 2018. Multi-directional geodesic neural networks via equivariant convolution. ACM TOG 37, 6 (2018), 1–14.Google ScholarDigital Library
51. Jing Ren, Adrien Poulenard, Peter Wonka, and Maks Ovsjanikov. 2018. Continuous and Orientation-preserving Correspondences via Functional Maps. ACM TOG 37, 6 (2018).Google Scholar
52. 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
53. STANLEY GOTSHALL BART Rylander and S Gotshall. 2002. Optimal population size and the genetic algorithm. Population 100, 400 (2002), 900.Google Scholar
54. Yusuf Sahillioğlu. 2018. A Genetic Isometric Shape Correspondence Algorithm with Adaptive Sampling. ACM Trans. Graph. 37, 5 (Oct. 2018).Google ScholarDigital Library
55. Luciano Silva, Olga Regina Pereira Bellon, and Kim L Boyer. 2005. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms. IEEE transactions on pattern analysis and machine intelligence 27, 5 (2005), 762–776.Google Scholar
56. Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. 2016. Entropic metric alignment for correspondence problems. ACM TOG 35, 4 (2016), 72.Google ScholarDigital Library
57. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proc. Eurographics Symposium on Geometry Processing. 109–116.Google Scholar
58. Robert W Sumner and Jovan Popović. 2004. Deformation Transfer for Triangle Meshes. ACM TOG 23 (2004).Google Scholar
59. 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 Transactions on Visualization and Computer Graphics 19, 7 (2013), 1199–1217.Google ScholarDigital Library
60. Ron Unger and John Moult. 1993. Genetic algorithms for protein folding simulations. Journal of molecular biology 231, 1 (1993), 75–81.Google ScholarCross Ref
61. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A survey on shape correspondence. In Computer Graphics Forum, Vol. 30. 1681–1707.Google ScholarCross Ref
62. Matthias Vestner, Roee Litman, Emanuele Rodola, Alex Bronstein, and Daniel Cremers. 2017. Product Manifold Filter: Non-rigid Shape Correspondence via Kernel Density Estimation in the Product Space. In 2017 IEEE CVPR. IEEE, 6681–6690.Google Scholar
63. Lingyu Wei, Qixing Huang, Duygu Ceylan, Etienne Vouga, and Hao Li. 2016. Dense human body correspondences using convolutional networks. In Proceedings of the IEEE CVPR. 1544–1553.Google ScholarCross Ref
64. Yingzi Wei, Yulan Hu, and Kanfeng Gu. 2007. Parallel search strategies for TSPs using a greedy genetic algorithm. In Third International Conference on Natural Computation (ICNC 2007), Vol. 3. IEEE, 786–790.Google ScholarDigital Library
65. Thomas Windheuser, Ulrich Schlickewei, Frank R Schmidt, and Daniel Cremers. 2011. Geometrically consistent elastic matching of 3d shapes: A linear programming solution. In Proc. IEEE International Conference on Computer Vision. 2134–2141.Google ScholarDigital Library
66. Sameh M Yamany, Mohamed N Ahmed, and Aly A Farag. 1999. A new genetic-based technique for matching 3-D curves and surfaces. Pattern Recognition 32, 10 (1999), 1817–1820.Google ScholarCross Ref
67. Hao Zhang, Alla Sheffer, Daniel Cohen-Or, Quan Zhou, Oliver Van Kaick, and Andrea Tagliasacchi. 2008. Deformation-driven shape correspondence. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1431–1439.Google Scholar
