基于三证据DS理论的双模式地图匹配算法

王 科,李 鹏,金 瑜,刘 宇

(1.武汉科技大学 计算机科学与技术学院,武汉 430065;2.智能信息处理与实时工业系统湖北省重点实验室,武汉 430065)

0 概述

近年来,汽车上电子地图[1]的普及率越来越高。大多数时候,汽车总是行走在道路上,现有的定位手段[2]如GPS、网络定位、基站定位等都不能精确地给出定位坐标,地图匹配的工作就是将定位结果纠正到正确的道路上,并尽可能符合汽车的准确位置。

常见的地图匹配算法有直接投影法、概率统计算法、拓扑结构算法、相关系数算法、DS证据理论算法等[3-9]。直接投影法是把定位点垂直投影到最近的道路上,此方法虽然计算量小,但误差较大,实际应用中是在最终确定了正确道路之后用此方法确定精确位置。概率统计算法的基本思想是根据定位坐标设置一个置信区域,计算误差椭圆,从中提取待匹配的道路节点信息,然后利用定位的方向、速度等信息确定匹配道路。但误差椭圆的计算和道路的筛选会带来巨大的计算量,无法保证系统的实时性。拓扑结构算法是在弧段和弧段之间建立了拓扑关系的基础上进行的,通过对历史匹配信息的综合,分析道路网的拓扑结构,确定匹配路段。由于考虑单一信息,对于较为复杂的道路,此类算法准确率会降低。相关系数算法是通过计算一段行驶时间内的定位点与数据库中各道路存储结点的相关性系数,选出相关性最高的作为匹配道路。这种算法需要较多的较准确的定位点才能准确匹配,但对于多条道路弧线相似的情况,不能准确识别。DS证据理论算法是对所有的候选道路集,选出2条及以上可以证明定位点在该道路上的证据,并构造适当的证据函数,分别对每条道路进行证据融合并计算出基本概率分配函数,函数值最高的即为最佳匹配道路。此外,还有基于曲率积分的地图匹配算法[10]、基于模糊逻辑识别的地图匹配算法[11]、基于人工神经网络的地图匹配算法[12]等。

本文针对当前基于DS证据理论的地图匹配算法进行改进,在距离和方向2个证据的基础上,增加了一个历史可信证据,通过对3个证据的融合来提高匹配结果的稳定性和准确率。另外,由于地图道路网的复杂性,一种匹配模式不能适用于所有类型的道路。对于所有道路,本文算法将其分为路口和路段两部分,对这2种不同的道路采用不同的模式进行匹配。路口模式是对路口的匹配,在路口使用概率统计算法确定误差区域,从中提取候选道路,然后使用基于三证据的DS证据理论方法计算各候选道路的概率分配函数值来确定匹配道路,最后利用相关系数算法进行结论论证。路段模式是对路段的匹配,使用改进的相关系数算法对历史匹配结果进行检验,通过检验输出投影点。

1 改进的DS证据理论

在进行DS证据论证之前,先要取得样本空间,即所有候选道路构成的集合。通过概率统计计算出定位点的置信区域,从中筛选出候选道路。

1.1 置信区域

置信区域是指根据概率统计理论中计算出误差椭圆内的区域,误差椭圆推导公式[13]如下:

(1)

(2)

(3)

其中,a、b是椭圆的长短半轴,σx和σy分别是经度和纬度的标准差,σxy是协方差,σ0是单位权值的后验方差,可改变它的大小调整置信区域的范围,φ是椭圆长半轴与正北方向的夹角。由于判断路段是否落在椭圆内需要执行大量的开方运算,因此在实际应用中通常将误差区域简化为矩形区域,该矩形区域为椭圆的最小包围矩形。长和宽的计算公式如下:

(4)

(5)

1.2 DS证据理论

DS证据理论是由A.P.Dempster提出,G.Shafer进一步完善的一种处理不确定性的理论[14]。该理论满足比概率论更弱的公理,能够区分“不确定”与“不知道”的差异。当存在多方证据时,可对证据进行融合,提高结果的可靠性。根据文献[8]应用于地图匹配的DS证据理论,设从概率统计算法计算出误差椭圆中提取的全部候选道路集合为:D={S1,S2,…,Si,…,Sn|i=1,2,…,n}。取定位点到Si的投影距离和当前行驶方向作为2个证据,用j进行编号。设证据函数为fij,因投影距离越小越可信,故分别取距离和方向偏值的倒数进行归一化处理即为证据函数,文献[8]已详细说明,此处不再赘述。文献[8]将基本概率分配函数构造为:

(6)

(7)

其中,mj(Si)表示证据j对命题“道路Si是匹配道路”的精确信任程度,mj(θ)表示不确定车辆在哪条道路上,kj表示证据j的可靠性参数,文献[8]对其默认值都取0.8。最后根据DS合成公式,将2个基本概率分配函数合成为一个基本概率分配函数m(Si),Si对应的概率分配函数值最大的即为匹配结果。

1.3 置信区域

由于二证据DS证据理论证据过少导致匹配结果不稳定且容易产生误匹配,引入第3个证据——历史证据。将距离和方向2个证据融合后的二证据概率分配函数再与历史证据进行融合。历史因子为前一定位点匹配道路的二证据概率分配函数值m′(max)。当j=3时,历史证据函数构造为:

(8)

在式(8)中,分母为所有候选道路的二证据基本概率分配函数值之和,分子为当前候选道路的二证据基本概率分配函数值再加上历史因子m′(max),若当前候选道路与历史道路不重合,则m′(max)为0。对于不同的候选道路,其历史证据函数的差异在于,前一定位点是否支持当前定位点位于当前候选道路上,即若前一定位点的匹配道路与当前候选道路重合,则m′(max)为前一定位点匹配道路的概率分配函数值,否则m′(max)为0。同样根据式(6)、式(7)得出历史证据的基本概率分配函数。由于目前还没有有效的可靠性参数理论计算方法,文献[8]亦未展开讨论,本文在实验中设置不同的历史证据可靠性参数k3,通过实验效果来确定k3的值。

根据DS融合公式将当前证据函数与历史证据进行融合,m′(Si)中的最大值即为匹配结果。融合后的基本概率公式为:

(9)

2 双模式地图匹配算法

传统地图匹配都只使用一种匹配模式,对匹配正确率和匹配速度的平衡没有进行研究,对此,本文提出一种双模式匹配算法。图1(a)是一个典型的交叉道路网络,当汽车行驶于道路A上接近路口时,此时是路口模式,首先计算置信区域,筛选候选道路,然后进行三证据融合得出结论,最后利用相似性对结论进行验证。由于加入了与历史证据的融合,在进入道路B之前匹配结果会稳定在道路A上。进入道路B的中间路段后,置信区域和三证据融合的大量计算会影响匹配速度,由于汽车移动的短时平稳特性,不需要复杂的推理。此时切换为路段模式,即直接通过计算相似性对结论进行验证,以确定汽车是行驶在该道路上,这样保证了匹配的高效性。如图1(b)对仅使用路口模式(单模式)和双模式匹配用时进行6次比较,在两者匹配正确率相同的情况下,可以看出双模式用时少。

图1 双模式切换路网图例分析

算法使用匹配队列存储已匹配成功的定位点,它是一个队列,队尾总是指向前一定位点,队列长度可根据道路的长度动态调整。另外需要注意的是,本文所指的道路的节点和结点是2个不同的概念。节点指的是一条弧段的2个端点或具有标志性的点,结点指的是一条弧段的坐标表示点。

2.1 置信区域

定义1(相似指数) 指当前匹配队列中的点形成的曲线与道路曲线的相似程度。相似指数用于对DS证据理论算法推理出结论进行2次检验,防止出现概率分配值最大而不满足相似性的匹配道路。令x代表经度,y代表纬度。假设用Q表示相似性,其公式如下:

(10)

其中,Rx和Ry分别是行驶轨迹经度与匹配道路经度和行驶轨迹纬度与匹配道路纬度的相关系数。首先根据匹配队列中的点和匹配道路生成一个n×4的样本矩阵,n为匹配队列的当前长度。矩阵的列从左到右依次为匹配队列中点的横坐标、纵坐标以及匹配道路的横坐标、纵坐标,表示如下:

根据样本矩阵计算相关系数的公式为:

(11)

这里仅以经度为示例给出公式,纬度把x换成对应的y即可。当相似指数达到预定值即判定匹配道路就是最终结果。

2.2 道路结构划分

定义2(转换节点) 算法把一条道路分为路口和路段,两者之间的界限称为转换节点。

如图2所示,假设Ni和Nj是一条道路的2个节点,Pc是当前定位点在此道路上的投影点,Dij是Ni到Nj的长度,Dki是Ni到Pc的长度,Dkj是Nj到Pc的长度,若定位点满足下式:

Dki>λDij&&Dkj>λDij

(12)

则处于路段,使用路段匹配模式;否则处于路口,使用路口匹配模式。

图2 转换节点示意图

2.3 算法实现

在进行地图匹配前,必须先做数据的预处理工作。由于各种版本的电子地图使用的坐标系各不相同,因此要把定位点转化为对应的坐标系才能进行计算。之后是数据有效性的判断,无效数据舍弃,并使用线性插值插入一个数据再进行匹配。接下来是模式的选择,根据式(12)判断当前定位点的位置,选择不同的模式进行匹配。算法伪代码如下:

输入GPS定位信息,按一定的频率自动接收

输出每个定位数据在地图上的匹配点

1.匹配参数初始化,数据接收准备;

2.While (第i个定位点di≠null) DO

3. 对di进行有效性判断及预处理;

4. 根据模式信号量选择不同模式进行匹配。

5. IF (路口模式)

6. 利用式(4)、式(5)计算误差区域,并从中筛选出所有候选道路s;

7. FOR ∀Si∈S DO

8. 利用式(9)计算出Si对应的概率分配函数值;

9. 选出概率分配函数值最大的对应的道路Si,对其进行相似性验证;

10. ELSE

11. 利用相似性对历史结果进行验证;

12. IF (检测换道)

13. 清空匹配队列,初始化各参数。

14. ELSE

15. 根据式(12)判断di是否为转换节点,若是,则设置模式信号量。

16.输出匹配结果,将di添加到匹配队列;

17.END While

接着分析算法的时间复杂度。设有n个点、m条候选道路。第6行是概率统计算法,时间复杂度为O(m×n),第8行是三证据D-S证据理论算法,对m条道路进行3次融合,时间复杂度为O(m×m×n),相似性验证的时间复杂度为O(n)。第15行是转换节点的判断,时间复杂度为O(n)。综上,时间复杂度为O(m×m×n)。从空间复杂度来看,整个算法维护一个匹配队列,其长度固定,空间复杂度为O(1)。n个点对应m条道路信息的存储,故空间复杂度为O(m×n)。

3 系统测试

本文的实验平台采用Android系统+百度地图来呈现。实验数据来源于真实的GPS数据采集。由于百度地图采用自家的bd09ll坐标系,因此在实验中要把GPS的坐标系转换成bd09ll坐标系。

本文采用带GPS定位的Android手机,驾车行驶在学校周边公路,以每5 s一次的频率来收集定位数据。在数据处理中利用获取到的道路信息,按算法需求编制道路存储结点及道路之间的节点,组建道路拓扑关系,计算道路长度、方向等。

3.1 可靠性参数选取

为确定合适的历史证据可靠性参数k3,首先对其取不同的值进行4次匹配正确率测试,取值范围为0.6～0.9,以0.05作为步长。为使参数适应多种环境,每次测试需选择不同的道路结构,包括平行道路、交叉道路、扇形道路、网格道路。实验统计结果如图3所示。

图3 k3取值测试分析

由图3可以看出,在各种类型道路中,综合起来当k3取0.8时,匹配正确率最高,故本文算法取k3=0.8。

3.2 匹配效果

本文选取了学校周边的一组定位数据作为测试样本,匹配算法采用文献[8]提出的一种汽车导航中的DS证据理论地图匹配算法(以下简称导航DS算法)和本文基于三证据DS证据理论地图匹配算法(以下简称三-DS算法),结果如图4、图5所示。其中红色部分(细点)是GPS定位轨迹,蓝色部分(粗点)是对应的匹配轨迹。图中一共有224个定位点,导航DS匹配成功的有194个点,三-DS匹配成功的有209个点,并且在匹配点的均匀性和稳定性方面,三-DS算法要优于前者。

图4 导航DS算法匹配效果

图5 三-DS算法匹配效果

3.3 匹配稳定性测试

为确定引入的历史证据对匹配结果稳定性的影响大小,对3条相近的平行路段匹配过程中各定位点概率分配值进行统计。已知汽车行驶在道路2上。统计仅使用2个证据(简称二-DS)和三-DS算法各个定位点在3条道路概率分配函数值,d1～d8表示8个定位点,结果如表1、表2所示。

表1 二-DS算法概率值

表2 三-DS算法概率值

从表1可以看出,若只采用二证据,d3～d5会出现误匹配,且匹配结果很不稳定。从表2可以看出,因加入了与历史证据的融合,没有出现误匹配,且匹配结果比较稳定。

3.4 匹配效率对比

为检验本文算法的匹配效率,本文比较了以下基准算法:1)本文提出的三-DS算法;2)直接投影算法;3)文献[8]提出的一种汽车导航中的DS证据理论地图匹配算法(导航DS);4)文献[10]提出的曲率积分约束地图匹配方法(曲率积分);5)文献[15]提出的基于概率统计、拓扑关系等结合的算法(拓扑算法)。

首先测试算法对密集定位点和稀疏定位点的匹配能力,使用不同的采样频率采集定位数据,对5种算法的准确率进行统计。实验控制道路长度为200 m,行驶速度为15 km/h,结果如图6、图7所示。

图6 不同频率数据集算法的正确率(密集定位点)

图7 不同频率数据集算法的正确率(稀疏定位点)

从图6、图7可以看出,在相对密集的数据集中,三-DS算法保持了较好的稳定性,正确率整体高于另外4种算法,导航DS算法对定位频率的依赖比较高,拓扑算法正确率较低且不稳定,曲率积分同样受定位频率影响较大;对于稀疏数据集,只有一些零星的点组成的轨迹,5种算法正确率下降都比较快,但三-DS算法仍具有一定的稳定性。

然后对比分析不同量数据集各种算法的匹配完成时间。图8列出了8组小量数据集及各算法完成匹配的时间。从图8中可以看出,在小量数据集中,除了直接投影外,三-DS算法完成时间比其他3种算法都要短,且随着数据集的增大增长较缓慢;其余算法用时较长,增长速度也较快。

图8 小量数据集算法完成时间对比

接着将数据集增大一个数量级,进一步比较各算法的性能。如图9所示,在中量数据集中三-DS算法继续保持优势,图10是大量数据集算法完成时间对比,三-DS算法明显要比其他4种算法用时少。

图9 中量数据集算法完成时间对比

图10 大量数据集算法完成时间对比

综上可见,基于三证据DS理论双模式地图匹配算法无论在完成时间还是正确率上,相比其他算法都有了一定提高。在计算能力相对较弱的移动平台上也能达到满意的效果。

4 结束语

本文对当前基于DS证据理论的地图匹配算法进行改进,在距离和方向2个证据的基础上,增加了一个历史可信证据,通过对3个证据的融合提高匹配结果的稳定性和准确率。实验结果表明,与传统DS理论地图匹配算法相比,三证据DS理论双模式地图匹配算法匹配准确率更高。但本文算法也存在不足之处,如算法中涉及到的一些系数权值都没有给出具体的确定方案,仅通过实验效果来确定,在处理复杂的立交桥等路段时,稳定性较差。在今后的研究中,会继续对算法做出更合理、更普适的改进。

[1] 黄瑞阳,郭建忠,余慧明,等.基于Silverlight的矢量地图符号模型设计与实践[J].测绘工程,2013,22(1):7-11.

[2] 段 荣,赵修斌,庞春雷,等.一种GPS移动基准站精密相对定位新算法[J].四川大学学报(工程科学版),2015,47(3):130-136.

[3] 周 成,袁家政,刘宏哲,等.智能交通领域中地图匹配算法研究[J].计算机科学,2015,42(10):1-6.

[4] BIERLAIRE M,CHEN J,NEWMAN J.A probabilistic map matching method for smartphone GPS data[J].Transportations Research,Part C:Emerging Technologies,2013,26(1):78-98.

[5] 朱 递,刘 瑜.一种路网拓扑约束下的增量型地图匹配算法[J].武汉大学学报(信息科学版),2017,42(1):77-83.

[6] 李清泉,胡 波,乐 阳.一种基于约束的最短路径低频浮动车数据地图匹配算法[J].武汉大学学报(信息科学版),2013,38(7):805-808.

[7] KAKUMA D,TSUICHIHARA S,RICARDEZ G A G,et al.Alignment of occupancy grid and floor maps using graph matching[C]//Proceedings of IEEE International Conference on Semantic Computing.Washington D.C.,USA:IEEE Press,2017:57-60.

[8] 李 珂,杨 杨,邱雪松.城市汽车导航中一种改进的 DS 证据理论地图匹配算法[J].测绘学报,2014,43(2):208-220.

[9] 向长风,徐 圆,朱群雄.一种面向景区导航的动态地图匹配算法[J].计算机工程,2016,42(10):32-37,44.

[10] 曾 喆,李清泉,邹海翔,等.曲率积分约束的GPS浮动车地图匹配方法[J].测绘学报,2015,44(10):1167-1176.

[11] DINH V Q,NGUYEN V D,van NGUYEN H,et al.Fuzzy encoding pattern for stereo matching cost[J].IEEE Transactions on Circuits and Systems for Video Technology,2016,26(7):1215-1228.

[12] SAEEDI S,PAULL L,TRENTINUI M,et al.Neural network-based multiple robot simultaneous localization and mapping[J].IEEE Transactions on Neural Networks,2011,22(12):2376-2387.

[13] 许国建,张志利,周召发.基于DR/GIS组合导航的误差补偿研究[J].计算机工程,2013,39(5):314-317.

[14] DONG G,KUANG G.Target recognition via information aggregation through Dempster-Shafer’s evidence theory[J].IEEE Geoscience and Remote Sensing Letters,2015,12(6):1247-1251.

[15] 王 敏,魏衡华,鲍远律.GPS导航系统中的地图匹配算法[J].计算机工程,2012,38(14):259-261.