1、序號(hào):HunanInstituteofScienceandTechnology圖像的霍夫曼編碼姓名：班級(jí)：學(xué)號(hào)：專業(yè):指導(dǎo)老師：完成時(shí)間:湖南理工學(xué)院物理與電子學(xué)院TOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 摘要:1 HYPERLINK l bookmark10 o Current Document 一、引言1 HYPERLINK l bookmark12 o Current Document 二、霍夫曼編碼簡介1三、霍夫曼編碼21、霍夫曼編碼規(guī)則22、霍夫曼樹3（1）霍夫曼樹的相關(guān)概念3（2）霍夫曼算法3（3）霍夫曼樹的構(gòu)建4

2、3、霍夫曼的局限性5 HYPERLINK l bookmark6 o Current Document 四、霍夫曼編碼分類61、截?cái)嗷舴蚵幋a62、自適應(yīng)霍夫曼編碼6 HYPERLINK l bookmark14 o Current Document 五、仿真8 HYPERLINK l bookmark16 o Current Document 六、結(jié)論12 HYPERLINK l bookmark18 o Current Document 參考文獻(xiàn)12 摘要:霍夫曼編碼是一種常用的無損編碼，他基于不同符號(hào)的概率分布，在信息源中出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短；出現(xiàn)概率越小的符號(hào)，其碼越長，從

3、而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。本文介紹了霍夫曼編碼的原理、方法、特點(diǎn)、應(yīng)用、霍夫曼樹的生成過程，霍夫曼編碼的產(chǎn)生，霍夫曼表的構(gòu)建，霍夫曼編碼的結(jié)果以及怎樣用MATLAB實(shí)現(xiàn)霍夫曼編碼。關(guān)鍵字：無損編碼霍夫曼編碼霍夫曼樹MATLAB一、引言隨著科學(xué)技術(shù)的發(fā)展和需求，人們廣泛致力于對各種文本、圖片、圖形、語言、聲音、活動(dòng)圖像和影視信號(hào)等實(shí)際信源進(jìn)行了實(shí)用壓縮方法和技術(shù)研究，使信源的數(shù)據(jù)壓縮技術(shù)得以蓬勃發(fā)展和逐漸走向成熟。在信息化高度發(fā)達(dá)的當(dāng)今社會(huì)，我們必須對信息的傳遞有著較高的要求，我們希望信息在傳遞的過程中，能夠保持節(jié)省性和保密性和無損性，而著名的霍夫曼編碼就能夠達(dá)到這樣的要求。因此研究霍

4、夫曼編碼對信息的壓縮和解壓是相當(dāng)有必要的。二、霍夫曼編碼簡介1952年，DavidA.Huffman在麻省理工攻讀博士時(shí)，根據(jù)香農(nóng)(Shannon)在1948年和范若(Fano)在1949年闡述的編碼思想提出了一種不定長編碼的方法霍夫曼編碼，并發(fā)表于一種構(gòu)建極小多余編碼的方法一文?；舴蚵幋a是常用的無損編碼方法，廣泛應(yīng)用于圖像壓縮技術(shù)。JPEG標(biāo)準(zhǔn)中的基準(zhǔn)模式采用的就是霍夫曼編碼。霍夫曼編碼是不定長編碼，即代表各元素的碼字長度不等。該編碼是基于不同符號(hào)的概率分布，在信息源中出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短；出現(xiàn)概率越小的符號(hào)，其碼越長，從而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。它在變長編碼中是最佳

5、的。在計(jì)算機(jī)信息處理中，“霍夫曼編碼”是一種一致性編碼法(又稱熵編碼法)霍夫曼編碼的基本方法是先對圖像數(shù)據(jù)掃描一遍，計(jì)算出各種像素出現(xiàn)的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張?jiān)搱D像的霍夫曼碼表。編碼后的圖像數(shù)據(jù)記錄的是每個(gè)像素的碼字，而碼字與實(shí)際像素值的對應(yīng)關(guān)系記錄在碼表中?；舴蚵幋a1、霍夫曼編碼規(guī)則設(shè)信源X的信源空間為：X:xxxXP：丨P(X):P(x)P(x)P(x)V12N丿其中，弋P(x=1，現(xiàn)用二進(jìn)制對信源X中的每一個(gè)符號(hào)i=1x(i=h2N)進(jìn)行編碼i將信源符號(hào)xi按其出現(xiàn)的概率，由大到小順序排列。將兩個(gè)最小的概率的信源符號(hào)進(jìn)行組合相加，并重復(fù)這一步驟，始終將較

6、大的概率分支放在上部，直到只剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止；對每對組合的上邊一個(gè)指定為1，下邊一個(gè)指定為0（或相反:對上邊一個(gè)指定為0，下邊一個(gè)指定為1）；畫出由每個(gè)信源符號(hào)到概率1處的路徑，記下沿路徑的1和0,所得的就是該符號(hào)的霍夫曼碼字。i=j2、霍夫曼樹（1）霍夫曼樹的相關(guān)概念霍夫曼樹：指所有葉子結(jié)點(diǎn)的二叉樹中帶權(quán)路徑長度最小的二叉樹。節(jié)點(diǎn)的帶權(quán)路徑長度：從樹的根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長度與該節(jié)點(diǎn)權(quán)的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。（2）霍夫曼算法根據(jù)給定的n個(gè)權(quán)值w1,w2,.,wn構(gòu)造n棵二叉樹的集合F二T1,T2,.,Tn,其中每棵二叉樹Ti中只有一個(gè)

7、帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)（2）和（3），直到F中只含一棵樹為止。這棵樹便是最優(yōu)二叉樹。（3）霍夫曼樹的構(gòu)建假設(shè)對由al、a2、a3、a4、a5、a6、a7、a8八個(gè)信源符號(hào)組成的源信息字符串:alala2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進(jìn)行霍夫曼編碼。首先應(yīng)對信息中各數(shù)字出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，得出各數(shù)字出現(xiàn)的相對概率。假設(shè)各數(shù)字出現(xiàn)的次數(shù)及概率如表1所Z示O表一碼值a

8、1a2a3a4a5a6a7a8次數(shù)22343331概率0.10.10.150.20.150.150.10.05具體過程是這樣的，先將所有符號(hào)排成一行構(gòu)成8個(gè)最底層節(jié)點(diǎn)。首先將這些節(jié)點(diǎn)中最小兩個(gè)概率值相加：0.05+0.1=0.15,得到新的節(jié)點(diǎn)，這時(shí)擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。再將兩個(gè)最小的概率值相加得到新的節(jié)點(diǎn)直到得到根節(jié)點(diǎn)概率為1.0為止。相加時(shí)，對于概率值相等的多個(gè)節(jié)點(diǎn)，可以任意選取。除根節(jié)點(diǎn)外，設(shè)節(jié)點(diǎn)左邊分支為0,右邊分支為1（也可以反過來）。根據(jù)表一生成的霍夫曼樹如圖1所示。3霍夫曼的局限性對于各值（碼值）的代碼（碼字）就是從根節(jié)點(diǎn)出

9、發(fā)到底層節(jié)點(diǎn)所經(jīng)歷的分支序列。如a4的代碼（碼字）為00,a6的碼字為111通常a4和a6等稱為碼值，00和111等稱為碼字。所有碼值和碼字對應(yīng)關(guān)系如表2所示。碼值ala4aSa?碼字010Oil1010011011110001001i=j利用霍夫曼編碼，每個(gè)符號(hào)的編碼長度只能為整數(shù)，所以如果源符號(hào)集的概率分布不是2負(fù)n次方的形式，則無法達(dá)到熵極限。輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸譯碼復(fù)雜需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布沒有錯(cuò)誤保護(hù)功能四、霍夫曼編碼分類1、截?cái)嗷舴蚵幋a霍夫曼編碼不僅適用于壓縮文本文件，經(jīng)過符號(hào)合并后也可用于二進(jìn)制文件。但在實(shí)用中，霍夫曼編碼的輸入符號(hào)數(shù)常受限于可實(shí)現(xiàn)的碼表大

10、小。JEPEG采用將碼字截?cái)酁椤扒熬Y碼（SSSS）+尾碼”的方法，對碼表進(jìn)行了簡化，這種編碼方法稱為截?cái)嗷舴蚵幋a。前綴碼用來指明尾碼的有效位數(shù)（設(shè)為B位），用標(biāo)準(zhǔn)的霍夫曼編碼；尾碼則直接采用B位自然二進(jìn)碼（對于給定的前綴碼它為定長碼，高位在前）。對于8位量化的圖像，SSSS值的范圍為011，故其碼表只有12項(xiàng)。根據(jù)DIFF的幅度范圍由表4.2查出前綴碼字和尾碼的位數(shù)后，貝U可按以下規(guī)則直接寫出尾碼的碼字，即尾碼為DIFF的B位原碼，若DIFF0反碼，若DIFF0按此規(guī)則，當(dāng)DIFF0時(shí)，尾碼的最高位是“1”；而當(dāng)DIFF0時(shí)則為“0”。解碼時(shí)則可借此來判斷DIFF的正負(fù)。2、自適應(yīng)霍夫曼編碼

11、（1）自適應(yīng)霍夫曼編碼提出的目的和意義在靜態(tài)霍夫曼編碼中，要構(gòu)造編碼樹必須提前統(tǒng)計(jì)被編碼對象中的符號(hào)出現(xiàn)概率，因此必須對輸入符號(hào)流進(jìn)行兩遍掃描，第一遍統(tǒng)計(jì)符號(hào)出現(xiàn)概率并構(gòu)造編碼樹，第二遍進(jìn)行編碼，這在很多實(shí)際應(yīng)用的場合中之不能接受的。其次，在存儲(chǔ)和傳送霍夫曼編碼時(shí)，必須先存儲(chǔ)和傳送霍夫曼編碼樹。再次，靜態(tài)編碼樹構(gòu)造方案不能對輸入符號(hào)流的局部統(tǒng)計(jì)規(guī)律變化做出反應(yīng)。這些問題使得靜態(tài)霍夫曼編碼在實(shí)際中并未得到廣泛的應(yīng)用。為了解決靜態(tài)Huffman編碼的缺點(diǎn)，人們提出了自適應(yīng)Huffman編碼這種方案不需要事先掃描輸入符號(hào)流，而是隨著編碼的進(jìn)行同時(shí)構(gòu)造Huffman樹，因此，只需要進(jìn)行一次掃描即可。在

12、接收端伴隨著解碼過程同時(shí)進(jìn)行著編碼樹的構(gòu)造。自適應(yīng)霍夫曼編碼解決了靜態(tài)編碼樹所面臨的主要問題，因此在實(shí)際領(lǐng)域比如在高質(zhì)量的圖像和視頻流傳輸中中獲得了廣泛的應(yīng)用。(2)自適應(yīng)霍夫曼編碼的原理這種方案在不需要事先構(gòu)Huffman樹，而是隨著編碼的進(jìn)行，逐步構(gòu)造Huffman樹。同時(shí)，這種編碼方案對符號(hào)的統(tǒng)計(jì)也動(dòng)態(tài)進(jìn)行，隨著編碼的進(jìn)行，同一個(gè)符號(hào)的編碼可能發(fā)生改變(變得更長或更短)。由于自適應(yīng)Huffman編碼算法采用了先編碼，后調(diào)整編碼樹的方案，相應(yīng)的解碼算法比較簡單。解碼算法也使用僅有唯一的NYT節(jié)點(diǎn)的編碼樹作為初始狀態(tài)，然后根據(jù)Huffman編碼數(shù)據(jù)流，對符號(hào)進(jìn)行還原。每次處理完一個(gè)符號(hào)，就使

13、用這個(gè)符號(hào)調(diào)整編碼樹。這樣，在每一次輸入新的符號(hào)之前，Huffman樹都處于與進(jìn)行編碼時(shí)使用的的Huffman樹完全相同的狀態(tài)，保證了解碼的正確性。自適應(yīng)霍夫曼編碼是一種擴(kuò)展的熵編碼方法，相比于先前的靜態(tài)霍夫曼編碼，自適應(yīng)霍夫曼編碼具有僅需單遍掃描、無需傳送編碼樹、能夠?qū)斎敕?hào)流的局部統(tǒng)計(jì)規(guī)律變化做出反應(yīng)等一系列優(yōu)點(diǎn)，具有更高的壓縮效率。這些優(yōu)點(diǎn)使得它在一些實(shí)時(shí)性、可靠性要求比較高的場合得到了廣泛的應(yīng)用，被稱為近代壓縮算法的靈魂。五、仿真用MATLAB實(shí)現(xiàn)圖像的霍夫曼編碼和解碼，代碼如下：closeall;clearall;clc;I=imread(lena.bmp);I=im2double

14、(I)*255;height,width=size(I);%求圖像的大小HWmatrix=zeros(height,width);Mat=zeros(height,width);HWmatrix(l,l)=I(l,l);fori=2:height%以下將圖像像素值傳遞給矩陣MatMat(i,l)=I(i-l,l);endforj=2:widthMat(l,j)=I(l,j-l);end%以下建立待編碼的數(shù)組symbols和fori=2:height每個(gè)像素出現(xiàn)的概率矩陣pforj=2:widthMat(i,j)=I(i,j-l)/2+I(i-l,j)/2;endendMat=floor(Mat

15、);HWmatrix=I-Mat;SymPro=zeros(2,l);SymNum=l;SymPro(l,l)=HWmatrix(l,l);SymExist=0;fori=1:heightforj=1:widthSymExist=0;fork=1:SymNumifSymPro(l,k)=HWmatrix(i,j)SymPro(2,k)=SymPro(2,k)+l;SymExist=1;break;endendifSymExist=0SymNum=SymNum+1;SymPro(l,SymNum)=HWmatrix(i,j);SymPro(2,SymNum)=l;endendendfori=1:

16、SymNumSymPro(3,i)=SymPro(2,i)/(height*width);endsymbols=SymPro(l,:);p=SymPro(3,:);dict,avglen=huffmandict(symbols,p);%產(chǎn)生霍夫曼編碼詞典，返回編碼詞典dict和平均碼長avglenactualsig=reshape(HWmatrix,l,);compress=huffmanenco(actualsig,dict);%利用dict對actuals來編碼，其結(jié)果存放在compress中UnitNum=ceil(size(compress,2)/8);Compressed=zeros

17、(l,UnitNum,uint8);fori=1:UnitNumforj=1:8if(i-l)*8+j)=size(compress,2)Compressed(i)=bitset(Compressed(i),j,compress(i-l)*8+j);endendiiendNewHeight=ceil(UnitNum/512);Compressed(width*NewHeight)=0;ReshapeCompressed=reshape(Compressed,NewHeight,width);imwrite(ReshapeCompressed,CompressedImage.bmp,bmp);R

18、estore=zeros(l,size(compress,2);fori=l:UnitNumforj=1:8if(i-l)*8+j)=size(compress,2)Restore(i-l)*8+j)=bitget(Compressed(i),j);endendenddecompress=huffmandeco(Restore,dict);%利用dict對Restore來解碼,其結(jié)果存放在decompress中Restoredlmage=reshape(decompress,512,512);RestoredImageGrayScale=uint8(RestoredImage+Mat);imwrite(RestoredImageGrayScale,RestoredImage.bmp,bmp);figure;subplot(l,3,l);imshow(I,0,255);%顯示原圖subplot(l,3,2);imshow(ReshapeCompressed);%顯示壓縮后的圖像subplo