引言
当今时代，数字地图对于每一个人来说都变得日益重要。普通用户下载诸如Google地图、百度地图等类似软件来寻找目的地以及周围的景点、住宿和餐旅等等。商家用来宣传自己的品牌(Fathi and Krumm 2010)。但对国内数字地图而言，目前大部分都由特定的地图供应商通过专门部署GPS装置的汽车在路上行驶并采集数据。数据获取与更新成本的高昂意味着购买这些这类地图数据需要花费大量的资金。因此，国内除了百度、高德、搜狗外，鲜有其他的地图服务商。然而，随着城市化进程的加快与道路网的建设与完善，用户却面临这样的问题：某个地方新修了一条道路，但因路网数据的更新不及时而无法在地图上找到这条路。如何缩短路网更新时间，尽可能满足用户的需求体验，则需要探索新的路网采集与更新方式。在带有GPS装置的移动设备越来越普遍的背景下，如何通过合理的路网挖掘算法，有效利用这些普通用户的定位数据，及时更新现有路网信息，这不仅极大降低路网更新的高昂成本，还将有力提升地图服务的质量与效率。
这项技术的难点有二：一是大数据量。每天有成千上万的人通过搭载有GPS装置的设备定位，假如按照每周一次更新的设想来获取GPS轨迹数据，这个数据量也将轻松突破TB级。大数据的获取与处理需要强有力的硬件支撑，但这不是本文的重点。二是合适的路网挖掘算法。将GPS数据转换为数字化路网，并与原有路网匹配，删除已经废弃的道路，添加新增的道路。世界上最大的开源地图提供商OpenStreetMap(Haklay and Weber 2008)采用一种让志愿者携带GPS装置记录GPS轨迹来手动更新地图的方式，获取的数据称为“志愿者地理信息”(Haklay 2008)。志愿者地理信息秉承“人人都是传感器”的理念(Schroedl, Wagstaff et al. 2004)，将每个人不仅作为地理信息的使用者，更是生产者。参考上述理念，本次实验通过寻找志愿者，确定所需的实验区，采用步行的方式，边走边采集GPS点，形成了大约10万条GPS轨迹数据，建立GPS轨迹数据库，并设计新型的路网挖掘算法，从中提取有用的路网信息挖掘路网。
国内外研究现状
国外对于道路的提取算法研究比较成熟。这些算法大都基于算术几何，有的以节点为核心，有的以特征追踪为核心。这对于较为规则的车辆轨迹处理是高效而准确的(Fathi, A. and J. 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)。
图4 10万条轨迹数据
整个实验区域的整体路网肉眼还是能够清晰辨认，但不同于以往专门采集的地理数据，路网存在很多错误路径和轨迹的不均匀分布。通过观察图的具体细节，可以看出步行轨迹不同于车辆轨迹的特点如下：
(1)可以在统计意义上看出路网的形状，但由于不是专门采集的数据，轨迹的方向几乎可以说毫无规律(图6);
(2)步行轨迹的终点容易集聚在一个地点，这些地点往往是一个景点入口，或者一个商城;
(3) 由于步行的随意性，道路两旁很容易出现一些不是路网的稀疏路线;
(4) 轨迹分布不均匀尤为明显;
(5) 更为重要的是步行者的轨迹不仅仅会出现一些交通路网上，还有可能出现在其他可以自由步行的场合，比如操场。
图5 局部数据放大图
算法流程
1.道格拉斯-普克线简化算法
在本试验中，算法预处理步骤是后续步骤能否有效运行的关键步骤。面对海量的步行轨迹数据，首先就是要将其中的不稳定和错误因素尽可能去除掉。一些经常在数据中出现的轨迹错误有下面几个：
(1) 不可估性。由于定位的不准确，一些轨迹会偏离原本的道路。
(2) 冗余性。步行轨迹的随意性决定了一些轨迹会有自身的一些重复。
(3) 跳跃性。志愿者GPS轨迹的不稳定性，导致一些轨迹出现很奇 怪的转弯或者跳跃。类似横穿街区，在非道路的地方的轨迹走动。
(4) 稀疏性。一些道路由于穿过社区，或者由于采样间隔的原因，使
得轨迹点往往比较稀疏，但仍可能是一条步行道路。
对于上述问题，首先采用一种叫道格拉斯-普克线简化的算法对数据进行处理。道格拉斯-普克算法(Douglas–Peucker algorithm)，亦称为拉默-道格拉斯-普克算法、迭代适应点算法或分裂与合并算法。该算法是将曲线近似表示为一系列点，以减少点的数量。
道格拉斯-普克算法处理效果的关键就是阈值的选择，本次实验综合考虑各个因素，选取一般道路正常宽度的50%作为阈值，得到经过线简化后的行人轨迹数据。线简化一方面纠正了一些行人轨迹的数据的轨迹错误，另一方面也降低了数据量。
2.细碎线段删除
在实验数据中能够看到一些小的细碎的线段，这些线段往往是没有意义的，在大数据量的前提下，这些数据的删除基本不会影响结果，而且还能减少带来的误差，降低数据量。
本文取道路一般宽度的两倍为阈值，将那些小于阈值的小线段从图中剔除。算法并行遍历每一条轨迹，计算轨迹长度，如果长度小于阈值，那么就将这条线段从数据中删除。
3. R树索引
由于需要匹配大量的轨迹数据，所以首先需要做的就是对道路数据建立空间索引。在GIS系统中，空间索引技术就是通过更加有效的组织方式，抽取与空间定位相关的信息组成对原空间数据的索引，以较小的数据量管理大量数据的查询，从而提高空间查询的效率和空间定位的准确性。空间索引的方式很多[17]，大致有网格索引、R树、K-D树和四叉树等。本实验采用了R树索引。R树在数据库等领域的功绩非常显著，很好得解决了高维空间搜索等问题。R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。
4. 删除已经废弃或不存在的路段
依次对道路数据和轨迹数据建立R树索引之后，首先要做的就是更新现有路网找到其中不存在的路网，把它删除，删除的目的一方面是为了减少数据的计算量，另一方面就是为以后的匹配减少弯路，简化匹配的难度，让轨迹点不会匹配到不存在的路上，思路很简单，只要分别遍历路网，查询周围的轨迹数据，如果轨迹数据小于一定的阈值，就可以把这段删除。至于这个阈值怎么定，往往需要一定的统计知识，本实验采用了总数据的2万分之一，即20条为临界值，得出去除无效道路后的路网。
5. 轨迹匹配
经过精简之后，计算的数据量就可以减少，同时也可以进行轨迹匹配。轨迹匹配的大致过程是遍历每一条轨迹，对每一条轨迹的每一个点在一定范围进行搜索，类似对点做一个一定半径长的缓冲区，搜索在缓冲区内的道路。如果搜索不到，则该点不做变化;如果搜索到一条道路，则将它匹配到该点到该道路的垂足上。
伪算法：
For each Trace t in VGIData Do
For each Point p in t Do
Result=Search Roads within SomeDistance
If Result.Count=0
Do NoThing
Else p=p. perpendicular(Result)
End If
End For
End For
Return new VGIData
该算法主要思想正确，耗时也比较短。在本次试验的机器上，大约用时半分钟便完成了对100,000条数据(处理过后大约50,000条)的处理。但处理结果虽然比起源数据已经好很多，但是并不是令人满意的(图7)
图7 蓝色为匹配生成的结果，下方为局部效果
图上可以看到大致明显的道路轮廓已经显现，但是一旦放到局部就会出现轨迹在道路之间随意“穿梭”的现象，原因显而易见，就是如果点靠近两条道路时候，由于一些误差，导致点看上去离自己原本那条路线更远，导致匹配到了另外一条道路上。这种现象会出现在平行的两条道路上，也会出现在两条路合并的路口。这个错误是影响匹配结果的关键因素。这也是地图匹配要完成的核心任务。对于这种错误，解决的办法就是当距离容差内找到的道路超过两条时，在进行地图匹配时可以参考先前匹配过的点的方向，根据方向调整匹配的道路，匹配时本次实验采取利用下面的条件进行匹配：
如果一个点容差D之内有两个以上的匹配道路，那么这个点匹配到Max(0.8*方向因子+0.2*距离因子)的道路上。其中方向因子=0.5-三点形成的夹角余弦/2,距离因子=1-距离/D，如果前一点为空，方向因子=0。
另外在匹配的时候要注意一些细节，由于在行人轨迹的随意性，一些行人的轨迹点并不在路上，如果错误地将这些点匹配到两旁的道路上，往往容易出现一些匹配错误。
匹配的结果如下(图8)：
图8 匹配结果图
6.道路提取
为了找出新的轨迹，可以用匹配后的轨迹与删减后的路网做一个减法运算，对于匹配后的轨迹的每一线段进行判断，判断它是否在当前路网内，如果不在，则将其保留。判断的条件有两个：
·没有任何路网与其有交点，这种比较少见。
·线段的一端与原路网的交点很多而另一端则没有交点，表明这是在原路网上拓建的路，是新路网。这种情况占大多数。
找出的新轨迹中有很多平行的道路，显然这些指向同一条道路，因此需要将这些道路合并为一条道路。合并这些道路的算法思路很简单，即找到那些平行的、相邻的线段，将这些线段合并为一条线段，该条线段将位于这些线段的中间，并且斜率的大小为这些线段角度的平均值。基本伪代码如下：
List VisitedLine,FeatureSet NewWays,FeatureSet outPut;
For Each Line in NewWays
If (line.Fid Exsit in VisitedLine)
Continue;
End If
List FindIntersectRoad=NewWays.Intersect(line.Buffer(0.001));
If (FindIntersectRoad.Length>=2)
List SimilarRoads=FindIntersectRoad.FindAll(Where Element in it Whose Angle≈line.Angle);
LineString newLine=SimilarRoads.MiddleLine;
outPut.Add(newLine);
Else
outPut.Add(line);
End If
End For
通过上面的思路，得到了最终生成的新路网(图9)。
图9 最终生成的新路网
结果分析与讨论
图10 最终生成的新路网细节比对
上图(图10)列出了一些匹配正确的结果，这些新提取的道路已经很好的匹配到了现实中道路，达到了预期的目标，并且整个流程借助于索引与并行技术，耗时非常短，处理10万条数据包括预处理大概用时35s,这是非常高效的。
本文针对大数据量的步行轨迹数据，提出一个从志愿者GPS轨迹中提取路网的初步解决方案。该方案首先运用一些几何算法对轨迹数据进行简化，为提高运算效率对数据建立了空间索引，同时借助地图匹配原理优化轨迹的正确匹配，最后构建了一个新的路网。整个流程通过使用并行技术加速，使得整个流程处理的效率非常高。虽然结果精度有待进一步提高，但为以后更精确的轨迹路网匹配打下了基础，也提供了一些经验,这是一个非常有意义的尝试。为更好地满足大数据的处理需求，一个以后的研究中将进一步加强地图匹配方法的有效性，这是道路提取与更新的的核心所在。将这一课题研究下去的意义毋庸置疑，如果能够大幅度提高提取的精度，将为地图公司省下一大笔资金，这是非常有价值的。（宋雪涛 蒲英霞）
参考文献
[1] Fathi, A. and J. Krumm (2010). Detecting road intersections from gps traces. Geographic Information Science, Springer: 56-69.
[2] Haklay, M. and P. Weber (2008). "Openstreetmap: User-generated street maps." Pervasive Computing, IEEE7(4): 12-18.
[3] Schroedl, S., et al. (2004). "Mining GPS traces for map refinement." Data mining and knowledge Discovery9(1): 59-87.
[4] 陈漪 (2011). 基于 GPS 数据的城市路网立交桥识别技术研究, 吉林大学.
[5] 廖顺华,孔令才,周创熙(2007).GPS道路采集数据内业一体化处理技术.中国公路 ,(19);85-86
[6] 孟立秋. 地图为人人, 人人都制图[J]. 测绘科学技术学报, 2012, 29(5): 313-320.
[7] 田文文. 基于自发地理信息的空间数据变化发现与更新方法研究[D]. 武汉大学, 2013.
[8] Haklay M, Singleton A, Parker C. Web mapping 2.0: The neogeography of the GeoWeb[J]. Geography Compass, 2008, 2(6): 2011-2039.
[9] Guo T, Iwamura K, Koga M. Towards high accuracy road maps generation from massive GPS traces data[C]//Geoscience and Remote Sensing Symposium, 2007. IGARSS 2007. IEEE International. IEEE, 2007: 667-670.
[10] Cao L, Krumm J. From GPS traces to a routable road map[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009: 3-12.
[11] Goodchild M F. in the World of Web 2.0[J]. International Journal, 2007, 2: 24-32.
[12] Scharl A, Tochtermann K. The geospatial web: How geobrowsers, social software and the Web 2.0 are shaping the network society[M]. Springer, 2009.
[13] Grira J, Bédard Y, Roche S. Spatial data uncertainty in the VGI world: Going from consumer to producer[J]. Geomatica, 2010, 64(1): 61-72.
[14] 沈亿辉. 阻击卡特里娜飓风——GIS 志愿者为飓风救援提供协助[J]. 软件世界, 2006, 1: 41-43.
[15] Lou Y, Zhang C, Zheng Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009: 352-361.
[16] 李清泉,黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报, 2010, 39(2): 0-145.
[17] 顾军.常用空间索引技术的分析.微型电脑应用,2001,17(12);40-42.
[18] Greenfeld J S. Matching GPS observations to locations on a digital map[C]//National Research Council (US). Transportation Research Board. Meeting (81st: 2002: Washington, DC). Preprint CD-ROM. 2002.
[19] 王树良, 丁刚毅, 钟鸣. 大数据下的空间数据挖掘思考[J]. 中国电子科学研究院学报, 2013, 8(1): 8-17.
[20] 张振辉;崔铁军;姚慧敏;;车辆导航系统中地图匹配新算法[J];海洋测绘;2006年02期.
原标题：基于行人GPS轨迹的路网提取更新并行算法设计与实现
声明：中国勘测联合网登载此文出于传递更多信息之目的，并不意味着赞同其观点或证实其描述，文章内容仅供参考。
