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

葉泰航　張書漿　徐建軍

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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導(dǎo)航地圖匹配是交通工程領(lǐng)域研究的關(guān)鍵技術(shù)。隨著基于浮動(dòng)車定位的實(shí)時(shí)路況監(jiān)測(cè)技術(shù)的推廣，以及大量基于位置的服務(wù)的涌現(xiàn)，常用的GPS匹配算法已不能滿足精度要求，尤其在高架與路面重疊、交疊、平行等情形下，難以給出高精度的匹配結(jié)果。

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

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

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

1 算法框架

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

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

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

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

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

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

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

⑴ 模糊化

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

1.3 可達(dá)性的判定

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

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

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

2 實(shí)驗(yàn)評(píng)估

本文采用最短投影距離法作為實(shí)驗(yàn)比較對(duì)象，即將該方法當(dāng)作基準(zhǔn)方法。最短投影距離法指將觀測(cè)點(diǎn)投影到投影距離最短的路段上。

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

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

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

[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