角度和距离分段占优地图匹配算法

张彦会，曹强荣，何 维

(广西科技大学a.广西汽车零部件与整车技术重点实验室;b.汽车与交通学院，广西柳州545006)

0 引言

随着智能运输系统(ITS)的迅速发展，车载导航定位系统越来越受到关注，因此，如何快速、准确地获得车辆的位置信息变得更为迫切，地图匹配算法是实现快速、准确获取位置信息的关键，所以研究地图匹配算法是很有必要的。当前的地图定位匹配算法较多，第一种是基于位置点的地图匹配算法，该算法的优点是实时性好、逻辑简单，但该算法只适用于以直线型道路为主的情况，对于弯道或交叉路口较多、道路密集的道路，该算法的匹配准确率降低，易造成识别混乱的情况[1-3］。第二种是基于轨迹曲线的地图匹配算法，该算法的优点是对局部定位点的波动不敏感，在交叉路口或弯道较多的道路上匹配效果好，但该算法计算量较大，算法复杂，实时性差[4-5］。第三种是基于概率统计的算法，该算法的优点是以地理信息系统(GIS)缓冲区分析方法代替全球定位系统(GPS)误差椭圆，车辆在路网中的定位准确性和可靠性高，但该算法只适用于GIS数字地图数据库精度和GPS定位数据精度高的情况，在精度不高的场合定位时间长，且无法防止定位累积误差[6-7］。第四种是基于模糊逻辑的地图匹配算法，该算法的优点是在不同的路段采用加权二维欧式距离作为相似性度量函数方法，在复杂路段上都能高效、实时的实现车辆的定位匹配，但该算法在不同路段建模的系数为经验值，缺乏理论依据[8］。

本文提出了基于角度和距离分段占优的地图匹配算法。首先，在分段占优算法中运用自适应匹配因子进行目标路段的最优选取，能够增强匹配时对正确路段的识别能力以及对复杂路段的适应能力，提高定位匹配精度;其次，在节点处采用融合技术筛选匹配区域，大大简化了程序的复杂度，提高了定位的实时响应性。

1 两级交错式网格划分与二次圆域筛选融合技术

寻找车辆当前行驶的道路从过程上可以分为两个部分，即待匹配路段的快速筛选和最优路段的权值判断。在待匹配路段的快速筛选过程中，筛选区域的大小直接影响匹配算法的实时性。筛选区域选择过大，增加算法的复杂程度和计算时间;筛选区域选择过小，可以导致没有待匹配的路段。采用两级交错式网格划分与二次圆域筛选融合的方法能很好地解决这一问题，实现匹配算法的实时性。

图1所示为例，以100 m×100 m进行网格划分，假定定位点P落在6号网格内。然后以6号网格的形心A为中心，进行100 m×100 m的网格划分，得到A1、A2、A3、A4这4个网格。再对这4个网格进行二级网格划分，得到50 m×50 m的子网格，即可进一步确定P点在50 m×50 m子网格的具体位置，图1中定位点P确定在6’子网格中。对落在不同子网格的定位点P进行分析，记i为子网格标号，则:

经上述单位逻辑分析，其匹配路段范围可始终限定在100 m×100 m的区域内。

设数字地图长为L，宽为H，假设规定边长为S的正方形作为网格，S一般取100 m。a，b分别表示L、H方向的网格数，定位点P的坐标为(X，Y)(设网格1左下角坐标为(0，0))，则 A，A1，A2，A3，A4，A5，A6，A7和 A8的计算过程如下:

图1 两级交错式网格划分

其中，[］表示取整数。

以定位点P的平面位置为圆心，以GPS实时水平估计误差HEP值的2倍为半径[7］，对上述经过两级交错式网格划分得到的待匹配路段进行二次圆域筛选，如图2所示。P为圆域筛选的圆心，经过此次筛选，可以进一步缩小待匹配路段区域的大小，减少计算量，细化十字路口拓扑图，提高十字路口的匹配精度。图2中打阴影部分是经过两级交错式网格划分与二次圆域筛选融合算法，最终得到的待匹配路段区域。

融合算法的实现更大程度上缩小了待匹配路段的区域，不涉及大量复杂的计算，保证路段搜索的快速性和算法的实时性。与传统的网格划分相比，融合算法实时性更好，并提高了十字路口的匹配精度，表现出很大的优越性。

图2 二次圆域筛选模型图

2 角度和距离分段占优自适应算法

判断车辆当前行驶在哪条路段上的因素主要有4个:(Ⅰ)车辆当前定位点距候选路段的投影距离;(Ⅱ)车辆当前行驶方向与候选路段方向的夹角;(Ⅲ)候选路段与前一匹配路段的几何拓扑关系[8］;(Ⅳ)两个连续定位点之间的连线同候选路段的夹角。一般来讲，对第Ⅰ、第Ⅱ和第Ⅳ个因素，L、θ、β参数值越小，成为匹配路段的可能性越大;对第Ⅲ个的因素，几何拓扑关系成相连或相似状态，成为匹配路段的可能性越大，反之亦然。图3为角度和距离示意图，车辆在行驶过程中，计算定位点到待选区域中各路段的投影距离Li、车辆当前行驶方向与候选路段方向的夹角θi和两个连续定位点之间的连线同候选路段的夹角βi，并根据式(2)计算出待选区域中各路段的匹配值ωi。

式中，ωLi为投影距离因子;ωθi为行驶方向角度因子;ωβi为行驶角度变化率因子。

根据式(2)中ωi的权值就可以选出待匹配区域最优路段，ωi数值最大的即为最终匹配路段。为消除地图匹配中的偶然误差，对ωi采取权重平均值法。

本文对式(2)中的ωLi、ωθi和ωβi匹配因子采用分段占优自适应算法，以节点为研究中心，如图4所示，O1为节点，a、b、c和d为4条道路，每条道路至少有一条路段组成。对于节点O1，分别与其连接的路段的长短为半径在平面内做匹配圆，选择半径最小的圆作为该节点的匹配区域;对于定位点P，以实时水平估计误差HEP值为半径做匹配圆。ωLi、ωθi和ωβi匹配因子随着匹配区域的不同而变化。(Ⅰ)原始定位点P的匹配圆和节点O1的匹配区域接触时(即定位点P靠近节点O1)，车辆发生拐弯的可能性比较大，ωθi在匹配值中的比重应该增大;ωβi在拐弯时为非线性跳动状态，故要大大降低它在匹配值中的比重;ωLi在拐弯时不起主要作用，故也适当降低其比重，如 ωLi=0.3，ωθi=0.6，ωβi=0.1。(Ⅱ)原始定位点P的匹配圆和节点O1的匹配区域未接触时，情况与(Ⅰ)中相反，ωLi和ωβi起着决定作用，故增加它们的比重，如 ωLi=0.45，ωθi=0.10，ωβi=0.45。匹配因子的数值随着定位点与节点的相对位置而变化，这样自适应算法能够增强对正确路段和复杂路段的正确识别，同时也增加了匹配因子的灵活性。

图3 角度和距离示意图

图4 分段占优自适应算法模型图

3 匹配算法实现及异常处理

3.1 匹配算法实现

硬件搭建主要包括3大部分，即嵌入式平台、GPS模块和GPRS模块。其中，嵌入式平台为友善之臂的Tiny6410开发板，安装android操作系统;GPS模块为美国GARMIN公司的GPS25LP;GPRS模块为明基M33G Series，内嵌TCP/IP协议。GPS和GPRS模块分别通过串口和开发板连接。图5为匹配算法的流程图，该算法的核心包括:融合技术筛选匹配路段和分段占优算法选取匹配路段。匹配算法的主要步骤如下:(Ⅰ)获取GPS定位数据。(Ⅱ)判断定位数据是否异常和Temp表中有无可信点。若异常且Temp表无可信点，则重新进行GPS数据获取;若异常且Temp表有可信点，则进行异常处理。(Ⅲ)WGS-84转BJ-54坐标。(Ⅳ)由原始定位点通过融合技术筛选匹配路段区域。(Ⅴ)计算误差区域，并判断筛选区位于误差区域的置信度是否大于90%，大于90%，继续，小于90%，重新筛选。(Ⅵ)依据分段占优匹配因子自适应算法，计算原始定位点到筛选区域内所有路段的匹配值，取最小值为当前车辆的行驶路段。(Ⅶ)将原始定位点通过投影法，显示在地图上。

图5 地图匹配算法流程图

3.2 异常处理

异常处理是指对异常的GPS定位点数据进行处理的过程，包括奇异点数据处理和信号暂时中断处理。

(Ⅰ)奇异点数据处理

GPS接收机在遇到较大干扰的情况下，可能出现“跳点”。为了防止出现错误的道路匹配现象，必须降低跳点的出现频率[9-11］。本文对接收GPS定位点数据进行卡尔曼滤波预处理，采用的滤波方式是该定位点与上一定位点之间的连线同候选路段的夹角变化率不得超过最大变化角度(如定义为30°)，否则可以将该定位点滤除，即滤波算法采用抛弃该点方式。

(Ⅱ)信号暂时中断处理

信号暂时中断时(如车辆行驶在隧道等GPS信号不强的位置上)，应该采用线性插值数据补偿或采用A_GPS进行辅助定位，在车辆行驶的方向上进行线性差值预判断，直到能正常接收到GPS定位数据为止。

4 试验分析

为了验证匹配算法的实时性及定位精度的准确性，本文对该算法进行了跑车试验。图6为原始接收的位置数据和匹配后的位置数据比较，图中的三角形表示接收的原始GPS定位数据，圆形表示进行匹配算法后的定位数据。由图6可知:进行匹配后的数据全部在实际道路上，表明该算法的定位精度高，匹配效果好。

图7为位置误差对比曲线，图中虚线部分为原始GPS数据在实际道路上的误差，实线部分为经过匹配算法后的误差。从图7可知:经过匹配算法后的位置误差大大降低，保证位置误差在5 m以内，定位精度优于原始GPS定位精度。定位误差时大时小主要受车速和路况影响，对比图6和图7，图6中车辆进入拐弯时，正好对应图7出现位置误差最大值，即10 s时所对应的误差。未经匹配算法的GPS原始数据误差在15 m以上，经过匹配算法后定位误差大大降低，提高十字路口的匹配精度，与设计的初衷符合，证明本算法的合理性和正确性。同时，从图7还可以看出:在0.5 s时，出现位置误差对比曲线，所以采用该算法后能快速地把GPS数据匹配到实际道路上，定位时间为0.5 s。

图6 十字交叉道路实例

图7 位置误差对比曲线

5 结束语

本文结合嵌入式/电子地图系统，提出一种基于角度和距离分段占优的地图匹配算法。该算法由于采用分段占优自适应匹配因子，并引入融合技术网格筛选匹配区域的思想，同时对实际匹配过程中出现的异常情况进行处理，解决了普通的定位算法响应速度慢，匹配误差大的缺点。最后，通过试验和实时在线验证，表明该算法能适应不同的路段及交叉路口，并增强了车辆导航系统的定位性能，提高了实时性和匹配精度。

[1]唐思静.车辆定位导航系统中地图匹配和路径规划算法研究[D］.西安:西安电子科技大学，2009.

[2]陈岚岚，毕笃彦，马时平.Hausdorff距离在图像匹配中的运用[J］.现代电子技术，2012，9(4):68-69.

[3]华永平，刘砚一.车载定位系统中综合地图匹配算法研究[J］.现代雷达，2010，32(3):53-56.

[4]李聪.地图匹配算法设计与实现[D］.北京:北京交通大学，2011.

[5]Li X，Zhang X H，Lin H.Deriving Network-constrained Trajectories from Sporadic Tracking Points Collected in Locationbased Senicesy[J］.Geo-spatial Information Science，2009，12(2):85-94.

[6]Glaus R，Peels G，Muller U，et al.Precise Rail Track Surveying[J］.GPS World，2004，12(2):76-78.

[7]隋心.GPS车辆导航系统中地图匹配算法研究[D］.葫芦岛:辽宁工程技术大学，2007.

[8]张振辉，崔铁军.车辆导航系统中地图匹配算法的研究[J］.技术交流与应用，2007(2):55-59.

[9]陈嘉，胡继华，张飞舟.面向车辆监控导航的地图匹配算法研究[J］.北京大学学报，2009，45(2):299-305.

[10]李清泉，黄练.基于GPS轨迹数据的地图匹配算法[J］.测绘学报，2010，39(2):207-212.

[11]White C E，Bernstein D，Kornhau S A L.Some Map-matching Algorithms for Personal Navigation Assistants[J］.Transportation Research Part C，2000(8):91-108.