范氏哈夫曼編碼在圖像壓縮中的應用

宦暉

關鍵詞：圖像壓縮；哈夫曼編碼；范氏哈夫曼編碼

1引言

近年來，圖像壓縮技術快速發展，各種新技術得以應用。但哈夫曼編碼作為一種傳統的基礎算法[1-2]，一直在圖像壓縮技術中占有重要地位。

哈夫曼編碼基于數據的統計特性，可以實現無損的圖像壓縮與解壓縮。范氏哈夫曼編碼是對傳統哈夫曼編碼的優化改進，通過對編碼規則約定限制，能更加高效地對哈夫曼樹進行編碼，減少編解碼過程所消耗的計算資源與存儲空間。

對范氏哈夫曼編碼在圖像壓縮中的實際效果進行驗證分析，是本文研究的出發點。通過對多組24位BMP圖像文件以及不同格式的BMP圖像文件進行壓縮與解壓縮，并對最終的壓縮效率進行對比，以得出相關結論。

2哈夫曼編碼

哈夫曼編碼是基于數據源的統計特性建立哈夫曼樹，再進行編碼的算法。建立哈夫曼樹是一個循環迭代的過程，每一步驟中的工作過程相同，具體過程為：編碼器獲取所有符號（ Symbol）的統計頻率，并將所有符號放置在一個集合中：從集合中選取統計頻率最低的兩個符號作為節點，并創建一個新的內部節點且放回集合中，原來的兩個節點被新創建的節點代替，新創建節點的統計頻率為所選兩個節點的統計頻率之和：將所選的兩個節點與新創建節點構成一個最小二叉樹。如此不斷地循環迭代，直到集合中只剩下一個節點（根節點），此時哈夫曼樹構建完成。

哈夫曼編碼壓縮后的數據量等于哈夫曼樹帶權路徑長度（Weighted Path Length，WPL）。哈夫曼樹的帶權路徑長度指的是所有節點的帶權路徑長度之和。n個編碼長度為Li（i=1，2，…，n）的葉節點的哈夫曼樹的帶權路徑長度為：

哈夫曼樹是帶權路徑長度最小的二叉樹，是最優二叉樹。在哈夫曼編碼表的結構中，每一棵最小二叉樹的左右子節點位置是隨機的，如果將哈夫曼樹中的任意一個最小二叉樹的左右節點位置互換，只會導致某些字符的具體編碼改變，但整個哈夫曼樹的帶權路徑總長度并不會發生變化，也不會影響哈夫曼編碼的壓縮率。如果能約定規則，限制哈夫曼樹中的最小二叉樹左右節點位置的不確定性，則表明哈夫曼樹所需的數據量可以有效降低。另外，傳統的哈夫曼編碼是通過將出現頻率較高的符號以較短編碼，從而提高壓縮率。但該方法有兩大缺點：首先，每一個樹節點都要儲存其父節點與子節點等相關信息，符號集合包含很多不同概率的符號，其數量越多，對應存儲空間將會增加越多；其次，哈夫曼樹的跟蹤和維護需要消耗非常大的計算資源。由于這兩個原因，傳統哈夫曼編碼在儲存空間以及計算效率上都需要提升、優化。

3范氏哈夫曼編碼

范氏哈夫曼編碼（Canonical Huffman Code）是施瓦茲（SCHWARTZ E S）提出的[4]，對傳統哈夫曼編碼進行優化的算法，通過對符號和編碼的下列三個數字序列屬性進行編碼規則約定限制，從而可以更加高效地對哈夫曼樹進行編碼。

范氏哈夫曼編碼約束規則如下。

（1）具有相同哈夫曼編碼長度的符號編碼是連續二進制整數，對應原碼的值越小，則對應哈夫曼編碼也越小。

（2）編碼長度為i的第一個符號的編碼H（i）與長度為i-l的最后～個符號的編碼H（i-l）的關系滿足以下公式：

該約束公式的含義是，長度為i第一個符號的編碼，是將長度為i-l的最后一個符號的編碼進行左移一位并補零。

（3）哈夫曼編碼長度最小的第一個符號從0開始。第一個符號的編碼方式是依照符號的編碼長度分配相同長度的“0”值。

根據以上三個約束規則，可按順序為確定了長度的每個符號分配唯一可譯碼（unique decodable code）。如此，就把存儲整個哈夫曼樹編碼表的任務簡化為存儲每個符號編碼長度的任務。

范氏霍夫曼編碼要求相同長度編碼必須是連續的[5]：為盡可能減小儲存空間，編碼長度為i的第一個符號可以從編碼長度為i-1的最后一個符號所獲得。另外，最小編碼長度的第一個編碼必須從0開始。范氏哈夫曼編碼通過其約束規則，可以根據每個符號的長度，按照范氏哈夫曼編碼的規則重構出整個編碼表。

在圖像數據的壓縮過程中，應實現兩方面的最小化，即存儲編碼表和哈夫曼樹的存儲空間最小化：編解碼過程所消耗的計算資源的最小化。范式哈夫曼編碼技術能同時滿足這兩方面的需求，比傳統的哈夫曼編碼技術更加有效[6]。

4對位圖文件進行壓縮、解壓縮

在本文研究中，以范氏哈夫曼編碼取代傳統哈夫曼編碼，對BMP圖像文件進行壓縮與解壓縮，并觀察實際的壓縮效率。

BMP是位圖（Bit Map）的簡稱，是未實行壓縮處理的原始圖像，存儲格式是位映射。在Windows操作系統自帶的畫圖軟件中可按單色、16色、256色、24位四種格式保存BMP圖像。BMP圖像主要有三個特點：一是格式簡單：二是圖像信息量豐富：三是存儲時所占用的內存較大。BMP圖像由四部分組成，如表1所列。

傳統哈夫曼編碼必須保存哈夫曼樹，本文研究中采用靜態數組實現哈夫曼樹的構建，哈夫曼樹節點包括權值、父節點、左右子節點，數據結構如下所示：

與傳統哈夫曼編碼相比，范式哈夫曼編碼節省了保存哈夫曼樹本身所需的數據量。

本文研究中的圖像壓縮解壓縮程序采用C++語言編寫，在CPU為Intel Core i5-102IOU，RAM為16CB的個人計算機上運行。

該程序的流程圖如圖1所示。

以24位位圖為樣本，對多組24位位圖進行測試，并選取三組不同壓縮效果的測試結果進行對比，如表2所列。

對于不同內容的圖像，壓縮率會根據內容而變化，這與圖像數據的統計特性有關[7]。統計上冗余信息較多的圖像，壓縮率較高。

在本文研究中，針對同一幅圖像，轉換為四種BMP格式，分別為單色位圖、16色位圖、256色位圖、24位位圖，然后進行壓縮與解壓測試，相應的測試數據如表3所列。

對同一幅圖像的不同位圖格式的壓縮率進行對比，程序對單色位圖的壓縮效果最好，對16色位圖的壓縮效果也較為理想，對256色位圖也有較高的壓縮率，而對24位位圖的壓縮效果最差。

就壓縮耗時與解壓耗時而言，對于字節長度較小的文件，壓縮耗時比解壓耗時長；對于字節長度較大的文件，壓縮耗時比解壓耗時短。

5結束語

本文研究使用范式哈夫曼編碼對BMP圖像進行壓縮處理，并得到相關測試數據。在相關程序的哈夫曼編碼過程中，判斷圖像是否全部出現256個顏色像素點后，僅讓有權值的像素點作為哈夫曼樹的葉結點，未出現的像素點不涉及哈夫曼樹的構建，由此可提高哈夫曼編碼的壓縮效率。由程序測試結果可知，屬于無損壓縮算法的范氏哈夫曼編碼的確能夠很好地無失真還原圖像壓縮文件。

在使用范氏哈夫曼編碼進行圖像壓縮的過程中，硬件平臺對于軟件算法上也有影響，可以針對不同硬件平臺的數據吞吐量和緩存資源來改進和優化算法。