GPS/DR組合導航的地圖粗匹配算法研究

晏 胤，黎福海

湖南大學 電氣與信息工程學院，長沙 410082

1 引言

隨著科技的發展，GPS導航越來越多的用在民用汽車導航領域。在信號正常的情況下，車載GPS產品的定位精度在20 m左右；在遇到高層建筑物、林蔭道、隧道、立交橋或者地下停車場時，車載GPS接收機接收到的信號將受到影響甚至出現中斷現象，這使得要獲得連續精確的導航定位信息，必須輔助其他的導航設備。

航位推算（Dead Reckoning，DR）是一種汽車自主式的導航定位技術，主要由方向傳感器、位移傳感器和高度傳感器組成。由于方向傳感器和位移傳感器的誤差隨時間的延長而積累，因此，在短時間內具有較高的精度，長時間單獨使用就會有較大的累積誤差。

GPS和DR兩者有很強的互補性，將兩者結合起來，可以保證系統能連續實時的為車輛提供較為精確的導航定位信息[1]。一方面，當GPS信號良好時，經過處理的GPS信號可以為DR糾正累積誤差，提高DR定位精度；一方面，當GPS信號不好時，可以適當地加大DR系統在導航定位中所占的比重，以提高整個系統的定位準確度。實際應用中，GPS/DR組合導航系統常常輔以地圖匹配（Map-Matching，MM）技術，實時的對組合導航系統輸出的信息[2]進行地圖匹配，可以將導航信息簡單、直觀地傳遞給駕駛者。

2 地圖匹配

2.1 地圖匹配技術

地圖匹配[3]的基本思想是將車輛的行駛軌跡與數字地圖中的道路對應起來，并確定車輛在道路網中的精確位置。因此，地圖匹配可以看成是兩個獨立的過程：一是確定車輛當前所在的行駛路段，簡稱粗匹配；二是將車輛精確定位到行駛路段上的一點，簡稱精匹配。地圖匹配是一種軟件技術的定位修正方法，其應用必須要有兩個前提：

（1）用于匹配的數字地圖包含高精度的道路位置信息及道路之間的聯通關系；

（2）被測車輛行駛在道路網中。

滿足上述兩個條件時，就可以把車輛的行駛軌跡與定位信息和數字地圖中的道路位置信息進行比較，并通過數據處理，確定車輛最可能的行駛道路和在該道路上的最大可能位置。

2.2 地圖匹配方法

目前常用于確定車輛當前所在的行駛路段的方法有直接投影法、相關性算法、概率統計法、模糊邏輯法等[4]。

直接投影法[5-6]是在車輛當前位置附近一定區域內查找最近的路段，直接將定位數據投影到此路段，投影點即為車輛的校正位置。此方法優點是簡單、易行，可以在一定程度上提高定位精度；缺點是穩定性差且效率低。

相關性算法[7-8]是利用特殊形狀（拐角、交叉等）對行車軌跡進行校正，在所有候選道路中，與實際測出路線相關性最高的路線定位車輛的真實行駛路線。傳統的相關性算法在航向改變大的情況下效果很好，但如果幾條候選線路相關性相差不大，就容易造成線路無法確定的缺陷。

概率統計法[9-10]是利用概率統計的方法設置一個置信區，把用來匹配的道路位置信息從中提取出來，并找出最佳匹配路段。此方法匹配的效率完全依靠數字地圖和GPS的精度，同時，還有一個缺陷就是算法沒有預定車輛一直在道路上，若偏離道路，將會產生積累誤差。

模糊邏輯法[11-12]是利用數字地圖匹配中所涉及的模糊度的定性決策過程，其特點是適用于絕大多數不同的路段，匹配效率高，實時性好，但建模參數缺乏理論依據，對慢車速和較大方向變化時匹配效果欠佳。

2.3 地圖粗匹配

要對在道路網中行駛的車輛進行精確定位，首先要確定車輛當前的行駛路段，即將車輛的行駛軌跡與道路網絡進行粗匹配。本文以直接投影法為基礎，結合相關性算法和概率統計法的優點，提出一種新的地圖粗匹配算法用來快速正確地選定車輛行車路段。

3 粗匹配算法

3.1 粗匹配算法總體設計

粗匹配算法選取與行車軌跡匹配程度最高的路段[13]作為當前行車路段，匹配程度用車輛定位點到候選路段之間的距離、行車方向與候選路段之間的方向偏差以及歷史匹配程度3個因素來衡量。車輛行駛軌跡與某條路段的匹配程度用下式計算：

式（1）對應的矩陣表達式如下：

假定在距離被定位車輛一定范圍內，有m條道路通過，對車輛的位置進行n次采樣。式（1）和式（2）中的各參數含義如下：M為當前匹配程度矩陣，mmn為第n個采樣點對第m條候選路段的匹配程度值；D為采樣點到候選路段之間的距離參數對角矩陣，d((m×n)(m×n))為第n個采樣點到第m條候選路段之間的距離參數值，α為距離參數的調整系數矩陣，αmn為對應采樣點到候選路段的調整系數；A為行車方向與候選路段方向的夾角參數對角矩陣，a((m×n)(m×n))為第n個采樣點行車方向與第m條候選路段方向的夾角參數值，β為行車方向與候選路段方向的夾角參數的調整系數矩陣，βmn為對應采樣點到候選路段的調整系數；M′為歷史匹配程度參數對角矩陣，m′((m×n)(m×n))第n個采樣點到第m條候選路段的歷史匹配程度參數值，γ為歷史匹配程度參數的調整系數矩陣，γmn為對應采樣點到候選路段的調整系數。

3.2 算法參數設置

3.2.1 距離參數及其調整系數

以采樣點為正方形中心，以200 m為邊長畫正方形，與這個正方形相交或在正方形內的所有路段為候選路段，若在此范圍內無候選路段，則說明車輛偏離道路較遠，不在道路網中行駛。Dij為車輛位置的第j個采樣點到候選路段第i條之間的距離，單位為米，Dmin為第j個采樣點到所有m條候選路段之間距離的最小值。

采樣點到路段的距離定義為采樣點到路段上所有點的最小值，分為3種情況：（1）采樣點在路段上，距離為0；（2）采樣點在路段外，過采樣點作路段的垂線，垂足在路段上，垂線段的長度即為距離d；（3）采樣點在路段外，垂足在路段的延長線上，采樣點與距垂足最近的那個端點的距離即為采樣點到路段的距離d1。如圖1所示，圖中距離的單位均為m。

圖1 點到線段距離

如圖1，車輛位置采樣點P由GPS測量位置數據經過濾波處理得到，由于目前GPS定位精度為20 m，設置參數d((i×j)(i×j))時，門限值選擇20 m比較合適；設置調整系數αij時，門限值選擇30 m和100 m比較合適。由于GPS的定位精度受實際使用環境影響，故選取調整系數時，通過多次仿真統計，將門限值擴大到距離門限值的1.5倍，當車輛位置采樣點到路段的距離小于30 m時，認為車輛在此路段的可能性非常高，調整系數取1；當大于100 m時，則若單獨考慮距離因素，車輛不可能在此路段上行駛，調整系數取0。距離參數及其調整系數都進行歸一化處理，其最大值均為1，以便對不同的道路的匹配程度有同一標準。

3.2.2 角度參數及其調整系數

Δθij為車輛在第j個采樣點的綜合行駛方向與第i條候選路段方向之間的夾角，單個GPS測向需要進行多點采樣并統計采樣點的位置，花費時間較多，而兩臺GPS測向又增加了設備成本，且車輛長度不大，導致的測向精度也不高。目前常用的低精度DR測向能控制在2°范圍之內，根據概率分布的3倍標準差原則，考慮到實際應用環境，設置參數a((i×j)(i×j))時，選取門限值 6°；設置調整系數βij時，選取門限值為15°和60°。當夾角小于15°時，車輛在此路段行駛的可能性很高，調整系數取1；當夾角大于60°時，車輛在此路段行駛的可能性非常低，調整系數取0。角度參數及其調整系數同樣運用歸一化原理，各自的最大值均為1。

3.2.3 歷史匹配參數及其調整系數

m′((i×j)(i×j))表示第j個采樣點對第i條候選路段的歷史匹配參數值，mik表示第k個采樣點對第i條路段匹配程度值，第一個采樣點對任何候選路段的歷史匹配參數取0，γij為對應的調整系數值。同時，根據控制k的值來控制歷史匹配點數對當前匹配程度的影響，這樣可以根據需要選取不同的窗口長度，滿足不同的道路速度需求。

4 仿真分析

4.1 粗匹配算法理論仿真與統計分析

衡量粗匹配算法的兩項標準是時效性和正確率，根據鄰近路段的密集性和與實際行駛路段的相似性[14]，模擬實際道路路況，將實際路況分6種情況進行仿真分析，同時，對各種不同的道路路況按3種不同的采樣點數進行匹配正確率統計比較，其結果如表1所示。

各種路況所代表的與實際行駛路段相似的道路信息如下：

路況1表示鄰近路段有一條道路與實際行駛路段平行，且與行駛路段的距離為20 m；

路況2表示鄰近路段有一條道路與實際行駛路段的夾角為10°，且在車輛行駛位置附近與行駛路段相交；

路況3為路況1和路況2的組合，且兩條相似道路分居在實際行駛路段的兩邊；

路況4表示鄰近路段有一條道路與實際行駛路段平行，且與行駛路段的距離為40 m；

路況5表示鄰近路段有一條道路與實際行駛路段的夾角為20°，且在車輛行駛位置附近與行駛路段相交；

路況6為路況4和路況5的組合，且兩條相似道路分居在實際行駛路段的兩邊。

每種路況類型進行3種不同的采樣點數的匹配，每個采樣點的時間間隔為1 s，與GPS的數據更新時間一致。假定定位車輛在道路上的行駛速度為20 m/s，即每個采樣點的間隔為20 m，表中的每個匹配正確率數據是經過50 000次的仿真后進行數理統計得到的平均值。從表中橫向數據可以看出，總體的匹配正確率隨采樣點數的增加而增加，采樣點數越多，匹配的穩定性越好；從縱向數據可以看出，在相似性和密集程度大大超出現實生活中道路類型路況3中，只需5 s的采樣匹配時間，就能讓算法的正確率保持在99%以上。路況3的單次匹配仿真圖如圖2所示；路況6的仿真條件滿足絕大多數的現實道路，將其作為實際路況的類型，其單次匹配仿真如圖3所示。

圖2 路況3匹配效果

圖3 況6匹配效果

圖2、圖3中，紅色的線段為單次仿真匹配出的路段，與實際行駛路段一致，藍色的“*”為5個采樣點。從實際仿真的數據統計可以看出，滿足絕大多數實際路況條件的路況6，3個采樣點的采樣時間為3 s，匹配的正確率超過99%，在匹配時效和正確率兩方面有著良好的兼容性。

4.2 實際路況模擬驗證

由于開闊地帶的道路信息相對比較簡單，對算法的實用性好壞檢驗說服力不強，故選取路況復雜程度較高的城區道路作為本次模擬仿真的行駛區域，將長沙市岳麓區湖南大學附近區域作為驗證算法匹配的地圖區域，其電子地圖界面如圖4所示。

圖4 匹配區域電子地圖

將圖4中的道路信息提取出來，并經過坐標轉換[15]，使其在二維坐標系中的位置坐標信息如圖5所示。

圖5 坐標轉換圖

車輛從E點出發，沿EN方向前進，如圖中紅色箭頭所示，其粗匹配效果如圖6所示。

圖6 際路況模擬粗匹配

圖6中，藍色的圓圈“o”為車輛的真實位置，紅色的星號“*”為車輛的GPS定位位置，紅色的線段是粗匹配算法選定的行車路段，與實際的行車路段一致，證明算法在模擬實際的行車路段時，一般的路況條件下，3個采樣點即只需要3 s的時間就能確定車輛的行車路段，時效性和準確率得到良好的兼顧。

4.3 匹配時效性比較

選取同樣的道路狀況和傳感器定位精度，考慮到實際的道路寬度和城市道路環境影響，將GPS的定位精度取為50 m，本文粗匹配算法分別與垂直投影匹配算法、歷史軌跡推算匹配法、自適應匹配算法進行匹配時間和匹配準確率的比較[16]，其比較數據如表2所示。

表2 不同粗匹配算法匹配時效性、準確率比較

從表2可以看出，在同樣的路況條件下，采用相同精度的傳感器設備，本文算法加入了電子羅盤，引入航向信息，只需要7個采樣點的時間就能保證91%的正確率，與表中其他算法相比，大大節省了選路時間，加快了車輛的選路過程，并在一定程度上提高了匹配的準確率。

5 結論

簡單介紹了GPS與DR的基本工作原理及各自的誤差分析，將地圖匹配分為粗匹配和精匹配兩個階段，并設計了粗匹配的算法。結合目前GPS和DR產品的精度和實際道路情況，對算法參數進行了合理設定。按照多點采樣原則對算法進行迭代，通過Matlab仿真測試和正確率統計分析，證明了匹配的正確率和穩定性隨采樣點數的增加而提高，與其他匹配算法相比，方向傳感器引入的測向參數大大加快了車輛的選路過程，節省了選路時間。綜合考慮粗匹配算法的時效性和正確率，選取5個采樣點能很好的滿足日常的定位需求，為后續的精匹配奠定了良好的基礎，為數字地圖匹配和車輛精確定位提供了一定的理論依據。

[1]寇艷紅，張其善，李先亮.車載GPS/DR組合導航系統的數據融合算法[J].北京航空航天大學學報，2003，29（3）：264-268.

[2]常青，鄭平方，柳重堪，等.車載GPS/DR組合導航系統數據融合算法研究[J].通信學報，2000，21（2）：42-48.

[3]Jingyu H，Xiong F，Linfeng L，et al.Online map matching by indexing approximate road segments[C]//Proceedings of IEEE 2nd International Conference on Software Engineering and Service Science，2011.

[4]方偉駿，黃圣國.GPS/MM車載導航系統的研究與實現[J].微計算機信息，2007，23（25）：215-216.

[5]Liu Z，Hu D，Feng G.Visual tracking based on direct orthogonal locality preserving projections.2012.

[6]蘇奎峰，鄧志東，黃振.基于曲率特征的自主車輛地圖匹配定位方法[J].機器人，2012，34（4）：440-448.

[7]Bernoulli T，Krammer M，Walder U，et al.Improvement of inertial sensor based indoor navigation by video content analysis[C]//Proceedings of International Conference on Indoor Positioning and Indoor Navigation，21-23 Sept，2011.

[8]Fanming L，Dong Q.A matching algorithm for GGI aided navigation where reference map is obtained by forward method[C]//Proceedings of IEEE International Conference on Information and Automation，20-23 June，2010.

[9]彭飛，柳重堪，張其善.基于代價函數的組合導航系統地圖匹配算法[J].北京航空航天大學學報，2002，28（3）：261-264.

[10]荊濤.車輛導航系統中地圖匹配的研究[J].鐵路計算機應用，2008，17（7）：1-5.

[11]張小國，何坤賢，王慶.一種移動對象數據庫的自適應更新方法[J].小型微型計算機系統，2010，31（12）：2331-2336.

[12]宋潔，李國燕，李娜娜，等.基于模糊邏輯的GPS/DR地圖匹配算法[J].計算機工程與科學，2008，30（10）：30-32.

[13]楊殿閣，連小珉，張濤，等.基于北斗衛星的車輛組合導航系統開發[J].清華大學學報：自然科學版，2008，48（5）：856-859.

[14]曾波，江資斌.GPS車載導航系統的地圖匹配算法[J].測繪工程，2004，13（3）：65-67.

[15]謝寧.GPS坐標轉換方法的精度對比分析[J].硅谷，2011（4）：30-41.

[16]靳松杰.GPS車輛導航定位系統及自適應地圖匹配算法的研究[D].西安：西安電子科技大學，2007.