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

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

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

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

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

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

矢量匹配；Douglas-Peucker算法；極坐標；輪廓特征點；匹配距離

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

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

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

1.1 基于改進的Douglas-Peucker算法的形狀簡化

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

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

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

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

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

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

1.2 基于極坐標的形狀描述

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

1.2.1 輪廓特征點的提取

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

1.2.2 特征向量集和特征點極坐標表示

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

(1)

其中(xi,yi)為面實體輪廓特征點坐標，m為特征點的個數(shù).

特征向量定義為由質(zhì)心向特征點所引的向量，所有特征向量的集合成為特征向量集[9]. 選取質(zhì)心為極坐標原點，X軸方向為極坐標正方向，逆時針方向為角度的正方向，將面實體上所有特征點用極坐標方式表示.

(a)節(jié)點極坐標表示 (b) 采樣點極坐標表示 (c) 面實體相似度度量圖3 面實體極坐標表示

1.2.3 面實體匹配方法

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

(2)

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

(3)

(4)

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

(5)

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

2 實驗與分析

2.1 面實體形狀簡化與分析

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

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

圖4 形狀簡化效果圖

表1 形狀簡化實驗效果圖

匹配要素編號節(jié)點簡化后節(jié)點采樣點周長/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 面實體形狀匹配與分析

2.2.1 形狀匹配

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

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

圖5 匹配實例

表2 要素匹配

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

表3 匹配算法對比

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

2.2.2 分析

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

3 結(jié)束語

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

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

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

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

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

[5]鄭宇志,張青年. 基于拓撲及空間相似性的面實體匹配方法研究[J]. 測繪科學技術(shù)學報, 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算法在無拓撲矢量數(shù)據(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