付仲良，邵世維

(1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢430079;

2.武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北武漢430079)

復(fù)雜面狀矢量要素快速形狀匹配方法

付仲良1，2，邵世維1

(1.武漢大學(xué) 遙感信息工程學(xué)院，湖北 武漢430079;

2.武漢大學(xué)測繪遙感信息工程國家重點實驗室，湖北武漢430079)

矢量要素匹配是數(shù)據(jù)庫合并和數(shù)據(jù)更新的核心問題。在分析現(xiàn)有匹配方法不足的基礎(chǔ)上，針對復(fù)雜面狀要素匹配問題，提出先對復(fù)雜面要素進(jìn)行基于Douglas-Peucker方法的形狀簡化，然后對簡化后的形狀再進(jìn)行形狀匹配。其中，形狀匹配通過正切空間的方法對要素進(jìn)行描述，然后利用形狀匹配距離計算出形狀差異。通過試驗表明該方法能夠有效提高矢量形狀匹配的速度以及正確率，較好地解決復(fù)雜情況面要素匹配的問題。

矢量匹配;形狀特征;空間相似性;Douglas-Peucker;正切空間

一、引 言

矢量要素的匹配是通過對目標(biāo)實體的幾何、拓?fù)浜驼Z義的相似性度量，識別出同一地區(qū)不同來源的空間數(shù)據(jù)集中的同一地物，從而建立兩個空間數(shù)據(jù)集之間同名目標(biāo)的聯(lián)系，并探測出不同空間數(shù)據(jù)集之間的差異或變化［1］。

矢量要素的匹配方法按照判別依據(jù)一般分為幾何匹配、拓?fù)淦ヅ浜驼Z義匹配。拓?fù)淦ヅ鋵儆谌鯒l件匹配，微小的差異都將導(dǎo)致匹配失敗;語義匹配常常依賴于數(shù)據(jù)模型、屬性數(shù)據(jù)類型及數(shù)據(jù)完整性，它們都不足以確定兩個面實體為同名實體，所以實際應(yīng)用中通常使用幾何匹配進(jìn)行目標(biāo)之間的相似識別。矢量要素的幾何匹配是通過計算參照目標(biāo)與源目標(biāo)之間的幾何相似度進(jìn)行的一種匹配方法。現(xiàn)階段針對面實體的幾何相似度提出一些解決方法，如文獻(xiàn)［2］根據(jù)兩個面目標(biāo)的重疊面積比值來計算其匹配的可能性，但會出現(xiàn)誤匹配的情況;文獻(xiàn)［3］通過傅里葉形狀描述子，來進(jìn)行多邊形形狀比較以及形狀查詢，但涉及大量運算并且匹配效率不高;文獻(xiàn)［4］提出基于空間實體特征(位置、形狀及大小)的相似性確定同名面實體匹配總相似度的方法，這種方法利用計算向量間絕對距離的方式來計算形狀相似度，但未考慮向量、數(shù)量不一致等情況。

為了提高面要素匹配的效率，同時又兼顧匹配的準(zhǔn)確度，首先將復(fù)雜面要素進(jìn)行形狀簡化，這樣既能降低噪聲的影響，又能排除不重要的形狀特征，保留其重要特征，從而提高匹配的速度;在形狀匹配時，利用正切空間的形狀描述方法對簡化后的要素進(jìn)行描述，然后利用形狀匹配距離再計算出形狀差異值。

二、復(fù)雜面狀矢量要素快速匹配方法

1.基于Douglas-Peucker的復(fù)雜面要素形狀簡化

定義:設(shè)簡化距離閾值為T;C為實平面上的閉合多邊形，P0，P1，…，Pn為該閉合多邊形上頂點，并沿順時針方向分布。計算出與P0距離最長的頂點Pk(如有幾個最長值取k值最小的Pk)，連接P0與Pk。利用直線P0Pk分別對兩段復(fù)合線P0－Pk和Pk－Pn上的節(jié)點計算到直線P0Pk的距離Di，選取其中距離最大的點Pj，如果Di大于限差閾值，則保留點，反之剔除該點。利用保留的最大距離點Pj將原復(fù)合線分為兩段，并用同樣的方法對位于它們之間的節(jié)點進(jìn)行檢測，重復(fù)此操作，直至節(jié)點到兩端點連線的距離最大值小于限差閾值為止，如圖1所示。

圖1 基于Dauglas-Peucker的形狀簡化

2.面要素形狀描述方法

假設(shè)多邊形的某一頂點作為參考點P0，θ1表示起始邊P0P1的方位角，φ1表示從起始邊P0P1到P1P2的轉(zhuǎn)角，φk表示沿著 Pk－1Pk到 PkPk+1的轉(zhuǎn)角，多邊形的正切空間形狀描述函數(shù)為θ(l)，x軸代表從起點P0沿著多邊形周邊到多邊形上各點Pk的歸一化距離，y軸代表各點沿著周邊的轉(zhuǎn)角(以順時針為正方向)的累加 θk= θk－1+φk+1(k=3，4，…，n)，如圖2(a)所示。由于不同起始點、不同的方向所得到的面實體正切空間函數(shù)不同，在源匹配多邊形中，定義P0(x0，y0)為起始點，其中x0=max{x|(xi，yi) ∈ A} ，y0=min{y|x=x0，(xi，yi)∈A}。從起始點P0沿著多邊形順時針旋轉(zhuǎn)方向為正方向，P0P1為起始方向線。以P0為原點、距離閾值T為半徑搜索包含在圓內(nèi)的目標(biāo)多邊形B的節(jié)點集合Q，選取與P0P1的方位角θ1差異最小的結(jié)點為目標(biāo)匹配多邊形的起始點P0'(如圖2(b)所示)。

圖2 基于正切空間的形狀描述函數(shù)

3.面要素形狀匹配方法

通過以上的形狀描述方法對多邊形A、B要素進(jìn)行形狀描述，將其形狀化為正切空間表達(dá)式，分別為θA(l)和θB(l)，其中s為x軸坐標(biāo)，θ為y軸坐標(biāo)。通過計算兩個矢量要素之間的形狀匹配距離來確定它們的相似性，進(jìn)而判斷兩要素是否匹配。定義其匹配距離為DAB的值越趨近于1，表示多邊形A和B的形狀越相似，匹配的程度越好。

三、試驗與結(jié)論

1.形狀簡化試驗與分析

采用上述方法對圖3中數(shù)據(jù)進(jìn)行形狀簡化試驗，給出一個簡化效果示意圖(簡化閾值分別為8 m、10 m和15 m)。

圖3 形狀簡化效果

利用文中基于正切空間的形狀描述函數(shù)，對比原要素與三種簡化后要素的形狀匹配距離、面積匹配距離和周長匹配距離(如表1所示)，可以看出，通過形狀簡化，要素節(jié)點數(shù)大大減少，要素的形狀、面積、周長的變化在8 m和10 m的簡化閾值下可以滿足匹配要求。

表1 形狀簡化試驗

2.形狀匹配實例與分析

本文以某地區(qū)2003年與2008年的圖斑要素(見圖4)進(jìn)行實例匹配，采用ArcGIS Engine 9.3與VS.NET 2008為開發(fā)平臺，進(jìn)行了形狀匹配試驗(如表2、表3所示)。其中簡化閾值分別為15 m與20 m，匹配閾值選取為0.85。

通過本文方法與文獻(xiàn)［2］(利用兩個面目標(biāo)的重疊面積比值)和文獻(xiàn)［3］(利用向量間絕對距離計算的方法)進(jìn)行比較(如表3所示)。

圖4 形狀簡化效果

表2 多尺度面要素形狀匹配

表3 匹配算法比較

從表2和表3可以看出，利用本文的快速匹配方法在速度上明顯快于文獻(xiàn)［2］中的算法。文獻(xiàn)［2］中計算兩面目標(biāo)的重疊面積，會消耗太多時間，而且通過重疊面積比值的方法匹配準(zhǔn)確率不高，會出現(xiàn)誤匹配情況。而文獻(xiàn)［3］中的速度介于簡化閾值15 m和20 m之間。綜上所述，選擇適當(dāng)?shù)暮喕撝担梢悦黠@提高形狀匹配效率，并且準(zhǔn)確率高于文獻(xiàn)［2］和文獻(xiàn)［3］中的算法。

四、結(jié)束語

實體匹配是多數(shù)據(jù)源多尺度數(shù)據(jù)集成與更新的關(guān)鍵技術(shù)，匹配效果的好壞直接影響到數(shù)據(jù)集成或更新的效果。本文將形狀相似性的距離觀與形狀特征簡化相結(jié)合，以形狀匹配距離作為相似性特征，通過Douglas-Peucker算法對復(fù)雜面要素進(jìn)行簡化，大大提高了匹配速度，并提出一種基于正切空間的面狀矢量要素形狀相似性度量模型，利用形狀描述函數(shù)較好地解決了匹配的準(zhǔn)確率問題。最后通過對相同數(shù)據(jù)不同匹配算法進(jìn)行試驗比較，在匹配的速度和準(zhǔn)確率上有明顯提高，說明本文的方法是有效的。

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

［2］吳建華，付仲良.數(shù)據(jù)更新中要素變化檢測與匹配方法［J］.計算機(jī)應(yīng)用，2008，28(6):1612-1615.

［3］郝燕玲，唐文靜，趙玉新，等.基于空間相似性的面實體匹配算法研究［J］.測繪學(xué)報，2008，37(4):501-506.

［4］唐爐亮，李清泉，楊必勝.空間數(shù)據(jù)網(wǎng)絡(luò)多分辨率傳輸?shù)膸缀螆D形相似性度量［J］.測繪學(xué)報，2009，38(4):336-340.

［5］楊得志，王杰臣，閭國年.矢量數(shù)據(jù)壓縮的Douglas-Peucker算法的實現(xiàn)與改進(jìn)［J］.測繪通報，2002(7):18-20.

［6］何磊，蔣大為，周敏.基于簡化多邊形類正切空間表示的圖形漸變算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2007，19(3):304-310.

Methods of Complex Polygon Element Fast Shape Matching

FU Zhongliang，SHAO Shiwei

0494-0911(2011)03-0026-03

P208

B

2010-08-24

付仲良(1965—)，男，湖北麻城人，教授，博士生導(dǎo)師，研究方向為圖形圖像處理、GIS等。