基于行人GPS轨迹提取路网信息的高效算法Word下载.doc

基于行人GPS轨迹提取路网信息的高效算法Word下载.doc

《基于行人GPS轨迹提取路网信息的高效算法Word下载.doc》由会员分享，可在线阅读，更多相关《基于行人GPS轨迹提取路网信息的高效算法Word下载.doc（17页珍藏版）》请在冰点文库上搜索。

大数据的获取与处理需要强有力的硬件支撑，但这不是本文的重点。

二是合适的路网挖掘算法。

将GPS数据转换为数字化路网，并与原有路网匹配，删除已经废弃的道路，添加新增的道路。

世界上最大的开源地图提供商OpenStreetMap（HaklayandWeber2008）采用一种让志愿者携带GPS装置记录GPS轨迹来手动更新地图的方式，获取的数据称为“志愿者地理信息”（Haklay2008）。

志愿者地理信息秉承“人人都是传感器”的理念（Schroedl,Wagstaffetal.2004），将每个人不仅作为地理信息的使用者，更是生产者。

参考上述理念，本次实验通过寻找志愿者，确定所需的实验区，采用步行的方式，边走边采集GPS点，形成了大约10万条GPS轨迹数据，建立GPS轨迹数据库，并设计新型的路网挖掘算法，从中提取有用的路网信息挖掘路网。

国内外研究现状

　　国外对于道路的提取算法研究比较成熟。

这些算法大都基于算术几何，有的以节点为核心，有的以特征追踪为核心。

这对于较为规则的车辆轨迹处理是高效而准确的（Fathi,A.andJ.Krumm,2010）。

这些算法之所以高效，一是因为算法设计的恰当，另一方面则是因为高采样率而低随机性的GPS数据。

这种通过专门的车载导航系统获取的大量数据，数据特征规则且明显（图1），算法难度不是很高。

然而，VGI数据在实践中往往是低采样率的，大约为2-5分钟有一个点，点与点之间相隔太远导致一些正常的匹配算法在面对VGI数据时低效，甚至有可能产生逻辑错误。

另外，专门采集数据处理后得到的信息主要用于驾驶的道路网，而对于行人需要的步行网，例如天桥、地下通道等减少交通负担的设施生成与更新方面研究不多。

图1来自文献[1]、[3]、[4]的原始数据，可以明显的看出路网而无干扰

　　国内对于通过GPS轨迹挖掘新道路网的研究相对较少，大部分算法是将矢量轨迹数据转换为栅格数据，然后利用图像识别算法提取路网，方法简单高效，但只适用于那些特征明显的轨迹的数据。

由于这类算法完全抛弃了矢量数据的优点，在面对VGI时就显得束手无措。

值得注意的是国内学者（陈琦，2011，廖顺华，2007）在这方面开展的一些研究。

这些研究多针对传统的路网采集方式，得到的GPS轨迹由专门的GPS装置采集得到，数据量小，用来更新专门的路段，比如陈漪的立交桥识别，实用性相对较小。

为了解决上述存在的问题，本文设计了一个用于挖掘步行GPS轨迹的并行算法。

首先，需要先研究一下VGI数据。

研究区数据

　　实验研究区来自安徽省合肥市市区的一部分，周长约20.12公里，面积约23.68平方公里。

由于是在市区，道路网比较密集，人流量巨大，所以路网的更新对于这个地区来说显得尤为重要。

同时也从百度公司获得了以前的旧路网数据。

图2研究区的路网数据（未经更新）

　　整体上看，大部分的道路网数据是正确的，但局部存在很多偏差（图4）。

图3路网与现实路网中的不匹配

　　本次实验的VGI数据采集部分模仿了OpenStreetMap的路网数据采集方式，但是更加突出了行人步行轨迹的无规律性，让志愿者在研究区域携带GPS走动，总共采集了将近10万条数据（图4）。

　　图410万条轨迹数据

　　整个实验区域的整体路网肉眼还是能够清晰辨认，但不同于以往专门采集的地理数据，路网存在很多错误路径和轨迹的不均匀分布。

通过观察图的具体细节，可以看出步行轨迹不同于车辆轨迹的特点如下：

（1）可以在统计意义上看出路网的形状，但由于不是专门采集的数据，轨迹的方向几乎可以说毫无规律（图6）;

（2）步行轨迹的终点容易集聚在一个地点，这些地点往往是一个景点入口，或者一个商城;

　　（3）由于步行的随意性，道路两旁很容易出现一些不是路网的稀疏路线;

　　（4）轨迹分布不均匀尤为明显;

　　（5）更为重要的是步行者的轨迹不仅仅会出现一些交通路网上，还有可能出现在其他可以自由步行的场合，比如操场。

图5局部数据放大图

算法流程

1.道格拉斯-普克线简化算法

　　在本试验中，算法预处理步骤是后续步骤能否有效运行的关键步骤。

面对海量的步行轨迹数据，首先就是要将其中的不稳定和错误因素尽可能去除掉。

一些经常在数据中出现的轨迹错误有下面几个：

（1）不可估性。

由于定位的不准确，一些轨迹会偏离原本的道路。

（2）冗余性。

步行轨迹的随意性决定了一些轨迹会有自身的一些重复。

　　（3）跳跃性。

志愿者GPS轨迹的不稳定性，导致一些轨迹出现很奇怪的转弯或者跳跃。

类似横穿街区，在非道路的地方的轨迹走动。

　　（4）稀疏性。

一些道路由于穿过社区，或者由于采样间隔的原因，使

　　得轨迹点往往比较稀疏，但仍可能是一条步行道路。

　　对于上述问题，首先采用一种叫道格拉斯-普克线简化的算法对数据进行处理。

道格拉斯-普克算法（Douglas–Peuckeralgorithm），亦称为拉默-道格拉斯-普克算法、迭代适应点算法或分裂与合并算法。

该算法是将曲线近似表示为一系列点，以减少点的数量。

　　道格拉斯-普克算法处理效果的关键就是阈值的选择，本次实验综合考虑各个因素，选取一般道路正常宽度的50%作为阈值，得到经过线简化后的行人轨迹数据。

线简化一方面纠正了一些行人轨迹的数据的轨迹错误，另一方面也降低了数据量。

2.细碎线段删除

　　在实验数据中能够看到一些小的细碎的线段，这些线段往往是没有意义的，在大数据量的前提下，这些数据的删除基本不会影响结果，而且还能减少带来的误差，降低数据量。

　　本文取道路一般宽度的两倍为阈值，将那些小于阈值的小线段从图中剔除。

算法并行遍历每一条轨迹，计算轨迹长度，如果长度小于阈值，那么就将这条线段从数据中删除。

3.R树索引

　　由于需要匹配大量的轨迹数据，所以首先需要做的就是对道路数据建立空间索引。

在GIS系统中，空间索引技术就是通过更加有效的组织方式，抽取与空间定位相关的信息组成对原空间数据的索引，以较小的数据量管理大量数据的查询，从而提高空间查询的效率和空间定位的准确性。

空间索引的方式很多[17]，大致有网格索引、R树、K-D树和四叉树等。

本实验采用了R树索引。

R树在数据库等领域的功绩非常显著，很好得解决了高维空间搜索等问题。

R树是B树在高维空间的扩展，是一棵平衡树。

每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。

4.删除已经废弃或不存在的路段

　　依次对道路数据和轨迹数据建立R树索引之后，首先要做的就是更新现有路网找到其中不存在的路网，把它删除，删除的目的一方面是为了减少数据的计算量，另一方面就是为以后的匹配减少弯路，简化匹配的难度，让轨迹点不会匹配到不存在的路上，思路很简单，只要分别遍历路网，查询周围的轨迹数据，如果轨迹数据小于一定的阈值，就可以把这段删除。

至于这个阈值怎么定，往往需要一定的统计知识，本实验采用了总数据的2万分之一，即20条为临界值，得出去除无效道路后的路网。

5.轨迹匹配

　　经过精简之后，计算的数据量就可以减少，同时也可以进行轨迹匹配。

轨迹匹配的大致过程是遍历每一条轨迹，对每一条轨迹的每一个点在一定范围进行搜索，类似对点做一个一定半径长的缓冲区，搜索在缓冲区内的道路。

如果搜索不到，则该点不做变化;

如果搜索到一条道路，则将它匹配到该点到该道路的垂足上。

　　伪算法：

　　ForeachTracetinVGIDataDo

　　ForeachPointpintDo

　　Result=SearchRoadswithinSomeDistance

　　IfResult.Count=0

　　DoNoThing

　　Elsep=p.perpendicular（Result）

　　EndIf

　　EndFor

　　ReturnnewVGIData

　　该算法主要思想正确，耗时也比较短。

在本次试验的机器上，大约用时半分钟便完成了对100,000条数据（处理过后大约50,000条）的处理。

但处理结果虽然比起源数据已经好很多，但是并不是令人满意的（图7）

图7蓝色为匹配生成的结果，下方为局部效果

　　图上可以看到大致明显的道路轮廓已经显现，但是一旦放到局部就会出现轨迹在道路之间随意“穿梭”的现象，原因显而易见，就是如果点靠近两条道路时候，由于一些误差，导致点看上去离自己原本那条路线更远，导致匹配到了另外一条道路上。

这种现象会出现在平行的两条道路上，也会出现在两条路合并的路口。

这个错误是影响匹配结果的关键因素。

这也是地图匹配要完成的核心任务。

对于这种错误，解决的办法就是当距离容差内找到的道路超过两条时，在进行地图匹配时可以参考先前匹配过的点的方向，根据方向调整匹配的道路，匹配时本次实验采取利用下面的条件进行匹配：

　　如果一个点容差D之内有两个以上的匹配道路，那么这个点匹配到Max（0.8*方向因子+0.2*距离因子）的道路上。

其中方向因子=0.5-三点形成的夹角余弦/2,距离因子=1-距离/D，如果前一点为空，方向因子=0。

　　另外在匹配的时候要注意一些细节，由于在行人轨迹的随意性，一些行人的轨迹点并不在路上，如果错误地将这些点匹配到两旁的道路上，往往容易出现一些匹配错误。

　　匹配的结果如下（图8）：

图8匹配结果图

6.道路提取

　　为了找出新的轨迹，可以用匹配后的轨迹与删减后的路网做一个减法运算，对于匹配后的轨迹的每一线段进行判断，判断它是否在当前路网内，如果不在，则将其保留。

判断的条件有两个：

　　·

没有任何路网与其有交点，这种比较少见。

线段的一端与原路网的交点很多而另一端则没有交点，表明这是在原路网上拓建的路，是新路网。

这种情况占大多数。

　　找出的新轨迹中有很多平行的道路，显然这些指向同一条道路，因此需要将这些道路合并为一条道路。

合并这些道路的算法思路很简单，即找到那些平行的、相邻的线段，将这些线段合并为一条线段，该条线段将位于这些线段的中间，并且斜率的大小为这些线段角度的平均值。

基本伪代码如下：

　　ListVisitedLine,FeatureSetNewWays,FeatureSetoutPut;

　　ForEachLineinNewWays

　　If（line.FidExsitinVisitedLine）

　　Continue;

　　ListFindIntersectRoad=NewWays.Intersect（line.Buffer（0.001））;

　　If（FindIntersectRoad.Length>

=2）

　　ListSimilarRoads=FindIntersectRoad.FindAll（WhereElementinitWhoseAngle≈line.Angle）;

　　LineStringnewLine=SimilarRoads.MiddleLine;

　　outPut.Add（newLine）;

　　Else

　　outPut.Add（line）;

　　通过上面的思路，得到了最终生成的新路网（图9）。

图9最终生成的新路网

结果分析与讨论

图10最终生成的新路网细节比对

　　上图（图10）列出了一些匹配正确的结果，这些新提取的道路已经很好的匹配到了现实中道路，达到了预期的目标，并且整个流程借助于索引与并行技术，耗时非常短，处理10万条数据包括预处理大概用时35s,这是非常高效的。

　　本文针对大数据量的步行轨迹数据，提出一个从志愿者GPS轨迹中提取路网的初步解决方案。

该方案首先运用一些几何算法对轨迹数据进行简化，为提高运算效率对数据建立了空间索引，同时借助地图匹配原理优化轨迹的正确匹配，最后构建了一个新的路网。

整个流程通过使用并行技术加速，使得整个流程处理的效率非常高。

虽然结果精度有待进一步提高，但为以后更精确的轨迹路网匹配打下了基础，也提供了一些经验,这是一个非常有意义的尝试。

为更好地满足大数据的处理需求，一个以后的研究中将进一步加强地图匹配方法的有效性，这是道路提取与更新的的核心所在。

将这一课题研究下去的意义毋庸置疑，如果能够大幅度提高提取的精度，将为地图公司省下一大笔资金，这是非常有价值的。

（转自中国勘测联合网测绘技术文章）