北京大学学报自然科学版 ›› 2018, Vol. 54 ›› Issue (6): 1235-1241.DOI: 10.13209/j.0479-8023.2018.038

上一篇    下一篇

一种基于HMM模型改进的地图匹配算法

刘旻, 李梅, 徐晓宇, 毛善君   

  1. 北京大学地球与空间科学学院, 北京 100871
  • 收稿日期:2017-11-15 修回日期:2018-01-02 出版日期:2018-11-20 发布日期:2018-11-20
  • 通讯作者: 李梅, E-mail: mli(at)pku.edu.cn
  • 基金资助:
    国家重点研发计划(2016YFC0803108)资助

An Improved Map Matching Algorithm Based on HMM Model

LIU Min, LI Mei, XU Xiaoyu, MAO Shanjun   

  1. School of Earth and Space Sciences, Peking University, Beijing 100871
  • Received:2017-11-15 Revised:2018-01-02 Online:2018-11-20 Published:2018-11-20
  • Contact: LI Mei, E-mail: mli(at)pku.edu.cn

摘要:

针对轨迹数据在线地图匹配中难以同时保障算法的准确率和时间效率的问题, 提出一种基于隐马尔科夫模型(HMM)改进的在线地图匹配算法, 并提出综合距离因素和方向因素计算发射概率的方法。与其他全局或者局部算法的不同之处在于, 改进的在线地图匹配算法引入可靠点进行轨迹分割, 减少了转移概率的计算和匹配结果的输出延时。用西雅图市浮动车的轨迹数据进行算法的实验验证, 结果表明, 与传统的HMM地图匹配算法相比, 改进的算法在准确率和时间效率上更优, 能够满足在线地图匹配的需求。

关键词: 地图匹配, 隐马尔科夫模型(HMM), 可靠点, 转移概率, 发射概率

Abstract:

For it’s difficult to guarantee the accuracy and time efficiency of online map matching simultaneously, an improved online map matching algorithm based on the HMM model is proposed. Different from other global or local algorithms, the algorithm introduces reliable point to divide the trajectory, thus reducing the calculation of transition probability and the output delay of matching results. Also, the method of calculating the transmitting probability by combining distance factor and directional factor is proposed. The algorithm is verified using floating car trajectory data in Seattle. Experimental results show that the proposed algorithm outperforms the traditional HMM map matching algorithm both in accuray and time efficiency, which can meet the requirement of online map matching.

Key words: map matching, HMM, reliable point, transition probability, transmitting

中图分类号: