网络约束下的轨迹压缩外文翻译资料

 2022-11-03 19:01:58

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

网络约束下的轨迹压缩

Georgios Kellaris

University of Piraeus, Greece

1.介绍

一个移动物体的轨迹可以被描述为一组具有lt;x, y, tgt;形式的三元数组，其中(x,y)是物体在时间t时刻的地理位置。对未来参照的许多路径的保存使得对其压缩成为需要。此外，一般用来检索一个物体的路径数据的方法是用GPS接收器。根据[8]，从GPS 接收器接收的数据点有一个2到8米范围的误差。因此，一个将这些数据与路网匹配的问题出现了，它又被称为地图匹配问题[1]。

现有的工作尝试为在线或者离线数据解决压缩路径的问题。在线算法在新的点接收到时压缩路径数据，与之相对的，离线算法则在数据点提前已知的情况下进行压缩。离线算法被成现于[5]和[7]。在[7]的成果中，Meratnia和de By也提出了一个针对在线数据的算法。两个关于在线数据的算法还在[9]当中被提出。对于地图匹配问题，Brakatsoulas et al. 提出了一种仅针对离线数据的算法。

虽然现有很多针对压缩和地图匹配问题的建议，但仍没有在[6]中提到的，能同时满足数据压缩需求和网络匹配的保护的建议。

在本研究中，我们建议针对在路网限制下的车辆数据压缩要通过连续地使用existing compression 和map-matching 算法。另外，我们提出了一个全新的算法。该算法关于已经进行过路网匹配的路径压缩，同时评估路网限制。

本篇文章行文如下。第二部分回顾了一些现有的关于路径压缩、路径地图匹配和路径相似性搜索的成果，因为我们需要比较这些方法的结果。第三部分提出了我们对于在路网限制下的压缩的建议和算法。第四部分评估了应用我们方法的结果。第五部分进行总结。

2.背景

在本节中我们表现了如下压缩方法。Douglas Peckeur[5]和Meratnia的方法，de By[7]关于离线数据的方法，Meratnia和de By[7]提出的Opening Window (OW)方法，Potamias et al.[1]的适用于离线数据的Tresholds和STTrace方法。针对地图匹配问题，我们展现了Brakatsoulas et al.的只用于离线数据的算法。我们还展示了E.Tiakas et al.的路网中路径相似性搜索的算法。

2.1路径压缩

我们展示的第一个针对路径压缩的算法是有名的Douglas-Peckeur算法，如图一所示。

图一 Douglas-Peckeur算法[6]

该算法运行如下。首先，它计算每个内点到第一个和左后一个点的连线(图一中的AB)的距离。接着，它找到距离AB线最远的点（图一中的C点）然后连接AC和CB。该算法随后用同样的方式递归地检查剩下的每个点到新的线段的距离。当没有任何一个距离超过预先设定的阈值时，该算法返回一系列线段。新的多义线的点比原先的少。

Meratnia和de By[7]使用Douglas-Peckeur[5]算法创造了一个新的压缩技术，这种技术还考虑了时间参数。被提出的算法用新的距离替换了Douglas-Peckeur[5]算法中使用的距离。该距离称为同步欧式距离（SED），它考虑了如图二所示的时间维度。

令Pb为当前检查的在线段P1Pn 上的点，如图二所示。点Pbrsquo; 的坐标用SED计算如下。

其中，。

以上描述的算法需要关于路径的预备知识。因此，在同一个作品中，Meratnia和de By提出了可用于在线数据的名为Opening Window（OW）的算法。该算法工作如下。起初，它定义一个第一个点和第三个点之间的线段。如果任一内点到线段的SED不大于给定的阈值，则算法将末端点在数据集中后移一点。当阈值被超过时，有两个选项：要么造成超过阈值的数据点，或者它的前一点被定义为当前线段的末端点及新线段的初始点。只要新的点出现，该方法就如前所述持续下去。

另外得，Potamias et al.[9]提出两个真多在线路径数据压缩的算法，Thresholds和STTrace。这两种算法利用坐标，速率和当前点的方向去计算下一个点可能出现的安全域。如果下个来临的点出现在计算出的安全域内，那么他可以被忽略。对于安全域的定义有两个选择。它可以用随后一个点的数据计算得出，无论那个点是否之前被忽略掉，或者它还可以用最后一个被选中的点的数据来计算。为了得到更好的结果，Potamias et al.提出将两种选择结合起来。两种安全域都进行计算，但是只有他们的交叉部分才被定义为安全域。

Thresholds和STTrace算法的不同在于后者提供了一种移除职权选择的点的能力。令M为能储存的最大的点的数量。对于每一个被选中的点，它到它前一个点和后一个点构成的线段的SED被计算出来。关于每一个被选中的点，该计算在下一个点加入的时候发生。当一个新的点被选中然后储存的点数恰好等于M时，一个老的点必须被移除，或者新的点必须被忽略掉。该情况如下进行选择。一开始找出被储存的点中有最小SED 的点。然后，计算出最后两个储存的点和新点的SED。返回了最小SED 值的那个点应该被移除或者忽略。该点的移除带来了可能的最小信息丢失。

2.2地图匹配

现在，就地图匹配问题而言，Brakatsouls et al.提出如下关于离线路径数据的算法。起初，该算法找到离路径的第一个点最近的边界。随后，对每个点Pi，已知点Pi-1已经被匹配，我们求出与Pi匹配的候选边界，如图3所示。Pi-1和边界c3匹配，因此c1和c2就是Pi的候选边界。

如下的两个度量用于边界计算：

和

其中mu;d, mu;a, na, nd 和a是如作品[1]中描述的预先定义的比例因子。度量Sd代表了距离，度量sa代表了方向。这些度量的和S越大，这个边界的匹配就越好。

如果当前点在候选边界上的预测不在任何边界的终点之间，则该算法不能进行到下一个点。相反，候选边界中最近的一条被设定为路径的一部分，然后下一系列的候选边界要进行计算。

为了提升算法的功能性，Brakatsoulas et al.提出使用“向前看”原则。也就是说，每个候选边界的总得分是通过加总固定数量的对于初始一个的边界的分数的来的，这是先于当前位置的。

图4展示了一个“向前看”原则如何就点Pi被使用的例子。对于这个店的候选边界c2，边界c2,1是点pi 1最好的候选边界，而对于候选边界c1，边界c1,1是点pi 1的最佳候选边界。边界c1和c2的最终评分是每一个最好的附属路径分数的和。

Brakatsoulas et al.[1]的地图匹配算法并没有考虑时间维度，也不适用于在线数据。但是，如果我们将“向前看”边界等于0（没有“向前看”检验发生），那么该算法可以被用于在线路径数据。

2.3网络中的路径相似性

传统的针对路径相似性搜索的方法不能被用于网络中的路径。它们的结果会不准确。因此Tiakas et al.[10]提出了一个路网限制下的路径相似性搜索方法。

令c(ui, uj)为节点ui到节点uj的成本。这两个节点之间的路网距离d(ui, uj)定义为：

关于时间维度，路径Ta和Tb之间的时间距离定义为：

其中T[i].t被定义为路径的第i点的暂时数值。

两个度量都满足[10]中证明的度量空间特性。通过结合两个度量，总的相似性可以表达如下：

其中，和是预先定义的权重因子。

在上述的分析中，每一个路径的长度被认为是和另一个相等的。在一般情形下，两个路径的长度可能不一样，每一个路径要按如下被分解为子路径。给定一个长度为m 的路径T，和一个整数mu;lt;m, m-mu; 1个子路径通过使用长度mu;的一个窗口被创建，一次一个节点地移动不断地进行下去。图5展示了长度为m=6的路径T分解为4个子路径Si，每一个子路径长为mu;=3。对于给定的路径T为了防止m要小于mu;，则T的最后一个点要被不停的重复知道T的长度等于mu;。

总的距离Dtotal(Ta, Tb)通过结合每一个子路径的Dtotal计算得到，如[10]中所介绍。

3网络压缩的建议方法

如前面部分所述，对于网络上的轨迹压缩的问题没有解决方案。地图匹配算法可以提供一种压缩形式，但它们不是为数据压缩而设计的，它们不能压缩已经匹配到网络上的轨迹。在本节中，我们提出了可能在网络约束下提供轨迹压缩的方法。

结合meratnia和德的[ 7 ]的用于在线和离线数据压缩和brakatsoulas等人[ 1 ]的地图匹配算法。，我们创造

两种选择如下:

a）我们应用压缩算法（Comp）原始未匹配的轨迹数据，然后我们将地图匹配算法（MM）应用于输出。 我们称这种方法Comp MM。。

b）我们将地图匹配算法（MM）应用于原始不匹配数据; 然后我们应用压缩算法（Comp）到输出，最后我们重新应用映射匹配算法（MM）到新的输出。 我们称之为MM Comp MM。

在在线数据的情况下，我们使用OW算法压缩和Brakatsoulas等 [1]的没有“前瞻”功能的地图匹配算法。

3.1算法的串行使用问题

Brakatsoulas等人的地图匹配算法 [1]不保留时间数据。 该信息对于压缩算法的适当功能（为了计算SED）是关键的，并且对于我们来说也是重要的，以便保持有用的轨迹数据。

地图匹配算法需要重新形成以保留时间信息。 对于通过算法添加到最终结果的每个边，需要对相应节点上的时间进行近似。 为了实现这一点，我们需要保持每个边缘上的第一个和最后一个点投影的信息（如果有的话）。 有了这些信息，我们可以如下所述进行。

我们考虑了两种点预测P1（在相应的边上点投影）和P2（在相应的边缘一点投影）两相邻的边与P3作为他们共同的节点，因为它如图6所示。

我们可以计算节点上的P3的时间t，假定物体以恒定速度移动，如下。

图6-节点时间的计算
当是P1到P3的距离时，并且是P2到P3的距离。

在一般情况下，点P1和P3可能不在相邻的边上，我们定义为距离d

从点到给定节点的网络距离。我们定义网络距离为从点到最近节点的距离加上需要从点的边行进以到达给定节点的所有边的长度。让P1和Pn成为两个点

和P节点的时间信息，需要如图7所示计算。

图7-一般情况下，节点的时间计算

在节点Pr的时间Tr被计算为：

3.2一个解决网络约束下轨迹压缩问题的新方法

可以引入新的压缩方法，通过改变给定轨迹的一些路径为较短的

路径。 这可以通过对轨迹的特定点执行最短路径算法来实现。

我们可以定义该算法可以实现的最大压缩。 由于它在我们的轨迹的一些子路径上使用最短路径算法，所以最大可实现压缩是在轨迹的第一和最后一点上执行的最短路径算法的结果。 考虑到这一点，我们在下面的段落中提出建议的算法。

该算法如图8所示工作。给定网络上的由七个点{P1，P2，P3，P4，P 5，P6，P7}，我们可以计算出最大值 可实现的压缩是{P1，a3，P7}，如图8（c）所示。

在算法的第一次通过时的第一点针对其随后的点检查轨迹，直到点和初始点之间的最短路径如图8（a）所示。没有最短的P1和P2之间的路径，因为它们是连续的点。在P1和P3之间将存在最短路径如果它们直接连接的话。我们假设

它们不是直接连接的，并且有最短的通过节点a1连接P1和P4的路径。然后

我们可以将轨迹的子路径{P1，P2，P3，P4}改变为{P1，a1，P4}。因此，我们的轨迹已经缩短7分之1。我们还需要计算将在节点a1对象的时间。这可以通过估计使用节点P1和P4上的时间数据以及通过考虑对象以恒定速度移动的办法。

此方法类似于在3.1部分中描述的方法。

当找到最短路径时，算法存储该路径结果并通过定义最后一个节点继续传递

找到的最短路径作为第一点并通过检查这个节点的连续点。在我们的例子中，我们检查P4作为下一个点。

如果我们需要一个更压缩的结果，该算法继续到第二

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140965]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章