基于手机传感器的车辆轨迹实时在线压缩方法

赵东保 ，冯林林 ，邓 悦 ，曹连海

（华北水利水电大学测绘与地理信息学院, 河南 郑州 450046）

伴随着基于位置的服务（location based service,LBS）[1]等现代技术的快速发展，产生了巨量用于刻画移动对象运动的时空轨迹数据，并被广泛应用于智能交通系统的分析决策.由于庞大的数据规模对于时空轨迹的存储、管理和分析带来了严峻挑战，因此，时空轨迹的数据压缩就成为了轨迹大数据研究领域的一个重要问题.

时空轨迹的数据压缩方法[2]主要分为基于特征点提取的压缩[3-6]、基于路网的压缩[7-9]和基于语义的压缩[10-11]等类别.基于特征点提取的压缩方法是一类通用的轨迹压缩方法，对数据的限制要求少.基于路网的压缩方法压缩率更低，但是被约束在道路网中，需要事先将轨迹数据进行较为复杂耗时的地图匹配.基于语义的压缩多是将时空轨迹转变为文本语义信息，仅在某些场景中应用.轨迹压缩还可以分为离线压缩和在线压缩两类，离线压缩是指整个轨迹数据全部读取完毕才进行压缩，一般都是利用轨迹数据的全局特征进行静态处理.例如：经典的DP（douglas-peucker）算法[3]就是根据中间轨迹点到全局首末轨迹点连线的垂直偏差距离提取轨迹特征点；TD-TR （top-down time radio）压缩算法[4]也是一种代表性离线压缩算法，其思路与DP算法相似，但采用时间同步欧式距离（synchronous Euclidean distance，SED）阈值代替垂直偏差距离阈值来更好地顾及轨迹的时空特性.在线压缩算法一般是基于轨迹数据的局部特征进行动态处理，以实现对轨迹数据的实时压缩，方便网络传输.代表性方法如滑动窗口算法[5]、标准开放窗口（normal opening window，NOPW）算法等[4,6]，其基本思路都是从动态改变的窗口中提取特征点，以实现在线压缩.轨迹压缩过程类似于曲线化简，因此制图综合领域的经典算法[12]也具有重要参考价值，但制图综合关注的是地理要素空间特征的概括与抽象，而轨迹压缩关注的是轨迹时空特征的采集、压缩、存储和传输等.

尽管已经存在了相当数量的时空轨迹压缩方法，然而采集轨迹数据的移动设备（如智能手机等）都有存储空间和用电量的限制，在智能手机等移动设备上使用这些压缩算法无疑会面临较高耗电量和占用较大存储空间的问题.由于智能手机设备不止具有GPS等定位传感器，还具有其他各类传感器，近些年来，一些学者利用手机传感器在用户活动模式识别方面开展了较多的研究工作.例如，文献[13-17]就系统讨论了如何利用手机传感器数据识别用户的日常运动模式，如坐下、静止、步行、跑步和上下楼梯等；文献[18-20]则研究了基于手机传感器数据识别用户的出行模式，诸如骑行、公交车、出租车、火车、地铁和轮渡等；文献[21-23]则研究了利用手机传感器识别车辆的运动模式，如急转弯、急刹车、急变道等危险驾驶行为.文献[24]对上述有关研究进行了总结归纳，对手机传感器在用户活动模式识别领域上取得的进展进行了全面综述.

虽然在轨迹压缩与基于手机传感器的用户活动模式识别领域都取得了重要进展，但是鲜有研究工作将二者相互结合，并根据双方研究特点，综合解决轨迹压缩问题.为此，本文通过智能手机内部多个低能耗传感器（如线性加速度传感器等）的相互配合作用来识别用户的运动状态变化，提出一种基于手机传感器识别车辆运动模式的车辆轨迹数据压缩算法，只有当运动状态发生改变时才采集该时刻下的轨迹特征点坐标，以便更好地节省手机存储空间，降低能耗和提高计算效率.

1 算法思路

轨迹压缩的核心目标是提取轨迹特征点，并去除冗余点.已有压缩算法都是先有原始轨迹，再从中提取特征点.但是，如果能够根据车辆的运动行为模式在轨迹的采集过程中识别出轨迹特征点，就可以直接略过冗余点，即可实现轨迹压缩.以图1为例，蓝色点、红色点和黑色点分别代表着本次车辆出行的起止点（见①、⑩处）、变速点（见②、④、⑦、⑨处）和转弯点（见③、⑤、⑥、⑧处）这些点显然都是需要采集的轨迹特征点，而白色点则是无须采集的轨迹冗余点.为此，可以借助智能手机的多个传感器完成对车辆运动行为模式的识别.本文算法的核心思想就是通过监测智能手机中低能耗的线性加速度传感器和方向传感器的数据变化来共同实时判断车辆运动行为模式是否发生变化，运动行为模式包含直线行驶、左右转弯、掉头、启动、制动、变速等，若车辆运动行为模式变化则使用GPS传感器记录当前点坐标，若车辆运动状态处于平稳不变时，则不采样，从而减少定位请求，以此完成省内存、低能耗的实时轨迹特征点采集工作，达到在线轨迹压缩的目的.

图1 轨迹特征点采集示意Fig.1 Collection of trajectory feature points

2 利用手机传感器识别车辆运动行为模式及轨迹特征点采集

为了尽可能地降低能耗，本文只借助线性加速度传感器和方向传感器识别车辆的运动行为模式.线性加速度计输出的是手机X、Y、Z三轴（如图2所示）的加速度值，且除去了重力加速度在3个轴上的分量.方向传感器的数据分别为方位角、俯仰角和翻滚角，其中方位角为手机绕Z轴旋转时，Y轴正方向与地磁场北极方向的夹角；俯仰角为手机绕X轴旋转时，Y轴正方向与水平方向的夹角；翻滚角为手机绕Y轴旋转时，X轴正方向与水平方向的夹角.在传感器数据采样过程中需保持手机自身姿态固定不变，但对初始姿态不做限制，可以任意摆放.在获取不同运动行为模式的传感器数据后，通过对数据的分析来找到相应运动模式下传感器的数据变化规律，以此作为运动模式识别的判断指标，并采集相应轨迹特征点.

图2 手机三轴坐标系Fig.2 Three-axis coordinate system of mobile phone

2.1 基于变速模式识别采集轨迹特征点

变速模式识别主要识别车辆的启动制动行为及车辆行驶过程中的急加减速行为，图3为手机线性加速度计在车辆启动和制动时各轴的数据变化情况.可以看出，车辆静止、加速启动、正常行驶和制动停车过程中，线性加速度值的变化趋势区分明显.在车辆静止候车状态时，三轴加速度围绕速度0上下有规律波动；当车辆加速启动时，Y轴加速度数据从0向正值快速变大，后加速结束又趋于0附近；当车辆正常匀速行驶时，三轴加速度围绕0值上下波动且幅度大于车辆静止时；当车辆制动停车时，Y轴加速度数据从0值附近向负值快速变大，

图3 车辆启动、制动时线性加速度计数据变化趋势Fig.3 Changes in linear accelerometer data during vehicle starting and breaking

变速特征点的识别方法：车辆的加减速行为反应在加速度序列的增减趋势变化上，那么加速度的时间数据序列就不是围绕某一值上下波动的平稳状态而是值不断上升或下降的非平稳状态，本文采用M-K （manner-Kendall）非参数趋势检验法[25]来识别加速度时间序列的变化趋势，该方法不需要样本数据遵循一定分布且不受少数异常值影响，故在加速度序列的趋势判断上具有较高的准确率.

设加速度时间序列含有n个数据，并记录为{x1,x2,···,xn}，是独立、随机同变量分布样本，对于所有的xi,xj，i,j≤n且i≠j，计算统计量为

式中： s g n(·) 为符号函数，

当n≥10 时（本文n=40 ），统计量S近似服从正态分布，其均值为0，方差为

构造标准正态分布统计量为

对U进行双边检验，在给定的置信水平 α 上，若|U|≥,则原假设是不可接受的，其中，为置信区间值.在 α 置信水平上，加速度时间序列存在明显的上升或下降趋势.当U＞0时，则为上升趋势，为车辆的加速运动，反之则为车辆的减速运动；若U的绝对值分别大于或等于 1.28、1.64 和 2.32，表示该样本通过置信度分别为 90%、95%以及99%的显著性检验水平，为确保对变速运动模式识别的敏感性，本文采用置信度为90%时的U值检验，即 |U|≥1.28.由于该阈值是对加速度值相对变化趋势的分析，为统计意义的参数，而非绝对量的加速度值，这有助于避免测量精度的影响，独立于手机型号.

2.2 基于转向模式识别采集轨迹特征点

车辆的转向模式识别主要是区分直线行驶和转弯行驶，当判断处于转弯行驶时则需要采集转向点坐标，当判断处于直线行驶则仅需要采集变速点即可.如图4所示为车辆行驶过程中手机方向传感器在发生不同转向行为时各个轴的数据变化情况.可以看出：车辆在转向时，俯仰角和翻滚角均保持平稳未发生明显趋势变化，而方位角则发生了剧烈的上升和下降变化，在车辆右转时，方位角逐渐增大，约为90°，反之左转时则逐渐减小，也约为90°.

图4 车辆转向行驶时方向传感器三轴数据变化Fig.4 Changes in three-axis data of direction sensor during vehicle turning

同时从图4（a）和4（b）可以看出：当车辆在幅度较大、距离较短的转弯时用时较短，且方位角曲线斜率较大，相应的车辆左转或掉头亦是如此；而车辆在幅度较小、但距离较长的缓慢转弯时用时较长，且方位角曲线斜率较小.此外，由于方向传感器中方位角的输出范围为 0～360°，会存在如图4（c）、图4（d）所示的方位角数据突变情况，多数情况下发生在车辆的转向和掉头行为中，有时也发生在车辆的直线行驶中（行驶方向正好为0或360°）.为此，在方向传感器数据的处理部分也需要考虑该特殊情况.总体而言，方向传感器的方位角数据所反映出的变化特征对转向行为具有良好的识别性.

转向特征点识别方法：本文将车辆转向行为分为左右转弯、掉头等幅度较大的短距离转弯和转向幅度较小的长距离转弯.通常一个左右转弯幅度大概在 80°～120°，当转向角度在 40°～60° 时，车辆大致位于道路的交叉点位置，故本文中当累计转向角累计到40° 时才采集一个转向特征点，以避免冗余采集.但对于小幅度的长距离转弯，若等到累计到40° 再采样特征点，此时车辆可能已经行驶了较长距离，故通过设置采样时间间隔阈值T来控制在累计转向角小于40° 的情况下的转向特征点采样.以图5为例介绍本算法转向特征点具体采样过程.图中：φ为方位角；t为采样时刻.

根据方位角φ的变化幅度及曲线变化率，假设图5中的AC、EF和HI段对应轨迹的直线段，CE、FH段对应轨迹的转向段，且CE段为大幅度短距离转弯，FH段为小幅度长距离转弯.定义锚点和浮动点，锚点为特征点，浮动点为当前时刻的采样点.初始时设数据采样序列第1点A为锚点(tmd，φmd)，序列 第 2点为浮动 点(tfd，φfd)， 其中： φmd、 φfd分别为锚点、浮动点的方位角；tmd、tfd分别为锚点、 浮动点所对应的采样时刻.累计转向角 θ 初值为 0.

当前转向角为

式中：φmd,···,φfd表示从锚点到浮动点的各数据点的方位角.

首先， 采用式（5）判断车辆行驶状态，当θ1≤ 3°时，认为车辆为直线行驶状态（如AC段），此过程不采样转向点，若该直线部分存在变速点（假如点B），则采样该坐标并将锚点A移动到当前点B，后继续采样新时刻的方位角数据；当θ1＞3°时，车辆视为转向行驶（如CE段），采样该转向点坐标并将锚点B移动到点C，然后，采用式（6）计算累计转向角，

当|θ |≥ 40°，则采集相应坐标（如点D），并令θ=0，后将锚点C移动到D点，同理，假设图1中点E为下一个 θ 到达 40° 的转向特征点.EF段判断仍采用与AC段相同的方法，假设识别出转向点F；在FH段，设：

当 |θ |＜ 40°，但 ΔT=T时，则采集该坐标（如点G、H），阈值T保证了长距离缓慢转弯的轨迹精度.

3 本文轨迹实时在线压缩算法步骤

本算法按照20 Hz采样频率，即采样间隔为0.05 s对手机内置方向传感器和线性加速度计进行数据采集和分析，以实时在线提取特征点，实现轨迹压缩.

设P为传感器的数据集，P={Pi}， 其中，Pi(t,φ,z)为 第i次采样的数据点，其中，z为三轴合线性加速度.初始时，令锚点Pstart=P1，浮动点Pcur=P2.设定T为5、10 s等，以初始时刻数据点的方位角为计算起点，累计转向角则步骤如下：

步 骤 1当φfd>φmax时 ， 令φmax=φfd； 当φfd＜φmin时 ，令φmin=φfd； 否则φmax、φmin不变.

步骤2采用式（4）、（5）分别计算正态统计变量U和 θ1，并分为两种情况.

情况 1当θ1≤ 3° 时，视为直线行驶，后根据U值继续判断：

1）若 |U|＜1.28 时，车辆处于匀速直线行驶或静止不动状态，则保持锚点Pstart不动，并继续采样新的传感器数据点Pcur，回到步骤1.

2）若 |U|≥ 1.28 时，车辆发生变速行为，当 ΔT≥T，则采样当前坐标点，并移动锚点Pstart到 当前点Pcur，令 φmax=φfd，φmin=φfd，后继续采样新的传感器数据点，重回步骤1.

情况 2当θ1＞3° 时，视为转向行驶，则采样该转向点坐标，并移动锚点Pstart到 当前点Pcur，且令φ=0， φmax=φfd，φmin= φfd；后采用式（6）计算 θ ，当|θ|≥ 40°时采样该点坐标，若在 ΔT=T期间始终未出现 |θ |≥ 40°的转向点，则在该时间段结束时也采集当前点坐标，并以相同方式移动锚点到浮动点处，且令 φ =0 ， φmax=φfd，φmin= φfd；重回步骤1.

重复循环上述步骤直到数据采集完毕.

4 算法性能评价标准

轨迹压缩算法的性能可从空间距离偏差、时空距离偏差、压缩率、实时性、压缩耗时等指标进行综合评价，各指标含义如下：

1）空间距离偏差.令P={P1,P2,···,Pn} 为按固定采样间隔采集的原始轨迹，L={L1,L2,···,Lk} 为压缩后保留的轨迹特征点，原始轨迹点的坐标表示为(xPi,yPi)，i=1,2,···,n，压缩后轨迹点的坐标表示为(xLl,yLl)，l=1,2,···,k，将原始轨迹点垂直投影到相应的化简线段上，如图6（a）中，P3的垂直投影点为Q3，将原始轨迹中任意点Pi与其对应点Qi的偏差距离记为Di，则该偏差距离之和的平均值即为空间距离平均偏差（average euclidean distance error，AEDE）.

图6 压缩精度指标的计算Fig.6 Calculation of compression accuracy indexes

2）时空距离偏差.时空距离偏差不仅考虑了轨迹点的位置而且还加入了时间属性，如图6（b）所示，P3的对应点仍是Q3，但该对应点是对时间信息进行线性插值得到的.在图6（b）的原始轨迹中，根据从起始点到任意点Pi所经历的时间与总的时间之比，再在相应的化简线段上进行线性插值即可得到Pi的对应点Qi，根据二者的偏差距离就可得到时空距离偏差，继而得到时空距离平均偏差（average synchronized euclidean distance error, ASEDE）.

3）压缩率R.压缩后保留轨迹特征点数k与原始轨迹点总数n的比值，表示为

4）实时性.实时性是指采集获取轨迹点后，需要多长时间方能确定该点是否是特征点.

5）压缩耗时.在规定的压缩率下，完成对一条轨迹的压缩所消耗的时间.

一般而言，很难有一种压缩算法在所有性能指标上全部占优，需要结合应用场景进行选择.当看重压缩精度指标时，通常离线压缩算法压缩精度最好，当看重实时性时，则可采用在线压缩算法.

5 实验验证与分析

5.1 实验环境

本次实验采用4种不同型号的智能手机（MI 8、MI 8 Lite、HONOR 20 和 HUAWEI P20）分别采集4种路况下的轨迹数据.手机均放置于车体内部，且对初始姿态不做要求，但应保证行驶过程中保持稳定.首先对3种传感器耗电情况进行实际测试（以MI 8手机为例）.算法中线性加速度传感器和方向传感器的采样间隔为 0.05 s，GPS 传感器为 1.00 s，采用消耗电池的容量值（mA·h）代表传感器的耗电量，实测结果如图7（a）所示.线性加速度传感器、方向传感器和GPS定位传感器每小时耗电约为1、2 mA·h和40 mA·h，GPS传感器的耗电量远远高于其他两种传感器.图7（b）是采用百度地图API的定位功能实验测得的在不同采样间隔下手机耗电量情况，随着定位请求采样间隔的增加，手机耗电量稳步降低.可见合理增大采样间隔，减少请求定位次数有助于一定程度上降低手机的能耗.

图7 手机内置传感器耗电情况Fig.7 Power consumption of built-in sensors in mobile phones

5.2 轨迹压缩结果

根据不同路况属性分成4种类型进行算法测试：1）高速道路，道路平滑顺直，路况好，车辆行驶速度快；2）山区道路，道路盘绕山体，蜿蜒曲折坡陡弯急；3）城郊道路，路况稍显复杂，存在个别颠簸路段，行驶速度较快；4）市区道路，车辆时速较慢，各种交通信号灯和交通堵塞，走走停停.如图8所示，图中包含了 4 种路况下的原始轨迹以及在阈值T=60 s时本文压缩算法提取的轨迹特征点.

图8 4种不同类型的实测轨迹路线图及其压缩结果Fig.8 Compression results of four different types of experimental vehicle trajectories

5.3 结果分析与评价

本文算法是基于特征点识别的轨迹压缩算法，将其与同类型代表性轨迹压缩算法进行全面对比.

5.3.1 与固定间隔采样的实验对比

采用本文算法对4种路况下的轨迹进行压缩，其时间间隔阈值T分别设置为 5、10、15、20 s.在保证相同压缩率的情况下，与固定时间间隔采样进行AEDE和ASEDE的精度对比.为保证压缩率一致，可根据图9（a）中本文算法在不同路况下的压缩率换算出固定时间间隔采样所对应的阈值.如在本文算法的T值分别为 5、10、15、20 s时，山区路段对应的固定T值应为 4、8、11、15 s，高速路段对应的则为 6、10、15、20 s，其他路况可同理计算得出.

实验结果如图9（b）～（e）所示，可以看出随着时间间隔阈值的增大，不同路段的压缩精度愈来愈差，而在这种趋势下，本文算法的时空距离偏差和空间距离偏差始终小于固定间隔采样的相应值，且随着采样间隔的增大，这种优势有增大趋势.此外，从图9（a）中可以看出在同样的采样时间间隔阈值下，本文算法对山区路段、城郊和市区路段、高速路段压缩率由高到低，表明了本文算法对不同路况具有一定程度的适应性.由于本文算法借助手机传感器可以实时识别并采集轨迹中的关键转向点和变速点，保证了轨迹的空间几何形态和时间特征，因此在相同压缩率下，本文算法在时间精度和空间精度都优于固定间隔采样.

图9 本文算法与固定间隔采样的压缩精度对比Fig.9 Comparison of compression accuracy between proposed algorithm and fixed interval sampling

5.3.2 与代表性算法的实验对比

将本文算法进一步和代表性在线压缩NOPW算法及离线压缩DP算法、TD-TR算法进行实验对比，以路况最复杂的山区路段为例，结果如图10所示.

从图10（a）和图10（b）中可以得出：本文算法的时空压缩精度强于DP算法，但弱于TD-TR算法和NOPW算法，就平均而言，本算法的时空距离平均偏差比在线NOPW算法多约0.4 m；本文算法的空间压缩精度弱于其他3种算法，在压缩率最低时，其空间距离平均偏差比在线NOPW算法多约1.4 m，平均多出0.6 m.这表明本文算法在压缩精度方面不如代表性算法，但相比手机GPS传感器的定位误差而言，总体差值也较小.

首先是压缩耗时少，图10（c）是各算法压缩耗时对比，可以看出压缩率在25%以下，本文算法的压缩总耗时都最少，且随着压缩率减小而逐步降低，比DP算法减少约30%的计算耗时.而NOPW算法的耗时却随着压缩率的降低逐渐增大，相比其它算法其耗时明显偏大，通常轨迹压缩的压缩率都是相当低的，这影响了其适用范围和普适性.

其次是实时性强，本文算法相较于DP、TD-TR等离线压缩算法可以实时在线地压缩轨迹，根据加速度传感器和方向传感器的数据处理，可以在当前秒就判定该轨迹点是否是特征点.NOPW尽管是在线压缩算法，但实时性有延迟.图10（d）是针对每秒采样一次的山区路段，NOPW算法在不同压缩率下判断得出读入的轨迹点是否是特征点的平均延迟时间，可以看出其在5%压缩率下，甚至要延迟十几秒方能确定特征点，这在某些智能交通应用场景是重要不足.

图10 本文算法与代表性算法的压缩实验对比Fig.10 Comparison of compression experiments between proposed algorithm and representative algorithms

最后是GPS请求定位次数少，上述各代表性轨迹压缩算法需采集所有原始轨迹点方能完成轨迹压缩，请求定位次数就是所有轨迹点个数.而本文算法只对轨迹的关键点才请求定位并进行坐标采集，GPS的请求定位次数仅仅只是保留下来的特征点数目.当需要对大规模浮动车（如出租车等）轨迹进行特征点采集并实时上传到服务器时，本文算法由于实时性强，无延迟且请求次数最少，显然有助于减弱对GPS传感器的使用强度和减少数据的网络传输量，有利于定位设备的节能.

6 结 论

本文通过监测分析手机中低能耗的线性加速度传感器和方向传感器的数据变化，来识别车辆的运动行为模式，并据此请求采集行驶过程中的轨迹特征点，从而实现车辆轨迹的实时在线压缩.将本文算法与代表性基于特征点提取的轨迹压缩算法进行实验对比，得出以下结论：本文算法在时空距离偏差上全面优于固定时间间隔采样法和DP算法，但弱于TD-DR算法和NOPW算法.尽管在压缩精度上稍欠不足，但却具有综合优势.首先，本文算法是在线压缩算法，实时性强，无延迟，压缩耗时少，对手机存储空间的占用少；其次，本文算法仅在关键特征点处才请求定位，减少了数据的网络传输量和对流量的消耗，减弱了对GPS传感器的使用强度，有助于一定程度上降低手机能耗；最后，本文算法对不同路况具有一定程度的适应性且算法所用的时间间隔阈值也便于普通用户理解.总之，本文算法是一个兼顾了多项指标的车辆轨迹实时在线压缩算法，适用于面向大众用户的轨迹类场景应用.