原文链接：https://www.cnblogs.com/LBSer/p/4612031.html

1 背景

　　如下图所示，1、2、3这三个点是汽车的GPS定位结果，尽管汽车是在道路上，但定位结果与道路存在偏差。地图匹配（Map Matching）是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程，其本质上是平面线段序列的模式匹配问题（ Alt等，2003）。

　　在实际应用中，GPS采样信号的质量会严重影响地图匹配结果：采样频率的降低、定位误差的加大、信号的丢失，都会使匹配的不准确性增加。这些情况在实际应用中经常出现。如何在这些情况下仍能保持较高的路径匹配准确率是个值得研究的问题。

　　2012年ACM SIGSPATIAL首次设立的竞赛，其内容就是地图匹配。三年前本人有幸和国防科大的杨岸然博士一同参加了该竞赛，收获良多。本博文也就是对参加竞赛的工作做一个简要的总结回顾，想要代码参考的朋友可以在下面留下邮箱，并注明用途。

　　

2  地图匹配算法综述

2.1 以使用到的信息来划分

　　现有的算法可被分成四类：几何、拓扑、概率、高级。

　　a）基于几何的算法考虑GPS点与道路的几何信息，如距离、角度等； 　　b）基于拓扑的算法使用道路拓扑信息来控制； 　　c）概率方法通过考虑GPS点的概率； 　　d）高级的算法往往综合考虑使用全面信息，有卡尔曼滤波、模糊逻辑模型、隐式马尔可夫模型等等。

2.2 以考虑采样点的范围来划分

　　根据考虑采样点的范围，可分成局部/增量算法、全局算法。

　　a）局部/增量算法是贪婪算法，每次确定一个匹配点，下个点从已经确定的匹配点开始。这些方法根据距离和方向相似性来找到局部最优点或边。（在线匹配） 　　b）全局算法是要从路网中找到一条与采样轨迹最接近的匹配轨迹。为了测量采样轨迹和匹配轨迹的相似性，大多数算法使用“Frechet距离”或者是“弱Frechet距离”。还有时空匹配算法、投票算法等。（离线匹配）

2.3 以采样点的频率来划分

　　根据轨迹数据的采样频率，现有的地图匹配算法可分成：

　　a）高频采样算法（所有局部算法、部分全局算法如Frechet距离判别法等）

　　b）低频采样算法（ST-matching算法、IVVM算法