使用模糊输入来计算弗雷歇距离
摘要
我们考虑到了当计算两条顶点是模糊的多边形曲线的弗雷歇距离的困难所在。在一块区域中一个不精确的点是可以在这一区域的任何一处的。通过将这些不精确的点建模为尺寸为D的球后，我们介绍了一种针对于这个问题的算法，那就是可以分别返回时间复杂度为，两条具有n个和m个顶点的不精确多边形曲线的最小弗雷歇距离。我们还提出了一种针对于平面且时间复杂度为 改善后的算法。在D维正交情况中，点被建模为平行轴框，然后使用 距离，我们给一个时间复杂度为 的算法。
我们还给出了一种有效的时间复杂度为 的算法去大约估计最大的弗雷歇距离，同样的，在平移后的最大或者最小的弗雷歇距离同样适用。这些算法实现了“现实”设置中的常数系数近似比（例如当那些模仿不精确的点的球的半径大致相同时）。
关键词：形状匹配，弗雷歇距离，不精准输入。
1.介绍
形状匹配是一项在广泛的计算机应用中，例如计算机视觉，计算机辅助设计，机器人技术，医学成像和药物设计，中非常重要的构成成分。在形状匹配中，我们根据两个几何对象的某些几何相似点来计算他们之间的距离。弗雷歇距离是针对于连续的形状例如曲线和曲面的一种自然距离函数，是使用形状的重新参数化定义的。
离散型弗雷歇距离是弗雷歇距离的一种变形，在d维中，分别给两条有n和m个顶点的多边形曲线，有一个动态规划算法计算在时间复杂度为 时它们之间的离散弗雷歇距离。随后Aronov et al提出了有效的对于两条自然曲线弗雷歇距离的近似算法，K-有界曲线和主干曲线。他们还提出了对于计算精准的离散型弗雷歇距离的伪输出敏感算法。
在之前，大多数对于弗雷歇距离的研究工作会假设输入的曲线是精准的。然而，这些曲线可能仅仅是一个估计。在很多情况下，几何数据来自于现实世界情景下的测量值，而且测量仪器的精度也是有限的。这种几何数据的不精准性最近也是被研究过，有相当多的针对于基础几何问题的算法可以处理模糊的数据，例如计算豪斯多夫距离，沃罗诺伊图，平面凸壳，Delaunay三角剖分。
模糊的数据可以通过不同的方式建模，对于由点组成的数据，一种可能的模型是将每个点分配给一个区域，通常是像一个磁盘或一个正方形，在这种情况下，用于计算Frechet距离的现有算法可能对测量的精确度过于敏感，并且它们可能产生解决方案而没有对其正确性或准确性提供任何保证。对于这种问题的解决方案就是将输入的不精准性考虑进算法的设计中去，以便他们产生一个解决方案，并提供关于质量的其他信息。
我们的成果。在这篇文章中，我们研究了计算两条多边形曲线之间的离散Fr#39;Echet距离的问题，其中多边形曲线的顶点不精确。每个顶点属于一个区域，他是 中的欧几里得球或轴平行框。我们考虑两种方案：正交方案和欧几里德方案。 在正交方案下，区域是框，我们使用距离。 在欧几里德方案下，这些地区是球，我们使用欧几里德距离。
这个问题的典型应用包括计算两个时空数据集的相似度，例如通过某些定位服务（例如全球定位系统）获得其顶点位置的移动对象（例如汽车，人，动物）的多边形轨迹，因此 ，这种应用是不准确的。
我们给两个模糊的n个点和m个点序列，我们给出算法来计算这两个序列之间的最小Frechet距离。在d维正交方案下，我们的算法在时间复杂度为。在欧几里得方案下，我们给了一个时间复杂度为 的算法，这是针对于任意维度d的，而且我们给了一种改进的时间复杂度为的算法。
我们还提供了一种一种时间复杂度为的算法来估计最大的弗雷歇距离。此外，我们给一些时间复杂度为的算法来分别找到可以最小化最小和最大弗雷歇距离的两个模糊点序列。这些算法在实际设置中实现了恒定的因子逼近比率，例如，当模拟不精确点的球的半径大致相同时，或者当任何两个连续的不精确点相距很远时（使得它们的不精确区域不重叠）。
2.符号与准备
我们在中，而且用度量间距，它既不是欧几里得距离也不是距离。设 表示两个在中的两个点序列。耦合是一系列有序对 使得：
- and ，
- 对于每个属于 ，以下三个必有一个为正确的：
（1） 和 .
（2）和 .
（3）和 .
离散弗雷歇距离F（A,B）是 中所有耦合中最小的，见图一。
在下文中，我们考虑到两个点序列A和B 的不精确的情况，所以我们给出中两个紧密区域序列，表示为 和他们指定了 可能
图一：点序列 和 间的离散弗雷歇距离通过耦合（1,1），（2,2），（3,2），（4,3）实现，且
位于哪里，因此对于每个i,j，我们都会有 和。对于所有，我们用 来表示序列对于所有，我们表示为
我们会考虑两种不同的情况，在欧几里得方案中，区域为在中封闭的欧几里得球，而我们用的是欧几里得距离。在正交方案中，区域为封闭的轴对其框，使用的距离为。区域序列H 的实现是由点序列，，完成的。同样的，区域序列V的实现是由点序列， 完成的。我们使用和 分别来表示A是H的一种实现，B是V的一种实现。当和时，我们会说是的一种实现，这样会被表示为。
定义1 对于两个区域序列H和V，在所有中实现里，最小的弗雷歇距离就是最小的离散型弗雷歇距离：
对于两个区域序列H和V，在所有中实现里，最大的弗雷歇距离就是最大的离散型弗雷歇距离
请注意，在上面的定义中，最小值和最大值是精确定义的，因为区域hi，vj是紧凑的。 图2显示了最小的Fr#39;echet距离的一个例子。
图二 点集和是区域序列和的实现。最小弗雷歇距离是由 实现的，所以我们称。
3.1决定性算法
我们决定性算法是基于动态规划的。在这种意义下，它与Eiter和Mannila的计算离散Fr#39;echet距离的算法有关，但是我们使用了额外的不变量来解决不精确性问题。这些新的不变量是经过精心选择的可行性区域，它表明当前点可能位于哪里。注意，H，V的实现空间的直接离散化将产生指数时间限制，因为人们必须考虑由方程式对于每一对i，j，定义的nm表面的排列。
随着算法的进行，我们从左下角到右上角迭代地计算n行m列数组的单元格，即从（1,1）到（n，m），其中第i 行表示区域，并且第j列表示。每个单元（i，j）包含两个可行性区域和。
需要记住的是（或者）表示序列（或者）。我们可以在定义1中看到，可行性区域代表着可能在的区域，也就是 是的实现区域所在，而且在这一个区域存在一个实现了且上两对耦合不是，。当有个耦合的上两对不是，时，另一个可行性区域代表着可能在的区域。因此实现，如此以至于当且仅当右上部分可行性区域或不是空集。
我们的决定性算法的伪代码。1-8行的初始化了数组中第一行和第二行的某些区域，额外的第0行和第0列也是。它允许当i = 1和j = 1时在主循环中正确处理的边界情况。主循环是9-15行。我们给了在这个循环中如何计算单元（i,j）的可行区域的简要描述。方案的不同反应了对于离散型弗雷歇距离的定义。假设我们已经有了一个耦合的有序对，那么耦合中下一对有三对可能相对应的组。首先下一对可能为。这种情况对应于数组中的对角，且新单元的两个可行区域仅仅由相对应的的不准确性区域（14/15行）决定。而对于下一对第二和第三种可能性就是或，它们代表着数组中垂直或水平的阵列。很明显，对于垂直阵列来说即为，对于水平阵列来说即为。我们也可以从图三中看出算法的例子。
算法DecideFracute;echetMin
输入: 2个点集 和且delta; gt; 0.
输出: 当是为真，其他情况都为假。
1. for i larr; 1 to n
- FHdelta;(i,0) larr; empty;
- FVdelta;(i,0) larr; empty;
4. for j larr; 1 to m
- FHdelta;(0,j) larr; empty;
- FVdelta;(0,j) larr; empty;
- FHdelta;(0,0) larr; Rd
- FVdelta;(0,0) larr; Rd
9. for i larr; 1 to n 10. for j larr; 1 to m 12. then
11. if FHdelta;(i minus; 1,j minus; 1) = empty; and FVdelta;(i minus; 1,j minus; 1) = empty;
- FVdelta;(i,j) larr; FVdelta;(i minus; 1,j) cap; hdelta;i
- else FH
- FVdelta;(i,j) larr; hdelta;i cap; vj
- if FHdelta;(n,m) = empty; and FVdelta;(n,m) = empty;
17. then return FALSE 18. else return TRUE
(b)在每个单元在左下角，在右上角
（a）区域和是虚线的，这些点代表着满足和且
图三.算法的例子
引理1.对于任意，，有当且仅当或，更准确的说，对于任意，有以下：
（a），当且仅当存在使得，并且存在一个耦合的最后两对不是可以实现。
（b），当且仅当存在使得，并且存在一个耦合的最后两对不是可以实现。
我们现在在时可以证明引理1，可以很容易的去检查或的边界情况。我们仅仅证明引理（a）；（b）的证据是相似的。我们的证明是通过上的归纳来完成的。所以我们假设引理1适用于所有在单元之前的经过算法处理的单元。尤其对于那些单元使来说是正确的。
我们首先假设，然后我们要证明存在使得，而且可以使得存在一个耦合的上两对不是可以实现，我们可以从以下两个情况中分辨出来：
- 第一种情况： 然后，在引导下，存在使得。我们还知道被调到14行的。换句话说，，而且存在使得 所以我们可以通过选择和来延伸。我们通过一对来延伸一个耦合来实现从而来实现上两对不是的偶来实现。
- 第二种情况：。然后被调到12行的。因此，所以我们知道存在使得。只要，就存在使得。所以我们选择来扩展。我们通过一对来延伸一个耦合来实现从而使上两对不是的耦合来实现。
现在我们假设存在使得存在上两对不是的耦合C可以实现。我们想要证实，我们从以下两个方面来即可区分出来。
- 第一种情况：。它代表着被调到14行的。只要，就有只要它就符合，因此，所以。
- 第二种情况： 。然后，在引导下，有，代表着，所以不可以出现在C中。上三对仅可能是或。所以我们有。只要，就有。只要，，的值便被调到在14行的，所以我们有。
这样就完善了引理1证明。紧接着引理1，算法正确的决定了。但我们仍然要分析这个算法。在正交情况下，第12-15行包含交叉d维中的两个轴对齐框; 它可以在O（d）时间内完成。 因此，我们获得以下结果：
定理1.在d维正交情况下，使，给两个模糊点集H和V，各自有n和m个点，我们可以在时间复杂度为里决定是否正确。
3.2 提高欧几里得方案中的决定性算法
在这一部分，对于欧几里得方案我们给了一个有效的算法。算法的简单实现需要构造区域，这两个可以是在中个球的交点。
即使在中，它会使算法的运算时间增加一个数量级。为了提高运算效率，我们将会展示怎么一步步的去在时间里计算这些交点。
我们将需要Dyer的以下研究结果。
引理2（Dyer）在d维=时，我
全文共11876字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11861]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
