An adaptive road centerline extraction method for different trajectory data scenarios based on combinatorial optimization

doi:10.11947/j.AGCS.2024.20220606

Abstract

Abstract: Vehicle trajectory data is an important data source for road map update. Extracting road centerlines from the disordered trajectory points or trajectory lines, and generating a structured vector map is a key step for road network generation and update based on trajectory data. The existing methods of road centerline extraction mainly use a single curve fitting algorithm, which are not adaptive to different data scenarios, especially for complex road structures and trajectories of different quality. In addition, compared with the professional collected high-frequency trajectory data, road centerline extraction based on the low-frequency trajectory data collected by float cars is still challenging due to the noise, sparsity, and low position accuracy. Therefore, this paper proposes an adaptive road centerline extraction method for different trajectory data scenarios based on combinatorial optimization and divide-and-conquer strategy. Based on preprocessing and clustering of trajectory data, this method classifies the trajectory data according to its distribution characteristics. Then, the optimal fitting algorithm is matched according to different data scenarios, and the ideal road centerline is generated by combinatorial optimization strategy. This method integrates the advantages of different fitting algorithms, and can effectively solve the road centerline extraction problem for different data scenarios such as sparse data and complex road structures (e.g. self-intersection overpasses). Experiments on floating car data in Beijing, China, were conducted and results show that the average position accuracy of the roads generated by this method is 1.24 m, which is significantly better than the existing available methods.

Key words: trajectory data, road centerline, curve fitting, adaptation, road network extraction

CLC Number:

P208

YAO Zhipeng, PENG Cheng, TANG Jianbo, LIU Guoping, YANG Xuexi, LIU Huimin, DENG Min. An adaptive road centerline extraction method for different trajectory data scenarios based on combinatorial optimization[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(2): 379-390.

References

[1] 吴涛, 向隆刚, 龚健雅. 路网更新的轨迹-地图匹配方法[J]. 测绘学报, 2017, 46(4):507-515. DOI:10.11947/j.AGCS.2017.20150479. WU Tao, XIANG Longgang, GONG Jianya. Renewal of road networks using map-matching technique of trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4):507-515.DOI:10.11947/j.AGCS.2017.20150479.
[2] 刘纪平, 张用川, 徐胜华, 等. 一种顾及道路复杂度的增量路网构建方法[J]. 测绘学报, 2019, 48(4):480-488.DOI:10.11947/J.AGCS.2019.20180419. LIU Jiping, ZHANG Yongchuan, XU Shenghua,et al. An incremental construction method of road network considering road complexity[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4):480-488.DOI:10.11947/J.AGCS.2019.20180419.
[3] 李德仁, 洪勇, 王密, 等. 测绘遥感能为智能驾驶做什么?[J]. 测绘学报, 2021, 50(11):1421-1431. DOI:10.11947/j.AGCS.2021.20210280. LI Deren, HONG Yong, WANG Mi, et al. What can surveying and remote sensing do for intelligent driving?[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(11):1421-1431.DOI:10.11947/j.AGCS.2021.20210280.
[4] 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.
[5] GUO Tao, IWAMURA K, KOGA M. Towards high accuracy road maps generation from massive GPS traces data [C]//Proceedings of 2007 IEEE International Geoscience and Remote Sensing Symposium. Barcelona:IEEE, 2007:667-670.
[6] ZHAO Lisheng, MAO Jiali, PU Min, et al. Automatic calibration of road intersection topology using trajectories [C]//Proceedings of 2020 IEEE International Conference on Data Engineering. Dallas:IEEE, 2020:1633-1644.
[7] EDELKAMP S, SCHRODL S. Route planning and map inference with global positioning traces[J]. Computer Science in Perspective, 2003, 2598:128-151.
[8] LIU Xuemei, BIAGIONI J, ERIKSSON J, et al. Mining large-scale, sparse GPS traces for map inference:comparison of approaches [C]//Proceedings of 2012 Knowledge Discovery and Data Mining. New York:Association for Computing Machinery, 2012:669-677.
[9] TANG Jianbo, DENG Min, HUANG Jincai, et al. An automatic method for detection and update of additive changes in road network with GPS trajectory data [J]. ISPRS International Journal of Geo-Information, 2019, 8(9):411.
[10] HASTIE T, STUETZLE W. Principal curves [J]. Journal of the American Statistical Association, 1989, 84(406):502-516.
[11] AGAMENNONI G, NIETO J I, NEBOT E M. Robust inference of principal road paths for intelligent transportation systems [J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1):298-308.
[12] WANG Yin, LIU Xuemei, HONG Wei, et al. Crowd Atlas:self-updating maps for cloud and personal use [C]//Proceedings of 2013 International Conference on Mobile Systems. New York:Association for Computing Machinery, 2013:469-470.
[13] KRZY A, ZEGER K, et al. Learning and design of principal curves[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(3):281-297.
[14] DENG Min, HUANG Jincai, ZHANG Yunfei, et al. Generating urban road intersection models from low-frequency GPS trajectory data [J]. International Journal of Geographical Information Science, 2018, 32(12):2337-2361.
[15] TANG Jianbo, DENG Min, HUANG Jincai, et al. A novel method for road intersection construction from vehicle trajectory data [J]. IEEE Access, 2019, 7(1):95065-95074.
[16] CHEN Chen, CHENG Yinhang. Roads digital map generation with multi-track GPS data [C]//Proceedings of 2008 International Workshop on Education Technology and Training & International Workshop on Geoscience and Remote Sensing. Shanghai:IEEE, 2008:508-511.
[17] BIAGIONI J, ERIKSSON J. Map inference in the face of noise and disparity [C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. California:Association for Computing Machinery, 2012:79-88.
[18] KUNTZSCH C, SESTER M, BRENNER C. Generative models for road network reconstruction [J]. International Journal of Geographical Information Science, 2016, 30(5):1012-1039.
[19] AHMED M, WENK C. Constructing street networks from GPS trajectories [C]//Proceedings of the 20th Annual European Conference on Algorithms. Berlin:Springer-Verlag, 2012:60-71.
[20] 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.
[21] CAO Lili, KRUMM J. From GPS traces to a routable road map [C]//Proceedings of the 17th ACM SIGSPATIAL International Confe-rence on Advances in Geographic Information Systems. New York:Association for Computing Machinery, 2009:3-12.
[22] DAVIES J J, BERESFORD A R, HOPPER A. Scalable, distributed, real-time map generation [J]. IEEE Pervasive Computing, 2006, 5(4):47-54.
[23] 唐炉亮, 于智伟, 任畅,等. 基于车载GPS轨迹的立体交叉口空间结构信息获取方法[J]. 交通运输工程学报, 2019, 19(5):170-179. TANG Luliang, YU Zhiwei, REN Chang,et al. Information acquisition method of three-dimensional intersection spatial structure based on vehicle GPS trajectory[J]. Journal of Traffic and Transportation Engineering, 2019, 19(5):170-179.
[24] 杨伟, 艾廷华. 运用约束Delaunay三角网从众源轨迹线提取道路边界[J]. 测绘学报, 2017, 46(2):237-245.DOI:10.11947/j.AGCS.2017.20160233. 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.DOI:10.11947/j.AGCS.2017.20160233.
[25] KARAGIORGOU S, PFOSER D. On vehicle tracking data-based road network generation [C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York:Association for Computing Machinery, 2012:89-98.
[26] LI Hengfeng, KULIK L, RAMAMOHANARAO K. Automatic generation and validation of road maps from GPS trajectory data sets [C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York:Association for Computing Machinery, 2016:1523-1532.
[27] 万子健, 李连营, 杨敏, 等. 车辆轨迹数据提取道路交叉口特征的决策树模型[J]. 测绘学报, 2019, 48(11):1391-1403.DOI:10.11947/j.AGCS.2019.20190011. WAN Zijian, LI Lianying, YANG Min,et al. Decision tree model for extracting road intersection feature from vehicle trajectory data[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11):1391-1403.DOI:10.11947/j.AGCS.2019.20190011.
[28] 唐炉亮, 杨雪, 靳晨,等. 基于约束高斯混合模型的车道信息获取[J].武汉大学学报(信息科学版), 2017, 42(3):341-347. TANG Luliang, YANG Xue, JIN Chen,et al. Traffic lane number extraction based on the constrained Gaussian mixture model[J]. Geomatics and Information Science of Wuhan University, 2017, 42(3):341-347.
[29] 唐炉亮, 牛乐, 杨雪, 等. 利用轨迹大数据进行城市道路交叉口识别及结构提取[J]. 测绘学报, 2017, 46(6):770-779.DOI:10.11947/j.AGCS.2017.20160614. TANG Luliang, NIU Le, YANG Xue,et al. Urban intersection recognition and construction based on big trace data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6):770-779.DOI:10.11947/j.AGCS.2017.20160614.
[30] 邓敏, 罗斌, 唐建波, 等. 顾及轨迹密度分布异质性的道路交叉口提取方法[J]. 测绘学报, 2023, 52(6):1000-1009.DOI:10.11947/j.AGCS.2023.20210173. DENG Min, LUO Bin, TANG Jianbo, et al. Extracting road intersections from vehicle trajectory data in the face of trace density dispa-rity[J]. Acta Geodaeticaet Cartographica Sinica, 2023, 52(6):1000-1009.DOI:10.11947/j.AGCS.2023.20210173.
[31] VERBEEK J J, VLASSIS N, KROSE B. A K-segments algorithm for finding principal curves [J]. Pattern Recognition Letters, 2002, 23(8):1009-1017.
[32] PIEGL L, TILLER W. The NURBS book [M]. Berlin:Springer-Verlag, 1997.
[33] PITTMAN J, MURTHY C A. Fitting optimal piecewise linear functions using genetic algorithms [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(7):701-718.