基于曲線擬合與拓?fù)浣Y(jié)構(gòu)的地圖匹配算法

滕志軍,,,,,

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

0 概述

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

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

1 地圖匹配基本原理

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

為了更詳細(xì)地說明地圖匹配過程,設(shè)車輛在圖1所示道路系統(tǒng)上行駛,在t時(shí)刻車輛所在的實(shí)際位置為道路B的pt點(diǎn),由于各種誤差的存在,衛(wèi)星定位數(shù)據(jù)給出的定位位置為PD。地圖匹配就是通過一定算法找出道路B并確定車輛所在當(dāng)前道路中的位置。

圖1 地圖匹配原理圖

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

2 改進(jìn)地圖匹配算法的實(shí)現(xiàn)

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

城市道路系統(tǒng)一般比較復(fù)雜,密集的建筑物會對衛(wèi)星定位數(shù)據(jù)造成一定的影響,易出現(xiàn)異常定位點(diǎn)。為了保證定位點(diǎn)的有效性,在進(jìn)行地圖匹配之前必須對衛(wèi)星定位數(shù)據(jù)預(yù)處理,剔除經(jīng)緯度或速度突變的數(shù)據(jù),并根據(jù)汽車的行駛方向、速度等信息補(bǔ)全所剔除的定位點(diǎn)。

當(dāng)出現(xiàn)漂移值時(shí),利用車輛前一點(diǎn)速度和車輛方向進(jìn)行插值,如圖2所示。

圖2 插值原理圖

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

xi+1=xi+viΔtsinε

yi+1=yi+viΔtcosε

(1)

2.2 檢索道路集合確定

誤差區(qū)域示意圖如圖3所示,其中,x軸方向?yàn)闁|,y軸方向?yàn)楸?橢圓中心為北斗系統(tǒng)接收的定位點(diǎn),a為橢圓長半軸,b為橢圓短半軸,φ為誤差橢圓長半軸與正北方向夾角,δ0稱作擴(kuò)張因子,可以通過其來調(diào)節(jié)橢圓大小,本文將其設(shè)置為1。

圖3 誤差區(qū)域示意圖

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

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

圖4 道路拓?fù)浣Y(jié)構(gòu)

2.3 匹配路段確定

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

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

k=0,1,…,m

(4)

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

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

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

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

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

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

圖5 距離匹配原理圖

2.4 匹配點(diǎn)確定

車輛行駛路段確定后,采用垂直投影法將定位點(diǎn)投影到候選道路上,因?yàn)榈缆范冀朴诰€段,所以可能會出現(xiàn)投影點(diǎn)不在道路上的情況。假設(shè)定位點(diǎn)D的坐標(biāo)為(x,y),道路兩端端點(diǎn)坐標(biāo)分別為S(x1,y1)和M(x2,y2),如果D的投影點(diǎn)在道路上,設(shè)為N(xi,yi)。定義:

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

圖6 投影原理圖

3 算法驗(yàn)證

3.1 實(shí)測驗(yàn)證

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

圖7 實(shí)測結(jié)果

3.2 精度仿真

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

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

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

圖9 匹配時(shí)間仿真結(jié)果

4 結(jié)束語

以相對誤差為判別標(biāo)準(zhǔn),本文提出一種基于曲線擬合的地圖匹配算法,輔之以道路網(wǎng)的拓?fù)潢P(guān)系減少匹配時(shí)間。實(shí)際測試和仿真結(jié)果表明,該算法具有匹配精度和效率高的優(yōu)點(diǎn),能很好地解決相近相似道路匹配難的問題。下一步將以本文算法為基礎(chǔ),在道路連通性的原則下對其進(jìn)行網(wǎng)格劃分,為設(shè)計(jì)降低采樣頻率的匹配算法提供思路。