近年来，随着互联网技术的发展，图像信息量不断增加，大量图像需要存储和传输[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上的投影为
| $ \mathit{\boldsymbol{n}} = {\mathit{\boldsymbol{s}}^{\rm{T}}}\mathit{\boldsymbol{t}}, $ | (1) |
投影后的方差为
| $ {\mathop{\rm var}} \left( \mathit{\boldsymbol{n}} \right) = Er\left[{{{\left( {{\mathit{\boldsymbol{s}}^{\rm{T}}}t-{\mathit{\boldsymbol{s}}^{\rm{T}}}e} \right)}^2}} \right] = {\mathit{\boldsymbol{s}}^{\rm{T}}}E\left[{\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right){{\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right)}^{\rm{T}}}} \right]s, $ |
其中，e为数据t的均值.由于PCA目的是寻找一个s，使得投影后的样本方差最大，故可以将此改写成一个拉格朗日问题，得到
| $ \mathop {\max }\limits_s \mathit{\boldsymbol{s}}\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right){\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right)^{\rm{T}}}{\mathit{\boldsymbol{s}}^{\rm{T}}}-\lambda \left( {\mathit{\boldsymbol{s}}{\mathit{\boldsymbol{s}}^{\rm{T}}} - 1} \right), $ | (2) |
对式(2)求导，并令导数为0，可得
| $ \left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right){\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right)^{\rm{T}}}\mathit{\boldsymbol{s}} = \lambda \mathit{\boldsymbol{s}}. $ | (3) |
如果s为协方差矩阵的特征向量，则λ为特征值，可通过舍弃某些对方差贡献小的特征值来达到降维的目的.最大特征值对应的单位特征向量S1贡献了方差的最大部分，第2特征值对应的单位特征向量S2贡献了方差的第2部分，依此类推.在对数据t投影之前，先要对n中心化.对于图像数据而言，一般不需要规范化方差，式(1)变为
| $ \mathit{\boldsymbol{n}} = {\mathit{\boldsymbol{s}}^{\rm{T}}}\left( {\mathit{\boldsymbol{t}}-\mathit{\boldsymbol{e}}} \right), $ | (4) |
其中，e为数据t的均值.求解s步骤同上，然后求解t的协方差矩阵，再求出其特征值和特征向量.并将特征值按从大到小的顺序排序，取前k个特征值和与其对应的特征向量s，代入式(4)，求解投影后的数据，该数据即为压缩后数据.若要用压缩后的数据重构原始图像，只需知道原数据的均值e、s、n.重构公式为
| $ \mathit{\boldsymbol{\hat t}} = \mathit{\boldsymbol{sn}} + \mathit{\boldsymbol{e}}, $ | (5) |
式(5)中，
图像数据通过小波分解，将系数的分布转折成树.根据该特征，定义数据结构为空间取向树.从图 1的4级小波分解空间取向树的结构中可以看到，每个系数有4个孩子：“黑色”标记的系数在LL子带和系数最高子带(HL1;LH1;HH1)中.以下系数坐标系用于表示集合分区，系数的位置由(i, j)表示，其中i和j分别表示行和列的索引.
|
图 1 SPIHT算法中的空间定位树结构 Fig. 1 SPIHT algorithm in the spatial positioningtree structure |
H为所有空间定向树的根.O(i, j)为系数的后代集合(i, j)，
| $ O\left( {i, j} \right) = \left\{ {\left( {2i, 2j} \right), \left( {2i, 2j + 1} \right), \left( {2i + 1, 2j + 1} \right)} \right\}, $ |
除(i, j)在LL中外; 当(i, j)在子带LL中时，O(i, j)定义为
| $ O\left( {i, j} \right) = \left\{ {\left( {i, j + {w_{LL}}} \right), \left( {i + {h_{LL}}, j + {w_{LL}}} \right)} \right\}, $ |
其中，wLL和hLL为宽度和高度.
D(i, j)为系数(i, j)的所有后代的集合，
| $ L\left( {i, j} \right):D\left( {i, j} \right)-O\left( {i, j} \right). $ |
图 1中，HL3是此方向子带中分辨率最低的，其中1个系数Ci, j3, 1为该方向树根节点，其子节点是HL2子带内的{2i+p, 2j+q}0≤p, q≤1，共4个系数，其孙节点是HL1子带内的{4i+p, 4j+q}0≤p, q≤3，共16个系数.如此，以Ci, j3, 1为根节点的一棵方向树[16]包含了21个系数, 有20个子孙.分解m≥2的层，HLm子带中节点公共的子孙节点个数为
| $ \sum\limits_{l = 1}^m {{4^l}} = \frac{4}{3}\left( {{4^{m-1}}-1} \right). $ |
图 1中，根节点位于最高层方位子带中，系数为根的方向树也叫最大方向树，可标作TL, d(i, j), 代表该树上所有系数的集合.其他层的系数也可以为根，构成一颗子方向树, 标作Tm, d(i, j).
而重要性函数Sn(τ)决定了坐标集的显著性，τ相对于阈值2n定义为
| $ {S_n}\left( \tau \right) = \left\{ \begin{array}{l} 1, \;\;\;\;\;\mathop {\max }\limits_{\left( {i, j} \right) \in \tau } \left| {{c_{i, j}}} \right| \ge {2^n}, \\ 0, \;\;\;\;\;其他, \end{array} \right. $ |
其中cj是小波系数.
在该算法中，使用了3个有序列表：无效集合列表(LIS)、无关列表像素(LIP)和有效像素列表(LSP)，来存储及设置分区期间的有效信息.
1.3 Huffman编码Huffman编码的主要思想是对数据符号发生的概率进行编码[12].源数据中出现的概率越高，对应的代码长度越短; 发生的概率越小，代码长度越长.因此应尽可能减少源数据代码符号，Huffman为接近压缩比上限的最佳编码方法.
1.4 基于PCA和SPIHT的哈夫曼编码算法为了确保压缩质量和提高压缩比，本文将PCA和SPIHT的哈夫曼编码算法相结合，对图像进行二级压缩.
1.4.1 PCA压缩首先对图像进行PCA降维处理，取前k个特征值和其对应的特征向量，求解压缩后的数据.只要知道原数据的均值e、s、n，就能根据压缩后的数据重构图像数据
利用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 |
为了验证本文算法的有效性，分别对10幅有代表性的图像进行压缩实验, 所有图像均为512*512的灰度图像.SPIHT算法采用的是type='bior4.4'.PCA降维处理和SPIHT算法将图像分解成不同子带的小波系数，并进行Huffman编码，得到编码比特流重建图像，计算图像的PNSR和SSIM.
PSNR是使用最广泛、最普遍的一种图像客观评价指标，是基于对应像素点间的误差，即基于误差敏感的图像质量评价指标.SSIM结构相似性也是一种全参考的图像质量评价指标，分别从亮度、对比度、结构三方面度量图像的相似性.本文压缩算法与SPIHT以及SPIHT与Huffman压缩结合算法的比较见表 1~5.
|
表 1 压缩比10：1时的PNSR值 Table 1 PSNR value when the compression ratio is 10:1 |
|
|
表 2 压缩比20：1时的PNSR值 Table 2 PSNR value when the compression ratio is 20:1 |
|
|
表 3 压缩比40：1时的PNSR值 Table 3 PSNR value when the compression ratio is 40:1 |
|
|
表 4 压缩比10：1时的SSIM值 Table 4 SSIM values when the compression ratio is 10:1 |
|
|
表 5 压缩比20：1时的SSIM值 Table 5 SSIM values when the compression ratio is 20: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种算法高.
|
|
表 6 压缩比40：1时的SSIM值 Table 6 SSIM values when the compression ratio is 40:1 |
本文算法与JEPG 2000压缩算法的比较见表 7.
|
|
表 7 不同压缩比时的PNSR和SSIM值 Table 7 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 imagewith the compression ratio of 40 |
提出了一种新的有损压缩算法，该算法结合了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]. Journal of Video Engineering, 2013, 37(3): 175–178. |
| [2] |
徐海. 基于小波变换的图像压缩的SPIHT改进算法[D]. 合肥: 合肥工业大学, 2006.
XU H.Image Compression Based on Wavelet Transform SPIHT Improved Algorithm[D].Hefei:Hefei University of Technology, 2006. |
| [3] |
胡昌华, 李国华, 周涛.
基于MATLAB 7.X的系统分析与设计.小波分析[M]. 第3版. 西安: 西安电子科技大学出版社, 2008.
HU C H, LI G H, ZHOU T. System Analysis and Design Based on MATLAB 7.X -Wavelet Analysis[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]. Science Technology and Engineering, 2013, 26: 7688–7691. DOI:10.3969/j.issn.1671-1815.2013.26.016 |
| [5] | DU Q, FOWLER J E. Hyperspectral image compression using JPEG2000 and principal component analysis[J]. IEEE Geoscience & Remote Sensing Letters, 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]. Microelectronics and Computer, 2011, 28(1): 92–94. |
| [7] | WANG C W, JENG J H.Image compression using PCA with clustering[C]//International Symposium on Intelligent Signal Processing and Communications Systems. 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]. Application Research of Computers, 2017(1): 1–6. |
| [9] | CHEN Y, HUANG Z, SUN H, et al.Lossy image compression using CA and contourlet transform[C]//MATEC Web of Conferences EDP Sciences. Paris:Atlantis Press, 2016. |
| [10] | RUFAI A M, ANBARJAFARI G, DEMIREL H. Lossy image compression using singular value decomposition and wavelet difference reduction[J]. Digital Signal Processing, 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]. IEEE Transactions on Circuits & Systems for Video Technology, 1996, 6(3): 243–250. |
| [12] |
尚文文, 田郡. 用Huffman编码实现图像压缩[J].
数字技术与应用, 2011(12): 238–239.
SHANG W W, TIAN J. Image compression using Huffman coding[J]. Digital Technology and Applications, 2011(12): 238–239. |
| [13] | NARASIMHULU S, RAMASHRI D T. Gray-scale image compression using DWT-SPIHT algorithm[J]. International Journal of Engineering Research and Applications, 2012, 2(4): 902–905. |
| [14] | SKODRAS A N, EBRAHIMI T.JPEG2000 image coding system theory and applications[C]//IEEE International Symposium on Circuits and Systems. Jinan:IEEE, 2006. |
| [15] | CHRISTOPOULOS C, SKODRAS A, EBRAHIMI T. The JPEG2000 still image coding system:An overview[J]. IEEE Transactions on Consumer Electronics, 2000, 46(4): 1103–1127. DOI:10.1109/30.920468 |
| [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]. Journal of Transportation Information and Security, 2004, 22(1): 32–34. |