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

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

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

0 引言

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

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

1 地圖匹配原理

1.1 地圖匹配基本原理

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

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

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

1.2 典型地圖匹配實現方法介紹

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

目前典型的地圖匹配算法有垂直投影法、概率統計法、相關性算法、基于網絡拓撲關系算法和基于權重的算法等。這幾種典型地圖匹配算法的優缺點、適用范圍等如表1所示。

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

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

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

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

2.1 候選路徑確定

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

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

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

構建的檢索框如圖2所示。

圖2 檢索框構建Fig.2 Build the searching box

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

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

2.2 匹配路徑確定

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

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

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

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

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

設行駛軌跡P由p個采樣點組成，候選路徑Q由q個采樣點組成。使用σ(P)和σ(Q)分別表示兩軌跡點的順序合集，則有σ(P)=(u1,…,up)和σ(Q)=(v1,…,vq)。構造序列點對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距離進行路徑選擇的方法具有一定的適用范圍，實際應用中，初始對準時裝定較高精度位置信息，車輛啟動后，每隔一定里程(5～10km)做一次匹配，將匹配結果和定位結果的誤差量作為修正量，對后續定位信息進行修正，進而提高導航精度。

2.3 匹配點的求取

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

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

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

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

1)求最佳模板特征段

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

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

2)計算匹配參數

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

(3)

3)求匹配點

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

(4)

式中，當P在n2以前或在n2上時，θ=θ2；當P在n2以后時，θ=θ1。

3 試驗驗證

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

圖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

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

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

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

以GPS衛星定位數據為基準，分別求取純慣性定位和地圖匹配修正后的位置誤差，誤差曲線如圖10所示。

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

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

4 結論

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

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