一種地圖匹配算法的設計與實現

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

(北京自動化控制設備研究所,北京100074)

一種地圖匹配算法的設計與實現

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

(北京自動化控制設備研究所,北京100074)

設計一種面向定位定向導航系統的地圖匹配算法,首先通過網格劃分和建立路段連通性拓撲關系表對電子地圖數據進行預處理；然后根據車輛的行駛狀態采取不同的候選路段確定方法, 計算各候選路段的匹配度,取值最大的作匹配路段；最后采用垂直投影法求取匹配點。通過跑車數據進行仿真試驗,驗證了該算法具有良好的準確性和實時性。

地圖匹配；網格劃分；拓撲關系；匹配度；候選路段；正交投影

0 引言

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

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

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

一個完整的地圖匹配算法一般包括3個過程：一是確定誤差區域,找出車輛附近的所有候選路段；二是從所有候選路段中確定車輛當前所在路段,即匹配路段；三是確定車輛在當前路段上的具體位置,即匹配點。現有的一些地圖算法中,算法簡單的,匹配精度低,準確性差；匹配準確性較好的算法,結構復雜,計算量大,匹配實時性差[2]。因此,在保證相對較高的匹配精度的同時,最大程度提高匹配效率將成為地圖匹配算法研究的重點。

本文以車載導航系統提供的車輛位置姿態信息為樣本,以shapefile格式電子地圖道路信息為模板,提出一種綜合車輛位置、航向信息以及路段拓撲關系的地圖匹配算法,具有良好的實時性和準確性。

1 地圖數據預處理

在上述提到的地圖匹配3個過程中,確定候選路段的范圍是影響匹配效率的主要因素。尤其在匹配開始階段,因為沒有歷史信息可以利用,也不知道大致范圍,所以在尋找車輛當前所在路段時要遍歷搜索大量的路段,大大影響匹配效率。另外,候選路段數量如果很大,匹配出錯的概率也會增加,從而影響匹配精度。因此,為了快速準確地確定候選路段,在匹配開始前對電子地圖數據進行預處理,具體做法是地圖網格區域劃分和建立路段間連通性拓撲關系表。

1.1 地圖網格劃分

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

(1)

其中,[ ]為取整。

圖2 地圖網格劃分及編號Fig.2 Map mesh division and mesh number

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

1.2 建立拓撲關系表

Shapefile格式電子地圖是一種無拓撲的矢量數據結構,即只存儲了路段的位置信息和屬性信息,并沒有表示路段與路段之間的拓撲關系[4]。我們認為,由于車速是有限的,所以在一定時間范圍內,車輛離開上一匹配路段后,只能行駛在與之相連的路段,而不可能在其他路段上行駛。所以,本文根據電子地圖道路數據建立了路段間的連通性拓撲關系表(見表1)。

表1 路段間連通性拓撲關系格式

當車輛離開上一時刻的匹配路段時,利用路段節點,從拓撲關系表中找到對應的路段作為候選路段進行匹配,從而節省了尋找候選路段的搜索時間,并且可以減少誤匹配現象的出現。

2 算法的設計與實現

2.1 候選路段的確定

根據車輛行駛狀態的不同,候選路段的選取準則也不同,可分為下面3個狀態：

1)初始狀態,初始時刻沒有歷史信息可以利用,此時確定定位點所在網格,取網格內所有路段作候選路段。

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

3)更新狀態,若車輛離開上一時刻的匹配路段,則查詢拓撲關系表,找到和上一路段相連通的所有路段作為候選路段,匹配結果將是對上一時刻匹配路段的更新[5]。

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

(2)

2.2 匹配路段的確定

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

(3)

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

2.3 路段上匹配點的確定

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

(4)

2.4 算法步驟和流程

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

算法的流程如圖3所示。算法的實現步驟如下：

步驟1：載入電子地圖,對地圖數據進行預處理。

步驟2：讀入導航系統提供的定位數據。

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

步驟4：判斷車輛是否離開了上一時刻匹配路段,如果是,索引拓撲關系表,找到候選路段；否則匹配路段沒變,跳轉至步驟8。

步驟5：判斷拓撲關系表中候選路段數目N,若N=1,則該路段就是匹配路段,跳轉至步驟8；若N>1,這N條路段為候選路段。

步驟6：利用式(1)確定定位點所在網格區域,取網格內所有路段為候選路段。

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

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

3 試驗驗證

利用定位定向導航系統跑車數據在Matlab仿真工具上對地圖匹配算法進行仿真試驗驗證。圖4～圖7所示為匹配結果的圖像顯示,藍點代表車輛的定位點,紅點代表匹配點。

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

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

圖6 轉彎匹配效果圖Fig.6 Intersection turn matching effect chart

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

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

表2 匹配準確性統計表

表3 匹配時間統計表

4 結論

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

[1] 劉興權,金美含.地圖匹配算法綜述[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].哈爾濱工程大學,2012.

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

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

[6] 蘇海濱,徐俊紅,程志沖.基于權重的改進綜合地圖匹配算法[J].中南大學學報,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

解放軍總裝備部預先研究項目(51309030104)

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

10.19306/j.cnki.2095-8110.2017.02.006

U666.1

A

2095-8110(2017)02-0031-04