顧及尺度變化和數(shù)據(jù)更新的道路網(wǎng)匹配算法

郭慶勝,謝育武,劉紀平，王 琳，周 林

1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢430079； 2.武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北 武漢430079； 3.中國測繪科學(xué)研究院，北京100830

?

顧及尺度變化和數(shù)據(jù)更新的道路網(wǎng)匹配算法

郭慶勝1,2,謝育武1,劉紀平3，王 琳1，周 林1

1.武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院，湖北 武漢430079； 2.武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北 武漢430079； 3.中國測繪科學(xué)研究院，北京100830

道路網(wǎng)數(shù)據(jù)匹配是地理空間數(shù)據(jù)庫進行變化探測和數(shù)據(jù)更新的重要前提，不同比例尺下的道路網(wǎng)之間的匹配是一個非常重要的部分。本文總結(jié)和分析了道路網(wǎng)匹配的已有算法，針對不同比例尺道路網(wǎng)之間的匹配可能存在的問題和難點，設(shè)計了一個融合多種匹配技術(shù)的算法。在考慮不同比例尺下道路網(wǎng)數(shù)據(jù)的特點基礎(chǔ)上，改進了空間場景結(jié)構(gòu)的評價方法；分析了stroke匹配算法在不同比例尺道路網(wǎng)數(shù)據(jù)下的局限性，提出了一種可針對不同比例尺下道路數(shù)據(jù)存在變化與更新的stroke部分匹配算法。試驗表明，文中所提出的方法能夠適應(yīng)不同比例尺下道路網(wǎng)的匹配，匹配效果較好，運行效率較高。

多比例尺；道路網(wǎng)；匹配；stroke部分匹配；空間場景結(jié)構(gòu)

空間目標匹配就是找出兩個數(shù)據(jù)集中在地理空間位置上具有同等分布格局的實體。我國系列基本比例尺地理空間數(shù)據(jù)庫逐步建成，而城市化發(fā)展帶來道路網(wǎng)數(shù)據(jù)變化更新周期縮短，對這些不同尺度、不同精度的道路網(wǎng)數(shù)據(jù)進行高效管理已成為空間數(shù)據(jù)庫技術(shù)的研究熱點。有效解決這個問題的關(guān)鍵之一是對不同版本空間數(shù)據(jù)中的同名要素進行自動識別，并建立它們之間的匹配關(guān)系。因此，不同比例尺下同名實體間匹配關(guān)系的準確、快速識別與建立是后續(xù)道路數(shù)據(jù)更新、集成與融合的基礎(chǔ)，具有重要意義[1]。

國內(nèi)外學(xué)者對道路網(wǎng)匹配算法已有比較深入研究，匹配算法主要分為：基于拓撲結(jié)構(gòu)的匹配[2-8]、基于幾何相似度的匹配[9-18]和基于數(shù)學(xué)模型的匹配[19-22]。基于拓撲結(jié)構(gòu)的匹配算法中，文獻[7]的算法首先進行節(jié)點、弧段的粗匹配，然后利用節(jié)點和弧段拓撲關(guān)系的相似性和離散Fréchet距離進行精確匹配?；趲缀蜗嗨贫鹊钠ヅ渌惴ㄖ校墨I[15]提出了基于格網(wǎng)索引的“折線—節(jié)點”距離匹配算法，將復(fù)雜的折線與折線之間的幾何相似度計算轉(zhuǎn)換為求節(jié)點到折線距離的匹配方法，降低了計算復(fù)雜度，并通過建立格網(wǎng)索引來提高計算效率。文獻[16]提出了一種基于概率理論的匹配模型，該模型在線目標匹配中融合多種匹配指標計算實體匹配概率大小來確定匹配實體?；跀?shù)學(xué)模型的算法中，文獻[20]提出了一種基于概率松弛方法的道路網(wǎng)匹配算法。文獻[22]通過多個幾何指標衡量匹配對之間的幾何特征差異，構(gòu)建道路網(wǎng)回歸匹配模型，并利用此模型對待匹配目標對進行匹配。

然而，由于制圖綜合的原因，再加上道路數(shù)據(jù)采集過程中，不同制圖員會對空間抽象有著各自的理解，在制作不同比例尺的地圖時，拓撲變化的規(guī)律具有不定性，不同比例尺道路網(wǎng)的匹配會出現(xiàn)一些特殊情況：

(1) 當比例尺變小時，道路網(wǎng)中的環(huán)會變成點、正方形或三角形道路；立交橋附屬結(jié)構(gòu)可能消失等情況。

(2) 當數(shù)據(jù)存在更新變化時，某一條道路在小比例尺地圖上為連貫的空間目標，但在大比例尺圖上可能因為道路的整改、變遷，該道路可能已經(jīng)分裂成兩條道路，或在道路形態(tài)結(jié)構(gòu)上發(fā)生了很大的改變。

(3) 當?shù)缆肪W(wǎng)稠密時，小比例尺某條道路很可能會在大比例尺匹配數(shù)據(jù)集中找到多條長度、方向、形狀等多個指標都基本一致的候選匹配對象，這就需要改進空間場景結(jié)構(gòu)的評價方法。

(4) 在不同尺度下還會存在單行線變雙行線、兩車道變4車道等情況。

綜上所述，單一匹配技術(shù)難以在不同比例尺道路網(wǎng)的匹配中得到較好的匹配效果。因此，本文試圖融合stroke技術(shù)、多因子幾何相似度計算、空間索引技術(shù)、正反雙向匹配、改進的空間場景結(jié)構(gòu)相似性評價方法以及stroke整體匹配與部分匹配相結(jié)合等多種技術(shù)進行不同比例尺道路網(wǎng)匹配。

1 不同比例尺道路網(wǎng)匹配的思路

不同比例尺的道路網(wǎng)匹配的數(shù)據(jù)處理流程如圖1所示，主要分為數(shù)據(jù)預(yù)處理、stroke整體匹配和stroke部分匹配3個部分。數(shù)據(jù)預(yù)處理部分主要完成不同比例尺道路內(nèi)部節(jié)點加密、stroke連接以及空間格網(wǎng)索引的建立。在stroke整體匹配過程中，主要完成不同比例尺道路在幾何形態(tài)和拓撲結(jié)構(gòu)都相似的道路匹配。對于未匹配成功的道路，可利用stroke部分匹配，最大限度地搜查同名目標的匹配關(guān)系。

圖1 不同比例尺道路網(wǎng)匹配的數(shù)據(jù)處理流程Fig.1 Procedure of road networks matching at different scales

為了提高目標匹配的計算效率，算法中對多種基礎(chǔ)幾何算法進行了改進，包括近似的緩沖區(qū)代替精密緩沖區(qū)。對于克服單一幾何相似度衡量指標的局限性，本文利用多個幾何相似度衡量指標計算空間目標的幾何相似度S(s1,s2)，計算見式(1)

(1)

式中，ω1、ω2和ω3均為經(jīng)驗權(quán)值(ω1、ω2和ω3均為正數(shù)，ω1+ω2+ω3=1)；s1和s2表示兩條stroke；H(·)為文獻[23]的所提出的Hausdorff距離修正計算方法；HT為Hausdorff距離閾值；LR(·)為兩個stroke長度之比計算函數(shù)，長度比越接近1，表明相似度越高；A(·)是兩個stroke之間的夾角(范圍在0～π之間)計算函數(shù)，在計算過程中，兩個stroke之間的夾角被抽象成由stroke首末節(jié)點所連成的線段之間的夾角；AT為夾角閾值。

根據(jù)Hausdorff距離的公式定義，若兩空間目標在幾何形態(tài)結(jié)構(gòu)上差異較大，則兩空間目標靠得再近，相互之間的Hausdorff距離也會較大。因此Hausdorff距離除了可以衡量目標之間的空間距離，還可以一定程度上衡量相互之間的幾何形態(tài)結(jié)構(gòu)相似度。此外，算法還融合了空間索引技術(shù)以及文獻[24]的正反雙向匹配。

2 空間場景結(jié)構(gòu)的相似性評價

全局一致性評價是指將待匹配空間場景與候選匹配空間場景進行整體相似性評價，既評價個體相似性，同時也評價空間場景結(jié)構(gòu)特征的相似性[25]。個體相似性的衡量可利用相似度計算公式(1)完成，而空間場景結(jié)構(gòu)的相似性則需要對stroke所處的空間分布格局進行評價。一條stroke的空間場景結(jié)構(gòu)由與其首、末節(jié)點相連的stroke所構(gòu)成，當需要比較兩條stroke之間的空間場景結(jié)構(gòu)相似度時，利用兩個空間場景中相互匹配成功的stroke匹配對來計算[25]。但是，不同比例尺道路網(wǎng)的抽象程度會有所不同，例如在表示同一地區(qū)的兩幅不同比例尺地圖上的道路數(shù)量可能存在差別，同名stroke的空間場景結(jié)構(gòu)就有可能不同，導(dǎo)致在空間場景結(jié)構(gòu)評價中出現(xiàn)誤判斷的情況。

在制圖綜合中，連通度、長度等被作為衡量一條道路重要性的常用指標，如果某條道路長度較長，則通常是一條具有“主干”“動脈”特點的道路，在制圖綜合中不易被剔除，也不容易因為時間的變化而出現(xiàn)消失、縮短等情況?；谶@樣地圖制圖規(guī)則，本文改進的空間場景結(jié)構(gòu)評價方法如下：

(1) 對于兩條可能存在匹配關(guān)系的stroke道路s(小比例尺)和m(大比例尺)，設(shè)s的首、末節(jié)點分別為ss和se；m的首、末節(jié)點分別為ms和me。為了能保證stroke道路整體匹配中首、末節(jié)點相對應(yīng)，需要先確定s與m的首、末節(jié)點對應(yīng)關(guān)系。因為不同比例尺下兩個同名空間目標的首末端點可能會有不同的對應(yīng)關(guān)系(若兩道路的空間數(shù)據(jù)采集方向相同，則s與m的首、末節(jié)點相互對應(yīng)；否則，可能是s的首節(jié)點與m的末節(jié)點相對應(yīng))。本文直接采用s與m的首、末節(jié)點相互之間的最小歐氏距離來確定節(jié)點的對應(yīng)關(guān)系。若兩道路首末節(jié)點走向一致，則得到兩個節(jié)點對P1(ss與ms)和P2(se與me)，否則，兩個節(jié)點對為P1(ss與me)和P2(se與ms)。

(2) 這里，設(shè)兩個節(jié)點對為P1(ss與ms)和P2(se與me)。對于節(jié)點對P1，設(shè)與ss相連的stroke集合為A，與ms相連的stroke集合為B。若集合A不為空，則選出A中最長的stroke道路，記為Ai，同理在B中選出最長的Bj，轉(zhuǎn)步驟(3)(對于另外一種節(jié)點對情況可以進行類似處理)。

(3) 設(shè)Ai和Bj之間計算的幾何相似度為Ss。若A和B都為空集，則Ss=1；若A、B中只有一個空集，則Ss=0；否則，利用式(1)進行計算Ss=S(Ai,Bj)。

(4) 得到Ss后，利用相同原理轉(zhuǎn)步驟(2)，對P2中的節(jié)點對計算Se。

(5) 最終的空間結(jié)構(gòu)場景相似度為Ss與Se的平均值Ss,e，若Ss,e大于給定的閾值，則認為匹配成功；否則匹配失敗。

3 stroke部分匹配

3.1 算法提出的背景

當?shù)缆房臻g數(shù)據(jù)出現(xiàn)變化時，若只利用式(1)進行匹配，將會得到非常低的相似度。如圖2(a)所示，在小比例尺圖上有s_Str1(由弧段s2和s3組成)和s_Str2(由弧段s1組成)兩條stroke。在數(shù)據(jù)出現(xiàn)更新變化的大比例尺圖上則有m_Str1(由弧段m3組成)和m_Str2(由弧段m1和m2組成)，如圖2(b)所示。此時，小比例尺圖上弧段s1與s2并沒有連接成一條stroke，因而無法與大比例尺圖上的m_Str2相匹配。從圖2(c)可以看出，不同比例尺的道路之間存在匹配情況，但是若只是判斷stroke是否整體匹配，則無法識別弧段s3與m3的匹配以及弧段s2與m2的匹配。很明顯，s_Str1與m_Str1以及s_Str1與m_Str2之間只存在部分匹配的情況。

圖2 存在stroke部分匹配的情況Fig.2 Examples of partial stroke matching

3.2 算法描述

在經(jīng)過stroke整體匹配后，設(shè)未能匹配上的小比例尺的stroke集合為S(共有n條)，大比例尺的stroke集為L。本文提出的stroke部分匹配的算法如下：

(1) 若集合S和L不同時為空，則遍歷集合S，對集合S中每條stroke道路Si(其中Si∈S;i=0,1,…,n)，利用格網(wǎng)空間索引和近似緩沖區(qū)在集合L中搜索出候選匹配集為M；否則結(jié)束。若集合M為空，則將Si從集合S中剔除，繼續(xù)遍歷S中的stroke；否則，設(shè)M共有m條stroke，對M的每一條stroke道路Mj(其中Mj∈M;j=0,1,…,m)進行遍歷處理。

(2) 設(shè)Si的弧段數(shù)為NSi，每條弧段表示為Si,q(其中，q=0,1,…,NSi)；設(shè)T為Hausdorff距離閾值。利用文獻[21]提出的SM_HD算法計算Si中的每一條弧段Si,q與Mj的Hausdorff距離Hq。若Hq>T，則設(shè)Si,q的屬性值HBi,q為false，否則HBi,q為true。這樣就可以得到Si各個弧段相對于Mj的Hausdorff距離是否滿足閾值的一個布爾型集合PSi

PSi={HBi,1,HBi,2,…,HBi,NSi}

同理，設(shè)Mj的弧段數(shù)為NMj，反過來計算Mj中每一條弧段Mj,p(其中，p=0,1,…,NMj)與Si的Hausdorff距離Hp，同理可得到HBj,p并形成布爾型集合PMj

PMj={HBj,1,HBj,2,…,HBj,NMj}

若PSi或PMj其中之一的元素全為false，則繼續(xù)對集合M的下一個stroke元素Mj+1進行處理；否則，轉(zhuǎn)到步驟(3)。

(3) 對PSi和PMj的元素值分別進行對比分析，若元素值從左到右連續(xù)的都為true值，則組成一個匹配體。PSi中第k個匹配體可以表示為PkSi=[Si,k′,Si,k″](其中k′、k″≤NSi，且k′、k″之間連續(xù))，這說明在Si中，從Si,k′到Si,k″之間的所有弧段的HB屬性值均為true，且所有弧段在Si中連續(xù)(依次相連)。

(4) 對PSi和PMj中的每個下標k一致的匹配體進行組合，形成一個“匹配對”，得到“匹配對”集合P。

(5) 遍歷P，對每個“匹配對”中所包含的Si中的弧段和Mj中的弧段分別重新連接成stroke。

(6) 對新生成的stroke進行長度比值和夾角計算。若長度比值和夾角都符合閾值條件，則認為部分匹配成功，將部分匹配成功的所有弧段標志為已匹配。若長度比值或夾角其中之一不符合閾值條件，則對較長的stroke按照順序(從首至末)剔除一條弧段后，將所剩下的弧段生成新stroke，再與“匹配對”中較短的stroke進行長度比值和夾角的計算，直至符合閾值條件或弧段全部剔除完，繼續(xù)遍歷P，若P已遍歷完畢，轉(zhuǎn)至步驟(7)，否則轉(zhuǎn)至步驟(5)。

(7) 檢查M是否被遍歷完畢。若遍歷完畢，則對Si的下一元素Si+1進行處理，轉(zhuǎn)至步驟(1)；否則，對Mj的下一元素Mj+1進行處理，轉(zhuǎn)至步驟(2)。

4 試驗與分析

為了校驗本文所提出的算法對不同比例尺下的道路網(wǎng)匹配的有效性，選擇了VS2010(C#)進行了算法的設(shè)計與實現(xiàn)。

4.1 比例尺變化較小的試驗

試驗選取了南昌市某地區(qū)兩幅比例尺分別為1∶5000和1∶2.5萬的道路網(wǎng)數(shù)據(jù)。其中，大比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為739條、502條和1 027.4 km。而小比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為301條、176條和634.8 km。試驗中，設(shè)插入點距離、Hausdorff距離閾值以及近似緩沖半徑均為150 m。兩種數(shù)據(jù)疊加后的情況如圖3所示。

在圖3中的A區(qū)域放大后如圖4(a)所示，大比例尺圖上原為雙行道(M1和M2)，在道路某處拓寬為4車道(增加a和b)，但在小比例尺圖中抽象為一條道路S。圖3的B區(qū)域放大后為圖4(b)所示，大比例尺圖上有縱橫交叉的道路所構(gòu)成的十字路口，在十字路口處還存在一些道路附屬結(jié)構(gòu)，使得道路交叉口處道路十分稠密，但在小比例尺地圖上，抽象簡化為縱橫交叉的兩條相交道路。

圖3 試驗1的道路網(wǎng)Fig.3 Road networks used in experiment 1

圖4 在圖3中區(qū)域A和B的匹配結(jié)果Fig.4 Matching results of region A and region B in Fig.3

在匹配處理后，得到圖4(a)中S與M1、M2匹配，但并沒有把a和b納入為匹配對象。所以，本算法在處理多車道目標匹配問題時，只選擇最佳匹配的對象，因為抽象而退化的附屬結(jié)構(gòu)目標不參與匹配。圖4(b)中也是如此，S與M1、M2匹配，十字交叉路口的附屬結(jié)構(gòu)道路沒有被納入匹配對象。

圖3上的C區(qū)域放大后如圖5所示，在大比例尺地圖上弧段a、b、c和d組成一條stroke(m_stroke)，但在小比例尺地圖上，由于道路結(jié)構(gòu)發(fā)生了變化，在小比例尺上不再存在與弧段b、c相匹配的目標，即大比例地圖上的m_stroke在小比例尺地圖上缺少圓弧部分，分成s1和s2兩條stroke。在進行stroke部分匹配過程中，計算得到s1與a的幾何相似度為0.990，s2與d的幾何相似度為0.905。此兩個匹配對都符合匹配閾值要求。

圖5 在圖3中的區(qū)域C的匹配結(jié)果Fig.5 Matching results of region C in Fig.3

4.2 比例尺變化較大的試驗

試驗數(shù)據(jù)為合肥市某地區(qū)的比例尺變化較大的兩幅地圖數(shù)據(jù)(1∶5000和1∶10萬)。小比例尺數(shù)據(jù)與大比例尺數(shù)據(jù)在道路形態(tài)和測量精度上都有較大的差異。其中，大比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為1945條、1294條和1 308.7 km。而小比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為359條、143條和629.5 km。試驗中，設(shè)插入點距離為150 m，Hausdorff距離閾值為200 m，近似緩沖半徑300 m。兩種數(shù)據(jù)疊加后的情況如圖6所示。

圖6中的區(qū)域A放大后如圖7所示，大比例尺的環(huán)形道路結(jié)構(gòu)變?yōu)樾”壤邎D上的十字路口。在進行stroke匹配時，小比例尺的弧段a′和c′會連接成s_stroke1，弧段b′和d′會連接成s_stroke2。而在大比例尺道路中，因為弧段a、b、c和d與環(huán)連接，所以它們各自成一條stroke。在匹配過程中，s_stroke1與弧段a所在的stroke和弧段b所在的stroke的幾何相似度分別是0.562和0.517，空間場景結(jié)構(gòu)相似度均為0。所以，需要進行stroke部分匹配，s_stroke1的a′弧段形成的stroke與弧段a形成的stroke的幾何相似度為0.934，c′弧段所在的stroke與弧段c形成的stroke的幾何相似度為0.942，說明這兩個“匹配對”的匹配成功。

圖6 試驗2的道路網(wǎng)Fig.6 Road networks used in experiment 2

圖7 環(huán)形結(jié)構(gòu)的匹配結(jié)果Fig.7 Matching result of ring structure

圖6中B區(qū)域放大后如圖8所示，在復(fù)雜的道路連接口處，在大比例尺圖上為橫向分布的兩條道路連接縱向分布的雙行道，并在連接口處出現(xiàn)分叉的連接結(jié)構(gòu)。而在小比例尺圖上，因為比例尺度跨度較大的原因，直接抽象成十字交叉路。經(jīng)過stroke整體匹配和stroke部分匹配算法處理后，弧段a與弧段a′匹配，弧段b與弧段b′匹配。而雙行道c在幾何形態(tài)和空間場景結(jié)構(gòu)都與c′相似度高，無需進行stroke部分匹配算法就可完成匹配過程。

圖8 有拓撲結(jié)構(gòu)變化的匹配結(jié)果Fig.8 Matching result of road networks with topological change

4.3 城郊接合部與鄉(xiāng)村道路的試驗

以上兩個試驗主要針對城市道路網(wǎng)的匹配，為了驗證本算法的高適應(yīng)性，選取了城郊接合部(武漢市某地區(qū)，試驗3)和鄉(xiāng)村道路(佛山市某地區(qū)，試驗4)作為試驗數(shù)據(jù)，這兩類數(shù)據(jù)的大小比例尺都分別為1∶5000和1∶2.5萬。兩次試驗都設(shè)插入點距離、Hausdorff距離閾值以及近似緩沖半徑均為150 m。其中，城郊接合部大比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為258條、211條和20.5 km。而小比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為144條、100條和15.9 km。城郊接合部的數(shù)據(jù)在比例尺變化不大時較少存在拓撲結(jié)構(gòu)發(fā)生變化的匹配情況，利用stroke整體匹配即可取得較好的匹配效果。

鄉(xiāng)村道路的試驗數(shù)據(jù)中，大比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為133條、77條和14.3 km。而小比例尺地圖中弧段數(shù)、stroke數(shù)和總長度分別為70條、26條和11.9 km。鄉(xiāng)村道路的數(shù)據(jù)與城郊接合部數(shù)據(jù)特點相似，但鄉(xiāng)村道路數(shù)據(jù)變化更新頻繁，部分區(qū)域的匹配需要stroke部分匹配算法進行處理。

4.4 試驗結(jié)果對比分析

為了對匹配效果進行評價，采用人工方式對試驗匹配結(jié)果進行了檢查，并利用文獻[21]的評價公式對結(jié)果進行評估，見式(2)

(2)

式中，P為匹配準確率；R為匹配召回率；f(C)為正確匹配數(shù)；f(W)為錯誤匹配數(shù)；f(U)為漏匹配數(shù)。前后4次試驗結(jié)果的統(tǒng)計信息如表1所示。表中除試驗3外各個試驗中f(C)+f(W)+f(U)都大于相應(yīng)試驗數(shù)據(jù)中的小比例尺的stroke數(shù)目。其原因是在匹配過程中，一部分小比例尺的stroke會在部分匹配中由一條stroke分成了若干條stroke形成若干匹配對。

表1 試驗結(jié)果的比較Tab.1 Comparison between experimental results

根據(jù)試驗結(jié)果的統(tǒng)計信息，本算法有著較高的匹配準確率和召回率。按照“數(shù)據(jù)集總長度/耗時”計算匹配速度，得到試驗1至試驗4的匹配速度分別是641.8 km/s、791.1 km/s、1 213.3 km/s和524 km/s。在試驗1中匹配速度之所以低于試驗2，是因為試驗2中比例尺變化較大，在大比例尺道路網(wǎng)中存在大量沒有匹配對象的細小stroke，從而減輕了計算壓力。而試驗3和試驗4因為數(shù)據(jù)復(fù)雜度較低、路網(wǎng)稀疏，匹配速度較高。

5 結(jié) 語

本文通過分析不同比例尺下的道路網(wǎng)匹配所存在的問題和技術(shù)難點，提出了一種融合多種道路網(wǎng)匹配技術(shù)的策略。同時，對空間場景結(jié)構(gòu)的評價方法進行了改進，針對整體stroke匹配不能適應(yīng)存在數(shù)據(jù)變化的道路網(wǎng)匹配情況，提出了stroke部分匹配方法。試驗表明，本文所提出的方法具有較高的匹配準確率、召回率和運行效率，且在處理不同比例尺道路網(wǎng)中的拓撲結(jié)構(gòu)變化時也能有很好的適應(yīng)性，可適用于不同比例尺的國家基本比例尺地理空間數(shù)據(jù)庫的道路網(wǎng)匹配。但是，閾值和權(quán)重這些參數(shù)目前都是通過人為經(jīng)驗設(shè)定的。在今后的研究工作中，將研究如何根據(jù)具體的數(shù)據(jù)自動設(shè)定閾值和權(quán)重，以進一步確保匹配的效果和質(zhì)量。

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B.Map Matching Algorithms for Intelligent Transport Systems Applications[C]∥Proceedings of the 13th World Congress on Intelligent Transport Systems Services.London: ITRD, 2006.

[2] DOYTSHER Y, FILIN S.The Detection of Corresponding Objects in a Linear-based Map Conflation[J].Surveying and Land Information Systems, 2000, 60(2): 117-128.

[3] MANTEL D, LIPECK U.Matching Cartographic Objects in Spatial Databases[C]∥Proceedings of the 20th ISPRS Congress, Commission 4.Istanbul, Turkey: ISPRS, 2004.

[4] ZHANG Meng, SHI Wei, MENG Liqiu.A Generic Matching Algorithm For Line Networks of Different Resolutions[C]∥Proceedings of the 8th ICA Workshop on Generalisation and Multiple Representation.A Corua, Spain: [s.n.], 2005.

[5] ZHANG Meng, SHI Wei, MENG Liqiu.A Matching Approach Focused on Parallel Roads and Looping Crosses in Digital Maps[C]∥International Symposium of Theoretical Cartography and Geo-Information Science.Wuhan, China: [s.n.], 2006.

[6] ZHANG Meng, MENG Liqiu, BOBRICH J.A Road-network Matching Approach Guided by “Structure”[J].Annals of GIS, 2010, 16(3): 165-176.

[7] 安曉亞, 孫群, 尉伯虎.利用相似性度量的不同比例尺地圖數(shù)據(jù)網(wǎng)狀要素匹配算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版), 2012, 37(2): 224-228, 241.AN Xiaoya, SUN Qun, WEI Bohu.Feature Matching from Network Data at Different Scales Based on Similarity Measure[J].Geomatics and Information Science of Wuhan University, 2012, 37(2): 224-228, 241.

[8] 劉闖, 錢海忠, 王驍, 等.顧及上下級空間關(guān)系相似性的道路網(wǎng)聯(lián)動匹配方法[J].測繪學(xué)報, 2016, 45(11): 1371-1383.DOI: 10.11947/j.AGCS.2016.20160062.LIU Chuang, QIAN Haizhong, WANG Xiao, et al.A Linkage Matching Method for Road Networks Considering the Similarity of Upper and Lower Spatial Relation[J].Acta Geodaetica et Cartographica Sinica, 2016, 45(11): 1371-1383.DOI: 10.11947/j.AGCS.2016.20160062.

[9] WALTER V, FRITSCH D.Matching Spatial Data Sets: A Statistical Approach[J].International Journal of Geographical Information Systems, 1999, 13(5): 445-473.

[10] ZHANG Meng, MENG Liqiu.An Iterative Road-matching Approach for the Integration of Postal Data[J].Computers, Environment and Urban Systems, 2007, 31(5): 597-615.

[11] ZHANG Meng, MENG Liqiu.Delimited Stroke Oriented Algorithm-working Principle and Implementation for the Matching of Road Networks[J].Annals of GIS, 2008, 14(1): 44-53.

[12] ZHANG M.Methods and Implementations of Road-network Matching[D].Munich, Germany: Technical University of Munich, 2009.

[13] VOLZ S.An Iterative Approach for Matching Multiple Representations of Street Data[C]∥Proceedings of ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data.Hanover, Germany: ISPRS, 2006: 101-110.

[14] DENG MIN, LI ZHILIN, CHEN XIAOYONG.Extended Hausdorff Distance for Spatial Objects in GIS[J].International Journal of Geographical Information Science, 2007, 21(4): 459-475.

[15] 陳玉敏, 龔健雅, 史文中.多尺度道路網(wǎng)的距離匹配算法研究[J].測繪學(xué)報, 2007, 36(1): 84-90.DOI: 10.3321/j.issn:1001-1595.2007.01.015.CHEN Yumin, GONG Jianya, SHI Wenzhong.A Distance-based Matching Algorithm for Multi-scale Road Networks[J].Acta Geodaetica et Cartographica Sinica, 2007, 36(1): 84-90.DOI: 10.3321/j.issn:1001-1595.2007.01.015.

[16] 童小華, 鄧愫愫, 史文中.基于概率的地圖實體匹配方法[J].測繪學(xué)報, 2007, 36(2): 210-217.DOI: 10.3321/j.issn:1001-1595.2007.02.017.TONG Xiaohua, DENG Susu, SHI Wenzhong.A Probabilistic Theory-based Matching Method[J].Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 210-217.DOI: 10.3321/j.issn:1001-1595.2007.02.017.

[17] 趙東保, 盛業(yè)華.全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J].測繪學(xué)報, 2010, 39(4): 416-421.ZHAO Dongbao, SHENG Yehua.Research on Automatic Matching of Vector Road Networks Based on Global Optimization[J].Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 416-421.

[18] HACKELOEER A, KLASING K, KRISP J M, et al.Road Network Conflation: An Iterative Hierarchical Approach[M]∥GARTNER G, HUANG Haosheng.Progress in Location-based Services 2014.Switzerland: Springer, 2015: 137-151.

[19] SONG Wenbo, KELLER J M, HAITHCOAT T L, et al.Relaxation-based Point Feature Matching for Vector Map Conflation[J].Transactions in GIS, 2011, 15(1): 43-60.

[20] 張云菲, 楊必勝, 欒學(xué)晨.利用概率松弛法的城市路網(wǎng)自動匹配[J].測繪學(xué)報, 2012, 41(6): 933-939.ZHANG Yunfei, YANG Bisheng, LUAN Xuechen.Automated Matching Urban Road Networks Using Probabilistic Relaxation[J].Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 933-939.

[21] TONG Xiaohua, LIANG Dan, JIN Yanmin.A Linear Road Object Matching Method for Conflation Based on Optimization and Logistic Regression[J].International Journal of Geographical Information Science, 2014, 28(4): 824-846.

[22] 付仲良, 楊元維, 高賢君, 等.道路網(wǎng)多特征匹配優(yōu)化算法[J].測繪學(xué)報, 2016, 45(5): 608-615.DOI: 10.11947/j.AGCS.2016.20150388.FU Zhongliang, YANG Yuanwei, GAO Xianjun, et al.An Optimization Algorithm for Multi-characteristics Road Network Matching[J].Acta Geodaetica et Cartographica Sinica, 2016, 45(5): 608-615.DOI: 10.11947/j.AGCS.2016.20150388.

[23] 張良國, 吳江琴, 高文, 等.基于Hausdorff距離的手勢識別[J].中國圖象圖形學(xué)報, 2002, 7(11): 1144-1150.ZHANG Liangguo, WU Jiangqin, GAO Wen, et al.Hand Gesture Recognition Based on Hausdorff Distance[J].Journal of Image and Graphics, 2002, 7(11): 1144-1150.

[24] 邵世維.基于幾何特征的多尺度矢量面狀實體匹配方法研究與應(yīng)用[D].武漢: 武漢大學(xué), 2011: 89-94.SHAO Shiwei.Researches and Applications on Polygon Entity Matching for Multi-scale Vector Data Based on Geometric Features[D].Wuhan: Wuhan University, 2011: 89-94.

[25] 翟仁健.基于全局一致性評價的多尺度矢量空間數(shù)據(jù)匹配方法研究[D].鄭州: 信息工程大學(xué), 2011: 51-79.ZHAI Renjian.Research on Automated Matching Methods for Multi-Scale Vector Spatial Data Based on Global Consistency Evaluation[D].Zhengzhou: Information Engineering University, 2011: 51-79.

(責任編輯：宋啟凡)

Algorithms for Road Networks Matching Considering Scale Variation and Data Update

GUO Qingsheng1,2,XIE Yuwu1,LIU Jiping3,WANG Lin1,ZHOU Lin1

1.School of Resources and Environment Science, Wuhan University, Wuhan 430079, China; 2.State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China; 3.Chinese Academy of Surveying and Mapping, Beijing 100830, China

Road network matching is an important prerequisite for the change detection and data updating of spatial database, and the matching of road networks at different scales is very important.In this paper, the existing algorithms road networks matching are summarized and analyzed firstly, and according to the problems and difficulties in the road networks matching at different scales, an algorithm integrating multiple matching techniques was designed.Based on the characteristics of road networks at different scales, the method of evaluating the structure of spatial scene was improved.The limitations of the algorithm based on stroke matching were analyzed for road networks data at the different scales, and the algorithm named “partial stroke matching” was put forward.The experiments indicate that the algorithm given in this paper can be used in matching of road networks at different scales, the effect of matching is good, and the running efficiency is high as well.

multi-scales；road networks；matching；partial stroke matching；spatial scene structure

The National Natural Science Foundation of China (No.41471384)；Special Fund for Research in the Public Interest (No.201512032)

GUO Qingsheng(1965—), male, PhD, professor, majors in cartographic generalization, intelligent handling and visualization of geographical information.

郭慶勝,謝育武,劉紀平，等.顧及尺度變化和數(shù)據(jù)更新的道路網(wǎng)匹配算法[J].測繪學(xué)報，2017,46(3)：381-388.

10.11947/j.AGCS.2017.20160364.

GUO Qingsheng,XIE Yuwu,LIU Jiping,et al.Algorithms for Road Networks Matching Considering Scale Variation and Data Update[J].Acta Geodaetica et Cartographica Sinica,2017,46(3):381-388.DOI:10.11947/j.AGCS.2017.20160364.

P208

A

1001-1595(2017)03-0381-08

國家自然科學(xué)基金(41471384)；公益性科研專項(201512032)

2016-07-18

修回日期：2017-03-01

郭慶勝(1965—)，男，博士，教授，主要從事地圖制圖綜合、地理信息智能化處理與可視化研究。

E-mail：guoqingsheng@whu.edu.cn