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

Abstract

top
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 3 D 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.

How to cite

top

Cremers, 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
  1. Stephen Boyd, Lieven Vandenberghe, Convex Optimization, (2004), Cambridge Univ. Press, New York, USA Zbl1058.90049MR2061575
  2. 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) 
  3. Alex Bronstein, Michael Bronstein, Umberto Castellani, SHREC 2010: Robust Correspondence Benchmark, Eurographics Workshop on 3D Object Retrieval (2010) 
  4. 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
  5. P. Ciarlet, An introduction to differential geometry with applications to elasticity, (2005), Springer, Dordrecht Zbl1100.53004MR2312300
  6. H. Delingette, Triangular Springs for Modeling Nonlinear Membranes, IEEE Transactions on Visualisation and Computer Graphics 14 (2008) 
  7. M. Desbrun, A. N. Hirani, M. Leok, J. E. Marsden, Discrete Exterior Calculus, (2005) Zbl1080.39021
  8. M.P. Do Carmo, Riemannian geometry, (1992), Birkhauser Zbl0752.53001MR1138207
  9. M. Giaquinta, G. Modica, J. Souček, Cartesian currents in the calculus of variations. II, 38 (1998), Springer-Verlag, Berlin Zbl0914.49002MR1645082
  10. Leo Grady, Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D, IEEE Trans. Pattern Anal. Mach. Intell. 32 (2010), 321-334 
  11. 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
  12. Marius Leordeanu, Martial Hebert, A spectral technique for correspondence problems using pairwise constraints, Proc. CVPR 2 (2005), 1482-1489 
  13. Y. Lipman, I. Daubechies, Surface Comparison with Mass Transportation, (2009) 
  14. Yaron Lipman, Thomas Funkhouser, Mobius Voting for Surface Correspondence, ACM Trans. on Graphics 28 (2009) 
  15. N. Litke, M. Droske, M. Rumpf, P. Schröder, An Image Processing Approach to Surface Matching, Symposium on Geometry Processing (2005), 207-216 
  16. 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
  17. 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
  18. Facundo Mémoli, Gromov-Wasserstein Distances and the Metric Approach to Object Matching, Found. Comput. Math. 11 (2011), 417-487 Zbl1244.68078MR2811584
  19. M. Meyer, M. Desbrun, P Schröder, A. Barr, Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, (2002) Zbl1069.53004
  20. Maks Ovsjanikov, Qi-Xing Huang, Leonidas J. Guibas, A Condition Number for Non-Rigid Shape Matching, Comput. Graph. Forum (2011), 1503-1512 
  21. Emanuele Rodolà, Alex Bronstein, Andrea Albarelli, Filippo Bergamasco, Andrea Torsello, A game-theoretic approach to deformable shape matching, Proc. CVPR (2012) 
  22. Emanuele Rodolà, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers, Efficient Shape Matching using Vector Extrapolation, Proc. BMVC (2013) 
  23. Emanuele Rodolà, Andrea Torsello, Tatsuya Harada, Yasuo Kuniyoshi, Daniel Cremers, Elastic Net Constraints for Shape Matching, Proc. ICCV (2013), Sydney, Australia 
  24. 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 
  25. 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
  26. 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
  27. John M. Sullivan, A Crystalline Approximation Theorem for Hypersurfaces, (1990) MR2685608
  28. Hermant Tagare, Shape-based nonrigid correspondence with application to heart motion analysis, IEEE Trans Med Imaging 18 (1999), 570-579 
  29. 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 
  30. 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 
  31. B. Wirth, L. Bar, M. Rumpf, G. Sapiro, Geodesics in Shape Space via Variational Time Discretization, EMMCVPR’09 5681 (2009), 288-302 
  32. 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 
  33. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.