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

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

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

中圖分類(lèi)號(hào)：TP391.41文獻(xiàn)標(biāo)識(shí)碼：A

1引言

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

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

2三種常用的圖像壓縮編碼方法簡(jiǎn)介

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

2.1香農(nóng)編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3哈夫曼編碼

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

哈夫曼編碼步驟如下：

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

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

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

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

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

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

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

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

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

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

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

3）碼字集合是唯一的；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4三種編碼方法的比較

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

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

[5]吳永輝， 俞建新. JPEG2000圖像壓縮算法概述及網(wǎng)絡(luò)應(yīng)用前景[J]. 計(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]田迎華，楊敬松，陶躍. 基于邊緣檢測(cè)的噪聲圖像壓縮編碼方法[J].計(jì)算機(jī)應(yīng)用：2008， 28 （9）：157～158.

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

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

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