一種面向高架區(qū)域的GPS導航地圖匹配算法

葉泰航　張書漿　徐建軍

摘 要： 對于包含高架的城市路網(wǎng)，傳統(tǒng)的GPS導航地圖匹配算法準確率較低。為了彌補傳統(tǒng)算法的不足，提出了一種面向高架區(qū)域的地圖匹配算法。同時為了保證算法實時性，提出了一種常數(shù)時間網(wǎng)格索引方法，快速返回導航點鄰域的路段集合；為了提高高架區(qū)域的導航匹配精度，提出了采用夾角、距離、高程、可達性四種輸入?yún)?shù)的模糊推理方法。該算法通過在杭州市中河高架區(qū)域的實驗結(jié)果表明，其相對于基準方法表現(xiàn)出更高的精度。

關(guān)鍵詞： 地圖匹配； 網(wǎng)格索引； 模糊推理； 智能交通系統(tǒng)

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2014）04-37-03

Abstract： Traditional GPS map-matching algorithms perform poorly in areas with viaducts. In order to make up for this shortcoming， a new algorithm is proposed in this paper. For the real-time computation， a new grid index method is designed to return road segments around an observed positioning point in O（1） time. For improving the accuracies in handling viaduct areas， an algorithm based on fuzzy inference is introduced， which takes four input parameters into account， including angles， projecting distances， the elevations and the reachability. The experiments as applying in the area of Zhong-he viaduct of Hangzhou city shows that the proposed algorithm performs better than the benchmark algorithm.

Key words： map matching； grid index； fuzzy inference algorithm； intelligent transportation system

0 引言

GPS導航地圖匹配是交通工程領(lǐng)域研究的關(guān)鍵技術(shù)。隨著基于浮動車定位的實時路況監(jiān)測技術(shù)的推廣，以及大量基于位置的服務的涌現(xiàn)，常用的GPS匹配算法已不能滿足精度要求，尤其在高架與路面重疊、交疊、平行等情形下，難以給出高精度的匹配結(jié)果。

已有的地圖匹配方法可粗略概括為：距離匹配法、拓撲匹配法、概率匹配法、高級匹配法四類。距離匹配法利用導航觀測點與道路之間的鄰近關(guān)系，如Bernstein[1]提出的點-點匹配法。拓撲匹配法基于地理實體之間的空間關(guān)系，例如 Greenfield[2]提出的基于拓撲的匹配算法。概率匹配法在觀測點的周圍擴展一個誤差區(qū)域（橢圓或者矩形），若多條路出現(xiàn)在該區(qū)域，則綜合運用行車方向、距離、連通性等因素決定正確的匹配，如Ochieng[3]提出的快速概率匹配算法。高級匹配法指的是Obradovic[4]提出的卡曼濾波，El Najjar[5]等提出的DS證據(jù)理論，以及Gustafsson等[6]提出的狀態(tài)空間模型和粒子過濾理論等。

傳統(tǒng)地圖匹配方法一般是初始匹配加后續(xù)匹配。初始匹配的目的是確定第一個置信度較高的匹配點。后續(xù)匹配基于初始匹配，綜合考慮其他因素來決定后續(xù)導航點的匹配路段。但若在高架與地面道路重疊和交疊的區(qū)域，初始匹配的正確匹配率較低，可能誤導后續(xù)匹配。

本文力圖從兩個方面提升匹配效果：①針對傳統(tǒng)方法實時性低的問題，設計一種常數(shù)時間網(wǎng)格索引方法提升實時性；②針對傳統(tǒng)方法在處理高架與路面重疊、交疊等復雜情形時的不足，通過合理利用高程信息提升精度。

1 算法框架

本文的算法框架包括四個部分：①常數(shù)時間網(wǎng)格索引方法；②基于模糊推理的高架區(qū)域匹配算法，對任何一個待匹配的導航點，通過模糊推理從候選匹配路段中決定最佳匹配路段；③可達性判定，以此來過濾掉候選匹配路段中不合理的匹配路段；④算法轉(zhuǎn)折點的決定，當算法滿足轉(zhuǎn)折條件時，啟動②、③相結(jié)合的算法模式。下面詳細介紹各個關(guān)鍵步驟。

1.1 建立常數(shù)時間網(wǎng)格索引

建立地圖索引是快速提取每個導航觀測點附近候選匹配路段的最有效手段。傳統(tǒng)的四叉樹索引和網(wǎng)格索引的查找時間均為對數(shù)時間量級，考慮到高并發(fā)情形下的實時性要求，我們提出一種新型的常數(shù)時間網(wǎng)格索引。

本索引技術(shù)比起傳統(tǒng)的網(wǎng)格索引技術(shù)有兩點改進：傳統(tǒng)方法采用二分搜索法查找待匹配點所在的網(wǎng)格，時間開銷為對數(shù)量級，而本索引技術(shù)采用哈希映射法，可以在O（1）時間查找到目標網(wǎng)格；傳統(tǒng)的緩沖區(qū)法作以待匹配點為質(zhì)心的緩沖區(qū)，計算哪些路段落在該緩沖區(qū)，而本索引技術(shù)在建立索引階段就對待匹配點所在網(wǎng)格的緩沖區(qū)中路段進行存儲，當查找到該網(wǎng)格時，無需計算就可確定候選匹配路段。這兩點改進大大提高了算法的實時性。

圖1所示為劃分了25個網(wǎng)格的網(wǎng)格劃分區(qū)域，每個網(wǎng)格的經(jīng)度范圍是0.006，緯度范圍是0.004，虛線和最小網(wǎng)格之間的部分是最小網(wǎng)格的緩沖區(qū)。對待匹配點P，只需用其經(jīng)度減去邊界經(jīng)度119.698，然后除以0.006后取整即P所在網(wǎng)格的列號，同理，將其緯度減去邊界緯度30.564，除以0.004便獲得P所在網(wǎng)格的行號。在建立網(wǎng)格索引時，每個網(wǎng)格將該網(wǎng)格及其緩沖區(qū)內(nèi)所有路段的ID存儲下來，緩沖區(qū)的選擇需要保證P的正確匹配路段一定在該網(wǎng)格或者其緩沖區(qū)中。

1.2 基于模糊推理的高架區(qū)域匹配算法

以下“夾角”指車頭方向與路段方向之間的夾角，路段為有向路段，方向由允許車輛行駛的方向決定，雙向行駛路段包含兩條有向路段；“距離”指導航觀測點到路段的垂直距離；“高程”是地面路段和高架路段的高度數(shù)據(jù)；“可達性”指從上一時刻的匹配路段出發(fā)，下一時刻能到達候選匹配路段的可能性。運用上述參數(shù)，設計了如圖2所示模糊推理系統(tǒng)。

⑴ 模糊化

根據(jù)定義的隸屬函數(shù)，將夾角、距離、高度差等信息映射成隸屬度值。本文所用的隸屬度函數(shù)為如圖3所示的鐘形和梯形函數(shù)，并根據(jù)100個典型樣本訓練得到夾角和距離的隸屬度函數(shù)的參數(shù)，具體細節(jié)如下。

1.3 可達性的判定

當某定位點確定被匹配正確，算法開始結(jié)合可達性信息。具體做法是：當檢測到某條路段不可達時，從候選路段中去掉不可達路段。不可達性的評估主要是檢查當前路段的鄰接后繼路段和兩跳后繼路段中是否有該候選路段，若無，則認為該路段不可達。

1.4 算法轉(zhuǎn)折點的判定

前面提到，只有當某一定位點確信無疑被正確匹配后，才啟動非高架匹配法2和高架匹配法2，這意味著算法進入一個更加可靠的匹配階段。有兩種情況可判定為必然匹配正確：①緩沖區(qū)只有一條路段；②緩沖區(qū)中有兩條路段，但C1-C2=90，其中C1和C2分別表示這兩條路段經(jīng)過模糊推理之后的輸出值。C1對應的路段必然匹配正確。

2 實驗評估

本文采用最短投影距離法作為實驗比較對象，即將該方法當作基準方法。最短投影距離法指將觀測點投影到投影距離最短的路段上。

匹配優(yōu)勢舉例1（高架交疊問題）：

本文方法在處理高架交疊情形的匹配問題時有明顯的效果。由于考慮了車頭方向，即圖中箭頭所指方向，可以有效地避免在交叉路口處的錯誤匹配。如圖4所示，采用本文的算法，P2會正確地匹配到轉(zhuǎn)盤，而基準方法則會將P2匹配到其他路段。

匹配優(yōu)勢舉例2（高架與地面路平行問題）：

本文方法對于高架路段和地面路段平行甚至重疊的情形可以處理得很好。如圖5所示，H表示高程值，采用本文的技術(shù)，P5、P6、P7的正確匹配路段為地面路段2，然而，基準方法將這三個點匹配到高架路段2。本文所用高程數(shù)據(jù)均為基于手機定位模塊駕車采集而得。

3 結(jié)束語

本文提出了一種面向高架區(qū)域的GPS導航地圖匹配算法，針對傳統(tǒng)方法實時性低的問題，設計了一種常數(shù)時間網(wǎng)格索引方法來提升算法的實時性；針對傳統(tǒng)方法在處理高架與路面重疊、交疊等復雜情形時的不足，通過合理利用高程信息來提升算法的精度；為了提高高架區(qū)域的導航匹配精度，提出了采用夾角、距離、高程、可達性四種輸入?yún)?shù)的模糊推理方法。本文方法具有如下兩點優(yōu)勢：①為一種O（1）時間網(wǎng)格索引，查找速度極快，可以節(jié)約查詢所需的時間開銷，提高了算法的實時性；②著重考慮解決高架附近的導航匹配問題，針對高架與地面重疊、交疊等實際情形，合理地引入高程信息達到提高匹配精度的目的。實驗結(jié)果表明，本文方法在處理高架區(qū)域的地圖匹配時具有較高的精度。下一步我們需要研究面向高并發(fā)場景的GPS導航地圖匹配方法。

參考文獻：

[1] Bernstein D.， Kornhauser A.. An Introduction to Map Matching for Personal Navigation Assistants[A]. National Research Council （US）. Transportation Research Board. Meeting[C]. Washington： Preprint CD-ROM，1998.

[2] Greenfeld， J. S.. Matching GPS Observations to Locations on a Digital Map[A]. National Research Council （US）. Transportation Research Board. Meeting[C]. Washington： Preprint CD-ROM，2002.

[3] Ochieng， W. Y.， Quddus， M. A.， Noland， R. B.. Map-matching in Complex Urban Road Networks[J]. Revista Brasileira de Cartografia，2004.2（55）：1-18

[4] Obradovic， D.， Lenz， H.， Schupfner， M.. Fusion of Map and Sensor Data in A Modern Car Navigation System[J]. Journal of VSLI Signal Processing，2006.45（2）：112-122

[5] E1 Najjar， M. E.， Bonnifait， P.. A Road-matching Method for Precise Vehicle Localization using Kalman Filtering and Belief Theory[J]. Autonomous Robots，2005.19（2）：173-191

[6] Gustafsson， F.， Gunnarsson， F.， Bergman， N.. Particle Filters for Positioning， Navigation， and Tracking[J]. IEEE Transactions on Signal Processing，2002.50（2）：425-437