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

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

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

3、/p><p><b>　　Abstract</b></p><p>　　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</p><p>　　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</p><p>　　Keywords: Image Processing，Image Compression，Compression algorithm，Image Coding，Huf.fman</p><p><b>　　目錄</b></p><p>　　1．數(shù)字圖像處理概述5&l

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

9、gt;　　2.2圖像數(shù)據(jù)壓縮原理8</p><p>　　2.3．圖像壓縮編碼9</p><p>　　2.3.1霍夫曼編碼9</p><p>　　2.3.2行程編碼11</p><p>　　2.3.3算術編碼11</p><p>　　2.3.4預測編碼11</p><p>　　2.3.

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

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

12、gt;<b>　　總結(jié)31</b></p><p><b>　　參考文獻32</b></p><p><b>　　致謝34</b></p><p>　　1．數(shù)字圖像處理概述</p><p>　　1.1數(shù)字圖像處理發(fā)展概況</p><p>　　數(shù)字圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

84、tem("pause");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　3.4.2 壓縮類的實現(xiàn)</p><p>　　1.Compress()成員函數(shù)是控制文件壓縮的關鍵模塊，Huffman樹的構(gòu)造是算法的核

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

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

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

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

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

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

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

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

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

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

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

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

97、將毫無意義?；趘ector的樹使用相對地址作為指針，就回避了動態(tài)內(nèi)存地址的問題。</p><p>　?。?）調(diào)用generateCode()</p><p>　　對于每個葉節(jié)點，順著到根節(jié)點的路徑，可以判斷每個字符的bit碼。在此過程中，確定樹的代價，它是生成的位碼的總位數(shù)。</p><p>　?。?）完成所有數(shù)據(jù)收集</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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