一種改進的軌跡地圖匹配算法

段宗濤，霍明生，康 軍

(長安大學信息工程學院，陜西 西安 710064)

地圖匹配是指將GPS點匹配到正確的道路上。在智能交通領域，交通流的預測及車輛的定位等方面都用到地圖匹配，因此一個好的地圖匹配算法是智能交通發展的有力保障。

根據輸入數據所涉及信息的不同，目前的地圖匹配算法[1]包括幾何地圖匹配算法、概率計算地圖匹配算法、拓撲地圖匹配算法和高級地圖匹配算法。幾何地圖匹配算法相對簡單易于實現，但是如果不使用GPS點之間的關系及道路之間的拓撲關系，匹配的準確度就會下降；概率計算地圖匹配算法多涉及公式的推導且不容易理解，匹配效率也很低；拓撲匹配算法對于復雜的城市道路匹配效率不高；當采樣頻率較低且路網較為復雜的情況下，高級地圖匹配算法具有很好的匹配準確率。

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

本文提出一種基于HMM的改進的地圖匹配算法。該地圖匹配算法的設計過程為：首先建立候選路段集和路段拓撲關系集，然后介紹算法中軌跡點的方向概率、觀測概率、狀態轉移概率及綜合概率，最后介紹最短路徑距離算法。

1 算法概述

本文數據采樣間隔為30 s以上，圖1為樣本數據采樣間隔分布圖，可知該樣本數據屬于低頻數據。目前針對低頻采樣數據的主要算法有HMMM、ST-Matching、IVMM等幾種常見的全局算法[4]。本文充分考慮空間特征和幾何拓撲結構，采用基于HMM改進的地圖匹配算法進行驗證。

1.1 路網拓撲構建

本文選擇的路網數據為西安市城區的21 027條路段、16 907個節點，在建立拓撲關系集時分別對路段和節點進行編號。圖2為西安市城區的路段和節點分布圖。

圖1 樣本數據間隔分布

圖2 西安市城區的路段和節點分布

由于每條路段都至少由兩個節點構成，根據其首、末兩個節點的經緯度坐標值計算每條路段的長度，根據計算結果可知，路段長度最小為1 m，最大為9186 m，根據路段節點、路段編號及路段的長度(距離權值)建立路網拓撲集，見表1。

表1 路網拓撲集

1.2 候選路段集構建

以當前軌跡點為圓心，選取半徑r=200 m，可以最大限度地保證正確的候選路段落入該圓域內，同時候選路段集合也不至于過大。對每個軌跡點做一個候選圓域，只要落在該圓域內的路段就記作候選路段，如圖3所示。

圖3 候選路段計算示意圖

由圖3可知，O點表示軌跡點，落在圓域內的每個節點與軌跡點之間的地面距離為d，只要該地面距離小于等于200 m，該節點對應的路段就可以作為該軌跡點的候選路段，建立候選路段集。

這里給出地面距離的計算公式：

已知兩點A(x1,y1)、B(x2,y2)，x1、x2表示A、B兩點的經度，y1、y2表示A、B兩點的緯度，利用弧長計算公式將經、緯度轉化為弧長，計算公式如下

D=dis·π/180

(1)

式中，dis為經、緯度值；D為對應的弧長。

由式(1)可得

(2)

A、B兩點間的地面距離公式為

(3)

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

1.3 投影坐標計算

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

圖4 投影示意圖

OO′的直線方程為

Y-Y1=k(X-X1)

(4)

PPe所在的直線方程為

(5)

P到OO′的垂直距離，即PPe的長度為

(6)

投影坐標(Xe,Ye)為

(7)

(8)

1.4 軌跡夾角θ的計算

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

圖5 軌跡夾角示意圖

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

(9)

2 改進算法分析

2.1 問題描述

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

給定GPS點的集合Z={z1,z2,…,zn}，每個GPS點包含經緯度和時間戳等信息。

每條路段e是一個有向邊，分別具有e.id，長度e.l，起始點e.start，結束點e.end和中間點。

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

2.2 算法描述

假設每一個GPS軌跡點為zt，t=1,2,…，n，軌跡點的每個候選路段為ri，i=1,2,…，n。

本文使用基于HMM的改進的地圖匹配算法，首先加入一個方向概率作為路段在匹配過程中的一個指標，其次將觀測概率以比值關系定義，最后將轉移概率簡化為實際地面距離與路徑距離的一個比值。該算法的描述如下：

基于改進的HMM算法描述

輸入：軌跡點zt、路網數據G(V,E)

輸出：軌跡點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)

方向概率的計算公式為

(10)

觀測概率[8]的計算公式為

(11)

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

轉移概率計算公式如下

(12)

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

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

(13)

利用式(13)計算軌跡點的max(P)，過程如圖6所示。

圖6 匹配過程

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

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

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

基于Dijkstra算法的矩形和橢圓限制搜索區域過程

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

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

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

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 試驗結果和分析

本文試驗所用的數據包含地圖數據[13]及西安市出租車數據，采樣間隔為30 s以上。GPS軌跡數據格式包括車牌號碼、GPS時間、經度、緯度、速度、方向角、浮動車狀態。為了驗證本文算法，首先測試了文獻[2]中Newson等提出的傳統的HMM算法，測試的準確率在86.4%。而采用本文改進的算法進行測試，匹配準確率可以達到94%以上，具有很好的匹配效果。

表2為軌跡點匹配前和匹配后的部分結果對比[14]。

表2 軌跡點坐標匹配前后對比

圖7為部分軌跡點匹配前的示意圖，圖8為部分軌跡點匹配后的示意圖。

圖7 匹配前

圖8 匹配后

使用傳統的HMM地圖匹配算法[2]和改進的HMM地圖匹配算法的準確率比較見表3。

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

4 結 語

本文使用基于HMM的改進的地圖匹配算法，建立路網拓撲集[15]，對軌跡點建立候選路段集，計算軌跡點候選路段的概率，選取最大概率值對應的路段為最佳的匹配路段。利用本文提出的算法可以達到很好的匹配效果，未來可以在計算最短路徑距離和候選路段選取方面進行優化。

參考文獻：

[1] 高文超，李國良，塔娜.軌跡路網匹配算法綜述[J].軟件學報，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] 李殿茜，王翌，劉壘，等.一種地圖匹配算法的設計與實現[J].導航定時，2017，4(2)：31-34.

[6] 陳鋒.一種改進的點到線的地圖匹配算法[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] 姜雪原.基于動態規劃算法的軌跡地圖匹配軟件設計與實現[J].軟件，2015，36(5)：108-112.

[12] 陸峰，盧東梅，崔偉宏.交通網絡限制搜索區域時間最短路徑算法[J].中國圖象圖形學報，1999，4(10)：849-853.

[13] 高強，張鳳荔，王瑞錦，等.軌跡大數據：數據處理關鍵技術研究綜述[J].軟件學報，2017，28(4)：959-992.

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

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