Elastic Geometric Shape Matching for Point Sets under Translations
Elastic Geometric Shape Matching for Point Sets under Translations
复制标题
DOI：
10.1007/978-3-319-21840-3_48
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
Christian Knauer;Fabian Stehn
中科院分区：
文献类型：
--
作者：
Christian Knauer;Fabian Stehn
非几何形状匹配问题给出了一个模式，一个模型Q，一个距离测度d（它形式化了这种形状的相似性的直观概念），以及一类适用于模式的几何变换。任务是在给定的类中找到一个转换，使转换后的模式（P）到模型Q的距离最小化在许多应用中，其中包括医学图像分析、工业设计、机器人或计算机视觉，在这些应用中，可能发生局部失真和复杂变形，这种设置过于限制，因为仅使用单个变换来将整个图案与模型对齐。几乎所有已知的处理非刚性变形的策略都应用了遗传算法（基于局部下降、松弛LP公式、模拟退火等）。这些算法得到的解的质量通常与全局最优解的质量无关，弹性几何形状匹配试图通过计算一整套变换T来弥补这种情况。每一个变换都应用于P的一个子模式。优化问题的目标变成了双重的：最小化转换子模式到模型的距离，同时最大化集合T中转换的相似性。这种建模的目的是策略，计算可证明的最佳解决方案，或替代近似结果的质量guaranteed.We认为一个简单的弹性几何形状匹配问题的变化在平面上，每个子形状只是一个单一的点。我们表明，这个问题已经是NP-困难的有向Hausdorff-或瓶颈距离下的任意翻译。我们补充我们的结果与有效的算法来计算变换系综下的两个距离的变体的问题，其中只有在规定的，固定的directionare允许。
Ingeometric shape matching problemsone is given a patternP, a modelQ, a distance measure d (which formalizes the intuitive notion of similarity of such shapes), and a class of geometric transformations applicable to the patternP. The task is to find a transformationtin the given class that minimizes the distance of the transformed patternt(P) to the modelQ(as measured by d) in order to compute the similarity of the given shapes.In many applications, among them medical-image analysis, industrial design, robotics or computer vision, where local distortions and complex deformations can occur, this setting is too restrictive, since only the single transformationtis used to align the entire pattern with the model. Almost all known strategies that deal with non-rigid deformations apply heuristics (based on local descent, relaxed LP formulations, simulated annealing, or alike). The quality of the solution found by these heuristics can usually not be related to the quality of a global optimum.Elastic geometric shape matchingtries to remedy this situation by computing a whole set of transformationsT. Each transformationis applied to a subpattern ofP. The objective of the optimization problem becomes twofold:Minimize the distanceof the (union of the) transformed subpatterns to the model while alsomaximizing the similarityof the transformations in the ensembleT. This modeling aims at strategies that compute provably optimal solutions, or alternatively approximative results of a guaranteed quality.We consider variations of a simple elastic geometric shape matching problem in the plane where each subshape is just a single point. We show that this problem already isNP-hard for the directed Hausdorff- or bottleneck distance under arbitrary translations. We complement our result with efficient algorithms to compute transformation ensembles under both distances for variants of the problem where only translationsin a prescribed, fixed directionare allowed.