“ENIGMA: evolutionary non-isometric geometry Matching” by Edelstein, Ezuz and Ben-Chen

  • ©Michal Edelstein, Danielle Ezuz, and Mirela (Miri) Ben-Chen



Session Title:

    Motion and Matching


    ENIGMA: evolutionary non-isometric geometry Matching



    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.


    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

ACM Digital Library Publication: