基于最小边界扇形的移动对象轨迹实时化简算法的进一步研究

张家碧，杨智应（上海海事大学信息工程学院，上海 201306）

基于最小边界扇形的移动对象轨迹实时化简算法的进一步研究

张家碧，杨智应
（上海海事大学信息工程学院，上海 201306）

随着各种便携式个人通信设备增加，带有GPS定位功能的设备在日常生活中日渐普及。在方便人们日常生活的同时也带来海量数据的管理等问题。提出一种新的基于最小边界扇形的移动对象实时化简算法，提出了关键点（key point）的概念。在具有基本定位功能的设备上，更好地获得接近原始轨迹的简化轨迹，同时基本保持原有的通信代价和计算开销。还提出一种新的基于区域面积的误差度量方式。实验结果证实该算法有较好的化简率和较快的处理速度，得到的化简结果更加接近实际。

移动对象；实时化简；误差

0　引言

随着社会的进步和科技的发展，内置定位功能的设备在人们的生活中得到了普及，人们在使用这些设备的同时产生的海量数据通过无线网络传输到了中央数据库［1］，针对这些按时间标记的位置信息的传输，处理，存储都成了棘手的问题。在现实场景中，常常对各类移动设备产生的数据进行压缩处理。其中，移动对象轨迹化简问题作为近年来备受关注的问题，对有效减少服务器负载和降低通讯代价有着至关重要的影响。简单地说，移动对象简化问题，就是针对原始轨迹，重新计算出一条新的尽量包含少的轨迹点的轨迹，并尽可能接近原始轨迹。

实际上原始轨迹数据在被压缩，降低开销的同时也损失了较多的轨迹特征。这在一些场景中是不利的。例如通过对船舶轨迹的分析，可发掘出海洋交通流的特征与规律，为海上交通管理部门提供依据［2］。过多的数据采集可能造成数据冗余等问题，加大了数据处理的难度；过多的轨迹点简化则会损失较多的轨迹特征，不利于数据分析。针对类似问题本文在基于最小边界扇形（MBS）的移动对象实时化简算法的基础上提出了一种新的实时的移动对象轨迹化简算法，力求在少量增加通信代价和计算开销的前提下，适当增加较能体现轨迹原本特征的轨迹点。它在继承基于最小边界扇形的移动对象轨迹实时化简算法简单，高效，对终端设备要求低等优秀特性的同时又能更好的体现出轨迹的特征。

1　相关工作

王欣然等人根据GPS系统中存在定位误差的实际情况，针对只有基本定位功能的GPS设备，提出了一种基于最小边界矩形（MBS）的实时轨迹化简算法。移动对象在本质上是随时间而变化的集合实体［3］。下面首先给出移动对象轨迹化简问题中所涉及到的一些定义。

定义1原始序列。在给定的欧氏空间中，原始轨迹序列O=｛o1，o2，…，on｝是有序的离散轨迹点Si=（p＜x，y＞，t）所构成的序列，其中（1≤i≤n）。

定义2 简化序列。简化序列S=｛s1，s2，…，sm｝可理解为：在欧氏空间中，原始序列简化后所形成的序列，其中m≤n。

1.1GPS误差分析

GPS测量是通过地面接收设备接收卫星传送来的信息，对于GPS卫星、卫星信号传播过程和地面接收设备都会对GPS测量产生误差。主要误差来源可分为：与GPS卫星有关的误差；与信号传播有关的误差；与接收设备有关的误差。其中第一类主要包括星历误差，星钟误差，地球自转效应误差等。这类误差通过轨道松弛法，差分法可以去除。最后一类误差则是接收机的固有误差，这类误差是无法消除的。文中所讨论的误差主要是这里提到的第二类误差，指的是不能由用户测量或由校正模型来计算的传播延时误差［4］。GPS定位误差由以下公式近似表示［5］：

其中σp为GPS定位误差的标准偏差，σUERE为伪距测量误差的标准偏差，GDOP为几何精度衰减因子。

1.2轨迹化简算法的研究

轨迹化简算法的研究主要的思路主要有三种：轨道压缩、推算定位和区域过滤［6］。轨道压缩方法的应用场景是早期的轨迹离线应用场景，通过引入线性化简算法和压缩算法等方法对历史轨迹数据进行化简，这类方法的压缩率较高，但压缩效率较低，不利于轨道数据的远程实时压缩［7］。基于推算定位思想的轨迹化简算法引入最大偏离误差阈值对未来位置进行预测［8］，简单的说这种算法的思路能表述为：无论何时只要对象的实际位置与其数据库位置的距离超过一个给定的阈值th，就执行一次数据库的更新。这类方法一般用于联机简化。基于区域过滤的方法一般通过给定的阈值和相关信息（如过去某些时刻的轨迹点位置，移动对象的速度方向等），构建安全区域（SA），再根据实际的轨迹点是否位于该区域内做出是否保留该轨迹点的判定。这种方法的缺点是缺乏对方向变化累计所带来的简化误差，且部分采取速度和方向绝对阈值的优化思路在处理不稳定参数时化简率难以提高［9］。

以上所提到的轨迹化简算法大多针对的是较为精准的移动设备，它们大多不仅能提供基本的位置信息还能提供移动对象的速度，方向等信息。在实际应用中这类设备往往比较昂贵。大多情景下的移动设备只有基本的定位功能（如车载终端，移动手机等）。在目前的研究中针对这种情况的算法较少。文献［10］首先提出了一种基于最小边界矩形的实时轨迹化简方法 （以下简称为MBR算法）并提出了一种基于封闭面积的误差度量方式来解决此类问题。在MBR算法中，首先构造包含相同轨迹点个数的最小包围矩形集合，将得到最小矩形面积与给定的标准面积大小的比较，最后通过针对最小边界矩形的分割/合并操作对原始轨迹数据进行简化。该算法提供了一种设计轨迹化简算法的新思路，即利用标准图形去逐段匹配整个轨迹［4］。但MBR算法本身也存在掩盖了较多原始轨迹特征，算法较复杂等问题。

1.3MBS

MBS算法沿着MBR算法所提出的使用标准图形去匹配每段轨迹的思路，使用最小包围扇形来近似化简移动对象轨迹。其化简的大概过程为：在每次接收到新的轨迹点信息时，重新构造最小边界新扇形。最后通过判断原始点到其估计点的距离是否超过用户所设定的误差阈值来决定是否向服务器更新移动对象的位置信息。其中原始点到其估计点间的距离是通过基于等极径的误差度量方式完成的。将所构造的扇形置于极坐标系环境中，以其余原始轨迹点到扇形顶点（同时也是极点）的距离的最大值为半径，极点为圆心做圆弧，圆弧与扇形角平分线的交点即为该原始轨迹点的估计点。如图1所示是某最小边界扇形中的原始轨迹点与其对应的估计点。其中o1，…，o5表示原始轨迹点，ole表示扇形的角平分线。在图1中s3即o3的估计点。MBS算法对终端的要求低，与MBR算法比较保留了移动的轨迹运动特征，但仍不能令人满意，且MBS算法对于移动速度较慢或存有较大误差的移动对象其化简结果不甚理想。MBS算法对原始数据中的每个轨迹点数据只浏览一次，其时间复杂度是线性的，空间复杂度根据构造扇形的方法不同而有所区别。

图1　原始轨迹点与其对应的估计点

2　本文方法

2.1基于扇形面积的误差度量方式

在移动对象轨迹化简问题中，为了衡量简化轨迹S和原始轨迹O之间的区别，我们要根据算法的特性选择不同的误差度量方式，不同的误差度量方式对于同一轨迹数据的化简过程，结果是不同的，进而影响到存储空间、处理速度等关键指标。现有的误差度量方式通常分为垂直欧氏距离，同步欧氏距离和Fréchet距离［11］。本文结合算法实际，从利于关键点的判断和减小计算开销出发，在基于等极径的误差度量方式的基础上提出了一种新的误差度量方式。根据基于等极径的误差度量方式，只要控制了扇形中等腰三角形底边的长（即图2中的d），便能对整个简化过程进行误差控制，在MBS算法中是通过比较d和st_error（用户设定的阈值）的大小来决定是否向服务器端更新对象位置信息。因此在扇形的顶角θ确定后，以st_error作为d的值，根据扇形公式，可以得到在顶角下的扇形的最大面积，记为smax。具体的误差度量方法是当每次接受新的位置点信息后，首先在构造的边界扇形内，以扇形的顶点作为极坐标的极点，扇形的一边作为极轴。接着判断顶角θ是否发生变化，在θ不变的情况下，判断所构建的扇形面积ssec与smax的大小关系。当ssec＞smax时，向服务器端更新该移动对象的位置信息数据，并发送关键点的位置信息到服务器端。假设顶角θ大小变化发生变化，则重新计算smax，再与ssec的面积进行比较。与原先的误差度量方式相比，新的误差度量方式由于不需要计算每个点的估计点位置以及估计点到其自身的距离，计算开销减小。另外，新的误差度量方式也为新的算法判断关键点提供了方便。

图2　基于等极径的误差度量方式

图3　基于扇形面积的误差度量方式

2.2一种新的基于最小边界扇形的移动对象轨迹实时化简算法

为了设计出针对只有基本定位功能的GPS设备（即只能提供移动对象的基本位置信息，不能提供方向，速度等更详细的信息）实时轨迹化简算法，本文提出了一种新的基于最小边界扇形的移动对象轨迹实时化简算法（以下简称为NMBS算法），在只有基本位置信息的前提下，通过算法化简得到的轨迹数据能更好地体现移动对象的轨迹特征，同时算法的主要性能特征（包含运行时间、存储开销、计算开销等）与其他主流化简算法相比并无明显劣势。使用尽可能小的代价达到提高数据的处理效率，降低数据规模，提高数据可靠性。

在移动对象的运动过程中，本文使用最小边界扇形 （Minimum Bounding Sector，MBS）来匹配其运动轨迹，结合基于扇形面积的误差度量方式，在构造最小边界扇形时，以上一次简化更新后的下一个位置点或感知刚开始的位置点为顶点，其余点到顶点的距离的最大值为半径的方法向前构造包围扇形。这种构造包围扇形的方法如图4所示。

图4　构造最小边界扇形

在NMBS算法中有一个关键的概念∶关键点（key point），下面给出关键点的定义：

定义3关键点。当新构造的扇形满足向服务器更新的条件时，若某原始轨迹点oi（3≤i≤n）的前2个或2个以上的点位于扇形角平分线的一侧或角平分线上，而oi位于角平分的另一侧或角平分线上，则称该点为关键点。

通过以上定义可以看出，关键点是较能体现出轨迹变化特征的点。假设在某一时刻i，根据NMBS算法所构造的边界扇形满足更新条件，在向服务器发送新的位置信息的前，先判断关键点。并将关键点的位置信息一并发送给服务器。通过增加较能体现移动对象轨迹特征的关键点，使简化后的轨迹更加接近原始轨迹。

图5　MBS中的关键点

根据关键点的定义，假设针对某一阈值st_error，如图5所示在接收到轨迹点o8时，满足更新条件，则点o5，o7，o8是关键点，向服务器更新o1，o5，o7，o8的位置信息。具体的算法如算法1所示，算法的第一个输入参数st_error是用户设定的误差阈值，第二个参数Traj表示原始轨迹数据集合。函数CalcMBS（buf，point）用于计算当前的最小边界扇形，其中buf表示存储历史轨迹点的集合，point表示最新得到的位置信息；函数 area （newMBS）用于计算当前构造的扇形面积，其中newMBS表示当前扇形信息；函数CalcCen（newMBS）用于计算当前扇形的圆心角大小；Calcarea（θ，st_error）用于计算在给定阈值st_error和圆心角下扇形的理论面积；函数keypoint（point）用来判断当前的点是否是关键点；Key是关键点的集合；函数BoundInfor（newMBS）用于获得当前扇形的边界信息包括扇形中心点坐标，以及距离该坐标点的最大值和到中心点与X轴所成最大角、最小角四个数据。

算法1 NMBS method

分析算法可知，由于NMBS是由一重循环构成，时间复杂度为o（n）（其中n表示轨迹点数）；在算法的执行过程中，由于关键点的判定，需要保留每个点的相对位置信息，因此，算法的空间复杂度为o（n）。这种新的基于最小边界扇形的移动对象轨迹实时化简算法虽然增大了存储开销，但由于每个点的信息仅仅是其位置信息（并不包含瞬时速度，方向等其他信息），使得这种增大在合理可接受的范围内。同时由于新的误差度量方式的提出，缩减了计算开销和处理时间。总的来说，该算法的特点是：算法本身对输入要求小（仅需要位置点信息和误差阈值），能较好地描述运动对象的运动趋势。

3　实验分析及估计

为对算法进行分析和性能评估，实验平台选取台式电脑做为测试硬件平台，具体的实验平台配置为：Pentium Dual-Core CPU E5500@2.80GHz，内存为2GB；实验环境为Windows 7操作系统和Eclipse开发环境。实验所使用的数据是从INFATI（Intelligent Farttilpasning）［12］得到。INFATI的位置信息是由2000-2001年期间从分成两组一共20辆行驶在丹麦的汽车上采集得到的，它由20个GPS数据集构成。为了进一步分析与评估NMBS算法的性能，本文选取了以下参数：

轨迹化简率：化简后到的轨迹中的轨迹点数量与原始轨迹中轨迹点数量的比值。

实际误差相遇于误差阈值的比值：某一时刻i，某简化轨迹点Si与其对应原始轨迹点oi的之间的距离与所设定的误差阈值之比。

实际误差相当于实际距离的比值：某一时刻i，某简化轨迹点Si与其对应原始轨迹点oi的之间的距离与实际相邻的两个轨迹点之间距离的比值。

轨迹的化简率体现了原始轨迹中的轨迹点被化简的多少，当这个值越小时，体现了原始轨迹中被化简掉的点越多，算法的简化程度越好。实际误差相遇于误差阈值的比值和相对实际距离的比值则反映了算法对误差控制的影响，是算法的质量指标。实际误差相遇于误差阈值的比值越接近1则说明算法有很好的误差控制［4］；实际误差相当于实际距离的比值越小则说明误差对实际距离的影响越小。

实验首先对算法的时间复杂度和空间复杂度进行了比较，结果如表1所示，其中n表示轨迹点的数量，m表示给定的存储空间的大小。

表1　各种算法的时间复杂度和空间复杂度的比较

接着，针对以上算法从简化率，与实际的误差大小，运行时间等角度，进行性能的分析和比较，具体的结果如图6所示。分析以下结果，可以看出文章所提出的算法有较好的稳定性，从处理时间来看，NMBS并没有因为增加要保留的点而使得算法运行时间与其余算法有明显劣势，能较好地保证实时性；从简化误差来看，算法体现了较好的误差控制。综合来说，NMBS算法有较好的综合性能。

图6　几种算法的性能比较

另外实验中还使用手机作为载体，对算法进行了实际的检测。本次实验中选取华为荣耀3c作为测试手机，手机的具体配置为：CPU型号：MTK6582，CPU频率：1.3GHz，CPU数：4核，RAM容量：2GB，ROM容量：8GB。手机搭配Android 4.4.2操作系统，开发中使用了百度地图的Android SDK v6.2.进行定位。实验中，每隔10s进行一次定位，试验中将误差阈值设置为5m。

表2　NMBS算法的实验结果记录

实验记录了3种场景：在道路上行走方向随意的行人，其行走速度约为4-10km/h；第二种是速度为15-20km/h的自行车，最后一种是正常行驶的公交车，速度约为30-40km/h。本次实验的结果记录如表2所示。实验结果表明，算法有着较好的化简率，图7是实验中的部分截图，从图7来看，化简后的轨迹能较好地和原轨迹重合（其中红色细实线表示原始轨迹，绿色粗实线表示简化后的轨迹），体现原轨迹的特征。从结果我们也能看出，当移动对象是行人时，其运动范围较小，运动速度较慢，由于受到GPS定位误差等影响。轨迹的绘制较为混乱，有一定误差，不够细致。当移动对象的运动范围较大，简化轨迹能较好地反映出原始轨迹的特点。总的来说算法的适用对象较为广泛，算法性能较为优秀。

4　结语

由于移动对象的移动规律、运动方向、速率、等因素的不可预知性，使得某一算法很难在多种情境下都体现出令人满意的性能。本文针对只具备基本定位功能的设备，设计出了NMBS实时算法。该算法确保了在某些环境下增加了信息量，有助于轨迹数据的挖掘，研究。同时实验结果表明NMBS的运行时间，开销等并没有因此有明显的增大。当然这种通过增加保留点数量的方法对保留轨迹点的数量的不可控性，能否在更新位置信息时做到对保留轨迹点数目的控制，以及使得保留的点更有价值，将是今后所需研究的问题。

图7　NMBS算法的化简结果

［1］王欣然，杨智应.基于PLAZA的移动对象轨迹实时化简方法［J］.计算机应用研究，2014，31（5）∶1316-1319.

［2］陈金海.海洋运输船舶轨迹分析研究进展［J］.中国航海，2012，35（3）∶54-57.

［3］Guting R H，Schneider M.Moving Objects Databases［M］.1版.高等教育出版社，2009∶25-30.

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

［5］Kaplan E D，Hegarty C J.Understanding GPS∶Principles and Applications［M］.Artech house，2006.

［6］李文海，程志光，卫东，向隆刚，郭晓倩.基于自适应安全区域的轨道实时化简方法［J］.计算机学报.2014，37（9）∶1923-1935.

［7］Potamias M，Patroumpas K，Sellis T.Amnesic Online Synopses for Moving Object/Proceedings of the 15th International Conference on Information and Konwledge Management.Glasgow，UK，2006∶784-785.

［8］Zhang R，Qi J Z，Lin d.A Highly Optimized Algorithm for Continuous Intersection Join Queries over Moving Objects.The Very Large Database Journal，2008，21（4）∶561-586.

［9］Cao H，Wolfson O，Trajcevski G.Spatio-Temporal Data Reduction with Deterministic Errorbounds.The Very Large Database Journal，2006，15（3）∶211-228.

［10］LIU G，IWAI M，SEZAKI K.An Online Method for Trajectory Simplification under Uncertainty of GPS［J］.Information and Media Technologies，2013，8（3）∶665-647.

［11］张玥，张宏莉，张伟哲.基于幂律分布的网络用户跨苏排序算法［J］.中文信息学报，2012，26（4）∶122-128

［12］C S Jensen，H Lahrmann，S Pakalnis，J Runge.The INFATI Data［Z］.Technical Report，Database and Programming Technologies Institute at Aalborg University，2004.

Moving Object；Real-Time Simplification；Error

Further Research on the Moving Object Trajectory Real-Time Simplification Algorithm Based on Minimum Boundary Sector

ZHANG Jia-bi，YANG Zhi-ying
（College of Information Engineering，Shanghai Maritime University 201306）

With a variety of portable personal communications equipment increased，with GPS positioning function equipment has become more and more popular in daily life，in the convenience of people's daily life，but also brings massive data management issues.Presents a new realtime moving object boundary minimum simplification algorithm based on sector，and puts forward the key point concept.The basic positioning devices，better gets the simplified trajectory closer to the original trajectory，and keeps the communication cost and computation cost of the original.Proposes a new error metric based on the area the way.Experimental results show that this algorithm has better of simple and fast processing speed，simplifies the results closer to the actual.

1007-1423（2016）20-0029-07

10.3969/j.issn.1007-1423.2016.20.006

张家碧（1991-），男，安徽合肥人，硕士研究生，研究方向为算法设计与分析、移动对象数据库

杨智应（1964-），男，博士，教授，研究方向为算法设计与分析、并行与分布式计算、移动自组网、RFID传感器网络与物联网

2016-03-15

2016-07-10