基于四級網格劃分的待匹配路段初篩方法研究

吳 偉，吳塹虹，鄧吉秋

(中南大學地球科學與信息物理學院，長沙 410083)

基于四級網格劃分的待匹配路段初篩方法研究

吳 偉，吳塹虹，鄧吉秋

(中南大學地球科學與信息物理學院，長沙 410083)

在地圖匹配過程中，待匹配路段初篩過程是影響其時間效率的關鍵。鑒于現有的路段初篩方法在最大檢索范圍的控制上仍有進一步縮減的空間，提出了一種四級交錯式網格篩選方法。通過對深圳市GPS定位數據的檢索實驗表明:該方法可有效縮減候選路段的篩選范圍，并在保證篩選范圍的穩定性上優于現有的方法;通過有效控制候選路段的檢索范圍，進一步減少了檢索時間。該方法在車載導航和大規模GPS數據處理等領域具有很大的應用價值。

GPS;地圖匹配;待匹配路段初篩;網格劃分

0 引言

在GPS數據應用領域，地圖匹配作為核心處理環節［1］已有了廣泛研究，其目的在于從路網中選擇出GPS點所處的最有可能路段，然后計算出GPS點在該道路上的精確位置［2］。地圖匹配算法一般包括GPS數據校驗、匹配道路初篩、特定算法求解以及定位點求取［3］4個主要環節。其中，匹配道路初篩是指以GPS點為中心，在給定誤差范圍內獲取落在該范圍內的道路集合。現有的初篩方法主要有直接計算法、移動窗口法［4］、交錯式移動窗口法［5］和多級網絡劃分的匹配道路初篩法［3］等等。直接計算法是指將整個路網作為候選道路，該方法效率較低，極少被使用;移動窗口法采用平面式網格劃分結構，將包括待定位點所在網格在內的9個相鄰單元格作為檢索范圍，其最大檢索范圍為9個單元格;交錯式移動窗口法在平面式網格之上新增一級網格，并使檢索范圍限定在1個或4個單元格之內，該方法將最大檢索范圍縮小到4個單元格;多級網絡劃分的匹配道路篩選方法采用與平面式網格類似的劃分結構，能將檢索范圍限定在1，2或4個單元格內。以上方法都在不同程度上縮減了檢索范圍，但不能保證檢索范圍的穩定性。為此，本文提出了四級網格劃分的待匹配路段初篩選方法。該方法將檢索范圍始終限定在一個單元格內，保證了檢索范圍的穩定性。

1 方法設計

1.1 網格劃分與數據組織

首先，根據圖幅范圍和定位精度誤差半徑R將整個圖幅分為M×N個、邊長L=K×R的單元格(K，M，N為≥2的整數)。為精確描述待定位點在一級單元格內的相對位置，對每個單元格進行4×4細分，形成16個邏輯子網格;依次編號后，其中［6，7，10，11］號子網格構成單元格的核心區。然后，以任意相鄰4個單元格的交點為中心，建立(M－1)×(N－1)個單元格，完成第二次劃分;第三次劃分是在一級網格中以左右相鄰單元格的公共邊的中點為中心建立N×(M－1)個單元格。最后，以一級網格上下相鄰單元格公共邊的中點為中心，建立(N－1)×M個單元格，構成第四級網格。

各級網格中的單元格大小相同，且都采用統一的編號規則:即以左下角開始，從左向右，從下往上依次編號。圖1中給出了四級網格劃分及編號示意圖。

圖1 四級網格劃分方法Fig.1 Four－level grid division method

網格劃分完畢后，要建立道路和各級單元格之間的索引關系，可用圖2所示的關系模型，將索引數據保存在數據庫中。

圖2 網格與道路索引關系模型Fig.2 Index model between grids and roads

1.2 網格篩選算法

按上述方法建好網格與道路索引關系后，使用本文提出的待選道路范圍篩選算法建立待定位點坐標與其所在網絡級別及編號的映射關系。

1.2.1 理論依據

Taylor［6］認為，單頻 GPS 接收機定位通常以距原始定位點100 m內的道路為計算路段，車輛位于這些路段的置信度為95%。所謂置信度［7］，是指特定個體對待特定命題真實性相信的程度。本文基于該原理，提出道路初篩中待定位點所在網格的置信度計算方法。即:以待定位點為中心，用定位精度R為半徑畫圓，以該圓與待定位點所在網格做交集，以所得交集的面積和該圓的面積比作為該網格置信度。其公式為

式中:p為網格置信度;S為以待定位點為中心、以定位精度R為半徑所得的圓;T為待定位點所在網格;area為面積計算函數。由式(1)可知，p的取值范圍為［0～1］。

圖3(網格T的邊長L=4R)給出了3種不同情況下網格置信度的示意圖。

圖3 網格置信度示意圖Fig.3 Examples of grid confidence level

如圖3所示，當點落在網格的核心區內，網格的置信度為最高值1(圖3(a));當點落在網格的邊界上時，網格置信度降至0.5(圖3(b));當點落在網格的角點上時，網格置信度降至0.25(圖3(c))。當p＜0.25時，待定位點已經不在網格范圍內。可見，待定位點離網格核心區越近，p的取值越接近于1，該網格作為候選道路的檢索范圍的可信度就越高。基于這種思想，本文設計了基于四級網格劃分的候選道路范圍篩選算法。

1.2.2 計算方法

設圖幅左下角坐標為(Left，Bottom)，右上角坐標為(Right，Top)，一級網格數量為M×N，單元格大小為(△x，△y)，待定位點 q的坐標為(x，y)。則由

可計算出點q在一級網格中的行號n、列號m;由

可計算出點q所在的子網格編號。式中nsub，msub分別為點q在一級網格單元格內的子行號和子列號，可分別由

計算出。式中［］為向上取整符號。已知m，n，sub，便可用

求得點q的候選道路范圍。式中:Gi為第i級網絡單元格編號，i=1，2，3，4;F為篩選函數。根據 m，n，sub的不同取值范圍，F采用2類略有差異的求解算法:當2≤n≤N－1且2≤m≤M－1時的“非邊界區域求解算法”和當m，n不在以上取值范圍內時的“邊界情況下的求解算法”。

1.2.2.1 非邊界區域求解算法

非邊界情況下的求解算法可簡述為:如果點q所在子網格sub為Gi的核心區，則將點q的候選道路檢索范圍限定在 Gi內。當2≤n≤N－1且2≤m≤M－1時，篩選函數F的求解偽算法程序為

IF sub=［6，7，10，11］THEN G1=(n －1)M+m;

IF(2≤n≤N －1)＆＆(2≤m≤M －1)THEN{

IF sub=1 THEN G2=(n－2)(M－1)+(m－1);

ELSE IF sub=4 THEN G2=(n－2)(M－1)+m;

ELSE IF sub=13 THEN G2=(n－1)(M－1)+(m－1);

ELSE IF sub=16 THEN G2=(n－1)(M－1)+m;

ELSE IF sub=［5，9］THEN G3=(n －1)(M－1)+(m－1);

ELSE IF sub=［8，12］THEN G3=(n －1)(M－1)+m;

ELSE IF sub=［2，3］THEN G4=(n －2)M+m;

ELSE IF sub=［14，15］THEN G4=(n －1)M+m;}

筆者以圖4中的3×3四級網格為例，說明求解過程。

圖4 四級網格樣例圖Fig.4 Example of four－level grid

圖4(a)以“網格級別－單元格編號”的方式(如1－5)標出各級網格單元格的編號，其中編號為1－5單元格放大后如圖4(b)所示。設點q所在子網格編號為sub，則有

①sub=6，7，10，11，q∈1 －5;

②sub=1，q∈2－1; ③sub=4，q∈2－2;

④sub=13，q∈2－3; ⑤sub=16，q∈2－4;

⑥sub=5，9，q∈3 －3; ⑦sub=8，12，q∈3 －4;

⑧sub=2，3，q∈4 －2; ⑨sub=14，15，q∈4 －5。

由圖4(b)可知，非邊界單元格的16個子網格均為各級網格單元格的核心區，因此在非邊界情況下，本方法可保證檢索范圍的置信度最高且將檢索范圍限定在1個單元格內。

1.2.2.2 邊界情況下的求解算法

當n=1或N，m=1或M時，點q落在一級網格的邊界上，此時的求解算法可簡述為:優先按核心區判定檢索范圍，如果子網格sub不屬于任何一級網格單元格的核心區，則選擇置信度最大的單元格作為檢索范圍。

本文以圖4(a)中的1－1單元格為例，說明在這種特殊情況下的求解原理。將單元格1－1和1－2放大后如圖5所示。

圖5 邊界網格示意圖Fig.5 Example of boundary grids

當點q落在1－1單元格內時，設其所在子網格編號為 sub，則有

①sub=1，2，3，5，9，6，7，10，11，q∈1 －1;

②sub=16，q∈2 －1;

③sub=4，8，12，q∈3 －1;

④sub=13，14，15，q∈4 －1。

第 6，7，10，11，8，12，14，15，16 號子網格分別是各級網格單元格的核心區，可用本節算法求得對應的網格編號。而對于 1，2，3，4，5，9，13 號子網格而言，它們不屬于任何一級網格單元格的核心區，因此要根據網格置信度最大化原則判定檢索范圍。其中1，2，3，5，9號子網格只在1－1的單元格的范圍內，如果點q落在它們當中，只有1－1號單元格作為候選檢索范圍。而4，13號子網格例外，它們位于2個單元格的共享范圍內。以4號單元格為例，其同時在1－1和3－1的范圍內，當點q落在其內時，就有2個單元格作為候選檢索范圍，但因3－1的置信度大于1－1的置信度，故將檢索范圍限定在3－1內。同理，當點q落在13號子網格內時，有1－1和4－1作為候選檢索范圍，但4－1的置信度大于1－1，因此檢索范圍限定在4－1內。根據這種判定原則，結合4個頂角和4條邊的各異情況，可編制出相應的篩選算法解決非核心區情況下的范圍判定。

2 實驗與分析

筆者在路網數據量為60932條的深圳市地圖內，按400 m×400 m建立四級網格，用Postgresql數據庫保存網格、道路及兩者間的索引關系。用5輛出租車(尾號分別為 G10，G23，G27，G31，G38)，在2009年08月01日00:00～24:00時段內的20000條GPS定位數據，在2 G內存，主頻為2 GHz雙核處理器硬件平臺上，分別用移動式窗口法、交錯式移動窗口法、多級網絡劃分法和四級網絡劃分法，按5000，10000，20000條的 GPS數據量分3組進行檢索實驗。其中，每種方法在每一組內做6次檢索，取6次檢索時間的平均值為該方法在該組內的檢索時間，經實驗后得到各種方法的檢索時間效率對比，其結果如圖6所示。

圖6 各方法效率對比Fig.6 Efficiency comparison between proposed method and tradition ways

從圖6可以看出，在同等GPS數據量條件下，四級網格篩選技術所花的檢索時間均比其他3種方法所花時間少，且平均檢索時間約為現有最優方法所花時間的1/2。在不同GPS數據規模下，因數據量的增加導致各種方法的檢索時間都有所上升，但四級網格篩選技術的檢索時間依然最少，與現有最優方法的檢索時間比仍保持為1/2。在以單元格為單位，決定待匹配路段檢索范圍時的不同選擇策略是導致4種方法在檢索時間上存在差異的根本原因。由于這種差異，使得在相同路網集上進行單個GPS點的待匹配道路初篩時，四級網格技術取得的路段數據量最小，進而為接下來的匹配過程從減少路段數據量角度輔助提升單個點的匹配校正時間效率。綜合對比不同初篩方法，以四級網格劃分的待匹配路段初篩方法在縮減最大檢索范圍和控制檢索范圍的穩定性上占有絕對優勢。

3 結論

本文的理論分析與實驗結果表明，基于四級網絡劃分策略的待匹配路段篩選方法在減少篩選范圍的能力和控制檢索范圍的穩定性上具有顯著的優越性。因該方法的實現不涉及到復雜的數學計算，并且可大大地縮短初選道路的檢索時間，因此可廣泛應用于各類匹配應用中。

［1］薛 明，呂衛鋒，諸彤宇.浮動車信息處理系統關鍵技術的研究［J］.微計算機信息，2006，22(11 －1):244 －246.Xue M，Lv W F，Zhu T Y.Study on the Key Technology of Floating Car Information Processing System［J］.Microcomputer Information，2006，22(11 －1):244 －246(in Chinese with English Abstract).

［2］唐進君，曹 凱.基于多準則融合的信任理論地圖匹配算法［J］.測繪科學，2009，34(5):14 －15.Tang J J，Cao K.A Map －matching algorithm Based on Multi－criteria Fusion Using Belief Theory［J］.Science of Surveying and Mapping，2009，34(5):14 －15(in Chinese with English Abstract).

［3］馮金巧，孫占全，劉 威.基于多級網絡劃分的匹配道路初篩方法研究［J］.交通信息與安全，2010，28(4):5 －8.Feng J Q，Sun Z Q，Liu W.Primary Screening Method of Matching Road Based on Multilevel Division of Road Network［J］.Journal of Transport Information and Safety，2010，28(4):5 － 8(in Chinese with English Abstract).

［4］蘇慧敏，周 鵬，陳 哲.基于DS證據理論的GPS/MM組合系統車輛定位算法［J］.北京航空航天大學學報，2001，27(2):157 －160.Su H M，Zhou P，Chen Z.Study of GPS/MM Integrated Navigation System for Vehicle Positioning Based on DS Evidence Reasoning［J］.Journal of Beijing University of Aeronautics and Astronautics，2001，27(2):157 －160(in Chinese with English Abstract).

［5］楊新勇，黃圣國.地圖匹配算法中的待配路段快速篩選方法［J］.華南理工大學學報:自然科學版，2004，32(2):62 －66.Yang X Y，Huang S G.Quick Road Choice Method in Map Matching Algorithms［J］.Journal of South China University of Technology:Natural Science Edition，2004，32(2):62 － 66(in Chinese with English Abstract).

［6］Taylor G，Blewitt G.Road Reduction Filtering Using GPS［C］//3th AGILE Conference on Geographic Information Science－helsinki.Finland:(s.n.)，2000:114 －119.

［7］趙國求.經典概率與量子概率［J］.武漢工程職業技術學院，2002，14(1):31 －32.Zhao G Q.Traditional Probability and Quantum Probability［J］.Journal of Wuhan Engineering Institute，2002，14(1):31 － 32(in Chinese with English Abstract).

Research on Primary Filtering Method for Pre－matching Road Sections Based on Four－level Grid Division

WU Wei，WU Qian －hong，DENG Ji－qiu
(School of Geosciences and Info－physics，Central South University，Changsha 410083，China)

The primary filtering of the pre－matching road sections in the map matching algorithm，in which GPS point finds the closest approximation road for driving，is the key factor of the time efficiency.There is a great deficiency of redundant searching range in the existing primary filtering methods.To reduce the searching range，this paper proposes a novel four－level interlaced grid filtering method，which can efficiently narrow the searching range.It is indicated that the method proposed in this paper is superior to the existing methods on the premise of guaranteeing the stability of the filtering range，as shown by experimental comparisons with many traditional methods based on GPS data.This method has high application values in many fields such as the vehicle navigations and large－scale GPS data processing because it can further reduce the searching time by controlling the searching range effectively.

GPS;map matching;primary filtering of pre－matching road sections;grid division

TP 79

A

1001－070X(2012)04－0026－04

2012－01－08;

2012－08－29

國家水體污染控制與治理科技重大專項課題(編號:2009ZX07212－001－06)。

10.6046/gtzyyg.2012.04.05

吳 偉(1987－)，男，碩士研究生，主要研究領域為并行計算和網絡地理信息系統。E－mail:xmzfighting@126.com。

(責任編輯:刁淑娟)