圖像的霍夫曼編碼

1、序號:HunanInstituteofScienceandTechnology圖像的霍夫曼編碼姓名：班級：學(xué)號：專業(yè):指導(dǎo)老師：完成時間:湖南理工學(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、截斷霍夫曼編碼62、自適應(yīng)霍夫曼編碼6 HYPERLINK l bookmark14 o Current Document 五、仿真8 HYPERLINK l bookmark16 o Current Document 六、結(jié)論12 HYPERLINK l bookmark18 o Current Document 參考文獻12 摘要:霍夫曼編碼是一種常用的無損編碼，他基于不同符號的概率分布，在信息源中出現(xiàn)概率越大的符號，相應(yīng)的碼越短；出現(xiàn)概率越小的符號，其碼越長，從

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

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

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

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

7、帶權(quán)為wi的根結(jié)點，其左右子樹均空。在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。重復(fù)（2）和（3），直到F中只含一棵樹為止。這棵樹便是最優(yōu)二叉樹。（3）霍夫曼樹的構(gòu)建假設(shè)對由al、a2、a3、a4、a5、a6、a7、a8八個信源符號組成的源信息字符串:alala2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進行霍夫曼編碼。首先應(yīng)對信息中各數(shù)字出現(xiàn)的次數(shù)進行統(tǒng)計，得出各數(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具體過程是這樣的，先將所有符號排成一行構(gòu)成8個最底層節(jié)點。首先將這些節(jié)點中最小兩個概率值相加：0.05+0.1=0.15,得到新的節(jié)點，這時擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。再將兩個最小的概率值相加得到新的節(jié)點直到得到根節(jié)點概率為1.0為止。相加時，對于概率值相等的多個節(jié)點，可以任意選取。除根節(jié)點外，設(shè)節(jié)點左邊分支為0,右邊分支為1（也可以反過來）。根據(jù)表一生成的霍夫曼樹如圖1所示。3霍夫曼的局限性對于各值（碼值）的代碼（碼字）就是從根節(jié)點出

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

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

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

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

13、用這個符號調(diào)整編碼樹。這樣，在每一次輸入新的符號之前，Huffman樹都處于與進行編碼時使用的的Huffman樹完全相同的狀態(tài)，保證了解碼的正確性。自適應(yīng)霍夫曼編碼是一種擴展的熵編碼方法，相比于先前的靜態(tài)霍夫曼編碼，自適應(yīng)霍夫曼編碼具有僅需單遍掃描、無需傳送編碼樹、能夠?qū)斎敕柫鞯木植拷y(tǒng)計規(guī)律變化做出反應(yīng)等一系列優(yōu)點，具有更高的壓縮效率。這些優(yōu)點使得它在一些實時性、可靠性要求比較高的場合得到了廣泛的應(yīng)用，被稱為近代壓縮算法的靈魂。五、仿真用MATLAB實現(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每個像素出現(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