一種地圖匹配算法的設(shè)計(jì)與實(shí)現(xiàn)

李殿茜,王 翌,劉 壘,劉 輝

(北京自動(dòng)化控制設(shè)備研究所,北京100074)

一種地圖匹配算法的設(shè)計(jì)與實(shí)現(xiàn)

李殿茜,王 翌,劉 壘,劉 輝

(北京自動(dòng)化控制設(shè)備研究所,北京100074)

設(shè)計(jì)一種面向定位定向?qū)Ш较到y(tǒng)的地圖匹配算法,首先通過網(wǎng)格劃分和建立路段連通性拓?fù)潢P(guān)系表對電子地圖數(shù)據(jù)進(jìn)行預(yù)處理；然后根據(jù)車輛的行駛狀態(tài)采取不同的候選路段確定方法, 計(jì)算各候選路段的匹配度,取值最大的作匹配路段；最后采用垂直投影法求取匹配點(diǎn)。通過跑車數(shù)據(jù)進(jìn)行仿真試驗(yàn),驗(yàn)證了該算法具有良好的準(zhǔn)確性和實(shí)時(shí)性。

地圖匹配；網(wǎng)格劃分；拓?fù)潢P(guān)系；匹配度；候選路段；正交投影

0 引言

隨著車載導(dǎo)航技術(shù)的發(fā)展,各種導(dǎo)航定位技術(shù)在車載導(dǎo)航系統(tǒng)中都得到了成功的應(yīng)用,例如GPS定位技術(shù)、慣性導(dǎo)航技術(shù)(Inertial Navigation System,INS)、航位推算技術(shù)(Dead Reckoning,DR)、無線電技術(shù)等,但每一種技術(shù)都有其無法克服的局限性。而采用地圖匹配技術(shù)(Map Matching)提升定位定向系統(tǒng)導(dǎo)航精度,具有不需要增添新的硬件、成本低、能有效抑制誤差發(fā)散等優(yōu)點(diǎn)。因此,對地圖匹配相關(guān)技術(shù)展開研究具有重要意義。

地圖匹配是一種基于軟件技術(shù)的定位誤差修正技術(shù),依靠精確的電子地圖和完善的地圖匹配算法實(shí)現(xiàn)道路信息與車輛定位信息之間的匹配。然后根據(jù)匹配結(jié)果,校正系統(tǒng)的定位輸出,從而獲取車輛正確的位置信息[1]。圖1所示為地圖匹配原理圖。

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

一個(gè)完整的地圖匹配算法一般包括3個(gè)過程：一是確定誤差區(qū)域,找出車輛附近的所有候選路段；二是從所有候選路段中確定車輛當(dāng)前所在路段,即匹配路段；三是確定車輛在當(dāng)前路段上的具體位置,即匹配點(diǎn)?，F(xiàn)有的一些地圖算法中,算法簡單的,匹配精度低,準(zhǔn)確性差；匹配準(zhǔn)確性較好的算法,結(jié)構(gòu)復(fù)雜,計(jì)算量大,匹配實(shí)時(shí)性差[2]。因此,在保證相對較高的匹配精度的同時(shí),最大程度提高匹配效率將成為地圖匹配算法研究的重點(diǎn)。

本文以車載導(dǎo)航系統(tǒng)提供的車輛位置姿態(tài)信息為樣本,以shapefile格式電子地圖道路信息為模板,提出一種綜合車輛位置、航向信息以及路段拓?fù)潢P(guān)系的地圖匹配算法,具有良好的實(shí)時(shí)性和準(zhǔn)確性。

1 地圖數(shù)據(jù)預(yù)處理

在上述提到的地圖匹配3個(gè)過程中,確定候選路段的范圍是影響匹配效率的主要因素。尤其在匹配開始階段,因?yàn)闆]有歷史信息可以利用,也不知道大致范圍,所以在尋找車輛當(dāng)前所在路段時(shí)要遍歷搜索大量的路段,大大影響匹配效率。另外,候選路段數(shù)量如果很大,匹配出錯(cuò)的概率也會(huì)增加,從而影響匹配精度。因此,為了快速準(zhǔn)確地確定候選路段,在匹配開始前對電子地圖數(shù)據(jù)進(jìn)行預(yù)處理,具體做法是地圖網(wǎng)格區(qū)域劃分和建立路段間連通性拓?fù)潢P(guān)系表。

1.1 地圖網(wǎng)格劃分

將電子地圖自左而右、自下而上按固定步長劃分成M×N個(gè)網(wǎng)格區(qū)域,并且每個(gè)網(wǎng)格都有唯一的編號(hào),其中M、N分別代表網(wǎng)格的行數(shù)和列數(shù)。如圖2所示,設(shè)電子地圖左下角頂點(diǎn)和右上角頂點(diǎn)坐標(biāo)分別為(X1,Y1)和(X2,Y2),則網(wǎng)格劃分時(shí)緯度和經(jīng)度方向的步長分別為hx、hy以及定位點(diǎn)(xo,yo)所在網(wǎng)格編號(hào)A由式(1)確定。

(1)

其中,[ ]為取整。

圖2 地圖網(wǎng)格劃分及編號(hào)Fig.2 Map mesh division and mesh number

判斷路段與網(wǎng)格關(guān)系,將位于網(wǎng)格內(nèi)以及與網(wǎng)格邊界相交的路段都認(rèn)為屬于該網(wǎng)格。建立網(wǎng)格-路段索引表,使得通過網(wǎng)格編號(hào)可以快速索引出屬于該網(wǎng)格的所有路段的編號(hào)[3]。因此,在匹配初始時(shí)刻確定候選路段時(shí),只要確定定位點(diǎn)所在網(wǎng)格就可以從屬于該網(wǎng)格的路段中進(jìn)行篩選,不需要遍歷電子地圖中所有的路段,從而大大減少了算法的計(jì)算量,提高算法效率。

1.2 建立拓?fù)潢P(guān)系表

Shapefile格式電子地圖是一種無拓?fù)涞氖噶繑?shù)據(jù)結(jié)構(gòu),即只存儲(chǔ)了路段的位置信息和屬性信息,并沒有表示路段與路段之間的拓?fù)潢P(guān)系[4]。我們認(rèn)為,由于車速是有限的,所以在一定時(shí)間范圍內(nèi),車輛離開上一匹配路段后,只能行駛在與之相連的路段,而不可能在其他路段上行駛。所以,本文根據(jù)電子地圖道路數(shù)據(jù)建立了路段間的連通性拓?fù)潢P(guān)系表(見表1)。

表1 路段間連通性拓?fù)潢P(guān)系格式

當(dāng)車輛離開上一時(shí)刻的匹配路段時(shí),利用路段節(jié)點(diǎn),從拓?fù)潢P(guān)系表中找到對應(yīng)的路段作為候選路段進(jìn)行匹配,從而節(jié)省了尋找候選路段的搜索時(shí)間,并且可以減少誤匹配現(xiàn)象的出現(xiàn)。

2 算法的設(shè)計(jì)與實(shí)現(xiàn)

2.1 候選路段的確定

根據(jù)車輛行駛狀態(tài)的不同,候選路段的選取準(zhǔn)則也不同,可分為下面3個(gè)狀態(tài)：

1)初始狀態(tài),初始時(shí)刻沒有歷史信息可以利用,此時(shí)確定定位點(diǎn)所在網(wǎng)格,取網(wǎng)格內(nèi)所有路段作候選路段。

2)跟蹤狀態(tài),若此刻車輛沒有離開上一時(shí)刻確定的匹配路段,則該路段即為此刻車輛的候選路段也就是匹配路段。相較于上一時(shí)刻,匹配路段沒有變化。

3)更新狀態(tài),若車輛離開上一時(shí)刻的匹配路段,則查詢拓?fù)潢P(guān)系表,找到和上一路段相連通的所有路段作為候選路段,匹配結(jié)果將是對上一時(shí)刻匹配路段的更新[5]。

設(shè)車輛定位坐標(biāo)為(xo,yo),某一路段的起止節(jié)點(diǎn)用(x1,y1)和(x2,y2)表示。由式(2),當(dāng)滿足0<η<1且d<ε(ε為設(shè)定的閾值,文中取30m)時(shí),認(rèn)為車輛沒有離開該路段。

(2)

2.2 匹配路段的確定

設(shè)某一時(shí)刻定位點(diǎn)到候選路段的距離為di,車輛行駛航向與路段方向夾角為Δθi,則定義匹配度fi,有

(3)

其中,wd、wθ分別表示距離因素和方向因素在匹配度中的權(quán)重系數(shù),滿足wd+wθ=1(本文中均取0.5)。由式(3)可知,定位點(diǎn)到路段的距離越小,車輛行駛航向和路段方向夾角越小則匹配度越大,說明該路段是當(dāng)前車輛所在道路的可能性就越大[6]。因此,在匹配過程中,求出定位點(diǎn)對于各個(gè)候選路段的匹配度,取匹配度最大的候選路段為車輛的匹配路段。

2.3 路段上匹配點(diǎn)的確定

匹配路段確定后,將車輛定位點(diǎn)向匹配路段上做投影,投影點(diǎn)作為車輛在路段上的匹配點(diǎn)[7]。匹配點(diǎn)(xp,yp)求取如下：

(4)

2.4 算法步驟和流程

圖3 地圖匹配算法流程圖Fig.3 Map matching algorithm flow chart

算法的流程如圖3所示。算法的實(shí)現(xiàn)步驟如下：

步驟1：載入電子地圖,對地圖數(shù)據(jù)進(jìn)行預(yù)處理。

步驟2：讀入導(dǎo)航系統(tǒng)提供的定位數(shù)據(jù)。

步驟3：判斷上一時(shí)刻匹配是否成功,若成功,利用式(2)計(jì)算η和d；否則跳轉(zhuǎn)至步驟6。

步驟4：判斷車輛是否離開了上一時(shí)刻匹配路段,如果是,索引拓?fù)潢P(guān)系表,找到候選路段；否則匹配路段沒變,跳轉(zhuǎn)至步驟8。

步驟5：判斷拓?fù)潢P(guān)系表中候選路段數(shù)目N,若N=1,則該路段就是匹配路段,跳轉(zhuǎn)至步驟8；若N>1,這N條路段為候選路段。

步驟6：利用式(1)確定定位點(diǎn)所在網(wǎng)格區(qū)域,取網(wǎng)格內(nèi)所有路段為候選路段。

步驟7：利用式(3)求取各候選路段的匹配度,比較匹配度大小確定匹配路段。

步驟8：向匹配路段上做正交投影,投影點(diǎn)作為車輛的匹配點(diǎn)。

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

利用定位定向?qū)Ш较到y(tǒng)跑車數(shù)據(jù)在Matlab仿真工具上對地圖匹配算法進(jìn)行仿真試驗(yàn)驗(yàn)證。圖4～圖7所示為匹配結(jié)果的圖像顯示,藍(lán)點(diǎn)代表車輛的定位點(diǎn),紅點(diǎn)代表匹配點(diǎn)。

圖4 全程匹配效果圖Fig.4 Full matching effect chart

圖5 單/雙行線變換路段匹配效果圖Fig.5 Transformation between single line and double line

圖6 轉(zhuǎn)彎匹配效果圖Fig.6 Intersection turn matching effect chart

圖7 平行路段匹配效果圖Fig.7 Parallel section matching effect chart

從表2可以看出,匹配成功率為99.5%,匹配正確率達(dá)到97.2%,表明該算法具有較好的匹配準(zhǔn)確性。表3所示為在初始狀態(tài)、跟蹤狀態(tài)和更新狀態(tài)下匹配單個(gè)定位點(diǎn)用的時(shí)間,以及整個(gè)匹配總時(shí)間。不難看出該匹配算法可以滿足一定的準(zhǔn)確性和實(shí)時(shí)性要求。

表2 匹配準(zhǔn)確性統(tǒng)計(jì)表

表3 匹配時(shí)間統(tǒng)計(jì)表

4 結(jié)論

確定候選路段時(shí)所遍歷的路段數(shù)目的多少直接影響地圖匹配算法的效率,通過對道路電子地圖進(jìn)行網(wǎng)格劃分并且建立路段間連通性拓?fù)潢P(guān)系,可以快速地確定出候選路段的范圍。引入匹配度計(jì)算,綜合考慮車輛和路段之間的距離因素和方向因素,可以準(zhǔn)確地確定匹配路段。將定位點(diǎn)往匹配路段做正交投影,取投影點(diǎn)作匹配點(diǎn),有效地消除了垂直與道路方向上的定位誤差,提高了匹配精度。

[1] 劉興權(quán),金美含.地圖匹配算法綜述[J].科技信息,2014(4):64-65.

[2] Miwa T, Kiuchi D, Yamamoto T, et al. Development of map matching algorithm for low frequency probe data [J]. Transportation Research Part C Emerging Technologies, 2012,22(5): 132-145.

[3] 李英飛.車載導(dǎo)航系統(tǒng)中數(shù)據(jù)處理與地圖匹配技術(shù)研究[D].哈爾濱工程大學(xué),2012.

[4] 周長英,陳穎.空間數(shù)據(jù)庫索引技術(shù)發(fā)展概況[J].黑龍江科技信息,2010(31)：84.

[5] 梁貞.基于權(quán)重的線到線地圖匹配算法的研究[D].北京交通大學(xué),2006.

[6] 蘇海濱,徐俊紅,程志沖.基于權(quán)重的改進(jìn)綜合地圖匹配算法[J].中南大學(xué)學(xué)報(bào),2011(9):773-777.

[7] Karimi H A, Conahan T, Roongpiboonsopit D.A methodology for predicting performances of map-matching algorithms[C]//International Symposium on Web and Wireless Geographical Information Systems. Springer Berlin Heidelberg, 2006: 202-213.

The Design and Implementation of a Map Matching Algorithm

LI Dian-xi, WANG Yi, LIU Lei, LIU Hui

(Beijing Institute of Automatic Control Equipment,Beijing 100074,China)

A map matching algorithm based on orientation navigation system is designed. The data of the electronic map is preprocessed by mesh division and building the topological relations between the sections. Then, according to driving state of the vehicle, a method of determining different candidate sections is designed. The calculated maximum of matching degree is taken as the matching section, and the projection point is used as the matching point. By using the data of vehicle experiment, the map matching algorithm is proved to have good accuracy and real-time performance.

Map matching; Mesh division; Topological relation; Matching degree; Ortho-perspective

2016-11-15；

2017-02-01

解放軍總裝備部預(yù)先研究項(xiàng)目(51309030104)

李殿茜(1989-),男,碩士,主要從事面向定位定向的地圖匹配技術(shù)方面的研究。E-mail: lidianxii@126.com

10.19306/j.cnki.2095-8110.2017.02.006

U666.1

A

2095-8110(2017)02-0031-04