道路匹配原理综述

导读：本文首发于高德技术,此次为作者转载.道路匹配是地图数据处理方面非常基础且重要的理论，特别是道路相关业务，一定避不开道路匹配的应用，这也是业务中普遍会碰到的痛点。

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

道路匹配定义及应用场景

定义

道路匹配是地图匹配理论的子集，通俗讲就是两幅地图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距离通过计算离散要素点集之间的最短距离的平均值，来度量线要素间的相似性。