CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes

• URL: http://arxiv.org/abs/2303.16202v1
• Date: Tue, 28 Mar 2023 17:59:55 GMT
• Title: CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes
• Authors: Harshil Bhatia and Edith Tretschk and Zorah L\"ahner and Marcel Seelbach Benkner and Michael Moeller and Christian Theobalt and Vladislav Golyanik
• Abstract summary: 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.
• Score: 62.45415756883437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, $\mathcal{NP}$-hard problem. A perfect matching is necessarily cycle-consistent: Following the pairwise point correspondences along several shapes must end up at the starting vertex of the original shape. Unfortunately, existing quantum shape-matching methods do not support multiple shapes and even less cycle consistency. This paper addresses the open challenges and introduces the first quantum-hybrid approach for 3D shape multi-matching; in addition, it is also cycle-consistent. Its iterative formulation is admissible to modern adiabatic quantum hardware and scales linearly with the total number of input shapes. Both these characteristics are achieved by reducing the $N$-shape case to a sequence of three-shape matchings, the derivation of which is our main technical contribution. Thanks to quantum annealing, high-quality solutions with low energy are retrieved for the intermediate $\mathcal{NP}$-hard objectives. On benchmark datasets, the proposed approach significantly outperforms extensions to multi-shape matching of a previous quantum-hybrid two-shape matching method and is on-par with classical multi-matching methods.

Related papers

• 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)
• Unsupervised Deep Multi-Shape Matching [15.050801537501462]
  3D shape matching is a long-standing problem in computer vision and computer graphics. We present a novel approach for deep multi-shape matching that ensures cycle-consistent multi-matchings. Our method achieves state-of-the-art results on several challenging benchmark datasets.
  arXiv  Detail & Related papers  (2022-07-20T01:22:08Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  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.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  Finding correspondences between shapes is a fundamental problem in computer vision and graphics. While isometries are often studied in shape correspondence problems, they have not been considered explicitly in the multi-matching setting. We present a suitable optimisation algorithm for solving our formulation and provide a convergence and complexity analysis.
  arXiv  Detail & Related papers  (2020-12-04T15:58:34Z)

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.