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

張浩 劉大明

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

關鍵詞：拓撲結構;HMM;觀測概率;轉移概率

中圖分類號：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 ?引 ?言

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

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

1 ?地圖匹配問題

1.1 ?建立路網

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

1.2 ?地圖匹配問題

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

為了分析軌跡點與路網的對應關系，假定對應關系為：

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

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

（2）

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

…，rn∈R，因此匹配問題可以轉化成以下目標函數：

或者

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

（3）

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

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

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

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

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

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

（5）

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

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

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

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

（7）

為此本文將轉移概率用式（8）表示：

（8）

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

2 ?算法模型與分析

2.1 ?數據集描述

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

地圖匹配的準確率為：

（9）

其中，acc為準確率，m為正確匹配到對應路段的軌跡點的個數，j為軌跡點的總數。

2.2 ?實驗分析

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

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

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

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

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

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

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

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

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

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

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

3 ?結 ?論

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

參考文獻：

[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] 張小國，王慶，萬德鈞.基于路網拓撲特性及先驗知識的地圖匹配算法 [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] 高文超，李國良，塔娜.路網匹配算法綜述 [J].軟件學報，2018，29（2）：225-250.

[15] 田甜，呂芳，王秀玲.一種基于浮動車優化地圖匹配方法 [J].現代電子技術，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] 王科，李鵬，金瑜，等.基于三證據DS理論的雙模式地圖匹配算法 [J].計算機工程，2018，44（5）：316-321.

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

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