基于隱馬爾可夫模型的有向地圖匹配算法研究

陳忠輝，王 彪，馮心欣，鄭海峰

(福州大學 物理和信息工程學院，福建 福州 350116)

0 引言

近年來,GPS(Global Positioning System)手持設備和汽車GPS設備變得越來越受歡迎。研究GPS數據在交通領域已成為一個熱點話題，如路徑推斷[1]、行駛時間預測[2]和個性化導航[3-4]。然而,由于設備的限制和環境噪聲的影響,車輛軌跡數據往往偏離實際的道路，因此地圖匹配成為這些研究過程中不可或缺的一部分。

大多數地圖匹配算法可以劃分為4個類別：幾何算法,拓撲算法,概率算法和先進算法[5]。

幾何算法[6]只考慮道路的形狀而忽視了路段間的相關性，例如,將一個GPS數據匹配到最近的路段。拓撲算法不僅考慮車輛軌跡之間的相關性,也考慮了相鄰路段間連通性。為了處理噪聲和低采樣率的軌跡,概率算法[7]在采樣點位置定義置信區域并考慮不同導航傳感器傳輸數據模式的影響。先進算法充分結合拓撲和概率，典型算法有卡爾曼濾波器、模糊邏輯、多元假設和隱馬爾可夫模型[8-9]。

隱馬爾可夫模型是一個關于時間序列的概率模型。它表示隱馬爾可夫鏈可以產生隨機隱藏狀態序列,并且每個隱藏狀態生成一個觀測狀態。地圖匹配的關鍵是找到道路網絡中每個觀測點最適合匹配路段，即隱藏狀態。這樣的序列可以通過維特比算法確定。

車輛軌跡數據是由一系列GPS點組成的，每一個GPS觀測點包括位置、航向、駕駛速度、時間戳。地圖匹配是指將GPS軌跡數據，經過特定的模型建立和計算，關聯到道路上并最終得到車輛在道路上的具體位置的過程。然而,由于數據存儲和通信傳輸帶寬的限制,車輛軌跡數據采樣間隔從幾十秒到幾分鐘,現有地圖匹配在處理實際的道路網絡時仍面臨以下兩個困難：

(1)傳統地圖匹配算法在處理低頻采樣數據(采樣間隔1～2 min)時效果仍不理想。應用于GPS觀測點高采樣頻率(采樣間隔1 s)的傳統地圖匹配方法并不總是能夠支持低頻的地圖匹配車輛軌跡。圖1所示為有兩個低頻采樣數據的匹配候選軌跡。傳統的地圖匹配方法無法確定真正的軌跡，而實際匹配的是紅色的軌跡。

圖1 低頻采樣數據的地圖匹配

(2)如圖2所示，根據是否考慮道路的雙向交通網絡，可以將道路網絡劃分成簡單和復雜的道路網絡。簡單路網不考慮雙向交通而認為是相同的道路,但復雜的路網則相反。大多數地圖匹配方法是在簡單的路網下進行的。然而, 處理實際的交通問題時經常需要考慮雙向交通，如交通擁堵分析,單向交通擁堵并不意味著雙向都不能通過。

圖2 道路網絡

基于上述觀察結果, 本文提出一個基于隱馬爾可夫模型的有向地圖算法(DHMM)。該算法充分考慮了GPS軌跡與道路的相關性以及相鄰GPS數據點間的幾何特征。結合福州地區真實的出租車軌跡數據，分別將DHMM算法與點到線(P-L)算法和HMM算法進行比較，實驗結果表明DHMM地圖匹配算法在低頻和復雜的路網下匹配準確率更高。

1 系統綜述

1.1 問題定義

定義1(道路網絡) 道路網絡G(V,E)是一個有向圖,V是道路交叉絡口,E是兩個相鄰交叉路口中間之間的路段。

定義2(路段) 路段E={en|n=1,2,…,N},每一條路段都是一個有向邊,它的起點是e.start,結束點是e.end。

定義3(軌跡數據) 軌跡數據P是一輛車一次行駛的數據。定義P=p1→…→pi→…→pT，其中T表示該車采樣點的總數,每個GPS點pi=〈x,y,t,v,dir〉,分別表示經度、緯度、采樣時間、瞬時速度、行駛方向,其中行駛方向有正北、東北、正東、東南正南、西南、正西、西北8個方向，分別用數字0～7表示。

1.2 算法框架

如圖3所示，在DHMM地圖匹配算法中，給定一系列的GPS觀測點，需要先確定一組最大可能的候選路段集，每一個候選路段都是馬爾可夫鏈中具有觀察概率的隱藏狀態。然后，計算每一對相鄰隱藏狀態的轉移概率，利用維特比算法最終找到一條概率最大的匹配軌跡。

圖3 地圖匹配算法框架

2 DHMM地圖匹配算法

2.1 候選路段

由于GPS設備或外部環境問題,或缺乏實際的道路網絡,觀測點pi在r范圍內可能沒有候選路段,對于這些異常數據點，可以直接忽略。

圖4 獲取候選路段

2.2 觀測概率

定義距離誤差為：

(1)

如圖5所示，每個觀察點的朝向與候選路段都會產生夾角θ，考慮到地圖匹配分別是在簡單的道路網絡和復雜的道路網絡下進行的，本文給出了兩個關于方向誤差的定義。

圖5 方向誤差

在簡單路網上，定義方向誤差為：

Eθ=|cosθ|

(2)

在復雜路網上，定義方向誤差為：

Eθ=cosθ

(3)

其中cosθ表示觀測點的朝向與路段方向的相似程度，因為道路網絡是一個有向圖，當在簡單的路網上匹配時，夾角θ可能會大于900，方向誤差為負數，會影響到匹配結果，添加絕對值可以解決這種問題。而在復雜的路網中，方向誤差為負數，則表示該候選路段不可能是正確匹配的路段。

圖6 計算cosθ

聯立公式(1)和(2)或公式(1)和(3)，可以得到觀測概率：

E=Ed·Eθ

(4)

2.3 轉移概率

(5)

2.4 匹配軌跡

在隱馬爾可夫模型中，通過維特比算法可以計算出概率最大的隱藏序列，即最優的匹配軌跡。對于車輛的一次軌跡P=p1→…→pi→…→pT，具體的計算過程如下：

初始時刻i=1時：

(6)

當i>1時，由遞推關系得出：

(7)

(8)

i=T時刻最大概率匹配路段：

(9)

最優匹配軌跡回溯：

xi=ψi(ei)，i=T-1,T-2,…,1

(10)

得到最優匹配軌跡X=x1→x2→…→xT。

DHMM地圖匹配算法是一種全局匹配方法。全局匹配方法指以一整條經緯度坐標點軌跡作為輸入，為所有可能的輸出匹配序列計算其對應的整體概率大小，并輸出具有最大概率的序列作為匹配軌跡。然而當軌跡數據量太大時，會影響匹配效率。本文通過使用滑動窗口限制匹配數據的數目來有效地解決這個問題。窗口大小是通過實驗評估獲取的。

3 實驗準備

3.1 道路網絡

如圖7所示，實驗使用福州路網地圖，地圖包含45 124條路段。實驗分別在簡單的路網和復雜的路網下進行。

圖7 福州道路網絡

3.2 GPS軌跡數據

所有的GPS軌跡數據都來自福州市5 123輛出租車，采集的時間從2015年12月2日到2015年12月10日。數據的采樣間隔是20 s，每一條數據都包含車牌號、經度、緯度、時間戳、速度以及朝向，其中朝向由0～7這8個數字表示，分別代表正北、東北、正東、東南等8個方向。由于該數據是從出租車GPS采集器上直接獲取的，無法得到正確的匹配道路進行實驗比較，為了方便驗證實驗的準確性，本文隨機地選取了其中一天10輛車的一次行駛數據。為了進一步測試DHMM地圖匹配算法在低頻采樣數據上的表現效果，對數據重采樣的采樣間隔為20 s，40 s，60 s，80 s，100 s和120 s。

3.3 參數的選擇

為了減少匹配的時間，限制候選路段的個數為5，獲取候選路段的范圍r=70 m。簡單路網參數的選擇：公式(1)中，設置參數σ=5 m。公式(5)中，設置參數λ=0.9。此外，設置滑動窗口的大小為3。相同地，在復雜路網下，設置參數σ=5 m，λ=0.9，設置滑動窗口的大小為6。

3.4 評估指標

在實驗中，使用匹配路段的準確率(AMR)作為評估指標，定義如下：

(11)

將DHMM方法分別與簡單的點到線(P-L)算法和由NEWSON P[10]提出的HMM算法進行比較。P-L算法只考慮觀察點和道路段之間的空間關系。HMM算法基于隱馬爾可夫模型，是目前最具代表性的地圖匹配算法，該算法的所有參數都來自文獻[10]。

4 實驗結果

4.1 AMR結果

使用匹配準確率來評估這三種方法在不同采樣間隔以及不同路網下的表現，結果如表1和表2所示。

表1 AMR(簡單的路網)

表2 AMR(復雜的路網)

在表1中，DHMM算法平均AMR相較于P-L方法和HMM算法分別提升了3%和5%。在表2中，P-L算法和HMM算法的準確率都僅僅保持在0.7，遠遠低于在簡單路網下的表現。而DHMM算法在120 s的采樣間隔下，準確率仍然達到0.867 2。

4.2 在不同路網下AMR的趨勢

如圖8所示，在簡單路網中，P-L算法與HMM算法在20 s到80 s的采樣間隔下，匹配準確率趨于穩定，但是到了100 s時，準確率急劇下降，這表明這兩種算法無法有效地處理低頻軌跡數據。而DHMM算法在處理低頻采樣間隔軌跡數據時，仍然有著不錯的表現。

在復雜路網中，由于沒有考慮到道路的方向，P-L算法和HMM算法都有著很差的表現。相反，DHMM算法即便在處理低頻的數據時，準確率也在0.85左右。

4.3 參數的影響

如圖9所示，當參數λ=0.9時，兩條點狀線達到最高點，對應的匹配準確率分別為0.955 1和0.896 7。如圖10所示，匹配準確率隨著滑動窗口大小的增大而增大。為了提高匹配的效率，在簡單路網下設置窗口大小為3，在復雜路網下設置窗口大小為6。

圖8 不同路網下AMR數值的變化趨勢

圖9 所有采樣間隔下λ值對AMR的影響

圖10 所有采樣間隔下滑動窗口大小對AMR的影響

5 總結

本文通過分析GPS軌跡與道路的相關性以及相鄰GPS數據點間的幾何特征，提出基于隱馬爾可夫模型的有向地圖匹配。將DHMM算法與P-L算法和HMM算法比較，結果顯示DHMM算法在低頻軌跡數據和復雜的路網下表現更為突出。

參考文獻

[1] LI M, AHMED A,SMOLA A J. Inferring movement trajectories from GPS snippets[C]// Eighth ACM International Conference on Web Search and Data Mining. ACM, 2015:325-334.

[2] WANG Y, ZHENG Y,XUE Y. Travel time estimation of a path using sparse trajectories[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:25-34.

[3] LI Y, SU H,DEMIRYUREK U, et al. PerNav: a route summarization framework for personalized navigation[C]// International Conference on Management of Data. ACM, 2016:2125-2128.

[4] SUN Y, WEI K,QIAO Z, et al. A personalized service for scheduling express delivery using courier trajectories[C]// IEEE International Conference on Web Services. IEEE, 2016:220-227.

[5] ZHENG Y. Trajectory data mining: an overview[J].ACM Transactions on Intelligent Systems & Technology, 2015, 6(3):1-41.

[6] GREENFELD J S. Matching GPS observations to locations on a digital map[C]// Transportation Research Board 81st Annual Meeting, 2002.

[7] JAGADEESH G R,SRIKANTHAN T. Probabilistic map matching of sparse and noisy smartphone location data[C]// IEEE International Conference on Intelligent Transportation Systems. IEEE, 2015:812-817.

[8] KOLLER H,WIDHALM P, DRAGASCHNIG M, et al. Fast Hidden Markov Model map-matching for sparse and noisy trajectories[C]//International Conference on Intelligent Transportation Systems. IEEE, 2015:2557-2561.

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

[10] NEWSON P,KRUMM J. Hidden Markov map matching through noise and sparseness[C]// ACM Sigspatial International Conference on Advances in Geographic Information Systems. ACM, 2009:336-343.