矢量轨迹有损压缩余弦垂距判别法

李升宏，耿生玲,2，田立勤,3，李路加，陈 娜，林连海

(1.青海师范大学 计算机学院，青海 西宁 810008；2.高原科学与可持续发展研究院，青海 西宁 810008； 3.华北科技学院 计算机学院，河北 廊坊 065201)

随着通信信息技术快速发展和广泛应用，产生了与人们工作和生活息息相关的海量数据。此类海量数据，应用于大到对航天、航空和卫星的轨迹实时跟踪中，小到无人驾驶、公交站台显示和到站提醒、网约平台的实时定位以及用户每时每刻所形成的位置变化中等，而这些数据都离不开矢量数据的获取与处理。一方面，矢量数据会源源不断地生产与输出，另一方面，用于存储数据的设备介质和计算机的处理能力始终有限。因此，矢量数据的有损压缩问题研究是大数据存储与传播的关键问题之一。

矢量数据指既有大小又有方向的一类数据集，通常用于表示地图图形或地理实体位置或形状的数据。轨迹压缩处理也叫曲线的特征点处理，或曲线的抽稀处理。压缩方法通常分为有损压缩[1]和无损压缩[2]，按其技术特点又可分为批处理算法、在线算法[3]和单遍扫描算法。前者是从待压缩的数据中精确地重建原始数据，不会造成信息损失。而后者是在一定误差范围内，从原始曲线Γ数据集中压缩重复冗余或连续变化形态不明显的数据元素，将剩余的元素按原序连接形成新的曲线Γ′。其中，Γ′⊂Γ，Γ′是Γ的子集。

当前，已出现众多成熟的有损压缩理论，如垂距限值法[3-7]、角度限制法、面积偏差控制法以及经典的道格拉斯(Douglas-Peucker,D-P)算法等[8-13]。王笑天等[14]针对D-P算法存在大量迭代计算问题，提出第一特征点提取法，把时间复杂度降到O(n)。但是，该算法每次操作的均是局部第一特征点，没有对全局特征点进行权衡，压缩后曲线部分出现形变。杨得志等[8]对D-P算法改进，利用径向距离作为补充约束条件控制压缩面积的误差，虽然使得压缩后的曲线较为光滑，但算法仍然存在大量的迭代操作。米学军等[5]利用直线逐渐逼近曲线空间，提出了面积偏差限值法，很大程度上解决了由于线段空间偏移过大以及面积偏差不可控的问题，效果明显。但是，需要进行大量的直线空间相交点方程求解和多边形面积的计算，导致时间复杂度剧增。

陈飞翔等[15]提出基于动态规划的矢量压缩算法。该算法通过一条参考路径构造一条可自适应调整宽度窄带区域，可限定最小误差搜索范围，算法虽然能有效缩短计算时间，减少压缩误差，但没有考虑多实体间的整体优化关系，会导致局部失真明显。汪林林等[16]在动态规划的基础上进一步改进，设定阈值最大位移防止局部失真，有效地解决了曲线部分失真的问题，但由于时间复杂度依然过高，不适用大数据下的矢量轨迹压缩。WEI等[17]设计了一种考虑轨迹空间和运动特征的算法。该算法能够根据船舶行为特征对自动识别系统(Automatic Identification System,AIS)轨迹进行有效的压缩，但算法中阈值参数不能自适应确定，且计算复杂度过高。张甜等[18]利用分段处理的思想，在速度保留算法的基础上提出基于速度分段的移动对象轨迹简化处理算法。该算法将原曲线分割成不同的速度保留段，通过计算各段的同步欧氏距离阈值进一步处理曲线节点，实验证明其效果好于速度保留算法。但是，该算法也是采用D-P算法简化轨迹，时间复杂度还是O(n2)，不适用于大数据下的矢量轨迹压缩。

为了进一步降低矢量轨迹压缩算法的时间复杂度，提高算法的处理能力，拟提出余弦垂距判别(Cosine Vertical Distance Discrimination,CVDD)算法。首先，该算法借助D-P算法和垂距限值法的垂距思想，通过优化角度限值法的角度判断方式减少空间计算。其次，利用球面余弦定理降低球面上两点间的距离误差。最后，把待处理轨迹划分为直道和弯道两种轨迹，并对各路段中的中间元素进行求其与底边线段上的垂距，将所得垂距与算法设定边界垂距阈值进行对比，再对垂距值小的中间元素进行压缩。最后,将该算法应用到二次青藏科考线路、卡车和出租车真实轨迹数据集中进行压缩实验，以验证所提算法的可行性和有效性。

1 预备知识

定义1球面坐标。地球表面上任意位置点P表示一个坐标对象P=(x,y,…)。其中：x表示位置所在的经度；y表示位置所在的纬度。P可扩展多个属性，如果移动物体在球面上运动，那么该物体在地球表面上t时刻的位置可以表示为Pt=(xt,yt,…)。

定义2矢量轨迹。运动物体在地球表面上按某种时间顺序沿着任意方向移动，则该物体会在地球表面上形成一条轨迹，用Γ={P1,P2,…,Pn}表示。Γ是一个连续的序列集，轨迹Γ中的第i个轨迹点可表示为Γ[i]，或者Pi。

定义4球面距离。设球面上任意两点PA(x1,y1)和PB(x2,y2)，两点间距离为dAB，地球半径为R，R≈6 370.856×103m，圆周率π=3.14，则可计算出PA的经纬度角分别为

PB的经纬度角分别为

进而得出PA和PB两点之间的球面距离为

dAB=Rarccos[(cosβ1cosβ2cos (α1-α2)+sinβ1sinβ2)]

定义5三元组。在矢量轨迹集Γ中，按照时间顺序依次序选取3个元素构成的子序列为Γ{Pk,Pk+1,Pk+2}(0≤k

定义6球面三角形面积。假设球面上任意不同的3点为PA(x1,y1)，PB(x2,y2)和PC(x3,y3)。3点形成的球面上的三角形面积为S△ABC，则根据定义4和海伦公式可求得

其中，

于是，可根据所求面积S△ABC求得三角形任意边对应的垂直高度分别为

定义7球面三角余弦值。球面上任意不同3点PA(x1,y1)，PB(x2,y2)和PC(x3,y3)，设点PB与线段dBA和dBC所构成夹角θB的余弦值为cosθB，则有

定义8压缩率。假设原始曲线Γ中的元素总个数为n，压缩后曲线中的个数是n′，压缩率为η，则原始曲线的压缩率为

其中,η越小，压缩程度越大。反之，压缩程度越小。

定义9最大位移。假设曲线上待压缩点Pi与其前后两点Pi-1和Pi+1所形成的线段的距离L为该待压缩点Pi到压缩后新曲线上的位移，则所有待压缩点与其前后两点所形成线段中位移最大的一个可设为Lmax。如图1所示：P2为待压缩点，则其与前后两点P1和P3所形成线段的位移为L1；P7为待压缩点，则其与前后两点P6和P8所形成线段的位移为L2；P10也是待压缩点，同理可以得到P10与前后两点P9和P11所形成线段的位移为L3。通过对比可以得到位移最大的是L1。因此，所有待压缩点与压缩后新曲线上的最大位移的表达式为Lmax=max{L1,L2,L3}=L1。

图1 最大位移示意图

定义10位移之和。假设原始轨迹Γ中全部待压缩点与其前后两点所形成线段上位移的总和为S,则根据定义9可知

2 经典压缩算法

当前成熟的有损压缩算法主要有垂距限值法、角度限值法以及经典的D-P算法。这3种算法都需要预先设定一个可容忍的限差值d或θ，然后再将原始轨迹Γ划分为一组组的三元组，通过对每组三元组进行节点间的距离计算或角度计算，把得到的距离d′或角度θ′分别与预设限差值进行对比判断，保留值大于限差值的节点，压缩值小于限差值的其他全部节点，从而达到矢量轨迹的有损压缩。前两种算法易于编程，操作简单，处理速度快，时间复杂度都为O(n),但当遇到曲率较大的弯道或者连绵起伏的路段时，完全破坏了原始路线的形态要素，压缩效果不佳。原始轨迹的形态要素被严重破坏情况如图2曲线走势所示。

图2 原始轨迹的形态要素被严重破坏情况

第三种算法是一个从全局到局部的过程，通过不断分割与遍历查找，从中发现和保留分割后的每段曲线的完整形态要素，在很大程度上保证曲线的基本形状不发生明显改变。但是，时间复杂度较高，最大为O(n2)，当待处理轨迹节点过多时，需要耗费更多的处理时间。

2.1 垂距限值法

垂距限值法是一种沿着同一方向顺序执行的局部压缩法。首先，设置一个可容忍的限差d，然后，从曲线的一端开始，每次顺序选取3个点构成三元组，构建第一、三两点间的直线，通过计算第二点d′到该直线的垂直距离，起点和终点除外，判断d′与d的关系。如果d′

图3 垂距限值法执行过程

2.2 角度限值法

角度限制法和垂距限值法的处理方式类似，也需要预先定义一个可容忍的限差θ，从曲线一端逐次遍历每个三元组，再进行每一步的角度值判断。该算法是从曲线一端选取一对三元组，先将第二点和第三点分别与第一点连线，即起点和终点除外，计算两线之间现成的夹角值为θ′。若θ′≥θ，则保留第二点，并以第二点为起点，继续作第三、第四点与第二点之间的连线；否则压缩第二点，并以第三点作为起点，重复以上工作，直到遍历完成。角度限值法执行过程如图4所示。

图4 角度限值法执行过

2.3 D-P经典算法

图5 D-P算法执行过程1

图6 D-P算法执行过程2

图7 D-P算法执行过程3

图8 D-P算法执行后最终压缩效果

3 余弦垂距判别法

3.1 算法思想

为了弥补垂距限值法、角度限值法和D-P算法的共同不足之处，CVDD在对三元组处理时，把每组三元组分成两种层面进行，在点层面对三元组中间元素的前后邻边距离作为首要条件。首先，识别三元组构成为密集点集或稀疏点集。然后，过滤掉密集点集中间元素，在线层面先通过余弦值作为判断条件将三元组按序连成的局部轨迹识别为曲直路段或弯道路段两种情况。最后，再通过边界垂距阈值dmax和dmin进行判断是否压缩各情况中三元组中的中间节点。整个处理过程考虑较为全面，进而将每一个不符合条件的中间元素进行压缩。

处理结果会出现两种极端情况，当阈值d非常大时，压缩后的Γ′只包含起点和终点元素，压缩率为η=2/n×100%，当阈值d过小时，又会出现压缩率为100%，即一个元素也没有压缩。

3.2 算法步骤说明

步骤1先获取原始矢量轨迹Γ，并以Γ构建动态列表，设为Plist。

步骤2循环遍历Plist，每次按序获取一组三元组，并以该三元组上3个点Pi、Pi+1、Pi+2，构建三角形，设为△ABC，并设其三角形三边分别为a,b,c。

步骤3通过定义4分别计算△ABC的边长a,b,c，若同时满足a≤dmax，c≤dmax，则识别3点为密集点集路段，压缩中间节点，并以Pi节点继续承担下次循环的起始点，循环继续。否则，识别为稀疏点集路段，执行下一步操作，其中，dmax取常量值，取值越大，原始轨迹处理后的失真程度越严重。因此，为了降低原始轨迹处理后的失真程度，实验中设定垂距上限阈值dmax为3 m。

步骤4若步骤3判断为稀疏点集路段，则通过步骤3所得三边距离a,b,c分别与定义6和定义7计算的△ABC底边上的高h和中间节点的余弦值cosB。如果cosB≤cosθ，则认为当前稀疏路段为曲直路段，包括直线。其中，cosθ是常量值，因为cos 180值为-1，为保留一定的误差范围，故取cosθ=-0.75。继续使用底边上的高h与dmax对比，若h≤dmax，则压缩中间点，继续以Pi为起始点，循环继续。否则，保留中间点，并以中间点作为下次循环的起始点，循环继续。

步骤5通过步骤4的判断，如果cosB>cosθ，则认为当前的稀疏路段是弯道。将底边上的高h与dmin进行对比，若h≤dmin，则直接压缩中间节点，并以Pi继续承担起始点，循环继续。否则，保留中间节点，以中间节点作为下次循环起始点，循环继续，其中，dmin也是常量值，其取值越小，压缩的坐标点数越少。因此，为了有效提高压缩坐标点的数量，选取垂距下限阈值dmin为2 m。

环境温度对矿化垃圾反应床稳态运行性能具有较大影响，主要表现在影响污染物去除性能及床体水力渗透性能2个方面。

步骤6持续步骤2～步骤4操作，直到算法遍历完成，Plist中剩下的元素即为压缩后的新数据集Γ′。

3.3 复杂度分析

根据算法步骤易知，CVDD算法仅对矢量数据集进行一次扫描。因此，时间复杂度为O(n)，考虑在该算法操作中定义的都是常量值，空间复杂度为O(1)。

4 实例结果与分析

实验共设3组真实数据集，分别是青藏科考数据集、北京出租车数据集以及北京卡车数据集，各组实验数据集信息如表1所示。

表1 实验数据集

4.1 实验环境

实验配置环境设定：硬件设备处理器为Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz 3.19 GHz，内存条大小8 GB，硬盘大小500 GB,固态盘256 G；软件为Window 10教育版64位，JDK1.8；开发工具为idea 2020.1,使用高德地图；开发语言用Java。

4.2 实验结果与分析

由于垂距限值法、角度限值法及D-P算法等都需要设置预先阈值。因此，在选取相同的限差值条件下，在同一台电脑上进行3组实验，每一组实验中，都统计CVDD算法与对比3种算法，在随着自变量即轨迹点数的变化所带来的一系列因变量如执行时间、压缩坐标点数、压缩前后位移的变化情况。最后，把4种算法分别在3组实验中运行实验，实验数据汇总结果如表2所示，数据分析分别如图9至图17所示。

表2 垂距限值法与CVDD算法在3组实验中的实验结果

图9 出租车组中不同算法的运行时间对比

图10 出租车组中不同算法的运行时间合并对比

图11 出租车组中不同算法的压缩率对比

接下来对每一组实验的折线图进行对比讨论。

1)在出租车组实验中，通过图9可知，随着原始轨迹中坐标元素的数量增大，4种算法的处理速度也受到原始轨迹中线路的形态要素影响而波动。其中，D-P算法从箭头指向的单位来看，使用时间最大，以107ms为单位，而其他的算法最大不超过800 ms。因此，从时间复杂度上判断，D-P算法性能不好，执行时间过长是因为其使用了大量的迭代操作。从图10可以看出，角度限值法的处理速度比垂距限值法和CVDD算法的处理速度要略胜一筹。从图11可以看出，随着原始轨迹的坐标元素增大，角度限值法的压缩效果反而不佳，压缩率接近80%。根据定义8可知，压缩比越大，压缩程度越不好，而其他3种算法的压缩率比走势基本一致。但是，从菱形组合线可以看出，所提的CVDD算法的压缩效果最佳。

图12 卡车组中不同算法的运行时间对比

图13 卡车组中不同算法的运行时间合并对比

2) 在卡车组实验中，通过图12可知，随着原始轨迹中坐标元素的数量增大，4种算法的处理速度也会受原始轨迹中线路的形态要素影响而波动。通过图13可知，角度限值法处理速度快，但通过图14可知，角度限制法的压缩率最大，压缩程度不佳，CVDD算法的压缩率最小，压缩程度最佳。

图14 卡车组中不同算法的压缩率对比

图15 科考组中不同算法的运行时间对比

3) 在科考组实验中，通过图15和图16可以看出，4种算法的压缩速度也随着科考线路的形态要素变化而波动。除D-P算法外，其他3种算法的执行时间都在130 ms以内。从图17可以看出，CVDD算法的压缩效率也是最佳的。

图16 科考组中不同算法的运行时间合并对比

图17 科考组中不同算法的压缩率对比

4.3 评价指标分析

矢量轨迹压缩算法评价指标可分为效率指标和精度指标。前者主要指压缩效率和执行效率即运行时间，后者包括如最大位移、位移之和、位移平均误差、位移标准差、面积偏差等多个方面。因此，将对CVDD算法进行不同的指标分析。

4.3.1 算法效率评价指标分析

根据实验结果显示，如图9和图10、图12和图13、图15和图16可知，随着原始坐标点的量不断增加，每组的执行时间在不断上升，前3种算法都是保持线性缓慢的增长，而 D-P算法的执行时间急剧上升。从图9和图12中的第四现象子图的y轴刻度可知，D-P的执行时间是107ms。由图10和图13可以看出，角度限值法执行时间较少，而垂距限值法和CVDD算法的执行时间稍微高一些，但3种算法的执行时间都在可控和可容忍时间范围内。垂距限值法和CVDD算法的执行时间走势基本一致，但从整体看来，CVDD算法比垂距限值法在执行时间上较为稳定。

在3组实验中，从原始坐标数与执行时间关系来看，角度限值法的处理速度最快，但通过图11、图14和图17可以看出，角度限值法的压缩效果最不佳，垂距限值法和CVDD算法的压缩效果最佳，D-P算法的压缩效果次之。通过对各种算法在3组实验中的运行时间和压缩率计算平均值，得出各种算法在3组实验中的平均执行时间和平均压缩率，具体如图18至图19所示。

图18 不同算法在相同实验中的平均运行时间对比

图19 不同算法在相同实验中的平均压缩率对比

从图18和图19可以看出，CVDD算法的平均执行时间基本上比其他几种算法快，平均压缩率也比其他几种算法优，且比垂距限值法的平均压缩率优3～7个百分点。因此，CVDD算法与其他几种算法对比具有较好的压缩效率和执行效率。

4.3.2 算法精度评价指标分析

通过算法效率评价指标分析初步得出，CVDD算法具有较好的压缩效率和执行效率。需要强调的是，压缩率是在压缩效果有效的范围内衡量，不能因为过度追求压缩率而导致压缩后线路失真。因此，需进一步对各算法进行精度上的评价指标分析。对3组真实轨迹数据集进一步实验取证，对每组轨迹数据集各随机选取部分路线继续实验，得出实验结果如表2所示。通过表2中数据进行求平均位移计算，得出垂距限值法与CVDD算法在3组实验中的平均位移如表3所示。

表3 垂距限值法与CVDD算法在3组实验中的平均位移

由表3可知，CVDD算法在3组实验中，位移平均误差分别是0.01 m，0.08 m和0.01 m，精确到厘米级别，而垂距限值法的位移平均误差分别是0.84 m，0.43 m和0.07 m，基本上只能精确到分米级别。因此，进一步证明CVDD算法的压缩效率和压缩效果要比垂距限值法优。

5 结语

在矢量轨迹数据处理中，为了获得有效的轨迹数据，提出了一种矢量轨迹有损压缩CVDD算法。该算法使用球面距离公式有效地避免了传统算法中通过平面欧式距离公式计算所带来的实际距离误差。将三元组进一步识别为密集点集与稀疏点集，不仅能有效地压缩弯道中的大量稠密节点，还能有效地避免破坏原始轨迹中的形态要素。使用余弦值替代角度值作为判断条件，能够有效地减少节点间空间上的计算成本，加快算法的处理速度。同时，使用边界垂距阈值(dmin，dmax)能够更加精准地判断是否压缩当前待处理的中间节点，并比传统算法中使用单一的垂距阈值d或θ更为灵活。最后，将该算法应用到3组真实的轨迹线路中进行实验测试。实验结果表明，无论从算法效率评价指标分析，还是从算法的精度评价指标进行对比分析，CVDD算法的执行时间和处理效果都优于其他几种传统的压缩算法。

CVDD算法是从原始轨迹的一端出发，逐步遍历连续的每一组三元组数据，其不仅可以处理离线的矢量数据，还能处理实时的在线矢量数据。考虑算法中使用的计算公式都可以延伸到多维空间中，CVDD算法还可扩展到多维空间的轨迹压缩中。