基于第一特征點的道格拉斯—普克壓縮算法

王笑天++呂海洋

摘 要：對傳統(tǒng)的道格拉斯-普克壓縮算法進(jìn)行了分析，指出其存在迭代計算，在面對復(fù)雜曲線時可能會出現(xiàn)效率較低的情況。提出了曲線第一特征點概念，并基于第一特征點對傳統(tǒng)算法進(jìn)行改進(jìn)，既保留曲線的基本形狀，又避免在算法中出現(xiàn)迭代，以較小的壓縮比性能損失為代價，顯著提升了算法的計算效率。通過仿真實例驗證了改進(jìn)算法的可行性。

關(guān)鍵詞關(guān)鍵詞：道格拉斯-普克算法；數(shù)據(jù)壓縮；第一特征點；壓縮比；計算效率

DOIDOI：10.11907/rjdk.162052

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011006803

0 引言

數(shù)據(jù)對于圖形系統(tǒng)的重要性不言而喻。隨著現(xiàn)代數(shù)據(jù)采集技術(shù)以及存儲技術(shù)的蓬勃發(fā)展，數(shù)據(jù)的量級也逐步由原先的K、M攀升到G，甚至是T了。對于網(wǎng)絡(luò)傳輸和絕大部分界面顯示而言，必須預(yù)先對數(shù)據(jù)進(jìn)行有效壓縮，保留必要的特征信息，去除不必要的冗余。而為了保證應(yīng)用的實時性，數(shù)據(jù)壓縮計算效率也應(yīng)予以考慮。

傳統(tǒng)的道格拉斯-普克算法能夠按照預(yù)先設(shè)定的閾值對曲線圖形進(jìn)行有效壓縮[12]，但因其算法中存在迭代，所以面對復(fù)雜曲線時可能會出現(xiàn)效率較低的情況。杜婧等[3]提出了一種改進(jìn)算法，能夠避免傳統(tǒng)算法中的迭代，但是引入了累積誤差，所以不適用于平緩曲線的壓縮。王凈等[45]針對一些特殊情況，對傳統(tǒng)算法進(jìn)行了改進(jìn)，拓展了適用場景。趙永清等[67]在閾值自動化設(shè)置方面提供了一些解決思路。本文通過定義曲線特征點，對傳統(tǒng)算法進(jìn)行改進(jìn)，既保留了曲線的基本形狀，又避免了在算法中出現(xiàn)迭代，以較小的壓縮比性能損失為代價顯著提升了算法的計算效率。

1 道格拉斯-普克算法

道格拉斯-普克算法是矢量曲線壓縮的經(jīng)典算法，它從整體角度考慮一條完整曲線。首先選取曲線的兩個端點，計算端點之間各點到兩個端點所在直線的垂直距離。如果這些點到直線的垂直距離中最大值小于或等于預(yù)先設(shè)定的閾值，則認(rèn)為所有這些點都可以丟棄；若最大距離大于預(yù)先設(shè)定的閾值，則認(rèn)為該最大距離點為線段上的關(guān)鍵點，需要保留。以此點將原曲線分為兩段，對這兩段再重復(fù)之前的步驟計算垂直距離，分別檢查最大距離值是否大于預(yù)先設(shè)定的閾值，以決定是否存在需要保留的關(guān)鍵點。重復(fù)此過程直到曲線上所有點都被檢測，以確定是否丟棄或保留。

如圖1所示，壓縮A、B兩點之間的曲線。先分別計算點C、D、E、F、G到直線AB的垂直距離，通過相互比較得到最大值，找出與之對應(yīng)的極值點為點E。如果該最大值仍小于或等于預(yù)先設(shè)定的閾值，則AB之間的點都可以丟棄，即在最大誤差不超過所設(shè)閾值的情況下，A、B兩點之間的曲線可以用直線AB近似取代；否則，保留E點，將原曲線分割為AE、EB兩段。對這兩段曲線重復(fù)之前的步驟，即分別計算點C、D到直線AE和點F、G到直線EB的垂直距離，檢查最大距離值是否大于預(yù)先設(shè)定的閾值，以決定是否需要保留相應(yīng)的極值點。

2 改進(jìn)算法

2.1 改進(jìn)算法描述

傳統(tǒng)的道格拉斯-普克算法是從整體角度對曲線圖形壓縮，通過查找曲線中每一段的關(guān)鍵點，確定最終要保留的點序列。該算法雖然能夠得到最優(yōu)的壓縮結(jié)果，但是面對復(fù)雜曲線時可能會因為關(guān)鍵點較多，需要對原曲線進(jìn)行多次分段求解，從而影響計算效率。

杜婧等[3]提出了一種改進(jìn)算法，對待檢測的曲線數(shù)據(jù)點按順序依次進(jìn)行計算和比較，能夠有效避免迭代產(chǎn)生。具體算法如下：先以曲線第1點為起點，第3點為終點，計算第2點到該直線的垂直距離，若垂直距離小于或等于預(yù)先設(shè)定的閾值，則認(rèn)為第2點可以丟棄。再以第1點為起點，第4點為終點，按上述方法判斷第3點是否可以丟棄；如果第2點到第1、3兩點連線的垂直距離大于預(yù)先設(shè)定的閾值，則認(rèn)為第2點是關(guān)鍵點，需要保留。再以第2點作為新的起點，第4點作為終點，按上述方法判斷第3點是否可以丟棄或保留。重復(fù)此過程直到所有點都被檢測，確定是否丟棄或保留。該算法雖然能提高計算效率，但由于其總是在相鄰點之間計算和比較距離，所以對于緩慢變化的曲線可能會失效，造成壓縮結(jié)果嚴(yán)重失真。

本文首先定義曲線第一特征點概念，即對于任意曲線，從起點開始依次遍歷，若發(fā)現(xiàn)曲線中的某點到曲線兩端點所在直線的垂直距離大于預(yù)先設(shè)定閾值，則認(rèn)為該點是曲線的第一特征點?；诖烁拍?，提出如下改進(jìn)算法：選取曲線的兩個端點，分別記為起點和終點，由起點開始查找該曲線是否存在第一特征點。若存在，則保留該特征點，并以其為新起點，與原曲線的終點組成新曲線，再在新曲線中查找是否存在第一特征點；若不存在，則認(rèn)為該曲線內(nèi)除起點和終點外的其余各點皆可丟棄。重復(fù)此過程直到所有點都被檢測，確定是否可以丟棄或需要保留。

2.2 性能比較

以圖2所示曲線AB為例，設(shè)置允許的最大誤差為3，對傳統(tǒng)的道格拉斯-普克算法、杜婧等提出的改進(jìn)算法以及本文提出的改進(jìn)算法三者運行結(jié)果進(jìn)行比較。

傳統(tǒng)的道格拉斯-普克算法運行如下：①依次計算點C、D、E、F、G至AB所在直線的垂直距離分別為3.3、5.3、6、5.3、3.3，根據(jù)保留最大垂直距離點的原則判斷點E是需要保留的關(guān)鍵點；②將曲線AB分割為曲線AE和曲線EB；③分別計算點C、D至AE所在直線和點F、G至EB所在直線的垂直距離，發(fā)現(xiàn)都小于允許的最大誤差值3，判斷點C、D、F、G都可以丟棄。

杜婧等改進(jìn)算法運行如下：①計算點C至AD所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點C可以丟棄；②計算點D至AE所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點D可以丟棄；③計算點E至AF所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點E可以丟棄；④計算點F至AG所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點F可以丟棄；⑤計算點G至AB所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點G可以丟棄。

本文改進(jìn)算法運行如下：①計算點C至AB所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點C可以丟棄；②計算點D至AB所在直線的垂直距離，發(fā)現(xiàn)大于允許的最大誤差值3，判斷點D是曲線AB的特征點，需要保留；③將待壓縮曲線的起點更新為點D；④計算點E至DB所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點E可以丟棄；⑤計算點F至DB所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點F可以丟棄；⑥計算點G至DB所在直線的垂直距離，發(fā)現(xiàn)小于允許的最大誤差值3，判斷點G可以丟棄。

由上述分析可知，3種不同的算法會得出3種截然不同的運行結(jié)果，如圖3所示。傳統(tǒng)的道格拉斯-普克算法與本文提出的改進(jìn)算法都能將壓縮后的數(shù)據(jù)誤差控制在預(yù)先設(shè)定的范圍內(nèi)。傳統(tǒng)的道格拉斯-普克算法通過分割與遍歷查找，能夠發(fā)現(xiàn)和保留每段曲線內(nèi)的最值特征點，從而最大限度地保證曲線的基本形狀不發(fā)生明顯改變。本文提出的改進(jìn)算法雖然也能按照允許誤差保留曲線的特征點，但由于每次都用第一特征點對曲線進(jìn)行重新劃分，未對所有特征點進(jìn)行比較，所以不能保證所保留的特征點是最優(yōu)組合，有可能導(dǎo)致圖形發(fā)生一定的形變，損失一定的壓縮率。杜婧等提出的改進(jìn)算法存在誤差累積問題，由于只觀察相鄰數(shù)據(jù)點之間的波動情況，所以當(dāng)曲線單向平緩延伸時，使用該算法就會丟失特征點，進(jìn)而造成壓縮結(jié)果嚴(yán)重失真。

在計算效率方面，兩種改進(jìn)算法優(yōu)勢較為明顯。傳統(tǒng)的道格拉斯-普克算法共需要進(jìn)行9次距離計算和9次數(shù)值比較，而改進(jìn)算法都只需進(jìn)行5次距離計算和5次數(shù)值比較。隨著保留關(guān)鍵點的增多，傳統(tǒng)算法需要進(jìn)一步分割曲線，并在分割后的曲線內(nèi)進(jìn)行遍歷查找，因而其計算量會顯著增加。而改進(jìn)算法均只需對原始曲線內(nèi)各點進(jìn)行一次遍歷計算，計算量與保留的關(guān)鍵點數(shù)量無關(guān)，因而不存在類似問題。

3 仿真實例

為進(jìn)一步檢驗改進(jìn)算法的可行性，使用Matlab工具生成兩種常見的曲線，如圖4所示。

傳統(tǒng)算法和改進(jìn)算法都能根據(jù)預(yù)設(shè)的允許誤差實現(xiàn)大幅壓縮數(shù)據(jù)點數(shù)的目的。傳統(tǒng)的道格拉斯-普克算法通過分割與遍歷查找，能夠保留每段曲線的最值特征點，從而最大限度地保證圖形基本形狀不發(fā)生明顯變化。改進(jìn)算法由于無法獲取特征點的最優(yōu)組合，所以有可能導(dǎo)致圖形發(fā)生細(xì)微的形變，并且在壓縮率上也會略遜一籌。在

計算量方面，傳統(tǒng)的道格拉斯-普克算法由于存在迭代計算，其實際計算量會隨著原始數(shù)據(jù)點數(shù)和保留數(shù)據(jù)關(guān)鍵點數(shù)的增多而顯著增加，改進(jìn)算法的計算量則始終與原始數(shù)據(jù)點數(shù)在同一數(shù)量級上。因此，在面對復(fù)雜曲線時，改進(jìn)算法能夠在壓縮比性能和計算效率兩方面折衷取優(yōu)。

4 結(jié)語

本文介紹了傳統(tǒng)的道格拉斯-普克算法原理及其在曲線圖形壓縮方面的應(yīng)用。提出曲線第一特征點概念，并基于第一特征點對傳統(tǒng)算法進(jìn)行改進(jìn)，以較小的壓縮比性能損失為代價，顯著提升了算法的計算效率。實例仿真證明了改進(jìn)算法的可行性。

參考文獻(xiàn)：

[1] DOUGLAS D，PEUCKER T.Algorithms for the deduction of the number of points required to represent a digitized line or its caricature[J].Cartographer，1973，10（2）：112122.

[2] 王進(jìn)寶，劉正綱.曲線矢量數(shù)據(jù)壓縮算法實現(xiàn)及評析[J].測繪與空間地理信息，2006，29（2）：122124.

[3] 杜婧，張獻(xiàn)州.道格拉斯普克算法的改進(jìn)及其在管線制圖中的應(yīng)用[J].鐵道勘察，2008（4）：2628.

[4] 王凈，江剛武，管華.增強(qiáng)型道格拉斯—普克壓縮算法的設(shè)計與實現(xiàn)[J].北京測繪，2002（3）：1316.

[5] 趙永清，謝傳節(jié)，喬玉良，等.基于最值點的道格拉斯-普克壓縮算法[J].軟件導(dǎo)刊，2008，7（11）：6062.

[6] 趙永清.自動設(shè)置閾值的道格拉斯普克壓縮法[J].山西煤炭管理干部學(xué)院學(xué)報，2013，26（3）：120122.

[7] 于靖，陳剛，張笑，等.面向自然岸線抽稀的改進(jìn)道格拉斯—普克算法[J].測繪科學(xué)，2015，40（4）：2328.

（責(zé)任編輯：杜能鋼）