Efficient Globally Optimal 2D-to-3D Deformable Shape Matching
This solves the problem of efficiently matching 2D sketches to 3D shapes for applications like shape analysis and retrieval, representing a foundational advancement.
The paper tackles the problem of non-rigid 2D-to-3D shape matching by proposing the first algorithm that computes the optimal matching in polynomial time with a worst-case complexity of O(mn^2 log(n)), and demonstrates practical efficiency with essentially linear runtime in m·n, providing excellent results for sketch-based deformable 3D shape retrieval.
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.