基于浮動(dòng)車GPS軌跡點(diǎn)數(shù)據(jù)的地圖匹配算法研究

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

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

引言

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

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

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

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

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

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

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

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

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

圖1 地圖匹配原理圖

地圖匹配原理一般可分成兩個(gè)過(guò)程來(lái)表達(dá)：即尋找GPS待匹配點(diǎn)最可能歸屬的道路，并將GPS浮動(dòng)點(diǎn)投影到這條它所歸屬的道路上面。

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

2 基于GPS軌跡點(diǎn)的浮動(dòng)車地圖匹配算法

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

2.1 網(wǎng)格匹配

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

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

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

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

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

（x，y）∈{G0}

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

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

2.2 節(jié)點(diǎn)匹配

Step1：計(jì)算GPS與路段的距離和方向差

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

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

得出GPS點(diǎn)與各校正點(diǎn)之間的距離d。

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

Step2：匹配度計(jì)算

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

圖3 GPS點(diǎn)匹配

Step3：Confidence Point（CP點(diǎn)）判斷

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

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

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

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

Step4：延遲匹配

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

圖5 非CP點(diǎn)延遲匹配示意圖

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

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

參考文獻(xiàn)

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

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

[3]重慶市交通綜合信息平臺(tái)試點(diǎn)工程技術(shù)報(bào)告[R].2012.

[4]孫棣華，等.基于預(yù)處理的城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)構(gòu)建算法[J].計(jì)算機(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].測(cè)繪科學(xué)，2010.

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

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

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