一種改進的浮動車地圖匹配算法

趙庶旭，張金秋，屈睿濤

(蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

浮動車數(shù)據(jù)在探索興趣點、更新道路網(wǎng)絡(luò)、預(yù)測交通、尋找最優(yōu)路徑等領(lǐng)域扮演了一個重要角色[1]。在實際應(yīng)用過程中，由于GPS設(shè)備自身局限性及環(huán)境噪聲干擾等因素[2]，車輛定位位置與實際運行位置之間存在偏差，這直接影響著后期的分析工作。地圖匹配算法可以將定位數(shù)據(jù)匹配到正確的行駛路段上，有效解決定位偏差問題[3-4]。現(xiàn)有的地圖匹配算法主要分為基于幾何信息的地圖匹配算法、基于拓撲關(guān)系的地圖匹配算法、基于概率統(tǒng)計的地圖匹配算法及先進的地圖匹配算法[5]。基于幾何信息的地圖匹配算法提出時間較早，只考慮幾何信息而忽略了道路的連接性[6]；基于拓撲關(guān)系的地圖匹配算法采用拓撲邏輯信息如路段連通性、道路方向和道路屬性[7]；基于概率統(tǒng)計的地圖匹配算法利用概率統(tǒng)計理論確定候選道路集、導(dǎo)航傳感器的誤差源及空間道路數(shù)據(jù)[8]；先進的地圖匹配算法主要采用人工智能的方法[9]。

DIANGE Y等在2011年提出了一種采用綜合模糊評價方法評估軌跡相似性，對位置、形狀、方向和行為方面的相似性進行量化[10]；肖維麗等在2015年提出了基于高程的改進D-S證據(jù)理論地圖匹配算法，通過引入高程信息提高了算法在復(fù)雜路況下的匹配準(zhǔn)確度，但單點匹配耗時較高，無法滿足實時性的需求[11]；王美玲等在2012年提出了浮動車地圖匹配算法，通過距離權(quán)重、航向權(quán)重及基于最短路徑的可達性權(quán)重確定最優(yōu)匹配道路，相較于傳統(tǒng)基于權(quán)重的地圖匹配算法引入可達性權(quán)重，提高了匹配的準(zhǔn)確度，但其對于最短路徑信息應(yīng)用僅限于可達與非可達，對于同樣可達的路段缺乏辨識度，在一定程度上限制了匹配準(zhǔn)確度[12]；曾喆等在2015年提出了曲率積分約束的浮動車地圖匹配算法，通過曲率積分度量軌跡曲線彎曲程度，以此作為前后定位點間關(guān)聯(lián)特性實現(xiàn)地圖匹配過程，在一定程度上提高了匹配精度，當(dāng)采樣間隔大于100 s時，匹配準(zhǔn)確度急劇降低[13]；劉衛(wèi)寧等在2016年提出了基于時空分析的地圖匹配算法，通過構(gòu)建網(wǎng)格索引方式提高了候選路段的確定速率，綜合考慮幾何及路網(wǎng)拓撲等信息提高匹配準(zhǔn)確度，但其未考慮網(wǎng)格索引中空網(wǎng)格問題且忽略了車輛航向信息，限制了其匹配的準(zhǔn)確度[14]。

浮動車數(shù)據(jù)考慮傳輸成本及存儲成本，通常采用低頻(60 s間隔及以上)采樣的方式[15]，相鄰定位點之間通過多個路段，兩個相鄰定位點之間拓撲缺失。現(xiàn)有地圖匹配算法應(yīng)用于低頻方式采樣的浮動車GPS數(shù)據(jù)時存在匹配準(zhǔn)確度與匹配效率不能同時兼顧的問題。

針對此問題，本文提出了一種改進的浮動車地圖匹配算法，采用改進的自適應(yīng)網(wǎng)格劃分方法快速確定候選路段集，基于司機駕駛習(xí)慣采用最短路徑信息建立前后定位點間聯(lián)系性，考慮單個定位點航向偶然性較大問題加入前后定位點間軌跡方向信息，基于最短距離權(quán)重、車輛航向權(quán)重、最短路徑權(quán)重及軌跡方向權(quán)重的總權(quán)重準(zhǔn)確確定最優(yōu)匹配路段及匹配點。

1 改進的浮動車地圖匹配算法

改進的浮動車地圖匹配算法流程如圖1所示。

圖1 地圖匹配算法流程

地圖匹配過程主要分為確定候選路段集與確定最優(yōu)匹配路段兩個步驟。本文算法基于改進自適應(yīng)網(wǎng)格劃分方法快速確定候選路段集，基于最短距離權(quán)重、車輛航向權(quán)重、最短路徑權(quán)重及軌跡方向權(quán)重的總權(quán)重準(zhǔn)確確定最優(yōu)匹配路段及匹配點。

1.1 網(wǎng)格劃分算法

1.1.1 基本網(wǎng)格劃分算法

基本的網(wǎng)格劃分方法是將電子地圖按照步長l，依照從左到右、從下到上的規(guī)則進行網(wǎng)格劃分，劃分為M×N個l×l的正方形獨立網(wǎng)格，網(wǎng)格編號為j(j=1,2,…,MN-1)。某一初始定位點P1經(jīng)緯度坐標(biāo)為(x,y)，其落入的網(wǎng)格編號j

(1)

式中，x0為電子地圖最小經(jīng)度，y0為最小緯度，對應(yīng)地圖坐標(biāo)點O(x0,y0),如圖2所示。

圖2 道路網(wǎng)格劃分

路段的任一點落入編號為j的網(wǎng)格內(nèi)，則將該路段加入該網(wǎng)格候選路段集Gj中，如圖3所示。

圖3 候選路段確定

1.1.2 自適應(yīng)基本網(wǎng)格劃分算法

基本電子地圖網(wǎng)格劃分算法，存在空網(wǎng)格即網(wǎng)格內(nèi)無路段情況，若有初始位置點落入空網(wǎng)格內(nèi)，如圖4所示，則直接導(dǎo)致匹配錯誤。針對此問題，本文提出一種改進的自適應(yīng)網(wǎng)格劃分方法，根據(jù)網(wǎng)格內(nèi)路段數(shù)動態(tài)合并網(wǎng)格。

圖4 無候選路段網(wǎng)格

自適應(yīng)網(wǎng)格劃分算法相關(guān)定義如下：

定義1：網(wǎng)格內(nèi)路段及與網(wǎng)格相交路段構(gòu)成的集合為該網(wǎng)格路段集，同時為落入該網(wǎng)格內(nèi)定位點對應(yīng)候選路段集。

定義2：對應(yīng)網(wǎng)格路段集為空的網(wǎng)格為空網(wǎng)格。

定義3：合并一次網(wǎng)格指合并空網(wǎng)格周圍直接與空網(wǎng)格相接的網(wǎng)格，合成網(wǎng)格編號仍為原空網(wǎng)格編號。

定義4：認定經(jīng)過兩次合并的網(wǎng)格若其對應(yīng)網(wǎng)格路段集仍為空，則認定該區(qū)域為錯誤區(qū)。

自適應(yīng)網(wǎng)格劃分算法基本思想如下：

步驟(1)：判斷各網(wǎng)格對應(yīng)網(wǎng)格路段集是否為空，若為空，則標(biāo)記對應(yīng)網(wǎng)格為空網(wǎng)格并進行下一步，若不為空則跳到步驟(4)。

步驟(2)：對空網(wǎng)格合并一次網(wǎng)格，判斷合成網(wǎng)格對應(yīng)網(wǎng)格路段集是否為空，若數(shù)量為空，則標(biāo)記該網(wǎng)格為空網(wǎng)格并進行下一步，若不為空則跳到步驟(4)。

步驟(3)：對空網(wǎng)格合并一次網(wǎng)格，判斷合成網(wǎng)格對應(yīng)網(wǎng)格路段集是否為空，若數(shù)量為空，則標(biāo)記該網(wǎng)格為錯誤區(qū)，若不為空則進行下一步。

步驟(4)：確定此路段集為該網(wǎng)格對應(yīng)網(wǎng)格路段集。

自適應(yīng)網(wǎng)格劃分算法在基本網(wǎng)格劃分算法快速高效確定候選路段集基礎(chǔ)上，有效解決了空網(wǎng)格問題，在一定程度上提高了匹配準(zhǔn)確度，為改進的浮動車地圖匹配算法高效精確實現(xiàn)地圖匹配過程奠定了基礎(chǔ)。

1.2 基于權(quán)重的最優(yōu)匹配路段確定算法

低頻采樣浮動車數(shù)據(jù)前后定位點間聯(lián)系性缺失，單個定位點航向偶然性較大，本文算法引入最短路徑構(gòu)建了前后定位點間聯(lián)系性，引入軌跡方向信息降低了單個定位點的偶然性。由于車輛可能不完全按照最短路徑運行，傳統(tǒng)的最短距離與航向信息仍被應(yīng)用到地圖匹配過程中。采用基于權(quán)重的最優(yōu)匹配路段確定算法，計算各候選路段權(quán)重，包括最短距離權(quán)重ZQ、航向差權(quán)重CQ、最短路徑權(quán)重LQ及軌跡方向差權(quán)重GQ，并計算總權(quán)重W以確定最優(yōu)匹配路段。

基于權(quán)重的最優(yōu)匹配路段確定算法相關(guān)定義如下：

定義5：最短距離指初始定位點到各候選路段的最短距離，最短距離可能是到候選路段垂點距離，也可能是到候選路段端點距離。

定義6：候選匹配點指候選路段上的對應(yīng)匹配點，是候選路段上到初始定位點距離最短的點，可能是初始定位點在候選路段上垂點，也可能是候選路段端點。

定義7：航向指從車輛定位數(shù)據(jù)中獲取的車輛行駛方向信息，以正北方向為零，航向變化范圍是0,2π。

定義8：候選路段方向是從路網(wǎng)數(shù)據(jù)中獲取的路段方向，以正北方向為零，候選路段方向變化范圍是0,2π。

定義9：最短路徑是指上一正確匹配點到當(dāng)前候選匹配點之間的最短路徑。

定義10：軌跡方向是指上一個初始定位點與當(dāng)前初始定位點之間連線的方向，以正北方向為零，其變化范圍是0,2π。

1.2.1 最短距離權(quán)重

最短距離權(quán)重用ZQ表示，其表達式為

(2)

(3)

1.2.2 航向差權(quán)重

航向差是指車輛航向與候選路段方向相比較得到的差值，車輛航向差權(quán)重記為CQ,其表達式為

CQ=Wcf(Δα)

(4)

(5)

1.2.3 最短路徑權(quán)重

通過前后定位點間最短路徑構(gòu)建聯(lián)系性，提高匹配準(zhǔn)確度。本文采用Dijkstra最短路徑搜索算法確定前后定位點間最短路徑。Dijkstra算法可搜索一點到其他所有點的最短路徑，由于城市路網(wǎng)密度較大，最短路徑搜索效率較低。采用文獻[1]中縮小搜索范圍的方法，根據(jù)車輛最大行駛速度vmax與前后定位點間時間差Δt確定最大行駛距離dmax，基于最大行駛距離構(gòu)建搜索區(qū)域

dmax=vmax·Δt

(6)

搜索區(qū)域如圖5所示，其中P1是上一定位點最終匹配點，P2是當(dāng)待帶匹配點。確定最短路徑搜索區(qū)域，可有效提高最短路徑搜索效率。

圖5 搜索區(qū)域

最短路徑權(quán)重用LQ表示，其表達式為

LQ=Wlf(Δm)

(7)

(8)

1.2.4 軌跡方向權(quán)重

方向差指軌跡方向與候選路段方向之間差值，軌跡方向權(quán)重用GQ表示，其表達式為

GQ=Wgf(Δθ)

(9)

(10)

圖6 軌跡方向信息

軌跡方向與候選路段方向差值越小，則對應(yīng)的候選匹配點是正確匹配點的可能性就越高。

1.2.5 總權(quán)重

權(quán)重總和為W，其表達式為

W=ZQ+CQ+LQ+GQ

(11)

根據(jù)公式計算每條候選路段的總權(quán)重，候選路段當(dāng)中最高權(quán)重的路段被認定為正確匹配路段，在選擇路段上的匹配點認定為正確的匹配位置點。

2 試驗和驗證

2.1 地圖數(shù)據(jù)處理

為了驗證算法的可行性，本文首先在ArcGIS平臺下建立山東省淄博市張店區(qū)路網(wǎng)數(shù)據(jù)，在路網(wǎng)數(shù)據(jù)中加入路段長度、路段方向及道路線路等信息，進行拓撲處理構(gòu)建路網(wǎng)拓撲關(guān)系，為改進浮動車地圖匹配算法提供完善可用的路網(wǎng)數(shù)據(jù)。選取(117.934,36.624)作為網(wǎng)格坐標(biāo)原點，使得張店區(qū)在第一象限，取l=50 m劃分網(wǎng)格，根據(jù)網(wǎng)格內(nèi)路段數(shù)動態(tài)合并網(wǎng)格，標(biāo)記錯誤區(qū)。

2.2 地圖匹配

本文試驗數(shù)據(jù)來源于2014年山東省淄博市出租車GPS數(shù)據(jù)。首先采用某出租車在2014年1月28日8：00：00—21：00:00的GPS數(shù)據(jù)進行驗證，該出租車GPS數(shù)據(jù)為0.067 Hz的低頻采樣數(shù)據(jù)，該時間段內(nèi)共有670條GPS數(shù)據(jù)，剔除不在淄博市張店區(qū)內(nèi)的GPS數(shù)據(jù)及長時間停留GPS數(shù)據(jù)后，共有438條可用數(shù)據(jù)。Wz、Wc、Wl、Wg值均設(shè)置為0.25。出租車GPS數(shù)據(jù)初始位置點、傳統(tǒng)基于最短距離與航向權(quán)重的匹配結(jié)果，以及本文匹配結(jié)果如圖7所示。

圖7 初始點與結(jié)果對比

局部匹配結(jié)果對比如圖8所示。從圖7和圖8中發(fā)現(xiàn)，傳統(tǒng)基于最短距離與航向權(quán)重的地圖匹配算法在匹配處于道路交叉口與平行路段的GPS位置點時易匹配錯誤，而本文算法在同樣情況下有較好匹配效果。

圖8 局部匹配效果

匹配結(jié)果對比分析見表1。

表1 匹配結(jié)果對比分析

單輛出租車GPS數(shù)據(jù)匹配結(jié)果表明，本文匹配算法在保證匹配效率的情況下提高了匹配準(zhǔn)確度，實現(xiàn)了預(yù)期目標(biāo)。

為進一步驗證本文算法對低頻采樣的浮動車數(shù)據(jù)匹配效果，基于原始數(shù)據(jù)采樣間隔進一步抽稀數(shù)據(jù)，得到采樣間隔為120 s及180 s的出租車GPS定位數(shù)據(jù)，使用原始定位數(shù)據(jù)(60 s采樣間隔)及抽稀得到的數(shù)據(jù)(120 s及180 s間隔)驗證算法性能，并與文獻[7]及文獻[9]匹配算法進行對比，試驗結(jié)果對比分析如圖9所示。

圖9 不同采樣頻率匹配對比

結(jié)果表明，對于60 s間隔的采樣數(shù)據(jù)，各算法均具有較高的匹配準(zhǔn)確度，采樣頻率降低時，各算法匹配準(zhǔn)確度均有所下降，但本文算法仍然具有較好的準(zhǔn)確度。文獻[7]匹配算法在傳統(tǒng)基于權(quán)重地圖匹配算法基礎(chǔ)之上加入可達性權(quán)重，提高了算法匹配準(zhǔn)確度，但可達性對于路網(wǎng)密集區(qū)域辨識度不高，且隨著采樣間隔的增大，車輛航向的偶然性也隨之增大，通過最短距離、航向及可達性判斷最優(yōu)匹配路段的難度增加，相應(yīng)的準(zhǔn)確度隨之降低。文獻[9]采用幾何及路網(wǎng)拓撲確定匹配點，當(dāng)采樣間隔增大時，通過此方法很難建立前后定位點間聯(lián)系，相應(yīng)匹配難度增加準(zhǔn)確度降低。本文算法基于最短路徑建立前后定位點間聯(lián)系性，基于軌跡方向信息弱化單個定位點航向偶然性，在采樣間隔增大時，可有效保障匹配的準(zhǔn)確性。

為驗證本文算法處理海量浮動車數(shù)據(jù)時的匹配性能，隨后選取500～50 000之間不同數(shù)量的GPS定位點數(shù)據(jù)測試算法，單點匹配耗時如圖10所示。

圖10 單點匹配耗時

由圖10可知，隨著定位點個數(shù)的不斷增加，單點匹配耗時略微呈上升趨勢，但其耗時仍能滿足一般智能交通系統(tǒng)的實時性要求。結(jié)果表明，本文匹配算法在處理海量浮動車數(shù)據(jù)時仍有較高的匹配效率。

本文算法通過改進的自適應(yīng)網(wǎng)格劃分方法快速確定候選路段集，增加最短路徑權(quán)重和軌跡方向權(quán)重輔助地圖匹配過程準(zhǔn)確確定最優(yōu)匹配路段，在保證算法運行效率的同時提高了算法匹配準(zhǔn)確度。

3 結(jié) 語

針對現(xiàn)有地圖匹配算法應(yīng)用于低頻采樣的浮動車數(shù)據(jù)時匹配準(zhǔn)確度與匹配效率不能同時兼顧的問題，本文提出了一種改進的浮動車地圖匹配算法。基于改進的自適應(yīng)網(wǎng)格劃分算法在高效確定候選路段集的同時有效解決了傳統(tǒng)網(wǎng)格化方法的空網(wǎng)格問題，在一定程度上提高了匹配的準(zhǔn)確度；基于權(quán)重的最優(yōu)匹配路段確定算法在傳統(tǒng)匹配算法中加入最短路徑與軌跡方向信息，建立了前后定位點間聯(lián)系性，削弱了單個定位點航向的偶然性，有效提高了算法的匹配準(zhǔn)確度。改進的自適應(yīng)網(wǎng)格劃分算法與基于權(quán)重的最優(yōu)匹配路段確定算法相結(jié)合，在保證匹配效率的同時提高了算法的匹配準(zhǔn)確度。最短路徑信息的引入在一定程度上增加了算法的復(fù)雜性，如何進一步降低最短路徑搜索時間是本文下一步研究的焦點。

[1] 沈敬偉,周廷剛,張弘弢.基于改進AOE網(wǎng)絡(luò)的低頻浮動車數(shù)據(jù)地圖匹配算法[J].西南交通大學(xué)學(xué)報,2015,50(3):497-503.

[2] 李清泉,黃練.基于GPS軌跡數(shù)據(jù)的地圖匹配算法[J].測繪學(xué)報,2010,39(2):207-212.

[3] 趙東保,劉雪梅,郭黎.網(wǎng)格索引支持下的大規(guī)模浮動車實時地圖匹配方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2014,26(9):1550-1556.

[4] 王仁禮,陳天澤,王冬紅.智能型地圖匹配綜合算法的研究[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2003,15(11):1443-1447，1451.

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

[6] WHITE C E，BERNSTEIN D，KORNHAUSER A L.Some Map Matching Algorithms for Personal Navigation Assistants[J].Transportation Research Part C:Emerging Technologies，2000，8(1):91-108.

[7] 盧文濤，周銀東，梅順良，等.基于拓撲結(jié)構(gòu)的地圖匹配算法研究[J].測控技術(shù)，2010，29(6):73-76.

[8] CHO Y，CHOI H.Accuracy Enhancement of Position Estimation Using Adaptive Kalman Filter and Map Matching[J].International Journal of Control and Automation，2014，7(7):167-178.

[9] 蘇海濱,王光政,王繼東.基于模糊神經(jīng)網(wǎng)絡(luò)的地圖匹配算法[J].北京科技大學(xué)學(xué)報,2012,34(1):43-47.

[10] YANG D，ZHANG T，LI J，et al.Synthetic Fuzzy Evaluation Method of Trajectory Similarity in Map-matching[J].Journal of Intelligent Transportation Systems，2011，15(4):193-204.

[11] 肖維麗,岳春生,奚玲.基于高程的改進D-S證據(jù)理論地圖匹配算法[J].計算機應(yīng)用與軟件,2015,32(7):262-265.

[12] 王美玲,程林.浮動車地圖匹配算法研究[J].測繪學(xué)報,2012,41(1):133-138.

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

[14] 劉衛(wèi)寧,汪杰宇,鄭林江.基于時空分析的地圖匹配算法研究[J].計算機應(yīng)用研究,2016,33(8):2266-2269.

[15] 楊旭華,彭朋.基于條件隨機場和低采樣率浮動車數(shù)據(jù)的地圖匹配算法[J].計算機科學(xué),2016,43(S1):68-72.