基于道路信息的智能地圖匹配算法

李磊磊，陳家斌，楊黎明，尹靜源，胡鳴凱，高宏斌

（1. 北京理工大學(xué) 自動化學(xué)院，北京 100081；2. 華北光學(xué)儀器有限公司，北京100053；3. 北京機電工程總體設(shè)計部，北京100039）

基于道路信息的智能地圖匹配算法

李磊磊1，陳家斌1，楊黎明2，尹靜源3，胡鳴凱1，高宏斌1

（1. 北京理工大學(xué) 自動化學(xué)院，北京 100081；2. 華北光學(xué)儀器有限公司，北京100053；3. 北京機電工程總體設(shè)計部，北京100039）

針對軍用車輛長時間、長距離高精度自主導(dǎo)航需求，提出了一種基于道路信息的智能地圖匹配算法。傳統(tǒng)地圖匹配算法在單獨使用時，都會存在一些不足之處。智能地圖匹配算法比較不同算法的優(yōu)缺點，選擇三種特點鮮明、互補性強的地圖匹配算法作為基礎(chǔ)算法，以慣性導(dǎo)航系統(tǒng)提供的導(dǎo)航信息為基礎(chǔ)，對車輛正在行駛的道路進(jìn)行識別和判斷，根據(jù)道路構(gòu)成情況自動選擇合適的算法，完成地圖匹配；并結(jié)合車輛行駛的航向和速度信息選擇橢圓形道路搜索區(qū)域。試驗車進(jìn)行5 h約240 km跑車試驗，地圖匹配定位精度約為10.33 m（CEP）。試驗結(jié)果證明該算法能夠適應(yīng)不同的道路狀況，有效抑制慣性導(dǎo)航誤差發(fā)散。

地圖匹配；慣性導(dǎo)航；航跡推算；電子地圖

導(dǎo)彈發(fā)射車需要具備遠(yuǎn)距離奔襲作戰(zhàn)能力，這就要求為其裝備的導(dǎo)航系統(tǒng)能夠長時間、長距離保持較高定位精度。傳統(tǒng)的慣性導(dǎo)航系統(tǒng)由于慣性器件誤差發(fā)散，無法滿足要求。在不考慮衛(wèi)星導(dǎo)航輔助情況下，運用地圖匹配技術(shù)[1-2]，以慣性導(dǎo)航信息為基礎(chǔ)，搜索車輛周圍的路徑信息，確定車輛正在行駛的道路，并通過地圖數(shù)據(jù)庫中道路坐標(biāo)信息對車輛位置進(jìn)行修正，從而抑制導(dǎo)航誤差發(fā)散，以滿足長時間高精度定位要求。

現(xiàn)在常用的地圖匹配算法有基于投影的匹配算法[3-5]、基于相關(guān)性的匹配算法[6]、基于模糊邏輯的匹配算法[7-8]、基于網(wǎng)絡(luò)拓?fù)潢P(guān)系的匹配算法[9-10]以及基于D-S證據(jù)推理[11-13]地圖匹配算法等。這些匹配算法在單獨使用時，都會有一些不足之處?；谕队暗钠ヅ渌惴ㄟ壿嫼唵?、速度快、實時性好，但在道路密集、道路形狀復(fù)雜和交叉路口等情況下，匹配準(zhǔn)確率較低；基于相關(guān)性的匹配算法在匹配路段特征比較明顯時才具有較好匹配效果；基于模糊邏輯的匹配算法準(zhǔn)確率高，但算法復(fù)雜，所需時間較長，計算量較大，很難滿足車輛定位的實時性要求；基于網(wǎng)絡(luò)拓?fù)潢P(guān)系的匹配算法能減少匹配道路搜索范圍，但其匹配效果有時會受到空間拓?fù)潢P(guān)系質(zhì)量的影響等等。

因此，本文提出了一種基于道路信息的智能地圖匹配算法。地圖匹配是以慣性導(dǎo)航系統(tǒng)提供的導(dǎo)航信息為基礎(chǔ)，對車輛正在行駛的道路進(jìn)行識別和判斷，車輛所在大概位置是已知的，可充分利用該信息對車輛周圍的道路情況進(jìn)行預(yù)判，根據(jù)不同的道路場景選擇合適的地圖匹配算法，提高匹配的實時性和準(zhǔn)確度。

1 地圖匹配系統(tǒng)組成

地圖匹配系統(tǒng)由慣性尋北儀、方位保持儀、高程計、里程計、導(dǎo)航顯示器、導(dǎo)航計算機和電子地圖組成，如圖1所示。其中，慣性尋北儀、方位保持儀、高程計和里程計組成航跡推算系統(tǒng)（DR系統(tǒng)）。慣性尋北儀在載體靜止的工作條件下自動完成北向基準(zhǔn)和載體姿態(tài)角的測量，為系統(tǒng)提供初始方位角；方位保持儀完成北向方位基準(zhǔn)的記憶，并敏感載體運動時航向角的變化；里程計敏感載體行駛距離，為導(dǎo)航解算提供里程信息；高程計測量載體的高程信息，使系統(tǒng)具有三維定位功能。航跡推算系統(tǒng)完成導(dǎo)航解算后，與電子地圖數(shù)據(jù)相結(jié)合，實現(xiàn)匹配導(dǎo)航。

圖1 地圖匹配系統(tǒng)Fig.1 Map matching system

2 智能匹配算法

2.1 道路搜索區(qū)域

地圖匹配中候選道路搜索區(qū)域選擇非常重要，區(qū)域過大可能會增加搜索道路的計算量，區(qū)域過小則可能漏掉正確的道路。傳統(tǒng)道路搜索區(qū)域是選定以車輛當(dāng)前位置為中心的圓形或矩形區(qū)域，本文結(jié)合多年積累的試驗數(shù)據(jù)，選擇以行車方向為長軸的橢圓形區(qū)域作為道路搜索區(qū)域，具體如圖2所示。

Fig.2 道路搜索區(qū)域示意圖Fig.2 Road searching area

圖2中，a為橢圓形道路搜索區(qū)域長半軸，b為短半軸，Ψ為橢圓形區(qū)域長半軸與北向夾角，即車輛行駛方向。基于航跡推算系統(tǒng)定位誤差和車輛行駛速度考慮，選取橢圓長半軸a和短半軸b為

2.2 匹配算法

在不同道路場景中，有效的地圖匹配算法也不相同。在傳統(tǒng)算法中選取幾種特點鮮明、互補性強的地圖匹配算法作為基礎(chǔ)算法，根據(jù)車輛正在行駛區(qū)域的道路信息，自動選擇合適的匹配算法。本文選取的基礎(chǔ)算法包括基于投影的匹配算法、基于相關(guān)性的匹配算法和基于模糊邏輯的匹配算法。

2.2.1 基于投影的匹配算法

基于投影的匹配算法設(shè)計簡單，實時性好，適合道路情況比較簡單的區(qū)域。算法原理如圖3所示。

圖3中，P點為待匹配的定位點，L1、L2表示定位點附近的道路。在投影匹配算法中，把待匹配的定位點向附近所有道路做投影，計算定位點與各道路間的投影距離ri及車輛行駛方向與道路間的夾角θi。 選出ri、θi值小于給定閾值的所有道路，并根據(jù)公式(4)計算各候選道路的距離度量值Ri：

Fig.3 基于投影的地圖匹配算法Fig.3 Map-matching algorithm based on projection

式中：Wr、Wθ分別是投影距離和方向夾角的權(quán)值。

在所有候選道路中，選擇距離度量值最小的作為匹配道路，即認(rèn)為車輛正在該道路上行駛。最后將車輛在匹配道路上的投影點作為車輛的當(dāng)前位置。

2.2.2 基于相關(guān)性的匹配算法

相關(guān)性地圖匹配算法是將采集到的車輛位置點按照順序組成定位軌跡，并將定位軌跡與數(shù)字地圖中的路段曲線軌跡進(jìn)行計算獲得兩者的相關(guān)系數(shù)，依據(jù)相關(guān)系數(shù)來判定軌跡與路段的相似性。

設(shè)航跡推算車輛行駛的軌跡為s，待確定的道路軌跡為li(i=1,2,…,n)。采用相關(guān)性算法計算出航跡推算軌跡與待確定道路軌跡的相關(guān)性系數(shù)ρi：

式中：k為采樣點，σs和分別為道路軌跡序列s（k）的標(biāo)準(zhǔn)差。ρi值較大則表明車輛行駛軌跡和該路段相關(guān)性比較高，車輛很可能正在該段道路行駛?；谙嚓P(guān)性的地圖匹配算法適合具有比較明顯道路信息特征的路段，比如岔路口拐彎處或角度變化比較大的曲線路段。

2.2.3 基于模糊邏輯的匹配算法

基于模糊邏輯的地圖匹配算法引入模糊邏輯評判規(guī)則，然后在評判規(guī)則的基礎(chǔ)上定義模糊隸屬度函數(shù)，最后依據(jù)模糊隸屬度函數(shù)，評判候選路段是否是車輛所行駛的路段。地圖匹配算法是對不確定的問題進(jìn)行定性決策，因此使用基于模糊邏輯的地圖匹配算法較幾何運算具有更好的魯棒性。匹配算法的模糊推理系統(tǒng)示意圖如圖4所示。

Fig.4 模糊推理系統(tǒng)示意圖Fig.4 Schematic of fuzzy inference system

車輛位置距離該路段的隸屬函數(shù)為

車輛航向與路段方向的差異的隸屬函數(shù)為

式中：MF1是車輛位置距離該路段的隸屬度；MF2是車輛航向與該路段方向之間的差異的隸屬度。規(guī)則 2只有在規(guī)則1的輸出超過設(shè)定的閾值時才評估，否則重復(fù)執(zhí)行這一步直到相似性超過設(shè)定的閾值。

規(guī)則 2：如果該路段與當(dāng)前行駛路段相似性在連續(xù)的幾個時間點中都很高，那么可以認(rèn)為該路段是當(dāng)前行駛路段。

2.3 匹配流程

智能地圖匹配算法首先根據(jù)航跡推算提供的基礎(chǔ)坐標(biāo)，結(jié)合車輛正在行駛的航向和速度信息，確定候選道路搜索的區(qū)域；然后，分析搜索區(qū)域內(nèi)道路構(gòu)成情況，選擇合適的地圖匹配算法；最后，通過選定的匹配算法完成地圖匹配，并對導(dǎo)航坐標(biāo)進(jìn)行修正。

當(dāng)?shù)缆匪阉鲄^(qū)域道路構(gòu)成比較簡單時，選擇基于投影的匹配算法進(jìn)行匹配；當(dāng)搜索區(qū)域道路信息有比較明顯的信息特征時，選擇基于相關(guān)性地圖匹配算法進(jìn)行匹配；當(dāng)搜索區(qū)域道路信息比較復(fù)雜時，選擇基于模糊邏輯地圖匹配算法進(jìn)行匹配。匹配算法流程如圖5所示。

模糊推理系統(tǒng)使用的規(guī)則如下：

規(guī)則 1：如果車輛位置距離該路段很近并且當(dāng)前車輛航向與該路段方向之間的差異很小，那么這條路段與當(dāng)前行駛路段相似性由下式給出：

Fig.5 匹配算法流程Fig.5 Flowchart of matching algorithm

3 試驗驗證

3.1 算法效果匹配

選擇三種具有代表性的路段對匹配算法進(jìn)行驗證。三種路段分別是簡單直行路段、轉(zhuǎn)彎路段和較為復(fù)雜路段。智能算法會自動選擇基于投影匹配算法、基于相關(guān)性匹配算法和基于模糊邏輯匹配算法，匹配效果如圖6～8所示。

Fig.6 直行路段匹配效果Fig.6 Matching effect in straight line section

Fig.7 轉(zhuǎn)彎路段匹配效果Fig.7 Matching effect in turning section

Fig.8 復(fù)雜路段匹配效果Fig.8 Matching effect in complex section

3.2 導(dǎo)航試驗

為了驗證地圖匹配算法長時間對慣導(dǎo)誤差的抑制效果，設(shè)計了沿北京市三環(huán)路線的跑車試驗。沿途?？?個位置點，分別是蘇州橋、新興橋、豐益橋、木樨園橋、十里河橋、國貿(mào)橋、三元橋和馬甸橋。在每個停靠點記錄匹配坐標(biāo)。以車上裝載的高精度實時差分GPS作為基準(zhǔn)，計算匹配坐標(biāo)誤差。試驗連續(xù)繞行三環(huán)主路5圈，試驗持續(xù)時間超過5 h，行駛里程約240 km。跑車路線圖如圖9所示，匹配坐標(biāo)誤差見表1。

導(dǎo)航坐標(biāo)系選用東北天坐標(biāo)系，X、Y分別表示北向和東向。通過表1數(shù)據(jù)計算地圖匹配系統(tǒng)定位精度為 10.33m（CEP）。從誤差分布來看，導(dǎo)航誤差并沒有因為跑車時間和跑車距離的增加而呈現(xiàn)出明顯發(fā)散趨勢，說明地圖匹配算法對慣性誤差積累起到很好的抑制作用。

Fig.9 試驗路線圖Fig.9 Experiment roadmap

表1 定位誤差試驗數(shù)據(jù)Tab.1 Positioning error test data

4 結(jié) 論

為適應(yīng)導(dǎo)彈發(fā)射車長航時高精度自主導(dǎo)航要求，提出了一種基于道路信息的智能地圖匹配算法。該算法根據(jù)航跡推算獲取的坐標(biāo)確定車輛所在大致區(qū)域，基于此區(qū)域道路構(gòu)成狀況自動選擇合適的地圖匹配算法，并在確定道路搜索范圍時，考慮航向和速度信息選擇橢圓形搜索區(qū)域。跑車實驗結(jié)果證明，該算法能夠適應(yīng)不同的道路狀況，可以較好抑制導(dǎo)航誤差發(fā)散，具有重要工程實用價值。

（References）：

[1] Hashemi M, Karimi H. A critical review of real-time map-matching algorithms: Current issues and future directions[J]. Computers, Environment and Urban Systems, 2015, 11: 153-165.

[2] Chen W, Li Z, Yu M, et a1. Effects of sensor errors on the performance of map matching[J]. Journal of Navigation, 2005, 58(02): 273-282.

[3] Bierlaire M, Chen J, Newman J. A probabilistic map matching method for smartphone GPS data[J]. Transportation Research Part C: Emerging Technologies, 2013, 2: 78-98.

[4] 王忠民, 王青, 張榮, 等. 一種基于位置點的地圖匹配改進(jìn)算法[J]. 計算機應(yīng)用研究, 2013, 30(11): 3318-3323. Wang Zhong-min, Wang Qing, Zhang Rong, et al. Improved map-matching algorithm based on position points[J]. Application Research of Computers, 2013, 30(11): 3318-3323.

[5] 孫永榮, 黃斌, 王麗娜, 等. 抗尺度變換的矢量地圖匹配導(dǎo)航方法[J]. 中國慣性技術(shù)學(xué)報, 2013, 20(1): 89-92. Sun Yong-rong, Huang Bin, Wang Li-na, et al. Vector map matching navigation method with anti-scale transformation[J]. Journal of Chinese Inertial Technology, 2013, 20(1): 89-92.

[6] 龔柏春, 羅建軍, 李歲勞, 等. 基于移動相關(guān)的最小二乘地圖匹配新算法[J]. 中國慣性技術(shù)學(xué)報, 2012, 20(4): 435-439. Gong Bai-chun, Luo Jian-jun, Li Sui-lao, et al. Novel map-matching algorithm based on moving-related least squares[J]. Journal of Chinese Inertial Technology, 2012, 20(4): 435-439.

[7] He Z, Xi-wei S, Zhuang L, et al. On-line map-matching framework for floating car data with low sampling rate in urban road networks[J]. IET Intelligent Transport Systems, 2013, 7(4): 404-414.

[8] Quddus M, Washington S. Shortest path and vehicle trajectory aided map-matching for low frequency GPS data[J]. Transportation Research Part C: Emerging Technologies, 2015, 6: 328-339.

[9] 趙東保, 劉雪梅, 郭黎. 網(wǎng)格索引支持下的大規(guī)模浮動車實時地圖匹配方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2014, 26(9): 1550-1556. Zhao Dong-bao, Liu Xue-mei, Guo Li. Real time map matching algorithm of floating car in support of spatial grid index[J]. Journal of Computer Aided Design & Computer Graphics, 2014, 26(9): 1550-1556.

[10] 韓萍, 桑威林, 趙愛軍, 等. 基于單向無跡卡爾曼濾波的飛機姿態(tài)算法[J]. 中國慣性技術(shù)學(xué)報, 2014, 22(5): 629-633. Han Ping, Sang Wei-lin, Zhao Ai-jun, et al. Simplex unscented Kalman filter for aircraft attitude algorithm[J]. Journal of Chinese Inertial Technology, 2014, 22(5): 629-633.

[11] Huang J, Qie JH, Liu CW, et a1. Cloud computingbased map-matching for transportation data center[J]. Electronic Commerce Research and Applications, 2015, 14(6): 431-443.

[12] Kim K, Seol S, Kong S H, et a1. High-speed train navigation system based on multi-sensor data fusion and map matching algorithm[J]. International Journal of Control Automation and Systems, 2015, 13(3): 503-512.

[13] 肖維麗, 岳春生, 奚玲. 基于高程的改進(jìn)D-S證據(jù)理論地圖匹配算法[J]. 計算機應(yīng)用與軟件, 2015, 32(7): 262-265. Xiao Wei-li, Yue Chun-sheng, Xi Ling. Improved D-S evidence theory map matching algorithm based on elevation information[J]. Computer Applications and Software, 2015, 32(7): 262-265.

Intelligent map-matching algorithm based on map information

LI Lei-lei1, CHEN Jia-bin1, YANG Li-ming2, YIN Jing-yuan3, HU Ming-kai1, GAO Hong-bin1

(1. School of Automation, Beijing Institute of Technology, Beijing, 100081 China; 2. Huabei Optical Instrument Co., LTD, Beijing 100053, China; 3. Beijing Electro-mechanical Engineering System Design Department, Beijing 100039, China)

In view of the military vehicle’s long-time, long-distance and high-precision autonomous navigation requirements, an intelligent map-matching algorithm based on road information is proposed. Traditional map-matching algorithms have some shortcomings when used alone. Three distinct characteristics and highly complementary map matching algorithms are picked out as the basic algorithms for intelligent map-matching algorithm by comparing the advantages and disadvantages of them. The road information is identified and judged based on inertial navigation information. An appropriate algorithm is automatically selected for map matching according to the road conditions. And the elliptical path search area is selected based on the vehicle's heading and speed information. The map matching positioning accuracy is 10.33 m (CEP) while the vehicle test is carried out by more than 5 h over approximate 240 km. Experimental results show that the algorithm can be adapted to different roads, and can effectively restrain the inertial navigation error’s diverges.

map-matching; inertial navigation; dead reckoning; electronic map

U666.1

A

1005-6734(2016)02-0170-05

10.13695/j.cnki.12-1222/o3.2016.02.006

2015-12-02；

2016-03-18

國防預(yù)研基金（9140A09050313BQ01127）；國家自然科學(xué)基金（91420203）

李磊磊（1978—），男，博士，講師，研究方向?qū)Ш健⒅茖?dǎo)與控制。E-mail: lileilei@bit.edu.cn