圖像編碼——霍夫曼編碼

1、 編號： 題 目 名 稱 圖像編碼霍夫曼編碼 學(xué) 生 姓 名 學(xué) 號 學(xué) 院 信息科學(xué)與工程學(xué)院 專 業(yè) 年 級 2009級通信一班 指 導(dǎo) 教 師 職 稱 老師 填 寫 時 間 2012年10月27日 摘  要進(jìn)入21世紀(jì)，人類已步入信息社會，新信息技術(shù)革命使人類被日益增多的多媒體信息所包圍，這也正好迎合了人類對要示提高視覺信息的需求。多媒體信息主要有三種形式：文本、聲音和圖像。從信息傳輸?shù)陌l(fā)展史（電報、電話、傳真、收音機(jī)、電視機(jī)直至現(xiàn)在的網(wǎng)絡(luò)）可以看出，人們逐漸將信息傳輸?shù)闹攸c(diǎn)從聲音轉(zhuǎn)向圖像，然而圖像是三種信息形式中數(shù)據(jù)量最大的，這給圖像的傳輸和存儲帶來了極大的困難。對于巨大的數(shù)

2、字圖像數(shù)據(jù)量，如果不經(jīng)過壓縮，不僅超出了計算機(jī)的存儲和處理能力，而且在現(xiàn)有的通信信道的傳輸速率下，是無法完成大量多媒體信息實(shí)時傳輸?shù)模瑪?shù)字圖像高速傳輸和存貯所需要的巨大容量已成為推廣數(shù)字圖像通信和最大障礙。因此，為了存儲、處理和傳輸這些數(shù)據(jù)，必須進(jìn)行壓縮。圖像壓縮之所以能夠進(jìn)行壓縮是因?yàn)樵紙D像數(shù)據(jù)是高度相關(guān)的，存在很大的數(shù)據(jù)冗余。數(shù)字圖像包含的冗余信息一般有以下幾種：空間冗余、時間冗余、信息熵冗余、統(tǒng)計冗余、結(jié)構(gòu)冗余、視覺冗余以及知識冗余等。圖像壓縮算法就是要在保證圖像一定的重建質(zhì)量的同時，盡可能多的去除這些冗余信息，以達(dá)到對圖像壓縮的目的。關(guān)鍵詞：圖像處理,圖像壓縮,壓縮算法,圖像編碼,霍

3、夫曼編碼1.圖像數(shù)據(jù)壓縮原理 對數(shù)字圖像進(jìn)行壓縮通常利用兩個基本原理:一是數(shù)字圖像的相關(guān)性。在圖像的同一行相鄰象素之間，相鄰象素之間，活動圖像的相鄰幀的對應(yīng)象素之間往往存在很強(qiáng)的相關(guān)性，去除或減少這些相關(guān)性，也即去除或減少圖像信息中的冗余度也就實(shí)現(xiàn)了對數(shù)字圖像的壓縮。幀內(nèi)象素的相關(guān)稱做空域相關(guān)性。相鄰幀間對應(yīng)象素之間的相關(guān)性稱做時域相關(guān)性。二是人的視覺心理特征。人的視覺對于邊緣急劇變化不敏感(視覺掩蓋效應(yīng))，對顏色分辨力弱，利用這些特征可以在相應(yīng)部分適當(dāng)降低編碼精度而使人從視覺上并不感覺到圖像質(zhì)量的下降，從而達(dá)到對數(shù)字圖像壓縮的目的。圖像數(shù)據(jù)壓縮的目的是在滿足一定圖像質(zhì)量的條件下，用盡可能少的

4、比特數(shù)來表示原始圖像，以提高圖像傳輸?shù)男屎蜏p少圖像存儲的容量，在信息論中稱為信源編碼。圖像壓縮是通過刪除圖像數(shù)據(jù)中冗余的或者不必要的部分來減小圖像數(shù)據(jù)量的技術(shù)，壓縮過程就是編碼過程，解壓縮過程就是解碼過程。壓縮技術(shù)分為無損壓縮和有損壓縮兩大類，前者在解碼時可以精確地恢復(fù)原圖像，沒有任何損失；后者在解碼時只能近似原圖像，不能無失真地恢復(fù)原圖像。假設(shè)有一個無記憶的信源,它產(chǎn)生的消息為ai,1iN,其出現(xiàn)的概率是已知的,記為P(ai)。則其信息量定義為: 由此可見一個消息出現(xiàn)的可能性越小，其信息量就越多，其出現(xiàn)對信息的貢獻(xiàn)量越大，反之亦然。信源的平均信息量稱為“熵”（entropy），可以表示為：

5、 對上式取以2為底的對數(shù)時，單位為比特（bits）：根據(jù)香農(nóng)（Shannon）無噪聲編碼定理，對于熵為H的信號源，對其進(jìn)行無失真編碼所可能達(dá)到的最低比特數(shù)為，這里為一任意小的正數(shù)，因此可能達(dá)到的 最大壓縮比：其中B是原始圖像的平均比特率。在圖像壓縮中，壓縮比是一個重要的衡量指標(biāo)?？梢远x壓縮比為：2.霍夫曼編碼 Huffman編碼在無損壓縮的編碼方法中，它是一種有效的編碼方法。它是霍夫曼博士在1952 年根據(jù)可變長最佳編碼定理提出的。依據(jù)信源數(shù)據(jù)中各信號出現(xiàn)的頻率分配不同長度的編碼。其基本思想是在編碼過程中，對出現(xiàn)頻率越高的值，分配越短的編碼長度，相應(yīng)地對出現(xiàn)頻率越低的值則分配較長的編碼長度，

6、它是一種無損編碼方法。采用霍夫曼編碼方法的實(shí)質(zhì)是針對統(tǒng)計結(jié)果對字符本身重新編碼，而不是對重復(fù)字符或重復(fù)子串編碼，得到的單位像素的比特數(shù)最接近圖像的實(shí)際熵值。例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對一篇英文進(jìn)行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對于英文中各個字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。例如：假設(shè)信源符號為【a、b、c、d、e、f、g】，其出現(xiàn)的

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

8、支標(biāo)記0，所有的字符根據(jù)其頻率標(biāo)記到對應(yīng)的葉子節(jié)點(diǎn)上，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑上遇到的0、1 字符串即為對應(yīng)葉子節(jié)點(diǎn)所在字符的編碼。a、b、c、d、e、f、g七個字符的huffman 編碼分別是：10、0001、0000、0011、11、01、0010，可以看到,符號只能出現(xiàn)在樹葉上,任何一個字符的路徑都不會是另一字符路徑的前綴路徑。3.哈夫曼編碼的圖像壓縮設(shè)計目標(biāo)是實(shí)現(xiàn)Huffman壓縮的編碼器。編碼器的工作過程呢個如下；首先讀入待壓縮的源文件，為保證與源文件信息完全一致，對文件的讀寫操作都用二進(jìn)制文件的方式進(jìn)行。與這只偶那個方式對應(yīng)的是ASCII方式讀寫。然后建立并分析字母表，對讀入內(nèi)存的源

9、文件我們以字節(jié)為單元進(jìn)行分析，將類型表示，其用C+內(nèi)建的，最多將有中可能的字符。我們對每種字符的出現(xiàn)頻度進(jìn)行統(tǒng)計，以頻度作為建立uffman樹的權(quán)值。頻度表建好之后，就可以根據(jù)前述算法建立Huffman樹，對出現(xiàn)的每種字符進(jìn)行Huffman編碼。此入時，再次讀入源文件，逐字節(jié)編碼，將得到的編碼流寫入到磁盤文件。 編碼的核心是Huffman樹，它也是連接編碼的紐帶?？紤]到Huffman樹節(jié)點(diǎn)的設(shè)計。編碼時從葉節(jié)點(diǎn)逐步構(gòu)建中間節(jié)點(diǎn)，到整顆樹。樹的節(jié)點(diǎn)應(yīng)該應(yīng)該包括的信息有：節(jié)點(diǎn)表示的字符，子字節(jié)的位置，字符出現(xiàn)的頻度，父節(jié)點(diǎn)的位置等，這些都是構(gòu)造Huffman所需要的。而解碼時，我們只需要能夠根據(jù)位

10、序列從樹的根節(jié)點(diǎn)循次遍歷到葉節(jié)點(diǎn)，葉節(jié)點(diǎn)保留其表示的字符，這就足夠了。4. 設(shè)計程序;clearload woman; %讀入圖像數(shù)據(jù)%X=imread('girl.bmp','bmp');data=uint8(X);zipped,info=huffencode(data); %調(diào)用Huffman編碼程序進(jìn)行壓縮unzipped=huffdecode(zipped,info,data);%調(diào)用Huffman編碼程序進(jìn)行解碼%顯示原始圖像和經(jīng)編碼后的圖像，顯示壓縮比，并計算均方根誤差得erms=0，表示是Huffman是無失真編碼subplot(121);imsh

11、ow(data);subplot(122);imshow(unzipped);%erms=compare(data(:),unzipped(:)cr=info.ratiowhos data unzipped zipped%huffencode函數(shù)對輸入矩陣vector進(jìn)行Huffman編碼，返回%編碼后的向量（壓縮后數(shù)據(jù)）及相關(guān)信息function zipped,info=huffencode(vector)%輸入和輸出都是unit8格式%info返回解碼需要的機(jī)構(gòu)信息%info.pad是添加的比特數(shù)%info.huffcodes是Huffman碼字%info.rows是原始圖像行數(shù)%info

12、.cols是原始圖像行數(shù)%info.length是原始圖像數(shù)據(jù)長度%info.maxcodelen是最長碼長if isa(vector,'uint8') error('input argument must be a uint8 vector');endm,n=size(vector);vector=vector(:)'f=frequency(vector); %計算各符號出現(xiàn)的概率symbols=find(f=0);f=f(symbols);f,sortindex=sort(f); %將符號按照出現(xiàn)的概率大小排序symbols=symbols(sort

13、index);len=length(symbols);symbols_index=num2cell(1:len);codeword_tmp=cell(len,1);while length(f)>1 %生產(chǎn)Huffman樹，得到碼字編碼表 index1=symbols_index1; index2=symbols_index2; codeword_tmp(index1)=addnode(codeword_tmp(index1),uint8(0); codeword_tmp(index2)=addnode(codeword_tmp(index2),uint8(1); f=sum(f(1:2

14、) f(3:end); symbols_index=index1,index2 symbols_index(3:end); f,sortindex=sort(f); symbols_index=symbols_index(sortindex);endcodeword=cell(256,1);codeword(symbols)=codeword_tmp;len=0;for index=1:length(vector) %得到整個圖像所有比特數(shù) len=len+length(codeworddouble(vector(index)+1);endstring=repmat(uint8(0),1,le

15、n);pointer=1;for index=1:length(vector) %對輸入圖像進(jìn)行編碼 code=codeworddouble(vector(index)+1; len=length(code); string(pointer+(0:len-1)=code; pointer=pointer+len;endlen=length(string);pad=8-mod(len,8); %非8整數(shù)倍時，最后補(bǔ)pad個0if pad>0 string=string uint8(zeros(1,pad);endcodeword=codeword(symbols);codelen=zero

16、s(size(codeword);weights=2.(0:23);maxcodelen=0;for index=1:length(codeword) len=length(codewordindex); if len>maxcodelen maxcodelen=len; end if len>0 code=sum(weights(codewordindex=1); code=bitset(code,len+1); codewordindex=code; codelen(index)=len; endendcodeword=codeword:;%計算壓縮后的向量cols=lengt

17、h(string)/8;string=reshape(string,8,cols);weights=2.(0:7);zipped=uint8(weights*double(string);%碼表存儲到一個稀疏矩陣huffcodes=sparse(1,1);for index=1:nnz(codeword) huffcodes(codeword(index),1)=symbols(index);end%填寫解碼時所需的結(jié)構(gòu)信息info.pad=pad;info.huffcodes=huffcodes;info.ratio=cols./length(vector);info.length=leng

18、th(vector);info.maxcodelen=maxcodelen;info.rows=m;info.cols=n;%huffdecode函數(shù)對輸入矩陣vector進(jìn)行Huffman編碼，%返回解壓后的圖像數(shù)據(jù)function vector=huffdecode(zipped,info,image)ifisa(zipped,'uint8') error('input argument must be a uint8 vector');end%產(chǎn)生0，1序列，每位占一個字節(jié)len=length(zipped);string=repmat(uint8(0),

19、1,len.*8);bitindex=1:8;for index=1:lenstring(bitindex+8.*(index-1)=uint8(bitget(zipped(index),bitindex);endstring=logical(string(:)');len=length(string);%開始解碼weights=2.(0:51);vector=repmat(uint8(0),1,info.length);vectorindex=1;codeindex=1;code=0;for index=1:len code=bitset(code,codeindex,string(

20、index); codeindex=codeindex+1; byte=decode(bitset(code,codeindex),info); if byte>0 vector(vectorindex)=byte-1; codeindex=1; code=0; vectorindex=vectorindex+1; endend%vector=reshape(vector,info.rows,info.cols);%函數(shù)addnode添加節(jié)點(diǎn)function codeword_new=addnode(codeword_old,item)codeword_new=cell(size(cod

21、eword_old);for index=1:length(codeword_old) codeword_newindex=item codeword_oldindex;end%函數(shù)frequency計算各符號出現(xiàn)的概率function f=frequency(vector)ifisa(vector,'uint8') error('input argument must be a uint8 vector');endf=repmat(0,1,256);len=length(vector);for index=0:255 f(index+1)=sum(vector=uint8(index);endf=f./len;%函數(shù)decode返回碼字對應(yīng)的符號function byte=decode(code,info)byte=info.huffcodes(code)5. 實(shí)驗(yàn)結(jié)果(1)對圖像woman進(jìn)行編碼cr = 0.6291 Name Size Bytes Class