哈夫曼編碼在圖像壓縮中的應用與分析

呂姣霖，徐 艷

（四川大學錦城學院計算機與軟件學院，四川 成都 611731）

0 引言

在各個行業之間進行信息傳輸時，由于數據、圖像的傳輸需要占據較大的信道容量，因此在數據、圖像傳輸的過程中，會由于信道容量的大量被占用，導致網絡卡頓。為了解決這一問題，研究出了文件壓縮、圖像壓縮等方式，在對數據和圖像進行傳輸之前，首先對其進行壓縮，使其傳輸過程中只需要占用比較小的內存，在接收信息后，再對文件和圖像等進行解壓。本文所研究的重點是常用的圖像壓縮技術-哈夫曼編碼，通過C++語言對編碼算法進行實現，從而對圖像壓縮的相關技術進行研究，通過哈夫曼編碼實現對圖像的壓縮和對比分析。

1 哈夫曼編碼簡介

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

2 哈夫曼編碼實現圖像壓縮

2.1 哈夫曼編碼實現圖像壓縮算法

本文以C++為基礎語言，結合哈夫曼編碼的思想，使編碼符號與被壓縮的圖像數據一一對應，利用二叉樹的構造方法，不斷置新新的根節點，使得最終的數據編碼由兩個子節點和一個根節點構成，算法如下：

（1）定義哈夫曼樹節點

哈夫曼樹主要由一個根節點和兩個子節點，一共三個節點構成，因此本次哈夫曼樹類型的構建一共定義4個整型成員，分別表示樹根節點、左節點、右節點和數量。

（2）構建哈夫曼樹

按照哈夫曼樹的構建步驟，按照出現概率的大小順序對字符進行排序，將字符出現次數最少的兩個節點構成哈夫曼樹新的節點，使用循環，不斷抽取排序中出現數量最少的節點，不斷合并組成新節點，直到最后只剩下兩組節點，構成最后的二叉樹[3]。

（3）定義有關圖片壓縮的功能函數

結合哈夫曼樹思想實現圖片的壓縮功能，通過對本次系統需要實現的功能進行分析，定義的函數需要實現創建哈夫曼樹、遞歸、哈夫曼編碼轉換、計算字節長度、解析字符串、讀取文件、讀取圖片、復制圖片信息、寫入圖片等功能。

（4）主函數中調用定義的方法

在主函數中，首先輸入圖片的路徑，讀取出圖片的信息，再將讀取到的圖片的信息進行哈夫曼編碼轉換，調用函數對轉換后的編碼進行排序，調用構建哈夫曼樹函數，構建出與本次圖片壓縮相關的哈夫曼樹[4]。最后調用解析函數，對數據進行解析，并將解析后的數據以壓縮圖的形式輸出。

2.2 哈夫曼編碼實現圖像壓縮關鍵代碼

在哈夫曼樹構建時，對已經排序的編碼出現的數量進行比較，篩選出出現次數最少的字符，在排序長度之內對字符編碼出現的次數進行比較，若當前比較的編碼出現的次數小于當前編碼出現的次數，將該編碼賦值給當前標記編碼。

在對哈夫曼編碼進行處理時，主要調用遞歸函數中的方法，獲取到圖像數據所對應的編碼表，并對哈夫曼樹左右子節點相對應的編碼進行遞歸，關鍵代碼如下：

進行哈夫曼編碼轉換的流程為：先對讀取圖片所獲得的數組進行初始化，再通過for 循環對哈夫曼樹所需要的編碼進行遍歷，獲取到圖片對應的所有哈夫曼編碼，對哈夫曼樹左右兩個子節點依次進行轉換。

對創建哈夫曼樹所需要的編碼進行轉換后，創建哈夫曼樹，調用函數獲取哈夫曼樹編碼表，對編碼進行遍歷，并將遍歷得出的編碼存儲于編碼表文件，關鍵代碼如下：

在使圖片數據與哈夫曼編碼一一對應，創建好哈夫曼樹后，打開文件，對哈夫曼編碼表進行讀取，解析哈夫曼編碼中的文件內容。

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

2.3 圖片壓縮前后對比分析

在完成哈夫曼編碼實現對圖片壓縮功能的程序部分后，用于測試的圖像為如圖1所示黑底背景的綠色水壺。

圖1 測試圖

圖1所示測試圖通過本次所設計的基于哈夫曼編碼的圖像壓縮系統進行壓縮后，得到壓縮圖。對測試圖原圖和壓縮圖進行比較后發現，壓縮圖與原圖文件大小基本一致，且壓縮圖與原圖相比，壓縮圖的外觀形狀、大小等特性與原圖相同，可視清晰度也與原圖相同。

3 結束語

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