基于浮動車GPS軌跡點數據的地圖匹配算法研究

摘 要：文章研究基于GPS浮動車軌跡點數據的地圖匹配原理及地圖匹配方法。提出了基于GPS點到校正點的匹配，并且利用連續幾個GPS點的軌跡確定結果，最終獲取較為正確的路網匹配結果，實現城市道路網絡浮動車GPS樣本數據與電子地圖的匹配速度與精度。為實時掌握與分析道路交通狀態提供基礎數據。

關鍵詞：浮動車；GPS；地圖匹配；軌跡點

引言

建立城市交通綜合信息平臺，通過對龐大的城市交通網絡中的實時交通信息進行深入分析，為改善城市交通信息服務水平，提高決策科學性，緩解城市交通擁堵提供了基礎。交通綜合信息平臺的數據支撐來源于交通基礎信息的實時采集，科學決策的依據在于數據分析的快速、準確。

GPS浮動車是獲取道路實時車速便捷有效的方法，可以通過車載GPS定位信息獲取道路實時車速及運行狀態（擁堵、暢通、緩行），其作為一種便捷廉價、可操作性高的車速采集手段已經被各城市普遍采用，特別是公交車與出租車安裝車載GPS設備最為常見。通過對公交車及出租車的GPS返回數據與城市道路網的匹配、分析來獲取道路的實時車速，進而實現對道路狀態的有效判斷。因此確保GPS浮動車軌跡點數據與信息平臺電子地圖快速、準確匹配是管理決策的基礎，研究準確適用的GPS浮動車軌跡點數據的地圖匹配算法是非常重要的。

1 GPS數據的地圖匹配原理

地圖匹配（Map-Match）簡稱MM技術，就是利用電子地圖的路網信息和GPS數據來實行對車輛行駛準確位置的確定，它是一種定位誤差修正技術。

浮動車所上報的GPS數據中包含有經緯度等地理信息，但這些GPS坐標只能反映車輛位置情況，而不能與實際路網路段直接相關聯。因此，車輛在路網中行駛的情況，必須要依賴于地圖匹配算法來完成車輛位置信息與路網位置的關聯。

地圖匹配算法的直接目的是將GPS測得的車輛位置或行駛軌跡，與現有的電子地圖道路路段數據進行比較，繼而找到車輛所處的道路，計算出浮動車輛在道路上所處的位置。一般地圖匹配過程有以下幾個步驟：

（1）通過對獲取的GPS數據的預處理及匹配模板的分析、描述，提取出點和道路的軌跡特征。

（2）根據對地圖匹配規則的制定，計算出GPS樣本和匹配模板兩者的相似度、匹配度。

（3）選取待匹配點距離最近或者是軌跡相似度、匹配度最高的道路曲線模板，可更正匹配樣本的位置或軌跡，作為匹配結果[1]。

圖1 地圖匹配原理圖

地圖匹配原理一般可分成兩個過程來表達：即尋找GPS待匹配點最可能歸屬的道路，并將GPS浮動點投影到這條它所歸屬的道路上面。

以上兩個過程的關鍵在于需找GPS待匹配點最可能歸屬的道路，基本的思想即是在GPS點四周一定范圍內搜索所有的可匹配點，然后根據匹配度計算，淘汰匹配度較低的點，選出最優點。并將此最優點作為GPS浮動車車輛的當前行駛路線。這樣，尋找最優點成為算法性能優劣的關鍵所在，如果搜索范圍過大，需對周圍各條道路一一篩選，增加了算法計算量，導致匹配速度緩慢。反之，如果搜索范圍過小，則有可能未能準確尋找到最佳匹配點，出現匹配錯誤，降低匹配的準確率。

2 基于GPS軌跡點的浮動車地圖匹配算法

可實現地圖匹配的算法很多，在GPS數據量極大，且算法應用的場景為實時車速展示，需要選擇一個合適的方法，保證匹配的準確性和匹配速度。因此文章提出的地圖匹配算法是基于GPS點到校正點的匹配，并且利用連續幾個GPS點的軌跡確定結果，最終獲取較為正確的路網匹配結果。

2.1 網格匹配

Step1：計算GPS點所歸屬網格。

當在系統中導入GPS數據信息后，可從這些原始數據中提取出坐標信息。可設為（x，y）。然后對該GPS坐標信息進行可信度檢測，首先取網格劃分中最大和最小的兩個坐標點，其中最大的坐標點位于地圖的右上角，假設為（xm，ym），最小的坐標點則位于地圖的左下角，假設為（xn，yn）。如果待匹配點坐標（x，y）滿足以下條件：

則認為該GPS點在研究坐標范圍之內，轉到下一步計算。

Step2：搜尋所在網格匹配

根據該GPS點的坐標信息，在網格列表中搜尋其所屬的網格。假設網格編號為G0，若

（x，y）∈{G0}

則判定該點位于G0網格內。

在搜尋到所在網格后，將所在網格G0中的所有校正點加入到待匹配集合。但在該匹配中需要注意的是當GPS點與網格邊距離小于1/3時，則需要將其相鄰網格（G1……G8）所包含的校正點一并加入待匹配集合，進行匹配度計算。（見圖2）

2.2 節點匹配

Step1：計算GPS與路段的距離和方向差

在網格匹配中搜尋出的校正點集合被稱為待匹配集合。需要將GPS點與帶匹配集合中的各個校正點進行匹配，找尋出最佳匹配點。

計算GPS點與各待匹配校正點之間的距離。設GPS點坐標為（x，y），GIS校正點坐標為（xr，yr），由于兩點距離較近，兩點接近于平面，則可根據平面距離公式

得出GPS點與各校正點之間的距離d。

計算GPS點與路段各校正點之間的夾角。取GPS數據的角度為？漬0，再與網格內的GIS路段校正點的切線方向角度？漬r（取正北方向為0°）求差值。可得出GPS點與路段方向的夾角α。

Step2：匹配度計算

匹配度是判斷校正點優劣的重要標準，是描述GPS點與一條道路的匹配程度，用實際算法所求得的數值進行量化，匹配度越大，就認為發出這個GPS數據的浮動車越有可能位于這條道路。對于匹配度的計算，主要考慮的是GPS與路段的距離及其與路段的夾角。

圖3 GPS點匹配

Step3：Confidence Point（CP點）判斷

針對GPS浮動車地圖匹配的特殊性，本文提出了Confidence Point判斷。所謂Confidence Point，就是可信點[8]。判斷是否為CP點，主要判斷其所有匹配點是否位于同一路段。

由于浮動車地圖匹配的最終目的是為城市各條道路得到路段平均速度提供起點、終點以及時間信息，而當車輛距離路口（包括城市立交路口、普通平面交叉路口、主輔路的出入口等）比較近時，由于GPS浮動車減速、并線等駕駛行為導致GPS數據中的方向信息等變化較大、準確性降低，使得系統比較難以確定車輛的準確位置。 但是考慮到GPS浮動車地圖匹配的一個最終目的是獲取路況實時信息，因此，如果無論車輛當前在哪條道路上行駛，只要能確定車輛必定通過或者必定離開某個路口，就可以根據GPS浮動車輛的下一個GPS定位數據確定其這一段時間的行駛軌跡。

因此當GPS數據處于路口節點或分合流點附近時，它所對應的匹配點并不在同一路段上，系統將這樣的數據判定為非CP點，作為延遲匹配點，利用行駛路徑進行匹配。反之，若GPS數據所對應的匹配點位于同一路段，則系統將其判定為CP可信點，對其各匹配點進行匹配度計算。

其中對于CP可信點，系統按照step3中匹配度計算中所確定的方法進行匹配度計算。取匹配度最大的點為最佳匹配點。對于非CP點，則轉入下一步。

Step4：延遲匹配

對于上一步所提到的非CP點，并無法通過單一的GPS數據匹配來確定浮動車的確切位置，這時就需要通過相同浮動車的多個GPS數據來聯合判斷車輛的行駛路線軌跡。

圖5 非CP點延遲匹配示意圖

假設某浮動車連續的n個GPS數據組成的序列Pn（n=1，2，3，……，k），滿足以下條件：

（1）P1點為CP點，P2為非CP點，且k小于延遲匹配的允許最大值；（2）Pk為已經確定的CP點，并能按照地圖匹配方法正確尋找到最佳匹配點。

則可利用前后兩個CP點P1和Pk，尋找這相鄰兩個CP點的最短路徑L。再利用最短路徑L對P2，P3，Pn-1進行匹配，去掉不屬于L的匹配點，再取最大匹配度點作為最佳匹配點。

3 結束語

文章所使用的地圖匹配方法通過獲取GPS浮動車數據，利用GPS坐標信息，通過比對電子地圖各條路段的地理信息，將浮動車位置關聯到路網上。

研究表明，該匹配算法具有以下優缺點：

（1）匹配速度快。由于將電子地圖網格化，避免了將GPS數據坐標與地圖中所有節點坐標的一一進行計算，而是僅選取了比較小范圍的節點進行匹配。提高了運算、匹配的效率。

（2）匹配精度較高。由于在匹配方法上采取了多種方法進行聯合使用，針對不同位置的GPS數據點運用不同的匹配方法，保證了每個GPS數據點匹配的準確性。特別是基于連續GPS點軌跡來判斷位置，使得匹配的結果更為準確。

重慶市政府在2011年開展“重慶市交通綜合信息平臺”建設，信息平臺對重慶城區的干路網交通信息進行采集與匯聚。文章的研究依托交通信息平臺的基礎數據，研究成果應用于重慶市主城區路網運行情況的評估與監控，經過實測對比，驗證了該算法的良好精度和適用性。

參考文獻

[1]張其善，吳金培，楊康凱.智能車輛定位導航系統及應用[M].北京：科學出版社，2002.

[2]肖鋒.面向道路交通狀態監測的GPS與GIS數據預處理關鍵技術研究[D].重慶大學碩士畢業論文，2008.

[3]重慶市交通綜合信息平臺試點工程技術報告[R].2012.

[4]孫棣華，等.基于預處理的城市路網拓撲結構構建算法[J].計算機工程與應用，2008（08）.

[5]車莉娜.車輛導航定位中的關鍵技術研究[D].遼寧工程技術大學碩士論文，2008.

[6]Weiliang ZENG， Zhaocheng HE and Xiwei SHE. Data Repair Method for Real Time Urban Link Speed Estimation，ASCE2011.

[7]王華.GIS城市道路最短路徑算法研究[J].測繪科學，2010.

[8]章威，等.基于大規模浮動車數據的地圖匹配算法[J].交通運輸系統工程與信息，2007（4）.

[9]程志華，劉小勇.基于GIS 的城市路網拓撲關系的自動建立及最短路徑分析[J].新疆農業大學學報，2007.

作者簡介：孫靜怡，女，昆明理工大學交通工程學院副教授。