一種改進(jìn)的地圖匹配技術(shù)在車載導(dǎo)航系統(tǒng)中的應(yīng)用

1、    一種改進(jìn)的地圖匹配技術(shù)在車載導(dǎo)航系統(tǒng)中的應(yīng)用0引言隨著城市化的進(jìn)展和汽車的普及，交通擁擠加劇，交通事故頻發(fā)，交通環(huán)境惡化，這成為長期以來困擾發(fā)展中國家和發(fā)達(dá)國家的嚴(yán)重問題。解決此問題的直接方法是提高路網(wǎng)的通行能力。可修建公路的空間有限，而且建設(shè)資金籌措困難。交通系統(tǒng)是復(fù)雜的大系統(tǒng)，我們應(yīng)從系統(tǒng)論的觀點(diǎn)出發(fā)，把車輛和道路綜合起來考慮，運(yùn)用各種高新技術(shù)系統(tǒng)解決交通問題，智能交通系統(tǒng)(intelligenttransportsystem)應(yīng)運(yùn)而生。整個智能交通系統(tǒng)都以車輛的0引 言隨著城市化的進(jìn)展和汽車的普及，交通擁擠加劇，交通事故頻發(fā)，交通環(huán)境惡化，

2、這成為長期以來困擾發(fā)展中國家和發(fā)達(dá)國家的嚴(yán)重問題。解決此問題的直接方法是提高路網(wǎng)的通行能力?？尚藿ü返目臻g有限，而且建設(shè)資金籌措困難。交通系統(tǒng)是復(fù)雜的大系統(tǒng)，我們應(yīng)從系統(tǒng)論的觀點(diǎn)出發(fā)，把車輛和道路綜合起來考慮，運(yùn)用各種高新技術(shù)系統(tǒng)解決交通問題，智能交通系統(tǒng)(intelligent     transport system)應(yīng)運(yùn)而生。整個智能交通系統(tǒng)都以車輛的定位導(dǎo)航為核心，車輛導(dǎo)航系統(tǒng)是智能交通系統(tǒng)的中心部件，是其他各種功能應(yīng)用的基礎(chǔ)。GPS或者GPSINS或者GPSDR方案以其結(jié)構(gòu)簡單、成本低廉、中高精度和良好的動態(tài)性能等優(yōu)點(diǎn)，被廣泛的應(yīng)用于車輛導(dǎo)航

3、系統(tǒng)。本文就是實(shí)現(xiàn)組合定位，在應(yīng)用地圖匹配(mapmatching，MM)定位技術(shù)進(jìn)行車輛定位，以便在行駛過程中為用戶提供準(zhǔn)確可靠的實(shí)時定位信息，為智能交通管理系統(tǒng)的實(shí)現(xiàn)提供技術(shù)上的保障。1地圖匹配的原理地圖匹配是一種基于軟件技術(shù)的定位修正方法，其基本思想是將車輛定位軌跡與數(shù)字地圖中的道路網(wǎng)信息聯(lián)系起來，并由此相對于地圖確定車輛的位置。地圖匹配應(yīng)用是基于以下2個假設(shè)條件：(1)車輛總是行駛在道路上；(2)采用的道路數(shù)據(jù)精度要高于車載定位導(dǎo)航系統(tǒng)的定位精度。 當(dāng)上述條件滿足時，就可以把定位數(shù)據(jù)和車輛運(yùn)行軌跡同數(shù)字化地圖所提供的道路位置信息相比較，通過適當(dāng)?shù)钠ヅ溥^程確定出車輛最可能的行駛路段以及車

4、輛在該路段中的最大可能位置。如果上述假設(shè)不成立，則地圖匹配將產(chǎn)生錯誤的位置輸出，并可能導(dǎo)致系統(tǒng)性能的嚴(yán)重下降。一般認(rèn)為用于匹配的數(shù)字地圖誤差不應(yīng)超過巧米(真實(shí)地面距離)。由于陸地車輛在除進(jìn)入停車場等之外的絕大多數(shù)時間內(nèi)都位于公路網(wǎng)絡(luò)中，因此使用地圖匹配技術(shù)的條件是滿足的。2地圖匹配算法地圖匹配的算法是曲線匹配原理和地理空間接近性分析方法的融合。曲線匹配算法的基本思想是：如果對一條曲線做任意數(shù)量、任意比例的分割，分割點(diǎn)都落在另一條曲線上，則兩條曲線嚴(yán)格匹配。實(shí)際應(yīng)用中，就是計(jì)算一條曲線上相對均勻的某一數(shù)量分割點(diǎn)到參考曲線的距離的平均值，將其作為到參考曲線的平均距離，并將此平均距離的倒數(shù)作為匹配優(yōu)

5、劣的度量?？臻g接近性分析方法就是在已知的可能正確的地理數(shù)據(jù)集中，按照空間最接近的方法匹配當(dāng)前定位數(shù)據(jù)。地圖匹配算法可分為2個相對獨(dú)立的過程：一是尋找車輛當(dāng)前行駛的道路；二是將當(dāng)前定位點(diǎn)投影到車輛行駛的道路上。其基本辦法是按照曲線匹配的思想在車輛航跡的鄰近區(qū)內(nèi)搜索所有道路路段及其組合，把這些組合路線分別與車輛航跡求取匹配度量值，將取得最佳匹配度量值的組合路線作為車輛當(dāng)前行駛路線。地圖匹配的常用算法有以下幾種：直接投影算法；相關(guān)性算法；半確定性算法；概率統(tǒng)計(jì)算法；模糊邏輯算法；基于計(jì)算幾何(非數(shù)值計(jì)算)知識(并暫時不考慮測量誤差)算法。由于計(jì)算幾何知識算法不需要數(shù)據(jù)融合，極少需要考慮行車方向，非常

6、直觀，并且減少了許多數(shù)值計(jì)算，具有極高的正確匹配率，能夠滿足快速、準(zhǔn)確、實(shí)時地定位車輛位置的要求。因此，本系統(tǒng)選用基于計(jì)算幾何知識的地圖匹配算法。基于計(jì)算幾何(非數(shù)值計(jì)算)知識(并暫不考慮測量誤差)，根據(jù)測量點(diǎn)位坐標(biāo)有2種思路：(1)不斷判斷剛測得的點(diǎn)位于道路的哪一側(cè)，如果剛測得的點(diǎn)與前期測得的某個點(diǎn)位于道路1的兩側(cè)，則車輛在道路1上行駛。如果道路1是一條彎曲的路徑，那么經(jīng)多次測量，并應(yīng)用該方法也可以判斷車輛所處的道路。(2)逐段計(jì)算測量點(diǎn)集的凸殼，依據(jù)道路與凸殼的交判斷車輛在哪條道路上行駛。但當(dāng)測量點(diǎn)全部位于1的同一側(cè)時，算法失敗。另該算法沒有考慮測量誤差，由此對GPS測量誤差的抗噪性差很有

7、可能使算法失敗。3改進(jìn)的地圖匹配方法在算法設(shè)計(jì)時基于以下4個方面的考慮：一是效率，地圖匹配算法必須能夠滿足車輛導(dǎo)航實(shí)時、快速的要求；二是精度，地圖匹配的目的就是有效地提高車輛定位目標(biāo)的精度，并保持定位結(jié)果的穩(wěn)定性；三是不同交通狀況分別給出策略處理以提高道路選取得正確率和縮短匹配時間；四是程序設(shè)計(jì)，必須用可以量化的方式保證程序設(shè)計(jì)的可能性?；谏鲜隹紤]提出了以下的地圖匹配算法，算法分為3個步驟。3.1數(shù)據(jù)預(yù)處理過程利用各種規(guī)則形成的知識庫過濾掉異常定位數(shù)據(jù)，并對其進(jìn)行有效插值。主要考慮的因素有：GPS板提供的PDOP值(一般取PROP>6)、地圖范圍(預(yù)先確定車輛行駛的有效地理區(qū)域)，以及

8、車輛的行駛速度等。其規(guī)則如下：規(guī)則1 IF PDOP>6 THEN GPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；規(guī)則2 IFPos(L，B)NOT IN MapArea THENGPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；規(guī)則3 IF Pos(V)>ConstCarSpeed THENGPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；規(guī)則4 IF Pos(V)<Const Car Speed(設(shè)定Const=8 kmh)THEN GPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；規(guī)則5 IF Car In隧道或立交橋THEN GPS數(shù)據(jù)異常；ELSE DR子系統(tǒng)啟動獲取定位數(shù)據(jù)。其中，MapArea為預(yù)先設(shè)定的車輛行駛的地理區(qū)域理論范圍；Pos(L，

9、B)為當(dāng)前車載GPS定位數(shù)據(jù)；Pos(V)為當(dāng)前車輛行駛速度；Car     Speed為預(yù)先設(shè)定的車輛行駛的最大理論值。3.2車輛行駛路段的確定美國取消SA干涉政策后，GPS的精度在正常狀況下小于25 m，在大部分路段可以直接投影獲得當(dāng)前車輛行駛的道路。難于判斷的情況一般出現(xiàn)在車輛通視條件較差等原因引起的GPS定位精度降低或車輛在道路交叉口時。令Cdistance為GPS值與當(dāng)前道路投影點(diǎn)之間的距離；distance為GPS值與其他道路投影點(diǎn)之間的距離；MaxD為預(yù)先設(shè)定的搜索道路的距離閾值。閾值通常根據(jù)概率準(zhǔn)則來確定，即必須以一定的概率包含車輛的實(shí)際

10、位置。按照統(tǒng)計(jì)理論，可首先確定一個誤差橢圓：車輛行駛路段的確定規(guī)則如下：規(guī)則1 當(dāng)接收到電子地圖的標(biāo)定信息如路徑規(guī)劃好的行車路線或者用戶自定義道路屬性類型代碼時，直接利用標(biāo)定信息匹配到所規(guī)劃的道路路段上去；規(guī)則2 IF在一定閾值內(nèi)搜索到的道路數(shù)<1THEN車輛不在道路上，利用概率統(tǒng)計(jì)算法，可根據(jù)GPS的實(shí)時定位數(shù)據(jù)建立一個動態(tài)可調(diào)的點(diǎn)緩沖區(qū)替代誤差橢圓，并利用誤差橢圓擴(kuò)展因子的原理，設(shè)置緩沖區(qū)擴(kuò)展比例因子，動態(tài)可調(diào)的緩沖區(qū)半徑按30     m，60 m，90 m和120 m四個等級由小到大逐級搜索落入緩沖區(qū)內(nèi)的道路路段。在GPS定位失效的情況下，

11、必須用DR(航位推算)定位的誤差參數(shù)來代替GPS參數(shù)，完成誤差區(qū)域的定義，以保證匹配過程的連續(xù)性。此時，要注意由于DR推算具有誤差累積效應(yīng)，隨著推算過程的進(jìn)行，統(tǒng)計(jì)模型誤差、測量誤差和各種隨機(jī)誤差將會不斷累積。因此，在按DR定位的誤差參數(shù)定義誤差橢圓后，還應(yīng)乘上適當(dāng)?shù)臄U(kuò)展因子來擴(kuò)大誤差區(qū)域，以反映誤差累積對定位精度的影響。采用裁剪算法迅速判定侯選路段，通過計(jì)算不僅可以判知落入緩沖區(qū)內(nèi)的路段，還可以求得路段與緩沖區(qū)的交點(diǎn)，從而取得GPS定位數(shù)據(jù)的匹配點(diǎn)坐標(biāo)；規(guī)則3 IF在一定閾值內(nèi)搜索到的道路數(shù)=1THEN利用直接投影算法，把此道路作為車輛行駛的當(dāng)前道路；規(guī)則4 在一定閾值內(nèi)搜索到的道路數(shù)>

12、;1&amp;相同的道路節(jié)點(diǎn)號THEN車輛行駛在道路交叉口，根據(jù)交通狀況種別A，B，C，D劃分，采取對應(yīng)策略，并利用相關(guān)性算法，計(jì)算測出軌跡與1組地圖數(shù)據(jù)的相關(guān)性系數(shù)，在所有候選地圖路線中與實(shí)際測出路線相關(guān)性最高的路線即為車輛行駛的真實(shí)路線；規(guī)則5 在一定閾值內(nèi)搜索到的道路數(shù)>1不同的道路節(jié)點(diǎn)號THEN車輛行駛在距離較近的平行道路之間，采用模糊邏輯算法中的利用距離和方向要素的線性組合方法，改進(jìn)算法，令p1+p2=1，并對p2參照模糊邏輯算法模式中的確定相似性度量函數(shù)的加權(quán)因子Q的模糊判決規(guī)則確定其值，然后計(jì)算基于曲線擬合的地圖匹配算法的相似性度量函數(shù)s，并選取最小值作為待匹配路段

13、，即：在考慮角度和距離因素的情況下，該路段達(dá)到最優(yōu)。加權(quán)因子q取值如下：規(guī)則5.1 IF道路為禁行或禁止轉(zhuǎn)向或單行道的逆向THEN q=1.5*q；規(guī)則5.2 IF已有路徑規(guī)劃且是路徑規(guī)劃路段THEN q=0.5*q；規(guī)則5.3 IF道路與車輛的行駛方向一致THEN q=0.25*q。規(guī)則6 IF發(fā)現(xiàn)如離開道路、電子地圖簡化后較為低級的道路描述不夠詳細(xì)、車輛進(jìn)入停車場等情況，找不到可以匹配的行走路段THEN手動停止地圖匹配，用接收的原始數(shù)據(jù)直接顯示，不進(jìn)行誤差矯正。3.3基于模糊邏輯的匹配路段可信度評判以候選路段取向與車輛行駛方向的差(heading，單位：度)值為論域X，令hh(X)、hc(x)為取向差(單位：度)的值x隸屬于模糊子集"路段與車輛行駛?cè)∠蛞恢滦院?quot;和"路段與車輛行駛?cè)∠蛞恢滦圆?quot;的隸屬度，則hh(X)、hc(X)可取為：在初始位置給定時，利用DR推算能夠準(zhǔn)確地描述出車輛在短時間內(nèi)的行駛軌跡。因此，可按如下方式定義候選路段形狀與當(dāng)前車輛行駛軌跡的相似度：根據(jù)DR推算原理，現(xiàn)時刻tn的車輛位置(xn，yn)和車輛行駛?cè)∠騨可根據(jù)上一時刻tn-1的車輛位置(xn-1，yn-1)和行駛?cè)∠騨-1按下列公式推出：式中：dn-1，n是tn-1到tn時刻車輛行駛過的距離，n-1，n是tn-1到tn時刻車輛行駛?cè)∠虻淖兓?dn-1，n