基于主成分分析和分层树集合划分的Huffman算法图像压缩研究

方炫苏， 黄樟灿， 陈亚雄(武汉理工大学 理学院， 湖北 武汉 430070)

基于主成分分析和分层树集合划分的Huffman算法图像压缩研究

方炫苏， 黄樟灿， 陈亚雄
(武汉理工大学 理学院， 湖北 武汉 430070)

互联网的飞速发展，产生了大量的图像信息.为了减少图片占用的存储空间，提高图像质量，提出了一种将主成分分析(PCA)和分层树集合划分(SPIHT)压缩算法相结合的有损图像压缩算法.首先对图像进行主成分分解，选取主要特征值进行压缩，再利用SPIHT算法将图像分解成不同子带的小波系数进行压缩，对SPIHT压缩系数进行哈夫曼编码，实现图像二级压缩.将本文提出的算法与SPIHT、SPIHT的哈夫曼编码、JEPG2000、PCA压缩算法进行了比较，结果表明本算法较其他压缩算法具有更好的性能，在压缩比相同的情况下能获得更高的PNSR和 SSIM.

PCA；SPIHT；Huffman；图像压缩；PNSR；SSIM

0 引 言

近年来，随着互联网技术的发展，图像信息量不断增加，大量图像需要存储和传输[1].为了有效防止图像信息在存储和传输过程中发生畸变，可以通过数字化处理将原图像转化为数字图像，然后再进行储存、传输和重建[2].小波变换是一种新的变换分析方法，继承并发展了短时傅立叶变换局部化的思想，同时又克服了窗口大小不随频率变化等缺点，能够提供随频率改变的“时间-频率”窗口，是进行信号时频分析和处理的理想工具[3].但是小波变换以小波基函数为基础的，每种小波基函数对不同类图像的适应程度不同，从而限制了压缩算法的应用范围[4].主成分分析PCA算法是一种基于特征向量的有损压缩算法[5-6]，可以有效找出数据的主成分，去除数据的冗余和噪声，达到降维的目的，并且方法简单，无参数限制，故提出了基于心理视觉冗余和PCA的图像压缩算法[7-10].由于在更高的压缩比下会产生更多误差，即接收端的均方误差会增高，而SPIHT实现了对DWT的更多改进[11]，无须采用特殊方法而直接输出.Huffman编码的主导思想是根据数据符号发生的概率进行编码.在源数据中出现概率越高的符号，相应的码长越短；出现概率越低的符号，其码长越长,从而达到用尽可能少的码符号表示源数据的目的.Huffman是接近压缩比上限的一种最佳编码方法[12].基于此，本文提出一种比Huffman更进一步组合压缩的简单有效的方法.大量实验结果显示，该方法节省了大量的位传输，增强了压缩性能[13].JPEG 2000是新一代静态图像的压缩算法，使用离散小波变换将原始图像“平铺”到矩形非重叠块中[14].平铺减小了内存要求，提高了JPEG 2000的压缩性能，优化了截断嵌入块的编码和码流组织形式[15].总体来看，PCA压缩技术提供了很好的PSNR值，并且有很低的压缩比；而基于SPIHT的Huffman算法提供了很好的压缩效果.然而，对于基于SPIHT的Huffman算法，可以结合基于PCA的图像压缩进行改进.本文提出的基于主成分分析和SPIHT压缩算法的有损图像压缩算法，已在10幅有代表性的图像上进行了测试，并与JEPG 2000进行比较，在压缩比相同情况下，本文算法各图像的PNSR和SSIM值均有所提高.

1 基于主成分分析和SPIHT变化的图像压缩

1.1 PCA 压缩算法

主成分分析PCA不需要输出信息，是一种非监督方法.PCA是一种将分布在一组变量上的信息集中至几个主要组成部分进行探索的统计方法.PCA的目标是使用另一组基向量来重新描述产生的数据空间，而新的基能揭示原来数据之间的关系[12].数据t在方向s上的投影为

n=sTt,

(1)

投影后的方差为

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

其中，e为数据t的均值.由于PCA目的是寻找一个s，使得投影后的样本方差最大，故可以将此改写成一个拉格朗日问题，得到

(2)

对式(2)求导，并令导数为0，可得

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

(3)

如果s为协方差矩阵的特征向量，则λ为特征值，可通过舍弃某些对方差贡献小的特征值来达到降维的目的.最大特征值对应的单位特征向量S1贡献了方差的最大部分，第2特征值对应的单位特征向量S2贡献了方差的第2部分，依此类推.在对数据t投影之前，先要对n中心化.对于图像数据而言，一般不需要规范化方差，式(1)变为

n=sT(t-e),

(4)

其中，e为数据t的均值.求解s步骤同上，然后求解t的协方差矩阵，再求出其特征值和特征向量.并将特征值按从大到小的顺序排序，取前k个特征值和与其对应的特征向量s，代入式(4)，求解投影后的数据，该数据即为压缩后数据.若要用压缩后的数据重构原始图像，只需知道原数据的均值e、s、n.重构公式为

(5)

1.2 SPIHT压缩算法

图像数据通过小波分解，将系数的分布转折成树.根据该特征，定义数据结构为空间取向树.从图1的4级小波分解空间取向树的结构中可以看到，每个系数有4个孩子： “黑色”标记的系数在LL子带和系数最高子带(HL1;LH1;HH1)中.以下系数坐标系用于表示集合分区，系数的位置由(i,j)表示，其中i和j分别表示行和列的索引.

H为所有空间定向树的根.O(i,j)为系数的后代集合(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)为系数(i,j)的所有后代的集合，

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

图1 SPIHT算法中的空间定位树结构Fig.1 SPIHT algorithm in the spatial positioning tree structure

图1中，根节点位于最高层方位子带中，系数为根的方向树也叫最大方向树，可标作TL,d(i,j),代表该树上所有系数的集合.其他层的系数也可以为根，构成一颗子方向树,标作Tm,d(i,j).

而重要性函数Sn(τ)决定了坐标集的显著性，τ相对于阈值2n定义为

其中cj是小波系数.

在该算法中，使用了3个有序列表： 无效集合列表(LIS)、无关列表像素(LIP)和有效像素列表(LSP)，来存储及设置分区期间的有效信息.

1.3 Huffman编码

Huffman编码的主要思想是对数据符号发生的概率进行编码[12].源数据中出现的概率越高，对应的代码长度越短;发生的概率越小，代码长度越长.因此应尽可能减少源数据代码符号，Huffman为接近压缩比上限的最佳编码方法.

1.4 基于PCA和SPIHT的哈夫曼编码算法

为了确保压缩质量和提高压缩比，本文将PCA和SPIHT的哈夫曼编码算法相结合，对图像进行二级压缩.

1.4.1 PCA压缩

1.4.2 SPIHT算法和Huffman算法

利用SPIHT算法将重构图像分解成不同子带的小波系数进行压缩，将SPIHT算法压缩系数进行Huffman编码，得到编码比特流.Huffman编码方法是先扫描要编码的文件，统计SPHIT算法压缩系数的概率，然后再将其编码成比特流.

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 实验及结果分析

为了验证本文算法的有效性，分别对10幅有代表性的图像进行压缩实验,所有图像均为512*512的灰度图像.SPIHT算法采用的是type='bior4.4'.PCA降维处理和SPIHT算法将图像分解成不同子带的小波系数，并进行Huffman编码，得到编码比特流重建图像，计算图像的PNSR和SSIM.

PSNR是使用最广泛、最普遍的一种图像客观评价指标，是基于对应像素点间的误差，即基于误差敏感的图像质量评价指标.SSIM结构相似性也是一种全参考的图像质量评价指标，分别从亮度、对比度、结构三方面度量图像的相似性.本文压缩算法与SPIHT以及SPIHT与Huffman压缩结合算法的比较见表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之间的关系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种算法好.定量和定性结果表明，本文算法有较好的图像质量和压缩比.由于SPIHT对图像信号贡献较大，Huffman有较好的图像性质，故能够很好地和PCA压缩算法结合，在相同压缩比时，提高了图像的质量和SSIM值.

图5 压缩比为40时的Perpers图像压缩效果图Fig.5 The compression chart of Peppers image with the compression ratio of 40

3 结 语

提出了一种新的有损压缩算法，该算法结合了PCA、SPIHT和Huffman算法的优点.PCA是为了重构图像，经过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].合肥： 合肥工业大学,2006.

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

[3] 胡昌华,李国华,周涛.基于MATLAB7.X的系统分析与设计.小波分析[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].科学技术与工程,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算法和小波包变换的人脸识别技术[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].计算机应用研究,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 编码实现图像压缩[J].数字技术与应用,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图像编码方法的研究与实现[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，女，本科，主要从事应用数学研究,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