復雜面狀矢量要素快速形狀匹配方法

付仲良，邵世維

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

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

復雜面狀矢量要素快速形狀匹配方法

付仲良1，2，邵世維1

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

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

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

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

一、引 言

矢量要素的匹配是通過對目標實體的幾何、拓撲和語義的相似性度量，識別出同一地區不同來源的空間數據集中的同一地物，從而建立兩個空間數據集之間同名目標的聯系，并探測出不同空間數據集之間的差異或變化［1］。

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

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

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

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

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

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

2.面要素形狀描述方法

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

圖2 基于正切空間的形狀描述函數

3.面要素形狀匹配方法

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

三、試驗與結論

1.形狀簡化試驗與分析

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

圖3 形狀簡化效果

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

表1 形狀簡化試驗

2.形狀匹配實例與分析

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

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

圖4 形狀簡化效果

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

表3 匹配算法比較

從表2和表3可以看出，利用本文的快速匹配方法在速度上明顯快于文獻［2］中的算法。文獻［2］中計算兩面目標的重疊面積，會消耗太多時間，而且通過重疊面積比值的方法匹配準確率不高，會出現誤匹配情況。而文獻［3］中的速度介于簡化閾值15 m和20 m之間。綜上所述，選擇適當的簡化閾值，可以明顯提高形狀匹配效率，并且準確率高于文獻［2］和文獻［3］中的算法。

四、結束語

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

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

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

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

［4］唐爐亮，李清泉，楊必勝.空間數據網絡多分辨率傳輸的幾何圖形相似性度量［J］.測繪學報，2009，38(4):336-340.

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

［6］何磊，蔣大為，周敏.基于簡化多邊形類正切空間表示的圖形漸變算法［J］.計算機輔助設計與圖形學學報，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—)，男，湖北麻城人，教授，博士生導師，研究方向為圖形圖像處理、GIS等。