A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching

• URL: http://arxiv.org/abs/2204.12805v1
• Date: Wed, 27 Apr 2022 09:47:47 GMT
• Title: A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching
• Authors: Paul Roetzer and Paul Swoboda and Daniel Cremers and Florian Bernard
• Abstract summary: We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
• Score: 69.14632473279651
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a scalable combinatorial algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We use the mathematically elegant formalism proposed by Windheuser et al. (ICCV 2011) where 3D shape matching was formulated as an integer linear program over the space of orientation-preserving diffeomorphisms. Until now, the resulting formulation had limited practical applicability due to its complicated constraint structure and its large size. We propose a novel primal heuristic coupled with a Lagrange dual problem that is several orders of magnitudes faster compared to previous solvers. This allows us to handle shapes with substantially more triangles than previously solvable. We demonstrate compelling results on diverse datasets, and, even showcase that we can address the challenging setting of matching two partial shapes without availability of complete shapes. Our code is publicly available at http://github.com/paul0noah/sm-comb .

Related papers

• Partial-to-Partial Shape Matching with Geometric Consistency [47.46502145377953]
  Finding correspondences between 3D shapes is an important and long-standing problem in computer vision, graphics and beyond. We bridge the gap between existing (rather artificial) 3D full shape matching and partial-to-partial real-world settings by exploiting geometric consistency as a strong constraint. For the first time, we achieve geometric consistency for partial-to-partial matching, which is realized by a novel integer non-linear program formalism building on triangle product spaces.
  arXiv  Detail & Related papers  (2024-04-18T14:14:07Z)
• Fast Discrete Optimisation for Geometrically Consistent 3D Shape Matching [35.292601017922905]
  We propose to combine the advantages of learning-based and formalisms for 3D shape matching. Our approach is (i) initialisation free powered by quasi-Newton, (ii) massively parallelisable and (iii) provides optimality gaps.
  arXiv  Detail & Related papers  (2023-10-12T11:23:07Z)
• Geometrically Consistent Partial Shape Matching [50.29468769172704]
  Finding correspondences between 3D shapes is a crucial problem in computer vision and graphics. An often neglected but essential property of matching geometrics is consistency. We propose a novel integer linear programming partial shape matching formulation.
  arXiv  Detail & Related papers  (2023-09-10T12:21:42Z)
• CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes [62.45415756883437]
  Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, $mathcalNP$-hard problem. Existing quantum shape-matching methods do not support multiple shapes and even less cycle consistency. This paper introduces the first quantum-hybrid approach for 3D shape multi-matching.
  arXiv  Detail & Related papers  (2023-03-28T17:59:55Z)
• Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching [12.740151710302397]
  We consider the problem of finding a continuous and non-rigid matching between a 2D contour and a 3D mesh. Existing solutions heavily rely on unrealistic prior assumptions to avoid degenerate solutions. We propose a novel 2D-3D shape matching formalism based on the conjugate product graph between the 2D contour and the 3D shape.
  arXiv  Detail & Related papers  (2022-11-21T15:41:28Z)
• Dense Non-Rigid Structure from Motion: A Manifold Viewpoint [162.88686222340962]
  Non-Rigid Structure-from-Motion (NRSfM) problem aims to recover 3D geometry of a deforming object from its 2D feature correspondences across multiple frames. We show that our approach significantly improves accuracy, scalability, and robustness against noise.
  arXiv  Detail & Related papers  (2020-06-15T09:15:54Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.