基于众源轨迹数据的道路中心线提取-杨伟.pdf

《基于众源轨迹数据的道路中心线提取-杨伟.pdf》由会员分享，可在线阅读，更多相关《基于众源轨迹数据的道路中心线提取-杨伟.pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第32卷第3期2016年5月地理与地理信息科学Geography and Geo-Inormation ScienceV0132 No3Mav 2016doi：103969jissn16720504201603001基于众源轨迹数据的道路中心线提取杨伟，艾廷华。(武汉大学资源与环境科学学院，湖北武汉430079)摘要：从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而，由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题，提出一种基于约束Detaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Dela

2、unay三角网，根据整体长边约束准则删除长边以提取道路面域多边形；然后对道路面多边形二次构建Ddaunay三角网，提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验，将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10以上。另外，以复杂环形道路为例，证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此，该方法不仅适合大数据处理、结果精度高，且算法成熟、易于实现。关键词：众源轨迹数据；道路提取；道路中心线；Delaunay三角网中图分类号：U495；P208 文献标识码：A 文章编号：16

3、720504(2016)03-0001-070引言道路地图数据是国家基础地理信息、智能交通的重要组成部分，在智慧城市建设、车辆智能导航、网络地图服务、地图数据更新等方面起着关键作用。然而，传统的道路网数据获取主要是专业测绘部门的实地测量、遥感影像的矢量化制图两种方式，不仅技术、成本要求高，且数据获取周期长、数据处理与维护工作量大，难以满足当前人们对路网数据高实时性、低成本的要求。因此，迫切需要一种经济适用、快速自动获取城市路网数据的新方法。目前，随着无线传感器与定位技术(如GPS、无线蜂窝网、RFID等)的发展与普及，产生了海量的出租车轨迹数据、微博签到轨迹、个人出行轨迹等VGI轨迹大数据1。

4、车行GPS轨迹数据是对车辆行驶路径的完整记录，蕴含了丰富的道路信息(如车道、转弯、限速、路宽、道路交叉口等)，直接反映了道路网络的几何特征。因此，利用车辆GPS轨迹快速自动地提取道路中心线几何数据，并实时构建、更新道路电子地图已成为可能。从GPS轨迹数据中自动提取道路几何数据已取得了不少研究成果L2。基于GPS轨迹的道路中心线提取方法分为3类：一是轨迹点聚类方法，如Edelkamp等3j提出了一种受限制的KMeans聚类算法，从车辆轨迹中提取道路中心线；GuoL州、Zhang等51将KMeans聚类与高斯模型相结合提取道路中心线并识别车道；但聚类方法不适合当前高噪音、稀疏采样的出租车GPS轨迹

5、。二是轨迹增量合并方法，如Cao等6基于物理力学思想剔除轨迹噪音，根据轨迹运动方向提取道路中心线；Karagiorgou等7提出了TraceBundle算法，对交叉口处的道路数据提取做了深入研究，并基于此又提出了TraceConflatiOn8算法，根据轨迹速度分割轨迹，生成不同图层，最后融合图层提取道路中心线；I。i等19j通过合并聚类轨迹线提取道路中心线，但该算法需要在道路交叉口处进行人工交互处理。唐炉亮等103提出了符合人类空间认知规律的路网生成方法，但该方法难以处理采样稀疏、高噪音的GPS轨迹数据。三是核密度估计与图像形态学方法，如ChenEll、ShiEl2、蒋益娟等一13利用图像处

6、理技术将轨迹点转为二值图像，利用形态学方法提取道路骨架线构建路网地图；Liu等14j将核密度估计(KDE)方法与KMeans聚类方法相结合提取路网数据。WuEl5、Wang等E16利用聚类、机器学习、概率统计等方法对道路交叉口的几何数据提取做了深入研究。另外，艾廷华等L17利用Delaunay三角网从街道多边形中提取街道中轴线；李功权等18从道路多边形中提取道路中心线以构建路网地图；Li等19从Fliekr照片地址数据中提取路名，并与提取的道路中心线收稿日期：20151217；修回日期：201602一15基金项目：国家自然科学基金资助项目(41531180)；国家高技术研究发展计划(863计划

7、)资助项目(2015AAl239012)作者简介：杨伟(1987一)，男，博士研究生，研究方向为时空数据挖掘与可视化。*通讯作者Email：tinghua_ai163net万方数据第2页 地理与地理信息科学 第32卷相融合，但该算法不适合快速提取道路，且仍需要大量人工干预。虽然道路提取取得了较多成果，但仍存在一些问题：1)算法相对复杂，面对海量的轨迹数据难以自动化、快速地提取道路中心线，并保证数据的几何拓扑精度。2)已有算法大多处理采样间隔14 S的高精度轨迹数据，并不适用于稀疏采样(采用间隔40s)、高噪音轨迹数据。因此，本文从图论的角度引入Delaunay三角网模型，对加密轨迹线构建Del

8、aunay三角网，利用Delaunay三角网的空间剖分特性、空间临近关系自动提取道路中心线。运用北京市出租车轨迹数据进行实验，提取了道路中心线几何数据，证明了该方法的有效性。1道路中心线提取流程及轨迹数据预处理11道路中心线提取流程Delaunay三角网作为一种构建数据集拓扑关系的方法，广泛应用于模式识别、空间数据挖掘如数据聚类20,21、多边形提取中轴线171822等领域。利用Delaunay三角网能很好地识别车辆轨迹数据沿道路网分布的条带状空间分布模式，并根据三角形的邻接关系快速提取道路中心线。故本文对加密轨迹线构建约束Delaunay三角网，利用约束Delaunay三角网特性提取道路中心

9、线，提取方法流程如图1所示。约束Delaunay三角网生成算法很多，这不是本文研究的重点，本文利用ArcGIS提供的开发接口构建三角网。输入：出租车GPS轨迹轨迹预处理，生成轨迹线 多边形二次构建约束DTN轨迹线构建约束DTN 中心线提取，剔除小毛刺整体长边约束，识别道路轮蒯l 道路中心线后处理输出：道路中心线图1道路中心线提取流程Fig1 The proee蟠of road centerline extraction12轨迹预处理及加密由于车辆轨迹采样间隔稀疏、建筑物遮挡、GPS信号漂移等原因，导致大量的噪音轨迹数据且对道路中心线提取产生干扰。轨迹点预处理包括经纬度越界、时间格式不正确、轨迹

10、点丢失等情况的处理；轨迹线预处理包括删除短轨迹线、删除轨迹线方向变化大且直接穿越不同道路的异常轨迹线。由于轨迹采样稀疏，如果直接对原始轨迹线构建约束Delaunay三角网则会破坏三角网的最邻近性特征，很难表征轨迹数据的空间分布模式并识别道路轮廓(图2a)。故本文将轨迹线进行加密以保证道路中心线提取的精度。轨迹线加密的规则为：首先确定加密步长阈值W，当轨迹线上相邻两轨迹点的距离大于阈值W时，则进行加密，反之不加密。本研究加密步长默认为道路平均宽度，也可根据需要设定。假设户i、pm是轨迹线上相邻的两轨迹点，当I PiP州I硼时，则加密点(Q)的横、纵坐标为： 以一哿I+A，挑=哿1+2(1)一弘一

11、、1 J其中：Atn历丢蒜忌一1，2，咒)。如图2b所示，加密轨迹线构建的约束Delaunay三角网能较好表征轨迹数据的空间分布，识别道路外部轮廓。21道路面域多边形提取从轨迹线构建的Delaunay三角网中可看出轨迹线聚集的内部区域三角形分布密集、边长面积较小，而轨迹线簇外的三角形边长面积都较大。因此，三角网中三角形的边长可分为两类，位于道路外空白区域的长边和位于道路内部的短边。故只需删除Delaunay三角网的长三角形即可较好地识别道路面域轮廓，便于提取道路中心线。根据Delaunay三角网边长的统计特征，得出一种整体长边边长约束准则。三角形长边删除阈值由以下几个参数决定：定义1 三角网整

12、体边长均值：由轨迹线簇Traj构建的Delaunay三角网DT(Traj)中，其所有边长的均值定义为整体边长均值，记为GlobalMean，即有：Global_Mean(G)=k局 (2)n ，式中：行表示Delaunay三角网中边的数量；I ei I表示第i条边的长度。定义2三角网整体边长变异：给定一个图G万方数据第3期 杨伟等：基于众源轨迹数据的道路中心线提取 第3页(三角网)，所有边长的标准差定义为整体边长变异，记为GlobaLriation，即有：k I-Global_Mean(G)2bal_Vari盘tion(G)一LF广一(3)定义3 K阶领域边长均值：给定一个图G(三角网)，户?

13、为图G的一个顶点，其K阶领域内所有Delaunay三角形边长的均值定义K阶邻域边长均值，记为Mean：，即有：Mear巷(p，)一妻k I厶 (4)，|式中：船表示K阶邻域内边的数目；k J表示第歹条边的长度。故在三角网中任意一个顶点Pi(轨迹点)整体长边约束准则Global_CutValue(P。)，公式表示为：Global_CutValue(p。)=Global_Mean(DT)+口Globa，l_M】ea，n(D、T)一c；。balYariaio押(DT) (5)u ， ， 、 叫1， u，式中：Meank(pi)表示与点Pi直接连接的边长均值；口垡笔等表示自适应约束算子，其旨在适用轨迹

14、数据分布的不均匀性；对于轨迹线簇外部的边，约束算子的值较小，则约束准则较严格，对于轨迹线簇内部的边，约束算子的值较大，则约束准则较宽松。口表示调节系数，默认为1，也可根据需要设定，口值越大，整体约束越宽松，反之则越严格，本文实验a取值为2。故对于由轨迹线构建的Delaunay三角网中任一顶点Pi与直接相邻接的边，长度大于或等于GlobalCutValue(p。)，则为整体长边，应当删除。当然不同的调节系数对道路面提取的最终结果将产生较大影响。如图3a所示，为删除整体长边后保留的三角网即是道路面多边形区域。将删除长边后保留的三角形合并为一个多边形，即是道路面多边形，如图3b所示。a)整f本长边删

15、豫k的三角悯 h)遵口*多边彤轮哪以90图3道路多边形提取Fig3 Raw road polygon extraction22道路中心线提取221三角形类型确定及中心线提取对提取的道路面多边形二次构建Delaunay三角网，并标记所有三角形的类型，目的是提取道路网中心线。根据三角形与道路多边形的邻接关系，可将三角形分为4类(图4)：第0类三角形是位于多边形外部的三角形，是无效三角形，对于提取道路中心线没有意义；将位于多边形内部的三角形分为3类，第l类三角形只有1个邻接三角形，第2类有两个邻接三角形，第3类是该三角形3条边都有邻接三角形。从图4中可以看出不同类型三角形的分布规律，第1类三角形位于

16、道路多边形出口、第3类三角形位于道路交叉口处、第2类三角形位于道路干线上，这种分布利于提取道路中心线。图4道路中心线提取方法Fig 4 The method of road centerline extraction对于道路中心线的提取，首先判断三角形是否是有效三角形。对于有效三角形，如果是第1类三角形，提取桥接边(有邻接三角形的边)的中点和另外两边中较长一边的中点，如图4中的点户j、P。；如果是第2类三角形提取两个桥接边的中点，如图4中的点P。；如果是第3类三角形则需提取该三角形的重心和3条桥接边的中点，如图4中的点P。、Q1。故道路中心线提取算法：从任意一个1类或3类三角形出发依次按三角形

17、的临近关系逐次搜索、按中心线提取原则依次提取相应节点，终止于1类或3类三角形，则得到一条道路网中心线，当所有的1类三角形作为出发或终止搜索过一遍，所有的3类三角形作为出发或终止搜索过三遍，道路网中心线提取完毕。222道路中心线小毛刺剔除 由于轨迹线数据的特殊性(轨迹线的方向变化、轨迹点的疏密程度等)，往往使得提取的道路面多边形边界不平滑，本文称为“多边形突刺”。多边形突刺则会导致出现图5a中的异常1类三角形，这种异常1类三角形往往导致更多异常的2类、3类三角形，这些异常三角形对道路中心线提取产生严重干扰。如图5b、图5c中提取的道路中心线出现了许多短小的分支中心线，这些分支中心线并不是真实的道

18、路，本文称为“中心线小毛刺”，其是由道路多边形突刺在道路干道边界尸 万方数据第4页 地理与地理信息科学 第32卷生成的1类异常三角形(1类三角形应分布在道路末端)所造成(图5a、图5c)。由于这种小毛刺的长度小于道路宽度，且这种线段起止点分别是第3类三角形和第1类三角形，故传统的解决方法是利用路宽的阈值删除小毛刺；但这种方法只适合于简单的道路结构，如遇到图5c中的复杂环形道路交叉口则会造成误删。故本文结合传统的方法，提出了一种新的解决策略，即基于面积阈值删除道路干道边界1类异常三角形。a)突刺三角形 (b)中心线小毛刺酗l曝辞摊I簿絮h-)星祭路IJ中心裴小毛刺图5复杂道路交叉口处中心线提取5

19、Road centerline extraction in complex road intersection通过统计分析发现，第1类三角形的面积大小呈两个极端分布：1)面积较小的由于道路边界突刺引起的异常1类三角形；2)面积较大的位于道路口末端的正常1类三角形。故根据面积大小阈值，结合三角网特性删除这些由道路边界突刺引起的三角形，最后只保留道路末端的正常1类三角形。面积阈值公式为：AreaCutValue=MeanArea+a*StdDev (6)式中：AreaCut坛lue为面积删除阈值，MeanAr鲫为Delaunay三角网中所有三角形的平均面积、口为自适应系数(默认为1)、StdDev

20、为三角网中三角形面积的标准差。根据面积阈值不断删除异常1类三角形，直到道路网干道边界没有异常1类三角形为止。223道路网数据后处理提取的道路中心线在第3类三角形处往往出现节点接头处断开、道路中心线节点在面积较大的第2类三角形处出现角度突变(图6)，这不符合常规电子地图与矢量数据的标准，故须对提取的道路中心线几何数据进行优化处理，包括道路中心线的光滑处理与位于第3类三角形处的道路节点的合并优化。道路中心线由一些列节点构成，故采用最小二乘法进行直线拟合，得到平滑的道路中心线：ynz+6，其中：(，z+1)z，Yi一簟Ey。)吐一立|J旦一(，2+1)Ey；一(y，)2)。=o io(7)由于第3类

21、三角形的重心在道路网络图中始终连接3条道路网络边，故凡是十字道路交叉口都变成了两个“V字形连接(图6a)。这种连接现象都发生在相邻的两个第3类三角形处，故本文通过找出起止点都为第3类三角形重心的线段，删除该线段，用这两个相邻的第3类三角形的公共边的中点代替，这样就得到了正确路网数据(图6b)。a)i苴路巾一L、线优化处理前 (11)道路中心线优化处理后图6道路中心线优化处理Fig6 The centerline optimization proc嘲ing3实验分析与结果评价31实验数据集与实验环境出租车GPS轨迹数据来源于微软研究院郑宇团队的11ver数据2 3|，为北京城区2008年2月3日

22、一天的出租车轨迹数据。其中出租车轨迹数据包括车辆标识m、GPS时间、GPS经度、GPS纬度等信息。轨迹点采样间隔为560 S不等，共有轨迹点3 055 105个，生成轨迹线124 506条，预处理后为45 768条(图7)。为验证本文提出的道路中心线提取方法，本文在P42G1Gwn7环境下，基于ArcGIS平台采用C#编程语言开发了基于众源时空轨迹数据的道路中心线提取实验系统，在此系统的支持下从北京市一天的出租车GPS轨迹中提取道路中心线。32实验结果分析对预处理后的出租车轨迹线构建约束Delaunay三角网，根据整体长边约束准则(式(5)删除长边，提取道路面粗轮廓多边形；然后对道路面多边形二

23、次构建Delaunay三角网，提取道路中心线。以北京市五环内轨迹数据为例，提取的道路中心线如图8所示，路名数据从微博签到轨迹数据中提取。参万端万方数据第3期 杨伟等：基于众源轨迹数据的道路中心线提取 第5页Z鞫一Z一Z-旷图7研究区域及轨迹线rig7 Study a嗍and t咧ectory line321 实验结果定性定量评价 本文借鉴文献19中的方法，将提取的道路几何数据与OSM电子地图2 4|、OSM道路网矢量数据241叠加比较，进行定性评价。图8中提取的道路中心线几何数据基本与实地道路相符合，尤其对于轨迹数据密度较高的道路区域，提取的道路中心线几何拓扑精度较高。为了定量评价实验结果，将

24、本方法实验结果与文献5中栅格化方法实验结果对比分析。采用文献25中提出的缓冲区检测方法评价道路中心线数据的几何精度。以OSM道路矢量数据为参考，分别建立2 rn、5 rn、7 In为半径宽度的缓冲区，计算落入缓冲区的道路中心线长度并统计百分比。利用ArcGIS的拓扑检查工具找出拓扑正确道路数量与拓扑错误道路数量，统计百分比。如表1所示，本文方法所提取的道路中心线数据在几何精度、拓扑正确性方面都比栅格化方法有较大提高，特别在2 m缓冲区的高精度结果有约30的提升。116。16，E 116。鲥E 116。24，E 116。捌E月 觥 l文 l I Ll l I ，L -14入l iT一1 1 一么

25、，?甾 网，戊 卜 -11 I粼， jl ，肘 托_ p Uk嗣 一卜 一咐霸捌凳 怠 召f刹 擀 个 1一 绷 泰 警 1 I I寸们 4 悼 点 ，叫 I I， H 。 产 H 鞋 + 瞽 手I I ll l I 计 止 一IJ 弋r譬 ， I l 拭l l L 1 II-17 J-订薯l一 1_r叫J 赶I 一1 _ 十 H I：il a” o_、： b 毫辱卜二紧 ， 常l - r 。一f1 l I蓬 划 觥I f kn1删l “ 吉、下 L J h队 椭h_。l r Ik 广 J H lL弋 - 盎 秭 k ， 一? 乇 弋斟霸l怼一一乏 徘 |撑幽体+歹_，一弋“一_j t7 既

26、滓州N芎I一E一一 、移j 7 表1实验结果评价Table 1 The evaluation of experiment results2 m缓冲区5 m缓冲区7 m缓冲区拓扑正确性本文方法 612816831852塑整垡直鎏 i；：!墅 !：!堑 !：!堑 !：!墅322复杂环形道路实验结果评价本文方法通过设置长边约束准则中的调节系数a参数值，帮助识别不同路网结构、不同轨迹密度分布的道路面域轮廓。尤其对于复杂环形道路的中心线提取，能较好地区别路面与空白区域，从而保证道路中心线的拓扑正确性。如图9所示，本文方法能正确区分环形道路中的小空白区域(图9b)、距离较近的双干道等复杂案例；反之，如图9

27、c所示，栅格化方法将环形道路空白区域错误识别为道路，从而导致道路中心线的拓扑错误。当然该方法对于不同的轨迹数据需要实验找出不同的调节参数，另外该方法也不能对道路边界进行精确识别，这是下一步的研究重点。从时间性能效率方面看，Delaunay三角网模型的实现算法已较成熟、稳定，其时间复杂度为(nlogn)L2 0|，完全适用于大数据处理；并且可以在较多的开源软件(如QGIS等)以及主流的GIS软件(如ArcGIS等)平台中实现，快速投入地图数据生产，所以本方法与其他道路中心线提取算法相比更简便、快速且易于实现。4结论与展望为了快速准确地从众源轨迹数据中提取道路几何数据，本文提出了一种基于约束Del

28、aunay三角网的道路中心线提取方法。首先对预处理后的车辆轨|i10 |110 |_|0|00万方数据第6页 地理与地理信息科学 第32卷(a 1原始轨迹数据醒)Drlaunm，浊提取的中心线 (c)栅格化方法提取的中心线复杂环形道路提取结果对比Fj孚9 C咖叩盯is蚰of the r幅llIts extracted from complex ring road迹线构建约束Delaunay三角网，根据整体长边约束准则删除长边提取道路面粗粒度轮廓多边形；然后对道路面多边形二次构建Delaunay三角形，提取道路中心线。利用北京市一天时间的出租车轨迹数据进行实验分析，用0SM道路网矢量数据作为参考

29、数据，与栅格化方法实验结果进行定性定量的对比评价。结果证明本文方法提取的道路中心线数据在几何、拓扑精度方面都比栅格化方法高，并且本方法在处理复杂道路结构、较大密度差异的轨迹数据时比栅格化方法更显优势。另外，本方法算法易于实现且适合大数据处理。本研究还需要深入完善的内容主要包括：1)更精确地提取道路面域数据。本研究中只识别了道路面域的粗轮廓，其结果并不精确；同时对于密度差异较大的轨迹数据，本文方法还需要改进，特别对于城市内部小区级别的道路提取需要深入研究。2)道路数据不仅包括道路中心线数据，还包括道路面、车道、路名等数据，故在后续工作中，将设计不同算法并融合不同类型的VGI轨迹数据以提取更丰富的

30、道路几何数据与属性数据。参考文献：1GOODCHILD M FCitizens aS sensors：The world of volunteeredgeographyJGeoJournal，2007，69(4)：211-221E2ANIVIED M，KARAGIORGOU s，PFOSER Det a1A comparison and evaluation of map construction algorithms using vehicletracking dataJGeoInformatica，2015。19(3)：601-6323EDELKAMP S，SCHRODL SRoute p

31、lanning and map inference with global positioning tracesAComputer Science inPerspectiveCSpringer Berlin Heidelberg，2003128-1514GUO T，1WAMURA K，K()GAL Towards high accuracy roadmaps generation from massive GPS traces dataA2007 IEEE Intematibnal Geosdence and Remote Sensing SymposiumC2007I-5ZHANG L。TH

32、IEMAnlN F，疆n口R M Integration of GPS traces谢th road map r AProceedings of the Second InternationalWorkshop on Computational Transportation ScienceCACM，2010172263 CAO L，KRUMM JFrom GPS traces tO a routable road mapEA-IProceedings of the 1 7th ACM SIGSPATIAL InternationalConference on Advances in Geogr

33、aphic Information SystemsrCACM，20093127KARAGIORGOU S，PFOSER 12 On vehicle tracking data-basedroad network generationAProceedings of the 20th Intemational Conference on Advances in Geographic Information SystemsECACM，201289988 KARAGl0RG0u S，PFOSER D，SKOUTAS 13Segmentation-based road network construct

34、ionAProceedings of the 21stACM SIGSPATIAL International COnferenee on Advances inGeographic Information SystemsCACM，2013460-46391 LI J，QIN Q，XIE C，et a1Integrated use of spatial and semanticrelationships for extracting road networks from floating car dataJInternational Journal of Applied Earth Obser

35、vation andGeoinformation，2012，19：238247Elo唐炉亮，刘章，杨雪，等符合认知规律的时空轨迹融合与路网生成方法J1测绘学报，2015，44(11)：12711276113 CHEN C，CHENG YRoads digiM map generation with multi-track GPS dataAr比lucation Technology and Training，2008c2008 International Workshop on Geoscience and RemoteSensing，2008，1：508-511123 XIE x，BING-

36、YUNG W K，AGHAJAN H，et aL Inferringdirected road networks from GPS traces by track alignmentJISPRS International Journal of Geo-lnformation，2015，4(4)：2446247L133蒋益娟，李响，李小杰，等利用车辆轨迹数据提取道路网络的几何特征与精度分析J地球信息科学学报，2012，14(2)：165170143 LIU x，BIAGIONI J，ERIKSSON J，et a1Mining large-scale，sparse GPS traces for

37、 map inference：Comparison of approachesAProceedings of the 18th ACM SIGKDD InternationalConference on Knowledge Discovery and Data MiningcACM。201266967715wu J，ZHU Y，KU T，et a1Detecting road intersections fromcoarse-gained GPS traces based on clusteringJJournal ofComputers，2013，8(11)：2959-2965万方数据第3期

38、 杨伟等：基于众源轨迹数据的道路中心线提取 第7页161 WANG J，RUI X，SONG x，et a1A novel approach forgenerating routable road maps from vehicle GPS tracesJInternational Journal of Geographical Information Science，2015，29(1)：6991E17艾廷华，郭仁忠基于约束Delaunay结构的街道中轴线提取及网络模型建立J测绘学报，2000，29(4)：348-354D8李功权，蔡祥云一种基于约束三角网的道路中心线的提取方法口长江大学学报

39、(自然科学版：理工卷)，2013(2)：47-50-191 LI J，QIN Q，HAN J，et at Mining trajectory data and geotaggeddata in social media for road map inferenceJ。Transactions inGIS，2015，19(1)：11820ESTIVILL-CASTRO V，LEE IMultilevel clustering and itsvisualization for exploratory spatial analysisF,J1Geolnformatica，2002，6(2)：1231

40、52212李光强，邓敏，刘启亮，等一种适应局部密度变化的空间聚类方法J测绘学报，2009，38(3)：255-263221艾廷华，郭仁忠支持地图综合的面状目标约束Delaunay三角网剖分J武汉测绘科技大学学报，2000，25(1)：3541F-23YuAN J，ZHENG Y，ZHANG C，et a1T drive：Driving directions based on taxi trajectoriesAProceedings of the 18thSIGSPATIAl。International Conference on Advances in Ge0一graphic Informa

41、tion SystemsCACM，201099108E24http：wunvopenstreetmaporg201510一31。25)ODCHILD M F，HUNTER G JA simple positional accuracy measure for linear featuresJInternational Journal ofGeographical Iniormation Science，1997，11(3)：299306Road Centerline Extraction from Crowdsourcing Trajectory DataYANG Wei，AI Tinghua

42、(School of Resource and Environmental Sciences，Wuhan University，Wuhan 430079，China)Abstract：Compared with traditional method，road centerline extraction from crowdsourcing trajectory data offers numerous advantages with respect to labor cost，realtime and data completenessHowever，it is difficult to co

43、nstruct road network using bigcrowdsourcing trajectory data due to the trajectory data with sampling sparse and large data volume and high noiseFor this issue，this study tries to explore the question of road centerline extraction by large volume of taxi GPS trajectory data，presentinga new method bas

44、ed on Delaunay triangulation modelThe whole method includes three stepsThe first one is to pre-process thevehicle trajectory data including the point anomaly removing and the conversion of trajectory point to track IineSecondly，construct Delaunay triangulation within the vehicle trajectory line to d

45、etect neighborhood relationAnd then，the road coarse polygon is extracted by cutting long triangle edge and organizing the polygon topologyConsidering the case that some of the trajectory segments are too long，a interpolation measure is used to add more points for the improved triangulationThirdly，co

46、nstructDelaunay triangulation within the road polygon to extract the road centerlineThe centerline is extracted by distinguishing threekinds of triangles and processing the road junctionThe experiment is conducted using one day of taxi track in Beijing CityCompared with conventional methods(raster)，

47、experimental results demonstrate that the accuracy of road geometry and topology is improved above 10 percent through the use of the method in this paperMoreover，the complex ring road is used as a casestudy to test the proposed methodExperimental results prove that the proposed method is more suitab

48、le for complex roadstructure and trajectory data with different densityAs a result，the results achieved with the proposed method show that roadcenterline can be generated with low cost，high efficiency，good maneuverability，based on crowdsourcing trajectory data，and bevery useful for mapping applicationKey words：crowdsourcing trajectory data；road extraction；road centerline；Delaunay triangulation万方数据