陳 濱

(閩江學院 現(xiàn)代教育技術中心，福建 福州 350108)

地圖匹配算法是以GPS、北斗導航衛(wèi)星等定位系統(tǒng)獲得的軌跡數(shù)據(jù)及高精度路網(wǎng)信息作為輸入，以此來識別車輛正在行駛的正確路段并確定車輛在路段上的位置[1].地圖匹配算法主要有幾何匹配算法、拓撲匹配算法、概率匹配算法、高級匹配算法[2]等，這些算法各有優(yōu)缺點和使用范圍，而如果要滿足實際的路網(wǎng)需求，就必須尋求新的匹配算法.

1 匹配因素分析

影響地圖匹配效果的因素很多，主要有：GPS定位點與候選道路之間的距離、航向差以及路網(wǎng)拓撲結構等，其中航向差因素是最重要的一個影響因子[3].

1.1 距離因素

GPS定位點到候選道路的距離是地圖匹配的基本依據(jù)，也是最簡單的一種匹配方式.其基本原理是由定位點向附近候選道路作垂線，定位點到垂足之間的距離d越小，匹配的可能性就越大[4].假設定位點為A(xa,ya)，垂足為B(xb,yb)，由兩點間距離公式知

(1)

特殊情況下，由P點向候選道路作垂線，垂足不在道路上，而在道路的延長線上,這時就要比較P點與道路兩個端點的距離，距離較小的端點即為匹配點.

則距離因子D可以由公式(2)量化，

(2)

由于實驗所用導航儀的精度為10 m，根據(jù)概率分布的三倍標準差原則，所以這里的閾值則分別選取10 m和30 m.

1.2 航向差因素

航向差指車輛行駛方向與候選道路方向間的角度差值[5].為簡明闡述航向差因素對地圖匹配的影響，將以正北方向為方向角起點，以順時針方向為旋轉(zhuǎn)正方向，車輛當前航向和正北方向的夾角定義為車輛方向角α；同理，候選道路方向與正北方向的夾角定義為道路方向角β.則航向差θ定義為

θ=min(|α-β|,|α-β+π|)，

(3)

則航向差因子W可以由公式(4)量化，

(4)

根據(jù)車輛行駛的實際情況，當航向角在30°以內(nèi)時，車輛行駛方向與道路走向基本一致；當航向角大于60°時，車輛是偏離道路行駛的，匹配的可能性幾乎為0.

1.3 路網(wǎng)拓撲結構因素

全局匹配算法的準確率一般會高于實時匹配算法，原因是全局匹配算法考慮了路網(wǎng)的拓撲結構T.在道路交通網(wǎng)絡中，路網(wǎng)拓撲結構指候選道路與歷史軌跡之間的連通性情況[6].

圖1 路網(wǎng)拓撲結構示意圖

如圖1，假設前一時刻車輛行駛在A道路上，根據(jù)GPS采樣點時間間隔以及車輛正常行駛速度推算可知，下一時刻車輛只可能行駛在B、C或者D道路上，而不可能跑到E、F和G道路上.因此，我們在下一時刻道路匹配時，候選道路只能在B、C和D中選擇，就能減小候選道路的數(shù)量，提高匹配效率.如果候選道路與前一時刻軌跡相連通，T取1，否則取0.

基于拓撲結構的匹配算法，最大優(yōu)點是在匹配之前，先利用路網(wǎng)的拓撲關系，篩選出可能的匹配道路，提高匹配效率.但是，該算法在使用過程中有一個前提條件，就是用來進行匹配的電子地圖的精確度一定要足夠高[7].

2 融合函數(shù)構建

從分析可知，距離、航向差以及路網(wǎng)拓撲結構因素都可以和接收的GPS定位點進行地圖匹配，但這些匹配方法只能應用于一些特殊路段.隨著道路交通網(wǎng)絡的不斷完善，在實際車輛行駛過程中，可能會遇到不同情況的路網(wǎng)結構，而依據(jù)單一的影響因子來判斷匹配點往往具有片面性和局限性.因此，本文構建了以距離因子D、航向差因子W、道路拓撲因子T為變量的融合函數(shù)F(D,W，T)，融合函數(shù)具體表達式為

F(D，θ，T)=AP/D+AHW+ATT，

(5)

其中，AP(>0)是距離參數(shù)，投影距離D越小，權重越大，實驗表明AP取任何一個正數(shù)都可以得到很好的結果；AH為航向角參數(shù)，根據(jù)實驗取25有較好的匹配效果；AT為拓撲結構參數(shù)，當路網(wǎng)結構復雜時取1，否則取0.

2.1 定義域的確定

實驗采取定義誤差橢圓的方式確定融合函數(shù)的定義域，以降低計算復雜度.誤差橢圓由公式(6)(7)(8)計算.

(6)

(7)

(8)

其中，Φ是誤差橢圓的長半軸和Y軸正方向的夾角，a和b分別是橢圓的長半軸和短半軸，σx是GPS定位數(shù)據(jù)正東方向誤差的標準差，σy是GPS定位數(shù)據(jù)沿著Y軸正方向誤差的標準差，σxy和σ0分別是協(xié)方差和單位權值的方差.

2.2 融合函數(shù)流程圖

為展現(xiàn)基于融合函數(shù)構建的地圖匹配算法的工作原理，融合函數(shù)流程圖如圖2.首先將接收到的GPS數(shù)據(jù)進行預處理，以縮小數(shù)據(jù)處理量.然后核對GPS定位點是否在候選道路上，如果在就直接匹配；不在則分別依據(jù)距離因素、航向差因素以及拓撲結構因素判斷候選道路；如果都無法確定，則依據(jù)融合函數(shù)來確定候選道路并匹配定位點.

圖2 融合函數(shù)匹配流程圖

3 實驗驗證

為了對融合函數(shù)算法進行驗證，本文進行實驗仿真.實驗過程中，采用南京市出租車GPS定位數(shù)據(jù)為實驗數(shù)據(jù)，以matlab軟件為仿真工具，同時結合Google Earth來顯示電子地圖.實驗中，我們首先把某段時間內(nèi)接收到的帶有誤差的GPS數(shù)據(jù)導入到Google Earth中繪制成原始的行車路線圖，如圖3所示，其中黑色線條為道路交通網(wǎng)絡，黑色圓點為該段時間內(nèi)接收到的車輛定位信息.車輛是自西向東行駛，經(jīng)過一個路口后繼續(xù)向西，然后在第二個十路路口右拐.可以看出，原始定位信息是有一定偏差，尤其在交叉路口會出現(xiàn)信號漂移的現(xiàn)象.

下面我們運用地圖匹配算法對這些定位信息進行修正.首先，我們對原始數(shù)據(jù)進行預處理，剔除漂移點等不良信息.然后，運用融合函數(shù)匹配算法將剩余的GPS信號和電子地圖網(wǎng)絡之間進行匹配.最后，將匹配后的數(shù)據(jù)重新導入到Google Earth中，顯示出匹配后的路線效果，如圖4所示.可以看出，該算法能很好地去除信號漂移點，并且在十字路口、平行路段以及拐彎路段都有較好的匹配效果.

4 結語

地圖匹配算法較好解決了車輛導航系統(tǒng)定位的不確定性問題，有助于修正導航系統(tǒng)的定位誤差.融合函數(shù)的匹配算法實時有效，綜合考慮了距離、航向差及道路拓撲結構等因素，得到了最優(yōu)的位置估計信息，對于交叉路口的匹配具有較高的匹配精確度.

圖3 原始軌跡圖

圖4 融合函數(shù)匹配算法