基于回溯的移动对象时序轨迹在线化简方法

摘 要：针对从移动端采集到的移动对象原始轨迹序列的化简，定义了一种回溯化简框架，通过线性预测来控制化简的时机，对当前时刻到回溯的历史轨迹的起始时刻之间的原始轨迹进行离线化简，化简采用时态距离作为误差度量方法.在回溯化简框架下，首先利用每次离线化简后新产生的化简点构建多个向量，通过向量计算出预测速度方向，旨在缩小预测方向与未来真实速度方向的差异；然后利用点集合存储有向无环图中必需访问边来降低最优线化简算法的时间复杂度.第1组实验表明，相对于直接使用最近两个位置点计算速度方向，抖动较为剧烈的原始轨迹在新的预测速度方向下的化简率更高，说明预测速度方向比切线速度方向更接近移动对象的未来运动方向；第2组实验表明，优化后离线化简算法的时间性能有所提高，说明减少边的访问量确实能够降低算法的时间开销.

关键词：移动对象数据库；轨迹；化简；回溯；线性预测；时态距离

中图分类号：TP301 文献标志码：A

Backtracking Based Method for On-line

Trajectory Simplification of Moving Objects

LI Xiang， ZHANG Dengyi

（School of Computer， Wuhan University， Wuhan 430072， China）

Abstract：For the simplification for the original trajectory sequence of the moving object collected from the mobile devices， this paper defined a kind of backtracking based simplification framework， which used the linear prediction and length of simplification queue to dominate the time of simplification， and simplified the original trajectory sequence between the present moment and starting time of a retrospective historical trajectory adopting the method of temporal distance as the error metric. In the backtracking based simplification framework， this paper first utilized the new reduced points to construct several vectors and predicted the velocity， which could narrow the gap between the prediction and actual velocity in the future. This paper then utilized the point sets to store the edges in the directed acyclic graph needed in the access to reduce time complexity of the algorithm. The first experiment shows that the reduction rate using the optimal velocity prediction is greater than that of the original velocity prediction with the high fluctuant trajectory data. It suggests that the predicted velocity is closer to the actual velocity in the future moving direction than that in the tangent direction. The second experiment shows that the time performances of the optimized simplification algorithm are improved. This study shows that the reduction of the visits of the edges can decrease the time overhead of the algorithm.

Key words：moving object database； trajectories； simplification； backtracking； linear prediction； temporal distance

如今GPS设备的普及使得基于位置的服务（Location Based Services，LBS）市场迅速增长，催生了大量的基于位置的应用.例如在车辆导航系统中，新的路线规划服务需要根据环境、车辆运行状态和道路交通规则[1]，综合考虑多个行车成本（时间、距离、油耗等），通过收集和分析车辆的历史轨迹得到驾驶员的行车偏好，然后为其定制个性化的行车路[2]. 而“未来1小时路况预测系统”将高速公路通行状况的历史数据、实时数据与路网状况结合，预测未来一小时内高速公路的拥堵状况.其次在商业动线设计中，通过分析大多数顾客在大型超市或者购物中心内的行进轨迹，找到不同类型顾客的兴趣点，对不同商品的摆放区域或不同商铺的位置进行精心设计，让顾客在商业体内部停留时间更久，在购物过程中尽可能经过更多有效区域，提升销售额.上述应用都需要使用大量的车辆、人的时序轨迹数据，但是，目前在使用轨迹数据中存在着三大问题，第一，通过网络传输大量的原始轨迹数据的代价十分高昂；第二，由于轨迹数据的低价值密度和存储设备限制，数据库无法保存全部轨迹数据[3]；第三，不断增长的轨迹数据规模使得在其中发现有用的模式变得更加困难，因此对原始轨迹进行化简和压缩具有重要的研究价值和实际意义.

一些研究引入压缩和线化简算法对移动对象的历史轨迹进行化简，实际是一个折线近似过程，首先由获取到的移动对象的轨迹点之间的连线构成时空折线来表达移动对象的原始轨迹，然后找到一条新的轨迹使其包含的原始轨迹尽量少点且尽可能接近原始轨迹，这一类方法的压缩率高，但是时间复杂度高，不适用于实时化简.一些研究者提出基于推算定位的化简方法，这一类方法需要根据现有的轨迹对移动对象未来的运动速度矢量进行估计，实际是对原始轨迹进行分段离线化简的过程，速度矢量估计的精确度直接影响到化简的质量，离线化简的效率直接影响到化简的时效性.另一些研究者提出了基于区域过滤的方法，该算法不同于用一条折线来近似原始轨迹的方法，通过参考运动速度、方向和时间构建安全区域来对原始轨迹点进行过滤，安全区域的构建代价高.

本文的研究基于推测定位通过回溯部分历史轨迹点来预测移动对象在未来一段时间内的运动趋势，在实际位置点与预测位置点的距离超过化简精度阈值时，对当前时刻到回溯的历史轨迹的起始时刻之间的轨迹进行化简.针对上述化简过程，本文对两个步骤进行了优化，首先针对整体抖动较为剧烈的轨迹，改进速度矢量的预测方法，减少离线化简的次数，提升轨迹的化简率；然后对离线化简算法的实现过程进行优化，提升化简的时间性能.

1 相关工作

在线化简的含义是在通过移动设备不断获取移动对象的轨迹点时对移动端累积的轨迹进行化简，旨在减少轨迹点从移动设备传输到服务器过程中的通讯代价，同时降低存储轨迹的代价.目前，已有的研究中，移动对象轨迹在线化简方法是根据其是否需要累积部分历史轨迹来对后续的轨迹点进行化简，化简方法可分为部分在线化简和完全在线化简.

1.1 部分在线化简

部分在线化简方法的核心思想在于不断累积和抛弃原始轨迹点，将化简转化为对无数个轨迹段的离线化简.第1类为基于推算定位[4]方法，该类方法是根据当前轨迹点和预测速度来估计下一个轨迹点，当下一个轨迹点的实际位置与估计位置的距离超过化简误差时，将该轨迹点放入化简轨迹，具有代表性的有线性推测定位（Linear Dead Reckoning）、连接保持推测定位（Connection-Preserving Dead Reckoning）和GRTS （Generic Remote Trajectory Simplification） [5].后者在前两者的基础之上将轨迹分为稳定部分、可变部分以及预测部分，通过预测部分推算预测轨迹点的位置，一旦预测轨迹点与实际轨迹点的距离大于化简误差，则对可变部分和预测部分的原始轨迹点进行离线化简，采用的离线化简方法主要是最优线化简方法Opt（optimal line simplification）[6]、段启发式方法Sec（segment heuristic）[7]以及道格拉斯普客算法DP（Douglas-Peucker）[8].基于推测定位方法的关键在于预测速度矢量的精度，其采用的速度矢量预测方法是直接使用预测起始点和其之前一点的向量进行减法运算后除以两点的时间间隔得到，即近似轨迹在预测起始点的切线方向.该方法对于较为平稳的轨迹能够保证在较长一段时间内移动对象的预测位置与实际位置的距离不超过化简精度阈值，但是对于抖动剧烈的轨迹，该方法得到的速度矢量与移动对象未碓硕方向的差距较大，使得化简过程中频繁触发离线化简，化简率降低.另一类是基于区域过滤方法，国内的一些研究者利用最小边界扇形[9-10]来近似简化移动对象的原始轨迹，在角度和距离两个层面上对简化误差进行控制，另一些研究者[11]通过引入速率和偏离阈值，构造分别适应于局部和总体速度的安全区域，实现轨迹简化.对于移动对象的运动速率和方向波动频繁的情况，基于区域过滤的方法需要频繁重新构建安全区域，计算代价较高.

1.2 完全在线化简

完全在线化简与部分在线化简的区别在于前者在化简过程不回溯历史轨迹点，只判断新到来的轨迹点是否是化简点.最常见的在线化简方法为均匀采样法（Uniform Sampling），即每间隔相同数量的原始轨迹点采样一个点放入化简轨迹，该方法简便快速，但是化简误差大.另一类经典的在线化简方法为OPW-TR[7]，其核心思想是首先以原始轨迹的第一个点为起始点开始维护一个窗口，不断将新的原始轨迹点放入窗口中，直到原始轨迹到起始点与窗口中某一点连线的同步欧氏距离超过阈值，此时将该点或该点之前的点放入化简轨迹中，并且以该点或该点之前的点为起始点重新维护窗口，该方法每接收到一个新的轨迹点后需要进行多次距离计算，时间复杂度较高.为了更好地保留轨迹的位置、时间和速度信息，有研究者提出了一种在线化简方法SQUISH[12-13]，使用优先队列过滤轨迹点实现化简，对于优先队列中除起始点外的任意一点，其优先级为该点到与该点相邻的前后两点之间连线的同步欧氏距离，一旦新进的点的到来导致优先队列溢出，则将优先级最低的点从队列中移除，并调整该点相邻两点的优先级.该方法与推测定位和道格拉斯普克算法相比在压缩率较小的情况下，化简误差较小，该化简方法的优先级计算方法不适用于高压缩率的化简.

2 回溯化简

本文以连续获取移动对象的传感轨迹为背景，将轨迹化简过程放置在客户端，客户端上的位置传感器不断感知新的位置，同时客户端通过化简框架对获取到的轨迹数据进行回溯化简，化简产生的化简点即时发送给移动对象数据库（Moving Object Databases，MOD），保证MOD接收的化简轨迹经过插值后与原始轨迹的误差小于给定的化简阈值.化简框架的符号说明如表1所示.

定理1 当回溯的历史轨迹序列长度达到阈值而触发离线化简的次数忽略不计时，回溯化简过程中根据历史轨迹序列推算的预测速度方向越接近移动对象在未来的实际运动速度方向，则轨迹的化简率越高.

证明 以图1为例，假定Shistory的长度阈值为100，若s8.t时刻的另一个预测速度v′p比vp更接近移动对象的未来速度，使得|s8.p-（u′3.p+v′p × （s8.t-u′3.t））|

证毕.

上述化简过程中的距离度量方法定义如下：

定义2 时态距离. 在二维空间中，给定原始轨迹S上的任意子轨迹段{si，si+1，…，si+l}，其时态映射化简轨迹段为ujuj+1（uj.t≤si.t

s′a.p=（sa.t-uj.t）uj+1.t-uj.t（uj+1.p-uj.p）+uj.p（1）

sa到化简轨迹段ujuj+1的时态距离为sa到s′a的欧氏距离：

disttemporal（sa，ujuj+1）=distEuclidean（sa，s′a）=

sa.p-（sa.t-uj.t）uj+1.t-uj.t（uj+1.p-uj.p）-uj.p（2）

引理1 原始轨迹S上任意子轨迹段{si，si+1，…，si+l}在化简轨迹U上的时态映射轨迹段为ujuj+1，如图2所示原始轨迹点si，si+1，…，si+l在轨迹段ujuj+1上的时态插值点分别为uj，s′i，s′i+1，…，s′i+l，uj+1，由式（2）得到原始轨迹段{si，si+1，…，si+l}的化简误差之和为∑i+la=idistEuclidean（sa，s′a），根据定积分的几何意义，当Δt趋近于零时，原始轨迹段{si，si+1，…，si+l}的化简误差之和近似为直线ujuj+1与曲线sisi+1…si+l∧围成的几何图形的面积.

由引理1可知，对于任意一段原始轨迹，若其对应化简轨迹的轨迹点越多，则该段原始轨迹的化简误差越小.

定义3 平均化简误差. 在二维空间中，原始轨迹序列为S：{s1，s2，…，sn}，化简轨迹序列U={u1，u2，…，ul}{s1，s2，…，sn}且U是按照化简精度阈值ε对S进行化简得到的，根据定义1，对于S上任意一轨迹点s1的时态距离为distEuclidean（si，s′i），其中s′i为si在化简轨迹段ujuj+1上的时态插值点，这个时态距离又称作轨迹点si的化简误差，那么原始轨迹序列S的平均化简误差为：

1n∑ni=1distEuclidean（si，s′i）=1n∑ni=1si.p-s′i.p（3）

定义4 轨迹抖动系数J. 原始轨迹序列S：{s1，s2，…，sn}中任意连续三点si-1，si，si+1，组成的两个向量si-1si和sisi+1的夹角余弦值为si的抖动系数，描述轨迹在si的抖动程度，则轨迹的抖动系数J为轨迹中所有连续三点组成的向量的夹角余弦值的平均值：

J=1n-2∑n-1i=2cos 〈si-1si，sisi+1〉 （4）

本文将轨迹抖动系数J=2/2作为轨迹抖动剧烈与否的分界线，抖动系数小于2/2的轨迹为抖动轨迹，即上述两个向量的角度差为45°～180°，抖动系数大于2/2的轨迹为平稳轨迹，即上述两个向量的角度差为0～45°，抖动系数越小则抖动越剧烈.

3 优化策略

本节将详细描述针对回溯化简框架下的在线化简算法的两个优化策略.

3.1 速度预测模型的优化

由于移动对象的运动具有惯性，而化简轨迹序列的更新反映了移动对象的运动方向l生了显著变化，因此我们通过MOD服务器接收到的化简点（包括后来被替换掉的）对速度矢量进行预测.

情形I 当前离线化简后新产生的化简点数量大于等于2时，说明移动对象在最近的几个化简点所覆盖的时间区域内发生较为显著的运动方向变化，此时通过MOD服务器最近接收到的4个化简点ui-3，ui-2，ui-1，ui构建如下3个向量：

v1=ui-2.p-ui-3.pui-2.t-ui-3.t，v2=ui-1.p-ui-2.pui-1.t-ui-2.t，

v3=ui.p-ui-1.pui.t-ui-1.t（5）

判断第1个向量到第2个向量的变化方向是否与第2个向量到第3个向量的变化方向是否同时向下或向上，若为肯定，则如图3（a）和（b）所示，此时轨迹呈现上扬趋势或下降趋势，预测速度的方向为：

vp=2v3-v2=2ui.p-ui-1.pui.t-ui-1.t-

ui-1.p-ui-2.pui-1.t-ui-2.t （6）

预测速度的大小为ui-1和ui之间的平均速率，若不是，则如图3（c）和（d）所示，此时轨迹呈现波浪变化，预测速度的方向为：

vp=12（v2+v3）=12（ui-1.p-ui-2.pui-1.t-ui-2.t+

ui.p-ui-1.pui.t-ui-1.t）（7）

预测速度的大小为ui-1和ui之间的平均速率.

情形Ⅱ 当前离线化简后新产生的化简点数量小于2时，说明移动对象在历史轨迹序列覆盖的时间范围内运动方向的变化不显著，此时通过MOD最近接收到的两个化简点ui-1和ui所覆盖的时间区域[ui-1.t，ui.t]内的原始轨迹序列的三等分点和ui-1，ui构建与情形I类似的3个向量，然后采用与情形I相同的方式计算预测速度方向，预测速度的大小为ui-1和ui之间的平均速率.

3.2 离线化简算法的优化

本文针对推测定位中离线化简通常采用的最优化线化简算法的实现过程进行优化，原算法的化简过程分为3步：第1步，根据回溯的历史轨迹点构建有向无环图；第2步，求有向无环图中起点s1到终点sm的最短路径；第3步，返回最短路径为化简结果.

本文在两个步骤中采用优化措施降低算法的时间复杂度的同时降低空间复杂度，第一是针对最优化线化简算法在第1步中构建有向无环图时需要构建所有可能存在的边，从而导致时间复杂度高的特点，仅仅构建广度优先搜索的过程中需要访问到的边，减少时态距离的计算量，且通过集合来代替邻接表或邻接矩阵存储边.具体做法是在广度优先搜索过程中将所有轨迹点进行分类，分类的原则是按照它们到起始点的距离进行判断，距离为0的点是起始点s1本身，因此将s1单独作为一个集合，然后访问到s1距离为1的所有点，把它们放入一个集合.再访问到这个集合中的每一个点距离为1且没有被放入任何一个集合的点，将这些点放入到一个新的集合中，然后对新的集合进行上述相同的处理，直到终点sm放入某个集合中.第二是每当访问到一个与当前集合Hc-1中的点之间存在边的点，就直接判断其与终点sm之间是否有边，若存在边，则最短路径已经得到，避免扫描一部分不相关的点.具体算法如下：

[7] MERATNIA N，ROLF A. Spatio-temporal compression techniques for moving point objects[C]// Proceedings of the International Conference on Extending Database Technology. Greece： Berlin Springer， 2004： 765-782.

[8] DOUGLAS D H， PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica： The International Journal for Geographic Information and Geovisualization， 1973， 10（2）：112-122.

[9] 王欣然， 杨智应. 基于最小边界扇形的移动对象轨迹实时化简算法[J]. 计算机应用， 2014， 34（8）： 2409-2414.

WANG Xinran，YANG Zhiying. Real-time trajectory simplification algorithm of moving objects based on minimum bounding sector[J]. Journal of Computer Applications， 2014， 34（8）： 2409-2414.（In Chinese）

[10]王欣然， 钪怯. 基于PLAZA的移动对象 轨迹实时化简方法[J]. 计算机应用研究， 2014， 31（5）： 1315-1319.

WANG Xinran，YANG Zhiying.Method of real-time trajectory simplification of moving object based on PLAZA[J]. Application Research of Computer， 2014， 31（5）：1315-1319.（In Chinese）

[11]李文海， 程志光， 文卫东， 等. 基于自适应安全区域的轨迹实时化简方法[J]. 计算机学报， 2014， 37（9）：1923-1935.

LI Wenhai， CHENG Zhiguang， WEN Weidong， et al. A safe-region based adaptive method for real-time trajectory simplification[J]. Chinese Journal of Computer， 2014， 37（9）：1923-1935.（In Chinese）

[12]MUCKELL J， HWANG J H， PATIL V， et al. SQUISH： an online approach for GPS trajectory compression[C]// Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications. Washington DC： ACM SIGMOD Record， 2011， 13：1-8.

[13]MUCKELL J， OLSEN P W， HWANG J H， et al. Compression of trajectory data： a comprehensive evaluation and new approach[J]. An International Journal on Advances of Computer Science for Geographic Information Systems， 2013， 18（3）：435-460.