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

王 科,李 鵬,金 瑜,劉 宇

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

0 概述

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

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

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

1 改進的DS證據理論

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

1.1 置信區域

置信區域是指根據概率統計理論中計算出誤差橢圓內的區域,誤差橢圓推導公式[13]如下:

(1)

(2)

(3)

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

(4)

(5)

1.2 DS證據理論

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

(6)

(7)

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

1.3 置信區域

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

(8)

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

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

(9)

2 雙模式地圖匹配算法

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

圖1 雙模式切換路網圖例分析

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

2.1 置信區域

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

(10)

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

根據樣本矩陣計算相關系數的公式為:

(11)

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

2.2 道路結構劃分

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

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

Dki>λDij&&Dkj>λDij

(12)

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

圖2 轉換節點示意圖

2.3 算法實現

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

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

輸出每個定位數據在地圖上的匹配點

1.匹配參數初始化,數據接收準備;

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

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

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

5. IF (路口模式)

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

7. FOR ?Si∈S DO

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

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

10. ELSE

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

12. IF (檢測換道)

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

14. ELSE

15. 根據式(12)判斷di是否為轉換節點,若是,則設置模式信號量。

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

17.END While

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

3 系統測試

本文的實驗平臺采用Android系統+百度地圖來呈現。實驗數據來源于真實的GPS數據采集。由于百度地圖采用自家的bd09ll坐標系,因此在實驗中要把GPS的坐標系轉換成bd09ll坐標系。

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

3.1 可靠性參數選取

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

圖3 k3取值測試分析

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

3.2 匹配效果

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

圖4 導航DS算法匹配效果

圖5 三-DS算法匹配效果

3.3 匹配穩定性測試

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

表1 二-DS算法概率值

表2 三-DS算法概率值

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

3.4 匹配效率對比

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

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

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

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

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

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

圖8 小量數據集算法完成時間對比

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

圖9 中量數據集算法完成時間對比

圖10 大量數據集算法完成時間對比

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

4 結束語

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

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

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

[3] 周 成,袁家政,劉宏哲,等.智能交通領域中地圖匹配算法研究[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] 朱 遞,劉 瑜.一種路網拓撲約束下的增量型地圖匹配算法[J].武漢大學學報(信息科學版),2017,42(1):77-83.

[6] 李清泉,胡 波,樂 陽.一種基于約束的最短路徑低頻浮動車數據地圖匹配算法[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].測繪學報,2014,43(2):208-220.

[9] 向長風,徐 圓,朱群雄.一種面向景區導航的動態地圖匹配算法[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] 許國建,張志利,周召發.基于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導航系統中的地圖匹配算法[J].計算機工程,2012,38(14):259-261.