对分形图像压缩编码方法的探讨

基于双伸缩因子映射的小波分形图像压缩编码方法惠存阳【摘要】本文基于小波变换研究了分形图像压缩系统.根据小波系数的能量分布特性,给出了新的小波树定义与分类方法,并在小波域内建立了具有双伸缩因子的压缩映射.在将新的压缩映射应用于图像编码过程时,结合小波嵌入式零树编码思想给出了新的小波分形图像压缩方法.数值实验给出了本文方法与已有方法的比较.%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。

©2003 Journal of Software 软件学报一种分形彩色图像压缩编码方法*焦华龙1+, 陈刚1,21(浙江大学计算机图象图形研究所,浙江杭州310027)2(宁波大学数字技术与应用软件研究所,浙江宁波315211)A Color Image Fractal Compression Coding MethodJIAO Hua-Long1+, CHEN Gang1,21(Institute of Computer Graphics and Imaging Processing, Zhejiang University, Hangzhou 310027, China)2(Institute of Digital Technology and Application Software, Ningbo University, Ningbo 315211, China)+ Corresponding author: Phn: 86-21-64325854 ext 814, Fax: 86-21-64325842, E-mail: hl_jiao@Received 2002-04-09; Accepted 2002-07-02Jiao HL, Chen G. A color image fractal compression coding method. Journal of Software, 2003,14(4):864~868.Abstract: In this paper, a color image fractal compression coding method is proposed by analyzing the correlation of r, g, b components of a color image and the remnant of layer information in quadtree scheme. It merges three-color components into one. Accordingly this method will reduce the matching blocks, which need to be saved and encoded by SFC (separated fractal coding) algorithm, into one and at one time the source data and layer information in quadtree scheme can sustain non-losses and high-proportion compression. Furthermore, by selecting different combinations, a series of coding methods that bear very close compression ratio and qual ity of decoded image are obtained. Moreover the coding speed of the luminosity method among them is faster than the other ones. Experimental results indicate that this approach excels SFC or standard JPEG and can be a good color image fractal compression algorithm.Key words: color image fractal coding; quadtree structure摘要: 在分析彩色图像色彩三分量r,g,b的相关性和分形四叉树编码层次信息冗余性的基础上,提出了一种分形彩色图像压缩编码方法.它将图像的3个独立的颜色分量按某种方式组合成1个来搜索匹配块,从而将需要存储和搜索的3个颜色分量匹配块(SFC方法)减少为1个,并且对四叉树层次信息进行压缩.此外,采用不同的组合,得到了几个图像压缩比和解码质量相近的编码方法,其中使用亮度分量的方法比使用其他方法速度更快.实验结果表明,它优于SFC方法及标准JPEG方法,不失为一种好的分形彩色图像压缩方法.关键词: 分形彩色图像编码;四叉树结构中图法分类号: TP391文献标识码: A自20世纪80年代Barnsley等人提出图像的分形压缩[1]以来,分形图像编码作为一种新的具有高压缩比潜在能力的图像编码方法,受到了广泛的关注.但是,其研究主要还是集中在灰度图像方面,对真彩色图像压缩算*Supported by the National Natural Science Foundation of China under Grant No.60202002 (国家自然科学基金)第一作者简介: 焦华龙(1976－),男,安徽无为人,硕士,主要研究领域为图像编码,图像检索,计算机图形学.焦华龙 等:一种分形彩色图像压缩编码方法 865 法的研究则相对较少[2].与黑白图像相比,彩色图像的色彩部分是其特有的,并且与人眼的视觉特性关系非常紧密,因而对彩色图像的处理也应有独特的方法.显然,编码真彩色图像的一个最直接的方法就是将真彩色图像看成是3个独立的灰度图像进行单独编码的SFC(separated fractal coding)方法[3].这种方法由于没有考虑彩色图像3个颜色分量之间的相关性,因而压缩比较低而且很费时.本文首先在分析灰度图像分形四叉树压缩编码[2]方法中树结构层次信息的冗余性的基础上,提出了改进这种存储方式的压缩算法,并且给出了树结构层次信息的压缩比计算公式;之后,我们对由一幅真彩色图像分别抽出的三色分量所组成的灰度图进行统计比较,发现它们有很大的相似性,在此基础上,我们提出了将三色分量组合成一个特征量来搜索匹配块的分形彩色图像压缩方法.由于此方法需要存储和搜索的匹配块信息相当于与它同等大的灰度图像,因而编码所需要的计算量和所能达到的压缩比要比SFC 方法有较为明显的提高,在恢复图像质量相近,且没有做Huffman 编码或算术编码等无损压缩的情况下,压缩比也超过了标准JPEG 方法.1 四叉树层次信息的冗余性及其压缩存储在分形压缩的四叉树方法当中,每一个R 块需要记录以下6个参数:(1) 找到的最佳匹配子块D 的位置(d x ,d y )(子块左上角坐标);(2) 对称和旋转变换的序号n ;(3) 灰度仿射变换系数α和β;(4) 子块R 的层次信息l (一般是32⨯32到4⨯4四层,用2bit 存储).以这6个参数作为R 的码本,就可以从任意图像经过迭代恢复到原图像.四叉树剖分是最常见的一种方案,基于初始的正方形剖分,一般要求R 块大小为2r ⨯2r ,剖分后得到4个2r -1⨯2r -1的子块.由于这种方案比较简单,在计算量要求较高的分形编码中比较通用.事实上,在R 块的6个参数当中的层次信息l 有很多的冗余.以剖分从32⨯32到4⨯4四层为例,当有一个R 块分到最小(4⨯4)时,紧跟它的3个块也一定是分到最小的块,这样,只需存储第1个R 块层次信息即可,其他3块的层次信息属于冗余部分;在作了对最小块的层次信息的处理之后,同样地,次小块(8⨯8)的层次信息依然存在这种冗余,即当有一个R 块分到次小时,紧跟它的3个存储的层次信息次小层或最小层信息(这里,一个最小层信息已经代表4个最小块,也相当于一个次小块),这样我们就可以用一个次小层信息加4个标志位(最小层用0,次小层用1)来表示;如此下去,直到最大块(32⨯32)为止.在解码阶段,用最后得到的块信息加上存储的所有标志位,就可以恢复整个四叉树.在经过了上述无损的消除层次信息冗余的处理之后,对于原先用2bit 表示的R 块,最小块我们只用了约0.25bit,其他非最小块也只用了约1bit,起到了一定的压缩作用(从实验来看,对于256⨯256块,一般会压缩大约3倍).这里给出可以从压缩过程推导出来的层次信息压缩倍数的计算公式如下(剖分从32⨯32到4⨯4):=R C 4321432164808421)(128n n n n n n n n ++++++, 其中C R 表示层次信息压缩倍数;n i 表示图像分块中大小为2i +1⨯2i +1的R 块个数(i =1,2,3,4).对于一般图像来说,n 1较大,因而有较好的压缩效果.推导过程如下:(1) 没有压缩之前需要的空间为)(24321n n n n +++个bit;(2) 经过压缩后,4⨯4块占用标志信息空间为0个bit,8⨯8块占用标志信息空间为4/12n n +个bit,16⨯16占用标志信息空间为16/4/123n n n ++个bit,32⨯32占用非标志信息空间为64/16/4/1234n n n n +++个bit,总计为64/)64808421(4321n n n n +++个bit;(3) 将没有压缩之前所需空间除以压缩后所占空间,即可得到上述压缩倍数计算公式.例如,对于如图1所示的四叉树剖分(设整个块大小是32⨯32的,块4⨯4到32⨯32在层次信息中分别用11,10,01,00表示),没有经过编码之前的表示为01 10 10 11 11 11 11 10 11 11 11 11 10 10 11 11 11 11 10 11 11 11 11 10 10,用了50个bit.经过一次处理之后变为01 10 10 11 10 11 10 10 11 10 11 10 10,经过两次处理后变为01 10 10 10及标志信息0 0 1 0 1 0 0 1 0 1 0 0,再经过一次Fig.1 An example of quadtree partition structure 图1 四叉树剖分结构示例866 Journal of Software 软件学报 2003,14(4) 编码后成为最终的01及标志信息0 1 1 1和0 0 1 0 1 0 0 1 0 1 0 0表示,由于最终的信息(非标志信息)只是32⨯32和16⨯16两种,故只要1bit 表示即可(01可用1来表示),也就是说,最后我们用了共17bit,压缩倍数为50/17≈3.解码时只需将编码过程反过来,就能恢复所有的层次信息.2 编码方法2.1 三色相关性在将图像中每个像素的三色分量r ,g ,b 各自单独抽取出来作为灰度图像在该点的灰度值的观察中,我们发现它们在结构上具有非常相似的地方,有差别的只是在不同的地方,其亮度有所不同(如图2所示).也就是说,当我们用分形方法进行图像编码时,如果有一个分量的R 块和D 块相似,那么另外两个分量的相同位置的R 块和D 块也非常相似,只是在亮度上有差别.通过统计分析亮度Y 及r ,g ,b 颜色之间的相关性,我们得到了表1的结果.该表中的数据显示r ,g ,b 之间确实存在着很大的相关性,证实了原先观察得出的结论,于是我们考虑利用这种相关性进行彩色图像编码.由于分形中有对像素的灰度进行匹配修正的仿射变换系数α和β,可以利用这个修正来弥补亮度的差别.在实验中发现下面的方法有不错的结果,即用r ,g ,b 的线性组合得到的亮度)113.0586.0301.0(b g r Y Y ++=来搜索匹配D 块,把该D 块也分别作为r ,g ,b 的匹配块,只是修改3个颜色分量中与亮度相关的信息α和β,这样就将SFC 方法中的3色分量单独搜索、单独存储的过程简化为用一个3色分量的组合特征量来搜索和存储,这既缩减了匹配时间(变为原来的3/1),又提高了压缩比(是原来的2倍多).从表2来看,当Y 颜色分量的匹配误差小于给定的阈值时,r ,g ,b 颜色分量的匹配误差是可以接受的,实验得到的解码图像质量与SFC 并没有太大的差别.这也说明了该方法的可行性.相关性系数的计算公式为,)()()()()(y D x D y E x E xy E xy -=ρ其中x ,y 为两向量,E (x ),D (x )分别为表示x 的所有分量的平均值和方差.Table 1 Percentages of correlation coefficient over 0.8 proportioned by every two-color components,which are obtained from 4⨯4 image segmentations of colorful picture Fruit表1 对彩色Fruit 图像分割为4⨯4小块得到的各颜色分量两两之间相关性系数大于0.8所占百分数Y r g b r94.5 100 90.2 81.0 g97.4 90.2 100 87.1 b 89.1 81.0 87.1 100Table 2 Percentages of the corresponding matching errors against r , g , b which are obtained fromsearching the matching blocks (threshold is 5.0) by Y in picture Fruit表2 Fruit 图像用Y 来搜索匹配块(阈值取为5.0)所得r ,g ,b 对应匹配误差所占百分数Matching errorr g b 10.0 94.0 79.496.3Fig.2 From left to right are gray images of picture Fruit composed by three-color components r , g , b respectively图2 从左到右分别是彩色水果图Fruit 的r ,g ,b 颜色分量组成的灰度图像焦华龙 等:一种分形彩色图像压缩编码方法8672.2 具体的编解码方法步骤从图像三色相关性出发,我们形成了彩色图像的如下的编、解码方法.方法1. (1) 对要编码的彩色图像I 每一像素点的r ,g ,b 进行组合(实验中取亮度分量Y =0.301r +0.586g +0.113b ),得到一幅灰度图I '.(2) 对灰度图I '进行传统的分形四叉树搜索,使I '中的每个R 块找到相匹配的D 块.(3) 将编码彩色图像I 的r (红色)分量所组成的灰度图r I 中R 块和D 块匹配的位置对称旋转变换,树结构用I '中得到的来替代,只是将反映亮度的部分(即灰度仿射变换系数α和β)用从r I 中计算得到的最佳匹配值重新计算进行修正;g ,b 也作与r 相同的处理.=α∑∑'-''-'-i i ii i d d d d r r 2)())((, =β,d r '-α其中R =(i r )是r I 中子块R 像素灰度值组成的n 维向量,D '=(i d ')是R I 中D 块经四邻域平均的与R 等大的子块,r 和d '分别是R 和D '的平均值.(4) 对彩色图像I 的每个R 块,存储从I '得到的匹配D 块位置,对称旋转变换及r ,g ,b 分量的6个亮度修正值,R 块的四叉树层次信息用我们前面所提出的方法存储.解码过程:先恢复R 块的树结构,再分别对r ,g ,b 分量用IFS(迭代函数系)迭代得到3幅灰度图I r ,I g ,I b ,最后将它们合成为一幅彩色图.此外,我们还对彩色图像求取R 相匹配的D 块尝试采用了其他方法.方法2.将每一点的颜色值看作一个3维向量,定义两点P (,p r ,p g p b ),Q (,q r ,q g q b )的距离为,)()()(),(222q p b q p g q p r b b g g r r Q P d -+-+-=ωωω其中r ω,g ω,b ω为每个分量的权重,r ω>0,g ω>0,b ω>0且r ω+g ω+b ω=1(在本文的实验中,取r ω=0.1875,g ω= 0.675,b ω=0.1875).R 块与D 块是否匹配,就看R 与D 每个对应点的距离的平方之和是否小于给定阈值,即下式是否满足.(),),(2Γ<'∑i i i d r d这里,R =(r i )是子块R 像素点组成的n 维向量,D '=(i d ')是D 块经四邻域平均的与R 等大的子块,Γ是给定阈值.方法3.与方法1相似,只是将颜色模型转换到YUV 空间,再在YUV 空间作彩色图像两点的距离定义,然后再将对应点的距离的平方之和是否小于给定阈值作为R 块和D 块是否匹配的标准.对于彩色图像质量衡量问题,由于颜色感知与人眼的视觉特征密切相关,对于不同的颜色以及颜色的不同变化方向,人眼的感知灵敏度是不一样的,因而颜色的度量是一个复杂的过程.这就使得彩色图像质量的评价比起灰度图像要困难得多.为了简单、客观起见,仍然采用PSNR 作为彩色图像恢复质量的评价,但是我们将分别列出图像三色分量的PSNR.3 实验结果及分析我们用本文的方法对随机抽取的256⨯256的24位真彩色图像进行了实验.在寻找块时,采用金字塔小波的加速算法[4]来提高编码速度,在P Ⅲ700型微机上基本上能够在2秒之内完成对一幅图像的编码(在实验中,我们没有引入旋转对称变换,同时仿射变换α取为经验值0.75).从实验的结果来看,本文提出的几种寻找匹配D 块的方法所得到的解码图像质量和压缩比相近,仅就速度来看,方法1编码要好一些,大约是其他方法编码速度的3倍.与SFC 相比(这里主要是指没有经过Huffman 或算术等无损编码处理的SFC 方法,因为我们的方法也没有经过这些处理),我们的方法在图像解码质量没有明显下降的情况下,编码速度及压缩比都有很大的提高.与标准JPEG(编码时采用JPEG 标准所提供的量化表,并使用经过优化的Huffman 码表)相比,在图像解码质量相似甚至更高的情况下,该方法即使对系数没有进行其他无损编码,也有相对较高的压缩比.表3和图3分别给出了868 Journal of Software 软件学报 2003,14(4) 各种方法比较的结果数据及解码图.其中图3(a)是原始图像,图3(b)是JPEG 解码图像(0.12=R C ,PSNR 分别为25.0(r ),26.0(g ),22.0(b )),图3(c)是使用本文的方法1得到的解码图像(2.14=R C ,PSNR 分别为24.9(r ),25.3(g ), 21.4(b )).Table 3 Compression ratio and PSNR of decoded image among several methods表3 各种方法图像压缩比及解码质量References :[1] Jacquin AE. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Transactions on ImageProcessing, 1992,1(1):10~30.[2] Zhao HL, Liang Z, Somy NY. Fractal color image compression. In: Proceedings of the XIII Brizilian Symposium on ComputerGraphics and Image Processing (SIBGRAPI 2000). 2000. 185~192. /proceedings/sibgraphi/0878/ 08780185abs.htm.[3] Moltedo L, Nappi M, Yitulano D, Vitulano S. Color image coding combining linear prediction and iterated function systems. SignalProcessing, 1997,63(12):157~162.[4] Zhan D, Chen G, Jin YW. Fast fractal image encoding method based on pyramid wavelet transform. Acta Electronica Sinica,1998,26(8):37~42 (in Chinese with English abstract).附中文参考文献:[4] 张旦,陈刚,金以文.基于金字塔小波变换的快速分形图像编码.电子学报,1998,26(8):37~42.(b) (c)(a) Fig.3 Comparison of the decoded images图3 解码图对比。

目录摘要 (1)1.引言 (1)2.分形图像压缩 (1)2. 1分形概述 (1)2. 2分形编码与解码算法描述 (2)2. 3 MATLAB程序实现及其仿真结果分析 (2)2.3.1 MATLAB程序实现 (2)2.3.2仿真结果分析比较 (6)3.离散余弦变换压缩 (6)3. 1离散余弦变换概述 (6)3. 2 DCT编码算法 (6)3. 3二维DCT变换 (7)3. 4 MATLAB程序实现及其仿真结果分析 (7)3.4.1 MATLAB程序实现 (7)3.4.2仿真结果分析比较 (8)4.本文小结 (9)5.参考文献 (10)附录 (11)学习《信息工程概论》感想和体会 (15)基于分形和DCT的图像压缩摘要：对于图像来说，如果需要进行快速或实时传输，就要对图像进行压缩，而随着网络的发展，图像压缩技术越来越被人们所关注。

本文针对图像压缩中较为常用的两种方式：分形和DCT，进行了探讨和分析。

为了体现压缩变换后其效果的明显程度，借助于Matlab软件编写对应算法，进行了算法仿真，对于DCT 也编写了C语言程序进行了上机实现。

最后，将两种方法的优缺点进行了比较和总结分析。

关键字：图像压缩; 分形; DCT; 算法仿真Abstract:Regarding the image, if you need to carry on fast or the live transmission, it is necessary to compress the image, and with the development of networks, image compression technology has been concerned. In this article, I discuss and analyze two ways which is the fractal and DCT of the compression. To reflect the effect of compression, I write the corresponding algorithm for the simulation algorithm by means of the Matlab software，also write the C language program for the DCT that is achieved on the computer. Finally, I compare and analyze the advantages and disadvantages of both methods .Key words:Image compression ; Fractal ; DCT ; Algorithm simulation1.引言随着计算机多媒体技术和通信技术的日益发展，以及网络的迅速普及，图像数据信息以其直观、形象的表现效果，在信息交流中的使用越来越广泛。

图像编码是指将连续的图像信号转换成数字编码的过程。

在图像编码中，分块压缩方法被广泛应用。

本文将探究图像编码中的分块压缩方法。

一、分块压缩方法的背景图像编码是为了在保持图像质量的基础上减小存储空间和传输带宽，从而实现高效的图像处理和传输。

分块压缩方法就是其中一种方法。

二、分块压缩方法的原理分块压缩方法将图像分成若干个块，对每个块进行编码和压缩。

根据图像的特性，使用不同的算法对每个块进行处理，以减小数据量。

分块压缩方法常用的算法有离散余弦变换（DCT）和小波变换（Wavelet Transform）等。

三、离散余弦变换（DCT）离散余弦变换是将一个N x N的图像块转换为一个N x N的频域系数块的过程。

DCT压缩能够有效地去除图像中的冗余信息，实现更好的压缩效果。

DCT在图像编码中的应用非常广泛，比如JPEG压缩算法就采用了DCT。

四、小波变换（Wavelet Transform）小波变换是将信号分解为多个不同频率的子信号，通过对子信号进行压缩和重构来实现数据压缩。

小波变换的特点是能够在时域和频域上进行分析，更好地适应图像中的不同频率成分。

五、分块压缩方法的优缺点分块压缩方法的优点是可以灵活地控制压缩的粒度，根据需要对图像的不同部分进行不同的处理。

另外，分块压缩方法采用了离散变换技术，能够更好地提取图像的特征，从而实现较好的压缩效果。

然而，分块压缩方法也存在一些缺点，比如在块边界处会出现压缩伪影，对图像细节的保留不够完美等。

六、分块压缩方法的应用分块压缩方法被广泛应用于图像编码中，特别是在无损和有损压缩标准中。

无损压缩主要用于医学图像、卫星图像等需要保留图像细节的领域。

有损压缩则主要用于互联网传输、图像存储等需要高压缩性能的领域。

七、总结分块压缩方法是图像编码中的重要方法之一，通过对图像进行分块处理和离散变换，可以实现对图像数据的高效压缩。

离散余弦变换和小波变换是目前常用的分块压缩方法。

分块压缩方法在图像编码中有着广泛的应用，并不断地进行优化和改进。

第13卷第2期2010年6月成都电子机械高等专科学校学报J ourna l of C hengdu E lectrom echan i ca lC o ll ege Vo.l 13,N o .2June .,2010收稿日期:2010-03-24作者简介:冉晓娟(1982-),女(汉族),四川成都人。

硕士,主要研究方向:计算机应用技术、图形图像处理、多媒体技术及应用等。

哈夫曼编码和分形编码图像压缩技术初探冉晓娟1,梁静2(1.四川烹饪高等专科学校 信息技术系,成都 610000;2.成都电子机械高等专科学校 网管中心,成都 610031)摘 要:随着信息技术的发展,各种影像、语音、文字、数据等信息都以数字化的方式存储起来,给信息的存储带来极大的压力。

资料压缩 成为解决信息储存不可缺少的工具。

本文通过介绍常见的图像压缩技术!!!哈夫曼编码和分形编码,提出了一些改进的方法。

关键词:图像压缩;哈夫曼编码;分形编码中图分类号:TP311.13 文献标志码:A 文章编号:1008-5440(2010)02-0017-04A Study ofHuff m an Codi ng and Fract al Codi ng I mage Co mpressi onRAN X iaojuan 1,L I ANG J ing 2(1.I n for m ati on T echno l ogy D epar t m en,t Sichu a n H igher Instit u te of Cu isine ,Chengdu 610000,Ch i na ;2.Cen ter ofN et w ork M anage m en,t Chengdu Electro m echan ical College ,Chengdu 610031,Ch i na)A bstract :W it h t h e devel o p m ent of i n for m ation tec hno l o gy ,all k i n ds of vi d eos ,voices ,texts ,data ando t h er infor m ati o n are d i g itall y stored ,w hich bri n g us great pressu re on ho w to store the tens of thou sandsof infor m ati o n .A s a resu l,t data c o m pression beco m es an i n d ispensab l e too l for infor m ati o n storage .Th is paper first introduces the co mm on m i age co m pression tec hnology Huff m an cod i n g and fractalcoding ,and t h en proposes so m e m i pr ove m en ts .K ey words :I m age co m pression ;H uff m an c odi n g ;Fractal coding图像压缩技术的提出最早可追溯到1948年的电视信号数字化,至今已有近70年的历史。

大学本科学生毕业设计—分形图像压缩的算法二零一二年六月中文摘要分形图像编码方法是近十年来诞生并发展起来的一种新型图像压缩方法，它将图像编码为一组收缩映射，由这组收缩映射的不动点近似待编码对象。

借助自可变换性特征有效地消除了图像表达上的数据冗余，具有编码效率高、与分辨率无关、解码算法简单等潜在优势，已成为当今国际上图像编码领域中令人瞩目的研究方向。

本课题旨在以分块迭代函数系统为基础，研究分形图像编码的理论、方法和实现技术，探讨其工作机理，评价其能力，弥补其缺陷，设计并实现高效的图像压缩/解压算法，为多媒体智能软件系统提供有效的工具。

本文阐述了分形理论应用在图像压缩领域的基本原理和实现该算法的关键技术，介绍了具有代表性的各种图像压缩的新方法，阐明了各个方法的优劣，最后简要总结了分形图像压缩的改进方法以及未来的发展趋势关键词:图像压缩,分形,算法ABSTRACTFractal image coding, which is also called attractor image coding, is a emergent method of image compression during the last decade. It codes images as contraction maps of which the fixed points approximate to the images. Redundancy in images are efficiently exploited via the self-transformability on the blockwise basis. Owing to its high compression ratio, good image quality, and resolution-independence of the decoded image, fractal image coding has been attracting much attention, and being considered to be promising in the realm of image compressionThis paper aims at giving a compreheresearch on the theory, methodology, and implementation techniques of fractal image coding under the iterated function systems, developing a set of efficient coding/decoding algorithms to support multimedia software applications.This paper expounds the basic principle of the application of fractal in the image compression field theory and key technology of thisalgorithm,this paper introduces all kinds oftypical new method of image compression.It compared the advantages and disadvantages of every method ,and finally summarized the improvement and the future development trend of the fractal image compression method.Keywords: Image Compressing，Fractal，algorithm目录第一章绪论 (6)第二章分形图像编码的相关介绍 (7)一、分形图像编码的基本原理 (8)二、分形图像编码的实现步骤 (10)（一）编码主要步骤 (11)（二）解码主要步骤 (12)三、分形图像压缩的发展方向 (13)（一）加快分形的编码速度 (13)（二）提高分形编码质量 (14)（三）分形序列图像编码 (14)第三章分形与其他技术相结合的改进方案 (16)一、提高压缩比和编码效果常用的改进方法 (16)（一）改进分割的方法 (16)（二）改进覆盖式方法 (17)（三）提高显示效果的后处理法 (17)二、DCT与分形混合编码 (17)三、小波分形混合图像编码 (19)四、提高编码和解码速度的方法 (20)（一）提高编码速度 (20)（二）提高解码速度 (21)第四章仿真实验 (21)一、分型图像压缩流程图 (21)二、实验环境与所需步骤 (22)（一）实验环境： (22)（二）仿真步骤： (22)三、实验程序 (23)五、仿真结果 (30)第五章结论 (32)参考文献 (33)附录 (34)第一章绪论十多年前,在计算机图形学中分形技术被用来模拟自然景象,其中最常用的思想便是迭代函数系统(IFS)和递归迭代函数系统(RIFS)。

分形图像压缩的应用与方法摘要：本文首先大体上介绍了分形的概念和发展历史，然后着重开始讨论分形的图像压缩技术，给出了图像压缩的一些概念包括了优缺点，因为要查找图形内自相似部分而导致压缩时间过长, 但是解压缩过程却非常快,过长的压缩时间使得分形压缩不可能应用于实时压缩。

其次从多个角度讨论了分形图像压缩的方法，比如采用迭代函数系统的图像压缩方法。

关键字：分形；图像压缩；迭代函数系统；正文：1.分形的概念和发展1.1分形的概念[1]分形理论是当今世界十分活跃的新理论。

作为前沿学科的分形理论认为，大自然是分形构成的。

大千世界，对称、均衡的对象和状态是少数和暂时的，而不对称、不均衡的对象和状态才是多数和长期的，分形几何是描述大自然的几何学。

作为人类探索复杂事物的新的认知方法，分形对于一切涉及组织结构和形态发生的领域，均有实际应用意义，并在石油勘探、地震预测、城市建设、癌症研究、经济分析等方面取得了不少突破性的进展。

分形的概念是美籍数学家曼德布罗特(B.B.Mandelbrot)率先提出的。

1967年他在美国《科学》杂志上发表了题为《英国的海岸线有多长？》的著名论文。

分形，是以非整数维形式充填空间的形态特征。

分形可以说是来自于一种思维上的理论存在。

1973年，曼德勃罗（B.B.Mandelbrot）在法兰西学院讲课时，首次提出了分维和分形几何的设想。

分形（Fractal）一词，是曼德勃罗创造出来的，其原意具有不规则、支离破碎等意义，分形几何学是一门以非规则几何形态为研究对象的几何学。

由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学。

分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。

曼德勃罗曾经为分形下过两个定义：1.满足下式条件Dim(A)>dim(A)的集合A，称为分形集。

其中，Dim(A)为集合A的Hausdoff维数（或分维数），dim(A)为其拓扑维数。