角度和距離分段占優(yōu)地圖匹配算法

張彥會(huì)，曹強(qiáng)榮，何 維

(廣西科技大學(xué)a.廣西汽車零部件與整車技術(shù)重點(diǎn)實(shí)驗(yàn)室;b.汽車與交通學(xué)院，廣西柳州545006)

0 引言

隨著智能運(yùn)輸系統(tǒng)(ITS)的迅速發(fā)展，車載導(dǎo)航定位系統(tǒng)越來越受到關(guān)注，因此，如何快速、準(zhǔn)確地獲得車輛的位置信息變得更為迫切，地圖匹配算法是實(shí)現(xiàn)快速、準(zhǔn)確獲取位置信息的關(guān)鍵，所以研究地圖匹配算法是很有必要的。當(dāng)前的地圖定位匹配算法較多，第一種是基于位置點(diǎn)的地圖匹配算法，該算法的優(yōu)點(diǎn)是實(shí)時(shí)性好、邏輯簡(jiǎn)單，但該算法只適用于以直線型道路為主的情況，對(duì)于彎道或交叉路口較多、道路密集的道路，該算法的匹配準(zhǔn)確率降低，易造成識(shí)別混亂的情況[1-3］。第二種是基于軌跡曲線的地圖匹配算法，該算法的優(yōu)點(diǎn)是對(duì)局部定位點(diǎn)的波動(dòng)不敏感，在交叉路口或彎道較多的道路上匹配效果好，但該算法計(jì)算量較大，算法復(fù)雜，實(shí)時(shí)性差[4-5］。第三種是基于概率統(tǒng)計(jì)的算法，該算法的優(yōu)點(diǎn)是以地理信息系統(tǒng)(GIS)緩沖區(qū)分析方法代替全球定位系統(tǒng)(GPS)誤差橢圓，車輛在路網(wǎng)中的定位準(zhǔn)確性和可靠性高，但該算法只適用于GIS數(shù)字地圖數(shù)據(jù)庫(kù)精度和GPS定位數(shù)據(jù)精度高的情況，在精度不高的場(chǎng)合定位時(shí)間長(zhǎng)，且無法防止定位累積誤差[6-7］。第四種是基于模糊邏輯的地圖匹配算法，該算法的優(yōu)點(diǎn)是在不同的路段采用加權(quán)二維歐式距離作為相似性度量函數(shù)方法，在復(fù)雜路段上都能高效、實(shí)時(shí)的實(shí)現(xiàn)車輛的定位匹配，但該算法在不同路段建模的系數(shù)為經(jīng)驗(yàn)值，缺乏理論依據(jù)[8］。

本文提出了基于角度和距離分段占優(yōu)的地圖匹配算法。首先，在分段占優(yōu)算法中運(yùn)用自適應(yīng)匹配因子進(jìn)行目標(biāo)路段的最優(yōu)選取，能夠增強(qiáng)匹配時(shí)對(duì)正確路段的識(shí)別能力以及對(duì)復(fù)雜路段的適應(yīng)能力，提高定位匹配精度;其次，在節(jié)點(diǎn)處采用融合技術(shù)篩選匹配區(qū)域，大大簡(jiǎn)化了程序的復(fù)雜度，提高了定位的實(shí)時(shí)響應(yīng)性。

1 兩級(jí)交錯(cuò)式網(wǎng)格劃分與二次圓域篩選融合技術(shù)

尋找車輛當(dāng)前行駛的道路從過程上可以分為兩個(gè)部分，即待匹配路段的快速篩選和最優(yōu)路段的權(quán)值判斷。在待匹配路段的快速篩選過程中，篩選區(qū)域的大小直接影響匹配算法的實(shí)時(shí)性。篩選區(qū)域選擇過大，增加算法的復(fù)雜程度和計(jì)算時(shí)間;篩選區(qū)域選擇過小，可以導(dǎo)致沒有待匹配的路段。采用兩級(jí)交錯(cuò)式網(wǎng)格劃分與二次圓域篩選融合的方法能很好地解決這一問題，實(shí)現(xiàn)匹配算法的實(shí)時(shí)性。

圖1所示為例，以100 m×100 m進(jìn)行網(wǎng)格劃分，假定定位點(diǎn)P落在6號(hào)網(wǎng)格內(nèi)。然后以6號(hào)網(wǎng)格的形心A為中心，進(jìn)行100 m×100 m的網(wǎng)格劃分，得到A1、A2、A3、A4這4個(gè)網(wǎng)格。再對(duì)這4個(gè)網(wǎng)格進(jìn)行二級(jí)網(wǎng)格劃分，得到50 m×50 m的子網(wǎng)格，即可進(jìn)一步確定P點(diǎn)在50 m×50 m子網(wǎng)格的具體位置，圖1中定位點(diǎn)P確定在6’子網(wǎng)格中。對(duì)落在不同子網(wǎng)格的定位點(diǎn)P進(jìn)行分析，記i為子網(wǎng)格標(biāo)號(hào)，則:

經(jīng)上述單位邏輯分析，其匹配路段范圍可始終限定在100 m×100 m的區(qū)域內(nèi)。

設(shè)數(shù)字地圖長(zhǎng)為L(zhǎng)，寬為H，假設(shè)規(guī)定邊長(zhǎng)為S的正方形作為網(wǎng)格，S一般取100 m。a，b分別表示L、H方向的網(wǎng)格數(shù)，定位點(diǎn)P的坐標(biāo)為(X，Y)(設(shè)網(wǎng)格1左下角坐標(biāo)為(0，0))，則 A，A1，A2，A3，A4，A5，A6，A7和 A8的計(jì)算過程如下:

圖1 兩級(jí)交錯(cuò)式網(wǎng)格劃分

其中，[］表示取整數(shù)。

以定位點(diǎn)P的平面位置為圓心，以GPS實(shí)時(shí)水平估計(jì)誤差HEP值的2倍為半徑[7］，對(duì)上述經(jīng)過兩級(jí)交錯(cuò)式網(wǎng)格劃分得到的待匹配路段進(jìn)行二次圓域篩選，如圖2所示。P為圓域篩選的圓心，經(jīng)過此次篩選，可以進(jìn)一步縮小待匹配路段區(qū)域的大小，減少計(jì)算量，細(xì)化十字路口拓?fù)鋱D，提高十字路口的匹配精度。圖2中打陰影部分是經(jīng)過兩級(jí)交錯(cuò)式網(wǎng)格劃分與二次圓域篩選融合算法，最終得到的待匹配路段區(qū)域。

融合算法的實(shí)現(xiàn)更大程度上縮小了待匹配路段的區(qū)域，不涉及大量復(fù)雜的計(jì)算，保證路段搜索的快速性和算法的實(shí)時(shí)性。與傳統(tǒng)的網(wǎng)格劃分相比，融合算法實(shí)時(shí)性更好，并提高了十字路口的匹配精度，表現(xiàn)出很大的優(yōu)越性。

圖2 二次圓域篩選模型圖

2 角度和距離分段占優(yōu)自適應(yīng)算法

判斷車輛當(dāng)前行駛在哪條路段上的因素主要有4個(gè):(Ⅰ)車輛當(dāng)前定位點(diǎn)距候選路段的投影距離;(Ⅱ)車輛當(dāng)前行駛方向與候選路段方向的夾角;(Ⅲ)候選路段與前一匹配路段的幾何拓?fù)潢P(guān)系[8］;(Ⅳ)兩個(gè)連續(xù)定位點(diǎn)之間的連線同候選路段的夾角。一般來講，對(duì)第Ⅰ、第Ⅱ和第Ⅳ個(gè)因素，L、θ、β參數(shù)值越小，成為匹配路段的可能性越大;對(duì)第Ⅲ個(gè)的因素，幾何拓?fù)潢P(guān)系成相連或相似狀態(tài)，成為匹配路段的可能性越大，反之亦然。圖3為角度和距離示意圖，車輛在行駛過程中，計(jì)算定位點(diǎn)到待選區(qū)域中各路段的投影距離Li、車輛當(dāng)前行駛方向與候選路段方向的夾角θi和兩個(gè)連續(xù)定位點(diǎn)之間的連線同候選路段的夾角βi，并根據(jù)式(2)計(jì)算出待選區(qū)域中各路段的匹配值ωi。

式中，ωLi為投影距離因子;ωθi為行駛方向角度因子;ωβi為行駛角度變化率因子。

根據(jù)式(2)中ωi的權(quán)值就可以選出待匹配區(qū)域最優(yōu)路段，ωi數(shù)值最大的即為最終匹配路段。為消除地圖匹配中的偶然誤差，對(duì)ωi采取權(quán)重平均值法。

本文對(duì)式(2)中的ωLi、ωθi和ωβi匹配因子采用分段占優(yōu)自適應(yīng)算法，以節(jié)點(diǎn)為研究中心，如圖4所示，O1為節(jié)點(diǎn)，a、b、c和d為4條道路，每條道路至少有一條路段組成。對(duì)于節(jié)點(diǎn)O1，分別與其連接的路段的長(zhǎng)短為半徑在平面內(nèi)做匹配圓，選擇半徑最小的圓作為該節(jié)點(diǎn)的匹配區(qū)域;對(duì)于定位點(diǎn)P，以實(shí)時(shí)水平估計(jì)誤差HEP值為半徑做匹配圓。ωLi、ωθi和ωβi匹配因子隨著匹配區(qū)域的不同而變化。(Ⅰ)原始定位點(diǎn)P的匹配圓和節(jié)點(diǎn)O1的匹配區(qū)域接觸時(shí)(即定位點(diǎn)P靠近節(jié)點(diǎn)O1)，車輛發(fā)生拐彎的可能性比較大，ωθi在匹配值中的比重應(yīng)該增大;ωβi在拐彎時(shí)為非線性跳動(dòng)狀態(tài)，故要大大降低它在匹配值中的比重;ωLi在拐彎時(shí)不起主要作用，故也適當(dāng)降低其比重，如 ωLi=0.3，ωθi=0.6，ωβi=0.1。(Ⅱ)原始定位點(diǎn)P的匹配圓和節(jié)點(diǎn)O1的匹配區(qū)域未接觸時(shí)，情況與(Ⅰ)中相反，ωLi和ωβi起著決定作用，故增加它們的比重，如 ωLi=0.45，ωθi=0.10，ωβi=0.45。匹配因子的數(shù)值隨著定位點(diǎn)與節(jié)點(diǎn)的相對(duì)位置而變化，這樣自適應(yīng)算法能夠增強(qiáng)對(duì)正確路段和復(fù)雜路段的正確識(shí)別，同時(shí)也增加了匹配因子的靈活性。

圖3 角度和距離示意圖

圖4 分段占優(yōu)自適應(yīng)算法模型圖

3 匹配算法實(shí)現(xiàn)及異常處理

3.1 匹配算法實(shí)現(xiàn)

硬件搭建主要包括3大部分，即嵌入式平臺(tái)、GPS模塊和GPRS模塊。其中，嵌入式平臺(tái)為友善之臂的Tiny6410開發(fā)板，安裝android操作系統(tǒng);GPS模塊為美國(guó)GARMIN公司的GPS25LP;GPRS模塊為明基M33G Series，內(nèi)嵌TCP/IP協(xié)議。GPS和GPRS模塊分別通過串口和開發(fā)板連接。圖5為匹配算法的流程圖，該算法的核心包括:融合技術(shù)篩選匹配路段和分段占優(yōu)算法選取匹配路段。匹配算法的主要步驟如下:(Ⅰ)獲取GPS定位數(shù)據(jù)。(Ⅱ)判斷定位數(shù)據(jù)是否異常和Temp表中有無可信點(diǎn)。若異常且Temp表無可信點(diǎn)，則重新進(jìn)行GPS數(shù)據(jù)獲取;若異常且Temp表有可信點(diǎn)，則進(jìn)行異常處理。(Ⅲ)WGS-84轉(zhuǎn)BJ-54坐標(biāo)。(Ⅳ)由原始定位點(diǎn)通過融合技術(shù)篩選匹配路段區(qū)域。(Ⅴ)計(jì)算誤差區(qū)域，并判斷篩選區(qū)位于誤差區(qū)域的置信度是否大于90%，大于90%，繼續(xù)，小于90%，重新篩選。(Ⅵ)依據(jù)分段占優(yōu)匹配因子自適應(yīng)算法，計(jì)算原始定位點(diǎn)到篩選區(qū)域內(nèi)所有路段的匹配值，取最小值為當(dāng)前車輛的行駛路段。(Ⅶ)將原始定位點(diǎn)通過投影法，顯示在地圖上。

圖5 地圖匹配算法流程圖

3.2 異常處理

異常處理是指對(duì)異常的GPS定位點(diǎn)數(shù)據(jù)進(jìn)行處理的過程，包括奇異點(diǎn)數(shù)據(jù)處理和信號(hào)暫時(shí)中斷處理。

(Ⅰ)奇異點(diǎn)數(shù)據(jù)處理

GPS接收機(jī)在遇到較大干擾的情況下，可能出現(xiàn)“跳點(diǎn)”。為了防止出現(xiàn)錯(cuò)誤的道路匹配現(xiàn)象，必須降低跳點(diǎn)的出現(xiàn)頻率[9-11］。本文對(duì)接收GPS定位點(diǎn)數(shù)據(jù)進(jìn)行卡爾曼濾波預(yù)處理，采用的濾波方式是該定位點(diǎn)與上一定位點(diǎn)之間的連線同候選路段的夾角變化率不得超過最大變化角度(如定義為30°)，否則可以將該定位點(diǎn)濾除，即濾波算法采用拋棄該點(diǎn)方式。

(Ⅱ)信號(hào)暫時(shí)中斷處理

信號(hào)暫時(shí)中斷時(shí)(如車輛行駛在隧道等GPS信號(hào)不強(qiáng)的位置上)，應(yīng)該采用線性插值數(shù)據(jù)補(bǔ)償或采用A_GPS進(jìn)行輔助定位，在車輛行駛的方向上進(jìn)行線性差值預(yù)判斷，直到能正常接收到GPS定位數(shù)據(jù)為止。

4 試驗(yàn)分析

為了驗(yàn)證匹配算法的實(shí)時(shí)性及定位精度的準(zhǔn)確性，本文對(duì)該算法進(jìn)行了跑車試驗(yàn)。圖6為原始接收的位置數(shù)據(jù)和匹配后的位置數(shù)據(jù)比較，圖中的三角形表示接收的原始GPS定位數(shù)據(jù)，圓形表示進(jìn)行匹配算法后的定位數(shù)據(jù)。由圖6可知:進(jìn)行匹配后的數(shù)據(jù)全部在實(shí)際道路上，表明該算法的定位精度高，匹配效果好。

圖7為位置誤差對(duì)比曲線，圖中虛線部分為原始GPS數(shù)據(jù)在實(shí)際道路上的誤差，實(shí)線部分為經(jīng)過匹配算法后的誤差。從圖7可知:經(jīng)過匹配算法后的位置誤差大大降低，保證位置誤差在5 m以內(nèi)，定位精度優(yōu)于原始GPS定位精度。定位誤差時(shí)大時(shí)小主要受車速和路況影響，對(duì)比圖6和圖7，圖6中車輛進(jìn)入拐彎時(shí)，正好對(duì)應(yīng)圖7出現(xiàn)位置誤差最大值，即10 s時(shí)所對(duì)應(yīng)的誤差。未經(jīng)匹配算法的GPS原始數(shù)據(jù)誤差在15 m以上，經(jīng)過匹配算法后定位誤差大大降低，提高十字路口的匹配精度，與設(shè)計(jì)的初衷符合，證明本算法的合理性和正確性。同時(shí)，從圖7還可以看出:在0.5 s時(shí)，出現(xiàn)位置誤差對(duì)比曲線，所以采用該算法后能快速地把GPS數(shù)據(jù)匹配到實(shí)際道路上，定位時(shí)間為0.5 s。

圖6 十字交叉道路實(shí)例

圖7 位置誤差對(duì)比曲線

5 結(jié)束語(yǔ)

本文結(jié)合嵌入式/電子地圖系統(tǒng)，提出一種基于角度和距離分段占優(yōu)的地圖匹配算法。該算法由于采用分段占優(yōu)自適應(yīng)匹配因子，并引入融合技術(shù)網(wǎng)格篩選匹配區(qū)域的思想，同時(shí)對(duì)實(shí)際匹配過程中出現(xiàn)的異常情況進(jìn)行處理，解決了普通的定位算法響應(yīng)速度慢，匹配誤差大的缺點(diǎn)。最后，通過試驗(yàn)和實(shí)時(shí)在線驗(yàn)證，表明該算法能適應(yīng)不同的路段及交叉路口，并增強(qiáng)了車輛導(dǎo)航系統(tǒng)的定位性能，提高了實(shí)時(shí)性和匹配精度。

[1]唐思靜.車輛定位導(dǎo)航系統(tǒng)中地圖匹配和路徑規(guī)劃算法研究[D］.西安:西安電子科技大學(xué)，2009.

[2]陳嵐嵐，畢篤彥，馬時(shí)平.Hausdorff距離在圖像匹配中的運(yùn)用[J］.現(xiàn)代電子技術(shù)，2012，9(4):68-69.

[3]華永平，劉硯一.車載定位系統(tǒng)中綜合地圖匹配算法研究[J］.現(xiàn)代雷達(dá)，2010，32(3):53-56.

[4]李聰.地圖匹配算法設(shè)計(jì)與實(shí)現(xiàn)[D］.北京:北京交通大學(xué)，2011.

[5]Li X，Zhang X H，Lin H.Deriving Network-constrained Trajectories from Sporadic Tracking Points Collected in Locationbased Senicesy[J］.Geo-spatial Information Science，2009，12(2):85-94.

[6]Glaus R，Peels G，Muller U，et al.Precise Rail Track Surveying[J］.GPS World，2004，12(2):76-78.

[7]隋心.GPS車輛導(dǎo)航系統(tǒng)中地圖匹配算法研究[D］.葫蘆島:遼寧工程技術(shù)大學(xué)，2007.

[8]張振輝，崔鐵軍.車輛導(dǎo)航系統(tǒng)中地圖匹配算法的研究[J］.技術(shù)交流與應(yīng)用，2007(2):55-59.

[9]陳嘉，胡繼華，張飛舟.面向車輛監(jiān)控導(dǎo)航的地圖匹配算法研究[J］.北京大學(xué)學(xué)報(bào)，2009，45(2):299-305.

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

[11]White C E，Bernstein D，Kornhau S A L.Some Map-matching Algorithms for Personal Navigation Assistants[J］.Transportation Research Part C，2000(8):91-108.