數(shù)字圖像處理(探索霍夫曼編碼)

1、探索霍夫曼編碼一、緒論在學(xué)習(xí)完了本學(xué)期的數(shù)字圖像處理課程后，我對圖像壓縮這部分內(nèi)容產(chǎn)生了興趣，通過深入學(xué)習(xí)，我用matlab 實現(xiàn)了霍夫曼編碼，成功地壓縮了圖像。隨著信息時代的來臨，多媒體已經(jīng)被人們廣泛的應(yīng)用于生活的各個領(lǐng)域。我們每天接受的信息開始以Gb 計，眾所周知Gb 是一個很大的單位，多媒體是指文字、聲音、圖形和圖像等各種媒體，它能比單純文字傳輸更多、更生動的信息，與此同時它的數(shù)據(jù)量也比文字要大得多，例如一幅分辨率為1024X 768、顏色24位的圖像將占到2.3MB的存儲空間，1 秒鐘沒有任何壓縮的數(shù)字視頻圖像需要上百兆字節(jié)的存儲空間，這是目前的存儲空間和傳輸寬帶不能承受的。采用數(shù)據(jù)壓

2、縮技術(shù)去除不必要的冗余數(shù)據(jù)以減少所需傳輸?shù)臄?shù)據(jù)量是必然的選擇。 而我正是對如何編碼使圖像壓縮而不至于影響人的體驗產(chǎn)生興趣的。上課時我了解到圖像數(shù)據(jù)存在3 種冗余：結(jié)構(gòu)冗余、統(tǒng)計冗余、以及心里視覺冗余。通過上網(wǎng)搜尋資料我也了解到編碼也是分3 種的：統(tǒng)計編碼、預(yù)測編碼，以及變換編碼。我主要深入學(xué)習(xí)了用統(tǒng)計編碼的方法來去除統(tǒng)計冗余。:、霍夫曼編碼概述赫夫曼（Huffman）編碼是1952年提出的，是一種比較經(jīng)典的信息無損熵編碼，該編碼依據(jù)變長最佳編碼定理，應(yīng)用Huffman 算法而產(chǎn)生。Huffman 編碼是一種基于統(tǒng)計的無損編碼。根據(jù)變長最佳編碼定理，Huffman 編碼步驟如下：（ 1）將信源符

3、號xi 按其出現(xiàn)的概率，由大到小順序排列。（ 2）將兩個最小的概率的信源符號進(jìn)行組合相加，并重復(fù)這一步驟， 始終將較大的概率分支放在上部，直到只剩下一個信源符號且概率達(dá)到1.0為止；（ 3） 對每對組合的上邊一個指定為1， 下邊一個指定為0（或相反：對上邊一個指定為0，下邊一個指定為1） ；（ 4） 畫出由每個信源符號到概率1.0處的路徑，記下沿路徑的1和 0；（ 5） 對于每個信源符號都寫出1 、 0 序列， 則從右到左就得到非等長的 Huffman 碼。Huffman 編碼的特點是：（ 1） Huffman 編碼構(gòu)造程序是明確的，但編出的碼不是唯一的，其原因之一是兩個概率分配碼字“0”和“

4、1”是任意選擇的（大概率為“ 0”，小概率為“1 ”，或者反之） 。第二原因是在排序過程中兩個概率相等，誰前誰后也是隨機的。這樣編出的碼字就不是唯一的。（ 2） Huffman 編碼結(jié)果，碼字不等長，平均碼字最短，效率最高，但碼字長短不一，實時硬件實現(xiàn)很復(fù)雜（特別是譯碼），而且在抗誤碼能力方面也比較差。（ 3） Huffman 編碼的信源概率是2的負(fù)冪時，效率達(dá)100%，但是對等概率分布的信源，產(chǎn)生定長碼，效率最低，因此編碼效率與信源符號概率分布相關(guān)，故Huffman 編碼依賴于信源統(tǒng)計特性，編碼前必須有信源這方面的先驗知識，這往往限制了霍夫曼編碼的應(yīng)用。（ 4） Huffman 編碼只能用近

5、似的整數(shù)位來表示單個符號，而不是理想的小數(shù)，這也是Huffman 編碼無法達(dá)到最理想的壓縮效果的原因假設(shè)一個文件中出現(xiàn)了8 種符號S0， S1， S2， S3， S4， S5， S6，S7,那么每種符號要編碼，至少需要 3比特。假設(shè)編碼成000, 001, 010 ，011 ，100 ，101 ，110 ，111 那 么 符 號 序 列S0S1S7S0S1S6S2S2S3S4S5S0S0S1 編 碼 后 變 成 000001111000001110010010011100101000000001 ， 共用了 42 比特。我們發(fā)現(xiàn)S0, S1, S2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn) 的頻

6、率比較小，如果我們采用一種編碼方案使得S0, S1, S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。例如，我們采用這樣的編碼方案：S0至US7的碼字分別01,11,101,0000,0001, 0010 ，0011 ，100 ， 那 么 上 述 符 號 序 列 變 成011110001110011101101000000010010010111 ， 共用了 39 比特， 盡 管有些碼字如S3， S4， S5， S6 變長了（由 3 位變成 4 位 ），但使用頻繁的幾個碼字如S0， S1 變短了，所以實現(xiàn)了壓縮?？捎上旅娴牟襟E得到霍夫曼碼的碼表首先把信源中的消息出現(xiàn)的頻率從小到大排

7、列。每一次選出頻率最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將 和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參 與比較。重復(fù)(2),直到最后得到和為1的根節(jié)點。將形成的二叉樹的左節(jié)點標(biāo) 0,右節(jié)點標(biāo)1。把從最上面的根節(jié) 點到最下面的葉子節(jié)點途中遇到的 0, 1序列串起來，就得到了各個 符號的編碼。上面的例子用 Huffman編碼的過程如圖下圖所示，其中圓圈中 的數(shù)字是新節(jié)點產(chǎn)生的順序。OQDQ 0001 OD10 001110Q1011101Huffman編碼的二叉樹示意圖信源的各個消息從S0到S7的出現(xiàn)概率分別為4/14 ,3/14 ,2/14 , 1/14, 1/14, 1/1

8、4, 1/14, 1/14。計算編碼效率為 98.5% 編碼的冗 余只有1.5%可見霍夫曼編碼效率很高。產(chǎn)生Huffman編碼需要對原始數(shù)據(jù)掃描兩遍。第一遍掃描要精 確地統(tǒng)計出原始數(shù)據(jù)中，每個值出現(xiàn)的頻率，第二遍是建立Huffman樹并進(jìn)行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡單有效，因而得到廣泛的應(yīng)用。三、霍夫曼編碼應(yīng)用本文霍夫曼編碼壓縮圖像的步驟如下：讀入圖像，并把它用矩陣表示。統(tǒng)計圖像顏色的種數(shù)。統(tǒng)計各種顏色值出現(xiàn)的概率，并把它們按從大到小的順序排列。進(jìn)行霍夫曼編碼的計算：定義一個矩陣M ， M 矩陣的第一行，存放的是需要編碼的各個顏色值出現(xiàn)的概

9、率，并且按照從大到小排列順序，然后再將第一行從后往前兩兩相加（即概率最小的兩個數(shù)相加），把相加得到的結(jié)果放到第二行，然后再將第二行重新進(jìn)行排序，依此類推，一直到最后一行，這時最后一行只有兩個概率，并且相加肯定為 1 。對 M 矩陣的數(shù)值進(jìn)行霍夫曼編碼：首先建立N 矩陣，用來存放編碼的碼字。然后將字符0，賦給最后一行的第一小段，再將字符1 ，賦給最后一行的第二小段，在M 矩陣中，由于每一行的最后兩個數(shù)，都是這一行中概率最小的兩個數(shù)，所以將倒數(shù)第二行的最后兩個數(shù)進(jìn)行相加， 然后用相加的結(jié)果到倒數(shù)第一行中去尋找，肯定會在倒數(shù)第一行中找到一樣的值，然后記錄下來在倒數(shù)第一行中這個值的位置，再將這個在M矩

10、陣中的位置對應(yīng)到 N矩陣中，將N矩陣中的該位置的字符賦給倒數(shù)第二行的第二小段和第三小段，最后在給第二小段的后面賦字符 0,給第三小段后面賦字 符1,然后將在最后一行找到的那個數(shù)的左邊的數(shù)，一一對應(yīng)到上一 行去，右邊的數(shù)，向左串一位，再對應(yīng)到上一行去，這樣依此類推， 那么在N矩陣的第一行，可以得到最后的編碼。實驗程序見附錄實驗結(jié)果如下：壓縮效果對比：原始圖像耐打后的壓縮圖像圖像大小比較:端拉百史除amg如制在彳扼守金豆 皿-I-汪鈿I.反唱交沖?S中；=圖于TIF 9JK文坤（.Tift*傳堂里!.W西E IIF國片室件打開E局2345名圖壬足國0.I打開為曲目印恁11王副地）.1 位CMlwi

11、V疣敵惴PfcU監(jiān)漸告文件關(guān)位蚤；CAUmtE無SS格鏟南建文件先大小：26.1 Ki 值自 740 TJ占用空同：24.Q KB576用力Ui司生可2艮口 K節(jié)（78號聿字向向謝TB1;,22 1503白城時司.2017125223 . 22:liDJflSBTifiJ：K> 1 丁年1標(biāo)三.訂牌:MEX時 aiO17r1?S?2 3 2155:M坊司時用201712223.22il5SM訪同時同：2£>睛隼12P?22 R , 22:1幺篦辰*t：口口口舊時高田3檢布師 UM西零出），3從圖中我們可以明顯的對比出來，經(jīng)過了霍夫曼編碼壓縮圖片 后，在畫質(zhì)上看不出明顯的區(qū)

12、別，但是實際上壓縮后的圖片大小是原 來的五分之一，占用空間是原來的三分之一。四、附錄派夫曼編碼實現(xiàn)圖像壓縮代碼:tic;clearz=imread('原圖.jpg ');gray2=rgb2gray(z);f0=gray2;subplot(1,2,1),image(f0);imshow(uint8(f0);title('原始圖像');f=abs(f0/4)-10;M,N=size(f);p=zeros(1,61);for t=1:61count=0;for i=1:Mfor j=1:Nif f(i,j)=t-1 count=count+1;endendendp(

13、t)=count;p0=p;endcore=cell(61,1);sign=zeros(61);for hh=1:60re=M*N;for t=1:61if (p(t)<re)&(p(t)>0) re=p(t);endendt=1;while (p(t)=re)&(t<61)t=t+1;endif sign(t,1)=0coret='0'elsecoret='0',coret;i=1;while (sign(t,i)=0)&(i<61)coresign(t,i)='0',coresign(t,i);

14、 i=i+1;endendp(t)=0;cou=t;re1=M*N;for t=1:61if (p(t)<re1)&(p(t)>0) re1=p(t);endendt=1;while (p(t)=re1)&(t<61)t=t+1;endif sign(t,1)=0coret='1'elsecoret='1',coret;i=1;while (sign(t,i)=0)&(i<61)coresign(t,i)='1',coresign(t,i);i=i+1;endendp(t)=p(t)+re;cou1

15、=t;i=1;while (sign(t,i)=0)&(i<61)i=i+1;endsign(t,i)=cou;i=i+1;j=1;while (sign(cou,j)=0)&(j<61)sign(t,i)=sign(cou,j);i=i+1;j=j+1;endend%產(chǎn)生huffman 碼fc=cell(M,N);for i=1:Mfor j=1:Nif f(i,j)<61fci,j=coref(i,j)+1;elsefci,j='0'endendend %fcimcore=char();for i=1:Mfor j=1:Nimcore=im

16、core,fci,j;endend%Computing the image sizedisp(' 原始圖像');imwrite(f0,' 原圖 .tif');imfinfo(' 原圖.tif')save picture imcore core; % 保存圖片碼流和編碼對應(yīng)表tocclear all;load picture.mat %載入圖片碼流和編碼對應(yīng)表Nc=size(core);Nic=size(imcore);flag=0;i=1;j=1;n=1;cz=char();len = 101;f=zeros(len);for n=1:Nic(2)if flag=0cz=cz,imcore(n);elsecz=imcore(n);flag=0;endfor t=1:Nc(1)if strcmp(cz,coret)f(j,i)=t;flag=1;if i>len-1;i=1;j=j+1;elsei=i+1;endbreak;endendendf=uint8(f*4+35);subplot(1,2,2)imshow(f);title(' 解碼后的壓縮圖像');imwrite(f,' 壓縮圖像.jpg'