圖像編碼——霍夫曼編碼

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

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

3、夫曼編碼1.圖像數(shù)據(jù)壓縮原理 對(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ì)顏色分辨力弱，利用這些特征可以在相應(yīng)部分適當(dāng)降低編碼精度而使人從視覺(jué)上并不感覺(jué)到圖像質(zhì)量的下降，從而達(dá)到對(duì)數(shù)字圖像壓縮的目的。圖像數(shù)據(jù)壓縮的目的是在滿足一定圖像質(zhì)量的條件下，用盡可能少的

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

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

6、它是一種無(wú)損編碼方法。采用霍夫曼編碼方法的實(shí)質(zhì)是針對(duì)統(tǒng)計(jì)結(jié)果對(duì)字符本身重新編碼，而不是對(duì)重復(fù)字符或重復(fù)子串編碼，得到的單位像素的比特?cái)?shù)最接近圖像的實(shí)際熵值。例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來(lái)表示，而z則可能花去25個(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ú)損壓縮的比例。例如：假設(shè)信源符號(hào)為【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個(gè)字符，對(duì)其進(jìn)行huffman 編碼，算法如下：首先按照每個(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)。得到一棵huffman 樹(shù)，如下圖所示：  圖 2.1在得到的huffman 樹(shù)上左分支標(biāo)記1，右分

8、支標(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、0000、0011、11、01、0010，可以看到,符號(hào)只能出現(xiàn)在樹(shù)葉上,任何一個(gè)字符的路徑都不會(huì)是另一字符路徑的前綴路徑。3.哈夫曼編碼的圖像壓縮設(shè)計(jì)目標(biāo)是實(shí)現(xiàn)Huffman壓縮的編碼器。編碼器的工作過(guò)程呢個(gè)如下；首先讀入待壓縮的源文件，為保證與源文件信息完全一致，對(duì)文件的讀寫操作都用二進(jìn)制文件的方式進(jìn)行。與這只偶那個(gè)方式對(duì)應(yīng)的是ASCII方式讀寫。然后建立并分析字母表，對(duì)讀入內(nèi)存的源

9、文件我們以字節(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í)，再次讀入源文件，逐字節(jié)編碼，將得到的編碼流寫入到磁盤文件。 編碼的核心是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ù)位

10、序列從樹(shù)的根節(jié)點(diǎn)循次遍歷到葉節(jié)點(diǎn)，葉節(jié)點(diǎn)保留其表示的字符，這就足夠了。4. 設(shè)計(jì)程序;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)編碼后的圖像，顯示壓縮比，并計(jì)算均方根誤差得erms=0，表示是Huffman是無(wú)失真編碼subplot(121);imsh

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

12、.cols是原始圖像行數(shù)%info.length是原始圖像數(shù)據(jù)長(zhǎng)度%info.maxcodelen是最長(zhǎng)碼長(zhǎng)if isa(vector,'uint8') error('input argument must be a uint8 vector');endm,n=size(vector);vector=vector(:)'f=frequency(vector); %計(jì)算各符號(hào)出現(xiàn)的概率symbols=find(f=0);f=f(symbols);f,sortindex=sort(f); %將符號(hào)按照出現(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樹(shù)，得到碼字編碼表 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) %得到整個(gè)圖像所有比特?cái)?shù) len=len+length(codeworddouble(vector(index)+1);endstring=repmat(uint8(0),1,le

15、n);pointer=1;for index=1:length(vector) %對(duì)輸入圖像進(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ù)倍時(shí)，最后補(bǔ)pad個(gè)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:;%計(jì)算壓縮后的向量cols=lengt

17、h(string)/8;string=reshape(string,8,cols);weights=2.(0:7);zipped=uint8(weights*double(string);%碼表存儲(chǔ)到一個(gè)稀疏矩陣huffcodes=sparse(1,1);for index=1:nnz(codeword) huffcodes(codeword(index),1)=symbols(index);end%填寫解碼時(shí)所需的結(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ù)對(duì)輸入矩陣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序列，每位占一個(gè)字節(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);%開(kāi)始解碼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計(jì)算各符號(hào)出現(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返回碼字對(duì)應(yīng)的符號(hào)function byte=decode(code,info)byte=info.huffcodes(code)5. 實(shí)驗(yàn)結(jié)果(1)對(duì)圖像woman進(jìn)行編碼cr = 0.6291 Name Size Bytes Class