分形图

第七章分形理论及其在图像处理中的应用

前面我们介绍了非线性电路的基本概念及原理以及混沌的相关理论，本章我们介绍非

线性科学的另一个重要的概念—分形。

分形形态在自然界中是非常普遍的，分形理论为我们研究自然界的复杂事物的客观规

律及其内在联系提供了新的概念和方法；分形具有广阔的应用前景，许多传统的科学难题，

由于分形的引入而取得显著进展。80年代初国外开始的“分形热”经久不息。美国著名物理

学家惠勒说过：今后谁不熟悉分形，谁就不能被称为科学上的文化人。所以在本书中单独

把分形列为一章来讨论和研究。

分形与混沌有许多共同之处，二者形影不离，互相交叉。混沌学研究的是运动过程，

是物理学;分形学研究的是静态图形，是几何学。

本章的内容是依据分形理论的产生、发展，及在图像编码中的应用算法以及发展趋势

这样一个流程而展开的。在本章最后介绍了分形与其它技术的有效的结合。如果读者对分

形理论已经有了一定的了解，可以跳过第一第二节，直接阅读第三节。

第一节自然界的分形现象

生活在北方的读者对雪花是不陌生的，那晶莹剔透的雪花曾引起无数诗人的赞叹。但

若问起雪花的形状是怎样的，能回答上来的读者不一定很多。也许有人会说，雪花是六角

形的，这既对，但又不完全对。雪花到底是什么形状呢？1904年瑞典数学家科和（koch）

讲述了一种描述雪花的方法。

先画一个等边三角形，把边长为原来三角形边长的三分之一的小等边三角形选放在原

来三角形的三条边上，由此得到一个六角星；再将这个六角星的每个角上的小等边三角形

按上述同样方法变成一个小六角星…如此一直进行下去，就得到了雪花的形状，如图7-1

所示。

图7-1一种描述雪花的方法

从上面的描述过程我们可以看出：原来雪花的每一部分经过放大都可以与它的整体一

１９７

模一样，小小的雪花竟然有这么多学问。现在已经有了一个专门的数学学科来研究像雪花

这样的图形，这就是20世纪70年代由美国计算机专家曼德布罗特（Mandelbrot）创立的分形几何。所谓分形几何就是研究不规则曲线的几何学。目前分形几何已经在很多领域得

[16,18,162,163]

到了应用。

再来看图7-2所示的一组图形，是不是对分形有所认识？（参见光盘文件）

图7-2一种分形三角形的画法

细心的读者会发现这两组图形中包含了很多相似形（形状相同，大小不一定相同）。

这种图形的特点就是图形的每一部分都和它本身的形状相同，我们叫它自相似形。自相似

图形属于分形图中的一种。通过计算机处理后，我们可以把一个简单的图形变成非常漂亮

的分形图。

分形理论建立于20世纪70年代末，30年来却震惊着世界科学界，被科学界列入20

世纪的20项重大科学发现之一。

众所周知，基于传统欧几里得几何学的各门自然科学总是把研究对象想象成一个个规

则的形体，而人类虽然熟悉却无法描述的自然界许许多多真实的图形竟如此不规则和支离

破碎，与欧几里得几何图形相比，拥有完全不同层次的复杂性。现代科学研究面对起伏蜿

蜒的山脉、坑坑洼洼的地面、曲曲折折的海岸线、层层分叉的树枝、支流纵横的水系、翻

腾变幻的浮云、地壳上的褶皱、密布人体周身的血管、满天闪烁的繁星、撕裂夜空的闪电、

魔鬼般跳跃的火焰、船尾湍急的涡流、拍岸的惊涛与浪花、金属和非金属材料的断面、生

物的大分子结构、分子光谱分布以及电磁波噪声分布等等，急切要求得到精确和深入的理

解。在这个传统欧几里得几何学无能为力的领域，分形理论脱颖而出，它的研究和应用成

果大放异彩。

目前，分形理论是非线性科学研究中十分活跃的一支，它的研究对象是自然界和非线

性系统中出现的不光滑和不规则的几何形体，分形理论的数学基础是分形几何。什么是分

形？分形是对没有特征长度（特征长度是指所考虑的集合对象所含有的各种长度的代表

者，例如一个球，可用它的半径作为它的特征长度。）但具有一定意义下的自相似图形和

１９８

结构的总称。“分形”一词译于英文Fractal，系分形理论的创始人曼德布罗特于1975年

由拉丁语Frangere一词创造而成，词本身具有“破碎”和“不规则”两个含义。

分形是美国科学家曼德布罗特给不规则的支离破碎的复杂图形的命名。1982年曼德布

罗特创造性的思维形成了以分数维、自相似性及无限可分为特点的、以迭代计算来描述的

分形集合概念。从图像处理的角度而言，在许多自然图像中确实存在某种形式的分形自相

似性，这就自然地产生了把分形概念用于图像编码的思想。1988年Barnsley首先利用图

像整体与局部的自相似性，提出了一种应用迭代函数系统理论实现的分形图像压缩编码。

1990年Jacquin创造性地利用图像块之间的相似性，提出了一种可由计算机完全自动实现

的分形图像编码算法，为分形图像编码的研究带来了一次质的飞跃，使利用分形编码进行

图像压缩的方法开始进入实用阶段。

第二节分形理论的产生、发展和定义

分形的研究可追溯到十九世纪，一些科学家曾经研究了大自然中物体和现象的几何形

状，发现普遍具有复杂的不规则形状，传统的欧氏几何学在描述这些现象时显得苍白无力。

究其原因，传统的物理学以牛顿的确定论为基础。1827年发现的布朗（Brown）运动轨迹

的复杂性、岩石在受击破碎时裂纹的复杂性、化学领域中高分子的复杂空间结构、化学振

荡现象等都难以用确定论来描述。伴随着多个学科类似问题的出现及研究，一门新的学科

-分形产生了。

分形理论是现代非线性科学研究中的一个非常活跃的一个分支，在地理、地质、材料

科学、工程技术、信息科学、生命科学等各个领域中都有广泛的应用。特别是随着计算机

科学的迅速发展和广泛应用，分形的思想和方法在模式识别、自然图像模拟、信息讯号处

理以及艺术制作等领域都取得了巨大的成功。分形理论的研究对象是自然界中非线性系统

中出现的不光滑和不规则的几何形体，分形理论的数学基础是分形几何。

一、分形理论的发展过程

被誉为大自然的几何学的分形理论，是现代数学的一个新分支，但其本质却是一种新

的世界观和方法论。它与动力系统的混沌理论交叉结合，相辅相成。它承认世界的局部可

能在一定条件下、过程中，在某一方面（形态，结构，信息，功能，时间，能量等）表现

出与整体的相似性;它承认空间维数的变化既可以是离散的也可以是连续的，因而拓展了

视野。

分形理论真正发展起来才十余年，并且方兴未艾，很多方面的理论还有待进一步研究。

值得注意的是，近年分形理论的应用发展远远超过了理论的发展，并且给分形的数学理论

提出了更新更高的要求。各种分形维数计算方法和实验方法的建立、改进和完善，使之理

论简便，可操作性强，是众多分形科学家们普遍关注的问题。而在理论研究上，维数的理

论计算、估计、分形重构（即求一动力系统，使其吸引集为给定分形集）、J集和M集及其

推广形式的性质、动力学特征及维数研究将会成为数学工作者们十分活跃的研究领域。多重分形理论的完善、严格以及如何用这些理论来解决实际问题可能会引起科学家们广泛的

１９９

兴趣，而动力学特征、相变和子波变换可能会成为其中的几个热点。

总的来说，分形理论的发展可分为三个阶段。

第一阶段为1872—1925年。在此阶段，数学家们已认识到几类典型的分形集，并力

图对这类集合与经典几何的差别进行描述、分类和刻画。十九世纪，虽然人们已认识到了

连续曲线与可微曲线的差别，但普遍认为连续曲线上的不可微点应是极少的。但，1872年，

伟大的数学家Weierstrass构造了一个连续但处处不可微的函数，这一结果在当时曾引起

了极大的震动。1904年瑞典科学家科和用非常简单的方法构造出处处连续但处处不可微的

曲线，现在称为科和曲线。

科和曲线的面积为零而长度为无穷大，具有严格的自相似性和无限精细结构。科和曲

线构造如下（参见图7-1）：设E0是具有单位长度的直线段，E1是由E0除去中间1/3的

线段，而代之以被除去的线段长度为等边三角形的另外两条边所得到的图形；对E1的每

个线段都进行同一过程来构造E2;以此类推，得到一个曲线序列{E

k

},当k充分大时，曲

线E

k

和E

k-1

只在精细的细节上不同;而当K→∞时，曲线序列{E

k

}趋于一个极限曲线F,我

们称F为科和曲线。具有严格自相似性和无限精细性。另一个例子是德国数学家康托

（Cantor）于1872年构造的康托三分集。1890年，意大利数学家Peano构造出了能够通

过某个正方形内所有点的曲线。这与传统的维数观念相矛盾，从而人们提出应正确考虑以

往的长度和面积的概念,豪斯道夫（Hausdroff）于1919年引入了集合的豪斯道夫测度和

豪斯道夫维数，这些概念实际上指出了为了测量一个集合对象，必须依赖于测量方式以及

测量所采用的尺度。

另一类典型的例子是随机分形集。1913年，Perrin指出布朗运动轨迹作为运动曲线

不具有导数。随后Wiener建立了很多布朗的概率模型。

总之，在第一阶段，人们已经认识到分形集合的存在性，并为讨论这些问题提供了最

基本的工具。

第二阶段：1926年-1975年。在这个阶段，人们对第一阶段提出的例子及其它分形集

合的性质进行了广泛深入的研究，深化了第一阶段的思想，并逐步形成了我的梦想600字 理论，而且研究

范围也扩展到了数学的许多分支里，取得了丰硕的成果。

在维数理论方面，众多的维数定义被引入。众多维数定义和理论的建立，使人们能从

不同的侧面刻画和分析分形集合的复杂性。对特定的分形集合，估计和计算它的各种维数及讨论其相互关系便形成了分形理论的一个基本研究课题。在这个背景下，提出了用于计

[18]

算集合维数的位势理论方法，维数的乘积理论，维测度技巧等。

在分形集合的结构和性质方面，Bosicovitch在此期间先后研究了曲线的维数、分形

集合的局部性质、Kakeya集、分形集合的积。在随机布朗运动方面，Levy建立了分式布

朗运动的理论，研究了稳定过程的性质。Levy在这方面的杰出工作是他成为随机分形理论

的先驱者。Levy对自相似集合的研究在这一阶段也占有重要的地位，现在对自相似集合的

一些研究可以追溯到他的研究成果。自相似集合是目前分形集合中研究最多最彻底的一类

分形集合。

在此期间，人们在数学的其它领域祖国我为你自豪 也找到了分形的例子，如在数论领域，人们研究了

数的数字分布，连分数的分形性质。人们对分形理论的研究已取得了重要的成果，但其研究和应用范围仍只局限在数学理论方面，并未试图去解释其它学科中产生的大量分形问

２００

题。

随着第二阶段对分形理论研究的深入和其它学科分形问题的大量涌现，客观上要求用

一种新的思想和工具去处理有关的问题。正是这样的时代背景下，曼德布罗特经过在众多

领域的长期研究后，将自己和已有的研究成果进行了总结和理论上的提升，从而揭示大到

宇宙空间的星系分布，小至分子的布朗运动，这些不同尺度上看似无序的和不规则的物质

运动的本质。简单孕育着复杂，复杂的物质运动背后往往有着简单的数学规律。例如，科

和曲线的生成规则十分简单，但它的结构却很复杂，具有无限的精细性。在1975年，诞

生的划时代的专著《Fractal:Form,Chance,andDimension》使分形几何的研究和发展进

入了一个新的时期。分形几何产生对于不具有光滑性的复杂对象的研究，而且随着分形理

论本身的不断完善，分形理论逐渐形成了描述和研究这种复杂对象的有力工具。而计算机

的发展，客观上使得人们表示和研究这种复杂对象成为可能。

从1975年到现在为第三个阶段。在这个阶段，分形几何的发展十分迅猛，分形几何

不仅在理论上得到了进一步的完善，而且它的研究内容也得到了扩展，如随机分形、多重

分形、迭代函数系统理论、复动力系统的吸引子理论、分形的数值方法、随机布朗运动和

布朗曲面等。现在，人们已看到了分形的极强的应用性，他的应用范围已扩展到了几乎所

有的应用学科，物理学、计算机图形学、图像处理、分子化学、材料科学乃至经济、艺术

等领域，并且已取得了令人瞩目的成果。这也说明了分形理论在一定程度上反映客观事物

的某些非常本质的东西。在这个阶段，国内外很多学者对分形理论及其在各个领域的应用

进行了大量的研究，已有很多的有关专著出版，发表的论文数量以几何级数逐年增加。

二、分形的定义

什么是分形呢？事实上，目前对分形还没有严格的数学定义。曼德布罗特早期将分形

定义为其豪斯道夫维数严格大于其拓扑维数的集合。但Peano曲线明显是分形却被这个定

义排除在外。后来，曼德布罗特又修改为局部和整体按某种方式相似的集合，相似可以是

严格意义下的，也可以是统计意义下的，这是目前基本认可的分形的描述性定义。现在人

们普遍认为无需对分形几何下一个严格的数学定义，只需对分形集的特征进行描述。一般

认为分形集合有以下几个主要的特征：

1）具有无限的精细结构。

2）具有某种自相似性。

3）某种分形维数大于它的拓扑维数。

4）不能用传统的几何语言描述。

5）往往可以由递归迭代等简单方法得到。

第三节分形理论在图像编码中的应用

一、图像压缩技术的分类

随着科学的发展、社会的进步，数字图像已经变成信息的重要来源，人们对图像存储

２０１

和通信的需求越来越大。从近期的发展来看，数字式电视、可视电话等的兴起与普及已成

为必然；高清晰电视的开发由于其巨大的市场需求和商业价值，已成为发达国家大力推进

的高科技项目。然而图像的信息是模拟的，只有数字化后才能由计算机进行各种处理和综

合。实现多媒体信息的交互处理，必须对各种媒体信息进行数字化。然而图像数字化后的

数据量十分庞大，他们存储时要占用大量的空间，处理时要占用大量的CPU时间，传输时

所占用的时间和带宽花费的成本更是让人无法接受，尽管提出了很多种改进办法，但都不

能彻底解决问题。实践证明，根本的方法是对图像的信息数据进行压缩。这样做可以明显

增大存储量，减少传输时间，节约传输成本，实现实时传输。假设一桢1920*1080像素的

HDTV彩色图像信息，需要占用3Mb多的存储容量，传输速率将达到数百Mbps。如果不经

过压缩处理，将给存储和传输带来极大的困难，导致多媒体通信难以实现。图像压缩也是

多媒体技术的关键和瓶颈技术之一。

能够对图像进行压缩的原因是图像中通常含有大量的数据冗余，一般包括以下几种：

1空间冗余

这是静态图像最主要的一种数据冗余。一幅图像记录画面上可见景物的灰度值，而同

一景物表面上个采样点的灰度值之间往往存在着空间连贯性，即相邻像素间的关联会产生

空间冗余。

2时间冗余

这是序列图像表示中经常包含的冗余。序列图像是由一组连续画面组成，其中的相邻

帧往往包含相同的背景和移动物体，只不过移动物体所在空间位置略有不同，这就产生了

大量的数据冗余，所以成为时间冗余。

3视觉冗余

人类的视觉系统对图像场的敏感性是非均匀和非线性的。然而，在记录原始的图像数

据时，通常假定视觉系统是线性和均匀的，对视觉敏感和不敏感同样对待，从而产生冗余

数据

4统计冗余

图像中的某一个像素的灰度值，总是和其周围像素灰度值有某种关系，他在统计的意

义上服从某些规律，利用这种性质也可以减少表示图像的数据量，因而称之为统计冗余。

多年来，人们根据图像的这些冗余特点，对图像的编码技术进行了广泛的研究，提出

了许多切实有效的图像编码方法。图像压缩技术可以分为两大类，即无损图像压缩技术和

有损压缩技术。所谓无损压缩技术是指在图像编码过程中没有任何的失真，但是压缩比不

高。这种压缩技术主要应用于医疗图像和卫星照片。有损压缩技术也就是图像编码过程中

有一部分信息损失。这些信息的损失对于人眼来说通常是可以容忍的，从而可以获取高压

缩比。它主要应用于多媒体通信中。

二、分形图像编码及其发展

[163]

分形编码算法是一种有损图像压缩技术。它是图像压缩的重要数学工具，有着广阔

的应用前景。分形图像压缩是以迭代函数系统（IFS）为理论基础，即用自然景物的自相似性来进行数据压缩。分形图像压缩算法具有高压缩比、任意尺度下的重构、快速编码等

２０２

优越性质。此项研究由ey于1988年首先提出，他成功地给予迭代函数系统的分

形图像压缩应用于计算机图形学上，对航空图像进行压缩编码，并获得了1000：1的压缩

比。但其算法有很大的局限性，最主要的就是编码过程需要人工干预。

分形压缩的基本原理是利用分形几何中的自相似性原理来进行图像压缩。所谓自相似

性就是指无论几何尺度如何变化，景物的任何一小部分的形状都与较大部分的形状极其相

似。分形用于图像编码，总的来说可以分为两大类。一类可称作分形模型图像压缩编码，

即事先对一类景物建立分形模型。编码时针对具体事物提取必要的分形参数，编码高中学期总结 传送，

实现压缩；另一类可称为IFS分形图像压缩编码，即利用迭代，得到原始图像的一个近似。

后一种实现方法简单，应用较为广泛。目前,图像压缩方法已有近百种,但是,压缩效果、

压缩比以及编码、解码时间还不能满足当前信息时代的要求。传统的压缩算法一般已经成

了定式,发展潜力不大,而分形图像压缩的思想新颖,潜力很大,在人工干预条件下压缩比

达到10000：1时,解码图像还有很好的视觉效果,是一个很有发展前途的压缩方法。

到目前为止，用数学系统去解析地研究分形最成功的是函数迭代系统（Iterated

FunctionSystem,简称IFS），它既包含了确定性过程又包含了随机过程。

对现实世界中的图像集合引入豪斯道夫度量，使其形成一个完备的度量空间，它的每

个点既表示一幅图像，又是欧氏空间的一个紧子集。

1、豪斯道夫距离空间该距离空间被认为是分形所在的空间，而分形之间的距离也

正是由这种豪斯道夫距离度量的。

2、仿射变换

22

定义：一个变换w:R

R

的形式为：

w(x

1

,x

2

)=(ax

1

+bx

2

+e,cx

1

+dx

2+f)

其中a,b,c,d,e,f均为实数，则称w为二维仿射变换，在直角坐标系中，我们可以写成如

下形式：



x



ab



x



e







w





y



cd



y











f







7-1

实际上这是一种最广泛的线性变换,设矩阵



ab



A





cd





7-2

则A的意义可分解为旋转、伸缩、扭曲、反演等。



ab



cos





cd













sin

sin





1tg







l

1

0取得成功









cos





tg



1





0l

2





7-3

如果已知原图及其变换图我们可以求出其中的仿射变换系数，这只要确定原图上三点

和变换图上三点即可，我们可以列出以下方程：

a*x

1

+b*y

1

+e=r

1

7-4

a*x

2

+b*y

2

+e=r

2

7-5

a*x

3

+b*y

3

+e=r

3

7-6

c*x

1

+d*y

1

+f=s

1

7-7

c*x

2

+d*y

2

+f=s

2

7-8

c*x

3

+d*y

3

+f=s

37-9

由以上六方程可求出a、b、c、d、e、f。分形图像压缩的理论基础是迭代函数系统定理、

收缩映像定理和拼贴定理。一个迭代函数系统由一个完备的度量空间和其上的一组收缩映

像组成。

２０３

3、收缩映像定理

函数空间中的每一个收敛映像都有一个固定点，使函数空间中的每一个点经过这个收

缩映像的连续作用后，形成的点列收敛于这个固定点。图7-3是经反复迭代最后收缩成一

图像的过程。

(a)(b)(c)(d)

(e)(f)(g)(h)

图7-3函数空间中的一个收缩映射

4、迭代函数系统定理

每个迭代函数系统都可以构成函数空间中的一个收缩映射。于是，我们得到结论,每

个迭代函数系统都决定一幅图像。一般我们用仿射变换来表示这些映射。IFS中的参数（也

就是对应的仿射变换的参数）的连续微小变化将使IFS对应的图像有微小的变化，如图7-4。

图7-4对应的是b增大反映了x的增大，相当于叶子高处的横向摆动增大，d减小反映了

树叶的整体高度减小。从视觉效果上看，这就是一片风中的叶子。

现在考虑反问题：给定一幅图像，能否找到一个迭代函数系统，而使这个系统正好能

决定给定的图像?这个问题由下面的拼贴定理给出了回答。

２０４

图7-4函数空间中的另一个收缩映射例子

5、拼贴定理

给定一幅图像I，可以选择N个收缩映像，这幅图像经过N个变换得到N个象集，每

个象集都是一块小图像。如果这N个小图像拼贴起来的图像与图像I之间的距离任意小，

则这N个收缩映像构成的迭代函数系统所决定的图像就任意地接近图橡I。这就告诉了我

们寻找迭代函数系统的方法。

三、交互的分形图像压缩方法。

在1990年，Jaquin提出了基于块的分形图像压缩算法。虽然该算法的压缩比低于

ey,但是他的编码过程可自动进行，因此此算法已经成为这一研究方向的典型代

表。Jacquin发展了IFS理论，提出了局部迭代函数理论（PIFS），他在此理论基础上提出

了一种基于方块划分的分形图像压缩方案，在其方案中首先将原始图像划分为固定大小的

方块，然后对每一块，通过反射变换在原始图像的紧缩图像中寻找最相似的部分。这些操

作可由计算机自动完成，他为分形图像压缩的研究带来了一次质的飞跃。

整个图像压缩的过程可以分成两大部分，一是编码过程，一是解码过程。在分形压缩

中，前者主要基于拼贴定理，这个过程中要考虑图像的灰度分布，以及概率求取的策略。

后者主要是随机迭代问题。

编码主要步骤如下：

1、分割成适当的块这可以借助于传统的图像处理技术，如边缘检测、频谱分析、纹

理分析等，当然也可以使用分数维的方法。分割出的每部分可以是一棵树、一片云等；也

可能稍微复杂一些，如一片海景，它包括泡沫、礁石、雾尘等；一般这每一部分都有比较

直观的自相似性特征。

IFS编码求取每一部分求其IFS编码，这就要借助拼贴定理了，同时也是人要参与

的地方，在这个过程中有一些必须注意的地方。

（1）每一块的“拷贝”必须小于原块，这是为了保证仿射变换的收缩性，至于每个拷

贝的大小要根据各块图像的性质来确定。

（2）用于拼贴的每个拷贝之间最好为不相连或紧相邻的。而不要重叠或者有空缺。这

一点对概率的确定很重要，它影响到重构图像的不变测度。所以对有重叠或空缺时，这部

分的“质量”在计算中不能复用或者简单地丢弃，并最终要保证

２０５

p

i

N

i

1

的成立。

3、仿射变换的概率设定拼贴的过程不仅要保证吸引子的形状，也要考虑到每块区域

灰度分布的情况，拼贴结束时要求出各个p

i

，Barnsley等人采取的方法仍然是下式：

a

i

d

i

b

i

c

i

7-10

Area(



i

(T

m))

p

i

Area(T

m)





ad

i

i1

n

i

b

i

ci

其中T

m表示某一分割后的图像块，这种方法有较快的计算速度，这种定义实际上是建

立在均匀测度的假设上的，即吸引子上相同大小的区域有相同的“质量”。但是这在对实

际的灰值图像处理过程中并不总是成立的，往往是经过某个仿射变换后的区域可能面积很

大，但包含的总的灰度能量可能很小；反之某些小区域却有较大的灰度能量。比如在图7-3

中三个小拷贝所占的面积一样多，但各部分的测度显然不同。

为此，一般的方法是对灰度能量多的区域干脆多重叠的几个相同的仿射变换。这在解

码的过程中可能造成的一个结果是重构图中存在伪灰度现象；同时在随机迭代重构时总的

步数也没有确定地给出，只能“足够大”，最后再把灰度归一化到［0，255］。为此，我们

在拼贴的过程中重新定义了概率的求取，令图像块T

m

能量为Q

m

：

Q

m





f(i,j)7-11

(i,j)Tm

f(i,j)表示点(i,j)处的图像灰度,则可定义概率：

ofW

i

(T

m)

7-12

Qm

其中分子表示Tm经w

i

变换后区域中的能量。这时的p

i

应该说可以很好地反映出了图

像内部灰度分配的信息，下面将看到，它还可以指导图像重构，即对每一图像块重构时总

的随机迭代次数就可以设为该块的总能量Q

m

,而每一次迭代生成点的灰度能量为1个单位。

此时概率p

i

计算稍微比前一种方法麻烦些，在计算中可以用w

i

(T

m

)与T

m

的逻辑与来获得

w

i

(T

m

)区域的能量。

4、分形库的建立与使用

对于分类的图像，我们可以预知该类图像中物体出现的范围，在同样使用上述的编码

过程中将会出现重复拼贴一些相似的区域，这种代价是无益的，为此可以使用分形库的方

法。即在库中预存贮着许多有意义的小的形态，当然它们不是以图像格式存入的，否则库

的容量将极其巨大，同样可以以IFS参数的形式来描述它们，则拼贴的过程就变成了用这

些IFS码生成的分形集来与图像中分割后的小区域进行匹配的过程，匹配的近似程度可以

由事先给出的度量公式来确定，这种公式有很多种形式，如均方误差等。一旦匹配好了，

就可以用这些IFS码来替换图像中的区域了。

四、基于分数维分割的图像编码

所有的分形都有一个特征数，也就是分数维去测定其不平整度、复杂度或卷积度。分

数维的微小变化可以引起形状的急剧改变。现实世界中,几何形体可以分为两大类。一类

是规则、光滑的,可以用直线段、平面片或小六面体来逼近,研究这一范畴的学科为传统几

何学。另一类的自然形态是不光滑、不规则的,具有精细的结构或自相似特征,不能用传统

的几何语言描述,我们称之为分形。如海岸线、山形、河川、树木、闪电等自然景物,以及微观世界中复杂且精细的结构、宏观世界里天体演变的各种形态。但这些例子在充分小的

P

i

２０６

Energy

比例下观察时，其分形特征就消失了。但在一定比例下它们表现了许多分形特征，这时我

们可以把它看作分形。

分形学使人们对自然界和人类社会的认识提高到一个崭新的高度。例如,曾使网络性

能模型的研究人员感到震惊的是"以太网数据传输具有自相似的本性",这是由Bellcore和

Boston大学的研究人员发现的。结果证明,Internet网络上数据的传输服从分形特征,不

要期望网上的数据流"光滑输出",由统计多路技术或异步传递模式转换的合并也不会有光

滑输出的数据流。这样流量控制就要重新考虑了。这为网络的合理设计与管理提供了理论

上的依据。

图像的最终目的是让人去观察的，而人的视觉系统（HumanVisualSystem）有其固有

的特性，比如对某些频率分量比对其它的敏感些。因此，对不敏感的部分可以粗略编码，

重构的解码图像也不会有接受不了的质量损失。所以，在编码系统中考虑到了人的视觉特

性将有利于提高压缩比。基于分割的图像编码就是这样一种技术，它根据视觉特征，使用

一些分割方法把图像分成若干类区域，对不同的类再使用不同的编码方法。但是传统的分

割技术有一些限制，比如它是按一定的灰度去划分的，这对一个复杂的纹理区域，可能要

分割成许多块，然而为了得到较大的压缩比我们必须限制分割的数目。因此可采用分数维

的方法。我们知道，分数维是物质的根本性质之一，它直接反映了人眼对表面粗糙度的感

受。这样可以把图像分割成纹理上类似的区域，例如可以分成如下三类，第一类是平滑区

域，第二类为平稳的纹理，第三类是粗糙的纹理。这样对图像分割以后，对不同类的区域

可以采用不同的编码策略，对第一类只要有灰度均值以及边界信息；第二类是要重点对待

的，这是人眼敏感的图像区域；第三类相应于图像中的高频部分，也是人眼不敏感的部分，

此处也可以用较高的压缩比来完成。这种基于视觉特性的分数维分割的图像压缩方法可以

获得相当高的压缩比。

[16,18]

有关分数维的具体含义及求法可参考相关的参考书，分形是和混沌相联系的，混

沌系统的维数一般也是分数维的，我们称其为李雅普诺夫维数，该维数反映了信息丢失的

程度。分形集是动力系统中那些不稳定轨迹的初始点的集合，即混沌集。混沌吸引子就是

分形集。

五、分形在视频图像压缩中的应用

分形压缩可以得到很高的压缩比，但在编码过程中计算量很大。一般是从两个方面试

图解决这一问题，一是要考虑新的算法，二是要考虑用硬件实现。由Barnsley创立的迭

代系统（IteratedSystem）公司已经研制出了板级的可用于彩色图像的分形压缩的硬件，

这种压缩卡对320X200X8的灰度图像在3秒内完成编码，而在解码中只通过软件完成，

不到1秒。当然这种硬件还不能实现视频图像的实时压缩，还有待于进一步的发展，但它

仍然具有广泛应用的价值。

分形图像压缩的编、解码过程是极不对称的。编码比解码要求多得多的时间，相应的

硬件复杂度集中在编码端，这非常适合于一处编码，多处解码的情况，即常说的广播方式。

用户在解码端，因此，不用花费过多的硬件费用，甚至只有软件也行。同时解码过程还有

独立于分辨力的特性，在解码端可以生成任何分辨率的图像，这可能有助于今后HDTV与

TV上信号兼容的问题。

六、当前分形图像压缩的发展状况

Jacquin提出的方案为分形压缩编码的研究注入了生机和活力，分形编码成为目前编

２０７

码研究的热点。目前分形编码方案大致有三个发展方向：加快分形的编解码速度、提高分

形的编码质量、基于分形的低码率视频编码。

发展方向之一：加快分形的编码速度

编码速度慢一直是分形编码实用化的最大障碍，下面分析Jacquin编码方案的计算复

杂度。

对于一个CC大小的图像，假设值域子块大小为KK,定义域子块大小为2K2K,

222

则该图像共有C/K个值域子块、（C-K+1）个定义域子块。在Jacquin的方案中，一个值

2

域子块和一个定义与子块之间的相似性的计算量与K成正比，而对于每一个值域子块，编

22

码计算量与（C-K+1）/K呈线性关系，所以，对于一幅图像来说，其编码复杂度与（C-K+1）

2222224

*K*C/K=（C-K+1）*C成正比，因此，分形编码的计算复杂度为O(C)。所以，减少搜

索、加快编码速度是研究的热点之一。

Jacquin根据子块的复杂度将其分成四类，对每个值域子块，仅在其同类的定义域子

块中进行搜索；采用多维最近邻搜索方法代替传统分形编码中序列的匹配过程，

其搜索匹配时间按指数级增长；等将Jacquin方案中使用的分类器替换成模糊分

类器，并使用遗传算法进行优化，该算法比未分类的编码方案快40%左右；和

通过对匹配块之间关系的研究发现，如果两子块的自身方差相差太远，则这两个

子块不可能相似，由此可去除许多不必要的匹配过程，提高压缩速度10倍以上；MinXue

等将传统编码方案中每个值域子块匹配的串行操作转换为并行操作，计算复杂度下降，缩

短了压缩的时间。

发展方向之二：提高分形编码质量

目前，提高分形编码质量的方法有三种：采用混合编码方案、改进分割方案、改进灰

度逼近能力等。分形与小波的结合编码是目前分形研究的一个新的方向，在本章的第四节

对此加以介绍，并附有实例，加深读者们的理解。

提高编码质量的方法是对传统的分割方法进行改进。Jacquin使用两次分割，在提高

编码质量的同时，又避免压缩比下降太多。随后又有许多学者对上述方法继续进行改进，

提出了四象限的划分方法，使分形压缩的质量和压缩速度有了较大的提高，是目前较为实

用的压缩方法。目前国内外研究者还提出了基于区域的分割方案。

在分形编码中常用的灰度逼近式为w(z)=s*z+t,可把灰度逼近式变为w(z)=t(z),t(z)

可为任意形式，可以为二次以上的多项式，有效提高了编码效果，改进图像质量。

发展方向之三：分形序列图像编码

在实际应用中，序列图像较静态图像有着更广阔的应用，而且由于时间维的引入，编

码方法也有新的变化，因此，序列图像编码是图像编码研究的热点之一。

1994年，加拿大学者Lazar等人发表了一篇论文，加入了时间维，将Jacquin的分形

编码从二维变换直接推广到三维，并直接借用静态图像的分形编码方案，但这样没有充分

利用桢间的相似性，压缩性能不佳。此后，又有人提出了自矢量量化的序列图像编码方案，

但图像恢复质量、压缩比及编码实时上仍不是很理想。因此分形序列图像编码是当今分形

压缩编码的一个重要方向。

第四节分形与其它理论的结合

２０８

分形图像压缩编码的应用已经深入到人类活动的各个方面，并已取得了令人瞩目的成

果。分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相关性，适合于自相似或

自仿射的图像压缩；分形图像压缩解码时能放大到任意大的尺寸，且保持精细的结构；在

高压缩比的情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉效果。对于编

码虽然有许多的改进措施，但是搜索匹配时间长还是不能满足许多实际的需要，基于此，

近几年来，很多学者和专家把分形与其它的技术和工具、方法混合编码取得了很好的效果。

常用的混合方案有与小波变换结合编码、与DCT变换结合编码、与加权有限自动机结合

编码、护肤品哪些好 与向量量化结合编码、与遗传算法结合编码、与FFT算法结合编码、与非线性模型

结合编码、与算术结合编码。近10年来，人们对于自适应块状分形编码进行了不懈的研

究,提出了以上若干改进算法，这些算法在不影响视觉效果的条件下，大大减少了编码时间，

而且在高压缩比和解码图像任意放大方面，比现有的静态图像国际压缩标准JPEG好得多，

已经开始显露出它的优势。分形图像编码方法的实际应用也初见端倪，如分形图像压缩解

码速度很快，当前已经适合于一次写入、多次读出的文档。

由于篇幅有限，这一节重点介绍小波与分形的结合编码、与遗传算法的混合编码以及

与DCT变换结合的编码三种混合编码方案。

一、小波分形混合图像编码

小波图像编码和分形图像编码是两种不同的图像编码方法。其中，小波图像编码是把

图像分解成不同的空间方向和不同分辨率的子带图像，人们可以根据需要，对不同子带图

像采用不同的量化策略来进行编码；而分形图像编码则适用于自相似性较强的图像。可惜

的是，一般的自然图像自相似性并不是很强，但是经过小波变换后的图像，其相同方向但

不同分辨率的子带图像却具有较强的相似性。因此，人们可以利用这种相似性，结合分形

编码的方法来进行编码，以大幅度地提高图像编码的压缩比。因此，小波分形混合图像编

码已成为今后的发展趋势。

经过多级小波变换，一幅图像被分解为一系列尺度、方向、空间局部变化的子带。由

于小波变换能获得很好的空间-频率多分辨率表示，而且在低频处有很好的频率特性，在

高频处有很好的空间选择性，因此符合视觉特性，能量也主要集中在低频子图像。而且同

方向不同分辨率的子带间具有相似性，可以利用分形，二者优势互补，给二者进行混合编

码提供了条件。在传统的分形图像编码中，由于寻找最佳匹配块需要进行大量计算，从而

编码时间过长。而利用小波分解后，图像块所具有的独特空间-频率特性，可以构造较好

的分类和搜索方法，因而大大加快了分形编码的速度。

这种混合编码基本思想简述见实例演示。

二、DCT与分形混合编码

自从分形图像压缩作为一种实用的方法由Jacquin首次提出以来，大多的关于分形图像压缩研究都集中在时间域进行，为了提高编码性能，一些变换域变换编码方法相继由

２０９

Barthel等提出。其中离散余弦变换(Discreteconsinetransformation),余弦调制滤波器组

（Cosinemodulatedfilterbanks）和小波变换等应用最为广泛。

分形图像编码的原理是要寻找一组收敛的仿射变换来重建图像，它利用同一图像中一

部分描述另外一部分，即利用图形的自相似性来减少图像的冗余度。频域变换的一个突出

优点就是他的能量紧凑特性，一幅图像经过频域变换后，总能量没有变化，但能量的分布

却发生了变化。能量将集中在它的低频部分，而高频部分所占的能量非常少，能量的这种

分布对分形压缩十分有利，因为分形图像压缩的主要过程是对同样大小的图像块进行能量

匹配，经过频域变换后，高频部分在能量匹配过程中产生的误差很小，基本可以忽略不计，

这就等于减少了匹配块的大小，从而减小了匹配误差。

去相关能力最强的是K-L变换，但由于其难以实现，人们转而寻找能实时处理的次最

佳变换，离散余弦变换就是其中的一种。近年来的研究表明，离散余弦变换是一种最接近

最佳的正交变换，性能接近K-L变换。

主要编码步骤：

（1）设原图像的大小为N*N,,首先把它划分为（N/8）

2

块大小为8*8的区块（range

block）,对所有的作DCT变换，得到一个N*N的区图像（rangimage）。接着，将原图像

在划分为（N/16）

2

块16*16的域块（Domainblock）,对所有的域块作DCT变换，然后再

经过变换后的16*16图像块中取出他的左上角8*8的块，这些块按照原图的顺序组成一个

域块库。

之所以只取图像左上角是因为域块在经过变换后，主要信息都保存在低频区，对应于

图像块的左上角，而高频区所占的能量相对较少，在以后的匹配中，起的作用很小。因此，

在构成域块时，我们只取左上角与区块同样大小的一部分。

（2）下面则是利用图像的自相似性进行分形压缩，其实质是寻找一组仿射变换，即

块匹配过程。它与时域的块匹配过程完全相同。但由于图像经过频域变换后，具有与时域

不同的特点，因此在具体的实现方法上存在着一些差别。首先，图像在经过DCT变换后,

能量集中到低频部分，特别是它的直流分量，占据了整幅图像能量的很大一部分，这就使

得我们必须对它们单独处理，而不把它带入块匹配的过程中。在匹配过程中，均值分量也

就不再需要。在DCT域分形编码中，我们是将这些直流分量直接作差分之后再进行量化、

熵编码。这样做不仅减少了块匹配的误差，而且在解码时，在第一次迭代过程中，就可以

得到直流分量，从而加快了解码的收敛速度。其次，图像块在经过DCT变换后，能量分

布具有一定的规律，不同于在时域中的杂乱无章的分布，因此在块匹配过程中，旋转所带

来的性能上的改进将变得非常小，与此同时，它却增加了所需的比特数，降低了压缩比。

所以在DCT分形压缩的块匹配过程中，不采用旋转因子。

（3）经过块匹配之后，将阈块的位置信息和仿射变换的系数（这里只有收敛因子）

进行熵编码，以进一步提高压缩比。编码算法可以选用哈夫曼编码或是算术编码。

为了加快编码速度，降低编码的复杂性，有人提出了选择性块匹配的编码方案，也就

是对那些平坦块不去进行块匹配，而是把它的直流分量直接编码输出。感兴趣的读者可以

参阅相关的文献介绍。

三、基于遗传算法的分形图像编码

２１０

遗传算法是模仿生物界的进化过程而得出的一种随机优化方法，对非线性、多极值的

问题尤其有效，它将问题的解编码表示成“染色体”，一群“染色体”组成初始种群，初

始种群置于问题的“环境”中，根据自然竞争、优胜劣汰的原则，种群通过遗传、交叉、

变异不断地进行演化，产生新的种群，这样经过若干代的进化，求得适合问题的最优解。

分形图像压缩中的值域块与定义域块的匹配是典型的多极值问题，由于遗传算法求解

多极值问题的有效性，将其应用于块的匹配（也可称为虚拟码书的搜索），可以大大降低

压缩编码的复杂度，同时很好地保持图像质量。应用于分形图像压缩中的遗传算法主要步

骤包括：

a物种的染色体编码表示。

b种群的初始化。

c适宜函数的选取。

d选择策略。

e交叉策略。

f遗传及变异策略。

g迭代终止准则。

经过许多学者的研究证明，将遗传算法应用于分形图像压缩，效果良好，对每一定义

2

域块需匹配的区域数目，穷尽搜索与遗传算法的比值，在O(10)量级，遗传算法较好地保

持了图像的质量，同时利用遗传算法的并行性可以进一步提高运行的速度。

由于分形压缩编码存在一定的失真度，其编码时间和编码效率与失真度密切相关。另

外分形压缩方法仍有许多尚待解决的问题：

a由于实际上的分形图像形状极不规则，即相似性表现的形式多种多样，只利用规则

的划分未免太勉强人意，需要进一步讨论相似性的提取。

ｂ失真率的研究现在很不全面，应给出更好的度量相似性的方法。

ｃ考虑如何利用图像块本身的特点，更快更好地寻找到匹配块，节省编码时间。

尽管如此，分形图像压缩仍以其高压缩比受到广泛的关注。目前，基于分形－小波混

合编码是研究的热点，还有很多方面可以进一步研究以充分挖掘其潜力：

（1）深入研究小波－分形变换的内在联系，进一步用分形集合的集合相似性来表示

小波分解域内子带间的相似的特征。

（2）对不同的小波基分解后频带的特性和差别加以研究，以挖掘出适合小波－分形

编码的小波基。

（3）将传统的分形编码方法中一些行之有效的思想应用于小波－分形编码。

（4）广泛结合一些目前已经相对完善的技术的优势（如子带编码、矢量量化），充分

利用信号处理的研究成果为图像编码领域注入新的活力。

第五节实例分析—小波与分形混合编码

一、引言

２１１

小波图像编码和分形图像编码是二种不同的图像编码方法,二者各有其特点,又都存在

一定的局限性。

一幅图像经过小波变换后,其相同方向但不同分辨率的子带图像具有较强的相似性。这

种相似结构正好与分形编码的特点具有互补性。如果采用一些新的编码方法,把二者有机

地结合起来,便能大幅度地提高图像编码的压缩比。

Rinaldo和Calvagno提出了一种利用图像小波分解后所表现出来子带间相似性进行分

形编码的方法，即所谓的块预测法。这种方法的主要思想是用变换域低分辨率的子带图像

来预测高一级分辨率的子带图像。Rinaldo提出的块预测法，虽然从理论来说较为简洁，

但由于分形块搜索是在同方向每相邻的两个小波子带内进行搜索，块搜索范围过大，耗时

过长，且并没有充分发掘和利用同方向各个子带间的结构性相似；同样,Levy和Wilson也

发表过类似的研究结果，后来Davis把小波子树的概念引入到分形图像编码中,提出了小波

子树自量化方法(Self-QuatizationofSubtrees)，其主要编码方法是把传统分形图像编

码中的图像块匹配转化为图像树匹配。Davis的方法虽然把图像块扩大为图像树，但却造

成了子树匹配过程中计算量的增大和分形搜索的困难。因此近年来,小波分形混合图像编

[114,116]

码领域内的研究主要是在这两种方法的基础上,进行不断的探讨。显然，这两种方法

都只是从某一个侧面揭示了小波分形的本质特征。

二、快速小波子带分形编码方法的提出

鉴于以上两类编码方法的特点和不足,在小波变换同方向不同分辨率相邻子带块预测

编码的基础上,本书作者提出一种新的快速图像编码方法，主要编码思想由以下四部分组

成：

1、子树位搜索法

相邻子带块预测编码在进行块匹配搜索时,对上一级分辨率子带内所有的块进行全面

的搜索比较,直至找出最相似的匹配块（误差最小的块）。这种块搜索法虽然精度较高,但

范围过大,搜索时间过长。小波子树具有结构上的相似性,即同方向不同分辨率相同位置的

块具有较强的相似性。根据小波子树的这一特点,块匹配时把搜索范围限制在图像树附近,

便能在保持一定的精度的情况下,大幅度缩小块搜索时间,这种在小波子树位置附近块匹

配搜索的方法即为子树位搜索法。

2、子带恢复基础编码法

相邻子带图像编码方法,编码时在小波分解后相邻的两个子带间进行分形预测，但解

码时则在恢复子带的基础上进行预测，这样必然给最后恢复的图像带来失真。为此提出子

带恢复基础编码法，从最低分辨率子带开始进行编码，然后逐级恢复,在恢复子带的基础

上逐级进行分形预测编码。

3、大误差块直接编码法

较低分辨率的子带在图像恢复中起着重要的作用。在多次实验中发现，越是低分辨率

子带,分形预测的误差越大,而这些误差较大的块（两个子带间相似程度差的块），在图像

恢复中起着极为关键的作用。为了减少误差,提高恢复图像质量,对一些低分辨率子带进行

块预测时,当块匹配误差超过某一门限值时,不再对这些块进行分形预测编码，而是直接记

２１２

录其值，进行无失真编码，这种方法即为大误差块直接编码法。大误码差块直接编码法虽

然在一定程度上降低了压缩比,但对保留图像重要信息,提高图像恢复质量起着关键作用。

整个编码方案的实现如图7-5所示(d1为块匹配误差门限值)。

图7-5快速小波子带分形编码流程图

三、计算机仿真实验及结果分析

1、实验环境

在多次的实验中,我们发现Bior4.4小波在图像分解与恢复中有较好的效果,故这里用

Bior4.4小波对512512的Lena和testpat1两个标准灰度图进行5级小波分解.实验使用微

机为PⅢ933,128M内存;编程语言为MATLAB6.0。

2、实验参数

实验用小波分解层数为五级,对第四级小波分解的低频子带直接进行无失真编码,块

匹配分形预测编码从第四级三个高频子带开始。

快速子带算法匹配块的大小根据子带分辨率的不同从低到高分别为:44、88、

1212、2626;相邻子带算法匹配块的大小分别为:33、66、1212、2626。

快速子带算法在小波分解第四级、第三级采用大误差块直接编码法。实验1中两级的

误差门限值分别为离职感谢语 6500、3000,直接进行无失真编码的块数Lena图为55、38,Testpat1图为

105、78;实验2中两级的误差门限值分别为6500、3000,直接进行无失真编码的块数Lena

图为92、38,Testpat1图为141、78;实验3中两级的误差门限值分别为6500、3000,直接进

行无失真编码的块数Lena图为157、38,Testpat1图为196、78。

3、实验结果

２１３

表7-1和表7-2分别为对Lena图和Testpat1图进行实验的结果,快速子带编码实验(1-6)

为在不同无误差门限值情况下采用新的改进方法进行的实验;为了说明子带恢复基础编码

法的作用,本节还进行不采用子带恢复基础编码法对比实验,此实验的其它条件与实验1或

4相同。

实验中所用峰值信噪比PSNR的计算公式为:

PSNR10lg

255

2MN

7-13

2



[f(m,n)f



(m,n)]

m1n1

MN

其中，f(m,n)为原始图像;f‵(m,n)为恢复图像;M,N为图像的总行数和总列数。d1为

第四级小波分解子带块匹配误差门限值,d2为第三级小波分解子带块匹配误差门限值。

表7-1Lena快速小波子带分形编码和相邻子带编码参数比较

实验名称压缩倍数PSNR/db编码时间/S误差门限值(d1,d2)

快速子带编码实验131.99128.6601086500,3000

快速子带编码实验225.56329.7781063000,3000

快速子带编码实验323.83430.510105650,3000

子带恢复法对比实验31.99128.5871076500,3000

相邻子带编码实验31.51924.68052800

a原始图像b相邻子带编码图c快速子带分形编码图

d快速子带分形编码实验2图e快速子带分形编码实验3图f子带恢复法对比实验图

图7-6实验1Lena实验结果图比较

表7-2Testpat1图快速小波子带分形编码和相邻子带编码参数比较

实验名称压缩倍数PSNR(db)编码时间(S)误差门限值(d1,d2)

２１４

快速子带编码实验422.67229.3071096500,3000

快速子带编码实验521.83429.8641083000,3000

快速子带编码实验620.65230.261107650,3000

子带恢复法对比实验22.67229.2571076500,3000

相邻子带编码实验31.51916.58852880

g原始图像h相邻子带编码图i快速子带分形编码实验4图

图7-7Testpat1实验结果图比较

j快速子带分形编码实验5图k快速子带分形编码实验6图l子带恢复法对比实验图

4、实验分析

从以上对Lena和Testpat1两个灰度图所进行的快速子带编码算法与基本的相邻子带

算法对比结果来看,在压缩倍数相近的情况下,快速子带算法在编码时间方面有500多倍

的提高,反映恢复图像质量的PSNR值也有较大提高;从是否采用子带恢复基础编码实验对

比结果来看,采用子带恢复法后PSNR值有所增加。显然,快速子带算法较相邻子带算法在编

码时间和恢复图像质量方面均有较大提高。

以上理论分析和实验证明,本文提出的快速小波子带分形图像编码算法,相对于相邻

子带编码算法,由于吸收了小波子树分形编码的优点,有效地缩小了子带块搜索范围,极大

地减少了编码时间;同时由于采用了子带恢复基础编码法和大误差块直编法堤亚纳河谷 ,对编码过程

带来的误差进行了修正,使恢复图像质量有了较大的改善。

通过以上分析，得出如下结论：

分形图像编码的过程是依据拼贴定理，通过给定的图像，寻找一组收缩映射，使其组

成的迭代函数系统的吸引子逼近给定图像，然后记录下相应参数。解码过程是由相应参数

确定迭代函数系统，并根据迭代函数系统定理，经过迭代生成图像。分形图像压缩的思想

新颖、潜力很大，其在压缩比达10000∶1时，解码图像仍有很好的视觉效果，它是一个

很有发展前途的图像压缩方法。但是，实现自动IFS编码（没有人工干预）仍有相当难度，

２１５

该领域至今仍存在许多问题有待解决。本章对分形图像压缩的理论基础和实现的关键技术

进行了全面综述，介绍了具有代表性的各种新方法，阐明了各个方法的特点，最后简要总

结一下分形图像压缩的改进以及发展趋势：

1、分形图像压缩的改进方法

（1）提高压缩比和编码效果常用的改进方法

改进分割的方法：有基本四叉树分割法、基于HV分割法。这两种分割方法都是将图

像分割成矩形。而图像块的相似性未必都落在矩形内。代替水平或垂直部分而采用的分割

方法有基于三角形分割法、基于六边形分割法、基于边界分割法、基于菱形分割法、基于

多边形分割法。

改进覆盖式方法：覆盖式方法有快速覆盖式分形压缩方法和四叉树重组QR算法两种。

它们都是采用通过合并值域块来提高压缩比。前者要求合并后不一定规则,后者合并后则

是规则的。

提高显示效果的后处理法：分形图像压缩对值域块独立编码,这不能保证块与块之间

的连接是光滑的,常有块效应出现,人的眼睛对此比较敏感。消除块效应的一个常用方法是

后处理,一般采用加权平均法。

（2）提高编码速度

编码过程中最耗时的是搜索最佳匹配的定义域块,要提高编码速度,就必须缩小搜索

范围,且保证最佳匹配落在该范围之内。其改进方法有:

分类法：搜索最佳匹配计算量很大,占用了编码的大部分时间,因而限制了它的实际应

用。为了缩短搜索时间,在匹配之前按照图像的特征如中值、方差、力矩和其它感知或统

计的几何特征,将定义域和值域块进行分类,匹配时只在同一类中进行搜索比较。这样在不

降低图像质量的前提下,大大提高了编码速度。常用的分类方法有:基于明暗度的定向分

类、基于空域特征的分类、基于相对矩的分类、基于小波的分类、基于人类视觉系统(HVS)

分类、基于模糊分类、原形的分类、自适应码本簇化的分类、向量量化的分类。以上各种

方法分别从不同的角度、使用不同的工具对图像块分类,各自保持了自己的特点,对加速编

码有不同程度的作用。

搜索法：匹配搜索耗时最长,常用的加速搜索方法有:局部搜索法、提取特征追踪法、

基于方差搜索法、FFT搜索法。

（3）提高解码速度

分形解码速度相对于编码要快得多,一般它迭代10次左右即可完成。然而对于一些实

际应用来说,仍然希望迭代次数越少越好,这样可以进一步加快解码速度。常用的加速方法

有金字塔式解码器、去均值解码算法、非迭代算法、BCC和ICC算法。

2、分形图像编码的优点

10多年来，虽然分形图像自动编码和解码不断改进．但仍然不够成熟，产生的压缩比

不够高，压缩效果还不十分理想，在当前图像压缩编码中还不能占据主导地位。国际标准

MPEG-4中已经把小波列了进去，但分形不在其中。静态图像压缩标准JPEG2000是完全使

用小波的图像编码方法，也没有把分形列进去。但我们应该看到分形图像压缩方法的优势

和巨大潜力。

（1）分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相关性，适合于自

相似或自仿射的图像压缩，而自然界中存在大量的自相似或自仿射的几何形状。因此，它

的适应范围很广。

（2）分形图像压缩（当前尚须人工干预）能获得相当高的压缩比(10000：1甚至更高)

和很好的压缩效果，具有很大的潜力。

（3）分形解码时能放大到任意大的尺寸，且保持精细的结构。

２１６

（4）在高压缩比的情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉

效果，这是其它方法不能相比的。因此．分形图像压缩是一个有潜力、有发展前途的压缩

方法。

3、分形图像编码的发展趋势

分形图像压缩编码研究发展趋势将有如下几个方面：

（1）分形编码在人工干预条件下能够达到相当高的压缩比。但对于如何去掉人工干

预则需研究给定的图像，实现计算机自动确定分形生长模型、L系统、IFS码和RIFS码

等，寻找新的压缩模型和新的突破点。

（2）综合分析当前自动编码的各种改进算法，在此基础上，继续寻找加快编码速度、

提高压缩比、改善压缩效果的突破性的改进方法。

（3）研究按分形维数分割图像，将分形维数相同的区域块用分形方法进行编码的理

论、方法和实现的算法。

（4）继续研究分形编码与其它编码方法相结合的新的编码方法。

（5）对分形图像压缩的计算机仿真和实际应用的研究。

习题七

一、针对曼德波罗图，如图习题7-1所示。

图习题7-1

（1）找出其中隐藏的“所有的”自然数，找出分布规律。

（2）在1、2、4、8……后面，有很长的带“刺”的线段，有何含义？

（3）分析一个自然数集合的子集合，简述其特点。

（4）分析Mandelbrot图这一“数学恐龙”，找一个较“美”的图形。

[16]

二、作出如下很好的迭代分形图（本题目引自文献）。

（1）BraayMartin提出一个公式



x

new

ySgn(x)Sqr(Abs(bxc))

y



new

ax

２１７

其中



1

Sgn(x)



1



0

x0

x00

,

Sqr(x)

x,

Abs(x)x

x，y为变量，a，b，c为可控常数。迭代初值为（0，0），a，b，c初值为，

a

45

0.4

90

10

-200

-137

10-137

b

2

1

30

-10

-4

17

10017

C

-300

0

10

100

-80

4

-104

（2）Martin给出的另一个公式



xysin(x)



yax



其中a是实参数，a与间相差0.07以内。

（3）Gumowski及Mira在研究同步质子加速器中粒子的运动轨迹的混沌行为时，提

出迭代方程



x

n1

(1b)F(x

n

)bx

n1



2

2x

F(x)ax(1a)

2

1x

在平面坐标的形式是



x

n1

by

n

F(x

n)



y



n1

x

n

F(x

n1

)

2



2x



F(x)a(1a)2

1x

在-1

的图形，这里开辟了一个计算机艺术的广阔天地。如

a

２１８

b

起始点

观察区域

-0.4

0.31

0.32

-0.4

-0.2

0.3

0.3-0.05

0

(4,0)

(12,0)

(5,0)

(20,0)

(10,0)(2,0)

(7,0),(12,0),(-21,0)

(2,0),(7.5,0),(9.8,0),(15,0),(18,0),(20,0),(25,0)

(-24,-18)~(24,18)

(-60,-45)~(60,45)

(-20,-15)~(20,15)

(-40,-32)~(40,32)

(-24,-18)~(24,18)

(-6,-4.5)~(6,4.5)

(-40,-30)~(40,30)

(-40,-30)~(40,30)

0.18

-0.25

-0.48

-0.4

0.01

0.10.7

(5.3,0),(8,0),(9,0),(15,0),(20,0)

0.998(0.998)

0.93

0.99

0.960.99

(0.93)

(0.99)

(0.96)(0.99)

(-32,-24)~(32,24)

(-16,-12)~(16,12)

(-16,-14)~(16,10)

(-16,-12)~(16,12)

(-16,-12)~(16,12)

(-12,-9)~(12,9)

(-20,-15)~(20,15)

0.9998(0.9998)

F(x)的形式也可以取

F(x)axcsinx

F(x)axccosx

F(x)acsinx

F(x)ax

cs

2

1x

F(x)还可以是分段函数

ax



F(x)



axc(x1)





axc(x1)

x1

x1

x1

对于这个分段函数，参数可取

a

2

3.50.9

b

1

c

-2

-3-1.4

起始值

(0.1,0)(0.1,0)

(12,0),(4.8,0),(2,0),(11,0)

２１９