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.
翻译:我们提出非硬化 2D 到 3D 形状匹配的第一个算法, 输入为 2D 形状, 以平面曲线表示, 3D 形状以表面表示; 输出为表面的连续曲线 。 我们将问题表现为在产品表面和曲线的三维圆形上找到最短的圆形路径 。 我们证明, 最佳匹配可以在多元时间计算, 其复杂度为$O( mn ⁇ 2\log(n)) 美元( worst- case) $( morst- case) ), 其中输入值为 $( mn ⁇ 2\\ log (n) ) 美元和 $n 美元, 表示模板曲线和 3D 形状的顶点数 。 我们还表明, 在实际操作中, 运行时间基本上为线性, $m\!\\\\\\\\\\\\\\\\\ n$! 。 使它成为形状分析和形状检索的有效方法 。 。 Q评估证实, 该方法为基于草图解的 3D 形状检索提供了极好的结果。 3D 。