# An Improved Map Matching Algorithm Based on HMM Model

## LIU Min, LI Mei†, XU Xiaoyu, MAO Shanjun

ACTA Scientiarum Naturalium Universitatis Pekinensis - - CONTENTS - LIU Min, LI Mei, XU Xiaoyu, et al

School of Earth and Space Sciences, Peking University, Beijing 100871; † Corresponding author, E-mail: [email protected]

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 probability

1 地图匹配问题

1.1 路网

1.2 轨迹

1.3 候选路段与候选点

2 基于HMM的地图匹配

HMM 模型是关于时序的概率模型, 主要应用于语音识别及行为分析等领域中。在地图匹配问题中, 轨迹数据是可见的, 视为观测序列; 实际经过的道路不可见, 视为隐形的状态。使用 HMM 算法进行地图匹配, 解决的是预测问题, 即基于给定的观测序列, 得出条件概率最大的状态序列, 利用动态规划进行求解, 过程如下。

3 研究方法

3.1 数据预处理

3.1.1 建立路网有向图

3.1.2 生成网格索引

3.2 轨迹分割3.2.1 候选集获取

3.2.2 发射概率计算

[9] Newson 等 认为观测到的轨迹点符合正态分布, 可以使用高斯函数来表达距离因素的发射概率,相应的计算公式为

1  || pi  ci k ||2  P ( p |l k ) exp  , (1) d ii 2 π   2 2 

i i在 Newson 等[9]的算法中, 发射概率仅与距离因素有关。本文认为发射概率的计算也需要考虑方向权重。轨迹点 pi的速度方向与路段的方向一般是一致的, 其瞬时速度方向与候选路段的夹角越小, 通过轨迹点匹配得到路段的可能性越大。方向因素的发射概率的计算公式为P ( p | lk )  (1  cos k )/2, (2)  ii i其中, k为速度方向与匹配路段的夹角。以正北方i向为基准, 计算速度和匹配路段与正北方向的夹角分别为i 和ik , 则 ik的计算公式为 ,  180。,  ik  i ik i k   i (3)。 。 360  k , k  180 i  i i i综合距离因素和方向因素, 发射概率的计算如下: P ( p | lk )  P ( p | lk ) P ( p |lk )。(4) ii d ii  ii

3.2.3 可靠点判断

[9] Newson 等 的地图匹配算法是对整条轨迹进行全局匹配, 当在线地图匹配中轨迹点数量较多时,该算法输出时延较长。针对此问题, 本文利用可靠点将轨迹分割成不同的增量, 能够保证轨迹增量两端匹配的准确性。

 , (5) P ( pi | lin )其中, 可靠点参数 λ 是一个经验参数, 其作用是对可靠点进行区分。可靠点的获取相当于对传统的点到线的地图匹配算法的改进。传统的基于点到线的地图匹配算法是基于距离和方向因素构建权重函数, 将权重最大的点作为匹配点, 具备较好的准确率。可靠点的获取是在此设置阈值 λ, 思路是基于数据统计及处理经验, 保证了可靠点处的匹配准确率。λ值的选取将在实验部分进行分析。

3.3 地图匹配算法3.3.1 传递概率状态转移概率代表从一个候选路段移动到另一个候选路段的过程。下面进行轨迹增量内状态转移概率矩阵的计算。本文中传递概率的计算基于一个假设: 出租车司机一般选择最近的路线行驶, 前后路段间的路网距离越小, 其传递概率越大。传递概率公式为

j P (l | li )  exp(dis) , (6)

t 1 t其中, lt 和 lt 分别为第 t+1 个轨迹点和第 t 个轨迹j i 1点对应的候选路段, 是人为设定的参数, Dis 代表从候选路段间的实际路网距离。区别于使用传统的BFS 算法(如 Dijkstra 算法), 本文使用启发式的A*算法进行路网距离的计算。A*算法不需要遍历路网中所有的路段, 其距离估算值与实际值越接近,算法运行速度越快, 效率越高。

3.3.2 维特比算法输出最优路径

11 func[ l 1]  P ( pi 1| l 1)max {func[ l 2] P ( l 1| l2 )}  l Li 2 12 k  argmax {func[ l 2] P ( l 1| l2 )} l Li 2 13 prev[ l 1] k 14 End  argmax {func[l]} //获取全局最优路径l Ln

4.2 实验结果

m,

AC  (7) n

5 结语

[1] Yuan J, Zheng Y, Xie X. Driving with knowledge from the physical world // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge 316‒324 Discovery and Data Mining. San Diego, 2011: [2] Chen C, Zhang D, Castro P S. Isolation-based online anomalous trajectory detection. IEEE Transactions 806‒818 on Intelligent Transportation Systems, 2013, 14(2): [3] Li X, Han J, Lee J, et al. Traffic density-based discovery of ho routes in road networks // Advances

in spatial 441‒459 and temporal databases. Berlin: Springer, 2007: [4] Zheng Y, Liu Y, Yuan J. Urban computing with taxicabs // Proceedings of the 13th International Conference 89‒98 on Ubiquitous Computing. Beijing,: ACM, 2011: [5] Zhang J T. Smarter outlier detection and deeper understanding of large-scale taxi trip records: a case study of NYC // Proceedings of the ACM SIGKDD

International 157‒162 Workshop on Urban Computing. Beijing, 2012: [6] 袁晶. 大规模轨迹数据的检索、挖掘及应用[D]. 合

Fig. 6 图 6 路网数据和轨迹数据Road network data and trajectory data