幾種常用圖像壓縮編碼方法的研究及C#實現

作者簡介：張燕紅（1981—），女，山東棲霞人，講師，碩士，研究方向：數字圖像處理，數據庫（E-mail：zhangyanhong1126@163.com）；王燕（1974—），女，山東煙臺人，小學高級教師，研究方向：軟件測試。

摘要：圖像壓縮是數字圖像處理的一項重要技術。本文研究基于統計特性的三種熵編碼圖像壓縮編碼方法—香農編碼、香農-弗諾編碼和哈夫曼編碼。并以C#為工具，對三種編碼方法進行實驗及對比，并通過實驗結果分析各算法的特點。實驗表明，哈夫曼編碼最節省存儲空間，單位碼長表達的信息量最為豐富；香農-弗諾編碼所占的存儲空間稍大于哈夫曼編碼，單位碼長表達的信息量比哈夫曼編碼稍少一些；而香農編碼所占存儲空間最大，單位碼長表達的信息量最少。

關鍵詞：圖像壓縮；香農編碼；香農-弗諾編碼；哈夫曼編碼

中圖分類號：TP391.41文獻標識碼：A

1引言

隨著科學的發展，人們對圖像存儲和通信的需求越來越大。為了提高傳輸速度，節省存儲空間，使圖像存儲、傳輸更為高效，最根本的途徑就是采用圖像壓縮技術[1]。目前，圖像壓縮編碼技術已發展到第二代。1985年，Kunt等人提出了第二代編碼技術。他們認為，第一代編碼技術只是以信息論和數字信號處理技術為理論基礎，旨在去除圖像元素中的線性相關性的一類編碼技術，壓縮比不高。而第二代編碼技術充分利用人的視覺、心理和圖像信息源的各種特征，實現從波形編碼到模型編碼的轉變，獲得了更高的壓縮比[2]。二十世紀八十年代以來，隨著小波變換理論、分形理論、人工神經網絡等理論的建立，人們開始突破傳統的信源編碼理論，圖像編碼進入了一個嶄新的時期。在繼續研究灰度圖像壓縮技術的同時，越來越關注它們在彩色圖像壓縮編碼技術中的推廣使用，圖像壓縮技術的應用前景也越來越廣闊。當前，電子產品的數字化已是大勢所趨，所有的數字產品均涉及到圖像壓縮技術，包括高清數字電視、可視電話、手機等。

當前，圖像壓縮方法按采用的技術不同主要分為預測編碼、變換編碼、統計編碼、靜態圖像編碼、電視編碼等[3]。本文主要研究基于統計特性的三種熵編碼圖像壓縮編碼方法—香農編碼、香農-弗諾編碼和哈夫曼編碼，并以C#為工具，對三種編碼方法進行實驗及對比，通過實驗結果分析總結各種方法的特點。

2三種常用的圖像壓縮編碼方法簡介

圖像熵表示圖像灰度級集合的平均比特數，單位為比特/像素，描述了圖像信源的平均信息量。熵編碼算法有多種，如香農編碼、香農-弗諾編碼、哈夫曼編碼、算術編碼、行程編碼和LZW編碼等[3]。本文只研究三種思想相近的基于統計特性的香農編碼、香農-弗諾編碼和哈夫曼編碼。

2.1香農編碼

香農編碼是一種長度不均勻的編碼方法。它的基本思想是：對于出現概率大的信息，采用短字長的碼，而對于出現概率小的信息用長字長的碼，以達到縮短平均碼長，從而實現數據壓縮的目的[4]。

香農編碼的具體步驟如下：

1）將圖像灰度級按出現的概率由大到小順序排列。

2）按下式計算出各概率對應的碼字長度其中Pi為灰度級為i的出現概率。

3）計算各概率對應的累加概率ai，即：

4）把各個累加概率由十進制轉換成二進制。

5）將二進制表示的累加概率去掉多于2）步中計算的ti的尾數，即獲得各個灰度級的碼字。

2.2香農-弗諾編碼

香農-弗諾編碼也屬于熵編碼方法的一種。

香農-弗諾編碼過程如下：

1）計算出每個灰度級出現的概率，并且按照從小到大的順序排列。

2）從序列中某個位置將序列分成兩個子序列，并盡量使這兩個序列概率和近似相等，給前面一個子序列賦值為1，后面一個子序列賦值0。

3）重復步驟2），直到各個子序列不能再分為止。

4）分配碼字，將每個像素所屬子序列的值串起來，這樣就得到了各個像素香農-弗諾編碼。

2.3哈夫曼編碼

哈夫曼編碼嚴格按照概率匹配方法決定碼長，概率大的灰度值對應于短碼，概率小的灰度值對應于長碼。

哈夫曼編碼步驟如下：

1）統計出圖像中每個灰度值出現的概率，并按照從大到小的順序排列。

2）每一次選出概率最小的兩個值，將它們相加，形成的新頻率值和其他頻率值形成一個新的頻率集合。

3）重復第2）步，直到最后得到頻率和為1。

4）分配碼字，對上述步驟反過來逐步向前進行編碼，每一步有兩個分支各賦予一個二進制碼，對概率大的賦予碼元0，對概率小的賦予碼元1（或相反）。

3實驗與結果分析

為方便實驗，首先以C#為工具，制作三種編碼方法的軟件生成界面，以圖1為例，分別對三種編碼方法進行編碼實驗，并計算其圖像熵值、編碼后的平均碼長和編碼效率，最后對三種編碼方法進行分析和比較。

3.1香農編碼實驗

根據香農編碼算法，應用C#生成的軟件，以圖1為例進行香農編碼實驗，計算圖像的熵值、平均碼長、編碼效率。得到實驗結果如圖2所示。

由圖2可以看出，香農編碼雖然達到了壓縮的目的，但平均碼長較長，編碼效率只有85.8319%，并不是很高，壓縮效果較差。對該編碼方法、編碼過程及實驗結果進行分析，可以得出以下結論：

1）由于編碼總是進一取整，香農編碼方法不一定是最佳的；

2）由于概率最大的灰度值的累加概率總是為0，故它對應的碼字總是0、00、000、0…0的式樣；

3）碼字集合是唯一的；

4）由于每個灰度值的碼長只與自身出現概率大小有關，與其余灰度值出現概率大小無關，所以碼字長度是確定的，短碼沒有得到充分利用，在圖像灰度級較大的情況下，大部分碼字有較長的碼長，降低了編碼的效率，只有當（1）式中前面的等號成立時才有很高的編碼效率，而這種情況是很少的，因此一般情況下香農編碼效率較低。

5）對于大部分圖像，編碼效率不高，冗余度大，因此其實用性受到很大限制。

3.2香農-弗諾編碼實驗

根據香農-弗諾編碼算法，應用C#生成的軟件，以圖1為例進行香農-弗諾編碼實驗，計算圖像的熵值、平均碼長、編碼效率。得到實驗結果如圖3所示。

由圖3實驗結果可知，香農-弗諾編碼也達到了壓縮的目的，平均碼長為6.385，較香農編碼的7.159減少較多，編碼效率為96.2441%，比香農編碼有了很大提高，編碼效率比較高。對該編碼方法、編碼過程及實驗結果進行分析，可以得出以下結論：

1）香農編碼實際上構造了一個碼樹，碼樹從樹根開始到終端節點結束。

2）由于賦碼元時的任意性，因此香農-弗諾編碼編出的碼字不唯一。

3）香農-弗諾編碼雖屬于概率匹配范疇，但并未嚴格遵守匹配規則，即不全是按“概率大碼長小、概率小碼長大”來決定碼長，有時會出現概率小碼長反而小的情況，因此平均碼長一般不會最小。

4）香農-弗諾編碼有較高的編碼效率，比較適合于每次分組概率都很接近的圖像。特別是對每次分組的概率集合概率都相當的圖像進行編碼時，可達到理想的編碼效率。

3.3哈夫曼編碼實驗

根據哈夫曼編碼算法，應用C#生成的軟件，以圖1為例進行哈夫曼編碼實驗，計算圖像的熵值、平均碼長、編碼效率。得到實驗結果如圖4所示。

由圖4實驗結果可知，與前兩種編碼相比，哈夫曼編碼的平均碼長為6.167，最接近圖像熵值，編碼效率為99.6436%，編碼效率高于香農編碼和香農-弗諾編碼，編碼效率高，編碼效果好。通過研究該編碼原理、編碼方法、編碼過程及實驗結果，分析總結哈夫曼編碼的特點如下：

1）哈夫曼編碼實際上構造了一個碼樹，與香農-弗諾編碼相反，碼樹從最上層的端點開始構造，直到樹根結束，最后得到一個橫放的碼樹，因此，編出的碼是即時碼。

2）哈夫曼編碼采用概率匹配方法來決定各碼字的碼長，概率大的灰度值對應于短碼，概率小的灰度值對應于長碼，從而使平均碼長最小。

3）每次對概率最小的兩個灰度值求概率之和形成縮減信源時，就構造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的，因此編出的碼字并不惟一。

4）對不同圖像的編碼效率不同，當圖像各灰度值概率為2的負冪次方時，達到100%的編碼效率；若圖像各灰度值的概率相等，則編碼效率最低。

5）有效的信源編碼可取得較好的冗余壓縮效果。

6）有效的信源編碼可使輸出碼元概率均勻化。

3.4三種編碼方法的比較

為了得到更為準確的實驗結論，下面以上述實驗所用的方法，對20幅不同大小的圖像進行實驗并記錄實驗結果，得到以下數據表1。

從表1可以看出，對20幅圖像，哈夫曼編碼的平均碼長都是最小，香農-弗諾編碼稍大于哈夫曼編碼，香農編碼最大。香農-弗諾編碼和哈夫曼編碼的編碼效率遠高于香農編碼，哈夫曼編碼又略高于香農-弗諾編碼。因此，可以得出，哈夫曼編碼具有最小的平均碼長，最高的編碼效率；香農-弗諾編碼的平均碼長略大于哈夫曼編碼，編碼效率略低于哈夫曼編碼；而香農編碼平均碼長最長，編碼效率最低。

4結束語

本文研究并實現了基于統計特性的三種熵編碼圖像壓縮編碼方法—香農編碼、香農-弗諾編碼和哈夫曼編碼。實驗表明：哈夫曼編碼最節省存儲空間，單位碼長表達的信息量最為豐富；香農-弗諾編碼所占的存儲空間稍大于哈夫曼編碼，單位碼長表達的信息量比哈夫曼編碼稍少一些；而香農編碼所占存儲空間最大，單位碼長表達的信息量最少。應根據具體圖像和各方法的特點選擇合適的壓縮編碼方法。

參考文獻

[1]劉剛.MATLAB數字圖像處理[M].北京：機械工業出版社，2010： 180-182.

[2]王向陽，楊紅穎. 基于人眼視覺特性的快速圖像編碼算法[J].軟件學報：2003，20（11）：37-38.

[3]James S Duncan .Nicholas AyacheMedical Image Analysis：Progress over Two Decades and the Challenges Ahead[J ]. IEEE Trans on Pattern Analysis and Machine Intelligence：2010 ， 22（1）： 85-86.

[4]張忠厚. LDPC編碼的MIMOOFDM系統設計與優化[J].世界科技研究與發展： 2012，34 （6）： 931-934.

[5]吳永輝， 俞建新. JPEG2000圖像壓縮算法概述及網絡應用前景[J]. 計算機工程： 2003， 29 （3）：7-10.

[6]章毓晉.圖像分割[M].北京：北京科學出版社， 2009：201- 202.

[7]Zimmer C，Zhang B， Dufour A. On the digital trail of mobile Cells[J ].IEEE Signal Proc： 2011， 23（3）：54 -62.

[8]田迎華，楊敬松，陶躍. 基于邊緣檢測的噪聲圖像壓縮編碼方法[J].計算機應用：2008， 28 （9）：157～158.

[9]邵軍花，劉玉紅，邸敬，等. 香農編碼的優化算法研究[J].蘭州交通大學學報： 2010， 15 （6）：58-59.

[10]王向陽，楊紅穎.一種新的低比特率圖像壓縮編碼算法[J].計算機研究與發展：2011， 20（7）： 129-131.

[11]王小科，李繼業. C#開發寶典[M].北京：機械工業出版社，2012： 380～382.