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

　　0引 言

　　随着城市化的进展和汽车的普及，交通拥挤加剧，交通事故频发，交通环境恶化，这成为长期以来困扰发展中国家和发达国家的严重问题。解决此问题的直接方法是提高路网的通行能力。可修建公路的空间有限，而且建设资金筹措困难。交通系统是复杂的大系统，我们应从系统论的观点出发，把车辆和道路综合起来考虑，运用各种高新技术系统解决交通问题，智能交通系统(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定位精度降低或车辆在道路交叉口时。[page]

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

　　车辆行驶路段的确定规则如下：

　　规则1 当接收到电子地图的标定信息如路径规划好的行车路线或者用户自定义道路属性类型代码时，直接利用标定信息匹配到所规划的道路路段上去；

　　规则2 IF在一定阈值内搜索到的道路数<1THEN车辆不在道路上，利用概率统计算法，可根据GPS的实时定位数据建立一个动态可调的点缓冲区替代误差椭圆，并利用误差椭圆扩展因子的原理，设置缓冲区扩展比例因子，动态可调的缓冲区半径按30 m，60 m，90 m和120 m四个等级由小到大逐级搜索落入缓冲区内的道路路段。在GPS定位失效的情况下，必须用DR(航位推算)定位的误差参数来代替GPS参数，完成误差区域的定义，以保证匹配过程的连续性。此时，要注意由于DR推算具有误差累积效应，随着推算过程的进行，统计模型误差、测量误差和各种随机误差将会不断累积。因此，在按DR定位的误差参数定义误差椭圆后，还应乘上适当的扩展因子来扩大误差区域，以反映误差累积对定位精度的影响。采用裁剪算法迅速判定侯选路段，通过计算不仅可以判知落入缓冲区内的路段，还可以求得路段与缓冲区的交点，从而取得GPS定位数据的匹配点坐标；

　　规则3 IF在一定阈值内搜索到的道路数=1THEN利用直接投影算法，把此道路作为车辆行驶的当前道路；

　　规则4 在一定阈值内搜索到的道路数>1&＆相同的道路节点号THEN车辆行驶在道路交叉口，根据交通状况种别A，B，C，D划分，采取对应策略，并利用相关性算法，计算测出轨迹与1组地图数据的相关性系数，在所有候选地图路线中与实际测出路线相关性最高的路线即为车辆行驶的真实路线；

　　规则5 在一定阈值内搜索到的道路数>1＆＆不同的道路节点号THEN车辆行驶在距离较近的平行道路之间，采用模糊逻辑算法中的利用距离和方向要素的线性组合方法，改进算法，令p1+p2=1，并对p2参照模糊逻辑算法模式中的确定相似性度量函数的加权因子Q的模糊判决规则确定其值，然后计算基于曲线拟合的地图匹配算法的相似性度量函数s，并选取最小值作为待匹配路段，即：在考虑角度和距离因素的情况下，该路段达到最优。

　　加权因子q取值如下：

规则5.1 IF道路为禁行或禁止转向或单行道的逆向THEN q="1".5*q；
规则5.2 IF已有路径规划且是路径规划路段THEN q="0".5*q；
规则5.3 IF道路与车辆的行驶方向一致THEN q="0".25*q。
规则6 IF发现如离开道路、电子地图简化后较为低级的道路描述不够详细、车辆进入停车场等情况，找不到可以匹配的行走路段THEN手动停止地图匹配，用接收的原始数据直接显示，不进行误差矫正。

　　3.3基于模糊逻辑的匹配路段可信度评判

　　以候选路段取向与车辆行驶方向的差(△heading，单位：度)值为论域X，令μhh(X)、μhc(x)为取向差(单位：度)的值x隶属于模糊子集"路段与车辆行驶取向一致性好"和"路段与车辆行驶取向一致性差"的隶属度，则μhh(X)、μhc(X)可取为：

　　在初始位置给定时，利用DR推算能够准确地描述出车辆在短时间内的行驶轨迹。因此，可按如下方式定义候选路段形状与当前车辆行驶轨迹的相似度：根据DR推算原理，现时刻tn的车辆位置(xn，yn)和车辆行驶取向θn可根据上一时刻tn-1的车辆位置(xn-1，yn-1)和行驶取向θn-1按下列公式推出：

　　式中：dn-1，n是tn-1到tn时刻车辆行驶过的距离，ωn-1，n是tn-1到tn时刻车辆行驶取向的变化量 (dn-1，n和ωn-1，n均由车载位移传感器和角速度传感器提供)。取车辆当前定位位置p0(x，y)在候选路段上的投影点p′0(x′，y′)为tn时刻DR推算定位的参考位置，取候选路段取向为tn时刻的参考行驶取向，则由DR推算公式可反推出前一时刻的推算定位参考点。通过多次推算即可获得一组参考点，具体数量可根据实际应用的要求确定。这里取参考点数目为5，则可定义候选路段与前5个单位时间内的DR定位轨迹平均距离差(单位：m)为：

　　上述隶属函数的图形如图1和图2所示。

[page]

以上述隶属度函数为基础，就可以对候选路段是当前车辆所在路段的可能性做出综合评判。以该可能性作为论域U，其元素u与论域X，Y和Z的笛卡尔乘积集：

　　它的元素(x，y，z)相对应，即u与三个因素有关。因此，在对u进行模糊评判时，因素集可以取为E={X，Y，Z)，评语集可取为F={大，小)，综合评判按下面的步骤进行：

　　(1) 对u进行单因素评价，然后利用其结果构造表示E与F之间模糊关系的模糊矩阵。设对因素X，Y，Z的单因素评价结果分别为模糊向量R1= [μhh(x)，μhc(x)]，R2=[μdh(y)，μdc(y)]和R3=[μ△dh(z)，μ△dc(z)]，则将以上模糊向量合在一起便得到表示E与F之间模糊关系的模糊矩阵 

　　(2)确定权向量P=[p1，p2，p3]，其中p1，p2，p3分别表示因素x，y，z在乱中的重要程度，p1+p2+p3=1。

　　(3)作模糊变换Q=P°R，所得模糊向量Q就是被评判对象U在评语集合F上的评判结果，其2个分量表示候选路段是车辆所在路段的可能性大小的程度。

　　在以上综合评判算法中，模糊矩阵乘法"°"采用简单的加权平均型算子(⊕，×)以便使结果兼顾各种因素。由于权向量的分量之和为1，运算⊕退化为一般的实数加法，因此算子(⊕，×)也可以改写成(+，×)。在这种情况下，模糊矩阵的乘法与普通矩阵的乘法完全一样。

　　有了对候选路段是当前车辆行驶路段的可能性的评价，就可以对以候选路段位置为参考进行地图匹配修正后的定位结果的可信度做出评价。评判中，应考虑到候选路段与前一时刻匹配路段的连通性，为此再引入以下规则：如果候选路段就是前一时刻匹配路段或者与前一时刻的匹配路段相连通，则利用该候选路段修正定位结果的可信度高。以修正结果为评判对象，取评判指标矩阵为(Q，Q′)，其中Q是候选路段的可能性评价矩阵，Q′是连通性评价矩阵，当候选路段与前一时刻匹配路段有连通关系时，Q′取为前一时刻匹配路段的可能性评价矩阵，否则以0矩阵取代。取评判权向量为P′=[p′1，p′2，p′3，p′4]，其分量分别对应于Q和Q′的各个分量，且p′1+p′2+p′3+p′4=1。将指标矩阵与权向量相乘，得μ=p′°[Q，Q′]T，称μ是修正定位结果的可信度，它为挑选最佳匹配路段提供了明确的依据。

　　4实验结果

　　交叉路口是地图匹配过程中最易出错的地方根据本文提出的改进的地图匹配算法理论，就交叉路口问题做性能分析，下面分两种情况讨论。

　　第一种情况：车辆直行通过交叉路口，如图3所示。

     轨迹点4，5靠近路段1，但轨迹点1、2、3、4、5拟合所得直线远远偏离路段1，靠近路段2，因而轨迹点5会正确匹配到路段2，不会被错误地匹配到路段 1。同理，轨迹点4也正确地匹配到路段2。由于考虑了轨迹的连续性，和基于位置点直接投影算法比起来，本文的算法不容易在交叉点出现匹配错误的情形。

　　第二种情况：车辆拐弯通过交叉路口，如图4所示。

　　轨迹点1、2、3、4、5拟合得到的拟合直线1与路段2的夹角小于30度，点5被匹配到路段2。同理，2、3、4、5、6拟合得到的拟合直线2与路段2的夹角也小于30度，点6被匹配到路段2。从图上可以看出，点5、6、7、8、9拟合得到的拟合直线5与路段1、2的夹角都大于30度，由算法基本原理可知，9不符合匹配条件，不予匹配。按照同样方法对其他点一一进行匹配。尽管在交叉路口附近会有少数的轨迹点不能被匹配，但匹配出来的轨迹能反映车辆的实际行驶轨迹，较好地处理了交叉路口的地图匹配问题。

　　为验证文中提出的地图匹配算法对导航系统定位精度的影响，利用该算法对跑车实测数据进行了实验。匹配结果表明，绝大多数(>96％)定位数据都能相对准确地匹配到道路上，匹配后的定位精度得到提高；匹配算法实现了实时，能够满足实际需要(1次／s)；在GPS受到一定程度的遮挡时系统能够正常识别并且匹配。