基于小波与分形理论的图像压缩编码算法

张爱华,何雨虹,张 璟

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

基于小波与分形理论的图像压缩编码算法

张爱华,何雨虹,张 璟

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

在分形图像编码中,影响分形图像编解码速度的主要因素是从大量码本中搜索R码本块的最佳匹配码本块。如果能够使用一种方式尽可能缩短匹配块的搜索范围,那么编码的时间就可以大大减少。然而，在提高编解码速度的同时，重构图像的质量却有所降低。针对上述这些问题，在定义一种图像子块的新特征—欧氏比基础上，将小波变换与分形编码有机结合,提出了一种基于小波与分形理论的图像压缩编码算法。该算法将全局搜索码本块转化为局部搜索码本块,缩短了编解码的时间,同时利用连续小波变换的平滑特性,进一步提高了重构图像质量。仿真实验结果表明，与特征算法中的梯度算法相比，所提出的算法不仅缩短了图像编解码的时间,还提高了重构图像的质量。

分形图像编码；小波变换；欧氏比；子块特征

0 引 言

随着图像存储与传输量的增大,图像压缩编码技术[1]受到广泛关注，而这一技术得到迅速发展却是近年来发生的事情。20世纪60年代末，在美国举行的“图像编码会议”宣告图像编码正式成为一门学科[2]。在此基础上,提出了许多新的算法与改进图像压缩算法。图像压缩编码技术从总体上来说就是利用图像数据固有的冗余性和相关性，将一个大的数据文件转成较小的同性质的文件,从而更加有效地存储和传输数据。1975年，图像压缩技术的主要成果体现在变换编码技术。1979年后，小波变换理论[3-5]以及分形理论的建立，为图像压缩编码提供了理论基础，同时使得图像压缩编码能够取得更高的比特率，并向着信噪比更高的方向发展。

Jacquin提出的方案让分形压缩编码的发展进入了新的高度，并成为目前编码研究的热点。针对分形图像压缩算法存在的问题，目前大致从以下几个方向展开:提高分形的编码解码速率;提高分形的编码PSNR值;分形压缩编码方法与其他方法相结合的新的压缩算法[6];开发能将图像精确分割的有效方法，如利用小波来帮助图像分割，是分形图像中的一个热门话题，也使得小波图像压缩成为当前最有发展前途的压缩方法之一。目前，对小波系数编码的问题是小波图像压缩研究的主要问题之一[7]。此外,小波变换与其他压缩方法相结合,如小波与分形相结合的图像压缩方法就是当前的一个研究热点。几乎每一种编码方法都有自己的优势，如果能利用这些优势，将图像压缩算法进行合理重组，或许能取得意想不到的效果。大多文献采用两种编码混合算法[8-9],而文中尝试将子块特征，分形以及小波三者结合进行编码。

小波变换能很好地分解图像，其本身虽然并不具有压缩功能，但对于图像信号的处理有着独特的优良特性。它把图像信号分解为具有不同尺度和空间选择性的一系列子空间信号，并可以由这些信号重构图像。基本的分形编码具有高压缩比，但是压缩过程的编码解码的速度和重构图像的质量都严重影响了分形图像编码的效果。连续小波变换具有一定的平滑性，对编码图像先进行小波变换能有效提高重构图像的质量。小波分解的低频信息保持了图像的主要能量，高频部分涵盖的信息较少，如果对低频部分利用“欧氏比”特征对图像码本进行匹配[10-11]，或许能取得较优的效果。实验结果表明，这样的混合编码，不仅能提高重构图像的质量，还能有效缩短编解码的时间。

1 理论基础

1.1 小波变换

定义1：所谓小波变换,即存在于一个较小区域的波，其数学定义为：设φ(t)为一平方可积函数,即φ(t)∈L2(R),若其变换φ(w)满足条件[6]:

则称φ(t)为一个基本小波或小波母函数。

定义2：将小波母函数进行伸缩或平移,设其尺度因子为a,平移因子为τ,并记平移伸缩后的函数为:

并称φa,τ(t)是参数a和τ的小波基函数。由于a和τ均取连续变换的值,因此又称为连续小波基函数,它们是由同一母函数φ(t)经伸缩和平移后得到的一组函数系列。对于二维图像信号,分别在水平和垂直方向进行滤波，实现二维小波多分辨率分解。原始信号f(x,y)通过一级小波分解被分成4个子带,即一个逼近信号LL和三个细节信号LH,HL,HH。其中，LL是低频分量,蕴含图像的主要能量；LH,HL,HH是高频分量,给出的是图像信号的细节与差别。

为了更加清楚地说明图形经过小波分解后,各个方向系数矩阵所代表的信息的不同特点,分别给出Lena图像经过一级小波分解的LL,LH,HL,HH方向的系数矩阵图像。从这四幅图像不难看出，水平、垂直方向都为低频的LL部分,集中了原始图像的主要能量,其他三个方向,即高频部分，显示了图像边缘、轮廓的纹理特征[12-14],如图1所示。

图1 一级小波分解各方向系数矩阵图

1.2 基本分形编码

然后记录D块的位置，变换类型w，s和o的值。

1.3 欧氏比特征

定义一种子块匹配特征。将每一图像子块R与D均分为四个部分(见图2)，求出各部分的灰度均值，根据它们的空间位置，令其对角线两元素之差组成矢量叉乘向量：

由上述方法分别求得子块R与父块D的子块矢量叉乘向量r，d。

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

设子块R=(r)，记

1.4 算法理论依据

首先给出一个简单结果：给定R,D∈Rn×n，以及最小值问题[19-20]:

显然,‖R-s·D-o·I‖2是s、o的二次多项式，分别对s、o求偏导，并令导数为零，求解关于s、o的线性方程组，得到问题的解为：

在分形编码中，每个C块由其最佳匹配块D∈Ω的灰度变换来近似，即R≈s·D+o·I。

下面给出特征C(R)的可行性分析。

R≈s·D+o·I

Rin=s·Djn+o·I(n=1,2,3,4)

r=s·d，ri=s·di

显然有：

因此得：

C(R)≈C(D)

2 算法分析

(1)设定阈值t,确保在与R块的欧氏比相差最小的Dm块的t邻域内寻找到最佳的匹配码块D。

(2)设定一个误差阈值H,确保这种误差不至太大,从而让解码图像质量得到保证。

首先要在预设邻域N(Dm,t)内寻找局部的匹配码块,若H小,则局部匹配块就可以作为最佳匹配块；否则的话,按照步长L来扩大邻域的搜索区域,继续进行搜索,直到搜索到邻域扩大为整个码本时停止。

3 算法实现

基于上述分析并结合小波变换,文中算法步骤可归纳如下:

Step1：对灰度图像进行小波分解,量化,提取低频系数矩阵图,并调整其尺度得到低频系数矩阵图。

Step2：图像的分割与码本的构成。把低频图像分割成不重叠的B×B块(记为R),同时,以横纵方向步长均为x的像素形成大小为2B×2B的D块池。对于其中每个D块,采用4-邻域像素值平均得到B×B块,而由这些子块构成的集合称为码本Ω。

Step3：参数的初始化。设定R子块的标准差阈值大小为y1,码块标准差阈值大小为η,误差阈值大小为H,初始邻域半径大小为t和扩域步长大小为L。

Step5：对于子块R:

(2)如果σR≥y1,对于每个给定的R子块,计算出C(R)的值,并用二分法在已排序的可行码本中搜索与C(R)的值相差最小的一个D块,并将其记作Dm。

Step6：搜索最佳的匹配块。

(1)令误差阈值为H。

(2)设临时变量为t,并初始化其值,令t=k。

(3)在Dm的t邻域范围内搜索最佳匹配块D,若E(R,D)

(4)否则,t=t+L,转步骤(3)。

Step7：记录下R的最佳匹配块D的位置,s,o的值和变换的类型。

Step8：对其余的子块R,重复进行步骤(4)～(6)。

4 实验结果及分析

用Matlab7.0对尺寸为512*512的Lena图像进行实验[24],用峰值信噪比(PSNR)以及编码时间作为评价算法性能的指标,其中t是搜索邻域的半径,并取D块的标准差阈值η的大小为1 225,R块标准差阈值y1的大小为1。将得到的实验结果分别与基本分形算法、特征算法中具有代表性的相对梯度算法进行比较,结果如图3～5以及表1所示(其中t=3)。

图3 原图

图4 文中算法结果

图5 相对梯度算法结果

表1 算法对比结果

对上面的实验数据进行分析可得,与基本分形算法相比,文中算法在保证一定重构图像质量的前提下,大大缩短了编解码的时间,与相对梯度算法相比,文中算法不仅提高了编解码的速度,而且改善了重构图像的质量。

5 结束语

由于基本分形编码的时间较长,定义一种子块新特征,以缩短编解码的时间,但同时也影响了重构图像的质量。为了在进一步缩短编解码时间的同时改善重构图像质量，提出了一种基于小波与分形理论的图像压缩编码算法。实验结果表明，相对于基本分形算法以及一些同类特征算法,提出算法的仿真效果更优,应用前景也更加广阔。今后，可尝试多种编码结合的混合编码算法，进一步加强改善重构图像质量的研究。

[1] 杨延宁.图像压缩编码技术[J].有线电视技术,2003,10(21):38-40.

[2] 刘 勍,张在峰,马义德,等.基于分形理论的图像压缩编码技术[J].信息与电子工程,2004,2(4):246-251.

[3] 尹显东,唐 丹,邓 君,等.图像小波变换的分形编码技术[J].信息与电子工程,2003,1(3):23-27.

[4] Li J,Kuo C C J.Image compression with a hybrid wavelet-fractal coder[J].IEEE Transactions on Image Processing,1999,8(6):868-874.

[5] 陈明夫.基于区域检测的小波分形图像压缩方法[D].哈尔滨：哈尔滨理工大学,2013.

[6] Davis G M.A wavelet-based analysis of fractal image compression[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,1998,7(2):141-154.

[7] 杜广环.基于小波分析的图像压缩算法应用[D].大连：大连理工大学,2008.

[8] 向 辉.基于小波理论的图像压缩算法研究[D].上海:华东师范大学,2005.

[9] 郝俊瑞,许红军.基于分类的小波-分形混合编码[J].无线电工程,2001(z1):85-88.

[10] 张爱华,盛 飞,杨 培,等.基于相似比的快速分形编码算法[J].计算机技术与发展,2012,22(11):176-178.

[11] Zhang Y,Zhai G.Wavelet-based fractal image compression[C]//Third international symposium on multispectral image processing and pattern recognition.[s.l.]:International Society for Optics and Photonics,2003:396-399.

[12] 黄 晋.混合小波-分形图像压缩方法的研究与实现[D].贵阳:贵州大学,2007.

[13] Barnsley M,Vince A.Fractal tilings from iterated function systems[J].Discrete & Computational Geometry,2014,51(3):729-752.

[14] Davoine F,Robert G,Chassery J M.How to improve pixel-based fractal image coding with adaptive partitions[M]//Fractals in engineering.London:Springer,2001:292-306.

[15] Barnsley M F,Hurd L P.Fractal image compression[M].Wellesley:AK Peters,1992.

[16] Wohlberg B,Jager G.A review of the fractal image coding literature[J].IEEE Transactions on Image Processing,1999,8(12):1716-1729.

[17] Jacobs E W,Fisher Y,Boss R D.Image compression:a study of the iterated transform method[J].Signal Processing,1992,29(3):251-263.

[18] Fisher Y.Fractal image compress:theory and application[M].New York:Spring-Verlag,1995:49-51.

[19] 庄振静,何传江,申小娜.基于规范块半范数的快速分形编码算法[J].计算机工程与应用,2010,46(2):170-173.

[20] 徐 庆,刘 弘,吴晓燕.基于2-范数匹配的分形图像编码改进算法[J].计算机工程,2010,36(4):205-206.

[21] 李高平.分形几何及其在图像压缩编码中的应用研究[D].重庆:重庆大学,2005.

[22] Shi Yipen,Gu Wei,Zhang Liming.Some new methods to fractal image compression[J].Communication in Nonliner Science & Numerical Simulation,1997,13(2):80-85.

[23] Polvere M,Nappi M.Speedup in fractal image coding:comparison of methods[J].IEEE Transactions on Image Processing,2000,9(6):1002-1009.

[24] 黄小虎,胡 清,黄 杰.基于MATLAB的分形仿真研究[J].电脑知识与技术,2007(5):847-849.

Image Compression Coding Algorithm Based on Wavelet and Fractal Theory

ZHANG Ai-hua,HE Yu-hong,ZHANG Jing

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

In fractal image coding,it is the main factor that affects the decoding speed to search the best D sub block of the R sub block from a large number of code-book.However,the time of encode-decode would be significantly reduced if the search range of blocks could be cut down as much as possible.It is the problem that while the speed of encoding being improved the quality of reconstructed image would be getting worse.Aiming at above problems,after a new feature of the image sub-blocks,Euclidean ratio,has been defined,a fractal coding algorithm integrated wavelet transform with fractal encoding has been proposed,which converts the global search code-book to the local search code-book for having shortened the decoding time and employs the smooth property of continuous wavelet transform for improvement of the reconstructed image quality.The simulation results show that the proposed algorithm has not only decreased encode-decode time but also promoted the reconstructed image quality compared with the relative gradients algorithm of the characteristic algorithm.

fractal image coding;wavelet transform;Euclidean ratio;sub block feature

2016-03-04

2016-07-13 网络出版时间：2017-04-28

国家自然科学基金面上项目(11471114，61372125)；江苏省自然科学基金项目(BK20150867)；南京邮电大学攀登计划一项(NY210018)

张爱华(1969-),女,博士,教授,研究方向为非线性分析及应用；何雨虹(1988-),女,硕士,研究方向为分形图像压缩算法改进。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.008.html

TN919.81

A

1673-629X(2017)06-0046-05

10.3969/j.issn.1673-629X.2017.06.010