SpiderMatch: 3D Shape Matching with Global Optimality and Geometric Consistency
Finding shortest paths on product spaces is a popular approach to tackle numerous variants of matching problems including the dynamic time warping method for matching signals the matching of curves or the matching of a curve to a 3D shape. While these approaches admit the computation of globally optimal solutions in polynomial time their natural generalisation to 3D shape matching is widely known to be intractable. In this work we address this issue by proposing a novel path-based formalism for 3D shape matching. More specifically we consider an alternative shape discretisation in which one of the 3D shapes (the source shape) is represented as a SpiderCurve i.e. a long self-intersecting curve that traces the 3D shape surface. We then tackle the 3D shape matching problem as finding a shortest path in the product graph of the SpiderCurve and the target 3D shape. Our approach introduces a set of novel constraints that ensure a globally geometrically consistent matching. Overall our formalism leads to an integer linear programming problem for which we experimentally show that it can efficiently be solved to global optimality. We demonstrate that our approach is competitive with recent state-of-the-art shape matching methods while in addition guaranteeing geometric consistency.
Code (1)
Tasks
Dynamic Time WarpingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
SIGMA: Scale-Invariant Global Sparse Shape Matching
We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for highly non-rigid shapes. To this end, we introduce a projected Laplace-Beltrami operator (PLBO) which combi…
DiscoMatch: Fast Discrete Optimisation for Geometrically Consistent 3D Shape Matching
In this work we propose to combine the advantages of learningbased and combinatorial formalisms for 3D shape matching. While learningbased methods lead to state-of-the-art matching performance, they do not ensure geometr…
validFast Globally Optimal and Geometrically Consistent 3D Shape Matching
Geometric consistency, i.e. the preservation of neighbourhoods, is a natural and strong prior in 3D shape matching. Geometrically consistent matchings are crucial for many downstream applications, such as texture transfe…
MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment
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 glob…
Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching
We consider the problem of finding a continuous and non-rigid matching between a 2D contour and a 3D mesh. While such problems can be solved to global optimality by finding a shortest path in the product graph between bo…