基于Huffman編碼的圖像壓縮解壓研究

摘要：根據(jù)BMP圖像的特點(diǎn)，提出了基于Huffman編碼的壓縮方法，分別采用RGB統(tǒng)一編碼和RGB分別編碼兩種方式對(duì)圖像進(jìn)行壓縮和解壓程序設(shè)計(jì)，然后對(duì)多幅圖像進(jìn)行了壓縮和解壓實(shí)驗(yàn)，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了相關(guān)的分析。

關(guān)鍵詞：Huffman編碼；BMP圖像壓縮；BMP圖像解壓

中圖分類(lèi)號(hào)：TP3931文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)04-0887-03

Huffman-based Coding of Image Compression Decompression

RAO Xing

(Computer Science， Wuhan University of Technology， Wuhan 430070， China)

Abstract: According to the BMP image， we proposed a compression method based on Huffman coding， codes were used to RGB and RGB uniform code in two ways， respectively， the image compression and decompression program design， and then multiple images of the compression and decompression experiments Finally， experimental results related to the analysis.

Key words: Huffman coding; BMP image compression; BMP image decompression

圖像壓縮是指以較少的比特有損或無(wú)損地表示原來(lái)的像素矩陣的技術(shù)，也稱(chēng)圖像編碼。圖像數(shù)據(jù)之所以能被壓縮，就是因?yàn)閿?shù)據(jù)中存在著冗余。圖像數(shù)據(jù)的冗余主要表現(xiàn)為空間冗余、時(shí)間冗余、信息熵冗余、結(jié)構(gòu)冗余、知識(shí)冗余、視覺(jué)冗余等。由于圖像數(shù)據(jù)量的龐大，在存儲(chǔ)、傳輸、處理時(shí)非常困難，因此圖像數(shù)據(jù)的壓縮就顯得非常重要。本文采用Huffman編碼對(duì)24位BMP圖像進(jìn)行壓縮和解壓設(shè)計(jì)，分別采用RGB統(tǒng)一編碼和RGB分別編碼兩種方式對(duì)圖像進(jìn)行壓縮和解壓設(shè)計(jì)，然后對(duì)多幅圖像進(jìn)行了壓縮實(shí)驗(yàn)，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了相關(guān)的分析。

1 簡(jiǎn)介

目前主要的圖像壓縮方法分為：有損數(shù)據(jù)壓縮和無(wú)損數(shù)據(jù)壓縮。其中有損壓縮主要包括變換編碼和預(yù)測(cè)編碼；無(wú)損壓縮主要包括Huffman編碼、算數(shù)編碼、行程長(zhǎng)度編碼等。主要的圖像格式包括：BMP、GIF、JPEG、PNG、TIFF等。由于在一幅圖像中，規(guī)則物體和規(guī)則背景的表面物理特性具有相關(guān)性，這些相關(guān)性的光成像結(jié)構(gòu)在數(shù)字化圖像中就表現(xiàn)為數(shù)據(jù)冗余，正式基于此才使得圖像存在壓縮的空間。

1.1 Huffman編碼

信息熵編碼是根據(jù)信源符號(hào)出現(xiàn)概率的分布特性而進(jìn)行的壓縮編碼。Huffman編碼是信息熵編碼的一種。

Huffman編碼的原理為：在變長(zhǎng)編碼中，對(duì)出現(xiàn)概率大的信源符號(hào)賦予短碼字，而對(duì)于出現(xiàn)概率小的信源符號(hào)賦予長(zhǎng)碼字。如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率大小的逆序排序，則編碼結(jié)果平均碼字長(zhǎng)度一定小于任何其他排列方式。

對(duì)于Huffman編碼，第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中每個(gè)值出現(xiàn)的頻率進(jìn)；第二遍掃描是建立哈夫曼樹(shù)并進(jìn)行編碼。

1.2 BMP圖像

BMP是一種與硬件設(shè)備無(wú)關(guān)的圖像文件格式，使用非常廣。它采用位映射存儲(chǔ)格式，除了圖像深度可選以外，不采用其他任何壓縮，因此，BMP文件所占用的空間很大。BMP文件的圖像深度可選lbit、4bit、8bit及24bit。BMP文件存儲(chǔ)數(shù)據(jù)時(shí)，圖像的掃描方式是按從左到右、從下到上的順序。由于BMP圖像沒(méi)有進(jìn)行壓縮，故本文選用24位的BMP圖像進(jìn)行壓縮和解壓。

2 BMP圖像壓縮

2.1 Huffman編碼算法

1) 根據(jù)給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)成n棵二叉樹(shù)的集合F={T1，T2，…，Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均空。

2) 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。

3) 在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。

4) 重復(fù)2)和3)，直到F只含有一棵樹(shù)為止。

5) Huffman樹(shù)構(gòu)造完成后，約定左分支表示字符‘0’，右分支表示字符‘1’，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)字符的編碼。

2.2 BMP圖像壓縮算法

BMP圖像壓縮首先要讀入符合要求的BMP圖像，掃描圖像構(gòu)建Huffman樹(shù)，對(duì)構(gòu)造的Huffman樹(shù)進(jìn)行編碼，重新掃描該BMP圖像，對(duì)該圖像中的數(shù)據(jù)進(jìn)行壓縮。

2.3 壓縮文件格式

BMP文件由文件頭、位圖信息頭、顏色信息和圖形數(shù)據(jù)四部分組成。在24位BMP圖像格式中沒(méi)有顏色信息數(shù)據(jù)項(xiàng)，故由文件頭、位圖信息頭和圖形數(shù)據(jù)三部分組成。其中將文件頭和位圖信息頭統(tǒng)稱(chēng)為BMP圖像頭，共占54字節(jié)。為了使壓縮后的文件保持?jǐn)?shù)據(jù)的完整性，故在壓縮文件中要加入54字節(jié)BMP圖像頭信息。

為了標(biāo)識(shí)該文件為壓縮后的BMP圖像，因此需要一個(gè)表示信息，在BMP文件中的表示信息為頭兩個(gè)字節(jié)為‘BM’，為此在該壓縮文件中加入一個(gè)字符‘C’，同BMP圖像頭信息的頭兩個(gè)自己‘BM’一起構(gòu)成字符串‘CBM’，以此來(lái)標(biāo)識(shí)該文件為BMP圖像的壓縮文件。

在壓縮過(guò)程中定義了兩種壓縮方案，RGB分開(kāi)壓縮和RGB統(tǒng)一壓縮，故在此用一個(gè)字節(jié)來(lái)表示RGB是否分開(kāi)壓縮，1表示分開(kāi)壓縮，0表示不分開(kāi)壓縮。

為了使壓縮后的信息能夠還原，需要一些附加信息。附加信息包括Huffman樹(shù)結(jié)構(gòu)信元個(gè)數(shù)n、Huffman樹(shù)信息、壓縮數(shù)據(jù)區(qū)字節(jié)數(shù)ByteCount和數(shù)據(jù)區(qū)最后一個(gè)字節(jié)的位數(shù)BitCount組成，其中Huffman樹(shù)信息包括n個(gè)(信息元，權(quán)重)二元組，據(jù)此就可以重構(gòu)Huffman樹(shù)，生成編碼，進(jìn)而進(jìn)行解碼。

RGB分開(kāi)壓縮時(shí)壓縮文件格式：字符‘C’+BMP圖像頭信息(54個(gè)byte)+RGB是否分開(kāi)壓縮(bool)+R{Huffman樹(shù)結(jié)構(gòu)信息元個(gè)數(shù)n(unsigned int)+huffman樹(shù)信息(n個(gè)(信息元(byte)，權(quán)重(unsigned int)))+壓縮數(shù)據(jù)區(qū)字節(jié)數(shù)ByteCount(unsigned int)+數(shù)據(jù)區(qū)最后一個(gè)字節(jié)的位數(shù)BitCount (byte)+壓縮數(shù)據(jù)區(qū)(ByteCount個(gè)數(shù)據(jù)(byte))}+G{同R}+B{同R}。

RGB統(tǒng)一壓縮時(shí)壓縮文件格式：字符‘C’+BMP圖像頭信息(54個(gè)byte)+RGB是否分開(kāi)壓縮(bool)+RGB{Huffman樹(shù)結(jié)構(gòu)信息元個(gè)數(shù)n(unsigned int)+huffman樹(shù)信息(n個(gè)(信息元(byte)，權(quán)重(unsigned int)))+壓縮數(shù)據(jù)區(qū)字節(jié)數(shù)ByteCount(unsigned int)+數(shù)據(jù)區(qū)最后一個(gè)字節(jié)的位數(shù)BitCount (byte)+壓縮數(shù)據(jù)區(qū)(ByteCount個(gè)數(shù)據(jù)(byte))}。

由以上壓縮文件格式可以看出該文件結(jié)構(gòu)是一種緊湊的文件格式，符合壓縮的要求。對(duì)以上文件格式分析得出，文件頭占55個(gè)字節(jié)，附加信息所占字節(jié)數(shù)如式(1)、(2)所示。

RGB分開(kāi)編碼時(shí)：

30+5*Rn+5*Gn+5*Bn (1)

其中Rn、Gn、Bn分別為Huffman樹(shù)結(jié)構(gòu)信息元個(gè)數(shù)。

RGB統(tǒng)一編碼時(shí)：

10+5*n (2)

其中n為Huffman樹(shù)結(jié)構(gòu)信息元個(gè)數(shù)。

3 BMP圖像解壓

由以上壓縮文件可知在解壓時(shí)，首先需要根據(jù)信息構(gòu)造Huffman樹(shù)，根據(jù)構(gòu)造的Huffman樹(shù)進(jìn)行解碼，從根結(jié)點(diǎn)出發(fā)直至找到葉子結(jié)點(diǎn)就可以求得該子串對(duì)應(yīng)的字符。在圖像解壓的過(guò)程中，由于需要重新構(gòu)造Huffman樹(shù)，所以必須保證所構(gòu)造的Huffman樹(shù)和編碼時(shí)所構(gòu)造的Huffman樹(shù)結(jié)構(gòu)一樣，否則無(wú)法獲得正確的解碼。要想使得所構(gòu)造的Huffman樹(shù)結(jié)構(gòu)一樣關(guān)鍵在于排序算法，只要在編碼和解碼時(shí)使用的排序算法是穩(wěn)定的，就能夠保證所構(gòu)造的Huffman樹(shù)和編碼時(shí)構(gòu)造的一樣。

4 實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)過(guò)程中選擇了三幅圖像分別進(jìn)行壓縮和解壓實(shí)驗(yàn)，通過(guò)壓縮得到壓縮文件，然后對(duì)壓縮文件進(jìn)行解壓能夠得到原圖像。在實(shí)驗(yàn)過(guò)程中所獲得的數(shù)據(jù)可以看出，無(wú)論是RGB分開(kāi)壓縮，還是RGB統(tǒng)一壓縮，其信息熵都比壓縮后的平均編碼長(zhǎng)度都要短一點(diǎn)，說(shuō)明都還有壓縮的空間。對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行壓縮比分析得到數(shù)據(jù)如表1所示。

由表1數(shù)據(jù)可以看出，Huffman編碼的壓縮比并不高，這主要由信息熵來(lái)決定，由第二幅圖片可以看出該圖片中存在大量的同色區(qū)域，信息熵都沒(méi)有超過(guò)三，因此其壓縮比最高，RGB分開(kāi)時(shí)到達(dá)3.067，RGB統(tǒng)一時(shí)達(dá)到2.698，由以上數(shù)據(jù)可以看出信息熵越小，其壓縮比越高；并且從表中可以看出RGB分開(kāi)編碼時(shí)的數(shù)據(jù)壓縮比比RGB統(tǒng)一編碼時(shí)要高，說(shuō)明同一色具有很大的相關(guān)性；一般情況下RGB分開(kāi)編碼時(shí)的文件壓縮比要比RGB統(tǒng)一編碼時(shí)要高，但由于在壓縮文件中存在附加信息，導(dǎo)致了Caustics.bmp該圖像的RGB分開(kāi)編碼的文件壓縮比比RGB統(tǒng)一編碼時(shí)的壓縮比高；從表中還可以看出數(shù)據(jù)的壓縮比要比文件的壓縮比高，這是由于在文件中存在附加數(shù)據(jù)。

5 結(jié)論

從以上實(shí)驗(yàn)數(shù)據(jù)分析中可以得到，圖像數(shù)據(jù)的信息熵小，其壓縮比越高；由RGB分開(kāi)壓縮時(shí)其數(shù)據(jù)壓縮比比RGB統(tǒng)一壓縮時(shí)要高，可以看出在同一幅圖像中同一色具有很大的相關(guān)性，由于在壓縮文件中存在附加信息導(dǎo)致文件壓縮比存在一些例外情況，但一般情況下圖像的RGB分開(kāi)編碼的文件壓縮比比RGB統(tǒng)一編碼時(shí)的壓縮比高；因此在對(duì)圖像進(jìn)行壓縮時(shí)要充分利用同一色分量的相關(guān)性來(lái)壓縮數(shù)據(jù)，這樣可以得到更高的壓縮比，但也要認(rèn)識(shí)到對(duì)不同分量分別處理會(huì)增加附加數(shù)據(jù)量，如果解壓算法需要的附加數(shù)據(jù)很多，由于對(duì)不同分量分別處理會(huì)帶來(lái)更多的附加數(shù)據(jù)，則文件壓縮比不一定會(huì)提高。

參考文獻(xiàn)：

[1] 田端財(cái)，殷曉麗.基于哈夫曼編碼的圖像壓縮技術(shù)研究[J].科技資訊，2009(8):29-30.

[2] 黃偉，龔沛曾.圖像壓縮中的幾種編碼方法[J].計(jì)算機(jī)應(yīng)用研究，2003(8):67-70.

[3] 吳俊政.一種基于奇異值分解的圖像壓縮方法[J].計(jì)算機(jī)與數(shù)字工程，2009(5):136-138.

[4] 謝春光.一種基于小波變換新型的圖像壓縮算法[J].圖像處理，2009(3-3):303-305.

[5] 邱敏華，徐林，邵謙明.基于小波分析的醫(yī)學(xué)超聲圖像壓縮及分組霍夫曼算法[J].復(fù)旦學(xué)報(bào):自然科學(xué)版，2004(1):62-67.