哈夫曼編碼在圖像壓縮中的應(yīng)用與分析

呂姣霖，徐 艷

（四川大學(xué)錦城學(xué)院計(jì)算機(jī)與軟件學(xué)院，四川 成都 611731）

0 引言

在各個(gè)行業(yè)之間進(jìn)行信息傳輸時(shí)，由于數(shù)據(jù)、圖像的傳輸需要占據(jù)較大的信道容量，因此在數(shù)據(jù)、圖像傳輸?shù)倪^程中，會(huì)由于信道容量的大量被占用，導(dǎo)致網(wǎng)絡(luò)卡頓。為了解決這一問題，研究出了文件壓縮、圖像壓縮等方式，在對(duì)數(shù)據(jù)和圖像進(jìn)行傳輸之前，首先對(duì)其進(jìn)行壓縮，使其傳輸過程中只需要占用比較小的內(nèi)存，在接收信息后，再對(duì)文件和圖像等進(jìn)行解壓。本文所研究的重點(diǎn)是常用的圖像壓縮技術(shù)-哈夫曼編碼，通過C++語言對(duì)編碼算法進(jìn)行實(shí)現(xiàn)，從而對(duì)圖像壓縮的相關(guān)技術(shù)進(jìn)行研究，通過哈夫曼編碼實(shí)現(xiàn)對(duì)圖像的壓縮和對(duì)比分析。

1 哈夫曼編碼簡(jiǎn)介

哈夫曼編碼出現(xiàn)于19世紀(jì)60年代，是國(guó)際有效的二進(jìn)制編碼之一，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，被認(rèn)為是接近于壓縮比上限的最佳編碼方法之一[1]。哈夫曼編碼是常用的編碼方式，亦稱為最佳編碼、熵編碼，適用于無損耗的數(shù)據(jù)壓縮[2]。在使用哈夫曼編碼實(shí)現(xiàn)對(duì)圖像的壓縮過程中，首先實(shí)現(xiàn)的是對(duì)圖像中所分解出來的數(shù)據(jù)進(jìn)行掃描，計(jì)算出圖像上各個(gè)像素所出現(xiàn)的概率，并根據(jù)各個(gè)數(shù)據(jù)出現(xiàn)概率的不同，指定哈夫曼編碼中的惟一碼字與各個(gè)不同概率的像素一一對(duì)應(yīng)，并將所有碼字組成哈夫曼碼表，在圖像加壓的過程中，可以通過壓縮時(shí)所組成的哈夫曼碼表的對(duì)應(yīng)關(guān)系，實(shí)現(xiàn)源圖像數(shù)據(jù)的還原。

2 哈夫曼編碼實(shí)現(xiàn)圖像壓縮

2.1 哈夫曼編碼實(shí)現(xiàn)圖像壓縮算法

本文以C++為基礎(chǔ)語言，結(jié)合哈夫曼編碼的思想，使編碼符號(hào)與被壓縮的圖像數(shù)據(jù)一一對(duì)應(yīng)，利用二叉樹的構(gòu)造方法，不斷置新新的根節(jié)點(diǎn)，使得最終的數(shù)據(jù)編碼由兩個(gè)子節(jié)點(diǎn)和一個(gè)根節(jié)點(diǎn)構(gòu)成，算法如下：

（1）定義哈夫曼樹節(jié)點(diǎn)

哈夫曼樹主要由一個(gè)根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)，一共三個(gè)節(jié)點(diǎn)構(gòu)成，因此本次哈夫曼樹類型的構(gòu)建一共定義4個(gè)整型成員，分別表示樹根節(jié)點(diǎn)、左節(jié)點(diǎn)、右節(jié)點(diǎn)和數(shù)量。

（2）構(gòu)建哈夫曼樹

按照哈夫曼樹的構(gòu)建步驟，按照出現(xiàn)概率的大小順序?qū)ψ址M(jìn)行排序，將字符出現(xiàn)次數(shù)最少的兩個(gè)節(jié)點(diǎn)構(gòu)成哈夫曼樹新的節(jié)點(diǎn)，使用循環(huán)，不斷抽取排序中出現(xiàn)數(shù)量最少的節(jié)點(diǎn)，不斷合并組成新節(jié)點(diǎn)，直到最后只剩下兩組節(jié)點(diǎn)，構(gòu)成最后的二叉樹[3]。

（3）定義有關(guān)圖片壓縮的功能函數(shù)

結(jié)合哈夫曼樹思想實(shí)現(xiàn)圖片的壓縮功能，通過對(duì)本次系統(tǒng)需要實(shí)現(xiàn)的功能進(jìn)行分析，定義的函數(shù)需要實(shí)現(xiàn)創(chuàng)建哈夫曼樹、遞歸、哈夫曼編碼轉(zhuǎn)換、計(jì)算字節(jié)長(zhǎng)度、解析字符串、讀取文件、讀取圖片、復(fù)制圖片信息、寫入圖片等功能。

（4）主函數(shù)中調(diào)用定義的方法

在主函數(shù)中，首先輸入圖片的路徑，讀取出圖片的信息，再將讀取到的圖片的信息進(jìn)行哈夫曼編碼轉(zhuǎn)換，調(diào)用函數(shù)對(duì)轉(zhuǎn)換后的編碼進(jìn)行排序，調(diào)用構(gòu)建哈夫曼樹函數(shù)，構(gòu)建出與本次圖片壓縮相關(guān)的哈夫曼樹[4]。最后調(diào)用解析函數(shù)，對(duì)數(shù)據(jù)進(jìn)行解析，并將解析后的數(shù)據(jù)以壓縮圖的形式輸出。

2.2 哈夫曼編碼實(shí)現(xiàn)圖像壓縮關(guān)鍵代碼

在哈夫曼樹構(gòu)建時(shí)，對(duì)已經(jīng)排序的編碼出現(xiàn)的數(shù)量進(jìn)行比較，篩選出出現(xiàn)次數(shù)最少的字符，在排序長(zhǎng)度之內(nèi)對(duì)字符編碼出現(xiàn)的次數(shù)進(jìn)行比較，若當(dāng)前比較的編碼出現(xiàn)的次數(shù)小于當(dāng)前編碼出現(xiàn)的次數(shù)，將該編碼賦值給當(dāng)前標(biāo)記編碼。

在對(duì)哈夫曼編碼進(jìn)行處理時(shí)，主要調(diào)用遞歸函數(shù)中的方法，獲取到圖像數(shù)據(jù)所對(duì)應(yīng)的編碼表，并對(duì)哈夫曼樹左右子節(jié)點(diǎn)相對(duì)應(yīng)的編碼進(jìn)行遞歸，關(guān)鍵代碼如下：

進(jìn)行哈夫曼編碼轉(zhuǎn)換的流程為：先對(duì)讀取圖片所獲得的數(shù)組進(jìn)行初始化，再通過for 循環(huán)對(duì)哈夫曼樹所需要的編碼進(jìn)行遍歷，獲取到圖片對(duì)應(yīng)的所有哈夫曼編碼，對(duì)哈夫曼樹左右兩個(gè)子節(jié)點(diǎn)依次進(jìn)行轉(zhuǎn)換。

對(duì)創(chuàng)建哈夫曼樹所需要的編碼進(jìn)行轉(zhuǎn)換后，創(chuàng)建哈夫曼樹，調(diào)用函數(shù)獲取哈夫曼樹編碼表，對(duì)編碼進(jìn)行遍歷，并將遍歷得出的編碼存儲(chǔ)于編碼表文件，關(guān)鍵代碼如下：

在使圖片數(shù)據(jù)與哈夫曼編碼一一對(duì)應(yīng)，創(chuàng)建好哈夫曼樹后，打開文件，對(duì)哈夫曼編碼表進(jìn)行讀取，解析哈夫曼編碼中的文件內(nèi)容。

解析哈夫曼編碼中的文件內(nèi)容后，讀取圖像壓縮后的文件，并存儲(chǔ)讀取壓縮文件后的信息，將圖片壓縮后的信息輸出，關(guān)鍵代碼如下：

2.3 圖片壓縮前后對(duì)比分析

在完成哈夫曼編碼實(shí)現(xiàn)對(duì)圖片壓縮功能的程序部分后，用于測(cè)試的圖像為如圖1所示黑底背景的綠色水壺。

圖1 測(cè)試圖

圖1所示測(cè)試圖通過本次所設(shè)計(jì)的基于哈夫曼編碼的圖像壓縮系統(tǒng)進(jìn)行壓縮后，得到壓縮圖。對(duì)測(cè)試圖原圖和壓縮圖進(jìn)行比較后發(fā)現(xiàn)，壓縮圖與原圖文件大小基本一致，且壓縮圖與原圖相比，壓縮圖的外觀形狀、大小等特性與原圖相同，可視清晰度也與原圖相同。

3 結(jié)束語

本文以C++為系統(tǒng)開發(fā)的基礎(chǔ)語言，以哈夫曼編碼構(gòu)成哈夫曼樹，以及哈夫曼樹逆向解碼過程為本次圖像壓縮系統(tǒng)設(shè)計(jì)的思想，設(shè)計(jì)并完成了基于哈夫曼編碼對(duì)圖片壓縮的功能。本文選用測(cè)試圖對(duì)其核心的圖片壓縮功能進(jìn)行了測(cè)試，測(cè)試圖通過本次所設(shè)計(jì)系統(tǒng)壓縮功能的壓縮后，所得到的壓縮圖與原圖文件大小基本一致，且視覺效果一致。通過對(duì)測(cè)試圖原圖與壓縮圖進(jìn)行比較，確定本次所設(shè)計(jì)的圖像壓縮功能，具有無損壓縮特性，在壓縮的過程中，并不會(huì)存在數(shù)據(jù)的損壞與丟失。因此通過哈夫曼編碼與哈夫曼原理所設(shè)計(jì)出的圖像壓縮系統(tǒng)，也是對(duì)需要壓縮的圖像的數(shù)據(jù)進(jìn)行采集，并將采集后的數(shù)據(jù)通過哈夫曼編碼進(jìn)行一一轉(zhuǎn)化，使編碼符號(hào)與數(shù)字字符產(chǎn)生一一對(duì)應(yīng)的關(guān)系，而不會(huì)因丟失圖片的數(shù)據(jù)，導(dǎo)致圖片的變形或受損[5]。