采用R树和轨迹分段的HMM高效地图匹配方法

doi:10.16182/j.issn1004731x.joss.21-1020

系统仿真学报 ›› 2023, Vol. 35 ›› Issue (2): 339-349.doi: 10.16182/j.issn1004731x.joss.21-1020

采用R树和轨迹分段的HMM高效地图匹配方法

宋縯蛟¹(), 周佳悦¹, 王龙浩¹, 吴婧¹, 李睿¹, 芮小平²()

^1.河海大学水文水资源学院，江苏南京 210098
^2.河海大学地球科学与工程学院，江苏南京 211100

收稿日期:2021-10-04 修回日期:2021-12-21 出版日期:2023-02-28 发布日期:2023-02-16
通讯作者: 芮小平 E-mail:songyanjiao2000@163.com;ruixpsz@163.com
作者简介:宋縯蛟(2000-)，男，硕士生，研究方向为地理大数据处理与分析。E-mail：songyanjiao2000@163.com
基金资助:
国家自然科学基金(41771478)

Efficient HMM Map Matching Method Using R-tree and Trajectory Segmentation

Yanjiao Song¹(), Jiayue Zhou¹, Longhao Wang¹, Jing Wu¹, Rui Li¹, Xiaoping Rui²()

^1.College of Hydrology and Water Resources, Hohai University, Nanjing 210098, China
^2.School of Earth Sciences and Engineering, Hohai University, Nanjing 211100, China

Received:2021-10-04 Revised:2021-12-21 Online:2023-02-28 Published:2023-02-16
Contact: Xiaoping Rui E-mail:songyanjiao2000@163.com;ruixpsz@163.com

摘要/Abstract

摘要：

针对传统隐马尔可夫模型(hidden-Markov model，HMM)地图匹配算法无法高效处理大量轨迹数据的问题，提出了一种改进的HMM地图匹配算法。采用R树空间索引 方法为路网建立空间索引，基于轨迹点位置变化率对GPS轨迹数据进行分段，并利用R树索引快速确定子轨迹所属的候选路段，在子轨迹中挑选关键点代替整段子轨迹判断所属路段，根据结果完成各子轨迹的地图匹配。仿真结果表明：与传统HMM地图匹配算法相比，改进算法可以同时减少道路搜索和轨迹点遍历的工作量，大幅提高算法效率。

关键词: 隐马尔可夫模型, 地图匹配, R树, 轨迹分段, GPS轨迹数据, 道路网络

Abstract:

In view of the incapability of traditional methods to efficiently process massive trajectory data, an improved HMM (hidden-Markov model) map matching algorithm is proposed. Spatial index for road networks is established through R-tree spatial index. GPS trajectory data are segmented based on the position change rates of trajectory points. R-tree index is used to quickly determine the candidate road section that sub-trajectories belong to, and the key points of the sub-trajectories instead of the entire sub-trajectories are selected to judge which road the sub-trajectories should be matched with. The map matching of each sub-trajectory is carried out on the basis of the former results. The algorithm is verified by a simulation experiment using Beijing's floating car data and OpenStreetMap data. Experimental result shows that the proposed algorithm can reduce the workload of road search and trajectory point traversal and can greatly improve the algorithmic efficiency.

Key words: hidden-Markov model, map matching, R-tree, trajectory segmentation, GPS trajectory data, road networks

中图分类号:

TP310.6

宋縯蛟, 周佳悦, 王龙浩, 吴婧, 李睿, 芮小平. 采用R树和轨迹分段的HMM高效地图匹配方法[J]. 系统仿真学报, 2023, 35(2): 339-349.

Yanjiao Song, Jiayue Zhou, Longhao Wang, Jing Wu, Rui Li, Xiaoping Rui. Efficient HMM Map Matching Method Using R-tree and Trajectory Segmentation[J]. Journal of System Simulation, 2023, 35(2): 339-349.

图/表 15

图1

图2

图3

图4

图5

图6

表1

表2

表3

表4

图7

表5

表6

图8

图9

参考文献 21

1	Xi Liu, Gong Li, Gong Yongxi, et al. Revealing Travel Patterns and City Structure with Taxi Trip Data[J]. Journal of Transport Geography(S0966-6923), 2015, 43(C): 78-90.
2	Yang Zhou, Fang Zhixiang, Jean-Claude Thill, et al. Functionally Critical Locations in an Urban Transportation Network: Identification and Space-Time Analysis Using Taxi Trajectories[J]. Computers, Environment and Urban Systems(S0198-9715), 2015, 52: 34-47.
3	朱递, 刘瑜. 一种路网拓扑约束下的增量型地图匹配算法[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.
4	吴涛, 向隆刚, 龚健雅. 路网更新的轨迹-地图匹配方法[J]. 测绘学报, 2017, 46(4): 507-515.
	Wu Tao, Xiang Longgang, Gong Jianya. Renewal of Roads Networks Using Map-matching Technique of Trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4): 507-515.
5	Cao Wen, Zhao Jing, Meng Weican, et al. Map Matching Algorithm According to Pseudo-Zernike Moments[C]//Second World Congress on Software Engineering. Wuhan: IEEE, 2010: 21-24.
6	Zheng Yu. Trajectory Data Mining: An Overview[J]. ACM Transactions on Intelligent Systems and Technology(S2157-6904), 2015, 6(3): 29.
7	卢家品, 罗月童, 黄兆嵩, 等. 基于排名学习和多源信息的地图匹配方法[J]. 浙江大学学报(理学版), 2020, 47(1): 27-35.
	Lu Jiapin, Luo Yuetong, Huang Zhaosong, et al. An Information Fusion Map Matching Method Based on ranking Learning[J]. Journal of Zhejiang University(Science Edition), 2020, 47(1): 27-35.
8	Ren Ming, Karimi Hassan A. A Fuzzy Logic Map Matching for Wheelchair Navigation[J]. GPS Solutions(S1521-1886), 2012, 16(3): 273-282.
9	Hu G, Shao J, Liu F, et al. IF-Matching: Towards Accurate Map-Matching with Information Fusion[J]. IEEE Transactions on Knowledge and Data Engineering(S2375-026X), 2017, 29(1): 114-127.
10	Bang Yoonsik, Kim Jiyoung, Yu Kiyun. An Improved Map-Matching Technique Based on the Fréchet Distance Approach for Pedestrian Navigation Services[J]. Sensors(S1424-8220), 2016, 16(10): 1768.
11	Ling Yuan, Li Dan, Hu Song. A Map-Matching Algorithm with Low-Frequency Floating Car Data Based on Matching Path[J]. EURASIP Journal on Wireless Communications and Networking(S1687-1499), 2018, 2018(1): 146.
12	Newson Paul, John Krumm. Hidden Markov Map Matching Through Noise and Sparseness[C]//17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS Seattle, Washington: Association for Computing Machinery, 2009: 336-343.
13	陈浩, 许长辉, 张晓平, 等. 基于隐马尔科夫模型和动态规划的手机数据移动轨迹匹配[J]. 地理与地理信息科学, 2019, 35(3): 1-8.
	Chen Hao, Xu Changhui, Zhang Xiaoping, et al. Hidden Markov Model and Dynamic Programming Based Map Matching Method for Mobile Trajectories Using Mobile Phone Data[J]. Geography and Geo-Information Science, 2019, 35(3): 1-8.
14	刘旻, 李梅, 徐晓宇, 等. 一种基于HMM模型改进的地图匹配算法[J]. 北京大学学报(自然科学版), 2018, 54(6): 1235-1241.
	Liu Min, Li Mei, Xu Xiaoyu, et al. An Improved Map Matching Algorithm Based on HMM Model[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2018, 54(6): 1235-1241.
15	王晓蒙, 池天河, 林晖, 等. 一种面向海量浮动车数据的地图匹配方法[J]. 地球信息科学学报, 2015, 17(10): 1143-1151.
	Wang Xiaomeng, Chi Tianhe, Lin Hui, et al. A Research of Map-Matching Method for Massive Floating Car Data[J]. Journal of Geo-Information Science, 2015, 17(10): 1143-1151.
16	Zhou Xibo, Ye Ding, Tan Haoyu, et al. HIMM: An HMM-Based Interactive Map-Matching System[C]//22nd International Conference on Database Systems for Advanced Applications. Cham: Springer International Publishing, 2017: 3-18.
17	吴刚, 邱煜晶, 王国仁. 基于隐马尔可夫模型和遗传算法的地图匹配算法[J]. 东北大学学报(自然科学版), 2017, 38(4): 472-475.
	Wu Gang, Qiu Yujing, Wang Guoren. Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm[J]. Journal of Northeastern University(Natural Science), 2017, 38(4): 472-475.
18	Huang Y, Rao W, Zhang Z, et al. Frequent Pattern-Based Map-Matching on Low Sampling Rate Trajectories[C]//2018 19th IEEE International Conference on Mobile Data Management.Aalborg, Denmark: IEEE 2018: 266-273.
19	Yan Xie, Zhou Kai, Miao Fang, et al. High-Accuracy Off-Line Map-Matching of Trajectory Network Division Based on Weight Adaptation HMM[J]. IEEE Access(S2169-3536), 2020, 8: 7256-7266.
20	吴军. 数学之美[M]. 北京: 人民邮电出版社, 2012: 49-58.
21	Guttman Antonin. R-Trees: A Dynamic Index Structure for Spatial Searching[J]. SIGMOD record(S0163-5808), 1984, 14(2): 47-57.

序号	北纬/(°)	东经/(°)	纬度变化率	经度变化率
1	39.978 728	116.344 453
2	39.978 682	116.344 456	-1.151×10^-6	2.579×10^-8
3	39.978 617	116.344 469	-1.626×10^-6	1.117×10^-7
4	39.978 685	116.344 443	1.701×10^-6	-2.235×10^-7
5	39.978 913	116.344 425	5.703×10^-6	-1.547×10^-7
6	39.979 310	116.344 444	9.930×10^-6	1.633×10^-7
7	39.979 486	116.344 405	4.402×10^-6	-3.352×10^-7
8	39.979 509	116.344 393	5.753×10^-7	-1.031×10^-7
9	39.979 598	116.344 397	2.226×10^-6	3.438×10^-8
10	39.979 493	116.344 384	-2.626×10^-6	-1.117×10^-7

序号	纬度判断	经度判断	子轨迹起点
1			否
2	<	<	否
3	<	<	否
4	<	<	否
5	>	<	是
6	>	<	是
7	>	<	是
8	<	<	否
9	<	<	否
10	>	<	是

序号	北纬	东经	行驶方向
1	39.981 675	116.336 576	93
2	39.981 715	116.336 470	89
3	39.981 727	116.336 485	92
4	39.981 727	116.336 486	95
5	39.981 726	116.336 483	90
6	39.981 727	116.336 501	97
7	39.981 728	116.336 512	91
8	39.981 729	116.336 525	86
9	39.981 729	116.336 523	85
10	39.981 730	116.336 528	87

序号	北纬	东经	行驶方向
1	39.981 675	116.336 576	93
2	39.981 715	116.336 470	89
4	39.981 727	116.336 485	95
6	39.981 727	116.336 501	97
8	39.981 729	116.336 525	86
9	39.981 729	116.336 525	85
10	39.981 730	116.336 528	87

候选路段	方向/(˚)	候选路段	方向/(˚)
1	95	4	173
2	7	5	41
3	6	6	89

采用R树和轨迹分段的HMM高效地图匹配方法

Efficient HMM Map Matching Method Using R-tree and Trajectory Segmentation

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 21

相关文章 3

编辑推荐

Metrics

本文评价

节点编号	概率	路径
1	0.443 2	1-1-1-1-1-1-1
2	0.048 7	1-3-6-1-1-1-1
3	0.023 6	1-5-2-1-6-1-1
4	0.001 5	2-1-5-4-6-3-1
5	0.000 1	5-3-2-4-5-1-6

[1]	何俊, 洪孙焱, 周义方, 申时凯, 邹目权. 基于HMM的多维数据下扶贫对象状态预测[J]. 系统仿真学报, 2022, 34(5): 1118-1126.
[2]	周楠, 艾剑良. 基于HMM和RNN的无人机语音控制方案与仿真研究[J]. 系统仿真学报, 2020, 32(3): 464-471.
[3]	谷志丹, 李擎, 赵辉. 行人自主导航定位的多级滤波方法[J]. 系统仿真学报, 2018, 30(12): 4727-4732.