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

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

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

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．?dāng)?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ù)字圖像處理的基本特點(diǎn)7</p><p><b>　　2．圖像壓縮8</b></p><p>　　2.1圖像壓縮技術(shù)概述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算術(shù)編碼11</p><p>　　2.3.4預(yù)測(cè)編碼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 設(shè)計(jì)流程圖14</p><p>　　3.3 哈弗曼樹(shù)的構(gòu)造15</p><p>　　3.4 圖像壓縮

11、的具體實(shí)現(xiàn)16</p><p>　　3.4.1 Huffman壓縮類的接口與應(yīng)用16</p><p>　　3.4.2 壓縮類的實(shí)現(xiàn)20</p><p>　　4 運(yùn)行結(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>　　參考文獻(xiàn)32</b></p><p><b>　　致謝34</b></p><p>　　1．?dāng)?shù)字圖像處理概述</p><p>　　1.1數(shù)字圖像處理發(fā)展概況</p><p>　　數(shù)字圖

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

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

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

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

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

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

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

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

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

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

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

24、成為研究圖像壓縮技術(shù)的問(wèn)題之源。</p><p>　　圖像數(shù)據(jù)之所以可以進(jìn)行壓縮，主要是因?yàn)橐话阍紙D像數(shù)據(jù)是高度相關(guān)的，都含有大量的冗余信息。圖像壓縮編碼的目的就是消除各種冗余，并在給定的畸變下用盡量少的比特?cái)?shù)來(lái)表征和重建圖像，使它符合預(yù)定應(yīng)用場(chǎng)合的要求。</p><p>　　2.2圖像數(shù)據(jù)壓縮原理</p><p>　　由于圖像數(shù)據(jù)之間存在這一定的冗余，所以使得數(shù)

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

26、相關(guān)性；</p><p>　　●時(shí)間冗余：活動(dòng)圖像兩個(gè)連續(xù)幀之間的冗余；</p><p>　　●信息熵冗余：?jiǎn)挝恍畔⒘看笥谄潇兀?lt;/p><p>　　●結(jié)構(gòu)冗余：區(qū)域上存在非常強(qiáng)的紋理結(jié)構(gòu)；</p><p>　　●知識(shí)冗余：有固定的結(jié)構(gòu)，如人的頭像；</p><p>　　●視覺(jué)冗余：某些圖像的失真是人眼不易覺(jué)察的。&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、子節(jié)點(diǎn)的指針（索引）</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>　　// 單個(gè)字符的最大位碼大小</p><p>　　const int MAXBITSIZE = 255;</p><p>　　typedef bitset&l

55、t;MAXBITSIZE> BitCode;</p><p>　　// 構(gòu)建Huffman樹(shù)的節(jié)點(diǎn)</p><p>　　// 壓縮算法使用這些屬性以及基類DiskHuffNode建立節(jié)點(diǎn)</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é)點(diǎn)在樹(shù)中的索引</p><p>　　int p

57、arent;// 自身節(jié)點(diǎn)的父節(jié)點(diǎn)</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>　　// “<”和“>”運(yùn)算符是構(gòu)建最大優(yōu)先級(jí)隊(duì)列和最小優(yōu)先級(jí)隊(duì)列必須的</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 圖像壓縮的具體實(shí)現(xiàn)</p><p>　　3.4.1 Huffman壓縮類的接口與應(yīng)用</p><p>　　本設(shè)計(jì)設(shè)計(jì)了Hcompress類來(lái)執(zhí)行文件的壓縮操作，文件hufcomp.cpp是使用Hcompress類進(jìn)行壓縮的主程序。</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() 打開(kāi)源文件fname,</p><p>　　// 生成二進(jìn)制輸出文件并添加后綴".huf"標(biāo)識(shí)，任何先前的擴(kuò)展名都被替換</p><p>　　// 邏輯標(biāo)志v確定是否輸出進(jìn)度消息</p><p>　　void setFile(const string& fn

65、ame);</p><p>　　// 打開(kāi)源文件fname,生成二進(jìn)制輸出文件以".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樹(shù)中節(jié)點(diǎn)數(shù)目</p><p>　　void displayTree() const;</p><p>　　// 顯示Huffman樹(shù)</p>&l

67、t;p>　　// 考慮屏幕尺寸，當(dāng)樹(shù)大小<= 11時(shí)推薦這樣做</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)計(jì)字符頻率</p><p>　　// charLoc維護(hù)文件出現(xiàn)的字符在Huffman樹(shù)中的下標(biāo)</p><p>　　int numberLeaves;</p><p>　　// numberL

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

70、se;</p><p>　　// 輸出進(jìn)度消息否？</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>　　// 樹(shù)僅有一個(gè)唯一字符么？</p><p>　　bool filesOpen;</p><p>　　// 源和目的文件打開(kāi)了么？</p><p>　　void freqAnalysis();</p><p>　　

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

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

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

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

76、公共成員函數(shù)compress()執(zhí)行壓縮步驟。為獲取壓縮進(jìn)程的一些內(nèi)部參數(shù)，本設(shè)計(jì)提供了disCompRatio()，用來(lái)顯示源文件大小，壓縮文件大小和壓縮比。</p><p>　　Hcompress類對(duì)象的應(yīng)用代碼示例如下：</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 << "請(qǐng)輸入源文件名: ";</p><p>　　cin >> fileName;</p><p>　　cout << "顯示進(jìn)程狀態(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 樹(shù)為：" << 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 壓縮類的實(shí)現(xiàn)</p><p>　　1.Compress()成員函數(shù)是控制文件壓縮的關(guān)鍵模塊，Huffman樹(shù)的構(gòu)造是算法的核

85、心功能所在。本設(shè)計(jì)就從這兩點(diǎn)出發(fā)考慮Huffman壓縮類得實(shí)現(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樹(shù)中 ..." << endl;</p><p>　　// 構(gòu)建Huffman樹(shù)</p><p>　　buildTree();</p><p

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

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

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

91、an所需要的僅是字符和子節(jié)點(diǎn)指針</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>　　// 對(duì)于僅含有單個(gè)字符的源文件，</p><p>　　// 刪除由于附加葉節(jié)點(diǎn)所添加到總體代價(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樹(shù)中查找對(duì)應(yīng)每個(gè)字符的Huffman碼</p><p>　　// 寫(xiě)入到dest文

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

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

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

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

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

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

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

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

102、;p><b>　　{</b></p><p>　　// 設(shè)置葉節(jié)點(diǎn)數(shù)目為2，</p><p>　　// 并在索引0或1位置添加1個(gè)葉節(jié)點(diǎn)</p><p>　　// 因?yàn)樵谶@些位置的字符不出現(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é)點(diǎn)</p><p>　　oneChar = true;</p

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

105、1;</p><p>　　tree.resize(treeSize);</p><p>　　// 檢索我們構(gòu)造中的樹(shù)</p><p>　　nodeIndex = 0;</p><p>　　// 開(kāi)始構(gòu)造各個(gè)葉節(jié)點(diǎn)</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 為默認(rèn)值</p><p>　　// 在cha

107、rLoc中記錄葉節(jié)點(diǎn)的位置，將節(jié)點(diǎn)插入到最小優(yōu)先級(jí)隊(duì)列中</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é)點(diǎn)的索引，用于</p><p>　　// writeCompressedData()函數(shù)</p>

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

110、p>　　// 生成父節(jié)點(diǎn), 并將父節(jié)點(diǎn)插入樹(shù)中</p><p>　　for (i=1; i <= numberLeaves-1; i++)</p><p><b>　　{</b></p><p>　　// 移除頻率最低的兩個(gè)節(jié)點(diǎn)。它們?cè)谙蛄繕?shù)中對(duì)應(yīng)節(jié)點(diǎn)的副本</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é)點(diǎn)（內(nèi)部節(jié)點(diǎn)），它的

112、子節(jié)點(diǎn)</p><p>　　// 在數(shù)組樹(shù)中的索引位置為x.index和y.index，</p><p>　　// 它的頻度為x和y的頻度和</p><p>　　// 這個(gè)節(jié)點(diǎn)的索引為nodeIndex，</p><p>　　// 其父節(jié)點(diǎn)暫時(shí)設(shè)為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é)點(diǎn)成員變量的值</p>&

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

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

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

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

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

119、現(xiàn)將源文件轉(zhuǎn)換為壓縮文件的過(guò)程。它首先以二進(jìn)制方式再次讀入源文件，將其諸字節(jié)解釋為字符，并產(chǎn)生對(duì)應(yīng)的壓縮編碼，此時(shí)壓縮編碼時(shí)在內(nèi)存中，再將整個(gè)壓縮碼由內(nèi)存轉(zhuǎn)移到磁盤(pá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)標(biāo)記</p><p>　　// 并將文件指針設(shè)為文件的開(kāi)始位置&l