基于众源轨迹数据的道路中心线提取

杨 伟,艾 廷 华

(武汉大学资源与环境科学学院，湖北 武汉 430079)

基于众源轨迹数据的道路中心线提取

杨 伟,艾 廷 华*

(武汉大学资源与环境科学学院，湖北 武汉 430079)

从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而，由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题，提出一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网，根据整体长边约束准则删除长边以提取道路面域多边形；然后对道路面多边形二次构建Delaunay三角网，提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验，将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10%以上。另外，以复杂环形道路为例，证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此，该方法不仅适合大数据处理、结果精度高,且算法成熟、易于实现。

众源轨迹数据；道路提取；道路中心线；Delaunay三角网

0 引言

道路地图数据是国家基础地理信息、智能交通的重要组成部分，在智慧城市建设、车辆智能导航、网络地图服务、地图数据更新等方面起着关键作用。然而，传统的道路网数据获取主要是专业测绘部门的实地测量、遥感影像的矢量化制图两种方式,不仅技术、成本要求高，且数据获取周期长、数据处理与维护工作量大，难以满足当前人们对路网数据高实时性、低成本的要求。因此，迫切需要一种经济适用、快速自动获取城市路网数据的新方法。

虽然道路提取取得了较多成果，但仍存在一些问题：1)算法相对复杂，面对海量的轨迹数据难以自动化、快速地提取道路中心线，并保证数据的几何拓扑精度。2)已有算法大多处理采样间隔1～4 s的高精度轨迹数据，并不适用于稀疏采样(采用间隔40 s)、高噪音轨迹数据。因此，本文从图论的角度引入Delaunay三角网模型，对加密轨迹线构建Delaunay三角网，利用Delaunay三角网的空间剖分特性、空间临近关系自动提取道路中心线。运用北京市出租车轨迹数据进行实验，提取了道路中心线几何数据，证明了该方法的有效性。

1 道路中心线提取流程及轨迹数据预处理

1.1 道路中心线提取流程

Delaunay三角网作为一种构建数据集拓扑关系的方法，广泛应用于模式识别、空间数据挖掘如数据聚类[20,21]、多边形提取中轴线[17,18,22]等领域。利用Delaunay三角网能很好地识别车辆轨迹数据沿道路网分布的条带状空间分布模式，并根据三角形的邻接关系快速提取道路中心线。故本文对加密轨迹线构建约束Delaunay三角网，利用约束Delaunay三角网特性提取道路中心线,提取方法流程如图1所示。约束Delaunay三角网生成算法很多，这不是本文研究的重点，本文利用ArcGIS提供的开发接口构建三角网。

图1 道路中心线提取流程Fig.1 The process of road centerline extraction

1.2 轨迹预处理及加密

由于车辆轨迹采样间隔稀疏、建筑物遮挡、GPS信号漂移等原因，导致大量的噪音轨迹数据且对道路中心线提取产生干扰。轨迹点预处理包括经纬度越界、时间格式不正确、轨迹点丢失等情况的处理；轨迹线预处理包括删除短轨迹线、删除轨迹线方向变化大且直接穿越不同道路的异常轨迹线。由于轨迹采样稀疏，如果直接对原始轨迹线构建约束Delaunay三角网则会破坏三角网的最邻近性特征，很难表征轨迹数据的空间分布模式并识别道路轮廓(图2a)。故本文将轨迹线进行加密以保证道路中心线提取的精度。轨迹线加密的规则为：首先确定加密步长阈值w，当轨迹线上相邻两轨迹点的距离大于阈值w时，则进行加密，反之不加密。本研究加密步长默认为道路平均宽度，也可根据需要设定。假设pi、pi+1是轨迹线上相邻的两轨迹点，当|pipi+1|>w时，则加密点(Qk)的横、纵坐标为：

(1)

图2 加密轨迹线构建Delaunay三角网Fig.2 Constructing Delaunay triangulation after the trajectory interpolated

2 基本原理与方法

2.1 道路面域多边形提取

作为一种新型复合调味品，鸡精成功运用了鲜味相乘的原理，实现了鲜度在味精基础上的成功翻倍。同时，由于添加了鸡肉等物质，鸡精尝起来更醇厚自然，更为重要的是鸡精只调鲜、不串味，能够很好地保留菜肴原本的味道。一个以鸡精为代表的鲜味时代也正式开启。

从轨迹线构建的Delaunay三角网中可看出轨迹线聚集的内部区域三角形分布密集、边长面积较小，而轨迹线簇外的三角形边长面积都较大。因此，三角网中三角形的边长可分为两类，位于道路外空白区域的长边和位于道路内部的短边。故只需删除Delaunay三角网的长三角形即可较好地识别道路面域轮廓，便于提取道路中心线。根据Delaunay三角网边长的统计特征，得出一种整体长边边长约束准则。三角形长边删除阈值由以下几个参数决定：

定义1 三角网整体边长均值： 由轨迹线簇Traj构建的Delaunay三角网DT(Traj)中，其所有边长的均值定义为整体边长均值，记为Global_Mean，即有：

(2)

式中:n表示Delaunay三角网中边的数量；|ei|表示第i条边的长度。

定义2 三角网整体边长变异： 给定一个图G(三角网)，所有边长的标准差定义为整体边长变异，记为Global_Variation，即有：

(3)

(4)

式中:n表示K阶邻域内边的数目；|ej|表示第j条边的长度。故在三角网中任意一个顶点pi(轨迹点)整体长边约束准则Global_CutValue(pi)，公式表示为：

Global_CutValue(pi)=Global_Mean(DT)+

(5)

图3 道路多边形提取Fig.3 Raw road polygon extraction

2.2 道路中心线提取

2.2.1 三角形类型确定及中心线提取 对提取的道路面多边形二次构建Delaunay三角网，并标记所有三角形的类型，目的是提取道路网中心线。根据三角形与道路多边形的邻接关系，可将三角形分为4类(图4):第0类三角形是位于多边形外部的三角形，是无效三角形，对于提取道路中心线没有意义;将位于多边形内部的三角形分为3类，第1类三角形只有1个邻接三角形，第2类有两个邻接三角形，第3类是该三角形3条边都有邻接三角形。从图4中可以看出不同类型三角形的分布规律，第1类三角形位于道路多边形出口、第3类三角形位于道路交叉口处、第2类三角形位于道路干线上，这种分布利于提取道路中心线。

图4 道路中心线提取方法Fig.4 The method of road centerline extraction

对于道路中心线的提取，首先判断三角形是否是有效三角形。对于有效三角形，如果是第1类三角形，提取桥接边(有邻接三角形的边)的中点和另外两边中较长一边的中点，如图4中的点p5、p4；如果是第2类三角形提取两个桥接边的中点，如图4中的点p3；如果是第3类三角形则需提取该三角形的重心和3条桥接边的中点，如图4中的点p1、Q1。故道路中心线提取算法：从任意一个1类或3类三角形出发依次按三角形的临近关系逐次搜索、按中心线提取原则依次提取相应节点，终止于1类或3类三角形，则得到一条道路网中心线，当所有的1类三角形作为出发或终止搜索过一遍，所有的3类三角形作为出发或终止搜索过三遍，道路网中心线提取完毕。

2.2.2 道路中心线小毛刺剔除 由于轨迹线数据的特殊性(轨迹线的方向变化、轨迹点的疏密程度等)，往往使得提取的道路面多边形边界不平滑，本文称为“多边形突刺”。多边形突刺则会导致出现图5a中的异常1类三角形，这种异常1类三角形往往导致更多异常的2类、3类三角形，这些异常三角形对道路中心线提取产生严重干扰。如图5b、图5c中提取的道路中心线出现了许多短小的分支中心线，这些分支中心线并不是真实的道路，本文称为“中心线小毛刺”,其是由道路多边形突刺在道路干道边界生成的1类异常三角形(1类三角形应分布在道路末端)所造成(图5a、图5c)。由于这种小毛刺的长度小于道路宽度,且这种线段起止点分别是第3类三角形和第1类三角形，故传统的解决方法是利用路宽的阈值删除小毛刺;但这种方法只适合于简单的道路结构，如遇到图5c中的复杂环形道路交叉口则会造成误删。故本文结合传统的方法，提出了一种新的解决策略，即基于面积阈值删除道路干道边界1类异常三角形。

图5 复杂道路交叉口处中心线提取Fig.5 Road centerline extraction in complex road intersection

通过统计分析发现，第1类三角形的面积大小呈两个极端分布:1)面积较小的由于道路边界突刺引起的异常1类三角形;2)面积较大的位于道路口末端的正常1类三角形。故根据面积大小阈值，结合三角网特性删除这些由道路边界突刺引起的三角形，最后只保留道路末端的正常1类三角形。面积阈值公式为：

AreaCutValue=MeanArea+α*StdDev

(6)

式中:AreaCutValue为面积删除阈值，MeanArea为Delaunay三角网中所有三角形的平均面积、α为自适应系数(默认为1)、StdDev为三角网中三角形面积的标准差。根据面积阈值不断删除异常1类三角形，直到道路网干道边界没有异常1类三角形为止。

2.2.3 道路网数据后处理 提取的道路中心线在第3类三角形处往往出现节点接头处断开、道路中心线节点在面积较大的第2类三角形处出现角度突变(图6)，这不符合常规电子地图与矢量数据的标准，故须对提取的道路中心线几何数据进行优化处理,包括道路中心线的光滑处理与位于第3类三角形处的道路节点的合并优化。道路中心线由一些列节点构成，故采用最小二乘法进行直线拟合，得到平滑的道路中心线：y=ax+b，其中:

(7)

由于第3类三角形的重心在道路网络图中始终连接3条道路网络边，故凡是十字道路交叉口都变成了两个“V”字形连接(图6a)。这种连接现象都发生在相邻的两个第3类三角形处，故本文通过找出起止点都为第3类三角形重心的线段，删除该线段，用这两个相邻的第3类三角形的公共边的中点代替，这样就得到了正确路网数据(图6b)。

图6 道路中心线优化处理Fig.6 The centerline optimization processing

3 实验分析与结果评价

3.1 实验数据集与实验环境

出租车GPS轨迹数据来源于微软研究院郑宇团队的TDriver数据[23]，为北京城区2008年2月3日一天的出租车轨迹数据。其中出租车轨迹数据包括车辆标识ID、GPS时间、GPS经度、GPS纬度等信息。轨迹点采样间隔为 5～60 s不等，共有轨迹点3 055 105个，生成轨迹线124 506条，预处理后为45 768条(图7)。为验证本文提出的道路中心线提取方法，本文在P4/2G/1G/Win7环境下，基于ArcGIS平台采用C#编程语言开发了基于众源时空轨迹数据的道路中心线提取实验系统，在此系统的支持下从北京市一天的出租车GPS轨迹中提取道路中心线。

3.2 实验结果分析

对预处理后的出租车轨迹线构建约束Delaunay三角网，根据整体长边约束准则(式(5))删除长边，提取道路面粗轮廓多边形；然后对道路面多边形二次构建Delaunay三角网，提取道路中心线。以北京市五环内轨迹数据为例，提取的道路中心线如图8所示，路名数据从微博签到轨迹数据中提取。

图7 研究区域及轨迹线Fig.7 Study area and trajectory line

3.2.1 实验结果定性定量评价 本文借鉴文献[19]中的方法，将提取的道路几何数据与OSM电子地图[24]、OSM道路网矢量数据[24]叠加比较，进行定性评价。图8中提取的道路中心线几何数据基本与实地道路相符合，尤其对于轨迹数据密度较高的道路区域，提取的道路中心线几何拓扑精度较高。

为了定量评价实验结果，将本方法实验结果与文献[5]中栅格化方法实验结果对比分析。采用文献[25]中提出的缓冲区检测方法评价道路中心线数据的几何精度。以OSM道路矢量数据为参考，分别建立2 m、5 m、7 m为半径宽度的缓冲区，计算落入缓冲区的道路中心线长度并统计百分比。利用ArcGIS的拓扑检查工具找出拓扑正确道路数量与拓扑错误道路数量，统计百分比。如表1所示，本文方法所提取的道路中心线数据在几何精度、拓扑正确性方面都比栅格化方法有较大提高，特别在2 m缓冲区的高精度结果有约30%的提升。

图8 道路网数据与OSM电子地图叠加比较Fig.8 Road centreline extraction and the comparison with OSM map

表1 实验结果评价Table 1 The evaluation of experiment results

3.2.2 复杂环形道路实验结果评价 本文方法通过设置长边约束准则中的调节系数α参数值，帮助识别不同路网结构、不同轨迹密度分布的道路面域轮廓。尤其对于复杂环形道路的中心线提取，能较好地区别路面与空白区域，从而保证道路中心线的拓扑正确性。如图9所示，本文方法能正确区分环形道路中的小空白区域(图9b)、距离较近的双干道等复杂案例；反之，如图9c所示，栅格化方法将环形道路空白区域错误识别为道路，从而导致道路中心线的拓扑错误。当然该方法对于不同的轨迹数据需要实验找出不同的调节参数，另外该方法也不能对道路边界进行精确识别，这是下一步的研究重点。从时间性能效率方面看，Delaunay三角网模型的实现算法已较成熟、稳定，其时间复杂度为(nlogn)[20]，完全适用于大数据处理；并且可以在较多的开源软件(如QGIS等)以及主流的GIS软件(如ArcGIS等)平台中实现，快速投入地图数据生产，所以本方法与其他道路中心线提取算法相比更简便、快速且易于实现。

4 结论与展望

图9 复杂环形道路提取结果对比Fig.9 Comparison of the results extracted from complex ring road

为了快速准确地从众源轨迹数据中提取道路几何数据，本文提出了一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网，根据整体长边约束准则删除长边提取道路面粗粒度轮廓多边形；然后对道路面多边形二次构建Delaunay三角形，提取道路中心线。利用北京市一天时间的出租车轨迹数据进行实验分析，用OSM道路网矢量数据作为参考数据，与栅格化方法实验结果进行定性定量的对比评价。结果证明本文方法提取的道路中心线数据在几何、拓扑精度方面都比栅格化方法高，并且本方法在处理复杂道路结构、较大密度差异的轨迹数据时比栅格化方法更显优势。另外，本方法算法易于实现且适合大数据处理。

本研究还需要深入完善的内容主要包括：1)更精确地提取道路面域数据。本研究中只识别了道路面域的粗轮廓，其结果并不精确；同时对于密度差异较大的轨迹数据，本文方法还需要改进，特别对于城市内部小区级别的道路提取需要深入研究。2)道路数据不仅包括道路中心线数据，还包括道路面、车道、路名等数据，故在后续工作中，将设计不同算法并融合不同类型的VGI轨迹数据以提取更丰富的道路几何数据与属性数据。

[1] GOODCHILD M F.Citizens as sensors:The world of volunteered geography[J].GeoJournal,2007,69(4):211-221.

[2] ANMED M,KARAGIORGOU S,PFOSER D,et al.A comparison and evaluation of map construction algorithms using vehicle tracking data[J].GeoInformatica,2015,19(3):601-632.

[3] EDELKAMP S,SCHRODL S.Route planning and map inference with global positioning traces[A].Computer Science in Perspective[C].Springer Berlin Heidelberg,2003.128-151.

[4] GUO T,IWAMURA K,KOGA M.Towards high accuracy road maps generation from massive GPS traces data[A].2007 IEEE International Geoscience and Remote Sensing Symposium[C].2007.

[5] ZHANG L,THIEMANN F,SESTER M.Integration of GPS traces with road map[A].Proceedings of the Second International Workshop on Computational Transportation Science[C].ACM,2010.17-22.

[6] CAO L,KRUMM J.From GPS traces to a routable road map[A].Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].ACM,2009.3-12.

[7] KARAGIORGOU S,PFOSER D.On vehicle tracking data-based road network generation[A].Proceedings of the 20th International Conference on Advances in Geographic Information Systems[C].ACM,2012.89-98.

[8] KARAGIORGOU S,PFOSER D,SKOUTAS D.Segmentation-based road network construction[A].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].ACM,2013.460-463.

[9] LI J,QIN Q,XIE C,et al.Integrated use of spatial and semantic relationships for extracting road networks from floating car data[J].International Journal of Applied Earth Observation and Geoinformation,2012,19:238-247.

[10] 唐炉亮,刘章,杨雪,等.符合认知规律的时空轨迹融合与路网生成方法[J].测绘学报,2015,44(11):1271-1276.

[11] CHEN C,CHENG Y.Roads digital map generation with multi-track GPS data[A].Education Technology and Training,2008[C].2008 International Workshop on Geoscience and Remote Sensing,2008,1:508-511.

[12] XIE X,BING-YUNG W K,AGHAJAN H,et al.Inferring directed road networks from GPS traces by track alignment[J].ISPRS International Journal of Geo-Information,2015,4(4):2446-2471.

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

[14] LIU X,BIAGIONI J,ERIKSSON J,et al.Mining large-scale,sparse GPS traces for map inference:Comparison of approaches[A].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2012.669-677.

[15] WU J,ZHU Y,KU T,et al.Detecting road intersections from coarse-gained GPS traces based on clustering[J].Journal of Computers,2013,8(11):2959-2965.

[16] WANG J,RUI X,SONG X,et al.A novel approach for generating routable road maps from vehicle GPS traces[J].International Journal of Geographical Information Science,2015,29(1):69-91.

[17] 艾廷华,郭仁忠.基于约束 Delaunay 结构的街道中轴线提取及网络模型建立[J].测绘学报,2000,29(4):348-354.

[18] 李功权,蔡祥云.一种基于约束三角网的道路中心线的提取方法[J].长江大学学报(自然科学版:理工卷),2013(2):47-50.

[19] LI J,QIN Q,HAN J,et al.Mining trajectory data and geotagged data in social media for road map inference[J].Transactions in GIS,2015,19(1):1-18.

[20] ESTIVILL-CASTRO V,LEE I.Multi-level clustering and its visualization for exploratory spatial analysis[J].GeoInformatica,2002,6(2):123-152.

[21] 李光强,邓敏,刘启亮,等.一种适应局部密度变化的空间聚类方法[J].测绘学报,2009,38(3):255-263.

[22] 艾廷华,郭仁忠.支持地图综合的面状目标约束Delaunay三角网剖分[J].武汉测绘科技大学学报,2000,25(1):35-41.

[23] YUAN J,ZHENG Y,ZHANG C,et al.T-drive:Driving directions based on taxi trajectories[A].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].ACM,2010.99-108.

[24] http://www.openstreetmap.org.2015-10-31.

[25] GOODCHILD M F,HUNTER G J.A simple positional accuracy measure for linear features[J].International Journal of Geographical Information Science,1997,11(3):299-306.

Road Centerline Extraction from Crowdsourcing Trajectory Data

YANG Wei，AI Ting-hua

(SchoolofResourceandEnvironmentalSciences,WuhanUniversity,Wuhan430079,China)

Compared with traditional method,road centerline extraction from crowdsourcing trajectory data offers numerous advantages with respect to labor cost,real-time and data completeness.However,it is difficult to construct road network using big crowdsourcing trajectory data due to the trajectory data with sampling sparse and large data volume and high noise.For this issue,this study tries to explore the question of road centerline extraction by large volume of taxi GPS trajectory data,presenting a new method based on Delaunay triangulation model.The whole method includes three steps.The first one is to pre-process the vehicle trajectory data including the point anomaly removing and the conversion of trajectory point to track line.Secondly,construct Delaunay triangulation within the vehicle trajectory line to detect neighborhood relation.And then,the road coarse polygon is extracted by cutting long triangle edge and organizing the polygon topology.Considering the case that some of the trajectory segments are too long,a interpolation measure is used to add more points for the improved triangulation.Thirdly,construct Delaunay triangulation within the road polygon to extract the road centerline.The centerline is extracted by distinguishing three kinds of triangles and processing the road junction.The experiment is conducted using one day of taxi track in Beijing City.Compared with conventional methods(raster),experimental results demonstrate that the accuracy of road geometry and topology is improved above 10 percent through the use of the method in this paper.Moreover,the complex ring road is used as a case study to test the proposed method.Experimental results prove that the proposed method is more suitable for complex road structure and trajectory data with different density.As a result,the results achieved with the proposed method show that road centerline can be generated with low cost,high efficiency,good maneuverability,based on crowdsourcing trajectory data,and be very useful for mapping application.

crowdsourcing trajectory data；road extraction；road centerline；Delaunay triangulation

2015-12-17；

2016-02-15

国家自然科学基金资助项目(41531180)；国家高技术研究发展计划(863计划)资助项目(2015AA1239012)

杨伟(1987-)，男,博士研究生，研究方向为时空数据挖掘与可视化。*通讯作者E-mail：tinghua_ai@163.net

10.3969/j.issn.1672-0504.2016.03.001

U495;P208

A

1672-0504(2016)03-0001-07