Laurenfrost's Blog.
今朝有酒今朝醉，明日愁来明日愁。
Map Matching as Service
综述阅读：地图匹配问题
Contents
该综述源自 Université libre de Bruxelles 的相关研究 MobilityDB，作者 Mohammadreza Amini。
原文开放获取：https://docs.mobilitydb.com/pub/MobilityDB-MapMatching.pdf
摘要
地图匹配问题包括将可以抽象为（经度、纬度、时间）三元组的GPS测量数据与道路网络匹配，以识别车辆行驶的正确路径。仅使用GPS数据来确定车辆的位置和路径是不够的，因为GPS点可能不准确，并且在某些区域存在GPS信号阻塞。这就是地图匹配问题重要的原因，因为它可以提高导航系统的性能，并将GPS点与底层道路网络匹配。
有许多工具和算法可以解决地图匹配问题。这些工具在解决问题的方式上有所不同。有些使用几何方法，而另一些则使用概率模型方法。本文的目的是首先给出问题和现有解决方案的最新研究，其次是测试一些知名的现有工具，以查看这些工具的结果和性能。
我们在工具测试和实验中使用的所有数据都是作者收集的真实数据。这为我们提供了对道路网络的必要领域知识，以更好地分析和观察结果。实验的目的是查看这些工具如何相互区分。
导论
地图匹配问题乍看之下似乎相对简单。可以简单地将每个GPS点匹配到最近的道路段。然而，这可能会产生不准确的结果，因为GPS点可能不准确，并且在密集的城市区域，存在许多彼此接近的道路段。另一种解决方案是考虑一系列GPS点，并用它们创建一条弧线，然后将其匹配到最近的道路段。当GPS样本不够准确时，这也可能产生不准确的结果。因此，我们需要一种更复杂的解决方案，考虑到GPS样本的不准确性。 一些拓扑和高级方法被提出以解决上述几何方法的问题。然而，这些方法在道路段彼此接近的城市区域并不那么准确。 迄今为止提出的最佳方法之一是使用隐马尔可夫模型（HMM）来解决地图匹配问题。这种方法利用过去匹配点的知识来匹配当前点，显示出良好和准确的结果。 首先，本文通过描述一些提出的方法，给出了地图匹配问题的最新研究。它重点介绍了HMM地图匹配，并详细解释了如何使用HMM解决问题。其次，本文使用作者收集的真实数据测试了一些现有的地图匹配工具，以查看这些工具的表现。实验旨在通过概述工具的性能和准确性来展示测试工具之间的差异。 本文结构如下。第一部分给出了地图匹配问题的最新研究，而第二部分则重点介绍了现有工具的实验。在第一章中，通过给出一些关于问题和数据格式的定义，描述了地图匹配问题。随后，简要描述了一些现有的方法。在第二章中，我们首先讨论了马尔可夫模型和隐马尔可夫模型，给出了一些定义，然后重点介绍了如何使用HMM解决地图匹配问题。我们还讨论了一些可以对算法进行的优化。我们通过简要介绍一些使用HMM进行地图匹配的工具来完成这一章。这些工具将在第二部分的实验中使用。在第三章中，我们首先解释了真实数据的格式和实验的方式，然后重点介绍了测试工具的性能基准。最后，第四章通过比较工具测试的结果，重点评估了获得的结果。
Part I 当前的最新研究成果
** *笔记：本文写于 2021-2022
1 地图匹配问题
1.1 问题描述
在 [1] 中，地图匹配（简称MM）问题被定义为利用传感器数据确定车辆所在道路的过程。同样，[2] 将地图匹配定义为将观察到的用户位置序列与数字地图上的道路网络对齐的过程。同时，[3] 给出了一个更正式的定义：“地图匹配将定位数据与空间道路网络数据（道路中心线）集成，以识别车辆行驶的正确链接，并确定车辆在链接上的位置”。由于其在导航系统和交通运输中的广泛应用，地图匹配一直很重要且仍然重要。车载导航系统使用不同的地图匹配算法将GPS数据与底层道路网络对齐。交通运输行业使用地图匹配来监控和分析其货物的移动。它还用于交通流量管理。随着车辆导航系统被用来建立交通模型，以帮助选择交通拥堵较少的最快道路，地图匹配变得越来越重要。 地图匹配有两种类型，在线地图匹配和离线地图匹配。在在线地图匹配中，需要实时确定对象当前位置，而在离线地图匹配中，给出了一系列位置，这意味着在运行地图匹配算法时，所有未来位置都是已知的 [4]。在在线地图匹配中，地图匹配是通过作为流的实时GPS数据完成的，并且没有未来数据的知识。算法必须足够快以处理传入数据并匹配每个位置。在离线地图匹配中，有一系列位置，算法可以利用关于先前位置的知识来匹配当前位置。
1.2 数据格式
地图匹配中使用的传感器数据主要是GPS数据，因为它广泛可用。地图匹配算法使用GPS数据将GPS坐标与底层道路网络匹配。了解GPS格式和地图表示方式对于开发可靠的地图匹配算法非常重要。
1.2.1 GPS 数据格式
一种广为流传的 GPS 数据格式是 GPX（GPS Exchange Format）。GPX 借助于 XML 形式来描述数据，是专门为 GPS 数据相关的程序设计的一种格式。GPX 可以包含航点 waypoints（路线或行程中的中间点或位置）、轨迹 tracks（GPS 坐标）和路线 routes。这些位置数据包含经度和纬度，同时也可以包含海拔、时间、速度、航向和其他相关信息。
在示例1.1中，你可以看到一个GPX示例文件。我们可以看到，我们有一个轨迹段的列表，每个轨迹点包含一个纬度和经度。此外，还有海拔和时间等附加信息。除了<trk>标签，我们还可以有以下标签：
<wpt>包含一个单独的航点。<rte>包含一条路线。
** *笔记：感觉很有趣的一点就是，这里给出的例子基本都是佳明 Garmin 定义的。搜了一下发现中文维基 上使用了相同的代码示例。
<? xml version="1.0" encoding="UTF-8" standalone="no" ?>
<gpx
xmlns="http://www.topografix.com/GPX/1/1"
xmlns:gpxx="http://www.garmin.com/xmlschemas/GpxExtensions/v3"
xmlns:gpxtpx="http://www.garmin.com/xmlschemas/TrackPointExtension/v1"
creator="Oregon 400t"
version="1.1"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.topografix.com/GPX/1/1
http://www.topografix.com/GPX/1/1/gpx.xsd
http://www.garmin.com/xmlschemas/GpxExtensions/v3
http://www.garmin.com/xmlschemas/GpxExtensionsv3.xsd
http://www.garmin.com/xmlschemas/TrackPointExtension/v1
http://www.garmin.com/xmlschemas/TrackPointExtensionv1.xsd">
<metadata>
<link href="http://www.garmin.com">
<text>Garmin International </text>
</link>
<time>2009-10-17T22:58:43Z</time>
</metadata>
<trk>
<name>Example GPX Document</name>
<trkseg>
<trkpt lat="47.644548" lon="-122.326897">
<ele>4.46 </ele>
<time>2009-10-17T18:37:26Z</time>
</trkpt>
<trkpt lat="47.644548" lon="-122.326897">
<ele>4.94 </ele>
<time>2009-10-17T18:37:31Z</time>
</trkpt>
<trkpt lat="47.644548" lon="-122.326897">
<ele>6.87 </ele>
<time>2009-10-17T18:37:34Z</time>
</trkpt>
</trkseg>
</trk>
</gpx>
Listing 1.1: GPX sample file
1.2.2 地图表示
在地图匹配中，我们需要了解底层的道路网络，以便将 GPS 数据匹配到道路上。这就是为什么在地图匹配算法中使用地图服务器的原因。与地图表示相关的一个领先且知名的项目是 OpenStreetMap（OSM）。OSM 是一个免费且开源的项目，允许用户创建一个免费的可编辑的世界地理数据库。OSM 提供了世界、国家和城市的地图表示，其中包含道路网络等。
用户可以从 OSM 下载世界上每个城市和国家的地图文件。正是由于它的可用性和多功能性，几乎所有的地图匹配服务都使用 OSM 进行地图表示。
1.3 现有方法
世界各地的工业界和研究人员开发了广泛的地图匹配算法。这些算法使用不同的技术，并且它们的性能也不同。有些算法比其他算法更准确，而有些则更快。算法的性能和正确性在很大程度上取决于其实现和输入数据。确保用于服务的地图匹配算法满足该特定服务的指定要求是至关重要的 [3]。
有不同的方法来解决将 GPS 点匹配到道路的问题。每种方法都有其自身的优缺点。在[3]中详细介绍了几种解决地图匹配问题的方法，我们将在接下来的小节中简要讨论这些方法。
1.3.1 几何方法
*所谓几何方法换句话说其实就是比较 GPS 数据和实际 road_link 的距离，离谁最近就是谁。不同方法的区别也仅仅是如何定义“距离”。 基于几何方法的算法只需要从路网空间数据中考虑 road_link 本身的形状。这意味着这种方法不考虑整个 road_link 网络是如何连接在一起的。[5]中列出了三种几何方法。
点到点匹配
这种方法会将每个点 $P_i$ 匹配到道路段的最近节点或形状点。在这种方法中，定义“接近”是很重要的。最常见和自然的定义最近点的方法之一是使用欧几里得距离公式。对于每个点，我们不必计算与网络中所有形状点的距离。我们可以定义一个合理大的半径，并且只计算该半径内点与形状点之间的距离，然后选择最近的一个。在图1.1中，你可以看到点到点匹配的示意图。这里与 $A^0$ 或 $A^1$ 相比 $P^t$ 更接近 $B^1$，因此它将匹配到弧 $B$，尽管直观上它应该匹配到弧 $A$。
尽管这种方法快速且易于实现，但它不是最实用的方法。其准确性和正确性在很大程度上取决于空间道路网络的创建方式。网络中具有更多形状点的弧更有可能与给定点匹配。因此，这并不总是产生最准确的解决方案。 *这里就是对道路取几个端点，单纯算点 $P^t$ 附近最近的端点，不看 road_link 本身的距离，谁离得近就是谁。
图1.1 点到点地图匹配示意图
点到曲线匹配
*这里就是算点和线段之间的距离。 在这种方法中，点 $P_i$ 被匹配到网络中最近的曲线。这里再次出现定义“接近”量的问题。要找到点 $x$ 到曲线 $A$ 的最小距离，必须找到 $x$ 到组成 $A$ 的每个线段的最小距离，并选择最小的那个。然后选择这个最小的线段作为点的匹配。在图1.2中可以找到这种方法的示意图。绿色路线代表车辆实际行驶的路线，我们可以看到，点 $P^3$ 被错误地匹配到了错误的道路上。
显然，这种方法比点到点方法产生更好的结果，但它也有一些自身的缺陷，使其在实践中不太可用。这种方法在道路密度高的区域（例如城市区域）中不会返回良好的结果。原因是，在这些区域中，最近的链接并不总是一致的正确选择，数据中的噪声甚至可能导致更多的错误结果。另一个问题是，这种方法不利用历史信息。也就是说，它不使用关于最后匹配点的任何知识，因此在匹配时可能会做出错误的选择。当然，这是几何方法中的一个更普遍的问题。
图1.2 点到曲线地图匹配示意图
曲线到曲线匹配
*单纯比较 GPS 点和 road_link 之间的距离不准确，那我们把一系列 GPS 点构成的曲线和 road_link 匹配不就正确率高了吗？ 最后，一种更好的方法是考虑 $m$ 个点在一起，并将它们匹配到与这些 $m$ 个点构建的分段线性曲线最近的弧。这意味着我们将车辆的轨迹与道路进行比较。
这需要测量两条曲线之间的距离。为此，首先从 $m$ 个点创建一条曲线，然后确定创建的弧与网络中其他道路弧之间的距离。最后，我们选择最近的弧作为匹配的轨迹。在图1.3中可以找到这种方法的示意图。这种方法在很大程度上取决于曲线中点的排序方式，因为它使用点到点方法来计算这些点之间的距离。因此，这种方法有时会产生意想不到的结果。
图1.3 曲线到曲线地图匹配示意图
1.3.2 拓扑方法
在这种方法中，我们尝试利用点、线和多边形等实体之间的关系。利用链接的几何形状以及链接的连接性和连续性的地图匹配算法被称为拓扑地图匹配方法。
加权拓扑算法（Weighted Topological Algorithms）就可以用来解决地图匹配问题 [6]。这是基于道路网络的拓扑分析，并且只使用数据位置点的经度和纬度信息。该算法不考虑任何航向、速度或海拔信息。该算法对异常值非常敏感。在实现该算法时必须谨慎对待异常值。
另一种类型的算法利用车辆轨迹与道路的拓扑特征（如道路转弯、道路曲率和道路连接）之间的相关性 [7]。在这种算法中，首先通过分析现场数据的统计信息定义一些阈值。然后在匹配点时使用这些阈值来消除一些候选道路段。该算法在道路方向不相似的交叉口处会遇到一些困难。为了解决这个问题，该算法使用后处理，但这使其不适合在线地图匹配。
最后，[8] 提出了一种增强的拓扑算法，该算法基于道路网络几何形状和派生导航数据之间的相似性标准。为了提高性能，还考虑了其他标准和参数，如车辆速度、车辆相对于候选链接的位置和航向信息。然后根据算法中定义的各种加权因子应用最佳匹配过程。
1.3.3 概率方法
概率方法在[3]中被定义为 *从 GPS 传感器获得一个位置修正范围，然后用这个修正范围定义一个椭圆形或矩形置信区域 “The algorithm that requires the definition of an elliptical or rectangular confidence region around a position fix obtained from a navigation sensor”。 在[9]中开发的增强概率算法中，当车辆通过交叉口时构建椭圆形误差区域。这是一种可靠的方法，因为在每个历元构建误差区域可能会导致错误的结果，因为可能存在与车辆行驶的链接足够接近的错误检测链接。该算法还包含一些有助于改进匹配过程的标准。例如，在该算法中，考虑了低速数据的航向信息的不准确性。该算法考虑了来自 GPS 数据和底层道路网络的各种误差。
1.3.4 高级方法
这些方法包括使用更精细概念的类型，如马尔可夫模型和隐马尔可夫模型（HMM）（在[1]中使用），我们将在第2章中详细讨论。现在让我们简要讨论一些其他高级方法。由于有许多高级方法，我们将只列出一些我们认为更有趣的方法。对于感兴趣的读者，可以在[10, 11, 12, 3, 13, 14, 15]中找到更多高级方法。
一些方法结合了多种方法以获得更好的结果。例如，[16]首先使用点到曲线方法来识别正确的链接。然后，利用位置修正到链接的正交投影将给定点匹配到道路网络。这减少了所谓的横向误差，即道路宽度上的误差。同时，为了减少纵向误差，使用了扩展卡尔曼滤波器（EKF）。该滤波器的性能在很大程度上取决于道路网络中的曲线表示和空间信息。该方法存在与点到曲线方法相同的问题，即在曲线密集的城市区域。如果第一步计算的数据不正确，其他步骤也会导致不正确的结果。
为了解决城市峡谷（GPS 信号被高楼和树木阻挡的区域）的问题，[17]提出了一种解决方案，该解决方案包括将车辆的路径近似建模为直线、弧线和多项式等曲线片段。当车辆进入已知难以匹配的区域时，该方法将车辆的路径限制在已知的道路段上。基于这一约束（尽管这是一个很大的约束），只需要两个 GPS 卫星即可获得定位信息。他们的方法实现了一个与EKF集成的概率算法，以估计车辆在交叉口的位置并识别正确的匹配。需要进一步测试该算法以评估其性能和正确性。该算法在一个或多个卫星可用时失败（即应该只有两个卫星）。
为了解决上述地图匹配问题，[8]开发了一种模糊逻辑算法，该算法使用了一些新的输入：
- 车辆速度
- 道路链接之间的连接性
- 定位方案的质量
- 修正位置相对于候选链接的位置
这些输入被纳入算法中，并根据传入数据应用规则。
2 隐马尔可夫模型(HMM)地图匹配
2.1 定义
在本节中，我们将定义一些概念，因为在进一步讨论之前了解这些概念非常重要。为了定义HMM，首先需要了解什么是马尔可夫模型。因此，首先我们将定义马尔可夫模型，然后定义隐马尔可夫模型。
2.1.1 马尔可夫模型
马尔可夫模型（链）是一个数学系统。该系统有一组状态和这些状态之间的转换
*就一个状态机的概念为什么要说这么绕…
。根据某些概率从一个状态转换到另一个状态。在图2.1中，可以找到一个表示某种具有两个关键部分的系统的马尔可夫模型示例。我们可以看到，从状态 wait 到状态 CS1 的概率是 0.2，而从状态 CS1 到状态 wait 的概率是0.4。
图2.1 马尔可夫模型示例
马尔可夫模型由以下组件指定 [18]：
- $Q = q_1, q_2, . . . , q_N$：$N$ 个状态；
- $A = a_{11}, a_{12}, . . . , a_{n1}, . . . , a_{nn}$：一个转换概率矩阵 $A$，其中每个 $a_{ij}$ 表示从状态 $i$ 到状态 $j$ 的移动概率，使得 $\sum_{j=1}^n a_{ij} = 1 \space \forall{i}$。这表明矩阵的每一行都是一个概率向量，因此每一行的和必须等于1；
- $π = π_1, π_2, . . . , π_n$：状态上的初始概率分布。$π_i$ 是马尔可夫模型将从状态 $i$ 开始的概率。一些状态 $j$ 可能有 $π_j = 0$，这意味着它们不能是初始状态。此外，$\sum_{i=1}^N \pi_i = 1$。
如果一个随机过程的未来状态的条件概率分布（基于过去和现在的状态）仅取决于当前状态，而不取决于之前的事件序列，我们就可以说这个随机过程满足马尔可夫性质 [19]。这意味着未来到达任何特定状态的概率仅取决于当前状态，而不取决于导致它的状态序列。换句话说，特定状态的概率仅取决于前一个状态。更正式地，我们有马尔可夫假设
$$ \tag{2.1} \mathbb{P}(q_i = a \vert q_1 … q_{i-1}) = \mathbb{P}(q_i = a \vert q_{i-1}) $$
这意味着马尔可夫模型是无记忆的，这就是马尔可夫模型与一般随机过程的不同之处。
2.1.2 隐马尔可夫模型
当我们想要计算一系列可观察事件的概率时，我们使用马尔可夫链。当然，当我们需要研究的事件以某种方式隐藏而无法直接观察时，这并不有用。这就是隐马尔可夫模型发挥作用的地方。隐马尔可夫模型允许我们将观察到的事件和隐藏的事件都建模到我们的概率模型中。HMM 由以下组件指定 [18]：
- $Q = q_1, q_2, . . . , q_N$：$N$ 个状态；
- $A = a_{11}, a_{12}, . . . , a_{n1}, . . . , a_{nn}$：一个转换概率矩阵 $A$，其中每个 $a_{ij}$ 表示从状态 $i$ 到状态 $j$ 的移动概率，使得 $\sum_{j=1}^n a_{ij} = 1 \space \forall{i}$。这表明矩阵的每一行都是一个概率向量，因此每一行的和必须等于1；
- $O = o_1, o_2, . . . , o_T$：$T$ 个观察值，观察值均从词汇表 $V = v_1, v_2, . . . , v_V$ 中抽取；
- $B = b_i(o_t)$：观察似然值，也称为发射概率，每个值分别表示从状态 $i$ 生成观察值 $o_t$ 的概率；
- $π = π_1, π_2, . . . , π_n$：状态上的初始概率分布。$π_i$ 是马尔可夫模型将从状态 $i$ 开始的概率。一些状态 $j$ 可能有 $π_j = 0$，这意味着它们不能是初始状态。此外，$\sum_{i=1}^N \pi_i = 1$。
在马尔可夫假设（方程 2.1）之外，我们还具有输出独立性，即
$$ \tag{2.2} \mathbb{P}(o_i \vert q_1 … q_i, q_T , o_1, … , o_i, … , o_T ) = \mathbb{P}(o_i, q_i) $$
也就是说，输出观察值 $o_i$ 的概率仅取决于生成该观察值的状态 $q_i$，而不取决于任何其他状态或任何其他观察值。
为了通过一个示例说明HMM的工作原理，我们重申[18]中使用的示例。我们被要求研究一个地区的全球变暖历史，但问题是我们缺少该地区特定时期的一些必要天气数据。然而，我们可以访问一个人的日记，其中包含该人在我们缺少天气数据的时期每天吃了多少冰淇淋。我们可以使用这些观察值来估计该时期的每日温度。为了简化，我们只假设有两种类型的日子：冷（C）和热（H）。具体来说，任务（也称为 Eisner 任务）是找到隐藏的天气状态序列 $Q$，这些状态导致该人吃冰淇淋，给定观察序列 $O$，即该人在特定日期吃的冰淇淋数量。在图2.2中，你可以看到一个表示该问题的简单HMM。两个隐藏状态是HOT和COLD，观察值（在字母表 $O$ = {1, 2, 3} 上）对应于特定日期吃的冰淇淋数量。例如，在冷天吃一个冰淇淋的概率是0.5，而在热天吃三个冰淇淋的概率是0.4。
图2.2 隐马尔可夫模型示例
隐马尔可夫模型基本上由三个问题表征 [20]：
Likelihood: given an HMM $\lambda = (A, B)$ and an observation sequence $O$, determine the likelihood $P(O | \lambda)$.
似然：给定一个HMM $\lambda = (A, B)$ 和一个观察序列 $O$，确定似然 $P(O | \lambda)$。Decoding: given an observation sequence $O$ and an HMM $\lambda = (A, B)$, discover the best hidden state sequence $Q$.
解码：给定一个观察序列 $O$ 和一个HMM $\lambda = (A, B)$，发现最佳隐藏状态序列 $Q$。Learning: given an observation sequence $O$ and the set of states in the HMM, learn the HMM parameters $A$ and $B$.
学习：给定一个观察序列 $O$ 和HMM中的状态集合，学习HMM参数 $A$ 和 $B$。
2.2 Map Matching with HMM
在本节中，我们将了解如何使用隐马尔可夫模型解决地图匹配问题。我们将以 [1] 作为主要参考，因为这篇论文在实际实现中最为常用，并对解决方案提供了非常清晰和良好的解释。该论文强调在保持问题的原则性方法的同时，使算法对几何噪声和时间稀疏的位置数据都具有鲁棒性。值得一提的是，这篇论文将地图匹配问题作为批处理问题来解决，这意味着它适用于离线地图匹配。然而，作者推测，他们算法的滑动窗口版本可能适用于在线地图匹配。
在第 1 章和 1.3 节中，我们讨论了解决地图匹配问题的一些方法。我们还看到，当数据有噪声或不够准确时，每种方法都存在一些问题。这些方法共同的问题之一是缺乏对过去匹配测量的了解。HMM 地图匹配通过在匹配当前测量的过程中考虑先前匹配的测量来解决这个问题。如第1章所述，地图匹配中的关键问题是位置数据所建议的道路与路径可行性之间的权衡。简单地将每个点匹配到最近的道路可能会导致奇怪的路径和怪异的驾驶行为。这就是为什么我们引入道路网络连接性的知识，以避免出现怪异行为。HMM 提供了一种有效的解决方案，以原则性和优雅的方式整合噪声数据和路径约束。
在[1]提出的算法中，HMM 的状态是单个道路段，状态测量是嘈杂的车辆位置测量。目标是将每个位置测量与适当的道路段匹配。更正式地说，HMM 的离散状态是 $N_r$ 个道路段，$r_i, i = 1 \ldots N_r$。在表示中，不同的道路段在交叉口之间运行。对于每个位置测量（纬度和经度）$z_t$，目标是找到车辆实际所在的道路段。在图2.3中可以找到地图匹配HMM的示意图。每个垂直切片代表与位置测量 $z_t$ 对应的时间点，对于三个时间 $t = 1, 2, 3$。在 $t = 1$ 时，有三条靠近 $z_1$ 的道路（在第一列中显示为三个黑点）。从这三条道路的最近点到 $t_2$ 时靠近 $z_2$ 的两条道路，每条道路都有三条可能的路径，$t_3$ 也类似。算法的目标是通过为每个 $t$ 选择一个道路段，找到通过格子的最可能路径。现在让我们深入了解这个算法中如何测量不同的概率，以及如何根据这些测量选择最佳路径。
图2.3 用于地图匹配时的 HMM 示意图
2.2.1 发射概率
在 2.1.2 小节中，我们将发射概率定义为仅基于该测量值，测量结果来自给定状态的可能性。给定位置测量 $z_t$，每个道路段 $r_i$ 都有一个发射概率 $p(z_t|r_i)$。这是观察到如果实际在道路段 $r_i$ 上的测量 $z_t$ 的可能性。对于给定的 $z_t$ 和 $r_i$，我们将道路段上最近的点表示为 $x_{t,i}$。直觉是，离测量值更远的道路段不太可能产生该测量值。
在图 2.4 中，可以找到这种表示法的示例。有三个道路段（$r_1$，$r_2$ 和 $r_3$）和两个测量点（$z_t$ 和 $z_{t+1}$）。第一个测量点（$z_t$）有 $X_{t,1}$ 和 $X_{t,3}$ 作为候选道路段。每个匹配候选会产生通往 $x_{t+1,2}$ 的路线，$x_{t+1,2}$ 是第二个测量点（$z_{t+1}$）的匹配候选。这两条道路各有其长度，两个测量点之间的大圆路径也有长度。根据 [1] 的结果，他们得出结论，正确匹配的路线距离和大圆距离比不正确匹配的更接近。在方程 2.3 中，你可以找到计算发射概率的公式。$\sigma_z$ 是 GPS 测量的标准差，在 [1] 中估计为 $\sigma_z = 1.4826 \space median_t (\Vert z_t − x_{t,i^∗} \Vert_{great \space circle})$ 。
$$ \tag{2.3} p (z_t \vert r_i) = \frac{1}{\sqrt{2\pi} \sigma_z} e^{0.5(\frac{\Vert z_t - x_{t,i}\Vert_{great \space circle}}{\sigma_z})^2} $$
要启动算法，我们还需要知道初始状态概率 $π_i, i = 1 \ldots N_r$。在地图匹配中，这表示在驾驶开始时车辆的第一条道路相对于所有道路的概率。一些算法为 $π_i$ 分配均匀分布，但在 [1] 中，算法使用第一个测量值 $z_1$ ，即 $π_i = p(z_1 | r_i)$。
图2.4 Emission probabilities notation illustration
2.2.2 转移概率
转移概率表示车辆在 $z_t$ 和 $z_{t+1}$ 的候选道路匹配之间移动的概率。直观上，我们更倾向于驾驶距离接近测量值之间大圆距离的转移。我们知道，对于测量值 $z_t$ 和候选道路段 $r_i$，道路段上最接近测量值的坐标（经度和纬度）点是 $x_{t,i}$。对于下一个测量值 $z_{t+1}$ 和候选道路段 $r_j$，相应的点是 $x_{t+1,j}$。我们使用配置为提供尽可能短的路线距离的路线规划器来计算这两点之间的驾驶距离。这种驾驶距离被称为"路线距离"，表示为 $\Vert x_{t,i} − x_{t+1,j}\Vert_{route}$。在 [1] 中，路线距离与测量点（大圆）的比较显示，$\vert \Vert z_t − z_{t+1} \Vert_{great circle} − \Vert x_{t,i} − x_{t+1,j} \Vert_{route} \vert$ 的直方图遵循指数概率分布。作者（在进行实验后）怀疑，对于正确的匹配，这两个距离将大致相同。原因是，在一对正确匹配之间在道路上行驶的相对较短距离将与测量的GPS点之间的距离大致相同。这一结果是通过计算作者收集的一些真实数据上的这些距离获得的。指数概率分布如方程2.4所示。术语 $d_t$ 在方程 2.5 中详细说明。$\beta$ 的值在 [1] 中估计为 $\beta = \frac{1}{\ln{(2)}} \space mediant_t (\vert \Vert z_t − z_{t+1} \Vert_{great circle} − \Vert x_{t,i} − x_{t+1,j} \Vert_{route} \vert)$。
$$ \tag{2.4} p(d_t) = \frac{1}{\beta} e^{-d_t / \beta} $$
$$ \tag{2.5} d_t = \vert \Vert z_t − z_{t+1} \Vert_{great circle} − \Vert x_{t,i} − x_{t+1,j} \Vert_{route} \vert $$
2.2.3 最优路径
维特比算法 [21] 用于计算通过HMM格子的最佳路径，使用从方程 2.3 获得的发射概率和从方程 2.4 获得的转移概率。维特比算法使用动态规划来快速发现通过格子的路径，该路径最大化发射和转移概率的乘积。维特比算法的输入包括：
- 观察空间 $O = {o_1, o_2, \ldots, o_N }$
- 状态空间 $S = {s_1, s_2, \ldots, s_K}$
- 初始概率 $π_i$，其中 $i = 1, 2, \ldots, N$
- 观察序列 $Y = (y_1, y_2, \ldots, y_T )$，如果时间 $t$ 的观察是 $o_i$，则 $y_t = o_i$
- 转移概率矩阵 $A$，大小为 $K×K$，$A_{ij}$ 存储从状态 $s_i$ 转移到状态 $s_j$ 的概率
- 发射概率矩阵 $B$，大小为 $K × N$，$B_{ij}$ 存储从状态 $s_i$ 观察到 $o_j$ 的概率
算法的输出是最可能的隐藏状态序列 $X = (x_1, x_2, \ldots, x_T )$，在地图匹配中这是匹配到道路段的点。在算法 2.1 中，你可以找到 Viterbi 算法的伪代码。
function Viterbi(O, S, Π, Y, A, B)
for each state i = 1, 2, . . . , K do
T1[i, 1] ← π_i.B_{iy_1}
T2[i, 1] ← 0
end for
for each observation j = 2, 3, . . . , T do
for each state i = 1, 2, . . . , K do
T1[i, j] ← max{k}(T1[k, j − 1].Aki.Biyj)
T2[i, j] ← arg max{k}(T1[k, j − 1].Aki.Biyj)
end for
end for
zT ← arg max{k}(T1[k, T])
xT ← szT
for j = T, T − 1, . . . , 2 do
zj−1 ← T2[zj , j]
xj−1 ← szj−1
end for
return X
end function
2.3 HMM 地图匹配优化
在 2.2 节中，我们了解了如何使用HMM解决地图匹配问题。所描述的方法代表了一种原则性方法，用于平衡测量噪声和路线行为的影响。尽管如此，该算法仍可以在实践中进行改进，使其更好更快。在本节中，我们将讨论一些可以利用的方面，以改进 HMM 地图匹配算法。
2.3.1 预处理
在使用 GPS 点构建 HMM 之前，我们通过时间序列解析所有点，并移除在距离前一个包含点 $2\sigma_z$ 范围内的点。这种预处理背后的原理是，直到我们看到一个至少距离其时间前任 $2\sigma_z$ 的点，我们对明显的移动是由于实际车辆运动而非噪声的信心较低。这减少了高采样率数据的HMM步骤数量。例如，在 [1] 中，他们估计相比没有这一预处理阶段的结果，这种预处理将他们真实基准数据的处理阶段加速至 38.9%。
2.3.2 HMM 断点及解决方案
当从一个时间步到下一个时间步的所有转移概率都为零时，HMM 格子中就会发生断点。现在让我们详细说明在 HMM 地图匹配中导致断点的条件：
路线定位：在算法的纯实现中，道路网络中的每条道路都将被视为潜在的匹配候选者，并且将计算这些匹配候选者之间的完整路线。将测量值与距离测量位置太远的道路段匹配是不实际的。因此，HMM 地图匹配算法将来自距离 $z_t$ 超过一个常数米的道路段的任何测量概率设为零。这个常数应该在算法中定义。这有助于减少算法需要考虑的每个 $z_t$的候选匹配数量。这在图 2.3 中用空心圆表示，代表距离太远无法考虑的道路段。这样，数据中可能存在没有匹配候选者在定义半径内的 GPS 点，这将导致实现在HMM的特定时间步没有匹配候选者。例如，当车辆进入隧道或城市峡谷时，就会出现这种情况。
低概率路线：在连接的道路网络上，可以发现任何两个道路段之间的路线。然而，一旦路线距离($\Vert x_{t,i} − x_{t+1,j} \Vert_{route}$)变得比大圆距离($\Vert z_t − z_{t+1} \Vert_{great circle}$)大得多，对应该路线的转移概率($p(d_t)$)变得极小。当路线变得迂回和奇怪时就会发生这种情况。与其继续寻找可能不存在的奇怪道路，我们可以在 $\Vert x_{t,i} − x_{t+1,j} \Vert_{route}$ 超过 $\Vert z_t − z_{t+1} \Vert_{great circle}$ 一定常数时终止路线搜索，并分配零概率。这个常数应该在算法中定义，并取决于环境和地面真实数据。
GPS异常值：如果我们知道 GPS 数据的来源和底层道路网络，我们可以排除不尊重任何约束的 GPS 数据，并认为路线不合理，将其概率设为零。例如，如果计算的路线要求车辆在城市区域超过 180 km/h 的速度，我们可以认为这条路线不合理，并将其概率设为零。
在 HMM 的纯实现中，Viterbi 算法总能发现通过 HMM 格子的完整最优路径。然而，上述简化可能限制匹配候选者的数量，并最终导致通过 HMM 的不完整路径。这导致在 HMM 中有很长的易于匹配的位置段，以及打破 HMM 的短位置段的截取。解决这个问题的一种方法是手动删除导致断点的点。然而，这种解决方案不太实用。另一种解决方案是自动化删除打破 HMM 的点的过程。在 [1] 中，使用了以下方式来自动化这一步骤。当检测到时间步 $t$ 和时间步 $t+1$ 之间存在断点时，测量点 $z_t$ 和 $z_{t+1}$ 从模型中移除，并检查断点是否修复。如果在重新检查上述点后，时间步 $t-1$ 和 $t+2$ 的测量点导致 HMM 重新连接，则认为断点已修复。如果断点仍然存在，我们继续移除两边的点，直到断点修复或者它们持续超过定义的常数秒（在 [1] 中，这个常数是 180 秒）。如果断点超过这个阈值，我们将数据分割成单独的行程，并分别对每个行程进行地图匹配。
2.4 最新 HMM 地图匹配工具
现在我们已经了解了如何使用 HMM 进行地图匹配，是时候讨论现有的实现和工具了。有很多使用 HMM 进行地图匹配的工具和服务。在本节中，我们关注最知名的工具，并简要介绍它们。在第二部分，我们使用这些工具来评估它们并匹配一些真实数据。
2.4.1 Barefoot
Barefoot 是一个开源 Java 库，用于离线和在线地图匹配。它使用 OpenStreetMap (OSM) 作为其地图。Barefoot 由两个核心部分组成：
- 地图服务器：这是一个基于 Docker 的地图服务器，提供对 OpenStreetMap 的街道地图数据的访问。该服务器可灵活用于任何地方（如分布式云基础设施）作为地图数据服务器，或与 Barefoot 的匹配器服务器并用。
- 软件库（和匹配器服务器）：Barefoot 库可用于进行地图匹配（在线和离线）和地图上的空间数据分析。如果不想将 Barefoot 作为 Java 库使用，可以使用匹配器服务器。Barefoot 中有两种类型的独立匹配器服务器：
- 离线匹配器服务器：这是用于离线地图匹配的独立服务器。服务器接收包含 GPS 坐标和时间的 JSON 对象数组，在匹配点后，发送包含匹配点的响应。响应可以是 GeoJSON格式或 SlimJSON 格式。此外，还可能有一个调试格式，输出有用信息，如测量时间戳和 WKT 格式的路线几何形状。
- 在线跟踪器服务器：这是用于在线地图匹配的独立服务器。服务器定期接收位置更新，并将其与底层道路网络匹配。服务器立即匹配每个位置，并实时维护对象在地图上的移动轨迹。
2.4.2 GraphHopper
GraphHopper 是一个快速且内存高效的路由引擎，也支持 HMM 地图匹配。它用 Java 编写，并在 Apache License 2.0下许可。它可以作为 Java 库或独立的网络服务器使用。这个路由引擎可以计算两点或多点之间路线的距离、时间、转弯指示和许多道路属性。它还支持地图匹配（或贴合道路）、等时线计算（计算并可视化特定交通模式的可达区域）、移动导航等。像 Barefoot 一样，GraphHopper 也使用 OpenStreetMap 作为默认的道路网络表示。可以使用其他地图，但在这种情况下需要自定义导入程序。与 Barefoot 不同，GraphHopper 不使用任何地图服务器来存储道路数据。它直接与OpenStreetMap 数据文件（osm.pbf）一起工作，不需要任何类型的数据库或 Docker 容器作为其地图组件。
2.4.3 Valhalla
Valhalla 是一个开源路由引擎，附带用于 OpenStreetMap 数据的库。Valhalla 还包括工具，如时间+距离矩阵计算、等时线、高程采样、地图匹配和路线优化。它用 C++ 编写，并具有 HTTP 服务器-客户端实现。该工具被分成较小的 API，设计用于执行特定任务，如地图匹配、路由图、瓦片生成、路由算法等。每个 API 可以通过发送 HTTP 请求来使用端点。在 Valhalla 中，地图表示为图形。图形瓦片可以下载，供客户端路由应用程序使用，或由不想经历数据创建痛苦的托管服务使用。结构化图层次结构（如高速公路、动脉、本地、过境）以及快捷边将确保高性能。还有一个在线演示服务器，可用于测试该工具。这不需要任何安装。
2.4.4 FMM
Fmm（Fast Map Matching）是一个用 C++ 和 Python 编写的开源地图匹配框架。它考虑最大化性能、可扩展性和功能。像其他工具一样，FMM 使用 OpenStreetMap 作为其地图。同样可以使用 ESRI shapefile 作为地图。该工具以 XML 格式接受配置，以逗号分隔的 CSV 格式接受 GPS 数据，其中每行存储一个轨迹，几何形状采用 WKT 线串格式。
第二部分 地图匹配工具的评估、观察和基准测试
3 工具测试和基准
在第2章结束时，我们列出了一些使用 HMM 解决地图匹配问题的现有工具。在本章中，我们将讨论如何测试这些工具，以及它们在不同阶段（如道路网络构建和地图匹配过程）的执行时间表现。我们还将讨论用于测试这些工具的数据。
参考文献
[1] Paul Newson and John Krumm. Hidden markov map matching through noise and sparseness. In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, November 4-6, Seattle, WA, pages 336–343, November 2009.
[2] Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-matching for low-sampling-rate gps trajectories. pages 352–361, 01 2009.
[3] Mohammed A. Quddus, Washington Y. Ochieng, and Robert B. Noland. Current mapmatching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C: Emerging Technologies, 15(5):312–328, 2007.
[4] Christian S. Jensen and Nerius Tradišauskas. Map matching. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, pages 1692–1696, Boston, MA, 2009. Springer US.
[5] Dave Bernstein and Alain L. Kornhauser. An introduction to map matching for personal navigation assistants. 1998.
[6] Josh Greenfeld. Matching gps observations to locations on a digital map. Transportation Research Board 81st Annual Meeting, 01 2002.
[7] Meng Yu. Improved positioning of land vehicle in its using digital map and other accessory information. Hong Kong Polytechnic University – Dissertations, 2006.
[8] Mohammed Quddus, Washington Ochieng, Lin Zhao, and Robert Noland. A general map matching algorithm for transport telematics applications. GPS Solutions, 73, 12 2003.
[9] Mohammed A. Quddus, Robert B. Noland, and Washington Y. Ochieng. Validation of map matching algorithms using high precision positioning with gps. Journal of Navigation, 58(2):257–271, 2005.
[10] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. volume 2, pages 853–864, 01 2005.
[11] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases, VLDB ’05, page 853–864. VLDB Endowment, 2005.
[12] Chalermchon Satirapod, Chris Rizos, and Jinling Wang. Gps single point positioning with sa off: How accurate can we get? Survey Review, 36:255–262, 10 2001.
[13] Lianxia Xi, Quan Liu, Minghua Li, and Zhong Liu. Map matching algorithm and its application. International Journal of Computational Intelligence Systems, 10 2007.
[14] Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. Matching planar maps. Journal of Algorithms, 49(2):262–283, 2003.
[15] D. Yang, B. Cai, and Y. Yuan. An improved map-matching algorithm used in vehicle navigation system. IEEE Proceedings on Intelligent Transportation Systems, 2:1246–1250, 01 2003.
[16] Wuk Kim, Gyu-In Jee, and JangGyu Lee. Efficient use of digital road map in various positioning for its. In IEEE 2000. Position Location and Navigation Symposium, pages 170–176, 2000.
[17] Youjing Cui and Shuzhi Sam Ge. Autonomous vehicle positioning with gps in urban canyon environments. IEEE Transactions on Robotics and Automation, 19(1):15–25, 2003.
[18] Daniel Jurafsky and James H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall PTR, USA, 1st edition, 2000.
[19] Christoph Haase and Stefan Kiefer. The odds of staying on budget. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming, pages 234–246, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[20] L.R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286, Feb 1989.
[21] A.J. Viterbi. A personal history of the viterbi algorithm. IEEE Signal Processing Magazine, 23(4):120–142, 2006.