崔松林,馮軍煥

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

0 引 言

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

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

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

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

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

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

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

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

圖1 簡單路網(wǎng)

2 匹配算法設計與實現(xiàn)

2.1 計算道路方向

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

RD=

2.2 計算定位點的投影點

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

情形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由多個點要素組成,在實際路網(wǎng)中,線段EF可能是曲折的,此種情況下,尋找位于道路起點和終點之間的點要素,選取最靠近定位點的點要素M1,然后選取左邊緊鄰M1的點要素M2,然后判斷M1M2G的類型,計算G的投影點。圖中選取的三角形是HIG.

假設點P1(x1,y1)、P2(x2,y2)、G3(x3,y3)是三個經(jīng)緯坐標點,其中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),對于獲取的候選道路集,需要計算出匹配度最優(yōu)的道路作為最終的匹配道路。道路匹配度的計算涉及兩個關鍵參數(shù): 1)定位點方向和道路方向的差值,差值的絕對值越小,說明車輛行駛的方向與道路方向越一致,車輛行駛在該道路上的可能性也就越大; 2)定位點到道路的距離d,該距離越小,說明車輛離該道路越近,車輛行駛在該道路上的可能性也就越大。rmw的計算方法為

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

(4)

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

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

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

圖4 網(wǎng)格劃分

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

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

如圖5所示,G1、G2為車輛GPS定位點,u、v、w、a為四條道路,其中G1的匹配道路為u,匹配點為P1,而G2是待匹配點。現(xiàn)以G2為圓心,以F和G2兩點之間的距離為半徑畫圓,與該圓相關聯(lián)的道路均選入候選道路集,圖中所示情況下,選入的候選道路有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定位系統(tǒng)無法搜索到定位信號,導致無法對車輛進行定位,同時也導致無法完成道路匹配。對于此種情況,本文算法提出了一種解決方式,但是該解決方式的前提是人們總是會選擇最近的路線前往目的地,這也使得本文提出的解決方式僅僅適用于某些特定情況。

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

圖6 車輛定位信號丟失

2.7 地圖匹配算法流程圖

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

圖7 算法匹配流程圖

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

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

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

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

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

3 算法驗證

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

圖8 軌跡點匹配結果

圖9 道路匹配結果

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

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

表3 三種算法用時統(tǒng)計表

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

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

4 結束語

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

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

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

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

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

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

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

[7] 王志建,王力,汪健.基于拓撲判斷的海量數(shù)據(jù)延時地圖匹配算法[J].西南交通大學學報, 2012, 47(5):86-1.

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

[9] 廖佳,俞薦中,李俊峰.一種利用網(wǎng)格劃分及方向加權的地圖匹配算法[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.