肖亞楠

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

C=arccos，公式（1）

W=C/L，公式（2）

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

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

Bi=Li/Si，公式（3）

公式（4）

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

3.2 形狀特征點(diǎn)的提取

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

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

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

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

3.3 基于形狀特征點(diǎn)的道格拉斯-普克算法

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

5 結(jié)論與展望

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

【參考文獻(xiàn)】

[1] ZHANG xinchang， ZENG guanghong， ZHANG qingnian. Urban Geographic Information System[M].Beijing：Science Press，2013. （張新長(zhǎng)， 曾廣鴻， 張青年.城市地理信息系統(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é)報(bào)·信息科學(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）.