一種復(fù)雜矢量面狀實(shí)體的匹配方法

張家新，韓保民 ，逯躍鋒，顏懷成

(山東理工大學(xué) 建筑工程學(xué)院，山東 淄博 255049)

一種復(fù)雜矢量面狀實(shí)體的匹配方法

張家新，韓保民 ，逯躍鋒，顏懷成

(山東理工大學(xué) 建筑工程學(xué)院，山東 淄博 255049)

針對(duì)復(fù)雜面狀實(shí)體要素匹配問題，采用一種公共邊對(duì)象化的Douglas-Peucker改進(jìn)算法對(duì)面實(shí)體形狀進(jìn)行簡化，然后將簡化后的面實(shí)體所提取的節(jié)點(diǎn)以及基于面實(shí)體周長的均勻采樣點(diǎn)作為面實(shí)體輪廓特征點(diǎn).利用提取的輪廓特征點(diǎn)，采取一種極坐標(biāo)方法對(duì)面實(shí)體進(jìn)行形狀描述，并分別計(jì)算出同名實(shí)體在節(jié)點(diǎn)和均勻采樣點(diǎn)處的距離差異，將獲取兩者綜合差異作為最終匹配標(biāo)準(zhǔn).通過實(shí)驗(yàn)對(duì)比分析可知，該方法能有效解決復(fù)雜面狀實(shí)體匹配速度和準(zhǔn)確率問題.

矢量匹配；Douglas-Peucker算法；極坐標(biāo)；輪廓特征點(diǎn)；匹配距離

在地理信息領(lǐng)域中，空間數(shù)據(jù)集成更新是維持?jǐn)?shù)據(jù)庫完整性和現(xiàn)勢性的基礎(chǔ)，而矢量匹配是其關(guān)鍵技術(shù). 面狀實(shí)體要素匹配是矢量要素匹配的重、難點(diǎn)問題，現(xiàn)實(shí)應(yīng)用中通常采用面狀實(shí)體之間幾何形狀相似程度來進(jìn)行匹配，即幾何匹配技術(shù)[1]，其難點(diǎn)就是在于如何對(duì)面狀實(shí)體準(zhǔn)確描述以及實(shí)體之間的匹配距離的量度. 針對(duì)面實(shí)體之間的幾何相似度度量問題，國內(nèi)外學(xué)者提出了很多解決方法.文獻(xiàn)[2]中，通過求取兩個(gè)面實(shí)體的重疊面積比來判別其匹配的可能性，由于需要重復(fù)計(jì)算面實(shí)體重疊面，運(yùn)算量較大且容易出現(xiàn)誤匹配現(xiàn)象.文獻(xiàn)[3]提出一種基于面實(shí)體形狀中心距離差異的匹配方法，對(duì)要素節(jié)點(diǎn)位置依賴較大，精度不高.文獻(xiàn)[4]通過一種基于拱高半徑的傅里葉形狀描述子進(jìn)行面實(shí)體形狀描述，采用綜合相似度進(jìn)行要素匹配，較好的對(duì)面實(shí)體進(jìn)行描述，但該方法涉及大量運(yùn)算，耗時(shí)較長.文獻(xiàn)[5]提出基于重心射線的實(shí)體描述方法來進(jìn)行面實(shí)體匹配，適用于簡單面實(shí)體匹配，對(duì)復(fù)雜面實(shí)體之間匹配精度不高.

現(xiàn)實(shí)生產(chǎn)中，面狀實(shí)體要素形狀復(fù)雜程度不一，而現(xiàn)有匹配方法缺乏對(duì)形狀較為復(fù)雜的面實(shí)體要素的匹配研究，本文在綜合分析現(xiàn)有匹配方法對(duì)復(fù)雜面狀實(shí)體匹配不足的基礎(chǔ)上，提出一種基于輪廓特征點(diǎn)極坐標(biāo)的面實(shí)體匹配方法，為了兼顧匹配速度和精度，采用一種公共邊對(duì)象化的Douglas-Peucker(DP)算法對(duì)復(fù)雜面裝實(shí)體進(jìn)行形狀簡化操作，然后通過提出面實(shí)體質(zhì)心和輪廓特征點(diǎn)的極坐標(biāo)描述方法進(jìn)行匹配分析. 通過將本文方法同文獻(xiàn)中不同方法的實(shí)驗(yàn)比較分析可得，本文提出的方法能夠較好的解決復(fù)雜面實(shí)體匹配問題.

1 復(fù)雜面實(shí)體形狀匹配方法

1.1 基于改進(jìn)的Douglas-Peucker算法的形狀簡化

DP算法的基本思路：將面實(shí)體要素用一系列點(diǎn)P0，P1，…，Pn(實(shí)體的節(jié)點(diǎn))組成的集合表示. 設(shè)定簡化距離閾值為Dthreshold，求出與P0距離最大的節(jié)點(diǎn)Pk，連接P0和Pk。計(jì)算弧段P0-Pn上的節(jié)點(diǎn)到直線P0-Pn的距離Di，并選出其中距離最大的點(diǎn)Pj，如果Di大于閾值Dthreshold，保留該點(diǎn)，反之刪除. 連接節(jié)點(diǎn)P0-Pj和Pk-Pj，將原弧段分成兩段，運(yùn)用以上同樣方法對(duì)位于它們之間的節(jié)點(diǎn)進(jìn)行刪減，采用遞歸的方法，重復(fù)此操作，直至所有節(jié)點(diǎn)滿足算法要求為止[6-7]. 如圖1所示.

圖1 DP算法形狀簡化示意圖

DP算法能成功的對(duì)面實(shí)體形狀實(shí)施簡化，但由算法對(duì)實(shí)體簡化原理可知，設(shè)定的距離閾值Dthreshold對(duì)實(shí)體的簡化精度產(chǎn)生直接影響，同時(shí)由閉合曲線表示的復(fù)雜多邊形可能存在相鄰等拓?fù)潢P(guān)系，在應(yīng)用DP算法對(duì)存在拓?fù)潢P(guān)系的復(fù)雜多邊形進(jìn)行形狀簡化時(shí)，可能產(chǎn)生如圖2(b)所示的部分“裂縫”現(xiàn)象。假設(shè)兩個(gè)相鄰的多邊形A1和A2，如圖2(a)所示：設(shè)定距離閾值為Dthreshold對(duì)多邊形A1選擇節(jié)點(diǎn)2和節(jié)點(diǎn)6作為起始點(diǎn)和終點(diǎn)，對(duì)多邊形A2選擇節(jié)點(diǎn)18和節(jié)點(diǎn)12作為起始點(diǎn)和終點(diǎn)，當(dāng)對(duì)多邊形A1圖形簡化時(shí)，公共弧段上節(jié)點(diǎn)9距離線段L2-6的距離小于Dthreshold被剔除，節(jié)點(diǎn)8距離線段L2-6大于距離閾值被保留，而對(duì)A2多邊形簡化時(shí)，節(jié)點(diǎn)9距離線段L18-12的距離大于Dthreshold被保留，節(jié)點(diǎn)8距離線段L18-12小于距離閾值被剔除，結(jié)果導(dǎo)致簡化后的兩多邊形公共邊處出現(xiàn)“裂縫”(如圖2(b)所示).

(a)DP前兩相鄰多邊形 (b) DP后兩相鄰多邊形圖2 DP算法的缺陷

由于“裂縫”現(xiàn)象的存在，在對(duì)復(fù)雜面實(shí)體匹配過程中可能導(dǎo)致匹配錯(cuò)誤，需要對(duì)DP算法進(jìn)行改進(jìn). 因此，為了解決上述的“裂縫”問題，本文采用文獻(xiàn)[8]提出的公共邊對(duì)象化的DP改進(jìn)算法實(shí)現(xiàn).

算法基本思路：首先采用面向?qū)ο缶幊碳夹g(shù)，創(chuàng)建公共邊類和最小外接矩形方法，判斷待匹配面實(shí)體之間是否存在公共邊，若不存在，直接采用DP算法將該待匹配面實(shí)體進(jìn)行簡化；若存在，則需判斷此公共邊是否為已經(jīng)提取. 若此公共邊為首次提取，則用創(chuàng)建的公共邊類將此公共邊進(jìn)行實(shí)例化(對(duì)象化)并存入動(dòng)態(tài)數(shù)組中，然后分別對(duì)公共邊和非公共邊部分采用DP算法進(jìn)行簡化；否則，只簡化非公共邊部分，并直接將先前已簡化的公共邊替換此公共邊. 如此循環(huán)直至所有要素簡化完成. 該算法有效避免了因公共邊重復(fù)簡化所引起的“裂縫”現(xiàn)象，提高簡化效率.

1.2 基于極坐標(biāo)的形狀描述

在多邊形的形狀描述中，本文采用一種基于極坐標(biāo)的形狀描述方法. 首先對(duì)采用改進(jìn)的DP算法簡化后的面實(shí)體提取節(jié)點(diǎn)和均勻采樣點(diǎn)作為面實(shí)體的輪廓特征點(diǎn)，然后分別由面實(shí)體的幾何中心(質(zhì)心)向特征點(diǎn)引向量得到特征向量集；最后分別統(tǒng)計(jì)節(jié)點(diǎn)向量集的距離ρ和方向α得到極坐標(biāo)(ρ，α)，(圖3(a))和均勻采樣點(diǎn)的向量集的距離ρ和方向β得到極坐標(biāo)(ρ，β)(圖3(b))，根據(jù)極坐標(biāo)來描述目標(biāo)形狀.

1.2.1 輪廓特征點(diǎn)的提取

面實(shí)體節(jié)點(diǎn)最能表述實(shí)體輪廓，提取面實(shí)體節(jié)點(diǎn)，并單獨(dú)保存至數(shù)組，同時(shí)對(duì)面實(shí)體輪廓采用均勻插值的方式得到均勻采樣點(diǎn)，并單獨(dú)保存至數(shù)組。提取均勻采樣點(diǎn)：首先計(jì)算面實(shí)體周長L，選取實(shí)體上節(jié)點(diǎn)坐標(biāo)pi(xi,yi)中yi值最大的節(jié)點(diǎn)，記為p0(x0,y0)，作為均勻采樣的起始點(diǎn)，根據(jù)面實(shí)體周長L，設(shè)定采樣距離閾值，對(duì)面實(shí)體輪廓等距離采樣，提取采樣點(diǎn).

1.2.2 特征向量集和特征點(diǎn)極坐標(biāo)表示

為了計(jì)算特征向量集，需要計(jì)算面實(shí)體的幾何中心O(本文采用質(zhì)心)，其定義如下：

(1)

其中(xi,yi)為面實(shí)體輪廓特征點(diǎn)坐標(biāo)，m為特征點(diǎn)的個(gè)數(shù).

特征向量定義為由質(zhì)心向特征點(diǎn)所引的向量，所有特征向量的集合成為特征向量集[9]. 選取質(zhì)心為極坐標(biāo)原點(diǎn)，X軸方向?yàn)闃O坐標(biāo)正方向，逆時(shí)針方向?yàn)榻嵌鹊恼较?，將面?shí)體上所有特征點(diǎn)用極坐標(biāo)方式表示.

(a)節(jié)點(diǎn)極坐標(biāo)表示 (b) 采樣點(diǎn)極坐標(biāo)表示 (c) 面實(shí)體相似度度量圖3 面實(shí)體極坐標(biāo)表示

1.2.3 面實(shí)體匹配方法

面實(shí)體之間的相似度用待匹配實(shí)體特征點(diǎn)與相應(yīng)候選匹配實(shí)體的輪廓交點(diǎn)之間的距離差異量度[10]，如圖3(c)所示，基于面實(shí)體A和面實(shí)體B形狀匹配，從面實(shí)體A中心點(diǎn)(質(zhì)心)出發(fā)連接輪廓特征點(diǎn)PAi，旋轉(zhuǎn)角為θi，并與實(shí)體B輪廓邊界相交，交點(diǎn)為PBi，計(jì)算PAi和PBi與原點(diǎn)的距離分別為DA(θi)=ρAi和DB(θi)=ρBi，將面實(shí)體A和B在θi方向上的距離差異DA-B(θi)=ρAi-ρBi作為相似性特征，則它們?cè)讦萯方向上的相似度為：

(2)

面實(shí)體輪廓由一系列的輪廓特征點(diǎn)表示(節(jié)點(diǎn)和均勻采樣點(diǎn))，通過統(tǒng)計(jì)方法分別計(jì)算實(shí)體A和B在節(jié)點(diǎn)和均勻采樣點(diǎn)的相識(shí)度：

(3)

(4)

則面實(shí)體A和B綜合相似度定義如下：

(5)

公式(5)中ω為節(jié)點(diǎn)描述實(shí)體形狀的權(quán)值，面實(shí)體形狀描述過程中，由于節(jié)點(diǎn)位置更能表現(xiàn)實(shí)體輪廓信息，ω取值應(yīng)當(dāng)滿足ω值大于0.5(本文實(shí)驗(yàn)中ω取值為0.65). 由公式(5)可得，Sim(A,B)值越接近于1，表明面實(shí)體之間相似度越高.

2 實(shí)驗(yàn)與分析

2.1 面實(shí)體形狀簡化與分析

采用上述改進(jìn)的DP算法對(duì)圖4(a)數(shù)據(jù)進(jìn)行形狀簡化實(shí)驗(yàn)，設(shè)定簡化閾值Dthreshold分別為5m、10m和20m，其簡化效果圖如圖4所示.

通過采用提取面實(shí)體公共邊對(duì)象化的方法對(duì)簡化算法改進(jìn)之后，很好的解決了常規(guī)DP算法在進(jìn)行形狀簡化時(shí)產(chǎn)生的“裂縫”現(xiàn)象. 利用本文提出的基于極坐標(biāo)的形狀描述方法，對(duì)比原要素與簡化閾值Dthreshold分別為5m、10m和20m的簡化后要素的面積匹配和周長匹配距離(如表1所示)，并將簡化后的匹配閾值設(shè)定為0.85，可以看出，通過形狀簡化，面要素節(jié)點(diǎn)數(shù)大幅度減少，要素的面積和周長在5m和10m的簡化閾值下可以滿足匹配要求.

圖4 形狀簡化效果圖

表1 形狀簡化實(shí)驗(yàn)效果圖

匹配要素編號(hào)節(jié)點(diǎn)簡化后節(jié)點(diǎn)采樣點(diǎn)周長/m周長匹配面積/m2面積匹配原要素A1238238752327.7831.0000014167.7321.00000A2274274662071.2821.0000011683.6821.000005m簡化A1238103732163.3290.9295214301.8210.99063A2274117641896.6380.9154911769.2350.9926910m簡化A123872692028.5780.8715014037.2900.99082A227478611768.2660.8536911551.7230.9887020m簡化A123848631945.0520.8358413624.6570.96167A227443551687.2130.8145811202.5330.95883

2.2 面實(shí)體形狀匹配與分析

2.2.1 形狀匹配

本文以山東某地區(qū)2006年與2012年的圖斑(如圖5所示)要素進(jìn)行形狀匹配，采用ArcGIS Engine10.1與VS.Net 2010為開發(fā)平臺(tái)，進(jìn)行形狀匹配實(shí)驗(yàn)(表2). 為了兼顧匹配速度和正確率，本文將改進(jìn)后的DP 算法簡化閾值Dthreshold設(shè)為8m，特征采樣點(diǎn)定義為從起始點(diǎn)(節(jié)點(diǎn)中yi值最大的點(diǎn))，沿面實(shí)體周長順時(shí)針方向每30m插入一個(gè)采樣點(diǎn)，并將實(shí)體匹配閾值設(shè)置為0.85.

為了更直觀地體現(xiàn)匹配效果，將本文方法與文獻(xiàn)[2]和文獻(xiàn)[3]的方法在匹配時(shí)間和效率上進(jìn)行比較，比較結(jié)果見表3.

圖5 匹配實(shí)例

表2 要素匹配

算法類型要素編號(hào)節(jié)點(diǎn)數(shù)簡化后節(jié)點(diǎn)采樣點(diǎn)匹配度算法時(shí)間/s是否匹配本文算法A11與A21B13與B25C3與D17A11∶67213488A21∶65811889B13∶726107101B25∶68411293C3∶4607354D17∶47180540.982010.536匹配0.725720.654不匹配0.974290.347匹配

表3 匹配算法對(duì)比

算法類型要素編號(hào)匹配度算法時(shí)間/s是否匹配文獻(xiàn)[2]算法A11與A210.987531.092匹配B13與B250.854071.120匹配C3與D170.988600.608匹配文獻(xiàn)[3]算法A11與A210.908550.391匹配B13與B250.637220.419不匹配C3與D170.880570.248匹配

2.2.2 分析

文獻(xiàn)[2]算法通過計(jì)算面實(shí)體形狀的重疊面積來描述要素相似性，由于重復(fù)計(jì)算面要素之間的面積重疊度，計(jì)算量較大，耗時(shí)較多，從表2和表3可以看出，本文算法在匹配速度上明顯優(yōu)于文獻(xiàn)[2]算法，并且當(dāng)兩面要素形狀接近時(shí)，文獻(xiàn)[2]算法會(huì)出現(xiàn)錯(cuò)誤匹配現(xiàn)象，如本文中的B13和B25要素匹配. 文獻(xiàn)[3]算法通過計(jì)算比較幾何中心的差異來描述形狀之間的相似度，模型描述相對(duì)簡單，計(jì)算量較小，算法在匹配速度上明顯占優(yōu)，由于此算法中要素幾何中心對(duì)節(jié)點(diǎn)坐標(biāo)依賴性較大，節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)位置的變化對(duì)幾何中心的坐標(biāo)都會(huì)產(chǎn)生較大的影響，比較表2和表3中算法的匹配度，算法[3]的匹配精度明顯較低，如果本文中提高設(shè)定匹配閾值至0.90，文獻(xiàn)[3]算法就會(huì)出現(xiàn)錯(cuò)誤匹配情況. 綜合比較，本文算法在匹配速度和準(zhǔn)確率上都具有優(yōu)勢.

3 結(jié)束語

面狀實(shí)體匹配是矢量要素匹配中重要的組成部分，其匹配效果直接影響到數(shù)據(jù)集成和更新的效果,具有相鄰等拓?fù)潢P(guān)系的復(fù)雜面實(shí)體匹配是矢量匹配的重點(diǎn)和難點(diǎn)問題[10]. 本文采用一種公共邊對(duì)象化的DP算法對(duì)復(fù)雜面實(shí)體進(jìn)行形狀簡化，較好的解決了常規(guī)DP算法在形狀簡化時(shí)產(chǎn)生的“裂縫”現(xiàn)象，提升了匹配速度，并提出一種基于極坐標(biāo)的實(shí)體輪廓特征點(diǎn)的形狀相似度度量方法，較好的解決了匹配的準(zhǔn)確率問題. 最后，通過將本文方法與不同匹配方法的比較分析可得，本文方法在匹配的速度和準(zhǔn)確率上都具優(yōu)勢，說明本文的方法是可行的.

[1]張橋平,李德仁,龔健雅.城市地圖數(shù)據(jù)庫面實(shí)體匹配技術(shù)[J].遙感學(xué)報(bào),2004,8(02): 107-112.

[2]吳建華,傅仲良.數(shù)據(jù)更新中要素變化檢測與匹配方法[J].計(jì)算機(jī)應(yīng)用,2008(06):1612-1615.

[3]郝燕玲,唐文靜,趙玉新,等.基于空間相似性的面實(shí)體匹配算法研究[J].測繪學(xué)報(bào),2008(04):501-506.

[4]付仲良,逯躍鋒.一種基于拱高半徑復(fù)變函數(shù)的面實(shí)體匹配算法[J].計(jì)算機(jī)應(yīng)用研究, 2012(09):3303-3306.

[5]鄭宇志,張青年. 基于拓?fù)浼翱臻g相似性的面實(shí)體匹配方法研究[J]. 測繪科學(xué)技術(shù)學(xué)報(bào), 2013,30(5): 510-514.

[6]DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[7]YU J, CHEN G, ZHANG X, et al. An improved Douglas-Peucker algorithm aimed at simplifying natural shoreline into direction-line[C]//Geoinformatics (GEOINFORMATICS), 2013 21st International Conference on. IEEE, 2013:1-5.

[8]謝亦才,李巖. Douglas-Peucker算法在無拓?fù)涫噶繑?shù)據(jù)壓縮中的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2009(32):189-192.

[9]CERRI A, FABIO B D. Comparing shapes through multi-scale approximations of the matching distance[J]. Computer Vision & Image Understanding, 2014, 121(121): 43-56.

[10]ALT H, BEHRENDS B, BL?MER J. Approximate matching of polygonal shapes[J]. Annals of Mathematics and Artificial Intelligence, 1995, 13(3-4): 251-265.

(編輯：姚佳良)

A matching method of complex vector polygon elements

ZHANG Jia-xin, HAN Bao-min, LU Yue-feng, YAN Huai-cheng

(School of Civil and Architectural Engineering,Shandong University of Technology, Zibo 255049, China)

Aiming at the problem of the method of complex vector polygon matching, a named common boundary objected Douglas-Peucker improved algorithm is adopted to compress the polygon elements, then extracted feature points of elements profile which consist of the nodes of polygon and uniform sampling points based on the polygon perimeter. Polar coordinates is exploited to shape description through features points, and computed the distance difference of nodes and sampling points of elements, respectively, then obtained the comprehensive difference as the final matching standards. Experiments shows that the method effectively improved the matching speed and accuracy of the complex vector polygon elements.

vector matching; Douglas-Peucker algorithm; polar coordinates; feature points; matching distance

2016-12-15

張家新，男，935290034@qq.com

1672-6197(2017)05-0065-05

P228.4

A