一種改進(jìn)的地圖匹配技術(shù)在車(chē)載導航系統中的應用

0引 言

　　隨著(zhù)城市化的進(jìn)展和汽車(chē)的普及，交通擁擠加劇，交通事故頻發(fā)，交通環(huán)境惡化，這成為長(cháng)期以來(lái)困擾發(fā)展中國家和發(fā)達國家的嚴重問(wèn)題。解決此問(wèn)題的直接方法是提高路網(wǎng)的通行能力?？尚藿ü返目臻g有限，而且建設資金籌措困難。交通系統是復雜的大系統，我們應從系統論的觀(guān)點(diǎn)出發(fā)，把車(chē)輛和道路綜合起來(lái)考慮，運用各種高新技術(shù)系統解決交通問(wèn)題，智能交通系統(intelligent transport system)應運而生。

　　整個(gè)智能交通系統都以車(chē)輛的定位導航為核心，車(chē)輛導航系統是智能交通系統的中心部件，是其他各種功能應用的基礎。GPS或者GPS／INS或者GPS／DR方案以其結構簡(jiǎn)單、成本低廉、中高精度和良好的動(dòng)態(tài)性能等優(yōu)點(diǎn)，被廣泛的應用于車(chē)輛導航系統。本文就是實(shí)現組合定位，在應用地圖匹配(map matching，MM)定位技術(shù)進(jìn)行車(chē)輛定位，以便在行駛過(guò)程中為用戶(hù)提供準確可靠的實(shí)時(shí)定位信息，為智能交通管理系統的實(shí)現提供技術(shù)上的保障。

1地圖匹配的原理

　　地圖匹配是一種基于軟件技術(shù)的定位修正方法，其基本思想是將車(chē)輛定位軌跡與數字地圖中的道路網(wǎng)信息聯(lián)系起來(lái)，并由此相對于地圖確定車(chē)輛的位置。

　　地圖匹配應用是基于以下2個(gè)假設條件：

　　(1)車(chē)輛總是行駛在道路上；

　　(2)采用的道路數據精度要高于車(chē)載定位導航系統的定位精度。 當上述條件滿(mǎn)足時(shí)，就可以把定位數據和車(chē)輛運行軌跡同數字化地圖所提供的道路位置信息相比較，通過(guò)適當的匹配過(guò)程確定出車(chē)輛最可能的行駛路段以及車(chē)輛在該路段中的最大可能位置。如果上述假設不成立，則地圖匹配將產(chǎn)生錯誤的位置輸出，并可能導致系統性能的嚴重下降。一般認為用于匹配的數字地圖誤差不應超過(guò)巧米(真實(shí)地面距離)。由于陸地車(chē)輛在除進(jìn)入停車(chē)場(chǎng)等之外的絕大多數時(shí)間內都位于公路網(wǎng)絡(luò )中，因此使用地圖匹配技術(shù)的條件是滿(mǎn)足的。

2地圖匹配算法

　　地圖匹配的算法是曲線(xiàn)匹配原理和地理空間接近性分析方法的融合。曲線(xiàn)匹配算法的基本思想是：如果對一條曲線(xiàn)做任意數量、任意比例的分割，分割點(diǎn)都落在另一條曲線(xiàn)上，則兩條曲線(xiàn)嚴格匹配。實(shí)際應用中，就是計算一條曲線(xiàn)上相對均勻的某一數量分割點(diǎn)到參考曲線(xiàn)的距離的平均值，將其作為到參考曲線(xiàn)的平均距離，并將此平均距離的倒數作為匹配優(yōu)劣的度量?？臻g接近性分析方法就是在已知的可能正確的地理數據集中，按照空間最接近的方法匹配當前定位數據。

　　地圖匹配算法可分為2個(gè)相對獨立的過(guò)程：一是尋找車(chē)輛當前行駛的道路；二是將當前定位點(diǎn)投影到車(chē)輛行駛的道路上。其基本辦法是按照曲線(xiàn)匹配的思想在車(chē)輛航跡的鄰近區內搜索所有道路路段及其組合，把這些組合路線(xiàn)分別與車(chē)輛航跡求取匹配度量值，將取得最佳匹配度量值的組合路線(xiàn)作為車(chē)輛當前行駛路線(xiàn)。地圖匹配的常用算法有以下幾種：直接投影算法；相關(guān)性算法；半確定性算法；概率統計算法；模糊邏輯算法；基于計算幾何(非數值計算)知識(并暫時(shí)不考慮測量誤差)算法。

　　由于計算幾何知識算法不需要數據融合，極少需要考慮行車(chē)方向，非常直觀(guān)，并且減少了許多數值計算，具有極高的正確匹配率，能夠滿(mǎn)足快速、準確、實(shí)時(shí)地定位車(chē)輛位置的要求。因此，本系統選用基于計算幾何知識的地圖匹配算法。

　　基于計算幾何(非數值計算)知識(并暫不考慮測量誤差)，根據測量點(diǎn)位坐標有2種思路：

　　(1)不斷判斷剛測得的點(diǎn)位于道路的哪一側，如果剛測得的點(diǎn)與前期測得的某個(gè)點(diǎn)位于道路1的兩側，則車(chē)輛在道路1上行駛。如果道路1是一條彎曲的路徑，那么經(jīng)多次測量，并應用該方法也可以判斷車(chē)輛所處的道路。

　　(2)逐段計算測量點(diǎn)集的凸殼，依據道路與凸殼的交判斷車(chē)輛在哪條道路上行駛。

　　但當測量點(diǎn)全部位于1的同一側時(shí)，算法失敗。另該算法沒(méi)有考慮測量誤差，由此對GPS測量誤差的抗噪性差很有可能使算法失敗。

3改進(jìn)的地圖匹配方法

　　在算法設計時(shí)基于以下4個(gè)方面的考慮：一是效率，地圖匹配算法必須能夠滿(mǎn)足車(chē)輛導航實(shí)時(shí)、快速的要求；二是精度，地圖匹配的目的就是有效地提高車(chē)輛定位目標的精度，并保持定位結果的穩定性；三是不同交通狀況分別給出策略處理以提高道路選取得正確率和縮短匹配時(shí)間；四是程序設計，必須用可以量化的方式保證程序設計的可能性?；谏鲜隹紤]提出了以下的地圖匹配算法，算法分為3個(gè)步驟。

3.1數據預處理過(guò)程

　　利用各種規則形成的知識庫過(guò)濾掉異常定位數據，并對其進(jìn)行有效插值。主要考慮的因素有：GPS板提供的PDOP值(一般取PROP>6)、地圖范圍(預先確定車(chē)輛行駛的有效地理區域)，以及車(chē)輛的行駛速度等。其規則如下：

規則1 IF PDOP>6 THEN GPS數據異常，轉規則5；
規則2 IF Pos(L，B)NOT IN MapArea THENGPS數據異常，轉規則5；
規則3 IF Pos(V)>Const Car Speed THENGPS數據異常，轉規則5；
規則4 IF Pos(V)<Const Car Speed(設定Const=8 km／h)THEN GPS數據異常，轉規則5；
規則5 IF Car In隧道或立交橋THEN GPS數據異常；ELSE DR子系統啟動(dòng)獲取定位數據。

　　其中，MapArea為預先設定的車(chē)輛行駛的地理區域理論范圍；Pos(L，B)為當前車(chē)載GPS定位數據；Pos(V)為當前車(chē)輛行駛速度；Car Speed為預先設定的車(chē)輛行駛的最大理論值。

3.2車(chē)輛行駛路段的確定

　　美國取消SA干涉政策后，GPS的精度在正常狀況下小于25 m，在大部分路段可以直接投影獲得當前車(chē)輛行駛的道路。難于判斷的情況一般出現在車(chē)輛通視條件較差等原因引起的GPS定位精度降低或車(chē)輛在道路交叉口時(shí)。

　　令△Cdistance為GPS值與當前道路投影點(diǎn)之間的距離；△distance為GPS值與其他道路投影點(diǎn)之間的距離；MaxD為預先設定的搜索道路的距離閾值。閾值通常根據概率準則來(lái)確定，即必須以一定的概率包含車(chē)輛的實(shí)際位置。按照統計理論，可首先確定一個(gè)誤差橢圓：


 
　　車(chē)輛行駛路段的確定規則如下：

　　規則1 當接收到電子地圖的標定信息如路徑規劃好的行車(chē)路線(xiàn)或者用戶(hù)自定義道路屬性類(lèi)型代碼時(shí)，直接利用標定信息匹配到所規劃的道路路段上去；

　　規則2 IF在一定閾值內搜索到的道路數<1THEN車(chē)輛不在道路上，利用概率統計算法，可根據GPS的實(shí)時(shí)定位數據建立一個(gè)動(dòng)態(tài)可調的點(diǎn)緩沖區替代誤差橢圓，并利用誤差橢圓擴展因子的原理，設置緩沖區擴展比例因子，動(dòng)態(tài)可調的緩沖區半徑按30 m，60 m，90 m和120 m四個(gè)等級由小到大逐級搜索落入緩沖區內的道路路段。在GPS定位失效的情況下，必須用DR(航位推算)定位的誤差參數來(lái)代替GPS參數，完成誤差區域的定義，以保證匹配過(guò)程的連續性。此時(shí)，要注意由于DR推算具有誤差累積效應，隨著(zhù)推算過(guò)程的進(jìn)行，統計模型誤差、測量誤差和各種隨機誤差將會(huì )不斷累積。因此，在按DR定位的誤差參數定義誤差橢圓后，還應乘上適當的擴展因子來(lái)擴大誤差區域，以反映誤差累積對定位精度的影響。采用裁剪算法迅速判定侯選路段，通過(guò)計算不僅可以判知落入緩沖區內的路段，還可以求得路段與緩沖區的交點(diǎn)，從而取得GPS定位數據的匹配點(diǎn)坐標；

　　規則3 IF在一定閾值內搜索到的道路數=1THEN利用直接投影算法，把此道路作為車(chē)輛行駛的當前道路；

　　規則4 在一定閾值內搜索到的道路數>1&＆相同的道路節點(diǎn)號THEN車(chē)輛行駛在道路交叉口，根據交通狀況種別A，B，C，D劃分，采取對應策略，并利用相關(guān)性算法，計算測出軌跡與1組地圖數據的相關(guān)性系數，在所有候選地圖路線(xiàn)中與實(shí)際測出路線(xiàn)相關(guān)性最高的路線(xiàn)即為車(chē)輛行駛的真實(shí)路線(xiàn)；

　　規則5 在一定閾值內搜索到的道路數>1＆＆不同的道路節點(diǎn)號THEN車(chē)輛行駛在距離較近的平行道路之間，采用模糊邏輯算法中的利用距離和方向要素的線(xiàn)性組合方法，改進(jìn)算法，令p1+p2=1，并對p2參照模糊邏輯算法模式中的確定相似性度量函數的加權因子Q的模糊判決規則確定其值，然后計算基于曲線(xiàn)擬合的地圖匹配算法的相似性度量函數s，并選取最小值作為待匹配路段，即：在考慮角度和距離因素的情況下，該路段達到最優(yōu)。

加權因子q取值如下：

規則5.1 IF道路為禁行或禁止轉向或單行道的逆向THEN q=1.5*q；
規則5.2 IF已有路徑規劃且是路徑規劃路段THEN q=0.5*q；
規則5.3 IF道路與車(chē)輛的行駛方向一致THEN q=0.25*q。
規則6 IF發(fā)現如離開(kāi)道路、電子地圖簡(jiǎn)化后較為低級的道路描述不夠詳細、車(chē)輛進(jìn)入停車(chē)場(chǎng)等情況，找不到可以匹配的行走路段THEN手動(dòng)停止地圖匹配，用接收的原始數據直接顯示，不進(jìn)行誤差矯正。

3.3基于模糊邏輯的匹配路段可信度評判

　　以候選路段取向與車(chē)輛行駛方向的差(△heading，單位：度)值為論域X，令μhh(X)、μhc(x)為取向差(單位：度)的值x隸屬于模糊子集"路段與車(chē)輛行駛取向一致性好"和"路段與車(chē)輛行駛取向一致性差"的隸屬度，則μhh(X)、μhc(X)可取為：

　　在初始位置給定時(shí)，利用DR推算能夠準確地描述出車(chē)輛在短時(shí)間內的行駛軌跡。因此，可按如下方式定義候選路段形狀與當前車(chē)輛行駛軌跡的相似度：根據DR推算原理，現時(shí)刻tn的車(chē)輛位置(xn，yn)和車(chē)輛行駛取向θn可根據上一時(shí)刻tn-1的車(chē)輛位置(xn-1，yn-1)和行駛取向θn-1按下列公式推出：

　　式中：dn-1，n是tn-1到tn時(shí)刻車(chē)輛行駛過(guò)的距離，ωn-1，n是tn-1到tn時(shí)刻車(chē)輛行駛取向的變化量(dn-1，n和ωn-1，n均由車(chē)載位移傳感器和角速度傳感器提供)。取車(chē)輛當前定位位置p0(x，y)在候選路段上的投影點(diǎn)p′0(x′，y′)為tn時(shí)刻DR推算定位的參考位置，取候選路段取向為tn時(shí)刻的參考行駛取向，則由DR推算公式可反推出前一時(shí)刻的推算定位參考點(diǎn)。通過(guò)多次推算即可獲得一組參考點(diǎn)，具體數量可根據實(shí)際應用的要求確定。這里取參考點(diǎn)數目為5，則可定義候選路段與前5個(gè)單位時(shí)間內的DR定位軌跡平均距離差(單位：m)為： 

　　上述隸屬函數的圖形如圖1和圖2所示。 


 
　　以上述隸屬度函數為基礎，就可以對候選路段是當前車(chē)輛所在路段的可能性做出綜合評判。以該可能性作為論域U，其元素u與論域X，Y和Z的笛卡爾乘積集：


 
　　它的元素(x，y，z)相對應，即u與三個(gè)因素有關(guān)。因此，在對u進(jìn)行模糊評判時(shí)，因素集可以取為E={X，Y，Z)，評語(yǔ)集可取為F={大，小)，綜合評判按下面的步驟進(jìn)行：

　　(1)對u進(jìn)行單因素評價(jià)，然后利用其結果構造表示E與F之間模糊關(guān)系的模糊矩陣。設對因素X，Y，Z的單因素評價(jià)結果分別為模糊向量R1=[μhh(x)，μhc(x)]，R2=[μdh(y)，μdc(y)]和R3=[μ△dh(z)，μ△dc(z)]，則將以上模糊向量合在一起便得到表示E與F之間模糊關(guān)系的模糊矩陣 (2)確定權向量P=[p1，p2，p3]，其中p1，p2，p3分別表示因素x，y，z在亂中的重要程度，p1+p2+p3=1。

　　(3)作模糊變換Q=P°R，所得模糊向量Q就是被評判對象U在評語(yǔ)集合F上的評判結果，其2個(gè)分量表示候選路段是車(chē)輛所在路段的可能性大小的程度。

　　在以上綜合評判算法中，模糊矩陣乘法"°"采用簡(jiǎn)單的加權平均型算子(⊕，×)以便使結果兼顧各種因素。由于權向量的分量之和為1，運算⊕退化為一般的實(shí)數加法，因此算子(⊕，×)也可以改寫(xiě)成(+，×)。在這種情況下，模糊矩陣的乘法與普通矩陣的乘法完全一樣。

　　有了對候選路段是當前車(chē)輛行駛路段的可能性的評價(jià)，就可以對以候選路段位置為參考進(jìn)行地圖匹配修正后的定位結果的可信度做出評價(jià)。評判中，應考慮到候選路段與前一時(shí)刻匹配路段的連通性，為此再引入以下規則：如果候選路段就是前一時(shí)刻匹配路段或者與前一時(shí)刻的匹配路段相連通，則利用該候選路段修正定位結果的可信度高。以修正結果為評判對象，取評判指標矩陣為(Q，Q′)，其中Q是候選路段的可能性評價(jià)矩陣，Q′是連通性評價(jià)矩陣，當候選路段與前一時(shí)刻匹配路段有連通關(guān)系時(shí)，Q′取為前一時(shí)刻匹配路段的可能性評價(jià)矩陣，否則以0矩陣取代。取評判權向量為P′=[p′1，p′2，p′3，p′4]，其分量分別對應于Q和Q′的各個(gè)分量，且p′1+p′2+p′3+p′4=1。將指標矩陣與權向量相乘，得μ=p′°[Q，Q′]T，稱(chēng)μ是修正定位結果的可信度，它為挑選最佳匹配路段提供了明確的依據。

4實(shí)驗結果

　　交叉路口是地圖匹配過(guò)程中最易出錯的地方根據本文提出的改進(jìn)的地圖匹配算法理論，就交叉路口問(wèn)題做性能分析，下面分兩種情況討論。

　　第一種情況：車(chē)輛直行通過(guò)交叉路口，如圖3所示。

 
 
　　軌跡點(diǎn)4，5靠近路段1，但軌跡點(diǎn)1、2、3、4、5擬合所得直線(xiàn)遠遠偏離路段1，靠近路段2，因而軌跡點(diǎn)5會(huì )正確匹配到路段2，不會(huì )被錯誤地匹配到路段1。同理，軌跡點(diǎn)4也正確地匹配到路段2。由于考慮了軌跡的連續性，和基于位置點(diǎn)直接投影算法比起來(lái)，本文的算法不容易在交叉點(diǎn)出現匹配錯誤的情形。

　　第二種情況：車(chē)輛拐彎通過(guò)交叉路口，如圖4所示。

　　軌跡點(diǎn)1、2、3、4、5擬合得到的擬合直線(xiàn)1與路段2的夾角小于30度，點(diǎn)5被匹配到路段2。同理，2、3、4、5、6擬合得到的擬合直線(xiàn)2與路段2的夾角也小于30度，點(diǎn)6被匹配到路段2。從圖上可以看出，點(diǎn)5、6、7、8、9擬合得到的擬合直線(xiàn)5與路段1、2的夾角都大于30度，由算法基本原理可知，9不符合匹配條件，不予匹配。按照同樣方法對其他點(diǎn)一一進(jìn)行匹配。盡管在交叉路口附近會(huì )有少數的軌跡點(diǎn)不能被匹配，但匹配出來(lái)的軌跡能反映車(chē)輛的實(shí)際行駛軌跡，較好地處理了交叉路口的地圖匹配問(wèn)題。

　　為驗證文中提出的地圖匹配算法對導航系統定位精度的影響，利用該算法對跑車(chē)實(shí)測數據進(jìn)行了實(shí)驗。匹配結果表明，絕大多數(>96％)定位數據都能相對準確地匹配到道路上，匹配后的定位精度得到提高；匹配算法實(shí)現了實(shí)時(shí)，能夠滿(mǎn)足實(shí)際需要(1次／s)；在GPS受到一定程度的遮擋時(shí)系統能夠正常識別并且匹配。