車載GPS地圖匹配算法研究背景意義及現(xiàn)狀

1、車載GPS地圖匹配算法研究背景意義及現(xiàn)狀1研究背景及意義12 國(guó)內(nèi)外研究現(xiàn)狀分析23常見地圖匹配算法分析3 1研究背景及意義當(dāng)今社會(huì)，機(jī)動(dòng)車數(shù)量迅猛增長(zhǎng)，從而導(dǎo)致交通流量過快增長(zhǎng)與有限的道路設(shè)施之間的矛盾激增，交通堵塞嚴(yán)重。如何的減少擁堵，有效地進(jìn)行交通疏導(dǎo)，合理的利用有限的交通設(shè)施是當(dāng)前亟待解決的難題，發(fā)展智能交通（ITS）是解決這些問題的有效方法。隨著GPS(Global Positioning System)衛(wèi)星定位技術(shù)和通信技術(shù)的日趨成熟，基于GPS的自動(dòng)定位在智能交通系統(tǒng)中顯示出其巨大的技術(shù)、經(jīng)濟(jì)和社會(huì)效益，基于GPS的自動(dòng)定位關(guān)鍵技術(shù)是地圖匹配技術(shù)。地圖匹配(Map matchin

2、g,簡(jiǎn)稱MM)是一種基于軟件技術(shù)的定位修正方法。地圖匹配基于兩個(gè)前提：首先，車輛總是行駛在道路上；其次，電子地圖道路數(shù)據(jù)精度應(yīng)高于浮動(dòng)車車載導(dǎo)航系統(tǒng)的位置估計(jì)精度。當(dāng)上述條件滿足時(shí)，將定位信息與道路信息進(jìn)行比較，通過一定的匹配過程，確定出車輛最可能的行駛路段及車輛在此路段中最可能的位置。地圖匹配算法的實(shí)現(xiàn)與電子地圖有著密切的關(guān)系，電子地圖必須具有正確的路網(wǎng)拓?fù)浣Y(jié)構(gòu)和足夠高的精度才能完成地圖匹配。地圖匹配技術(shù)在ITS中的應(yīng)用可以總結(jié)為以下三個(gè)方面： 用于地圖顯示。地圖匹配在ITS中最基本的應(yīng)用是實(shí)現(xiàn)被跟蹤車輛在電子地圖上的顯示。由于各種定位技術(shù)存在不同程度的定位誤差，造成了車輛的定位點(diǎn)通常沒有落

3、在道路上。而ITS的大部分信息都要通過電子地圖來(lái)顯示，因此，必須通過地圖匹配算法將車輛匹配到其正在行駛的道路上。 用于提高定位精度。由于高樓和高架橋阻擋接收機(jī)的信號(hào)等因素的影響，GPS有時(shí)無(wú)法提供足夠的定位精度。航位推算可以實(shí)現(xiàn)車輛的自主導(dǎo)航，但需要車輛初始位置的輸入，而且慣性期間的漂移誤差和標(biāo)定誤差將使累積誤差隨時(shí)間而增大。此時(shí)可以利用地圖匹配算法來(lái)改善定位精度，高精度的電子地圖可用于修正定位估計(jì)的誤差。 用于終端用戶路徑引導(dǎo)等應(yīng)用。路徑引導(dǎo)是幫助駕駛員沿預(yù)定的路線行駛從而順利達(dá)到目的地的過程。為此，必須由地圖匹配模塊為路徑引導(dǎo)模塊提供當(dāng)前車輛的準(zhǔn)確位置，路徑引導(dǎo)模塊與地圖信息相結(jié)合產(chǎn)生適當(dāng)

4、的實(shí)時(shí)駕駛指令，引導(dǎo)車輛到達(dá)目的地。由于地圖匹配算法的研究具有很強(qiáng)的實(shí)用價(jià)值，在ITS中具有重要作用，因此，研究低成本，高效率和高精度的地圖匹配算法具有重要的理論和實(shí)際意義。 2 國(guó)內(nèi)外研究現(xiàn)狀分析 基于卡爾曼濾波的地圖匹配算法韓國(guó)Seoul Nat 大學(xué)的Wuk Kim、Gyu-In Jee 和JangGyu Lee (2000) 為解決白噪聲和偏移誤差干擾的而造成定位的低精度和在道路交叉口處道路的選擇模糊問題，提出了一種新算法，該算法以重大偏倚作為主要的誤差，校正車輛的位置，此算法可以認(rèn)為是由一種基于重大偏倚誤差的模型和卡爾曼濾波器組成，該算法已經(jīng)在GPS導(dǎo)航系統(tǒng)中得到了實(shí)際的應(yīng)用。意大利

5、的Tiano,A.、Zirilli,A.和Pizzocchero,F. 在2001年研究了一種可用于整合導(dǎo)航系統(tǒng)的新算法，來(lái)對(duì)各種海上、地上的交通工具例如船舶與汽車進(jìn)行精確地位置估算。該算法結(jié)合了神經(jīng)模糊卡爾曼濾波與地圖匹配算法，目的是改進(jìn)GPS與傳感器（例如陀螺儀）結(jié)合的實(shí)時(shí)地圖匹配系統(tǒng)。通過實(shí)驗(yàn)結(jié)果，可以看出該系統(tǒng)在通常交通狀況下，車輛的位置定位準(zhǔn)確度較高。美國(guó)學(xué)者 Hao Xu, Chin-woo Tan, Yuanlu Bao 在2008年研究一種基于卡爾曼濾波和GPS誤差校正的地圖匹配改進(jìn)算法。其通過對(duì)對(duì)GPS誤差分析的可知，GPS在兩個(gè)垂直方向上的分量被加進(jìn)數(shù)據(jù)空間作為數(shù)據(jù)變量，構(gòu)

6、成新的卡爾曼濾波器模型。同時(shí)，根據(jù)浮動(dòng)車轉(zhuǎn)彎后的信息和行駛軌跡可以得到沿道路方向上的GPS誤差。改進(jìn)的卡爾曼濾波算法和搜索行駛軌跡GPS誤差的算法相結(jié)合，得到了一個(gè)新的改進(jìn)的算法。該算法處理誤差十分的有效，該誤差包括沿道路方向和垂直于道路方向的偏移誤差和白噪聲誤差。通過實(shí)驗(yàn)研究可知，該算法模型是非常有效。結(jié)果顯示，該算法有助于提高浮動(dòng)車導(dǎo)航系統(tǒng)的精度。 航位推算地圖匹配算法法國(guó)的Renault,s 和Meizel,D. (2006) 提出了一種在復(fù)雜城市環(huán)境中解決車輛定位問題的地圖匹配算法。此算法利用GPS數(shù)據(jù)和航位推算系統(tǒng)，并結(jié)合了改進(jìn)的卡爾曼濾波器使用精確地GIS電子地圖，采用點(diǎn)集合搜索和

7、橢圓算法，在一定程度上提高了匹配精度和匹配效率。 權(quán)重地圖匹配算法美國(guó)芝加哥的Huabei Yin 和Wolfson,O.在2004年提出了一種基于權(quán)重的地圖匹配算法，該算法通過把一個(gè)移動(dòng)對(duì)象在3D時(shí)空中的運(yùn)動(dòng)軌跡即一個(gè)(x,y,t) 坐標(biāo)時(shí)間序列匹配到精確地GIS電子地圖的道路上，并通過實(shí)驗(yàn)驗(yàn)證，根據(jù)GPS取樣的時(shí)間間隔，平均能達(dá)到94%的正確率。湖南大學(xué)的胡林、古正氣等(2008年)研究了基于權(quán)值D-S證據(jù)理論的地圖匹配算法。該算法對(duì)傳統(tǒng)的D-S證據(jù)理論進(jìn)行了改進(jìn)，解決了證據(jù)的可信度問題。該算法首先根據(jù)證據(jù)的局部決策算出局部決策值，構(gòu)造整個(gè)系統(tǒng)的支持矩陣，并求出支持矩陣的特征向量，并以此作

8、為各個(gè)證據(jù)的可信度，然后把可信度作為各個(gè)證據(jù)的權(quán)值，以此修正D-S證據(jù)的融合算法，使新的組合理論規(guī)則能夠有效的處理證據(jù)中的沖突信息；然后結(jié)合當(dāng)前城市道路網(wǎng)日益復(fù)雜的實(shí)際特點(diǎn)，把基于權(quán)值的D-S證據(jù)理論應(yīng)用于地圖匹配中。公安部交通管理科學(xué)研究所的張雷元、徐棱、劉小明（2009年）提出的改進(jìn)的要素加權(quán)算法。其原理是綜合地圖匹配中的道路幾何信息、GPS歷史信息、GPS導(dǎo)航方向信息以及道路拓?fù)湫畔?，?jì)算候選路段的匹配權(quán)重，然后通過綜合比較權(quán)重，采用圈中最高的路作為匹配路段。 幾何的地圖匹配算法北京理工大學(xué)的周培德、付夢(mèng)?。?004年）提出了基于計(jì)算幾何的地圖匹配方法，就是采用不斷計(jì)算GPS信號(hào)點(diǎn)是否構(gòu)

9、成凸殼，并判斷道路是否穿越該凸殼來(lái)確定定位信號(hào)點(diǎn)的匹配道路。 基于云模型的地圖匹配算法山東理工大學(xué)唐進(jìn)軍、曹凱（2007年）提出基于云模型不確定性推理的地圖匹配算法。該算法的關(guān)鍵是提出一種能夠?qū)崿F(xiàn)定性概念與定量數(shù)值之間不確定性轉(zhuǎn)換的云模型。通過建立云規(guī)則，和進(jìn)行基于云模型的不確定性推理，并結(jié)合高程輔助方法來(lái)構(gòu)筑地圖匹配模型。 基于路網(wǎng)拓?fù)浣Y(jié)構(gòu)的地圖匹配算法重慶大學(xué)孫棣華等（2008年）針對(duì)MapInfo數(shù)據(jù)格式電子地圖不具備拓?fù)浣Y(jié)構(gòu)，且現(xiàn)有拓?fù)浣Y(jié)構(gòu)構(gòu)建算法精度低、效率差等不足，提出在路網(wǎng)拓?fù)浣Y(jié)構(gòu)構(gòu)建前，應(yīng)用緩沖區(qū)分析技術(shù)和計(jì)算區(qū)域質(zhì)點(diǎn)等預(yù)處理方法，對(duì)原始路網(wǎng)不規(guī)則的關(guān)系進(jìn)行分類和道路信息補(bǔ)充，

10、以此為基礎(chǔ)創(chuàng)建道路段和節(jié)點(diǎn)圖層，建立路網(wǎng)拓?fù)潢P(guān)系。實(shí)驗(yàn)結(jié)果表明，該算法構(gòu)建精度和效率明顯提高。3常見地圖匹配算法分析地圖匹配算法包括路段選擇算法和具體位置識(shí)別算法，現(xiàn)有的路段選擇的地圖匹配方法主要分為兩大類：以降噪技術(shù)為主的地圖匹配算法和以選路為基礎(chǔ)的地圖匹配算法。以降噪為基礎(chǔ)的地圖匹配算法主要思想是通過軟件技術(shù)，利用恰當(dāng)?shù)臄?shù)學(xué)手段如卡爾曼濾波等降低GPS信號(hào)的噪聲，以提高匹配精度。但是現(xiàn)有降噪技術(shù)為指導(dǎo)思想的地圖匹配算法并不是特別的適合于工程應(yīng)用中。以選路為基礎(chǔ)的地圖匹配算法也可以分為兩類：只運(yùn)用路網(wǎng)幾何信息的算法和將路網(wǎng)幾何信息與路網(wǎng)拓?fù)湫再|(zhì)相結(jié)合的算法。只運(yùn)用路網(wǎng)幾何信息的地圖匹配算法主

11、要有：點(diǎn)到點(diǎn)、點(diǎn)到線、線到線的匹配算法。此類算法，實(shí)現(xiàn)比較簡(jiǎn)單，計(jì)算量小，前期的處理工作量少，易于實(shí)現(xiàn)，缺點(diǎn)是在匹配時(shí)只利用了路網(wǎng)的幾何信息，沒有利用路網(wǎng)的拓?fù)浣Y(jié)構(gòu)信息，使其受定位誤差及地圖精度影響較大，穩(wěn)定性不佳，容易產(chǎn)生振蕩，極易發(fā)生匹配錯(cuò)誤。 將路網(wǎng)幾何信息和路網(wǎng)拓?fù)浣Y(jié)構(gòu)信息相結(jié)合的地圖匹配算法是現(xiàn)在的主流研究方向，可細(xì)分為以下幾類： 改進(jìn)的算法有改進(jìn)的點(diǎn)到線、線到線的匹配算法。此類算法充分利用了拓?fù)湫畔⒓绰肪W(wǎng)的連通性，增加了起點(diǎn)和終點(diǎn)的信息。如果前一時(shí)刻的匹配可信，那么就應(yīng)用拓?fù)湫畔⑵ヅ浜罄m(xù)定位點(diǎn)。但是，一個(gè)錯(cuò)誤的匹配會(huì)導(dǎo)致一系列的誤匹配。 傳統(tǒng)的地圖匹配方法有概率統(tǒng)計(jì)算法、相關(guān)性算法

12、和基于模糊邏輯的地圖匹配算法。傳統(tǒng)的地圖匹配算法在曲線和折線路段時(shí)，效果最好，但權(quán)重的不好選取。 基于模式識(shí)別的匹配方法，包括基于神經(jīng)網(wǎng)絡(luò)和數(shù)據(jù)融合的方法(D-S數(shù)據(jù)論證) 。 基于代價(jià)函數(shù)的地圖匹配算法以上二類算法，精度高，對(duì)于特地區(qū)域的地圖匹配效果明顯，但由于計(jì)算量大，實(shí)現(xiàn)非常復(fù)雜，同時(shí)實(shí)時(shí)性很差。 目前將車輛匹配到路段上具體位置的匹配算法主要以下三種： 垂直投影法：將定位點(diǎn)垂直投影到當(dāng)前行駛的路段上，投影點(diǎn)即為匹配點(diǎn)。這種方法邏輯簡(jiǎn)單、速度快、實(shí)時(shí)性好、所需內(nèi)存空間少，通過投影使車輛定位數(shù)據(jù)僅殘留定位誤差在車輛前進(jìn)路線上的徑向分量，從而極大地改善系統(tǒng)的定位精度；但在道路密集、道路形狀復(fù)雜和交叉路口等情況下，匹配準(zhǔn)確率較低。