基于小波变换与分形结合的图像压缩算法

2018-09-22汪玮玮张爱华

计算机技术与发展 2018年9期

汪玮玮，张爱华

(南京邮电大学理学院，江苏南京 210046)

0 引言

将分形理论[1]用在图像压缩上之所以有作用，是因为根据此理论，从计算的角度很多复杂的图像信息含量很少，可以通过简单的算法迭代出来。比如自然界中的蕨类植物图像，看起来比较复杂，如果用一般图形表示法需要上万个数据，但是如果采用分形理论方法，只需要24个数据，建立迭代函数系统就可以在计算机上产生这类图像。因此，通过迭代函数系统，利用参数不多的算法可以将相当复杂的自然图像显示在计算机上，也就是说，通过简单的算法就可以控制复杂图像，这是分形理论在图像压缩领域应用的主要根据之一[2-7]。此外，分形意味着自然界是许多复杂形态中潜藏着有组织的结构，如果能在这些复杂的形态中提取出关键的有效信息，很容易就可以将自然界的复杂图像进行清晰的展现，这是分形理论在图像压缩领域应用的另一个重要依据[8-11]。当今，众多学者研究此类问题的关键指向了如何在保证图像质量的前提下加快分形编码的速度[12]。

小波变换理论在图像压缩处理领域的应用也非常广泛[13-16]。众所周知，一幅图像经过小波变换处理后，总数据量既没有增加也没有减少，由于一幅图像的低频区域包含主要信息，而一些其他的细节信息保存在高频区域。因此不难想到一种简单的图像压缩方法就是将图像高频区域部分的信息去除，而保存低频区域部分的信息。这种方法虽然简单，但是在图像压缩后没有了细节信息，影响效果。因此文中提出一种结合小波变换和分形特征的方法。由于图像经过小波变换后，其自相似性被破坏，在引入分形特征时，对于低频区域图像信息不再进行分形压缩，直接保存处理；在高频区域则利用提出的相似比特征，进行分形编码压缩。

1 算法的理论基础

1.1 小波变换的定义

1.2 小波变换压缩方法

考虑到二维尺度函数式可分离，也就是φ(x,y)=φ(x)φ(y)，其中φ(x)是一个尺度函数。二维尺度函数的伸缩和平移变换记为φj,m,n(x,y)=2jφ(x-2jm,y-2jn)，其中j,m,n是整数。简单概括一下，小波变换压缩方法的过程是从一幅2N×2N原始图像f1(x,y)开始，在每一次变换中，利用一个小波基图像与原始图像做内积运算，然后与x和y坐标上每隔两个点取出一个点抽样而生成，这样每次变换可以分解成四个1/4大小的、分辨率不同的子图像。

利用小波变换分解图像，分解后图像的总数据信息量没有发生变化，但是图像中的数据信息发生了转移，分解之后的一系列子图像，它们的分辨率都不相同。子图像的分辨率与频率呈正比，其中高频率的子图像上的数据信息比较少，大部分数值接近于零。所以一幅图像的低频区域包含主要信息，而一些其他的细节信息保存在高频区域，因此提出一种将小波变换和分形特征相结合的方法。

2 基于子块特征的快速分形编码方法

根据基本分形编码算法的公式知，码本池Ω容量的大小决定了编码过程中所耗费的时间。如果能够通过定义图像子块的特征，将全局搜索转变为该特征下的近邻搜索，这样就缩减了匹配搜索的空间，即能减少编码过程中的时间消耗。

在基本分形编码算法中，为了寻求R块的最佳匹配块，需要求解下面的极小化问题：

(1)

其中，m表示R块的最佳匹配块序号；I∈Rn×n表示所有元素均为1的常值块；R=(r1,…,rk,…,rN)，D=(d1,…,dk,…,dN)分别表示R块、D块像素点灰度值按某种方式向量化后的向量。

每个待编码的R块通过自仿射变换ω在码本池Ω中寻找均方根误差最小的D块作为其最佳匹配块，即：

R≈ω(D)=s·D+o·I

(2)

用最小二乘法求得极小化问题的解为：

(3)

此时，匹配的误差就为：

(4)

将式3中的ο代入式2有：

(5)

若将与R块、D块相同位置的小块R1和D1取出来，那它们也应该满足：

(6)

将式5、6两边同时做比值，得到：

(7)

由此可以看出，如果R块和D块能够匹配成对，那么它们的自相似比也应当比较接近。

下面给出了图像子块的一种新特征定义，并对该特征与匹配误差之间的关系进行了说明。

首先将每一幅图像的子块R与D平均分成四个部分(见图1)，再分别求出每个部分的灰度均值。根据它们的空间位置，令其对角线两元素之差组成叉乘向量：

图1 D块(左)和R块(右)

下面给出相似比特征φ(D)的可行性分析：

R≈s·D+ο·I

所以，φ(R)≈φ(D)。

3 小波与分形相结合的图像压缩方法

为了实现图像处理的批量化，将小波变换与分形特征相结合，先利用小波变换对图像进行压缩处理，再将分形特征算法引入进来，将这两种方法叠加进行处理。

首先，将待压缩的图像处理成一幅二维数字图像，对其分别进行垂直和水平方向的小波滤波处理，从而将图像分成四个离散的子带。四个子带分别是：垂直和水平方向的低频子带LL1(它能够反映原图像的基本特性)、水平方向的低频和垂直方向的高频子带LH1、水平方向的高频和垂直方向的低频子带HL1以及水平和垂直方向的高频子带HH1。这三个子带所反映的主要是该图像在水平方向、垂直方向与对角线方向的边缘、纹理和轮廓等特征信息。图像经过小波分解后被分成低频区域和高频区域，低频区域在很小的空间内却包含了原始图像的大部分特征信息，然而高频区域往往占用很大的空间，却只散布着原始图像的小部分特征信息。所以，正是由于图像经过小波变换，其自相似性被破坏，在引入分形特征时，对于低频区域的图像信息不再进行分形压缩，直接保存处理即可；而在高频区域则利用上述提出的相似比特征，进行分形编码压缩。

4 算法实现

4.1 算法步骤

根据以上分析，文中提出的方法实现如下：

(2)进行小波变换分解后，每一个子分量会分成七个子带，将LL1量化后直接保存，对LH1、HL1、HH1、LH2、HL2、HH2再次进行分形特征的编码处理。

①将低频图像分割成大小为B×B的R块，同时，以横纵方向步长均为x的像素形成大小为2B×2B的D块池，由这些子块构成的集合称为码本Ωη={D∈Ω|σD≥η}。其中η为码块标准差阈值，y1为R块的标准差阈值。

②对于子块R：如果σR

③在Dm的t邻域内搜索最佳匹配块，如果E(R,D)

④记录下最佳匹配块D的位置、s、o的值以及变换的类型。对于剩下的子块R，重复上述步骤。

(3)对经过分形压缩编码处理后的各子带进行解码，通过迭代操作，得到各子带解码后的图像信息。

(4)对解码完成的图像进行小波反变换，最终得到压缩后的图像信息。

4.2 实验结果及分析

用MATLAB R2012b对大小为512×512的Lena图像进行实验，将图像压缩编码的时间和峰值信噪比作为评价算法性能的指标。其中取D块的标准差阈值η=1 225，R块的标准差阈值y1=1。将得到的实验结果分别与基本分形算法和小波与欧氏比特征结合的算法进行比较，结果如图2～4以及表1所示。

图2 Lena图像

图3 文中算法(t=10)

图4 小波与欧氏比特征结合算法(t=10)

迭代次数邻域参数(t)文中算法基本分形算法小波+欧氏比算法PSNR/dBTime/sPSNR/dBTime/sPSNR/dBTime/s1145.933.83339.5213.84538.9230.5223.64342.4545.8715.2443.2132.4139.63110.135148.294.13352.2514.18552.9633.5055.87355.0748.769.8950.5841.5452.6890.3110148.294.33352.2514.62552.9531.0256.04365.9848.7812.4050.6241.3652.7391.12

根据以上仿真数据分析可以知道，与基本分形理论算法相比，文中提出的方法在保证一定重构图像质量的前提下，大大缩短了图像压缩编码的时间；而与文献[10]提出的算法相比，文中方法不仅提高了图像压缩编码的速度，而且在一定程度上改善了重构图像的质量。