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

马 俐，赵红东，Hafiz Shehzad Ahmed，彭晓灿，韩铁成

(河北工业大学 电子信息工程学院，天津 300401)

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

马 俐，赵红东，Hafiz Shehzad Ahmed，彭晓灿，韩铁成

(河北工业大学 电子信息工程学院，天津 300401)

遥感图像在环境监测、军事侦察等多方面有着广泛应用，然而遥感图像包含信息量大，对其进行压缩来提高存储效率具有重要意义。传统分形编码由于压缩比大的特点被广泛应用到遥感图像压缩中，但是传统分形编码存在压缩时间太长的问题。提出提升小波变换与改进分形结合的压缩方法，把提升小波变换后的低频分量进行基于最小方差搜索法的分形压缩。实验结果表明，提升小波变换与改进的分形结合的压缩方法与小波变换与分形结合的压缩方法相比，在峰值信噪比保持在35 dB不变的情况下，压缩时间大约可以缩短8倍，图像压缩比也有提高。

提升小波变换；遥感图像；分形编码

近年来，遥感技术成为现代科学技术的重要组成部分，遥感图像包含的信息量很大，对信道的传输提出更高的要求，有限的信道容量和传输海量遥感数据的需求之间的矛盾日益突出，对传输的遥感数据进行压缩具有非常重要的价值和意义。目前，图像压缩处理的方法有很多种，但是由于遥感图像包含数据量太大，一些典型的压缩技术并不能得到满意的效果[1-5]。而分形压缩技术利用局部和整体的自相似性去除冗余信息可以获得几十到几百倍的压缩比。但是传统的分形算法的缺点是运算时间较长、产生“块效应”，人们想到在变换域进行压缩，文献的实验结果表明在变换域进行分形压缩的性能优于空间域[1,3,6]。小波变换具有能量集中、计算简单、对边缘信息处理强、能消除“块效应”的优点[1]。因此，人们开始对小波变换和分形结合的方法进行研究。

在传统的分形压缩编码中，值域块的搜索占用大部分的编码时间。最早人们主要研究如何通过改变值域块的搜索方式来缩短压缩时间。Zhu Lei[7]等人提出遥感图像的分形压缩算法，采用四叉树搜索的方法，在保证图像重构质量不下降的情况下，压缩时间缩短了不到1 s。赵坚[4]等人提出基于小波变换的快速分形图像编码，该方法与传统的分形压缩编码相比，缩短了编码时间。宋凭[6]等人根据小波变换后系数能量分布特性，提出提升小波变换与分形相结合的图像压缩算法，经过提升小波变换后的低频部分采用改进的分形图像编码，该方法提高了压缩效率。Yuen C.Y.[8]等人提出四叉树渐进式结构的非搜索分形压缩算法，该算法提高了图像恢复质量，但是压缩时间没有缩短。娄莉[9]等人提出基于分形的图像编码改进算法，对小波分解后的高层子图进行基本分形编码，该方法与传统的分形压缩编码比，压缩时间缩短约80%。李会[10]等人提出一种快速分形编码方法，原始图像通过被插值正交多小波分解达到缩小的效果，再利用分形编码进行压缩，该方法与传统的分形编码算法比，压缩时间缩短约75%。以上提出的压缩方法大多是与传统分形压缩编码进行比较，而且压缩时间缩短倍数不高。本文结合小波变换具有变换后能量主要集中在低频部分和小波变换时间短的特性，先将原始图像进行一次提升小波变换，然后低频分量采用改进的搜索方法进行分形编码。本文所提出的小波变换与改进的分形编码结合的压缩方法，在保证峰值信噪比基本不变的情况下，压缩时间缩短了87%以上，压缩比也得到一定提高。

1 提升小波变换与分形编码的算法理论

1.1 提升小波变换

Mallat算法是二维离散小波变换使用频率最高的方法，该算法是通过在图像的水平方向和垂直方向交替使用低通和高通滤波器实现的[6]。这种方法运算复杂度高，计算量和存储量都很大。提升小波变换能有效解决这一问题，被称为第二代小波变换。在提升小波变换过程中，双正交滤波器是在空间域形成的，不会被傅里叶变换影响。提升算法的实现流程为，现有的滤波器首先被分解成不同的模块，然后每个模块依次实现小波变换。分裂、预测、更新[6]是依次实现提升变换的步骤，如图1所示。

图1 提升小波变换示意图

分解过程为F(Sn)=(Sn-1,dn-1)，其中F(Sn)为分解过程。预测过程主要是去除分裂过程中产生的冗余。奇数序列dn-1被偶数序列Sn-1的预测值P(Sn-1)进行预测，也就是奇信号的预测值来自偶数序列被滤波器P滤波后的值。原始信号Sn被比其小的Sn-1和dn-1代替，重复n次以后，原始信号可以表示为{Sn,dn，…，S1，d1}。更新的目的是子集更好地保持原始信号的全局特性。提升小波变换的逆变换过程为反更新、反预测和合并操作。

1.2 传统分形图像编码

1.2.1 分形图像编码数学理论

定义1 迭代函数系统(IFS)是由完备度量空间(X,d)和一组有限的压缩映射ωn∶X→X及其相应的压缩因子Sn(n=1,2,…,N)组成[2]。通常迭代函数系统(IFS)表示为{X;ωn,n=1,2,…,N},压缩因子为S=max{Sn,n=1,2,…,N}。

定理1 拼贴定理：设(X,d)是完备度量空间，设定集合L∈H(x)及正数ε。选取一个IFS{X∶ωf,j=1,2,…,n}，它的压缩因子是s:0≤s≤1，使得

(1)

那么

(2)

式中：A是IFS的吸引子；s是压缩因子。

定义2 反射变换：一个变换ω：Rn→Rn如果具有如下形式

(3)

式中：a,b,c,d,e,f均为实数，则ω被称为二维仿射变换[1,11]。对于一个方块像素块，通常有8种变换方式，如表1所示。

表1 8种对称变换

变换代号矩阵含义变换代号矩阵含义01001æèçöø÷恒等变换40110æèçöø÷沿Y=X轴反射1100-1æèçöø÷沿Y轴反射501-10æèçöø÷90°旋转2-1001æèçöø÷沿X轴反射60-110æèçöø÷270°旋转3-100-1æèçöø÷180°旋转70-1-10æèçöø÷沿Y=-X轴反射

1.2.2 分形压缩的基本方法

分形编码是利用图像本身的自相似特性[12]，构造出迭代函数系统(IFS)，根据拼贴定理寻找出每个子图像的IFS码[1]。就是把一个子图像经过分形仿射变换后去逼近同一幅图像中的其他子图像，只需记录仿射变换的系数，进而完成对图像的压缩。

(4)

1.3 改进的分形图像压缩

传统分形压缩方法中，在给值域块寻找最佳匹配的定义域块时，采用的搜索方法是在全局中的每个定义域块的8种仿射变换中，通过式(4)计算每个码本和已知值域块的最小误差来找出最佳匹配块，可以得到较好的重构图像，但是它需要很长的时间[13]。如何减少搜索时间是提高编码效率的关键，也是对分形图像压缩算法改进的方法之一。本文在给值域块寻找最佳匹配的定义域块的搜索方法上进行改进，提出基于最小方差的搜索方法，把搜索方法分为2个步骤进行：

1)先计算已知值域块与每一个定义域块像素值的方差，再找出方差最小时所对应的定义域块。

(5)

式中：n代表值域块中所包含像素值的数量；ri，di分别代表值域块和定义域块中所含的像素值。

2)在找出的定义域块所对应的8种仿射变换中，根据最小二乘法和式(4)找出最佳匹配的定义域块，并记录最佳匹配参数。

1.4 小波与改进的分形编码结合的图像压缩方法

提升小波变换中利用9/7双正交小波，该小波具有对称性、光滑性好和压缩性好的优点[6]。三个高频分量和一个低频分量可以通过把原始图像进行一次9/7提升小波变换得到。原始图像的大多数信息分布在低频部分，图像的细节和边缘部分位于高频分量。对低频分量进行压缩可以进一步减少分块数量，从而缩短压缩时间。将提升小波变换后的低频分量进行改进的分形压缩算法，具体的压缩步骤如下：

1)将原始大小为256×256的图像进行小波提升变换，分解成大小为128×128的4个部分。取低频分量LL进行分形压缩算法。

2)把LL图像分解成大小为4×4的值域块(记Ri),构成R块池。相邻R块之间不重叠，所有R块构成LL图像。

3)把LL图像分解成大小为8×8的定义域块(记Di)，构成D块池。相邻D块之间可以重叠。把每个D块取4邻域像素平均值，得到4×4的像素块，再把得到的像素块进行8种仿射变换，即得到码本Ω。

4)对于每一个值域块Ri，按以下步骤在码本Ω中找出最佳匹配块tkDi(m)。

(1)给定的一个Ri，在所有Di中找到与Ri所含像素值的方差最小的Di(m)；

(2)根据式(6)、(7)计算参数si和oi(s代表对比度，o代表亮度)，在Di(m)的8个等距变换子块中，根据式(8)求出误差最小的、与已知值域块Ri最佳匹配的定义域子块tkDi(m),即

(6)

(7)

(8)

式中：n代表值域块中像素点个数；s,o分别代表对比度和亮度；ri,di代表值域块和定义域块。

5)找到每个值域块的分形码，即得到了分形编码文件。

解码步骤如下：

1)从分形编码文件中读出LL图像、R块、D块的大小。

2)对于R块中的每个Ri，根据分形编码文件中的分形码，在D中找到对应的Di，根据Ri=si·(tk(S(Di(m))))+oi·1得到所有R块后，根据拼贴定理得到第一次迭代图像。

3)通常情况下，迭代8～10次后，图像不再会有明显变化，此时得到了重构图像。

4)对所得重构图像结合三个高频分量进行提升小波逆变换得到解压缩后的原始图像。

2 实验分析与结论

在实验中，分别选用张家口市阳原县的3幅遥感图像进行测试。所用图像是10 m空间分辨率的多光谱数据(MUS影像)，波谱范围分别为0.52～0.59 μm(band2)，0.63～0.69 μm(band3)，0.77～0.89 μm(band4)；对每幅图像分别采用提升小波变换与分形结合的方法和提升小波变换与改进的分形结合的方法进行测验，采用MATLAB7.0在内存为4 Gbyte的计算机上运行程序，所使用图像大小为256×256，得到的结果如图2～4、表2～4所示。

图2 实验运行图像(图像1)

图3 实验运行图像(图像2)

图4 实验运行图像(图像3)

方法运行时间/s压缩比峰值信噪比/dB小波与分形结合118.109163.0237.101小波与改进分形结合14.366184.2337.031

表3 实验图像2的计算机运行结果

方法运行时间/s压缩比峰值信噪比/dB小波与分形结合115.844106.1036.106小波与改进分形结合12.249115.8735.918

表4 实验图像3的计算机运行结果

方法运行时间/s压缩比峰值信噪比/dB小波与分形结合118.375186.5341.114小波与改进分形结合14.250193.9941.078

由表2、表3、表4得到的结果看出，本文提出的提升小波变换与改进的分形结合的压缩算法重构的图像质量变化不大。通过对改进方法前后的压缩时间进行分析，由图5得出，在保证图像压缩前后峰值信噪比基本保持不变的情况下，本文改进的算法比传统的小波变换与分形结合的压缩方法的运行时间减少了87.5%，压缩比也有所增加，具有一定的使用价值。

图5 所用实验图像经过改进压缩方法前后所用时间比

[1] 王惠溧，邹峰嵘．基于四邻域的分形遥感图像压缩[D]．长沙：中南大学，2012.

[2] 张豆豆．几种改进的快速分形图像压缩算法[D]．大连：大连理工大学，2015.

[3] 郑秋梅, 赵敏, 王风华,等. 基于不规则区域分割及灰度排序分类的分形压缩算法[J]. 中国石油大学学报(自然科学版), 2014, 38(3):169-173.

[4] 赵坚, 俞斯乐. 基于小波变换的快速分形图像编码[J]. 通信学报, 1999, 20(3):85-87.

[5] DU S L,YAN Y P,MA Y D．Quantum-accelerated fractal image compression: an interdisciplinary approach[J]．IEEE ieee signal processing letters ,2014,22(4): 499-503.

[6] 宋凭, 刘波, 曹剑中,等. 提升小波变换与分形相结合的图像压缩[J]. 光子学报, 2006, 35(11):1784-1787.

[7] ZHU L, YANG J. Fast multi-spectral image coding algorithm based on fractal[C]//Proc. International Symposium on Intelligence Information Processing and Trusted Computing. [S.l.]：IEEE, 2010:446-449.

[8] YUEN C H, LUI O Y, WONG K W. Hybrid fractal image coding with quadtree-based progressive structure[J]. Journal of visual communication & image representation, 2013, 24(8):1328-1341.

[9] 娄莉, 刘天时. 一种基于分形的图像编码改进算法[J]. 微计算机信息, 2010, 26(11):206-208.

[10] 李会, 房汉雄, 朱恒军. 基于正交多小波变换的快速分形图像编码[J]. 齐齐哈尔大学学报(自然科学版), 2011, 27(1):1-6.

[11] MEKHALFA F, AVANAKI M R, BERKANI D. A Lossless hybrid wavelet-fractal compression for welding radiographic images[J]. Journal of X-ray science and technology, 2016(8):610-625.

[12] 俞玉莲. 一种改进的分形图像压缩算法[J]. 信息技术,2015(6):55-57.

[13] WANG X Y, ZHANG D D, WEI N. Fractal image coding algorithm using particle swarm optimization and hybrid quadtree partition scheme[J]. IET image processing, 2015, 9(2):153-161.

[14] WU M S. Genetic algorithm based on discrete wavelet transformation for fractal image compression[J]. Journal of visual communication & image representation, 2014, 25(8):1835-1841.

责任编辑：薛 京

Image compression algorithm based on combination of lifting wavelet transform and fractal

MA Li, ZHAO Hongdong, Hafiz Shehzad Ahmed, PENG Xiaocan, HAN Tiecheng

(ElectronicandInformationEngineering,HebeiUniversityofTechnology,Tianjin300401，China)

Remote sensing image is widely applied in environmental monitoring, military reconnaissance and other aspects. However, remote sensing images contain a large amount of information, it is important to improve storage efficiency. Traditional fractal coding has been widely applied to the remote sensing image compression due to the high compression ratio. But the compression time of the traditional fractal coding is too long. A compression method based on the combination of lifting wavelet transform and the fractal is proposed in this paper, making the best of the coefficients distribution, the algorithm is consisted of improved fractal coding in low-frequency of lifting wavelet transform coefficients. Experimental results show that the compression time can be shorted about 8 times, and the compression ratio is improved compared with the former unimproved method based on the peak signal to noise ratio(PSNR) is maintained at 35 dB unchanged.

lifting wavelet transform; remote sensing image; fractal coding

马俐，赵红东，Hafiz Shehzad Ahmed，等.提升小波变换与分形结合的图像压缩算法[J]. 电视技术，2017,41(2)：11-15. MA L, ZHAO H D, AHMED H S , et al.Image compression algorithm based on combination of lifting wavelet transform and fractal[J]. Video engineering，2017,41(2)：11-15.

TN919.81

A

10.16280/j.videoe.2017.02.003

河北省自然科学基金项目(F2013202256)

2016-05-20