【正文】 每個碼字惟一可譯。哈夫曼編碼對不同的信源，其編碼效率是不同的。 靜態(tài)哈夫曼編碼的具體編碼過程 哈夫曼編碼步驟：1）把信源符號xi(i=1,2,… ,N) 按出現(xiàn)概率的值由大到小的順序排列；2）對兩個概率最小的符號分別分配以“0”和“1”，然后把這兩個概率相加作為一個新的輔助符號的概率；3）將這個新的輔助符號與其他符號一起重新按概率大小順序排列；4）跳到第2 步，直到出現(xiàn)概率相加為1 為止；5）用線將符號連接起來，從而得到一個碼樹，樹的N 個端點對應(yīng)N 個信源符號；6）從最后一個概率為1 的節(jié)點開始，沿著到達信源的每個符號，將一路遇到的二進制碼“0”或“1”順序排列起來，就是端點所對應(yīng)的信源符號的碼字。（3） 重復(fù)第2步，直到形成一個符號為止（樹），其概率最后等于1。算法步驟如下：（1） 初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序。同其他碼詞長度可變的編碼一樣，區(qū)別在于不同碼詞的生成是基于不同符號出現(xiàn)的不同概率。在哈夫曼編碼樹的基礎(chǔ)上，該算法的編碼部分輸入一系列的符號，根據(jù)哈夫曼樹對符號進行翻譯，以符號在哈夫曼樹上的位置作為編碼結(jié)果。所有可能的輸入符號（通常對應(yīng)為字節(jié)）哈夫曼編碼樹上對應(yīng)為一個葉節(jié)點，在葉節(jié)點的位置就是該符號的哈夫曼編碼。因此，在第4章第二節(jié)，根據(jù)字符編碼的單值性，對哈夫曼編碼的第二個改進做了介紹，即用一個二維數(shù)組模擬哈夫曼樹的創(chuàng)建過程并得到字符的前綴編碼，這一改進有效地提高了壓縮比。 另外，由于在構(gòu)造靜態(tài)哈夫曼樹時，大量的時間消耗在從元素集合中選取兩個最小的元素上，因此，在其中引入了堆排序算法，這一改進有效地縮短了壓縮時間，第4章第一節(jié)對這一改進做了介紹。之后，分別利用這兩種編碼算法實現(xiàn)了圖像的壓縮，并且給出了相應(yīng)的C語言代碼。 本設(shè)計所做的主要工作 由上可知，不論是靜態(tài)哈夫曼編碼還是動態(tài)哈夫曼編碼，其編碼和解碼過程都相對簡單，而如何構(gòu)造哈夫曼編碼樹成為問題的關(guān)鍵。靜態(tài)哈夫曼編碼是以每個字符出現(xiàn)的概率為權(quán)值構(gòu)造哈夫曼編碼樹，字符存在于葉子上，每個字符都有唯一的二進制序列表示，壓縮時，只要壓入相應(yīng)的哈夫曼編碼即可；解壓時，根據(jù)取出的哈夫曼編碼，從根結(jié)點出發(fā)，編碼為0時走左子樹，為1時走右子樹，直至葉結(jié)點。然后將從根到葉子的路徑上的標(biāo)號依次相連，作為該葉子所表示字符的編碼。這棵樹便是哈夫曼 樹。這種編碼是一種無前綴編碼，即，任一字符的編碼都不會是其他字符編碼的前綴，因而數(shù)據(jù)編碼后在存儲與傳輸?shù)倪^程中不會產(chǎn)生二義性。所有可能的輸入符號在哈夫曼樹上對應(yīng)為一個葉結(jié)點，葉結(jié)點的位置就是該符號的哈夫曼編碼。它的實現(xiàn)主要借助于哈夫曼樹。它是一種無損壓縮編碼方法，其基本原理是出現(xiàn)頻度較高的數(shù)據(jù)用較短的代碼，出現(xiàn)頻度較低的數(shù)據(jù)用較長的代碼。一個編碼系統(tǒng)要研究的問題是設(shè)法減小編碼平均長度R，使編碼效率η盡量趨于1，而冗余度趨于0。這種狀態(tài)的編碼方法，成為最佳編碼。當(dāng)然如果編碼結(jié)果使R 遠大于H，表明這種編碼方法效率很低，占用比特數(shù)太多。按信息論中信源信息熵的定義，圖像的熵定義為： (1) 圖像的熵表示像素各個灰度級數(shù)據(jù)的統(tǒng)計平均值，給出了對輸入灰度級集合進行編碼時所需的平均位數(shù)的下限。壓縮方法的優(yōu)劣主要由壓縮比和所恢復(fù)的圖像的質(zhì)量兩個方面來衡量。無損壓縮中去掉的僅僅是圖像數(shù)據(jù)中冗余的數(shù)據(jù)，經(jīng)解碼重建的圖像和原始圖像沒有任何失真，如哈夫曼編碼、行程編碼、算術(shù)編碼；有損壓縮是指解碼重建的圖像與原始圖像相比有失真，不能精確地復(fù)原，但視覺效果基本上相同，是實現(xiàn)高壓縮比的編碼方法，如預(yù)測編碼、變換編碼。從當(dāng)前發(fā)展情況來看，它仍處于深入研究的階段。第二代是指20 世紀(jì)80 年代以后的編碼方法，它突破了信源編碼理論，結(jié)合分形、模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分利用了人類視覺系統(tǒng)生理特性和圖像信源的各種特性。因此，圖像數(shù)據(jù)在傳輸和存儲中，數(shù)據(jù)的壓縮是必不可少的 圖像壓縮編碼技術(shù)概述 圖像壓縮編碼技術(shù)分類 圖像壓縮編碼的方法很多，其分類視出發(fā)點不同而有差異。如果能對這些冗余成分加以有效削減，就能夠大大節(jié)減圖像的存儲空間，減少圖像傳輸時所占信道容量，使得現(xiàn)有的PC 和網(wǎng)絡(luò)在指標(biāo)和性能方面能夠達到處理圖像信息的要求。統(tǒng)計測量表明圖像信號在相鄰像素間、相鄰行間、相鄰幀之間存在著很強的相關(guān)性。僅靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現(xiàn)實的。如不進行編碼壓縮處理，一張存650MB 字節(jié)的光盤僅能存放24s 左右的640 像素480 像素的圖像畫面[1][5]。如果以30 幀/s 的速度播放，則每秒的數(shù)據(jù)量為6404802430bit=，需要221 Mbit/s 的通信回路。圖像編碼與壓縮的目的就是對圖像數(shù)據(jù)按一定的規(guī)則進行變換和組合，從而達到以盡可能少的代碼表示盡可能多的圖像信息。重慶理工大學(xué)畢業(yè)論文 哈夫曼編碼的實現(xiàn)及應(yīng)用哈夫曼編碼的實現(xiàn)及應(yīng)用畢業(yè)設(shè)計目錄摘要 IAbstract II第一章 緒論 1 研究目的及意義 1 圖像壓縮編碼技術(shù)概述 2 圖像壓縮編碼技術(shù)分類 2 圖像壓縮編碼評價 2 哈夫曼編碼簡介 3 本設(shè)計所做的主要工作 4第二章 利用靜態(tài)哈夫曼編碼實現(xiàn)圖像壓縮 5 靜態(tài)哈夫曼編碼介紹 5 靜態(tài)哈夫曼編碼樹的構(gòu)造 6 靜態(tài)哈夫曼編碼的具體編碼過程 6 靜態(tài)哈夫曼編碼的算法實例 7 利用靜態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn) 9 壓縮的實現(xiàn) 9 解壓縮的實現(xiàn) 11 圖象壓縮實例 12第三章 利用動態(tài)哈夫曼編碼實現(xiàn)圖像壓縮 15 動態(tài)哈夫曼編碼的提出 15 動態(tài)哈夫曼編碼的原理 15 動態(tài)哈夫曼編碼的算法思想 16 動態(tài)哈夫曼編碼的編碼實例 18 利用動態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn) 25 數(shù)據(jù)結(jié)構(gòu) 25 壓縮的實現(xiàn) 26 解壓縮的實現(xiàn) 27 圖像壓縮實例 28 靜態(tài)哈夫曼編碼與動態(tài)哈夫曼編碼的比較 29第四章 對哈夫曼編碼的改進 31 在哈夫曼編碼中引入堆排序 31 模擬哈夫曼樹的創(chuàng)建 32第五章 總結(jié) 34 總結(jié) 34參考文獻 35附錄 36重慶理工大學(xué)畢業(yè)論文 哈夫曼編碼的實現(xiàn)及應(yīng)用 第一章 緒論 研究目的及意義 從信息論角度看，信源編碼的一個最主要的目的，就是要解決數(shù)據(jù)的壓縮問題。數(shù)據(jù)壓縮是指以最少的代碼表示信源所發(fā)出的信號，減少容納給定信息集合或數(shù)據(jù)采樣集合的信號空間。 圖像數(shù)字化之后，其數(shù)據(jù)量非常龐大，例如，一副640480 的彩色圖像（24bit/像素）。在多媒體中，海量圖像數(shù)據(jù)的存儲和處理是一個難題?？傊髷?shù)據(jù)量的圖像信息會給存儲器的存儲容量、通信干線通道的帶寬以及計算機的處理速度增加極大的壓力。另一方面，圖像本身包含著大量的冗余成分。一般情況下，畫面中亮度變化相對平坦的地方，相鄰像素就有相同的值，而且對相鄰幀的圖像來說，畫面中的大部分區(qū)域信號變化緩慢，尤其是背景部分幾乎不變。沒有壓縮技術(shù)的發(fā)展，大容量圖像信息的存儲與傳輸難以適應(yīng)應(yīng)用的要求，多媒體通信技術(shù)也難以推廣。從圖像壓縮技術(shù)發(fā)展過程來看，可將圖像壓縮編碼分為兩代，第一代是指20世紀(jì)80年代以前的編碼方法，它主要研究有關(guān)信息熵、編碼方法以及數(shù)據(jù)壓縮比等內(nèi)容。但由于“第二代”編碼技術(shù)增加了分析的難度，所以大大增加了實現(xiàn)的復(fù)雜性。 根據(jù)解壓重建后的圖像與原始圖像之間是否有誤差，圖像壓縮編碼分為無損（也成為無失真、無誤差、信息保持、可逆壓縮）編碼和有損（有誤差、有失真、不可逆）編碼兩大類。 圖像壓縮編碼評價 圖像信號在編碼和傳輸中會產(chǎn)生誤差，尤其是在熵壓縮編碼中，產(chǎn)生的誤差應(yīng)在允許的范圍內(nèi)。(1)圖像熵 設(shè)數(shù)字圖像像素灰度級集合為{d1,d2,……,dn}，其對應(yīng)的概率分別為p(d1)，p(d2)，……,p(dn)。(2)平均碼字長度 設(shè)ai 為數(shù)字圖像中灰度級di 所對應(yīng)的碼字長度（二進制代碼的位數(shù)），其相應(yīng)出現(xiàn)的概率為p(di)，則該數(shù)字圖像所賦予的平均碼字長度為： (2)(3)編碼效率 (3) 根據(jù)信息論中信源碼理論，可以證明在R ≥ H 條件下，總可以設(shè)計出某種無失真編碼方法。最好的編碼結(jié)果是使R 等于或接近于H。(4)壓縮比 壓縮比是指編碼前后平均碼長之比，如果用n 表示編碼前每個字符的平均碼長，通常為用二進制碼表示時的位數(shù)，則壓縮比可表示為： (4) 一般來說，壓縮比大，則說明被壓縮掉的數(shù)據(jù)量多。 哈夫曼編碼簡介 哈夫曼編碼是根據(jù)可變長最佳編碼定理，應(yīng)用哈夫曼算法而產(chǎn)生的一種編碼方法。這些代碼都是二進制碼，且碼長是可變的。哈夫曼樹，又稱最優(yōu)二叉樹，是一類帶權(quán)路徑最短的樹。具體來說，一個符號對應(yīng)的哈夫曼編碼就是從根結(jié)點開始，沿左支或右支前進，一直找到該符號所對應(yīng)的葉結(jié)點為止的路徑所產(chǎn)生的二進制編碼。假設(shè)原始數(shù)據(jù)中含有k 個各不相同的字符a1，a2，ak，所出現(xiàn)的頻率分別為w1，w2，wk，則哈夫曼編碼算法[2]如下：（1） 根據(jù)給定的n 個權(quán)值{w1，w2，……wn}構(gòu)成n 棵二叉樹的集合F={T1，T2，……，Tn}，其中每棵二叉樹Ti（i=1，2，……n）中只有一個權(quán)值為wi 的根結(jié)點，其左、右子樹均為空；（2）在F 中選取兩棵結(jié)點的權(quán)值最小的樹作為左、右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和；（3） 在F 中刪除這兩棵樹，同時將新得到的二叉樹加入到F 中；（4） 重復(fù)步驟（2）和（3），直到F 中只含一棵樹為止。（5） 將哈夫曼 樹的左支標(biāo)0，右支標(biāo)1，或者左支標(biāo)1，右支標(biāo)0（本文采用前一種形式）。 哈夫曼編碼有靜態(tài)和動態(tài)兩類。動態(tài)哈夫曼編碼又稱自適應(yīng)哈夫曼編碼，它對數(shù)據(jù)壓縮依據(jù)的是動態(tài)變化的哈夫曼編碼樹，具體地說，對第i+1個字符的編碼是根據(jù)原始數(shù)據(jù)中前i個字符所建立哈夫曼編碼樹進行的。論文分別在第2章、第3章中詳細介紹了靜態(tài)哈夫曼編碼樹和動態(tài)哈夫曼編碼樹的構(gòu)造方案，并且通過例子演示了構(gòu)造過程。第3章最后一節(jié)對兩種編碼方法作了比較。在靜態(tài)哈夫曼編碼算法中，哈夫曼樹的保存占用了大量的空間，而動態(tài)哈夫曼編碼算法，雖然克服了前者的缺點，但是算法復(fù)雜，而且解壓縮時間長。第二章 利用靜態(tài)哈夫曼編碼實現(xiàn)圖像壓縮 靜態(tài)哈夫曼編碼介紹 哈夫曼編碼是上個世紀(jì)五十年代由哈夫曼教授研制開發(fā)的,它借助了數(shù)據(jù)結(jié)構(gòu)當(dāng)中的樹型結(jié)構(gòu),在哈夫曼算法的支持下構(gòu)造出一棵最優(yōu)二叉樹,我們把這類樹命名為哈夫曼樹. 因此,準(zhǔn)確地說,哈夫曼編碼是在哈夫曼樹的基礎(chǔ)之上構(gòu)造出來的一種編碼形式,它的本身有著非常廣泛的應(yīng)用. 那么,哈夫曼編碼是如何來實現(xiàn)數(shù)據(jù)的壓縮和解壓縮的呢? 眾所周知,在計算機當(dāng)中,數(shù)據(jù)的存儲和加工都是以字節(jié)作為基本單位的,一個西文字符要通過一個字節(jié)來表達,而一個漢字就要用兩個字節(jié),我們把這種每一個字符都通過相同的字節(jié)數(shù)來表達的編碼形式稱為定長編碼. 以西文為例,例如我們要在計算機當(dāng)中存儲這樣的一句話: I am a teacher . 就需要15個字節(jié),也就是120個二進制位的數(shù)據(jù)來實現(xiàn). 與這種定長編碼不同的是,哈夫曼編碼是一種變長編碼. 它根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼. 換句話說如果一個字符在一段文檔當(dāng)中出現(xiàn)的次數(shù)多,它的編碼就相應(yīng)的短,如果一個字符在一段文檔當(dāng)中出現(xiàn)的次數(shù)少,它的編碼就相應(yīng)的長. 當(dāng)編