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

2、必要的冗余數據以減少所需傳輸的數據量是必然的選擇。而我正是對如何編碼使圖像壓縮而不至于影響人的體驗產生興趣的。上課時我了解到圖像數據存在3種冗余：結構冗余、統計冗余、以及心里視覺冗余。通過上網搜尋資料我也了解到編碼也是分3種的：統計編碼、預測編碼，以及變換編碼。我主要深入學習了用統計編碼的方法來去除統計冗余。二、霍夫曼編碼概述赫夫曼（Huffman）編碼是1952年提出的，是一種比較經典的信息無損熵編碼，該編碼依據變長最佳編碼定理，應用Huffman算法而產生。Huffman編碼是一種基于統計的無損編碼。根據變長最佳編碼定理，Huffman編碼步驟如下：（1）將信源符號xi按其出現的概率，由大

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

4、是在排序過程中兩個概率相等，誰前誰后也是隨機的。這樣編出的碼字就不是唯一的。（2）Huffman編碼結果，碼字不等長，平均碼字最短，效率最高，但碼字長短不一，實時硬件實現很復雜（特別是譯碼），而且在抗誤碼能力方面也比較差。（3）Huffman編碼的信源概率是2的負冪時，效率達100%，但是對等概率分布的信源，產生定長碼，效率最低，因此編碼效率與信源符號概率分布相關，故Huffman編碼依賴于信源統計特性，編碼前必須有信源這方面的先驗知識，這往往限制了霍夫曼編碼的應用。（4）Huffman編碼只能用近似的整數位來表示單個符號，而不是理想的小數，這也是Huffman編碼無法達到最理想的壓縮效果的原

5、因假設一個文件中出現了8種符號S0，S1，S2，S3，S4，S5，S6，S7，那么每種符號要編碼，至少需要3比特。假設編碼成000，001，010，011，100，101，110，111那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成000001111000001110010010011100101000000001，共用了42比特。我們發現S0，S1，S2這三個符號出現的頻率比較大，其它符號出現的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數。例如，我們采用這樣的編碼方案：S0到S7的碼字分別01，

6、11，101，0000，0001，0010，0011，100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39比特，盡管有些碼字如S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現了壓縮。可由下面的步驟得到霍夫曼碼的碼表首先把信源中的消息出現的頻率從小到大排列。每一次選出頻率最小的兩個值，作為二叉樹的兩個葉子節點，將和作為它們的根節點，這兩個葉子節點不再參與比較，新的根節點參與比較。重復(2)，直到最后得到和為1的根節點。將形成的二叉樹的左節點標0，右節點標1。把從最上面的根節點到最下面

7、的葉子節點途中遇到的0，1序列串起來，就得到了各個符號的編碼。上面的例子用Huffman編碼的過程如圖下圖所示，其中圓圈中的數字是新節點產生的順序。Huffman編碼的二叉樹示意圖信源的各個消息從S0到S7的出現概率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。計算編碼效率為98.5%，編碼的冗余只有1.5%，可見霍夫曼編碼效率很高。產生Huffman編碼需要對原始數據掃描兩遍。第一遍掃描要精確地統計出原始數據中，每個值出現的頻率，第二遍是建立Huffman樹并進行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼，因此數據壓縮和還原速度都較慢，但簡單有效，因

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

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

10、大小比較： 從圖中我們可以明顯的對比出來，經過了霍夫曼編碼壓縮圖片后，在畫質上看不出明顯的區別，但是實際上壓縮后的圖片大小是原來的五分之一，占用空間是原來的三分之一。四、附錄%霍夫曼編碼實現圖像壓縮代碼：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 %產生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五.總結學習完本門課程之后，是我的知識面有