地图匹配算法综述

地图匹配算法综述1地图匹配算法综述一、地图匹配：现有算法车辆导航系统实时接收GPS位置速度信息，以交通地图为背景显示车辆行驶轨迹。保证所显示的轨迹反映车辆的实际行驶过程，包括行驶路段，转弯过程及当前位置，就是地图匹配问题所要解决的目标。本节首先对地图匹配问题涉及到的基础概念、误差模型给出简要说明，同时介绍当前流行的一些地图匹配算法的思路与特点。1.1地图匹配问题介绍利用车载GPS接收机实时获得车辆轨迹，进而确定其在交通矢量地图道路上的位置，是当前车载导航系统的基础。独立GPS车载导航系统中克服GPS误差以及地图误差显示车辆在道路网上的位置主要是通过地图匹配算法，也就是根据GPS信号中的数据和地图道路网信息，利用几何方法、概率统计方法、模式识别或者人工神经网路等技术将车辆位置匹配到地图道路上的相应位置[8-12]。由于行驶中的车辆绝大部分都是在道路上的，所以通常的地图算法都有一个车辆在道路上的默认前提。地图匹配的准确性决定了GPS车辆导航系统的准确性、实时性与可靠性。具体来说取决于两方面：确定当前车辆正在行驶的路段的准确性与确定车辆在行驶路段上的位置的准确性。前者是现有算法的研究重点，而后者涉及到沿道路方向的误差校正，在现有算法中还没有得以有效解决。地图匹配的目标是将轨迹匹配到道路上，当道路是准确的时，也就成了确定GPS的准确位置，然后利用垂直映射方法完成匹配。要实时获得车辆所在的道路及位置通过地图匹配来实现是一种比较普遍而且成本较低的方法。车辆导航与定位系统中的地图匹配问题概括来讲就是将车载GPS接收机获得的带有误差的GPS轨迹位置匹配到带有误差的交通矢量地图道路上的相应位置。下面我们通过具体的数学模型地图匹配算法综述2来给地图匹配问题以详细的数学描述。地图匹配的基本过程如图4.1所示。符号定义及其物理意义说明如下：图4.1地图匹配模型1)g(k)是车辆GPS轨迹点，内容为k时刻车辆上的GPS定位数据（经纬度），对应于矢量地图上相应的经纬度位置点。由于GPS误差和矢量地图误差的存在，当车辆在道路弧段Si上行驶时，g(k)通常并不位于弧段Si上。2)p(k)为g(k)的地图道路匹配点，表示地图匹配算法对g(k)进行偏差修正获得的车辆k时刻在矢量地图道路上的对应点，简称g(k)的匹配点。匹配点所在矢量地图弧段Si上的位置，应该尽可能反映出实际车辆在该段道路上的相应位置。3)e(k)为g(k)的地图匹配修正量，表示g(k)与其匹配点p(k)间的误差修正。需要指明匹配点所在的弧段p(k)Si时，使用符号e(k)[Si]表示g(k)对于弧段Si上的匹配点所使用的匹配修正量。上述3个基本量之间的关系如图画所示，即p(k)=g(k)+e(k)(4)地图匹配修正量e(k)源自于GPS定位误差和交通矢量地图精度误差的综合误差效应。4)e(k)的正交分解将e(k)正交分解为弧段横向修正量ev(k).R与弧段纵向修正量eh(k).R，有(5)式中e(k)[Si]的纵向单位矢径的正向与车辆在弧段Si上的前进方向一致，横向单位矢径与垂直，构成右旋直交坐标如图4.1所示。需要注意的是,ev(k)与eh(k)均为标量，它们的大小与符号说明如下。5)弧段横向修正量ev(k)表示g(k)的道路弧段横向偏差，ev(k)的幅值|ev(k)|大小表示g(k)到达弧段的最短距离，即地图匹配算法综述3(6)式中q(k)=q(gk,Si)称为g(k)的弧段Si最近点，也就是g(k)对弧Si作垂线与弧段Si的交点。ev(k)[Si]的符号正负取决于是否与横向单位矢径的方向一致。正值表示g(k)偏差在按前进方向测算的道路弧段Si的右侧，反之，当车辆g(k)位于道路弧段的左侧，ev(k)为负值。q(k)由g(k)与相应弧段Si唯一确定，所以ev(k)[Si]是一个已知标量。6)弧段纵向修正量eh(k)表示g(k)的道路弧段纵向偏差，反映g(k)的地图道路匹配点p(k)沿道路弧段方向上的预测偏差，即(7)eh(k)的取正值表示匹配点p(k)位于g(k)的前方，反之，当车辆g(k)必须向后退方向匹配时eh(k)为负值。弧段纵向修正量eh(k)[Si]与匹配点p(k)直接相关，是地图道路匹配算法最重要又最难精确求解的预测变量。如何克服这一误差分量的影响是论文研究的一个重点。地图匹配过程实际上就是利用车辆行驶的GPS轨迹g(k)，基于矢量地图的拓扑结构，以及其它可获得的车辆运动信息来确定车辆正在运行的道路弧段Si，以及在上面的准确对应方位p(k)。1.2常见地图匹配算法正如本章开始的时候介绍，地图匹配算法经常被用来在车辆导航系统中确定车辆在道路上的位置。大部分地图算法都假设车辆行驶过程中是在有限的道路网上进行的，在绝大部分情况下车辆都是满足这种情况的。当然，当车辆实际上不在已知道路上行驶时，地图匹配可能增加GPS定位误差。还有一个假设是大部分现有算法的前提，就是矢量地图的高精确度。但是在实际应用中，用户并不能得到所有需要区域的高精确地图[1]。文献[1]对于现有地图匹配算法作了很好的总结，并且在文献中介绍了四种地图匹配算法类型：1）半确定性算法；2）概率统计算法；3）基于模糊逻辑的算法；4）模式识别算法。半确定算法需要的一个基本前提是需要知道车辆的初始位置和车辆运行方地图匹配算法综述4向，然后多种条件判断会用来判定车辆是否在已知道路网上。这种地图匹配算法一般用于带有航位推测定位系统的车辆导航系统。概率统计算法是在从车辆导航系统获得的轨迹位置周围建立矩形或者长方形的置信区域。模糊逻辑的算法是基于一系列的规则及其权重的设计来实现的。是一种基于已有知识的规则系统。由于地图匹配算法本质上是模式识别的过程，所以模式识别领域中的多种算法都可以应用于地图匹配问题的解决，比较典型的是人工神经网络。地图匹配过程可以用多种算法实现，从简单的搜索技术[13]，到复杂的数学工具[14]，如卡尔曼滤波。在后面地图匹配算法的详细回顾中，我们主要将其分为三类：几何方法，概率统计算法和其他高级算法。1.2.1几何匹配算法几何匹配算法利用地图道路网的几何信息进行匹配，它只考虑路段的形状距离等，而不考虑道路的连接关系。最常见的几何地图匹配算法，是一种简单的搜索过程。每一个车辆GPS轨迹点被匹配到最近的地图道路网节点处或最近路段上的最近点。这种算法在车辆导航系统中的实现非常简单，但是直接用其匹配原始车辆轨迹经常会出现误识别，尤其是在道路密集的城市地区和交叉路口处。所以这种算法在实际车辆导航系统中直接使用的很少。一些高级匹配算法在对车辆轨迹进行处理后，用这种方法完成最后的步骤，将经过处理或者识别的匹配点映射到对应道路上进行显示。文献[8]对这种最简单的匹配算法进行一下改进，利用GPS信息中的速度方向信息或者车辆运行连续性参考前面时刻轨迹点匹配的道路辅助选择当前轨迹匹配的道路，选择好匹配的道路后将轨迹点投影到该道路曲线上完成匹配。当车行驶在道路上时，存在三个状态信息，速度、方向和当前所在街道。不难理解三个事实：当车辆远离交叉路口时，它不可能从一条街“跳”到另一条街；连续两次从GPS信号得到的方向绝对差总小于某个小量，除非它在交叉路口转向；当车辆行驶在道路上时，偶尔较大偏离道路的信号应该忽略。概括来说，就是利用车辆轨迹的连续性和矢量电子地图的拓扑结构，将车辆轨迹和道路网格进行匹配，从而过滤GPS信号的定位误差，更形象一些，可以说是根据GPS信号将车辆“拉”到道路上来。因此，修正算法应该涉及车辆当前和以前的方向及街道的拓扑索引。这种改进后的匹配地图匹配算法综述5算法能够有效减少匹配的误识别率。文献[15]中的方法考虑多个轨迹点的地图匹配算法是根据一段时间内，连续多个轨迹点拟和为曲线与道路曲线进行比较匹配，确定车辆运行道路以及车辆在道路上的位置。文献[16]中，White对几种几何地图匹配算法进行了详细的介绍和比较，包括点到点匹配、点到弧匹配、弧到弧匹配以及利用地图拓扑结构的地图匹配。通过对各种算法的匹配效果进行比较，说明了利用更多点的信息可以提高识别的准确率，而且匹配过程中利用地图拓扑结构可以有效提高地图匹配算法效果。文献[17]提出了基于权重的几何地图匹配算法，首先比较车辆方向(从GPS接收机获得)与周围道路方向的偏差，比较当前轨迹点与周围道路弧的距离偏差，然后对两个偏差设定不同的权重，获得针对不同道路的权重和，最后比较这些权重和，最小的就是匹配可能性最大的。这种算法利用了车辆的方向信息来辅助地图匹配。这些改进后的几何地图匹配算法在确定了轨迹匹配后的道路后，用最短距离匹配方式，将车辆轨迹映射到该道路上距离轨迹最近的点上。1.2.2概率统计算法概率统计算法是在从车辆导航系统获得的轨迹位置周围建立矩形或者长方形的置信区域。这种算法最早是1989年由Honeyetal设计的[18]。文献[1]中介绍了其在GPS车辆导航系统中的应用，置信区域的大小可以由GPS位置的各种误差大小来确定。之后，置信区域被重叠到交通矢量地图上，来确定匹配道路。当置信区域中包含多条路段时，利用车辆的速度方向信息、与前面匹配道路的关联信息以及最近距离原则来确定唯一的匹配路段。当在一定可信度区域内没有道路时，视车辆不在道路上。文献[1]中没有介绍对这种算法的具体实现，在具体设计时，车辆的速度信息和距离下一个交叉路口的距离信息都可以被应用到概率统计算法中。算法的主要目标也是如何正确识别当前车辆运行所在的道路。确定匹配道路后，用最短距离匹配方式将车辆轨迹映射到该道路上距离轨迹最近的点上。1.2.3其他高级算法除了上面两种常用的地图匹配处理思路以外，卡尔曼滤波、模糊理论和人工地图匹配算法综述6神经网络等理论也被应用于车辆导航系统的地图匹配问题的解决中。卡尔曼滤波器是一种高效率的递归滤波器（自回归滤波器）[19]，用于估计离散时间过程的状态变量。卡尔曼滤波器最初就是用来设计空间导航系统的[1]，当前被广泛应用于各种系统。在车辆导航系统中，也是目前使用的重要信号滤波手段和多传感器融合方法。在独立GPS车载导航系统的地图匹配算法中，融合交通矢量地图上的道路网信息，是这类算法与单纯的GPS接收器信号处理最大不同之处。例如论文[20]中，将地图上路段的几何数学表达式作为卡尔曼滤波的一个约束条件该地图匹配算法能够部分校正沿道路方向的误差。论文[21]中介绍的算法虽然在状态空间中包含了互相垂直的两个方向上的状态进行车辆位置预测估计。另外的地图匹配算法运用模糊理论[9]，人工神经网络等领域的知识实现匹配过程[22]。这些算法在固定场合下有很高的匹配准确率，但是需要大量的数据进行算法参数的前期学习和总结。1.3对现有算法分析以上介绍的这些算法研究重点都在如何确定匹配道路上，而并没有设计有效的方法在匹配道路上寻找匹配点，都是简单的采用垂直映射的方法，用轨迹点到匹配道路的垂足作为匹配点。这样的处理方法对于弧段纵向偏差无能为力。同时也没有明确的对地图误差给地图匹配带来的问题进行解决。而这些误差关系到定位与导航准确性的重要因素，尤其是交叉点附近。对于导航过程中获得的各种信息利用的越充分越能提高地图匹配的准确性。这些方法中考虑的车辆方向、速度、位置、历史轨迹和地图的拓扑结构信息，是新算法中需要借鉴利用的。现有地图匹配算法的另外一个问题是对地图道路网误差的忽视。虽然当前的交通矢量地图的准确性有了很大提高，但是某些区域的地图的位置准确性不是很高，而且在相对准确的交通地图中的某些局部可能有较大误差，这些都会对地图匹配算法的准确性产生影响。实际上地图匹配算法的概念就是将车辆轨迹匹配到地图道路上，而不是简单的车辆轨迹误差校正。这就意味着地图匹配算法本身就应该包含匹配过程中对地图误差的克服与处理。卡尔曼滤波器由于其对于包含随机噪声的信号有很好的滤波性能，所以是处理车辆轨迹误差的一个很好工具，但是其模型对噪声的概率分布有比较高的要地图匹配算法综述7求，要求其为0均值的白噪声。而根据论文第二章中的GPS误差的均值曲线和自相关函数曲线可以看出其并不符合卡尔曼滤波器的模型要求。当前大部分应用于独立G