基于改進的HMM地圖匹配算法

張浩 劉大明

摘 ?要：針對路網(wǎng)拓撲結(jié)構(gòu)的復雜和軌跡信息利用不充分問題，文章提出了一種改進的HMM，該方法考慮了真實路網(wǎng)的拓撲信息，軌跡的位置、方向和速度信息。在計算發(fā)射概率時用二維正態(tài)分布將軌跡的位置信息和方向信息融合，轉(zhuǎn)移概率計算時考慮到候選道路的限制速度和距離的非線性關(guān)聯(lián)，并在實驗中得到驗證，改進后的匹配成功率比傳統(tǒng)HMM提高了7%。

關(guān)鍵詞：拓撲結(jié)構(gòu);HMM;觀測概率;轉(zhuǎn)移概率

中圖分類號：TP301.6 ? ? ?文獻標識碼：A 文章編號：2096-4706（2020）21-0084-04

The Map Matching Algorithm Based on Improved HMM

ZHANG Hao，LIU Daming

（School of Computer Science and Technology，Shanghai University of Electric Power，Shanghai ?200090，China）

Abstract：In view of the complexity of road network topology and inadequate utilization of track information，an improved HMM method is proposed in this paper，which considers the topology information，track position，direction and velocity information of the real road network. In the calculation of the emission probability，the location information and direction information of the trajectory are fused together with the two-dimensional normal distribution. In the calculation of the transition probability，the nonlinear relation between the limit speed and distance of the candidate road is taken into account，which is verified in the experiment. The improved matching success rate is 7% higher than the traditional HMM.

Keywords：topology;HMM;observation probability;transition probability

0 ?引 ?言

隨著無線通信技術(shù)和定位技術(shù)的發(fā)展，軌跡數(shù)據(jù)可用于空間數(shù)據(jù)挖掘、智能交通[1-3]、城市規(guī)劃[4，5]等領(lǐng)域。近年來學者在地圖匹配算法或技術(shù)方面做了大量的研究。Quddus等人將其歸納為四種類型：基于幾何的算法、基于拓撲的算法、基于概率的算法和基于高級數(shù)學理論的算法[6]?；趲缀蔚乃惴ㄖ饕紤]路網(wǎng)和軌跡的幾何特征，如點對點[7]、點對線[8]和線對線算法[9]，但是基于幾何的算法通常會忽略拓撲信息，這可能導致復雜場景的錯誤匹配;基于拓撲的算法則側(cè)重于軌跡和路網(wǎng)之間的拓撲關(guān)系[10]，包括拓撲加權(quán)算法[11]、地圖匹配算法[12]和加權(quán)地圖匹配算法[13]，這類算法將路網(wǎng)處理為圖結(jié)構(gòu)，從而將拓撲信息納入其中，適用于高采樣率的地圖匹配算法;基于概率的算法將GPS位置視為隨機變量，軌跡視為隨機過程。HMM是這些算法中常用的算法?；贖MM的方法非常適合道路匹配[14]，HMM可以同時考慮幾何和地形信息，卻不需要訓練數(shù)據(jù)，但是該算法對最短路徑進行計算使得計算開銷很大。位置和方向信息不符合嚴格的獨立分布，因而HMM的發(fā)射概率計算公式并不適用于地圖匹配。模糊邏輯[15]、神經(jīng)網(wǎng)絡(luò)[16]、卡爾曼濾波[17，18]、粒子濾波和Dempster-Shafer[19]理論等先進的數(shù)學和人工智能理論在地圖匹配領(lǐng)域廣泛應(yīng)用，但是此類算法通常需要大量的訓練數(shù)據(jù)集來執(zhí)行逐點匹配，使得它們的實際應(yīng)用非常困難。

基于此，作者提出了一種改進的HMM方法并應(yīng)用于地圖匹配，該方法不僅考慮了路網(wǎng)的拓撲信息，軌跡的位置和方向信息，還在計算發(fā)射概率時將軌跡的位置信息和方向信息融合，轉(zhuǎn)移概率計算時考慮到候選道路速度和距離的關(guān)聯(lián)，并從數(shù)學的角度對匹配問題進行了研究。該方法在降低計算成本、減輕拓撲誤差對路網(wǎng)的影響方面具有明顯的優(yōu)勢。

1 ?地圖匹配問題

1.1 ?建立路網(wǎng)

路網(wǎng)數(shù)據(jù)一般是shapefile格式，通過讀取shp文件和dbf文件，獲取道路的節(jié)點ID、坐標信息及屬性信息，從而建立路網(wǎng)的有向圖G（V，E），其中V的元素為道路端點，E的元素為道路路段。

1.2 ?地圖匹配問題

本質(zhì)上匹配問題可以推廣為一個優(yōu)化問題，在給定條件下尋找匹配的最優(yōu)解。對應(yīng)的GPS測量值g可定義為物理位置x和誤差λ的疊加。對單一的軌跡點進行各種形式觀測概率的計算，忽略了軌跡點的前后關(guān)聯(lián)。

為了分析軌跡點與路網(wǎng)的對應(yīng)關(guān)系，假定對應(yīng)關(guān)系為：

g=x+λ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

其中，x∈r，r∈R，且r為路段，R為所有路段的集合，λ為GPS測量誤差。為了說明，式（1）可以寫成：

（2）

其中，x1∈r1，x2∈r2，…，xn∈rn和r1∈R，r2∈R，

…，rn∈R，因此匹配問題可以轉(zhuǎn)化成以下目標函數(shù)：

或者

解決地圖匹配問題包括為每一個GPS測量值在真實道路上找到一個最優(yōu)的匹配點。在本研究中，我們將目標函數(shù)重新定義為隨機過程：

（3）

其中，p（xi+1=si+1|xi=si）是指在前一個軌跡匹配概率最大的前提下下一個軌跡點選擇路段的概率，si為候選路段。

在匹配概率最大的情況下，尋找一個最優(yōu)映射集使得{si|i=1，2，…，n}取得最大匹配概率。

觀測概率用來描述一個GPS測量值g對應(yīng)一個候選狀態(tài)x的可能性有多大，可以通過考慮位置和方向信息表示為條件概率：

Po（g）=p（x=xo|g，xr=gr|gr） ? ? ? ? ? ? ? ?（4）

其中，xr為軌跡方向信息。

Newson等認為觀測到的軌跡點符合正態(tài)分布，可以使用高斯函數(shù)來表達距離因素的發(fā)射概率，本文考慮到軌跡點的距離、方向、速度三者之間具有很大的關(guān)聯(lián)，所以采用的是二維正態(tài)分布表示觀測概率，計算公式為：

（5）

其中，，，μ1為從軌跡點至候選路段的均值，μ2為GPS設(shè)備的系統(tǒng)誤差，σ1為GPS的誤差的標準差，一般取值為20，σ2為方向觀測誤差的方差，ρ均為常數(shù)，且σ1>0，σ2>0，|ρ|<1則稱（x，y）服從參數(shù)為μ1，μ2，σ1，σ2，ρ的二維正態(tài)分布，記作（x，y）～N（μ1，μ2，σ12，σ22，ρ）。

d（x-g）=‖x-g‖ ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

其中，d（x-g）為點到路段的距離。

假定 ?為速度方向與匹配路段的夾角。以正北方向為基準，計算速度與正北方向的夾角為βi，匹配路段與正北方向的夾角分別為 ，則 ?計算公式為：

（7）

為此本文將轉(zhuǎn)移概率用式（8）表示：

（8）

其中，xi+1為第i+1個軌跡點，xi為第i個軌跡點對應(yīng)的候選路段;ω1+ω2=1，其中ω1>0，ω2>0;v為所選路段的限速;Dis為從候選路段間的實際路網(wǎng)距離。區(qū)別于使用傳統(tǒng)的BFS算法（如Dijkstra算法），本文使用啟發(fā)式的A*算法進行路網(wǎng)距離的計算。A*算法不需要遍歷路網(wǎng)中所有的路段，其距離估算值與實際值越接近，算法運行速度越快，效率越高。

2 ?算法模型與分析

2.1 ?數(shù)據(jù)集描述

本文的軌跡數(shù)據(jù)來源于北京市二環(huán)周圍100輛出租車，24 860條GPS數(shù)據(jù)[20]，此數(shù)據(jù)集的GPS軌跡由帶有時間戳的點序列表示，每個點包含緯度、經(jīng)度、速度和方向信息。緩沖區(qū)半徑R設(shè)為200 m。

地圖匹配的準確率為：

（9）

其中，acc為準確率，m為正確匹配到對應(yīng)路段的軌跡點的個數(shù)，j為軌跡點的總數(shù)。

2.2 ?實驗分析

在計算觀測概率時選擇二維正態(tài)分布作為概率公式，其中的μ1，μ2，σ1，σ2，ρ參數(shù)有些是基于經(jīng)驗，有些是路網(wǎng)數(shù)據(jù)分析而來，其中ρ參數(shù)是反應(yīng)距離和方向關(guān)聯(lián)度大小的關(guān)鍵指標，在實驗中以線性遞進驗證取值ρ為多少時軌跡匹配率最高，如圖1、圖2所示。

分別選擇50，200，1 000條軌跡分析相關(guān)系數(shù)ρ取值的適用性，計算每組實驗的匹配準確率平均值，如圖2所示。從圖1和圖2中可得在計算觀測概率時ρ的取值雖然對匹配準確率的影響很大，但是總體的準確率依舊很高，可以發(fā)現(xiàn)當ρ取值為0.7時，匹配效果最為顯著。

當ρ取值為0.7，轉(zhuǎn)移概率選用經(jīng)典計算公式時，對比本文算法和HMM的匹配準確率，如表1所示。

考慮到距離和方向的關(guān)聯(lián)性，并通過實驗分析確定了關(guān)聯(lián)度參數(shù)的取值，表1中的結(jié)果證明了匹配的準確率提高了2.58%。

當ρ取值為0.7時，我們選擇一條軌跡分析ω取值對匹配準確率的影響，實驗結(jié)果如圖3、圖4所示。

為了避免匹配偶然性的發(fā)生，分別選擇50，200，1 000條軌跡分析ω取值的適用性，分別計算每一條軌跡的匹配準確率，總軌跡數(shù)疊加取其平均值，如圖3所示。

從圖3和圖4可得隨著ω取值的增大，準確率相對的增大，在相關(guān)系數(shù)ω為0.6時，軌跡匹配正確率的最大，隨后便不斷地下滑。本文選擇ω為0.6作為實驗的最終參數(shù)。匹配的準確率有些許波動，原因可能是真實路網(wǎng)中的某些路段沒有收錄在地圖數(shù)據(jù)中，或是待匹配軌跡過度分散和漂移嚴重。

為此我們對本文所選用的數(shù)據(jù)集做了總體的預(yù)測，并將本文算法和原始HMM進行對比，如表2所示。

由表2可得，本文算法比原始的算法在匹配準確率上提高了7.12%，效果非常顯著。

本文截取了部分出租車在一定時間段內(nèi)的行駛軌跡點匹配到道路網(wǎng)的情況，其匹配結(jié)果如圖5、圖6中加粗的黑線所示。

從圖5和圖6中可以看出本文提出的地圖匹配算法不僅適用于短路徑匹配還在長軌跡段取得了優(yōu)異的效果。

3 ?結(jié) ?論

在地圖匹配的研究中，本文提出了一種改進HMM地圖匹配算法。在計算觀測概率時兼顧了位置和方向的關(guān)聯(lián)性，轉(zhuǎn)移概率計算中將速度因素納入考慮。結(jié)果表明，該算法的準確率可達97%。雖然我們的算法很大程度上依賴于詳細正確路網(wǎng)數(shù)據(jù)，但仍在復雜路段取得了高精度的匹配。需要注意的是是該算法仍會受到相鄰平行路段或多車道的干擾，候選路段的精確快速搜索以及駕駛?cè)说男熊嚵晳T等因素的影響，上述問題是未來研究的潛在重要課題。

參考文獻：

[1] YUAN J，ZHENG Y，XIE X，et al. Driving with knowledge from the physical world [C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining.New York：Association for Computing Machinery，2011：316-324.

[2] CHEN C，ZHANG D Q，CASTRO P S，et al. iBOAT：Isolation-based online anomalous trajectory detection [J].IEEE Transactions on Intelligent Transportation Systems，2013，14（2）：806-818.

[3] LI X L，HAN J W，LEE J G，et al. Traffic density-based discovery of hot routes in road networks [C]//Proceedings of the 10th international conference on Advances in spatial and temporal databases.Berlin：Springer-Verlag，2007：441-459.

[4] ZHENG Y，LIU Y C，YUAN J，et al. Urban Computing with Taxicabs [C]//Proceedings of the 13th ACM International Conference on Ubiquitous Computing.New York：Association for Computing Machinery，2011：89-98.

[5] ZHANG J T. Smarter outlier detection and deeper understanding of large-scale taxi trip records：a case study of NYC [C]//Proceedings of the ACM SIGKDD International Workshop on Urban Computing.New York：Association for Computing Machinery，2012：157-162.

[6] QUDDUS M A，OCHIENG W Y，NOLAND R B. Current map-matching algorithms for transport applications：State-of-the art and future research directions [J].Transportation Research Part C：Emerging Technologies，2007，15（5）：312-328.

[7] KIM S，KIM J H. Adaptive fuzzy-network-based C-measure map-matching algorithm for car navigation system [J].IEEE Transactions on Industrial Electronics，2001，48（2）：432-441.

[8] WHITE C E，BERNSTEIN D，KORNHAUSER A L. Some map matching algorithms for personal navigation assistants [J].Transportation Research Part C：Emerging Technologies，2000，8（1-6）：91-108.

[9] PHUYAL A，BISHNU P. Adaptive trajectory segmentation method and its application in in-car navigation system [D].Ohio：The Ohio State University，2001.

[10] 張小國，王慶，萬德鈞.基于路網(wǎng)拓撲特性及先驗知識的地圖匹配算法 [J].東南大學學報（自然科學版），2006（4）：625-629.

[11] 盛彩英，席唱白，錢天陸，等.浮動車軌跡點地圖匹配及插值算法 [J].測繪科學，2019，44（8）：106-112.

[12] QUDDUS M A，OCHIENG W Y，ZHAO L，et al. A general map matching algorithm for transport telematics applications [J].GPS Solutions，2003，7（3）：157-167.

[13] HASHEMI M，KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks [J].Journal of Intelligent Transportation Systems，2016，20（6）：573-590.

[14] 高文超，李國良，塔娜.路網(wǎng)匹配算法綜述 [J].軟件學報，2018，29（2）：225-250.

[15] 田甜，呂芳，王秀玲.一種基于浮動車優(yōu)化地圖匹配方法 [J].現(xiàn)代電子技術(shù)，2015，38（11）：159-162.

[16] LI H Q，WU G. Map Matching for Taxi GPS Data with Extreme Learning Machine [C]//International Conference on Advanced Data Mining and Applications，2014：447-460.

[17] XU H，LIU H C，TAN C W，et al. Development and Application of an Enhanced Kalman Filter and Global Positioning System Error-Correction Approach for Improved Map-Matching [J].Journal of Intelligent Transportation Systems，2010，14（1）：27-36.

[18] SMAILI C，NAJJAR M E B E，CHARPILLET F. A Hybrid Bayesian Framework for Map Matching：Formulation Using Switching Kalman Filter [J].Journal of Intelligent & Robotic Systems，2014，74（3-4）：725-743.

[19] 王科，李鵬，金瑜，等.基于三證據(jù)DS理論的雙模式地圖匹配算法 [J].計算機工程，2018，44（5）：316-321.

[20] 曾嘉酈，孫立雙，王曉明.北京出租車GPS軌跡數(shù)據(jù)地圖匹配算法研究 [J].北京測繪，2019，33（3）：255-260.

作者簡介：張浩（1996—），男，漢族，安徽蚌埠人，碩士研究生，主要研究方向：軌跡預(yù)測、物聯(lián)網(wǎng)技術(shù)、嵌入式系統(tǒng)開發(fā);劉大明（1971—），男，漢族，上海人，副教授，博士，主要研究方向：物聯(lián)網(wǎng)技術(shù)、嵌入式系統(tǒng)與設(shè)計、智能工業(yè)機器人。