一種基于格網劃分的浮動車數據自適應地圖匹配方法研究

陶 華 超，馬 林 兵，魏 慧 麗,周 群

(中山大學地理科學與規劃學院，廣東 廣州 510275)

?

一種基于格網劃分的浮動車數據自適應地圖匹配方法研究

陶 華 超，馬 林 兵*，魏 慧 麗,周 群

(中山大學地理科學與規劃學院，廣東 廣州 510275)

利用單一的匹配算法對區域內的浮動車數據進行地圖匹配，會出現浮動車點匹配到鄰近路段上的跳躍現象。該文將區域劃分格網，遍歷待匹配點所在格網及其8鄰域格網，篩選出候選路段、結點集合；根據候選路段、結點數量特征，自主選擇合適的算法，計算幾何距離和匹配度指標以評價匹配結果，確保匹配準確性。通過廣州的部分區域數據進行算法驗證表明：基于合適步長的格網劃分能夠提高匹配效率；與單一的最近點匹配算法相比，自適應綜合匹配算法能夠較好地避免“點跳躍”，提高匹配準確度。

浮動車數據；地圖匹配；自適應；格網；匹配度

0 引言

浮動車數據(Floating Car Data ,FCD)作為一種新型的動態實時交通信息，能夠承載車輛行駛過程中的瞬時速度、瞬時方位角及位置等信息。通過對這些信息的實時獲取、分析，可實現對道路交通狀態的實時評價，并預測未來一段時間內的交通運行狀態。實際過程中由于浮動車定位精度的限制(一般為GPS單點定位)及數據采樣的非連續性，會產生數據漂移現象，為了獲取準確有效的道路交通信息，需利用地圖匹配技術，將FCD定位到相對正確的道路位置上；因為只有判斷出車輛在哪條道路上行駛，才能將FCD轉化為道路的交通狀態[1]。因此，地圖匹配技術的優劣直接影響FCD的處理效果。

從1989年至今，至少出現了35種不同的地圖匹配算法[2]，其中較為經典的有：幾何分析算法[3]、拓撲分析算法[4,5]、基于概率理論[6,7]的算法及基于統計學理論[8]的改進算法等。但是實際區域內路網分布或密集或稀疏，在具體的浮動車數據匹配過程中，如果匹配算法過于單一，由于不同區域特征的差異性，會導致匹配結果在鄰近路段上出現跳躍現象，如圖1所示:點3匹配后落到Road2上，與其他點的匹配結果對比，存在明顯 “點跳躍”現象。

本文結合待匹配FCD點的候選路段數量特征，將待匹配FCD所在的區域劃分為路網密集區域、路網交叉路口、路網稀疏區域3種類型，并改進Yang等[9]提出的比值法、結點法和最短路徑法3種算法，自適應地針對不同類型區域內的待匹配FCD點采用更合理的算法進行地圖匹配。與文獻[9]中依賴幾何距離量算實現匹配不同的是，本文自適應地圖匹配方法在具體實現過程中引入匹配度(方向相似性)，從幾何距離和方向相似性兩方面共同得出匹配結果，有效地提高了數據匹配結果的準確性。同時，本文利用格網劃分法將搜索范圍限定在待匹配FCD點所在格網及其8鄰域格網內，改善了候選路段與候選結點的搜索效率，提高了匹配效率。

圖1 匹配點跳躍

Fig.1 Jump of the matching points

1 自適應綜合匹配算法

1.1 算法思想

本文在綜合分析不同區域匹配特征的基礎上，結合待匹配FCD點的候選路段數量特征，設計了一種自適應綜合匹配算法，有效避免 “點跳躍”現象，達到區域內全面協調匹配的效果。

首先將待匹配FCD所在的區域劃分為3種類型：1)路網密集區域:區域中待匹配FCD點存在多個候選路段，選擇比值法能夠快速有效地篩選出匹配路段;2)路網交叉路口:區域中比值法往往匹配不正確，而結點法能夠通過比較待匹配FCD點與候選結點之間的距離及結點匹配度實現快速定位匹配結點；3)路網稀疏區域:對此類區域中待匹配點和以上兩個區域中未能匹配的FCD點，在確定其前后都存在準確的匹配點后，運用最短路徑法并結合司機出行規律及待匹配點的前后位置能夠準確定位。

為了提高匹配效率，本文對區域進行格網劃分，將搜索候選路段及候選結點的范圍縮小為待匹配FCD點所在格網及其8鄰域網格。根據研究區域的范圍特征和定位精度即誤差半徑，將整個圖幅按照合適的步長劃分為M×N個單元格，通過搜索相應格網獲得候選路段與結點的集合。生成的格網其覆蓋范圍要大小適中，確保每個格網內所包含的路段密度適宜。

為了提高匹配準確性，本文引入匹配度概念以確保FCD點與匹配道路保持最大的方向相似性。匹配度是衡量浮動車點匹配程度的一個指標，是待匹配點的瞬時方位角與待匹配點和匹配路段中鄰近結點或匹配結點的方位角差值的絕對值。匹配度的計算分兩種情況：1)如果是將FCD點匹配到某一路段的最近距離點，匹配度就等于待匹配點的瞬時方位角與待匹配點和匹配路段中最近距離點鄰近結點的方位角差值的絕對值；2)如果是將FCD點匹配到某一路段的結點，匹配度則為該匹配點的方位角與所匹配的結點方位角差值的絕對值。其中，匹配度值越小，表明匹配度越高，反之，匹配度越低。對于匹配度計算過程中路段結點方位角的確定，可以通過路網處理預先計算出來：首先按照道路走向，將路段上的結點排序，然后根據下式計算：

(1)

(2)

(3)

式(1)中，Startpoint、Endpoint為路段中排序前后相鄰的結點。對于雙向路段，結點的方位角也應有兩個，而對于交叉口處結點的方位角，一般具有多個，所以關于相反方向結點方位角的表示，可以根據第一個方向排序計算的Direction結果進行式(2)中的處理，獲得相反方向的Rdirection，如式(3)。

1.2 算法實現

自適應綜合匹配算法是針對不同區域內FCD點綜合運用比值法、結點法、最短路徑法完成匹配。其中，比值法是將待匹配FCD點到候選路段集合中次近路段的距離和其到最近路段距離的比值作為一個判斷指標，實際匹配過程中，如果計算得到的指標值大于指定閾值，同時該情況下計算得到的匹配度較高，待匹配FCD點就匹配到距其最近路段的最近點上，否則對該匹配點進行標記；結點法是通過計算待匹配FCD點與候選結點之間的距離及匹配度，綜合比較后將其匹配到匹配度高且距離較近F的結點；最短路徑法是建立在假定浮動車行駛過程中行駛者總是選擇行程起止點之間最短的道路作為優先行駛路線的基礎上，依據路網拓撲關系和歷史數據，從候選路段中選擇組成最短路徑的路段，將待匹配點匹配到匹配度較高的最短路段的最近距離點。

本文方法實現主要包括路網數據處理、格網劃分、自適應算法選擇，具體實現流程如圖2所示。首先對匹配路網進行拓撲構建及錯誤檢查，確保路網的連通性和方向性[10]；路網結點的方位角計算可在該階段根據處理后路段的走向，利用方位角計算公式進行。然后對區域進行格網劃分，根據區域范圍特征按照一定步長生成格網，并將初始FCD點、路段結點、路段與網格進行關聯，通過遍歷待匹配FCD點所在格網及其8鄰域格網篩選出候選路段及候選結點集合。最后根據候選路段和結點的特征，分3種情況實現算法選擇：對于候選路段大于等于兩條的FCD點(路網密集區域)進行比值法匹配，利用匹配度進行匹配效果控制,將FCD點匹配到最近路段的最近點；對于候選路段僅有一條或未能滿足比值法匹配的FCD點(通常分布于交叉口附近)，利用結點法匹配，當匹配度滿足要求時將其匹配到路段結點位置；對于剩余未有效匹配的FCD點(一般為路網稀疏區域)，比值法和結點法的應用保證了前后FCD點的準確匹配，此時利用最短路徑法可準確將其匹配到最短路徑的最近距離點。

圖2 本文方法技術流程

Fig.2 Flow chart of algorithm of auto-adaptive map matching for floating car data

2 算法驗證

2.1 數據準備

本文采用廣州市越秀區與荔灣區內5輛出租車于2009年4月30日一天內采集的FCD點，其中FCD所記錄的屬性字段格式如表1所示。通過對FCD點進行預處理(剔除采集設備無效時獲取的FCD點)后，篩選出2 147個FCD點用于對自適應綜合匹配算法進行驗證，檢驗過程中所使用的匹配道路網為越秀區與荔灣區電子地圖，圖3即為研究范圍內的道路網及初始FCD點的分布。

表1 FCD屬性字段格式

Table 1 Formats of FCD attribute field

字段數據格式實例描述LICENSEVARCHAR2(20)粵AO77U5車牌號GPS＿TIMEDATE2009-05-0117：52：26信號時間LONGITUDECHAR(10)113．26657經度LATITUDECHAR(9)23．19069緯度SPEEDCHAR(3)56速度DIRCHAR(3)170角度(方位角)EFFCHAR(1)1有效標識(1代表有效，0代表無效)STATCHAR(1)54空車，5重車

2.2 結果評價

算法實現采用C#語言編程，在3.07 GHz CPU、4 G內存的臺式機上運行，2 147個FCD點匹配耗時約140 s，其中單點的平均匹配時間為65 ms。對比目前運行的大多數浮動車地圖匹配算法，單點匹配時間在幾毫秒至幾十毫秒之間[1]，所以自適應綜合匹配算法能夠滿足正常要求。進一步研究發現，格網步長的選擇對匹配效率有較大影響；針對文中算法驗證的區域(區域外接矩形為70 000 m×50 000 m，浮動車GPS設備定位誤差與電子地圖的精度誤差都不超過20 m)，分別采用100 m、200 m、300 m、400 m、500 m、600 m、700 m的步長進行格網劃分，計算得出對2 000多個FCD點進行匹配的時間變化如圖4：匹配時間與格網步長呈現出“微笑曲線”。其中200～500 m的格網步長區間內地圖匹配效率較高，低于或高于該區間的匹配效率有所降低，本文在驗證算法有效性時以300 m作為步長，以提高匹配效率。

Fig.3 Layout of the road network and initial FCD

圖4 格網步長對匹配效率的影響

Fig.4 Impact on matching efficiency of grid step

圖5 自適應算法與最近點算法匹配結果對比

Fig.5 Contrast of auto-adaptive algorithm and closest point algorithm

對于FCD匹配結果的準確性，對比最近點算法(將點匹配到其最近距離路段的最近點處的一種算法)，其中車牌號“粵A04Q35”的3個FCD點匹配結果如圖5所示：初始FCD點102、103、104經過自適應綜合匹配算法(以下簡稱自適應算法)匹配相應地落在長堤大馬路的A、B、C點處，對照屬性表2，點104是利用自適應算法中的結點法實現匹配，點103和102是利用比值法實現匹配；而最近點算法的匹配結果顯示浮動車點102落在長堤大馬路的點D處，另外兩點103和104則落在另外一條道路的E、F點處，具體屬性信息如表3所示。通過查看初始數據的屬性(表4)，3個FCD點時間間隔約為20 s，并且點102、103、104按照該時間間隔為有序FCD點，顯然，自適應算法的匹配結果符合實際情況，而最近點算法匹配結果出現“點跳躍”。因此得出：在道路密集與路網交叉口區域，自適應算法的匹配結果較為準確，能夠有效避免 “點跳躍”現象。

表2 自適應算法匹配后FCD屬性數據

Table 2 Attribute data of FCD after matching with the auto-adaptive algorithm

IDLICENSEGPS＿TIMELONGITUDELATITUDESPEEDDIRSTATROADNAMEFLAG102粵A04Q3509：49：40113．25714223．11473482464長堤大馬路1103粵A04Q3509：50：01113．25670323．11461803124長堤大馬路1104粵A04Q3509：50：21113．25667823．114611133244一般市政道路2

注：“ROADNAME”屬性表示FCD的匹配路段名稱，“FLAG”屬性表示匹配方法，其中1表示比值法，2表示結點法，3表示最短路徑法。

表3 最近點算法匹配后FCD屬性數據

Table 3 Attribute data of FCD after matching with the closest point algorithm

IDLICENSEGPS＿TIMELONGITUDELATITUDESPEEDDIRSTATROADNAMEFLAG102粵A04Q3509：49：40113．25714223．11473482464長堤大馬路4103粵A04Q3509：50：01113．25670323．11455603124一般市政道路4104粵A04Q3509：50：21113．25668423．114598133244一般市政道路4

注：“FLAG”屬性表示匹配方法，其中4表示最近點法。

表4 初始(匹配前)FCD屬性數據

Table 4 Attribute data of initial (before matching) FCD

IDLICENSEGPS＿TIMELONGITUDELATITUDESPEEDDIRSTAT102粵A04Q3509：49：40113．25715023．11471082464103粵A04Q3509：50：01113．25672623．11455603124104粵A04Q3509：50：21113．25669023．114600133244

3 結語

本文在綜合分析不同區域匹配特征的基礎上，結合待匹配FCD點的候選路段數量特征，設計了一種基于格網劃分的FCD自適應地圖匹配方法。經過算法驗證，利用格網劃分進行候選路段和結點的初步篩選，在控制檢索范圍有效性上具有顯著的優越性，同時合適步長的格網劃分能夠有效提高匹配效率；對比單一匹配算法(最近點算法)的匹配結果，本文提出的自適應綜合匹配算法能夠有效避免“點跳躍”，保證匹配結果的準確性。

由于文中采用的最短路徑法是在一定的假設條件下執行的，最短路徑的構建過程是以歐氏距離為指標，而實際出行過程中存在眾多的不確定性，如司機可能會根據實際路況選擇行程時間或行駛距離較為適宜的路線，那么，根據理論獲得的最短路徑可能并不符合司機的最短路徑要求，就會產生匹配錯誤。因此，最短路徑法需要盡可能模擬真實路況，綜合差異因素尋找“出租車司機的最短路徑”，這樣最短路徑法的匹配結果才能準確，本文算法的準確性和自適應性才更有保證，而這將是后續研究的重點。

[1] 王美玲,程林.浮動車地圖匹配算法研究[J].測繪學報,2012,41(1):133-138.

[2] QUDDUS M C,OCHIENG W Y,NOLAND R B.Current map-matching algorithms for transport applications:State-of-the art and future research directions[J].Transportation Research Part C:Emerging Technologies,2007,15(5):312-328.

[3] 陸文昌,張迎,陳龍,等.基于計算幾何的地圖匹配算法研究[J].機械設計與制造,2012,10(1):43-45.

[4] 陳波,王茂林,王宏,等.一種基于網絡拓撲關系的地圖匹配算法[J].測繪科學技術學報,2006,23(5):331-334.

[5] 屈宏斌.基于網絡拓撲關系的綜合地圖匹配算法[D].蘭州:蘭州大學,2006.

[6] 蘇惠敏,周鵬.基于 D-S 證據理論的 GPS/MM 組合系統車輛定位算法[J].北京航空航天大學學報,2001,27(2):157-162.

[7] 楊易,谷正氣,胡林,等.基于概率決策的車輛導航系統地圖匹配算法[J].汽車工程,2006,28(10):897-901.

[8] WHITE C E,BERNSTEIN D,KORNHOUSER A L.Some map matching algorithms for personal navigation assistants[J].Transportation Research Part C:Emerging Technologies,2000,8(1):91-108.

[9] YANG J,KANG S,CHON K.The map matching algorithm of GPS data with relatively long polling time intervals[J].Journal of the Eastern Asia Society for Transportation Studies,2005,6:2561-2573.

[10] 朱麗云,郭繼孚,溫慧敏,等.一種適用于復雜城市路網的浮動車實時地圖匹配技術[J].交通與計算機,2008,25(6):81-84.

Study on an Algorithm of Auto-Adaptive Map Matching for Floating Car Data Based on Grid Division

TAO Hua-chao,MA Lin-bing,WEI Hui-li,ZHOU Qun

(SchoolofGeographyandPlanning，SunYat-SenUniversity,Guangzhou510275,China)

A new method is proposed in this paper that is an auto-adaptive approach to deal with FCD to match the map based on grid.It traverses the grids including the prepared-matching point and its eight neighboring grids after the computational domain is divided into suitableM×Ngrids,and then filters out candidate sections or nodes collection.According to the quantitative characteristics of candidate sections or nodes,it is auto enough to choose the appropriate algorithm to calculate.To ensure the matching accuracy,the geometric distance and matching degree are introduced to evaluate the matching result during the implementation process.The experiment indicates that the matching efficiency will be affected by the step length of grid.And combined with matching degree,the auto-adaptive matching algorithm is better to avoid "jumps" and can increase matching accuracy comparing with the closest point matching algorithm.Discussions of the benefits and shortcomings associated with this method are provided,along with suggestion for future research.

Floating Car Data(FCD);map matching;auto-adaptive;grid;matching degree

2014-11-05；

2015-01-28

“十二五”國家科技支撐項目(37000-41070400)

陶華超(1990-)，男，碩士研究生，從事GIS理論與方法、時空數據庫研究。*通訊作者 E-mail:malb@mail.sysu.edu.cn

10.3969/j.issn.1672-0504.2015.03.005

P208；U12

A

1672-0504(2015)03-0022-04