# Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching

Daniel Cremers^{[1]}; Emanuele Rodolà^{[1]}; Thomas Windheuser^{[1]}

- [1] Technische Universität München

Actes des rencontres du CIRM (2013)

- Volume: 3, Issue: 1, page 107-117
- ISSN: 2105-0597

## Access Full Article

top## Abstract

top## How to cite

topCremers, Daniel, Rodolà, Emanuele, and Windheuser, Thomas. "Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching." Actes des rencontres du CIRM 3.1 (2013): 107-117. <http://eudml.org/doc/275345>.

@article{Cremers2013,

abstract = {We present two methods for non-rigid shape matching. Both methods formulate shape matching as an energy minimization problem, where the energy measures distortion of the metric defined on the shapes in one case, or directly describes the physical deformation relating the two shapes in the other case. The first method considers a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off a weighting parameter is introduced to combine two existing relaxations, namely spectral and game-theoretic. This leads to an approach for deformable shape matching with controllable sparsity. The second method focuses on computing a geometrically consistent and spatially dense matching between two $3D$ shapes. Rather than mapping points to points it matches infinitesimal surface patches while preserving the geometric structures. In this spirit, matchings are considered as diffeomorphisms between the objects’ surfaces which are by definition geometrically consistent. Based on the observation that such diffeomorphisms can be represented as closed and continuous surfaces in the product space of the two shapes, this leads to a minimal surface problem in this product space. The proposed discrete formulation describes the search space with linear constraints. Computationally, the approach results in a binary linear program whose relaxed version can be solved efficiently in a globally optimal manner.},

affiliation = {Technische Universität München; Technische Universität München; Technische Universität München},

author = {Cremers, Daniel, Rodolà, Emanuele, Windheuser, Thomas},

journal = {Actes des rencontres du CIRM},

keywords = {shape matching; metric spaces; elastic deformation},

language = {eng},

month = {11},

number = {1},

pages = {107-117},

publisher = {CIRM},

title = {Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching},

url = {http://eudml.org/doc/275345},

volume = {3},

year = {2013},

}

TY - JOUR

AU - Cremers, Daniel

AU - Rodolà, Emanuele

AU - Windheuser, Thomas

TI - Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching

JO - Actes des rencontres du CIRM

DA - 2013/11//

PB - CIRM

VL - 3

IS - 1

SP - 107

EP - 117

AB - We present two methods for non-rigid shape matching. Both methods formulate shape matching as an energy minimization problem, where the energy measures distortion of the metric defined on the shapes in one case, or directly describes the physical deformation relating the two shapes in the other case. The first method considers a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off a weighting parameter is introduced to combine two existing relaxations, namely spectral and game-theoretic. This leads to an approach for deformable shape matching with controllable sparsity. The second method focuses on computing a geometrically consistent and spatially dense matching between two $3D$ shapes. Rather than mapping points to points it matches infinitesimal surface patches while preserving the geometric structures. In this spirit, matchings are considered as diffeomorphisms between the objects’ surfaces which are by definition geometrically consistent. Based on the observation that such diffeomorphisms can be represented as closed and continuous surfaces in the product space of the two shapes, this leads to a minimal surface problem in this product space. The proposed discrete formulation describes the search space with linear constraints. Computationally, the approach results in a binary linear program whose relaxed version can be solved efficiently in a globally optimal manner.

LA - eng

KW - shape matching; metric spaces; elastic deformation

UR - http://eudml.org/doc/275345

ER -

## References

top- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, (2004), Cambridge Univ. Press, New York, USA Zbl1058.90049MR2061575
- E. Boyer, A. M. Bronstein, M. M. Bronstein, B. Bustos, T. Darom, R. Horaud, I. Hotz, Y. Keller, J. Keustermans, A. Kovnatsky, R. Litman, J. Reininghaus, I. Sipiran, D. Smeets, P. Suetens, D. Vandermeulen, A. Zaharescu, V. Zobel, SHREC 2011: robust feature detection and description benchmark, ArXiv e-prints (2011)
- Alex Bronstein, Michael Bronstein, Umberto Castellani, SHREC 2010: Robust Correspondence Benchmark, Eurographics Workshop on 3D Object Retrieval (2010)
- Alex Bronstein, Michael Bronstein, Ron Kimmel, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. National Academy of Science (PNAS) 103 (2006), 1168-1172 Zbl1160.65306MR2204074
- P. Ciarlet, An introduction to differential geometry with applications to elasticity, (2005), Springer, Dordrecht Zbl1100.53004MR2312300
- H. Delingette, Triangular Springs for Modeling Nonlinear Membranes, IEEE Transactions on Visualisation and Computer Graphics 14 (2008)
- M. Desbrun, A. N. Hirani, M. Leok, J. E. Marsden, Discrete Exterior Calculus, (2005) Zbl1080.39021
- M.P. Do Carmo, Riemannian geometry, (1992), Birkhauser Zbl0752.53001MR1138207
- M. Giaquinta, G. Modica, J. Souček, Cartesian currents in the calculus of variations. II, 38 (1998), Springer-Verlag, Berlin Zbl0914.49002MR1645082
- Leo Grady, Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D, IEEE Trans. Pattern Anal. Mach. Intell. 32 (2010), 321-334
- W. Koiter, On the nonlinear theory of thin elastic shells. I, II, III, Nederl. Akad. Wetensch. Proc. Ser. B 69 (1966), 1-17, 18–32, 33–54 MR192706
- Marius Leordeanu, Martial Hebert, A spectral technique for correspondence problems using pairwise constraints, Proc. CVPR 2 (2005), 1482-1489
- Y. Lipman, I. Daubechies, Surface Comparison with Mass Transportation, (2009)
- Yaron Lipman, Thomas Funkhouser, Mobius Voting for Surface Correspondence, ACM Trans. on Graphics 28 (2009)
- N. Litke, M. Droske, M. Rumpf, P. Schröder, An Image Processing Approach to Surface Matching, Symposium on Geometry Processing (2005), 207-216
- Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, Tania Querido, A survey for the quadratic assignment problem, European Journal of Operational Research 176 (2007), 657-690 Zbl1103.90058MR2267435
- F. Mémoli, G. Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math. 5 (2005), 313-346 Zbl1101.53022MR2168679
- Facundo Mémoli, Gromov-Wasserstein Distances and the Metric Approach to Object Matching, Found. Comput. Math. 11 (2011), 417-487 Zbl1244.68078MR2811584
- M. Meyer, M. Desbrun, P Schröder, A. Barr, Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, (2002) Zbl1069.53004
- Maks Ovsjanikov, Qi-Xing Huang, Leonidas J. Guibas, A Condition Number for Non-Rigid Shape Matching, Comput. Graph. Forum (2011), 1503-1512
- Emanuele Rodolà, Alex Bronstein, Andrea Albarelli, Filippo Bergamasco, Andrea Torsello, A game-theoretic approach to deformable shape matching, Proc. CVPR (2012)
- Emanuele Rodolà, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers, Efficient Shape Matching using Vector Extrapolation, Proc. BMVC (2013)
- Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers, Elastic Net Constraints for Shape Matching, Proc. ICCV (2013), Sydney, Australia
- F. R. Schmidt, Dirk Farin, D. Cremers, Fast Matching of Planar Shapes in Sub-cubic Runtime, IEEE Int. Conf. on Computer Vision (2007), Rio de Janeiro
- T. Schoenemann, F. Kahl, D. Cremers, Curvature Regularity for Region-based Image Segmentation and Inpainting: A Linear Programming Relaxation, IEEE Int. Conf. on Computer Vision (2009), Kyoto Zbl1254.68282
- Shai Shalev-Shwartz, Yoram Singer, Efficient Learning of Label Ranking by Soft Projections onto Polyhedra, J. Mach. Learn. Res. 7 (2006), 1567-1599 Zbl1222.68302MR2274417
- John M. Sullivan, A Crystalline Approximation Theorem for Hypersurfaces, (1990) MR2685608
- Hermant Tagare, Shape-based nonrigid correspondence with application to heart motion analysis, IEEE Trans Med Imaging 18 (1999), 570-579
- Daniel Vlasic, Ilya Baran, Wojciech Matusik, Jovan Popović, Articulated mesh animation from multi-view silhouettes, ACM SIGGRAPH 2008 papers (2008), 97:1-97:9, ACM, New York, NY, USA
- Thomas Windheuser, Ulrich Schlickewei, Frank R Schmidt, Daniel Cremers, Geometrically consistent elastic matching of 3d shapes: A linear programming solution, Computer Vision (ICCV), 2011 IEEE International Conference on (2011), 2134-2141
- B. Wirth, L. Bar, M. Rumpf, G. Sapiro, Geodesics in Shape Space via Variational Time Discretization, EMMCVPR’09 5681 (2009), 288-302
- Yun Zeng, Chaohui Wang, Yang Wang, Xianfeng Gu, Dimitris Samaras, Nikos Paragios, Dense non-rigid surface registration using high-order graph matching, Proc. CVPR (2010), 382-389
- Hui Zou, Trevor Hastie, Regularization and variable selection via the Elastic Net, Journal of the Royal Statistical Society, Series B 67 (2005), 301-320 Zbl1069.62054MR2137327

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.