圖像的無損壓縮程序設計 霍夫曼編碼

1、沈陽理工大學數(shù)字圖像處理課程設計成績評定表學生姓名班級學號1203030119專業(yè)電子信息工程課程設計題目圖像的無損壓縮程序設計霍夫曼編碼評語組長簽字：成績日期2015年7月20日課程設計任務書學院信息科學與工程專業(yè)電子信息工程學生姓名班級學號1203030119課程設計題目圖像的無損壓縮程序設計霍夫曼編碼實踐教學要求與任務：本課題通過matlab編寫適當?shù)暮瘮?shù)，對一個隨機信源進行哈夫曼編碼，得出碼字，平均碼長和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過程與特點，并且提高綜合運用所學理論知識獨立分析和解決問題的能力。工作計劃與進度安排：2015年7月8日11日：熟悉編

2、程環(huán)境，查閱相關資料。2015年7月11日12日：圖像的霍夫曼編碼程序設計。2015年7月12日13日：編碼、調試、實驗與分析。2015年7月13日15日：撰寫課程設計報告。2015年7月15日19日：準備答辯。指導教師：2015年7月2日專業(yè)負責人：2015年7月2日學院教學副院長：2015年7月2日摘 要哈夫曼編碼(huffman coding)是一種編碼方式，以哈夫曼樹即最優(yōu)二叉樹，帶權路徑長度最小的二叉樹，經(jīng)常應用于數(shù)據(jù)壓縮。在計算機信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"），用于數(shù)據(jù)的無損耗壓縮。這一術語是指使用一張?zhí)厥獾木幋a表將源字符（例如

3、某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。本課題通過matlab編寫適當?shù)暮瘮?shù)，對一個隨機信源進行哈夫曼編碼，得出碼字，平均碼長和編碼效率。從而理解信源編碼的基本思想與目的以及哈夫曼編碼方法的基本過程與特點，并且提高綜合運用所學理論知識獨立分析和解決問題的能力。關鍵字：哈夫曼；信源編碼；matlab目 錄1設計目的及相關知識11.1設計目的11.2圖像的霍夫曼編碼概念11.3matlab圖像處理通

4、用函數(shù)12課程設計分析32.1 圖像的霍夫曼編碼概述32.2 圖像的霍夫曼編碼舉例43仿真64結果及分析95附錄12結束語15參考文獻161設計目的及相關知識1.1設計目的1）了解霍夫曼編碼的原理。2）理解圖像的霍夫曼編碼原理，了解其應用，掌握圖像的霍夫曼編碼的方法。3）對圖像編碼程序設計進行較深入的認識，對知識牢固掌握。4）掌握圖像霍夫曼編碼的整個過程及其中的注意事項。5）了解圖像無損壓縮的目的及好處。1.2圖像的霍夫曼編碼概念所謂霍夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊，把兩個最小的概率相加，作為新的概率和剩余的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最后變成1。每次相加

5、時都將“0”和“1”賦與相加的兩個概率，讀出時由該符號開始一直走到最后的“1”，將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的霍夫曼編碼1.3 matlab圖像處理通用函數(shù)colorbar  顯示彩色條語法：colorbar colorbar('vert') colorbar('horiz') colorbar(h) h=colorbar(.) colorbar(.,'peer',axes_handle)getimage從坐標軸取得圖像數(shù)據(jù)語法：a=getimage(h) x,y,a=getimage(h) .,

6、a,flag=getimage(h) .=getimageimshow顯示圖像語法：imshow(i,n) imshow(i,low high) imshow(bw) imshow(x,map) imshow(rgb) imshow(.,display_option) imshow(x,y,a,.) imshow filename h=imshow(.)montage 在矩形框中同時顯示多幅圖像語法：montage(i) montage(bw) montage(x,map) montage(rgb) h=montage(.)immovie創(chuàng)建多幀索引圖的電影動畫語法：mov=immovie(x

7、,map) mov=immovie(rgb)subimage在一副圖中顯示多個圖像語法：subimage(x,map) subimage(i) subimage(bw)   subimage(rgb) subimage(x,y,.) subimage(.)truesize調整圖像顯示尺寸語法：truesize(fig,mrowsmcols) truesize(fig)warp 將圖像顯示到紋理映射表面語法：warp(x,map) warp(i ,n) warp(z,.) warp(x,y,z,.)   h=warp(.)zoom 縮放圖像語法：zoom on zoom of

8、f zoom out zoom reset zoom zoom xon zoom yon zoom(factor) zoom(fig,option)2課程設計分析2.1 圖像的霍夫曼編碼概述赫夫曼（huffman）編碼是1952年提出的，是一種比較經(jīng)典的信息無損熵編碼，該編碼依據(jù)變長最佳編碼定理，應用huffman算法而產生。huffman編碼是一種基于統(tǒng)計的無損編碼。根據(jù)變長最佳編碼定理，huffman編碼步驟如下：（1）將信源符號xi按其出現(xiàn)的概率，由大到小順序排列。（2）將兩個最小的概率的信源符號進行組合相加，并重復這一步驟，始終將較大的概率分支放在上部，直到只剩下一個信源符號且概率達到

9、1.0為止；（3）對每對組合的上邊一個指定為1，下邊一個指定為0（或相反：對上邊一個指定為0，下邊一個指定為1）；（4）畫出由每個信源符號到概率1.0處的路徑，記下沿路徑的1和0；（5）對于每個信源符號都寫出1、0序列，則從右到左就得到非等長的huffman碼。huffman編碼的特點是：（1）huffman編碼構造程序是明確的，但編出的碼不是唯一的，其原因之一是兩個概率分配碼字“0”和“1”是任意選擇的（大概率為“0”，小概率為“1”，或者反之）。第二原因是在排序過程中兩個概率相等，誰前誰后也是隨機的。這樣編出的碼字就不是唯一的。（2）huffman編碼結果，碼字不等長，平均碼字最短，效率最

10、高，但碼字長短不一，實時硬件實現(xiàn)很復雜（特別是譯碼），而且在抗誤碼能力方面也比較差。（3）huffman編碼的信源概率是2的負冪時，效率達100%，但是對等概率分布的信源，產生定長碼，效率最低，因此編碼效率與信源符號概率分布相關，故huffman編碼依賴于信源統(tǒng)計特性，編碼前必須有信源這方面的先驗知識，這往往限制了霍夫曼編碼的應用。（4）huffman編碼只能用近似的整數(shù)位來表示單個符號，而不是理想的小數(shù)，這也是huffman編碼無法達到最理想的壓縮效果的原因。2.2 圖像的霍夫曼編碼舉例假設一個文件中出現(xiàn)了8種符號s0，s1，s2，s3，s4，s5，s6，s7，那么每種符號要編碼，至少需要3

11、比特。假設編碼成000，001，010，011，100，101，110，111那么符號序列s0s1s7s0s1s6s2s2s3s4s5s0s0s1編碼后變成000001111000001110010010011100101000000001，共用了42比特。我們發(fā)現(xiàn)s0，s1，s2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得s0，s1，s2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。例如，我們采用這樣的編碼方案：s0到s7的碼字分別01，11，101，0000，0001，0010，0011，100，那么上述符號序列變成0111100011100

12、11101101000000010010010111，共用了39比特，盡管有些碼字如s3，s4，s5，s6變長了(由3位變成4位)，但使用頻繁的幾個碼字如s0，s1變短了，所以實現(xiàn)了壓縮?？捎上旅娴牟襟E得到霍夫曼碼的碼表(1) 首先把信源中的消息出現(xiàn)的頻率從小到大排列。(2) 每一次選出頻率最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。(3) 重復(2)，直到最后得到和為1的根節(jié)點。(4) 將形成的二叉樹的左節(jié)點標0，右節(jié)點標1。把從最上面的根節(jié)點到最下面的葉子節(jié)點途中遇到的0，1序列串起來，就得到了各個符號的編碼。上面的例子用h

13、uffman編碼的過程如圖下圖所示，其中圓圈中的數(shù)字是新節(jié)點產生的順序。圖2-1    huffman編碼的二叉樹示意圖信源的各個消息從s0到s7的出現(xiàn)概率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。計算編碼效率為98.5%，編碼的冗余只有1.5%，可見霍夫曼編碼效率很高。產生huffman編碼需要對原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計出原始數(shù)據(jù)中，每個值出現(xiàn)的頻率，第二遍是建立huffman樹并進行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡單有效，因而得到廣泛的應用。3仿真主程序

14、：%以下為主程序mainp.mclcclearclose all;%定義hufdata/len為全局變量的結構體global hufdata;global lendisp('計算機正在準備輸出霍夫曼編碼結果,請耐心等待');%原始碼字的灰度a=imread('kids.tif');%分區(qū)畫出原始圖像和灰度直方圖figure;subplot(1,2,1)imshow(a);%取消坐標軸和邊框axis offbox offtitle('matlab自帶圖像','fontsize',13);subplot(1,2,2);axis off

15、box offimhist(a);title('圖像灰度直方圖','fontsize',13);%圖像的灰度統(tǒng)計graystatistics=imhist(a);graystatistics=graystatistics'grayratioo=graystatistics/sum(graystatistics);grayrationo=find(grayratioo=0);len=length(grayrationo);%初始化灰度集，防止系統(tǒng)隨即賦予其垃圾值grayratio=ones(1,len);for i=1:lengrayratio(i)=gr

16、ayratioo(i); endgrayratio=abs(sort(-grayratio);%將圖像灰度概率賦予結構體for i=1:lenhufdata(i).value=grayratio(i);end% 霍夫曼編碼/霍夫曼編碼huffmancode(len);%輸出碼字zippedhuffman=1;for i=1:lentmpdata=hufdata(i).code;str=''for j=1:length(tmpdata)str=strcat(str,num2str(tmpdata(j);zippedhuffman=zippedhuffman+1;enddisp(s

17、trcat('a',num2str(i),'= ',str)endi;%計算計算機一共輸出多少個霍夫曼編碼/霍夫曼編碼zippedhuffman;%計算在刪去0灰度級壓縮之前的原始圖像字節(jié)容量unzipped_delete=i*8;%計算壓縮比率ratio_delete=zippedhuffman/unzipped_delete;%計算圖像的壓縮比率ad=num2str(ratio_delete*100);str2=strcat(ad,'%');disp(strcat('霍夫曼編碼壓縮比率','= ',str2)4

18、結果及分析結果:圖4-1 輸出原圖像與該圖像像灰度直方圖計算機正在準備輸出霍夫曼編碼結果,請耐心等待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=01011

19、1a28=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

20、=0100100a57=0011101a58=0011100a59=0001001a60=0001000a61=10110101a62=101101001a63=101101000霍夫曼編碼壓縮比率=78.9683%分析：從輸出灰度直方圖可得出該圖像的量化值主要集中在低灰度級處，通過輸出可以看到該灰度級對應的霍夫曼編碼，并且輸出了該圖像的壓縮效率。明顯可得出霍夫曼編碼大大的節(jié)省了空間，可以明顯的減少發(fā)送時間。5附錄子程序：%子程序：霍夫曼編碼/霍夫曼編碼函數(shù)huffmancode.mfunction huffmancode(originsize)global hufdata;global le

21、nfor i=1:len%霍夫曼編碼樹左邊紀錄為1hufdata(i).left=1;%霍夫曼編碼樹右邊紀錄為0hufdata(i).right=0;%輸出碼初始化為0hufdata(i).code=;%排序列表初始化sortlist(i).symbol=i;sortlist(i).value=hufdata(i).value;end%初始化原始消息數(shù)目newsymbol=originsize;for n=originsize:-1:2%將n個消息進行排序sortlist=sortdata(sortlist,n);%將最后兩個出現(xiàn)概率最小的消息合成一個消息newsymbol=newsymbol

22、+1;hufdata(newsymbol).value=sortlist(n-1).value+sortlist(n).value;hufdata(newsymbol).left=sortlist(n-1).symbol;hufdata(newsymbol).right=sortlist(n).symbol;%將消息添加到列隊的最后，為n-1個消息重新排序作好準備sortlist(n-1).symbol=newsymbol;sortlist(n-1).value=hufdata(newsymbol).value;end%遍歷霍夫曼樹，獲得霍夫曼編碼/霍夫曼編碼visit(newsymbol,l

23、en,);end%子程序：冒泡排序法函數(shù)sortdata.mfunction redata=sortdata(sortlist,n)%根據(jù)消息概率進行排序for k=n:-1:2for j=1:k-1min=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=sb

24、l;endendendredata=sortlist;end%子程序：遍歷霍夫曼編碼/霍夫曼編碼樹搜索函數(shù)visit.mfunction visit(node,n,ocode)global hufdataif node<=n%如果沒有霍夫曼編碼/霍夫曼編碼樹的子接點直接輸出原始碼，這里為空碼（）hufdata(node).code=ocode;elseif(hufdata(node).left>0)%遍歷左分支接點輸出1，這里采用子函數(shù)嵌套調用ocode1=ocode 1;visit(hufdata(node).left,n,ocode1);endif(hufdata(node).right