该要

Map-matching是指将手机gps上报的轨迹点（经纬度）映射到路网上。由于精度问题，上报的轨迹点通常和实际位置有所偏差，因此产生了很多算法进行绑路，其中效果最好的是hmm（隐马尔可夫模型）的应用。本文简单介绍将hmm模型运用在map matching（轨迹点绑路）上。

示意图

hmm模型五个变量定义

状态值的取值空间：图中所示有五条线段，因此状态空间为{S1,S2,S3,S4,S5}。考虑到map-matching是一个处理连续轨迹点的问题，因此我们可以以当前点的位置坐标出发，一定范围内的link都属于状态空间。有时连续两个gps点的位置差异过大，超过一定范围的点称之为跳点，对于跳点需要过滤掉。

观察值: {o1,o2,o3,o4,o5,o6,o7,o8}（经纬度，方向，速度等）。

转移概率矩阵：这里最主要考虑到的是轨迹的连续性。设想如果当前轨迹点在L1上，那么下一个轨迹点大概率出现在和它联通的link上，也就是{L1,L2,L5}。其中转移到本身的概率可能更高（特别是link比较长时）。而转移到{L3,L4}上的概率就比较低了，其中距离越远，概率越低。转移矩阵时一个N×N的矩阵，其中N表示link的数量。

其中转移矩阵中的Rij表示从Li转移到Lj的概率 

观察概率矩阵：如果观察到的点离link越近，那么它属于这条link的可能性也就越大。参考文献中是如下定义的。

它是一个M×N的矩阵，其中Oij表示第i个观察点属于在link j中概率 

初始状态向量：它表示在o1点在各link中出现的概率值。它是一个N×1的矩阵，其中Ii1表示初始点出现在link i中的概率值。

Viterbi算法

定义好hmm模型的5个变量值后，我们实际求解的是每个观察点最大概率出现在哪条link上，并计算出投影值（实际真实位置）。其求解过程可以使用经典的Viterbi算法。

从初始的状态向量开始，它其实表示的是o1出现在link[n]中的概率值。由此可以计算出o2出现在link[n]中的概率值。假设o2出现在link1中，存在的路径包括link[1->1]（o1出现在link1中，o2也出现在link1中），link[2->1]，一直到link[N->1]。我们只需要保留这N个概率值中的最大值，原因是马尔可夫链中的前提条件就是下一个状态值只和当前状态值有关，和历史的状态值无关。这也和我们使用的场景是相符合的，下一个点的位置只和当前位置有关，而和历史位置是无关的。

P[link[i] -> link[j]] = P[link[i]] * R[i->j] * O[j|k]

（当前观察点从link[i]转移到link[j]的概率是前一个观察点属于link[i]的概率，乘以link[i]到link[j]的转移概率，再乘以当前观察点属于link[j]的观察概率）

逐一计算每个观察点属于link的概率值，同时保留属于各link的最大概率路径，直到遍历所有的观察点。再最后计算出的N个概率值中，选择最大概率值，这个各观察点所属的link就确定下来了。

效果评估

Map-matching的绑路结果通常可以有两种评估方式。一是通过人工标注来实现，二是通过其它辅助工具，如行程记录仪来判断绑路的效果。

总结

使用hmm模型计算map-matching能获取到比较高的准确率（文献中提到能到达90%以上）。保留轨迹点数越多，理论上计算的准确率就越高，但是性能会下降，需要做好平衡。另一方面，在主辅路/高架/隧道等场景下却难以识别，需要添加策略辅助。

参考文献

Matlab算法案例--- 基于隐马尔科夫模型(HMM)的地图匹配(Map-Matching) - 知乎

隐马尔可夫链_丁叔叔的博客-CSDN博客_隐马尔可夫链

[LBS]地图Map-Matching流行算法及应用 – Semocean