李想，章登义

(武汉大学 计算机学院,湖北 武汉 430072)

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

李想†，章登义

(武汉大学 计算机学院,湖北 武汉 430072)

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

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

如今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 回溯化简. 在当前时刻tc，原始轨迹序列为S:{s1,s2,…,si}，MOD维护的化简轨迹序列U={u1,u2,…,uj}⊆{s1,s2,…,si}，保留一部分历史轨迹序列Shistory:{si-l,…,si-1,si}，时刻tc+k×Δt(k∈N+)，位置服务器接收到新的位置点si+k，一旦si+k与线性预测位置点的距离大于ε或者Shistory的元素个数达到最大值，则对历史轨迹序列Shistory:{si-l,…,si-1,si,si+1,…,si+k}则进行离线化简.化简结果为ΔU，然后删除MOD维护的时间范围在[si-l.t,si.t)内的化简轨迹点后得到集合U′，新的化简轨迹序列为U=U′∪ΔU.

图1 回溯化简示例

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

证毕.

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

(1)

(2)

图2 原始轨迹映射到化简轨迹示意图

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

(3)

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

(4)

3 优化策略

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

3.1 速度预测模型的优化

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

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

(5)

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

(6)

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

(7)

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

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

图3 速度向量方向变化情况示意图

3.2 离线化简算法的优化

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

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

算法1.Opt+算法.

输入：回溯的历史轨迹序列Shistory:{s1,s2,…,sm-1,sm}，化简精度阈值ε

输出：化简结果u

1.H0={s1};B={s2,…,sm-1,sm};c=1;

2.WHILE(B≠)DO{

3.Hc←;

4.FOREACHsiinHc-1andEACHsjinBDO{//逆序访问Hc-1和U中的元素

5. cond=TRUE;

6.FOREACHskinShistoryWHEREsi.t

8. cond=cond &TRUE;

9.ELSE

10. cond=cond &FALSE;

11.BREAK;

12. }

13.IF(cond)THEN//si到sj的边存在

14.IF(sj==sm)THEN

15.RETURN; //已找到最短路径

16. con=TRUE;

17.FOREACHsqinShistoryWHEREsj.t

19. con=con &TRUE;

20.ELSE

21. con=con &FALSE;BREAK;

22. }

23.IF(con)THEN//sj到sm的边存在

24.RETURN; //已找到最短路径

25.B←B{sj};

26.Hc←Hc∪{sj};

27. }

28.c=c+1;

29. }

改进后的Opt+算法在采取了两种优化措施之后，避免了构建一些不会访问到的边的计算和一些顶点的访问，若化简结果中仅有起始点s1和终止点sm，则此时能够达到最好的时间复杂度O(m).由于Opt+算法通过集合关系来表示在有向无环图中顶点之间边的关系且只需要保存每个顶点，因此其空间复杂度为O(m).

4 实验结果

为了验证优化策略对轨迹化简性能的提升，本文在回溯化简框架下的在线化简方法的基础上用C++实现了上述优化策略.实验的硬件平台为：Intel®CoreTMi7-3630QM2.4GHzCPU, 16G内存和750GB硬盘；软件环境为Win7操作系统和VS2008编译系统.实验数据通过OpenStreetMap(OpenStreetMap.http://www.openstreetmap.org/)网站中的真实轨迹数据集提取获得.在实验中，化简率定义为原始轨迹的点数量与化简轨迹的点数量之比，化简误差定义为化简轨迹经由原始轨迹参考插值后的时态距离的平均值.

4.1 化简率提升验证实验

实验选取抖动系数分别为J=0.4,J=0.5,J=0.6,J=0.7和J=0.707等5类抖动程度依次减弱的轨迹，在化简精度阈值为10～50m变化过程中，分别使用切线速度和本文的优化速度时的化简率.

图4(a)给出了不同化简精度阈值下5类抖动轨迹的化简率比较图，可以看出在抖动系数较小，即轨迹抖动非常剧烈时，本文的优化速度下在化简精度为20～40m时与切线速度下相比具有一定的优势，但是随着抖动系数的增大，这种优势逐渐缩小至零.图4(b)给出了不同化简精度阈值下5类抖动轨迹的离线化简次数情况，可以看出轨迹抖动系数较小时，本文的优化速度下的离线化简次数通常小于切线速度下的离线化简次数，说明本文的优化速度比切线速度更接近对象未来的速度.图4(c)给出了与4(a)相应条件下的化简误差，可以看出在保证化简误差小于化简精度阈值的前提下，本文的优化速度下的化简误差与切线速度下相比十分接近.

化简精度阈值/m

化简精度阈值/m

化简精度阈值/m

4.2 化简时间性能提升验证实验

实验选取轨迹点数量为100万的轨迹，在化简精度阈值由10～100m的变化过程中，比较回溯化简框架下Opt+算法与Opt[6]算法的化简时间性能，同时将DP[8]算法和Sec[7]算法作为参照.

图5(a)给出了100万轨迹下化简精度阈值变化过程中化简所消耗时间的情况.4种算法中，Opt算法的化简时间随着化简精度阈值的变大而显著增长，Opt+算法的化简时间随着化简精度阈值的变大而略有减少，最终趋于平稳，DP算法受化简精度阈值变化的影响较小，Sec算法的化简时间随着化简精度阈值的变大而略有增长.化简精度阈值超过10m时，Opt+算法的化简时间性能优于Opt算法.在化简精度阈值为20～100m时，Opt+算法所消耗的时间约为Opt算法的10%～70%，这是由于化简精度阈值的增大导致化简队列平均长度变大，如图5(b)所示，使得Opt算法中构建有向无环图所消耗的时间显著增加，同时总体的化简次数减少，如图5(c)所示，使得变长段Opt+算法消耗的时间降低到一定范围.

化简精度阈值/m

化简精度阈值/m

化简精度阈值/m

5 结 论

本文在基于推测定位的时序轨迹回溯化简框架下，分别对化简过程中的速度预测模型和离线化简算法进行优化.实验结果表明，对于抖动剧烈的轨迹化简，优化后的速度下与原有切线速度下相比在化简率上有一定的优势，而优化后的离线化简算法与原方法相比在时间性能上有较大的提升.当前的工作主要有两点不足，一是仍然在欧氏空间中讨论移动对象时序轨迹的化简问题，而目前一部分移动对象的轨迹数据都是在道路网络下产生的，本研究没有考虑路网约束对化简的影响；二是化简没有将轨迹点的空间维度与时间维度相结合，仍然只是对空间维度进行化简，而把时间维仅作为空间维的一个附加维度.因此未来的工作将重点考察道路网络约束下的轨迹特征，着眼于基于道路网络的移动对象时序轨迹的时空化简方法研究.

[1] 吴乙万, 黄智. 基于动态虚拟障碍物的智能车辆局部路径规划方法[J]. 湖南大学学报：自然科学版, 2013,40(1):33-37.

WUYiwan,HUANGZhi.Dynamicvirtualobstaclebasedlocalpathplanningforintelligentvehicle[J].JournalofHunanUniversity:NaturalSciences, 2013, 40(1): 33-37.(InChinese)

[2]DAIJ,YANGB,GUOC,etal. Personalized route recommendation using big trajectory data[C]// International Conference on Data Engineering. Seoul: IEEE Computer Society, 2015:543-554.

[3] 许佳捷, 郑凯, 池明旻,等. 轨迹大数据:数据、应用与技术现状[J]. 通信学报, 2015, 36(12):97-105.

XU Jiajie, ZHENG Kai, CHI Mingmin,etal. Trajectory big data: data, applications and techniques[J]. Journal on Communications, 2015, 36(12):97-105.(In Chinese)

[4] BAIER P, DÜRR F,ROTHERMEL K. Opportunistic position update protocols for mobile devices[C]// Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York: ACM SIGMOD Record, 2013:787-796.

[5] LANGE R,DÜRR F,ROTHERMEL K. Efficient real-time trajectory tracking[J]. The International Journal on Very Large Data Bases, 2011, 20(5):671-694.

[6] KATSIKOULI P, SARKAR R, GAO J. Persistence based online signal and trajectory simplification for mobile devices[C]// Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM SIGMOD Record, 2014:371-380.

[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,etal. 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,etal. 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,etal. 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.

Backtracking Based Method for On-line Trajectory Simplification of Moving Objects

LI Xiang†, ZHANG Dengyi

(School of Computer, Wuhan University, Wuhan 430072, China)

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.

moving object database; trajectories; simplification; backtracking; linear prediction; temporal distance

1674-2974(2017)02-0149-08

10.16339/j.cnki.hdxbzkb.2017.02.021

2016-05-20

国家自然科学基金资助项目(60903035, 41001296),National Natural Science Foundation of China(60903035, 41001296);国家高技术研究发展计划(863计划)资助项目(2013AA12A301),National High Technology Research and Development Program of China (863 Program) (2013AA12A301)

李想(1987-)，男，湖北黄冈人，武汉大学博士研究生

†通讯联系人，E-mail: lixiang1987@whu.edu.cn

TP301

A