幾種常用圖像壓縮編碼方法的研究及C#實(shí)現(xiàn)

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

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

關(guān)鍵詞：圖像壓縮；香農(nóng)編碼；香農(nóng)-弗諾編碼；哈夫曼編碼

中圖分類號：TP391.41文獻(xiàn)標(biāo)識碼：A

1引言

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

當(dāng)前，圖像壓縮方法按采用的技術(shù)不同主要分為預(yù)測編碼、變換編碼、統(tǒng)計編碼、靜態(tài)圖像編碼、電視編碼等[3]。本文主要研究基于統(tǒng)計特性的三種熵編碼圖像壓縮編碼方法—香農(nóng)編碼、香農(nóng)-弗諾編碼和哈夫曼編碼，并以C#為工具，對三種編碼方法進(jìn)行實(shí)驗(yàn)及對比，通過實(shí)驗(yàn)結(jié)果分析總結(jié)各種方法的特點(diǎn)。

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

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

2.1香農(nóng)編碼

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

香農(nóng)編碼的具體步驟如下：

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

2）按下式計算出各概率對應(yīng)的碼字長度其中Pi為灰度級為i的出現(xiàn)概率。

3）計算各概率對應(yīng)的累加概率ai，即：

4）把各個累加概率由十進(jìn)制轉(zhuǎn)換成二進(jìn)制。

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

2.2香農(nóng)-弗諾編碼

香農(nóng)-弗諾編碼也屬于熵編碼方法的一種。

香農(nóng)-弗諾編碼過程如下：

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

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

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

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

2.3哈夫曼編碼

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

哈夫曼編碼步驟如下：

1）統(tǒng)計出圖像中每個灰度值出現(xiàn)的概率，并按照從大到小的順序排列。

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

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

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

3實(shí)驗(yàn)與結(jié)果分析

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

3.1香農(nóng)編碼實(shí)驗(yàn)

根據(jù)香農(nóng)編碼算法，應(yīng)用C#生成的軟件，以圖1為例進(jìn)行香農(nóng)編碼實(shí)驗(yàn)，計算圖像的熵值、平均碼長、編碼效率。得到實(shí)驗(yàn)結(jié)果如圖2所示。

由圖2可以看出，香農(nóng)編碼雖然達(dá)到了壓縮的目的，但平均碼長較長，編碼效率只有85.8319%，并不是很高，壓縮效果較差。對該編碼方法、編碼過程及實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以得出以下結(jié)論：

1）由于編碼總是進(jìn)一取整，香農(nóng)編碼方法不一定是最佳的；

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

3）碼字集合是唯一的；

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

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

3.2香農(nóng)-弗諾編碼實(shí)驗(yàn)

根據(jù)香農(nóng)-弗諾編碼算法，應(yīng)用C#生成的軟件，以圖1為例進(jìn)行香農(nóng)-弗諾編碼實(shí)驗(yàn)，計算圖像的熵值、平均碼長、編碼效率。得到實(shí)驗(yàn)結(jié)果如圖3所示。

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

1）香農(nóng)編碼實(shí)際上構(gòu)造了一個碼樹，碼樹從樹根開始到終端節(jié)點(diǎn)結(jié)束。

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

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

4）香農(nóng)-弗諾編碼有較高的編碼效率，比較適合于每次分組概率都很接近的圖像。特別是對每次分組的概率集合概率都相當(dāng)?shù)膱D像進(jìn)行編碼時，可達(dá)到理想的編碼效率。

3.3哈夫曼編碼實(shí)驗(yàn)

根據(jù)哈夫曼編碼算法，應(yīng)用C#生成的軟件，以圖1為例進(jìn)行哈夫曼編碼實(shí)驗(yàn)，計算圖像的熵值、平均碼長、編碼效率。得到實(shí)驗(yàn)結(jié)果如圖4所示。

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

1）哈夫曼編碼實(shí)際上構(gòu)造了一個碼樹，與香農(nóng)-弗諾編碼相反，碼樹從最上層的端點(diǎn)開始構(gòu)造，直到樹根結(jié)束，最后得到一個橫放的碼樹，因此，編出的碼是即時碼。

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

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

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

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

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

3.4三種編碼方法的比較

為了得到更為準(zhǔn)確的實(shí)驗(yàn)結(jié)論，下面以上述實(shí)驗(yàn)所用的方法，對20幅不同大小的圖像進(jìn)行實(shí)驗(yàn)并記錄實(shí)驗(yàn)結(jié)果，得到以下數(shù)據(jù)表1。

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

4結(jié)束語

本文研究并實(shí)現(xiàn)了基于統(tǒng)計特性的三種熵編碼圖像壓縮編碼方法—香農(nóng)編碼、香農(nóng)-弗諾編碼和哈夫曼編碼。實(shí)驗(yàn)表明：哈夫曼編碼最節(jié)省存儲空間，單位碼長表達(dá)的信息量最為豐富；香農(nóng)-弗諾編碼所占的存儲空間稍大于哈夫曼編碼，單位碼長表達(dá)的信息量比哈夫曼編碼稍少一些；而香農(nóng)編碼所占存儲空間最大，單位碼長表達(dá)的信息量最少。應(yīng)根據(jù)具體圖像和各方法的特點(diǎn)選擇合適的壓縮編碼方法。

參考文獻(xiàn)

[1]劉剛.MATLAB數(shù)字圖像處理[M].北京：機(jī)械工業(yè)出版社，2010： 180-182.

[2]王向陽，楊紅穎. 基于人眼視覺特性的快速圖像編碼算法[J].軟件學(xué)報：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系統(tǒng)設(shè)計與優(yōu)化[J].世界科技研究與發(fā)展： 2012，34 （6）： 931-934.

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

[6]章毓晉.圖像分割[M].北京：北京科學(xué)出版社， 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].計算機(jī)應(yīng)用：2008， 28 （9）：157～158.

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

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

[11]王小科，李繼業(yè). C#開發(fā)寶典[M].北京：機(jī)械工業(yè)出版社，2012： 380～382.