基于谱图小波变换的图像压缩编码方法①

王 林,宋 星

(西安理工大学 自动化与信息工程学院,西安 710048)

图像压缩主要解决的问题是尽量减少用来表示图像信息的数据量,通常使用某种变换去掉图像中的冗余信息来达到压缩的目的.针对图像压缩的图像变换,使图像在变换域能量集中地表示,大量的信息集中于少数的系数上,而其他的数据很小或几乎为零,数据进行压缩编码处理时就能更加有效地压缩数据,这对图像的高效存储与传输具有十分重要的意义.

目前,常见的用于图像压缩的变换主要有K-L交换、Fourier变换、离散余弦变换(DCT)、小波变换以及近几年出现的以几何多尺度分析[1]为主要工具的新型变换等.多年来,小波变换在图像压缩中已得到了成功的应用,但是图像的不连续处的变换系数存在显著误差导致重建图像质量较差.图可对复杂的、不规则区域中定义的信号[2,3]进行有效表示.因此,2011 年Hammond等人提出了谱图小波变换(Spectral Graph Wavelet Transform,SGWT)[4],它是一种多尺度几何分析理论,基于谱图理论[5]和小波变换理论,具有很好的尺度不变性和局部自适应性,能对不规则区域图像进行很好的稀疏表示,并具备完备的理论体系从稀疏系数中恢复原始图像,在图像处理领域得到了迅速的发展.2013年,Ortega等人提出了基于图的小波图像编码方法[6],通过设计滤波器,然后利用SPIHT算法对滤波器系数进行压缩编码.

为了改善小波压缩图像重构质量较差的缺点,本文利用谱图小波变换对图像进行分解,提出一种针对谱图小波系数的集合分裂嵌入式块编码(Set Partitioned Embedded Block,SPECK)算法,具有较高的编码速度,是嵌入式图像编码算法中性能较好的一种.实验结果表明,该算法对经典图像压缩编码后均取得了不错的压缩效果,具有较高的压缩比和峰值信噪比.

1 谱图小波

1.1 经典小波变换

连续小波的产生与母小波的选择有关,引入尺度因子s,这里令s>0,位置因子a,则小波在不同的位置和尺度下对应的母小波可表示为:

则函数f(t)在尺度s和位置a处的连续小波变换定义为:

从傅里叶域角度出发,假设尺度参数s是离散的,将位置参数a作为函数独立的变量,连续小波在傅里叶域表示为:

1.2 谱图理论

加权图可用G=(V,E,W)表示,其中V表示节点集,E表示边集,w为边对应的权值.讨论有限无向图,其中N为图中节点数,表示图G的邻接矩阵,该矩阵元素am,n可表示如下:

度d(m)定义为称为图G的度矩阵.

图拉普拉斯[7]矩阵L定义为:

L为实对称矩阵该矩阵具有一组完备的正交向量集,并且L对应的特征值均为非负值.对应的特征向量相互正交,特征值满足:

拉普拉斯矩阵的特征空间类似于傅里叶域.因此,定义图上傅里叶变换[8]:

相应的,图上傅里叶逆变换定义为:

1.3 谱图小波变换

类似于图的傅里叶变换,为了定义图上的小波变换,选择满足的小波核函数g,使对应于在尺度t和节点n,图的拉普拉斯矩阵的特征空间L,定义谱图小波

选择满足的低通滤波核函数h,定义图上的尺度函数

小波系数和尺度系数如式(10)和式(11)所示:

因为对于大图不能明确的计算拉普拉斯矩阵的特征空间,文献[6]提出一种快速谱图小波变换算法,它用切比雪夫多项式逼近[9]小波核函数g和h.

cj,k表示切比雪夫系数,Mj是多项式逼近的阶数,表示阶数是k的移位切比雪夫多项式.给出快速的近似谱图小波变换:

根据公式(13)和(14)给出的快速小波系数和尺度系数计算公式,当尺度 Nscales=4,256×256 的 lena.bmp谱图小波变换得到一个低频系数和4个高频系数,如图1所示.

图1 谱图小波分解示意图

尺度系数也称为低频系数,如图1(a)所示,可以看出它集中了原始图像的主要能量.小波系数也称为高频系数,如图1(b～f)所示,显示了图像边缘、轮廓的纹理特征,其数值远小于尺度系数值.所以说在谱图小波系数中存在许多不重要的系数,具有能量聚集性以及能量随尺度增加而衰减的特性.

从一组给定的谱图小波系数c=wf中恢复一个图信号,合并所有的小波变换,框架算子将信号f映射成框架系数,即其中c0=Thf是尺度系数,是尺度为sj的小波系数使用伪逆算子从逼近系数和小波系数重构信号的计算本文采用共轭梯度方法,而W*W和W*的计算采用快速切比雪夫多项式逼近方法.

2 基于谱图小波系数的 SPECK 算法

在完成图像的谱图小波变换后,得到多个一维的小波系数向量.由于小波系数中存在许多不重要的系数,具有能量聚集性以及能量随尺度增加而衰减的特性,而基于块集合划分思想的SPECK(集合分裂嵌入式块编码)算法[10]是一种针对小波系数的编码算法,该算法是近期嵌入式分级图像编码算法中性能较好的一种.

为了消除分量系数之间的冗余性,本文使用改进后的SPECK编码算法[11,12]进行位平面编码,具体算法为编码时将所有分量系数视为一个整体,对各个分量进行交叉位平面编码,生成一个混合的位流.

设cj,n表示在尺度下sj的第n个谱小波变换系数.算法的实现过程中,采用逐次逼近量化,定义了非重要集合链表(LIS)和重要系数链表(LSC)两个链表.具体的算法流程如下所示.

算法.基于改进的SPECK算法的谱图小波系数编码1)算法初始化计算 将变换系数c分成根集合S=c0和剩余集合 置 LSC 为空表,并将 S放入LIS中.2)分类扫描过程按|S|大小升序排列集合S,对每个 执行子过程如果 执行子过程3)精细扫描过程对上次分类扫描过程中己是显著的系数,输出该系数的第k个显著位.4)量化步长更新如果位平面索引 k>0,k=k–1,返回第 2)步;否则停止.其中,各个子过程描述如下:输出集合S的第k个显著位如果如果S是单个系数,输出系数的符号位,然后放入LSC中;否则执行子过程如果 从LIS中删除S如果如果把 S 放入 LIS 中对集合将 S 分裂成 S1,S2,其中输出集合Si的第k个显著位如果

如果Si是单个系数,输出系数的符号位,然后放入LIS中否则执行子过程如果,把 S 放入 LIS 中:输出集合I的第k个显著位如果执行子过程:将 I分裂成 S*和 I*,其中,对集合S*,执行子过程对集合I*,执行子过程

3 实验结果与分析

对该算法整体分析可知,算法中全部可变参数有尺度参数Nscales,切比雪夫多项式阶数m,设计参数k=200以及扫描次数sm.由于切比雪夫多项式阶数m影响重构图像的质量,因此实验中以m值作为变量,得到不同质量的重构图像.

3.1 图像数据压缩

对图像压缩性能的评价则可以用压缩比Cr来表示如下:

由于不同码率下恢复图像的质量不同,因此压缩率并不是一个独立的指标,必须与图像恢复质量统一进行比较.

在进行算法测试时,选取512×512像素的经典图像,利用文中提出的算法,设置Nscales=5,在保证图像重构质量良好的情况下,得到压缩后数据量与原数据的压缩比(Cr)及峰值信噪比(PSNR),压缩结果如表1所示.

表1 512×512 像素图像压缩结果

分析表1中的数据,将谱图小波压缩后得到的图像与原图像进行对比,可以看出文中提出的压缩算法在一定程度上减少了数据量,总体得到了不错的压缩效果,证明了本文提出的谱小波压缩方案的可行性.这是由于选取了合适的参数,突出了图像重构中较大小波系数的重要性,而且基于块编码的算法较大程度地减少了较小的小波系数,从而提高了压缩比.

3.2 重构误差衡量

峰值信噪比(PSNR)表示峰值信号与噪声的比值,它是表征图像重构效果的重要指标[13],PSNR评价模型定义如下:

式中,MES为均方误差,是原始图像与重构图像之间的灰度差,M和N为图像矩阵维度数(图像像素),l为图像最大灰度值,通常 8 bit的图像l为 255.PSNR值越大,表示重构误差越小,两幅图像相似度越高.

为验证算法的有效性,设置不同的切比雪夫多项式阶数m,得到图像重构结果如表2所示,在相同条件下m越小,相应的图像的PSNR也越高,重构误差就相对较小.

表2 不同 m 下的图像重构结果

分别以256×256和512×512像素的lena图像为例进行相关实验.选取扫描次数sm=6,尺度参数Nscales=5,切比雪夫多项式阶数m分别取3和5,得到结果如图2所示.对比不同m下的重构图像,可以看出,图2(b)的重构图像与图2(c)相比更接近原始图像,也就是说,重构误差就相对较小.

图2 256×256 像素的 lena 重构图像

图3 512×512 像素的 lena 重构图像

3.3 相关算法的分析比较

选取256×256的lena和template图像,利用上述压缩比Cr和峰值信噪比PSNR的定义式,我们可以在相同条件下,利用本文的算法与基于小波变换的SPECK编码算法计算得到不同尺度下的Cr值和PSNR值,结果如表3所示.

表3 基于不同变换的编码算法的图像压缩重构结果

表3中的数据显示,本文提出的压缩算法与基于小波变换的压缩算法相比较,有更大的压缩比,这说明谱图小波压缩的压缩效果更为明显.并且随着尺度的改变压缩比变化很小,图像重构质量也相对稳定.

综上所述,本文提出的压缩算法在对几个经典图像进行压缩编码后,均取得了较好的压缩比.且与基于小波变换的编码算法进行对比,在减少占用内存空间和重构误差方面都有了一定的改进.

4 结论与展望

本文采用基于谱图理论和经典小波变换理论的谱图小波变换,提出了一种针对谱小波系数利用SPECK编码进行压缩编码的新方法.文中对几个经典的图像进行了性能测试,均取得了不错的压缩效果,并从压缩比和峰值信噪比两个方面讨论了图像压缩及重构的质量,该算法在减少数据存储空间和重构误差方面都有了一定的改进.但是对于大图来讲,编解码的速度相对较慢,这也是未来继续研究的方向.

参考文献

1Jansen M,Nason GP,on,Silverman BW,et al.Multiscale methods for data on graphs and irregular multidimensional situations.Journal of the Royal Statistical Society,2009,71(1): 97–125.[doi: 10.1111/rssb.2008.71.issue-1]

2Shuman DI,Narang SK,Frossard P,et al.The emerging field of signal processing on graphs: Extending highdimensional data analysis to networks and other irregular domains.IEEE Signal Processing Magazine,2013,30(3):83–98.[doi: 10.1109/MSP.2012.2235192]

3Narang SK,Gadde A,Ortega A.Signal processing techniques for interpolation of graph structured data.Proceedings of 2013 IEEE International Conference on Acoustics,Speech and Signal Processing.Vancouver,BC,Canada.2013.5445–5449.

4Hammond DK,Vandergheynst P,Gribonval R.Wavelets on graphs via spectral graph theory.Applied and Computational Harmonic Analysis,2011,30(2): 129 –150.[doi: 10.1016/j.acha.2010.04.005]

5Narang SK,Ortega A.Downsampling graphs using spectral theory.Proceedings of 2011 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP).Prague,Czech Republic.2011.4208–4211.

6Narang SK,Chao YH,Ortega A.Critically sampled graphbased wavelet transforms for image coding.Proceedings of 2013 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference.Kaohsiung,China.2013.1–4.

7Sakiyama A,Tanaka Y.Edge-aware image graph expansion methods for oversampled graph Laplacian matrix.Proceedings of 2014 IEEE International Conference on Image Processing (ICIP).Paris,France.2014.2958–2962.

8Sandryhaila A,Moura JMF.Discrete signal processing on graphs: Graph fourier transform.Proceedings of 2013 IEEE International Conference on Acoustics,Speech and Signal Processing.Vancouver,BC,Canada.2013.6167–6170.

9Sakiyama A,Watanabe K,Tanaka Y.Spectral graph wavelets and filter banks with low approximation error.IEEE Transactions on Signal and Information Processing over Networks,2016,2(3): 230–245.[doi: 10.1109/TSIPN.2016.2581303]

10Pearlman WA,Islam A,Nagaraj N,et al.Efficient,lowcomplexity image coding with a set-partitioning embedded block coder.IEEE Transactions on Circuits and Systems for Video Technology,2004,14(11): 1219–1235.[doi: 10.1109/TCSVT.2004.835150]

11张红萍.SPECK图像编码算法的研究与改进[硕士学位论文].西安: 西安电子科技大学,2008.

12陈思佳.一种改进的嵌入式小波图像编码算法.现代计算机,2013,(8): 20–24.

13佟雨兵,张其善,祁云平.基于PSNR与SSIM联合的图像质量评价模型.中国图象图形学报 ,2006,11(12):1758–1763.[doi: 10.11834/jig.2006012307]