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

關(guān)鍵詞：浮動車；GPS；地圖匹配；軌跡點

引言

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

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

1 GPS數(shù)據(jù)的地圖匹配原理

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

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

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

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

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

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

圖1 地圖匹配原理圖

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

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

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

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

2.1 網(wǎng)格匹配

Step1：計算GPS點所歸屬網(wǎng)格。

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

則認(rèn)為該GPS點在研究坐標(biāo)范圍之內(nèi)，轉(zhuǎn)到下一步計算。

Step2：搜尋所在網(wǎng)格匹配

根據(jù)該GPS點的坐標(biāo)信息，在網(wǎng)格列表中搜尋其所屬的網(wǎng)格。假設(shè)網(wǎng)格編號為G0，若

（x，y）∈{G0}

則判定該點位于G0網(wǎng)格內(nèi)。

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

2.2 節(jié)點匹配

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

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

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

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

計算GPS點與路段各校正點之間的夾角。取GPS數(shù)據(jù)的角度為？漬0，再與網(wǎng)格內(nèi)的GIS路段校正點的切線方向角度？漬r（取正北方向為0°）求差值?？傻贸鯣PS點與路段方向的夾角α。

Step2：匹配度計算

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

圖3 GPS點匹配

Step3：Confidence Point（CP點）判斷

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

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

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

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

Step4：延遲匹配

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

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

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

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

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

3 結(jié)束語

文章所使用的地圖匹配方法通過獲取GPS浮動車數(shù)據(jù)，利用GPS坐標(biāo)信息，通過比對電子地圖各條路段的地理信息，將浮動車位置關(guān)聯(lián)到路網(wǎng)上。

研究表明，該匹配算法具有以下優(yōu)缺點：

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

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

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

參考文獻

[1]張其善，吳金培，楊康凱.智能車輛定位導(dǎo)航系統(tǒng)及應(yīng)用[M].北京：科學(xué)出版社，2002.

[2]肖鋒.面向道路交通狀態(tài)監(jiān)測的GPS與GIS數(shù)據(jù)預(yù)處理關(guān)鍵技術(shù)研究[D].重慶大學(xué)碩士畢業(yè)論文，2008.

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

[4]孫棣華，等.基于預(yù)處理的城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)構(gòu)建算法[J].計算機工程與應(yīng)用，2008（08）.

[5]車?yán)蚰?車輛導(dǎo)航定位中的關(guān)鍵技術(shù)研究[D].遼寧工程技術(shù)大學(xué)碩士論文，2008.

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

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

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

[9]程志華，劉小勇.基于GIS 的城市路網(wǎng)拓?fù)潢P(guān)系的自動建立及最短路徑分析[J].新疆農(nóng)業(yè)大學(xué)學(xué)報，2007.

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