滕志軍，曲兆強(qiáng)，何義昌，佟育春，徐春雨，張麗偉

（1. 東北電力大學(xué) 信息工程學(xué)院，吉林 132012；2. 國網(wǎng)吉林供電公司 信息通信分公司，吉林 132000）

基于初始位置的高速公路快速地圖匹配算法

滕志軍1，曲兆強(qiáng)1，何義昌1，佟育春2，徐春雨2，張麗偉2

（1. 東北電力大學(xué) 信息工程學(xué)院，吉林 132012；2. 國網(wǎng)吉林供電公司 信息通信分公司，吉林 132000）

針對車輛行駛在高速公路過程中，傳統(tǒng)地圖匹配算法存在大量冗余檢索時間，且消除垂直誤差后仍存在水平誤差等問題，設(shè)計了一種基于初始定位信息的快速地圖匹配算法。該算法首先利用初始定位點(diǎn)到候選路段的距離與夾角確定車輛所行駛道路，然后考慮道路網(wǎng)拓?fù)浣Y(jié)構(gòu)和連通性，將后續(xù)定位點(diǎn)直接投影到初始確定的道路上，減少檢索道路的時間；同時為提高算法的精確度，在引用初始定位信息時，通過設(shè)置距離閾值剔除定位數(shù)據(jù)漂移點(diǎn)，并利用一元線性方程建立HP模型以消除水平誤差。經(jīng)理論計算和實(shí)際測試表明，該算法利用初始獲得的7個連續(xù)定位點(diǎn)，能準(zhǔn)確檢索出車輛正在行駛的道路，節(jié)省36%的檢索時間，借助HP模型可以減少定位點(diǎn)與車輛實(shí)際位置之間45%的投影誤差。因此，與連續(xù)匹配算法和垂直投影方式相比，該算法具有檢索過程簡單、檢索準(zhǔn)確率高、誤差消除大的優(yōu)勢。

高速公路；初始信息；地圖匹配；距離閾值；水平誤差

地圖匹配（Map Maching，MM）是一種新興的通過軟件來矯正定位誤差的方法。該方法把車載端獲得的定位信息與高精度的電子地圖數(shù)據(jù)相結(jié)合，通過一定的匹配算法確定車輛所行駛的實(shí)際道路并將車輛位置準(zhǔn)確顯示在可視化地圖上[1-2]。高速公路路網(wǎng)與城市街道路網(wǎng)相比，具有結(jié)構(gòu)簡單、交叉路口少、長距離單線行駛的特點(diǎn)。傳統(tǒng)的基于權(quán)重、D-S證據(jù)推理、模糊識別、卡爾曼濾波的地圖匹配算法在高速公路路網(wǎng)中都具有較好的性能[3-6]，但是基于D-S證據(jù)推理、模糊識別等的算法存在計算復(fù)雜程度高、匹配實(shí)時性偏低的缺陷，而基于距離和方向的地圖匹配算法識別過程較簡單，實(shí)時性強(qiáng)[7]，因此本文結(jié)合高速公路路網(wǎng)結(jié)構(gòu)比較簡單，車輛行駛連續(xù)性較強(qiáng)的特點(diǎn)，提出一種基于初始位置信息的高速公路快速地圖匹配算法。

該算法主要利用車輛進(jìn)入新路段的初始定位信息來確定車輛行駛道路。行駛道路確定后，若不出現(xiàn)交叉道路，對后續(xù)定位點(diǎn)不做匹配處理，直接將其投影到前一階段所確定的道路上。到達(dá)交叉路口時，重新啟動該算法完成路段確定。同時為了保證初始定位信息所確定候選道路的準(zhǔn)確性，根據(jù)高速公路限速指標(biāo)和定位誤差設(shè)置閾值剔除定位漂移值。最后利用車輛的方向角和定位點(diǎn)坐標(biāo)作線性方程消除水平誤差保證車輛在水平移動過程中的精準(zhǔn)性。

1 地圖匹配基本原理

地圖匹配技術(shù)中車輛行駛道路的確定要滿足兩個先決條件，一是待匹配的車輛正行駛在道路上，二是用作顯示的電子地圖精度要高于車輛定位誤差。第一個條件在一般情況下是滿足的；由于電子地圖誤差在5 m左右，北斗民用定位誤差在15 m左右，第二個條件也是滿足的。地圖匹配完成兩個主要過程：首先根據(jù)定位信息檢索出車輛正在行駛的道路；其次就是矯正車輛定位點(diǎn)，將接收機(jī)接收的定位點(diǎn)顯示在車輛所行駛的道路[8-10]。

為了更形象地描述地圖匹配問題，假設(shè)車輛在道路A1行駛后經(jīng)交叉路口駛?cè)氲缆稟2，車載接收設(shè)備獲得的定位點(diǎn)為“○”，車輛實(shí)際位置為“●”，由圖1可以看出，定位點(diǎn)集合為車輛實(shí)際位置為地圖匹配算法就是通過一定規(guī)則確定車輛所行駛的道路，并將U··投影到U上。傳統(tǒng)投影過程是直接做道路垂線，垂足為車輛顯示位置，該方法只是消除了垂直誤差，本文提出一種根據(jù)定位角度做斜線的投影方法來消除水平誤差，而且由于各種誤差原因，導(dǎo)致的定位漂移點(diǎn)（如點(diǎn)4·）可根據(jù)車輛速度、角度、硬件誤差建立的閾值范圍進(jìn)行剔除，并根據(jù)定位信息進(jìn)行插值（插值點(diǎn)為★）彌補(bǔ)缺失定位點(diǎn)。

圖1 匹配原理示意圖Fig.1 Schematic diagram of matching principle

2 算法實(shí)現(xiàn)框架

高速公路的路網(wǎng)不會存在復(fù)雜交叉路段，車輛會長時間在一條道路上行駛，因此地圖匹配出現(xiàn)誤匹配的情況很少發(fā)生。在基于傳統(tǒng)高速公路地圖匹配算法上，本文以基于距離和方向的地圖匹配算法為基礎(chǔ)，主要以提高算法效率和匹配精度兩方面進(jìn)行研究和改進(jìn)。本文算法框架主要包括三個主要部分：①確定定位數(shù)據(jù)閾值范圍，利用前一點(diǎn)角度和速度信息進(jìn)行插值彌補(bǔ)剔除的定位點(diǎn)；②利用基于距離和角度的匹配算法，確定車輛行駛道路；③考慮有效定位點(diǎn)角度信息，確定車輛行駛方向，利用修正定位角度和坐標(biāo)值作車輛投影點(diǎn)消除水平誤差。下面詳細(xì)介紹各個步驟。

2.1 設(shè)置閾值剔除漂移點(diǎn)并插值

目前的接收機(jī)具有修正部分隨機(jī)誤差的功能。對于由相對論效應(yīng)、大氣層延遲、多徑效應(yīng)引起的誤差目前已有相應(yīng)的解決方法，而且由于高速路處于較空曠地帶，大型建筑物、密集樹林半透明物體等干擾因素較弱。但是由于衛(wèi)星瞬間失鎖，或者高速路附近大型電力設(shè)備的影響，車輛接收的數(shù)據(jù)會出現(xiàn)突變的波動，即出現(xiàn)數(shù)據(jù)漂移現(xiàn)象，如圖2所示，會有個別定位點(diǎn)不符合定位軌跡特性，出現(xiàn)遠(yuǎn)離道路的現(xiàn)象，設(shè)置閾值就是為了找出漂移點(diǎn)并做插值處理。

圖2 定位數(shù)據(jù)漂移特征Fig.2 Positioning data drift characteristics

漂移值的主要特征是車輛定位點(diǎn)中的速度和經(jīng)緯度信息出現(xiàn)異常，出現(xiàn)遠(yuǎn)離道路的異常情況，因此本文采用門限技術(shù)對漂移值進(jìn)行甄別，通過設(shè)置一個距離閾值，對距離外的定位點(diǎn)剔除并插值，距離的閾值由速度和定位誤差決定。首先得出浮動車的速度上限Vmax：

式中，Vmax為車輛速度顯示上限，Vhmax為高速公路最高限速，Vs為衛(wèi)星瞬時速度誤差。故在速度限制下車輛最大距離偏移量為

其中：Δt為兩個相鄰定位點(diǎn)的時間間隔，由Vs帶來的誤差范圍用誤差圓來描述；r為一定置信水平下定位數(shù)據(jù)的誤差圓半徑，由此可得下一定位點(diǎn)的距離閾值，如圖3所示。

圖3 閾值范圍示意圖Fig.3 Schematic diagram of threshold range

距離閾值由兩部分組成：

當(dāng)出現(xiàn)漂移值時，利用車輛前一點(diǎn)速度和車輛方向進(jìn)行插值，如圖4所示。由于車輛獲取定位點(diǎn)的頻率較高，當(dāng)車輛在弧線路段行駛時可以將道路看作短距離的直線路段，因此插值后定位點(diǎn)坐標(biāo)為：

圖4 插值原理圖Fig.4 Interpolation principle

2.2 基于距離和方向的快速地圖匹配算法

對缺失的定位點(diǎn)補(bǔ)全后，進(jìn)行候選路段的確定，其中候選道路是在一定范圍內(nèi)選擇的，該范圍內(nèi)包括的道路應(yīng)包含車輛正在行駛的路段，令分別為車輛向東方向與向北方向定位誤差的標(biāo)準(zhǔn)差，是方差，是協(xié)方差，則誤差圓的半徑R為：

如圖5所示，pi為車輛定位點(diǎn)，虛線范圍為誤差圓?？梢钥闯?，在誤差區(qū)域內(nèi)存在三條候選道路而剔除掉三條道路，定位點(diǎn)在三條道路的投影點(diǎn)為，投影距離為di（i=1,2,3），通過投影距離以及車輛方向與道路方向夾角判斷車輛所行駛的道路。

圖5 誤差圓示意圖Fig.5 Error circle

一般車輛接收設(shè)備每隔 1～5 s接收一次定位點(diǎn)，由于車輛在高速公路行駛速度較快，車輛連續(xù)7個定位點(diǎn)的行駛距離所占候選道路的比重能保證算法的準(zhǔn)確性，因此本文通過7個定位點(diǎn)的平均匹配程度來確定車輛行駛道路。假設(shè)iθ為道路方向與車輛方向夾角，為定位點(diǎn)到候選道路的距離，α和β是兩個因素的權(quán)重，考慮高速公路道路弧度較小，可近似看作直線，因此本文地圖匹配算法的綜合評價函數(shù)為：

當(dāng)車輛進(jìn)入高速公路后，車載接收設(shè)備會在t1時刻獲得第一個定位點(diǎn)。首先計算第一個定位點(diǎn)到各個候選路段的綜合評價函數(shù)值，并將定位點(diǎn)暫時投影到匹配程度最高，也就是W值最低的路段；之后進(jìn)行t2時刻定位點(diǎn)的匹配，從實(shí)際情況可以知道，t2時刻定位點(diǎn)所確定的候選范圍內(nèi)的道路與t1時刻所確定的候選路段差別不大，如果t2時刻出現(xiàn)新道路，可令t1時刻對該道路的匹配程度為 0，同時并將該時刻定位點(diǎn)投影到評價函數(shù)值最低的路段，同理對時刻定位點(diǎn)做相同處理；最后得出每條道路的平均匹配程度，選擇最高平均匹配程度的道路，即W最低的路段作為車輛行駛道路。值計算公式為式(7)，選擇

道路作為車輛正在行駛道路。路段確定后，將前7個點(diǎn)位點(diǎn)矯正投影到所確定道路上，之后的定位點(diǎn)不做匹配處理，直接將定位點(diǎn)投影到該條道路上，當(dāng)出現(xiàn)交叉路口時，重新啟動該算法，確定下一階段要匹配的道路。

2.3 HP模型建立

車輛所行駛道路確定后，將定位點(diǎn)投影到所確定道路上，傳統(tǒng)投影方式如圖 6(a)所示，根據(jù)道路角度和車輛行駛角度將定位點(diǎn)PM投影到與道路的垂點(diǎn)P。該方式僅僅消除了車輛與道路間的垂直誤差，車輛與道路間水平誤差仍然存在，因此本文提出一種兩直線相交的方式確定車輛在道路的準(zhǔn)確位置，即建立一種水平投影（Horizontal Projection，HP）模型，如圖6(b)所示，將車輛定位點(diǎn)所在直線與道路所在直線交點(diǎn)作為車輛的實(shí)際位置。

圖6 垂直和水平投影示意圖Fig.6 Schematic of vertical and horizontal projection

圖6(b)中iθ和hθ分別是車輛行駛方向和道路方向與正北方向的夾角，由于高速公路道路角度波動較小，和iθ做車輛定位點(diǎn)所在直線方程YM，利用與之相近道路點(diǎn)可以將長距離道路近似為一條直線，若進(jìn)入弧線道路，可通過較少數(shù)量路點(diǎn)構(gòu)建直線方程，具體投影過程為：利用定位點(diǎn)和hθ做道路所在直線方程YG，先求聯(lián)立方程：

在坐標(biāo)系下，所求道路一般都與正北方向存在夾角，即斜率存在，因此所求交點(diǎn)即為方程組(10)的唯一解。求得位置參數(shù)后建立方程組：

求得解P(x,y)為兩直線交點(diǎn)，

通過前7個定位點(diǎn)確定候選道路后，未出現(xiàn)交叉等判別路口時，便一直將該路段作為車輛行駛道路，僅僅將接收或修正的定位點(diǎn)水平投影到道路上，不用額外判斷車輛行駛在哪一條道路。

3 算法測試

3.1 實(shí)測驗(yàn)證

為了驗(yàn)證本文算法的實(shí)際性能，選取吉林市繞城高速部分道路作為測試路線，車載定位模塊采用北斗UM220模塊，設(shè)定采樣間隔為 2 s，地圖為 MapInfo格式的吉林省道路數(shù)據(jù)，比例尺為 1︰200，兩個權(quán)重分別設(shè)置為0.5，車輛首先進(jìn)入岔口1，此時在候選區(qū)域內(nèi)存在的三條候選道路從下向上記為經(jīng)過岔口 2時將候選道路按照從下向上記為經(jīng)過岔口3時將候選道路從左到右記作圖7為車輛定位軌跡，可以看出，定位點(diǎn)分布于車輛行駛道路的兩側(cè)，有些定位點(diǎn)離不同道路距離很相近，單純靠1個定位點(diǎn)匹配值確定實(shí)際行駛道路容易出現(xiàn)誤差。

圖7 車輛軌跡圖Fig.7 Vehicle track

圖8 匹配效果圖Fig.8 Matching effect

圖8為車輛匹配效果圖，其中表1、2、3分別是前7個定位點(diǎn)在岔口1、2、3候選道路上匹配值。由表1看出，在t1時刻，定位點(diǎn)在A3道路匹配程度最高，但是7個定位點(diǎn)中，1A道路平均匹匹配值最低，故1A應(yīng)是車輛行駛道路；在表2中，候選道理B1匹配值最低，即B1為車輛行駛道路；在表3中，從平均匹配值中可以看出C2道路為候選道路，從單點(diǎn)匹配值中也能得出相應(yīng)結(jié)果，但從平均匹配值可以消除靠單點(diǎn)來確定道路的不確定性。

3.2 仿真比較

為了驗(yàn)證本文算法的快速性和誤差消除情況，對三種算法進(jìn)行仿真比較。仿真條件設(shè)置為候選道路條數(shù)固定，固定為三條，前1000 m是本文算法初始確定車輛行駛道路階段。仿真結(jié)果如圖9所示?？梢钥闯?，在前1000 m內(nèi)本文算法相對其它算法匹配時間相當(dāng)，這是因?yàn)楸疚乃惴ㄔ谒酵队斑^程中要復(fù)雜些，但是車輛駛出1000 m后，由于本文算法不需重新檢索道路，單點(diǎn)平均匹配時間降至 3.6 ms，而其它兩種算法均在5.5 ms左右，相對于其它算法節(jié)省36%的冗余時間。系統(tǒng)的誤差包括車輛定位點(diǎn)到車輛實(shí)際位置的垂直誤差和水平誤差。由圖10可以看出，僅通過垂直投影只能消除30%左右的定位誤差，通過水平方式的投影可以消除車輛實(shí)際行駛位置與匹配點(diǎn)之間大約45%的誤差，相對其他算法匹配準(zhǔn)確度有較明顯提高，因此本文算法不僅具有時間上的快速匹配特點(diǎn)，還可以最大限度地消除定位誤差，保證車輛在道路行駛的連續(xù)性。

圖9 時間比較Fig.9 Time comparison

圖10 誤差消除仿真Fig.10 Simulation on error elimination

表1 岔口1候選道路匹配值Tab.1 Candidate road matching values at Fork 1

表2 岔口2候選道路匹配值Tab.2 Candidate road matching values at Fork 2

表3 岔口3候選道路匹配值Tab.3 Candidate road matching values at Fork 3

4 結(jié) 論

針對高速公路結(jié)構(gòu)簡單的特點(diǎn)，本文提出一種基于車輛初始定位信息的高速公路快速地圖匹配算法。該算法在通過初始定位信息確定候選道路后，若不出現(xiàn)交叉道路，則將后續(xù)定位點(diǎn)直接投影到所確定的道路上，大大節(jié)省了不必要的匹配時間。同時，該算法通過設(shè)置閾值降低檢索候選道路的時間和建立HP模型減少了水平誤差。實(shí)測結(jié)果表明，該算法能準(zhǔn)確地確定車輛的行駛道路，節(jié)省了車輛直線行駛時不必要的檢索道路所需的時間。

（References）：

[1]李清泉, 胡波, 樂陽. 一種基于約束的最短路徑低頻浮動車數(shù)據(jù)地圖匹配算法[J]. 武漢大學(xué)學(xué)報（信息科學(xué)版), 2013, 38(7): 805-808.Li Qing-quan, Hu Bo, Le Yang. A data map matching algorithm based on constrained shortest path low frequency floating car[J]. Geomatics and Information of Wuhan University, 2013, 38(7): 805-808.

[2]Yang Xin-yong, Huang Sheng-guo. Quick road choice method in map matching algorithms[J]. Journal of South China University of Technology, 2016, 32(2): 62-66.

[3]Ma Chun-yang, Zhang Xin, Gao Peng. Space-map-matchingbased candidate selection for GPS map matching[C]//2016 IEEE International Conference on Service Operations and Logistics, and Informatics. 2016: 77-82.

[4]Peker A U, Tosun O, Akin H L, et al. Fusion of map matching and traffic sign recognition[C]//IEEE Intelligent Vehicles Symposium. 2014: 867-872.

[5]Berry J W, Fleischer L, Hart W E, et al. Sensor placement in municipal water networks[J]. Journal of Water Resources Planning & Management, 2005, 131(3): 237-243.

[6]王新龍, 于潔. 基于矢量跟蹤的SINS/GPS深組合導(dǎo)航方法[J]. 中國慣性技術(shù)學(xué)報, 2009, 17(6): 710-717.Wang Xin-long, Yu Jie. Deeply SINS/GPS integrated navigation method based on vector tracking[J]. Journal of Chinese Inertial Technology, 2009, 17(6): 710-717.

[7]Komiya K, Miyashita S, Maruoka Y, et al. Control of autonomous mobile robot using map matching with optimized search range[J]. Electrical Engineering in Japan,2015, 190(4): 66-75.

[8]Li Liang, Quddus M, Zhao Lin. High accuracy tightlycoupled integrity monitoring algorithm for map-matching[J]. Emerging Technologies, 2013, 36(3): 13-26.

[9]Su Hai-bin, Wang Guang-zheng, Wang Ji-dong. Map matching algorithm based on fuzzy neural networks[J].Journal of University of Science and Technology Beijing,2012, 34(1): 43-47.

[10]孟陽, 高社生, 高兵兵, 等. 基于UFK的INS/GNSS/CNS組合導(dǎo)航最優(yōu)數(shù)據(jù)融合方法[J]. 中國慣性技術(shù)學(xué)報, 2016, 24(6): 746-751.Meng Yang, Gao She-sheng, Gao Bing-bing, et al. UFK-based optimal data fusion method for integrated INS/GNSS/CNS[J]. Journal of Chinese Inertial Technology,2016, 24(6): 746-751.

Fast map-matching algorithm for highway based on initial position

TENG Zhi-jun1, QU Zhang-qiang1, HE Yi-chang1, TONG Yu-chun2, XU Chun-yu2, ZAHNG Li-wei2
(1. Department of Information Engineering, Northeast Dianli University, Jilin 132012, China;2. Communication Branch, State Grid JiLin Power Supply Company, Jilin 132011, China)

The traditional map-matching algorithms have large amount of redundant retrieval time, and the horizontal error still exists after eliminating the vertical error. To solve these problems, a fast map-matching algorithm based on initial location information is designed for the vehicle traveling in the expressway. First,the algorithm uses the distance and the angle between the initial positioning point and the candidate road section to determine the vehicle’s running road. Then, considering the road network topology and connectivity, the subsequent positioning point is directly projected onto the initial determined road to reduce the time of searching the road. In order to improve the accuracy of the algorithm, when the initial location information is referenced, the drifting data is removed by setting the distance threshold, and the HP model is established by using the univariate linear equation to eliminate the horizontal error. Theoretical calculation and actual test show that, the proposed algorithm can accurately retrieve the road where the vehicle is traveling and save 36% of the retrieval time by using the seven consecutive positioning points, and the HP model can reduce 45% of the projection error between the positioning point and the actual position of the vehicle.Compared with traditional map-matching algorithms, the proposed algorithm has the advantages of simple retrieval process, high retrieval accuracy, and significant reduction of horizontal error.

express way; initial information; fast map matching; threshold of distance; horizontal error

1005-6734(2017)04-0461-05

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

P208

A

2017-04-17；

2017-07-25

國家自然科學(xué)基金項(xiàng)目（51277023）

滕志軍（1973—），男，教授，研究方向?yàn)闊o線通信技術(shù)。E-mail: 753731087@qq.com