基于道路连通性和最短路径的综合地图匹配算法

崔松林,冯军焕

(西南交通大学 信息科学与技术学院,四川 成都 611756)

0 引 言

在智能交通领域中,一般通过实时收集浮动车的运行信息,如经度、纬度、速度、方向和定位时间等关键参数,并结合道路路网信息进行动态实时的交通大数据分析,从而了解道路的交通流量,堵塞状况,为车辆调度、车辆实时导航、道路规划建设等提供决策依据[1-2]。

地图匹配的本质是根据车辆GPS定位点匹配出电子地图中相对应的道路,通过读取车辆GPS定位信息,匹配出车辆所行驶的道路信息,从而分析道路的交通状况[3-4]。地图匹配的一般步骤为:1) 确定候选道路集; 2) 确定匹配道路; 3) 把待匹配点投影到匹配道路上,投影点即为最终匹配点[5]。

现有的地图匹配算法有要素加权法[6]、路网拓扑法[7-8]、网格划分法[9-10]等。要素加权法的特点是每次匹配的候选道路集为整个路网中的道路,依次计算每条道路的匹配度,匹配度最优的道路作为匹配道路,计算量大、速度慢。基于路网拓扑关系的匹配算法具有一定的匹配精度,但是首次匹配仍然需要遍历整个路网,并且在信号丢失的情况下,候选道路集仅仅考虑与上一匹配道路邻接的道路,不免会出错。网格划分法一定程度上减少了候选道路的数据量,但是网格的位置及大小无法动态调整,选取候选道路集时,判断情况过多,具有一定的局限性。还有一些其他算法[11-13],原理复杂,难于实现,很难投入实际应用。

本文在充分分析上述算法的基础上,综合利用GPS定位点方向、道路方向、GPS定位点和道路的最短距离以及道路的连通性,提出一种基于道路连通性和最短路径的地图匹配算法,该算法在匹配过程中采用捕捉圆的方式选取候选道路集,在速度和准确率上较优于传统算法,而且针对车辆定位信号丢失的情况,提出了一种推测车辆经过道路的方法。

1 地图数据预处理

本文采用成都市范围内的OpenStreetMap免费开放地图数据集作为实验数据集,该数据集中的道路要素是由一系列点要素组成。本文把每条道路要素存储为:[道路编号,起点要素,终点要素,点要素序列]。由于存储的每条道路要素是彼此孤立的,所以还需要建立道路要素之间的连通性。

如图1所示的道路网,其中小写字母表示道路名称,大写字母表示道路的起点或者终点。为建立道路之间的连通性,对路网进行预处理,采用键值对的存储方式将起点相同的道路存储在一起,存储格式为:[起点要素:[直接相连的道路要素]]。若要搜索与道路u直接相连的道路,可以读取预先存储的道路u的基本信息,得到道路u的终点B,而以B为起点的道路已经预先存储到键值为B的键值对中-[B:[v,w]],从而获取与道路u直接相连的道路是v和w.

联系人: 崔松林 E-mail: 437941580@qq.com

图1 简单路网

2 匹配算法设计与实现

2.1 计算道路方向

由于车载GPS定位系统对车辆行驶方向的定位为顺时针与正北方向的夹角,因此,为方便计算,道路方向的计算也以顺时针与正北方向的夹角为准。若某道路的起点和终点分别为P1(x1,y1)和P2(x2,y2),则该道路方向大小RD的计算方式如下,其中k表示直线P1P2的斜率:

RD=

2.2 计算定位点的投影点

投影点的计算主要考虑两种情况,1)匹配出的道路要素仅由两个点要素标示,此种情况,投影点的计算较为简单; 2)匹配出的道路要素由两个以上点要素标示,此时需要根据定位点与道路各点要素的距离关系,将投影点的计算方式转化为第一种情况。

情形1: 道路要素仅由两个点要素标示,如图2所示,其中Gn表示车辆的GPS定位点,E、F表

图2 车辆定位点分布位置

示道路的起点和终点。

① 当定位点位于道路上,定位点也即是投影点,定位点到道路的最短距离为0,图中G4点属于符合此情况。

② 当定位点在道路外,此时判断由点Gn、E、F三点所确定的三角形类型,如果△EFGn是锐角三角形,则说明由定位点向线段EF引垂线,垂足在线段EF上,即投影点可以落在线段EF上,图中G2点符合此种情况。如果△EFGn不是锐角三角形,则说明由定位点向线段EF引垂线,垂足在线段EF的延长线上,即投影点不可能落在线段EF上,此种情况下,如果定位点相对靠近起点,则选起点作为该定位点的投影点,否则选终点作为投影点,图中G1、G3符合此种情况。

情形2: 道路要素由多于两个点要素组成,如图3所示。首先判断△EFG的类型。

图3 定位点与道路各点要素的距离

① 若△EFG不是锐角三角形,则说明定位点的投影点无法落在线段EF上,此种情况下,如果点G相对靠近点E,那么选点E作为点G的投影点,否则选点F。

② 若△EFG是锐角三角形,则说明投影点可以落在线段EF上,但此时不能像情形1那样,直接计算投影点,因为线段EF由多个点要素组成,在实际路网中,线段EF可能是曲折的,此种情况下,寻找位于道路起点和终点之间的点要素,选取最靠近定位点的点要素M1,然后选取左边紧邻M1的点要素M2,然后判断M1M2G的类型,计算G的投影点。图中选取的三角形是HIG.

假设点P1(x1,y1)、P2(x2,y2)、G3(x3,y3)是三个经纬坐标点,其中P1和P2是某道路的起点坐标和终点坐标,G3是车辆GPS定位点,则情形1的求解过程如下:

(1)

x=x3,

y=x1,

(2)

x=(k2x1+k(y3-y1)+x3)/k2+1),

y=(k2y3+y1+x3-x1)/(k2+1).

(3)

由式(1)可以得出ΔP1P2G3三边大小,然后通过简单的判定计算可知ΔP1P2G3的类型。首先,当ΔP1P2G3是锐角三角形时,如果线段P1P2所在直线的斜率k不存在时,G3在线段P1P2的投影点(x,y)由式(2)得出,否则当斜率k存在时,投影点(x,y)由式(3)得出。其次,当ΔP1P2G3不是锐角三角形时,投影点为P1或者P2之一,筛选较为简单,不再赘述。情形2可以分解为情形1进行计算,也不再赘述。

2.3 计算道路的匹配度

本文将道路匹配度简记为rmw(road matching weight),对于获取的候选道路集,需要计算出匹配度最优的道路作为最终的匹配道路。道路匹配度的计算涉及两个关键参数: 1)定位点方向和道路方向的差值,差值的绝对值越小,说明车辆行驶的方向与道路方向越一致,车辆行驶在该道路上的可能性也就越大; 2)定位点到道路的距离d,该距离越小,说明车辆离该道路越近,车辆行驶在该道路上的可能性也就越大。rmw的计算方法为

rmw=|PD-RD|×ratio+d×(1-ratio),

(4)

式中:PD为车辆定位时定位点方向;RD为道路方向;d为定位点到道路的距离;ratio为调节方向和距离占比的参数,在车辆刚刚起步时,方向因素可信度不高,距离因素可信度相对较高,此时本文算法使ratio=0.4,在车辆的行驶状态稳定以后,情况正好相反,此时本文算法使ratio=0.6.

2.4 初次匹配候选道路集的选取

在初次匹配时,如果按照常规的匹配方式,候选道路集为整个路网,逐一计算每条道路的匹配度,然后选取匹配度最优的道路作为匹配道路,此种方式遍历了整个路网,显然效率低下。所以本算法在初次匹配时采用网格划分法进行优化。首先,对地图数据集进行预处理,把整个路网均匀的划分成若干块,并对每块进行编号;其次,对于每个网格所关联的道路进行预先存储。如图4所示,在初次匹配时,先判断车辆定位点所属网格编号,如果属于P网格,则取P网格所关联的所有道路作为候选道路。

图4 网格划分

2.5 匹配过程中候选道路集的选取

在非初次匹配和非信号丢失的情况下,本文算法选取候选道路集时,以当前定位点为圆心,以上一匹配点所在道路的终点和当前定位点两点之间的距离为半径,画捕捉圆,位于该圆内和与该圆相交的道路均选入候选道路集。一般情况下,捕捉圆半径比较大,通常会包含多条道路。

如图5所示,G1、G2为车辆GPS定位点,u、v、w、a为四条道路,其中G1的匹配道路为u,匹配点为P1,而G2是待匹配点。现以G2为圆心,以F和G2两点之间的距离为半径画圆,与该圆相关联的道路均选入候选道路集,图中所示情况下,选入的候选道路有a、v、w。

图5 候选道路集的选取

算法1：匹配过程中候选道路集的选取算法: 输入:当前定位点坐标G(x,y),前一个定位点所匹配的道路R；输出:候选道路集CRS

initCRS (R);

E←queryRoadEndNode(R),r←distacne(G,E);

RS←queryMap(E),appendCRS(RS);

for(i←2toCRS.size())

R1←CRS.get(i);

E1←queryRoadEndNode(R1);

if(distance(G,E1)

RS1←queryMap(E1),appendCRS(RS1);

end if

end for

Output CRS

详细步骤为

1) 初始化时,将前一定位点所匹配的道路R加入候选道路集(第1行)。

2) 读取道路R的终点,保存至变量E,并计算定位点G和点E两点之间的距离,结果赋值给r(第2行)。

3) 从键值对集合中,查询以E为起点的道路,查询结果赋值给RS,并将RS追加到CRS集合中(第3行)。

4) 遍历集合CRS中的每一条道路的终点E1和点G两点之间的距离是否小于r,若是,则把以E1为起点的道路均追加到集合CRS中(第4～10行)。

5) 输出候选道路集CRS(第11行)。

2.6 异常情况下处理

在某些情况下车载GPS定位系统无法搜索到定位信号,导致无法对车辆进行定位,同时也导致无法完成道路匹配。对于此种情况,本文算法提出了一种解决方式,但是该解决方式的前提是人们总是会选择最近的路线前往目的地,这也使得本文提出的解决方式仅仅适用于某些特定情况。

如图6所示,车载定位系统接收到最后一个定位信号G1后,在此后的一段时间内便无法再获取定位信号,直至车辆行驶到道路k上才再次获取到定位信号G2.定位信号G1,本文根据道路连通性将其匹配到道路f上,定位信号G2,由于道路连通性丢失,本文采用网格划分法将其匹配到道路k上,前面已经假设车辆会选择最近的道路行驶,即车辆从道路f上前往道路k的过程中,会选择穿过道路g,因为该路径最短。具体算法实现时,本文借鉴迪杰斯特拉最短路径算法,整个路网可以看出一个有向图,而且道路的起点坐标、终点坐标和道路长度已知,算法实现较为简单,限于篇幅,本文不在赘述。

图6 车辆定位信号丢失

2.7 地图匹配算法流程图

改进的地图匹配算法如图7所示,详细步骤为:地图数据预处理(网格划分,道路连通性建立等)。读取车辆GPS定位点,若没有定位点可读取,说明车辆所有轨迹点已匹配完,匹配结束。

图7 算法匹配流程图

获取定位点,判断是否存在已匹配道路,如果不存在已匹配的道路,即无法根据连通性获取候选道路集,跳到步骤4);如果存在已匹配道路,则根据道路连通性获取候选道路,跳到步骤5)。

1) 根据待匹配点所在网格选取候选道路集。

2) 根据距离因素和方向因素,从候选道路集中选出最优匹配道路。

3) 判断与上一匹配点的时间差是否大于15s(本文采样点的时间间隔为3s, 可根据实际情况调整),若是,则发生了GPS信号丢失,转至步骤3);若不是,转至步骤2)。

4) 启动最短路径算法,推算出车辆经过的道路,然后转至步骤2)。

3 算法验证

为了便于实验,开车在绕校园行驶一圈采集轨迹数据。为模拟信号丢失的情况,删除一部分采集的轨迹点。地图数据集为成都市犀浦镇路网,并进行了预处理,在Pycharm平台上,运用python语言,分别对要素权重法、网格划分法和本文提出的综合算法进行实现,本文综合算法的匹配结果如图8、图9所示。三种算法的对比分析,如表1、表2、表3所示。

图8 轨迹点匹配结果

图9 道路匹配结果

算法种类定位点数匹配准确数匹配准确率/%要素加权法36727875.7网格划分法36726772.5本文综合法36735997.8

表2 三种算法匹配道路准确性统计表

表3 三种算法用时统计表

图8中从知行路到精勤路的部分轨迹点被删除-模拟信号丢失情况。图9为使用matplotlib绘图库工具画出的车辆轨迹点和相应匹配道路示意图。从图中可以看出,整个过程中匹配出的道路是连续的,说明了本文算法在信号丢失的情况下,依然可以正确匹配出车辆经过的道路,很好的解决了在GPS信号丢失情况下,无法实现道路匹配的问题。

从三表中可知,要素加权法,在匹配点和匹配道路上的匹配准确率比网格划分法要高,但是运行时间和单点匹配时间比网格划分法慢,因为要素加权法需要遍历所有路网中的道路,而网格划分法只需遍历网格内的道路。本文综合算法首次匹配遍历网格内的道路,匹配过程中遍历捕捉圆内的道路,准确率和速度都比较较高。

4 结束语

本文提出的基于连通性和最短路径的地图匹配算法,易编写实现,实用性强。首次匹配根据匹配点所在网格,筛选候选道路集,减少了首次匹配需要计算候选道路集的数量,提高了首次匹配速度。匹配过程中采用捕捉圆的方式筛选候选道路集,在速度和准确率上,较优于传统的地图匹配算法。在信号丢失的情况下,采用最短路径算法推算出车辆经过的道路,实现了道路匹配。同时本算法也为道路交通流量研究提供了基础数据的获取方式。

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

[2] 吴世全.基于浮动车数据交通参数提取技术探讨[J].测绘与空间地理信息, 2013, 36(7):133-135.

[3] 朱征宇,崔明,刘琳.一种基于终端的地图匹配方法[J].计算机科学, 2013, 40(5):291-295.

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

[5] 李殿茜,王翌,刘垒.一种地图匹配算法的设计与实现[J].导航定位与授时, 2017, 4(2):31-34.

[6]ORANA,JAILLETP.Apreciseproximity-weightformulationformapmatchingalgorithms[C]//IEE-EWPNC.IEEE, 2013:1-6.

[7] 王志建,王力,汪健.基于拓扑判断的海量数据延时地图匹配算法[J].西南交通大学学报, 2012, 47(5):86-1.

[8]LEVINR,KRAVIE,KANZAY.Concurrentandrobusttopologicalmapmatching[C]//InternationalConferenceonAdvancesinGeographicInformationSystems.ACM, 2012:617-620.

[9] 廖佳,俞荐中,李俊峰.一种利用网格划分及方向加权的地图匹配算法[J].测绘通报, 2017, 30(3):124-127.

[10]GUOB,TANGT,ZHOUD.Aquickmapmatchingalg-orithmfortrainlocatingbasedongridpartit-ion[C]//InternationalConferenceonTransportationEngineering. 2007:3197-3202.

[11]罗跃军,宋向勃,郑莉.一种基于空间语义特征的浮动车轨迹匹配技术 [J].测绘通报, 2015, 1(3):108-110.

[12]YANGYL,YEH,FEISM.Integratedmapmatchingalgorithmbasedonfuzzylogicanddeadreck-oning[C]//InternationalConferenceonControlAutomationandSystems.IEEE, 2010:1139-1142.

[13]唐进君,刘芳.基于路径预测的不确定性推理组合地图匹配算法[J].测绘学报, 2010, 39(5):546-550.