MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment

• URL: http://arxiv.org/abs/2002.12623v1
• Date: Fri, 28 Feb 2020 09:54:06 GMT
• Title: MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment
• Authors: Florian Bernard, Zeeshan Khan Suri, Christian Theobalt
• Abstract summary: 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.
• Score: 77.38594866794429
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a convex mixed-integer programming formulation for non-rigid shape matching. To this end, we propose a novel shape deformation model based on an efficient low-dimensional discrete model, so that finding a globally optimal solution is tractable in (most) practical cases. Our approach combines several favourable properties: it is independent of the initialisation, it is much more efficient to solve to global optimality compared to analogous quadratic assignment problem formulations, and it is highly flexible in terms of the variants of matching problems it can handle. Experimentally we demonstrate that our approach outperforms existing methods for sparse shape matching, that it can be used for initialising dense shape matching methods, and we showcase its flexibility on several examples.

Related papers

• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
  We study the assortment optimization problem under the mixed-logit customer choice model. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex.
  arXiv  Detail & Related papers  (2024-07-26T06:27:11Z)
• Lp-Norm Constrained One-Class Classifier Combination [18.27510863075184]
  We consider the one-class classification problem by modelling the sparsity/uniformity of the ensemble. We present an effective approach to solve formulated convex constrained problem efficiently.
  arXiv  Detail & Related papers  (2023-12-25T16:32:34Z)
• 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)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• 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)
• 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.