Matching the high sampled trajectory with road networks based on path increment

doi:10.11947/j.AGCS.2023.20210513

Abstract

Abstract: Aiming at matching the high sampled GNSS trajectory data with complex urban road networks, a matching method based on path increment is proposed. The method consists of two parts:combined filtering and incremental matching. Firstly, the road network is simplified through combined filtering, and then the matching process is carried out with the road paths as the increments. During the matching process at the intersection point, the similarity evaluation scheme integrating distance factor and curvature is adopted. In order to verify the effectiveness of the method, several high sampled trajectory data with different complexity are selected for experiments. The method is compared with two existing matching methods, including the curvedness feature constrained map matching method and hidden Markov model (HMM). The results show that the proposed method not only performs better in accuracy and efficiency, but also can suppress the occurrence of matching errors in various complex sections.

Key words: map matching, GNSS trajectory, high sampling frequency, complex road network, increment

CLC Number:

P208

WANG Haoyan, LIU Yuangang, LI Shaohua, LIANG Bo, HE Zongyi. Matching the high sampled trajectory with road networks based on path increment[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(2): 329-340.

References

[1] ZHENG Yu. Trajectory data mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):1-41.
[2] WANG Hongyu, LI Jin, HOU Zhenshan, et al. Research on parallelized real-time map matching algorithm for massive GPS data[J]. Cluster Computing, 2017, 20(2):1123-1134.
[3] GONG Yuejiao, CHEN En, ZHANG Xinglin, et al. AntMapper:an ant colony-based map matching approach for trajectory-based applications[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(2):390-401.
[4] BERNSTEIN D, KORNHAUSER A. An introduction to map-matching for personal navigation assistants[R]. New Jersey:TIDE Centre Technical Report, 1996.
[5] BENTLEY J L, MAURER H A. Efficient worst-case data structures for range searching[J]. Acta Informatica, 1980, 13(2):155-168.
[6] QUDDUS M A, OCHIENG W Y, NOLAND R B. Current map-matching algorithms for transport applications:state-of-the art and future research directions[J]. Transportation Research Part C:Emerging Technologies, 2007, 15(5):312-328.
[7] ALT H, EFRAT A, ROTE G, et al. Matching planar maps[J]. Journal of Algorithms, 2003, 49(2):262-283.
[8] QUDDUS M A, OCHIENG W Y, ZHAO Lin, et al. A general map matching algorithm for transport telematics applications[J]. GPS Solutions, 2003, 7(3):157-167.
[9] GREENFELD J S. Matching GPS observations to locations on a digital map[J]. Transportation Research Board, 2002,3:1-13.
[10] JABBOUR M, BONNIFAIT P, CHERFAOUI V. Map-matching integrity using multihypothesis road-tracking[J]. Journal of Intelligent Transportation Systems, 2008, 12(4):189-201.
[11] OCHIENG W Y, QUDDUS M, NOLAND R B. Map-matching in complex urban road networks[J]. Revista Brasileira De Cartografia, 2009, 55(2):1-14.
[12] 朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[J]. 武汉大学学报(信息科学版), 2017, 42(1):77-83. ZHU Di, LIU Yu. An incremental map-matching method based on road network topology[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1):77-83.
[13] 李翔, 马爽, 杨辉, 等. 矢量道路拓扑追踪匹配算法[J]. 中国图象图形学报, 2017, 22(5):596-609. LI Xiang, MA Shuang, YANG Hui, et al. Vector road matching algorithm based on a topological path[J]. Journal of Image and Graphics, 2017, 22(5):596-609.
[14] 殷吉崇, 武芳, 李安平, 等. 顾及速度与航向信息的轨迹匹配方法[J]. 武汉大学学报(信息科学版), 2021, 46(11):1774-1781. YIN Jichong, WU Fang, LI Anping, et al. Trajectory matching considering speed and heading information[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11):1774-1781.
[15] LIU Minshi, ZHANG Ling, GE Junlian, et al. Map matching for urban high-sampling-frequency GPS trajectories[J]. ISPRS International Journal of Geo-Information, 2020, 9(1):31.
[16] HASHEMI M, KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks[J]. Journal of Intelligent Transportation Systems, 2016, 20(6):573-590.
[17] ZHAO Xiangmo, CHENG Xin, ZHOU Jingmei, et al. Advanced topological map matching algorithm based on D-S theory[J]. Arabian Journal for Science and Engineering, 2018, 43(8):3863-3874.
[18] KUBICKA M, CELA A, MOUNIER H, et al. Comparative study and application-oriented classification of vehicular map-matching methods[J]. IEEE Intelligent Transportation Systems Magazine, 2018, 10(2):150-166.
[19] LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM Sigspatial International Conference on Advances in Geographic Information Systems. Seattle, WA,USA:ACM press, 2009:352-361.
[20] MILLARD-BALL A, HAMPSHIRE R C, WEINBERGER R R. Map-matching poor-quality GPS data in urban environments:the pgMapMatch package[J]. Transportation Planning and Technology, 2019, 42(6):539-553.
[21] ZENG Zhe, ZHANG Tong, LI Qingquan, et al. Curvedness feature constrained map matching for low-frequency probe vehicle data[J]. International Journal of Geographical Information Science, 2016, 30(4):660-690.
[22] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Seattle, WA,USA:ACM press, 2009:336-343.
[23] ZHANG Haiyan, LUO Yonglong, YU Qingying, et al. Map-matching approach based on link factor and hidden Markov model[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(3):5455-5471.
[24] CHE M, WANG Y, ZHANG C, et al. An enhanced hidden Markov map matching model for floating car data[J]. Sensors (Basel, Switzerland), 2018, 18(6):E1758.
[25] SONG Chengbo, YAN Xuefeng, STEPHEN N, et al. Hidden Markov model and driver path preference for floating car trajectory map matching[J]. IET Intelligent Transport Systems, 2018, 12(10):1433-1441.
[26] CUI Ge, BIAN Wentao, WANG Xin. Hidden Markov map matching based on trajectory segmentation with heading homogeneity[J]. GeoInformatica, 2021, 25(1):179-206.
[27] QI Hui, DI Xiaoqiang, LI Jinqing. Map-matching algorithm based on the junction decision domain and the hidden Markov model[J]. PLoS One, 2019, 14(5):e0216476.
[28] 郑诗晨, 盛业华, 吕海洋. 基于粒子滤波的行车轨迹路网匹配方法[J]. 地球信息科学学报, 2020, 22(11):2109-2117. ZHENG Shichen, SHENG Yehua, LÜ Haiyang. Vehicle trajectory-map matching based on particle filter[J]. Journal of Geo-Information Science, 2020, 22(11):2109-2117.
[29] 孙文彬, 熊婷. 历史数据和强化学习相结合的低频轨迹数据匹配算法[J]. 测绘学报, 2016, 45(11):1328-1334.DOI:10.11947/j.AGCS.2016.20160046. SUN Wenbin, XIONG Ting. A low-sampling-rate trajectory matching algorithm in combination of history trajectory and reinforcement learning[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(11):1328-1334.DOI:10.11947/j.AGCS.2016.20160046.
[30] YANG Diange, ZHANG Tao, LI Jiangtao, et al. Synthetic fuzzy evaluation method of trajectory similarity in map-matching[J]. Journal of Intelligent Transportation Systems, 2011, 15(4):193-204.
[31] LIU Xiliang, LIU Kang, LI Mingxiao, et al. A ST-CRF map-matching method for low-frequency floating car data[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(5):1241-1254.
[32] LIU Yankai, LI Zhuo. A novel algorithm of low sampling rate GPS trajectories on map-matching[J]. EURASIP Journal on Wireless Communications and Networking, 2017, 2017(1):30.
[33] BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data[C]//Proceedings of the 31st International Conference on Very large Data Bases. Oslo, Norway:[s.n.],2005:853-864.
[34] LUO Linbo, HOU Xiangting, CAI Wentong, et al. Incremental route inference from low-sampling GPS data:an opportunistic approach to online map matching[J]. Information Sciences, 2020, 512:1407-1423.