众源轨迹归并算法研究

《众源轨迹归并算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、；GPS；轨迹数据；轨迹归并;Needleman-Wunsch算法引言近年来，内嵌GPS定位功能的智能手机以及移动互联网的普及,使基于智能手机的位置服务得到广泛应用，大量的GPS轨迹数据可方便获取。国内外研究者根据带有GPS装置的移动设备所产生的历史轨迹数据来提取路网信息，并对其进行了大量研究，轨迹数据在车辆导航领域也已得到广泛应用。国外StefanEdelkamp最先提岀了基于K-Means算法的路网提取方法，该方法引入了拟合方法来表示道路中心线，进一步提高了路网的精度⑴;国内LijuanZhang提出了一种将GPS轨迹与现有路网相融合的路网校正方法［2］

3、。该方法使用OpenStreetMap(OSM)⑶为参考路网，能有效地降低GPS轨迹误差的影响，提高路网的精度,但需要以现有路网为基础来进行。随着城市规模的不断扩大，路网信息的更新也愈加频繁，众多学者也通过各种方法来构建准确且更新及时的地图。一般情况下，当新修道路尚未正式投入使用时，虽然禁止通行，但通常已有行人或者车辆来往。因此基于GPS移动设备产生的轨迹的路网构建方法需要快速获取并及时更新电子地图中的路网体系，这对于车辆导航、交通规划、土地利用等具有多重应用价值和意义。1GPS轨迹归并面临的问题分析1.1GPS轨迹的误差主要误差可分为：GPS定位误差、坐标

4、转化误差和数字地图误差。1.2数据量大每天有成千上万的人通过搭载有内嵌GPS定位功能的智能设备进行定位，假如按照每周更新一次的设想来获取GPS轨迹数据，这个数据量也将轻松突破TB级。1.3轨迹的不均匀分布文章数据采集部分模仿了OpenStreetMap的路网数据采集方式，在此基础上增加了行人的步行轨迹。携带开启GPS功能的智能手机的志愿者按自己的习惯行走，自动采集GPS数据点。对这些行人轨迹进行分析，可以得出行人步行轨迹的无规律性：（1）单个行人的轨迹方向几乎毫无规律；（2）由于步行的随意性，道路两旁很容易出现一些不是路网的稀疏路线；（3）步行轨迹的终点容易

5、聚集在一个地点，这些地点往往是一个地点的进出口等。2轨迹归并算法研究通过对上述问题进行分析，结合GPS轨迹数据采集成本低、更新速度快和覆盖范围广等特点，利用计算机网络技术、计算机软件技术和GIS技术等技术，结合轨迹归并实验，深入分析时空轨迹路网；详细探讨在特定时空轨迹路网下，轨迹在地理空间中呈现的时空分布特性和时空分布格局。2.1GPS轨迹数据预处理研究文章通过步行和车载的方式，使用GPS轨迹记录设备采集数据，形成GPS轨迹数据，建立GPS轨迹数据库。根据行人步行轨迹特点，GPS轨迹数据优化研究需要厘清：（1）GPS轨迹数据误差如何影响GPS轨迹数据库性能；

6、（2）GPS轨迹更新不及时的地图如何影响车辆导航。目前线状要素化简经典算法是道格拉斯-普克线简化算法[4],它的优点是具有平移和旋转不变性，给定曲线与阈值后，抽样结果一定。运用道格拉斯-普克线简化算法可去除掉原来的无意义的弯曲线段以简化GPS轨迹数据，从而有利于后面的轨迹几何计算和索引构建。算法实现效果如图2所示，其中灰色表示原始数据，黑色表示简化后的轨迹，其在一定程度上具有适用性。2.2构建轨迹归并算法模型文章研究全局比对Needleman-Wunsch算法模型[5-6]应用于GPS轨迹归并。该算法最初设计用于对齐DNA和蛋白质序列，作者认为也可用于GPS

7、轨迹比较。要全局对齐的两组GPS轨迹坐标序列是GAATTCAGTTA（序列1）,GGATCGA（序列2）,因此M=ll和N=7（分别是序列1和序列2的长度）。假设一个高级评分方案:如果序列1的位置i的残基与序列2的位置j的残基相同（匹配得分），则Si,j=2；此外Si,j=-l（不匹配得分），w=-2（空位得分）。一般Needleman-Wunsch技术的全局序列比对过程有以下几个步骤：(1)初始化矩阵全局比对动态规划方法的第一步是创建具有M+1列和N+1行的矩阵，其中M和N对应于待比对序列的大小。矩阵的第一行和第一列最初可以用0填充。(2)填充矩阵对于每个

8、位置，Mi,j被定义为位置i,j处的最大得分。Mi,