基于MATLAB的圖像Huffman編碼研究

./成績評閱人中國礦業(yè)大學(xué)2015-2016學(xué)年第二學(xué)期《數(shù)字視頻技術(shù)》課程小設(shè)計考核圖像的Huffman編碼研究專業(yè)班級：信息13-04班學(xué)生：王振宇、龍航、王一鳴學(xué)生學(xué)號：04131407、04131403、04131406本人重聲明：本人認(rèn)真、獨(dú)立完成了查找資料、完成作業(yè)、編寫程序等考核任務(wù),無抄襲行為。簽字：日期：2引言圖像數(shù)據(jù)壓縮的目的數(shù)字圖像通常要求很大的比特數(shù),這給圖像的傳輸和存儲帶來相當(dāng)大的困難。要占用很多的資源,花很高的費(fèi)用。一般原始圖像存在很大的冗余度。所以,對圖像數(shù)據(jù)壓縮顯得非常重要。圖像數(shù)據(jù)壓縮的原理對數(shù)字圖像壓縮主要運(yùn)用兩個基本原理：一是圖像的相關(guān)性。在圖像同一相鄰像素之間,活動圖像的相鄰幀的對應(yīng)像素之間往往存在很強(qiáng)的相關(guān)性,去除或減少這些相關(guān)性,也就除去或減少圖像信息中的冗余度,繼而實現(xiàn)對數(shù)字圖像的壓縮。二是人的視覺心理特征,人的視覺對于邊緣急劇變化不敏感,對顏色分辨力弱,利用這些特征在相應(yīng)部分降低編碼精度而使人從視覺上感覺不到圖像質(zhì)量的下降,從而達(dá)到對數(shù)字圖像壓縮的目的。Huffman編碼Huffman編碼是一種編碼方式,是一種用于無損數(shù)據(jù)壓縮的熵編碼算法。它是Huffman在1952年根據(jù)Shannon在1948年和Fano在1949年闡述的這種編碼思想下提出的一種不定長編碼的方法,有時也稱之為最佳編碼。依據(jù)信源數(shù)據(jù)中各信號出現(xiàn)的頻率分配不同長度的編碼。其基本思想是在編碼過程中,對出現(xiàn)頻率越高的值,分配越短的編碼長度,相應(yīng)地對出現(xiàn)頻率越低的值則分配較長的編碼長度,完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字。哈夫曼編碼方法的實質(zhì)是針對統(tǒng)計結(jié)果對字符本身重新編碼,而不是對重復(fù)字符或重復(fù)子串編碼,得到的單位像素的比特數(shù)最接近圖像的實際熵值。設(shè)計任務(wù)設(shè)計任務(wù)研究實現(xiàn)灰度圖像的Huffman編碼和解碼恢復(fù)。設(shè)計目的了解Huffman編碼的基本原理及其特點(diǎn)；理解并熟練對圖像進(jìn)行哈夫曼編碼的算法；學(xué)習(xí)和熟悉MATLAB圖像處理工具箱；熟悉和掌握MATLAB程序設(shè)計方法；設(shè)計要求現(xiàn)灰度圖像的Huffman編碼和解碼恢復(fù)圖像；處理結(jié)果要求最終圖像顯示,且計算圖像的信息熵,平均碼字長度,編碼效率,壓縮比?？傮w設(shè)計方案系統(tǒng)運(yùn)行環(huán)境Windows8.1/10系統(tǒng)編程軟件平臺MATLABR2013a/R2014aHuffman編碼算法原理哈夫曼編碼的基本方法是先對圖像數(shù)據(jù)掃描一遍,計算出各種像素出現(xiàn)的概率,按概率的大小指定不同長度的唯一碼字,由此得到一該圖像的哈夫曼碼表。編碼后的圖像數(shù)據(jù)記錄的是每個像素的碼字,而碼字與實際像素值的對應(yīng)關(guān)系記錄在碼表中。計算信源符號出現(xiàn)的概率；將信源符號按其出現(xiàn)的概率,由小到大順序排列,并從左至右排列為葉節(jié)點(diǎn)[1]；將兩個概率最小的頂層節(jié)點(diǎn)進(jìn)行組合相加,組成一個父節(jié)點(diǎn),并在到左右子節(jié)點(diǎn)的兩條連線上分別標(biāo)記0和1；重復(fù)上一步驟,直到得到根節(jié)點(diǎn),形成一顆二叉樹；從根節(jié)點(diǎn)開始到相應(yīng)于每個符號的葉節(jié)點(diǎn)的0/1串,就是該符號的二進(jìn)制哈夫曼編碼。Huffman編碼算法的特點(diǎn)編出來的碼都是異字頭碼,保證了碼的唯一可譯性。由于編碼長度可變。因此譯碼時間較長,使得哈夫曼編碼的壓縮與還原相當(dāng)費(fèi)時。編碼長度不統(tǒng)一,硬件實現(xiàn)有難度。對不同信源的編碼效率不同,當(dāng)信源的符號概率為2的負(fù)冪次方時,達(dá)到100％的編碼效率；若信源符號的概率相等,則編碼效率最低。由于符號按概率大小排列既可以從右到左也可以從左到右,即0與1的指定是任意的,故最后的編碼結(jié)果可能不唯一,但僅僅是分配的代碼不同,其平均碼長是一樣的,故不影響編碼效率與數(shù)據(jù)壓縮性能。算法流程圖設(shè)計主流程圖開始開始加載圖像,并將其灰度化將灰度圖像轉(zhuǎn)換成無符號的8位整數(shù)矩陣調(diào)用Huffman編碼程序進(jìn)行壓縮調(diào)用Huffman解碼程序進(jìn)行解碼顯示原始圖像、灰度圖像和經(jīng)編碼解碼后的圖像結(jié)束顯示平均碼長、壓縮比、信息熵及編碼效率編碼流程圖開始開始計算各符號〔灰度值出現(xiàn)概率按照概率從小到大排序生成Huffman樹得到二進(jìn)制哈夫曼編碼碼字對圖像〔圖像矩陣進(jìn)行編碼計算編碼參數(shù)〔平均碼長、信息熵等計算二進(jìn)制碼字對應(yīng)的十進(jìn)制數(shù),并存入矩陣中,得到碼字與灰度值的對應(yīng)關(guān)系表,即碼表結(jié)束解碼流程圖開始開始結(jié)束讀取壓縮矩陣,并存入行向量中解碼后的矩陣按圖像矩陣尺寸重排,得到解碼矩陣解碼,按位讀取行向量中的編碼并進(jìn)行相應(yīng)灰度值匹配組員任務(wù)分工王振宇：編寫主要程序,編碼解碼函數(shù)程序及相關(guān)子程序,修改報告及演示文稿。龍航：編寫部分主程序及部分函數(shù)程序,撰寫報告。王一鳴：編寫部分程序,進(jìn)行程序調(diào)試完善,制作演示文稿。程序?qū)崿F(xiàn)函數(shù)主程序clc;clear;closeall;X=imread<'peppers.JPG'>;%圖像灰度化R=X<:,:,1>;G=X<:,:,2>;B=X<:,:,3>;Y=0.299*R+0.587*G+0.114*B;subplot<1,3,1>;imshow<X>;title<'原始圖像'>;data=uint8<Y>;[zipped,info]=huffencode<data>;%調(diào)用Huffman編碼程序進(jìn)行壓縮unzipped=huffdecode<zipped,info>;%調(diào)用Huffman編碼程序進(jìn)行解碼%顯示原始圖像,灰度化圖像和經(jīng)編碼解碼后的圖像subplot<1,3,2>;imshow<data>;title<'灰度化圖像'>;subplot<1,3,3>;imshow<unzipped>;title<'Huffman編碼并解碼后圖像'>;disp<'平均碼長'>;L=info.avalendisp<'壓縮比'>;CR=info.ratiodisp<'信息熵'>;H=info.hdisp<'編碼效率'>;CE=info.ce編碼程序%huffencode函數(shù)對輸入矩陣vector進(jìn)行Huffman編碼,返回編碼后的數(shù)據(jù)及相關(guān)信息function[zipped,info]=huffencode<vector>if~isa<vector,'uint8'>%確定輸入矩陣是uint8格式error<'inputargumentmustbeauint8vector'>;end[m,n]=size<vector>;%求輸入矩陣的行列數(shù)vector=vector<:>';%將矩陣按列轉(zhuǎn)換成一列后轉(zhuǎn)至,成為一個行向量<其中存放灰度值>f=frequency<vector>;%計算各符號出現(xiàn)的概率symbols=find<f~=0>;%返回概率矩陣中非零元素的位置向量,作為符號向量f=f<symbols>;%非零概率位置上的概率值組成非零概率行向量[f,sortindex]=sort<f>;%將符號按照出現(xiàn)的概率從小到大排序,并保留非零概率向量位置索引fs=f;symbols=symbols<sortindex>;%讀出原位置向量中的值〔即概率向量中的位置,得到按概率排序后的符號向量len=length<symbols>;%讀取位置向量的長度symbols_index=num2cell<1:len>;%生成從1開始以1遞增,1行l(wèi)en列的細(xì)胞型矩陣codeword_tmp=cell<len,1>;%創(chuàng)建一個len行1列的細(xì)胞型變量用于存放碼字whilelength<f>>1%生成Huffman樹,得到二進(jìn)制碼字編碼表index1=symbols_index{1};index2=symbols_index{2};codeword_tmp<index1>=addnode<codeword_tmp<index1>,uint8<0>>;%添加節(jié)點(diǎn)且該分支按0標(biāo)記codeword_tmp<index2>=addnode<codeword_tmp<index2>,uint8<1>>;%添加節(jié)點(diǎn)且該分支按1標(biāo)記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>;%得到新的索引表endcodeword=cell<256,1>;codeword<symbols>=codeword_tmp;%各符號二進(jìn)制碼字按原符號位存入細(xì)胞型矩陣len=0;fori=1:length<symbols>%得到各符長矩陣wordlen<i>=length<codeword_tmp{i}>;endavawordlen=fs*wordlen';%計算平均碼長Hlog=log2<fs>';H=-<fs*Hlog>;%計算信息熵forindex=1:length<vector>%得到整個圖像各點(diǎn)灰度值轉(zhuǎn)化為二進(jìn)制碼字后的總比特數(shù)len=len+length<codeword{double<vector<index>>+1}>;endstring=repmat<uint8<0>,1,len>;%創(chuàng)建元素數(shù)與總比特數(shù)一致的行向量pointer=1;%定義指針變量forindex=1:length<vector>%對輸入圖像進(jìn)行編碼code=codeword{double<vector<index>>+1};%對應(yīng)符號的二進(jìn)制碼字給codelen=length<code>;%讀取碼字長度string<pointer+<0:len-1>>=code;%將二進(jìn)制碼字存入行向量中pointer=pointer+len;%指針移移位end%將二進(jìn)制編碼按照每8位生成一個新字符。len=length<string>;zp=8-mod<len,8>;ifzp>0string=[stringuint8<zeros<1,zp>>];%不足8位的在后補(bǔ)零endcodeword=codeword<symbols>;%碼字按符號概率放入列向量中codelen=zeros<size<codeword>>;%創(chuàng)建與列向量元素數(shù)相同的列向量weights=2.^<0:23>;maxcodelen=0;forindex=1:length<codeword>len=length<codeword{index}>;%讀二進(jìn)制碼字長度iflen>0code=sum<weights<codeword{index}==1>>;%計算二進(jìn)制碼字對應(yīng)的十進(jìn)制數(shù)code=bitset<code,len+1>;%將碼字最高位的上一位置1codeword{index}=code;codelen<index>=len;%碼字長度存入列向量中endendcodeword=[codeword{:}];%轉(zhuǎn)化為行向量%計算壓縮后的向量cols=length<string>/8;string=reshape<string,8,cols>;weights=2.^<0:7>;zipped=uint8<weights*double<string>>;%碼表存儲到一個稀疏矩陣huffcodes=sparse<1,1>;forindex=1:nnz<codeword>huffcodes<codeword<index>,1>=symbols<index>;end%返回編碼參數(shù)info.zeropad=zp;%info.zeropad是添加的比特數(shù)info.huffcodes=huffcodes;%info.huffcodes是Huffman碼字表info.length=length<vector>;%info.length是灰度化圖像矩陣長度info.rows=m;%info.rows是灰度化圖像行數(shù)info.cols=n;%info.cols是灰度化圖像列數(shù)info.avalen=avawordlen;%info.ratio是平均碼長info.ratio=8/avawordlen;%info.ratio是壓縮比info.h=H;%info.h是信息熵info.ce=H/avawordlen;%info.ce是計算編碼效率%函數(shù)frequency計算各符號出現(xiàn)的概率functionf=frequency<vector>if~isa<vector,'uint8'>%確定矩陣是uint8格式error<'inputargumentmustbeauint8vector'>;endf=zeros<1,256>;%設(shè)置一個256個元素都為0的行向量len=length<vector>;%讀取輸入矩陣元素個數(shù)forindex=0:1:255f<index+1>=sum<vector==index>;%統(tǒng)計輸入圖像矩陣中0至255各值出現(xiàn)的個數(shù),存入一個行向量中endf=f./len;%求各符號值出現(xiàn)的概率%函數(shù)addnode添加節(jié)點(diǎn)確定符字functioncodeword_new=addnode<codeword_old,item>codeword_new=cell<size<codeword_old>>;%前一步碼字維數(shù)作為新細(xì)胞型變量的維數(shù),用于存放碼字forindex=1:length<codeword_old>%確定符號對應(yīng)碼字codeword_new{index}=[itemcodeword_old{index}];end譯碼程序%huffdecode函數(shù)對輸入矩陣vector進(jìn)行Huffman編碼,返回解壓后的圖像數(shù)據(jù)functionvector=huffdecode<zipped,info>if~isa<zipped,'uint8'>%確定壓縮矩陣是uint8格式error<'inputargumentmustbeauint8vector'>;endlen=length<zipped>;%讀取壓縮矩陣長度string=repmat<uint8<0>,1,len*8>;%創(chuàng)建全為0的行向量bitindex=<1:8>;forindex=1:lenstring<bitindex+8.*<index-1>>=uint8<bitget<zipped<index>,bitindex>>;%讀取壓縮矩陣中的值并轉(zhuǎn)化為8位二進(jìn)制按順序放入string矩陣中endlen=length<string>;%開始解碼weights=2.^<0:51>;vector=repmat<uint8<0>,1,info.length>;%創(chuàng)建與灰度化圖像行向量等長的行向量vectorindex=1;codeindex=1;code=0;forindex=1:len-1code=bitset<code,codeindex,string<index>>;%按位讀編碼碼字codeindex=codeindex+1;%移位byte=decode<bitset<code,codeindex>,info>;%進(jìn)行碼字匹配,讀取相對應(yīng)符號ifbyte>0%若讀取到對應(yīng)符號則進(jìn)行下面操作,無符號繼續(xù)按位讀取碼字vector<vectorindex>=byte-1;%將符號表示的灰度值放入容器矩陣中codeindex=1;%重置code=0;%重置vectorindex=vectorindex+1;%容器指針移位endendvector=reshape<vector,info.rows,info.cols>;%將構(gòu)成的灰度矩陣按原圖矩陣行列數(shù)重構(gòu),解碼完成%函數(shù)decode返回碼字