成績(jī)?cè)u(píng)定表學(xué)生姓名班級(jí)學(xué)號(hào)1203030119專(zhuān)業(yè)電子信息工程課程設(shè)計(jì)題目圖像的無(wú)損壓縮程序設(shè)計(jì)——霍夫曼編碼評(píng)語(yǔ)組長(zhǎng)簽字：成績(jī)?nèi)掌?015年7月20日課程設(shè)計(jì)任務(wù)書(shū)學(xué)院信息科學(xué)與工程專(zhuān)業(yè)電子信息工程學(xué)生姓名班級(jí)學(xué)號(hào)1203030119課程設(shè)計(jì)題目圖像的無(wú)損壓縮程序設(shè)計(jì)——霍夫曼編碼實(shí)踐教學(xué)要求與任務(wù)：本課題通過(guò)MATLAB編寫(xiě)適當(dāng)?shù)暮瘮?shù)，對(duì)一個(gè)隨機(jī)信源進(jìn)行哈夫曼編碼，得出碼字，平均碼長(zhǎng)和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過(guò)程與特點(diǎn)，并且提高綜合運(yùn)用所學(xué)理論知識(shí)獨(dú)立分析和解決問(wèn)題的能力。工作計(jì)劃與進(jìn)度安排：2015年7月8日—11日：熟悉編程環(huán)境，查閱相關(guān)資料。2015年7月11日—12日：圖像的霍夫曼編碼程序設(shè)計(jì)。2015年7月12日—13日：編碼、調(diào)試、實(shí)驗(yàn)與分析。2015年7月13日—15日：撰寫(xiě)課程設(shè)計(jì)報(bào)告。2015年7月15日—19日：準(zhǔn)備答辯。指導(dǎo)教師：2015年7月2日專(zhuān)業(yè)負(fù)責(zé)人：2015年7月2日學(xué)院教學(xué)副院長(zhǎng)：2015年7月2日摘要哈夫曼編碼(HuffmanCoding)是一種編碼方式，以哈夫曼樹(shù)—即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱(chēng)"熵編碼法"），用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。本課題通過(guò)MATLAB編寫(xiě)適當(dāng)?shù)暮瘮?shù)，對(duì)一個(gè)隨機(jī)信源進(jìn)行哈夫曼編碼，得出碼字，平均碼長(zhǎng)和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過(guò)程與特點(diǎn)，并且提高綜合運(yùn)用所學(xué)理論知識(shí)獨(dú)立分析和解決問(wèn)題的能力。關(guān)鍵字：哈夫曼；信源編碼；MATLAB

目錄HYPERLINK1設(shè)計(jì)目的及相關(guān)知識(shí) 1HYPERLINK1.1設(shè)計(jì)目的 1HYPERLINK1.2圖像的霍夫曼編碼概念 1HYPERLINK1.3Matlab圖像處理通用函數(shù) 1HYPERLINK2課程設(shè)計(jì)分析 3HYPERLINK2.1圖像的霍夫曼編碼概述 3HYPERLINK2.2圖像的霍夫曼編碼舉例 4HYPERLINK3仿真 6HYPERLINK4結(jié)果及分析 9HYPERLINK5附錄 12HYPERLINK結(jié)束語(yǔ) 15HYPERLINK參考文獻(xiàn) 161設(shè)計(jì)目的及相關(guān)知識(shí)1.1設(shè)計(jì)目的1）了解霍夫曼編碼的原理。2）理解圖像的霍夫曼編碼原理，了解其應(yīng)用，掌握?qǐng)D像的霍夫曼編碼的方法。3）對(duì)圖像編碼程序設(shè)計(jì)進(jìn)行較深入的認(rèn)識(shí)，對(duì)知識(shí)牢固掌握。4）掌握?qǐng)D像霍夫曼編碼的整個(gè)過(guò)程及其中的注意事項(xiàng)。5）了解圖像無(wú)損壓縮的目的及好處。1.2圖像的霍夫曼編碼概念所謂霍夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊(duì)，把兩個(gè)最小的概率相加，作為新的概率和剩余的概率重新排隊(duì)，再把最小的兩個(gè)概率相加，再重新排隊(duì)，直到最后變成1。每次相加時(shí)都將“0”和“1”賦與相加的兩個(gè)概率，讀出時(shí)由該符號(hào)開(kāi)始一直走到最后的“1”，將路線(xiàn)上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號(hào)的霍夫曼編碼1.3Matlab圖像處理通用函數(shù)colorbar

顯示彩色條語(yǔ)法：colorbar\colorbar('vert')\colorbar('horiz')\colorbar(h)\h=colorbar(...)\colorbar(...,'peer',axes_handle)getimage從坐標(biāo)軸取得圖像數(shù)據(jù)語(yǔ)法：A=getimage(h)\[x,y,A]=getimage(h)\[...,A,flag]=getimage(h)\[...]=getimageimshow顯示圖像語(yǔ)法：imshow(I,n)\imshow(I,[lowhigh])\imshow(BW)\imshow(X,map)\imshow(RGB)\imshow(...,display_option)\imshow(x,y,A,...)\imshowfilename\h=imshow(...)montage在矩形框中同時(shí)顯示多幅圖像語(yǔ)法：montage(I)\montage(BW)\montage(X,map)\montage(RGB)\h=montage(...)immovie創(chuàng)建多幀索引圖的電影動(dòng)畫(huà)語(yǔ)法：mov=immovie(X,map)\mov=immovie(RGB)subimage在一副圖中顯示多個(gè)圖像語(yǔ)法：subimage(X,map)\subimage(I)\subimage(BW)\

subimage(RGB)\subimage(x,y,...)\subimage(...)truesize調(diào)整圖像顯示尺寸語(yǔ)法：truesize(fig,[mrowsmcols])\truesize(fig)warp將圖像顯示到紋理映射表面語(yǔ)法：warp(X,map)\warp(I,n)\warp(z,...)warp(x,y,z,...)\

h=warp(...)zoom縮放圖像語(yǔ)法：zoomon\zoomoff\zoomout\zoomreset\zoom\zoomxon\zoomyon\zoom(factor)\zoom(fig,option)2課程設(shè)計(jì)分析2.1圖像的霍夫曼編碼概述赫夫曼（Huffman）編碼是1952年提出的，是一種比較經(jīng)典的信息無(wú)損熵編碼，該編碼依據(jù)變長(zhǎng)最佳編碼定理，應(yīng)用Huffman算法而產(chǎn)生。Huffman編碼是一種基于統(tǒng)計(jì)的無(wú)損編碼。根據(jù)變長(zhǎng)最佳編碼定理，Huffman編碼步驟如下：（1）將信源符號(hào)xi按其出現(xiàn)的概率，由大到小順序排列。（2）將兩個(gè)最小的概率的信源符號(hào)進(jìn)行組合相加，并重復(fù)這一步驟，始終將較大的概率分支放在上部，直到只剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止；（3）對(duì)每對(duì)組合的上邊一個(gè)指定為1，下邊一個(gè)指定為0（或相反：對(duì)上邊一個(gè)指定為0，下邊一個(gè)指定為1）；（4）畫(huà)出由每個(gè)信源符號(hào)到概率1.0處的路徑，記下沿路徑的1和0；（5）對(duì)于每個(gè)信源符號(hào)都寫(xiě)出1、0序列，則從右到左就得到非等長(zhǎng)的Huffman碼。Huffman編碼的特點(diǎn)是：（1）Huffman編碼構(gòu)造程序是明確的，但編出的碼不是唯一的，其原因之一是兩個(gè)概率分配碼字“0”和“1”是任意選擇的（大概率為“0”，小概率為“1”，或者反之）。第二原因是在排序過(guò)程中兩個(gè)概率相等，誰(shuí)前誰(shuí)后也是隨機(jī)的。這樣編出的碼字就不是唯一的。（2）Huffman編碼結(jié)果，碼字不等長(zhǎng)，平均碼字最短，效率最高，但碼字長(zhǎng)短不一，實(shí)時(shí)硬件實(shí)現(xiàn)很復(fù)雜（特別是譯碼），而且在抗誤碼能力方面也比較差。（3）Huffman編碼的信源概率是2的負(fù)冪時(shí)，效率達(dá)100%，但是對(duì)等概率分布的信源，產(chǎn)生定長(zhǎng)碼，效率最低，因此編碼效率與信源符號(hào)概率分布相關(guān)，故Huffman編碼依賴(lài)于信源統(tǒng)計(jì)特性，編碼前必須有信源這方面的先驗(yàn)知識(shí)，這往往限制了霍夫曼編碼的應(yīng)用。（4）Huffman編碼只能用近似的整數(shù)位來(lái)表示單個(gè)符號(hào)，而不是理想的小數(shù)，這也是Huffman編碼無(wú)法達(dá)到最理想的壓縮效果的原因。2.2圖像的霍夫曼編碼舉例假設(shè)一個(gè)文件中出現(xiàn)了8種符號(hào)S0，S1，S2，S3，S4，S5，S6，S7，那么每種符號(hào)要編碼，至少需要3比特。假設(shè)編碼成000，001，010，011，100，101，110，111那么符號(hào)序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成000001111000001110010010011100101000000001，共用了42比特。我們發(fā)現(xiàn)S0，S1，S2這三個(gè)符號(hào)出現(xiàn)的頻率比較大，其它符號(hào)出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號(hào)的碼字長(zhǎng)，這樣就能夠減少占用的比特?cái)?shù)。例如，我們采用這樣的編碼方案：S0到S7的碼字分別01，11，101，0000，0001，0010，0011，100，那么上述符號(hào)序列變成011110001110011101101000000010010010111，共用了39比特，盡管有些碼字如S3，S4，S5，S6變長(zhǎng)了(由3位變成4位)，但使用頻繁的幾個(gè)碼字如S0，S1變短了，所以實(shí)現(xiàn)了壓縮?？捎上旅娴牟襟E得到霍夫曼碼的碼表首先把信源中的消息出現(xiàn)的頻率從小到大排列。每一次選出頻率最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。重復(fù)(2)，直到最后得到和為1的根節(jié)點(diǎn)。將形成的二叉樹(shù)的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0，1序列串起來(lái)，就得到了各個(gè)符號(hào)的編碼。上面的例子用Huffman編碼的過(guò)程如圖下圖所示，其中圓圈中的數(shù)字是新節(jié)點(diǎn)產(chǎn)生的順序。圖2-1

Huffman編碼的二叉樹(shù)示意圖信源的各個(gè)消息從S0到S7的出現(xiàn)概率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。計(jì)算編碼效率為98.5%，編碼的冗余只有1.5%，可見(jiàn)霍夫曼編碼效率很高。產(chǎn)生Huffman編碼需要對(duì)原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中，每個(gè)值出現(xiàn)的頻率，第二遍是建立Huffman樹(shù)并進(jìn)行編碼。由于需要建立二叉樹(shù)并遍歷二叉樹(shù)生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡(jiǎn)單有效，因而得到廣泛的應(yīng)用。3仿真主程序：%以下為主程序mainp.m

clc

clear

closeall;

%定義HufData/Len為全局變量的結(jié)構(gòu)體

globalHufData;

globalLen

disp('計(jì)算機(jī)正在準(zhǔn)備輸出霍夫曼編碼結(jié)果,請(qǐng)耐心等待……');

%原始碼字的灰度

a=imread('kids.tif');

%分區(qū)畫(huà)出原始圖像和灰度直方圖

figure;

subplot(1,2,1)

imshow(a);

%取消坐標(biāo)軸和邊框

axisoff

boxoff

title('MATLAB自帶圖像','fontsize',13);

subplot(1,2,2);

axisoff

boxoff

imhist(a);

title('圖像灰度直方圖','fontsize',13);

%圖像的灰度統(tǒng)計(jì)

GrayStatistics=imhist(a);

GrayStatistics=GrayStatistics';

GrayRatioo=GrayStatistics/sum(GrayStatistics);

GrayRatioNO=find(GrayRatioo~=0);

Len=length(GrayRatioNO);

%初始化灰度集，防止系統(tǒng)隨即賦予其垃圾值

GrayRatio=ones(1,Len);

fori=1:Len

GrayRatio(i)=GrayRatioo(i);

end

GrayRatio=abs(sort(-GrayRatio));

%將圖像灰度概率賦予結(jié)構(gòu)體

fori=1:Len

HufData(i).value=GrayRatio(i);

end

%霍夫曼編碼/霍夫曼編碼

HuffmanCode(Len);

%輸出碼字

zippedHuffman=1;

fori=1:Len

tmpData=HufData(i).code;

str='';

forj=1:length(tmpData)

str=strcat(str,num2str(tmpData(j)));

zippedHuffman=zippedHuffman+1;

end

disp(strcat('a',num2str(i),'=',str))

end

i;

%計(jì)算計(jì)算機(jī)一共輸出多少個(gè)霍夫曼編碼/霍夫曼編碼

zippedHuffman;

%計(jì)算在刪去0灰度級(jí)壓縮之前的原始圖像字節(jié)容量

unzipped_delete=i*8;

%計(jì)算壓縮比率

ratio_delete=zippedHuffman/unzipped_delete;

%計(jì)算圖像的壓縮比率

ad=num2str(ratio_delete*100);

str2=strcat(ad,'%');

disp(strcat('霍夫曼編碼壓縮比率','=',str2))4結(jié)果及分析結(jié)果:圖4-1輸出原圖像與該圖像像灰度直方圖計(jì)算機(jī)正在準(zhǔn)備輸出霍夫曼編碼結(jié)果,請(qǐng)耐心等待……a1=110a2=11110a3=11101a4=01100a5=01010a6=01000a7=00101a8=00011a9=111111a10=111001a11=101111a12=101100a13=101011a14=101010a15=101001a16=100111a17=100110a18=100100a19=100011a20=100010a21=100001a22=100000a23=011111a24=011110a25=011011a26=011010a27=010111a28=010110a29=010011a30=001111a31=001101a32=001100a33=001001a34=001000a35=000101a36=000011a37=000010a38=000001a39=000000a40=1111101a41=1111100a42=1110001a43=1110000a44=1011101a45=1011100a46=1011011a47=1010001a48=1010000a49=1001011a50=1001010a51=0111011a52=0111010a53=0111001a54=0111000a55=0100101a56=0100100a57=0011101a58=0011100a59=0001001a60=0001000a61=10110101a62=101101001a63=101101000霍夫曼編碼壓縮比率=78.9683%分析：從輸出灰度直方圖可得出該圖像的量化值主要集中在低灰度級(jí)處，通過(guò)輸出可以看到該灰度級(jí)對(duì)應(yīng)的霍夫曼編碼，并且輸出了該圖像的壓縮效率。明顯可得出霍夫曼編碼大大的節(jié)省了空間，可以明顯的減少發(fā)送時(shí)間。5附錄子程序：%子程序：霍夫曼編碼/霍夫曼編碼函數(shù)HuffmanCode.m

functionHuffmanCode(OriginSize)

globalHufData;

globalLen

fori=1:Len

%%霍夫曼編碼樹(shù)左邊紀(jì)錄為1

HufData(i).left=1;

%%霍夫曼編碼樹(shù)右邊紀(jì)錄為0

HufData(i).right=0;

%%輸出碼初始化為0

HufData(i).code=[];

%%排序列表初始化

SortList(i).symbol=i;

SortList(i).value=HufData(i).value;

end

%初始化原始消息數(shù)目

newsymbol=OriginSize;

forn=OriginSize:-1:2

%將N個(gè)消息進(jìn)行排序

SortList=sortdata(SortList,n);

%將最后兩個(gè)出現(xiàn)概率最小的消息合成一個(gè)消息

newsymbol=newsymbol+1;

HufData(newsymbol).value=SortList(n-1).value+SortList(n).value;

HufData(newsymbol).left=SortList(n-1).symbol;

HufData(newsymbol).right=SortList(n).symbol;

%將消息添加到列隊(duì)的最后，為N-1個(gè)消息重新排序作好準(zhǔn)備

SortList(n-1).symbol=newsymbol;

SortList(n-1).value=HufData(newsymbol).value;

end

%遍歷霍夫曼樹(shù)，獲得霍夫曼編碼/霍夫曼編碼

visit(newsymbol,Len,[]);

end%子程序：冒泡排序法函數(shù)sortdata.m

functionreData=sortdata(SortList,n)

%根據(jù)消息概率進(jìn)行排序

fork=n:-1:2

forj=1:k-1

min=SortList(j).value;

sbl=SortList(j).symbol;

if(min<SortList(j+1).value)

SortList(j).value=SortList(j+1).value;

SortList(j+1).value=min;

SortList(j).symbol=SortList(j+1).symbol;

SortList(j+1).symbol=sbl;

end

end

end

reData=SortList;

end%子程序：遍歷霍夫曼編碼/霍夫曼編碼樹(shù)搜索函數(shù)visit.m

functionvisit(node,n,ocode)

globalHufData

ifnode<=n

%如果沒(méi)有霍夫曼編碼/霍夫曼編碼樹(shù)的子接點(diǎn)直接輸出原始碼，這里為空碼（[]）HufData(node).code=ocode;

else

if(HufData(node).left>0)

%遍歷左分支接點(diǎn)輸出1，這里采用子函數(shù)嵌套調(diào)用

ocode1=[ocode1];

visit(HufData(node).left,n,ocode1);

end

if(HufData(node).right>0)