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

劉 峰，郭 陽(yáng)，鄭 辛，李殿茜

(1.北京自動(dòng)化控制設(shè)備研究所，北京 100074；2.國(guó)防科技大學(xué)，長(zhǎng)沙 410000；3.中國(guó)航天科工集團(tuán)有限公司，北京 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ù)、無(wú)線電技術(shù)等，但每一種技術(shù)都有其無(wú)法克服的局限性。例如當(dāng)車輛通過(guò)涵洞、隧道、立交橋時(shí)，或者衛(wèi)星接收機(jī)受到遮擋、干擾時(shí)，導(dǎo)致衛(wèi)星無(wú)法正常定位；受陀螺漂移、加速度計(jì)零偏等慣性器件誤差的影響，慣性定位定向的定位誤差會(huì)隨著行駛時(shí)間和行駛距離的增加而增大。采用地圖匹配(Map Matching)技術(shù)提升定位定向系統(tǒng)的定位精度，具有不需要增添新的硬件、成本低、能有效抑制誤差發(fā)散等優(yōu)點(diǎn)。因此對(duì)地圖匹配相關(guān)技術(shù)展開(kāi)研究具有重要意義。

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

1 地圖匹配原理

1.1 地圖匹配基本原理

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

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

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

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

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

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

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

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

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

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

2.1 候選路徑確定

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

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

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

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

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

2)候選路徑的進(jìn)一步篩選

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

2.2 匹配路徑確定

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

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

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

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

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

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

P、Q軌跡點(diǎn)之間的序列對(duì)之間長(zhǎng)度定義為各序列對(duì)中歐式距離的最大值，表達(dá)式如下

(1)

那么其離散Frechet距離為

(2)

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

2.3 匹配點(diǎn)的求取

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

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

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

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

1)求最佳模板特征段

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

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

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

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

(3)

3)求匹配點(diǎn)

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

(4)

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

3 試驗(yàn)驗(yàn)證

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

圖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)確和車輛行駛軌跡對(duì)應(yīng)的路徑匹配。

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

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

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

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

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

4 結(jié)論

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

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