交叉路段背景下改進的D-S證據(jù)理論地圖匹配算法

滕志軍，張 宇，李昊天

（1.東北電力大學(xué) 現(xiàn)代電力系統(tǒng)仿真控制與綠色電能新技術(shù)教育部重點實驗室，吉林132012；2.東北電力大學(xué) 電氣工程學(xué)院，吉林132012；)

隨著經(jīng)濟的快速發(fā)展以及人口向大城市發(fā)展浪潮的興起，城市交通越來越發(fā)達，道路越來越復(fù)雜。在實際的車輛導(dǎo)航中，由于GPS 的系統(tǒng)誤差、信號的傳輸誤差、數(shù)據(jù)的偶然誤差以及電子地圖的精度問題等，導(dǎo)致GPS 軌跡點和實際道路點存在偏差[1]，這會使駕駛者偏離正確行駛路線，錯誤駕駛，更嚴重的是可能會帶來交通事故。因此，一種快速、有效、準確的方法對提高導(dǎo)航性能尤為重要。目前主要有兩種解決方法[2]，一種是提高GPS 軌跡點的精度以及電子地圖的精度，但該方法比較復(fù)雜，成本也比較高，特別是現(xiàn)在的道路日新月異，很難及時對電子地圖進行更新；另一種方法是通過地圖匹配對GPS 軌跡點進行一系列處理，特別是對偏離正確道路的軌跡點數(shù)據(jù)進行糾正，使其重新定位到正確道路上，該方法比較容易實現(xiàn)，成本也比較低，成為當前研究熱點。

地圖匹配技術(shù)應(yīng)用廣泛，為車輛導(dǎo)航、交通流分析、地理社交網(wǎng)絡(luò)分析等領(lǐng)域[3-6]提供與位置服務(wù)相關(guān)的幫助。目前國內(nèi)外提出的算法主要是針對非特定路段即普通路段，主要有基于概率的地圖匹配算法[7]、基于幾何的地圖匹配算法[8]、基于拓撲約束的地圖匹配算法[9-10]、基于權(quán)重的地圖匹配算法[11-12]等。這些算法各有優(yōu)缺點，原理簡單、容易實現(xiàn)的算法匹配精度不高，原理復(fù)雜、實現(xiàn)難度大的算法匹配精度高。交叉路段[13]是路網(wǎng)中最復(fù)雜的情況，道路密度大且連接復(fù)雜，目前的地圖匹配算法一般把它當作普通道路處理，極有可能造成誤匹配、不匹配、匹配精度低等問題，因此交叉路段的匹配是地圖匹配的難點[14]。如圖1，汽車行駛在A 路段，目的地為Z 點，正準備進入連續(xù)的交叉路段，真實軌跡為A 路段到B 路段，但由于匹配錯誤，將軌跡點錯誤匹配到C 路段，此時要到達目的地則需要右拐進入D 路段，但對于真實軌跡而言，此時右拐相當于進入E 路段，離目的地越來越遠，導(dǎo)致最終的行駛路線與正確的路線有很大不同，因此提高交叉路段的地圖匹配精度對我們快速準確到達目的地有著非常重要的意義。針對交叉路段存在的問題，本文提出一種交叉路段背景下改進的D-S 證據(jù)理論算法，重點利用方向證據(jù)對傳統(tǒng)的候選路段概率公式進行改進來彌補傳統(tǒng)D-S 證據(jù)理論中交叉路段精確度不高的問題。

圖1 錯誤匹配示意圖Fig.1 Mismatching diagram

1 地圖匹配算法的實現(xiàn)

1.1 數(shù)據(jù)預(yù)處理

在地圖匹配前，首先要對數(shù)據(jù)進行預(yù)處理。數(shù)據(jù)預(yù)處理由兩個部分組成:剔除異常數(shù)據(jù)并插值[15]補全缺失的數(shù)據(jù)和生成網(wǎng)格索引。

1.1.1 剔除異常數(shù)據(jù)并補全缺失的數(shù)據(jù)

城市道路路況復(fù)雜，存在隧道、高架橋和密集的高大建筑物等，可能會影響GPS 信號的傳輸，從而使接收機獲取的數(shù)據(jù)異常。為了減小異常數(shù)據(jù)對匹配性能的影響，需要對GPS 數(shù)據(jù)進行處理，剔除異常數(shù)據(jù)并利用插值法根據(jù)兩個連續(xù)的車輛歷史定位點來補全下一個缺失的數(shù)據(jù)。定位點中包含的信息有:經(jīng)緯度、車輛速度、車輛行駛方向與正北方向的夾角、時間戳等。剔除原理如圖2所示，插值原理如圖3所示。

圖2 剔除原理圖Fig.2 Schematic of elimination

本文設(shè)置一個距離閾值R，對超過閾值范圍的定位點進行剔除，距離閾值由兩部分共同決定，分別是車輛最大偏移量和定位誤差。

由式(1)首先計算車輛的最大速度Vmax。

其中Vtmax為道路最高限速，Vs為瞬時速度誤差。故車輛最大偏移量L 為:

其中Δt為采樣間隔。r 為一定置信水平下定位數(shù)據(jù)的誤差圓半徑，由此可得距離閾值。

定位點到路段的距離超過距離閾值，則該定位點剔除，否則保留該定位點。

圖3 插值原理圖Fig.3 Schematic of interpolation

由于在交叉路段車輛采樣頻率較高，因此任何兩個相鄰采樣點經(jīng)過的路段可以看成是直線路段。本文插值后的定位點坐標如式(4)(5)所示，其中(xi,yi)表示當前需插值補全的定位點坐標，(xi-1,yi-1)表示車輛前一個歷史定位點坐標，vi-1為車輛前一歷史定位點行駛速度，ψi-1、ψi-2分別表示車輛在前兩個定位點時的行駛方向與正北方向的夾角。

1.1.2 生成網(wǎng)格索引

地圖匹配過程中需要獲取GPS 定位點的候選路段，最基礎(chǔ)的方法是每獲得一個定位點就查詢一次電子地圖中的整個道路網(wǎng)絡(luò)，該方法比較精確但會導(dǎo)致耗時較長，從而影響匹配性能，因此本文引入網(wǎng)格索引[16]，從而減少查詢時間、快速地獲取候選路段。網(wǎng)格索引的基本思想是，將整個電子地圖分成若干個格網(wǎng)，提前算出每個網(wǎng)格中所包含的或相交的路段。當進行查詢時，首先確定對象所在的格網(wǎng)，然后再快速查詢所在網(wǎng)格所包含的候選路段，大大提高查詢速度。

1.2 候選集獲取

對定位數(shù)據(jù)預(yù)處理后，根據(jù)定位數(shù)據(jù)信息來確定實際道路所在的大致區(qū)域，目前常用方法是根據(jù)概率確定一個誤差橢圓，該橢圓區(qū)域內(nèi)包含車輛位置。誤差橢圓推導(dǎo)公式為:

其中，a、b分別是橢圓長、短半軸，σX和σY分別是定位點經(jīng)度和緯度的標準差，σXY是協(xié)方差，φ是橢圓長半軸與正北方向的夾角，σ0是可調(diào)因子。由以上橢圓公式可以看出，相關(guān)參量計算比較復(fù)雜，因此本文對其進行簡化，減少計算開銷，簡化后的橢圓中心為當前定位點Pi(xi,yi)，其相關(guān)參量計算為:

2a'、2c'分別為簡化后的橢圓的長軸和焦距。在簡化后的橢圓中，基于網(wǎng)格索引確定軌跡點所處的網(wǎng)格，并查詢以該網(wǎng)格為中心的3×3 的網(wǎng)格內(nèi)誤差圓中所包含的或與誤差圓相切的路段作為候選路段。設(shè)從誤差圓中提取的全部候選道路集合為D={S1,S2,…Si,…,Sk|i=1,2…k}，過程如圖4所示，點O為軌跡點，K、L、M、N 為以該軌跡點為中心的3×3網(wǎng)格中的路段，在這些路段中尋找誤差圓中包含的或與誤差圓相切的路段，最終得到點O 的候選路段為M和N。

圖4 獲取候選路段示意圖Fig.4 The diagram of obtaining the candidate road section

1.3 基于交叉路段的D-S 證據(jù)理論地圖匹配算法

1.3.1 距離的概率分配函數(shù)m1(Si)

距離是地圖匹配算法中最主要的判斷準則，某一定位點最有可能的真實位置就是在距離其最近的道路上。根據(jù)距離的遠近給定位點的所有候選路段分配不同的概率m1(Si)，其中i=1,2,3…k。且定位點的所有候選路段距離的概率之和為1。距離證據(jù)函數(shù)αi構(gòu)造為

式中di為GPS 定位點到候選路段Si的最短距離，距離的概率分配函數(shù)構(gòu)造如式(12)。

如圖5，計算距離di時，分為兩種情形（P1和P2為定位點），設(shè)定位點坐標為(x,y)，道路兩端端點的坐標為M(x1,y1)，N(x2,y2)。

圖5 最短距離計算Fig.5 Calculation of shortest distance

①定位點P1在路段MN 上的投影點為P3，且P3在道路上，則線段P1P3的長度即為所求的最短距離d1。

②定位點P2在路段NM 上的投影點為P4，但P4并不在路段上，而是在它的延長線上，此時取距離P2最近的道路點為M，最短距離d2即為線段P2M 的長度。

1.3.2 方向的概率分配函數(shù)m2(Si)

方向是車輛周圍存在較多候選道路時確定匹配路段的另一判斷準則。在考慮方向時，直接計算車輛行駛方向與所屬道路方向之間夾角比較復(fù)雜，本文中先得出車輛行駛方向與正北方向的夾角以及所屬道路方向與正北方向的夾角，然后將兩夾角作差即可得出車輛行駛方向與所屬道路方向之間的夾角。根據(jù)兩者之間夾角的大小對定位點的所有候選路段分配不同的概率m2(Si)，其中i=1,2,3…k。同樣定位點的所有候選路段方向的概率之和為1。方向證據(jù)函數(shù)βi構(gòu)造為

式中θi為車輛行進方向與所屬道路方向之間的夾角，則方向的概率分配函數(shù)定義式為

如圖6所示，在道路Si上選取一直線路段并在其上任選兩點（記為P 和Q），以P 為原點，設(shè)Q 坐標為(x3,y3)，通過式(17)計算可得道路Si與北向夾角γi。

圖6 道路方向與車輛方向夾角示意圖Fig.6 The diagram of the angle between the road direction and the vehicle direction

若x3=0，y3＜0，則γi=π；x3=0，y3＞0，則γi=0。

至于車輛與北向夾角ψ，目前許多定位軟件可直接獲取。

綜上所述，車輛行進方向與所屬道路方向之間差值θi為式(18)。

1.3.3 候選路段概率計算

本文研究對象為交叉路段，其定位點有可能在各條道路之間，由于各道路之間的方向角相差較大，因此相對距離信息而言，方向信息的可靠性較強?；诜较蛐畔⑵ヅ涞降趇條路段的可信度取決于匹配到除第i條路段以外的其它路段，即匹配到除第i條路段以外的其它路段的概率越小，匹配到第i條路段的可信度就越大。因此可信度定義如式(19)。

在求出了距離的概率分配函數(shù)m1(Si)和方向的概率分配函數(shù)m2(Si)以及可信度之后，進行候選路段概率計算，候選路段概率公式構(gòu)造如式(20)。

其中，F(xiàn)、G是GPS 點的候選路段。選取該真實GPS點概率最大值對應(yīng)的候選路段作為該GPS 點的匹配路段，即認為當前時刻車輛在該路段上。

1.3.4 算法步驟和流程

步驟1:對數(shù)據(jù)進行預(yù)處理。設(shè)閾值去除異常數(shù)據(jù)，插值補全缺失數(shù)據(jù)，并進行網(wǎng)格索引減少匹配時間。

步驟2:根據(jù)簡化的誤差圓獲取候選道路集。

步驟3:計算距離和方向的基本概率函數(shù)。

步驟4:根據(jù)方向證據(jù)定義可信度。

步驟5:改進候選路段概率公式，計算軌跡點的所有候選路段概率。

步驟6:對候選路段概率進行排序，概率最大值對應(yīng)的路段即為匹配路段。

2 算法的實測驗證與仿真比較

2.1 實測驗證

為了驗證改進型地圖匹配算法性能，對算法進行模擬實測驗證。定位模塊選取車載導(dǎo)航常用的GPSUM220 雙模模塊，采樣頻率為2 Hz。本文在多種主要為交叉路段的城市路網(wǎng)環(huán)境下進行測試。

圖8 實測匹配軌跡Fig.8 Measured matching trajectory

圖8為本文算法下的一個匹配圖，各定位點能很好地匹配到所行駛的道路上，在連續(xù)的多個交叉路段仍能有極高的匹配準確率。

2.2 仿真比較

圖9為直接投影算法、傳統(tǒng)D-S 證據(jù)理論算法、曲線擬合匹配算法和本文改進D-S 證據(jù)理論匹配算法四種不同地圖匹配算法在相同條件下的各自匹配準確率仿真圖。其中算法的準確率是用匹配正確的定位點數(shù)與獲得的總定位點數(shù)的比值來衡量?？梢钥闯?，本文算法在平行路段的匹配準確率相對于其它地圖匹配算法要低，但在交叉路段其匹配準確率極高，匹配率約為97%，對比其它方法在準確率上至少提高4%，這是由于本文算法是針對交叉路段，重點使用方向信息，因此本文算法在交叉路段最適用，但對于側(cè)重于距離信息的平行路段則效果較差，在匹配準確率上比不上針對非特定路段的其它三種算法。

圖9 匹配準確率對比Fig.9 Comparison of matching accuracy

圖10～13 分別為四種算法在候選路段條數(shù)分別為2、3、4、5 時的單點匹配時間的仿真結(jié)果。其中，藍色曲線是直接投影算法，綠色曲線是傳統(tǒng)D-S 證據(jù)理論算法，黑色曲線是曲線擬合算法，紅色曲線是本文算法。匹配時間為從獲取定位點到確定候選路段所需的平均時間。由四幅圖橫向?qū)Ρ葋砜矗S著候選區(qū)域內(nèi)候選路段的增加，本文算法單點匹配時間雖也隨之增加但增幅最少，當候選區(qū)域內(nèi)有兩條候選路段時，本文算法的單點匹配時間為4.2 ms 左右，當候選區(qū)域內(nèi)有五條候選道路時，本文算法單點匹配 時間僅為5.4 ms 左右。由四幅圖縱向?qū)Ρ葋砜矗谒姆N算法中，不論候選區(qū)域內(nèi)有幾條候選道路，本文改進算法的單點匹配時間均低于其它算法，總體而言，本文算法在時間上至少可提高1 ms 左右。實時性較好。

圖10 兩條候選路段時對應(yīng)的單點匹配時間Fig.10 Single point matching time for two candidate road sections

圖11 三條候選路段時對應(yīng)的單點匹配時間Fig.11 Single point matching time for three candidate road sections

圖12 四條候選路段時對應(yīng)的單點匹配時間Fig.12 Single point matching time for four candidate road sections

圖13 五條候選路段時對應(yīng)的單點匹配時間Fig.13 Single point matching time for five candidate road sections

3 結(jié) 論

本文以交叉路段為研究對象，提出一種交叉路段背景下改進的D-S 證據(jù)理論地圖匹配算法，通過設(shè)置距離閾值剔除異常點，并借助插值法補全缺失點，簡化誤差橢圓減少匹配時間，構(gòu)造方向和距離的基本概率函數(shù)及引入可信度改進候選概率函數(shù)，最終確定匹配路段。結(jié)果表明，該算法提高了匹配精度并縮短了定位點的單點匹配時間，能很好地解決交叉路段匹配難的問題。