英语原文共 6 页

2013 届国际联网车辆与博览会会议 (ICCVE)

一种基于HMM的累积邻近权重映射匹配方法

阿里奥兰

未来城市流动 IRG

新加坡-麻省理工学院研究与技术联盟 (SMART)

新加坡，138602

电子邮件: aoran@smart.mit.edu

帕特里克监狱

电气工程与公司部科学(EECS)麻省理工学院

剑桥，美国02139

电子邮件: jaillet@mit.edu

摘要

在本研究中，我们引入了一种基于累积邻近权重公式的隐马尔可夫模型映射匹配方法。这个新公式是基于点分段权的线积分，而不是基于最短距离的标准权。利用西雅图地区的车辆和地图数据对该方法进行了测试。为了将新的权重与传统的权重进行清晰的比较，进行了多个仿真，重点对长采样周期、高噪声的GPS数据进行了匹配。总的来说，通过新的重量可以提高地图匹配(MM)的精确度。可以看出，在存在低频采样和/或噪声GPS数据的情况下，新的权重可能比基于最短距离的权重更好。

I .简介

自2000年代初以来，基于卫星的导航设备的使用一直在稳步增长，因此，利用底层道路网络对这些设备采集的车辆位置测量数据进行分析，以确定车辆的真实位置，已成为地图匹配(MM)通用名称下的一个主要研究问题。在过去的二十年中，关于这个问题提出了许多种不同方法。早期的地图匹配(MM)方法是以经常采样的GPS点1(例如，以1秒的间隔采样)为前提开发的。有了这些数据，过去十年来的大多数方法都能够获得几乎完美的匹配结果。然而，当数据点之间的采样周期较长时，尤其是当采样周期超过30秒时，这些方法的效果并不理想。因此，在过去的几年里，人们对解决低频GPS数据的非传统地图匹配(MM)问题的方法越来越感兴趣。精度下降的主要原因是测量频率较低时，车辆从一个点到下一个点的行程不确定性越来越大[1]。为了减少不确定性增加的影响，提出了各种启发式方法。虽然这些启发式方法在一定程度上提高了地图匹配(MM)精度，但是仍然需要更多的研究来获得低采样GPS数据的高精度方法。第二件事要注意的是，地图匹配(MM)方法的精度也会随着所选网络的道路稀疏度和GPS设备的测量质量而变化。虽然使用非常精确的GPS接收器可以获得几乎100%的精度，但在没有城市峡谷的稀疏网络上行驶时，不可能在每种情况中都获得如此高的精度。出于这个原因，最近人们有更多的兴趣开发大噪声情况下的GPS测量方法。任何能够解决这两个问题的建议，虽然不特别依赖于特定的底层地图匹配(MM)算法，也不依赖于额外的数据(仅使用定位数据)，但总体上都有益于使用地图匹配(MM)方法。

注：

这项研究得到了新加坡国家研究基金会通过新加坡麻省理工学院研究与技术联盟的FM IRG研究项目的支持。

作者要感谢微软研究院的Paul Newson和John Krumm为其他研究人员提供了他们的车辆和地图数据。

作者要感谢Smart的Kakali Basak、Liang Yu和Joseph K.Lee对QGIS软件的有益讨论。

在本文中，我们使用通用术语“GPS点”，用于从卫星导航设备收集的每次有时间戳的车辆位置数据。

对于地图匹配(MM)方法，一些概念始终是必要的；通过改进与之相关的措施，可以实现上述目标。观测到的GPS点与网络中的路段之间的空间接近性概念就是其中之一。在确定性方法中，它被量化为近似权重，例如[2]、[3]，在概率方法中，它被量化为观测(发射)概率，例如[4]、[5]。虽然分段接近的构思在每种方法中都是唯一的，但所有的构思仍然遵循一个事实，对于给定的GPS点，更接近这一点的片段更可能是真正的片段，而不是更远的片段[6]。因此，在确定性方法中，距离的单调递减函数和概率方法中，通过高斯分布定义的距离的似然函数最为常见。同时，有趣的是要注意，在所有的这些功能中，量化一个路段相对于给定的GPS点的接近程度，从该点到路段的最短距离被用作唯一的参数[2]、[3]、[4]、[5]、[7]、[8]、[9]、[10]。虽然这是一个来量化段和点的接近程度的有效方法，但请注意，它只依赖于道路段最近点的接近程度。最近在[12]中详细讨论了这种方法的缺点，作者已经证明，这种方法可能产生可疑的权重(概率)，例如，几何结构和方向非常不同的路段，只有在距GPS点的最短距离相同的情况下才能获得相同的权重。另一种方法是，为段上的点定义点向邻近权重，通过线积分定义的这些权重的累积值产生该段的邻近权重。在假定路段为直线、GPS噪声为高斯的前提下，提出了一种概率方法的权重封闭形式。在最近的一些研究中，也提出了避免基于最短距离的近似权重的类似公式，例如[13]，但没有紧凑的公式因此，建议的累积邻近权重[12]可以很容易地实现，但对概率方法的总体改进是有效的。

然而，[12]并没有将所建议的权重作为实际地图匹配(MM)算法的一部分，因此，此时仍需进行完整的地图匹配(MM)分析，以确定所建议的权重是否能提高概率方法的总体精度。如果是这样，我们还需要确定在什么情况下可能是这种情况。在本研究中，我们试图通过开发一种基于隐马尔可夫模型(HMM)的地图匹配(MM)算法来回答这些问题，该算法具有建议的累积邻近权。为了将地图匹配(MM)结果和建议的权重和传统的基于最短距离的权重进行比较，还开发了一种使用后一个权重的并行算法。选择HMM作为基础方法是因为它在公式化地图匹配(MM)问题时很简单，并且通过Viterbi算法找到最可能的路段序列，可靠地估计出它产生的结果。首先由Hummel[14]使用，后来由Newson和Krumm[4]使用，HMM最近已成为概率地图匹配(MM)研究中一种被证实的方法。

由于接近权重仅通过位置数据来定义，为了对这两种方法进行清晰的比较，在本研究中，我们假设只有这种数据的可用性。仅使用车辆的位置数据来确定车辆的真实位置的问题，基本的道路网被认为是最基本的地图匹配(MM)问题。在这个问题上，其他地图匹配(MM)变量可以通过额外数据的可用性来定义，例如速度或航向数据；毫无疑问，它们的可用性可以提高匹配结果。因此，我们的模拟中反映的改进也可以通过额外数据的可用性来看到。

在我们的模拟中，我们使用了Newson和Krumm在[4]中最初使用的相同GPS和道路网络数据集。使用该数据集的主要原因是地面真实数据的可用性，这有助于我们正确识别算法下不匹配的段数。此外，该数据集的使用也为我们提供了一个安全检查基于最短距离的算法的机会，通过将我们的结果与他们的结果进行比较。虽然我们将从比较标准地图匹配(MM)问题(每秒采样的GPS数据)两种算法的性能开始模拟，但我们主要关注的是它们在低采样和噪声数据下的性能。

论文的其余部分按如下方式组织：第一，在II中，我们将从最短距离和累积权重的角度简要地重新引入邻近权重。稍后在III中，我们将详细介绍用于解决地图匹配问题的基于HMM的方法。最后，在IV中，我们将描述我们的模拟，并展示我们的结果。随后将对结果进行比较并进行讨论，以评估新的近似权重。

II. 定义接近权重(概率)

A. 基于最短距离的路段接近权与基于线积分的路段接近权

设d(p，s)定义两点p和s之间的距离；dm(p，s)定义点p和路段sisin;S之间的最短距离。同时，设f:r →r ，为定义地图匹配(MM)方法中路段的接近权重的一般权重函数，Wm(p，s)通过最短距离测量确定的d定义的路段s相对于p的接近权重。然后，在其一般形式下，基于最短距离的近似权重可表示为：

(1)

为了定义更精确的s接近权，可以定义s上每个点的接近权，并沿s求和。设f(d(p，s))为S点相对于P的近似权重，则S路段相对于P的累积近似权重可用沿S的线积分表示：

(2)

一旦计算出所有段的权重，就可以进行标准化以获得相对权重：

(3)

B. 概率地图匹配(MM)方法的近似权重：

在[12]中，(2)是在概率方法下进行的，其中距离的似然函数用作权重函数，f.让Pr(p |d(p，s))表示车辆实际位置距离点p距离d(p，s)的可能性。然后，根据(2)，当在P，P r(P|s)处观测时，车辆在S段上行驶的总可能性可以用S上的积分来定义，该积分也产生概率方法的累积接近权重：

(4)

Pr(pd(p，s))选择了以GPS点为中心的高斯分布，其平均值为零，类似于[4]、[5]、[7]、[15]、[16]、[10]、[11]。

(5)

式中，sigma;是GPS测量的假定标准偏差。通过将(5)替换为(4)，并将路段s参数化，得到一个闭合形式，如下所示：

(6)

式中，Phi;是高斯分布的标准累积分布函数，常数为：

(7)

其中(xA，yA)和(xB，yB)是节点nA和nB的笛卡尔坐标，用于定义路段s。另一方面，如果使用基于最短距离的近似权重函数(1)和相同的高斯似然函数(5)，则可获得以下权重：

(8)

如前所述，在概率地图匹配(MM)文献中，这些近似权重通常被称为观测概率，我们将交替使用这两个术语。

III. 基于HMM的地图匹配(MM)算法

地图匹配(MM)问题可以看作是一个离散时间状态估计问题，其中系统在某一时刻的状态k，Xk是车辆在k处通过的路段，在k，Yk处的测量值是车辆的位置。当车辆的动力学(速度、加速度、航向等)未知时，从概率的角度来接近这个估计问题是合理的。考虑到这些状态是不可观测的，而且GPS测量是独立的，这个问题可以在HMM框架下解决。HMM双变量离散时间过程{Xk，Yk} kge;0，其中Xk是一个马尔可夫链，条件是{Xk}，{Yk}是一个独立随机变量序列，因此Yk的条件分布仅取决于Xk[17]。它的特点是五元组、状态空间、观测空间、状态转移概率、观测概率和初始概率。

对于地图匹配(MM)问题，HMM状态空间将由道路网络的路段组成，观测空间将是由全球经纬度坐标定义的连续空间。由于我们最初没有关于系统状态的任何附加信息，初始概率可以被认为是均匀分布的。以P r(Xk|Yk)状态为条件的观测概率取决于几个因素，如路段的经纬度/海拔、卫星健康等。与其他概率地图匹配(MM)方法一样，在该方法中，我们也考虑了一个简化模型，其中观测概率仅由GPS点与该段的接近程度来定义。事实上，根据这一简化假设，在观测概率这一术语下，(6)和(8)的概率邻近权重已经变得已知。马尔可夫转移概率的公式在III-B中进行了讨论。

A. 候选段/链接

我们通过识别给定GPS点的候选路段开始分析，即识别可能是车辆行驶的原始路段的路段。在实际应用中，我们使用的是圆形误差区而不是椭圆误差区，在确定误差区大小时，地图匹配(MM)方法之间还没有达成共识。大多数方法都使用足够大的圆半径，例如100 m[10]和200 m[4]，以确保没有遗漏任何真实的段。然而，这种方法在计算上可能不可行。因为本区域以外的路段被排除为不太可能的路段，从概率的角度来看，人们只需确保被排除路段成为真正路段的概率几乎等于零。因此，在我们的方法中，我们将误差区域的大小作为GPS测量噪声标准差sigma;o的函数，而不是预设值。当GPS噪声假设为双变量、不相关高斯分布时，通过半径为R0=5sigma;o的圆误差区域，我们预计100000个GPS测量中只有1个在该区域之外。因为这个数字只是期望值，所以我们将这个系数加倍，并在我们的算法中将误差圆的半径固定为，R0=10sigma;0。总的来说，对于所有的模拟，包括那些添加了噪声的GPS数据，它足以捕捉所有真正的候选片段。

确定一组给定GPS点的候选路段是一个范围查询问题，本研究采用单元数据结构来解决这一问题。在识别候选段时，仅通过识别错误区域内的节点来识别候选段的通用方法是不够的。这种方法会错过一个候选段，该候选段的节点保持在错误区域之外，但仍然通过该区域。为了不错过这些，我们需要将单元大小增加到一个更大的值，与段长度相关。同时，给定一个GPS点，我们在找到候选段之前无法知道其长度；但是要完全检测这些段，我们需要知道它们的长度。网络上最长的段的长度可以作为单元大小，但这将导致大量的候选，其中大多数可能永远不会通过错误圈。因此，除了由最长段长度定义的较大单元外，还使用了尺寸为100米的次要、较细的单元结构。范围查询作为这两个单元结构的组合来实现，并考虑网络中分段的长度。

在[12]中，(6)是在假定路段为直线的前提下开发的。在空间矢量图中，这种假设可能不成立。然而，在这些地图中，路段用多段线表示，多段线是由其形状点定义的直线连接的联合，例如，图1中的S4段是L4,1和L4,2的联合。因此，在处理任何矢量图时，(6)对于这些直线链接仍然有效，并可用于查找组成一段的链接的权重。由于这些链接是不相交的(交叉点除外)，因此可以通过这些链接的权重之和找到段的接近权重。作为替代方案，可以单独分析每个链接，整个地图匹配(MM)分析可以基于链接而不是段。

图1. 围绕GPS点p1定义的圆形误差区域，用于识别其候选路段S1、S2、S3和S4。S4是一条多段线道路，由两条直线连接线L4,1和L4,2组成。黑点{ni}表示网络的节点/形状点，红点{mi}表示候选段与错误区域的交点。

注意，为了找到从一个段到一个点的最短距离，也需要找到

资料编号：[4885]