欧阳鸿，刘建勋，刘毅志，廖祝华，陈佘喜

(湖南科技大学知识处理与网络化制造湖南省普通高等学校重点实验室，湖南 湘潭 411201)

0 引言

电子地图是构建智能交通系统的基础，因此，准确提取和及时更新其中的路网信息，对于道路规划和车辆导航等方面至关重要。传统的路网提取方法主要分为实地测绘方法和基于遥感影像的生成方法两种。前者准确率较高，但耗时耗力;后者能够自动生成路网，但准确率较低，且影像的更新周期较长。随着全球定位系统(GPS)信号记录仪的广泛普及，人们可以方便快捷地获取越来越精确的GPS数据。所以，基于GPS轨迹的路网提取方法成为了当前的研究趋势，引起了学术界与工业界的共同关注。

得益于城市出租车监控的需要，人们获取了大量的出租车运行轨迹数据，使得基于浮动车或出租车的GPS轨迹的路网提取方法成为可能。目前，这一方面已开展大量探索性研究工作，例如:Cao等［1］模拟物理学中的引力和斥力对GPS轨迹进行优化处理，增量式地生成表达路网信息的曲线图;Schroedl等［2］提出一种类似K-means算法的路网提取方法，并引用最小二乘法拟合道路中心线;Zhang等［3］提出一种路网更新方法，通过融合大量的GPS轨迹来增强已有路网信息的精确性;蒋益娟等［4］利用图像细化算法获取路网的骨架信息，再通过矢量化方式构建道路网络。由于车辆行驶对道路宽度的需求，现有数据与方法难以支持小路(Pathway)或支路(Branch)等的自动提取。随着内嵌GPS定位功能的智能手机以及移动互联网的普及，基于智能手机的位置服务得到广泛应用，大量的步行GPS轨迹数据将可方便获取。利用步行的GPS轨迹数据自动提取路网，不但可成为已有基于车辆GPS轨迹的路网提取的补充(例如:应用于车辆无法涉及的小路与支路的自动提取)，还可应用于抗震救灾、小区导航或乡村游览。例如，地震时利用步行GPS轨迹来提取各可通行小路，能够有效地帮助人们在道路损毁的城市中开展救援工作。

为此，本文提出基于步行GPS轨迹的路网提取方法。它分为数据预处理、道路中心线生成和路网精度评价3个部分。本文工作的主要贡献有:

(1)将步行GPS轨迹用于小路提取。据笔者所知，该方法尚属首次采用。(2)它有助于路网的及时更新。一般来说，新修道路尚未投入使用时，尽管车辆无法通行，可是通常已有行人来往了。此外，由于步行速度较慢，相对于车载GPS，本文方法在较短时间内能够获取较多的 GPS数据。因此，依据步行GPS轨迹能够更加及时地更新路网。

1 本文方法的框架

本文依据步行GPS轨迹所记录的经纬度信息，设计并实现了一种路网提取的方法，可及时更新与校正当前电子地图的路网信息。其框架图如图1所示。

首先，通过数据预处理去除原始GPS轨迹的异常值，确保轨迹数据的精确性。然后，利用GPS轨迹自动地生成道路中心线，并进行路网的矢量化处理。最后，以百度地图等相关信息为参考路网，分别从定性与定量两方面对本文方法的路网提取性能进行评价。其中，道路中心线生成方法包括轨迹点聚类、聚类点分割和中心线拟合3个部分，即:先把预处理后的GPS轨迹点进行聚类以此来获取聚类点，实际上起到了稀疏轨迹样本点的作用;然后，依据这些聚类点的转角大小以及相邻聚类点之间的距离间隔对其进行分割，用于确定道路的拟合顺序;再引用准均匀B样条曲线进行道路拟合，最终生成道路中心线。

图1 本文方法的框架图

2 本文的路网提取方法

2.1 数据预处理

GPS设备在记录移动对象的位置信息时，由于受随机噪音和误差的影响而产生冗余等错误类型的数据，直接影响了算法运行的效率与路网提取的质量。数据预处理是下一步路网提取的基础和前提，主要包括消减冗余数据、去除停滞点和轨迹平滑等3个步骤。

(1)消减冗余数据。当GPS接收机的信号突然中断时，其在短时间内会重复记录最后收到的定位数据。在低速运动时，GPS接收机仍会依据设定的采集频率接收定位数据。这些不必要的、大量冗余的定位数据，严重干扰了路网提取算法的效率。设相邻轨迹点pi与 pi+1，如果其距离 Di小于阈值Dmin，则表明这些记录是无效的。因此，对于这种类型的错误数据应该予以删除。

图2 去除停滞点示意图

(2)去除停滞点。当移动对象在某位置点的移动速度很慢(甚至停顿)时，在其周围可能出现大量杂乱的GPS数据，本文称该位置点为停滞点。为了去除这类错误数据，本文借鉴Zhou等［5］的DJ-Cluster密度聚类算法，即:分别设定聚类半径和轨迹点数量的阈值，通过聚类方法去除高密度区域内的所有轨迹点数据。图2中明显可见，该方法可以有效地去除停滞点这一类错误数据。

图3 轨迹平滑处理示意图

(3)轨迹平滑处理。通过滤波处理可以消除GPS轨迹部分的随机误差，达到平滑原始GPS轨迹的效果，保证了轨迹整体的相对平滑性，如图3所示。本文采用高斯滤波方法来平滑数据，滤波参数设计为GPS设备采样频率的5倍，避免了对正常轨迹点产生不必要的影响［6］。高斯滤波计算公式如式(1)所示:

其中，x'与y'为经过平滑运算的坐标值，k(ti)为高斯核函数。

2.2 道路中心线的自动生成

本文的路网提取方法其基本思路是依据GPS轨迹自动地生成道路中心线。它包括轨迹点聚类、聚类点分割和中心线拟合3个部分。其过程和算法详细介绍如下。

(1)轨迹点聚类。轨迹数据基本都是沿着道路分布，因而本文设计了一种滚动式聚类算法，即沿着轨迹数据的延伸方向来获取聚类点。设定轨迹点数量m和聚类半径d，以此为聚类的约束条件。如果每个轨迹点其d邻域内的点数量大于m，则通过聚类算法将d邻域内包含的轨迹点转化为聚类点。聚类点的坐标值由该邻域内所有的轨迹点共同决定。

(2)聚类点分割。聚类点分割的目标在于使分割后的每段聚类点都可以用一个曲线函数来拟合，以便得到一条曲线来表示相应的道路中心线。本文中，分割的依据是由聚类点的转角大小以及相邻聚类点之间的距离间隔来决定。转角的大小反映了轨迹方向的变化程度，转角过大的聚类点亦被称为拐点［7］。通过分割聚类点，能够有效地保持路网的局部特征，同时又不会丢失路网的全局信息。

(3)中心线拟合。由于道路的形状存在一定的复杂性，故本文采用了准均匀B样条曲线拟合方法，生成可以表示道路中心线的曲线。与B样条曲线相比，准均匀B样条曲线克服了首尾端点不在曲线上这一缺点，即在其首尾端点处做N重复度处理。同时也具有局部修改性和更逼近特征多边形的特点，得到的目标曲线是光滑分段多项式函数。其数学表达式如式(2):

其中，Pi(i=0，1，…，n)是控制多边形的顶点(简称控制顶点)，Ni，k(t)(i=0，1，…，n)为 B 样条基函数。

道路中心线生成算法如图4所示。

图4 道路中心线生成算法

3 实验结果与分析

本文数据选自湖南科技大学步行巡检GPS数据集［8-9］。其采集时间是2011年3月至6月，参与的保安人员为11人，覆盖着整个校园包括南北校区的教学区、行政办公区、职工家属小区和学生宿舍区等，面积达3千余亩。其采样频率为每秒一次，数据大小约1.44 GB，以CSV格式保存，共有1746万个轨迹点，主要包括经度、纬度、时间等属性。

本文在湖南科技大学的南校区区域内随机选取约18万个轨迹点(约17 MB)。实验机器配置为:英特尔i3 550 3.2 GHz双核处理器、2 GB内存，在Mat-lab 2010+ArcGIS 9.3环境下实现。

图5 本文方法的实现过程示意图

分析轨迹点的空间分布特征，利用GPS轨迹点自动地生成道路中心线。直接使用ArcGIS软件提供的矢量化工具转化成线形矢量文件，再通过坐标转换和配准，即可得到同一坐标系统下的矢量化路网信息。图5(a)为预处理之前的原始GPS轨迹数据，图5(b)为预处理之后的轨迹数据，图5(c)为聚类之后的GPS聚类点，图5(d)为道路中心线拟合之后的结果图。为了评价本文方法的路网提取性能，以百度地图等相关信息为参考路网，然后分别从定性与定量两方面进行评价。

(1)定性评价。其基本思路是将本文实验结果与参考路网进行图层叠加对比分析。图6(a)为本文实验结果与Google Earth卫星地图的比较图，图6(b)为与百度地图路网的比较图。在图6(b)中，虚线条表示百度地图路网，另外3种线条都表示提取的路网信息，分别对应着实际路网中的历史道路、新增小路、新增主干道。从整体来看，本文提取的路网和现有的路网结构基本一致，但是通过局部的比较可发现，新增的道路信息是现有路网结构所缺少的部分。经过实地调查发现，其系因现有的电子地图尚未更新该片区域新修建的道路所致。这亦说明基于步行GPS轨迹的路网提取方法不但可以更新现有路网的主干道信息，而且能够挖掘出小路信息，这点是车载GPS轨迹所不具备的优势。

(2)定量评价。其基本思路是获取实验结果与百度地图路网相互匹配的路网集合，然后引用覆盖率α和误检率β来评价本文方法的路网提取性能［10］。其定义如式(3)、(4)所示。

其中，φ 表示百度路网集合，φ ={P1，P2，…，Pk}，ψ 表示实验结果的路网集合，σ为两者相互匹配的路网集合，len(P)表示路网的长度。

图6 本文方法的定性评价

本文借鉴Zhang等［3］提出的缓冲区方法，以百度地图路网为缓冲分析的对象，分别获取各缓冲半径内本文提取的路网与百度地图路网两者相互匹配的路网集合。由文献［11］可知，商业地图OpenStreetMap(OSM)与实际道路相应的间隔主要分布在［-10，10］米(m)之间，因而可认为本文采用的缓冲半径阈值是在合理的范围之内。百度地图路网的总长度为4992.24 m，本文提取的路网长度为 6140.83 m，其中新增的主干道信息为839.86 m，新增的小路信息为338.87 m。

如表1所示，缓冲半径为10 m时，本文方法的路网覆盖率和误检率分别为98.73%、18.84%。通过图6(b)可发现，本文方法误检率过高的一个主要原因是百度地图路网中没有更新的道路在本文的方法中被识别出来。忽略未在百度地图路网中及时更新的新增道路，误检率则由18.84%减小到3.26%。因此，本文方法能有效进行路网更新。

表1 本文方法的定量评价结果

4 结束语

路网信息的准确提取和及时更新，对于道路规划和车辆导航等方面至关重要。本文提出基于步行GPS轨迹的路网提取方法，能够根据GPS数据自动提取小路或支路等。实验结果表明:本文方法的误检率仅3.26%，覆盖率可达96.21%;能够准确提取小路和更新路网。

［1］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.2009:3-12.

［2］Schroedl S，Wagstaff K，Rogers S，et al.Mining GPS traces for map refinement［J］.Data Mining and Knowledge Discovery，2004，9(1):59-87.

［3］Zhang L，Thiemann F，Sester M.Integration of GPS traces with road map［C］//Proceedings of the 2nd International Workshop on Computational Transportation Science.2010:17-22.

［4］蒋益娟，李响，李小杰，等.利用车辆轨迹数据提取道路网络的几何特征与精度分析［J］.地球信息科学学报，2012，14(2):165-170.

［5］Zhou C，Frankowski D，Ludford P，et al.Discovering personal gazetteers:An interactive clustering approach［C］//Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems.2004:266-273.

［6］Yan Z，Parent C，Spaccapietra S，et al.A hybrid model and computing platform for spatio-semantic trajectories［C］//Proceedings of the 7th International Conference on the Semantic Web:Research and Applications.2010:60-75.

［7］袁冠，夏士雄，张磊，等.基于结构相似度的轨迹聚类算法［J］.通信学报，2011，32(9):103-110.

［8］Li H，Liu J，Liu Y，et al.Evaluating roving patrol effectiveness by GPS trajectory［C］//Proceedings of the 9th International Conference on Dependable，Autonomic and Secure Computing.2011:832-837.

［9］李欢欢，刘建勋，刘毅志.基于轨迹数据挖掘的保安绩效考核模型研究［C］//第七届和谐人机环境联合学术会议(HHME2011)论文集.北京:清华大学出版社，2011:314-319.

［10］Liu X，Zhu Y，Wang Y，et al.RoadRecognition Using Coarse-grained Vehicular Traces［R］.Technical Report HPL-2012-26，HP Laboratories，2012.

［11］Wang Y，Zhu Y，He Z，et al.Challenges and Opportunities in Exploiting Large-scale GPS Probe Data［R］.Technical Report HPL-2011-109，HP Laboratories，2011.