多媒体技术11分形压缩课件

第11章分形编码分形压缩的基本思想是，利用数据的自相似或自仿射特征，构造相应的局部迭代函数系统，从而只需要少量的数据就可以恢复与原图象相近的图象，达到压缩图形数据的目的本节先介绍分形和迭代函数系统的基本内容，然后讨论分形压缩的具体方法，最后给出若干图象的分形压缩的实例一．分形分形(fractal)是法国数学家BenoitB.Mandelbrot于1975年在创立分形几何学(fractalgeometry)时所造的一个新词，指具有一定自相似性的复杂不规则形体，一般为自然界中的物体和形态随机分形：如海岸线、云彩、山川、水系、树、烟雾、波浪、草坪、纹理和湍流等，这些都是随机分形，具有统计自相似性数学分形：如Koch曲线、Sierpinski地毯、Mandelbrot集、Julia集、L系统和分数布朗运动等规则的数学分形，具有严格自相似性1．Mandelbrot集和Julia集复动力系统——Mandelbrot集和Julia集，是由复迭代公式z=z2+C (1)

确定的收敛集，其中：z=x+iy,C=a+ib为复变量Mandelbrot集：若固定C，让(1)式每次从某个固定z0=x0+iy0（如x0=0,y0=0）开始进行无穷迭代，当其发散到无穷大时（可用|z|2=x2+y2>4来判断），用发散速度（迭代次数）来给C平面上所对应点着色，则在a：-2.2~0.6、b：-1.25~1.25的区域内，可得到变幻无穷且能无穷放大的美丽图案Mandelbrot集2Mandelbrot集3Julia集若固定C，让Z0在一定区域（如|x|<1.75,|y|<1.75）内变化，则(1)式迭代的收敛集为Julia集也可以似前M集着色，所得图形也非常美丽2．分维分维(fractaldimension)是分形的核心概念要测量复杂的形状的长度、面积或体积不仅是非常困难的事，有时甚至是不可能的，如英格兰的海岸线长度，中国地表的面积，一棵大榕树的体积等等。解决办法之一，是测量它们的复杂程度，所用的度量工具就是形体的维数一般来说，一个物体的维数D、线度（直径）l和测度（即一维形体的长度、二维形体的面积或三维形体的体积等等）m有如下关系式：lD=m (1)如线度扩大一倍（2l），则长度也扩大一倍（(2l)1=2l）、但面积则扩大到4倍（(2l)2=4l2）、而体积则扩大到8倍（(2l)3=8l

3）分维的计算从(1)式容易推导出维数的计算公式：这里的维数（分维）D不必是整数，可以是小数或分数，所以又叫分数维。如Koch曲线的分维D=ln4/ln3=1.2618Peano曲线的分维D=ln4/ln2=2Sierpinski三角地毯的分维D=ln3/ln2=1.5850复杂的不规则物体，其分维一般大于其拓扑维数，将这样的形体称为分形二．迭代函数系统MichaelF.Barnsley于1985年提出的迭代函数系统(IteratedFuctionSystems，IFS)是构造分形的有力工具，而分形压缩的图像是作为迭代函数系统的不变集出现的，它们本质上是一些压缩仿射变换迭代函数系统的思想虽然早已见于J.Hutchinson于1981年所写的论文，但其命名及系统研究与应用却应归功于Barnsley。他不仅提出了IFS的随机迭代算法，还将IFS成功地用于分形插值函数的构造及分形图像的压缩1．迭代函数系统的概念设(K，d)是一个紧度量空间，一般取K为Rn的一个紧子集(即有界闭集)，取d为Euclid度量若wi

(i=1，2，...，N)是K到K的连续映射，记w={w1，w2，...，wN}，则称{K，w}为迭代函数系统若wi：K→K是连续压缩映射，即对任意x，y∈K，存在压缩因子si，0≤si<1，使 则称{K，w}为压缩(compact)或双曲(hyperbolic)迭代函数系统，以下简称其为IFSIFS与分形记 设H为K的所有非空子集组成的集合，h为Hausdorff度量： 则(H，h)也是紧度量空间定义W：H→H为 其中wi(A)={wi(x)：x∈A}，则W为一压缩映射若G∈H，且W(G)=G，则称G为此IFS的吸引子或不变集。这样的不变集通常都是分形，其分维D满足下列等式：2．生成IFS不变集的方法生成IFS不变集的方法有两种，一种是确定性方法，另一种则是被称作“混沌游戏”的随机方法，限于篇幅这里对它们不作系统讨论下面介绍的只是一种二维IFS的具体生成方法设 ，定义压缩变换wi：K→K如下：(i=1，2，...，N)仿射变换其中 为一压缩矩阵，可取元素

(2)

其中ri、θi、ei分别为x的压缩因子、旋转角度与位移，qi、φi、fi分别为y的压缩因子、旋转角度与位移显然wi可视为压缩、旋转与平移的合成，是一类典型的仿射变换。ri、θi、ei、qi、φi、fi取不同的值就得到不同的wi，不同的wi与N对应于不同的IFS，从而可得不同的不变集(分形)G随机迭代算法随机迭代算法——从任意位置的一点出发，随机选择一wi对点进行映射，循环迭代迭代中随机选择wi的概率pi取为对为零的pi可用一很小的正数(如0.001)代替下列图例是用随机迭代算法作出的IFS的不变集螺线Koch曲线三角Sierpinski垫羊齿叶青草3．局部迭代函数系统上面所介绍的IFS方法中，每个压缩仿射变换wi都作用于所有区域，所以只能生成全图是一整个严格自相似或自仿射分形的图形但一般的图象显然不是一个整体分形，而只是它的一些部分之间存在某种相似或仿射性。解决这一问题的办法是将区域A分割成若干（可以相交的）小块Ri，并使每个压缩仿射变换wi都局限在一个小块区域Ri上这需要将IFS定义中的 改为 即得局部迭代函数系统（LIFS=LocalIFS）由拼接定理可知，将各个局部仿射变换的结果拼接起来就能得到整个区域的仿射变换灰度平移变换图象是一种二维数据，灰度图为多值数据（一般为256个值）上一节所讨论的局部迭代函数系统LIFS虽然可以直接处理二维二值数据，但对多值数据还得略加改造改造的方法是在原有的压缩、旋转、位置平移等变换的基础上，再加上灰度平移变换。即灰度变换：g(x,y)=g(x,y)+gshift三．分形压缩方法从上小节可知，由IFS可以生成各种分形图形，但是反过来如何从一个已有的图象找出生成它的IFS呢？这正是分形压缩所要解决的关键问题虽然Barnsley早在1987年就提出了分形压缩的基本思想，但开始时需要借助于人工干涉来寻找每个图象的IFS，不适合计算机自动处理。后来虽然发展了若干分形压缩方法和技术，但出于商业考虑，一直不为外人所知直到1993年Barnsley出版了分形图象压缩的专著，透漏了其中的一些基本方法，才让人们对分形压缩有所了解1．分形压缩的基本原理图象数据的分形压缩是利用图象的自相似和自仿射性质，寻找生成该图象的若干局部IFS，将所得的局部IFS参数保存起来，形成编码文件（即压缩后的图象），这就是编码过程至于解码过程，是从任意一个初始图象出发，用编码文件中的局部IFS参数，经过若干次迭代生成不变集，所得到的就是与原图象近似的一个图象分形压缩的具体方法压缩过程：先将原图分成若干块，针对每一块，在原图中进行各种压缩、旋转、位置平移、和灰度平移变换，寻找该块的最佳匹配块然后将其压缩比、旋转操作、位置坐标、及灰度平移量作为一个局部IFS参数组记录下来，形成编码文件还可以再用其他无损压缩方法再对该文件进行进一步的编码压缩解压缩过程：（与上面刚好相反）先用无损压缩的解码方法还原局部IFS编码文件然后任意给定一个初始图象，并将图象象编码时一样地分块，接着按编码文件中的参数进行一遍各个块的局部IFS变换，得到一个迭代图对该图进行同样的分块和变换得到下一个迭代图；如此下去，直到所得到的迭代图不再改变（收敛到不变集）为止最后所得的图象就是原图象的一个近似2．分形压缩的简化方法考虑到实际图象是离散数据，不能进行连续的压缩、旋转、位置平移、和灰度平移变换再考虑到计算机的计算能力，即使对这些变换的离散变换也不能穷尽各种可能下面介绍一种简化方法：为了简单起见，将图象等分成若干正方小块，只考虑两倍的纵横等比压缩，只进行横向、纵向、对角三种镜象变换，考虑逐点的位置平移，灰度平移是对整个小块的平均灰度进行的即取局部IFS参数中的从而位置和灰度变换简化为： 和 g(x,y)=g(x,y)+gi1）压缩过程分形压缩的具体算法及过程如下：从磁盘文件中读入原图象到内存，并确定等分块的大小由原图得到减半图（用原图中相邻四点的灰度的平均值作为减半图中一点的灰度值）在减半图中寻找原图中每一小块的最佳匹配块，具体方法如下计算原图小块的平均值对减半图从左到右、从上到下逐点循环计算减半图中每一小块的平均值，与原图小块的平均值比较得到灰度平移值：gi，并对减半图的小块镜象灰度平移变换：g(x,y)=g(x,y)+gi

对灰度平移后的减半图小块施行各种镜象变换θk

，φk

，k=1,2,3,4计算每种变换后的小块与原图小块的灰度误差平均值；在减半图的所有小块中，以灰度误差平均值最小的小块为原图小块的最佳匹配块，对应的变换为最佳变换；将最佳匹配块的左上角的坐标(xi，yi)、对应的变换编号(ki)、灰度平移值gi作为原图一小块的局部IFS参数；将原图的每个等分小块的最佳匹配块的局部IFS参数组Pi=（xi，yi，ki，gi）存入磁盘中，得到压缩图象的编码文件

2）解码过程解压缩过程与压缩过程类似，只是顺序相反，且没有寻找最佳匹配块的过程，所有要简单的多解压缩的具体算法与过程如下：任意给定一个与原图大小相等的初始图象（如每点的灰度值都为128），由该图得到减半图（方法同压缩时的）将初始图象按压缩时的大小等分，依次读入编码文件中的局部IFS参数组Pi

=（xi，yi，ki，gi）按参数中的坐标（xi，yi）确定减半图中最佳匹配块的位置，并按参数gi及k=ki对此匹配块进行灰度平移（g=g+gi)与镜象变换：将变换后的匹配块写入初始图中，对所有的等分块都这样做后就得到迭代图象再对迭代图按如上四步操作，可得到下一个迭代图象，如此下去直到迭代图不再改变（收敛到不变集）为止（一般6~10次迭代就够了）最后所得的迭代图就是原图象的一个近似图象图象的分形压缩与解压缩的过程框图问题与改进上述方法中没有考虑对LIFS编码文件进一步的无损压缩图象压缩倍数完全由象素的分块大小确定，如4×4象素分块压缩2倍、8×8象素分块压缩8倍、16×16象素分块压缩32倍这种简化分形压缩方法，由于进行简单的等分而产生了明显的高频分块效应，另外由于只考虑了两倍压缩和有限的几种旋转变换，所以复原效果不太理想若采用图象处理领域中其他的一些自适应分块方法，可改善高频分块效应；若多考虑一些不同比例的压缩变换及各种旋转镜象变换，可以提高复原效果。不过这样一来会大大加大处理难度与计算量3．压缩实例分形压缩方法的计算量很大，如用前面介绍的简化方法，采用486DX2/66的PC机，一幅128×128象素的256级灰度图需要26分多钟、256×256象素的图耗时近8个小时、512×512象素的图则得5天半但是解压缩的计算量却相当小，一般只需要几秒钟就够了。下图是两种256级灰度图象的分形压缩情况：灰度图象的分形压缩（128×128象素）上排为Lena图像，下排为云图每排从左到右：原图、压缩2倍、压缩8倍、压缩32倍MSS遥感图象的分形压缩（128×128象素）上排为第一波段，下排为第四波段每排从左到右：原图、压缩2倍、压缩8倍、压缩32倍分析与改善从图中可以看出，用简化的分形压缩方法压缩，有明显的高频分块效应，且随着压缩倍数（分块大小）的增加，分块效应越来越大另外由于考虑的压缩比例和变换种类太少，复原效果不太好，随着压缩倍数的增加，复原图与原图的误差越来越大，压缩32倍的图象几乎面目全非