改进地图匹配技术在车载导航的应用

　　随着城市化的进展和汽车的普及，交通拥挤加剧，交通事故频发，交通环境恶化，这成为长期以来困扰发展中国家和发达国家的严重问题。解决此问题的直接方法是提高路网的通行能力。可修建公路的空间有限，而且建设资金筹措困难。交通系统是复杂的大系统，我们应从系统论的观点出发，把车辆和道路综合起来考虑，运用各种高新技术系统解决交通问题，智能交通系统（intelligent transport system）应运而生。

　　整个智能交通系统都以车辆的定位导航为核心，车辆导航系统是智能交通系统的中心部件，是其他各种功能应用的基础。GPS或者GPS／INS或者GPS／DR方案以其结构简单、成本低廉、中高精度和良好的动态性能等优点，被广泛的应用于车辆导航系统。本文就是实现组合定位，在应用地图匹配（map matching，MM）定位技术进行车辆定位，以便在行驶过程中为用户提供准确可靠的实时定位信息，为智能交通管理系统的实现提供技术上的保障。

　　1 地图匹配的原理

　　地图匹配是一种基于软件技术的定位修正方法，其基本思想是将车辆定位轨迹与数字地图中的道路网信息联系起来，并由此相对于地图确定车辆的位置。

　　地图匹配应用是基于以下2个假设条件：

　　（1）车辆总是行驶在道路上；

　　（2）采用的道路数据精度要高于车载定位导航系统的定位精度。 当上述条件满足时，就可以把定位数据和车辆运行轨迹同数字化地图所提供的道路位置信息相比较，通过适当的匹配过程确定出车辆最可能的行驶路段以及车辆在该路段中的最大可能位置。如果上述假设不成立，则地图匹配将产生错误的位置输出，并可能导致系统性能的严重下降。一般认为用于匹配的数字地图误差不应超过巧米（真实地面距离）。由于陆地车辆在除进入停车场等之外的绝大多数时间内都位于公路网络中，因此使用地图匹配技术的条件是满足的。

　　2 地图匹配算法

　　地图匹配的算法是曲线匹配原理和地理空间接近性分析方法的融合。曲线匹配算法的基本思想是：如果对一条曲线做任意数量、任意比例的分割，分割点都落在另一条曲线上，则两条曲线严格匹配。实际应用中，就是计算一条曲线上相对均匀的某一数量分割点到参考曲线的距离的平均值，将其作为到参考曲线的平均距离，并将此平均距离的倒数作为匹配优劣的度量。空间接近性分析方法就是在已知的可能正确的地理数据集中，按照空间最接近的方法匹配当前定位数据。

　　地图匹配算法可分为2个相对独立的过程：一是寻找车辆当前行驶的道路；二是将当前定位点投影到车辆行驶的道路上。其基本办法是按照曲线匹配的思想在车辆航迹的邻近区内搜索所有道路路段及其组合，把这些组合路线分别与车辆航迹求取匹配度量值，将取得最佳匹配度量值的组合路线作为车辆当前行驶路线。地图匹配的常用算法有以下几种：直接投影算法；相关性算法；半确定性算法；概率统计算法；模糊逻辑算法；基于计算几何（非数值计算）知识（并暂时不考虑测量误差）算法。

　　由于计算几何知识算法不需要数据融合，极少需要考虑行车方向，非常直观，并且减少了许多数值计算，具有极高的正确匹配率，能够满足快速、准确、实时地定位车辆位置的要求。因此，本系统选用基于计算几何知识的地图匹配算法。

　　基于计算几何（非数值计算）知识（并暂不考虑测量误差），根据测量点位坐标有2种思路：

　　（1）不断判断刚测得的点位于道路的哪一侧，如果刚测得的点与前期测得的某个点位于道路1的两侧，则车辆在道路1上行驶。如果道路1是一条弯曲的路径，那么经多次测量，并应用该方法也可以判断车辆所处的道路。

　　（2）逐段计算测量点集的凸壳，依据道路与凸壳的交判断车辆在哪条道路上行驶。

　　但当测量点全部位于1的同一侧时，算法失败。另该算法没有考虑测量误差，由此对GPS测量误差的抗噪性差很有可能使算法失败。

　　3 改进的地图匹配方法

　　在算法设计时基于以下4个方面的考虑：一是效率，地图匹配算法必须能够满足车辆导航实时、快速的要求；二是精度，地图匹配的目的就是有效地提高车辆定位目标的精度，并保持定位结果的稳定性；三是不同交通状况分别给出策略处理以提高道路选取得正确率和缩短匹配时间；四是程序设计，必须用可以量化的方式保证程序设计的可能性。基于上述考虑提出了以下的地图匹配算法，算法分为3个步骤。

　　3.1 数据预处理过程

　　利用各种规则形成的知识库过滤掉异常定位数据，并对其进行有效插值。主要考虑的因素有：GPS板提供的PDOP值（一般取PROP>6）、地图范围（预先确定车辆行驶的有效地理区域），以及车辆的行驶速度等。其规则如下：

　　规则1 IF PDOP>6 THEN GPS数据异常，转规则5；

　　规则2 IF Pos（L，B）NOT IN MapArea THENGPS数据异常，转规则5；

　　规则3 IF Pos（V）>Const Car Speed THENGPS数据异常，转规则5；

　　规则4 IF Pos（V）　　规则5 IF Car In隧道或立交桥THEN GPS数据异常；ELSE DR子系统启动获取定位数据。

　　其中，MapArea为预先设定的车辆行驶的地理区域理论范围；Pos（L，B）为当前车载GPS定位数据；Pos（V）为当前车辆行驶速度；Car Speed为预先设定的车辆行驶的最大理论值。

　　3.2 车辆行驶路段的确定

　　美国取消SA干涉政策后，GPS的精度在正常状况下小于25 m，在大部分路段可以直接投影获得当前车辆行驶的道路。难于判断的情况一般出现在车辆通视条件较差等原因引起的GPS定位精度降低或车辆在道路交叉口时。

　　令△Cdistance为GPS值与当前道路投影点之间的距离；△distance为GPS值与其他道路投影点之间的距离；MaxD为预先设定的搜索道路的距离阈值。阈值通常根据概率准则来确定，即必须以一定的概率包含车辆的实际位置。按照统计理论，可首先确定一个误差椭圆：