基于形狀特征點的改進道格拉斯—普克壓縮算法

肖亞楠

【摘 要】 本文通過對傳統的矢量數據壓縮算法的分析發現，道格拉斯-普克壓縮算法在處理復雜線要素時，存在錯誤刪除特征點、存在自相交等問題；而垂距法則注重局部判斷處理，沒有從宏觀角度對整體線要素進行分析處理。基于此對道格拉斯-普克壓縮算法進行了改進，首先根據各頂點處的形狀參數大小，提取特征點，然后以各特征點為分界點對線要素進行分段，最后使用道格拉斯普克算法對各分段進行處理。文中使用矢量數據對算法進行了驗證，并與傳統矢量壓縮算法的處理結果進行了比較，發現改進后的算法在處理復雜線要素時具有更高的準確性。

【關鍵詞】 矢量數據 數據壓縮 道格拉斯-普克壓縮算法 形狀特征點

1 引言

地理數據的有效獲取與處理，一直以來都是進行GIS工程建設以及地圖制圖的重要基礎性工作，地理數據的數量以及處理質量將直接影響后續的數據分析與應用工作。

本文分析了傳統矢量數據壓縮算法的優缺點，融入了線要素形狀特征的思想，對道格拉斯-普克算法進行了改進，并對改進后的算法進行了實驗驗證。

2 傳統矢量數據壓縮算法

矢量數據壓縮是在保證信息量的前提下，盡可能的減少表達信息所需要的數據量。矢量數據壓縮的方法一是降低數據精度，二是減少構成線要素的數據點。前者在精度要求較高的應用中不適用，后者常見算法有間隔點刪除法、光欄法、垂距法，以及最為經典的道格拉斯-普克算法（Douglas-Peucker algorithm）。

間隔點刪除法沒有考慮各頂點之間的關系，僅按照間隔進行數據刪除，精度保持效果較差；垂距法和光欄法均為局部算法，僅考慮局部頂點之間的位置關系，沒有考慮到線要素的整體性，并且在數據量大的情況下，對精度的保持效果有所下降。

道格拉斯-普克算法綜合考慮了線要素的整體特征，通過計算線要素各中間頂點到首尾頂點連線的距離，比較最大距離值與閾值的大小，若小于閾值，則刪除所有中間點；若大于閾值，則以距離最大點為分界點，將線要素分割為前后兩段。對分段后的線要素重復上述操作，直到線要素無法再分割為止。具體實現如圖1所示。

道格拉斯-普克算法的原理簡單、操作效率高，且從線要素整體入手，考慮了線要素的整體特性，利用特征點對線要素進行分段處理，在一定程度上同時兼顧了線要素的局部特征，在矢量數據壓縮中有很強的可取性。但是在處理復雜線要素時，可能會出現自相交、線要素形狀難以保持等情況，壓縮效果不佳。

3 基于形狀特征點的道格拉斯-普克壓縮算法

3.1 曲率等形狀參數及其相關概念

曲率用于衡量幾何體的不平坦程度[2]。從數學角度上講，曲率表示曲線偏離直線的程度，是曲線上某一點的切線方向角對弧長的轉動率。通過微分定義，即W=dC/dL，其中W表示曲線上某一點的曲率，dC表示該點處切線與其臨近點處切線的夾角，dL表示該點與其臨近點間的弧長。

在矢量數據空間中，曲線由若干個頂點表示，無法使用一般意義上的曲率定義表示，本文參照數學定義，將Pi點處的轉角和曲率分別定義為

C=arccos，公式（1）

W=C/L，公式（2）

其中，Pi-1、Pi+1分別為與Pi點相鄰的前、后頂點，C為Pi點處的轉角，W為Pi點處的曲率，L為、Pi-1、Pi、Pi+1間的弧長（即兩線段總長）。曲率同時考慮了轉角大小與對應弧段的長度，是曲線在某一點處彎曲程度的定量表示[3]，其值越大，表示曲線的彎曲程度越大。

彎曲度和頂點形狀指數也是描述現狀物體彎曲程度的重要參數。彎曲度為觀測線長與兩端點間距離的比值，即

Bi=Li/Si，公式（3）

公式（4）

Bi為曲線的彎曲度，Li為觀測點到相鄰兩點間的距離和，Si為與觀測點相鄰的兩點間距離[1]。Ji為觀察頂點的形狀指數，W為該點處轉角。彎曲度越大，表示曲線性越好，反之則直線性越好；當頂點處的轉角一定時，與其相鄰的兩端臂長越長，則形狀指數越大，表示對區域范圍內的曲線影響越大，也即形狀貢獻率越高。

3.2 形狀特征點的提取

曲率等形狀參數可以用來衡量圖形局部變化程度，則形狀特征點就是復雜圖形局部變化劇烈的頂點，這些頂點在矢量數據壓縮時應該保留。為了曲率特征點的提取過程如下：

1對線要素的構成頂點進行排序，并依次計算各頂點的曲率Wi、彎曲度Li及形狀指數Ji，并計算其平均值Wc、Lc、Jc。

2從曲率、彎曲度、形狀指數三個方面對頂點進行觀察：首先將Wc作為曲率閾值，比較選定頂點曲率值與閾值的大小，若大于閾值，則保留該頂點；其次將Lc作為彎曲度閾值，比較選定頂點彎曲度值與閾值的大小，若大于閾值，則保留該頂點；最后將Jc作為形狀指數的閾值，比較選定頂點形狀指數與閾值的大小，若大于閾值，則保留該頂點。若曲率、彎曲度、形狀指數均小于閾值，則舍棄該頂點。全部頂點處理完成后得到初步形狀特征點集。

3提取的特征點中有變化微小的頂點，這些頂點的存在對于曲線形狀的貢獻不大，需要剔除。具體做法為：連接選定特征點的兩相鄰特征點，計算該特征點到該連線的距離，若大于閾值則保留；為避免數據壓縮后出現自相交的情況，可以判斷各特征點相鄰頂點的連線與其后所有相鄰頂點的連線的相交情況，如果相交，則需要保留該頂點；若以上條件均不符合，則移除該特征點。全部處理完成后得到最終的特征點集。

3.3 基于形狀特征點的道格拉斯-普克算法

提取形狀特征點的目的是為了保持復雜圖形在數據壓縮后的形狀特征，并避免出現自相交現象。提取完成后，以特征點為分界點，將曲線分割成若干段，并對分割之后的曲線段依次進行道格拉斯-普克算法壓縮處理，也即基于形狀特征點的道格拉斯-普克算法。

4 實驗結果分析

筆者在Visual Studio 2013平臺上，使用C#語言對傳統道格拉斯-普克算法以及基于形狀特征點的道格拉斯-普克算法進行了對比實現，并在ArcGIS Desktop平臺上采集矢量線數據作為試驗數據，分別使用傳統道格拉斯-普克算法以及基于形狀特征點的道格拉斯-普克算法對數據進行處理，結果如圖2所示。

從壓縮結果的形狀也正方面分析，傳統道格拉斯-普克算法對于閾值的變化更為敏感，而基于形狀特征點的算法則對閾值的敏感度。由于先提取了待處理線段的形狀特征點，為線段構建了線段“骨架”，故無論閾值如何變化，數據壓縮結果都能保持線段的原始形狀變化特征。

從算法效率方面分析，基于形狀特征點的道格拉斯-普克算法盡管先進行了形狀特征點的提取，增加了額外的數據處理時間，但將原始線段根據提取的特征點進行分段劃分處理，降低了道格拉斯-普克算法的迭代深度，提高了算法的時間效率。

5 結論與展望

本文分析了傳統道格拉斯-普克算法的優勢及不足之處，并綜合考慮圖形的形狀特性，提取出形狀特征點集，然后以特征點為分界將圖形曲線分割為若干子曲線，并依次對其執行道格拉斯-普克算法處理。實驗證明，該算法能夠有效解決道格拉斯-普克算法在處理復雜圖形時存在的自相交及形狀失真的情況，并且在時間效率上也存在一定的優勢。

【參考文獻】

[1] ZHANG xinchang， ZENG guanghong， ZHANG qingnian. Urban Geographic Information System[M].Beijing：Science Press，2013. （張新長， 曾廣鴻， 張青年.城市地理信息系統[M]. 北京： 科學出版社， 2013. ）.

[2] GUO qingshen， YANG zuqiao， FENG ke. Extracting Topographic Characteristic Line from Contours[J].Geomatics and Information Science of Wuhan University，2008，33（3），253-256. （郭慶勝， 楊族橋， 馮科. 基于等高線提取地形特征線的研究[J]. 武漢大學學報·信息科學版， 2008， 33（3）， 253-256. ）.

[3] HU peng， YOU lian， YANG chuanyong. Map Algebra[M].Wuhan：Wuhan University Press，2002. （胡鵬， 游漣， 楊傳勇， 等. 地圖代數[M] . 武漢：武漢大學出版社， 2002）.