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

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

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

3、號(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”和“

4、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 編碼依賴于信源統(tǒng)計(jì)特性，編碼前必須有信源這方面的先驗(yàn)知識(shí)，這往往限制了霍夫曼編碼的應(yīng)用。（ 4） Huffman 編碼只能用近

5、似的整數(shù)位來(lái)表示單個(gè)符號(hào)，而不是理想的小數(shù)，這也是Huffman 編碼無(wú)法達(dá)到最理想的壓縮效果的原因假設(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) 的頻

6、率比較小，如果我們采用一種編碼方案使得S0, S1, S2的碼字短，其它符號(hào)的碼字長(zhǎng)，這樣就能夠減少占用的比特?cái)?shù)。例如，我們采用這樣的編碼方案：S0至US7的碼字分別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)了壓縮。可由下面的步驟得到霍夫曼碼的碼表首先把信源中的消息出現(xiàn)的頻率從小到大排

7、列。每一次選出頻率最小的兩個(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)生的順序。OQDQ 0001 OD10 001110Q1011101Huffman編碼的二叉樹(shù)示意圖信源的各個(gè)消息從S0到S7的出現(xiàn)概率分別為4/14 ,3/14 ,2/14 , 1/14, 1/14, 1/1

8、4, 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)用。三、霍夫曼編碼應(yīng)用本文霍夫曼編碼壓縮圖像的步驟如下：讀入圖像，并把它用矩陣表示。統(tǒng)計(jì)圖像顏色的種數(shù)。統(tǒng)計(jì)各種顏色值出現(xiàn)的概率，并把它們按從大到小的順序排列。進(jìn)行霍夫曼編碼的計(jì)算：定義一個(gè)矩陣M ， M 矩陣的第一行，存放的是需要編碼的各個(gè)顏色值出現(xiàn)的概

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

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

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

12、別，但是實(shí)際上壓縮后的圖片大小是原 來(lái)的五分之一，占用空間是原來(lái)的三分之一。四、附錄派夫曼編碼實(shí)現(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; % 保存圖片碼流和編碼對(duì)應(yīng)表tocclear all;load picture.mat %載入圖片碼流和編碼對(duì)應(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'