Efficient Globally Optimal 2D-to-3D Deformable Shape Matching
We propose the first algorithm for non-rigid 2D-to-3D shape matching, where the input is a 2D shape represented as a planar curve and a 3D shape represented as a surface; the output is a continuous curve on the surface. We cast the problem as finding the shortest circular path on the product 3-manifold of the surface and the curve. We prove that the optimal matching can be computed in polynomial time with a (worst-case) complexity of $O(mn^2\log(n))$, where $m$ and $n$ denote the number of vertices on the template curve and the 3D shape respectively. We also demonstrate that in practice the runtime is essentially linear in $m\!\cdot\! n$ making it an efficient method for shape analysis and shape retrieval. Quantitative evaluation confirms that the method provides excellent results for sketch-based deformable 3D shape retrieval.
Code (0)
등록된 구현이 없습니다.
Tasks
3D Shape RetrievalRetrievalSimilar Papers 제목 키워드 기반
Superadditivity and Convex Optimization for Globally Optimal Cell Segmentation using Deformable Shape Models
Cell nuclei segmentation is challenging due to shape variation and closely clustered or partially overlapping objects. Most previous methods are not globally optimal, limited to elliptical models, or are computationally …
Cell SegmentationComputational EfficiencyImage SegmentationSegmentationSpiderMatch: 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…
Dynamic Time WarpingFast 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…
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…
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…