GPS/DR组合导航的地图粗匹配算法研究

晏 胤，黎福海

湖南大学 电气与信息工程学院，长沙 410082

1 引言

随着科技的发展，GPS导航越来越多的用在民用汽车导航领域。在信号正常的情况下，车载GPS产品的定位精度在20 m左右；在遇到高层建筑物、林荫道、隧道、立交桥或者地下停车场时，车载GPS接收机接收到的信号将受到影响甚至出现中断现象，这使得要获得连续精确的导航定位信息，必须辅助其他的导航设备。

航位推算（Dead Reckoning，DR）是一种汽车自主式的导航定位技术，主要由方向传感器、位移传感器和高度传感器组成。由于方向传感器和位移传感器的误差随时间的延长而积累，因此，在短时间内具有较高的精度，长时间单独使用就会有较大的累积误差。

GPS和DR两者有很强的互补性，将两者结合起来，可以保证系统能连续实时的为车辆提供较为精确的导航定位信息[1]。一方面，当GPS信号良好时，经过处理的GPS信号可以为DR纠正累积误差，提高DR定位精度；一方面，当GPS信号不好时，可以适当地加大DR系统在导航定位中所占的比重，以提高整个系统的定位准确度。实际应用中，GPS/DR组合导航系统常常辅以地图匹配（Map-Matching，MM）技术，实时的对组合导航系统输出的信息[2]进行地图匹配，可以将导航信息简单、直观地传递给驾驶者。

2 地图匹配

2.1 地图匹配技术

地图匹配[3]的基本思想是将车辆的行驶轨迹与数字地图中的道路对应起来，并确定车辆在道路网中的精确位置。因此，地图匹配可以看成是两个独立的过程：一是确定车辆当前所在的行驶路段，简称粗匹配；二是将车辆精确定位到行驶路段上的一点，简称精匹配。地图匹配是一种软件技术的定位修正方法，其应用必须要有两个前提：

（1）用于匹配的数字地图包含高精度的道路位置信息及道路之间的联通关系；

（2）被测车辆行驶在道路网中。

满足上述两个条件时，就可以把车辆的行驶轨迹与定位信息和数字地图中的道路位置信息进行比较，并通过数据处理，确定车辆最可能的行驶道路和在该道路上的最大可能位置。

2.2 地图匹配方法

目前常用于确定车辆当前所在的行驶路段的方法有直接投影法、相关性算法、概率统计法、模糊逻辑法等[4]。

直接投影法[5-6]是在车辆当前位置附近一定区域内查找最近的路段，直接将定位数据投影到此路段，投影点即为车辆的校正位置。此方法优点是简单、易行，可以在一定程度上提高定位精度；缺点是稳定性差且效率低。

相关性算法[7-8]是利用特殊形状（拐角、交叉等）对行车轨迹进行校正，在所有候选道路中，与实际测出路线相关性最高的路线定位车辆的真实行驶路线。传统的相关性算法在航向改变大的情况下效果很好，但如果几条候选线路相关性相差不大，就容易造成线路无法确定的缺陷。

概率统计法[9-10]是利用概率统计的方法设置一个置信区，把用来匹配的道路位置信息从中提取出来，并找出最佳匹配路段。此方法匹配的效率完全依靠数字地图和GPS的精度，同时，还有一个缺陷就是算法没有预定车辆一直在道路上，若偏离道路，将会产生积累误差。

模糊逻辑法[11-12]是利用数字地图匹配中所涉及的模糊度的定性决策过程，其特点是适用于绝大多数不同的路段，匹配效率高，实时性好，但建模参数缺乏理论依据，对慢车速和较大方向变化时匹配效果欠佳。

2.3 地图粗匹配

要对在道路网中行驶的车辆进行精确定位，首先要确定车辆当前的行驶路段，即将车辆的行驶轨迹与道路网络进行粗匹配。本文以直接投影法为基础，结合相关性算法和概率统计法的优点，提出一种新的地图粗匹配算法用来快速正确地选定车辆行车路段。

3 粗匹配算法

3.1 粗匹配算法总体设计

粗匹配算法选取与行车轨迹匹配程度最高的路段[13]作为当前行车路段，匹配程度用车辆定位点到候选路段之间的距离、行车方向与候选路段之间的方向偏差以及历史匹配程度3个因素来衡量。车辆行驶轨迹与某条路段的匹配程度用下式计算：

式（1）对应的矩阵表达式如下：

假定在距离被定位车辆一定范围内，有m条道路通过，对车辆的位置进行n次采样。式（1）和式（2）中的各参数含义如下：M为当前匹配程度矩阵，mmn为第n个采样点对第m条候选路段的匹配程度值；D为采样点到候选路段之间的距离参数对角矩阵，d((m×n)(m×n))为第n个采样点到第m条候选路段之间的距离参数值，α为距离参数的调整系数矩阵，αmn为对应采样点到候选路段的调整系数；A为行车方向与候选路段方向的夹角参数对角矩阵，a((m×n)(m×n))为第n个采样点行车方向与第m条候选路段方向的夹角参数值，β为行车方向与候选路段方向的夹角参数的调整系数矩阵，βmn为对应采样点到候选路段的调整系数；M′为历史匹配程度参数对角矩阵，m′((m×n)(m×n))第n个采样点到第m条候选路段的历史匹配程度参数值，γ为历史匹配程度参数的调整系数矩阵，γmn为对应采样点到候选路段的调整系数。

3.2 算法参数设置

3.2.1 距离参数及其调整系数

以采样点为正方形中心，以200 m为边长画正方形，与这个正方形相交或在正方形内的所有路段为候选路段，若在此范围内无候选路段，则说明车辆偏离道路较远，不在道路网中行驶。Dij为车辆位置的第j个采样点到候选路段第i条之间的距离，单位为米，Dmin为第j个采样点到所有m条候选路段之间距离的最小值。

采样点到路段的距离定义为采样点到路段上所有点的最小值，分为3种情况：（1）采样点在路段上，距离为0；（2）采样点在路段外，过采样点作路段的垂线，垂足在路段上，垂线段的长度即为距离d；（3）采样点在路段外，垂足在路段的延长线上，采样点与距垂足最近的那个端点的距离即为采样点到路段的距离d1。如图1所示，图中距离的单位均为m。

图1 点到线段距离

如图1，车辆位置采样点P由GPS测量位置数据经过滤波处理得到，由于目前GPS定位精度为20 m，设置参数d((i×j)(i×j))时，门限值选择20 m比较合适；设置调整系数αij时，门限值选择30 m和100 m比较合适。由于GPS的定位精度受实际使用环境影响，故选取调整系数时，通过多次仿真统计，将门限值扩大到距离门限值的1.5倍，当车辆位置采样点到路段的距离小于30 m时，认为车辆在此路段的可能性非常高，调整系数取1；当大于100 m时，则若单独考虑距离因素，车辆不可能在此路段上行驶，调整系数取0。距离参数及其调整系数都进行归一化处理，其最大值均为1，以便对不同的道路的匹配程度有同一标准。

3.2.2 角度参数及其调整系数

Δθij为车辆在第j个采样点的综合行驶方向与第i条候选路段方向之间的夹角，单个GPS测向需要进行多点采样并统计采样点的位置，花费时间较多，而两台GPS测向又增加了设备成本，且车辆长度不大，导致的测向精度也不高。目前常用的低精度DR测向能控制在2°范围之内，根据概率分布的3倍标准差原则，考虑到实际应用环境，设置参数a((i×j)(i×j))时，选取门限值 6°；设置调整系数βij时，选取门限值为15°和60°。当夹角小于15°时，车辆在此路段行驶的可能性很高，调整系数取1；当夹角大于60°时，车辆在此路段行驶的可能性非常低，调整系数取0。角度参数及其调整系数同样运用归一化原理，各自的最大值均为1。

3.2.3 历史匹配参数及其调整系数

m′((i×j)(i×j))表示第j个采样点对第i条候选路段的历史匹配参数值，mik表示第k个采样点对第i条路段匹配程度值，第一个采样点对任何候选路段的历史匹配参数取0，γij为对应的调整系数值。同时，根据控制k的值来控制历史匹配点数对当前匹配程度的影响，这样可以根据需要选取不同的窗口长度，满足不同的道路速度需求。

4 仿真分析

4.1 粗匹配算法理论仿真与统计分析

衡量粗匹配算法的两项标准是时效性和正确率，根据邻近路段的密集性和与实际行驶路段的相似性[14]，模拟实际道路路况，将实际路况分6种情况进行仿真分析，同时，对各种不同的道路路况按3种不同的采样点数进行匹配正确率统计比较，其结果如表1所示。

各种路况所代表的与实际行驶路段相似的道路信息如下：

路况1表示邻近路段有一条道路与实际行驶路段平行，且与行驶路段的距离为20 m；

路况2表示邻近路段有一条道路与实际行驶路段的夹角为10°，且在车辆行驶位置附近与行驶路段相交；

路况3为路况1和路况2的组合，且两条相似道路分居在实际行驶路段的两边；

路况4表示邻近路段有一条道路与实际行驶路段平行，且与行驶路段的距离为40 m；

路况5表示邻近路段有一条道路与实际行驶路段的夹角为20°，且在车辆行驶位置附近与行驶路段相交；

路况6为路况4和路况5的组合，且两条相似道路分居在实际行驶路段的两边。

每种路况类型进行3种不同的采样点数的匹配，每个采样点的时间间隔为1 s，与GPS的数据更新时间一致。假定定位车辆在道路上的行驶速度为20 m/s，即每个采样点的间隔为20 m，表中的每个匹配正确率数据是经过50 000次的仿真后进行数理统计得到的平均值。从表中横向数据可以看出，总体的匹配正确率随采样点数的增加而增加，采样点数越多，匹配的稳定性越好；从纵向数据可以看出，在相似性和密集程度大大超出现实生活中道路类型路况3中，只需5 s的采样匹配时间，就能让算法的正确率保持在99%以上。路况3的单次匹配仿真图如图2所示；路况6的仿真条件满足绝大多数的现实道路，将其作为实际路况的类型，其单次匹配仿真如图3所示。

图2 路况3匹配效果

图3 况6匹配效果

图2、图3中，红色的线段为单次仿真匹配出的路段，与实际行驶路段一致，蓝色的“*”为5个采样点。从实际仿真的数据统计可以看出，满足绝大多数实际路况条件的路况6，3个采样点的采样时间为3 s，匹配的正确率超过99%，在匹配时效和正确率两方面有着良好的兼容性。

4.2 实际路况模拟验证

由于开阔地带的道路信息相对比较简单，对算法的实用性好坏检验说服力不强，故选取路况复杂程度较高的城区道路作为本次模拟仿真的行驶区域，将长沙市岳麓区湖南大学附近区域作为验证算法匹配的地图区域，其电子地图界面如图4所示。

图4 匹配区域电子地图

将图4中的道路信息提取出来，并经过坐标转换[15]，使其在二维坐标系中的位置坐标信息如图5所示。

图5 坐标转换图

车辆从E点出发，沿EN方向前进，如图中红色箭头所示，其粗匹配效果如图6所示。

图6 际路况模拟粗匹配

图6中，蓝色的圆圈“o”为车辆的真实位置，红色的星号“*”为车辆的GPS定位位置，红色的线段是粗匹配算法选定的行车路段，与实际的行车路段一致，证明算法在模拟实际的行车路段时，一般的路况条件下，3个采样点即只需要3 s的时间就能确定车辆的行车路段，时效性和准确率得到良好的兼顾。

4.3 匹配时效性比较

选取同样的道路状况和传感器定位精度，考虑到实际的道路宽度和城市道路环境影响，将GPS的定位精度取为50 m，本文粗匹配算法分别与垂直投影匹配算法、历史轨迹推算匹配法、自适应匹配算法进行匹配时间和匹配准确率的比较[16]，其比较数据如表2所示。

表2 不同粗匹配算法匹配时效性、准确率比较

从表2可以看出，在同样的路况条件下，采用相同精度的传感器设备，本文算法加入了电子罗盘，引入航向信息，只需要7个采样点的时间就能保证91%的正确率，与表中其他算法相比，大大节省了选路时间，加快了车辆的选路过程，并在一定程度上提高了匹配的准确率。

5 结论

简单介绍了GPS与DR的基本工作原理及各自的误差分析，将地图匹配分为粗匹配和精匹配两个阶段，并设计了粗匹配的算法。结合目前GPS和DR产品的精度和实际道路情况，对算法参数进行了合理设定。按照多点采样原则对算法进行迭代，通过Matlab仿真测试和正确率统计分析，证明了匹配的正确率和稳定性随采样点数的增加而提高，与其他匹配算法相比，方向传感器引入的测向参数大大加快了车辆的选路过程，节省了选路时间。综合考虑粗匹配算法的时效性和正确率，选取5个采样点能很好的满足日常的定位需求，为后续的精匹配奠定了良好的基础，为数字地图匹配和车辆精确定位提供了一定的理论依据。

[1]寇艳红，张其善，李先亮.车载GPS/DR组合导航系统的数据融合算法[J].北京航空航天大学学报，2003，29（3）：264-268.

[2]常青，郑平方，柳重堪，等.车载GPS/DR组合导航系统数据融合算法研究[J].通信学报，2000，21（2）：42-48.

[3]Jingyu H，Xiong F，Linfeng L，et al.Online map matching by indexing approximate road segments[C]//Proceedings of IEEE 2nd International Conference on Software Engineering and Service Science，2011.

[4]方伟骏，黄圣国.GPS/MM车载导航系统的研究与实现[J].微计算机信息，2007，23（25）：215-216.

[5]Liu Z，Hu D，Feng G.Visual tracking based on direct orthogonal locality preserving projections.2012.

[6]苏奎峰，邓志东，黄振.基于曲率特征的自主车辆地图匹配定位方法[J].机器人，2012，34（4）：440-448.

[7]Bernoulli T，Krammer M，Walder U，et al.Improvement of inertial sensor based indoor navigation by video content analysis[C]//Proceedings of International Conference on Indoor Positioning and Indoor Navigation，21-23 Sept，2011.

[8]Fanming L，Dong Q.A matching algorithm for GGI aided navigation where reference map is obtained by forward method[C]//Proceedings of IEEE International Conference on Information and Automation，20-23 June，2010.

[9]彭飞，柳重堪，张其善.基于代价函数的组合导航系统地图匹配算法[J].北京航空航天大学学报，2002，28（3）：261-264.

[10]荆涛.车辆导航系统中地图匹配的研究[J].铁路计算机应用，2008，17（7）：1-5.

[11]张小国，何坤贤，王庆.一种移动对象数据库的自适应更新方法[J].小型微型计算机系统，2010，31（12）：2331-2336.

[12]宋洁，李国燕，李娜娜，等.基于模糊逻辑的GPS/DR地图匹配算法[J].计算机工程与科学，2008，30（10）：30-32.

[13]杨殿阁，连小珉，张涛，等.基于北斗卫星的车辆组合导航系统开发[J].清华大学学报：自然科学版，2008，48（5）：856-859.

[14]曾波，江资斌.GPS车载导航系统的地图匹配算法[J].测绘工程，2004，13（3）：65-67.

[15]谢宁.GPS坐标转换方法的精度对比分析[J].硅谷，2011（4）：30-41.

[16]靳松杰.GPS车辆导航定位系统及自适应地图匹配算法的研究[D].西安：西安电子科技大学，2007.