GPS航迹线的自适应折半查找化简算法

王 静,谭祥爽,宋现锋,,汪超亮

(1.中国科学院大学资源与环境学院,北京 100049; 2.中国科学院光电研究院,北京 100094)

GPS航迹线的自适应折半查找化简算法

王 静1,谭祥爽1,宋现锋1,2,汪超亮2

(1.中国科学院大学资源与环境学院,北京 100049; 2.中国科学院光电研究院,北京 100094)

提出了一种新的全球定位系统(GPS)航迹线自适应折半查找化简算法,采用了Sleeve-fitting算法的最优骨架点判断模式来保证航迹线的化简质量,通过粗筛与精选相结合的分步处理方式来提高化简效率:粗筛是利用经验步长值动态预测下一步搜索步长,快速确定包含骨架点的搜索区间;精选是在搜索区间内利用折半查找的方式搜索到骨架点.将某市城区的GPS航迹数据应用于文中算法,结果表明,该算法大幅度提高了化简效率,同时最大程度地保持了化简后航迹线与原始航迹在形态特征上的一致性.

GPS航迹;线化简;折半查找;最优骨架点

随着卫星导航系统的普及,出租车、公交车以及各种巡查车辆都安装了低成本的全球定位系统(GPS)接收机,遍及城市的各条街道,用于实时监测车辆运行.这些定位数据精度低,但是覆盖范围广、数据量大,已经逐渐成为交通路网提取的主要数据源.为了在道路转弯处获取精确的结果,通常GPS接收机以1 s甚至更小的频率采集道路坐标数据.采样点越密集,则越贴近原始道路的空间分布,但随之而来的数据量急剧增大,对其管理和分析都带来了困难[1].比如,不同尺度地图展示的道路详细程度存在差异,在给定尺度较为容易显示的地图信息,则无法有效地在较小尺度上展示[2].因此,需要对GPS航迹线进行有效化简,剔除平直道路区大量的冗余点,转弯的路口区保留较多的点,以最大程度反映原始道路的形态特征.

国内外学者围绕曲线化简问题进行了深入研究,但是当前方法对于GPS航迹线化简的适用性受到限制.Mc Master将化简算法划分为:独立点算法、局部处理算法、无限制条件的局部处理扩展算法、有限制条件的局部处理扩展算法以及全局算法[3].其中,独立算法以固定间隔选取航迹点,不能保证最优航迹点(骨架点)被保留下来,化简结果失真度大.全局算法中应用最广泛的Douglas-Peucker算法[4],不能解决GPS航迹线中航迹重复、交叉以及起点与终点相近或重叠的问题.根据以上分析,GPS航迹线化简需要采用一种局部化简算法.近几年,诸多学者提出遗传、小波变换等人工智能算法进行曲线化简[5-7],但是算法实现过程复杂,不适合大数据量的GPS航迹线的快速化简需求.

为此,笔者提出了一种GPS航迹线的自适应折半查找化简算法.该算法采用了Sleeve-fitting算法的最优骨架点判断模式,在骨架点搜索过程中,利用经验步长值来动态地预测下一步搜索步长,快速确定骨架点的合理搜索区间;然后,采用折半查找方法判断搜索区间内的骨架点,加快了搜索速度.结果表明,文中算法的化简效果较好地保持了原始道路形态,更重要的是效率得到了大幅度的提高,符合大数据量化简的需求.

1 材料与方法

1.1 实验数据

实验区位于某市,面积约13.7 km×9.8 km.这些GPS航迹线涵盖了直线、弯曲、平面和多层立交各种交通结构,可以满足验证化简算法的需求.GPS航迹数据来自于巡检车辆上安装的低成本GPS接收机,以1 s的频率记录坐标点,包括经度、纬度和时间.文中用于化简的航迹约有10条,合计18 401个航迹点.

1.2 最优骨架点定义

骨架点定义采用了Sleeve-fitting算法[8]提出的概念.假设一段航迹线由一系列连续点构成(如图1所示),图中矩形平行于首末点连线(虚基线),限差是矩形宽度的一半.点是否在矩形内表示其到基线垂直距离和限差的关系.给定起始点(或前骨架点)P1和终点P3,构成一个判断区间.连接P1与P3形成基线,计算位于P1与P3之间的点到基线的垂直距离,如果所有点的垂直距离都小于给定的限差值,则认为P1与P3形成的基线可以近似代表P1与P3之间的曲线段,此时P3为骨架点.

根据上述定义,骨架点不一定是最优骨架点.仍然以P1为起点,移动终点至P4,构成新的判断区间,判断P1与P4所连基线是否可以代替P1与P4之间的曲线段.如果可以近似代替,此时P4是骨架点,同时确认P3不是最优骨架点.依次类推,当P1与P5构成判断区间时,如果基线不能够近似代表曲线段,则P5为非骨架点,而P4则可确认为最优骨架点.这种最优骨架点的定义方式使得航迹线达到了最大程度化简.

图1 化简过程示意图

1.3 自适应折半查找化简算法

1.3.1 最优骨架点的折半查找

航迹线的化简过程就是最优骨架点的搜索过程.在化简过程中,航迹线的首末两个端点保留为骨架点.判断首末两端点之间是否含有骨架点的方法如下:连接两个端点形成基线,如果两个端点之间存在着某点到基线的垂直距离大于给定的限值,则认为存在骨架点;否则,两端点连线就是化简结果.

文中采用折半查找方法来实现骨架点的定位,即精选过程.给定一个搜索区间,位于前骨架点(首端点)的右侧,假设其中含有骨架点.搜索区间的起点和前骨架点可以重合,也可以不重合.具体搜索过程如下:在搜索区间内,其中间点将搜索区间分为左右两个子区间,连接前骨架点与搜索区间的中间点形成基线,如果前骨架点与中间点之间存在着骨架点,则将左子区间设为新搜索区间进行递归处理;否则,将右子区间设为新搜索区间进行递归处理.直到搜索区间不能划分为止,最后一个搜索区间的左端点就是骨架点.值得注意的是,在处理过程中,基线的左端点一直是前骨架点保持不变,右端点根据折半查找方法在搜索区间内变动,直到确定骨架点为止.以搜索到的骨架点为起点,重复上述过程,查找新骨架点,直到完成整条航迹线的处理为止.

1.3.2 搜索区间的动态预测

为保证折半查找算法中的搜索区间含有骨架点,需要合理确定出搜索区间的长度,即粗筛过程.这里引入步长的概念,假定搜索区间的长度是步长的倍数,可表示为

其中,y为搜索区间长度,x为步长,k为整数,m为航迹线的总点数.给定步长x,搜索区间长度是随着k值而变化的.k值的确定方法:将k值依次加一取值,对长度为kx的搜索区间进行判断,直到其内部含有骨架点为止.

在确定搜索范围的过程中,k值的穷举法效率较低.如果指定的步长接近于被搜索的骨架点与前骨架点之间的长度,则穷举次数将大大减小,化简速度也将提高.下面给出了两种步长赋值方法:平均值法和卡尔曼滤波预测法.平均值法是将前n个骨架点间长度的平均值赋为步长;卡尔曼滤波预测法是根据前两个骨架点之间的长度,经过增益计算预测当前的步长值的,具体方法如下:

假设所有步长为离散控制过程的系统X(k),步长观测量为Z(k),则观测模型为

其中,X(k)即为第k个骨架点的步长,U(k)为当前状态的控制量,A和B是系统参数,H是测量系统的参数; W(k)和V(k)分别表示过程和测量的噪声.其协方差分别是Q和R.则有

其中,X(k|k-1)是预测结果;X(k-1|k-1)是前一个状态的结果,即前两个骨架点之间的长度; P(k|k-1)是X(k|k-1)对应的协方差;P(k-1|k-1)是X(k-1|k-1)对应的协方差;A′是A的转置矩阵;Q是系统过程的协方差.

根据以上两个式子得到当前步长的预测结果,结合测量值,计算得到步长最优化估算值为

其中,Kg(k)为卡尔曼增益;P(k|k)为k状态下的协方差,用于下一个骨架点步长的预测.

1.4 评价方法

根据Mc Master提出的化简算法的评估方法,这里选取了压缩率、长度比、距离位移、面积位移和曲折度指标,从航迹线的压缩程度和骨架线质量两个方面对化简算法进行了评价.

压缩率高表明剔除的冗余点多,说明化简效果好;长度比大表明压缩后的骨架线越接近原始航迹线的长度,说明骨架线的保真度高;距离位移大表明骨架线偏移原始航迹线远,说明骨架线的保真度低;面积位移大表明骨架线和原始航迹线之间的空隙大,说明骨架线的保真度低;曲折度高表明骨架线和原始航迹线相比变化幅度增大,说明保真度低.各参数的表达式如下:

压缩率为

长度比为

距离位移为

面积位移为

曲折度为

其中,m和n分别为化简后点数和原始点数;L′和L分别为化简后曲线和原始曲线的长度;Pij是第i个原始点到第j条化简弧段的垂直距离;Sj表示第j条化简弧段与原始曲线围成的面积;βij表示第i条原始弧段与第j条化简弧段的夹角;αi表示原始曲线上第i条弧段与第i+1条弧段组成的夹角.

2 结果与讨论

文中选择了4种已有的经典局部算法Reumann-Witkam(RW)[9]、Sleeve-Fitting(SF)、Opheim (OP)[10]、Lang(LA)[11]和自适应折半查找(ABS)算法进行比较.对于ABS算法,根据1.3节提出的两种步长赋值方法,分别得到了ABS_M(平均值)和ABS_K(卡尔曼滤波预测值)两种化简结果.

2.1 可视化对比分析

图2显示了压缩率为93%时,折半查找方法化简结果和原始航迹的叠加效果.图2表明,GPS航迹线得到了大幅度化简,尤其在道路平滑路段,其形状与原始航迹保持高度一致.

为了验证自适应折半查找算法的化简效果,在限差值相同(如3.5 m)的情况下,利用以上5种算法对GPS航迹线分别进行了化简.图3显示了各算法在转弯、直线处的局部化简结果,其在整个实验数据中的位置在图2中进行了标示.

由图3可见,SF算法与ABS算法的化简质量基本一致,二者均对航迹线进行了最大程度的化简,获得了较高的压缩率,并且保留了曲率变化特征大的点以保持原始航迹线形态;LA算法在路口或转弯处的化简效果显著,但在直线处受到

图2 折半查找化简结果

图3 相同限差值下(3.5 m)各算法可视化化简结果

所给化简区间大小的限制产生了大量冗余点.由于其化简区间的大小由人工根据经验设定,使得化简结果的质量具有很大的不确定性;RW算法保留了部分冗余点,没有达到最大程度的化简;OP算法在RW算法的基础上,进一步保留了更多骨架点,虽然提高了与原始航迹线的形态符合程度,但是却大大降低了压缩率,尤其是在平直线段位置.

2.2 定量评价与分析

2.2.1 压缩率比较

化简过程中,给定相同的限差值(3.5 m),比较各算法化简结果的压缩率差异.

表1 相同限差值下各算法压缩率

表1表明,在已有的4种算法中,SF算法具有最高的压缩比率,超过93%的冗余点被剔除了,而其他3种算法结果接近,效果较差.LA算法的结果取决于初始步长值,不具有重复性;OP算法因增加两个限制条件,保留了更多的原始点,压缩率小于RW算法.文中提出的自适应折半查找化简算法的压缩率与SF算法的压缩率接近,且略好,主要是因为SF算法和ABS算法的化简思想类似,都为查找最优骨架点所致.

2.2.2 化简效率与效果比较

化简过程中,给定相同的压缩率(85%),即保持骨架点数目相同,比较各种算法的化简效率和效果,结果如表2所示.结果表明,在已有的4种算法中,SF算法的化简结果具有最好的化简质量,但是化简效率很低; LA算法化简质量次之;RW算法与OP算法化简质量最差,不具可比性.其中,SF算法的结果具有重复性,但是LA算法的结果具有不确定性,主要取决于人工输入的步长,步长越小,化简所需时间越短,但化简质量欠佳.OP算法在RW算法的基础上增加了两个限制条件,因此其运行时间较长.

表2 相同压缩率下的各算法化简结果评价指标

文中提出的自适应折半查找化简算法的效果接近于SF算法,甚至更好些,但是化简时间却远小于SF算法的.同SF算法一样,ABS算法也是通过查询最优骨架点来生成化简曲线,因其采用了不同的骨架点搜索区间确定和骨架点查找方式,才大幅度地节省了化简时间.ABS算法同样具有可重复性,不需要人工干预.其中,基于卡尔曼滤波方法动态预测步长,使得化简效率比平均值步长法的更高.

3 结束语

提出了一种高效的化简算法用于降低GPS航迹线的数据冗余,同当前的几种成熟的局部压缩算法相比,该算法更适合于GPS航迹数据的化简.相对于RW、OP和LA算法,该算法能提供自适应步长,应用灵活,适用于各种数据集;因仅有限差1个参数,其自动化程度更高.相对于SF算法,该算法利用折半查找的方法搜索骨架点,极大减少了骨架点的搜索时间,大幅度提高了化简效率,但保持了很高的化简质量.

通过与当前4种成熟化简算法的定性和定量比较,结果表明,文中提出的算法在应用于GPS航迹线化简时,克服了压缩率和化简效率低的缺点,同时保证了化简效果.此外,该算法还可以做进一步的探索,比如考虑GPS数据本身误差对化简过程的影响,提供自适应限差值控制化简的程度和质量等.

[1]Ivanov R.Real-time GPS Track Simplification Algorithm for Outdoor Navigation of Visually Impaired[J].Journal ofNetwork and Computer Applications,2012,35(5):1559-1567.

[2]Park W,Yu K.Hybrid Line Simplification for Cartographic Generalization[J].Pattern Recognition Letters,2011,32 (9):1267-1273.

[3]Mc Master R B.The Geometric Properties of Numerical Generalization[J].Geographical Analysis,1987,19(4):330-346.

[4]Douglas D,Peucker T.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].The Canadian Cartographer,1973,10(2):112-122.

[5]黄娟,程耀东.多分辨率小波分析在GIS线状要素简化中的应用[J].唐山学院学报,2010,23(7):13-16.

Huang Juan,Cheng Yaodong.Application of Multi-resolution Wavelet Analysis in GIS Linear Element Simplification [J].Journal of Tangshan College,2010,23(7):13-16.

[6]任海艳,陈飞翔.自适应遗传算法的改进及在曲线化简中的应用[J].计算机工程与应用,2012,48(11):152-155.

Ren Haiyan,Chen Feixiang.Improvement of Adaptive Genetic Algorithms and Application in Line Simplification[J]. Computer Engineering and Applications,2012,48(11):152-155.

[7]武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-355.

Wu Fang,Deng Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica,2003,32(4):349-355.

[8]Zhao Z,Saalfeld A.Linear-time Sleeve-fitting Polyline Simplification Algorithms[DB/OL].[2012-12-30].http:// mapcontext.com/autocarto/proceedings/auto-carto-131pdf/linear-time-sleeve-fitting-pdyline-simplification-algorithm.pdf.

[9]Reumann K,Witkam A P M.Optimizing Curve Segmentation in Computer Graphics[C]//Proceedings of International Computing Symposium.Amsterdam:North-Holland,1974:467-472.

[10]Opheim H.Fast Data Reduction of a Digitized Curve[J].Geo-Processing,1982,2:33-40.

[11]Lang T.Rules for Robot Draughtsmen[J].Geographical Magazine,1969,42(1):50-51.

(编辑:齐淑娟)

Adaptive binary search polyline simplification algorithm for GPS trajectories

WANG Jing1,TAN Xiangshuang1,SONG Xianfeng1,2,WANG Chaoliang2
(1.College of Resources and Environment,Graduate University of Chinese Academy of Sciences,Beijing 100049,China;2.Academy of Opto-Electronics,Chinese Academy of Sciences,Beijing 100094,China)

This paper proposes an adaptive binary search polyline simplification algorithm for simplifying GPS trajectories,which adopts the optimal skeleton point conceptual model of the Sleeve-fitting algorithm to retain a maximum point reduction.Meanwhile,the innovating modifications of screening roughly and handpickedly are suggested to improve the efficiency of simplification process significantly:Dynamically predicting the search step to determine quickly a search interval within which at least one skeleton point falls;Applying a binary search in the search interval of the GPS trajectory to locate the optimal skeleton point.The GPS trajectories acquired in Huaibei City,China are used for testing polyline simplification.As a result,our proposed algorithm preserves the best shape characteristics with a shortest running time.

GPS trajectories;binary search;polyline simplification;the optimal skeleton point

P208

A

1001-2400(2014)05-0155-06

2013-07-09< class="emphasis_bold">网络出版时间:

时间:2014-01-12

中国科学院知识创新工程重要方向性资助项目(KZCX2-EW-QN605);国家科技重大专项“大型油气田及煤层气开发”资助项目(2011ZX05039-004)

王 静(1986-),女,中国科学院大学博士研究生,E-mail:qiufengwj@163.com,xfsong@ucas.ac.cn.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.026.html

10.3969/j.issn.1001-2400.2014.05.026