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

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

0 引言

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

大多數(shù)地圖匹配算法可以劃分為4個(gè)類別：幾何算法,拓?fù)渌惴?概率算法和先進(jìn)算法[5]。

幾何算法[6]只考慮道路的形狀而忽視了路段間的相關(guān)性，例如,將一個(gè)GPS數(shù)據(jù)匹配到最近的路段。拓?fù)渌惴ú粌H考慮車輛軌跡之間的相關(guān)性,也考慮了相鄰路段間連通性。為了處理噪聲和低采樣率的軌跡,概率算法[7]在采樣點(diǎn)位置定義置信區(qū)域并考慮不同導(dǎo)航傳感器傳輸數(shù)據(jù)模式的影響。先進(jìn)算法充分結(jié)合拓?fù)浜透怕?，典型算法有卡爾曼濾波器、模糊邏輯、多元假設(shè)和隱馬爾可夫模型[8-9]。

隱馬爾可夫模型是一個(gè)關(guān)于時(shí)間序列的概率模型。它表示隱馬爾可夫鏈可以產(chǎn)生隨機(jī)隱藏狀態(tài)序列,并且每個(gè)隱藏狀態(tài)生成一個(gè)觀測(cè)狀態(tài)。地圖匹配的關(guān)鍵是找到道路網(wǎng)絡(luò)中每個(gè)觀測(cè)點(diǎn)最適合匹配路段，即隱藏狀態(tài)。這樣的序列可以通過維特比算法確定。

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

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

圖1 低頻采樣數(shù)據(jù)的地圖匹配

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

圖2 道路網(wǎng)絡(luò)

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

1 系統(tǒng)綜述

1.1 問題定義

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

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

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

1.2 算法框架

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

圖3 地圖匹配算法框架

2 DHMM地圖匹配算法

2.1 候選路段

由于GPS設(shè)備或外部環(huán)境問題,或缺乏實(shí)際的道路網(wǎng)絡(luò),觀測(cè)點(diǎn)pi在r范圍內(nèi)可能沒有候選路段,對(duì)于這些異常數(shù)據(jù)點(diǎn)，可以直接忽略。

圖4 獲取候選路段

2.2 觀測(cè)概率

定義距離誤差為：

(1)

如圖5所示，每個(gè)觀察點(diǎn)的朝向與候選路段都會(huì)產(chǎn)生夾角θ，考慮到地圖匹配分別是在簡(jiǎn)單的道路網(wǎng)絡(luò)和復(fù)雜的道路網(wǎng)絡(luò)下進(jìn)行的，本文給出了兩個(gè)關(guān)于方向誤差的定義。

圖5 方向誤差

在簡(jiǎn)單路網(wǎng)上，定義方向誤差為：

Eθ=|cosθ|

(2)

在復(fù)雜路網(wǎng)上，定義方向誤差為：

Eθ=cosθ

(3)

其中cosθ表示觀測(cè)點(diǎn)的朝向與路段方向的相似程度，因?yàn)榈缆肪W(wǎng)絡(luò)是一個(gè)有向圖，當(dāng)在簡(jiǎn)單的路網(wǎng)上匹配時(shí)，夾角θ可能會(huì)大于900，方向誤差為負(fù)數(shù)，會(huì)影響到匹配結(jié)果，添加絕對(duì)值可以解決這種問題。而在復(fù)雜的路網(wǎng)中，方向誤差為負(fù)數(shù)，則表示該候選路段不可能是正確匹配的路段。

圖6 計(jì)算cosθ

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

E=Ed·Eθ

(4)

2.3 轉(zhuǎn)移概率

(5)

2.4 匹配軌跡

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

初始時(shí)刻i=1時(shí)：

(6)

當(dāng)i>1時(shí)，由遞推關(guān)系得出：

(7)

(8)

i=T時(shí)刻最大概率匹配路段：

(9)

最優(yōu)匹配軌跡回溯：

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

(10)

得到最優(yōu)匹配軌跡X=x1→x2→…→xT。

DHMM地圖匹配算法是一種全局匹配方法。全局匹配方法指以一整條經(jīng)緯度坐標(biāo)點(diǎn)軌跡作為輸入，為所有可能的輸出匹配序列計(jì)算其對(duì)應(yīng)的整體概率大小，并輸出具有最大概率的序列作為匹配軌跡。然而當(dāng)軌跡數(shù)據(jù)量太大時(shí)，會(huì)影響匹配效率。本文通過使用滑動(dòng)窗口限制匹配數(shù)據(jù)的數(shù)目來有效地解決這個(gè)問題。窗口大小是通過實(shí)驗(yàn)評(píng)估獲取的。

3 實(shí)驗(yàn)準(zhǔn)備

3.1 道路網(wǎng)絡(luò)

如圖7所示，實(shí)驗(yàn)使用福州路網(wǎng)地圖，地圖包含45 124條路段。實(shí)驗(yàn)分別在簡(jiǎn)單的路網(wǎng)和復(fù)雜的路網(wǎng)下進(jìn)行。

圖7 福州道路網(wǎng)絡(luò)

3.2 GPS軌跡數(shù)據(jù)

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

3.3 參數(shù)的選擇

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

3.4 評(píng)估指標(biāo)

在實(shí)驗(yàn)中，使用匹配路段的準(zhǔn)確率(AMR)作為評(píng)估指標(biāo)，定義如下：

(11)

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

4 實(shí)驗(yàn)結(jié)果

4.1 AMR結(jié)果

使用匹配準(zhǔn)確率來評(píng)估這三種方法在不同采樣間隔以及不同路網(wǎng)下的表現(xiàn)，結(jié)果如表1和表2所示。

表1 AMR(簡(jiǎn)單的路網(wǎng))

表2 AMR(復(fù)雜的路網(wǎng))

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

4.2 在不同路網(wǎng)下AMR的趨勢(shì)

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

在復(fù)雜路網(wǎng)中，由于沒有考慮到道路的方向，P-L算法和HMM算法都有著很差的表現(xiàn)。相反，DHMM算法即便在處理低頻的數(shù)據(jù)時(shí)，準(zhǔn)確率也在0.85左右。

4.3 參數(shù)的影響

如圖9所示，當(dāng)參數(shù)λ=0.9時(shí)，兩條點(diǎn)狀線達(dá)到最高點(diǎn)，對(duì)應(yīng)的匹配準(zhǔn)確率分別為0.955 1和0.896 7。如圖10所示，匹配準(zhǔn)確率隨著滑動(dòng)窗口大小的增大而增大。為了提高匹配的效率，在簡(jiǎn)單路網(wǎng)下設(shè)置窗口大小為3，在復(fù)雜路網(wǎng)下設(shè)置窗口大小為6。

圖8 不同路網(wǎng)下AMR數(shù)值的變化趨勢(shì)

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

圖10 所有采樣間隔下滑動(dòng)窗口大小對(duì)AMR的影響

5 總結(jié)

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

參考文獻(xiàn)

[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] 王曉蒙, 池天河, 林暉,等. 一種面向海量浮動(dòng)車數(shù)據(jù)的地圖匹配方法[J]. 地球信息科學(xué)學(xué)報(bào), 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.