郭慶勝,謝育武,劉紀(jì)平，王 琳，周 林

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

2 空間場(chǎng)景結(jié)構(gòu)的相似性評(píng)價(jià)

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

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

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

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

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

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

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

3 stroke部分匹配

3.1 算法提出的背景

當(dāng)?shù)缆房臻g數(shù)據(jù)出現(xiàn)變化時(shí)，若只利用式(1)進(jìn)行匹配，將會(huì)得到非常低的相似度。如圖2(a)所示，在小比例尺圖上有s_Str1(由弧段s2和s3組成)和s_Str2(由弧段s1組成)兩條stroke。在數(shù)據(jù)出現(xiàn)更新變化的大比例尺圖上則有m_Str1(由弧段m3組成)和m_Str2(由弧段m1和m2組成)，如圖2(b)所示。此時(shí)，小比例尺圖上弧段s1與s2并沒(méi)有連接成一條stroke，因而無(wú)法與大比例尺圖上的m_Str2相匹配。從圖2(c)可以看出，不同比例尺的道路之間存在匹配情況，但是若只是判斷stroke是否整體匹配，則無(wú)法識(shí)別弧段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)過(guò)stroke整體匹配后，設(shè)未能匹配上的小比例尺的stroke集合為S(共有n條)，大比例尺的stroke集為L(zhǎng)。本文提出的stroke部分匹配的算法如下：

(1) 若集合S和L不同時(shí)為空，則遍歷集合S，對(duì)集合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，對(duì)M的每一條stroke道路Mj(其中Mj∈M;j=0,1,…,m)進(jìn)行遍歷處理。

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

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

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

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

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

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

(4) 對(duì)PSi和PMj中的每個(gè)下標(biāo)k一致的匹配體進(jìn)行組合，形成一個(gè)“匹配對(duì)”，得到“匹配對(duì)”集合P。

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

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

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

4 試驗(yàn)與分析

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

4.1 比例尺變化較小的試驗(yàn)

試驗(yàn)選取了南昌市某地區(qū)兩幅比例尺分別為1∶5000和1∶2.5萬(wàn)的道路網(wǎng)數(shù)據(jù)。其中，大比例尺地圖中弧段數(shù)、stroke數(shù)和總長(zhǎng)度分別為739條、502條和1 027.4 km。而小比例尺地圖中弧段數(shù)、stroke數(shù)和總長(zhǎng)度分別為301條、176條和634.8 km。試驗(yàn)中，設(shè)插入點(diǎn)距離、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)，使得道路交叉口處道路十分稠密，但在小比例尺地圖上，抽象簡(jiǎn)化為縱橫交叉的兩條相交道路。

圖3 試驗(yàn)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匹配，但并沒(méi)有把a(bǔ)和b納入為匹配對(duì)象。所以，本算法在處理多車道目標(biāo)匹配問(wèn)題時(shí)，只選擇最佳匹配的對(duì)象，因?yàn)槌橄蠖嘶母綄俳Y(jié)構(gòu)目標(biāo)不參與匹配。圖4(b)中也是如此，S與M1、M2匹配，十字交叉路口的附屬結(jié)構(gòu)道路沒(méi)有被納入匹配對(duì)象。

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

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

4.2 比例尺變化較大的試驗(yàn)

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

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

圖6 試驗(yàn)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)。而在小比例尺圖上，因?yàn)楸壤叨瓤缍容^大的原因，直接抽象成十字交叉路。經(jīng)過(guò)stroke整體匹配和stroke部分匹配算法處理后，弧段a與弧段a′匹配，弧段b與弧段b′匹配。而雙行道c在幾何形態(tài)和空間場(chǎng)景結(jié)構(gòu)都與c′相似度高，無(wú)需進(jìn)行stroke部分匹配算法就可完成匹配過(guò)程。

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

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

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

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

4.4 試驗(yàn)結(jié)果對(duì)比分析

為了對(duì)匹配效果進(jìn)行評(píng)價(jià)，采用人工方式對(duì)試驗(yàn)匹配結(jié)果進(jìn)行了檢查，并利用文獻(xiàn)[21]的評(píng)價(jià)公式對(duì)結(jié)果進(jìn)行評(píng)估，見(jiàn)式(2)

(2)

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

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

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

5 結(jié) 語(yǔ)

本文通過(guò)分析不同比例尺下的道路網(wǎng)匹配所存在的問(wèn)題和技術(shù)難點(diǎn)，提出了一種融合多種道路網(wǎng)匹配技術(shù)的策略。同時(shí)，對(duì)空間場(chǎng)景結(jié)構(gòu)的評(píng)價(jià)方法進(jìn)行了改進(jìn)，針對(duì)整體stroke匹配不能適應(yīng)存在數(shù)據(jù)變化的道路網(wǎng)匹配情況，提出了stroke部分匹配方法。試驗(yàn)表明，本文所提出的方法具有較高的匹配準(zhǔn)確率、召回率和運(yùn)行效率，且在處理不同比例尺道路網(wǎng)中的拓?fù)浣Y(jié)構(gòu)變化時(shí)也能有很好的適應(yīng)性，可適用于不同比例尺的國(guó)家基本比例尺地理空間數(shù)據(jù)庫(kù)的道路網(wǎng)匹配。但是，閾值和權(quán)重這些參數(shù)目前都是通過(guò)人為經(jīng)驗(yàn)設(shè)定的。在今后的研究工作中，將研究如何根據(jù)具體的數(shù)據(jù)自動(dòng)設(shè)定閾值和權(quán)重，以進(jì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é)報(bào)(信息科學(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] 劉闖, 錢海忠, 王驍, 等.顧及上下級(jí)空間關(guān)系相似性的道路網(wǎng)聯(lián)動(dòng)匹配方法[J].測(cè)繪學(xué)報(bào), 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].測(cè)繪學(xué)報(bào), 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] 童小華, 鄧愫愫, 史文中.基于概率的地圖實(shí)體匹配方法[J].測(cè)繪學(xué)報(bào), 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)自動(dòng)匹配方法研究[J].測(cè)繪學(xué)報(bào), 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] 張?jiān)品? 楊必勝, 欒學(xué)晨.利用概率松弛法的城市路網(wǎng)自動(dòng)匹配[J].測(cè)繪學(xué)報(bào), 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].測(cè)繪學(xué)報(bào), 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] 張良國(guó), 吳江琴, 高文, 等.基于Hausdorff距離的手勢(shì)識(shí)別[J].中國(guó)圖象圖形學(xué)報(bào), 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] 邵世維.基于幾何特征的多尺度矢量面狀實(shí)體匹配方法研究與應(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] 翟仁健.基于全局一致性評(píng)價(jià)的多尺度矢量空間數(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.

(責(zé)任編輯：宋啟凡)

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.

郭慶勝,謝育武,劉紀(jì)平，等.顧及尺度變化和數(shù)據(jù)更新的道路網(wǎng)匹配算法[J].測(cè)繪學(xué)報(bào)，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

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

2016-07-18

修回日期：2017-03-01

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

E-mail：guoqingsheng@whu.edu.cn