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

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

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

　　1地圖匹配的原理

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

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

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

　　2地圖匹配算法

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

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

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

　　基于計(jì)算幾何(非數(shù)值計(jì)算)知識(shí)(并暫不考慮測(cè)量誤差)，根據(jù)測(cè)量點(diǎn)位坐標(biāo)有2種思路：

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

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

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

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

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

　　3.1數(shù)據(jù)預(yù)處理過(guò)程

　　利用各種規(guī)則形成的知識(shí)庫(kù)過(guò)濾掉異常定位數(shù)據(jù)，并對(duì)其進(jìn)行有效插值。主要考慮的因素有：GPS板提供的PDOP值(一般取PROP>6)、地圖范圍(預(yù)先確定車(chē)輛行駛的有效地理區(qū)域)，以及車(chē)輛的行駛速度等。其規(guī)則如下：
規(guī)則1 IF PDOP>6 THEN GPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；
規(guī)則2 IF Pos(L，B)NOT IN MapArea THENGPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；
規(guī)則3 IF Pos( V)>Const Car Speed THENGPS數(shù)據(jù)異常，轉(zhuǎn)規(guī)則5；
規(guī)則4 IF Pos(V)規(guī)則5 IF Car In隧道或立交橋THEN GPS數(shù)據(jù)異常；ELSE DR子系統(tǒng)啟動(dòng)獲取定位數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

　　規(guī)則5 在一定閾值內(nèi)搜索到的道路數(shù)>1＆＆不同的道路節(jié)點(diǎn)號(hào)THEN車(chē)輛行駛在距離較近的平行道路之間，采用模糊邏輯算法中的利用距離和方向要素的線性組合方法，改進(jìn)算法，令p1+p2=1，并對(duì)p2參照模糊邏輯算法模式中的確定相似性度量函數(shù)的加權(quán)因子Q的模糊判決規(guī)則確定其值，然后計(jì)算基于曲線擬合的地圖匹配算法的相似性度量函數(shù)s，并選取最小值作為待匹配路段，即：在考慮角度和距離因素的情況下，該路段達(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道路與車(chē)輛的行駛方向一致THEN q="0".25*q。
規(guī)則6 IF發(fā)現(xiàn)如離開(kāi)道路、電子地圖簡(jiǎn)化后較為低級(jí)的道路描述不夠詳細(xì)、車(chē)輛進(jìn)入停車(chē)場(chǎng)等情況，找不到可以匹配的行走路段THEN手動(dòng)停止地圖匹配，用接收的原始數(shù)據(jù)直接顯示，不進(jìn)行誤差矯正。

　　3.3基于模糊邏輯的匹配路段可信度評(píng)判

　　以候選路段取向與車(chē)輛行駛方向的差(△heading，單位：度)值為論域X，令μhh(X)、μhc(x)為取向差(單位：度)的值x隸屬于模糊子集"路段與車(chē)輛行駛?cè)∠蛞恢滦院?quot;和"路段與車(chē)輛行駛?cè)∠蛞恢滦圆?quot;的隸屬度，則μhh(X)、μhc(X)可取為：

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

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

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

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

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

　　(1) 對(duì)u進(jìn)行單因素評(píng)價(jià)，然后利用其結(jié)果構(gòu)造表示E與F之間模糊關(guān)系的模糊矩陣。設(shè)對(duì)因素X，Y，Z的單因素評(píng)價(jià)結(jié)果分別為模糊向量R1= [μhh(x)，μhc(x)]，R2=[μdh(y)，μdc(y)]和R3=[μ△dh(z)，μ△dc(z)]，則將以上模糊向量合在一起便得到表示E與F之間模糊關(guān)系的模糊矩陣 

　　(2)確定權(quán)向量P=[p1，p2，p3]，其中p1，p2，p3分別表示因素x，y，z在亂中的重要程度，p1+p2+p3=1。

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

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

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

　　4實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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