改進的地圖匹配技術在車載導航系統(tǒng)中的應用

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

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

　　1地圖匹配的原理

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

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

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

　　2地圖匹配算法

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

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

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

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

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

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

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

　　3改進的地圖匹配方法

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

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

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

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

　　3.2車輛行駛路段的確定

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

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

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

　　規(guī)則1 當接收到電子地圖的標定信息如路徑規(guī)劃好的行車路線或者用戶自定義道路屬性類型代碼時，直接利用標定信息匹配到所規(guī)劃的道路路段上去；

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

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

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

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

　　加權因子q取值如下：

規(guī)則5.1 IF道路為禁行或禁止轉向或單行道的逆向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)如離開道路、電子地圖簡化后較為低級的道路描述不夠詳細、車輛進入停車場等情況，找不到可以匹配的行走路段THEN手動停止地圖匹配，用接收的原始數(shù)據(jù)直接顯示，不進行誤差矯正。

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

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

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

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

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

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

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

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

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

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

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

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

　　4實驗結果

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

　　第一種情況：車輛直行通過交叉路口，如圖3所示。

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

　　第二種情況：車輛拐彎通過交叉路口，如圖4所示。

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

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