一種改進(jìn)的浮動車地圖匹配算法

丁閃閃 刁含樓

摘 要：為提高浮動車地圖匹配精度，提出一種改進(jìn)的浮動車地圖匹配算法，綜合利用道路拓?fù)潢P(guān)系和車輛定位誤差，縮小候選路段范圍，采用基于距離與方向的要素加權(quán)方法確定最終匹配點(diǎn)，減少正確匹配路段被剔除的概率。依托南京市局部路網(wǎng)以及浮動車定位數(shù)據(jù)進(jìn)行實(shí)例分析，結(jié)果表明，該方法具有較好的精度和實(shí)時性。

關(guān)鍵詞：浮動車;地圖匹配;道路拓?fù)?要素加權(quán)

中圖分類號：P228.4 文獻(xiàn)標(biāo)識碼：A

0 引言

隨著智能交通系統(tǒng)的應(yīng)用發(fā)展，安裝車載定位設(shè)備的車輛越來越多，浮動車數(shù)據(jù)采集技術(shù)開始廣泛應(yīng)用于城市路況信息獲取、道路建設(shè)和出行規(guī)劃上[1]。地圖匹配是浮動車技術(shù)的重要組成部分，由于路網(wǎng)環(huán)境、電子地圖誤差和定位設(shè)備誤差的影響，浮動車采集的定位點(diǎn)會隨機(jī)分布在道路兩側(cè)一定寬度范圍內(nèi)，只有將這些定位點(diǎn)修正到其行駛的道路上，才能開展相關(guān)應(yīng)用。

目前，國內(nèi)外學(xué)者研究的地圖匹配算法主要包括幾何匹配算法、概率統(tǒng)計(jì)匹配算法、相關(guān)性匹配算法、基于要素加權(quán)的匹配算法、模式識別匹配算法等[2]。其中，基于要素加權(quán)的地圖匹配算法具有邏輯簡單、速度快、實(shí)時性好等優(yōu)點(diǎn)，得到較為廣泛的應(yīng)用。鄒珍提出一種改進(jìn)的基于權(quán)重的地圖匹配算法[3]，將權(quán)重模型與交通規(guī)則約束、最短路徑算法相結(jié)合。曾嘉酈等提出一種出租車地圖匹配算法[4]，基于定位點(diǎn)到路段的距離、以及車輛行駛方向與道路方向的夾角確定候選路段，根據(jù)距離和方向的綜合權(quán)重進(jìn)行軌跡點(diǎn)匹配。在對以往的研究進(jìn)行分析后發(fā)現(xiàn)，充分利用道路拓?fù)浜投鄠€要素可以進(jìn)一步提高浮動車地圖匹配精度。

本文從這一角度出發(fā)，綜合利用道路拓?fù)潢P(guān)系和車輛定位誤差，縮小候選路段范圍，然后采用基于距離與方向的要素加權(quán)方法確定最終的匹配點(diǎn)，以期能夠提高浮動車地圖匹配精度，并確保匹配的實(shí)時性。

1 理論基礎(chǔ)

1.1 基于網(wǎng)格法的誤差區(qū)域初步確定

在算法設(shè)計(jì)時，默認(rèn)車輛總是行駛在道路上，由此可知誤差區(qū)域以一定的范圍包含著車輛的實(shí)際位置，通過確定誤差區(qū)域，可以排除大量不相關(guān)的路段，減少算法的復(fù)雜度。

本文采用網(wǎng)格法確定誤差區(qū)域，在柵格地圖基礎(chǔ)上建立網(wǎng)格，利用折半查找法快速尋找出浮動車軌跡點(diǎn)所在的候選區(qū)域。由于定位接收機(jī)接收到的數(shù)據(jù)誤差95%都在20 m以內(nèi)，而數(shù)據(jù)投射到電子地圖上的誤差為15 m左右。綜合考慮，取每個網(wǎng)格的邊長為40 m。

根據(jù)浮動車定位點(diǎn)的經(jīng)緯度數(shù)據(jù)，可以確定定位點(diǎn)在哪個網(wǎng)格塊，選取定位點(diǎn)所在網(wǎng)格及其周邊的8個網(wǎng)格作為誤差區(qū)域。

1.2 基于道路拓?fù)涞恼`差區(qū)域縮小

在電子地圖中，道路拓?fù)潢P(guān)系是指節(jié)點(diǎn)與弧段之間的相互關(guān)系，在道路聯(lián)通的情況下，一定時間范圍內(nèi)，由于車輛的行駛速度有限，因此存在著一個最遠(yuǎn)能夠到達(dá)的距離。如圖1所示，假設(shè)此時車輛行駛在道路1上，當(dāng)前匹配點(diǎn)確定為，則由于行駛速度的限制，下一時刻，車輛最遠(yuǎn)只能到達(dá)、或點(diǎn)，即下一匹配點(diǎn)的位置只能存在于圖中黑色實(shí)線部分的路段上。

傳統(tǒng)的考慮道路拓?fù)潢P(guān)系的地圖匹配算法中，通常是在確定誤差區(qū)域后，將定位點(diǎn)向誤差區(qū)域內(nèi)的所有候選路段做投影，確定多個虛擬匹配點(diǎn)，然后將車輛無法到達(dá)的匹配點(diǎn)所在的路段去除，對剩余的虛擬匹配點(diǎn)，根據(jù)多要素計(jì)算綜合匹配度，確定最終的匹配位置。如圖2所示，為當(dāng)前定位點(diǎn)，和為候選路段2和3上的虛擬匹配點(diǎn)，考慮道路拓?fù)潢P(guān)系后，認(rèn)為點(diǎn)無法到達(dá)，因此將候選路段2去除，候選路段3成為最終的匹配路段，而成為最終的匹配點(diǎn)。但是從圖中下一匹配點(diǎn)的位置可以判斷，為錯誤匹配點(diǎn)。

針對以上可能出現(xiàn)的錯誤匹配情況，本文做了一定程度改進(jìn)，在采用網(wǎng)格法確定候選路段后，并不急于將定位點(diǎn)向各路段進(jìn)行投影，而是先根據(jù)前一匹配點(diǎn)的位置和道路拓?fù)湫裕硗獯_定一個匹配點(diǎn)可能存在的誤差區(qū)域。將該誤差區(qū)域與網(wǎng)格法確定的誤差區(qū)域疊加，得到最終誤差區(qū)域。將最終誤差區(qū)域內(nèi)路段上的每一個點(diǎn)均作為虛擬匹配點(diǎn)，以避免圖2將路段2整條去除、造成錯誤匹配的情況。

1.3 基于要素加權(quán)的最終匹配點(diǎn)確定

對于每一個虛擬匹配點(diǎn)，首先判斷其與定位點(diǎn)的直線距離是否超過閾值，如果超過閾值則剔除，如果在閾值范圍內(nèi)，則進(jìn)一步采用基于要素加權(quán)的方式計(jì)算其綜合匹配度。對所有能夠獲取的、并且對地圖匹配精度產(chǎn)生影響的因素進(jìn)行分析，最終選取距離和方向作為考慮要素。第個虛擬匹配點(diǎn)的綜合匹配度計(jì)算公式為：

式中：——距離的權(quán)重系數(shù);

——距離匹配度;

——方向匹配度;

——距離閾值，設(shè)置為40 m;

——定位點(diǎn)方向;

——虛擬匹配點(diǎn)所在路段;

——定位點(diǎn)與虛擬匹配點(diǎn)之間的直線距離;

——定位點(diǎn)方向與虛擬匹配點(diǎn)所在路段方向的夾角，。

對于每一個虛擬匹配點(diǎn)均計(jì)算一個綜合匹配度，最后選取綜合匹配度最大的點(diǎn)作為最終匹配點(diǎn)。

1.4 完整算法的流程圖

2 實(shí)例分析

選取一小部分南京市城市路網(wǎng)作為研究對象，浮動車數(shù)據(jù)采樣間隔為30 s，通過實(shí)現(xiàn)匹配過程，并將匹配路段分為普通路段和交叉口，結(jié)果如圖4、5所示：

圖中，“?！贝淼氖歉榆嚩ㄎ粩?shù)據(jù)，“*”為浮動車地圖匹配點(diǎn)。由圖可知，普通路段共16個定位點(diǎn)，均準(zhǔn)確匹配到道路上，匹配準(zhǔn)確度100%，交叉口共7個定位點(diǎn)，其中6個準(zhǔn)確匹配到道路上，匹配準(zhǔn)確度85.7%。普通路段和交叉口的匹配時間分別為0.3 s和0.7 s，具有較好的響應(yīng)速度。

3 結(jié)束語

本文提出一種改進(jìn)的浮動車地圖匹配算法，通過綜合考慮要素加權(quán)與路網(wǎng)拓?fù)浯_定匹配路段，主要結(jié)論如下：

（1）基于網(wǎng)格法初步確定誤差區(qū)域，提高了算法的運(yùn)行效率，雖然網(wǎng)格范圍較大，可能包含了與定位點(diǎn)距離超過閾值的點(diǎn)，但這些點(diǎn)可在后續(xù)步驟中快速判斷和刪除。

（2）對于存在前一匹配點(diǎn)的情況，根據(jù)道路拓?fù)潢P(guān)系縮小誤差區(qū)域，同時完整保留匹配點(diǎn)可能存在的范圍，減少了匹配到錯誤路段的概率。

（3）選取不同的權(quán)重系數(shù)會對結(jié)果產(chǎn)生不同影響，本文中采用了固定的權(quán)重系數(shù)，下一步將研究根據(jù)道路特征、車輛運(yùn)行狀態(tài)等動態(tài)調(diào)整權(quán)重系數(shù)，以期進(jìn)一步提高算法精度。

參考文獻(xiàn)：

[1]丁閃閃，王維鋒，季錦章，等.一種城市快速路主輔道的浮動車地圖匹配方法[P].中國發(fā)明專利，ZL201510259876.2，2015-05-20.

[2]孫棣華，張星霞，張志良.地圖匹配技術(shù)及其在智能交通系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2005，42（20）：225-228.

[3]鄒珍.基于GPS的浮動車數(shù)據(jù)與實(shí)地圖匹配的算法研究[D].武漢理工大學(xué)，2013.

[4]曾嘉酈，孫立雙，王曉明.北京出租車GPS軌跡數(shù)據(jù)地圖匹配算法研究[J].北京測繪，2019，33（03）：255-260.