许惠，杨智应

（上海海事大学信息工程学院计算机系，上海201306）

基于高斯滤波的移动对象轨迹化简实时算法

许惠，杨智应

（上海海事大学信息工程学院计算机系，上海201306）

基于PLAZA和高斯图像滤波，研究了带有定位误差的移动对象轨迹化简算法。所设计的算法主要应用于移动终端设备，能够对定位设备采集到的移动对象原始轨迹数据进行简化，降低移动终端的通信代价和计算开销，提高轨迹数据的使用效率和价值。算法按照时间序列的处理思想，同时利用信号去噪的方法对原始的定位信号进行滤波，可以达到降低误差影响和减小数据冗余的效果。然后按照PLAZA算法的思想进行化简。实验结果证实该算法具有较好的化简率和较快的处理速度，实际应用表明该算法有较好实用价值。

移动对象；实时轨迹化简；定位误差；滤波

0 引言

随着汽车、轮船及手持设备等移动对象数量的增加，移动位置信息也随之飞速增长。这些位置信息作为一种无限的数据流通过无线网络发送到中央数据库中，大量对象频繁更新位置信息时，海量的数据将会以一种无法预测的高频率传送到中央处理器进行处理，这对于传统的数据库管理系统来说是无法处理的。因此，通常需要对其进行压缩处理。

移动对象轨迹化简问题作为移动对象数据库研究领域的重要分支之一，对于高效地管理和分析移动对象数据有着至关重要的影响。在实际应用中，由于定位系统存在定位误差，很多廉价的定位装置会在不利的环境产生不可忽视的误差。针对此问题本文基于PLAZA方法和高斯滤波提出一种实时移动轨迹化简方法（GPlaza），它的思想是针对具有较大误差的定位装置，首先对原始测量数据进行高斯滤波，以减小GPS定位误差的影响，然后构建合理的误差区域对后续的轨迹点进行过滤化简。

1 问题建模

1.1 移动对象轨迹模型

移动对象轨迹化简就是从组成曲线的点序集合O中抽取一个点序集合O′，用这个子集作为一个新的信息源，在规定的精度范围内，该子集从内容上尽可能地反映原子集O，而在数量上则尽可能地精简，即压缩比尽可能的小。进行矢量数据压缩的核心是在不扰乱拓扑关系的前提下，对原始采集数据进行合理删减[1]。

理论上，通常将移动对象O的轨迹表示为三维空间中的一条折线。三维空间中的两个维和空间相关，第三维是时间；即Oi={xi，yi，ti}。为了简化计算复杂性需要将三维空间的折线投影到二维空间平面上。

1.2 定位方法原理及误差分析

卫星导航接收机是通过接收卫星广播的星历信息，获取信号的传播时间从而解算接收机坐标[2]。在信号发送、传输和接收等环节存在着各种干扰和误差，如测量同步误差、多径传输和各种噪声干扰。从来源上来说误差可以分为四类：与卫星有关的误差、与信号传播有关的误差、与接收机有关的误差以及地球潮汐、负荷潮等造成的其他误差。而与信号传播有关的误差包括电离层折射误差、对流程折射误差及多径效应误差。GPS定位误差由以下公式近似表示[3]：

其中σp为GPS定位标准偏差，σUERE为伪距测量的标准偏差，GDOP为几何精度衰减因子（Geometric Dilution of Precision）。因此，对于一个特定地域来说，定位误差并不是固定的，可以看作符合标准正态分布。

2 相关工作

移动对象轨迹的化简方法主要使用线性推测，利用垂距阈值、角度限定和混合区域过滤三种思想进行化简。

垂距阈值算法通常使用线性预测为应用场景，通过引入最大偏离误差阈值对显著轨迹进行识别[4]。比较早也是目前最通用的算法是Douglas-Peucker算法[5]。随之产生了很多实时算法，如线性外推（LEx）算法和连接-保持推测算法（CDRM）等。

角度限定通过定义方向向量在一定误差范围的角度对移动对象方向误差进行限定，若方向偏差超过限定值则进行更新。线性分段化简方法（Piecewise Linear Approximation）是一个针对时间序列的有效压缩方法[6]。PLAZA通过分区角度（Zoing Angle）来判断轨迹是否保留，并较早用于以无限时间序列方式生成的数据流的压缩问题上，可以形式化地处理二维数据。NPLAZA结合移动对象的轨迹特点，将其拓展为三维坐标（二维空间和一维为时间）下的点的轨迹。如图1所示。

图1 NPLAZA算法示例图

混合区域过滤算法结合垂距和角度两个方面构造安全区域，根据待测点所处位置决定点的取舍。基于阈值的抽样算法（TPG）作为典型的区域过滤算法，通过给定的阈值和已知信息（包括过去轨迹点的位置、速度和方向等），构建下一个轨迹点的安全区域（SA），然后判断是否保存该轨迹点。

以上轨迹化简算法都是针对精确的数据所做的化简，而实际应用中，精确的定位设备往往比较昂贵，因此使用相比较少；而大部分使用的是廉价的定位装置，由此产生的带有较大误差的位置信息会在很大程度上影响化简算法结果的准确性和压缩率，因此产生了考虑定位误差的移动对象化简算法。参考文献[7]提出了一种基于MBR的实时轨迹化简算法，该算法通过一套针对标准最小边界矩形的分割/合并操作以及选择策略来对空间轨迹数据进行化简。参考文献[8]经过研究改进了MBR算法：采用最小包围扇形来近似化简其移动轨迹，提升了算法效率并减小了偏移误差。如图2所示。

图2 基于MBS的化简算法

3 方法提出

3.1 目前算法分析

对于无定位误差数据的实时轨迹方法已经有较好的研究，如上面提到的线性化简、TPG算法和NPLAZA算法等。其中PLAZA算法简化率和误差范围在相同复杂度的算法中已接近最优。而针对考虑定位误差的实时化简算法目前还较少。根据目前所知，有MBR和改进的MBS算法等，相比之下MBS在实际应用中有较好的效果。但是实际应用中MBS的化简率为50%左右，对于存在较大误差、速度较慢的移动对象，其化简结果不甚理想。

考虑到相邻移动对象轨迹点之间的相关性非常大，且定位误差是一种服从高斯分布的随机误差，即白噪声，由于高斯滤波对随机噪声有良好处理效果[9]，本文使用高斯滤波器对误差定位信号进行预处理，用于减小误差。虽然误差不可避免，但利用滤波处理后的数据可以有效减小误差的影响，对轨迹进行平滑。然后考虑NPLAZA算法对轨迹数据处理具有高效性和很好的处理结果，对数据运用NPLAZA算法进行化简和存储，具体方法如下。

首先，对象从发出定位信息开始，根据设定的滤波模板大小n，前n-1个点不做处理；从第n个更新点开始，每次更新时对之前的n个点进行高斯变换，结果作为新的第n/2个数据，然后判断是否更新。具体实现方法如下：对于已知的两个轨迹点Pi，Pj，先计算出其划分角度θ=θε（i，j），当下一时刻k的轨迹点Pk的位置信息到来时计算并且结合给定的距离误差阈值δ以及时间差k-j与时刻j处的瞬时速度vk计算出来的距离范围共同构建安全区域SA，若Pk在SA范围内则将轨迹点Pk忽略，并执行进一步缩小划分角度的范围；否则将Pk-1以及Pk作为新的起点。如图1所示。

算法描述如下：

输入：角度阈值ε、距离阈值δ以及原始序列O；

输出：简化序列S。

算法流程：

3.2 定位误差情况分类

由于定位误差的不确定性，例如随着接收装置精度或者所处环境的不同，接收装置定位的误差可能有很大变化：目前正常状态手持设备和车载系统的定位误差是10 m左右，而环境差异较大时可能是50 m甚至是几百米。借助基站定位对GPS定位的补充，会对定位产生一定的帮助，但并没有解决定位装置的误差对化简算法的影响。而误差的大小对算法化简的结果是不一样的，比如对于可认为是精确定位的点，若使用高斯滤波将影响数据的可靠性，而对于超出可以接受的误差进行滤波又会降低数据的精确度。因此本文使用一种对误差进行自适应判断的方法。首先对误差进行范围划分：确定一个阈值δ1使之作为精确定位数据和有误差数据的分界线。然后对精确定位数据的处理时利用简单的PLAZA算法进行化简，而对可处理的误差数据首先利用高斯滤波进行预处理，之后利用PLAZA算法（即GPlaza算法）进行化简。

4 实验分析及估计

4.1 算法性能分析

实验选取台式电脑作为测试硬件平台，具体配置为：Pentium（R）Dual-Core CPU E5500@2.80 GHz，内存为2 GB；软件环境为Windows 7操作系统和Eclipse开发环境。实验数据是从项目INFATI（INtelligent FArtTIlpasning）[10]得到。INFATI的位置数据信息是从2001年2月到3月期间，从9辆行驶在丹麦的汽车中采集得到的。为了更好地分析各个算法，本文定义了以下参数：

化简率：是指矢量数据压缩后的数据量与压缩前的数据量之比。

线段空间偏移：某一时刻实际简化结果与定位结果之间的距离与设置误差阈值的比值。

相对误差：是指压缩后新生成的线段与被压缩的曲线在空间的偏移量，使用实际简化结果与定位结果之间的距离与实际相邻两个定位结果之间的距离比值。

化简率是数据压缩算法的数量指标，追求较小的压缩比是进行数据压缩算法设计的根本出发点，线段空间偏移和相对误差控制是数据压缩的质量指标（越小越好），一个好的压缩算法应该是结合实际需求，对以上3个指标进行最大限度的平衡。

首先对上文中算法的时间复杂度和空间复杂度进行比较，如表1所示，其中n为轨迹点的数量，m为给定的存储空间的大小。结果显示，GPlaza算法和大多数实时算法一样，可以在线性时间内结束。

表1 各个算法的时间复杂度与空间复杂度

接下来利用上述实验数据和实验平台，使用Java编程语言来实现算法，从简化率、线段空间偏移、测评角度以及运行时间四个方面以量化类的指标来比较分析这7种算法的性能特点，其结果如图3所示。从图中可以看出，GPlaza算法的化简率在比较的算法中有很大的优势；但由于GPlaza算法的滤波特性，使得其空间偏移较大，而对于有较大定位误差的数据，较大的相对误差不一定是坏事；而GPlaza算法拥有相对较好的相对误差和较快的处理速度。因此，综合来说，GPlaza算法有着较好的综合性能。

4.2 实际应用化简结果分析

图3 算法性能综合比较

实际应用选取HTC5088手机为测试平台，具体配置如下：CPU型号：Spreadtrum（展讯）Shark（4核Cortex-A7架构）；CPU频率：1 024 MHz；RAM容量：512 MB；操作系统：Android OS 4.1.2。Android应用开发中利用百度地图Android SDK v3.2.0应用程序开发包进行定位和显示。

本文记录了三次实验的记录，应用场景分别是：（1）行走于上海海事大学内的行人（平均速度是7~10 km/s）；（2）行进于上海市临港区的公交车（平均速度为50km/s）；（3）运行中的上海地铁16号线（平均速度为80~100 km/s）。实验记录如表2。

表2 GPlaza算法模拟结果

由于正常情况下GPS系统的误差是10 m，因此本文采用15 m作为精确定位数据和有误差数据的分界线。本次实验选取的定位采样频率为10 s，误差阈值设置为20 m或30 m不等，图4显示的是上述实验结果的轨迹结果（其中细实线段为原始轨迹，粗实折线为简化后的轨迹）。实验结果表明：本文使用的算法有较好的化简率，从图中可以看出简化后的轨迹与原始轨迹重合较好，线段空间偏移较小。综合来看，对于高速运动的对象，GPlaza算法化简压缩率较好，而低速运动的对象压缩率稍差，而线段空间偏移都较小。需要说明的是，由于地铁通常运行于地下，获取不到卫星定位信息，只能采用WiFi或基站定位，从而使定位偏差极度扩大，继而严重影响轨迹精度。

图4 模拟GPlaza算法化简结果

5 总结

移动对象轨迹有其独特的方面，比如数据的多维性、信号的连续和冗余性、测量数据存在误差等。针对这些特点，本文将信号滤波的思想运用到移动对象数据化简算法上，结合时间序列处理的方法，提出了基于高斯滤波的角度分区线性化简算法。由于高斯滤波在去噪方面的良好表现，该算法在处理针对GPS定位误差的定位数据时显现出很大的优势。在实际应用中，加上合适的滤波模板和阈值设定，得到了较好的应用。实验表明，该算法有高效的轨迹化简性能，并且得到的简化轨迹与原始轨迹之间的误差稳定可控。由于在某些环境（室内或地下），不能获得定位信息，因此会导致轨迹信息失准，因此如何对无效轨迹进行判定和修复，如何利用较少的简化轨迹更好地重建和检索历史轨迹，以及如何更好地预测未来轨迹将是以后的工作重点。

[1]米学军，盛广铭，张婧，等.GIS中面积偏差控制下的矢量数据压缩算法[J].地理学报，2012（10）：1236-1240.

[2]赵琳，丁继成，马雪飞.卫星导航原理与应用[M].西安：西北工业大学出版社，2011.

[3]袁建平，罗建军，岳晓奎.卫星导航原理与应用[M].北京：宇航出版社，2003.

[4]张达夫，张昕明.基于时空特性的GPS轨迹数据压缩算法[J].交通信息与安全，2013，6（31）：6-9.

[5]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.

[6]SOROUSH E，WU K，PEI J.Fast and quality-guaranteeddata streaming in resource-constrained sensor networks[C]. In Proceedings of the 9th ACM International Symposium on Mobile ad Hoc Networking and Computing，ACM，2008：391-400.

[7]GUANGWEN L，MASAYUKI I，KAORU S.An online method for trajectory simplification under uncertainty of GPS[J].情報处理学会論文誌.データベース，2013，6（3）：40-49.

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

[9]李惠芬，蒋向前，李柱.高斯滤波稳健性能的研究与改进[J].仪器仪表学报，2004，25（5）：633-637.

[10]JENSEN C S，LAHRMANN H，PAKALNIS S，et al.The INFATI data[M].arXiv preprint cs/0410001，2004.

Real-time trajectory sim p lification algorithm of moving object based on Gauss filtering

Xu Hui，Yang Zhiying
（College of Information and Engineering，Shanghai Maritime University，Shanghai 201306，China）

Based on PLAZA and Gauss image filtering，the research is about simplification algorithm of moving object trajectories with positioning error.The algorithm，which is mainly applied to the mobile terminal，is able to simplify the original trajectory of moving object，and reduce the communication and computation cost of mobile terminal.Thus the algorithm can improve the efficiency and value of track data.According to the thought of time series method and signal doeoising，the algorithm first process the original position data with gauss filter，which can decrease the influence of location error.And then simplify the trajectory according to the theory of PLAZA algorithm.The experimental results confirmed that the algorithm has better reduction rate and faster processing speed，the practical application show that this algorithm has better use value in real life.

moving object；real-time trajectory simplification；location error；filtering

TP301

A

1674-7720（2015）13-0012-05

2015-03-04）

许惠（1991-），男，硕士，主要研究方向：移动对象数据库。

杨智应（1964-），男，博士，教授，主要研究方向：算法与复杂性、移动计算、分布式计算与软件工程。