基于双伸缩因子映射的小波分形图像压缩编码方法惠存阳【摘要】本文基于小波变换研究了分形图像压缩系统.根据小波系数的能量分布特性,给出了新的小波树定义与分类方法,并在小波域内建立了具有双伸缩因子的压缩映射.在将新的压缩映射应用于图像编码过程时,结合小波嵌入式零树编码思想给出了新的小波分形图像压缩方法.数值实验给出了本文方法与已有方法的比较.%The paper considers the fractal image compression system based on the wavelet transform.By the energy distribution of wavelet coefficients for images, we give a new kind of classification methods for wavelet trees and establish a compression mapping with two scale factors which is used for image coding. Using the idea of the embedded image coding using zero-trees of wavelet coefficients, a new wavelet fractal image compression method is proposed. Several numerical experiments are conducted and compared with existing methods.【期刊名称】《工程数学学报》【年(卷),期】2011(028)002【总页数】7页(P150-156)【关键词】分形图像编码;伸缩因子;小波;压缩映射【作者】惠存阳【作者单位】西安文理学院数学系,西安,710065【正文语种】中文【中图分类】O184;O174.31 引言分形图像编码是基于压缩映射的一种图像编码方法，由Barnsley[1]首先提出．该方法常常能够达到较高的压缩比，优于其它编码方法．但Barnsley并未公布其具体算法．之后，他的学生Jacquin[2]基于图像分块的方式，采用逐块变换系统(PTS)，首次给出了分形图像编码的算法．但应用PTS时，需要进行大量的搜索计算，耗时较多．为此，有许多文献给予了改进，如为了减小搜索计算量而提出的固定网络搜索法、分类搜索法、四叉树搜索法以及最优搜索法等．在子块划分方面，Fisher等人[3]提出了自适应四叉树编码方法，这就是目前常用的分形图形压缩方法．进一步的工作可参见文献[4-8]．分形图像压缩方法发展的另一个重要方向是结合小波分析的编码方法研究．Davis[9]首先讨论了小波域内的分形图像编码方法，并对分形编码方法和解码收敛性进行了研究．该方法较空间域的分形编码方法有了许多改进．首先是编码时间缩短；其次通过适当的小波选择可使恢复图像质量没有方块效应，主观上图像具有较高的质量．但Davis所采用的压缩映射依赖于单伸缩因子，给匹配造成困难，常常需要分解子树，使得计算量增加．我们注意到，自然界中的图像并不是数学意义上的严格自相似图像，因而具有单伸缩因子的仿射变换在实际图像压缩中常常会产生较大的匹配误差．为了提高子树与父树的匹配精度，减小匹配搜索范围，本文根据小波性质，研究了新的小波树分类方法与双因子匹配映射．实验表明，本文所给出的双因子匹配映射能够明显的减少子树与父树的匹配误差，在给定匹配误差时有更多的子树能找到匹配父树，因而有利于提高恢复图像的质量及编码速度．2 Davis小波分形图像压缩方法2.1 小波树Davis将三个方向上的小波系数定义为一棵小波树，如图1所示．在四级小波分解时，小波树有三个根结点均位于第三层，每个根结点在较细尺度的同一方向上又有四个‘孩子’，图1中用方格状块表示所有的根结点与父结点．与空间域的子块及父块概念相对应，在小波域有子树(range subtree)与父树(domain subtree)的概念．与子树比较，父树的根结点位于尺度较粗的分解层上．如图1所示，若根结点在J=3的分解层上的小波树称为子树，而根结点在分解层J=4上的小波树称为父树．所有父树构成的集合称为父树库．图1:小波树的构造2.2 压缩映射与图像压缩思想由于小波树的特殊结构，对父树的抽样及仿射变换与空间域有所不同．在小波域中，‘平均－抽样’操作ˆA采用减少一个分辨率的办法进行，把父树的‘叶子’，即最精细尺度上的小波系数置为0，其余尺度上的小波系数移向下一个精细尺度．经过ˆA操作后，父树的大小与子树相同．小波域内的仿射变换与空间域中的8种仿射变换[2]直接对应．因而旋转及反射变换涉及到小波树的三个方向，除了对每一个方向上小波树的子块进行反射、旋转变换外，对某些变换还需要交换LH与HL方向上子块的位置，这些变换称为等距算子，记为L．小波域中的质量映射定义为：其中α称为伸缩因子，D为父树．综上所述，小波父树到子树的仿射变换可表示为小波分形图像压缩的基本思想是：对于给定的子树R，用父树来逼近子树，即寻找适当的伸缩因子、等距变换L，使达到最小．3 小波分形图像编码方法的改进3.1 小波树的分类我们知道，在对图像作小波塔型分解后，三个方向上的能量分布是不均衡的，HH 方向分布的能量最小，而LH方向与HL方向分布的能量较大．为此，我们定义每个方向上的小波系数为一棵小波树，并将小波树分为如下四类：1)零数：相对于阈值T，树上每个系数都是无效的；2)根重要树：只有根结点是有效的，而其他结点是无效的；3)可自变换树：如果它可找到满足匹配误差要求的父树；4)复杂树：除上述三类树之外的小波树．与EZW[10]的分类方法相比，本文分类方法引入了根重要树．在编码时，最低频的逼近系数量化后直接保存．小波树扫描从最低频(子带)开始按之字型进行，每一子带内的位置扫描完后进入下一子带扫描，直到最高频(子带)为止，而在每一分解层内，先扫描HL方向的根结点，再扫描LH方向的根结点，最后扫描HH方向的根结点．3.2 父树到子树的映射我们定义父树到子树的映射为如下形式的仿射变换其中n的大小取决于子树的尺寸．基于匹配误差与存储ki需要的比特数，本文考虑两个伸缩因子的情况，即前l个取同一个值，后n−l个取同一个值．记父树为D=(D1,D2)，子树为R=(R1,R2)，且R1的大小与ˆA(D1)的大小相同，则父树与子树的匹配误差为其中|·|表示欧氏距离，M=dim(R)．3.3 编码与解码过程根据上述小波树分类方法，我们结合嵌入式零树编码[8]思想给出了如下分形编码方法．假设判别小波系数是否有效的阈值为T0，匹配误差阈值Te，则具体算法如下：步骤1 对原图像作N级小波分解；步骤2 量化并保留逼近系数与最粗尺度上的小波系数；步骤3 分别构造子树库与父树库；置dep=N−1；步骤4 扫描第dep层的小波系数，记根结点为p的小波子树为Rp．若Rp是已编码的子树后辈，则不编码，按顺序考虑下一子树；否则对Rp做如下处理：1)如果Rp是零树，则记下其类别，作为编码，按顺序扫描下一子树；2)如果Rp是根重要树，则记下其类别，并保留根结点，编码完成后，再按顺序扫描下一子树；3)如果Rp是可自变换的子树，则保留父树Dp的位置，两个伸缩因子及仿射变换类型作为子树Rp的编码，再按顺序考虑下一子树；4)如果子树Rp是复杂树，则保留根结点，并将子树Rp留到下一个较高频子带进行编码．重复1)到4)操作，直至第dep层内的子树处理完为止；步骤5 如果dep=1，编码结束．否则，置dep=dep−1，转到步骤4．小波分形图像编码流程图如图2所示．解码过程如下：步骤1 任取一图像TU，将保留的逼近系数与小波系数置于左上角；步骤2 重复如下操作：1)造父树库； 2)对图像TU的相应子树按其分类进行解码；直至满足要求为止；步骤3 做小波逆变换，给出解码图像．图2:改进后的小波分形图像编码流程图4 实验结果小波基函数选为B9/7双正交小波[11]，原始图像为512×512Lena头像，灰度值量化为256级，如图3所示．在以下各实验中均作6级小波分解．4.1 编码方法的效果在实验中，当子树根结点位于J=2的分辨率层时(参看图1)，不再用父树编码子树，而是直接编码系数．父树位置与仿射变换类型用等长编码，如对第五层的子树，编码其父树的位置需要6bit，下一层需要8bit，储存每一仿射变换用3bit．对于子树的类型及保留的小波系数(先量化)用算术编码进行编码．实验结果如表1，图4所示，其中CR为压缩比，PSNR为峰值信噪比．由表1可以看出，在相同峰值信噪比的情况下，本文所给方法的压缩比要高于Davis方法．表1: 本文方法与Davis编码方法的结果比较编码方法 Bit Rate(bpp)CR PSNR(dB)本文方法 0.118 67.3:1 29.9 Davis方法 0.121 65.6:1 29.9图3:512×512Lena原始图像图4: 本文方法实验结果CR=67.3,PSNR=29.914.2 各类小波树统计我们就不同的阈值Te，统计了在一次编码中每一分辨率层内各类树的数量，结果列于表2，其中Te为匹配误差的阈值，T0为判断小波系数是否有效的阈值，J为子树根结点所在的分解层．表2: 各类树统计结果，其中J为子树根结点所在的层Lena Te=50,J=5Te=40,J=4 Te=40,J=3 总计零树Te=50 167 291 1070 1528 151 262 1031 1444根重要树Te=45 Te=5093 202 762 1057 87 179 770 1036可自变换树Te=45 Te=50172 202 220 666 192 237 299 807复杂树Te=45 Te=50336649 544 1457 Te=45338 674 596 1529由表2可见，在需要编码的子树中根重要树占有较大的比例，平均在20%左右．这说明在分类中增加根重要树的分类是合理的，因为对根重要树，不需要搜索匹配父树，对其单独编码可减少计算量，进而提高编码速度．表3给出了每一层的搜索次数(每棵子树在父树库中搜索一遍算一次)．在采用本文所给出的方法时，搜索次数明显减少，如在低层J=3时，搜索次数减少49%．表3: 搜索次数统计(阈值T0=50)，其中J为子树所在的层Lena Te=50,J=5Te=40,J=4 Te=40,J=3 总计本文方法 508 851 764 2123分形方法 601 1053 1526 3180减少搜索次数 15% 19% 49% 33%4.3 匹配映射效果实验为了验证双因子匹配映射的有效性，我们统计了分别采用双因子匹配映射与单因子匹配映射编码时，每一分辨率层内可自变换树的数量，结果列于表4．由表4可见，双因子匹配映射在较低频子带可以找到较多的可自变换树．因为根结点在较低频子带的子树包含较多的小波系数，所以使用双因子匹配映射具有明显的优势．表4: 每一子带内可自变换树数量统计，表中左边T0=50，右边T0=40LenaTe=50 J=5 Te=40 J=4 Te=40 J=3双因子匹配映射 172 192 202 237 220 299单因子匹配映射 120 140 143 184 123 1805 结论本文主要结合小波嵌入式零树编码思想研究了分形图像压缩方法，提出了新的小波树分类方法与具有双伸缩因子的匹配映射，并用数值实验验证了所给方法的有效性．进一步的工作将从理论上分析算法的复杂性，这对于匹配映射的研究具有重要意义．参考文献：【相关文献】[1]Michael F,Barnsley A D.A better way to compress images[J].BYTE,1988,13(1):215-223[2]Jacquin A.Fractal image coding based on a theory of iterated contractive image transformations[J].IEEE Transaction on Image Processing,1992,1(1):18-32[3]Jacobs E W,Fisher Y,Boss R D.Image compression:a study of the iterated transform method[J].Signal Processing,1992,29:251-263[4]Jacquin A E.Image coding based on fractal theory of iterated contractive Markov operators[R].Part 1,2,Theoretical Foundation,Report on Mathematics 91389-016,Geogia Institute of Technology,1989[5]Fisher Y,Menlove S.Fractal Coding with HV Partitions,Fractal Image Compression—Theory and Application[M].New York:Springer Verlag,1995:119-136[6]Darroine F,Bertin F,Chassery J M.An adaptive partition for fractal imagescoding[J].Fractals,1997,5:243-256[7]Distasi R,Nappi M,Riccio D.A range/domain approximation error-based approach for fractal image compression[J].IEEE Transaction on Image Processing,2006,15(1):89-97 [8]Nadernejad E,Hassanpour H,Salarian M.Improving quality of fractal compressed images[C]//International Conference on Machine Vision,2007:56-61[9]Davis G A.Wavelet-based analysis of fractal image compression[J].IEEE Transaction on Image processing,1998,7(2):141-154[10]Shapiro J M.Embedded image coding using zerotrees of wavelet coefficients[J].IEEE Transaction Signal Processing,1993,41(12):3445-3462[11]马社祥，刘贵忠，尚赵伟.基于小波变换的图形和视频压缩编码[J].工程数学学报，2001,18(小波专刊):21-25 Ma S X,Liu G Z,Shang Z W.Graphics and video image compression coding based on wavelet transform[J].Chinese Journal of EngineeringMathematics,2001,18(Wavelet Special Issue):21-25。
GPU加速的图像实时分形编码孙冬;高清维;卢一相;竺德【摘要】Fractal image encoding can provide a high compression ratio with a high reconstructed image quality, but it suffers from long encoding time, so it is difficult to promote. A new scheme based on image-fractal ( FW) encoding was proposed. Under the CUDA specification, GPU was used to search the best match parent-tree for each sub-tree parallel. Experiment results proved that the scheme could magnificently reduce encoding time to milliseconds-level with maintaining the reconstructed quality and the requirements of real-time was satisfied.%图像分形编码压缩率大且质量较高，但实时性不好，因此难以推广应用。
提出使用GPU对编码进行加速的方案。
以图像FW算法为基础，在CUDA规范下，使用GPU并行地对图像中所有的待编码子树同时进行最优父树搜索。
实验表明，该文编码方案在保持原有算法图像解码质量的情况下，可将编码时间缩短至毫秒级，满足了实时性的要求。
【期刊名称】《安徽大学学报（自然科学版）》【年(卷),期】2014(000)003【总页数】6页(P50-55)【关键词】分形编码;图形处理器;计算统一设备架构;实时性【作者】孙冬;高清维;卢一相;竺德【作者单位】安徽大学电气工程与自动化学院，安徽合肥 230601;安徽大学电气工程与自动化学院，安徽合肥 230601;安徽大学电气工程与自动化学院，安徽合肥 230601;安徽大学电气工程与自动化学院，安徽合肥 230601【正文语种】中文【中图分类】TP391作为新一代的图像压缩技术，分形编码自20世纪80年代提出以来，由于具有极高的压缩比和较好的解码质量，引起了人们的广泛关注.然而分形编码时间过长是其固有的缺点，这也限制了它的推广和应用.为减少编码时间，近30年来许多学者对此开展了深入研究［1－3］，他们的工作主要集中于:如何在不明显降低图像解码质量的基础上，尽可能地减少待搜索父块的数量.在已经提出的诸多改进方案中，以Davids的工作最为出色，他提出的小波域分形(wavelet－fractal，简称FW)编码算法［1］能够极大地缩短编码时间，而且解码图像质量更高.虽然后人对FW编码方案又进行了许多改进，但编码时间距实时化仍有约2个数量级的差距.现代处理器的架构已经将并行计算作为提高性能的一个最重要途径.高性能的CPU 由于很难克服提高时钟频率后的散热问题，转而使用增加运算核心的方法来加速.作为CPU的协处理器，图形处理器(graphics processor unit，简称GPU)的计算能力在近年内以远超摩尔定律的速度爆炸性增长.据报道2013年nVidia公司基于开普勒架构GK110核心的GTX Titan型GPU单精度浮点运算峰值速度达每秒4.5万亿次，拥有2 688个流处理单元，由71亿个晶体管组成，而热设计功耗仅为250 W.由于GPU拥有CPU所不具有的超密集高并行的计算特点，将GPU用于非图形领域的通用科学计算逐渐成为人们关注的热点，具有重要的理论意义和应用价值［4－7］.受此启发，作者将GPU应用到图像分形编码中，以寻求一种高实时性的编码方案.1 FW编码原理Barnsley认为，自然界的图像具有局部自相似性［8］.Jacqain根据这一假设，把图像描述成一个带灰度映射的局部迭代函数系统(local iterated function system with gray level maps，简称LIFSM)的吸引子.文献［9－10］中给出了LIFSM的编码原理，将图像分割成若干不重叠的块，并为每个块寻找一个与其相似的父块及对应的映射关系.由于空域中大小为2J×2J的块交流成分在小波域中近似地对应为根在第J级子带上的小波树SJ，因此，当空域中的两个块具有相似性时，它们在小波域中所对应树的各级数据之间也具有相似性，并且这种相似性是一致的(空域块的自相似性和相应小波域中树的自相似性请参见图1，图1b中，每棵树由3个方向的分支组成).Davis根据这一事实，把LIFSM编码引入小波域，提出了FW编码算法，将空域中块的相似性用小波域中树的相似性来近似等价.与LIFSM编码相比，FW编码算法能够极大地缩短编码时间，而且解码图像的视觉质量也更高.图1 自相似性Fig.1 Self-similarity对图像作小波变换.设是根在第J级子带(m，n)处的树，FW编码算法将为每棵树找出一棵根在第J+1级子带(u，v)处的父树，使得在收缩变换A、仿射变换及对比度变换下，与在MSE意义下误差最小，即取最小值.当树和充分相似时，二者之间的误差e近似为0.此时(1)式可写为其中:代表树在第 j级子带上的数据，它由 3 个 2J－j× 2J－j大小的数据块组成;Lm，n为仿射变换，其对树上的数据进行逐层的变换，一般地，Lm，n限定为文献［11］所限定的8种特殊变换之一;A为收缩算子，它使树损失掉第1级子带上3个高频方向的数据，也即下降一级分辨率.省略位置下标，收缩算子A满足gm，n为对比度变换因子，定义为其中:Cov为协方差运算.因为FW编码是有损的，所以为了能够在编码时对图像质量进行控制，可以对(1)式中的误差e设定上限阈值E，并且规定当e＞E时，不再对树进行FW码的近似存储，而是直接储其小波系数.显然，当E充分大时，FW编码将退化为小波编码，但是编码时间不会减少，因为最优父树的搜索是必需的.FW的解码是逐级迭代完成的.因为根在第J+1级子带(u，v)处的父树与根在第J级子带(m，n)处的子树具有相似性，因此可以使用下式从父树中恢复子树数据J次迭代后，解码完成.对树的存储可以用对其 FW 码的存储来近似，这就是小波域分形编码的原理.2 并行化算法计算统一设备架构(compute unified device architecture，简称CUDA)是通用GPU计算的一种技术规范，由NVidia公司于2007年提出.与传统的通用GPU计算方式不同，在CUDA规范下，用户可以用C或其他语言进行自由的GPU编程，而不再需要调用图形API.CUDA程序由在CPU上执行的Host部分和在GPU上执行的Device部分共同组成，其中，Host部分主要负责Host端资源(内存)的分配与释放、Device端资源(全局显存、纹理显存、共享显存、寄存器)的分配与释放、内存与显存之间数据的I/O;Device部分主要负责显存中数据的计算、计算线程的同步.在Device中执行的代码称为内核(Kernal).基于CUDA的GPU编程模型如图2所示.图2 基于CUDA的GPU编程模型Fig.2 The GPU programming model based on CUDA从图2可知，Device部分数据并行处理在逻辑上是由众多的线程(Thread)共同完成的，这些线程将各自处理显存中数据的一小部分.CUDA中的线程是分级组织的:多个线程可以组成一个块(Block)，多个块又可以组成一个网格(Grid).一般情况下，一个网格就代表一个计算任务.因为网格和块可以在程序中定义成一维或多维(网格最多可定义为二维，块最多可定义为三维)，所以在实际编程中，可根据需要对计算任务进行自由的切割以方便程序的编写.由FW编码原理可知，对图像进行编码的实质是为每棵根在第J级子带处的子树搜索一棵与其最为相似的父树.为了加速这一过程，可以使用并行的方法，为所有的子树同时进行最优父树搜索.根据CUDA编程模型，作者提出的并行化的FW编码算法如图3所示.图3 并行FW编码算法Fig.3 The parallelized version of FW encoding algorithm在图3中，每个子树的编码过程都由一个Device线程进行处理.因为每个GPU核心只能同时运行一个线程，所以GPU核心数量N越大，线程运行的并发性就越好，总的编码速度也就越快.可以证明，若一个算法中有P部分(0≤P≤1)可以做并行处理时，理想情况下的加速比为在FW编码中，因为小波变换部分的计算量远小于编码部分，所以P≈1，此时加速比可接近最大值N.考虑到当今的主流GPU都具有数量众多的核心，所以当使用GPU代替CPU进行编码时，性能会有本质上的提升.3 实验为验证该文算法的正确性和有效性，使用一幅512×512的标准测试图像“Lena”，分别用CPU和GPU对其进行FW编码和解码，并对解码图像和编码时间进行对比.其中FW编码算法中的小波变换部分采用“sym4”小波，作4级变换，分形编码部分误差阈值E=200.程序开发环境为Visual C++2005，软件运行环境为32位Windows 7，内存为4 GB.图4给出了分别使用CPU和GPU对测试图像进行编码后的解码图像(50%的比例显示)，其中PSNR=32.69.图4 FW解码图像Fig.4 FW decoded images由图4可知，采用GPU的解码图像和CPU的解码图像是一致的，这证明了GPU 编码的正确性.表1给出了不同规格GPU对测试图像进行编码的时间，并与CPU 的编码时间进行对比.其中编码时间的计算从小波变换之后开始到FW码由显存拷贝回内存后结束，运行10次取最小值;CPU的计算时间为仅使用1颗核心时的结果.表1 GPU与CPU的FW编码时间对比Tab.1 The comparison of FW encoding time between GPU and CPU处理器种类处理器型号核心数主频/GHz 编码时间/s 加速比CPU Intel E5300 2 2.53 14.945 1.00 GPU nVidia 9600 GT 64 1.62 0.640 23.35 GPU nVidia 9800 GT 112 1.50 0.409 36.51 GPU nVidia GTX260 192 1.24 0.292 51.18 GPU nVidia GTX460 336 1.35 0.171 88.36由表1可见，采用GPU的编码时间远小于CPU的编码时间，因此采用GPU进行FW编码是快速有效的，且具有较高的实时性.4 结束语借助于GPU强大的计算能力，作者所提出的并行FW编码方案可以在不降低图像质量的情况下，大幅减少编码所需的时间，实现了图像分形编码的实时化，具有重要的实用价值.参考文献:［1］Davis G.A wavelet－based analysis of fractal image compression ［J］.IEEE Trans on Image Processing，1998，7(2):141－154.［2］Hyun J，Lickho S.A spectrum－based searching technique for the most favorable section of digital music［J］.IEEE Trans Consumer Electronics，2009，55(4):2122－2126.［3］Lv J，Ye Z X，Zou Y R.Huber fractal image coding based on a fitting plane［J］.IEEE Trans on Image Processing，2013，22(1):134－145.［4］冯娜.基于GPU的档案数据库应用研究［J］.武汉理工大学学报，2011，33(6):148－151.［5］Chen Y W.Fast virus signature matching based on the high performance computing of GPU［C］∥IEEE International Conference on Communication Software and Networks，2010:513－515.［6］杨正龙，金林，李蔚清.基于GPU的图形电磁计算加速算法［J］.电子学报，2007，35(6):1056－1060.［7］马巍巍，孙冬，吴先良.基于GPU的高阶辛FDTD算法的并行仿真研究［J］.合肥工业大学学报:自然科学版，2012，35(7):926－929.［8］Barnsley M F，Sloan A D.A better way to compress images byte ［M］.McGraw－Hill:Inc Hightstown NJ USA，1988:215－223.［9］Jacqain A E.A novel frctal block－coding technique for digital image ［C］∥IEEE International Co nference on Acoustics，Speech，and Signal Processing，1990:2225－2228.［10］Wohlberg B，Jager B D.A review of the fractal image coding literature［J］.IEEE Trans on Image Processing，1999，8(12):1716－1729. ［11］赵健，雷蕾，蒲小勤.分形理论及其在信号处理中的应用［M］.北京:清华大学出版社，2008:57－75.。
基于二维特征的快速分形图像编码方案李高平【摘要】分形图像编码方法因其具有高压缩比、重建速度快、分辨率无关性等优点使得它有很好的发展前景.但是,编码过程需要在一个海量码本中寻找每个range 块的最佳匹配domain块而耗去特别多的时间,这阻碍了它的广泛应用.为了加快编码过程,提取图像快的能量和方差来构成它的二维特征,作为图像子块间的相似性度量,在range块与domain块匹配时,大多数与range块的二维特征不相近的domain块,可以在匹配前排除.因此,对一个range块,能够在较小的搜索范围内找到它的最佳匹配domain块,使编码时间极大地减小.仿真实验显示,它能够大大缩短编码时间,同时实现和全搜索分形编码方法相近的重建图像质量.【期刊名称】《西南民族大学学报（自然科学版）》【年(卷),期】2011(037)003【总页数】6页(P485-490)【关键词】分形图像编码;图像压缩;二维特征【作者】李高平【作者单位】西南民族大学计算机科学与技术学院,四川成都610041【正文语种】中文【中图分类】TP391.41分形图像编码是一种新型图像压缩技术, 由Barnsley和Sloan在1988年首次提出[1], 它突破了以往图像编码的框架, 巧妙地利用图像中的自相似性, 将一副图像用一组迭代函数系统(IFS) 来表示, 由于IFS中的参数数据量比图像本身的数据量小得多, 所以它能够达到高倍压缩的目的. 1990年Jacquin基于块分割实现了能在计算机上自行处理的全搜索分形图像压缩编码[2]. 这种图像编码方法因其思想新颖、压缩比高、分辨率无关性等优点倍受图像压缩界的青睐. 然而, 它在编码过程需要特别长的时间, 限制了它在图像压缩领域的广泛应用. 所以,在保证重建图像质量的前提下, 如何实现快速的编码是分形图像编码技术的一个重要课题[3].针对编码过程特别耗时问题, 提出了许多改进方案来加快编码速度, 其中比较有效的方法是分类法和特征向量法[4], 针对这两种方法, 文献[4]的对比研究表明, 特征向量法比分类法更为有效. 但是, 特征向量法的不足之处在于因特征向量维数高而需要增加额外存储, 且编码性能随着维数增高而越差. 为了改进特征向量法的这个缺点, 有些研究者做了一些探索, 重新定义了图像块的特征向量[5-9], 也取得了一定的加速效果. 本文在此基础上, 对特征向量法做了进一步的研究, 首先将图像块上各像素点灰度值排列成一个样本, 提取其能量和方差来构成图像块的二维特征, 用它作为图像子块间的相似性度量, 然后, 把二维特征一维化为能量方差积特征. 在寻找range块的最佳匹配domain块时, 只搜索与range块的能量方差积特征相近的domain块, 这样可以使一个range块能够在较小的搜索范围内找到它的最佳匹配domain块, 从而极大地缩短编码时间. 三幅测试图像的仿真结果表明, 它不仅实现了平均加快编码过程的速度10倍, 而且得到了与全搜索法相近的重建图像质量.为了表述方便, 将大小的图像块的像素点灰度值排序, 使其对应于线性空间RN中的向量. 这样, 图像块 R和 D的像素点灰度值所构成的向量可以分别记为别表示块R和D上各像素点的灰度值. 用x表示X ∈ RN的均值, 用分别表示向量内积和2-范数,用(RN,E)代表灰度图像空间(R是实数集, E为均方根失真度量函数), m表示R 块的最佳匹配块序号, s为对比度因子, o为亮度偏移量,是所有元素均为1的常值块. 全搜索分形图像编码过程的流程图如图1所示.具体地说, 在编码时, 要得到每一个range块(简称R块)的最佳匹配domain块(简称D块), 必须按照全搜索方式在码本Ω中寻找. 若D是R的最佳匹配块, 那么, 在自仿射变换w下, w()D=⋅sD+o⋅I与R的均方误差应该是最小的, 即需要对下述极小化问题进行求解：因直接求解问题(1)是十分困难的, 所以, 只能寻求次优解法求解(1)中内层约束极小化：先忽略对比度因子约束, 然后对作截断处理来解决. 此时, 问题(1)的内层约束极小化变为：用最小二乘法求解问题(2), 得到此时, 匹配误差为接着用全搜索法求解问题(1)的外层极小化问题：通过问题(1)的次优求解, 就得到了该R块的分形码为仿射变换参数(储存传输需量化为等距变换序号t、最佳匹配块的位置m. 所有R块的分形码的集合∪就用来表示要编码的图像.重建图像时, 用编码过程得到的图像分形码描述的变换参数, 迭代作用于任何初始图像来生成.首先, 探讨是不是所有的R块都需要在码本Ω中搜索其匹配块后, 才能得到分形码？由式(4)可以推出, 这表明当子块R具有足够小的标准差σR时, 选择码本Ω中的任意D∈RN块作为其匹配块, 匹配误差都是很小的. 因此, 对待编码R块, 可以按照它的标准差σR的大小来决定它是否需要匹配搜索.对给定的阈值参数τ>0, 只对σR>τ的待编码R块(通常是图像的非平滑区域, 称为非平滑块), 才从码本Ω中搜索其最佳匹配块.其次, 想办法减少R块要搜索码本Ω的容量. 流程图1表明, 编码过程之所以耗时就在于R块与D块匹配搜索所用码本Ω的容量太大. 若能按照某种条件, 在匹配前就从码本Ω中排除不太可能匹配R块的D块, 只搜索与R块匹配可能性大的D块,那就缩减了码本Ω容量的目的. 为此, 定义图像块的能量和方差 VX分别为：于是, 图像块X的二维特征定义为为了避免增加额外存储, 将它一维化为能量方差积特征作为图像子块的相似性度量. 换句话说, 两个相似的图像子块, 它们的能量方差积特征应该接近. 以此为基础, 首先将码本中的 D块按其能量方差积特征L(D) 的大小进行升序排列, 即满足其次, 使用二分法在升序码本Ω中搜索与L(R) 相差最小的初始匹配块搜索它的匹配块Dm (i). 显然, 编码时间自然会随着搜索空间缩减而减少. 但是, 这样做图像的重建质量有没有保证呢？这就要看在邻域内找到的匹配块(简称局部匹配块), 有多少是全局搜索意义下的最佳匹配块(简称全局匹配块). 现以Lena、Boat和Peppers(512×512, 256灰度级)三幅测试图像为例, 观察它有多少非平滑R块的全局匹配块能在邻域里找到. 表1为其实验结果, 表中标识“M-N”是指集合{根据表1中的实验数据, 可以算出三幅测试图像只需要在以初始匹配块 D c 为中心, 搜索码本Ω中10%的码本块就能找到全局最佳匹配块的非平滑R块的比例分别为22.9%、23.3%、24.3%, 搜索码本Ω中50%的码本块就能找到全局最佳匹配块的非平滑R块的比例分别为 74.9%、74.9%、74.1% , 几乎要进行全局搜索才能找到全局最佳匹配块的非平滑R块的比例分别为3.1%、3%、3.1%. 这些数据表明, 在能量方差积特征意义下,有五分之一多的非平滑 R块只需要在邻域半径的邻域δ内就能找到全局最佳匹配块, 接近四分之三的非平滑 R块只需要在邻域半径k的邻域内就能找到全局最佳匹配块. 也就是说,大多数非平滑 R块的最佳匹配块 D m 在初始匹配块 D c 的附近, 不必搜索全部码本Ω, 在邻域δ(Dc,k)内找到的局部匹配块就是全局匹配块.此外, 根据s的表达式(3)和Cauchy-Schwarz不等式, 有式(7)表明, 对于给定的输入子块R, 如果码本块D的标准差Dσ小于σR, 那么s满足约束||1s<的可能性减少, 被截断处理掉的可能性增大, 也就是说标准差小于输入子块R标准差的码本块, 成为它的匹配块的可能性小. 因此, 可以根据码本块D的标准差Dσ, 从码本Ω中预先排除小标准差码本块, 得到子块R搜索的容许码本如下：显然, 不同的子快R, 其容许码本′的容量也不同. 用容许码本′代替码本Ω, 它有效地减少了码本容量,对编码过程的加速效果和重建图像质量的影响见表2. 以测试图像Lena、Boat和Peppers(512×512, 8bit量化)为例, 它平均加快了编码过程2.14倍, 以PSNR度量的重建图像质量平均下降为1.18dB.基于上述分析, 编码过程的仿真算法描述如下：(1) 把待编码图像I分割为n×n大小的图像块(不允许重叠), 记为R块, 其上的像素点灰度值排列成向量(2) 在同一图像I中, 以滑窗步长为δ像素来生成大小为2n×2n的图像块(允许重叠), 通过收缩和8种等距变换得到n×n大小D块, 全体D块集合就构成码本Ω.(3) 对于待编码R块, 其容许码本为以Lena、Boat、Peppers(512×512, 256灰度级)三幅图像为测试对象, 验证本文提出的快速方案的编码效果. 实验平台为运行Windows XP 的AMD Athlon x2-250 processor 3.01 GHz, 编程语言为C++. 图像用一致方块分割,R块、D块大小分别为4×4、8×8, 滑窗步长为8.本文的快速算法的编码时间和重建图像质量取决于阈值参数τ和搜索窗口邻域半径k. 如何确定阈值参数τ的大小, 文献[10]做的实验研究表明, 随着τ取值增大, 编码速度加快, 但块效应严重, 当4τ≤时, 块效应基本消失, 因此, 本文方案选取4τ=作为默认值. 对于搜索窗口邻域半径k的选取, 仅从实验的角度来探讨它的取值, 表3列出了搜索窗口半径k对编码性能影响的实验数据. 表3中数据表明, 在能量方差积特征意义下, 从一个待编码R块的初始匹配块 D c 的邻域中搜索其匹配块时, 随着参数k的增大, 虽然以PSNR度量的重建图像质量越好, 但是编码所耗的时间也会增长. 当′时, 重建图像质量基本变化不大, 当k < 0 .5Ω′时,重建图像的质量变化较大, 从兼顾编码时间和重建图像质量的角度, 选取为宜.下面针对选用的三幅图像, 在相同的实验条件下, 来测试全搜索分形图像编码方法与本文所提快速编码方案(τ =4,k =0.5Ω ′)的编码性能优劣. 全搜索方法和本文方案的实验结果列于表4, 从表中数据看, 本文方案相对于全搜索方法, 在重建图像质量(以PSNR度量)平均下降仅为0.56 dB的情况下, 平均加快它的编码速度10余倍.如果么本文方案在PSNR值平均下降1.64 dB的情况下, 可以平均加快编码速度47倍以上, 此时, 从图1给出的三副测试图像在本文方案和全搜索方法的重建图像对比结果看, 本文方案的重建图像的主观质量也是不错的. 上述结果表明本文的快速编码方案优于全搜索编码方法.本文利用图像块的能量和方差二维特征, 提出了一个快速分形编码方案, 把非平滑R块的最佳匹配块的搜索范围限制在其二维特征意义下初始匹配块的邻域内搜索. 测试图像的仿真结果表明, 对大多数非平滑 R块,能够在初始匹配块的最近邻域内找到的局部匹配块就是它的全局最佳匹配块. 本文方案与全搜索分形图像编码方法相比, 仅对非平滑 R块才编码, 且它的搜索空间也大大减少了, 有效地降低了算法的复杂度. 本文方案不仅实现了与全搜索方法的重建图像质量相近, 而且还平均加快了它的编码速度大约10倍. 因此, 从兼顾质量和编码速度的角度看, 本文提出的快速编码方案确实提高了全搜索方法的编码速度.【相关文献】[1] BARNSLEY M, SLOAN A. A better way to compress images[J]. BYTE, 1988(1): 215-223.[2] JACQUIN A E. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations[J], IEEE Trans Image Processing,1992,1(1):18-30[3] WOHLBERG B, JAGER G. A review of the fractal image coding literature [J]. IEEE Transactions on Image Processing, 1999, 8 (12):1716-1729.[4] POLVERE M, NAPPI M. Speed-up in fractal image coding: comparison ofmethods[J].IEEE Trans Image Process,2000,9(6):1002-1009.[5] HE C, YANG SX, XU X. Fast fractal image compression based on one-norm of normalised block[J]. Electron Lett ,2004,40(17):1052-1053.[6] 何传江, 黄席樾. 基于图像块叉迹的快速分形图像编码算法[J]. 计算机学报, 2005, 28 (10): 1753-1759.[7] 何传江, 申小娜. 改进分形图像编码的叉迹算法[J]. 计算机学报, 2007, 30 (12): 2156-2163.[8] 李高平, 雷开彬, 周绪川. 使用2－范数匹配的快速分形图像编码算法[J]. 计算机工程与应用,2008, 44(5)：85-87, 108.[9] 李高平. 主对角和特征的快速分形图像编码[J]. 计算机工程与应用,2010, 46(26)：176-178, 190.[10] 李高平, 何传江, 黄娟娟. 提高分形图像编码质量与速度的方案[J].计算机仿真,2006, 23(5)：163-166.。
基于小波变换的分形图像编码压缩算法赵蓉; 王辉; 张爱华【期刊名称】《《计算机应用与软件》》【年(卷),期】2019(036)011【总页数】6页(P262-266,305)【关键词】分形; 图像压缩; 九块和; 小波【作者】赵蓉; 王辉; 张爱华【作者单位】南京邮电大学理学院江苏南京210023【正文语种】中文【中图分类】TP751.10 引言分形图像编码最早是将原始图像表示为图像空间中一系列压缩映射的吸引子。
后来基于方块分割的算法又被提出，但因花费时间过多，不能被广泛应用。
近年来，新提出的特征向量法应用方便、效果好。
根据图像子图的特征点的选取原则，本文选取规范化图像子块的九块(4个顶点，4条边上的中点及一个中心点)位置上的像素点作为特征点，并以这些特征点的归一化值的绝对值和来定义图像子块的九块和特征。
先在理论上证明九块和与均方误差的关系不等式，再对码本中的码本块按照其九块和的大小进行排序，找到R块的初始匹配块之后，直接在邻域内进行匹配搜索。
这样可以有效地缩小搜索范围，从而减少分形编码时间。
分形编码的发展有力地推动了图像编码技术的发展，但是压缩时间较长，不能满足实时处理的要求。
近年来，将分形编码与小波结合的混合编码方法取得了巨大的成功[1-7]。
小波变换不可以直接用于压缩，但可以用来分解图像。
图像经小波变换后，得到小波系数。
虽然小波变换前后的数据量相同，但小波变换后，图像的能量得到了重新分配，低频子带集中了绝大部分能量，3个高频子带拥有的能量少，因此对低频子带采用尽量多的量化级别，其他子带采用较少的量化级别。
并且图像经过多级小波分解后，得到的各级子带间具有较强的相似性，而分形的优势就是在于自相似性强的图像[6]。
因此，本文将小波与九块和特征相结合，取得了一些进展。
1 小波变换的理论基础1.1 小波定义和连续小波变换小波定义：对于任意一函数ψ(t),若ψ(t)∈L2(R)，即函数平方可积，当满足：ψ(t)dt=0(1)则称ψ(t)为基本小波或母小波，当ψ(t)随着t的变化而上下浮动时，形成小波。
