The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation

doi:10.11947/j.AGCS.2017.20160233

Abstract

Abstract: Extraction of road boundary accurately from crowdsourcing trajectory lines is still a hard work.Therefore,this study presented a new approach to use vehicle trajectory lines to extract road boundary.Firstly, constructing constrained Delaunay triangulation within interpolated track lines to calculate road boundary descriptors using triangle edge length and Voronoi cell.Road boundary recognition model was established by integrating the two boundary descriptors.Then,based on seed polygons,a regional growing method was proposed to extract road boundary. Finally, taxi GPS traces in Beijing were used to verify the validity of the novel method, and the results also showed that our method was suitable for GPS traces with disparity density,complex road structure and different time interval.

Key words: crowdsourcing trajectory, road updating, Delaunay triangulation, spatial clustering

CLC Number:

P208

YANG Wei, AI Tinghua. The Extraction of Road Boundary from Crowdsourcing Trajectory Using Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 237-245.

References

[1] AHMED 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.
[2] 杨伟, 艾廷华. 基于车辆轨迹大数据的道路网更新方法研究[J]. 计算机研究与发展, 2016, 53(12):2681-2693. YANG Wei, AI Tinghua. A Method for Road Network Updating Based on Vehicle Trajectory Big Data[J]. Journal of Computer Research and Development, 2016, 53(12):2681-2693.
[3] WANG Jing, RUI Xiaoping, SONG Xianfeng, 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.
[4] ZHANG Lijuan,THIEMANN F,SESTER M. Integration of GPS Traces with Road Map[C]//Proceedings of the Third International Workshop on Computational Transportation Science. New York:ACM, 2010:17-22.
[5] GUO Tao, IWAMURA K, KOGA M. Towards High Accuracy Road Maps Generation from Massive GPS Traces Data[C]//Proceedings of the 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona:IEEE, 2007:667-670.
[6] LIU Xuemei, BIAGIONI J, ERIKSSON J, et al. Mining Large-scale, Sparse GPS Traces for Map Inference:Comparison of Approaches[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:669-677.
[7] CAO Lili, KRUMM J. From GPS Traces to a Routable Road Map[C]//Proceedings of the 17th ACM SIGSP-ATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2009:3-12.
[8] LI Jun, QIN Qiming, XIE Chao, 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.
[9] 唐炉亮, 刘章, 杨雪, 等. 符合认知规律的时空轨迹融合与路网生成方法[J]. 测绘学报, 2015, 44(11):1271-1276. DOI:10.11947/j.AGCS.2015.20140591. TANG Luliang, LIU Zhang, YANG Xue, et al. A Method of Spatio-temporal Trajectory Fusion and Road Network Generation Based on Cognitive Law[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(11):1271-1276. DOI:10.11947/j.AGCS.2015.20140591.
[10] WU Junwei, ZHU Yunlong, KU Tao, et al. Detecting Road Intersections from Coarse-gained GPS Traces Based on Clustering[J]. Journal of Computers, 2013, 8(11):2959-2965.
[11] XIE Xingzhe,BING-YUNGWONG 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.
[12] SHI Wenhuan, SHEN Shuhan, LIU Yuncai. Automatic Generation of Road Network Map from Massive GPS, Vehicle Trajectories[C]//Proceedings of the 12th International IEEE Conference on Intelligent Transportation Systems. St. Louis, MO:IEEE, 2009:1-6.
[13] 蒋益娟, 李响, 李小杰, 等. 利用车辆轨迹数据提取道路网络的几何特征与精度分析[J]. 地球信息科学学报, 2012, 14(2):165-170. JIANG Yijuan, LI Xiang, LI Xiaojie, et al. Geometrical Characteristics Extraction and Accuracy Analysis of Road Network Based on Vehicle Trajectory Data[J]. Journal of Geo-Information Science, 2012, 14(2):165-170.
[14] KUNTZSCH C, SESTER M, BRENNER C. Generative Models for Road Network Reconstruction[J]. International Journal of Geographical Information Science, 2016, 30(5):1012-1039.
[15] WANG Yin,LIU Xuemei,WEI Hong, et al. Crowd Atlas:Self-updating Maps for Cloud and Personal Use[C]//Proceedings of the 11th Annual International Conference on Mobile Systems, Applications, and Services. New York:ACM, 2013:27-40.
[16] 李怡静, 胡翔云, 张剑清, 等. 影像与LiDAR数据信息融合复杂场景下的道路自动提取[J]. 测绘学报, 2012, 41(6):870-876. LI Yijing,HU Xiangyun,ZHANG Jianqing,et al. Automatic Road Extraction in Complex Scenes Based on Information Fusion from LiDAR Data and Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):870-876.
[17] 方莉娜, 杨必胜. 车载激光扫描数据的结构化道路自动提取方法[J]. 测绘学报, 2013, 42(2):260-267. FANG Lina, YANG Bisheng. Automated Extracting Structural Roads from Mobile Laser Scanning Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2):260-267.
[18] 杨伟, 艾廷华. 基于众源轨迹数据的道路中心线提取[J]. 地理与地理信息科学, 2016, 32(3):1-7. YANG Wei, AI Tinghua. Road Centerline Extraction from Crowdsourcing Trajectory Data[J]. Geography and Geo-Information Science, 2016, 32(3):1-7.
[19] 李清泉, 李德仁. 大数据GIS[J]. 武汉大学学报(信息科学版), 2014, 39(6):641-644. LI Qingquan, LI Deren. Big Data GIS[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):641-644.
[20] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10):3224-3236.
[21] LIU Qiliang, TANG Jianbo, DENG Min, et al. An Iterative Detection and Removal Method for Detecting Spatial Clusters of Different Densities[J]. Transactions in GIS, 2015, 19(1):82-106.
[22] 艾廷华, 郭仁忠. 基于约束Delaunay结构的街道中轴线提取及网络模型建立[J]. 测绘学报, 2000, 29(4):348-354. AI Tinghua, GUO Renzhong. Extracting Center-lines and Building Street Network Based on Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4):348-354.
[23] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2):175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2):175-181.
[24] ZHENG Yu, LI Quannan, CHEN Yukun, et al. Understanding Mobility based on GPS Data[C]//Proceedings of the 10th International Conference on Ubiquitous Computing. New York:ACM, 2008:312-321.
[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.