一種改進(jìn)的軌跡地圖匹配算法

段宗濤，霍明生，康 軍

(長(zhǎng)安大學(xué)信息工程學(xué)院，陜西 西安 710064)

地圖匹配是指將GPS點(diǎn)匹配到正確的道路上。在智能交通領(lǐng)域，交通流的預(yù)測(cè)及車輛的定位等方面都用到地圖匹配，因此一個(gè)好的地圖匹配算法是智能交通發(fā)展的有力保障。

根據(jù)輸入數(shù)據(jù)所涉及信息的不同，目前的地圖匹配算法[1]包括幾何地圖匹配算法、概率計(jì)算地圖匹配算法、拓?fù)涞貓D匹配算法和高級(jí)地圖匹配算法。幾何地圖匹配算法相對(duì)簡(jiǎn)單易于實(shí)現(xiàn)，但是如果不使用GPS點(diǎn)之間的關(guān)系及道路之間的拓?fù)潢P(guān)系，匹配的準(zhǔn)確度就會(huì)下降；概率計(jì)算地圖匹配算法多涉及公式的推導(dǎo)且不容易理解，匹配效率也很低；拓?fù)淦ヅ渌惴▽?duì)于復(fù)雜的城市道路匹配效率不高；當(dāng)采樣頻率較低且路網(wǎng)較為復(fù)雜的情況下，高級(jí)地圖匹配算法具有很好的匹配準(zhǔn)確率。

文獻(xiàn)[2]中Newson等在2009年第一次提出了HMM(hidden Markov model)算法，雖然該算法對(duì)于時(shí)間間隔較大的數(shù)據(jù)具有很大的改善，但是沒(méi)有考慮方向信息只考慮了距離信息。文獻(xiàn)[3]提出了一種動(dòng)態(tài)編程方法來(lái)識(shí)別每條路段，但試驗(yàn)結(jié)果表明該算法對(duì)于時(shí)間間隔較大的低頻數(shù)據(jù)正確率較低。

本文提出一種基于HMM的改進(jìn)的地圖匹配算法。該地圖匹配算法的設(shè)計(jì)過(guò)程為：首先建立候選路段集和路段拓?fù)潢P(guān)系集，然后介紹算法中軌跡點(diǎn)的方向概率、觀測(cè)概率、狀態(tài)轉(zhuǎn)移概率及綜合概率，最后介紹最短路徑距離算法。

1 算法概述

本文數(shù)據(jù)采樣間隔為30 s以上，圖1為樣本數(shù)據(jù)采樣間隔分布圖，可知該樣本數(shù)據(jù)屬于低頻數(shù)據(jù)。目前針對(duì)低頻采樣數(shù)據(jù)的主要算法有HMMM、ST-Matching、IVMM等幾種常見的全局算法[4]。本文充分考慮空間特征和幾何拓?fù)浣Y(jié)構(gòu)，采用基于HMM改進(jìn)的地圖匹配算法進(jìn)行驗(yàn)證。

1.1 路網(wǎng)拓?fù)錁?gòu)建

本文選擇的路網(wǎng)數(shù)據(jù)為西安市城區(qū)的21 027條路段、16 907個(gè)節(jié)點(diǎn)，在建立拓?fù)潢P(guān)系集時(shí)分別對(duì)路段和節(jié)點(diǎn)進(jìn)行編號(hào)。圖2為西安市城區(qū)的路段和節(jié)點(diǎn)分布圖。

圖1 樣本數(shù)據(jù)間隔分布

圖2 西安市城區(qū)的路段和節(jié)點(diǎn)分布

由于每條路段都至少由兩個(gè)節(jié)點(diǎn)構(gòu)成，根據(jù)其首、末兩個(gè)節(jié)點(diǎn)的經(jīng)緯度坐標(biāo)值計(jì)算每條路段的長(zhǎng)度，根據(jù)計(jì)算結(jié)果可知，路段長(zhǎng)度最小為1 m，最大為9186 m，根據(jù)路段節(jié)點(diǎn)、路段編號(hào)及路段的長(zhǎng)度(距離權(quán)值)建立路網(wǎng)拓?fù)浼?，見?。

表1 路網(wǎng)拓?fù)浼?/p>

1.2 候選路段集構(gòu)建

以當(dāng)前軌跡點(diǎn)為圓心，選取半徑r=200 m，可以最大限度地保證正確的候選路段落入該圓域內(nèi)，同時(shí)候選路段集合也不至于過(guò)大。對(duì)每個(gè)軌跡點(diǎn)做一個(gè)候選圓域，只要落在該圓域內(nèi)的路段就記作候選路段，如圖3所示。

圖3 候選路段計(jì)算示意圖

由圖3可知，O點(diǎn)表示軌跡點(diǎn)，落在圓域內(nèi)的每個(gè)節(jié)點(diǎn)與軌跡點(diǎn)之間的地面距離為d，只要該地面距離小于等于200 m，該節(jié)點(diǎn)對(duì)應(yīng)的路段就可以作為該軌跡點(diǎn)的候選路段，建立候選路段集。

這里給出地面距離的計(jì)算公式：

已知兩點(diǎn)A(x1,y1)、B(x2,y2)，x1、x2表示A、B兩點(diǎn)的經(jīng)度，y1、y2表示A、B兩點(diǎn)的緯度，利用弧長(zhǎng)計(jì)算公式將經(jīng)、緯度轉(zhuǎn)化為弧長(zhǎng)，計(jì)算公式如下

D=dis·π/180

(1)

式中，dis為經(jīng)、緯度值；D為對(duì)應(yīng)的弧長(zhǎng)。

由式(1)可得

(2)

A、B兩點(diǎn)間的地面距離公式為

(3)

式中，a=Y2-Y1；b=X2-X1；R為地球半徑，取R=6 378 137 m。

1.3 投影坐標(biāo)計(jì)算

如圖4所示，P(X0,Y0)為軌跡點(diǎn)，O(X2,Y2)、O′(X1,Y1)為候選路段的首、末節(jié)點(diǎn)，Pe(Xe,Ye)為投影坐標(biāo)，則投影點(diǎn)坐標(biāo)[5]計(jì)算公式如下：

圖4 投影示意圖

OO′的直線方程為

Y-Y1=k(X-X1)

(4)

PPe所在的直線方程為

(5)

P到OO′的垂直距離，即PPe的長(zhǎng)度為

(6)

投影坐標(biāo)(Xe,Ye)為

(7)

(8)

1.4 軌跡夾角θ的計(jì)算

如圖5所示，軌跡點(diǎn)坐標(biāo)為(x,y)，將軌跡點(diǎn)行駛方向與正北方向順時(shí)針旋轉(zhuǎn)的夾角記為φ，Si為軌跡點(diǎn)的候選路段[6]，將Si與正北方向的順時(shí)針旋轉(zhuǎn)夾角記為θ。

圖5 軌跡夾角示意圖

A(Xa,Ya)、B(Xb,Yb)為候選路段Si上的首、末節(jié)點(diǎn)，候選路段Si的行駛夾角θ的計(jì)算公式為

(9)

2 改進(jìn)算法分析

2.1 問(wèn)題描述

軌跡匹配問(wèn)題是給定未加工的GPS軌跡Z和路網(wǎng)G(V,E)，從G中尋找路徑可以從起始點(diǎn)達(dá)到指定點(diǎn)的過(guò)程。

給定GPS點(diǎn)的集合Z={z1,z2,…,zn}，每個(gè)GPS點(diǎn)包含經(jīng)緯度和時(shí)間戳等信息。

每條路段e是一個(gè)有向邊，分別具有e.id，長(zhǎng)度e.l，起始點(diǎn)e.start，結(jié)束點(diǎn)e.end和中間點(diǎn)。

路網(wǎng)是一個(gè)有向圖G(V,E)，V是頂點(diǎn)集合，代表路口或道路中的轉(zhuǎn)折點(diǎn)，E是一系列有向邊，代表路網(wǎng)中的路段。

2.2 算法描述

假設(shè)每一個(gè)GPS軌跡點(diǎn)為zt，t=1,2,…，n，軌跡點(diǎn)的每個(gè)候選路段為ri，i=1,2,…，n。

本文使用基于HMM的改進(jìn)的地圖匹配算法，首先加入一個(gè)方向概率作為路段在匹配過(guò)程中的一個(gè)指標(biāo)，其次將觀測(cè)概率以比值關(guān)系定義，最后將轉(zhuǎn)移概率簡(jiǎn)化為實(shí)際地面距離與路徑距離的一個(gè)比值。該算法的描述如下：

基于改進(jìn)的HMM算法描述

輸入：軌跡點(diǎn)zt、路網(wǎng)數(shù)據(jù)G(V,E)

輸出：軌跡點(diǎn)zt的綜合概率的max(P)

1. set the candidate radiusr=200 m

2. calculatezt→node of each road less than 200 m

3. get the candidate roadri

4. calculatext,i,θ,φ,ω,dt,Nω,p(zt|ri,p(xt,i→xt+1,j)

5. getPof each candidate road

6. get max(P) of eachzt

7. return max(P)

方向概率的計(jì)算公式為

(10)

觀測(cè)概率[8]的計(jì)算公式為

(11)

由式(11)可知，GPS軌跡點(diǎn)與候選路段的地面距離越近，該路段的觀測(cè)概率就會(huì)越大；反之，距離越遠(yuǎn)，觀測(cè)概率就越小。因此，距離越小的候選路段最有可能是其真正的候選路段。

轉(zhuǎn)移概率計(jì)算公式如下

(12)

根據(jù)式(10)、式(11)、式(12)定義綜合概率為

P=Nωp(dt)p(xt,i→xt+1,j)

(13)

利用式(13)計(jì)算軌跡點(diǎn)的max(P)，過(guò)程如圖6所示。

圖6 匹配過(guò)程

利用本文提出的改進(jìn)算法并行計(jì)算軌跡點(diǎn)的最大P，最后對(duì)整個(gè)軌跡點(diǎn)進(jìn)行匯總，得到一個(gè)計(jì)算值最大的匹配點(diǎn)的序列形成匹配路徑。

2.3 最短路徑算法[10]描述

在式(12)中求解相鄰兩個(gè)軌跡點(diǎn)xt,i和xt+1,j(i=1,2，…，m,j=1,2，…，n)的最短路徑route距離[11]時(shí)，采用基于廣度優(yōu)先搜索和優(yōu)先隊(duì)列的Dijkstra算法，由于在每次求解時(shí)都會(huì)進(jìn)行m·n次運(yùn)算才可得到route值，為了減少時(shí)間復(fù)雜度，采用矩形和橢圓限制搜索區(qū)域[12]進(jìn)行改進(jìn)。

基于Dijkstra算法的矩形和橢圓限制搜索區(qū)域過(guò)程

輸入：xt,i→xt+1,j，矩形搜索區(qū)域G(V,E)

輸出：xt,i→xt+1,j的最短路徑距離d[v]

1. fuction Dijkstra(G,w,s)∥w表示路徑長(zhǎng)度

2. for each vertex inV

3.d[v]=infinity

4. previous[v]=undefined

5.d[s]=0

6.Sis empty set

7.Qis a set of all vertexs

8. whileQis not an empty set

9.u=Get min(Q)

10.S.add(u)

11. for each edge outgoing from u as (u,v)

12. ifd[v]>d[u]+w(u,v)

13.d[v]=d[u]+w(u,v)

14. previous[v]=u

15. end if

16. returnd[v]

3 試驗(yàn)結(jié)果和分析

本文試驗(yàn)所用的數(shù)據(jù)包含地圖數(shù)據(jù)[13]及西安市出租車數(shù)據(jù)，采樣間隔為30 s以上。GPS軌跡數(shù)據(jù)格式包括車牌號(hào)碼、GPS時(shí)間、經(jīng)度、緯度、速度、方向角、浮動(dòng)車狀態(tài)。為了驗(yàn)證本文算法，首先測(cè)試了文獻(xiàn)[2]中Newson等提出的傳統(tǒng)的HMM算法，測(cè)試的準(zhǔn)確率在86.4%。而采用本文改進(jìn)的算法進(jìn)行測(cè)試，匹配準(zhǔn)確率可以達(dá)到94%以上，具有很好的匹配效果。

表2為軌跡點(diǎn)匹配前和匹配后的部分結(jié)果對(duì)比[14]。

表2 軌跡點(diǎn)坐標(biāo)匹配前后對(duì)比

圖7為部分軌跡點(diǎn)匹配前的示意圖，圖8為部分軌跡點(diǎn)匹配后的示意圖。

圖7 匹配前

圖8 匹配后

使用傳統(tǒng)的HMM地圖匹配算法[2]和改進(jìn)的HMM地圖匹配算法的準(zhǔn)確率比較見表3。

表3 算法準(zhǔn)確率比較 (%)

4 結(jié) 語(yǔ)

本文使用基于HMM的改進(jìn)的地圖匹配算法，建立路網(wǎng)拓?fù)浼痆15]，對(duì)軌跡點(diǎn)建立候選路段集，計(jì)算軌跡點(diǎn)候選路段的概率，選取最大概率值對(duì)應(yīng)的路段為最佳的匹配路段。利用本文提出的算法可以達(dá)到很好的匹配效果，未來(lái)可以在計(jì)算最短路徑距離和候選路段選取方面進(jìn)行優(yōu)化。

參考文獻(xiàn)：

[1] 高文超，李國(guó)良，塔娜.軌跡路網(wǎng)匹配算法綜述[J].軟件學(xué)報(bào)，2018,29(2)：225-250.

[2] NEWSON P，KRUMM J.Hidden Markov Map Matching Through Noise and Sparseness[J].ACM GIS，2009，9(11)：336-343.

[3] CHEN B Y，YUAN H，LI Q，et al.Map Matching Algorithm for Large-scale Low-frequency Floating Car Data[J].International Journal of Geographical Information Science，2014，28(1)：22-38.

[4] YUAN J，ZHENG Y，ZHANG C，et al.An Interactive-voting Based Map Matching Algorithm[J].Mobile Data Management，2010，11(10)：43-52.

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

[6] 陳鋒.一種改進(jìn)的點(diǎn)到線的地圖匹配算法[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2004，4(4)：74-76.

[7] KRUMM J.A Markov Model for Driver Turn Prediction[J].Society of Automotive Engineers，2008，22(1)：1-25.

[8] ZELENKOV A V.Calculation of Parameters of Hidden Markov Models Used in the Navigation Systems of Surface Transportation for Map Matching:A Review[J].Automatic Control and Computer Sciences，2010，44(6)：309-323.

[9] SZWED P，PEKALA K.An Incremental Mapmatching Algorithm Based on HMM [J].International Conference on Artifical Intelligence and Soft Computing，2014，13(2)：579-590.

[10] QUDDUS M，WSHINGTON S.Shortest Path and Vehicle Trajectory Aided Map-matching for Low Frequency GPS Data[J].Transportation Research Part C，2015，2(17)：328-339.

[11] 姜雪原.基于動(dòng)態(tài)規(guī)劃算法的軌跡地圖匹配軟件設(shè)計(jì)與實(shí)現(xiàn)[J].軟件，2015，36(5)：108-112.

[12] 陸峰，盧東梅，崔偉宏.交通網(wǎng)絡(luò)限制搜索區(qū)域時(shí)間最短路徑算法[J].中國(guó)圖象圖形學(xué)報(bào)，1999，4(10)：849-853.

[13] 高強(qiáng)，張鳳荔，王瑞錦，等.軌跡大數(shù)據(jù)：數(shù)據(jù)處理關(guān)鍵技術(shù)研究綜述[J].軟件學(xué)報(bào)，2017，28(4)：959-992.

[14] 吳剛，邱煜晶，王國(guó)仁，等.基于隱馬爾科夫模型和遺傳算法的地圖匹配算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2017，38(4)：472-475.

[15] 王曉蒙，池天河，林暉，等.一種面向海量浮動(dòng)車數(shù)據(jù)的地圖匹配算法方法[J].地球信息科學(xué)，2015，17(10)：1143-1150.