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

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

2、必要的冗余數(shù)據(jù)以減少所需傳輸?shù)臄?shù)據(jù)量是必然的選擇。而我正是對(duì)如何編碼使圖像壓縮而不至于影響人的體驗(yàn)產(chǎn)生興趣的。上課時(shí)我了解到圖像數(shù)據(jù)存在3種冗余：結(jié)構(gòu)冗余、統(tǒng)計(jì)冗余、以及心里視覺冗余。通過上網(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）將信源符號(hào)xi按其出現(xiàn)的概率，由大

3、到小順序排列。（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）畫出由每個(gè)信源符號(hào)到概率1.0處的路徑，記下沿路徑的1和0；（5）對(duì)于每個(gè)信源符號(hào)都寫出1、0序列，則從右到左就得到非等長(zhǎng)的Huffman碼。Huffman編碼的特點(diǎn)是：（1）Huffman編碼構(gòu)造程序是明確的，但編出的碼不是唯一的，其原因之一是兩個(gè)概率分配碼字“0”和“1”是任意選擇的（大概率為“0”，小概率為“1”，或者反之）。第二原因

4、是在排序過程中兩個(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編碼只能用近似的整數(shù)位來(lái)表示單個(gè)符號(hào)，而不是理想的小數(shù)，這也是Huffman編碼無(wú)法達(dá)到最理想的壓縮效果的原

5、因假設(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，

6、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è)值，作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。重復(fù)(2)，直到最后得到和為1的根節(jié)點(diǎn)。將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面

7、的葉子節(jié)點(diǎn)途中遇到的0，1序列串起來(lái)，就得到了各個(gè)符號(hào)的編碼。上面的例子用Huffman編碼的過程如圖下圖所示，其中圓圈中的數(shù)字是新節(jié)點(diǎn)產(chǎn)生的順序。Huffman編碼的二叉樹示意圖信源的各個(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%，可見霍夫曼編碼效率很高。產(chǎn)生Huffman編碼需要對(duì)原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中，每個(gè)值出現(xiàn)的頻率，第二遍是建立Huffman樹并進(jìn)行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數(shù)據(jù)壓縮和還原速度都較慢，但簡(jiǎn)單有效，因

8、而得到廣泛的應(yīng)用。三、霍夫曼編碼應(yīng)用本文霍夫曼編碼壓縮圖像的步驟如下：讀入圖像，并把它用矩陣表示。統(tǒng)計(jì)圖像顏色的種數(shù)。統(tǒng)計(jì)各種顏色值出現(xiàn)的概率，并把它們按從大到小的順序排列。進(jìn)行霍夫曼編碼的計(jì)算： 定義一個(gè)矩陣M，M矩陣的第一行，存放的是需要編碼的各個(gè)顏色值出現(xiàn)的概率，并且按照從大到小排列順序，然后再將第一行從后往前兩兩相加（即概率最小的兩個(gè)數(shù)相加），把相加得到的結(jié)果放到第二行，然后再將第二行重新進(jìn)行排序，依此類推，一直到最后一行，這時(shí)最后一行只有兩個(gè)概率，并且相加肯定為1 。 對(duì)M矩陣的數(shù)值進(jìn)行霍夫曼編碼：首先建立N矩陣，用來(lái)存放編碼的碼字。然后將字符0，賦給最后一行的第一小段，再將字符1，

9、賦給最后一行的第二小段，在M矩陣中，由于每一行的最后兩個(gè)數(shù)，都是這一行中概率最小的兩個(gè)數(shù)，所以將倒數(shù)第二行的最后兩個(gè)數(shù)進(jìn)行相加，然后用相加的結(jié)果到倒數(shù)第一行中去尋找，肯定會(huì)在倒數(shù)第一行中找到一樣的值，然后記錄下來(lái)在倒數(shù)第一行中這個(gè)值的位置，再將這個(gè)在M矩陣中的位置對(duì)應(yīng)到N矩陣中， 將N矩陣中的該位置的字符賦給倒數(shù)第二行的第二小段和第三小段，最后在給第二小段的后面賦字符0，給第三小段后面賦字符1，然后將在最后一行找到的那個(gè)數(shù)的左邊的數(shù)，一一對(duì)應(yīng)到上一行去，右邊的數(shù)，向左串一位，再對(duì)應(yīng)到上一行去，這樣依此類推，那么在N矩陣的第一行，可以得到最后的編碼。實(shí)驗(yàn)程序見附錄實(shí)驗(yàn)結(jié)果如下：壓縮效果對(duì)比：圖像

10、大小比較： 從圖中我們可以明顯的對(duì)比出來(lái)，經(jīng)過了霍夫曼編碼壓縮圖片后，在畫質(zhì)上看不出明顯的區(qū)別，但是實(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:61 count=0; for i=1:M for j=1:N if f(i,j)=

11、t-1 count=count+1; end end end p(t)=count;p0=p;endcore=cell(61,1);sign=zeros(61);for hh=1:60 re=M*N; for t=1:61 if (p(t)0) re=p(t); end end t=1; while (p(t)=re)&(t61) t=t+1; end if sign(t,1)=0 coret=0; else coret=0,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=0,coresign(t,i); i=i+1; end end p

12、(t)=0; cou=t; re1=M*N; for t=1:61 if (p(t)0) re1=p(t); end end t=1; while (p(t)=re1)&(t61) t=t+1; end if sign(t,1)=0 coret=1; else coret=1,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=1,coresign(t,i); i=i+1; end end p(t)=p(t)+re; cou1=t; i=1; while (sign(t,i)=0)&(i61) i=i+1; end sign(t,i)=cou

13、; i=i+1; j=1; while (sign(cou,j)=0)&(j61) sign(t,i)=sign(cou,j); i=i+1; j=j+1; endend %產(chǎn)生huffman碼fc=cell(M,N);for i=1:M for j=1:N if f(i,j)len-1; i=1; j=j+1; else i=i+1; end break; end endendf=uint8(f*4+35);subplot(1,2,2)imshow(f);title(解碼后的壓縮圖像);imwrite(f,壓縮圖像.jpg);imfinfo(壓縮圖像.jpg)toc五.總結(jié)學(xué)習(xí)完本門課程之后，是我的知識(shí)面有