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 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.
@article{ACIRM_2013__3_1_107_0,
author = {Daniel Cremers and Emanuele Rodol\`a and Thomas Windheuser},
title = {Relaxations for {Minimizing} {Metric} {Distortion} and {Elastic} {Energies} for {3D} {Shape} {Matching}},
journal = {Actes des rencontres du CIRM},
pages = {107--117},
publisher = {CIRM},
volume = {3},
number = {1},
year = {2013},
doi = {10.5802/acirm.60},
zbl = {06938608},
language = {en},
url = {https://acirm.centre-mersenne.org/articles/10.5802/acirm.60/}
}
TY - JOUR AU - Daniel Cremers AU - Emanuele Rodolà AU - Thomas Windheuser TI - Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching JO - Actes des rencontres du CIRM PY - 2013 SP - 107 EP - 117 VL - 3 IS - 1 PB - CIRM UR - https://acirm.centre-mersenne.org/articles/10.5802/acirm.60/ DO - 10.5802/acirm.60 LA - en ID - ACIRM_2013__3_1_107_0 ER -
%0 Journal Article %A Daniel Cremers %A Emanuele Rodolà %A Thomas Windheuser %T Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching %J Actes des rencontres du CIRM %D 2013 %P 107-117 %V 3 %N 1 %I CIRM %U https://acirm.centre-mersenne.org/articles/10.5802/acirm.60/ %R 10.5802/acirm.60 %G en %F ACIRM_2013__3_1_107_0
Daniel Cremers; Emanuele Rodolà; Thomas Windheuser. Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching. Actes des rencontres du CIRM, Volume 3 (2013) no. 1, pp. 107-117. doi : 10.5802/acirm.60. https://acirm.centre-mersenne.org/articles/10.5802/acirm.60/
[1] Convex Optimization, Cambridge Univ. Press, New York, USA, 2004 | Zbl
[2] SHREC 2011: robust feature detection and description benchmark, ArXiv e-prints (2011)
[3] SHREC 2010: Robust Correspondence Benchmark, Eurographics Workshop on 3D Object Retrieval (2010) http://perception.inrialpes.fr/Publications/2010/BBCDGHKKVMOS10
[4] 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] 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] 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] Discrete Exterior Calculus, 2005
[8] Riemannian geometry, Birkhauser, 1992
[9] 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] 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] 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] A spectral technique for correspondence problems using pairwise constraints, Proc. CVPR, Volume 2 (2005), pp. 1482-1489 | DOI
[13] Surface Comparison with Mass Transportation, 2009
[14] Mobius Voting for Surface Correspondence, ACM Trans. on Graphics, Volume 28 (2009) no. 3
[15] An Image Processing Approach to Surface Matching, Symposium on Geometry Processing (2005), pp. 207-216
[16] A survey for the quadratic assignment problem, European Journal of Operational Research, Volume 176 (2007) no. 2, pp. 657-690 | DOI | MR | Zbl
[17] 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] Gromov-Wasserstein Distances and the Metric Approach to Object Matching, Found. Comput. Math., Volume 11 (2011), pp. 417-487 | DOI | MR | Zbl
[19] Discrete Differential-Geometry Operators for Triangulated 2-Manifolds, 2002
[20] A Condition Number for Non-Rigid Shape Matching, Comput. Graph. Forum (2011), pp. 1503-1512 | DOI
[21] A game-theoretic approach to deformable shape matching, Proc. CVPR (2012)
[22] Efficient Shape Matching using Vector Extrapolation, Proc. BMVC (2013)
[23] Elastic Net Constraints for Shape Matching, Proc. ICCV (2013)
[24] Fast Matching of Planar Shapes in Sub-cubic Runtime, IEEE Int. Conf. on Computer Vision (2007)
[25] Curvature Regularity for Region-based Image Segmentation and Inpainting: A Linear Programming Relaxation, IEEE Int. Conf. on Computer Vision (2009)
[26] 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] A Crystalline Approximation Theorem for Hypersurfaces, Princeton University, October (1990) (Ph. D. Thesis)
[28] Shape-based nonrigid correspondence with application to heart motion analysis, IEEE Trans Med Imaging, Volume 18 (1999) no. 7, pp. 570-579 | DOI
[29] Articulated mesh animation from multi-view silhouettes, ACM SIGGRAPH 2008 papers (SIGGRAPH ’08) (2008), p. 97:1-97:9 http://doi.acm.org/10.1145/1399504.1360696 | DOI
[30] Geometrically consistent elastic matching of 3d shapes: A linear programming solution, Computer Vision (ICCV), 2011 IEEE International Conference on (2011), pp. 2134-2141 | DOI
[31] Geodesics in Shape Space via Variational Time Discretization, EMMCVPR’09 (LNCS), Volume 5681 (2009), pp. 288-302
[32] Dense non-rigid surface registration using high-order graph matching, Proc. CVPR (2010), pp. 382-389
[33] 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
Cited by Sources: