• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2016-12-22 21:42:26王笑天呂海洋
      軟件導(dǎo)刊 2016年11期
      關(guān)鍵詞:道格拉斯壓縮比

      王笑天++呂海洋

      摘 要:對傳統(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é)任編輯:杜能鋼)

      猜你喜歡
      道格拉斯壓縮比
      最后一秒的冠軍
      幸福(2023年20期)2023-10-22 17:41:26
      為何我們今天必須聽聽弗雷德里克·道格拉斯在《合眾國的危險源頭》演說中發(fā)出的警告 精讀
      英語文摘(2022年1期)2022-02-16 01:19:06
      最后一秒的冠軍
      質(zhì)量比改變壓縮比的辛烷值測定機(jī)
      軟件(2020年3期)2020-04-20 01:45:24
      沒有過錯并不等于是對的
      幸福(2019年30期)2019-12-18 06:58:30
      發(fā)動機(jī)可變壓縮比技術(shù)的發(fā)展趨勢
      汽車文摘(2017年8期)2017-12-06 21:40:01
      可變壓縮比技術(shù)在汽油機(jī)上的應(yīng)用研究
      汽車文摘(2016年8期)2016-12-07 01:05:40
      只有你
      低溫廢氣再循環(huán)及低壓縮比對降低歐6柴油機(jī)氮氧化物排放的影響
      高幾何壓縮比活塞的燃燒室形狀探討
      鄄城县| 都安| 苍溪县| 东海县| 江安县| 陈巴尔虎旗| 桂林市| 金寨县| 德江县| 商都县| 武隆县| 玛沁县| 巴林右旗| 辽阳市| 漳州市| 建始县| 聂荣县| 阿瓦提县| 天津市| 新巴尔虎左旗| 南昌县| 武鸣县| 白朗县| 刚察县| 吴忠市| 易门县| 乐山市| 长沙县| 会昌县| 扬中市| 吉林市| 崇文区| 左贡县| 周宁县| 壶关县| 神木县| 洞口县| 本溪市| 平武县| 阜城县| 临高县|