MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment
This addresses shape matching problems in computer vision and graphics, offering a flexible and efficient solution with global optimality guarantees.
The paper tackles non-rigid shape alignment by proposing a convex mixed-integer programming formulation that finds globally optimal solutions efficiently, outperforming existing methods for sparse shape matching and enabling initialization for dense matching.
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.