基于GPS車輛軌跡數(shù)據(jù)的地圖匹配算法研究

陳芳芳

（阿里巴巴集團 北京市 100102）

在我國，車輛的管理是一個很重要的問題，目前國內(nèi)很多城市都出現(xiàn)了停車難、車位貴等現(xiàn)象。由于人們出行越來越多導致交通壓力增大，交通擁堵問題也越來越突出，車輛管理的智能化成為人們關(guān)注和解決的熱點。基于GPS車輛軌跡數(shù)據(jù)技術(shù)能夠?qū)崿F(xiàn)對道路路段信息采集并進行實時更新與控制，通過衛(wèi)星定位系統(tǒng)獲取到最新路況情況和周邊環(huán)境狀況以及用戶需求變化等相關(guān)路況資料，利用地圖數(shù)據(jù)庫存儲在服務(wù)器中以便調(diào)用地理信息系統(tǒng)，提高運輸效率及準確性的同時也能節(jié)省人力資源成本、增強競爭力。由于這些原因，基于GPS車輛軌跡數(shù)據(jù)的路徑匹配算法在交通領(lǐng)域得到了廣泛研究和應用。

1 地圖匹配算法研究

1.1 地圖匹配的概念

車輛的軌跡匹配是基于地圖數(shù)據(jù)集進行路徑規(guī)劃，以滿足用戶需求，實現(xiàn)對路段、道路和時間點等信息在計算機中顯示，并根據(jù)實際情況選擇合適路線。定位技術(shù)結(jié)合地圖匹配算法，實現(xiàn)車輛的三維地形圖和交路GPS數(shù)據(jù)。該方法能夠有效地減少人工操作過程中存在著錯誤率高、計算量大等問題，同時還能避免算法在實際應用中路由過采樣點處的布設(shè)誤差以及由于天氣原因產(chǎn)生局部精度差值造成定位失敗，提高了系統(tǒng)運行速度并降低成本。

地圖匹配算法主要包含兩個重要的過程：一是要先定位到該物體當前正在形式的道路，并根據(jù)路線圖確定目的地，從而得到地圖匹配方測量點。二是將當前的定位點投影到道路上，計算出匹配方的位置。車輛軌跡數(shù)據(jù)是基于GPS實時導航系統(tǒng)而產(chǎn)生，該算法可以根據(jù)道路信息生成路線圖，并能獲取當前時間段內(nèi)的車流量、車道數(shù)和方向等基礎(chǔ)參數(shù)。

1.2 常用的地圖匹配算法

（1）直接投影法。直接投影方法的應用是基于在車輛運動方向上，通過計算車輪與軌道間距離，從而得到地面點坐標。該算法的基本思想是根據(jù)實際的車輛運動軌跡，在計算機上計算車輪與軌道間距離，從而得到地面點坐標，該算法采用的是輪軌測距和軌道數(shù)據(jù)匹配，可以在計算機上通過GPS軌跡數(shù)據(jù)計算出車輛運動速度和加速度，該算法的實現(xiàn)需要硬件、軟件以及數(shù)據(jù)庫。直接投影方法如圖1所示。

圖1：直接投影方法

圖1中P點可以看做為一個定位點，而道路A和道路B是離該定位點最近的兩條道路，該車輛軌跡上有一條起始點，且相鄰兩條道路之間距離較近，根據(jù)交通流分析的方法計算出兩條車道數(shù)和A、B路段間平均坐標。通過公式（1）可以分別計算道路的距離度量值：

式中ri表示點P到各條道路的隱射聚力，θi是物體行駛方向與道路之間的夾角，分別為距離和方向的權(quán)重系數(shù)。

（2）基于幾何關(guān)系的算法?；趲缀侮P(guān)系的路徑匹配算法是一種常見且實用性較高的車輛軌跡匹配方法，它把GPS導航和無人機航拍相結(jié)合，根據(jù)地理位置、周邊環(huán)境等信息對車輛位置進行定位。通常基于幾何關(guān)系的地圖匹配算法具體分為三種：點到點的匹配、點到線的匹配及線到線的匹配。

點到點的匹配，指的是將GPS定位點匹配到附近道路網(wǎng)絡(luò)中的節(jié)點或形狀點上，以一定的比例、位置計算出所匹配到點處的坐標，并按照某種規(guī)則進行組合，從而得到車輛軌跡。此算法匹配速度快，但計算量大，且在車輛運動軌跡數(shù)據(jù)中，該算法可以有效的處理大量道路數(shù)據(jù)。點到點匹配的具體數(shù)學計算模型如圖2所示。

圖2：點到點匹配

點到線的匹配是指車輛從起點到終點間的所有路段上的數(shù)據(jù)信息匹配，是基于GPS定位技術(shù)實現(xiàn)，其原理是通過GPS定位點做所有待匹配路段的投影距離，并將其與已匹配路段的實際距離進行對比，從而得出車輛在起點到終點間所有道路上運行軌跡信息。具體做法是當?shù)缆窞橹本€道路時，通過GPS地圖數(shù)據(jù)計算出車輛的坐標，再將其平分成不同路段，分別匹配到直線路和交叉口，再做垂線段。點到線的匹配的數(shù)學模型如圖3所示。

由圖3中可知，P點到直線AB的距離為的計算如公式（2）所示：

圖3：點到線的匹配

P點到直線AB的投影點C即為候選匹配點，k為直線AB的斜率，則C點的坐標計算如公式（3）所示：

線到線的匹配算法是交通領(lǐng)域中的一個重要內(nèi)容，也是解決數(shù)據(jù)匹配問題最常用且有效、最快速和最有效率途徑之一，在車輛運動控制和智能導航等方面得到了廣泛研究。該算法不僅利用了當前GPS定位數(shù)據(jù)，還利用了歷史軌跡數(shù)據(jù)，可以在地圖數(shù)據(jù)中添加導航信息，使車輛軌跡的匹配更加準確。與前面兩種算法相比，該算法是一種更先進的算法，具有很強的實時性，可以在地圖數(shù)據(jù)中添加導航信息。線到線的匹配算法的具體數(shù)學計算模型如圖4所示。

圖4：線到線的匹配

用積分來計算兩條曲線之間的距離，則曲線的平均距離計算如公式（4）所示：

（3）概率統(tǒng)計算法。概率統(tǒng)計算法是根據(jù)實測值或歷史測得的數(shù)據(jù)，對所有可能出現(xiàn)的情形，按一定規(guī)則進行統(tǒng)計運算分析。該算法的基本思想是依據(jù)GPS 接收到的定位數(shù)據(jù)設(shè)置一個誤差區(qū)域，根據(jù)實際數(shù)據(jù)和已知的車輛軌跡分析出兩者之間的關(guān)系，計算出相應誤差區(qū)域，再將得到結(jié)果與真實軌道差值進行比較以驗證匹配算法正確性。概率統(tǒng)計算法利用誤差橢圓確定了置信區(qū)域，然后從數(shù)字地圖數(shù)中提取候選路段，然后根據(jù)已提取的路段信息計算出車輛行駛方向、運行距離等行車狀態(tài)，最后將結(jié)果與真實軌道差值進行比較，得到匹配情況。按照統(tǒng)計理論，定位誤差橢圓的推導如公式（5）所示：

（4）模糊邏輯算法。模糊邏輯算法是利用計算機對輸入信息進行判斷，并根據(jù)相應的規(guī)則來處理輸出。它通過模擬人腦中多角度和空間經(jīng)驗而得出一個較為理想化結(jié)果，其優(yōu)點在于能夠在一定范圍內(nèi)實現(xiàn)最優(yōu)控制。該方法主要有兩種形式：一種情況是將所有信息按不同方式劃分成許多集合，然后再進行劃分，這種方法在計算過程中能夠?qū)崿F(xiàn)快速準確的運算，并且能將時間分割為若干個小區(qū)間。另一種則為根據(jù)集合確定出一個規(guī)則函數(shù)來實現(xiàn)模糊邏輯推理，通過GPS車輛軌跡數(shù)據(jù)的特點來確定出離散點在同一地點下所對應的位置。

1.3 改進的基于權(quán)重的地圖匹配算法

基于權(quán)重的地圖匹配算法是在車輛軌跡數(shù)據(jù)中引入了一些權(quán)重，這些指標和層次分析法可以有效地對采集到的交通信息進行處理。它能夠?qū)⒏鞣N不同類型道路之間存在著一定差異性，但是由于其本身具有主觀因素導致計算過程復雜、運算量大等問題限制了其應用范圍與實際價值不相符甚至出現(xiàn)偏差，同時也無法準確獲得所需匹配路段的具體位置以及車輛在整個路網(wǎng)中所處地理位置，因此不能很好地利用這些數(shù)據(jù)對路徑優(yōu)化算法進行設(shè)計和實現(xiàn)。

基于權(quán)重的地圖匹配算法是局部修正算法，它的計算量比較大，但在實際應用中，由于車輛運動軌跡具有不確定性，所以需要進行大量數(shù)據(jù)處理。本文進行GPS車輛軌跡研究時，主要是將基于權(quán)重的地圖匹配算法和道路拓撲結(jié)構(gòu)相結(jié)合，通過GPS車輛軌跡數(shù)據(jù)進行匹配，同時，將車輛軌跡數(shù)據(jù)和道路信息相結(jié)合，從而獲得更加精確的匹配結(jié)果。

2 影響地圖匹配質(zhì)量的因素

2.1 GPS定位誤差

在車輛路徑規(guī)劃中，定位誤差是不可避免的，GPS數(shù)據(jù)采集到的是行駛距離、車道位置信息以及方向偏差等多種因素引起的車跡地別的偏移而產(chǎn)生，從而影響到車輛行駛的準確性。由于這些信息存在于不同載體上且具有不確定性和非連續(xù)性特征，因此對衛(wèi)星導航系統(tǒng)造成了一定程度上損失?；谲囕v軌跡匹配算法可以實現(xiàn)道路資源合理分配并提高道路運輸效率：通過使用GIS地圖定位軟件，可有效避免交通擁堵情況，GPS軌跡數(shù)據(jù)中蘊含著大量的車輛位置和行程信息，可以在地圖上顯示停車位、路徑等相關(guān)參數(shù)，利用GIS地理信息系統(tǒng)（如衛(wèi)星定位系統(tǒng)）獲取道路資源時，可實現(xiàn)對地面交通流進行實時監(jiān)控。

GPS定位誤差包括內(nèi)部誤差和外部誤差。內(nèi)部誤差是指由衛(wèi)星接收引起的固定誤差，主要原因是衛(wèi)星運行速度太慢，并且在經(jīng)過若干年后，GPS車輛軌跡數(shù)據(jù)精度已經(jīng)很難滿足用戶的需求。外部誤差則有環(huán)境因素和天氣原因等方面引起，主要包括GPS系統(tǒng)自身存在的一些缺陷,例如氣象條件、地形地貌以及道路狀況等，這些都會對定位精度造成影響?；贕PS車輛軌跡數(shù)據(jù)的定位方法，通過對已有算法原理進行分析歸納，提出了利用多傳感器網(wǎng)絡(luò)相結(jié)合來提高車位計算精度、增強地圖匹配速度和滿足用戶需求等優(yōu)化方案。

2.2 電子地圖誤差

由于通過GPS軌跡數(shù)據(jù)中的車輛位置、速度、方向等信息來匹配到當前車主所處地點，并在這些內(nèi)容記錄下行駛時間，根據(jù)地圖上顯示出來的路線圖和對應路段進行坐標計算。因此在交通系統(tǒng)中占有重要地位，其性能優(yōu)劣直接影響到車輛運行速度、道路數(shù)據(jù)傳輸質(zhì)量和處理效率等?；贕PS軌跡數(shù)據(jù)采集與分析技術(shù)是一種新型地理信息系統(tǒng)，該數(shù)據(jù)庫采用了GIS地圖管理系統(tǒng)來管理平臺上所有存儲空間位置分布圖譜，并根據(jù)道路信息數(shù)據(jù)建立了基于地圖數(shù)據(jù)庫的車輛軌跡庫。電子地圖的精度誤差對地圖匹配效果的影響很小，但出現(xiàn)道路變更、道路情況復雜以及電子地圖精度較低的情況時，將會加大電子地圖的誤差，導致地圖匹配失效。

2.3 坐標變換誤差

坐標變換的精度是指計算出車輛在坐標系中點相對于車軸或線下兩點間軌跡角度。它可以消除由軌道誤差所引起的數(shù)據(jù)處理上出現(xiàn)錯誤。由于GPS定位系統(tǒng)采用的是車載天線，因此其坐標變化對車上車輛位置也有一定影響，因此需要在車輛軌跡匹配過程中對其坐標進行準確的調(diào)整以保證數(shù)據(jù)能夠滿足實際需求。

3 地圖匹配軟件的實現(xiàn)

3.1 開發(fā)工具及環(huán)境

車輛軌跡數(shù)據(jù)的匹配是一個過程,它需要根據(jù)實際情況進行選擇和分析。在開發(fā)工具上，主要采用Microsoft Visual Studio 2010開發(fā)平臺和MapInfo公司提供的MapX控件進行地圖匹配模塊的集成二次開發(fā)，利用MATLAB、Java語言和C++編程語言對車輛軌跡進行數(shù)據(jù)處理，同時結(jié)合數(shù)據(jù)庫技術(shù)，完成了基于GPS的車輛路徑軌跡匹配算法。其中硬件環(huán)境使用的是智能手機定位模塊和計算機硬件。

3.2 地圖匹配的總體設(shè)計與實現(xiàn)

地圖匹配的應用目的不同，對地圖匹配的實時性、效率等的要求不同，導致車輛軌跡匹配的方法也不同?；贕PS數(shù)據(jù)平臺，通過合理安排車道、車速等基本信息，根據(jù)道路情況確定路線并實現(xiàn)實時路況顯示，利用GPS軌跡信息進行車輛路徑匹配，可以大大提高路況數(shù)據(jù)的實時性，為司機提供一條準確、快速且易于操作控制和保護的道路。根據(jù)本文的應用需求，地圖匹配軟件的總體設(shè)計如圖5所示。

圖5：地圖匹配軟件的總體設(shè)計

4 實驗效果分析

本次實驗的數(shù)據(jù)來源為兩部分，一部分為校園實測數(shù)據(jù)，該數(shù)據(jù)是通過Android智能手機的GPS定位技術(shù)，通過數(shù)據(jù)的拼接與處理，生成位置軌跡，再使用GPS車輛運動控制軟件GPRS模塊獲取到導航信息。另一部分是基于匹配算法中基于對已有地圖資料進行調(diào)整后得到較為精確地車距、時間等參數(shù)。這些結(jié)果都能在一定程度上減少人為因素造成不必要損失和提高計算精度降低成本支出，另外該方法可以通過GPS衛(wèi)星定位系統(tǒng)實現(xiàn)高分辨率的道路數(shù)據(jù)，還可利用車輛軌跡數(shù)據(jù)庫提供的交通狀況實時分析數(shù)據(jù)支持來滿足用戶需求，通過車輛軌跡數(shù)據(jù)的匹配計算可以得到道路行程時間，還能在地圖上提供更加精確地導航路徑，滿足用戶對車距、速度等參數(shù)的要求。

通過實驗，對本文所提出的算法進行分析研究，圍繞準確性和實時性2個重要指標，來衡量本文算法的有效性。

4.1 準確性分析

為了驗證本文匹配算法的準確性，分別采用三組不同地方的GPS軌跡進行實驗，并獲取了車輛軌跡數(shù)據(jù)。通過不同的方法，將所獲取到的GPS軌跡與電子地圖進行匹配，結(jié)果對比如表1所示。

表1：基于權(quán)重的匹配算法

4.2 實時性分析

在實驗過程中，為了評價該算法的實時性，我們對車輛軌跡數(shù)據(jù)的獲取、處理和匹配過程進行了研究。通過分析得知,使用GPS導航定位模塊,基于地圖生成算法中最常用到的是曲線擬合。本次實驗通過多線程并行化方法優(yōu)化算法，實驗結(jié)果如表2所示。

表2：實驗結(jié)果

實驗結(jié)果表明:基于GPS的車輛軌跡數(shù)據(jù)匹配算法在實際應用中具有較好的效果,能夠滿足用戶對實時信息和路面狀況準確且及時地提供相應導航服務(wù)。同時,該方法還可以用于交通監(jiān)控領(lǐng)域，如交通擁堵的實時監(jiān)測、高速公路動態(tài)流量采集等方面。

5 總結(jié)

綜上所述，隨著GPS技術(shù)的不斷成熟，基于交通信息數(shù)據(jù)領(lǐng)域?qū)囕v軌跡智能化管理已經(jīng)成為現(xiàn)實，在我國國內(nèi)許多大城市和綜合實力強大、使用方便的公共停車場也越來越多，基于交通信息數(shù)據(jù)領(lǐng)域的GPS車輛軌跡智能化系統(tǒng)已經(jīng)在國內(nèi)被廣泛投入使用。本文基于GPS車輛軌跡數(shù)據(jù)采集與匹配算法研究，對基于個人GPS軌跡數(shù)據(jù)的地圖匹配算法進行了研究，提升位置服務(wù)應用的用戶體驗，實現(xiàn)交通信息實時匹配。根據(jù)車輛軌跡數(shù)據(jù)獲取和處理的基本原理，提出基于位置、距離等關(guān)鍵參數(shù)，利用GPS車輛運動學模型，結(jié)合GIS平臺進行車位分配算法研究。通過實驗結(jié)果表明：基于權(quán)重的地圖匹配算法具有較高的精確度與高效性，同時也能保證在城市道路擁堵情況下提高運輸效率并降低交通事故發(fā)生率，其計算速度快且可重復率低是它存在和發(fā)展所要求實現(xiàn)的目標之一。