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

王笑天++呂海洋

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

關鍵詞關鍵詞：道格拉斯-普克算法；數據壓縮；第一特征點；壓縮比；計算效率

DOIDOI：10.11907/rjdk.162052

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2016）011006803

0 引言

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

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

1 道格拉斯-普克算法

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

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

2 改進算法

2.1 改進算法描述

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

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

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

2.2 性能比較

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

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

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

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

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

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

3 仿真實例

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

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

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

4 結語

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

參考文獻：

[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].測繪與空間地理信息，2006，29（2）：122124.

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

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

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

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

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

（責任編輯：杜能鋼）