基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)設(shè)計說明

1、 PAGE21 / NUMPAGES26 課程設(shè)計任務(wù)書題 目:基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)初始條件：計算機(jī)Windows8操作系統(tǒng)MATLAB7.8.0軟件要求完成的主要任務(wù):設(shè)計哈夫曼編碼的圖像編解碼系統(tǒng)、利用軟件編寫程序、仿真實(shí)現(xiàn)時間安排：第1-18周：理論講解第19周：理論設(shè)計，實(shí)驗(yàn)室安裝調(diào)試以與撰寫設(shè)計報告答辯：時間：7月2日地點(diǎn): 鑒主15樓通信實(shí)驗(yàn)室四 指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日目錄 TOC o 1-3 h z u HYPERLINK l _Toc360453520目錄 PAGEREF _Toc360453520 h IHYPER

2、LINK l _Toc360453521摘要 PAGEREF _Toc360453521 h IIHYPERLINK l _Toc360453522ABSTRACT PAGEREF _Toc360453522 h IIIHYPERLINK l _Toc3604535231引言 PAGEREF _Toc360453523 h 1HYPERLINK l _Toc3604535241.1圖像數(shù)據(jù)壓縮的目的 PAGEREF _Toc360453524 h 1HYPERLINK l _Toc3604535251.2圖像數(shù)據(jù)壓縮的原理 PAGEREF _Toc360453525 h 1HYPERLINK

3、l _Toc3604535261.3常用的壓縮編碼方法 PAGEREF _Toc360453526 h 3HYPERLINK l _Toc3604535272哈夫曼編碼 PAGEREF _Toc360453527 h 3HYPERLINK l _Toc3604535282.1 哈夫曼編碼簡介 PAGEREF _Toc360453528 h 3HYPERLINK l _Toc3604535292.2哈夫曼編碼步驟 PAGEREF _Toc360453529 h 3HYPERLINK l _Toc3604535302.3 哈夫曼編碼的缺點(diǎn) PAGEREF _Toc360453530 h 5HYPE

4、RLINK l _Toc3604535313基于哈夫曼編碼的圖像編解碼系統(tǒng)的程序設(shè)計 PAGEREF _Toc360453531 h 6HYPERLINK l _Toc3604535323.1 分塊程序設(shè)計分析 PAGEREF _Toc360453532 h 6HYPERLINK l _Toc3604535333.2主程序 PAGEREF _Toc360453533 h 8HYPERLINK l _Toc3604535343.3程序函數(shù) PAGEREF _Toc360453534 h 8HYPERLINK l _Toc3604535353.3.1編碼函數(shù) PAGEREF _Toc3604535

5、35 h 8HYPERLINK l _Toc3604535363.3.2解碼函數(shù) PAGEREF _Toc360453536 h 12HYPERLINK l _Toc3604535373.3.3符號概率計算函數(shù) PAGEREF _Toc360453537 h 13HYPERLINK l _Toc3604535383.3.4節(jié)點(diǎn)添加函數(shù) PAGEREF _Toc360453538 h 14HYPERLINK l _Toc3604535393.3.5解碼返回符號函數(shù) PAGEREF _Toc360453539 h 14HYPERLINK l _Toc3604535404系統(tǒng)仿真結(jié)果 PAGEREF

6、 _Toc360453540 h 15HYPERLINK l _Toc3604535414.1程序運(yùn)行結(jié)果 PAGEREF _Toc360453541 h 15HYPERLINK l _Toc3604535424.2 程序運(yùn)行結(jié)果分析 PAGEREF _Toc360453542 h 16HYPERLINK l _Toc3604535435.總結(jié) PAGEREF _Toc360453543 h 18HYPERLINK l _Toc360453544參考文獻(xiàn) PAGEREF _Toc360453544 h 19摘要本論文首先介紹了圖像壓縮相關(guān)知識。隨后，分析概述了哈夫曼壓縮編碼的原理與方法，并采用

7、 MATLAB 軟件對兩幅圖片進(jìn)行壓縮編碼程序設(shè)計，獲得壓縮信息與哈夫曼編碼表，分析壓縮后的圖像像素數(shù)據(jù)與壓縮比。關(guān)鍵詞： 圖像壓縮；MATLAB；哈夫曼編碼;無損壓縮編碼ABSTRACTThis paper firstly introduces the theoretical knowledgeof image compression. Then, it analyses the principle and method of Huffman codingand using Huffman coding principle and methods, compression coding de

8、sign is made for two images on the MATLAB software.Also gain the compression information and Huffman coding table. Whats more, compressed image pixel data and compression ratio are analyzed. Key words： Image compression; MATLAB; Huffman encoding;Lossless compression coding1引言1.1圖像數(shù)據(jù)壓縮的目的數(shù)字圖像通常要求很大的比

9、特數(shù)，這給圖像的傳輸和存儲帶來相當(dāng)大的困難。要占用很多的資源，花很高的費(fèi)用。一般原始圖像中存在很大的冗余度。例如1；一幅512x512的灰度圖象的比特數(shù)為512x512x8=256k 。例如2；一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8 bit，總比特數(shù)為90 x60 x24x3x512x512x8bit=97,200M。 例如3：一CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影光圖像（還有聲音）就需要160CD光盤用來存儲。所以，對圖像數(shù)據(jù)進(jìn)行壓縮顯得非常必要。而通常用戶通常允許圖像失真；當(dāng)信道的分辨率不與原始圖像的分辨率時，降低輸入

10、的原始圖像的分辨率對輸出圖像分辨率影響不大；用戶對原始圖像的信號不全都感興趣，可用特征提取和圖像識別的方法，丟掉大量無用的信息；提取有用的信息，使必須傳輸和存儲的圖像數(shù)據(jù)大大減少。在以上的條件下，其為數(shù)據(jù)壓縮提供了可能性。圖像數(shù)據(jù)壓縮的目的是在滿足一定圖像質(zhì)量條件下，用盡可能少的比特數(shù)來表示原始圖像，以提高圖像傳輸?shù)男屎蜏p少圖像存儲的容量。在信息論中稱為信源編碼。1.2圖像數(shù)據(jù)壓縮的原理對數(shù)字圖像進(jìn)行壓縮通常利用兩個基本原理:一是數(shù)字圖像的相關(guān)性。在圖像的同一行相鄰象素之間，相鄰象素之間，活動圖像的相鄰幀的對應(yīng)象素之間往往存在很強(qiáng)的相關(guān)性，去除或減少這些相關(guān)性，也即去除或減少圖像信息中的冗余

11、度也就實(shí)現(xiàn)了對數(shù)字圖像的壓縮。幀象素的相關(guān)稱做空域相關(guān)性。相鄰幀間對應(yīng)象素之間的相關(guān)性稱做時域相關(guān)性。二是人的視覺心理特征。人的視覺對于邊緣急劇變化不敏感(視覺掩蓋效應(yīng))，對顏色分辨力弱，利用這些特征可以在相應(yīng)部分適當(dāng)降低編碼精度而使人從視覺上并不感覺到圖像質(zhì)量的下降，從而達(dá)到對數(shù)字圖像壓縮的目的。圖像壓縮是通過刪除圖像數(shù)據(jù)中冗余的或者不必要的部分來減小圖像數(shù)據(jù)量的技術(shù)，壓縮過程就是編碼過程，解壓縮過程就是解碼過程。壓縮技術(shù)分為無損壓縮和有損壓縮兩大類，前者在解碼時可以精確地恢復(fù)原圖像，沒有任何損失；后者在解碼時只能近似原圖像，不能無失真地恢復(fù)原圖像。假設(shè)有一個無記憶的信源,它產(chǎn)生的消息為ai

12、,1iN,其出現(xiàn)的概率是已知的,記為P(ai)。則其信息量定義為:由此可見一個消息出現(xiàn)的可能性越小，其信息量就越多，其出現(xiàn)對信息的貢獻(xiàn)量越大，反之亦然。信源的平均信息量稱為“熵”（entropy），可以表示為：對上式取以2為底的對數(shù)時，單位為比特（bits）：根據(jù)香農(nóng)（Shannon）無噪聲編碼定理，對于熵為H的信號源，對其進(jìn)行無失真編碼所可能達(dá)到的最低比特數(shù)為，這里為一任意小的正數(shù)，因此可能達(dá)到的 最大壓縮比：其中B是原始圖像的平均比特率。在圖像壓縮中，壓縮比是一個重要的衡量指標(biāo)。可以定義壓縮比為：圖像的平均碼字長度R為：編碼效率定義為:信息冗余度為：1.3常用的壓縮編碼方法圖1-1常用的壓

13、縮編碼方法2哈夫曼編碼2.1 哈夫曼編碼簡介哈夫曼編碼是哈夫曼博士在1952 年根據(jù)可變長最佳編碼定理提出的, 它依據(jù)信源數(shù)據(jù)中各信號出現(xiàn)的頻率分配不同長度的編碼。即，對于出現(xiàn)概率大的信息符號編以短字長的碼，對于出現(xiàn)概率小的信息符號編以長字長的碼。采用哈夫曼編碼方法的實(shí)質(zhì)是針對統(tǒng)計結(jié)果對字符本身重新編碼，而不是對重復(fù)字符或重復(fù)子串編碼，得到的單位像素的比特數(shù)最接近圖像的實(shí)際熵值。它是一種無損編碼方法。2.2哈夫曼編碼步驟其具體步驟如下：1.將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。2.把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的

14、概率加起來，合成一個概率。 3.重復(fù)上述做法，直到最后剩下兩個概率為止。4.從最后一步剩下的兩個概率開始逐步向前進(jìn)行編碼。每步只需對兩個分支各賦予一個二進(jìn)制碼，如對概率大的賦予碼0，對概率小的賦予碼1。例如：假設(shè)信源符號為a、b、c、d、e、f、g，其出現(xiàn)的概率相應(yīng)的為0.25、0.025、0.025、0.05、0.35、0.25、0.05，一共7個字符，對其進(jìn)行哈夫曼編碼，算法如下：首先按照每個字符出現(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)的頻率之和作

15、為根節(jié)點(diǎn)。把原排列中最小的兩個節(jié)點(diǎn)刪除，新的根節(jié)點(diǎn)插入排列保持大小從左到右的排列順序不變；重復(fù)執(zhí)行2），直到最后得到值為1 的根節(jié)點(diǎn)。得到一棵哈夫曼樹，如下圖所示：圖 2.1哈夫曼編碼樹在得到的哈夫曼樹上左分支標(biāo)記1，右分支標(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七個字符的哈夫曼編碼分別是：10、0001、0000、0011、11、01、0010，可以看到,符號只能出現(xiàn)在樹葉上,任何一個字符的路徑都不會是另一字符路徑的前綴路徑。2.3 哈夫曼編碼的缺點(diǎn)哈夫曼編碼雖然是最佳編碼，但存

16、在一些缺點(diǎn)，具體如下：（1）對于過短的文件進(jìn)行編碼，意義不大。因?yàn)榇鎯蚵鼧涞男畔⑿枰欢ǖ拇鎯臻g；（2）利用哈夫曼編碼，若用于通信網(wǎng)絡(luò)，會引起較大的延時；（3）對較大文件進(jìn)行編碼，會出現(xiàn)頻繁的磁盤讀寫訪問，降低了數(shù)據(jù)編碼的速度。3基于哈夫曼編碼的圖像編解碼系統(tǒng)的程序設(shè)計3.1 分塊程序設(shè)計分析（1）首先，尋找出現(xiàn)的所有元素，接著計算各元素出現(xiàn)的概率，并將元素按照出現(xiàn)概率排列，產(chǎn)生碼字。部分程序如下：function huffcode，info=codeing（vector）p=probability（vector）； %計算各元素出現(xiàn)的概率simbols=find（p）； %尋找出現(xiàn)的所

17、有元素p=p（simbols）；p，sortindex=sort（p）； %概率從小到大排列simbols=simbols（sortindex）；%將元素按照出現(xiàn)概率排列l(wèi)en=length（simbols）；%產(chǎn)生碼字（2）把出現(xiàn)的元素概率最小的兩個相加合并成新的概率，與剩余的概率組成新的概率集合，直到剩下最后兩個概率。部分程序如下：while length（p）1；index1=simbols_index1；index2=simbols_index2；codeword_tmp （index1） =addnode （codeword_tmp（index1），uint8（0）；codeword

18、_tmp （index2） =addnode （codeword_tmp（index2），uint8（1）；p=sum（p（1:2） p（3:end）；simbols_index =index1 index2 simbols_index（3:end）；p，sortindex=sort（p）；%將數(shù)據(jù)重新排列simbols_index=simbols_index（sortindex）；（3）從最后一步開始反向進(jìn)行分配碼字，對于每次相加的兩個概率，給大的賦“0”，小的賦“1”，存儲到一個稀疏矩陣，最后寫出01 序列的哈夫曼編碼。部分程序如下：pad=8-mod（len，8）；if pad0；str

19、ing=string uint8（zeros（1，pad）；endcols=length（string）/8；%計算壓縮后的向量string=reshape（string，8，cols）；weights=2.（0:7）；huffcode =uint8 （weights*double （string）；% 編碼字符串湊成一個%字節(jié)一個字節(jié)存在huffcodecodeword=codeword（simbols）；%保存實(shí)際有出現(xiàn)元素對應(yīng)的碼字（4）把整字節(jié)存儲的huffcode 一位一位取出，轉(zhuǎn)為字符串，去掉原來為湊整字節(jié)數(shù)所添加的零進(jìn)行解碼。部分解碼程序如下：vector=zeros（1，inf

20、o.length，uint8）；%解碼vectorindex=1；codeindex=1；code=0；for index=1:len；code=bitset（code，codeindex，string（index）；codeindex=codeindex+1；byte =info.codetable （bitset （code，codeindex）；%從碼字表中讀出對應(yīng)元素if byte0；vector（vectorindex）=byte-1；codeindex=1；code=0；vectorindex=vectorindex+1；（5）顯示編碼的壓縮信息（如壓縮率、最大碼長等），部分程序如

21、下所示：whos data huffcode huffdecode %顯示壓縮效果fprintf（pad=%dn，info.pad）； %info.pad=為湊整字節(jié)數(shù)，編碼字符串最后添加零的位數(shù)fprintf （ratio=%fn，info.ratio）； %info.ratio=壓縮率fprintf （maxcodelen=%dn，info.maxcodelen）；%info.maxcodelen=最大碼長3.2主程序系統(tǒng)設(shè)計的完整主程序如下%主程序% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03clcclearcd;X=imread

22、(watch.bmp);data=uint8(X); zipped,info=huffencode(data); unzipped=huffdecode(zipped,info);subplot(121);imshow(data);title(原始圖像)subplot(122);imshow(unzipped);title(解碼后的圖像)whos data unzipped zippedfprintf(pad=%dn,info.pad); %info.pad=為湊整字節(jié)數(shù)，編碼字符串最后添加零的位數(shù)fprintf(ratio=%fn,info.ratio); %info.ratio=壓縮率fp

23、rintf(maxcodelen=%dn,info.maxcodelen);%info.maxcodelen=最大碼長3.3程序函數(shù)3.3.1編碼函數(shù)主程序中使用的函數(shù)代碼如下%編碼函數(shù)% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03%huffencode函數(shù)對輸入矩陣vector進(jìn)行huffman編碼，返回編碼后的向量與相關(guān)信息function zipped,info= huffencode(vector) if isa(vector,uint8) eror(input argument must be a uint8 vector);

24、 end m,n=size(vector); vector=vector(:); f=frequency(vector); symbols=find(f=0); f=f(symbols); f,sortindex=sort(f); symbols=symbols(sortindex); len=length(symbols); symbols_index=num2cell(1:len); codeword_tmp=cell(len,1); while length(f)1 index1=symbols_index1; index2=symbols_index2; codeword_tmp(in

25、dex1)=addnode(codeword_tmp(index1),uint8(0); codeword_tmp(index2)=addnode(codeword_tmp(index2),uint8(1); f=sum(f(1:2) f(3:end); symbols_index=index1,index2 symbols_index(3:end); f,sortindex=sort(f); symbols_index=symbols_index(sortindex); end codeword=cell(256,1); codeword(symbols)=codeword_tmp; len

26、=0; for index=1:length(vector) len=len+length(codeworddouble(vector(index)+1); end string=repmat(uint8(0),1,len); pointer=1; for index=1:length(vector) code=codeworddouble(vector(index)+1; len=length(code); string(pointer+(0:len-1)=code; pointer=pointer+len; end len=length(string); pad=8-mod(len,8);

27、 if pad0 string=string uint8(zeros(1,pad); end codeword=codeword(symbols); codelen=zeros(size(codeword); weights=2.(0:23); maxcodelen=0; for index=1:length(codeword) len=length(codewordindex); if lenmaxcodelen maxcodelen=len; end if len0 code=sum(weights(codewordindex=1); code=bitset(code,len+1); co

28、dewordindex=code; codelen(index)=len; end end codeword=codeword:; %計算壓縮后的向量 cols=length(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 %填寫解碼

29、時所需的結(jié)構(gòu)信息 info.pad=pad; info.huffcodes=huffcodes; info.ratio=cols./length(vector); info.length=length(vector); info.maxcodelen=maxcodelen; info.rows=m; info.cols=n; %huffdecode函數(shù)對輸入矩陣vector進(jìn)行Huffman編碼，%返回解壓后的圖像數(shù)據(jù)3.3.2解碼函數(shù)%解碼函數(shù)% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03%huffdecode函數(shù)對輸入矩陣vecto

30、r進(jìn)行huffman解碼，返回解壓后的圖像數(shù)據(jù)function vector=huffdecode(zipped,info) if isa(zipped,uint8) error(input argument must be a uint8 vector); end %產(chǎn)生0，1序列，每位占一個字節(jié) len=length(zipped); string=repmat(uint8(0),1,len.*8); bitindex=1:8; for index=1:len string(bitindex+8.*(index-1)=uint8(bitget(zipped(index),bitindex)

31、; end string=logical(string(:); len=length(string); string(len-info.pad+1):end)=; 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(index); codeindex=codeindex+1; byte=decode(bitset

32、(code,codeindex),info); if byte0 vector(vectorindex)=byte-1; codeindex=1; code=0; vectorindex=vectorindex+1; end end vector=reshape(vector,info.rows,info.cols);3.3.3符號概率計算函數(shù)%函數(shù)frequency計算各符號出現(xiàn)的概率% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03function f=frequency(vector)ifisa(vector,uint8) error

33、(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;3.3.4節(jié)點(diǎn)添加函數(shù)%函數(shù)addnode添加節(jié)點(diǎn)% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03function codeword_new=addnode(codeword_old,item)codeword_new=cell(size(codeword_

34、old);for index=1:length(codeword_old) codeword_newindex=item codeword_oldindex;end3.3.5解碼返回符號函數(shù)%函數(shù)decode返回碼字對應(yīng)的符號% 信息處理課群綜合訓(xùn)練與設(shè)計-基于哈夫曼編碼的圖像編解碼系統(tǒng)設(shè)計與實(shí)現(xiàn)%信息SY1001班-王鳴-03function byte=decode(code,info)byte=info.huffcodes(code);4系統(tǒng)仿真結(jié)果4.1程序運(yùn)行結(jié)果根據(jù)設(shè)計好的程序加載到MATLAB軟件中(即m文件)，運(yùn)行輸出結(jié)果。選擇一幅位圖圖像（watch.bmp）進(jìn)行哈夫曼編碼壓縮

35、編碼，得到輸出結(jié)果如下：圖4-1位圖圖像壓縮編碼輸出結(jié)果1圖4-2位圖圖像壓縮編碼輸出結(jié)果2選擇一幅jpg圖像（王鳴.jpg）進(jìn)行哈夫曼編碼壓縮編碼，得到輸出結(jié)果如下：圖4-3jpg圖像壓縮編碼輸出結(jié)果1圖4-4jpg圖像壓縮編碼輸出結(jié)果24.2 程序運(yùn)行結(jié)果分析（1）圖像壓縮、解壓縮整個過程大約要花23 min，一開始不知道，以為死機(jī)，后來稍等會就會出結(jié)果； （2）認(rèn)真觀察原始圖像和新圖像，比較發(fā)現(xiàn)：新舊的位圖圖像視覺效果相差不大，但是其文件大小卻變小了。如watch圖像262144bytes減小到233877bytes。壓縮率為0.892170。由此可說明，哈夫曼編碼是一種無損壓縮編碼,它不會造成信息損失,解壓縮時能夠從壓縮數(shù)據(jù)精確地恢復(fù)原始圖像。（3）比較兩幅不同大小的位圖的壓縮比可知，對不同的信源，哈夫曼編碼的壓縮比不同。（4）后者為jpg彩色圖像，有RGB三個分量，所以其輸出有三個分量