一种基于小波零树编码和K—mean聚类的图像压缩的实现

陈慧++龙飞++段智云

摘要：针对在低比特率时图像存在严重的方块效应等不足，本文提出了一种基于小波零树编码和K-mean聚类的图像压缩算法。其中基于小波零树的图像编码克服了图像JPEG标准压缩算法在统计值较少时的方块效应现象，通过K-mean聚类算法可以改善小波零树编码算法中没有充分考虑到小波系数同一子带中相邻元素之间相关性的缺陷。实验结果表明，此改进的图像编码算法具有较好的信噪比和压缩比。

关键词：图像编码；小波变换；K-mean聚类

中图分类号：TN919.81

文献标识码：A

DOI： 10.3969/j.issn.1003-6970.2016.02.008

引言

目前为止，JPEG标准在中高码率对于静止的图像取得了较好的压缩性能，并且具有压缩效率高和图像质量损失少的优点，但自身也存在局限性。比如，图像在低比特率时，重构图像存在严重的方块效应，不能很好地适应网络传输中传描图像的需要；JPEG的压缩比普遍不高，一般小于50%；基于DCT变换的JPEG标准压缩算法，如果图像的重要信息集中在相对窄小的频段，DCT变换能得到较好的结果，然而如果图像的细节是非平稳的，需要较宽的频带来表示，即需要许多变换系数的表述。基于小波零树编码和K-mean聚类的图像压缩算法，国内外学者已经进行了深入而广泛的探讨与研究。张琦在论文中提到了基于小波变换的图像压缩技术，但复原之后的图像有明显的方块效应；柳斌等将基于零树量化的小波编码用于图像压缩中，但是图像细节描述时间长，算法复杂度较高；吴青等手巴基于层次聚类的方法用于图像压缩算法的优化中，虽然可以实现时间优化，但也存在压缩率低的缺点。

本文采用小波系数变换的图像编码，既可以克服了JPEG标准压缩算法在低比特率下严重的方块效应，又可以通过K-mean聚类算法改善小波零树编码算法中没有充分考虑到小波系数同一子带中相邻元素之间相关性的缺陷，因此，在图像压缩的应用中有一定的价值和前景。

1 基于小波零树编码和K-mean聚类的图像压缩算法

l.l 小波变换的零树编码

小波零树编码用于图像压缩是小波分析应用的一个重要方面，它的特点是压缩比高，压缩速度快，压缩后能保持信号与图像的特征不变，且在传递中可以抗干扰。本文采用嵌入式小波变换（EZW），它是以相对适中的复杂度等级产生达到最新技术发展水平的压缩性能。

通过扫描小波变换后生成二进制树结构子带的零树来进行编码，每一棵零树的形成需要对图像进行2次扫描。在生成第1棵零树时，首先找出变换后图像的最大绝对值系数，用它的一半作为初始阈值，对图像进行第1次扫描，将变换图像中绝对值小于阈值的系数看作0，在按照零树符号的定义形成零树；在第2次扫描中，对那些绝对值大于阈值的节点按其绝对值是否超过阈值的2.5倍附加一个比特l或0来描述其精度。然后将阈值减半再经2次扫描生成第2棵零树，在第1次扫描生成零树时，以前已经大于阈值的节点不再考虑，而第2次扫描附加比特时则要考虑以前非零的节点以继续求精，如此往复下去，不断生成零树编码直到达到需要为止。

1.2 K-mean聚类算法

K-me an聚类最早是由Mac Queer所提出来的，是以最小化适应函数作为判断准则将所要分类的数据依次划分到事先设定的类中。K均值聚类算法是采用多次迭代的反复循环过程的聚类算法，算法结束的标志是迭代结束，换句话说也就是聚类间的数据元素不会再一次被调整。K-mean聚类算法实现的一般步骤如下：

步骤一：将所要聚类的样本数据量{Zii=l，2…n}聚成k类，则需要随机产生聚类中心作为初始化类中心

步骤四：如果J不变或代表点未发生变化则算法结束，否则程序转向步骤二。

2 基于小波零树编码和K-mean聚类的图像压缩算法的实现

基于小波零树编码和K-mean聚类算法的图像压缩，可获得更高的压缩效率，且其计算复杂度低，其具体步骤如下：

第一步：对输入的图像进行小波变换，分别低频小波子带系数和高频子带系数；

第二步：将具有相同属性的图像小波变换后的低频系数组织起来进行描述，利用K-mean聚类算法分类低频的小波子带系数，划分成K类，对聚类后的低频系数做移位预处理；

第三步：图像中每个低频小波系数按照所属的类中心，进行小波零树编码；

第四步：对图像中其余的高频小波系数进行小波零树编码。

3 实验结果

实验采用的图像是标准测试库图像，在处理器为Intel Core 2，主频1.26GHz的计算机上，通过MATLAB7.0对算法进行仿真，本文采用最优线性算法、JPEG算法和本文基于小波零树编码和K-mean聚类的图像压缩算法对Lena（256x256）图像进行实验并进行比较，计算峰值信噪比PSNR，表达式如下所示。

设f（i，i）表示原图像的第i列j行的像素值，f（i，j）表示插值后图像的第i列i行的像素值，M为图像的高，N为图像的宽。

同时选择Borb、Boat和Lena图像在相同的信噪比PSNR=20时进行压缩比的比较。

本文算法克服了JPEG标准压缩算法存在的方块效应，其中，K代表的是K-mean聚类算法选取的类别数。表1给出了最优线性算法、JPEG标准压缩算法和本文算法在聚类类别数为K=50、100下的MSE和PSNR。从表1中可以看出，本文算法两个指标均优于JPEG算法，随着聚类类别数K的增大，效果会更好；本文算法比最优线性和JPEG算法有更好的均方误差和信噪比。表2给出，了相同PSNR条件下的压缩比，即具有相同图像质量条件下的压缩比，从表2中看出，本文算法能够在保证图像质量一致的条件下，获得比JPEG标准算法更大的压缩比；相同信噪比下三幅图像的压缩比随着K-mean聚类算法的类数增加有所增加。

4 结论

本文提出了一种通过小波零树编码和K-mean聚类算法的图像压缩算法，在客观评价方面得到了较好的结果，通过小波系数分成高频和低频信息，分别采用不同的方法进行量化编码，取得了理想的效果，有一定的使用价值。本文通过采用小波域系数的零树编码算法，克服了JPEG标准压缩算法在低比特率下严重的方块效应，通过K-mean聚类算法，克服了嵌入式零树编码算法没有充分考虑到图像小波系数同一子带中相邻元素之间相关性的缺陷。本文算法的输出码可进一步利用熵编码提高压缩比，或通过码率分配进一步提高压缩性能。另外，如何结合实际应用，更好地选择聚类参数K值，亦可作为下一步研究的一个重点，尝试使用不同的聚类方法加以改进也是研究的难点。