非线性07分形及其在图象处理中的应用资料

1、第七章 分形理论及其在图像处理中的应用前面我们介绍了非线性电路的基本概念及原理以及混沌的相关理论，本章我们介绍非线性科学的另一个重要的概念分形。分形形态在自然界中是非常普遍的，分形理论为我们研究自然界的复杂事物的客观规律及其内在联系提供了新的概念和方法；分形具有广阔的应用前景，许多传统的科学难题，由于分形的引入而取得显著进展。80年代初国外开始的“分形热”经久不息。美国著名物理学家惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。所以在本书中单独把分形列为一章来讨论和研究。分形与混沌有许多共同之处，二者形影不离，互相交叉。混沌学研究的是运动过程，是物理学; 分形学研究的是静态图形，是几

2、何学。本章的内容是依据分形理论的产生、发展，及在图像编码中的应用算法以及发展趋势这样一个流程而展开的。在本章最后介绍了分形与其它技术的有效的结合。如果读者对分形理论已经有了一定的了解，可以跳过第一第二节，直接阅读第三节。第一节 自然界的分形现象生活在北方的读者对雪花是不陌生的，那晶莹剔透的雪花曾引起无数诗人的赞叹。但若问起雪花的形状是怎样的，能回答上来的读者不一定很多。也许有人会说，雪花是六角形的，这既对，但又不完全对。雪花到底是什么形状呢？1904年瑞典数学家科和（koch）讲述了一种描述雪花的方法。先画一个等边三角形，把边长为原来三角形边长的三分之一的小等边三角形选放在原来三角形的三条边上

3、，由此得到一个六角星；再将这个六角星的每个角上的小等边三角形按上述同样方法变成一个小六角星如此一直进行下去，就得到了雪花的形状，如图7-1所示。 图7-1 一种描述雪花的方法从上面的描述过程我们可以看出：原来雪花的每一部分经过放大都可以与它的整体一模一样，小小的雪花竟然有这么多学问。现在已经有了一个专门的数学学科来研究像雪花这样的图形，这就是20世纪70年代由美国计算机专家曼德布罗特（Mandelbrot）创立的分形几何。所谓分形几何就是研究不规则曲线的几何学。目前分形几何已经在很多领域得到了应用16,18,162,163。再来看图7-2所示的一组图形，是不是对分形有所认识？（参见光盘文件MA

4、T1070.MAT） 图7-2 一种分形三角形的画法细心的读者会发现这两组图形中包含了很多相似形（形状相同，大小不一定相同）。这种图形的特点就是图形的每一部分都和它本身的形状相同，我们叫它自相似形。自相似图形属于分形图中的一种。通过计算机处理后，我们可以把一个简单的图形变成非常漂亮的分形图。分形理论建立于20世纪70年代末，30年来却震惊着世界科学界，被科学界列入20世纪的20项重大科学发现之一。众所周知，基于传统欧几里得几何学的各门自然科学总是把研究对象想象成一个个规则的形体，而人类虽然熟悉却无法描述的自然界许许多多真实的图形竟如此不规则和支离破碎，与欧几里得几何图形相比，拥有完全不同层次的

5、复杂性。现代科学研究面对起伏蜿蜒的山脉、坑坑洼洼的地面、曲曲折折的海岸线、层层分叉的树枝、支流纵横的水系、翻腾变幻的浮云、地壳上的褶皱、密布人体周身的血管、满天闪烁的繁星、撕裂夜空的闪电、魔鬼般跳跃的火焰、船尾湍急的涡流、拍岸的惊涛与浪花、金属和非金属材料的断面、生物的大分子结构、分子光谱分布以及电磁波噪声分布等等，急切要求得到精确和深入的理解。在这个传统欧几里得几何学无能为力的领域，分形理论脱颖而出，它的研究和应用成果大放异彩。目前，分形理论是非线性科学研究中十分活跃的一支，它的研究对象是自然界和非线性系统中出现的不光滑和不规则的几何形体，分形理论的数学基础是分形几何。什么是分形？分形是对没

6、有特征长度（特征长度是指所考虑的集合对象所含有的各种长度的代表者，例如一个球，可用它的半径作为它的特征长度。）但具有一定意义下的自相似图形和结构的总称。“分形”一词译于英文Fractal，系分形理论的创始人曼德布罗特于1975年由拉丁语Frangere一词创造而成，词本身具有“破碎”和“不规则”两个含义。分形是美国科学家曼德布罗特给不规则的支离破碎的复杂图形的命名。1982年曼德布罗特创造性的思维形成了以分数维、自相似性及无限可分为特点的、以迭代计算来描述的分形集合概念。从图像处理的角度而言，在许多自然图像中确实存在某种形式的分形自相似性，这就自然地产生了把分形概念用于图像编码的思想。1988

7、年Barnsley首先利用图像整体与局部的自相似性，提出了一种应用迭代函数系统理论实现的分形图像压缩编码。1990年Jacquin创造性地利用图像块之间的相似性，提出了一种可由计算机完全自动实现的分形图像编码算法，为分形图像编码的研究带来了一次质的飞跃，使利用分形编码进行图像压缩的方法开始进入实用阶段。第二节 分形理论的产生、发展和定义分形的研究可追溯到十九世纪，一些科学家曾经研究了大自然中物体和现象的几何形状，发现普遍具有复杂的不规则形状，传统的欧氏几何学在描述这些现象时显得苍白无力。究其原因，传统的物理学以牛顿的确定论为基础。1827年发现的布朗（Brown）运动轨迹的复杂性、岩石在受击破

8、碎时裂纹的复杂性、化学领域中高分子的复杂空间结构、化学振荡现象等都难以用确定论来描述。伴随着多个学科类似问题的出现及研究，一门新的学科-分形产生了。分形理论是现代非线性科学研究中的一个非常活跃的一个分支，在地理、地质、材料科学、工程技术、信息科学、生命科学等各个领域中都有广泛的应用。特别是随着计算机科学的迅速发展和广泛应用，分形的思想和方法在模式识别、自然图像模拟、信息讯号处理以及艺术制作等领域都取得了巨大的成功。分形理论的研究对象是自然界中非线性系统中出现的不光滑和不规则的几何形体，分形理论的数学基础是分形几何。一、分形理论的发展过程被誉为大自然的几何学的分形理论，是现代数学的一个新分支，但

9、其本质却是一种新的世界观和方法论。它与动力系统的混沌理论交叉结合，相辅相成。它承认世界的局部可能在一定条件下、过程中，在某一方面（形态，结构，信息，功能，时间，能量等）表现出与整体的相似性; 它承认空间维数的变化既可以是离散的也可以是连续的，因而拓展了视野。分形理论真正发展起来才十余年，并且方兴未艾，很多方面的理论还有待进一步研究。值得注意的是，近年分形理论的应用发展远远超过了理论的发展，并且给分形的数学理论提出了更新更高的要求。各种分形维数计算方法和实验方法的建立、改进和完善，使之理论简便，可操作性强，是众多分形科学家们普遍关注的问题。而在理论研究上，维数的理论计算、估计、分形重构（即求一动

10、力系统，使其吸引集为给定分形集）、J集和M集及其推广形式的性质、动力学特征及维数研究将会成为数学工作者们十分活跃的研究领域。多重分形理论的完善、严格以及如何用这些理论来解决实际问题可能会引起科学家们广泛的兴趣，而动力学特征、相变和子波变换可能会成为其中的几个热点。总的来说，分形理论的发展可分为三个阶段。第一阶段为18721925年。在此阶段，数学家们已认识到几类典型的分形集，并力图对这类集合与经典几何的差别进行描述、分类和刻画。十九世纪，虽然人们已认识到了连续曲线与可微曲线的差别，但普遍认为连续曲线上的不可微点应是极少的。但，1872年，伟大的数学家Weierstrass构造了一个连续但处处不

11、可微的函数，这一结果在当时曾引起了极大的震动。1904年瑞典科学家科和用非常简单的方法构造出处处连续但处处不可微的曲线，现在称为科和曲线。科和曲线的面积为零而长度为无穷大，具有严格的自相似性和无限精细结构。科和曲线构造如下（参见图7-1）：设E0是具有单位长度的直线段，E1是由E0除去中间1/3的线段，而代之以被除去的线段长度为等边三角形的另外两条边所得到的图形；对E1的每个线段都进行同一过程来构造E2;以此类推，得到一个曲线序列Ek, 当k充分大时，曲线Ek和Ek-1只在精细的细节上不同; 而当K时，曲线序列Ek趋于一个极限曲线F,我们称F为科和曲线。具有严格自相似性和无限精细性。另一个例子

12、是德国数学家康托（Cantor）于1872年构造的康托三分集。1890年，意大利数学家Peano构造出了能够通过某个正方形内所有点的曲线。这与传统的维数观念相矛盾，从而人们提出应正确考虑以往的长度和面积的概念,豪斯道夫（Hausdroff）于1919年引入了集合的豪斯道夫测度和豪斯道夫维数，这些概念实际上指出了为了测量一个集合对象，必须依赖于测量方式以及测量所采用的尺度。另一类典型的例子是随机分形集。1913年，Perrin指出布朗运动轨迹作为运动曲线不具有导数。随后Wiener建立了很多布朗的概率模型。总之，在第一阶段，人们已经认识到分形集合的存在性，并为讨论这些问题提供了最基本的工具。第二

13、阶段：1926年-1975年。在这个阶段，人们对第一阶段提出的例子及其它分形集合的性质进行了广泛深入的研究，深化了第一阶段的思想，并逐步形成了理论，而且研究范围也扩展到了数学的许多分支里，取得了丰硕的成果。在维数理论方面，众多的维数定义被引入。众多维数定义和理论的建立，使人们能从不同的侧面刻画和分析分形集合的复杂性。对特定的分形集合，估计和计算它的各种维数及讨论其相互关系便形成了分形理论的一个基本研究课题。在这个背景下，提出了用于计算集合维数的位势理论方法，维数的乘积理论，维测度技巧等18。在分形集合的结构和性质方面，Bosicovitch 在此期间先后研究了曲线的维数、分形集合的局部性质、K

14、akeya集、分形集合的积。在随机布朗运动方面，Levy建立了分式布朗运动的理论，研究了稳定过程的性质。Levy在这方面的杰出工作是他成为随机分形理论的先驱者。Levy对自相似集合的研究在这一阶段也占有重要的地位，现在对自相似集合的一些研究可以追溯到他的研究成果。自相似集合是目前分形集合中研究最多最彻底的一类分形集合。在此期间，人们在数学的其它领域也找到了分形的例子，如在数论领域，人们研究了数的数字分布，连分数的分形性质。人们对分形理论的研究已取得了重要的成果，但其研究和应用范围仍只局限在数学理论方面，并未试图去解释其它学科中产生的大量分形问题。随着第二阶段对分形理论研究的深入和其它学科分形问

15、题的大量涌现，客观上要求用一种新的思想和工具去处理有关的问题。正是这样的时代背景下，曼德布罗特经过在众多领域的长期研究后，将自己和已有的研究成果进行了总结和理论上的提升，从而揭示大到宇宙空间的星系分布，小至分子的布朗运动，这些不同尺度上看似无序的和不规则的物质运动的本质。简单孕育着复杂，复杂的物质运动背后往往有着简单的数学规律。例如，科和曲线的生成规则十分简单，但它的结构却很复杂，具有无限的精细性。在1975年，诞生的划时代的专著Fractal: Form,Chance,and Dimension使分形几何的研究和发展进入了一个新的时期。分形几何产生对于不具有光滑性的复杂对象的研究，而且随着分

16、形理论本身的不断完善，分形理论逐渐形成了描述和研究这种复杂对象的有力工具。而计算机的发展，客观上使得人们表示和研究这种复杂对象成为可能。从1975年到现在为第三个阶段。在这个阶段，分形几何的发展十分迅猛，分形几何不仅在理论上得到了进一步的完善，而且它的研究内容也得到了扩展，如随机分形、多重分形、迭代函数系统理论、复动力系统的吸引子理论、分形的数值方法、随机布朗运动和布朗曲面等。现在，人们已看到了分形的极强的应用性，他的应用范围已扩展到了几乎所有的应用学科，物理学、计算机图形学、图像处理、分子化学、材料科学乃至经济、艺术等领域，并且已取得了令人瞩目的成果。这也说明了分形理论在一定程度上反映客观事

17、物的某些非常本质的东西。在这个阶段，国内外很多学者对分形理论及其在各个领域的应用进行了大量的研究，已有很多的有关专著出版，发表的论文数量以几何级数逐年增加。二、分形的定义什么是分形呢？事实上，目前对分形还没有严格的数学定义。曼德布罗特早期将分形定义为其豪斯道夫维数严格大于其拓扑维数的集合。但Peano曲线明显是分形却被这个定义排除在外。后来，曼德布罗特又修改为局部和整体按某种方式相似的集合，相似可以是严格意义下的，也可以是统计意义下的，这是目前基本认可的分形的描述性定义。现在人们普遍认为无需对分形几何下一个严格的数学定义，只需对分形集的特征进行描述。一般认为分形集合有以下几个主要的特征：1）具

18、有无限的精细结构。2）具有某种自相似性。3）某种分形维数大于它的拓扑维数。4）不能用传统的几何语言描述。5）往往可以由递归迭代等简单方法得到。第三节 分形理论在图像编码中的应用一、图像压缩技术的分类随着科学的发展、社会的进步，数字图像已经变成信息的重要来源，人们对图像存储和通信的需求越来越大。从近期的发展来看，数字式电视、可视电话等的兴起与普及已成为必然；高清晰电视的开发由于其巨大的市场需求和商业价值，已成为发达国家大力推进的高科技项目。然而图像的信息是模拟的，只有数字化后才能由计算机进行各种处理和综合。实现多媒体信息的交互处理，必须对各种媒体信息进行数字化。然而图像数字化后的数据量十分庞大，

19、他们存储时要占用大量的空间，处理时要占用大量的CPU时间，传输时所占用的时间和带宽花费的成本更是让人无法接受，尽管提出了很多种改进办法，但都不能彻底解决问题。实践证明，根本的方法是对图像的信息数据进行压缩。这样做可以明显增大存储量，减少传输时间，节约传输成本，实现实时传输。假设一桢1920*1080像素的HDTV彩色图像信息，需要占用3Mb多的存储容量，传输速率将达到数百Mbps。如果不经过压缩处理，将给存储和传输带来极大的困难，导致多媒体通信难以实现。图像压缩也是多媒体技术的关键和瓶颈技术之一。能够对图像进行压缩的原因是图像中通常含有大量的数据冗余，一般包括以下几种：1 空间冗余这是静态图像

20、最主要的一种数据冗余。一幅图像记录画面上可见景物的灰度值，而同一景物表面上个采样点的灰度值之间往往存在着空间连贯性，即相邻像素间的关联会产生空间冗余。2 时间冗余这是序列图像表示中经常包含的冗余。序列图像是由一组连续画面组成，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在空间位置略有不同，这就产生了大量的数据冗余，所以成为时间冗余。3 视觉冗余人类的视觉系统对图像场的敏感性是非均匀和非线性的。然而，在记录原始的图像数据时，通常假定视觉系统是线性和均匀的，对视觉敏感和不敏感同样对待，从而产生冗余数据4 统计冗余图像中的某一个像素的灰度值，总是和其周围像素灰度值有某种关系，他在统计的

21、意义上服从某些规律，利用这种性质也可以减少表示图像的数据量，因而称之为统计冗余。多年来，人们根据图像的这些冗余特点，对图像的编码技术进行了广泛的研究，提出了许多切实有效的图像编码方法。图像压缩技术可以分为两大类，即无损图像压缩技术和有损压缩技术。所谓无损压缩技术是指在图像编码过程中没有任何的失真，但是压缩比不高。这种压缩技术主要应用于医疗图像和卫星照片。有损压缩技术也就是图像编码过程中有一部分信息损失。这些信息的损失对于人眼来说通常是可以容忍的，从而可以获取高压缩比。它主要应用于多媒体通信中。二、分形图像编码及其发展分形编码算法是一种有损图像压缩技术163。它是图像压缩的重要数学工具，有着广阔

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

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

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

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

26、这个收缩映像的连续作用后，形成的点列收敛于这个固定点。图7-3是经反复迭代最后收缩成一图像的过程。 (a) (b) (c) (d) (e) (f) (g) (h)图7-3 函数空间中的一个收缩映射4、迭代函数系统定理每个迭代函数系统都可以构成函数空间中的一个收缩映射。于是，我们得到结论,每个迭代函数系统都决定一幅图像。一般我们用仿射变换来表示这些映射。IFS中的参数（也就是对应的仿射变换的参数）的连续微小变化将使IFS对应的图像有微小的变化，如图7-4。图7-4对应的是b增大反映了x的增大，相当于叶子高处的横向摆动增大，d减小反映了树叶的整体高度减小。从视觉效果上看，这就是一片风中的叶子。现在

27、考虑反问题：给定一幅图像，能否找到一个迭代函数系统，而使这个系统正好能决定给定的图像?这个问题由下面的拼贴定理给出了回答。图7-4 函数空间中的另一个收缩映射例子5、拼贴定理给定一幅图像I，可以选择N个收缩映像，这幅图像经过N个变换得到N个象集，每个象集都是一块小图像。如果这N个小图像拼贴起来的图像与图像I之间的距离任意小，则这N个收缩映像构成的迭代函数系统所决定的图像就任意地接近图橡I。这就告诉了我们寻找迭代函数系统的方法。三、交互的分形图像压缩方法。在1990年，Jaquin提出了基于块的分形图像压缩算法。虽然该算法的压缩比低于M.Barnsley,但是他的编码过程可自动进行，因此此算法已

28、经成为这一研究方向的典型代表。Jacquin发展了IFS理论，提出了局部迭代函数理论（PIFS），他在此理论基础上提出了一种基于方块划分的分形图像压缩方案，在其方案中首先将原始图像划分为固定大小的方块，然后对每一块，通过反射变换在原始图像的紧缩图像中寻找最相似的部分。这些操作可由计算机自动完成，他为分形图像压缩的研究带来了一次质的飞跃。整个图像压缩的过程可以分成两大部分，一是编码过程，一是解码过程。在分形压缩中，前者主要基于拼贴定理，这个过程中要考虑图像的灰度分布，以及概率求取的策略。后者主要是随机迭代问题。编码主要步骤如下：1、分割成适当的块 这可以借助于传统的图像处理技术，如边缘检测、频谱

29、分析、纹理分析等，当然也可以使用分数维的方法。分割出的每部分可以是一棵树、一片云等；也可能稍微复杂一些，如一片海景，它包括泡沫、礁石、雾尘等；一般这每一部分都有比较直观的自相似性特征。IFS编码求取 每一部分求其IFS编码，这就要借助拼贴定理了，同时也是人要参与的地方，在这个过程中有一些必须注意的地方。（1）每一块的“拷贝”必须小于原块，这是为了保证仿射变换的收缩性，至于每个拷贝的大小要根据各块图像的性质来确定。（2）用于拼贴的每个拷贝之间最好为不相连或紧相邻的。而不要重叠或者有空缺。这一点对概率的确定很重要，它影响到重构图像的不变测度。所以对有重叠或空缺时，这部分的“质量”在计算中不能复用或

30、者简单地丢弃，并最终要保证的成立。3、仿射变换的概率设定 拼贴的过程不仅要保证吸引子的形状，也要考虑到每块区域灰度分布的情况，拼贴结束时要求出各个pi，Barnsley等人采取的方法仍然是下式： 7-10其中Tm表示某一分割后的图像块，这种方法有较快的计算速度，这种定义实际上是建立在均匀测度的假设上的，即吸引子上相同大小的区域有相同的“质量”。但是这在对实际的灰值图像处理过程中并不总是成立的，往往是经过某个仿射变换后的区域可能面积很大，但包含的总的灰度能量可能很小；反之某些小区域却有较大的灰度能量。比如在图7-3中三个小拷贝所占的面积一样多，但各部分的测度显然不同。为此，一般的方法是对灰度能量

31、多的区域干脆多重叠的几个相同的仿射变换。这在解码的过程中可能造成的一个结果是重构图中存在伪灰度现象；同时在随机迭代重构时总的步数也没有确定地给出，只能“足够大”，最后再把灰度归一化到0，255。为此，我们在拼贴的过程中重新定义了概率的求取，令图像块Tm能量为Qm： 7-11f(i,j)表示点(i,j)处的图像灰度,则可定义概率： 7-12其中分子表示Tm经wi变换后区域中的能量。这时的pi应该说可以很好地反映出了图像内部灰度分配的信息，下面将看到，它还可以指导图像重构，即对每一图像块重构时总的随机迭代次数就可以设为该块的总能量Qm,而每一次迭代生成点的灰度能量为1个单位。此时概率pi计算稍微比

32、前一种方法麻烦些，在计算中可以用wi(Tm)与Tm的逻辑与来获得wi(Tm)区域的能量。4、分形库的建立与使用对于分类的图像，我们可以预知该类图像中物体出现的范围，在同样使用上述的编码过程中将会出现重复拼贴一些相似的区域，这种代价是无益的，为此可以使用分形库的方法。即在库中预存贮着许多有意义的小的形态，当然它们不是以图像格式存入的，否则库的容量将极其巨大，同样可以以IFS参数的形式来描述它们，则拼贴的过程就变成了用这些IFS码生成的分形集来与图像中分割后的小区域进行匹配的过程，匹配的近似程度可以由事先给出的度量公式来确定，这种公式有很多种形式，如均方误差等。一旦匹配好了，就可以用这些 IFS码

33、来替换图像中的区域了。四、基于分数维分割的图像编码所有的分形都有一个特征数，也就是分数维去测定其不平整度、复杂度或卷积度。分数维的微小变化可以引起形状的急剧改变。现实世界中,几何形体可以分为两大类。一类是规则、光滑的,可以用直线段、平面片或小六面体来逼近,研究这一范畴的学科为传统几何学。另一类的自然形态是不光滑、不规则的,具有精细的结构或自相似特征,不能用传统的几何语言描述,我们称之为分形。如海岸线、山形、河川、树木、闪电等自然景物,以及微观世界中复杂且精细的结构、宏观世界里天体演变的各种形态。但这些例子在充分小的比例下观察时，其分形特征就消失了。但在一定比例下它们表现了许多分形特征，这时我们

34、可以把它看作分形。分形学使人们对自然界和人类社会的认识提高到一个崭新的高度。例如,曾使网络性能模型的研究人员感到震惊的是以太网数据传输具有自相似的本性,这是由Bellcore和 Boston大学的研究人员发现的。结果证明,Internet网络上数据的传输服从分形特征,不要期望网上的数据流光滑输出,由统计多路技术或异步传递模式转换的合并也不会有光滑输出的数据流。这样流量控制就要重新考虑了。这为网络的合理设计与管理提供了理论上的依据。图像的最终目的是让人去观察的，而人的视觉系统（Human Visual System）有其固有的特性，比如对某些频率分量比对其它的敏感些。因此，对不敏感的部分可以粗略

35、编码，重构的解码图像也不会有接受不了的质量损失。所以，在编码系统中考虑到了人的视觉特性将有利于提高压缩比。基于分割的图像编码就是这样一种技术，它根据视觉特征，使用一些分割方法把图像分成若干类区域，对不同的类再使用不同的编码方法。但是传统的分割技术有一些限制，比如它是按一定的灰度去划分的，这对一个复杂的纹理区域，可能要分割成许多块，然而为了得到较大的压缩比我们必须限制分割的数目。因此可采用分数维的方法。我们知道，分数维是物质的根本性质之一，它直接反映了人眼对表面粗糙度的感受。这样可以把图像分割成纹理上类似的区域，例如可以分成如下三类，第一类是平滑区域，第二类为平稳的纹理，第三类是粗糙的纹理。这样

36、对图像分割以后，对不同类的区域可以采用不同的编码策略，对第一类只要有灰度均值以及边界信息；第二类是要重点对待的，这是人眼敏感的图像区域；第三类相应于图像中的高频部分，也是人眼不敏感的部分，此处也可以用较高的压缩比来完成。这种基于视觉特性的分数维分割的图像压缩方法可以获得相当高的压缩比。有关分数维的具体含义及求法可参考相关的参考书16,18，分形是和混沌相联系的，混沌系统的维数一般也是分数维的，我们称其为李雅普诺夫维数，该维数反映了信息丢失的程度。分形集是动力系统中那些不稳定轨迹的初始点的集合，即混沌集。混沌吸引子就是分形集。五、分形在视频图像压缩中的应用分形压缩可以得到很高的压缩比，但在编码过

37、程中计算量很大。一般是从两个方面试图解决这一问题，一是要考虑新的算法，二是要考虑用硬件实现。由Barnsley创立的迭代系统（IteratedSystem）公司已经研制出了板级的可用于彩色图像的分形压缩的硬件，这种压缩卡对320 X 200 X 8的灰度图像在3秒内完成编码，而在解码中只通过软件完成，不到1秒。当然这种硬件还不能实现视频图像的实时压缩，还有待于进一步的发展，但它仍然具有广泛应用的价值。分形图像压缩的编、解码过程是极不对称的。编码比解码要求多得多的时间，相应的硬件复杂度集中在编码端，这非常适合于一处编码，多处解码的情况，即常说的广播方式。用户在解码端，因此，不用花费过多的硬件费用

38、，甚至只有软件也行。同时解码过程还有独立于分辨力的特性，在解码端可以生成任何分辨率的图像，这可能有助于今后HDTV与TV上信号兼容的问题。六、当前分形图像压缩的发展状况Jacquin提出的方案为分形压缩编码的研究注入了生机和活力，分形编码成为目前编码研究的热点。目前分形编码方案大致有三个发展方向：加快分形的编解码速度、提高分形的编码质量、基于分形的低码率视频编码。发展方向之一：加快分形的编码速度编码速度慢一直是分形编码实用化的最大障碍，下面分析Jacquin编码方案的计算复杂度。对于一个CC大小的图像，假设值域子块大小为KK,定义域子块大小为2 K2K,则该图像共有C2/K2个值域子块、（C-

39、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采用多维最近邻搜索方法代替传统分形编码中序列的匹配过程，其搜索匹配时间按指数级增长；K.F.Loe等将Jacquin方

40、案中使用的分类器替换成模糊分类器，并使用遗传算法进行优化，该算法比未分类的编码方案快40%左右；C.K.Lee和W.K.Lee通过对匹配块之间关系的研究发现，如果两子块的自身方差相差太远，则这两个子块不可能相似，由此可去除许多不必要的匹配过程，提高压缩速度10倍以上；Min Xue等将传统编码方案中每个值域子块匹配的串行操作转换为并行操作，计算复杂度下降，缩短了压缩的时间。发展方向之二：提高分形编码质量目前，提高分形编码质量的方法有三种：采用混合编码方案、改进分割方案、改进灰度逼近能力等。分形与小波的结合编码是目前分形研究的一个新的方向，在本章的第四节对此加以介绍，并附有实例，加深读者们的理解

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

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

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

44、高压缩比和解码图像任意放大方面，比现有的静态图像国际压缩标准JPEG好得多，已经开始显露出它的优势。分形图像编码方法的实际应用也初见端倪，如分形图像压缩解码速度很快，当前已经适合于一次写入、多次读出的文档。由于篇幅有限，这一节重点介绍小波与分形的结合编码、与遗传算法的混合编码以及与DCT变换结合的编码三种混合编码方案。一、小波分形混合图像编码小波图像编码和分形图像编码是两种不同的图像编码方法。其中，小波图像编码是把图像分解成不同的空间方向和不同分辨率的子带图像，人们可以根据需要，对不同子带图像采用不同的量化策略来进行编码；而分形图像编码则适用于自相似性较强的图像。可惜的是，一般的自然图像自相似

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

46、进行大量计算，从而编码时间过长。而利用小波分解后，图像块所具有的独特空间-频率特性，可以构造较好的分类和搜索方法，因而大大加快了分形编码的速度。这种混合编码基本思想简述见实例演示。二、DCT与分形混合编码自从分形图像压缩作为一种实用的方法由Jacquin首次提出以来，大多的关于分形图像压缩研究都集中在时间域进行，为了提高编码性能，一些变换域变换编码方法相继由Barthel等提出。其中离散余弦变换(Discrete consine transformation),余弦调制滤波器组（Cosine modulated filter banks）和小波变换等应用最为广泛。分形图像编码的原理是要寻找一组

47、收敛的仿射变换来重建图像，它利用同一图像中一部分描述另外一部分，即利用图形的自相似性来减少图像的冗余度。频域变换的一个突出优点就是他的能量紧凑特性，一幅图像经过频域变换后，总能量没有变化，但能量的分布却发生了变化。能量将集中在它的低频部分，而高频部分所占的能量非常少，能量的这种分布对分形压缩十分有利，因为分形图像压缩的主要过程是对同样大小的图像块进行能量匹配，经过频域变换后，高频部分在能量匹配过程中产生的误差很小，基本可以忽略不计，这就等于减少了匹配块的大小，从而减小了匹配误差。去相关能力最强的是K-L变换，但由于其难以实现，人们转而寻找能实时处理的次最佳变换，离散余弦变换就是其中的一种。近年

48、来的研究表明，离散余弦变换是一种最接近最佳的正交变换，性能接近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的块，这些块按照原图的顺序组成一个域块库。之所以只取图像左上角是因为域块在经过变换后，主要信息都保存在低频区，对应于图像块的左上角，而高频区所占的能量相对较少，在以后的匹配

49、中，起的作用很小。因此，在构成域块时，我们只取左上角与区块同样大小的一部分。（2）下面则是利用图像的自相似性进行分形压缩，其实质是寻找一组仿射变换，即块匹配过程。它与时域的块匹配过程完全相同。但由于图像经过频域变换后，具有与时域不同的特点，因此在具体的实现方法上存在着一些差别。首先，图像在经过DCT变换后,能量集中到低频部分，特别是它的直流分量，占据了整幅图像能量的很大一部分，这就使得我们必须对它们单独处理，而不把它带入块匹配的过程中。在匹配过程中，均值分量也就不再需要。在DCT域分形编码中，我们是将这些直流分量直接作差分之后再进行量化、熵编码。这样做不仅减少了块匹配的误差，而且在解码时，在第

50、一次迭代过程中，就可以得到直流分量，从而加快了解码的收敛速度。其次，图像块在经过DCT变换后，能量分布具有一定的规律，不同于在时域中的杂乱无章的分布，因此在块匹配过程中，旋转所带来的性能上的改进将变得非常小，与此同时，它却增加了所需的比特数，降低了压缩比。所以在DCT分形压缩的块匹配过程中，不采用旋转因子。（3）经过块匹配之后，将阈块的位置信息和仿射变换的系数（这里只有收敛因子）进行熵编码，以进一步提高压缩比。编码算法可以选用哈夫曼编码或是算术编码。为了加快编码速度，降低编码的复杂性，有人提出了选择性块匹配的编码方案，也就是对那些平坦块不去进行块匹配，而是把它的直流分量直接编码输出。感兴趣的读

51、者可以参阅相关的文献介绍。三、基于遗传算法的分形图像编码遗传算法是模仿生物界的进化过程而得出的一种随机优化方法，对非线性、多极值的问题尤其有效，它将问题的解编码表示成“染色体”，一群“染色体”组成初始种群，初始种群置于问题的“环境”中，根据自然竞争、优胜劣汰的原则，种群通过遗传、交叉、变异不断地进行演化，产生新的种群，这样经过若干代的进化，求得适合问题的最优解。分形图像压缩中的值域块与定义域块的匹配是典型的多极值问题，由于遗传算法求解多极值问题的有效性，将其应用于块的匹配（也可称为虚拟码书的搜索），可以大大降低压缩编码的复杂度，同时很好地保持图像质量。应用于分形图像压缩中的遗传算法主要步骤包括

52、：a 物种的染色体编码表示。b 种群的初始化。c 适宜函数的选取。d 选择策略。e 交叉策略。f 遗传及变异策略。g 迭代终止准则。经过许多学者的研究证明，将遗传算法应用于分形图像压缩，效果良好，对每一定义域块需匹配的区域数目，穷尽搜索与遗传算法的比值，在O(102)量级，遗传算法较好地保持了图像的质量，同时利用遗传算法的并行性可以进一步提高运行的速度。由于分形压缩编码存在一定的失真度，其编码时间和编码效率与失真度密切相关。另外分形压缩方法仍有许多尚待解决的问题：a 由于实际上的分形图像形状极不规则，即相似性表现的形式多种多样，只利用规则的划分未免太勉强人意，需要进一步讨论相似性的提取。失真率

53、的研究现在很不全面，应给出更好的度量相似性的方法。考虑如何利用图像块本身的特点，更快更好地寻找到匹配块，节省编码时间。尽管如此，分形图像压缩仍以其高压缩比受到广泛的关注。目前，基于分形小波混合编码是研究的热点，还有很多方面可以进一步研究以充分挖掘其潜力：（1）深入研究小波分形变换的内在联系，进一步用分形集合的集合相似性来表示小波分解域内子带间的相似的特征。（2）对不同的小波基分解后频带的特性和差别加以研究，以挖掘出适合小波分形编码的小波基。（3）将传统的分形编码方法中一些行之有效的思想应用于小波分形编码。（4）广泛结合一些目前已经相对完善的技术的优势（如子带编码、矢量量化），充分利用信号处理的

54、研究成果为图像编码领域注入新的活力。第五节 实例分析小波与分形混合编码一、引言小波图像编码和分形图像编码是二种不同的图像编码方法,二者各有其特点,又都存在一定的局限性。一幅图像经过小波变换后,其相同方向但不同分辨率的子带图像具有较强的相似性。这种相似结构正好与分形编码的特点具有互补性。如果采用一些新的编码方法,把二者有机地结合起来,便能大幅度地提高图像编码的压缩比。Rinaldo和Calvagno提出了一种利用图像小波分解后所表现出来子带间相似性进行分形编码的方法，即所谓的块预测法。这种方法的主要思想是用变换域低分辨率的子带图像来预测高一级分辨率的子带图像。Rinaldo提出的块预测法，虽然从

55、理论来说较为简洁，但由于分形块搜索是在同方向每相邻的两个小波子带内进行搜索，块搜索范围过大，耗时过长，且并没有充分发掘和利用同方向各个子带间的结构性相似；同样,Levy和Wilson也发表过类似的研究结果，后来Davis把小波子树的概念引入到分形图像编码中,提出了小波子树自量化方法(Self-Quatization of Subtrees)，其主要编码方法是把传统分形图像编码中的图像块匹配转化为图像树匹配。Davis的方法虽然把图像块扩大为图像树，但却造成了子树匹配过程中计算量的增大和分形搜索的困难。因此近年来,小波分形混合图像编码领域内的研究主要是在这两种方法的基础上,进行不断的探讨114,116。显然，这两种方法都只是从某一个侧面揭示了小波分形的本质特征。二、快速小波子带分形编码方法的提出鉴于以上两类编码方法的特点和不足,在小波变换同方向不同分辨率相邻子带块预测编码的基础上,本书作者提出一种新的快速图像编码方法，主要编码思想由以下四部分组成：1、子树位搜索法相邻子带块预测编码在进行块匹配搜索时,对上一级分辨率子带