基于众源轨迹数据的道路中心线提取
|
摘要
从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而,由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题,提出一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网,根据整体长边约束准则删除长边以提取道路面域多边形;然后对道路面多边形二次构建Delaunay三角网,提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验,将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10%以上。另外,以复杂环形道路为例,证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此,该方法不仅适合大数据处理、结果精度高,且算法成熟、易于实现。
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.
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.
引文
[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].2007IEEE 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.Segmentationbased 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 multitrack GPS data[A].Education Technology and Training,2008[C].2008International 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.
[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].2007IEEE 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.Segmentationbased 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 multitrack GPS data[A].Education Technology and Training,2008[C].2008International 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.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |