瞿逸倫，卿 立，張 迪，何 偉，李殿茜

(1.北京自動化控制設(shè)備研究所·北京·100074；2.空裝駐北京地區(qū)第二軍事代表室·北京·100074)

0 引 言

地圖匹配技術(shù)已被廣泛應(yīng)用于車載導(dǎo)航定位系統(tǒng)[1]。該技術(shù)實質(zhì)上是基于車輛始終行駛在道路上的假設(shè)，通過各類傳感器獲取車輛的行駛軌跡，并將行駛軌跡與數(shù)字地圖中提供的路徑信息進(jìn)行匹配，以獲取車輛的絕對位置[2]。

目前，現(xiàn)有的地圖匹配算法包括直接投影法、概率統(tǒng)計法、相關(guān)性算法、基于網(wǎng)絡(luò)拓?fù)潢P(guān)系的算法等。直接投影法是一種典型的點到線的確定型匹配算法。其基本思路為：求取定位點與周圍路段之間的距離，通過比較投影距離的大小，確定車輛所在的道路。一般而言，可選擇定位點和路段間垂直投影距離最小的路段為匹配路段，取投影點作為車輛在道路上的匹配點。直接投影法的算法邏輯簡單，匹配速度快，但其不能消除沿道路方向上的定位誤差。直接投影法對原始定位精度的要求較高，對道路交叉口等復(fù)雜路段的匹配精度較低，穩(wěn)定性較差[3-5]。

概率統(tǒng)計法的基本思想是依據(jù)車輛的定位信息、利用概率準(zhǔn)則設(shè)置一個置信區(qū)域(誤差橢圓)，從而在每次匹配時不再需要遍歷所有路段，極大地縮小了候選路段的范圍，最后可通過對候選路段的判斷得到最佳的匹配結(jié)果。概率統(tǒng)計法的優(yōu)點在于通過設(shè)置誤差區(qū)域，縮小了匹配路段的選擇范圍，使得匹配效率得到了提高。但是，概率統(tǒng)計法并沒有有效利用車輛行駛的歷史信息。如果當(dāng)前置信區(qū)域道路密集，匹配位置在相鄰路段間可能反復(fù)跳躍，產(chǎn)生誤匹配，進(jìn)而影響匹配精度[6]。

基于拓?fù)潢P(guān)系的地圖匹配算法通過對前一次的匹配結(jié)果和對車輛前進(jìn)方向進(jìn)行分析，利用道路的空間拓?fù)潢P(guān)系，確定當(dāng)前定位點候選路段的范圍，并快速找出定位點所在的匹配路段，進(jìn)而計算出當(dāng)前定位點的匹配點?；谕?fù)潢P(guān)系的地圖匹配算法實時性較好，而且在候選路段相互平行的情況下匹配效果明顯。但是，該算法必須在電子地圖道路拓?fù)潢P(guān)系完整的情況下才可應(yīng)用。同時，匹配的正確性對初始匹配結(jié)果的依賴性大，算法的容錯能力較差[5]。

現(xiàn)有的地圖匹配算法往往需要根據(jù)行駛軌跡在地圖道路信息中尋找匹配路段，或依賴初始匹配結(jié)果。城市道路環(huán)境多存在多種岔路、路口、死路，以及短支路等，并且路網(wǎng)分布密集?，F(xiàn)有地圖匹配算法在此場景下需要頻繁尋路，并且容易發(fā)生尋路錯誤、難以及時修正尋路結(jié)果的情況，進(jìn)而影響后續(xù)匹配結(jié)果。在城市峽谷環(huán)境中，衛(wèi)星信號會被遮擋，易導(dǎo)致初始定位誤差較大[7-9]。

對此，本文提出了一種基于圖像卷積的地圖匹配算法。該算法利用車載慣性/里程計組合導(dǎo)航系統(tǒng)確定車輛行駛軌跡，將軌跡圖像與地圖圖像進(jìn)行匹配、完成定位，并且通過匹配結(jié)果對慣性/里程計定位結(jié)果進(jìn)行補(bǔ)償，抑制其誤差發(fā)散。該算法不依賴于對匹配路段的尋找，可適用于初始定位誤差較大的使用場景。同時，由于慣性/里程計不依賴外部信息源，用其軌跡進(jìn)行匹配可在提高精度的同時保持系統(tǒng)的自主性。

1 Web墨卡托坐標(biāo)系

Web墨卡托坐標(biāo)系是一種利用公共可視化偽墨卡托投影方法而得到的坐標(biāo)系，是一種為谷歌地圖、微軟虛擬地球等網(wǎng)絡(luò)地理所應(yīng)用的地圖投影坐標(biāo)系，如圖1所示。

圖1 墨卡托投影Fig.1 Mercator projection

公共可視化偽墨卡托投影是正軸等角圓柱投影。設(shè)地球為正球體，假想存在一個與地軸方向一致的圓柱切于地球，按等角條件將經(jīng)緯網(wǎng)投影到圓柱面上，將圓柱面展為平面，即可得到其投影[10]，通過墨卡托投影可得到Web墨卡托坐標(biāo)系。

不同于WGS-84坐標(biāo)系、GCJ-02坐標(biāo)系等橢球面地理坐標(biāo)系，Web墨卡托坐標(biāo)系以地球經(jīng)緯度作為參考。Web墨卡托坐標(biāo)系為投影坐標(biāo)系，是平面坐標(biāo)系，以米為單位。

本文后續(xù)對于地圖信息、道路信息以及定位信息的描述皆在Web墨卡托坐標(biāo)系下進(jìn)行，取東向為X正方向，北向為Y正方向。

2 二維離散卷積

圖像經(jīng)過數(shù)字采樣可轉(zhuǎn)化為矩陣，因此圖像卷積實質(zhì)上是二維離散卷積，如式(1)～式(2)所示。其中，*表示卷積運(yùn)算

H=F*G

(1)

(2)

圖像經(jīng)數(shù)字采樣得到矩陣G。在卷積過程中，采用一個大小為a×b的矩陣F來表示特征權(quán)值，這樣的矩陣被稱為卷積核。F的尺寸通常小于G。當(dāng)F中第1行第1列元素F(1,1)與G中第i行第j列元素G(i,j)重合時，將F中的每個元素與G中重疊區(qū)域的每個元素分別相乘，其乘積之和為該區(qū)域的卷積值，即卷積陣H中第i行第j列元素H(i,j)。F在G上滑動，通過每一次滑動可得到對應(yīng)區(qū)域的卷積值。最終，F(xiàn)遍歷G，可得出關(guān)于圖像的卷積矩陣H。

卷積可以從輸入的圖像中提取圖像的特征，并可以保留像素間的空間關(guān)系。在每次運(yùn)算中，將卷積核元素與圖像中卷積核覆蓋區(qū)域的元素分別相乘求和，可得到卷積值。卷積值反應(yīng)了該區(qū)域內(nèi)圖像特征與卷積核特征的相關(guān)性。以二值圖像及二值卷積核為例，每個卷積值代表了該圖像重復(fù)區(qū)域與卷積核的圖像重復(fù)像素點個數(shù)。

3 基于二維離散卷積的地圖匹配算法

車載慣性/里程計組合導(dǎo)航系統(tǒng)能夠測量車輛的位置信息，且不依靠外界信息源，具備自主性。但是，慣性/里程計自身的特性導(dǎo)致其定位誤差隨時間及行駛里程的增加而發(fā)散，難以在長時間、大范圍條件下保持定位精度。對此，本文提出根據(jù)車輛行駛軌跡進(jìn)行地圖匹配，以確保長時間、大范圍條件下的定位精度[11-13]。

本文通過車載慣性/里程計組合導(dǎo)航系統(tǒng)的定位信息，獲得車輛行駛軌跡及軌跡圖像，將軌跡圖像與地圖道路圖像進(jìn)行卷積，在地圖圖像上尋找與行駛軌跡相關(guān)度最高的道路，進(jìn)而通過像素點位置與地圖道路信息進(jìn)行匹配，輸出當(dāng)前的位置信息。

3.1 算法流程

設(shè)每次匹配需截取的車輛行駛軌跡長度為Lt。在初次匹配時，根據(jù)里程計信息，在行駛里程大于Lt后，截取車輛行駛軌跡，并根據(jù)歷史信息對其進(jìn)行補(bǔ)償，以補(bǔ)償后的軌跡作為初始軌跡，繪制軌跡圖像。根據(jù)截取軌跡的邊界信息判斷此時軌跡是否處于當(dāng)前載入的地圖塊之內(nèi)，若不在地圖塊內(nèi)，則根據(jù)當(dāng)前軌跡所在位置搜索其所在的地圖塊，并載入新的地圖塊信息、繪制其地圖塊的圖像；若在地圖塊內(nèi)，則判斷此時軌跡是否正在跨越地圖塊邊界，若是則進(jìn)入下一拍，若不是則開始匹配。

由于慣性/里程計組合定位信息存在一定的初始誤差，故需要在軌跡圖像范圍的基礎(chǔ)上擴(kuò)大匹配區(qū)域。開始匹配后，首先將軌跡圖像的邊界南北向與東西向各延展le米，以此范圍在地圖塊圖像上進(jìn)行截取，得到匹配區(qū)域的地圖圖像。將軌跡圖像作為卷積核在匹配區(qū)域的地圖圖像上進(jìn)行卷積，得到與本次匹配的卷積矩陣。對卷積矩陣進(jìn)行歸一化后，進(jìn)行判決：(1)卷積矩陣中有且僅有一個最大卷積值；(2)卷積值超過門限。若同時滿足上述兩條判決，則本次匹配成功，推算地圖匹配的位置信息；否則，匹配失敗，進(jìn)入下一拍。

通過搜索卷積矩陣中最大卷積值相對于卷積陣的坐標(biāo)，以及軌跡圖像中末端點像素相對于軌跡圖像的坐標(biāo)，即可推算出當(dāng)前位置在地圖圖像中的像素坐標(biāo)，通過地圖信息得到當(dāng)前位置信息，并輸出本拍的匹配位置信息。同時，計算慣性/里程計定位結(jié)果與匹配結(jié)果的差值，以此差值對下次匹配時的慣性/里程計定位結(jié)果進(jìn)行補(bǔ)償。先進(jìn)行補(bǔ)償，再進(jìn)行下次匹配。

本次匹配結(jié)束后，根據(jù)里程計信息，在繼續(xù)往前行駛l米后，截取從當(dāng)前位置向前、長度為Lt的軌跡作為新的匹配軌跡，并進(jìn)行下次匹配。算法流程如圖2所示。

圖2 算法流程圖Fig.2 Flow diagram

3.2 軌跡截取及軌跡圖像繪制

在初次匹配時，需利用到里程計的信息。當(dāng)里程計輸出首次大于Lt時，取車輛行駛軌跡為初始軌跡，并根據(jù)慣性/里程計組合定位信息繪制其軌跡圖像。

將慣性/里程計組合導(dǎo)航定位系統(tǒng)的輸出位置坐標(biāo)轉(zhuǎn)換為其在Web墨卡托坐標(biāo)系下的坐標(biāo)，即可得到一組Web墨卡托坐標(biāo)系下的軌跡坐標(biāo)。設(shè)軌跡中的坐標(biāo)組數(shù)為n，則Web墨卡托坐標(biāo)系下的軌跡坐標(biāo)可表示為

(3)

取軌跡X方向坐標(biāo)最大值Xtmax、X方向坐標(biāo)最小值Xtmin、Y方向坐標(biāo)最大值Ytmax、Y方向坐標(biāo)最小值Ytmin為軌跡邊界。將軌跡繪制為軌跡圖像，需要將軌跡位置轉(zhuǎn)換為像素點的坐標(biāo)軌跡圖像矩陣中所有的軌跡點坐標(biāo)處對應(yīng)的矩陣元素置為1，其余置0，即可得到軌跡圖像矩陣Tm×n。

同理，當(dāng)一拍匹配結(jié)束后，等待里程計測量值增加l米，根據(jù)里程計信息截取從末端起長度為Lt的軌跡信息。根據(jù)上述步驟計算得到新的軌跡圖像矩陣，以此進(jìn)行下一拍的匹配。

3.3 地圖搜索與地圖圖像繪制

截取軌跡期間，可得到軌跡于Web墨卡托坐標(biāo)系下的邊界信息Xtmax、Xtmin、Ytmax、Ytmin，以及慣性/里程計組合輸出的Web墨卡托坐標(biāo)系下的當(dāng)前位置(Xtn,Ytn)。將當(dāng)前位置(Xtn,Ytn)與當(dāng)前已載入地圖塊的邊界進(jìn)行對比，判斷軌跡是否仍處于當(dāng)前載入的地圖塊。Xbmin為地圖X坐標(biāo)的最小值，Xbmax為地圖X坐標(biāo)的最大值，Ybmin為地圖Y坐標(biāo)的最小值，Ybmax為地圖Y坐標(biāo)的最大值。若滿足

(4)

則軌跡已在地圖內(nèi)；若軌跡不在地圖內(nèi)，則重新搜索地圖。若是初次匹配，則無需判斷當(dāng)前位置是否在地圖內(nèi)，可直接進(jìn)入地圖搜索步驟。

搜索地圖則根據(jù)慣性/里程計輸出的當(dāng)前位置于Web墨卡托坐標(biāo)系下坐標(biāo)(Xtn,Ytn)，搜索當(dāng)前所處的地圖塊。遍歷地圖文件中的每個地圖塊的邊界，當(dāng)存在地圖塊滿足式(4)條件時，則選取該地圖塊為當(dāng)前所在，并載入地圖信息，繪制地圖塊。

繪制地圖圖像與繪制軌跡圖像類似。將地圖圖像矩陣中道路所在的像素點對應(yīng)的矩陣元素設(shè)置為1，將其余置為0，即可得到地圖圖像矩陣Μp×q。

3.4 地圖像素對應(yīng)的地理位置

為后續(xù)推算匹配位置，需要為地圖圖像的每個像素添加與其對應(yīng)的Web墨卡托坐標(biāo)系下的位置坐標(biāo)。設(shè)地圖圖像中第1行第1列像素對應(yīng)的Web墨卡托坐標(biāo)系下的坐標(biāo)為(Xmw1,Ymw1)，其中

(5)

式中，R為取整運(yùn)算，Ppixel為一個正方形像素的邊長所代表的實際距離。圖像中第p0行和第q0列像素對應(yīng)的Web墨卡托坐標(biāo)系下的坐標(biāo)為(Xmwp0,Ymwq0)，其中

(6)

由此，可以推算地圖圖像上每個像素點對應(yīng)的Web墨卡托坐標(biāo)系下的位置坐標(biāo)。

3.5 匹配區(qū)域截取

由于慣性/里程計組合定位信息存在一定的初始誤差，需要在軌跡圖像范圍的基礎(chǔ)上擴(kuò)大匹配區(qū)域。地圖塊的整體圖像較大，將地圖塊圖像整體與軌跡圖像進(jìn)行卷積，將帶來巨大的計算量，影響匹配的實時性，故需要從地圖塊圖像中截取部分圖像作為匹配區(qū)域圖像。

將慣性/里程計輸出的軌跡圖像的邊界南北向與東西向各延展le米，以此范圍在地圖圖像上進(jìn)行截取。匹配區(qū)域在地圖圖像上的邊界像素坐標(biāo)可按下式求出

(7)

設(shè)

(8)

根據(jù)邊界，截取地圖圖像矩陣中由Xpmin列至Xpmax列、由Ypmin行至Ypmax行區(qū)域內(nèi)的元素作為匹配區(qū)域，得到匹配區(qū)域圖像矩陣Pj×k。

3.6 軌跡匹配

將軌跡圖像矩陣作為卷積核，在匹配區(qū)域圖像上進(jìn)行二維離散Valid卷積，即卷積核內(nèi)的所有元素均有圖像矩陣中的元素與其對應(yīng)。卷積核在輸入圖像中滑動，滑動步長為1。在每一次滑動過程中，卷積核內(nèi)的每個元素與對應(yīng)匹配區(qū)域圖像中的重疊區(qū)域的每個元素分別相乘，其乘積之和即為該區(qū)域的卷積值。卷積核遍歷圖像中所有的點，即得到卷積矩陣C0

C0(m-p+1)×(n-q+1)=Tm×n*Pp×q

(9)

在得到卷積陣C0后，對卷積陣C0進(jìn)行歸一化處理，設(shè)

(10)

則歸一化的卷積陣C為

(11)

通過卷積陣C對本次匹配的可用性進(jìn)行判別。設(shè)C中的最大元素為Cmax，判別條件如下

(1)C有且僅有一個最大值Cmax；

(2)Cmax超過門限值Cs。

若同時滿足上述兩項判決條件，則本次匹配有效，繼續(xù)推算匹配位置的坐標(biāo)；否則，本次匹配失敗，進(jìn)入下一拍。

3.7 匹配位置推算

若滿足判決條件，設(shè)Cmax元素在C陣中的矩陣坐標(biāo)為(Xc,Yc)。當(dāng)前所處位置為軌跡末端點，其在軌跡圖像矩陣T中的矩陣坐標(biāo)為(Xtfn,Ytfn)。根據(jù)式(6)，Web墨卡托坐標(biāo)系下的軌跡末端點的匹配位置可通過式(12)進(jìn)行解算

(12)

3.8 地圖匹配在定位定向系統(tǒng)中的應(yīng)用

當(dāng)定位定向系統(tǒng)采用純慣性導(dǎo)航時，由于慣性器件的誤差積累效應(yīng)，慣性導(dǎo)航系統(tǒng)的定位誤差將會隨導(dǎo)航時間的增加而迅速發(fā)散。慣性/里程計組合能夠在一定程度上抑制慣性誤差發(fā)散，但隨著里程增加，定位誤差依然會逐漸積累[14-15]。

地圖匹配具有較高的理論精度，但在復(fù)雜路況下，其存在匹配結(jié)果不可用的情況，故其定位結(jié)果存在不連續(xù)性?？赏ㄟ^地圖匹配修正慣性/里程計的積累誤差，使地圖匹配與慣性/里程計形成優(yōu)勢互補(bǔ)，從而保證長時間、連續(xù)的高精度定位輸出。

設(shè)當(dāng)?shù)貓D匹配結(jié)果可用時，地圖匹配當(dāng)前輸出的定位結(jié)果為(Xw,Yw)，定位定向系統(tǒng)當(dāng)前輸出的定位結(jié)果為(Xtn,Ytn)，則此時的位置修正量為

(13)

用本次匹配所得的修正量對后續(xù)的慣性/里程計定位結(jié)果進(jìn)行補(bǔ)償

(X′tn+1,Y′tn+1)=(Xtn+1+eX,Ytn+1+eY)

(14)

以此類推，當(dāng)進(jìn)入下一次地圖匹配時，軌跡信息被上一拍匹配的修正量所補(bǔ)償。先補(bǔ)償、后匹配的方式能夠避免由慣性/里程計誤差發(fā)散所導(dǎo)致的軌跡與真實路段距離過遠(yuǎn)、進(jìn)而匹配失敗的情況。同時，由于卷積計算本身的特性，匹配對圖像畸變有一定的適應(yīng)性。上述適應(yīng)性使得即使由于誤差發(fā)散導(dǎo)致軌跡出現(xiàn)一定的變形，仍能保證匹配的正確性與精度。當(dāng)下次匹配有效時，則對修正量進(jìn)行更新；當(dāng)?shù)貓D匹配結(jié)果不可用時，則不對修正量進(jìn)行更新。

4 仿真驗證

根據(jù)跑車數(shù)據(jù)，對地圖匹配與定位定向設(shè)備組合定位效果進(jìn)行仿真驗證。定位定向系統(tǒng)采用慣性/里程計組合導(dǎo)航系統(tǒng)進(jìn)行定位，仿真條件如表1所示。

表1 仿真條件Tab.1 Simulation Condition

將慣性/里程計組合位置輸出作為軌跡信息，進(jìn)行地圖匹配。當(dāng)匹配成功時，根據(jù)式(13)、式(14)的地圖匹配結(jié)果對慣性/里程計定位結(jié)果進(jìn)行補(bǔ)償，仿真結(jié)果如圖3～圖5所示。

圖4 東向位置誤差Fig.4 East position error

圖5 綜合位置誤差Fig.5 Position error

仿真的位置誤差統(tǒng)計如表2所示。

表2 誤差統(tǒng)計(1σ)Tab.2 Error statistics(1σ)

從圖3～圖5可以看出，當(dāng)匹配成功時，可通過匹配結(jié)果對后續(xù)慣性/里程計定位結(jié)果進(jìn)行補(bǔ)償。這種補(bǔ)償方式能夠消除一定的定位誤差，對慣性/里程計的定位誤差發(fā)散具有一定的抑制作用。由表2的統(tǒng)計結(jié)果可以看出，經(jīng)地圖匹配的補(bǔ)償，慣性/里程計組合定位精度高于無匹配的慣性/里程計組合。

5 結(jié) 論

本文通過圖像卷積的方式，對車輛行駛軌跡圖像與地圖圖像進(jìn)行了匹配，并完成了定位。相比現(xiàn)有的地圖匹配算法，該算法不依賴路口匹配，避免了由較大的初始誤差場景所帶來的尋路錯誤，以及由路口匹配錯誤對后續(xù)匹配精度帶來的影響。通過地圖匹配對定位定向設(shè)備進(jìn)行誤差修正，提高了定位精度，且其不需要依靠外部信息源，具備一定的自主性。