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

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

Abstract

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

CLC Number:

TP310.6

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.

Figures/Tables 15

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 1

Table 2

Table 3

Table 4

Fig. 7

Table 5

Table 6

Fig. 8

Fig. 9

References 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