分形图像压缩的算法本科学生毕业设计

《分形图像压缩的算法本科学生毕业设计》由会员分享，可在线阅读，更多相关《分形图像压缩的算法本科学生毕业设计（37页珍藏版）》请在装配图网上搜索。

1、大学本科学生毕业设计（论文）毕业设计(论文)大学本科学生毕业设计 分形图像压缩的算法中文摘要 分形图像编码方法是近十年来诞生并发展起来的一种新型图像压缩方法，它将图像编码为一组收缩映射，由这组收缩映射的不动点近似待编码对象。借助自可变换性特征有效地消除了图像表达上的数据冗余，具有编码效率高、与分辨率无关、解码算法简单等潜在优势，已成为当今国际上图像编码领域中令人瞩目的研究方向。本课题旨在以分块迭代函数系统为基础，研究分形图像编码的理论、方法和实现技术，探讨其工作机理，评价其能力，弥补其缺陷，设计并实现高效的图像压缩/解压算法，为多媒体智能软件系统提供有效的工具。本文阐述了分形理论应用在图像压缩

2、领域的基本原理和实现该算法的关键技术，介绍了具有代表性的各种图像压缩的新方法，阐明了各个方法的优劣，最后简要总结了分形图像压缩的改进方法以及未来的发展趋势关键词: 图像压缩,分形,算法ABSTRACT Fractal 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 appr

3、oximate 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 co

4、nsidered to be promising in the realm of image compression This 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 multimedi

5、a software applications.This paper expounds the basic principle of the application of fractal in the image compression field theory and key technology of this algorithm,this paper introduces all kinds oftypical new method of image compression.It compared the advantages and disadvantages of every met

6、hod ,and finally summarized the improvement and the future development trend of the fractal image compression method. Keywords: Image Compressing，Fractal，algorithm目 录第一章 绪论6第二章 分形图像编码的相关介绍7一、 分形图像编码的基本原理7二、分形图像编码的实现步骤9（一）编码主要步骤9（二）解码主要步骤11三、分形图像压缩的发展方向11（一）加快分形的编码速度11（二）提高分形编码质量12（三）分形序列图像编码12第三章 分形

7、与其他技术相结合的改进方案13一、 提高压缩比和编码效果常用的改进方法13（一）改进分割的方法13（二）改进覆盖式方法13（三）提高显示效果的后处理法14二、 DCT与分形混合编码14三、 小波分形混合图像编码15四、 提高编码和解码速度的方法16（一）提高编码速度16（二）提高解码速度16第四章 仿真实验17一、 分型图像压缩流程图17二、实验环境与所需步骤18（一）实验环境：18（二）仿真步骤：18三、实验程序18五、仿真结果22第五章 结论24参考文献25附 录26 第一章 绪论 十多年前,在计算机图形学中分形技术被用来模拟自然景象,其中最常用的思想便是迭代函数系统(IFS)和递归迭代函

8、数系统(RIFS)。Barnsley首先看到迭代函数系统对模拟自然景象(如云图、树和叶子)的潜力。 IFS方法在数字图像压缩理论和应用上得到越来越多的关注,成为当今图像压缩领域中最新的方法之一. Barnsley和Sloan指出，分形图像压缩技术能获得很高的压缩比。Jacquin首先实现了完全自动的分形压缩编码算法，给分形图像压缩技术带来突破性进展。分形图像压缩技术是在此算法基础上逐渐发展,成为当今图像压缩的一个新领域。 “分形”一词译于英文Fractal，系分形理论的创始人曼德尔布罗特（B.B.Mandelbrot）于1975年由拉丁语Frangere一词创造而成，词本身具有“破碎”和“不规

9、则”两个含义，主要是给自然界中存在的大量的不规则的支离破碎的复杂图形的命名。 1982年Mandelbrot用创造性的思维形成了以分数维、自相似性及无限可分为特点的、以迭代计算来描述的分形集合概念。从图像处理的角度而言，在许多自然图像中确实存在某种形式的分形子相似性，这就自然地产生了把分形概念用于图像编码的思想。 1988年Barnsley首先利用图像整体与局部的自相似性，提出了一种应用迭代函数系统理论实现的分形图像压缩编码。 1990年Jacquin创造性地利用图像块之间的相似性，提出了一种可由计算机完全自动实现的分形图像编码算法，为分形图像编码的研究带来了一次质的飞跃，使利用分形编码进行图

10、像压缩的方法开始进入实用阶段。1992年底，美国微软公司成功研制了一张“Microsoft Encarta”光盘.它仅用600Mbytes，就存贮了大量的文字数据、长达7h的声像资料、100部动画片、800张彩色地图和1000幅逼真的风景照片。这张光盘的研制采用了分形图像压缩技术。此技术以迭代函数系统为基础,采用了与常规技术不同的思想,能达到很好的压缩效果，目前,这一技术已引起了学者们的浓厚兴趣与深入研究,显示了广阔的应用前景。第二章 分形图像编码的相关介绍分形编码算法是一种有损图像压缩技术。它是图像压缩的重要数学工具，有着广阔的应用前景。分形图像压缩是以迭代函数系统（IFS）为理论基础，即用

11、自然景物的自相似性来进行数据压缩。分形图像压缩算法具有高压缩比、任意尺度下的重构、快速编码等优越性。此项研究由M.Barnsley于1988年首先提出，他成功地给予迭代函数系统的分形图像压缩应用于计算机图形学上，对航空图像进行压缩编码，并获得了1000：1的压缩比。但其算法有很大的局限性，最主要的缺陷就是编码过程需要人工干预。一、 分形图像编码的基本原理分形压缩的基本原理是利用分形几何中的自相似性原理来进行图象压缩。所谓自相似性就是指无论几何尺度如何变化，景物的任何一小部分的形状都与较大部分的形状极其相似。分形用于图像编码，总的来说可以分为两大类。一类可称作分形模型图像压缩编码，即事先对一类景

12、物建立分形模型。编码时针对具体事物提取必要的分形参数，编码传送，实现压缩；另一类可称为IFS分形图像压缩编码，即利用迭代，得到原始图像的一个近似。后一种实现方法简单，应用较为广泛。目前,图像压缩方法已有近百种,但是,压缩效果、压缩比以及编码、解码时间还不能满足当前信息时代的要求。传统的压缩算法一般已经成了定式,发展潜力不大,而分形图像压缩的思想新颖,潜力很大,在(人工干预条件下)压缩比达到10000：1时,解码图像还有很好的视觉效果,是一个很有发展前途的压缩方法。 到目前为止，用数学系统去解析地研究分形最成功的是函数迭代系统（Iterated Function System,简称IFS），它既

13、包含了确定性过程又包含了随机过程。 对现实世界中的图像集合引入Hausdorff度量，使其形成一个完备的度量空间，它的每个点既表示一幅图像，又是欧氏空间的一个紧子集。 Hausdorff 距离空间该距离空间被认为是分形所在的空间，而分形之间的距离也正是由这种Hausdorff距离度量的。 仿射变换 定义： 一个变换w:R2 R2 的形式为： w(x1,x2) = (ax1+bx2+e, cx1+dx2+f)其中a,b,c,d,e,f均为实数，则称w 为二维仿射变换，在直角坐标系中，我们可以写成如下形式： （1）实际上这是一种最广泛的线性变换,设矩阵 （2）则A 的意义可分解为旋转,伸缩,扭曲,

14、反演等。 (3) 如果已知原图及其变换图我们可以求出其中的仿射变换系数，这只要确定原图上三点和变换图上三点即可，我们可以列出以下方程： a*x1+b*y1+e=r1 （4）a*x2+b*y2+e=r2 （5）a*x3+b*y3+e=r3 （6）c*x1+d*y1+f=s1 （7）c*x2+d*y2+f=s2 （8）c*x3+d*y3+f=s3 （9）由以上六方程可求出a、b、c、d、e、f。分形图像压缩的理论基础是迭代函数系统（IFS）定理、收缩映像定理和拼贴定理。一个迭代函数系统由一个完备的度量空间和其上的一组收缩映像组成。 收缩映像定理 函数空间中的每一个收敛映像都有一个固定点，使函数空间

15、中的每一个点经过这个收缩映像的连续作用后形成的点列收敛于这个固定点。 迭代函数系统定理 每个迭代函数系统都可以构成函数空间中的一个收缩映射。于是，我们得到结论,每个迭代函数系统都决定一幅图像。一般我们用仿射变换来表示这些映射。 拼贴定理 给定一幅图像I，可以选择N个收缩映像，这幅图像经过N个变换得到N个象集每个象集都是一块小图像。如果这N个小图像拼贴起来的图像与图像I之间的距离任意小，则这N个收缩映像构成的迭代函数系统所决定的图像就任意地接近图像I。这就告诉了我们寻找迭代函数系统的方法。二、分形图像编码的实现步骤整个图像压缩的过程可以分成两大部分，一是编码过程，一是解码过程。在分形压缩中，前者

16、主要基于拼贴定理，这个过程中要考虑图像的灰度分布，以及概率求取的策略。后者主要是随机迭代问题。（一）编码主要步骤1.分割成适当的块 这可以借助于传统的图像处理技术，如边缘检测，频谱分析，纹理分析等，当然也可以使用分数维的方法。分割出的每部分可以是一棵树，一片云等；也可能稍微复杂一些，如一片海景，它包括泡沫、礁石、雾震等；一般这每一部分都有比较直观的自相似性特征。 2.IFS编码求取 每一部分求其IFS编码，这就要借助拼贴定理了，同时也是人要参与的地方，在这个过程中有一些必须注意的地方。 1）每一块的“拷贝”必须小于原块，这是为了保证仿射变换的收缩性，至于每个拷贝的大小要根据各块图像的性质来确定

17、。 2）用于拼贴的每个拷贝之间最好为不相连或紧相邻的。而不要重叠或者有空缺。这一点对概率的确定很重要，它影响到重构图像的不变测度。所以对有重叠或空缺时，这部分的“质量”在计算中不能复用或者简单地丢弃，并最终要保证 的成立。3.仿射变换的概率设定 拼贴的过程不仅要保证吸引子的形状，也要考虑到每块区域灰度分布的情况，拼贴结束时要求出各个pi，Barnsley等人采取的方法仍然是下式： （10）其中Tm表示某一分割后的图像块，这种方法有较快的计算速度，这种定义实际上是建立在均匀测度的假设上的，即吸引子上相同大小的区域有相同的“质量”。但是这在对实际的灰值图像处理过程中并不总是成立的，往往是经过某个仿

18、射变换后的区域可能面积很大，但包含的总的灰度能量可能很小；反之某些小区域却有较大的灰度能量。 为此，一般的方法是对灰度能量多的区域干脆多重叠几个相同的仿射变换。这在解码的过程中可能造成的一个结果是重构图中存在伪灰度现象；同时在随机迭代重构时总的步数也没有确定地给出，只能“足够大”，最后再把灰度归一化到0，255。为此，我们在拼贴的过程中重新定义了概率的求取，令图像块Tm能量为Qm： （11）f（i，j）表示点（i,j）处的图像灰度,则可定义概率： (12)其中分子表示Tm经wi变换后区域中的能量。这时的pi应该说可以很好地反映出了图像内部灰度分配的信息，它还可以指导图像重构，即对每一图像块重构

19、时总的随机迭代次数就可以设为该块的总能量Qm,而每一次迭代生成点的灰度能量为为1个单位。此时概率pi计算稍微比前一种方法麻烦些，在计算中可以用wi(Tm)与Tm的逻辑与来获得wi(Tm)区域的能量。（二）解码主要步骤 分形的解码步骤很简单，可以用任意的图像作为初始图像，经过存储的相应的迭代函数的若干次迭代就可以准确的恢复原图。三、分形图像压缩的发展方向 在1990年，Jaquin提出了基于块的分形图像压缩算法。虽然该算法的压缩比低于M.Barnsley,但是他的编码过程可自动进行。因此此算法已经成为这一研究方向的典型代表。Jacquin发展了IFS理论，提出了局部迭代函数理论（PIFS），他在

20、此理论基础上提出了一种基于方块划分的分形图像压缩方案，在其方案中首先将原始图像划分为固定大小的方块，然后对每一块，通过反射变换在原始图像的紧缩图像中寻找最相似的部分。这些操作可由计算机自动完成，他为分形图像压缩的研究带来了一次质的飞跃。 Jacquin提出的方案为分形压缩编码的研究注入了生机和活力，使分形编码成为目前编码研究的热点。目前分形编码方案大致有三个发展方向：加快分形的编解码速度、提高分形的编码质量、基于分形序列图像的编码。 （一）加快分形的编码速度 编码速度慢一直是分形编码实用化的最大障碍，下面分析Jacquin编码方案的计算复杂度。对于一个CC大小的图像，假设值域子块大小为KK,定

21、义域子块大小为2 K2K,则该图像共有C2/K2个值域子块，（C-K+1）2个定义域子块。在Jacquin的方案中，一个值域子块和一个定义与子块之间的相似性的计算量与K2成正比，而对于每一个值域子块，编码计算量与（C-K+1）2/K2呈线性关系，所以，对于一幅图像来说，其编码复杂度与（C-K+1）2* K2*C2/ K2=（C-K+1）2*C2成正比，因此，分形编码的计算复杂度为O(C4)。所以，减少搜索、加快编码速度是研究的热点之一。 Jacquin根据子块的复杂度将其分成四类，对每个值域子块，仅在其同类的定义域子块中进行搜索；D.Saupr采用多维最近邻搜索方法代替传统分形编码中序列的匹配

22、过程，其搜索匹配时间按指数级增长；K.F.Loe等将Jacquin方案中使用的分类器替换成模糊分类器，并使用遗传算法进行优化，该算法比未分类的编码方案快40%左右；C.K.Lee和W.K.Lee通过对匹配块之间关系的研究发现，如果两子块的自身方差相差太远，则这两个子块不可能相似，由此可去除许多不必要的匹配过程，提高压缩速度10倍以上；Min Xue等将传统编码方案中每个值域子块匹配的串行操作转换为并行操作，计算复杂度下降，缩短了压缩的时间。 （二）提高分形编码质量 目前，提高分形编码质量的方法有三种：采用混合编码方案、改进分割方案、改进灰度逼近能力等。提高编码质量的方法是对传统的分割方法进行改

23、进。Jacquin使用两次分割，在提高编码质量的同时，又避免压缩比下降太多。随后又有许多学者对上述方法继续进行改进，提出了四象限的划分方法，是分形压缩的质量和压缩速度有了较大的提高，是目前较为实用的压缩方法。目前国内外研究者还提出了基于区域的分割方案。在分形编码中常用的灰度逼近式为w(z)=s*z+t,可把灰度逼近式变为w(z)=t(z),t(z)可为任意形式，可以为二次以上的多项式，有效提高了编码效果，改进图像质量。 （三）分形序列图像编码 在实际应用中，序列图像较静态图像有着更广阔的应用，而且由于时间维的引入，编码方法也有新的变化5，因此，序列图像编码是图像编码研究的热点之一。 1994年

24、，加拿大学者Lazar等人发表了一篇论文，加入了时间维，将Jacquin的分形编码从二维变换直接推广到三维，并直接借用静态图像的分形编码方案，但这样没有充分利用桢间的相似性，压缩性能不佳。此后，又有人提出了自矢量量化的序列图像编码方案，但图像恢复质量、压缩比及编码实时上仍不是很理想。因此分形序列图像编码是当今分形压缩编码的一个重要方向。第三章 分形与其他技术相结合的改进方案分形图像压缩编码的应用已经深入到人类活动的各个方面，并已取得了令人瞩目的成果。分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相关性，适合于自相似或自仿射的图像压缩；分形图像压缩解码时能放大到任意大的尺寸，且保持精细的结

25、构；在高压缩比的情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉效果。但是对于编码虽然有许多的改进措施，但是搜索匹配时间过长还是不能满足许多实际的需要，基于此，近两年来, 很多学者和专家把分形与其它的技术和工具、方法混合编码取得了很好的效果。常用的混合方案有与小波变换结合编码、与DCT变换结合编码、与加权有限自动机结合编码、与向量量化结合编码、与遗传算法结合编码、与FFT算法结合编码、与非线性模型结合编码、与算术结合编码。近10年来,人们对于自适应块状分形编码进行了不懈的研究,提出了以上若干改进算法,这些算法在不影响视觉效果的条件下,大大减少了编码时间。而且在高压缩比和解码图像任意放大

26、方面,比现有的静态图像国际压缩标准JPEG好得多,已经开始显露出它的优势。分形图像编码方法的实际应用也初见端倪,如分形图像压缩解码速度很快,当前已经适合于一次写入、多次读出的文档。一、 提高压缩比和编码效果常用的改进方法（一）改进分割的方法 有基本四叉树分割法、基于HV分割法。这两种分割方法都是将图像分割成矩形。而图像块的相似性未必都落在矩形内。代替水平或垂直剖分而采用的分割方法有基于三角形分割法、基于六边形分割法、基于边界分割法、基于菱形分割法、基于多边形分割法。 （二）改进覆盖式方法 覆盖式方法有快速覆盖式分形压缩方法和四叉树重组QR算法两种它们都是采用通过合并值域块来提高压缩比。前者要求

27、合并后不一定规则,后者合并后则是规则的。 （三）提高显示效果的后处理法 分形图像压缩对值域块独立编码,这不能保证块与块之间的连接是光滑的,常有块效应出现,人的眼睛对此比较敏感。消除块效应的一个常用方法是后处理,一般采用加权平均法。二、 DCT与分形混合编码 自从分形图像压缩作为一种实用的方法由Jacquin首次提出以来，大多数关于分形图像压缩的研究都集中在时间域进行，为了提高编码性能，一些变换域变换编码方法相继由Barthel等提出。其中离散余弦变换(Discrete consine transformationg),余弦调制滤波器组（Cosine modulated filter banks

28、）和小波变换等应用最为广泛，小波变换与分形的结合在上面已经作了简要地介绍。在这里我们介绍一下DCT与分形的混合编码方案。 分形图像编码的原理是要寻找一组收敛的仿射变换来重建图像，利用同一图像中一部分描述另外一部分，即利用图形的自相似性来减少图像的冗余度。频域变换的一个突出优点就是他的能量紧凑特性，一幅图像经过频域变换后，总能量没有变化，但能量的分布却发生了变化。能量将集中在它的低频部分，而高频部分所占的能量非常少，能量的这种分布对分形压缩十分有利，因为分形图像压缩的主要过程是对同样大小的图像块进行能量匹配，经过频域变换后，高频部分在能量匹配过程中产生的误差很小，基本可以忽略不计，这就等于减少了

29、匹配块的大小，从而减小了匹配误差。 去相关能力最强的是K-L变换，但由于其难以实现，人们转而寻找能实时处理的次最佳变换，离散余弦变换就是其中的一种。近年来的研究表明，离散余弦变换是一种最接近最佳的正交变换，性能接近K-L变换。 主要编码步骤： （1）设原图像的大小为N*N，首先把它划分为（N/8）2块大小为8*8的区块（range block）,对所有的作DCT变换，得到一个N*N的区图像（rang image）。接着，将原图像在划分为（N/16）2块16*16的域块（Domain block），对所有的域块作DCT变换，然后再经过变换后的16*16图像块中取出他的左上角8*8的块，这些块按照

30、原图的顺序组成一个域块库。之所以只取图像左上角是因为域块在经过变换后，主要信息都保存在低频区，对应于图像块的左上角，而高频区所占的能量相对较少，在以后的匹配中，起的作用很小。因此，在构成域块时，我们只取左上角与区块同样大小的一部分。 (2)接下来则是利用图像的自相似性进行分形压缩，其实质是寻找一组仿射变换，即块匹配过程。它与时域的块匹配过程完全相同。但由于图像经过频域变换后，具有与时域不同的特点，因此在具体的实现方法上存在着一些差别。首先：图像在经过DCT变换后,能量集中到低频部分，特别是它的直流分量，占据了整幅图像能量的很大一部分，这就使得我们必须对它们单独处理，而不把它带入块匹配的过程中。

31、在匹配过程中，均值分量也就不再需要。在DCT域分形编码中，我们是将这些直流分量直接作差分之后再进行量化、熵编码。这样做不仅减少了块匹配的误差，而且在解码时，在第一次迭代过程中，就可以得到直流分量，从而加快了解码的收敛速度。其次，图像块在经过DCT变换后，能量分布具有一定的规律，不同于在时域中的杂乱无章的分布，因此在块匹配过程中，旋转所带来的性能上的改进将变得非常小，与此同时，它却增加了所需的比特数，降低了压缩比。所以我们建议在DCT分形压缩的块匹配过程中，我们不采用旋转因子。 （3）经过块匹配之后，将阈块的位置信息和仿射变换的系数（这里只有收敛因子）进行熵编码，以进一步提高压缩比。编码算法可以

32、选用哈夫曼编码或是算术编码。 为了加快编码速度，降低编码的复杂性，有人提出了选择性块匹配的编码方案，也就是对那些平坦块不去进行块匹配，而是把它的直流分量直接编码输出。感兴趣的读者可以参阅相关的文献介绍，在这里由于篇幅有限，就不多做介绍。三、 小波分形混合图像编码 小波图像编码和分形图像编码是两种不同的图像编码方法。其中，小波图像编码是把图像分解成不同的空间方向和不同分辨率的子带图像，人们可以根据需要，对不同子带图像采用不同的量化策略来进行编码6；而分形图像编码则适用于自相似性较强的图像。可惜的是，一般的自然图像自相似性并不是很强，但是经过小波变换后的图像，其相同方向但不同分辨率的子带图像却具有

33、较强的相似性5,10。因此，人们可以利用这种相似性，结合分形编码的方法来进行编码，以大幅度地提高图像编码的压缩比。因此，小波分形混合图像编码已成为今后的发展趋势。 经过多级小波变换，一幅图像被分解为一系列尺度、方向、空间局部变化的子带。由于小波变换能获得很好的空间-频率多分辨率表示，而且在低频处有很好的频率特性，在高频处有很好的空间选择性，因此符合人类的视觉特性11，能量主要集中在低频子图像。而且同方向不同分辨率的子带间具有相似性，可以利用分形，二者优势互补，给二者进行混合编码提供了条件。在传统的分形图像编码中，由于寻找最佳匹配块需要进行大量计算，从而编码时间过长，而利用小波分解后，图像块所具

34、有的独特空间-频率特性，可以构造较好的分类和搜索方法，因而大大加快了分形编码的速度。四、 提高编码和解码速度的方法（一）提高编码速度在编码过程中最耗时的是搜索最佳匹配的定义域块,要提高编码速度,就必须缩小搜索范围,且保证最佳匹配落在该范围之内。其改进方法有: 1.分类法 ：搜索最佳匹配计算量很大,占用了编码的大部分时间,因而限制了它的实际应用。为了缩短搜索时间,在匹配之前按照图像的特征如中值、方差、矩和其它感知或统计的几何特征,将定义域和值域块进行分类,匹配时只在同一类中进行搜索比较。这样在不降低图像质量的前提下,大大提高了编码速度。常用的分类方法有:基于明暗度的定向分类、基于空域特征的分类、

35、基于相对矩的分类、基于小波的分类、基于人类视觉系统(HVS)分类、基于模糊分类、原形的分类、自适应码本簇化的分类、向量量化的分类。以上各种方法分别从不同的角度、使用不同的工具对图像块分类,各自保持了自己的特点,对加速编码有不同程度的作用。 2.搜索法 ：匹配搜索耗时最长,常用的加速搜索方法有:局部搜索法、提取特征追踪法、基于方差搜索法、FFT搜索法。 （二）提高解码速度分形解码速度相对于编码要快得多,一般它迭代10次即可完成。然而对于一些实际应用来说,仍然希望迭代次数越少越好,这样可以进一步加快解码速度。常用的加速方法有金字塔式解码器、去均值解码算法、非迭代算法、BCC和ICC算法。第四章 仿

36、真实验一、 分型图像压缩流程图 读取父块、子块和原图尺寸信息初始化解码空白图像将复原的子图想放到原图像相应的位置恢复出压缩前的图像结束根据分行码，将找到的父块经适当变换找到所有字块，经拼贴形成一次迭代图像是否达到迭代次数YN将图像分割为子块与父块读入图像找出子块与父块像素点平均值的最小值结束存储各项参数读取原始图像灰度值将压缩后的父块进行8次变换计算最小误差和误差值误差值是否小于或等于给定误差YN分形图像压缩的编 分形图像压缩的解码过程流程图 码过程流程图二、实验环境与所需步骤（一）实验环境： 在实验时采用的硬件和软件平台为CPU T6500 2.1G，RAM 2G，操作系统Windows X

37、P，开发语言为MATLAB 7.11.0（二）仿真步骤： 1.编码过程 （1）读入图像，读取原始图像的灰度值 （2）将原始图像分割成8*8和16*16的像素图 （3）借助拼贴定理，对每一部分求其IFS编码，每个收缩后的父块进行8种变换（矩阵0度旋转，矩阵水平中线反射，矩阵垂直中线反射，矩阵180度旋转，矩阵相对135度反射，矩阵90度旋转，矩阵270度旋转，矩阵相对45度反射），进行匹配运算，对每一个子图在图像中寻找一块与之最匹配的父图 （4）存储迭代函数，找出最佳匹配块，记下坐标值和应用误差值，一次完成对原图像的编码，从而实现图像的压缩2.解码过程 （1）从分形编码文件中读取子图，父图以及原

38、图尺寸的信息 （2）根据所得的数据，定义两个和原图一样大小的图像区：R区和D区。R区用来保存迭代过程中所生成的图像，D区用来产生码本Q。 （3）初始化解码空白图像（4）对于R区中每个R块Rj，根据分形文件中的分形码，在D区中找到相应的Di块，经过适当变换得到所有的R块后，经拼贴就形成了一次迭代的图像。 （5）将R区的图像复制到D区。（6）如果迭代次数达到预定次数则停止，否则重复步骤(2)一(5)。（7）所有R区块解码完成则解码图像完成。三、实验程序outfp = fopen(imfrcode_2.txt,w);Is = imread(a.jpg);Is = rgb2gray(Is);m,n =

39、 size(Is);m16 = ceil(m/16);n16 = ceil(n/16);I(1:16*m16,1:16*n16) = 0;I(1:m,1:n) = Is;Ns = 0;Nb = 0;fprintf(outfp,原始图像的灰度值为：n);for i = 1:16*m16 for j = 1:16*n16 fprintf(outfp,%4.0f,I(i,j); end fprintf(outfp,n);endfor i = 1:2*m16 for j = 1:2*n16 Ns = Ns + 1; Small(1:8,1:8,Ns) = I(8*i-7:8*i,8*j-7:8*j);

40、 endendfprintf(outfp,n原始图像所分成的子图个数为：%4.0fn,Ns);for i = 1:m16 for j = 1:n16 Nb = Nb + 1; Big(1:16,1:16,Nb) = I(16*i-15:16*i,16*j-15:16*j); endendfprintf(outfp,n原始图像所分成的父图个数为：%4.0fn,Nb);for i = 1:Nb for j = 1:8 for k = 1:8 Temp4 = Big(2*j-1:2*j,2*k-1:2*k,i); Big2(j,k,i) = sum(Temp4(:)/4; end endendfor

41、 i = 1:Nb Temp8 = Big2(1:8,1:8,i); TrBig(1:8,1:8,i*8-7) = Temp8; TrBig(1:8,1:8,i*8-6) = fliplr(Temp8); TrBig(1:8,1:8,i*8-5) = flipud(Temp8); TrBig(1:8,1:8,i*8-4) = rot90(Temp8); TrBig(1:8,1:8,i*8-3) = rot90(rot90(Temp8); TrBig(1:8,1:8,i*8-2) = rot90(rot90(rot90(Temp8); TrBig(1:8,1:8,i*8-1) = Temp8;

42、TrBig(1:8,1:8,i*8) = rot90(flipud(Temp8);endfprintf(outfp,n各子图对应的参数及父图位置为：n);for i = 1:Ns Temp8 = reshape(Small(1:8,1:8,i),1,64); for j = 1:8*Nb Temp = reshape(TrBig(1:8,1:8,j),1,64); Temps = (64*sum(Temp8.*Temp) - sum(Temp8)*sum(Temp) . / (64*sum(Temp.2) - (sum(Temp)2); Tempo = (sum(Temp8) - Temps*

43、sum(Temp) / 64; Temph = sum(Temps*Temp + Tempo - Temp8).2); %Temph = (sum(Temp8.2) - Temps*(Temps*sum(Temp.2) . % - 2*sum(Temp8.*Temp) + 2*Tempo*sum(Temp) + . % Tempo*(64*Tempo - 2*sum(Temp8) / 64; if j = 1 Hmin = Temph; Fs(i) = Temps; Fo(i) = Tempo; XY(i) = ceil(j/8); Tw(i) = mod(j,8); else if Temp

44、h Hmin Hmin = Temph; Fs(i) = Temps; Fo(i) = Tempo; XY(i) = ceil(j/8); Tw(i) = mod(j,8); end end endfprintf(outfp,s值：%8.5f o值：%8.5f XY值：%4.0f Tw值：%2.0fn,.Fs(i),Fo(i),XY(i),Tw(i);endfprintf(outfp,n解码过程：);Inew(1:16*m16,1:16*n16) = 0; % 解码过程for n = 1:8 Nr = 1; fprintf(outfp,n迭代过程%3.0f的生成图像素为：n,n); for i

45、 = 1:16*m16 for j = 1:16*n16 fprintf(outfp,%4.0f,Inew(i,j); end fprintf(outfp,n);endfor i = 1:2*m16 for j = 1:2*n16 Tx = ceil(XY(Nr)/n16); Ty = XY(Nr) - (Tx-1)*n16; Temp16 = Inew(16*Tx-15:16*Tx,16*Ty-15:16*Ty); Temp8 = m16to8(Temp16); switch Tw(Nr) case 0 Temp8 = rot90(flipud(Temp8); case 1 Temp8 =

46、Temp8; case 2 Temp8 = fliplr(Temp8); case 3 Temp8 = flipud(Temp8); case 4 Temp8 = rot90(Temp8); case 5 Temp8 = rot90(rot90(Temp8); case 6 Temp8 = rot90(rot90(rot90(Temp8); case 7 Temp8 = Temp8; end Inew(8*i-7:8*i,8*j-7:8*j) = Fs(Nr)*Temp8 + Fo(Nr); Nr = Nr + 1; end end endIgray = mat2gray(I);Inew =

47、mat2gray(Inew);subplot(1,2,1),imshow(Igray);subplot(1,2,2),imshow(Inew);fclose(outfp);函数m16to8（将16*16的图象块通过平均变成8*8的图象块）：function y=m16to8(x)y=zeros(8,8);for i=1:8 for j=1:8 a=x(2*i-1:2*i,2*j-1:2*j); y(i,j) = sum(a(:)/4; endend五、仿真结果 1、原图2.分型图象压缩数据（具体数据见附录） s:：比度调节系数 o：亮度调节系数 XY：大区域编号 Tw：变换方式3.原图像及还原

48、后的图像第五章 结论10多年来，虽然分形图像自动编码和解码不断改进但仍然不够成熟，产生的压缩比不够高，压缩效果还不十分理想，在当前图像压缩编码中还不能占据主导地位。国际标准MPEG-4中已经把小波列了进去，但分形不在其中。静态图像压缩标准JPEG2000是完全使用小波的图像编码方法，也没有把分形列进去。但我们应该看到分形图像压缩方法的优势和巨大潜力。 l 分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相关性，适合于自相似或自仿射的图像压缩，而自然界中存在大量的自相似或自仿射的几何形状。因此，它的适应范围很广。 l 分形图像压缩（当前尚须人工干预）能获得相当高的压缩比(10000：1甚至更

49、高)和很好的压缩效果，具有很大的潜力。 l 分形解码时能放大到任意大的尺寸，且保持精细的结构。 l 在高压缩比的情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉效果，这是其它方法不能相比的。 因此分形图像压缩是一个有潜力、有发展前途的压缩方法。 分形图像压缩编码研究发展趋势将有如下几个方面： l 分形编码在人工干预条件下能够达到相当高的压缩比。但对于如何去掉人工干预则需研究给定的图像，实现计算机自动确定分形生长模型、 L系统、IFS码和RIFS码等，寻找新的压缩模型和新的突破点。 l 综合分析当前自动编码的各种改进算法，在此基础上，继续寻找加快编码速度、提高压缩比、改善压缩效果的突破性

50、的改进方法。 l 研究按分形维数分割图像、将分形维数相同的区域块用分形方法进行编码的理论、方法和实现的算法。 l 继续研究分形编码与其它编码方法相结合的新的编码方法。 研究新的度量相似性的准则，在保持压缩比的前提下，降低恢复图像的失真率。参考文献1 迟健男,宋春林,杨旭,一种新的快速分形图像压缩方法,辽宁省交通高等专科学校学报,2004.3, 6(1):21-24 2 Hurtgen B,Mols P,Simon S F. Fratcal transform coding of color images.SPIE Vis Commun Image Process,1994,2308:1683-

51、1691 3 J.H. van Hateren and A. van der Schaaf, Independent component filters of natural images compared with simple cells in primary visual cortex. it Proc.R.Soc.Lond. B, 265:359-366, 1998. 4 吴蓓,翟娟娟,李晓辉,基于视觉特性的分形图像压缩编码,信息技术,2002,10 5 K. Koroutchev and J. Dorronsoro, Hash-like Fractal Image Compressi

52、on with Linear Execution Time, Iberian Conference on Pattern Recognition and Image Analysis, IbPRIA 2003. 6 万卫兵,施鹏飞,基于分形和小波的混合图像压缩,中国体视学与图像分析,2002.9, 12(3):45-50 7 D. Saupe, R. Hamzaoui, and H. Hartenstein, Fractal image compression: an introductory overview, in: Fractal Models for Image Synthesis,

53、Encoding, and Analysis, D. Saupe and J. Hart (eds.), SIGGRAPH 96, New Orleans, 1996. 附 录注： s:：比度调节系数 o：亮度调节系数 XY：大区域编号 Tw：变换方式Tw值： 0为矩阵0度旋转 Tw值： 4为矩阵180度旋转Tw值： 1为矩阵垂直中线反射 Tw值： 5为矩阵270度旋转Tw值： 2为矩阵水平中线反射 Tw值： 6为矩阵相对45度反射Tw值： 3为矩阵90度旋转 Tw值： 7为矩阵相对135度反射仿真实验分形图像压缩数据：s值： 0.06244 o值：26.78730 XY值： 103 Tw值：

54、 6s值： 0.86764 o值：11.44554 XY值： 76 Tw值： 0s值： 0.81260 o值：15.01807 XY值： 107 Tw值： 2s值： 0.84056 o值： 8.06776 XY值： 70 Tw值： 7s值：-0.93865 o值：228.44447 XY值： 50 Tw值： 6s值： 1.06826 o值：21.00629 XY值： 107 Tw值： 2s值： 5.42789 o值：36.59971 XY值： 118 Tw值： 0s值： 0.89085 o值：58.52606 XY值： 116 Tw值： 6s值： 0.93165 o值：14.57885 XY值

55、： 108 Tw值： 3s值： 0.99366 o值：32.70083 XY值： 116 Tw值： 3s值： 0.92759 o值： 0.96922 XY值： 92 Tw值： 0s值： 0.06446 o值：23.02569 XY值： 26 Tw值： 3s值： 0.96464 o值：18.19278 XY值： 86 Tw值： 5s值： 0.93479 o值：67.28423 XY值： 101 Tw值： 3s值： 0.79469 o值：15.51959 XY值： 11 Tw值： 7s值：-0.98183 o值：235.55938 XY值： 50 Tw值： 6s值： 0.97493 o值：36.9

56、5078 XY值： 84 Tw值： 1s值： 0.95093 o值：28.99080 XY值： 80 Tw值： 2s值：-5.63434 o值：233.37569 XY值： 118 Tw值： 0s值：-0.70194 o值：205.25157 XY值： 45 Tw值： 6s值： 1.00816 o值：12.19398 XY值： 107 Tw值： 4s值： 0.09640 o值：-1.93640 XY值： 27 Tw值： 1s值： 0.42744 o值：11.55621 XY值： 1 Tw值： 7s值：-4.89230 o值：202.47211 XY值： 118 Tw值： 1s值： 0.9857

57、1 o值：14.93724 XY值： 11 Tw值： 3s值：-0.98507 o值：244.86513 XY值： 80 Tw值： 0s值： 0.44913 o值：10.24048 XY值： 1 Tw值： 5s值： 0.07164 o值：23.27015 XY值： 74 Tw值： 1s值：-0.84551 o值：226.39508 XY值： 84 Tw值： 3s值：-0.77831 o值：227.76796 XY值： 71 Tw值： 5s值： 0.72183 o值：11.29626 XY值： 61 Tw值： 6s值：-0.97872 o值：228.67812 XY值： 71 Tw值： 1s值：

58、-0.93204 o值：236.00917 XY值： 71 Tw值： 2s值： 0.04674 o值：21.88126 XY值： 2 Tw值： 6s值：-0.05973 o值：32.36427 XY值： 67 Tw值： 7s值： 0.99386 o值：19.53937 XY值： 43 Tw值： 3s值： 0.76635 o值：14.06239 XY值： 70 Tw值： 7s值： 0.90699 o值：43.54250 XY值： 50 Tw值： 3s值：-0.05404 o值：30.46811 XY值： 35 Tw值： 6s值： 0.50752 o值：13.82699 XY值： 87 Tw值：

59、7s值： 0.99041 o值： 8.96774 XY值： 109 Tw值： 1s值： 0.05142 o值：16.62598 XY值： 37 Tw值： 7s值： 0.05736 o值：18.82414 XY值： 54 Tw值： 3s值： 0.12293 o值：-3.03263 XY值： 71 Tw值： 5s值：-0.88541 o值：212.83790 XY值： 50 Tw值： 7s值： 1.00067 o值：17.63618 XY值： 107 Tw值： 0s值：-0.88709 o值：214.04326 XY值： 80 Tw值： 5s值： 1.05989 o值：10.96769 XY值：

60、42 Tw值： 4s值： 0.96839 o值： 2.27733 XY值： 109 Tw值： 6s值：-0.82702 o值：225.59963 XY值： 50 Tw值： 5s值： 0.69301 o值：22.90832 XY值： 114 Tw值： 4s值： 1.03012 o值：25.16087 XY值： 108 Tw值： 7s值： 0.84386 o值：12.57536 XY值： 83 Tw值： 7s值： 0.11593 o值：21.95026 XY值： 98 Tw值： 7s值： 0.85865 o值：26.86843 XY值： 16 Tw值： 7s值： 1.05668 o值：43.18809 XY值： 116 Tw值： 3s值：-0.77680 o值：229.38013 XY值： 84 Tw值： 6s值：-0.87114 o值：242.96397 XY值： 1 Tw值： 5s值： 1.0