一种基于理想隐性马尔科夫模型的地图匹配算法

冯 通，杜文才

(海南大学 信息科学技术学院，海南 海口570228)

近年，随着民用GPS(Global Positioning System，全球定位系统)等定位设备在移动终端上的广泛使用以及基于位置服务(Location-Based Service)和移动社交网络(Mobile Social Network )的发展和普及，大量的轨迹数据在日常生活中正在日益积累. 为了分析和处理这些数据，需要将轨迹点映射到道路网络中.

尽管有些应用，如车辆导航等，系统需要掌握移动对象精确的轨迹信息，但大多应用仅需获知移动对象所经过的道路序列即可，这些应用包括公交路径规划、交通流统计等. 因此，对低频采样轨迹点的地图匹配提出了要求. 然而，轨迹数据的稀疏性、设备的测量误差及路网数据的偏差向这一工作提出了挑战.于是，对GPS 数据稀疏性及数据噪声的算法研究成为学者们研究的热点. 文献［1］提出了一种基于Frechet 距离的全局地图匹配算法，拥有较高的正确率，但它的计算复杂度较高. 文献［2］提出了一种基于隐性马尔科夫模型(Hidden Markov Model，HMM)的地图匹配算法，该算法能够有效的找出移动对象经过的道路序列. 文献［4］中针对地图匹配算法做了较为全面的总结. 文献［5］提出一种用于在线完成这一过程的算法，即增量式地图匹配. 文献［6］利用近似算法加快了这一过程，并指出当GPS 采样频率较高时，即使仅将轨迹点匹配至最近的道路片段也可得到较高的正确率. 文献［7］提出了一种基于历史轨迹的路网匹配算法，通过历史轨迹来推出移动对象可能经过的道路. 文献［8 －10］提出了一种基于多假设的路网匹配算法. 以上文献工作均需要较为复杂的数据模型，不便于算法的高效实现.

因此，笔者提出了一种基于理想马尔科夫模型的地图匹配算法，其次在不同程度的简化路网下，分别对所提算法的性能进行了评估，这也为如何选择合适的道路网络采样密度提供了重要的参考.

1 问题描述

地图匹配问题的形式化描述如下

输入 一系列GPS 观察点，其中Ot=(xt，yt)包含在时间t 时，移动对象的经度和纬度;道路网络G =(V，E)，其中，cpi代表路网的交叉点(以下简称CP)，即路口或道路中的转折点;为一系列有向边，代表路网中的道路片段.

输出 一系列相连的道路序列其中，表示与观测点匹配的道路片段.

图1 为地图匹配的示例图，其中观察点序列为(1，2，3，4，5)，道路网络中包含15 个CP(A，B，…，K，W，X，Y，Z)及相应的连接道路. 本示例中，观测点可被匹配到多种道路序列中，比如观测点序列(1，2，3)可以被匹配到蜿蜒道路(A，B，C，…，G，H)或被匹配到高速公路(X，Y，Z). 地图匹配的目的是找到移动对象经过的最大似然的CP 序列.

另一方面，地图匹配的精度还受道路粒度的影响. 如图2 所示，本文将路口和道路的转折点处均视为CP. 在许多地图数据中，如OpenStreetMap［3］，道路被表示为CP 的序列. 此外，当前的地图匹配算法多是用观测点在道路上的几何投影的方式来获取道路候选集.

图1 地图匹配示例

图2 用交叉点（CP）表示道路网络

2 基于隐性马尔科夫模型的地图匹配

在HMM 模型中，假设移动对象在CP 间移动，且移动的过程符合马尔科夫模型. 由于无法直接观察到移动对象所经过的道路轨迹，所以将这些轨迹称为隐性状态. 不过，可以观测到隐性状态的输出，即GPS 序列点. 此外，还假设观测值仅与移动对象的隐性状态相关.

图3 给出了隐性马尔科夫模型的示意图及本文所采用的模型与先前工作的对比. 其中，上半部分代表隐性状态间的转移，而下半部分代表相应的观察结果.

图3 2 种HMM 模型对比

隐性马尔科夫模型主要包含3 种概率

发射概率(Emission Probability)代表在特定隐性状态下，得到某观察值的概率，表示为Pr(Ot|CPt=cpi)，即在时间t，隐性状态为cpi时，观察值为Ot的概率. 与先前的工作相同，认为观察点符合正态分布，中心位于cpi.

状态转移概率(State Transition Probability)代表移动对象从一个CP 移动至另一个CP 的概率，对应于图3 所示理想隐性马尔科夫模型中的状态转移. 假设状态转移概率与CP 间的距离正相关，即

其中，β 用于调节cpi与cpj间最短距离dij对结果的影响.

起始状态概率 代表移动对象初始时位于某CP 的概率，实验中使用相应CP 的发射概率来表示移动对象的起始状态概率，即

2.1 与先前工作对比 文献［2］中，状态转移概率定义如下

其中，Rt表示Ot在道路网络上的投影点，dRt，Rt－1代表Rt与Rt+1间的路网距离. 这种状态转移概率依赖于当前及上一次观察状态，因此不能严格满足Viterbi 算法中对状态转移概率的要求. 这种不足是由于算法设计时的一些考虑导致的，也导致2 个问题得产生. 首先，为了利用Viterbi 算法计算转移序列，需要利用式(1)近似得到Pr(Rt+1|Rt)，但利用此近似概率得到的结果并非一定是式(1)的最大似然结果. 再者，式(1)将Rt在路网上的几何投影作为移动对象隐性状态的一部分. 但轨迹点在路网上投影并不唯一，这就增大了HMM 最大似然解的寻找难度.

为了解决上述问题，使用离散的路网采样点而非道路本身来表示移动对象的隐性状态，从而保证算法找到最优路径. 实验结果显示，尽管算法的实现较为简单，但仍能取得与文献［2］中所提方法相似的性能.

2.2 算法实现 根据文中所提的概率计算方式，可以利用Viterbi 算法求出在理想隐性马尔科夫模型下移动对象的最大似然的CP 序列. 算法的求解细节与文献［2］相似，由于篇幅限制，本文仅给出IHMM 算法的基本步骤.

针对每一个GPS 点，首先找到与之相近的所有CP，并计算相应的发射概率，然后将GPS 轨迹点和CP序列作为Viterbi 算法的输入，并计算得出最大似然的CP 序列. 通过上述描述，可以看出算法的结果与CP 的采样粒度相关. 为此，在不同CP 粒度的路网下测试了本文算法.

3 实 验

用Microsoft Dataset(MD)［2］作为地图匹配算法的测试数据集. 其中包含7 531 个GPS 轨迹点，采样间隔为1 s，行驶距离为81 km. 为了模拟GPS 轨迹点的稀疏性，分别将采样间隔设为90 s、120 s、180 s、240 s、300 s、360 s、420 s、480 s、540 s 和600 s. 采用文献［2］提出了方法道路错误匹配指数(Route Mismatch Fraction，RMF)来评估算法的性能，并与其中的算法(以下简称HMM)进行对比. IHMM 算法的参数:σ=1.0，β=100.0，对于每个GPS 点，找出拥有最大发射概率的3 个CP.

图4 性能对比

图5 算法效率对比

图4 显示了在不同采样频率下的地图匹配算法的性能. IHMM 的RMF 稍高于HMM，这是由于未进行数据的预处理来去除其中的噪声. 从图4 中可以看出，尽管IHMM 实现较为简单，但然拥有与HMM 相似的性能. 在采样间隔上升至600 s，RMF 出现少许下降. 如文献［2］中所述，RMF 指标由匹配正确和匹配错误的点数量共同决定. 随着采样间隔的增加，采样点数量也迅速降低，算法的正确率逐渐下降. 此时错误点减少的数量逐渐超过正确点减少的数量，从而导致RMF 出现少许降低.

图5 显示了IHMM 算法及HMM 算法在不同采样间隔下的匹配速度，其中IHMM 的匹配速度约为HMM 算法的2 倍，这是在由于IHMM 算法中不需要计算轨迹点向道路边的投影，且IHMM 算法中状态转移概率计算较为简单.

图6 道路简化示意

此外，通过去除路网中的10%、20%、30%、40%、50%、60%、70%和80%的CP 来模拟稀疏路网. 图6 为去除50%的CP 点的所得简化路网中，道路片段的平均长度依次为:55 m、61 m、67 m、72 m、80 m、87 m、94 m 和102 m. 在采样间隔为90 s 的GPS 轨迹点上进行地图匹配实验. 结果显示随着道路稀疏程度的增加，算法的性能变化较小，如当道路片段长度有87 m 降低至55 m 时，匹配错误的轨迹点数量仅增加9%. 但当道路片段增加至94 m 时，算法的性能开始出现快速下降.

4 小 结

本文给出了一个基于理想隐形马尔科夫模型的地图匹配算法，该算法实现更为简单，且在处理低频采样的GPS 轨迹时仍有较好的性能. 在真实数据集上对算法进行了测试，实验结果显示所提算法与先前复杂的算法拥有相近的性能. 此外，实验结果显示在约半数交叉点被移除的情况下，算法依然拥有较好的性能.

［1］BRAKATSOULAS S，PFOSER D，SALAS R，et al. On map-matching vehicle tracking data proceeding of the 31st VLDB Conference，Trondheim，August 30-September 2，2005［C］. ［S.l.］:ACM，2005.

［2］NEWSON P，KRUMM J. Hidden markov map matching through noise and sparseness proceeding of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，Seattle，November 4-6，2009［C］. ［S.l.］:ACM GIS，2009.

［3］OpenStreetMap.［EB/OL］.［2014 －03 －01］. http:∥www.openstreetmap.org.

［4］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］. Transport. Res. Part C:Emerging Tech，2007，15:12 －328.

［5］GOH C Y，DAUWELS J，MITROVIC N，et al. Online map-matching based on Hidden Markov model for real-time traffic sensing applications proceeding of the 15th International IEEE Annual Conference on Intelligent Transportation Systems，Anchorage，September 16-19，2012［C］.［S.l.］:［s.n.］，2012.

［6］CHEN D，DRIEMEL A，GUIBAS L J，et al. Approximate map matching with respect to the Fréchet distance proceeding of The Workshop on Algorithm Engineering and Experiments (ALENEX11)，San Francisco，January 22，2011［C］. Philadelphia:SIAM，2011.

［7］ZHENG K，ZHENG Y，XIE X，et al. Reducing uncertainty of low-sampling-rate trajectories proceeding of the 28th International Conference on Data Engineering (ICDE)，Washington DC，April 1-5，2012［C］.［S.l.］:［s.n.］，2012.

［8］ABDALLAH F，G. NASSREDINE G，DENOEUX T. A multiple-hypothesis map-matching method suitable for weighted and box-shaped state estimation for localization［J］. IEEE Trans. on Intelligent Transportation Systems，2011，12(4)1495 －1510.

［9］REID D. An algorithm for tracking multiple targets［J］. IEEE Trans. on Automatic Control，1979:24(6)843 －854.

［10］PYO J S，SHIN D H，SUNG T S. Development of a map matching method using the multiple hypothesis technique proceeding of the Intelligent Transportation Systems，Oakland，August 25-29，2001［C］.［S.l.］:［s.n.］，2001.