Fast hierarchical codebook search for fractal coding of still images

分形图像编码的快速算法
杨倩;穆晓敏
【期刊名称】《河南科学》
【年(卷),期】2005(023)003
【摘要】针对分形图像编码时间过长的缺点,提出了一种快速分形图像编码方法. 此快速方法充分利用了分形中迭代函数系统的吸引子的分辨率与尺度无关的特性,将原始图像缩小后进行压缩,从而加快了编码的速度. 实验结果表明,较之传统的分形编码方法,此方法在相近的解码图像质量和压缩比的情况下,编码时间大为缩短.【总页数】3页(P426-428)
【作者】杨倩;穆晓敏
【作者单位】郑州大学信息工程学院,河南,郑州,450052;郑州大学信息工程学院,河南,郑州,450052
【正文语种】中文
【中图分类】TN919.8
【相关文献】
1.基于FGSE的快速分形图像编码算法及其多描述编码方案 [J], 刘美琴;赵耀
2.改进转动惯量特征的快速分形图像编码算法 [J], 李高平;杨军;陈毅红
3.四分位数特征的快速分形图像编码算法 [J], 李高平;向慧芬;赵正武
4.基于HV分割的快速分形图像编码算法 [J], 张林娜;袁和金
5.基于子域对角和的快速分形图像编码算法 [J], 王丽娜;刘晓东;贺兴华;沈灿岭
因版权原因，仅展示原文概要，查看原文内容请购买。

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

分形图像编码的快速细粒度迭代解码陈毅松;王继成;张福炎【期刊名称】《计算机学报》【年(卷),期】2002(025)003【摘要】该文基于分形图像编码的固有特征,阐述和研究了分形图像编码的迭代解码方法的"可分级性"概念,在这一思想指导下,在迭代解码过程中用单缓冲算法取代传统分形编码中的双缓冲算法,在节省了内存空间开销的同时有效地实现了更细粒度上的质量可分级性解码.继而提出了一种块排序解码算法用于基于变尺寸自适应块分割的分形编解码方案中,获得了更快的解码收敛速度.通过以上一系列算法思想深入地阐述了分形编解码中"质量连续可分级性"的思想,给出了一个初步的实现模型并对结果作了详尽的分析.【总页数】7页(P269-275)【作者】陈毅松;王继成;张福炎【作者单位】南京大学计算机科学技术系,南京,210093；南京大学软件新技术国家重点实验室,南京,210093;南京大学计算机科学技术系,南京,210093；南京大学软件新技术国家重点实验室,南京,210093;南京大学计算机科学技术系,南京,210093；南京大学软件新技术国家重点实验室,南京,210093【正文语种】中文【中图分类】TP391【相关文献】1.一种基于迭代函数系统的分形图像编码方法 [J], 田金超;孟克;韩志学2.小波分析应用于迭代分形和统计预测分形相结合的图像编码方法 [J], 王大凯;魏海3.基于分形维数和小波的快速分形图像编码 [J], 王英霞; 赵德平; 雷红4.分形图像编码中解码图像质量的预测 [J], 王强;梁德群;毕胜5.基于小波分解和分形迭代的图像编码新方法 [J], 田金文;柳斌;柳健;张天序因版权原因，仅展示原文概要，查看原文内容请购买。

用小波变换加速分形图像编码
袁立宇;黎绍发
【期刊名称】《华南理工大学学报：自然科学版》
【年(卷),期】1999(27)12
【摘要】针对分形图像编码过程十分耗时的弱点,提出了一种结合小波变换特性来实现的快速分形编码算法.实验显示新算法有较好的加速效果.
【总页数】5页(P79-83)
【关键词】分形编码;小波变换;IFS;分形图像编码;图像处理
【作者】袁立宇;黎绍发
【作者单位】华南理工大学计算机系
【正文语种】中文
【中图分类】TN919.8
【相关文献】
1.基于小波变换的分形特征图像编码 [J], 王小侠;戴芳;赵凤群
2.基于提升小波变换的快速分形图像编码 [J], 程璐璐;孙万蓉;薛丹;李京京
3.一种基于小波变换的邻域搜索分形图像编码 [J], 李从宏;于凤芹
4.基于正交多小波变换的快速分形图像编码 [J], 李会;房汉雄;朱恒军
5.基于小波变换的分形图像编码压缩算法 [J], 赵蓉; 王辉; 张爱华
因版权原因，仅展示原文概要，查看原文内容请购买。

基于局部方差的快速分形图像块编码算法
范策
【期刊名称】《计算机应用与软件》
【年(卷),期】2001(018)006
【摘要】在分形图像块编码中，大部分时间花在序列块和较大的主池间寻找紧密的匹配上。

对一幅较大的图像来说，由于主池按指数地增加，这种时间上的耗费便加剧了。

本文提出了利用主块局部方差来减少搜索的空间。

通过根据其局部方差排序收缩的主池，我们可以把所有可能的紧密匹配都限定在一个相对小范围的窗口来限制搜索空间，而在得到同样编码图像质量前提下同满搜索方法相比，编码的时间可以被缩短，其提高的速度可以达10倍左右。

【总页数】5页(P56-60)
【作者】范策
【作者单位】烟台大学计算机学院
【正文语种】中文
【中图分类】TP391.4
【相关文献】
1.快速分形图像编码局部方差算法的改进 [J], 何传江;蒋海军;黄席樾
2.图像子块特征匹配的快速分形编码算法 [J], 李高平;刘莉
3.基于局部方差和DCT变换的混合分形图像编码算法 [J], 周一鸣;张超;张曾科
4.基于图像块叉迹的快速分形图像编码算法 [J], 何传江;黄席樾
5.基于图像子块特征的快速分形图像编码算法 [J], 周一鸣;张超;张曾科
因版权原因，仅展示原文概要，查看原文内容请购买。

快速分形图象编码
何爱军;马争鸣
【期刊名称】《中国图象图形学报：A辑》
【年(卷),期】1999(4)9
【摘要】提出了一种新的快速分形图象编码方法。

该方法通过自适应的图象分块、相似块集的矩分类、相似块和图象块的正交分解以及象素递增的动态搜索等４个
步骤来加快分形图象编码的过程。

实验结果表明，提出的方法在缩短编码时间方面确有其效，特别是对于细节丰富的图象，效果尤为明显。

【总页数】6页(P719-724)
【关键词】分形图象编码;自适应图象分割;矩分类
【作者】何爱军;马争鸣
【作者单位】中山大学电子系信息处理实验室
【正文语种】中文
【中图分类】TN919.8
【相关文献】
1.基于卷积的快速分形图象压缩编码 [J], 王美琴
2.基于子块显著不相关检验的快速分形图象编码 [J], 熊惠霖;王岳环
3.基于邻域搜索的快速分形图象压缩编码方法 [J], 王心芬
4.基于小波变换的快速分形图象压缩编码 [J], 夏利民;谷士文
5.分形插值和分形图象压缩编码相结合进行图象数据压缩 [J], 杨绍国
因版权原因，仅展示原文概要，查看原文内容请购买。

快速的分形码图像检索方法
王兴元;陈志丰
【期刊名称】《计算机科学与探索》
【年(卷),期】2009(003)004
【摘要】针对分形域上的基于内容的图像检索(content-based image retrieval,CBIR),提出了一种新颖的基于无搜索的自适应四叉树分割的快速分形编码方法,来提取图像特征,从而使图像检索的编码阶段速度显著提高.对一幅256×256图像编码,算法平均约需0.048 5 S,比何的方法约快70倍,并且解码图像质量良好.改进了匹配算法来实现图像的快速检索,其准确性要高于洪的方法;最后通过对分形码距及分形码块数的分析,提出了进一步提高检索速度的方案.
【总页数】10页(P423-432)
【作者】王兴元;陈志丰
【作者单位】大连理工大学电子与信息工程学院计算机应用研究所,辽宁大
连,116024;大连理工大学电子与信息工程学院计算机应用研究所,辽宁大连,116024【正文语种】中文
【中图分类】TP301.5
【相关文献】
1.一种图像快速综合检索方法 [J], 张长宏;孙琦龙
2.基于二分图最佳匹配的图像检索方法 [J], 金红娇;罗时光
3.改进视觉词袋模型的快速图像检索方法 [J], 张祯伟;石朝侠
4.MEPG-7分块加权主颜色及相关反馈的图像检索方法 [J], 高立春;徐叶强
5.融合多层卷积神经网络特征的快速图像检索方法 [J], 王志明;张航
因版权原因，仅展示原文概要，查看原文内容请购买。