基于三證據(jù)DS理論的雙模式地圖匹配算法

王 科,李 鵬,金 瑜,劉 宇

(1.武漢科技大學 計算機科學與技術(shù)學院,武漢 430065;2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室,武漢 430065)

0 概述

近年來,汽車上電子地圖[1]的普及率越來越高。大多數(shù)時候,汽車總是行走在道路上,現(xiàn)有的定位手段[2]如GPS、網(wǎng)絡(luò)定位、基站定位等都不能精確地給出定位坐標,地圖匹配的工作就是將定位結(jié)果糾正到正確的道路上,并盡可能符合汽車的準確位置。

常見的地圖匹配算法有直接投影法、概率統(tǒng)計算法、拓撲結(jié)構(gòu)算法、相關(guān)系數(shù)算法、DS證據(jù)理論算法等[3-9]。直接投影法是把定位點垂直投影到最近的道路上,此方法雖然計算量小,但誤差較大,實際應用中是在最終確定了正確道路之后用此方法確定精確位置。概率統(tǒng)計算法的基本思想是根據(jù)定位坐標設(shè)置一個置信區(qū)域,計算誤差橢圓,從中提取待匹配的道路節(jié)點信息,然后利用定位的方向、速度等信息確定匹配道路。但誤差橢圓的計算和道路的篩選會帶來巨大的計算量,無法保證系統(tǒng)的實時性。拓撲結(jié)構(gòu)算法是在弧段和弧段之間建立了拓撲關(guān)系的基礎(chǔ)上進行的,通過對歷史匹配信息的綜合,分析道路網(wǎng)的拓撲結(jié)構(gòu),確定匹配路段。由于考慮單一信息,對于較為復雜的道路,此類算法準確率會降低。相關(guān)系數(shù)算法是通過計算一段行駛時間內(nèi)的定位點與數(shù)據(jù)庫中各道路存儲結(jié)點的相關(guān)性系數(shù),選出相關(guān)性最高的作為匹配道路。這種算法需要較多的較準確的定位點才能準確匹配,但對于多條道路弧線相似的情況,不能準確識別。DS證據(jù)理論算法是對所有的候選道路集,選出2條及以上可以證明定位點在該道路上的證據(jù),并構(gòu)造適當?shù)淖C據(jù)函數(shù),分別對每條道路進行證據(jù)融合并計算出基本概率分配函數(shù),函數(shù)值最高的即為最佳匹配道路。此外,還有基于曲率積分的地圖匹配算法[10]、基于模糊邏輯識別的地圖匹配算法[11]、基于人工神經(jīng)網(wǎng)絡(luò)的地圖匹配算法[12]等。

本文針對當前基于DS證據(jù)理論的地圖匹配算法進行改進,在距離和方向2個證據(jù)的基礎(chǔ)上,增加了一個歷史可信證據(jù),通過對3個證據(jù)的融合來提高匹配結(jié)果的穩(wěn)定性和準確率。另外,由于地圖道路網(wǎng)的復雜性,一種匹配模式不能適用于所有類型的道路。對于所有道路,本文算法將其分為路口和路段兩部分,對這2種不同的道路采用不同的模式進行匹配。路口模式是對路口的匹配,在路口使用概率統(tǒng)計算法確定誤差區(qū)域,從中提取候選道路,然后使用基于三證據(jù)的DS證據(jù)理論方法計算各候選道路的概率分配函數(shù)值來確定匹配道路,最后利用相關(guān)系數(shù)算法進行結(jié)論論證。路段模式是對路段的匹配,使用改進的相關(guān)系數(shù)算法對歷史匹配結(jié)果進行檢驗,通過檢驗輸出投影點。

1 改進的DS證據(jù)理論

在進行DS證據(jù)論證之前,先要取得樣本空間,即所有候選道路構(gòu)成的集合。通過概率統(tǒng)計計算出定位點的置信區(qū)域,從中篩選出候選道路。

1.1 置信區(qū)域

置信區(qū)域是指根據(jù)概率統(tǒng)計理論中計算出誤差橢圓內(nèi)的區(qū)域,誤差橢圓推導公式[13]如下:

(1)

(2)

(3)

其中,a、b是橢圓的長短半軸,σx和σy分別是經(jīng)度和緯度的標準差,σxy是協(xié)方差,σ0是單位權(quán)值的后驗方差,可改變它的大小調(diào)整置信區(qū)域的范圍,φ是橢圓長半軸與正北方向的夾角。由于判斷路段是否落在橢圓內(nèi)需要執(zhí)行大量的開方運算,因此在實際應用中通常將誤差區(qū)域簡化為矩形區(qū)域,該矩形區(qū)域為橢圓的最小包圍矩形。長和寬的計算公式如下:

(4)

(5)

1.2 DS證據(jù)理論

DS證據(jù)理論是由A.P.Dempster提出,G.Shafer進一步完善的一種處理不確定性的理論[14]。該理論滿足比概率論更弱的公理,能夠區(qū)分“不確定”與“不知道”的差異。當存在多方證據(jù)時,可對證據(jù)進行融合,提高結(jié)果的可靠性。根據(jù)文獻[8]應用于地圖匹配的DS證據(jù)理論,設(shè)從概率統(tǒng)計算法計算出誤差橢圓中提取的全部候選道路集合為:D={S1,S2,…,Si,…,Sn|i=1,2,…,n}。取定位點到Si的投影距離和當前行駛方向作為2個證據(jù),用j進行編號。設(shè)證據(jù)函數(shù)為fij,因投影距離越小越可信,故分別取距離和方向偏值的倒數(shù)進行歸一化處理即為證據(jù)函數(shù),文獻[8]已詳細說明,此處不再贅述。文獻[8]將基本概率分配函數(shù)構(gòu)造為:

(6)

(7)

其中,mj(Si)表示證據(jù)j對命題“道路Si是匹配道路”的精確信任程度,mj(θ)表示不確定車輛在哪條道路上,kj表示證據(jù)j的可靠性參數(shù),文獻[8]對其默認值都取0.8。最后根據(jù)DS合成公式,將2個基本概率分配函數(shù)合成為一個基本概率分配函數(shù)m(Si),Si對應的概率分配函數(shù)值最大的即為匹配結(jié)果。

1.3 置信區(qū)域

由于二證據(jù)DS證據(jù)理論證據(jù)過少導致匹配結(jié)果不穩(wěn)定且容易產(chǎn)生誤匹配,引入第3個證據(jù)——歷史證據(jù)。將距離和方向2個證據(jù)融合后的二證據(jù)概率分配函數(shù)再與歷史證據(jù)進行融合。歷史因子為前一定位點匹配道路的二證據(jù)概率分配函數(shù)值m′(max)。當j=3時,歷史證據(jù)函數(shù)構(gòu)造為:

(8)

在式(8)中,分母為所有候選道路的二證據(jù)基本概率分配函數(shù)值之和,分子為當前候選道路的二證據(jù)基本概率分配函數(shù)值再加上歷史因子m′(max),若當前候選道路與歷史道路不重合,則m′(max)為0。對于不同的候選道路,其歷史證據(jù)函數(shù)的差異在于,前一定位點是否支持當前定位點位于當前候選道路上,即若前一定位點的匹配道路與當前候選道路重合,則m′(max)為前一定位點匹配道路的概率分配函數(shù)值,否則m′(max)為0。同樣根據(jù)式(6)、式(7)得出歷史證據(jù)的基本概率分配函數(shù)。由于目前還沒有有效的可靠性參數(shù)理論計算方法,文獻[8]亦未展開討論,本文在實驗中設(shè)置不同的歷史證據(jù)可靠性參數(shù)k3,通過實驗效果來確定k3的值。

根據(jù)DS融合公式將當前證據(jù)函數(shù)與歷史證據(jù)進行融合,m′(Si)中的最大值即為匹配結(jié)果。融合后的基本概率公式為:

(9)

2 雙模式地圖匹配算法

傳統(tǒng)地圖匹配都只使用一種匹配模式,對匹配正確率和匹配速度的平衡沒有進行研究,對此,本文提出一種雙模式匹配算法。圖1(a)是一個典型的交叉道路網(wǎng)絡(luò),當汽車行駛于道路A上接近路口時,此時是路口模式,首先計算置信區(qū)域,篩選候選道路,然后進行三證據(jù)融合得出結(jié)論,最后利用相似性對結(jié)論進行驗證。由于加入了與歷史證據(jù)的融合,在進入道路B之前匹配結(jié)果會穩(wěn)定在道路A上。進入道路B的中間路段后,置信區(qū)域和三證據(jù)融合的大量計算會影響匹配速度,由于汽車移動的短時平穩(wěn)特性,不需要復雜的推理。此時切換為路段模式,即直接通過計算相似性對結(jié)論進行驗證,以確定汽車是行駛在該道路上,這樣保證了匹配的高效性。如圖1(b)對僅使用路口模式(單模式)和雙模式匹配用時進行6次比較,在兩者匹配正確率相同的情況下,可以看出雙模式用時少。

圖1 雙模式切換路網(wǎng)圖例分析

算法使用匹配隊列存儲已匹配成功的定位點,它是一個隊列,隊尾總是指向前一定位點,隊列長度可根據(jù)道路的長度動態(tài)調(diào)整。另外需要注意的是,本文所指的道路的節(jié)點和結(jié)點是2個不同的概念。節(jié)點指的是一條弧段的2個端點或具有標志性的點,結(jié)點指的是一條弧段的坐標表示點。

2.1 置信區(qū)域

定義1(相似指數(shù)) 指當前匹配隊列中的點形成的曲線與道路曲線的相似程度。相似指數(shù)用于對DS證據(jù)理論算法推理出結(jié)論進行2次檢驗,防止出現(xiàn)概率分配值最大而不滿足相似性的匹配道路。令x代表經(jīng)度,y代表緯度。假設(shè)用Q表示相似性,其公式如下:

(10)

其中,Rx和Ry分別是行駛軌跡經(jīng)度與匹配道路經(jīng)度和行駛軌跡緯度與匹配道路緯度的相關(guān)系數(shù)。首先根據(jù)匹配隊列中的點和匹配道路生成一個n×4的樣本矩陣,n為匹配隊列的當前長度。矩陣的列從左到右依次為匹配隊列中點的橫坐標、縱坐標以及匹配道路的橫坐標、縱坐標,表示如下:

根據(jù)樣本矩陣計算相關(guān)系數(shù)的公式為:

(11)

這里僅以經(jīng)度為示例給出公式,緯度把x換成對應的y即可。當相似指數(shù)達到預定值即判定匹配道路就是最終結(jié)果。

2.2 道路結(jié)構(gòu)劃分

定義2(轉(zhuǎn)換節(jié)點) 算法把一條道路分為路口和路段,兩者之間的界限稱為轉(zhuǎn)換節(jié)點。

如圖2所示,假設(shè)Ni和Nj是一條道路的2個節(jié)點,Pc是當前定位點在此道路上的投影點,Dij是Ni到Nj的長度,Dki是Ni到Pc的長度,Dkj是Nj到Pc的長度,若定位點滿足下式:

Dki>λDij&&Dkj>λDij

(12)

則處于路段,使用路段匹配模式;否則處于路口,使用路口匹配模式。

圖2 轉(zhuǎn)換節(jié)點示意圖

2.3 算法實現(xiàn)

在進行地圖匹配前,必須先做數(shù)據(jù)的預處理工作。由于各種版本的電子地圖使用的坐標系各不相同,因此要把定位點轉(zhuǎn)化為對應的坐標系才能進行計算。之后是數(shù)據(jù)有效性的判斷,無效數(shù)據(jù)舍棄,并使用線性插值插入一個數(shù)據(jù)再進行匹配。接下來是模式的選擇,根據(jù)式(12)判斷當前定位點的位置,選擇不同的模式進行匹配。算法偽代碼如下:

輸入GPS定位信息,按一定的頻率自動接收

輸出每個定位數(shù)據(jù)在地圖上的匹配點

1.匹配參數(shù)初始化,數(shù)據(jù)接收準備;

2.While (第i個定位點di≠null) DO

3. 對di進行有效性判斷及預處理;

4. 根據(jù)模式信號量選擇不同模式進行匹配。

5. IF (路口模式)

6. 利用式(4)、式(5)計算誤差區(qū)域,并從中篩選出所有候選道路s;

7. FOR ?Si∈S DO

8. 利用式(9)計算出Si對應的概率分配函數(shù)值;

9. 選出概率分配函數(shù)值最大的對應的道路Si,對其進行相似性驗證;

10. ELSE

11. 利用相似性對歷史結(jié)果進行驗證;

12. IF (檢測換道)

13. 清空匹配隊列,初始化各參數(shù)。

14. ELSE

15. 根據(jù)式(12)判斷di是否為轉(zhuǎn)換節(jié)點,若是,則設(shè)置模式信號量。

16.輸出匹配結(jié)果,將di添加到匹配隊列;

17.END While

接著分析算法的時間復雜度。設(shè)有n個點、m條候選道路。第6行是概率統(tǒng)計算法,時間復雜度為O(m×n),第8行是三證據(jù)D-S證據(jù)理論算法,對m條道路進行3次融合,時間復雜度為O(m×m×n),相似性驗證的時間復雜度為O(n)。第15行是轉(zhuǎn)換節(jié)點的判斷,時間復雜度為O(n)。綜上,時間復雜度為O(m×m×n)。從空間復雜度來看,整個算法維護一個匹配隊列,其長度固定,空間復雜度為O(1)。n個點對應m條道路信息的存儲,故空間復雜度為O(m×n)。

3 系統(tǒng)測試

本文的實驗平臺采用Android系統(tǒng)+百度地圖來呈現(xiàn)。實驗數(shù)據(jù)來源于真實的GPS數(shù)據(jù)采集。由于百度地圖采用自家的bd09ll坐標系,因此在實驗中要把GPS的坐標系轉(zhuǎn)換成bd09ll坐標系。

本文采用帶GPS定位的Android手機,駕車行駛在學校周邊公路,以每5 s一次的頻率來收集定位數(shù)據(jù)。在數(shù)據(jù)處理中利用獲取到的道路信息,按算法需求編制道路存儲結(jié)點及道路之間的節(jié)點,組建道路拓撲關(guān)系,計算道路長度、方向等。

3.1 可靠性參數(shù)選取

為確定合適的歷史證據(jù)可靠性參數(shù)k3,首先對其取不同的值進行4次匹配正確率測試,取值范圍為0.6～0.9,以0.05作為步長。為使參數(shù)適應多種環(huán)境,每次測試需選擇不同的道路結(jié)構(gòu),包括平行道路、交叉道路、扇形道路、網(wǎng)格道路。實驗統(tǒng)計結(jié)果如圖3所示。

圖3 k3取值測試分析

由圖3可以看出,在各種類型道路中,綜合起來當k3取0.8時,匹配正確率最高,故本文算法取k3=0.8。

3.2 匹配效果

本文選取了學校周邊的一組定位數(shù)據(jù)作為測試樣本,匹配算法采用文獻[8]提出的一種汽車導航中的DS證據(jù)理論地圖匹配算法(以下簡稱導航DS算法)和本文基于三證據(jù)DS證據(jù)理論地圖匹配算法(以下簡稱三-DS算法),結(jié)果如圖4、圖5所示。其中紅色部分(細點)是GPS定位軌跡,藍色部分(粗點)是對應的匹配軌跡。圖中一共有224個定位點,導航DS匹配成功的有194個點,三-DS匹配成功的有209個點,并且在匹配點的均勻性和穩(wěn)定性方面,三-DS算法要優(yōu)于前者。

圖4 導航DS算法匹配效果

圖5 三-DS算法匹配效果

3.3 匹配穩(wěn)定性測試

為確定引入的歷史證據(jù)對匹配結(jié)果穩(wěn)定性的影響大小,對3條相近的平行路段匹配過程中各定位點概率分配值進行統(tǒng)計。已知汽車行駛在道路2上。統(tǒng)計僅使用2個證據(jù)(簡稱二-DS)和三-DS算法各個定位點在3條道路概率分配函數(shù)值,d1～d8表示8個定位點,結(jié)果如表1、表2所示。

表1 二-DS算法概率值

表2 三-DS算法概率值

從表1可以看出,若只采用二證據(jù),d3～d5會出現(xiàn)誤匹配,且匹配結(jié)果很不穩(wěn)定。從表2可以看出,因加入了與歷史證據(jù)的融合,沒有出現(xiàn)誤匹配,且匹配結(jié)果比較穩(wěn)定。

3.4 匹配效率對比

為檢驗本文算法的匹配效率,本文比較了以下基準算法:1)本文提出的三-DS算法;2)直接投影算法;3)文獻[8]提出的一種汽車導航中的DS證據(jù)理論地圖匹配算法(導航DS);4)文獻[10]提出的曲率積分約束地圖匹配方法(曲率積分);5)文獻[15]提出的基于概率統(tǒng)計、拓撲關(guān)系等結(jié)合的算法(拓撲算法)。

首先測試算法對密集定位點和稀疏定位點的匹配能力,使用不同的采樣頻率采集定位數(shù)據(jù),對5種算法的準確率進行統(tǒng)計。實驗控制道路長度為200 m,行駛速度為15 km/h,結(jié)果如圖6、圖7所示。

圖6 不同頻率數(shù)據(jù)集算法的正確率(密集定位點)

圖7 不同頻率數(shù)據(jù)集算法的正確率(稀疏定位點)

從圖6、圖7可以看出,在相對密集的數(shù)據(jù)集中,三-DS算法保持了較好的穩(wěn)定性,正確率整體高于另外4種算法,導航DS算法對定位頻率的依賴比較高,拓撲算法正確率較低且不穩(wěn)定,曲率積分同樣受定位頻率影響較大;對于稀疏數(shù)據(jù)集,只有一些零星的點組成的軌跡,5種算法正確率下降都比較快,但三-DS算法仍具有一定的穩(wěn)定性。

然后對比分析不同量數(shù)據(jù)集各種算法的匹配完成時間。圖8列出了8組小量數(shù)據(jù)集及各算法完成匹配的時間。從圖8中可以看出,在小量數(shù)據(jù)集中,除了直接投影外,三-DS算法完成時間比其他3種算法都要短,且隨著數(shù)據(jù)集的增大增長較緩慢;其余算法用時較長,增長速度也較快。

圖8 小量數(shù)據(jù)集算法完成時間對比

接著將數(shù)據(jù)集增大一個數(shù)量級,進一步比較各算法的性能。如圖9所示,在中量數(shù)據(jù)集中三-DS算法繼續(xù)保持優(yōu)勢,圖10是大量數(shù)據(jù)集算法完成時間對比,三-DS算法明顯要比其他4種算法用時少。

圖9 中量數(shù)據(jù)集算法完成時間對比

圖10 大量數(shù)據(jù)集算法完成時間對比

綜上可見,基于三證據(jù)DS理論雙模式地圖匹配算法無論在完成時間還是正確率上,相比其他算法都有了一定提高。在計算能力相對較弱的移動平臺上也能達到滿意的效果。

4 結(jié)束語

本文對當前基于DS證據(jù)理論的地圖匹配算法進行改進,在距離和方向2個證據(jù)的基礎(chǔ)上,增加了一個歷史可信證據(jù),通過對3個證據(jù)的融合提高匹配結(jié)果的穩(wěn)定性和準確率。實驗結(jié)果表明,與傳統(tǒng)DS理論地圖匹配算法相比,三證據(jù)DS理論雙模式地圖匹配算法匹配準確率更高。但本文算法也存在不足之處,如算法中涉及到的一些系數(shù)權(quán)值都沒有給出具體的確定方案,僅通過實驗效果來確定,在處理復雜的立交橋等路段時,穩(wěn)定性較差。在今后的研究中,會繼續(xù)對算法做出更合理、更普適的改進。

[1] 黃瑞陽,郭建忠,余慧明,等.基于Silverlight的矢量地圖符號模型設(shè)計與實踐[J].測繪工程,2013,22(1):7-11.

[2] 段 榮,趙修斌,龐春雷,等.一種GPS移動基準站精密相對定位新算法[J].四川大學學報(工程科學版),2015,47(3):130-136.

[3] 周 成,袁家政,劉宏哲,等.智能交通領(lǐng)域中地圖匹配算法研究[J].計算機科學,2015,42(10):1-6.

[4] BIERLAIRE M,CHEN J,NEWMAN J.A probabilistic map matching method for smartphone GPS data[J].Transportations Research,Part C:Emerging Technologies,2013,26(1):78-98.

[5] 朱 遞,劉 瑜.一種路網(wǎng)拓撲約束下的增量型地圖匹配算法[J].武漢大學學報(信息科學版),2017,42(1):77-83.

[6] 李清泉,胡 波,樂 陽.一種基于約束的最短路徑低頻浮動車數(shù)據(jù)地圖匹配算法[J].武漢大學學報(信息科學版),2013,38(7):805-808.

[7] KAKUMA D,TSUICHIHARA S,RICARDEZ G A G,et al.Alignment of occupancy grid and floor maps using graph matching[C]//Proceedings of IEEE International Conference on Semantic Computing.Washington D.C.,USA:IEEE Press,2017:57-60.

[8] 李 珂,楊 楊,邱雪松.城市汽車導航中一種改進的 DS 證據(jù)理論地圖匹配算法[J].測繪學報,2014,43(2):208-220.

[9] 向長風,徐 圓,朱群雄.一種面向景區(qū)導航的動態(tài)地圖匹配算法[J].計算機工程,2016,42(10):32-37,44.

[10] 曾 喆,李清泉,鄒海翔,等.曲率積分約束的GPS浮動車地圖匹配方法[J].測繪學報,2015,44(10):1167-1176.

[11] DINH V Q,NGUYEN V D,van NGUYEN H,et al.Fuzzy encoding pattern for stereo matching cost[J].IEEE Transactions on Circuits and Systems for Video Technology,2016,26(7):1215-1228.

[12] SAEEDI S,PAULL L,TRENTINUI M,et al.Neural network-based multiple robot simultaneous localization and mapping[J].IEEE Transactions on Neural Networks,2011,22(12):2376-2387.

[13] 許國建,張志利,周召發(fā).基于DR/GIS組合導航的誤差補償研究[J].計算機工程,2013,39(5):314-317.

[14] DONG G,KUANG G.Target recognition via information aggregation through Dempster-Shafer’s evidence theory[J].IEEE Geoscience and Remote Sensing Letters,2015,12(6):1247-1251.

[15] 王 敏,魏衡華,鮑遠律.GPS導航系統(tǒng)中的地圖匹配算法[J].計算機工程,2012,38(14):259-261.