适应不同轨迹数据场景的道路线形组合优化提取方法

doi:10.11947/j.AGCS.2024.20220606

测绘学报 ›› 2024, Vol. 53 ›› Issue (2): 379-390.doi: 10.11947/j.AGCS.2024.20220606

适应不同轨迹数据场景的道路线形组合优化提取方法

姚志鹏¹, 彭程¹, 唐建波^1,2, 刘国平³, 杨学习^1,2, 刘慧敏¹, 邓敏^1,2

1. 中南大学地球科学与信息物理学院, 湖南长沙 410083;
2. 湖南省地理空间信息工程技术研究中心, 湖南长沙 410007;
3. 北京滴滴出行科技有限公司, 北京 100089

收稿日期:2022-10-24 修回日期:2023-11-27 发布日期:2024-03-08
通讯作者: 唐建波 E-mail:jianbo.tang@csu.edu.cn
作者简介:姚志鹏(1998-),男,硕士,研究方向为时空轨迹数据挖掘与分析。E-mail:zhipengyao@csu.edu.cn
基金资助:
国家自然科学基金（42271462；42171441；42271485）；国家重点研发计划（2022YFB3904203）；湖南省自然科学基金（2021JJ40727；2022JJ30703；2020JJ4749）

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

YAO Zhipeng¹, PENG Cheng¹, TANG Jianbo^1,2, LIU Guoping³, YANG Xuexi^1,2, LIU Huimin¹, DENG Min^1,2

1. School of Geosciences and Info-physics, Central South University, Changsha 410083, China;
2. Hunan Geospatial Information Engineering and Technology Research Center, Changsha 410007, China;
3. Beijing Didi Chuxing Technology Co., Ltd., Beijing 100089, China

Received:2022-10-24 Revised:2023-11-27 Published:2024-03-08
Supported by:
The National Natural Science Foundation of China (Nos. 42271462; 42171441; 42271485); The National Key Research and Development Program of China (No. 2022YFB3904203); Hunan Provincial Natural Science Foundation of China (Nos. 2021JJ40727; 2022JJ30703; 2020JJ4749)

摘要/Abstract

摘要： 车辆轨迹数据是当前城市导航路网地图动态更新的一种重要数据源，从杂乱无序的轨迹点或轨迹线中提取并拟合道路几何形态，进而生成结构化的道路矢量地图是基于轨迹数据进行道路网地图构建与更新的关键步骤。现有的道路中心线提取方法主要采用单一的线形拟合算法进行轨迹数据拟合，然而真实道路的几何形态复杂多样和车辆轨迹数据质量参差不齐，导致单一的道路线形拟合算法只能在某些特定的数据场景下适用，无法针对不同的数据场景自适应的拟合出理想的道路中心线。此外，相比于专业测量方式采集的高频轨迹数据，出租车等采集的低频轨迹数据存在轨迹点稀疏、噪声多、定位误差大等问题，这使得从低频轨迹数据中提取理想的道路中心线仍具有挑战，尤其是针对复杂的交叉口区域。为此，本文基于分治策略的思想，提出了一种适应不同轨迹数据场景的道路线形组合优化提取方法。该方法在轨迹数据预处理的基础上，根据轨迹数据的分布特点对数据进行场景分类；进而，针对不同的数据场景匹配最优的线形拟合算法，通过组合优化策略生成理想的道路中心线。本文方法融合不同拟合算法的互补优势，可以有效解决数据分布稀疏、道路结构复杂（如自相交立交桥）等不同数据场景下的道路线形拟合问题。采用北京市出租车轨迹数据进行试验与对比分析，本文方法生成道路的平均位置精度为1.24 m，显著优于现有代表性方法。

关键词: 轨迹数据, 道路中心线, 线形拟合, 自适应, 路网提取

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

中图分类号:

P208

姚志鹏, 彭程, 唐建波, 刘国平, 杨学习, 刘慧敏, 邓敏. 适应不同轨迹数据场景的道路线形组合优化提取方法[J]. 测绘学报, 2024, 53(2): 379-390.

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.

参考文献

[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.

适应不同轨迹数据场景的道路线形组合优化提取方法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	孙根云, 李忍忍, 张爱竹, 安娜, 付航, 潘兆杰. 高光谱影像逆近邻密度峰值聚类的波段选择算法[J]. 测绘学报, 2024, 53(1): 8-19.
[2]	江宝得, 黄威, 许少芬, 巫勇. 融合分散自适应注意力机制的多尺度遥感影像建筑物实例细化提取[J]. 测绘学报, 2023, 52(9): 1504-1514.
[3]	苏小宁, 石睿娟, 鲍庆华, 朱庆, 孟国杰, 闫浩文. GNSS连续观测站构造运动变化特征自适应提取方法[J]. 测绘学报, 2023, 52(8): 1245-1254.
[4]	连仁包, 张振敏, 廖一鹏, 邹长忠, 黄立勤. 结合测地距离场与曲线平滑的遥感图像道路中心线快速提取[J]. 测绘学报, 2023, 52(8): 1317-1329.
[5]	王梓豪, 唐炉亮, 杨雪, 戴领, 李朝奎. 利用车载GNSS轨迹大数据的U-Turn道路结构信息获取方法[J]. 测绘学报, 2023, 52(8): 1330-1341.
[6]	邓敏, 罗斌, 唐建波, 姚志鹏, 刘国平, 温翔, 胡润波, 柴华, 胡文柯. 顾及轨迹密度分布异质性的道路交叉口提取方法[J]. 测绘学报, 2023, 52(6): 1000-1009.
[7]	李增科, 孙耀文, 陈昭冰, 赵龙, 高井祥. 顾及组合导航闭环反馈的变分贝叶斯自适应滤波优化算法[J]. 测绘学报, 2023, 52(5): 725-737.
[8]	王超, 王帅, 陈晓, 李俊勇, 谢涛. 联合UNet++和多级差分模块的多源光学遥感影像对象级变化检测[J]. 测绘学报, 2023, 52(2): 283-296.
[9]	沈秭扬, 倪欢, 管海燕. 遥感图像跨域语义分割的无监督域自适应对齐方法[J]. 测绘学报, 2023, 52(12): 2115-2126.
[10]	龚循强, 侯昭阳, 吕开云, 鲁铁定, 夏元平, 李威俊. 结合改进Laplacian能量和参数自适应双通道ULPCNN的遥感影像融合方法[J]. 测绘学报, 2023, 52(11): 1892-1905.
[11]	刘海砚, 郭漩, 刘俊楠. 时空和语义结合的船舶轨迹数据压缩方法[J]. 测绘学报, 2023, 52(11): 1974-1982.
[12]	晏雄锋, 袁拓, 杨敏, 孔博, 刘鹏程. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278.
[13]	刘万科, 农旗, 陶贤露, 朱锋, 胡捷. 非完整约束的OD/SINS自适应组合导航方法[J]. 测绘学报, 2022, 51(1): 9-17.
[14]	靳凯迪, 柴洪洲, 宿楚涵, 向民志. 顾及有色噪声的光纤陀螺随机噪声自适应滤波方法[J]. 测绘学报, 2022, 51(1): 80-86.
[15]	代维秀, 陈占龙, 谢鹏. 居民出行与轨迹行为交互模式挖掘与关联技术[J]. 测绘学报, 2021, 50(4): 532-543.