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

肖亞楠

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

【關(guān)鍵詞】 矢量數(shù)據(jù) 數(shù)據(jù)壓縮 道格拉斯-普克壓縮算法 形狀特征點

1 引言

地理數(shù)據(jù)的有效獲取與處理，一直以來都是進行GIS工程建設(shè)以及地圖制圖的重要基礎(chǔ)性工作，地理數(shù)據(jù)的數(shù)量以及處理質(zhì)量將直接影響后續(xù)的數(shù)據(jù)分析與應(yīng)用工作。

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

2 傳統(tǒng)矢量數(shù)據(jù)壓縮算法

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

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

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

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

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

3.1 曲率等形狀參數(shù)及其相關(guān)概念

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

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

C=arccos，公式（1）

W=C/L，公式（2）

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

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

Bi=Li/Si，公式（3）

公式（4）

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

3.2 形狀特征點的提取

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

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

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

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

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

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

4 實驗結(jié)果分析

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

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

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

5 結(jié)論與展望

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

【參考文獻】

[1] ZHANG xinchang， ZENG guanghong， ZHANG qingnian. Urban Geographic Information System[M].Beijing：Science Press，2013. （張新長， 曾廣鴻， 張青年.城市地理信息系統(tǒng)[M]. 北京： 科學(xué)出版社， 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]. 武漢大學(xué)學(xué)報·信息科學(xué)版， 2008， 33（3）， 253-256. ）.

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