一種改進的浮動車地圖匹配算法

丁閃閃 刁含樓

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

關鍵詞：浮動車;地圖匹配;道路拓撲;要素加權

中圖分類號：P228.4 文獻標識碼：A

0 引言

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

目前，國內外學者研究的地圖匹配算法主要包括幾何匹配算法、概率統計匹配算法、相關性匹配算法、基于要素加權的匹配算法、模式識別匹配算法等[2]。其中，基于要素加權的地圖匹配算法具有邏輯簡單、速度快、實時性好等優點，得到較為廣泛的應用。鄒珍提出一種改進的基于權重的地圖匹配算法[3]，將權重模型與交通規則約束、最短路徑算法相結合。曾嘉酈等提出一種出租車地圖匹配算法[4]，基于定位點到路段的距離、以及車輛行駛方向與道路方向的夾角確定候選路段，根據距離和方向的綜合權重進行軌跡點匹配。在對以往的研究進行分析后發現，充分利用道路拓撲和多個要素可以進一步提高浮動車地圖匹配精度。

本文從這一角度出發，綜合利用道路拓撲關系和車輛定位誤差，縮小候選路段范圍，然后采用基于距離與方向的要素加權方法確定最終的匹配點，以期能夠提高浮動車地圖匹配精度，并確保匹配的實時性。

1 理論基礎

1.1 基于網格法的誤差區域初步確定

在算法設計時，默認車輛總是行駛在道路上，由此可知誤差區域以一定的范圍包含著車輛的實際位置，通過確定誤差區域，可以排除大量不相關的路段，減少算法的復雜度。

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

根據浮動車定位點的經緯度數據，可以確定定位點在哪個網格塊，選取定位點所在網格及其周邊的8個網格作為誤差區域。

1.2 基于道路拓撲的誤差區域縮小

在電子地圖中，道路拓撲關系是指節點與弧段之間的相互關系，在道路聯通的情況下，一定時間范圍內，由于車輛的行駛速度有限，因此存在著一個最遠能夠到達的距離。如圖1所示，假設此時車輛行駛在道路1上，當前匹配點確定為，則由于行駛速度的限制，下一時刻，車輛最遠只能到達、或點，即下一匹配點的位置只能存在于圖中黑色實線部分的路段上。

傳統的考慮道路拓撲關系的地圖匹配算法中，通常是在確定誤差區域后，將定位點向誤差區域內的所有候選路段做投影，確定多個虛擬匹配點，然后將車輛無法到達的匹配點所在的路段去除，對剩余的虛擬匹配點，根據多要素計算綜合匹配度，確定最終的匹配位置。如圖2所示，為當前定位點，和為候選路段2和3上的虛擬匹配點，考慮道路拓撲關系后，認為點無法到達，因此將候選路段2去除，候選路段3成為最終的匹配路段，而成為最終的匹配點。但是從圖中下一匹配點的位置可以判斷，為錯誤匹配點。

針對以上可能出現的錯誤匹配情況，本文做了一定程度改進，在采用網格法確定候選路段后，并不急于將定位點向各路段進行投影，而是先根據前一匹配點的位置和道路拓撲性，另外確定一個匹配點可能存在的誤差區域。將該誤差區域與網格法確定的誤差區域疊加，得到最終誤差區域。將最終誤差區域內路段上的每一個點均作為虛擬匹配點，以避免圖2將路段2整條去除、造成錯誤匹配的情況。

1.3 基于要素加權的最終匹配點確定

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

式中：——距離的權重系數;

——距離匹配度;

——方向匹配度;

——距離閾值，設置為40 m;

——定位點方向;

——虛擬匹配點所在路段;

——定位點與虛擬匹配點之間的直線距離;

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

對于每一個虛擬匹配點均計算一個綜合匹配度，最后選取綜合匹配度最大的點作為最終匹配點。

1.4 完整算法的流程圖

2 實例分析

選取一小部分南京市城市路網作為研究對象，浮動車數據采樣間隔為30 s，通過實現匹配過程，并將匹配路段分為普通路段和交叉口，結果如圖4、5所示：

圖中，“。”代表的是浮動車定位數據，“*”為浮動車地圖匹配點。由圖可知，普通路段共16個定位點，均準確匹配到道路上，匹配準確度100%，交叉口共7個定位點，其中6個準確匹配到道路上，匹配準確度85.7%。普通路段和交叉口的匹配時間分別為0.3 s和0.7 s，具有較好的響應速度。

3 結束語

本文提出一種改進的浮動車地圖匹配算法，通過綜合考慮要素加權與路網拓撲確定匹配路段，主要結論如下：

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

（2）對于存在前一匹配點的情況，根據道路拓撲關系縮小誤差區域，同時完整保留匹配點可能存在的范圍，減少了匹配到錯誤路段的概率。

（3）選取不同的權重系數會對結果產生不同影響，本文中采用了固定的權重系數，下一步將研究根據道路特征、車輛運行狀態等動態調整權重系數，以期進一步提高算法精度。

參考文獻：

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

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

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

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