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

葉泰航　張書漿　徐建軍

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

關鍵詞： 地圖匹配； 網格索引； 模糊推理； 智能交通系統

中圖分類號：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導航地圖匹配是交通工程領域研究的關鍵技術。隨著基于浮動車定位的實時路況監測技術的推廣，以及大量基于位置的服務的涌現，常用的GPS匹配算法已不能滿足精度要求，尤其在高架與路面重疊、交疊、平行等情形下，難以給出高精度的匹配結果。

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

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

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

1 算法框架

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

1.1 建立常數時間網格索引

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

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

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

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

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

⑴ 模糊化

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

1.3 可達性的判定

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

1.4 算法轉折點的判定

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

2 實驗評估

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

匹配優勢舉例1（高架交疊問題）：

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

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

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

3 結束語

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