漫话 | 地图数据处理之道路匹配篇

导读：道路匹配是地图数据处理方面非常基础且重要的理论，特别是道路相关业务，一定避不开道路匹配的应用，这也是业务中普遍会碰到的痛点。

本文属于「漫话地图」系列，我们将结合地图数据业务的特点，持续介绍地图行业一些有趣的知识点，希望能抛砖引玉，为大家带来一定的启思和裨益，欢迎长期关注。

道路匹配定义及应用场景

定义

道路匹配是地图匹配理论的子集，通俗讲就是两幅地图 A 和 B，在没有唯一 ID 关联的情况下，如何确定地图 A 上的道路是 B 上一条道路的过程。如果做交通轨迹或者地图数据融合方面的研究，那么就一定会遇到地图匹配的问题。

地图匹配 Map Matching:不同条件下获取同一物景的地图之间的配准关系。

道路匹配是刨除了点和面状匹配之外的线状要素理论，道路的话就是路网，也是实际应用中研究最多、应用最广的一部分。

利用路网数据，采用适当算法，将目标定位映射到实际道路上的过程，具体来说道路匹配是：

• 地图匹配理论的首要子集

• 针对矢量拓扑道路数据的匹配模式

• 异源道路数据融合的关键

• 导航定位精度改善的重要手段

应用

最常见的应用场景

道路匹配最直观的应用就是地图导航。手机自带 GPS 的定位精度在 10 米上下，单车道的宽度一般是 2-3 米。实际上，手机 GPS 定位不足以精确判断车辆行驶的实际道路。但大家会发现，通常情况下高德导航的道路定位都是很准确的，导航过程中地图会知道用户在某某道路而不是附近小区或者沟河中。

究其原因，用户导航过程中，系统一直在计算 GPS 位置和导航路线 &路网间的配准关系，从而进行一定程度的纠偏，这也是提高定位精度的重要手段。

大家也会经常发现同一手机第三方客户 API 定位效果比高德地图差了不少，刨除硬件因素，实际上这里有算法水平的差异。

空间距离和评价曲线相似性的一般方法

离散点集匹配

路网匹配的两个方面应用：第一个是离散点集匹配，相对简单，随机离散点没有形状和拓扑关系，用欧氏距离作吸附即可，典型应用如离散热力图。

曲线拟合

实际中更有应用价值的是曲线拟合匹配关系，比如轨迹和路网，GPS 序列和导航路的相似性。

曲线信息更多，这方面比离散点集有更多的评价要素，也有更高的复杂度。评价曲线相似性的一般要素有长度、形状、曲率、拓扑关系、方向比如正向逆向、距离、属性例如交通规则左转右转禁行等信息。

算法分类

曲线匹配方法分类

基于几何信息的匹配算法考虑形状、角度等常规要素，属于早期的一些算法，实现最简单，准确度最低。基于拓扑信息的算法，准确度比几何方法大大提升，应用最广。基于概率预测的算法，实现比较困难，实际上应用不多。

目前有一些比较高级的算法理论，包括隐马模型等等，在实际应用中准确度是相对最高的。

实时算法主要用于在线导航，时间和空间复杂度低，离线算法用于数据处理的离线计算，算法复杂，追求最高准确度。

空间距离

线要素的匹配，主要通过几何、拓扑或语义相似度来进行识别，其中通过空间距离来进行要素匹配的常用方式有：

• 闵可夫斯基距离(Minkowski Distance)

• 欧氏距离(Euclidean Distance)

• 曼哈顿距离(Manhattan Distance)

• 切比雪夫距离(Chebyshev Distance)

• 汉明距离(Hamming distance)

• 杰卡德相似系数(Jaccard similarity coefficient)

• 豪斯多夫距离(Hausdorff Distance)

• 弗雷歇距离(Fréchet 距离)

评价曲线相似性-弗雷歇距离

什么是弗雷歇距离?

Fréchet distance（弗雷歇距离）是法国数学家 Maurice RenéFréchet 在 1906 年提出的一种路径空间相似形描述定义。

狗绳距离

弗雷歇距离通俗的讲就是狗绳距离，人和狗之间有一条狗绳约束。主人走路径 A，狗走路径 B，各自走完这两条路径过程中所需要的 最短狗绳长度就是弗雷歇距离。

最大距离最小化

设定 t 是时间点，该时刻曲线 A 上的采样点为 A(t), 曲线 B 上采样点为 B(t)。如果使用欧氏距离，则容易定义 d (A(t),B(t)) 。在每次采样中 t 离散的遍历区间[0,1]，得到该种采样下的最大距离。弗雷歇距离就是使该最大距离最小化的采样方式下的值。

K-WALK 和弗雷歇排列

给定一个有 n 点的路链 P=〈p1 , p2 , … , pn 〉，一个沿着 P 的 k 步分割成为 k 个不相交的非空子集，称为 K-WALK。

给定两个路链 A =〈a1 , …, am 〉, B =〈b1 , …, bn 〉，一个沿着 A 和 B 的组合步(Paired Work)是 A 的 k-walk {Ai}i =1 …k 和一个沿着 B 的 k-walk {B i}i =1 …k 组成(1 ≤i ≤k) 。

链 A 和 B 间的离散 Fréchet 距离(discrete Fréchet distance)就是一个沿着链 A 和 B 的组合步 W={(Ai ,Bi)}的最小花费，这个组合步称为链 A 和 B 的 Fréchet 排列(Fréchet alignment)，也称为最佳组合步。弗雷歇距离实际上就是不断的遍历计算，尝试找出最佳组合步的过程。

利用平均弗雷歇距离评价曲线相似性

采用平均 Fréchet 距离代替离散 Fréchet 距离，因为前者是从顶点距离集合中选取的一个最大距离，易受到局部变形较大点的影响。

基于离散 Fréchet 距离识别曲线上点与点之间最短路径的方法，平均 Fréchet 距离通过计算离散要素点集之间的最短距离的平均值，来度量线要素间的相似性。

全局算法

两条曲线之间的匹配，研究的是 1:1 的关系，实际应用中 GPS 轨迹比较长的时候面临 M:N 全局择优的问题。

进行全局路线匹配时，需要考虑 M:N 的情况来确定整体路径，代表性的算法是使用弗雷歇距离来衡量待匹配序列和候选路段序列的匹配度，并作为路段的权重，由此构建网络图，通过计算最短路径得到最佳匹配结果。

最准确的匹配模型-隐式马尔科夫模型 HMM

除了弗雷歇距离外，再介绍一种高级算法，也是目前应用中准确度最高的一种算法(和最通用解决方案)—隐式马尔科夫模型 HMM。

20 世纪 60 年代，Leonard E. Baum 和其它作者在一系列的统计学论文中描述了隐式马尔科夫模型。它最初的应用之一是语音识别，80 年代成为信号处理的研究重点，现已成功用于故障诊断、行为识别、文字识别、自然语言处理以及生物信息等领域。

核心特征

• 隐式马尔科夫模型五要素：2 个状态集合和 3 个概率矩阵，Viterbi 算法。

• 隐含状态 S：马尔科夫模型中实际所隐含的状态，通常无法通过直接观测得到，这些状态之间满足马尔科夫性质。

• 可观测状态 O：通过直接观测而得到的状态，在隐式马尔科夫模型中与隐含状态相关联。

• 状态转移概率矩阵 A：描述隐式马尔科夫模型中各个状态之间的转移概率。

• 观测状态概率矩阵 B：表示在 t 时刻隐含状态是 Sj 条件下，其可观测状态为 Ok 的概率。

• 初始状态概率矩阵π：表示隐含状态在初始时刻 t=1 的概率矩阵

维特比算法详见:

https://blog.csdn.net/xueyingxue001/article/details/52396494

开源实现 Graphhopper-mapmatching，Java 实现的地图匹配项目，作为开源导航引擎 graphhopper 的子项目提供，最新实现用的是隐式马尔科夫模型，GitHub 地址：

https://github.com/graphhopper/map-matching

解决三类问题

路网匹配实际是一个解码问题，基于 HMM 的路网匹配算法是在一系列观察的前提下，寻找最有可能产生这个观察序列的隐含状态序列。一系列 GPS 位置点集合是可观测状态，寻找最有可能产生位置点集合的路网隐藏序列。

基于隐马尔科夫模型的路网匹配过程

衍生算法集合

其中 STM 算法，稳定健壮，实用性强，有成熟的研究和开源实现。

ACM SIGSPATIAL Cup

2012 年 ACM SIGSPATIAL Cup 是由 ACM 主办的全球范围内关于地图匹配算法的科技竞赛，竞赛吸引了来自全球 31 支专业级的参赛队伍。所有算法当中匹配准确率最高的两个都是基于 HMM 的匹配算法。

道路匹配在业务中的应用

道路匹配在自动化项目中的应用，包括交通轨迹拟合度计算和道路自动识别等。

更多场景，比如异源数据融合、轨迹数据挖掘、交通数据分析、城市规划等领域，道路匹配都有广泛的应用前景。