基于融合函數構建的GPS車輛軌跡地圖匹配算法

陳 濱

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

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

1 匹配因素分析

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

1.1 距離因素

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

(1)

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

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

(2)

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

1.2 航向差因素

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

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

(3)

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

(4)

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

1.3 路網拓撲結構因素

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

圖1 路網拓撲結構示意圖

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

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

2 融合函數構建

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

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

(5)

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

2.1 定義域的確定

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

(6)

(7)

(8)

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

2.2 融合函數流程圖

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

圖2 融合函數匹配流程圖

3 實驗驗證

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

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

4 結語

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

圖3 原始軌跡圖

圖4 融合函數匹配算法