基于道路連通性和最短路徑的綜合地圖匹配算法

崔松林,馮軍煥

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院,四川 成都 611756)

0 引 言

在智能交通領(lǐng)域中,一般通過實(shí)時(shí)收集浮動(dòng)車的運(yùn)行信息,如經(jīng)度、緯度、速度、方向和定位時(shí)間等關(guān)鍵參數(shù),并結(jié)合道路路網(wǎng)信息進(jìn)行動(dòng)態(tài)實(shí)時(shí)的交通大數(shù)據(jù)分析,從而了解道路的交通流量,堵塞狀況,為車輛調(diào)度、車輛實(shí)時(shí)導(dǎo)航、道路規(guī)劃建設(shè)等提供決策依據(jù)[1-2]。

地圖匹配的本質(zhì)是根據(jù)車輛GPS定位點(diǎn)匹配出電子地圖中相對應(yīng)的道路,通過讀取車輛GPS定位信息,匹配出車輛所行駛的道路信息,從而分析道路的交通狀況[3-4]。地圖匹配的一般步驟為:1) 確定候選道路集; 2) 確定匹配道路; 3) 把待匹配點(diǎn)投影到匹配道路上,投影點(diǎn)即為最終匹配點(diǎn)[5]。

現(xiàn)有的地圖匹配算法有要素加權(quán)法[6]、路網(wǎng)拓?fù)浞╗7-8]、網(wǎng)格劃分法[9-10]等。要素加權(quán)法的特點(diǎn)是每次匹配的候選道路集為整個(gè)路網(wǎng)中的道路,依次計(jì)算每條道路的匹配度,匹配度最優(yōu)的道路作為匹配道路,計(jì)算量大、速度慢?；诼肪W(wǎng)拓?fù)潢P(guān)系的匹配算法具有一定的匹配精度,但是首次匹配仍然需要遍歷整個(gè)路網(wǎng),并且在信號丟失的情況下,候選道路集僅僅考慮與上一匹配道路鄰接的道路,不免會(huì)出錯(cuò)。網(wǎng)格劃分法一定程度上減少了候選道路的數(shù)據(jù)量,但是網(wǎng)格的位置及大小無法動(dòng)態(tài)調(diào)整,選取候選道路集時(shí),判斷情況過多,具有一定的局限性。還有一些其他算法[11-13],原理復(fù)雜,難于實(shí)現(xiàn),很難投入實(shí)際應(yīng)用。

本文在充分分析上述算法的基礎(chǔ)上,綜合利用GPS定位點(diǎn)方向、道路方向、GPS定位點(diǎn)和道路的最短距離以及道路的連通性,提出一種基于道路連通性和最短路徑的地圖匹配算法,該算法在匹配過程中采用捕捉圓的方式選取候選道路集,在速度和準(zhǔn)確率上較優(yōu)于傳統(tǒng)算法,而且針對車輛定位信號丟失的情況,提出了一種推測車輛經(jīng)過道路的方法。

1 地圖數(shù)據(jù)預(yù)處理

本文采用成都市范圍內(nèi)的OpenStreetMap免費(fèi)開放地圖數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集,該數(shù)據(jù)集中的道路要素是由一系列點(diǎn)要素組成。本文把每條道路要素存儲為:[道路編號,起點(diǎn)要素,終點(diǎn)要素,點(diǎn)要素序列]。由于存儲的每條道路要素是彼此孤立的,所以還需要建立道路要素之間的連通性。

如圖1所示的道路網(wǎng),其中小寫字母表示道路名稱,大寫字母表示道路的起點(diǎn)或者終點(diǎn)。為建立道路之間的連通性,對路網(wǎng)進(jìn)行預(yù)處理,采用鍵值對的存儲方式將起點(diǎn)相同的道路存儲在一起,存儲格式為:[起點(diǎn)要素:[直接相連的道路要素]]。若要搜索與道路u直接相連的道路,可以讀取預(yù)先存儲的道路u的基本信息,得到道路u的終點(diǎn)B,而以B為起點(diǎn)的道路已經(jīng)預(yù)先存儲到鍵值為B的鍵值對中-[B:[v,w]],從而獲取與道路u直接相連的道路是v和w.

聯(lián)系人: 崔松林 E-mail: 437941580@qq.com

圖1 簡單路網(wǎng)

2 匹配算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 計(jì)算道路方向

由于車載GPS定位系統(tǒng)對車輛行駛方向的定位為順時(shí)針與正北方向的夾角,因此,為方便計(jì)算,道路方向的計(jì)算也以順時(shí)針與正北方向的夾角為準(zhǔn)。若某道路的起點(diǎn)和終點(diǎn)分別為P1(x1,y1)和P2(x2,y2),則該道路方向大小RD的計(jì)算方式如下,其中k表示直線P1P2的斜率:

RD=

2.2 計(jì)算定位點(diǎn)的投影點(diǎn)

投影點(diǎn)的計(jì)算主要考慮兩種情況,1)匹配出的道路要素僅由兩個(gè)點(diǎn)要素標(biāo)示,此種情況,投影點(diǎn)的計(jì)算較為簡單; 2)匹配出的道路要素由兩個(gè)以上點(diǎn)要素標(biāo)示,此時(shí)需要根據(jù)定位點(diǎn)與道路各點(diǎn)要素的距離關(guān)系,將投影點(diǎn)的計(jì)算方式轉(zhuǎn)化為第一種情況。

情形1: 道路要素僅由兩個(gè)點(diǎn)要素標(biāo)示,如圖2所示,其中Gn表示車輛的GPS定位點(diǎn),E、F表

圖2 車輛定位點(diǎn)分布位置

示道路的起點(diǎn)和終點(diǎn)。

① 當(dāng)定位點(diǎn)位于道路上,定位點(diǎn)也即是投影點(diǎn),定位點(diǎn)到道路的最短距離為0,圖中G4點(diǎn)屬于符合此情況。

② 當(dāng)定位點(diǎn)在道路外,此時(shí)判斷由點(diǎn)Gn、E、F三點(diǎn)所確定的三角形類型,如果△EFGn是銳角三角形,則說明由定位點(diǎn)向線段EF引垂線,垂足在線段EF上,即投影點(diǎn)可以落在線段EF上,圖中G2點(diǎn)符合此種情況。如果△EFGn不是銳角三角形,則說明由定位點(diǎn)向線段EF引垂線,垂足在線段EF的延長線上,即投影點(diǎn)不可能落在線段EF上,此種情況下,如果定位點(diǎn)相對靠近起點(diǎn),則選起點(diǎn)作為該定位點(diǎn)的投影點(diǎn),否則選終點(diǎn)作為投影點(diǎn),圖中G1、G3符合此種情況。

情形2: 道路要素由多于兩個(gè)點(diǎn)要素組成,如圖3所示。首先判斷△EFG的類型。

圖3 定位點(diǎn)與道路各點(diǎn)要素的距離

① 若△EFG不是銳角三角形,則說明定位點(diǎn)的投影點(diǎn)無法落在線段EF上,此種情況下,如果點(diǎn)G相對靠近點(diǎn)E,那么選點(diǎn)E作為點(diǎn)G的投影點(diǎn),否則選點(diǎn)F。

② 若△EFG是銳角三角形,則說明投影點(diǎn)可以落在線段EF上,但此時(shí)不能像情形1那樣,直接計(jì)算投影點(diǎn),因?yàn)榫€段EF由多個(gè)點(diǎn)要素組成,在實(shí)際路網(wǎng)中,線段EF可能是曲折的,此種情況下,尋找位于道路起點(diǎn)和終點(diǎn)之間的點(diǎn)要素,選取最靠近定位點(diǎn)的點(diǎn)要素M1,然后選取左邊緊鄰M1的點(diǎn)要素M2,然后判斷M1M2G的類型,計(jì)算G的投影點(diǎn)。圖中選取的三角形是HIG.

假設(shè)點(diǎn)P1(x1,y1)、P2(x2,y2)、G3(x3,y3)是三個(gè)經(jīng)緯坐標(biāo)點(diǎn),其中P1和P2是某道路的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo),G3是車輛GPS定位點(diǎn),則情形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三邊大小,然后通過簡單的判定計(jì)算可知ΔP1P2G3的類型。首先,當(dāng)ΔP1P2G3是銳角三角形時(shí),如果線段P1P2所在直線的斜率k不存在時(shí),G3在線段P1P2的投影點(diǎn)(x,y)由式(2)得出,否則當(dāng)斜率k存在時(shí),投影點(diǎn)(x,y)由式(3)得出。其次,當(dāng)ΔP1P2G3不是銳角三角形時(shí),投影點(diǎn)為P1或者P2之一,篩選較為簡單,不再贅述。情形2可以分解為情形1進(jìn)行計(jì)算,也不再贅述。

2.3 計(jì)算道路的匹配度

本文將道路匹配度簡記為rmw(road matching weight),對于獲取的候選道路集,需要計(jì)算出匹配度最優(yōu)的道路作為最終的匹配道路。道路匹配度的計(jì)算涉及兩個(gè)關(guān)鍵參數(shù): 1)定位點(diǎn)方向和道路方向的差值,差值的絕對值越小,說明車輛行駛的方向與道路方向越一致,車輛行駛在該道路上的可能性也就越大; 2)定位點(diǎn)到道路的距離d,該距離越小,說明車輛離該道路越近,車輛行駛在該道路上的可能性也就越大。rmw的計(jì)算方法為

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

(4)

式中:PD為車輛定位時(shí)定位點(diǎn)方向;RD為道路方向;d為定位點(diǎn)到道路的距離;ratio為調(diào)節(jié)方向和距離占比的參數(shù),在車輛剛剛起步時(shí),方向因素可信度不高,距離因素可信度相對較高,此時(shí)本文算法使ratio=0.4,在車輛的行駛狀態(tài)穩(wěn)定以后,情況正好相反,此時(shí)本文算法使ratio=0.6.

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

在初次匹配時(shí),如果按照常規(guī)的匹配方式,候選道路集為整個(gè)路網(wǎng),逐一計(jì)算每條道路的匹配度,然后選取匹配度最優(yōu)的道路作為匹配道路,此種方式遍歷了整個(gè)路網(wǎng),顯然效率低下。所以本算法在初次匹配時(shí)采用網(wǎng)格劃分法進(jìn)行優(yōu)化。首先,對地圖數(shù)據(jù)集進(jìn)行預(yù)處理,把整個(gè)路網(wǎng)均勻的劃分成若干塊,并對每塊進(jìn)行編號;其次,對于每個(gè)網(wǎng)格所關(guān)聯(lián)的道路進(jìn)行預(yù)先存儲。如圖4所示,在初次匹配時(shí),先判斷車輛定位點(diǎn)所屬網(wǎng)格編號,如果屬于P網(wǎng)格,則取P網(wǎng)格所關(guān)聯(lián)的所有道路作為候選道路。

圖4 網(wǎng)格劃分

2.5 匹配過程中候選道路集的選取

在非初次匹配和非信號丟失的情況下,本文算法選取候選道路集時(shí),以當(dāng)前定位點(diǎn)為圓心,以上一匹配點(diǎn)所在道路的終點(diǎn)和當(dāng)前定位點(diǎn)兩點(diǎn)之間的距離為半徑,畫捕捉圓,位于該圓內(nèi)和與該圓相交的道路均選入候選道路集。一般情況下,捕捉圓半徑比較大,通常會(huì)包含多條道路。

如圖5所示,G1、G2為車輛GPS定位點(diǎn),u、v、w、a為四條道路,其中G1的匹配道路為u,匹配點(diǎn)為P1,而G2是待匹配點(diǎn)。現(xiàn)以G2為圓心,以F和G2兩點(diǎn)之間的距離為半徑畫圓,與該圓相關(guān)聯(lián)的道路均選入候選道路集,圖中所示情況下,選入的候選道路有a、v、w。

圖5 候選道路集的選取

算法1：匹配過程中候選道路集的選取算法: 輸入:當(dāng)前定位點(diǎn)坐標(biāo)G(x,y),前一個(gè)定位點(diǎn)所匹配的道路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

詳細(xì)步驟為

1) 初始化時(shí),將前一定位點(diǎn)所匹配的道路R加入候選道路集(第1行)。

2) 讀取道路R的終點(diǎn),保存至變量E,并計(jì)算定位點(diǎn)G和點(diǎn)E兩點(diǎn)之間的距離,結(jié)果賦值給r(第2行)。

3) 從鍵值對集合中,查詢以E為起點(diǎn)的道路,查詢結(jié)果賦值給RS,并將RS追加到CRS集合中(第3行)。

4) 遍歷集合CRS中的每一條道路的終點(diǎn)E1和點(diǎn)G兩點(diǎn)之間的距離是否小于r,若是,則把以E1為起點(diǎn)的道路均追加到集合CRS中(第4～10行)。

5) 輸出候選道路集CRS(第11行)。

2.6 異常情況下處理

在某些情況下車載GPS定位系統(tǒng)無法搜索到定位信號,導(dǎo)致無法對車輛進(jìn)行定位,同時(shí)也導(dǎo)致無法完成道路匹配。對于此種情況,本文算法提出了一種解決方式,但是該解決方式的前提是人們總是會(huì)選擇最近的路線前往目的地,這也使得本文提出的解決方式僅僅適用于某些特定情況。

如圖6所示,車載定位系統(tǒng)接收到最后一個(gè)定位信號G1后,在此后的一段時(shí)間內(nèi)便無法再獲取定位信號,直至車輛行駛到道路k上才再次獲取到定位信號G2.定位信號G1,本文根據(jù)道路連通性將其匹配到道路f上,定位信號G2,由于道路連通性丟失,本文采用網(wǎng)格劃分法將其匹配到道路k上,前面已經(jīng)假設(shè)車輛會(huì)選擇最近的道路行駛,即車輛從道路f上前往道路k的過程中,會(huì)選擇穿過道路g,因?yàn)樵撀窂阶疃?。具體算法實(shí)現(xiàn)時(shí),本文借鑒迪杰斯特拉最短路徑算法,整個(gè)路網(wǎng)可以看出一個(gè)有向圖,而且道路的起點(diǎn)坐標(biāo)、終點(diǎn)坐標(biāo)和道路長度已知,算法實(shí)現(xiàn)較為簡單,限于篇幅,本文不在贅述。

圖6 車輛定位信號丟失

2.7 地圖匹配算法流程圖

改進(jìn)的地圖匹配算法如圖7所示,詳細(xì)步驟為:地圖數(shù)據(jù)預(yù)處理(網(wǎng)格劃分,道路連通性建立等)。讀取車輛GPS定位點(diǎn),若沒有定位點(diǎn)可讀取,說明車輛所有軌跡點(diǎn)已匹配完,匹配結(jié)束。

圖7 算法匹配流程圖

獲取定位點(diǎn),判斷是否存在已匹配道路,如果不存在已匹配的道路,即無法根據(jù)連通性獲取候選道路集,跳到步驟4);如果存在已匹配道路,則根據(jù)道路連通性獲取候選道路,跳到步驟5)。

1) 根據(jù)待匹配點(diǎn)所在網(wǎng)格選取候選道路集。

2) 根據(jù)距離因素和方向因素,從候選道路集中選出最優(yōu)匹配道路。

3) 判斷與上一匹配點(diǎn)的時(shí)間差是否大于15s(本文采樣點(diǎn)的時(shí)間間隔為3s, 可根據(jù)實(shí)際情況調(diào)整),若是,則發(fā)生了GPS信號丟失,轉(zhuǎn)至步驟3);若不是,轉(zhuǎn)至步驟2)。

4) 啟動(dòng)最短路徑算法,推算出車輛經(jīng)過的道路,然后轉(zhuǎn)至步驟2)。

3 算法驗(yàn)證

為了便于實(shí)驗(yàn),開車在繞校園行駛一圈采集軌跡數(shù)據(jù)。為模擬信號丟失的情況,刪除一部分采集的軌跡點(diǎn)。地圖數(shù)據(jù)集為成都市犀浦鎮(zhèn)路網(wǎng),并進(jìn)行了預(yù)處理,在Pycharm平臺上,運(yùn)用python語言,分別對要素權(quán)重法、網(wǎng)格劃分法和本文提出的綜合算法進(jìn)行實(shí)現(xiàn),本文綜合算法的匹配結(jié)果如圖8、圖9所示。三種算法的對比分析,如表1、表2、表3所示。

圖8 軌跡點(diǎn)匹配結(jié)果

圖9 道路匹配結(jié)果

算法種類定位點(diǎn)數(shù)匹配準(zhǔn)確數(shù)匹配準(zhǔn)確率/%要素加權(quán)法36727875.7網(wǎng)格劃分法36726772.5本文綜合法36735997.8

表2 三種算法匹配道路準(zhǔn)確性統(tǒng)計(jì)表

表3 三種算法用時(shí)統(tǒng)計(jì)表

圖8中從知行路到精勤路的部分軌跡點(diǎn)被刪除-模擬信號丟失情況。圖9為使用matplotlib繪圖庫工具畫出的車輛軌跡點(diǎn)和相應(yīng)匹配道路示意圖。從圖中可以看出,整個(gè)過程中匹配出的道路是連續(xù)的,說明了本文算法在信號丟失的情況下,依然可以正確匹配出車輛經(jīng)過的道路,很好的解決了在GPS信號丟失情況下,無法實(shí)現(xiàn)道路匹配的問題。

從三表中可知,要素加權(quán)法,在匹配點(diǎn)和匹配道路上的匹配準(zhǔn)確率比網(wǎng)格劃分法要高,但是運(yùn)行時(shí)間和單點(diǎn)匹配時(shí)間比網(wǎng)格劃分法慢,因?yàn)橐丶訖?quán)法需要遍歷所有路網(wǎng)中的道路,而網(wǎng)格劃分法只需遍歷網(wǎng)格內(nèi)的道路。本文綜合算法首次匹配遍歷網(wǎng)格內(nèi)的道路,匹配過程中遍歷捕捉圓內(nèi)的道路,準(zhǔn)確率和速度都比較較高。

4 結(jié)束語

本文提出的基于連通性和最短路徑的地圖匹配算法,易編寫實(shí)現(xiàn),實(shí)用性強(qiáng)。首次匹配根據(jù)匹配點(diǎn)所在網(wǎng)格,篩選候選道路集,減少了首次匹配需要計(jì)算候選道路集的數(shù)量,提高了首次匹配速度。匹配過程中采用捕捉圓的方式篩選候選道路集,在速度和準(zhǔn)確率上,較優(yōu)于傳統(tǒng)的地圖匹配算法。在信號丟失的情況下,采用最短路徑算法推算出車輛經(jīng)過的道路,實(shí)現(xiàn)了道路匹配。同時(shí)本算法也為道路交通流量研究提供了基礎(chǔ)數(shù)據(jù)的獲取方式。

[1] 周成,袁家政,劉宏哲.智能交通領(lǐng)域中地圖匹配算法研究[J].計(jì)算機(jī)科學(xué), 2015, 42(10):1-6.

[2] 吳世全.基于浮動(dòng)車數(shù)據(jù)交通參數(shù)提取技術(shù)探討[J].測繪與空間地理信息, 2013, 36(7):133-135.

[3] 朱征宇,崔明,劉琳.一種基于終端的地圖匹配方法[J].計(jì)算機(jī)科學(xué), 2013, 40(5):291-295.

[4] 李清泉,黃練.基于軌跡數(shù)據(jù)的地圖匹配算法[J].測繪學(xué)報(bào), 2010, 39(2):207-212.

[5] 李殿茜,王翌,劉壘.一種地圖匹配算法的設(shè)計(jì)與實(shí)現(xiàn)[J].導(dǎo)航定位與授時(shí), 2017, 4(2):31-34.

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

[7] 王志建,王力,汪健.基于拓?fù)渑袛嗟暮Ａ繑?shù)據(jù)延時(shí)地圖匹配算法[J].西南交通大學(xué)學(xué)報(bào), 2012, 47(5):86-1.

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

[9] 廖佳,俞薦中,李俊峰.一種利用網(wǎng)格劃分及方向加權(quán)的地圖匹配算法[J].測繪通報(bào), 2017, 30(3):124-127.

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

[11]羅躍軍,宋向勃,鄭莉.一種基于空間語義特征的浮動(dòng)車軌跡匹配技術(shù) [J].測繪通報(bào), 2015, 1(3):108-110.

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

[13]唐進(jìn)君,劉芳.基于路徑預(yù)測的不確定性推理組合地圖匹配算法[J].測繪學(xué)報(bào), 2010, 39(5):546-550.