吳 偉，吳塹虹，鄧吉秋

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

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

吳 偉，吳塹虹，鄧吉秋

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

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

GPS;地圖匹配;待匹配路段初篩;網(wǎng)格劃分

0 引言

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

1 方法設(shè)計

1.1 網(wǎng)格劃分與數(shù)據(jù)組織

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

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

圖1 四級網(wǎng)格劃分方法Fig.1 Four－level grid division method

網(wǎng)格劃分完畢后，要建立道路和各級單元格之間的索引關(guān)系，可用圖2所示的關(guān)系模型，將索引數(shù)據(jù)保存在數(shù)據(jù)庫中。

圖2 網(wǎng)格與道路索引關(guān)系模型Fig.2 Index model between grids and roads

1.2 網(wǎng)格篩選算法

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

1.2.1 理論依據(jù)

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

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

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

圖3 網(wǎng)格置信度示意圖Fig.3 Examples of grid confidence level

如圖3所示，當(dāng)點落在網(wǎng)格的核心區(qū)內(nèi)，網(wǎng)格的置信度為最高值1(圖3(a));當(dāng)點落在網(wǎng)格的邊界上時，網(wǎng)格置信度降至0.5(圖3(b));當(dāng)點落在網(wǎng)格的角點上時，網(wǎng)格置信度降至0.25(圖3(c))。當(dāng)p＜0.25時，待定位點已經(jīng)不在網(wǎng)格范圍內(nèi)?？梢姡ㄎ稽c離網(wǎng)格核心區(qū)越近，p的取值越接近于1，該網(wǎng)格作為候選道路的檢索范圍的可信度就越高?；谶@種思想，本文設(shè)計了基于四級網(wǎng)格劃分的候選道路范圍篩選算法。

1.2.2 計算方法

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

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

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

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

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

1.2.2.1 非邊界區(qū)域求解算法

非邊界情況下的求解算法可簡述為:如果點q所在子網(wǎng)格sub為Gi的核心區(qū)，則將點q的候選道路檢索范圍限定在 Gi內(nèi)。當(dāng)2≤n≤N－1且2≤m≤M－1時，篩選函數(shù)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四級網(wǎng)格為例，說明求解過程。

圖4 四級網(wǎng)格樣例圖Fig.4 Example of four－level grid

圖4(a)以“網(wǎng)格級別－單元格編號”的方式(如1－5)標(biāo)出各級網(wǎng)格單元格的編號，其中編號為1－5單元格放大后如圖4(b)所示。設(shè)點q所在子網(wǎng)格編號為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個子網(wǎng)格均為各級網(wǎng)格單元格的核心區(qū)，因此在非邊界情況下，本方法可保證檢索范圍的置信度最高且將檢索范圍限定在1個單元格內(nèi)。

1.2.2.2 邊界情況下的求解算法

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

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

圖5 邊界網(wǎng)格示意圖Fig.5 Example of boundary grids

當(dāng)點q落在1－1單元格內(nèi)時，設(shè)其所在子網(wǎng)格編號為 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 號子網(wǎng)格分別是各級網(wǎng)格單元格的核心區(qū)，可用本節(jié)算法求得對應(yīng)的網(wǎng)格編號。而對于 1，2，3，4，5，9，13 號子網(wǎng)格而言，它們不屬于任何一級網(wǎng)格單元格的核心區(qū)，因此要根據(jù)網(wǎng)格置信度最大化原則判定檢索范圍。其中1，2，3，5，9號子網(wǎng)格只在1－1的單元格的范圍內(nèi)，如果點q落在它們當(dāng)中，只有1－1號單元格作為候選檢索范圍。而4，13號子網(wǎng)格例外，它們位于2個單元格的共享范圍內(nèi)。以4號單元格為例，其同時在1－1和3－1的范圍內(nèi)，當(dāng)點q落在其內(nèi)時，就有2個單元格作為候選檢索范圍，但因3－1的置信度大于1－1的置信度，故將檢索范圍限定在3－1內(nèi)。同理，當(dāng)點q落在13號子網(wǎng)格內(nèi)時，有1－1和4－1作為候選檢索范圍，但4－1的置信度大于1－1，因此檢索范圍限定在4－1內(nèi)。根據(jù)這種判定原則，結(jié)合4個頂角和4條邊的各異情況，可編制出相應(yīng)的篩選算法解決非核心區(qū)情況下的范圍判定。

2 實驗與分析

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

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

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

3 結(jié)論

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

［1］薛 明，呂衛(wèi)鋒，諸彤宇.浮動車信息處理系統(tǒng)關(guān)鍵技術(shù)的研究［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］唐進君，曹 凱.基于多準(zhǔn)則融合的信任理論地圖匹配算法［J］.測繪科學(xué)，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］馮金巧，孫占全，劉 威.基于多級網(wǎng)絡(luò)劃分的匹配道路初篩方法研究［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證據(jù)理論的GPS/MM組合系統(tǒng)車輛定位算法［J］.北京航空航天大學(xué)學(xué)報，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］.華南理工大學(xué)學(xué)報:自然科學(xué)版，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－h(huán)elsinki.Finland:(s.n.)，2000:114 －119.

［7］趙國求.經(jīng)典概率與量子概率［J］.武漢工程職業(yè)技術(shù)學(xué)院，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 －h(huán)ong，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－)，男，碩士研究生，主要研究領(lǐng)域為并行計算和網(wǎng)絡(luò)地理信息系統(tǒng)。E－mail:xmzfighting@126.com。

(責(zé)任編輯:刁淑娟)