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

Cremers, Daniel; Rodolà, Emanuele; Windheuser, Thomas

Actes des rencontres du CIRM, Tome 3 (2013) no. 1, pp. 107-117.

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.

Mots clés : shape matching, metric spaces, elastic deformation

[1] Boyd, Stephen; Vandenberghe, Lieven Convex Optimization, Cambridge Univ. Press, New York, USA, 2004 | Zbl

[2] Boyer, E.; Bronstein, A. M.; Bronstein, M. M.; Bustos, B.; Darom, T.; Horaud, R.; Hotz, I.; Keller, Y.; Keustermans, J.; Kovnatsky, A.; Litman, R.; Reininghaus, J.; Sipiran, I.; Smeets, D.; Suetens, P.; Vandermeulen, D.; Zaharescu, A.; Zobel, V. SHREC 2011: robust feature detection and description benchmark, ArXiv e-prints (2011)

[3] Bronstein, Alex; Bronstein, Michael; Castellani, Umberto SHREC 2010: Robust Correspondence Benchmark, Eurographics Workshop on 3D Object Retrieval (2010) http://perception.inrialpes.fr/Publications/2010/BBCDGHKKVMOS10

[4] Bronstein, Alex; Bronstein, Michael; Kimmel, Ron Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, Proc. National Academy of Science (PNAS), Volume 103 (2006) no. 5, pp. 1168-1172 | DOI | MR | Zbl

[5] Ciarlet, P. An introduction to differential geometry with applications to elasticity, Springer, Dordrecht, 2005, iv+209 pages Reprinted from J. Elasticity 78/79 (2005), no. 1-3 [MR2196098] | DOI | MR | Zbl

[6] Delingette, H. Triangular Springs for Modeling Nonlinear Membranes, IEEE Transactions on Visualisation and Computer Graphics, Volume 14 (2008) no. 2 http://doi.ieeecomputersociety.org/10.1109/TVCG.2007.70431

[7] Desbrun, M.; Hirani, A. N.; Leok, M.; Marsden, J. E. Discrete Exterior Calculus, 2005

[8] Do Carmo, M.P. Riemannian geometry, Birkhauser, 1992

[9] Giaquinta, M.; Modica, G.; Souček, J. Cartesian currents in the calculus of variations. II, Ergebnisse der Mathematik und ihrer Grenzgebiete., 38, Springer-Verlag, Berlin, 1998, xxiv+697 pages (Variational integrals) | MR | Zbl

[10] Grady, Leo Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D, IEEE Trans. Pattern Anal. Mach. Intell., Volume 32 (2010) no. 2, pp. 321-334 | DOI

[11] Koiter, W. On the nonlinear theory of thin elastic shells. I, II, III, Nederl. Akad. Wetensch. Proc. Ser. B, Volume 69 (1966), p. 1-17, 18–32, 33–54 | MR

[12] Leordeanu, Marius; Hebert, Martial A spectral technique for correspondence problems using pairwise constraints, Proc. CVPR, Volume 2 (2005), pp. 1482-1489 | DOI

[13] Lipman, Y.; Daubechies, I. Surface Comparison with Mass Transportation, 2009

[14] Lipman, Yaron; Funkhouser, Thomas Mobius Voting for Surface Correspondence, ACM Trans. on Graphics, Volume 28 (2009) no. 3

[15] Litke, N.; Droske, M.; Rumpf, M.; Schröder, P. An Image Processing Approach to Surface Matching, Symposium on Geometry Processing (2005), pp. 207-216

[16] Loiola, Eliane Maria; de Abreu, Nair Maria Maia; Boaventura-Netto, Paulo Oswaldo; Hahn, Peter; Querido, Tania A survey for the quadratic assignment problem, European Journal of Operational Research, Volume 176 (2007) no. 2, pp. 657-690 | DOI | MR | Zbl

[17] Mémoli, F.; Sapiro, G. A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math., Volume 5 (2005), pp. 313-346 | DOI | MR | Zbl

[18] Mémoli, Facundo Gromov-Wasserstein Distances and the Metric Approach to Object Matching, Found. Comput. Math., Volume 11 (2011), pp. 417-487 | DOI | MR | Zbl

[19] Meyer, M.; Desbrun, M.; Schröder, P; Barr, A. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, 2002

[20] Ovsjanikov, Maks; Huang, Qi-Xing; Guibas, Leonidas J. A Condition Number for Non-Rigid Shape Matching, Comput. Graph. Forum (2011), pp. 1503-1512 | DOI

[21] Rodolà, Emanuele; Bronstein, Alex; Albarelli, Andrea; Bergamasco, Filippo; Torsello, Andrea A game-theoretic approach to deformable shape matching, Proc. CVPR (2012)

[22] Rodolà, Emanuele; Harada, Tatsuya; Kuniyoshi, Yasuo; Cremers, Daniel Efficient Shape Matching using Vector Extrapolation, Proc. BMVC (2013)

[23] Rodolà, Emanuele; Torsello, Andrea; Harada, Tatsuya; Kuniyoshi, Yasuo; Cremers, Daniel Elastic Net Constraints for Shape Matching, Proc. ICCV, Sydney, Australia (2013)

[24] Schmidt, F. R.; Farin, Dirk; Cremers, D. Fast Matching of Planar Shapes in Sub-cubic Runtime, IEEE Int. Conf. on Computer Vision, Rio de Janeiro (2007)

[25] Schoenemann, T.; Kahl, F.; Cremers, D. Curvature Regularity for Region-based Image Segmentation and Inpainting: A Linear Programming Relaxation, IEEE Int. Conf. on Computer Vision, Kyoto (2009)

[26] Shalev-Shwartz, Shai; Singer, Yoram Efficient Learning of Label Ranking by Soft Projections onto Polyhedra, J. Mach. Learn. Res., Volume 7 (2006), pp. 1567-1599 http://dl.acm.org/citation.cfm?id=1248547.1248605 | MR | Zbl

[27] Sullivan, John M. A Crystalline Approximation Theorem for Hypersurfaces, Princeton University, October (1990) (Ph. D. Thesis)

[28] Tagare, Hermant Shape-based nonrigid correspondence with application to heart motion analysis, IEEE Trans Med Imaging, Volume 18 (1999) no. 7, pp. 570-579 | DOI

[29] Vlasic, Daniel; Baran, Ilya; Matusik, Wojciech; Popović, Jovan Articulated mesh animation from multi-view silhouettes, ACM SIGGRAPH 2008 papers (SIGGRAPH ’08), ACM, New York, NY, USA (2008), p. 97:1-97:9 http://doi.acm.org/10.1145/1399504.1360696 | DOI

[30] Windheuser, Thomas; Schlickewei, Ulrich; Schmidt, Frank R; Cremers, Daniel Geometrically consistent elastic matching of 3d shapes: A linear programming solution, Computer Vision (ICCV), 2011 IEEE International Conference on, IEEE (2011), pp. 2134-2141 | DOI

[31] Wirth, B.; Bar, L.; Rumpf, M.; Sapiro, G. Geodesics in Shape Space via Variational Time Discretization, EMMCVPR’09 (LNCS), Volume 5681 (2009), pp. 288-302

[32] Zeng, Yun; Wang, Chaohui; Wang, Yang; Gu, Xianfeng; Samaras, Dimitris; Paragios, Nikos Dense non-rigid surface registration using high-order graph matching, Proc. CVPR (2010), pp. 382-389

[33] Zou, Hui; Hastie, Trevor Regularization and variable selection via the Elastic Net, Journal of the Royal Statistical Society, Series B, Volume 67 (2005), pp. 301-320 | DOI | MR | Zbl