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

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

0 引 言

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

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

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

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

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

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

1 Web墨卡托坐標系

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

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

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

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

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

2 二維離散卷積

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

H=F*G

(1)

(2)

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

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

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

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

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

3.1 算法流程

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

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

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

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

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

3.4 地圖像素對應的地理位置

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

(5)

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

(6)

由此，可以推算地圖圖像上每個像素點對應的Web墨卡托坐標系下的位置坐標。

3.5 匹配區(qū)域截取

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

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

(7)

設(shè)

(8)

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

3.6 軌跡匹配

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

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

(9)

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

(10)

則歸一化的卷積陣C為

(11)

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

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

(2)Cmax超過門限值Cs。

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

3.7 匹配位置推算

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

(12)

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

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

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

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

(13)

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

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

(14)

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

4 仿真驗證

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

表1 仿真條件Tab.1 Simulation Condition

將慣性/里程計組合位置輸出作為軌跡信息，進行地圖匹配。當匹配成功時，根據(jù)式(13)、式(14)的地圖匹配結(jié)果對慣性/里程計定位結(jié)果進行補償，仿真結(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可以看出，當匹配成功時，可通過匹配結(jié)果對后續(xù)慣性/里程計定位結(jié)果進行補償。這種補償方式能夠消除一定的定位誤差，對慣性/里程計的定位誤差發(fā)散具有一定的抑制作用。由表2的統(tǒng)計結(jié)果可以看出，經(jīng)地圖匹配的補償，慣性/里程計組合定位精度高于無匹配的慣性/里程計組合。

5 結(jié) 論

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