畢業(yè)設計---圖像壓縮算法

上傳人：奔*** IP屬地：河北更新時間：2024-03-02 格式：doc 頁數：34 大?。?35.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩33頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　摘要　　隨著多媒體技術和通訊技術的不斷發(fā)展, 多媒體娛樂、信息高速公路等不斷對信息數據的存儲和傳輸提出了更高的要求, 也給現有的有限帶寬以嚴峻的考驗, 特別是具有龐大數據量的數字圖像通信, 更難以傳輸和存儲, 極大地制約了圖像通信的發(fā)展, 因此圖像壓縮技術受到了越來越多的關注。圖像壓縮的目的就是把原來較大的圖像用盡量少的字

2、節(jié)表示和傳輸,并且要求復原圖像有較好的質量。利用圖像壓縮, 可以減輕圖像存儲和傳輸的負擔, 使圖像在網絡上實現快速傳輸和實時處理。　　本文主要介紹數字圖像處理的發(fā)展概況，圖像壓縮處理的原理和特點，對多種壓縮編碼方法進行描述和比較，詳細討論了Huffman編碼的圖像壓縮處理的原理和應用。　　關鍵詞：圖像處理,圖像壓縮,壓縮算法,圖像編碼,霍夫曼編碼<

3、/p>　　Abstract　　With the developing of multimedia technology and communication technology, multimedia entertainment, information, information highway have kept on data

4、 storage and transmission put forward higher requirements, but also to the limited bandwidth available to a severe test, especially with large data amount of digital image communication, more difficult to transport and s

5、torage, greatly restricted the development of image communication, image compression techniques are therefore more and more atten　　This paper mainly introduces the development situation of the digita

6、l image processing, the principle and feature of image compression processing , and the variety of compression coding method was described and compared, detailedly discussed the principle and application of compression

7、processing based on Huffman　　Keywords: Image Processing，Image Compression，Compression algorithm，Image Coding，Huf.fman　　目錄　　1．數字圖像處理概述5&l

8、t;/p>　　1.1數字圖像處理發(fā)展概況5　　1.2數字圖像處理主要研究的內容6　　1.3數字圖像處理的基本特點7　　2．圖像壓縮8　　2.1圖像壓縮技術概述8<p&

9、gt;　　2.2圖像數據壓縮原理8　　2.3．圖像壓縮編碼9　　2.3.1霍夫曼編碼9　　2.3.2行程編碼11　　2.3.3算術編碼11　　2.3.4預測編碼11　　2.3.

10、5變換編碼12　　2.3.6其他編碼12　　3 哈夫曼編碼的圖像壓縮14　　3.1 需求分析14　　3.2 設計流程圖14　　3.3 哈弗曼樹的構造15　　3.4 圖像壓縮

11、的具體實現16　　3.4.1 Huffman壓縮類的接口與應用16　　3.4.2 壓縮類的實現20　　4 運行結果顯示及其分析28　　4.1 結果顯示：28　　4.2 結果分析：30<p&

12、gt;　　總結31　　參考文獻32　　致謝34　　1．數字圖像處理概述　　1.1數字圖像處理發(fā)展概況　　數字圖

13、像處理（Digital Image Processing）又稱為計算機圖像處理，它是指將圖像信號轉換成數字信號并利用計算機對其進行處理的過程。數字圖像處理最早出現于20世紀50年代，當時的電子計算機已經發(fā)展到一定水平，人們開始利用計算機來處理圖形和圖像信息。數字圖像處理作為一門學科大約形成于20世紀60年代初期。早期的圖像處理的目的是改善圖像的質量，它以人為對象，以改善人的視覺效果為目的。圖像處理中，輸入的是質量低的圖像，輸出的是改善質

14、量后的圖像，常用的圖像處理方法有圖像增強、復原、編碼、壓縮等。首次獲得實際成功應用的是美國噴氣推進實驗室（JPL）。他們對航天探測器徘徊者7號在1964年發(fā)回的幾千張月球照片使用了圖像處理技術，如幾何校正、灰度變換、去除噪聲等方法進行處理，并考慮了太陽位置和月球環(huán)境的影響，由計算機成功地繪制出月球表面地圖，獲得了巨大的成功。隨后又對探測飛船發(fā)回的近十萬張照片進行更為復雜的圖像處理，以致獲得了月球的地形圖、彩色圖及全景鑲嵌圖，獲得了非凡的

15、成果，為人類登月創(chuàng)舉奠定了堅實的基礎，也推動了數字圖像處理這門學科的誕生。在以后的宇航空間技術，如對火星、土星等星　　1.2數字圖像處理主要研究的內容　　數字圖像處理主要研究的內容有以下幾個方面：　　1) 圖像變換由于圖像陣列很大，直接在空間域中進行處理，涉及計算量很大。因此，往往采用各種圖像變換的方法，如傅立葉

16、變換、沃爾什變換、離散余弦變換等間接處理技術，將空間域的處理轉換為變換域處理，不僅可減少計算量，而且可獲得更有效的處理（如傅立葉變換可在頻域中進行數字濾波處理）。目前新興研究的小波變換在時域和頻域中都具有良好的局部化特性，它在圖像處理中也有著廣泛而有效的應用。2)圖像編碼壓縮技術可減少描述圖像的數據量（即比特數），以便節(jié)省圖像傳輸、處理時間和減少所占用的存儲器容量。壓縮可以在不失真的前提下獲得，也可以在允許的失真條件下進行。編碼是壓縮技

17、術中最重要的方法，它在圖像處理技術中是發(fā)展最早且比較成熟的技術。3)圖像增強和復原的目的是為了提高圖像的質量，如去除噪聲，提高圖像的清晰度等。圖像增強不考慮圖像降質的原因，突出圖像中所感興趣的部分。如強化圖像高頻分量，可使圖像中物體輪廓清晰，細節(jié)明顯；如強化低頻分量可減少圖像中噪聲影響。圖像復原要求對圖像降質的原因有一定的了解，一般講應根據降質過程建立"降質模型"，再采用某種濾波方法，恢復或重建原來的圖像。4)圖像分

18、割是數字圖像處理中的關鍵技　　1.3數字圖像處理的基本特點　　1）.目前，數字圖像處理的信息大多是二維信息，處理信息量很大。如一幅256×256低分辨率黑白圖像，要求約64kbit的數據量；對高分辨率彩色512×512圖像，則要求768kbit數據量；如果要處理30幀/秒的電視圖像序列，則每秒要求500kbit～22.5Mbit數據量

19、。因此對計算機的計算速度、存儲容量等要求較高。2）數字圖像處理占用的頻帶較寬。與語言信息相比，占用的頻帶要大幾個數量級。如電視圖像的帶寬約5.6MHz，而語音帶寬僅為4kHz左右。所以在成像、傳輸、存儲、處理、顯示等各個環(huán)節(jié)的實現上，技術難度較大，成本亦高，這就對頻帶壓縮技術提出了更高的要求。3）數字圖像中各個像素是不獨立的，其相關性大。在圖像畫面上，經常有很多像素有相同或接近的灰度。就電視畫面而言，同一行中相鄰兩個像素或相鄰兩行間的像

20、素，其相關系數可達0.9以上，而相鄰兩幀之間的相關性比幀內相關性一般說還要大些。因此，圖像處理中信息壓縮的潛力很大。4）由于圖像是三維景物的二維投影，一幅圖象本身不具備復現三維景物的全部幾何信息的能力，很顯然三維景物背后部分信息在二維圖像畫面上是反映不出來的。因此，要分析和理解三維景物　　數字圖像處理的再現性好，處理精度高，適用面寬，靈活性高，而圖像是人類獲取和交換信息的主要來源，因此，圖像處理

21、的應用領域必然涉及到人類生活和工作的方方面面。隨著人類活動范圍的不斷擴大，圖像處理的應用領域也將隨之不斷擴大。　　2．圖像壓縮 　　2.1圖像壓縮技術概述　　圖像壓縮就是減少表示數字圖像時需要的數據量。是指以較少的比特有損或無損地表示原來的像素矩陣的技術，也稱圖像編

22、碼。　　在我們的生活中無論是普通人還是一些工作在科研領域的科技工作者，都會對數據信息進行傳輸與存儲有所接觸。隨著數字時代的到來，影像的制作、處理和存儲都脫離了傳統(tǒng)的介質（紙、膠片等），相比傳統(tǒng)方式，數字圖像有著傳統(tǒng)方式無法比擬的優(yōu)越性。但是每種技術出現的同時，都有制約其發(fā)展的一面。比如數字電視、遙感照片、由雷達、飛機等提供的軍事偵察圖像、可視電話、會議電視和傳真照片，在教育、商業(yè)、管理等領域的圖

23、文資料、CT 機、X 射線機等設備的醫(yī)用圖像、天氣云圖等等，無論是利用哪種傳輸媒介進行傳輸的信息，都會都會遇到需要對大量圖像數據進行傳輸與存儲的問題。而對大量圖像數據進行傳輸要保證其傳輸的質量、速度等，對其進行存儲也要考慮其大小容量等。所以，要解決大量圖像數據的傳輸與存儲，在當前傳輸媒介中，存在傳輸帶寬的限制，故在一些限制條件下傳輸盡可能多的活動圖像，如何能對圖像數據進行最大限度的壓縮，并且保證壓縮后的重建圖像能夠被用戶所接受等問題，就

24、成為研究圖像壓縮技術的問題之源。　　圖像數據之所以可以進行壓縮，主要是因為一般原始圖像數據是高度相關的，都含有大量的冗余信息。圖像壓縮編碼的目的就是消除各種冗余，并在給定的畸變下用盡量少的比特數來表征和重建圖像，使它符合預定應用場合的要求。　　2.2圖像數據壓縮原理　　由于圖像數據之間存在這一定的冗余，所以使得數

25、據的壓縮成為可能。信息論的創(chuàng)始人Shannon 提出把數據看作是信息和冗余度（redundancy）的組合。所謂冗余度是由于一副圖像的各像素之間存在著很大的相關性，可利用一些編碼的方法刪去它們，從而達到減少冗余壓縮數據的目的。為了去掉數據中的冗余，常常要考慮信號源的統(tǒng)計特性，或建立信號源的統(tǒng)計模型。　　圖像的冗余包括以下幾種：　　●空間冗余：像素點之間的

26、相關性；　　●時間冗余：活動圖像兩個連續(xù)幀之間的冗余；　　●信息熵冗余：單位信息量大于其熵；　　●結構冗余：區(qū)域上存在非常強的紋理結構；　　●知識冗余：有固定的結構，如人的頭像；　　●視覺冗余：某些圖像的失真是人眼不易覺察的。&l

27、t;/p>　　對數字圖像進行壓縮通常利用兩個基本原理:一是數字圖像的相關性。在圖像的同一行相鄰象素之間，相鄰象素之間，活動圖像的相鄰幀的對應象素之間往往存在很強的相關性，去除或減少這些相關性，也即去除或減少圖像信息中的冗余度也就實現了對數字圖像的壓縮。幀內象素的相關稱做空域相關性。相鄰幀間對應象素之間的相關性稱做時域相關性。二是人的視覺心理特征。人的視覺對于邊緣急劇變化不敏感(視覺掩蓋效應)，對顏色分辨力弱，

28、利用這些特征可以在相應部分適當降低編碼精度而使人從視覺上并不感覺到圖像質量的下降，從而達到對數字圖像壓縮的目的。　　2.3．圖像壓縮編碼　　目前圖像編碼壓縮的方法很多，其分類方法根據出發(fā)點不同而有差異。根據解壓重建后的圖像和原始圖像之間是否具有誤差，圖像編碼壓縮分為無誤差編碼和有誤差編碼兩大類。無損編碼中刪除的僅僅是圖像數據中冗余的數據，經解碼重建的圖像

29、和原始圖像沒有任何失真，常用于復制、保存十分珍貴的歷史、文物圖像等場合；有損編碼是指解碼重建的圖像與原圖像相比有失真，不能精確的復原，但視覺效果基本相同，是實現高壓縮比的編碼方法，數字電視、圖像傳輸和多媒體等常采用這類編碼方法。　　圖像壓縮技術：　　A：無損壓縮：a．霍夫曼編碼 b．行程編碼 c．

30、算術編碼　　B：有損壓縮：a．預測編碼 b．變換編碼 c．其他編碼　　2.3.1霍夫曼編碼　　Huffman編碼在無損壓縮的編碼方法中，它是一種有效的編碼方法。它是霍夫曼博士在1952 年根據可變長最佳編碼定理提出的。依據信源數據中各信號出現的頻率分配不同長度的編碼。其基本思想是在編碼過程

31、中，對出現頻率越高的值，分配越短的編碼長度，相應地對出現頻率越低的值則分配較長的編碼長度，它是一種無損編碼方法。采用霍夫曼編碼方法的實質是針對統(tǒng)計結果對字符本身重新編碼，而不是對重復字符或重復子串編碼，得到的單位像素的比特數最接近圖像的實際熵值。　　例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25

32、個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對于英文中各個字母出現概率的較準確的估算，就可以大幅度提高無損壓縮的比例。　　例如：假設信源符號為【a、b、c、d、e、f、g】，其出現的概率相應的為【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7個

33、字符，對其進行huffman 編碼，算法如下：　　首先按照每個字符出現的頻率大小從左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；選出最小的兩個值作為葉子節(jié)點構成一棵二叉樹，值較大的葉子節(jié)點在左，兩個葉子節(jié)點對應的頻率之和作為根節(jié)點。把原排列中最小的兩個節(jié)點刪除，新的根節(jié)點插入排列保持大小從左到右的排列順序不變；重復執(zhí)行2），直到最后得到值為1 的根節(jié)點。得

34、到一棵huffman 樹，如下圖所示：　　圖 2.1　　在得到的huffman 樹上左分支標記1，右分支標記0，所有的字符根據其頻率標記到對應的葉子節(jié)點上，從根節(jié)點到葉子節(jié)點路徑上遇到的0、1 字符串即為對應葉子節(jié)點所在字符的編碼。a、b、c、d、e、f、g七個字符的huffman 編碼分別是：10、0001、000

35、0、0011、11、01、0010，可以看到,符號只能出現在樹葉上,任何一個字符的路徑都不會是另一字符路徑的前綴路徑。　　2.3.2行程編碼　　行程編碼又稱RLE壓縮方法，其中RLE是Run-Length-Encoding的縮寫，這種縮寫方法廣泛用于各種圖像格式的數據壓縮處理中，是最簡單的壓縮圖像方法之一。</

36、p>　　行程編碼技術是在給定的圖像數據中尋找連續(xù)重復的數值，然后用兩個字符值取代這些連續(xù)值。例如，有一串字母表示的數據為“aaabbbbccccdddedddaa”經過行程編碼處理可表示為“3a4b4c3d1e3d2a”。這種方法在處理包含大量重復信息的數據時可以獲得很好的壓縮效率。但是如果連續(xù)重復的數據很少，則難獲得較好的壓縮比。而且甚至可能會導致壓縮后的編碼字節(jié)數大于處理前的圖像字節(jié)數。所以行程編碼的壓縮

37、效率與圖像數據的分布情況密切相關。　　2.3.3算術編碼　　算術編碼與霍夫曼編碼方法相似，都是利用比較短的代碼取代圖像數據中出現比較頻繁的數據，而利用比較長的代碼取代圖像數據中使用頻率比較低的數據從而達到數據壓縮的目的。其基本思想是將被編碼的數據序列表示成0 和1 之間的一個間隔（也就是一個小數范圍），該間隔的位置與

38、輸入數據的概率分布有關。信息越長，表示間隔就越小，因而表示這一間隔所需的二進制位數就越多（由于間隔是用小數表示的）。算術壓縮算法中兩個基本的要素為源數據出現的頻率以及其對應的編碼區(qū)間。其中，源數據的出現頻率、編碼區(qū)間則決定算術編碼算法最終的輸出數據。　　2.3.4預測編碼　　預測編碼方式是目前應用比較廣泛的編碼技術之

39、一。預測編碼中典型的壓縮方法有脈沖編碼調制（PCM，Pulse Code Modulation）、差分脈沖編碼調制（DPCM，Differential Pulse Code Modulation）、自適應差分脈沖編碼調制（ADPCM，Adaptive Differential Pulse Code Modulation）等，它們較適合于聲音、圖像數據的壓縮，因為這些數據由采樣得到，相鄰樣值之間的差相差不會很大，可以用較少位來表示。通常，

40、圖像的相鄰像素值具有較強的相關性，觀察一個像素的相鄰像素就可以得到關于該像素的大量信息。這種性質導致了預測編碼技術。采用預測編碼時，傳輸的不是圖像的實際像素值（色度值或亮度值），而是實際像素和預測像素值之差，即預測誤差。預測編碼分為無失真預測編碼和有失真預測編碼。無失真預測編碼是指對預測誤差不進行量化，所以不會丟失任何信息。有失真編碼要對預測誤差進行量化處理，而量化必然要產生一定的誤差。<

41、b>　　2.3.5變換編碼　　預測編碼認為冗余度是數據固有的，通過對信源建模來盡可能精確地預測源數據，去除圖像的時間冗余度。但是冗余度有時與不同的表達方法也有很大的關系，變換編碼是將原始數據“變換”到另一個更為緊湊的表示空間，去除圖像的空間冗余度，可得到比預測編碼更高的數據壓縮。　　變換編碼是將圖像時域信號變換到系數空間（頻域）

42、上進行處理的方法。在時域空間上具有很強相關的信息，在頻域上反映出在某些特定的區(qū)域內能量常常被集中在一起或者是系數矩陣的分布具有某些規(guī)律，從而可以利用這些規(guī)律分配頻域上的量化比特數而達到壓縮的目的。變換編碼的目的在于去掉幀內或幀間圖像內容的相關性，它對變換后的系數進行編碼，而不是對圖像的原始像素進行編碼。　　先對信號進行某種函數變換, 從一種信號（空間）變換到另一信號（空間）然后再對變換后的信號進

43、行編碼。比如將時城信號變換到頻域，就是因為聲音和圖像的大部分信號都是低頻信號，在頻域中信號能比較集中，換為頻域信號后再進行采樣、編碼，可以達到壓縮數據的效果。可以看出預測編碼和變換編碼相比：預測編碼主要在時空域上進行，變換編碼則主要在變換域上進行。采用變換編碼的有DEF（傅立葉變換）、DTC（離散余弦變換等）。　　2.3.6其他編碼&

44、lt;p>　　LZW 編碼：LZW（Lempel-Ziv-Welch Encoding）編碼原理是將每一個字節(jié)的值都要與下一個字節(jié)的值配成一個字符對，并為每個字符對設定一個代碼。當同樣的一個字符對再度出現時，就用代號代替這一字符對，然后再以這個代號與下個字符配對。LZW 編碼原理的一個重要特征是，代碼不僅僅能取代一串同值的數據，也能夠代替一串不同值的數據。在圖像數據中若有某些不同值的數據經常重復出現，也能找到一個代號來取代這些數據

45、串。在此方面，LZW 壓縮原理是優(yōu)于RLE 的。　　矢量量化編碼：利用相鄰圖像數據間的高度相關性，將輸入圖像數據序列分組，每一組m個數據構成m維矢量，一起進行編碼，即一次量化多個點。矢量量化編碼屬于有損壓縮編碼，它的缺點是復雜度隨矢量維數呈指數增加，數據量和計算量都很大。子帶編碼的基本思想是使用一組帶通濾波器把輸入圖像的傅立葉頻譜分成若干個連續(xù)的頻段，每個頻段稱為子帶。對每個子帶中的圖像信號采用

46、單獨的編碼方案去編碼。采用對每個子帶分別編碼的優(yōu)點是：第一，對每個子帶信號分別進行自適應控制，量化階的大小可以按照每個子帶的能量電平加以調節(jié)。具有較高能量電平的子帶用大的量化階去量化，以減少總的量化噪聲。第二，可根據每個子帶信號在感覺上的重要性，對每個子帶分配不同的位數，用來表示每個樣本值。例如，在低頻子帶中，為了保護圖像的邊緣輪廓結構，就要求用較小的量化階、較多的量化級數，即分配較多的位數來表示樣本值。而圖像中的噪聲及圖像的細節(jié)，通常

47、出現在高頻子帶中，對它分配較少的位數。第三，各子帶的量化噪聲都局限在本子帶內，即使某個子帶內的信號能量較小，也不會被其他子帶的量化噪聲掩蓋掉。　　3 哈夫曼編碼的圖像壓縮　　3.1 需求分析　　設計目標是實現Huffman壓縮的編碼器。編碼器的工作過程呢個如下；首先讀入待壓縮

48、的源文件，為保證與源文件信息完全一致，對文件的讀寫操作都用二進制文件的方式進行。與這只偶那個方式對應的是ASCII方式讀寫。然后建立并分析字母表，對讀入內存的源文件我們以字節(jié)為單元進行分析，將類型表示，其用C++內建的ＣＨＡＲ，最多將有２５６中可能的字符。我們對每種字符的出現頻度進行統(tǒng)計，以頻度作為建立Ｈuffman樹的權值。頻度表建好之后，就可以根據前述算法建立Huffman樹，對出現的每種字符進行Huffman編碼。此入時，再次讀入

49、源文件，逐字節(jié)編碼，將得到的編碼流寫入到磁盤文件。 　　可以看出編碼的核心是Huffman樹，它也是連接編碼的紐帶?？紤]到Huffman樹節(jié)點的設計。編碼時從葉節(jié)點逐步構建中間節(jié)點，到整顆樹。樹的節(jié)點應該應該包括的信息有：節(jié)點表示的字符，子字節(jié)的位置，字符出現的頻度，父節(jié)點的位置等，這些都是構造Huffman所需要的。而解碼時，我們只需要能夠根據位序列從樹的根節(jié)點循次遍歷到葉節(jié)點，葉節(jié)點保留其表

50、示的字符，這就足夠了。　　3.2 設計流程圖　　本設計目的是為了實現圖像壓縮，霍夫曼算法是實現此目的關鍵步驟。因此本設計流程圖是以霍夫曼為中心展開敘述的。流程圖如圖3-1所示。　　圖3-1流程圖

51、　3.3 Huffman數的構造　　基類設計如下：　　// NIL 表示一個空子樹　　const short NIL = -1;　　// 壓縮文件中Huffman樹的節(jié)點對象　　class

52、DiskHuffNode　　{　　public:　　// 存儲的字符　　unsigned char ch;　　//

53、子節(jié)點的指針（索引）　　short left;　　short right;　　DiskHuffNode (unsigned char c = 0, short lptr = NIL, short rptr = NIL):　　ch(c), left(lptr), right

54、(rptr)　　{}　　};　　// 單個字符的最大位碼大小　　const int MAXBITSIZE = 255;　　typedef bitset&l

55、t;MAXBITSIZE> BitCode;　　// 構建Huffman樹的節(jié)點　　// 壓縮算法使用這些屬性以及基類DiskHuffNode建立節(jié)點　　// 此類中的屬性在解壓縮算法中并不需要　　class HuffNode: public DiskHuffNod

56、e　　{　　public:　　int freq;// f字符ch的出現頻度　　int index;// 自身節(jié)點在樹中的索引　　int p

57、arent;// 自身節(jié)點的父節(jié)點　　int numberOfBits;// ch的Huffman編碼的bit數目　　BitCode bits;// 放置Huffman碼的bitset容器　　HuffNode (unsigned char c = 0, short lptr = NIL, sho

58、rt rptr = NIL,　　int f = 0, int indx = NIL, int p = 0,　　int numBits = 0, int maxSizeOfBits = MAXBITSIZE):　　DiskHuffNode(c, lptr, rptr), freq(f), index(indx),&

59、lt;/p>　　parent(p), numberOfBits(numBits), bits(0)　　{}　　// “<”和“>”運算符是構建最大優(yōu)先級隊列和最小優(yōu)先級隊列必須的　　friend bool operator< (c

60、onst HuffNode& lhs, const HuffNode& rhs)　　{　　return lhs.freq < rhs.freq;　　}　　friend boo

61、l operator> (const HuffNode& lhs, const HuffNode& rhs)　　{　　return lhs.freq > rhs.freq;　　}<

62、p>　　};　　3.4 圖像壓縮的具體實現　　3.4.1 Huffman壓縮類的接口與應用　　本設計設計了Hcompress類來執(zhí)行文件的壓縮操作，文件hufcomp.cpp是使用Hcompress類進行壓縮的主程序。　　Hc

63、ompress類的聲明如下：　　class HCompress　　{　　public:　　HCompress(const string& fname, bool v = false);&l

64、t;/p>　　// 構造函數。調用setFile() 打開源文件fname,　　// 生成二進制輸出文件并添加后綴".huf"標識，任何先前的擴展名都被替換　　// 邏輯標志v確定是否輸出進度消息　　void setFile(const string& fn

65、ame);　　// 打開源文件fname,生成二進制輸出文件以".huf"為后綴　　void compress();　　// 壓縮文件　　void dispCompRatio() const;

66、;　　// 顯示壓縮比　　int size() const;　　// 返回Huffman樹中節(jié)點數目　　void displayTree() const;　　// 顯示Huffman樹&l

67、t;p>　　// 考慮屏幕尺寸，當樹大小<= 11時推薦這樣做　　private:　　fstream source;　　fstream dest;　　// 輸入輸出流

68、;　　vector<int> charFreq, charLoc;　　// charFreq用于統(tǒng)計字符頻率　　// charLoc維護文件出現的字符在Huffman樹中的下標　　int numberLeaves;　　// numberL

69、eaves是樹的葉節(jié)點（字符節(jié)點）數目　　short treeSize;　　// 壓縮文件中Huffman樹節(jié)點數目　　vector<HuffNode> tree;　　// 存儲Huffman樹　　bool verbo

70、se;　　// 輸出進度消息否？　　unsigned long fileSize;　　// 源文件的大小　　unsigned long totalBits;　　// 源文件的壓縮鏡像中使用的總

71、bits數目　　bool oneChar;　　// 樹僅有一個唯一字符么？　　bool filesOpen;　　// 源和目的文件打開了么？　　void freqAnalysis();

72、// 判斷源文件中字符頻度并將它們存儲到charFreq　　// 同時確定numberLeaves，并列出fileSize　　// 這樣我們可以看出壓縮算法的效果　　void buildTree();　　// 構造Huffman樹

73、;　　void generateCodes();　　// 對每個葉節(jié)點，沿Huffman樹上溯以確定每個字符的Huffman碼 　　// 并計算被壓縮數據的總位數　　void writeCompressedData();　　// 再次讀入源文件&l

74、t;p>　　// 并將依據Huffman樹指定的Huffman碼寫到流dest中　　void mem_to_file(bit_vector& bv,fstream& ostr);　　// 將二進制bit序列從內存?zhèn)鬟f到文件中　　void treeData();<

75、p>　　// 輸出Huffman樹數據　　};　　Hcompress類得對象的構造函數有一個參數用來指定被壓縮文件的源文件名。構造函數生成的類對象先打開源文件fname，創(chuàng)建一個擴展名為.huf的二進制輸出文件。對象創(chuàng)建后，當需要用同一對象壓縮另一個文件時，可以用新文件名再次調用setFile()公共成員函數。

76、公共成員函數compress()執(zhí)行壓縮步驟。為獲取壓縮進程的一些內部參數，本設計提供了disCompRatio()，用來顯示源文件大小，壓縮文件大小和壓縮比。　　Hcompress類對象的應用代碼示例如下：　　#include <iostream>　　#include <iomanip>

77、//For setpricision　　#include <string>　　#include "HCompress.h"// HCompress class　　using namespace std;　　int main()&l

78、t;/p>　　{string fileName;　　bool verbose;　　char response;　　// prompt for the source file name and whether　　// to use the ve

79、rbose option for Huffman compression　　cout << "請輸入源文件名: ";　　cin >> fileName;　　cout << "顯示進程狀態(tài)消息否？ (y or n): ";

80、;　　cin >> response;　　if (response == 'y')　　verbose = true;　　else　　verbose = false;

81、　　cout << endl;　　// declare an HCompress object　　HCompress hc(fileName, verbose);　　// compress the file　　hc.compress();

82、　　// output the compression ratio　　hc.dispCompRatio();　　if (hc.size() <= 11)　　{　　// display t

83、he Huffman tree if the tree is small　　cout << "Huffman 樹為：" << endl;　　hc.displayTree();　　}　　sys

84、tem("pause");　　return 0;　　}　　3.4.2 壓縮類的實現　　1.Compress()成員函數是控制文件壓縮的關鍵模塊，Huffman樹的構造是算法的核

85、心功能所在。本設計就從這兩點出發(fā)考慮Huffman壓縮類得實現。　　Compress()成員函數的定義如下：　　void HCompress::compress()　　{　　int i;</

86、p>　　DiskHuffNode tmp;　　if (verbose)　　cout << "源文件字符集頻度分析中 ..." << endl;　　// 執(zhí)行頻度分析

87、;　　freqAnalysis();　　if (verbose)　　cout << "構造Huffman樹中 ..." << endl;　　// 構建Huffman樹　　buildTree();<p

88、>　　if (verbose)　　cout << "生成Huffman碼中 ..." << endl << endl;　　// 為每個字符生成Huffman碼，并計算壓縮字符中的總字符數目　　generateCodes();&l

89、t;p>　　// 如果選擇verbose，此時樹已生成，可以輸出樹數據　　if (verbose)　　treeData();　　if (verbose)　　cout << "生成壓縮文件中 ..." << endl <

90、;< endl;　　// 輸出樹大小　　dest.write((char *)&treeSize, sizeof(short));　　// 輸出樹：注意我們只輸出HuffNode對象的基類部分，　　// 解壓縮Huffm

91、an所需要的僅是字符和子節(jié)點指針　　for (i=0; i < treeSize; i++)　　{　　tmp = (DiskHuffNode)tree[i];　　dest.write((char *) &tmp, siz

92、eof(DiskHuffNode));　　}　　// 對于僅含有單個字符的源文件，　　// 刪除由于附加葉節(jié)點所添加到總體代價的多余位　　if (oneChar)　　totalBits--;&

93、lt;/p>　　// 輸出Huffman壓縮文件的比特總數目　　dest.write((char *)&totalBits, sizeof(unsigned long));　　// 完整讀入源文件，在Huffman樹中查找對應每個字符的Huffman碼　　// 寫入到dest文

94、件中　　writeCompressedData();　　// 關閉源文件和目的文件　　source.close();　　dest.close();　　filesOpen = false;&

95、lt;b>　　}　　它的執(zhí)行過程如下：　　調用freeAnalysis()　　讀取源文件，列出文件中每個字符出現的個數。當首次讀到一個字符時，將葉節(jié)點計數數目numberLeaves加1。算法利用葉節(jié)點數目來分配Huffman樹。另外函數也計算文件的

96、大小，以支持下面計算壓縮比的需要。　?。?）調用bulidTree ()　　為文件構造Huffman樹。為了將Huffman樹寫入到壓縮文件，如前面的需求分析中所描述那樣，我們采用基于vector實現的數。這時指針是整數索引，可任意把它理解為相對地址，而不是基于鏈表的數結構的動態(tài)生成的內存地址。動態(tài)的內存地址指向程序特定的一次運行中的內存，寫它到文件

97、將毫無意義。基于vector的樹使用相對地址作為指針，就回避了動態(tài)內存地址的問題。　　（3）調用generateCode()　　對于每個葉節(jié)點，順著到根節(jié)點的路徑，可以判斷每個字符的bit碼。在此過程中，確定樹的代價，它是生成的位碼的總位數。　　（4）完成所有數據收集

98、Huffman樹的最大節(jié)點數目為2*256-1=511。將此數值以16位整數寫入到壓縮文件中。　　（5）將Huffman樹的基類以字符流的形式寫入到壓縮文件中。　?。?）將位碼總數寫入到壓縮文件中　?。?）調用writeCompressData()　　再次讀取源文件。對每

99、個字符，將它對應的位碼寫入到壓縮文件中。　　2.構造Huffman樹　　前面部分已經設計好了樹節(jié)點的集成層次類，并詳述了構造Huffman樹的原理，現在我們從freeAnalysis（）的分析結果出發(fā)，構造Huffman樹。　　void HCompress::buildTree()<

100、p>　　{　　// 順序遍歷Huffman樹節(jié)點　　int i, nodeIndex;　　// 捕捉從優(yōu)先級隊列中出來的節(jié)點　　HuffNode x, y;　　// 最小優(yōu)先級隊列，用于

101、構建Huffman樹　　priority_queue<HuffNode, vector<HuffNode>, greater<HuffNode> > pq;　　// 處理文件僅有一個獨特字符的特殊情形　　if (numberLeaves == 1)<

102、;p>　　{　　// 設置葉節(jié)點數目為2，　　// 并在索引0或1位置添加1個葉節(jié)點　　// 因為在這些位置的字符不出現在文件中　　numberLeaves = 2;　　if (char

103、Freq[0] != 0)　　charFreq[1] = 1;　　else　　charFreq[0] = 1;　　// 記錄我們已經添加了填充節(jié)點　　oneChar = true;</p

104、>　　}　　else　　oneChar = false;　　// 樹的大小為2*numberLeaves-1　　treeSize = 2*numberLeaves -

105、1;　　tree.resize(treeSize);　　// 檢索我們構造中的樹　　nodeIndex = 0;　　// 開始構造各個葉節(jié)點　　// value = char(i)

106、　// left/right = NIL,　　// frequency = charFreq[i]　　// index = nodeIndex　　// parent, numberOfBits, maxSizeOfBits 為默認值　　// 在cha

107、rLoc中記錄葉節(jié)點的位置，將節(jié)點插入到最小優(yōu)先級隊列中　　for (i=0; i < MAXCHARS; i++)　　if (charFreq[i] != 0)　　{　　tree[nodeIndex] = HuffNode((

108、unsigned char)(i), NIL, NIL,　　charFreq[i], nodeIndex);　　pq.push(tree[nodeIndex]);　　// 記錄該葉節(jié)點的索引，用于　　// writeCompressedData()函數

109、　　charLoc[i] = nodeIndex;　　// 準備構造下一個節(jié)點　　nodeIndex++;　　}　　// 對于 numberLeaves-1 次迭代, 移除節(jié)點對,<

110、p>　　// 生成父節(jié)點, 并將父節(jié)點插入樹中　　for (i=1; i <= numberLeaves-1; i++)　　{　　// 移除頻率最低的兩個節(jié)點。它們在向量樹中對應節(jié)點的副本　　// 位置為x.index和y

111、.index　　x = pq.top();　　pq.pop();　　y = pq.top();　　pq.pop();　　// 生成父節(jié)點（內部節(jié)點），它的

112、子節(jié)點　　// 在數組樹中的索引位置為x.index和y.index，　　// 它的頻度為x和y的頻度和　　// 這個節(jié)點的索引為nodeIndex，　　// 其父節(jié)點暫時設為0　　tree[nodeIndex] = HuffNo

113、de(char(0), x.index, y.index,　　x.freq + y.freq,　　nodeIndex, 0, 0, 0);　　// 使用x.index和y.index，　　// 將nodeIndex分配為x和y的父節(jié)點成員變量的值&

114、lt;p>　　tree[x.index].parent = nodeIndex;　　tree[y.index].parent = nodeIndex;　　// 將新的父節(jié)點插入到優(yōu)先級隊列　　pq.push(tree[nodeIndex]);　　nodeIndex+

115、+;　　}　　if (verbose)　　cout << " Huffman樹的節(jié)點數目: "　　<< treeSize << endl << endl;<

116、/p>　　}　　在算法中需要注意這樣一個細節(jié)問題，即包括這樣的特殊情況：樹只包含有一個唯一的字符。在這種情兩況下，為了滿足擴展二叉樹的內部節(jié)點必須有兩個子節(jié)點的要求，此函數還須生成另外一葉節(jié)點個節(jié)點作為填充的輔助節(jié)點。函數首先生成葉節(jié)點，索引范圍為0~number-1，每個葉節(jié)點都含有字符值，它出現的頻率和節(jié)點自身的索引值，然后

117、再生成內部節(jié)點。此步需要執(zhí)行一個number-1次的循環(huán)。來自優(yōu)先隊列中的每個節(jié)點都包含自己在向量樹中的索引值，這便利了節(jié)點關系的建立，可以將索引值賦值給父節(jié)點的左指針或右指針，也能夠通過索引快速設置對應子節(jié)點的父節(jié)點屬性。　　3．生成位碼　　函數generateCode()從每個葉節(jié)點開始，沿著父節(jié)點路徑往上直到發(fā)

118、現根節(jié)點，就能夠確定每個葉節(jié)點位碼。每向上一步，如果此節(jié)點是其父節(jié)點的左子節(jié)點，就把位碼相應位設為0，如果是右子節(jié)點，則設為1。這樣發(fā)現的位碼是逆序的，當將它賦值給葉節(jié)點的位碼數據成員時，需要將位碼再次逆轉。　　4．寫位碼　　成員函數writeCompressData()參考上面已經生成的Huffman 編碼方案，實

119、現將源文件轉換為壓縮文件的過程。它首先以二進制方式再次讀入源文件，將其諸字節(jié)解釋為字符，并產生對應的壓縮編碼，此時壓縮編碼時在內存中，再將整個壓縮碼由內存轉移到磁盤文件。其代碼如下：　　void HCompress::writeCompressedData()　　{ // 用于容納壓縮文件Huffman碼的位向量<

120、p>　　bit_vector compressedData(totalBits,false);　　int bitPos, i, j;　　unsigned char ch;　　// 為源文件清除end-of-file狀態(tài)標記　　// 并將文件指針設為文件的開始位置&l

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

畢業(yè)設計---圖像壓縮算法

文檔簡介

溫馨提示

最新文檔

評論

畢業(yè)設計---圖像壓縮算法

文檔簡介

溫馨提示

最新文檔

評論

免費下載