基于主成分分析和分層樹集合劃分的Huffman算法圖像壓縮研究

方炫蘇， 黃樟燦， 陳亞雄(武漢理工大學 理學院， 湖北 武漢 430070)

基于主成分分析和分層樹集合劃分的Huffman算法圖像壓縮研究

方炫蘇， 黃樟燦， 陳亞雄
(武漢理工大學 理學院， 湖北 武漢 430070)

互聯(lián)網(wǎng)的飛速發(fā)展，產(chǎn)生了大量的圖像信息.為了減少圖片占用的存儲空間，提高圖像質(zhì)量，提出了一種將主成分分析(PCA)和分層樹集合劃分(SPIHT)壓縮算法相結(jié)合的有損圖像壓縮算法.首先對圖像進行主成分分解，選取主要特征值進行壓縮，再利用SPIHT算法將圖像分解成不同子帶的小波系數(shù)進行壓縮，對SPIHT壓縮系數(shù)進行哈夫曼編碼，實現(xiàn)圖像二級壓縮.將本文提出的算法與SPIHT、SPIHT的哈夫曼編碼、JEPG2000、PCA壓縮算法進行了比較，結(jié)果表明本算法較其他壓縮算法具有更好的性能，在壓縮比相同的情況下能獲得更高的PNSR和 SSIM.

PCA；SPIHT；Huffman；圖像壓縮；PNSR；SSIM

0 引 言

近年來，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，圖像信息量不斷增加，大量圖像需要存儲和傳輸[1].為了有效防止圖像信息在存儲和傳輸過程中發(fā)生畸變，可以通過數(shù)字化處理將原圖像轉(zhuǎn)化為數(shù)字圖像，然后再進行儲存、傳輸和重建[2].小波變換是一種新的變換分析方法，繼承并發(fā)展了短時傅立葉變換局部化的思想，同時又克服了窗口大小不隨頻率變化等缺點，能夠提供隨頻率改變的“時間-頻率”窗口，是進行信號時頻分析和處理的理想工具[3].但是小波變換以小波基函數(shù)為基礎(chǔ)的，每種小波基函數(shù)對不同類圖像的適應(yīng)程度不同，從而限制了壓縮算法的應(yīng)用范圍[4].主成分分析PCA算法是一種基于特征向量的有損壓縮算法[5-6]，可以有效找出數(shù)據(jù)的主成分，去除數(shù)據(jù)的冗余和噪聲，達到降維的目的，并且方法簡單，無參數(shù)限制，故提出了基于心理視覺冗余和PCA的圖像壓縮算法[7-10].由于在更高的壓縮比下會產(chǎn)生更多誤差，即接收端的均方誤差會增高，而SPIHT實現(xiàn)了對DWT的更多改進[11]，無須采用特殊方法而直接輸出.Huffman編碼的主導思想是根據(jù)數(shù)據(jù)符號發(fā)生的概率進行編碼.在源數(shù)據(jù)中出現(xiàn)概率越高的符號，相應(yīng)的碼長越短；出現(xiàn)概率越低的符號，其碼長越長,從而達到用盡可能少的碼符號表示源數(shù)據(jù)的目的.Huffman是接近壓縮比上限的一種最佳編碼方法[12].基于此，本文提出一種比Huffman更進一步組合壓縮的簡單有效的方法.大量實驗結(jié)果顯示，該方法節(jié)省了大量的位傳輸，增強了壓縮性能[13].JPEG 2000是新一代靜態(tài)圖像的壓縮算法，使用離散小波變換將原始圖像“平鋪”到矩形非重疊塊中[14].平鋪減小了內(nèi)存要求，提高了JPEG 2000的壓縮性能，優(yōu)化了截斷嵌入塊的編碼和碼流組織形式[15].總體來看，PCA壓縮技術(shù)提供了很好的PSNR值，并且有很低的壓縮比；而基于SPIHT的Huffman算法提供了很好的壓縮效果.然而，對于基于SPIHT的Huffman算法，可以結(jié)合基于PCA的圖像壓縮進行改進.本文提出的基于主成分分析和SPIHT壓縮算法的有損圖像壓縮算法，已在10幅有代表性的圖像上進行了測試，并與JEPG 2000進行比較，在壓縮比相同情況下，本文算法各圖像的PNSR和SSIM值均有所提高.

1 基于主成分分析和SPIHT變化的圖像壓縮

1.1 PCA 壓縮算法

主成分分析PCA不需要輸出信息，是一種非監(jiān)督方法.PCA是一種將分布在一組變量上的信息集中至幾個主要組成部分進行探索的統(tǒng)計方法.PCA的目標是使用另一組基向量來重新描述產(chǎn)生的數(shù)據(jù)空間，而新的基能揭示原來數(shù)據(jù)之間的關(guān)系[12].數(shù)據(jù)t在方向s上的投影為

n=sTt,

(1)

投影后的方差為

var(n)=Er[(sTt-sTe)2]=sTE[(t-e)(t-e)T]s,

其中，e為數(shù)據(jù)t的均值.由于PCA目的是尋找一個s，使得投影后的樣本方差最大，故可以將此改寫成一個拉格朗日問題，得到

(2)

對式(2)求導，并令導數(shù)為0，可得

(t-e)(t-e)Ts=λs.

(3)

如果s為協(xié)方差矩陣的特征向量，則λ為特征值，可通過舍棄某些對方差貢獻小的特征值來達到降維的目的.最大特征值對應(yīng)的單位特征向量S1貢獻了方差的最大部分，第2特征值對應(yīng)的單位特征向量S2貢獻了方差的第2部分，依此類推.在對數(shù)據(jù)t投影之前，先要對n中心化.對于圖像數(shù)據(jù)而言，一般不需要規(guī)范化方差，式(1)變?yōu)?/p>

n=sT(t-e),

(4)

其中，e為數(shù)據(jù)t的均值.求解s步驟同上，然后求解t的協(xié)方差矩陣，再求出其特征值和特征向量.并將特征值按從大到小的順序排序，取前k個特征值和與其對應(yīng)的特征向量s，代入式(4)，求解投影后的數(shù)據(jù)，該數(shù)據(jù)即為壓縮后數(shù)據(jù).若要用壓縮后的數(shù)據(jù)重構(gòu)原始圖像，只需知道原數(shù)據(jù)的均值e、s、n.重構(gòu)公式為

(5)

1.2 SPIHT壓縮算法

圖像數(shù)據(jù)通過小波分解，將系數(shù)的分布轉(zhuǎn)折成樹.根據(jù)該特征，定義數(shù)據(jù)結(jié)構(gòu)為空間取向樹.從圖1的4級小波分解空間取向樹的結(jié)構(gòu)中可以看到，每個系數(shù)有4個孩子： “黑色”標記的系數(shù)在LL子帶和系數(shù)最高子帶(HL1;LH1;HH1)中.以下系數(shù)坐標系用于表示集合分區(qū)，系數(shù)的位置由(i,j)表示，其中i和j分別表示行和列的索引.

H為所有空間定向樹的根.O(i,j)為系數(shù)的后代集合(i,j)，

O(i,j)={(2i,2j),(2i,2j+1),(2i+1,2j+1)}，

除(i,j)在LL中外; 當(i,j)在子帶LL中時，O(i,j)定義為

O(i,j)={(i,j+wLL),(i+hLL,j+wLL)}，

其中，wLL和hLL為寬度和高度.

D(i,j)為系數(shù)(i,j)的所有后代的集合，

L(i,j)：D(i,j)-O(i,j).

圖1 SPIHT算法中的空間定位樹結(jié)構(gòu)Fig.1 SPIHT algorithm in the spatial positioning tree structure

圖1中，根節(jié)點位于最高層方位子帶中，系數(shù)為根的方向樹也叫最大方向樹，可標作TL,d(i,j),代表該樹上所有系數(shù)的集合.其他層的系數(shù)也可以為根，構(gòu)成一顆子方向樹,標作Tm,d(i,j).

而重要性函數(shù)Sn(τ)決定了坐標集的顯著性，τ相對于閾值2n定義為

其中cj是小波系數(shù).

在該算法中，使用了3個有序列表： 無效集合列表(LIS)、無關(guān)列表像素(LIP)和有效像素列表(LSP)，來存儲及設(shè)置分區(qū)期間的有效信息.

1.3 Huffman編碼

Huffman編碼的主要思想是對數(shù)據(jù)符號發(fā)生的概率進行編碼[12].源數(shù)據(jù)中出現(xiàn)的概率越高，對應(yīng)的代碼長度越短;發(fā)生的概率越小，代碼長度越長.因此應(yīng)盡可能減少源數(shù)據(jù)代碼符號，Huffman為接近壓縮比上限的最佳編碼方法.

1.4 基于PCA和SPIHT的哈夫曼編碼算法

為了確保壓縮質(zhì)量和提高壓縮比，本文將PCA和SPIHT的哈夫曼編碼算法相結(jié)合，對圖像進行二級壓縮.

1.4.1 PCA壓縮

1.4.2 SPIHT算法和Huffman算法

利用SPIHT算法將重構(gòu)圖像分解成不同子帶的小波系數(shù)進行壓縮，將SPIHT算法壓縮系數(shù)進行Huffman編碼，得到編碼比特流.Huffman編碼方法是先掃描要編碼的文件，統(tǒng)計SPHIT算法壓縮系數(shù)的概率，然后再將其編碼成比特流.

1.4.3 逆SPIHT和逆Huffman

首先，對編碼比特流進行Huffman逆變化，然后進行SPIHT逆變化.其算法流程如圖2和3所示.

圖2 本文壓縮框圖Fig.2 The block diagram of compression

圖3 重建圖像框圖Fig.3 The block diagram of reconstruction

2 實驗及結(jié)果分析

為了驗證本文算法的有效性，分別對10幅有代表性的圖像進行壓縮實驗,所有圖像均為512*512的灰度圖像.SPIHT算法采用的是type='bior4.4'.PCA降維處理和SPIHT算法將圖像分解成不同子帶的小波系數(shù)，并進行Huffman編碼，得到編碼比特流重建圖像，計算圖像的PNSR和SSIM.

PSNR是使用最廣泛、最普遍的一種圖像客觀評價指標，是基于對應(yīng)像素點間的誤差，即基于誤差敏感的圖像質(zhì)量評價指標.SSIM結(jié)構(gòu)相似性也是一種全參考的圖像質(zhì)量評價指標，分別從亮度、對比度、結(jié)構(gòu)三方面度量圖像的相似性.本文壓縮算法與SPIHT以及SPIHT與Huffman壓縮結(jié)合算法的比較見表1～5.

表1 壓縮比10：1時的PNSR值Table1 PSNR value when the compression ratio is 10：1

表2 壓縮比20：1時的PNSR值Table2 PSNR value when the compression ratio is 20：1

表3 壓縮比40：1時的PNSR值Table3 PSNR value when the compression ratio is 40：1

表4 壓縮比10：1時的SSIM值Table4 SSIM values when the compression ratio is 10：1

表5 壓縮比20：1時的SSIM值Table5 SSIM values when the compression ratio is 20：1

表6 壓縮比40：1時的SSIM值Table6 SSIM values when the compression ratio is 40：1

表1顯示在壓縮比為10：1時，使用文中算法和SPIHT算法以及SPIHT+Huffman算法的PNSR值，表2和表3分別表示在壓縮比為20：1和40：1時的PNSR值.從表1～3可以看出，本文算法比SPIHT和SPIHT+Huffman算法好.在相同的壓縮比下，本文算法比SPIHT算法提高約10 dB，比SPIHT+Huffman算法提高約2 dB.表4～表6為壓縮比分別為10：1，20：1和40：1時3種算法的SSIM值.可以看出本文算法顯然比其他2種算法高.

本文算法與JEPG 2000壓縮算法的比較見表7.

表7 不同壓縮比時的PNSR和SSIM值Table7 PSNR and SSIM values with difference compression ratios

由表7知，在相同的壓縮比下，本文算法的PNSR和SSIM值比JEPG 2000壓縮算法高.

用Matlab軟件繪制Perpers圖像的PNSR值如圖4所示，可以直觀看出，本文算法的PNSR值顯然比JEPG 2000壓縮算法、SPIHT壓縮算法以及SPIHT+Huffman算法高.

圖4 不同算法中壓縮比和PNSR之間的關(guān)系Fig.4 The relationship between compression ratio and PNSR in different algorithms

通過Matlab軟件將本文壓縮與SPIHT壓縮、SPIHT+Huffman壓縮、JEPG 2000壓縮和PCA壓縮的效果進行了比較，壓縮比為40時，Perpers圖像壓縮后的效果圖如圖5所示.本文算法的PNSR值比其他2種算法高；當壓縮比提高時，本文算法還是比其他2種算法好.定量和定性結(jié)果表明，本文算法有較好的圖像質(zhì)量和壓縮比.由于SPIHT對圖像信號貢獻較大，Huffman有較好的圖像性質(zhì)，故能夠很好地和PCA壓縮算法結(jié)合，在相同壓縮比時，提高了圖像的質(zhì)量和SSIM值.

圖5 壓縮比為40時的Perpers圖像壓縮效果圖Fig.5 The compression chart of Peppers image with the compression ratio of 40

3 結(jié) 語

提出了一種新的有損壓縮算法，該算法結(jié)合了PCA、SPIHT和Huffman算法的優(yōu)點.PCA是為了重構(gòu)圖像，經(jīng)過SPIHT和Huffman算法達到壓縮圖像的目的.本文算法的壓縮比是PCA壓縮比和SPIHT和Huffman算法壓縮比的乘積.通過定量與定性測算可知，本文的壓縮算法較SPIHT壓縮和Huffman壓縮算法好.

[1] AN H,MENG L,ZHAO L,et al,Long-distance transmission and high-speed and real-time storage technology of image data[J].JournalofVideoEngineering，2013，37(3) ： 175-178.

[2] 徐海.基于小波變換的圖像壓縮的SPIHT改進算法[D].合肥： 合肥工業(yè)大學,2006.

XU H.ImageCompressionBasedonWaveletTransformSPIHTImprovedAlgorithm[D].Hefei ： Hefei University of Technology,2006.

[3] 胡昌華,李國華,周濤.基于MATLAB7.X的系統(tǒng)分析與設(shè)計.小波分析[M].第3版.西安： 西安電子科技大學出版社,2008.

HU C H,LI G H,ZHOU T.SystemAnalysisandDesignBasedonMATLAB7.X-WaveletAnalysis[M].3rd ed. Xi’an： Xidian University Press,2008.

[4] 張帆.基于心理視覺冗余和 PCA 的圖像壓縮算法[J].科學技術(shù)與工程,2013,26： 7688-7691

ZHANG F.Image compression algorithm based on psychological visual redundancy and PCA [J].ScienceTechnologyandEngineering,2013,26： 7688-7691.

[5] DU Q,FOWLER J E.Hyperspectral image compression using JPEG2000 and principal component analysis[J].IEEEGeoscience&RemoteSensingLetters,2007,4(2)： 201-205.

[6] 楊穎嫻．基于PCA算法和小波包變換的人臉識別技術(shù)[J]．微電子學與計算機，2011,28(1)： 92-94.

YANG Y X.Face recognition technology based on PCA algorithm and wavelet packet transform[J].MicroelectronicsandComputer,2011,28 (1)： 92-94.

[7] WANG C W,JENG J H.Image compression using PCA with clustering[C]//InternationalSymposiumonIntelligentSignalProcessingandCommunicationsSystems. Taibei： Circuits and System Society,2012： 458-462.

[8] 陳亞雄,黃樟燦,馮磊.基于奇異值分解和Contour let變換的圖像壓縮算法[J].計算機應(yīng)用研究,2017(1)： 1-6.

CHEN Y X,HUANG Z C,FENG L.Image compression algorithm based on singular value decomposition and contourlet transform [J].ApplicationResearchofComputers,2017(1)： 1-6.

[9] CHEN Y,HUANG Z,SUN H,et al.Lossy image compression using CA and contourlet transform[C]//MATECWebofConferencesEDPSciences. Paris： Atlantis Press,2016.

[10] RUFAI A M,ANBARJAFARI G,DEMIREL H.Lossy image compression using singular value decomposition and wavelet difference reduction[J].DigitalSignalProcessing,2013,24(1)： 117-123.

[11] SAID A,PEARLMAN W A.A new,fast,and efficient image codec based on set partitioning in hierarchical trees[J].IEEETransactionsonCircuits&SystemsforVideoTechnology,1996,6(3)： 243-250.

[12] 尚文文,田郡.用 Huffman 編碼實現(xiàn)圖像壓縮[J].數(shù)字技術(shù)與應(yīng)用,2011 (12)： 238-239.

SHANG W W,TIAN J.Image compression using Huffman coding [J].DigitalTechnologyandApplications,2011 (12)： 238-239.

[13] NARASIMHULU S,RAMASHRI D T.Gray-scale image compression using DWT-SPIHT algorithm[J].InternationalJournalofEngineeringResearchandApplications,2012,2(4)： 902-905.

[14] SKODRAS A N,EBRAHIMI T.JPEG2000 image coding system theory and applications[C]//IEEEInternationalSymposiumonCircuitsandSystems. Jinan： IEEE,2006.

[15] CHRISTOPOULOS C, SKODRAS A, EBRAHIMI T. The JPEG2000 still image coding system： An overview[J].IEEETransactionsonConsumerElectronics,2000,46(4)： 1103-1127.

[16] 張昱,王虹.基于空間方向樹的改進EZW圖像編碼方法的研究與實現(xiàn)[J].交通信息與安全,2004,22(1)： 32-34.

ZHANG Y,WANG H.Study and implementation of improved ezw image coding method based on spatial direction tree [J].JournalofTransportationInformationandSecurity,2004,22 (1)： 32-34.

FANG Xiansu,HUANG Zhangcan,CHEN Yaxiong
(SchoolofScience,WuhanUniversityofTechnology,Wuhan430070,China)

In order to reduce the storage and improve the image quality of the compressed, a lossy image compression algorithm based on principal component analysis and set partitioning in hierarchical tree(SPIHT)compression algorithm is proposed. Firstly, the image is decomposed by principal component decomposition, and the main features are selected to realize image compression, then SPIHT algorithm is used to compress the image into wavelet coefficients of different subband. Finally, Huffman coding is employed to achieve two-level image compression. Comparing this algorithm with SPIHT algorithm, Huffman coding algorithm of SPIHT, JEPG 2000 and PCA compression algorithm, our experimental results demonstrate a better performance than other compression algorithms and can obtain higher PNSR and SSIM under the same compression ratio.

PCA; SPIHT; Huffman; image compression；PNSR；SSIM

2016-12-08.

國家科技支撐計劃項目(2013BAJ02B00).

方炫蘇(1996—)，ORCID： http： //orcid.org/0000-0002-6406-1799，女，本科，主要從事應(yīng)用數(shù)學研究,E-mail： 793137669@qq.com.

10.3785/j.issn.1008-9497.2018.01-009

TP 751

A

1008-9497(2018)01-054-06

ResearchonHuffmanalgorithmbasedonPCAandSPIHTforimagecompression.Journal of Zhejiang University (Science Edition)，2018,45(1)： 054-059