馮 通，杜文才

(海南大學 信息科學技術(shù)學院，海南 ?？?70228)

近年，隨著民用GPS(Global Positioning System，全球定位系統(tǒng))等定位設備在移動終端上的廣泛使用以及基于位置服務(Location-Based Service)和移動社交網(wǎng)絡(Mobile Social Network )的發(fā)展和普及，大量的軌跡數(shù)據(jù)在日常生活中正在日益積累. 為了分析和處理這些數(shù)據(jù)，需要將軌跡點映射到道路網(wǎng)絡中.

盡管有些應用，如車輛導航等，系統(tǒng)需要掌握移動對象精確的軌跡信息，但大多應用僅需獲知移動對象所經(jīng)過的道路序列即可，這些應用包括公交路徑規(guī)劃、交通流統(tǒng)計等. 因此，對低頻采樣軌跡點的地圖匹配提出了要求. 然而，軌跡數(shù)據(jù)的稀疏性、設備的測量誤差及路網(wǎng)數(shù)據(jù)的偏差向這一工作提出了挑戰(zhàn).于是，對GPS 數(shù)據(jù)稀疏性及數(shù)據(jù)噪聲的算法研究成為學者們研究的熱點. 文獻［1］提出了一種基于Frechet 距離的全局地圖匹配算法，擁有較高的正確率，但它的計算復雜度較高. 文獻［2］提出了一種基于隱性馬爾科夫模型(Hidden Markov Model，HMM)的地圖匹配算法，該算法能夠有效的找出移動對象經(jīng)過的道路序列. 文獻［4］中針對地圖匹配算法做了較為全面的總結(jié). 文獻［5］提出一種用于在線完成這一過程的算法，即增量式地圖匹配. 文獻［6］利用近似算法加快了這一過程，并指出當GPS 采樣頻率較高時，即使僅將軌跡點匹配至最近的道路片段也可得到較高的正確率. 文獻［7］提出了一種基于歷史軌跡的路網(wǎng)匹配算法，通過歷史軌跡來推出移動對象可能經(jīng)過的道路. 文獻［8 －10］提出了一種基于多假設的路網(wǎng)匹配算法. 以上文獻工作均需要較為復雜的數(shù)據(jù)模型，不便于算法的高效實現(xiàn).

因此，筆者提出了一種基于理想馬爾科夫模型的地圖匹配算法，其次在不同程度的簡化路網(wǎng)下，分別對所提算法的性能進行了評估，這也為如何選擇合適的道路網(wǎng)絡采樣密度提供了重要的參考.

1 問題描述

地圖匹配問題的形式化描述如下

輸入 一系列GPS 觀察點，其中Ot=(xt，yt)包含在時間t 時，移動對象的經(jīng)度和緯度;道路網(wǎng)絡G =(V，E)，其中，cpi代表路網(wǎng)的交叉點(以下簡稱CP)，即路口或道路中的轉(zhuǎn)折點;為一系列有向邊，代表路網(wǎng)中的道路片段.

輸出 一系列相連的道路序列其中，表示與觀測點匹配的道路片段.

圖1 為地圖匹配的示例圖，其中觀察點序列為(1，2，3，4，5)，道路網(wǎng)絡中包含15 個CP(A，B，…，K，W，X，Y，Z)及相應的連接道路. 本示例中，觀測點可被匹配到多種道路序列中，比如觀測點序列(1，2，3)可以被匹配到蜿蜒道路(A，B，C，…，G，H)或被匹配到高速公路(X，Y，Z). 地圖匹配的目的是找到移動對象經(jīng)過的最大似然的CP 序列.

另一方面，地圖匹配的精度還受道路粒度的影響. 如圖2 所示，本文將路口和道路的轉(zhuǎn)折點處均視為CP. 在許多地圖數(shù)據(jù)中，如OpenStreetMap［3］，道路被表示為CP 的序列. 此外，當前的地圖匹配算法多是用觀測點在道路上的幾何投影的方式來獲取道路候選集.

圖1 地圖匹配示例

圖2 用交叉點（CP）表示道路網(wǎng)絡

2 基于隱性馬爾科夫模型的地圖匹配

在HMM 模型中，假設移動對象在CP 間移動，且移動的過程符合馬爾科夫模型. 由于無法直接觀察到移動對象所經(jīng)過的道路軌跡，所以將這些軌跡稱為隱性狀態(tài). 不過，可以觀測到隱性狀態(tài)的輸出，即GPS 序列點. 此外，還假設觀測值僅與移動對象的隱性狀態(tài)相關(guān).

圖3 給出了隱性馬爾科夫模型的示意圖及本文所采用的模型與先前工作的對比. 其中，上半部分代表隱性狀態(tài)間的轉(zhuǎn)移，而下半部分代表相應的觀察結(jié)果.

圖3 2 種HMM 模型對比

隱性馬爾科夫模型主要包含3 種概率

發(fā)射概率(Emission Probability)代表在特定隱性狀態(tài)下，得到某觀察值的概率，表示為Pr(Ot|CPt=cpi)，即在時間t，隱性狀態(tài)為cpi時，觀察值為Ot的概率. 與先前的工作相同，認為觀察點符合正態(tài)分布，中心位于cpi.

狀態(tài)轉(zhuǎn)移概率(State Transition Probability)代表移動對象從一個CP 移動至另一個CP 的概率，對應于圖3 所示理想隱性馬爾科夫模型中的狀態(tài)轉(zhuǎn)移. 假設狀態(tài)轉(zhuǎn)移概率與CP 間的距離正相關(guān)，即

其中，β 用于調(diào)節(jié)cpi與cpj間最短距離dij對結(jié)果的影響.

起始狀態(tài)概率 代表移動對象初始時位于某CP 的概率，實驗中使用相應CP 的發(fā)射概率來表示移動對象的起始狀態(tài)概率，即

2.1 與先前工作對比 文獻［2］中，狀態(tài)轉(zhuǎn)移概率定義如下

其中，Rt表示Ot在道路網(wǎng)絡上的投影點，dRt，Rt－1代表Rt與Rt+1間的路網(wǎng)距離. 這種狀態(tài)轉(zhuǎn)移概率依賴于當前及上一次觀察狀態(tài)，因此不能嚴格滿足Viterbi 算法中對狀態(tài)轉(zhuǎn)移概率的要求. 這種不足是由于算法設計時的一些考慮導致的，也導致2 個問題得產(chǎn)生. 首先，為了利用Viterbi 算法計算轉(zhuǎn)移序列，需要利用式(1)近似得到Pr(Rt+1|Rt)，但利用此近似概率得到的結(jié)果并非一定是式(1)的最大似然結(jié)果. 再者，式(1)將Rt在路網(wǎng)上的幾何投影作為移動對象隱性狀態(tài)的一部分. 但軌跡點在路網(wǎng)上投影并不唯一，這就增大了HMM 最大似然解的尋找難度.

為了解決上述問題，使用離散的路網(wǎng)采樣點而非道路本身來表示移動對象的隱性狀態(tài)，從而保證算法找到最優(yōu)路徑. 實驗結(jié)果顯示，盡管算法的實現(xiàn)較為簡單，但仍能取得與文獻［2］中所提方法相似的性能.

2.2 算法實現(xiàn) 根據(jù)文中所提的概率計算方式，可以利用Viterbi 算法求出在理想隱性馬爾科夫模型下移動對象的最大似然的CP 序列. 算法的求解細節(jié)與文獻［2］相似，由于篇幅限制，本文僅給出IHMM 算法的基本步驟.

針對每一個GPS 點，首先找到與之相近的所有CP，并計算相應的發(fā)射概率，然后將GPS 軌跡點和CP序列作為Viterbi 算法的輸入，并計算得出最大似然的CP 序列. 通過上述描述，可以看出算法的結(jié)果與CP 的采樣粒度相關(guān). 為此，在不同CP 粒度的路網(wǎng)下測試了本文算法.

3 實 驗

用Microsoft Dataset(MD)［2］作為地圖匹配算法的測試數(shù)據(jù)集. 其中包含7 531 個GPS 軌跡點，采樣間隔為1 s，行駛距離為81 km. 為了模擬GPS 軌跡點的稀疏性，分別將采樣間隔設為90 s、120 s、180 s、240 s、300 s、360 s、420 s、480 s、540 s 和600 s. 采用文獻［2］提出了方法道路錯誤匹配指數(shù)(Route Mismatch Fraction，RMF)來評估算法的性能，并與其中的算法(以下簡稱HMM)進行對比. IHMM 算法的參數(shù):σ=1.0，β=100.0，對于每個GPS 點，找出擁有最大發(fā)射概率的3 個CP.

圖4 性能對比

圖5 算法效率對比

圖4 顯示了在不同采樣頻率下的地圖匹配算法的性能. IHMM 的RMF 稍高于HMM，這是由于未進行數(shù)據(jù)的預處理來去除其中的噪聲. 從圖4 中可以看出，盡管IHMM 實現(xiàn)較為簡單，但然擁有與HMM 相似的性能. 在采樣間隔上升至600 s，RMF 出現(xiàn)少許下降. 如文獻［2］中所述，RMF 指標由匹配正確和匹配錯誤的點數(shù)量共同決定. 隨著采樣間隔的增加，采樣點數(shù)量也迅速降低，算法的正確率逐漸下降. 此時錯誤點減少的數(shù)量逐漸超過正確點減少的數(shù)量，從而導致RMF 出現(xiàn)少許降低.

圖5 顯示了IHMM 算法及HMM 算法在不同采樣間隔下的匹配速度，其中IHMM 的匹配速度約為HMM 算法的2 倍，這是在由于IHMM 算法中不需要計算軌跡點向道路邊的投影，且IHMM 算法中狀態(tài)轉(zhuǎn)移概率計算較為簡單.

圖6 道路簡化示意

此外，通過去除路網(wǎng)中的10%、20%、30%、40%、50%、60%、70%和80%的CP 來模擬稀疏路網(wǎng). 圖6 為去除50%的CP 點的所得簡化路網(wǎng)中，道路片段的平均長度依次為:55 m、61 m、67 m、72 m、80 m、87 m、94 m 和102 m. 在采樣間隔為90 s 的GPS 軌跡點上進行地圖匹配實驗. 結(jié)果顯示隨著道路稀疏程度的增加，算法的性能變化較小，如當?shù)缆菲伍L度有87 m 降低至55 m 時，匹配錯誤的軌跡點數(shù)量僅增加9%. 但當?shù)缆菲卧黾又?4 m 時，算法的性能開始出現(xiàn)快速下降.

4 小 結(jié)

本文給出了一個基于理想隱形馬爾科夫模型的地圖匹配算法，該算法實現(xiàn)更為簡單，且在處理低頻采樣的GPS 軌跡時仍有較好的性能. 在真實數(shù)據(jù)集上對算法進行了測試，實驗結(jié)果顯示所提算法與先前復雜的算法擁有相近的性能. 此外，實驗結(jié)果顯示在約半數(shù)交叉點被移除的情況下，算法依然擁有較好的性能.

［1］BRAKATSOULAS S，PFOSER D，SALAS R，et al. On map-matching vehicle tracking data proceeding of the 31st VLDB Conference，Trondheim，August 30-September 2，2005［C］. ［S.l.］:ACM，2005.

［2］NEWSON P，KRUMM J. Hidden markov map matching through noise and sparseness proceeding of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，Seattle，November 4-6，2009［C］. ［S.l.］:ACM GIS，2009.

［3］OpenStreetMap.［EB/OL］.［2014 －03 －01］. http:∥www.openstreetmap.org.

［4］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］. Transport. Res. Part C:Emerging Tech，2007，15:12 －328.

［5］GOH C Y，DAUWELS J，MITROVIC N，et al. Online map-matching based on Hidden Markov model for real-time traffic sensing applications proceeding of the 15th International IEEE Annual Conference on Intelligent Transportation Systems，Anchorage，September 16-19，2012［C］.［S.l.］:［s.n.］，2012.

［6］CHEN D，DRIEMEL A，GUIBAS L J，et al. Approximate map matching with respect to the Fréchet distance proceeding of The Workshop on Algorithm Engineering and Experiments (ALENEX11)，San Francisco，January 22，2011［C］. Philadelphia:SIAM，2011.

［7］ZHENG K，ZHENG Y，XIE X，et al. Reducing uncertainty of low-sampling-rate trajectories proceeding of the 28th International Conference on Data Engineering (ICDE)，Washington DC，April 1-5，2012［C］.［S.l.］:［s.n.］，2012.

［8］ABDALLAH F，G. NASSREDINE G，DENOEUX T. A multiple-hypothesis map-matching method suitable for weighted and box-shaped state estimation for localization［J］. IEEE Trans. on Intelligent Transportation Systems，2011，12(4)1495 －1510.

［9］REID D. An algorithm for tracking multiple targets［J］. IEEE Trans. on Automatic Control，1979:24(6)843 －854.

［10］PYO J S，SHIN D H，SUNG T S. Development of a map matching method using the multiple hypothesis technique proceeding of the Intelligent Transportation Systems，Oakland，August 25-29，2001［C］.［S.l.］:［s.n.］，2001.