劉 峰，郭 陽，鄭 辛，李殿茜

(1.北京自動化控制設(shè)備研究所，北京 100074；2.國防科技大學(xué)，長沙 410000；3.中國航天科工集團有限公司，北京 100048)

0 引言

隨著車載導(dǎo)航技術(shù)的發(fā)展，各種定位定向技術(shù)在車載導(dǎo)航系統(tǒng)中都得到了成功的應(yīng)用，如衛(wèi)星定位技術(shù)、慣性導(dǎo)航(Inertial Navigation System，INS)技術(shù)、航位推算(Dead Reckoning，DR)技術(shù)、無線電技術(shù)等，但每一種技術(shù)都有其無法克服的局限性。例如當(dāng)車輛通過涵洞、隧道、立交橋時，或者衛(wèi)星接收機受到遮擋、干擾時，導(dǎo)致衛(wèi)星無法正常定位；受陀螺漂移、加速度計零偏等慣性器件誤差的影響，慣性定位定向的定位誤差會隨著行駛時間和行駛距離的增加而增大。采用地圖匹配(Map Matching)技術(shù)提升定位定向系統(tǒng)的定位精度，具有不需要增添新的硬件、成本低、能有效抑制誤差發(fā)散等優(yōu)點。因此對地圖匹配相關(guān)技術(shù)展開研究具有重要意義。

地圖匹配是一種基于軟件技術(shù)的定位誤差修正技術(shù)，依靠精確的數(shù)字地圖道路信息和地圖匹配算法實現(xiàn)道路信息與車輛定位信息之間的匹配。本文將從地圖匹配的基本原理出發(fā)，針對點到線型地圖匹配方法的局限性，提出了一種基于道路幾何特征的地圖匹配方法，并進行試驗驗證。

1 地圖匹配原理

1.1 地圖匹配基本原理

地圖匹配的基本原理具體來說就是以某個車輛的定位點或某段車輛的定位軌跡作為待匹配樣本，將該點或該軌跡曲線附近的所有道路上的位置點或道路曲線作為模板，通過待匹配樣本與模板間的匹配，選擇相似度最高的模板作為匹配結(jié)果，然后根據(jù)匹配結(jié)果，校正系統(tǒng)的定位輸出，從而獲取正確的行駛路線。圖1所示為地圖匹配原理圖，通過慣性定位定向系統(tǒng)測得車輛位置或行駛軌跡，與數(shù)字矢量地圖的道路數(shù)據(jù)進行比較，經(jīng)過地圖匹配后，找到車輛所在的道路，并且確定車輛在道路上的具體位置。

圖1 地圖匹配原理圖Fig.1 Map-matching principle diagram

地圖匹配可以看作是一個模式識別的過程。一個完整的地圖匹配算法一般包括3個過程：1)確定誤差區(qū)域，找出車輛附近所有待匹配的候選路段；2)從所有候選路段中確定車輛所行駛路段，即匹配路段；3)確定車輛在道路上的具體位置，即匹配點。

1.2 典型地圖匹配實現(xiàn)方法介紹

通常所謂的地圖匹配方法的不同，往往指的是確定匹配路段也就是尋找車輛所在的道路采用的方法不同，對于車輛在路段上的具體位置，確定方法相對比較單一。大多數(shù)算法在找到車輛當(dāng)前行駛的路段后，只是將定位點往路段上簡單地作投影，將投影點作為車輛在道路上的匹配點，實際屬于點到線型的地圖匹配方法。

目前典型的地圖匹配算法有垂直投影法、概率統(tǒng)計法、相關(guān)性算法、基于網(wǎng)絡(luò)拓撲關(guān)系算法和基于權(quán)重的算法等。這幾種典型地圖匹配算法的優(yōu)缺點、適用范圍等如表1所示。

表1 典型地圖匹配算法比較Tab.1 Typical map-matching algorithm comparisons

2 基于道路幾何特征的地圖匹配方法

點到線式的地圖匹配算法，是以比較定位點到道路的投影距離作為匹配路段選取的重要標(biāo)準(zhǔn)，這要求只有定位精度較高時才能匹配到正確的道路上，多用于輔助衛(wèi)星導(dǎo)航定位。而且該方法只能抑制垂直于道路方向的誤差，但難以修正沿道路方向上的誤差。另外，每個定位點往往獨立匹配，并沒有充分利用歷史匹配信息，當(dāng)遇到野點時，容易出現(xiàn)誤匹配，從而影響系統(tǒng)的可靠性及匹配精度。

不同于GPS衛(wèi)星導(dǎo)航，當(dāng)車輛采用慣性導(dǎo)航時，行駛過程中的定位軌跡為連續(xù)平滑的曲線，并且行駛一段里程或經(jīng)過特殊路況(如拐彎、轉(zhuǎn)盤等)時，軌跡往往具有明顯的幾何形狀。在對匹配實時性要求不高的情況下，可以通過比較車輛行駛軌跡和道路之間的幾何形狀進行地圖匹配，形成一種基于道路幾何特征的線到線型的匹配方法。下面將從候選路徑的確定、匹配路徑的確定和最終匹配點的求取3個方面對該方法進行詳細介紹。

2.1 候選路徑確定

候選路徑的確定就是對數(shù)字矢量地圖中道路信息的篩選，縮小尋找車輛當(dāng)前所在匹配路段時的搜索范圍，從復(fù)雜地圖路網(wǎng)中檢索出幾條道路路徑作為確定最終行駛路徑的候選項。候選路徑的選取原則是：確保包含正確匹配路徑的前提下，盡可能地減少待匹配路徑的數(shù)目，以提高匹配效率。

1)檢索框確定候選路徑集

以慣性定位定向的定位坐標(biāo)為幾何中心，以固定長度為邊長，構(gòu)造檢索框，并記錄此刻的航向角，代表車輛行駛方向，其結(jié)構(gòu)為(Point, SearchBox, Heading)。其中，Point為檢索框中心線坐標(biāo)；SearchBox為檢索框邊界左下和右上2個對角點坐標(biāo)；Heading為慣性定位定向系統(tǒng)輸出坐標(biāo)點時刻測得的慣導(dǎo)航向角。利用搜索框進行空間索引，行車過程中實時搜索沿途周邊一定范圍內(nèi)的路段，構(gòu)成候選路徑集。

構(gòu)建的檢索框如圖2所示。

圖2 檢索框構(gòu)建Fig.2 Build the searching box

2)候選路徑的進一步篩選

由于慣性導(dǎo)航系統(tǒng)可以提供精確的車輛航向信息，所以可以通過比較航向ψ和道路方向θ對候選路徑集進行進一步篩選。將候選路段集中滿足Δθ<π/4(其中Δθ=|θ-ψ|)的路段重新組合為數(shù)目更少的候選路徑集LL={ll1,ll2,…,llm},(m≤n)，以此為基礎(chǔ)進行后續(xù)計算。

2.2 匹配路徑確定

1)利用道格拉斯-普克法處理定位軌跡

數(shù)字矢量地圖中，路段信息利用折線近似曲線的方法，由能表征路段幾何形狀的采樣點表示。其特點是，采樣點分布不均勻，轉(zhuǎn)彎部分采樣點分布密集，直線部分采樣點分布稀疏，可認為低頻非定周期采樣。而慣性定位定向系統(tǒng)輸出的車輛行駛軌跡由固定周期高頻采樣數(shù)據(jù)組成，所以，在對定位軌跡和路徑進行匹配時，在盡可能保證原有曲線形態(tài)不至于有太大改變的同時，對定位軌跡點進行抽稀處理。本文采用道格拉斯-普克法對定位軌跡進行處理，其優(yōu)點是具有平移和旋轉(zhuǎn)不變性，能夠在保持原來波形的條件下，壓縮大量的數(shù)據(jù)，如圖3所示。

圖3 道格拉斯-普克法處理定位軌跡Fig.3 The location trajectories by Douglas-Peucker algorithm

2)利用Frechet距離確定匹配路徑

確定匹配路徑，可認為是從眾多候選曲線中找到和定位軌跡曲線相似性最高的那條。本文采用比較2條曲線Frechet距離的方法，F(xiàn)rechet距離越小，這2條曲線的相似度越高。所以取和處理后車輛定位軌跡之間Frechet距離最小的候選路徑為匹配路徑。

設(shè)行駛軌跡P由p個采樣點組成，候選路徑Q由q個采樣點組成。使用σ(P)和σ(Q)分別表示兩軌跡點的順序合集，則有σ(P)=(u1,…,up)和σ(Q)=(v1,…,vq)。構(gòu)造序列點對L: {(ua1,vb1),(ua2,vb2),…,(uam,vbm)}其中，a1=1,b1=1,am=p,bm=q，對于任意i=1,…,q有ai+1=ai或ai+1=ai+1和bi+1=bi。

P、Q軌跡點之間的序列對之間長度定義為各序列對中歐式距離的最大值，表達式如下

(1)

那么其離散Frechet距離為

(2)

使用Frechet距離進行路徑選擇的方法具有一定的適用范圍，實際應(yīng)用中，初始對準(zhǔn)時裝定較高精度位置信息，車輛啟動后，每隔一定里程(5～10km)做一次匹配，將匹配結(jié)果和定位結(jié)果的誤差量作為修正量，對后續(xù)定位信息進行修正，進而提高導(dǎo)航精度。

2.3 匹配點的求取

對圖3所示路段上各特征點求其曲率，如圖4所示。經(jīng)分析知，對于幾何特征明顯的路段，其采樣點曲率變化規(guī)律由最小值A(chǔ)不斷增加到最大值B，然后不斷減小到最小值C。

圖4 路徑幾何特征點曲率變化規(guī)律Fig.4 Geometric feature point curvature variation rule

依次求取定位軌跡點序列和匹配路段點序列中各個點的曲率，并對其進行如下處理：當(dāng)某點曲率大于某閾值η時，用其上述所對應(yīng)的A、B、C這3個特征點表示該段。以此類推，將車輛軌跡拆分成若干段，每一段都由上述的3個特征點表示。

假設(shè)定位定向軌跡和匹配路徑分別由m和n個特征段構(gòu)成。在匹配路徑特征段中選取一段P1作為模板特征段，在軌跡特征段中選取一段P2作為待樣本特征段。則具體匹配過程如下：

1)求最佳模板特征段

如圖5所示，定義T為空間兩點之間的平移向量；P2經(jīng)過平移變換T得到特征段P3，使得P3和P1有共同的原點m2。θ1和θ2被定義為慣導(dǎo)軌跡特征段到匹配路徑特征段的旋轉(zhuǎn)角。定義W=|θ2-θ1|為P1和P2旋轉(zhuǎn)角度量參數(shù)，分別計算P2與匹配路徑的各個特征路段的匹配度，得到一個評價空間Q={W1,W2,W3,…,Wm}。求取Q中的最小值 ，那么P2與道路中的第k段為最佳模板特征段。

圖5 特征路段匹配示意圖Fig.5 Schematic diagram of matching between two characteristic sections

2)計算匹配參數(shù)

如圖5所示，樣本特征段P2到最佳模板特征段P1的匹配參數(shù)包括1個平移參數(shù)T、2個旋轉(zhuǎn)參數(shù)R1和R2，以及1個拉伸參數(shù)S，各自求取公式如下

(3)

3)求匹配點

設(shè)以特征段為骨架的定位軌跡上的任意一點為P，P*為經(jīng)過匹配參數(shù)變換得到的的匹配點，則有

(4)

式中，當(dāng)P在n2以前或在n2上時，θ=θ2；當(dāng)P在n2以后時，θ=θ1。

3 試驗驗證

1)圖6～圖8所示依次為車輛行駛過程中，經(jīng)過檢索框索引確定的候選路段(紅色)、利用航向角篩選后的候選路段和最終匹配路徑。

圖6 檢索框確定候選路徑集(紅色)Fig.6 The candidate path(red lines) determined by searching box

圖7 航向信息近一步篩選候選路徑集(紅色)Fig.7 Candidate paths further filtered by direction

圖8 匹配路徑的確定(紅色)Fig.8 Matching path determination

可以看出，該算法可以有效地確定候選路徑，并準(zhǔn)確和車輛行駛軌跡對應(yīng)的路徑匹配。

2)以道路地圖為背景圖，將GPS衛(wèi)星定位(精度≤1m)、慣性定位定向系統(tǒng)輸出以及地圖匹配得到的行車軌跡進行比較，如圖9所示。

圖9 一段行車軌跡的匹配結(jié)果Fig.9 Matching result of a driving track

以GPS衛(wèi)星定位數(shù)據(jù)為基準(zhǔn)，分別求取純慣性定位和地圖匹配修正后的位置誤差，誤差曲線如圖10所示。

圖10 地圖匹配前后位置誤差對比Fig.10 Comparison of position errors before and after map matching

從圖10中可以看出，利用地圖匹配可將經(jīng)度誤差從49m提高到20m，緯度誤差從65m提高到15m，證明了該算法可以達到較高的匹配精度。

4 結(jié)論

有效的匹配方法是實現(xiàn)地圖匹配的核心，目前典型算法簡單的匹配精度低、可靠性較差；匹配準(zhǔn)確性高的計算復(fù)雜，匹配效率差。

本文利用慣性導(dǎo)航軌跡連續(xù)、航向信息準(zhǔn)確的特點，設(shè)計了一種基于道路幾何特征的地圖匹配方法。通過比較車輛行駛軌跡和道路之間的幾何特征進行地圖匹配，經(jīng)驗證該方法可行，且可達到較高的匹配精度。