基于改進(jìn)的HMM地圖匹配算法

張浩 劉大明

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

關(guān)鍵詞：拓?fù)浣Y(jié)構(gòu);HMM;觀測概率;轉(zhuǎn)移概率

中圖分類號：TP301.6 ? ? ?文獻(xiàn)標(biāo)識碼：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)域。近年來學(xué)者在地圖匹配算法或技術(shù)方面做了大量的研究。Quddus等人將其歸納為四種類型：基于幾何的算法、基于拓?fù)涞乃惴ā⒒诟怕实乃惴ê突诟呒墧?shù)學(xué)理論的算法[6]。基于幾何的算法主要考慮路網(wǎng)和軌跡的幾何特征，如點(diǎn)對點(diǎn)[7]、點(diǎn)對線[8]和線對線算法[9]，但是基于幾何的算法通常會忽略拓?fù)湫畔ⅲ@可能導(dǎo)致復(fù)雜場景的錯(cuò)誤匹配;基于拓?fù)涞乃惴▌t側(cè)重于軌跡和路網(wǎng)之間的拓?fù)潢P(guān)系[10]，包括拓?fù)浼訖?quán)算法[11]、地圖匹配算法[12]和加權(quán)地圖匹配算法[13]，這類算法將路網(wǎng)處理為圖結(jié)構(gòu)，從而將拓?fù)湫畔⒓{入其中，適用于高采樣率的地圖匹配算法;基于概率的算法將GPS位置視為隨機(jī)變量，軌跡視為隨機(jī)過程。HMM是這些算法中常用的算法。基于HMM的方法非常適合道路匹配[14]，HMM可以同時(shí)考慮幾何和地形信息，卻不需要訓(xùn)練數(shù)據(jù)，但是該算法對最短路徑進(jìn)行計(jì)算使得計(jì)算開銷很大。位置和方向信息不符合嚴(yán)格的獨(dú)立分布，因而HMM的發(fā)射概率計(jì)算公式并不適用于地圖匹配。模糊邏輯[15]、神經(jīng)網(wǎng)絡(luò)[16]、卡爾曼濾波[17，18]、粒子濾波和Dempster-Shafer[19]理論等先進(jìn)的數(shù)學(xué)和人工智能理論在地圖匹配領(lǐng)域廣泛應(yīng)用，但是此類算法通常需要大量的訓(xùn)練數(shù)據(jù)集來執(zhí)行逐點(diǎn)匹配，使得它們的實(shí)際應(yīng)用非常困難。

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

1 ?地圖匹配問題

1.1 ?建立路網(wǎng)

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

1.2 ?地圖匹配問題

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

為了分析軌跡點(diǎ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)化成以下目標(biāo)函數(shù)：

或者

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

（3）

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

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

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

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

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

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

（5）

其中，，，μ1為從軌跡點(diǎn)至候選路段的均值，μ2為GPS設(shè)備的系統(tǒng)誤差，σ1為GPS的誤差的標(biāo)準(zhǔn)差，一般取值為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）為點(diǎn)到路段的距離。

假定 ?為速度方向與匹配路段的夾角。以正北方向?yàn)榛鶞?zhǔn)，計(jì)算速度與正北方向的夾角為βi，匹配路段與正北方向的夾角分別為 ，則 ?計(jì)算公式為：

（7）

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

（8）

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

2 ?算法模型與分析

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

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

地圖匹配的準(zhǔn)確率為：

（9）

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

2.2 ?實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

3 ?結(jié) ?論

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

參考文獻(xiàn)：

[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)拓?fù)涮匦约跋闰?yàn)知識的地圖匹配算法 [J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2006（4）：625-629.

[11] 盛彩英，席唱白，錢天陸，等.浮動車軌跡點(diǎn)地圖匹配及插值算法 [J].測繪科學(xué)，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].軟件學(xué)報(bào)，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].計(jì)算機(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è)計(jì)、智能工業(yè)機(jī)器人。