基于曲線擬合與拓撲結構的地圖匹配算法

滕志軍,,,,,

(1.東北電力大學 信息工程學院,吉林 吉林 132012; 2.國網七臺河供電公司,黑龍江 七臺河 154600;3.東北師范大學附屬中學,長春 132000; 4.國網吉林供電公司,吉林 吉林 132011)

0 概述

隨著北斗二代導航系統的逐漸完善,北斗導航定位技術已被廣泛應用于地面移動目標的跟蹤定位,車載導航系統就是眾多的應用之一。但在實際的車輛導航中,由于定位數據的系統誤差和偶然誤差以及電子地圖精度的問題,會造成定位點與車輛所在實際道路點存在偏差[1-3],這不僅會給駕駛者帶來視覺上的疲勞,而且這種錯誤信息會帶來嚴重的交通事故。因此,研究快速、準確、有效的方法來減少這種誤差,對提高導航的性能尤為重要。目前解決這種問題的方法主要有2種[4-5]:一是提高導航定位數據和導航電子地圖的精度,但是這種方法實現起來較復雜,成本較高;二是通過目前常用的匹配算法來修正車輛的正確位置,即通過計算定位點與道路點的誤差進行強行修正[6],這種方法成本較低,比較容易實現,因此,成為研究的熱點。

地圖匹配技術已被廣泛應用于車輛導航、導彈制導、雷達探測等方面。很多學者對該技術進行了詳細研究。目前提出的算法主要有基于權重的地圖匹配算法[7]、基于D-S證據推理的地圖匹配算法[8]、基于模糊理論以及基于神經網絡的地圖匹配準則[9-10]等。這些算法各有優缺點,適應情況各不相同,而且原理比較復雜,實現難度較大。針對傳統曲線擬合匹配算法在復雜路段精度低的缺陷[11-12],本文提出以相對誤差為基準進行曲線擬合的地圖匹配算法,在平行路段采用最短距離判別法來彌補曲線擬合算法在平行路段不精確的缺點。

1 地圖匹配基本原理

地圖匹配技術的實現首先要滿足2個最基本的先決條件[13]:一是車輛總是行駛在道路上;二是所采用的道路電子地圖的精度要高于定位數據的精度。進行車輛匹配時第1個條件是符合的,第2個條件中目前的電子地圖精度也是符合要求的。地圖匹配要實現2個目標[14-15]:首先要在候選路段內確定車輛所行駛的實際道路,其次就是對定位系統接收到的定位數據與實際的電子路況中的信息通過地圖匹配算法進行修正,從而確定車輛所在的實際位置。

為了更詳細地說明地圖匹配過程,設車輛在圖1所示道路系統上行駛,在t時刻車輛所在的實際位置為道路B的pt點,由于各種誤差的存在,衛星定位數據給出的定位位置為PD。地圖匹配就是通過一定算法找出道路B并確定車輛所在當前道路中的位置。

圖1 地圖匹配原理圖

隨著城市道路網的密集程度加大,相似相鄰道路越來越多,在定量分析的情況下,高斯最小二乘法的評價依據是針對等精度數據而言的,也就是說觀測數據有大體相同的絕對誤差,但是衛星定位數據的誤差不具有一致性[16]。針對這種情況,本文提出以相對擬合誤差平方和最小為原則的曲線擬合地圖匹配算法。

2 改進地圖匹配算法的實現

2.1 數據預處理

城市道路系統一般比較復雜,密集的建筑物會對衛星定位數據造成一定的影響,易出現異常定位點。為了保證定位點的有效性,在進行地圖匹配之前必須對衛星定位數據預處理,剔除經緯度或速度突變的數據,并根據汽車的行駛方向、速度等信息補全所剔除的定位點。

當出現漂移值時,利用車輛前一點速度和車輛方向進行插值,如圖2所示。

圖2 插值原理圖

由于車輛獲取定位點的頻率較高,當車輛在弧線路段行駛時可以將道路看做短距離的直線路段,因此插值后定位點坐標如式(1)所示,其中(x,y)表示定位點坐標。

xi+1=xi+viΔtsinε

yi+1=yi+viΔtcosε

(1)

2.2 檢索道路集合確定

誤差區域示意圖如圖3所示,其中,x軸方向為東,y軸方向為北,橢圓中心為北斗系統接收的定位點,a為橢圓長半軸,b為橢圓短半軸,φ為誤差橢圓長半軸與正北方向夾角,δ0稱作擴張因子,可以通過其來調節橢圓大小,本文將其設置為1。

圖3 誤差區域示意圖

由于橢圓在計算過程中較復雜,此處用誤差圓來代替誤差橢圓。誤差圓的中心與橢圓中心為同一點,其半徑為誤差橢圓長半軸,如下式所示。

候選區域確定后,候選區域內的道路集合中包含車輛正在行駛的道路,但是隨著道路網的密集程度加大,該集合內的道路條數可能較多,會消耗大量的匹配冗余時間。針對該問題,本文提出一種考慮道路網拓撲結構的策略。如圖4所示,假設車輛正在道路1上行駛,考慮道路的拓撲結構、連通性以及車輛的行駛速度,與道路1相連的只有道路2和道路3,車輛下一時刻不可能出現在道路4～道路6上,減少了大量的道路檢索時間,提高了算法的時效性。

圖4 道路拓撲結構

2.3 匹配路段確定

確定匹配路段的過程如下:

1)改進的地圖匹配算法以相對誤差最小為最佳擬合準則。設定位點的坐標為pi(xi,yi)(i=1,2,…,N),用一個m次多項式y=a0+a1x+a2x2+…+amxm來擬合N個觀測點數據,使得相對誤差的平方和最小。下面給出求解過程。

k=0,1,…,m

(4)

進而可得如式(5)所示的正則方程組。

該正則方程組的解即為所求擬合多項式的系數,將多項式轉化為矩陣形式并化簡得到式(6)。

即XA=Y的形式,那么A=(XTX)-1XTY,這樣就可以求得系數矩陣,因此,得出各系數的大小。

由于在電子地圖中的道路是用直線和線段來代替的,地圖匹配的前提是車輛行駛在道路上,考慮到這一前提,在一定的行駛距離內可以用直線來擬合車輛的歷史軌跡,直線的斜率由上述求解方法可得:

鑒于道路的最短距離和合理的計算量本文選取5個觀測點做一次擬合曲線,即用直線擬合,由式(7)可得該5點所擬合的直線斜率為:

其中,(xi,yi),i=1,2,3,4,5是導航定位數據經坐標轉換后的地圖坐標,由地圖匹配的原理可知,k0反映了車輛的行駛方向,在測量誤差允許的范圍內筆者認為車輛方向夾角和候選道路夾角差值30°以內的道路為所要匹配的路段。因此,得出地圖匹配算法的綜合評價函數z為:

圖5 距離匹配原理圖

2.4 匹配點確定

車輛行駛路段確定后,采用垂直投影法將定位點投影到候選道路上,因為道路都近似于線段,所以可能會出現投影點不在道路上的情況。假設定位點D的坐標為(x,y),道路兩端端點坐標分別為S(x1,y1)和M(x2,y2),如果D的投影點在道路上,設為N(xi,yi)。定義:

其中,θ是向量SD和向量SM的夾角。當01時投影點出現在M端延長線上,此時定義投影點為M(x2,y2)。如圖6所示,D落在C區域內時投影點為N(xi,yi),落在C1區域時投影點為S(x1,y1),落在C2區域時投影點為M(x2,y2)。

圖6 投影原理圖

3 算法驗證

3.1 實測驗證

為了驗證本文改進地圖匹配算法的有效性,對其進行實測驗證,定位模塊為北斗UM220模塊,地圖通過調用百度地圖來完成。在校園內進行跑圖測試,圖7給出了利用該算法進行實測的結果,采樣頻率為10 s。圖7(a)是原始定位數據軌跡,圖7(b)是在該算法下的匹配圖。由圖7(b)可以看出,各定位點能很好地匹配到所行駛的道路上,在道路復雜情況下,該算法仍具有最高的匹配準確率。

圖7 實測結果

3.2 精度仿真

圖8為4種不同地圖匹配算法在同一條件下的匹配準確率仿真結果,從中可以看出:當車輛行駛附近有2條相似道路時,匹配準確率都達到98%以上;當出現3條以上相似候選道路時,雖然4種匹配算法匹配精度都有所下降,但是本文匹配算法相對其他算法匹配準確度下降緩慢;當檢索區域內有5條相似道路時,本文算法的匹配準確率仍在92%左右。由此表明,本文改進算法在復雜路段仍具有較好的匹配性能。

圖8 不同算法的匹配率比較

圖9為對本文算法、傳統曲線擬合算法、D-S證據理論算法、直接投影算法的匹配時間仿真結果。其中匹配時間為從獲取定位點到尋找出車輛行駛道路然后進行垂直投影所花的平均時間。從圖9(a)可以看出,在檢索區域內有2條候選道路時,本文算法單點匹配時間約為4.45 ms,由4幅圖橫向比較來看,隨著檢索區域候選道路條數增加,本文算法單點匹配時間增幅較少,即使候選區域道路條數為5,本文算法單點匹配時間仍為5 ms左右,而其他比較算法均在8 ms以上,增幅較大,因此,本文算法在復雜道路下仍具有快速性。

圖9 匹配時間仿真結果

4 結束語

以相對誤差為判別標準,本文提出一種基于曲線擬合的地圖匹配算法,輔之以道路網的拓撲關系減少匹配時間。實際測試和仿真結果表明,該算法具有匹配精度和效率高的優點,能很好地解決相近相似道路匹配難的問題。下一步將以本文算法為基礎,在道路連通性的原則下對其進行網格劃分,為設計降低采樣頻率的匹配算法提供思路。