众源轨迹归并算法研究

【前言】众源轨迹归并算法研究由文秘帮小编整理而成，但愿对你的学习工作带来帮助。1 GPS轨迹归并面临的问题分析 1.1 GPS轨迹的误差 主要误差可分为：GPS定位误差、坐标转化误差和数字地图误差。 1.2 数据量大 每天有成千上万的人通过搭载有内嵌GPS定位功能的智能设备进行定位，假如按照每周更新一次的设想来获取GPS轨迹数据，这个数据量也将轻松突破T...

摘 要：在快速发展的城市和地区，路网信息要求精度准确、需要及时更新，未及时更新路网信息而导致的交通事故及二次事故频发是发达国家和发展中国家普遍面临的问题。如何利用计算机等相关技术自动化地获取和更新路网信息并对其进行相应的改善是城市交通相关部门及相关学者关心的一个问题。根据Global Positioning System（GPS）设备产生的历史轨迹数据对城市进行研究的方法逐渐受到重视，且相关方法取得了一定的进展。文章在Needleman-Wunsch算法的基础上提出一种轨迹归并最优匹配的算法，并通过实验验证其可以较好地提取路网信息。

关键词：路网；GPS；轨迹数据；轨迹归并；Needleman-Wunsch算法

引言

近年来，内嵌GPS定位功能的智能手机以及移动互联网的普及，使基于智能手机的位置服务得到广泛应用，大量的GPS轨迹数据可方便获取。国内外研究者根据带有GPS装置的移动设备所产生的历史轨迹数据来提取路网信息，并对其进行了大量研究，轨迹数据在车辆导航领域也已得到广泛应用。国外Stefan Edelkamp最先提出了基于K-Means算法的路网提取方法，该方法引入了拟合方法来表示道路中心线，进一步提高了路网的精度[1]；国内Lijuan Zhang提出了一种将GPS轨迹与现有路网相融合的路网校正方法[2]。该方法使用OpenStreetMap（OSM）[3]为参考路网，能有效地降低 GPS轨迹误差的影响，提高路网的精度，但需要以现有路网为基础来进行。

随着城市规模的不断扩大，路网信息的更新也愈加频繁，众多学者也通过各种方法来构建准确且更新及时的地图。一般情况下，当新修道路尚未正式投入使用时，虽然禁止通行，但通常已有行人或者车辆来往。因此基于GPS移动设备产生的轨迹的路网构建方法需要快速获取并及时更新电子地图中的路网体系，这对于车辆导航、交通规划、土地利用等具有多重应用价值和意义。

1 GPS轨迹归并面临的问题分析

1.1 GPS轨迹的误差

主要误差可分为：GPS定位误差、坐标转化误差和数字地图误差。

1.2 数据量大

每天有成千上万的人通过搭载有内嵌GPS定位功能的智能设备进行定位，假如按照每周更新一次的设想来获取GPS轨迹数据，这个数据量也将轻松突破TB级。

1.3 轨迹的不均匀分布

文章数据采集部分模仿了OpenStreetMap的路网数据采集方式，在此基础上增加了行人的步行轨迹。携带开启GPS功能的智能手机的志愿者按自己的习惯行走，自动采集GPS数据点。对这些行人轨迹进行分析，可以得出行人步行轨迹的无规律性：（1）单个行人的轨迹方向几乎毫无规律；（2）由于步行的随意性，道路两旁很容易出现一些不是路网的稀疏路线；（3）步行轨迹的终点容易聚集在一个地点，这些地点往往是一个地点的进出口等。

2 轨迹归并算法研究

通过对上述问题进行分析，结合GPS轨迹数据采集成本低、更新速度快和覆盖范围广等特点，利用计算机网络技术、计算机软件技术和GIS技术等技术，结合轨迹归并实验，深入分析时空轨迹路网；详细探讨在特定时空轨迹路网下，轨迹在地理空间中呈现的时空分布特性和时空分布格局。

2.1 GPS轨迹数据预处理研究

文章通过步行和车载的方式，使用GPS轨迹记录设备采集数据，形成GPS轨迹数据，建立GPS轨迹数据库。根据行人步行轨迹特点，GPS轨迹数据优化研究需要厘清：（1）GPS轨迹数据误差如何影响GPS轨迹数据库性能；（2）GPS轨迹更新不及时的地图如何影响车辆导航。目前线状要素化简经典算法是道格拉斯-普克线简化算法[4]，它的优点是具有平移和旋转不变性，给定曲线与阈值后，抽样结果一定。

运用道格拉斯-普克线简化算法可去除掉原来的无意义的弯曲线段以简化GPS轨迹数据，从而有利于后面的轨迹几何计算和索引构建。算法实现效果如图2所示，其中灰色表示原始数据，黑色表示简化后的轨迹，其在一定程度上具有适用性。

2.2 构建轨迹归并算法模型

文章研究全局比对Needleman-Wunsch算法模型[5-6]应用于GPS轨迹归并。该算法最初设计用于对齐DNA和蛋白质序列，作者认为也可用于GPS轨迹比较。要全局对齐的两组GPS轨迹坐标序列是GAATTCAGTTA（序列1），GGATCGA（序列2），因此M=11和N=7（分别是序列1和序列2的长度）。假设一个高级评分方案：如果序列1的位置i的残基与序列2的位置j的残基相同（匹配得分），则Si，j=2；此外Si，j=-1（不匹配得分），w=-2（空位得分）。一般Needl

eman-Wunsch技术的全局序列比对过程有以下几个步骤：

（1）初始化矩阵

全局比对动态规划方法的第一步是创建具有M+1列和N+1行的矩阵，其中M和N对应于待比对序列的大小。矩阵的第一行和第一列最初可以用0填充。

（2）填充矩阵

对于每个位置，Mi，j被定义为位置i，j处的最大得分。

Mi，j=Maximum[

Mi-1，j-1+Si，j，

Mi，j-1+w1，

Mi-1，j+w2]

其中，Si，j表示对角线中的匹配/失配，w1表示序列1中的间隙，w2表示序列2中的间隙，w1=w2。判断两个GPS轨迹点是否匹配，则设置阈值为10米，计算经纬度两点之间距离，小于等于阈值则匹配，否则不匹配。

（3）回溯

在矩阵填充步骤之后，两个序列的最大全局比对得分为3，回溯将确定导致最大得分的实际比对。

总分=2-1+2+2-2+2-2+2-2-2+2=3

从实验最后得到的总分可以得知，这两条路线可以得到最大对准得分，即为最优匹配。经过归并后的GPS轨迹数据如图8和图9所示，其中灰色表示两条原始GPS轨迹数据，黑色表示归并后的轨迹数据。

3 结束语

根据上述实验可知行人轨迹路径是复杂多变的，这加剧了数据的冗余度和复杂度，使用道格拉斯-普克线简化算法可以对轨迹数据进行初步处理以实现有效数据数量的缩减。基于Needleman-Wunsch算法的模型方法可以较好地进行轨迹归并，从而提取出较为准确的路网信息，可为车辆导航提供较准确、及时的路线规划。实验中虽然取得了一定成果，但仍存在一些问题：如果轨迹越长则矩阵越长，因此矩阵填充的计算需要花费大量时间；实验未进行多条轨迹的并行归并处理，还需进行进一步研究。

参考文献

[1]EdelkampS， Schrdl S. Route Planning and Map Inference with Global Positioning Traces[M].Computer Science in Perspective. Springer Berlin Heidelberg，2003：128-151.

[2]Zhang L， Thiemann F， Sester M. Integration of GPS traces with road map[C]. InProc. 2nd International Workshop on Computational Transportation Science， ACM，2010：17-22.

[3]Haklay M， Weber P. Openstreetmap： User-generated street maps[J].Pervasive Computing， IEEE，2008，7（4）：12-18.

[4]王晓理，陈双军，魏斌，等.曲线拟合的Douglas-Peucker算法阈值优化选择[J].测绘科学技术学报，2010（06）.

[5]汪浩.基因序列比对算法的优化研究[D].中国农业科学院，2015.

[6]Edelkamp S， Schrl S. Route Planning and Map Inference with Global Positioning Traces[M].Computer Science in Perspective. Springer Berlin Heidelberg，2003：128-151.