王笑天++呂海洋

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

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

DOIDOI：10.11907/rjdk.162052

中圖分類號(hào)：TP312

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

0 引言

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

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

1 道格拉斯-普克算法

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

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

2 改進(jìn)算法

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

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

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

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

2.2 性能比較

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

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

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

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

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

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

3 仿真實(shí)例

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

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

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

4 結(jié)語(yǔ)

本文介紹了傳統(tǒng)的道格拉斯-普克算法原理及其在曲線圖形壓縮方面的應(yīng)用。提出曲線第一特征點(diǎn)概念，并基于第一特征點(diǎn)對(duì)傳統(tǒng)算法進(jìn)行改進(jìn)，以較小的壓縮比性能損失為代價(jià)，顯著提升了算法的計(jì)算效率。實(shí)例仿真證明了改進(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ù)壓縮算法實(shí)現(xiàn)及評(píng)析[J].測(cè)繪與空間地理信息，2006，29（2）：122124.

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

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

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

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

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

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