当前位置： >>
什么是分形
引言自然界是宇宙万物的总称，是各种物质系统相互作用相互联系的总体，它包括 大至宇宙天体的形成演化，小到微观世界中基本粒子的运动。随着牛顿经典力学的 创立，爱因斯坦相对论，以及量子力学的发展，人类在自然科学方面已经取得了辉 煌的成就；随着天体物理学以及其他相关学科的迅速发展，人类已经登上月球，进 入太空；人类对微观世界由质点组成的简单系统的运动规律也有了全面
而正确的认 识。尽管如此，如果人们稍微注意一下周围环境中发生的大量非线形不可逆现象， 就会发现，人们对这些现象知之甚少，对许多问题甚至于束手无策。举一个通俗的 例子，当你仰望蔚蓝的天空，常常可以看到天空中漂浮着一团团白云，尽管它的形 态是千变万化的，但是如果用不同倍数的望远镜来观察云团时，它的形态几乎是保 持不变，也既是说白云的形态和望远镜的放大倍数无关。 分形的原文 Fractal 是 Mandelbrot 用拉丁词根进行拼造出来的单词， 意思是细 片，破碎，分数等等。它是描述不规则几何形态的有效的工具。自然界中，绝大部 分物体形态不是有序的，稳定的和确定性的，而是处于无序的，不稳定的，非平衡 的和随机的状态之中。然而，曲折绵长的海岸线，凹凸不平的地表，变幻无常的浮 云，错综复杂的血管等等，诸如此类的不规则几何形态都是传统数学和物理学难以 描述和表达的。也正是于此，当 Mandelbrot 提出分形的概念后，才会引起科学界的 极大兴趣和轰动。人们对这一新兴学科感到震惊，因为它是如此的贴近生活，如此 具有诱人的发展前景，如此具有巨大的应用价值。 分形理论使人们能以新的观念，新的手段来处理这些难题，透过扑朔迷离的无 序的混乱现象和不规则的形态，揭示隐藏在复杂现象背后的规律，局部和整体之间 的本质联系。分形理论在某些学科的成功尝试，极大地激发了科学研究工作者的兴 趣，他们把分形理论逐渐扩展到其它的学科领域，更进一步的促进了分形学的发展。 无论是国内还是国外都不定期的召开一些关于分形的学术会议，一时间关于分形理 论的学术论文如火如荼的发表在各种期刊杂志上。 分形所涉及的领域极为广泛，包括哲学，数学，生物学，物理学，材料科学， 医学，农学，气象学，天文学，计算机图形学等，可以说如今的分形无处不在。分 形的发展，一部分得益于由分形产生的图形让人如痴如醉，但是更多的是因为分形 的实用价值。采用分形方法，可以利用少量的数据生成各种不同的复杂的图形。根 据分形的自相似性，能够对图形图像进行有效的压缩。美国著名物理学家惠勒说过： 今后谁不熟悉分形，谁就不能被称为科学上的文化人。 尽管分形理论从 Mandelbrot 的提出距今只有短短的三十多年的时间， 但是其发 展速度可谓是日新月异，让人刮目相看。分形理论 20 世纪 70 年代末传入我国，在-1-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建我国的科研人员，学者的共同努力下，其理论研究和应用获得了飞速的发展。1986 年北京大学成立了非线性科学中心。1989 年 7 月在成都四川大学召开“第一届全国 分形理论及应用学术讨论会” 。1991 年 11 月在武汉华中理工大学召开第二届会议。 1993 年 10 月在合肥中国科技大学召开第三届会议。仅从这些学术会议就可以看出， 我国对分形研究的重视。我国的科学家们积极进行分形理论的研究，探索，并取得 了丰硕的成果。其中产生了不少分形领域的专家和学者。他们的研究理论成果为推 动我国乃至国际分形的发展做出了不可磨灭的贡献。 虽然分形产生的图形是复杂的，美丽的，实用的，但是描述它们的方法却是简 单的。现在有效的描述方法有林式系统(L-systems，简称 L 系统)和函数迭代系统 (Interated Function System，简称 IFS 系统)。前者是由是林德梅叶 1968 年为模 拟生物形态而设计的，后来史密斯于 1984 年 、普鲁辛凯维奇于 1986 年，分别将它 应用于计算机图形学，引起生物学界和计算机界人士极大兴趣，一时发表了许多论 文和专著。后者是美国佐治亚理工学院的巴恩斯利教授首创的。IFS 系统的理论与 方法是分形自然景观模拟及分形图像压缩的理论基础，其基本思想是认为物体的全 局和局部在仿射变换的意义下具有自相似结构，这就形成了著名的拼接定理。IFS 方 法 的 魅 力 在 于 它 是 分 形 迭 代 生 成 的 “ 反 问 题 ” ， 根 据 拼 接 定 理 (collage theorem)，对于一个给定的图形(比如：一张照片)，求得几个生成规则，就可以大 幅度压缩信息。 分形作为一门新兴学科，其应用潜力是巨大的，尤其是在计算机模拟方面更是 具有很大的实用价值。所以，学习和研究分形，实现分形在实际生活中的应用，都 具有一定的诱惑力。 本文第一章从分形的基本理论知识入手，结合分形的发展历程，阐述了分形的 基本概念，以及分形维数。第二章通过几个典型的分形实例简单的说明了分形的构 造过程。第三章详细地介绍了两种分形的描述方法(L 系统和 IFS 系统)。虽然 L 系 统和 IFS 系统生成分形图形的实现简单明了，但是它们所形成的图形是二维的，这 样的视觉效果和真实自然界的物体形态有很大差别。所以本文在第四章节中探讨了 几种实现三维的算法，这样生成的图形视觉效果得到了很大的改观。第一章 什么是分形1.1 分形的由来1975 年，美籍法国数学家曼德尔布罗特(B.Madelbrot)根据拉丁文形容词 “fractus” ，并对其加以改造，成为现今广为人知的“fractal” ，它的含义是不规 则的，琐碎的，支离破碎的等。我国则把它翻译成“分形” 。曼德尔布罗特使用-2-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建“fractal”来描述大自然中各种不规则的事物形态，比如：曲折绵长的海岸线，错 综复杂的血管，延绵起伏的山脉等。他们具有一个共同的特征，那就是他们的形态 是不光滑的，粗糙的，是无法用传统的数学，物理学描述的，这就是分形。1.2 分形的发展历程分形某些概念，最早可追述到一百多年前，接着又有不少科学家提出分形的图 例和理论，但是那时由于受传统理论的约束，不仅没有得到应有的发展，而且被一 些科学家视为“异类” ，是不合常理的，是不能接受的。涉及分形理论的典型代表有 1860 年，瑞士一个数学家塞莱里埃(C.Cellerer)提出“连续函数必定可微”是错误 的，并给出反例。1883 年，德国数学家康托(G.Cantor)构造的康托三分集。1890 年 意大利数学家皮亚诺(G.Peano)构造的平面曲线，它是一种充满空间的曲线，称为皮 亚诺曲线。1904 年，瑞典数学家柯赫(H.von Koch)构造出柯赫雪花曲线。1910 年， 德国数学家豪斯道夫(F.Hausdorff)开始了奇异集合性质与量的研究， 提出分数维概 念等。1919 年，豪斯道夫(F.Hausdorff)给出维数的新定义，为维数的非整数化提 供了理论基础。 尽管前人的理论没有得到应有的重视，但是它却为以后分形理论的发展奠定了 基础。曼德尔布罗特于 1967 年在科学杂志上发表了一篇具有启发性的文章： “英国 的海岸线有多长？” ，引起了世人的关注。1975 年曼德尔布罗特用法文出版了第一 部分形著作《分形对象：形、机遇和维数》 。之后，曼德尔布罗特又对该著作加以修 改，加入了他对分形几何的新的思想、观点。1982 年，曼德尔布罗特又出版了《自 然界的分形几何》 。在这该著作中他为分形重新加以定义。在这期间，又有很多科学 家投入到分形的研究领域，促使分形得到长足的发展，其中有 1982 年特里科特 (C.Tricot)引 入填 充维数 ， 1983 年格 拉斯 伯格(P.Grassberger) 和 普罗克 西 娅 (I.Procaccia)提出根据观测记录的时间数据列直接计算动力系统吸引子维数的算 法。1985 年，曼德尔布罗特提出并研究自然界中广泛存在的自仿射集，它包括自相 似集并可通过仿射映射严格定义。1982 年德金(F.M.Dekking)研究递归集，这类分 形集由迭代过程和嵌入方法生成，范围更广泛，但维数研究非常困难。1989 年，钟 红柳等人解决了德金猜想，确定了一大类递归集的维数。随着分形理论的发展和维 数计算方法的逐步提出与改进，1982 年以后，分形理论逐渐在很多领域得到应用并 越来越广泛。 自然界的物体形态不是固定不变的，稳定的，它们的形态变化多端，所以在描 述它们的时候也应该采用随机方式， 这样才能充分体现其一般性。 基于这一点， 1968 年曼德尔布罗特研究布朗运动的随机过程时，将其推广到与分形有关的分数布朗运 动。1974 年他又提出了分形渗流模型。1988 年柴叶斯(J.T.Chayes)给出了详细的数 学分析。1984 年，扎乐(U.Zahle)通过随机分形模拟出更真实的自然现象。-3-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建1.3 自相似性一个系统的自相似性 [1] 是指某种结构或过程的特征从不同的空间尺度或时间 尺度来看都是相似的，或者某系统或结构的局域性质或局域结构与整体类似。对于 欧氏几何而言，它们的形态是极其规则的，而且是严格对称的，人们描述起来很容 易，例如：我们想要描述一个圆形，那么只要给出圆点和半径，就能很快得出具体 的图形。然而，对于不规则的物体形态，我们就会显得束手无策。凹凸不平的地表， 怪石林立的山峰，诸如此类的实物形态，我们是无法用欧氏理论描述的。尽管大自 然的物体形态是千变万化的，但是如果我们从一个分形上任意选取一个局部区域， 对其进行放大，再将放大后的图形与原图加以比较，我们发现它们之间形状特征呈 现出令人惊讶的自相似性。举一个例子，对于一支花朵，有主干和支干，如果把支 干掰下来和主干比较，那么它们之间极为相似，如果再仔细地看一看花心的话，又 会发现花瓣和花瓣之间是对称的，而且也是相似的。总而言之，物质的各个部分都 或多或少的具有自相似结构。 物体的自相似性为科研人员提供了研究事物新的思路，那就是，既然物体的形 态是有规律可寻的，那么我们就有办法对其进行描述。基于这一思想，我们可以利 用物体的自相似性，定义一个简单的图形规则，再在这个规则的基础上不断的进行 规则迭代，最终会生成让人意想不到的图形。 当然，自然界的事物是自相似的，但不是严格的完全的相似。尽管我们观察的 分形体有很多的相似之处，然而，严格的来说它们还是有一定差别的。这就存在一 个问题，即是相似度 [1] 。它用来表示一个分形的局部与局部以及局部与整体之间的 相似程度。另外，相似并不代表相同或者简单的重复 [1] 。如果我们将局部图形用放 大镜放大 X 倍后，不一定会和原图完全吻合，这一点应该值得注意。1.4 分形的维数欧氏几何学具有几千年的历史，它研究的是一些规整的图形，比如：直线，圆， 椭圆，菱形，正方形，立方体，长方体，球体等。这些不同类型的曲线和形状都有 一个共同的基础――欧氏几何，即它们可以被定义为代数方程(例如：Ax + By + Cz = D)或微分方程的解集。从欧氏几何测量中，可以看出点、直线、平面图形、空间 图形的维数分别是 0，1，2，和 3，而且都是整数。 维数是几何对象的重要特征量，维数包含了集合的几何性质的许多信息。一个 图形维数的大小，表示它占有空间的大小。尤其是在分形中，它对如何准确地描述 图形起到了很大的作用。分形维数是判断两个分形是否一致的度量标准之一。-4-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建1.4.1Hausdorff 维数 上面已经述说了，欧氏维数都是整数。然而，现实生活中遇到的物体的维数常 常不是一个整数值。1919 年，波恩大学数学家豪斯道夫(Felix Hausdorff)从测量 的角度获得 Hausdorff 维数的定义，它为不规则物体的描述提供了数学依据。 在表述 Hausdorff 维数之前，先说一说 Hausdorff 测度。如果 U 为 n 维欧氏空 间 R n 中任何非空子集，U 的直径定义为|U|=sup{|x-y|：x，y ∈ U}，即 U 内任何两 点距离的最大值，式中的 sup 是上确界的缩写。如果{U i }为可数（或有限）个直径 不超过 δ 的集够成的覆盖 F 的集类， F ? 即 则称{ U i }为 F 的一个 δ -覆盖。 设 F 为 R n 中的任何子集，s 为一非负数，对任何 δ &0,定义 H δ (F)=inf{sUUi =1∞i， 且对每一个 i， 都有 0&| U i |≤ δ ,∑|Ui=1∞i| s ：{ U i }为 F 的 δ -覆盖}(1.0)式中的 inf 是下确界的缩写。 于是考虑所有直径不超过 δ 的 F 的覆盖，并试图使这些直径的 s 次幂的和达到 最小。当 δ 减少时，式 1.0 中能覆盖 F 的集类是减少的，所以下确界 H δ (F)随着增s加且当 δ →0 时趋于一个极限(集合的上确界与下确界直观地被认为是集合的最大值 与最小值)。 记作 H s (F)= lim H δ (F)δ →0 s(1.1)对 R n 中的任何子集 F， 这个极限都存在， 但极限值可以是(并且通常是)0 或 ∞ 。 s H (F)就被称为 F 的 s-维 Hausdorff 测度。 长度，面积和体积的比例性质是众所周知的，当它们的比例放大 λ 倍时，曲线 的长度放大 λ 倍，平面区域的面积则放大 λ 2 倍，三维物体的体积则放大 λ 3 倍。 同样，Hausdorff 测度也符合这一规律。所以，一个 s 维的 Hausdorff 测度对物体 放大了 λ s 倍。 容易看出对任何给定的集 F 和 δ &1， δ (F)对 S 是不增的， Hs 因此由(1.1)式 H s (F) 也是不增的。事实上，有更进一步的结论：若 t&s，且{ U i }为 F 的 δ -覆盖，则有-5-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建∑|Uii|t ≤ δst? s∑|Uii|s(1.2)取其下确界，得 H δ (F)≤ δst? sH δ (F)。令 δ →0，对于 t&s，若 H s (F)& ∞ ，则H t (F)=0。所以 H s (F)存在 s 的一个临界点使得 H(F)从 ∞ “跳跃”到 0。这个临界值 称为 F 的 Hausdorff 维数。 1.4.2 拓扑维数 拓扑维数是比分形维数更基本的量，以 D T 表示，它取整数值，在不作位相变换 的基础上是不变的，即通过把空间适当地放大或缩小，甚至扭转，可转换成孤立点 这样的集合的拓扑维数是 0，而可转换成直线这样的集合的拓扑维数是 1。所以拓扑 维数就是几何对象的经典维数，在一般情况下，点是 0 维，线是 1 维，面是 2 维， 体是 3 维。拓扑维数是不随几何对象形状而变化的整数维数。 1.4.3 计盒维数 计盒维数是应用最广泛的维数之一，它的普遍应用主要是由于这种维数的数字 计算及经验估计相对容易一些。 设 F 是 R n 上任意非空的有界子集，N δ (F)是直径为 δ ，可以覆盖 F 的集的最少 个数，则 F 的下、上计盒维数分别定义为 [1]DimB F = limδ →0log N δ ( F ) ? log δ log N δ ( F ) ? log δ(1.3)DimB F = limδ →0(1.4)如果这两个值相等，则称这共同的值为 F 的计盒维数，记为DimB F = limδ →0log N δ ( F ) ? log δ(1.5)1.5 分形维数的计算-6-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建在欧氏几何中， 维数通常表示为在空间中确定一个点所需要的独立坐标的数目。 要确定一条直线上的点需要一个独立坐标，其维数是 1；要确定平面上的点则需要 两个独立的坐标，其维数是 2；确定三维空间上的点则需要三个独立的坐标，其维 数是 3。但是也可以通过其它的方法来计算欧氏几何的维数。 把一个几何对象的线段放大 X 倍，如果它自身是原来几何体的 Y 倍，那么该对 象的维数是 D=lnY/lnX (1.6) 例如，把一个正方形的每边放大 2 倍，那么它自身将变为原来的正方形的 4 倍，也 就是说，X=2，Y=4，所以 D=ln4/ln2=2，说明正方形的维数是 2。 上面表述了欧氏几何维数的计算，推而广之，如果把一个正方形分成 4 个小正 方形，每个小正方形是原来边长的 1/2， 小正方形的面积是原正方形的 1/4，则此 时 X=1/2，Y=1/4，再利用(1.6)式带入计算,同样可得 D=2，既是正方形的维数为 2。 这个例子属于分形的一种。当然，在计算分形维数中最为常用并且最具有代表性的 是 Hausdorff 维数，公式如下： D H = lnＮ(r)/ln(1/r) (1.7) 式子中的 D H 可以是整数，也可以是分数。值得一提的是，这个公式也适用于欧氏 几何。 例如， 下面将要介绍的 Koch 曲线， 由于它的基本单元由 4 段等长的线段构成， 每段长度为 1/3，那么Ｎ=4，r=1/3， D H = ln4/ln3 = 1.26181.6 分形的定义对于分形的概念一直没有严格的定义。不同学科领域的学者对分形的理解是不 同的，所以很难给出统一的，让所有的科研人员都能接受的定义。曼德尔布罗特先 后对分形给出两个定义，第一个定义是 1982 年提出的，四年后，他又提出了更为实 用，更易于理解的定义，所以后一种定义一直沿用至今。 定义 1.1 如果一个集合在欧氏空间中的 Hausdorff 维数 D H 恒大于其拓扑维数 D T 即 D H & DT 则称该集合为分形集，简称为分形 [1] 。 定义 1.2 组成部分以某种方式与整体相似的形体叫分形 [1] 。 对于定义 1.1 的理解需要一定的数学基础， 不仅要知道什么是 Hausdorff 维数， 而且要知道什么是拓扑维数，看起来很抽象，也不容易推广。定义 1.2 比较笼统的 说明了自然界中的物质只要局部和局部或者局部和整体之间存在自相似性，那么这 个物质就是分形。正是这一比较“模糊”的概念被人们普遍接受，同时也促进了分 形的发展。 根据自相似性的程度，分形可分为有规分形 [1] 和无规分形 [1] 。有规分形是指具-7-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建有严格的自相似性的分形，比如，三分康托集，Koch 曲线。无规分形是指具有统计 意义上的自相似性的分形，比如，曲折绵长的海岸线，漂浮的云等。1.7 本章小结曼德尔布罗特提出分形后，分形作为一门新兴学科引起了科学界的极大关注。 本章首先由分形的发展历程开始，简要的介绍了一些科学家对分形所作出的杰出贡 献。他们的研究理论推动了分形的发展。Hausdorff 维数的提出，为分形提供了数 学基础，使许多维数不是整数的物体能够得到准确的表述，为分形的发展奠定了坚 实的基础。第二章 几种典型的分形2.1 三分康托集1883 年，德国数学家康托(G.Cantor)提出了如今广为人知的三分康托集。三分 康托集是很容易构造的，然而，它却显示出许多最典型的分形特征。它是从单位区 间出发，再由这个区间不断地去掉部分子区间的过程构造出来的(如图 2.0)。其详 细构造过程是：第一步，把闭区间[0，1]平均分为三段，去掉中间的 1/3 部分段， 则只剩下两个闭区间[0，1/3]和[2/3，1]。第二步，再将剩下的两个闭区间各自平 均分为三段， 同样去掉中间的区间段， 这时剩下四段闭区间： [0， 1/9]， [2/9， 1/3]， [2/3，7/9]和[8/9，1]。第三步，重复删除每个小区间中间的 1/3 段。如此不断的 分割下去， 最后剩下的各个小区间段就构成了三分康托集。 三分康托集的 Hausdorff 维数是 0.6309。 三分康托集具有很多性质，下面简要介绍其中的一些性质(令三分康托集为 F)： (1) 康托集是自相似的。显而一见，区间[0，1/3]和[2/3，1]内的 F 的部分与 F 是几何相似的，相似比为 1/3。在[0，1/9]，[2/9，1/3]，[2/3，7/9]和[8/9，1] 四个区间内，F 的部分也与 F 相似，其相似比为 1/9。依次类推，这个集包含很多不 同比例的与自身相似的样本。 (2) F 有“精细结构” ，它包含有任意小比例的细节，越放大三分康托集的图， 间隙就越清楚地呈现出来。 (3) 康托集是完备的闭集合，并且是非空的，故又称“非空完备集” 。 (4) 尽管 F 有错综复杂的细节结构，但 F 的实际定义却非常简单明了。 (5) F 的几何性质难以用传统的术语来描述，它既不是满足某些简单条件的点 的轨迹，也不是任何简单方程的解集。-8-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建(6) F 的局部几何性质也难以描述的，在它的每点附近都是大量被各种不同间 隔分开的其它点。 (7) 虽然 F 在某种意义上是相当大的集(是不可数无穷的)，然而，它的大小不 适合用于用通常的测度和长度的度量，用任何合理定义的长度来度量，F 的长度总 为零。图 2-0三分康托集的构造过程推而广之，假如我们在平面上构造康托集，那么最终生成的集合称为康托尘。 康托尘的构造和三分康托集的构造很相似，它是将一个正方形分割成 16 个小正方 形，保留其中的四个，去掉其它的小正方形，依次类推，无限的循环下去。康托尘 具有和康托集相似的性质，这里不在论述。如果去掉不同的正方形，所获得的集合 是不同的。 前面介绍的是非随机的有规分形，当然也可以构造随机的三分康托集。例如， 在构造三分康托集的过程中，每一个区间要分成三个小区间，但是在具体舍弃哪一 个 1/3 线段上不是事先确定好的，而是随机的。每次把线段分成三部分，不是总是 去掉中间的一段，而是靠类似投骰子的方法决定的。随机的三分康托集构造过程如 下图 2.1 所示(由于是随机的，所以生成的集合无数种，这只是其中的一种)。-9-PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建图 2-1 随机三分康托集的构造过程一般来说，在构造随机的三分康托集时，有两个条件是可以改变的，一是对初 始长度进行多少等份或者不等份的规定；二是留下哪些部分，去掉哪个部分 [1] 。既 然是随机的，那么在构造过程中应该在所有的尺度上也表现其随机性，也就是说应 当在构造过程中每一步，都使用随机的方法。尽管在构造它们的过程中引入了随机 性的概念，但是它们仍然属于分形的范畴，只不过生成的集合的各个元素之间是统 计自相似性的，也既是说把某个局部经过放大后，它与整体有相同的统计分布。2.2 Koch 曲线1904 年，瑞典数学家柯赫构造了 “Koch 曲线”几何图形。Koch 曲线大于一维， 具有无限的长度，但是又小于二维，并且生成的图形的面积为零。它和三分康托集 一样，是一个典型的分形。根据分形的次数不同，生成的 Koch 曲线也有很多种，比 如三次 Koch 曲线，四次 Koch 曲线等。下面以三次 Koch 曲线为例，介绍 Koch 曲线 的构造方法，其它的可依此类推。 三次 Koch 曲线的构造过程主要分为三大步骤：第一步，给定一个初始图形―― 一条线段；第二步，将这条线段中间的 1/3 处向外折起；第三步，按照第二步的方 法不断的把各段线段中间的 1/3 处向外折起。这样无限的进行下去，最终即可构造 出 Koch 曲线。其图例构造过程如下图 3-3 所示(迭代了 6 次的图形)。- 10 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建图 2-3 Koch 曲线的生成过程无可否认，Koch 曲线的生成过程是简单的，但其曲线又是复杂的。首先，它有 很多个折点，而且这些折点是不可微的，当然也就没有切线了。其次，Koch 曲线在 许多方面的性质与三分康托集列出的那些性质类似，它由四个与总体相似的“四分 之一”部分组成，但是比例系数是 1/3。它在任何尺度下的不规则性反映了它的精 细结构，但是这样错综复杂的构造却出自于一个基本的简单结构。现在把图 2-3 的 初始图形改换成三角形，再按照上述的方法进行折叠，那么会得到另外一个分形， 也既是 Koch 雪花，它的构造过程将在以后的章节中介绍。 三分康托集有随机和非随机两种形式，Koch 曲线也不例外，Koch 也能够构造出 随机的 Koch 曲线，其方法和过程同三分康托集类似，这里不在重复述说。2.3 Julia 集Julia 集是由法国数学家 Gaston Julia 和 Pierre Faton 在发展了复变函数迭 代的基础理论后获得的。Julia 集也是一个典型的分形，只是在表达上相当复杂， 难以用古典的数学方法描述。 Julia 集由一个复变函数 ?( z )= z 2 + c ( c 为常数)迭代生成。尽管这个复变函 数看起来很简单，然而它却能够生成很复杂的分形图形。如图 2-4 所示- 11 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建图 2-4 Julia 集由于 c 可以是任意值，所以当 c 取不同的值时，生成的 Julia 集的图形也不相同。2.4 本章小结本章简要的介绍了几种典型的分形事例，比较直观的说明了什么是分形，以及 如何来构造分形。通过这些分形实例，我们可以看出构造分形是简单的，但是生成 的集合是复杂的(如三分康托集)，图形是绚丽多彩的(Julia 集)。第三章 分形的描述图像是人类描述自然界中客观事物直观的，有效的方法。实现客观事物的计算 机模拟是许多科学家一直致力的研究课题。他们孜孜不倦的富有激情的研究如何才 能有效的表示真实的事物。分形的描述也不例外，它的出现同样引起了科学界的极 大兴趣。 就其计算机的实现来说，有很多不同的算法，但是具体那种算法更有效、更实 用则要针对不同的情况。分形的描述常用的方法有 L 系统和 IFS 系统两种。从它们 所绘制出的分形来说，L 系统要比 IFS 系统简单。L 系统只是简单的字符串的迭代， 而 IFS 系统在这方面要复杂的多，比如 Julia 集等。3.1 L 系统- 12 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建林氏系统(通常称 L 系统)是林德梅叶 1968 年为模拟生物形态而设计的， 后来史 密斯于 1984 年 、普鲁辛凯维奇于 1986 年，分别将它应用于计算机图形学，引起生 物学界和计算机界人士极大兴趣，一时发表了许多论文和专著。 3.1.1 L 系统生成图形的基本原理 L 系统实际上是字符串重写系统，L 系统的工作原理非常简单。如果把一个字符 看作是一种操作，而且每种不同的字符解释成不同的操作。基于这种思想，那么就 可以利用字符串生成各种不同的分形图形，于是只要能生成字符串，也就等于生成 了图形。 L 系统中生成图形的字符串可以是任意的可识别的字符组成，比如， ， ， “F”“-” “+”在程序设计中“F”表示从当前位置向前一个单位长度，同时画线，“-”表示 从当前方向顺时针旋转一个给定的角度， “+”表示从当前方向逆时针旋转一个给定 的角度。在生成字符串的过程中，先从一个称为公理的起始字符开始，再将该公理 字符替换成规则中的子字符串，这是第一次迭代。然后，再把子字符串作为母串， 将母串中的字符用规则中的子串替代，依此类推，就可以完成 L 系统的迭代，其字 符串的长度由迭代次数控制。例如： 公理：F 规则：F-F++F-F 第一次迭代：F-F++F-F 第二次迭代：F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F …………………………………………………………… …………………………………………………………… …………………………………………………………… 这样不断地迭代下去，则会生成一个很长的字符串。规则作用一次，称作一级，用 n 代换级数。一般来说选择的级数不宜太高，通常选 2-8 级，最多 15 级。 如果再把生成的字符串中的每一个字符解释成为每一步操作，并把它画出来， 那么最终便会生成让人意想不到的分形图形。现在就以上面的例子为例，既然字符 串已经生成，下面就是如何解释它们了。在笛卡儿坐标系上，假如规定起始点的坐 标是(0,1),起始角度为 0，F 所走的步长为单位 1，-和+旋转的角度为 90 ° 。那么在 第一次迭代生成的字符串 F-F++F-F 可绘制成图 3-0。其步骤：当遇到第一个“F” 时，由事先规定的规则从点(0，1)到点(1，1)画一条线段 1，接着是字符“-” ，它 使当前的角度方向顺时针旋转 90 ，此时的方向是沿 y 轴的负向，再遇到第二个字 符“F”时，就沿着新的角度方向再画一条线段 2，两个字符“+”使得画线的方向°- 13 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建变为沿 y 轴的正向，因为 y 轴负向逆时针旋转两个 90 ° ，遇到第三个“F”后画线 3， “-”又使画线的方向朝向 x 轴的正向，最后一个“F”画成线段 4。图 3-0 简单事例虽然图 3-0 看起来非常简单，但是如果是一个更为复杂的字符串，也就是说经 过反复迭代后生成的字符串，那么画出来的图形就会很复杂。尽管如此，生成的图 形仍然具有分形的特征。当然，仅仅给出上述几个字母的龟形说明还不够，假如模 拟树木的分叉，就需引进两个新的符号，用龟形解释如下： “［”：将龟形的当前状态压入堆栈，存入堆栈的信息包括龟形的位置和方向， 可能还有其它属性，如所画线段的颜色及宽度。 “］”：从堆栈中弹出一个状态作为当前状态，不画线，尽管龟形的状态通常 是改变的。 事实上，L 系统是一种形式语言。L 系统可分为三类：0L 系统，1L 系统和 2L 系 统。0L 系统是上下文无关的；1L 系统仅考虑单边的语法关系，即左边相关或者右边 相关；2L 系统既考虑左边的语法关系，又考虑右边的语法关系，它是对上下文要求 最为严格的方法。下面仅就最简单的 L 系统类型加以说明，即是 0L 系统。 令 V 表示一个字符表，V * 表示 V 上所有字符串的集合，V + 表示 V 上所有非空字 符串的集合。一个字符串 0L 系统是一个有序的三元素集合 G=&V， ω ， P &，其中 V 表示系统中能识别的所有字符， ω ∈ V + 是一个非空字符串，称作公理， P ? VХV * 是产生式的有限集合。产生式( a ， x ) ∈ P 写作 a → x ，字符 a 和字符串 x 分别称 为产生式的前驱和后继。假设对于任何字符 a ∈ x ，至少有一个字符串 x ∈ V * ，使 得 a → x 。若对给定的前驱 a ∈ V 无显示说明的产生式，则规定自反规则 a → a 属于 产生式集合 P 。对于每个 a ∈ V，当且仅当恰有一个 x ∈ V * 使得 a → x ，称 0L 系统- 14 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建是确定的，记作 DOL 系统。 尽管 0L 系统在所有 L 系统类型中是最简单的， 但是它却能够生成许多典型的分 形事例。下面结合由 Koch 曲线构成的 Koch 雪花作为例子，详细地介绍 0L 系统如何 生成分形图形。 上面已经阐明，L 系统的公理和产生式都是由字符串描述的，并且要使字符串 和图形联系起来，就要把每个字符赋予特定的含义。现在采用龟形加以说明。将龟 形形态定义为三元素集合( x ， y ， α )，其中( x ， y )是用笛卡儿坐标表示的龟图 位置， α 表示龟图的方向，给定步长 d 和角度增量 δ 。 F( d ) ： 向 前 移 一 步 ， 步 长 为 d ， 龟 形 形 态 变 为 ( x' ， y' ， α ) ， 其 中x' = x + d cos α ， y ' = y + d sin α ，在点( x ， y )和( x ' ， y ' )之间画一直线段。+( δ )：向左旋转 δ ，龟形的下一个状态为( x ， y ， α + δ )，角的正向为逆时 针方向。 -( δ )：向右旋转 δ ，龟形的下一个状态为( x ， y ， α - δ )，角的负向为顺时 针方向。 下面就以典型的 Koch 曲线为例，说明用龟形画分形图形的过程 [ 7 ] ：δ ：60 °初始图 生成元 起始有两个图形，一个是初始图形，另一个是生成元。生成元是一个非闭合的 有向折线。因此，构造的每个阶段都从折线开始，用生成元替代每个直的线段，压 缩生成元，并把它们放在与原来直线段有相同端点的位置上，依此类推。 Koch 曲线的初始图形是一个边长为 1 的等边三角形(如图 3-1(a))， 生成元是一 条有四个边长为 1/3 的线段组成的非闭合的有向折线(如图 3-1(b))，将初始图形的 每一条线段(即初始图形的每条边)都由生成元替代，得到图形 3-1(c)，它是第一次 迭代的结果。再将生成元的每条线段缩小为原来的 1/3 长，依次替代图 3-1(c)中的 每一条线段，则生成图形如 3-1(d)所示，这样周而复始的循环迭代，即可获得 Koch 雪花。ω ：F(1)--F(1)--F(1) P ：F( d )→F( d /3)+F( d /3)--F( d /3)+F( d /3)- 15 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建(a)初始图形(b)生成元(c)第一次迭代 图 3-1 Koch 曲线的构造(d)第二次迭代若公理(初始图形)为一个正方形，生成元也很简单，向前走两步，右转走一步， 回转，走一步，右转，再走一步。图形结构见图 3-2，规则如下：δ ：90 °ω ：F-F-F-F-F P ：F=FF-F-F-F- 16 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建图 3-2 四方内生树，右图为代入 8 次后的图形图 3.3 是用 L 系统生成的希尔伯特曲线。生成该曲线的规则有两条。δ ：90 °ω ：Y 初始字符串为任意字母，可以看成是一点 P ：X=-YF+XFX+FY第一个生成规则Y=+XF-YFY-FX+ 第二个生成规则(a) n=1(b) n=2- 17 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建(c) n=3 图 3-3 希尔伯特曲线(d) n=4用 L 系统生成谢尔品斯基四方垫，图形如图 3-4 所示，规则如下：δ ：90 °ω ：F+F+F+F P ：F=FF+F+F+F+FF(a)n=1(b)n=2(c)n=3 图 3-4 谢尔品斯基四方垫(d)n=4- 18 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建3.1.2 随机的 L 系统 自然界中的物质形态不是固定不变的，而是随机的，尽管它们有一定的规律可 寻。世界上没有完全按相同方式生长的两棵植物。即使是同一种植物，其形态也存 在很大差别，如茎的高矮、开花的位置、种子的形状，等等。尤其是由环境的影响 带来的形态变异。例如，作物由于肥料充足而粒大穗多。基于此，从模拟植物的效 果来说，用上述方法得到的图形显然有些呆板，不那么形象了。如果在保留某种植 物主要特征的情况下，为了产生细节上的不同变化，以求生成的植物图形更加生动 逼真，那么可以引入随机性。它的好处就是模拟出来的植物更加接近真实的事物形 态。随机的 L 系统是有序的四元素集 [ 8 ] ，其表达式为： G=&V， ω ， P ， π & 其中 V，ω 的意义和三元式相同，然而这里的 P 却是随机的生成规则集，π 为函数， 且有∑ π ( P ) =1。i =1 iπ图 3-5 随机 L 系统生成的植物图形图 3-5 是采用随机 L 系统的数学模型生成的某一植物的图形。 它是由如下规则产 生的， V={F，+，-，[，]} ω =Fπ ( P1 )- 19 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建P1 : F→F [ + F ] F [ - F ] F π ( P2 ) P2 : F→F [ + F ] F [ - F [ + F ] ] π ( P3 ) P3 : F→F F [ - F + F + F ] + [ + F C F C F ]这里取 π (P i )=1/3，则 π ( P )+ π ( P2 )+ π ( P3 )=1 1 随机 L 系统模拟自然界植物的形态随机性，对同一符号，存在几个产生规则， 选择哪一个要根据其概率分布。这种概率分布可以根据先验概率来确定。随机 L 系 统考虑了在植物的形态生成过程中随机因素的影响，因而丰富了 L 系统的表现力。 3.1.3 L 系统的算法 L 系统侧重于植物拓扑结构的表达，它试图用抽象出来的规则描述植物的形态 及生长规律，该系统虽然具有定义简洁、结构化程度高、易于实现等优点。通常计 算机生成分形图形的算法大多是所谓的“迭代” ，在程序中的实现形式是“递归”调 用。众所周知，递归程序与非递归程序的区别在于：递归程序很难用通常的方法来 控制它的流程。虽然这一点是一个问题，但是这也是它的优点之所在，因为它的算 法非常简单。正是基于递归算法的这一优点，在编制 L 系统程序的时候就是采用这 种算法。 通过前面的理论分析，L 系统算法的关键在于字符串的生成。下面对这个过程 进行具体的分析(JAVA 语言)。 L 系统中用到的全局变量算法中用到的全局变量- 20 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建startX：整型变量，起始点的X坐标位置 startY：整型变量，起始点的Y坐标位置 initDirection：整型变量，开始绘画时的初始方向角 direction：双精度变量，是角度变化的中间变量，记录当前角度值 lengthF：双精度变量，每步步长(即画一条线段的长度) rotation：双精度变量，作图中的旋转角度 startDepth：整型变量，画图迭代次数 ruleNumber：整型变量，规则数 sStart：字符串变量，公理(即生成元) sRule[][]：字符串变量，规则数组 doublePoint：记录线段的两点,由类定义L 系统的核心程序段算法：HuiHua(Graphics g, String instruction, int depth) 参数：① g 图形属性 ② instruction 字符串 ③ depth 迭代次数 局部中间变量：i，j 为整型；c 为字符串型 if (depth==0) //深度为0，表示可以画了 depth -= 1;//每递归一次迭代次数减一 Vector aPoint = new Vector();//用向量记录“[”时的点的坐标 Vector aDirection = new Vector();//用向量记录出现“[”时的 //方向角 for (i=0;i&instruction.length();i++) { c = instruction.charAt(i); // 开始递归 for(j=0;j&ruleNj++) { if (c==sRule[j][0].charAt(0)) { HuiHua(g, sRule[j][1], depth); //若找到公理符合规则，就调用规则 //进行递归 } //获取公理或者规则中的字符- 21 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建} if (c=='F') { // 如果深度达到所设定的深度时即画出线段 if (depth==0||j==ruleNumber) { double rad=2*Math.PI*direction/360;// 角度转换 double p=lengthF * Math.cos(rad); double q=lengthF * Math.sin(rad); b = new doublePoint(a.x+p, a.y+q); g.drawLine((int)(a.x),(int)(400-a.y),(int)(b.x) ,(int)(400-b.y) ); a = // 前一线段的终点为后一线段的起始点 } } else if (c=='+') direction += //逆时针转角度 else if (c=='-') direction -= //顺时针转角度 else if (c=='[') { //入栈 aPoint.addElement(a); sDirection = String.valueOf(direction); aDirection.addElement(sDirection); } else if (c==']') { //出栈 a=(doublePoint)(aPoint.elementAt(aPoint.size()-1)); sDirection=(String)(aDirection.elementAt(aDirection.size()-1)); direction=Double.valueOf(sDirection).doubleValue(); aPoint.removeElementAt(aPoint.size()-1); aDirection.removeElementAt(aDirection.size()-1); } } }记录坐标点的类类函数 doublePoint(double x1,double y1) 参数：x1 点的 x 坐标- 22 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建y1 点的 y 坐标 局部变量：x，y 为双精度型 doublePoint(double x1,double y1) {x=x1;y=y1;}图 3.6 就是不同的迭代次数生成的图形(程序中设定 d 为 3.0，初始的方向角 90 ° ， 给定的旋转角-30 ° )。(a)迭代 5 次(b)迭代 6 次(c)迭代 7 次 图 3-6 开花的草(d)迭代 8 次程序以公理 G 开始， 在第二层的 for 循环中满足规则一的条件， 进入递归循环， 由于递归的深度(递归深度也叫递归次数)不为零，那么继续以字符“G”递归，直到 depth 为零的时候返回，程序返回后，又以 G→GFX[+++++GFG][-----GFG]规则中的 第二个字符“F”继续递归，它同样递归到深度为零时为止。依此类推，当迭代次数- 23 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建是 5 时，最终的图形就如图 3-6(a)所示。 3.1.4 L 系统的实验数据 下面是 L 系统程序中的事例数据，以及一些验证的数据，如下表 1 所示。表 1 中包含有事例名称、角度增量、公理和生成规则。 表 1：L 系统实验数据一览表事例名称 角度增量 公理 ω G F X=F-XF F[+F[+F][-F]F][-F[+F][-F]F]F[+F][-F]F S=[+++G][---H]FFS 有花蕾的 植物 -18 K G=+G[-FH]F H=-H[+FG]F K=FSF 枝 蒲公英 -25.7341 30 F Y F=F[+F]F[-F]F X=X[-FFF][+FFF]FX Y=YFX[+Y][-Y] 灌木丛 -30 F F=FF-[-F+F+F]+[+F-F-F] S=[+++H][---G]TS G=+H[-G]L 棕榈 -18 SLFFF H=-G[+H]L T=TL L=[-FFF][+FFF]F 开花的草 -30 G G=[+FGF][-FGF]XG X=XFX 斜枝 -1.2 F F=F[+++++++++++++++++++++++++F]-F [-------------------------F]F 杨柳 树 -22.5 30 F X F=FF+[+F-F-F]-[-F+F+F] X=F[+X]F[-X]+X F=FF 对称的树 30 X X=F[+X][-X]FX F=FF 生成规则 P G=GFX[+++++GFG][-----GFG] 斜草 树伞 -3 30- 24 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建谢尔品斯基 四方垫 Koch 曲线 四方内生树 希尔伯特曲 线90F+F+F+FF=FF+F+F+F+FF60 90 90F―F--F F-F-F-F-F YF=F+F--F+F F=FF-F-F-F X=-YF+XFX+FYY=+XF-YFY-FX+3.2 IFS 系统迭代函数系统(IFS， 简称迭代函数系统)方法是美国佐治亚理工学院的巴恩斯利 (Michael F.Barnsly)等人首先应用一组收缩仿射变换生成分形图像，即通过对原始 图形(生成元)的收缩、旋转、平移等变换形成的极限图形而具有自相似的分形结构， 并将该仿射变换集称之为 IFS。它与复平面上 ?( z )= z 2 + c ( z ， c 为复数)迭代产生 的分形存在着内在的联系，只是 ?( z )属于非线形变换，而 IFS 属于线形变换。IFS 系统的理论与方法是分形自然景观模拟及分形图像压缩的理论基础，其基本思想是 认为物体的全局和局部在仿射变换的意义下具有自相似结构，这就形成了著名的拼 接定理。IFS 方法的魅力在于它是分形迭代生成的“反问题”，根据拼接定理 (collage theorem)，对于一个给定的图形(比如一幅图片)，求得几个生成规则，就 可以大幅度压缩信息。 3.2.1 IFS 的数学基础 函数迭代系统是一个比较复杂的生成分形图形的方法，它需要依附很多的数学 知识。下面就 IFS 系统所牵涉到的定义、定理和引理进行简单的论述。 定义 3.1 设 ( X , d ) 为一完备度量空间， (H ( X )) 为 X 的非空紧子集组成的集 令 合。 ?A, B ∈ (H ( X )) ， A 到 B 的距离 d 定义如下：d ( A, B ) = max{d ( x, B ); x ∈ A}其中 d ( x, B ) = min{d ( x, y ); y ∈ B}。 用 ∨ 表示两数中取其中较大的一个，则 A, B 之间的 Hausdorff 距离为：(3.0)h( A, B ) = d ( A, B ) ∨ d ( B, A)(3.1)- 25 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建可以证明 ( H ( X ), h ( d )) 同样是一度量空间。 定义 3.2 变换 ω : R → R2 2?x ? ?a b ? ? x ? ?c ? ω? ? = ? ? ? y? + ?g? ? y? ?e f ? ? ? ? ?a , b, c, e, f , g ∈ R(3.2)称为二维仿射变换。公式(3.2)是 IFS 系统中生成分形点的算法基础，在分形图形的 生成过程中起到重要的作用。 定义 3.3 设 ( X , d ) 为一度量空间，变换 f : X → X 称为压缩映射，如果存在 着实数 s 满足条件 0 ≤ s & 1 ，使得 ?x, y ∈ X ，有d ( f ( x ), f ( y )) ≤ sd ( x, y ) s 称为 f 的压缩因子。(3.3)定理 3.1 设 ω : X → X 为度量空间 ( X , d ) 上的压缩映射， 压缩因子为 s ， 则映 射W : H ( X ) → H ( X )W ( B ) = {ω ( X ); X ∈ B}是 ( H ( X ), h ( d )) 上的压缩因子为 s 的压缩映射。?B ∈ H ( X )(3.4)引理 3.1 压缩映射 ω : X → X 是连续映射。 引理 3.2 压缩映射 ω : X → X 把 X 的一个非空紧集映射成 X 的非空紧集， 即 映射 H ( X ) 到自身。 定理 3.2 (压缩映射定理)设 ω : X → X 是完备度量空间 ( X , d ) 上的压缩映射， 则 ω 具 有 惟 一 的 不 动 点 xω ∈ X ， 并 且 对 于 任 意 点 x ∈ X ， 序 列{ωn( x ); n = 0,1,2 ? ? ? ? ?}收敛于 xω ，即对于每个 x ∈ X ，有 lim ω n ( x ) = xω 。这里n →∞- 26 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建ω n (x ) 表示映射 ω 的 n 次复合，即 ω n ( x ) = ω (ω (? ? ? ? ?ω ( x ))) 。定义 3.4 一个双曲(Hyperbolic)迭代函数系统(IFS)是由一个完备度量空间( X , d ) 及 其 上 的 一 组 压 缩 映 射 ωi : X → X 组 成 ， ωi 的 压 缩 因 子 为 si , i = 1,2,? ? ? ? N 。迭代函数系统记为 {X ;ωi , i = 1,2,? ? ? ? N }，迭代函数系统的压缩因子为 s = max{si , i = 1,2,? ? ? ? N } 。 定义 3.5 对给定的迭代函数系统 {X ;ωi , i = 1,2,? ? ? ? N }，压缩映射集 ωn 及其中 的系数统称为该迭代函数系统的 IFS 码。 定义 3.6 给定一个迭代函数系统 {X ;ωi , i = 1,2,? ? ? ? N }，称集合 E 是它的一个 不变集或者吸引子，如果 E =Uω (E) 。i i =1N这里双曲的概念是指映射是压缩的，一般地，我们用压缩仿射变换来表示这些 映射。在这种情况下 IFS 的形式如下：? ? ? x ? ?ai bi ? ? x ? ?ci ? ? X ;ωi ? ? = ? ? ? y ? + ? g ?; i = 1,2,? ? ? ? N ? ? y ? ?ei f i ? ? ? ? i ? ? ?IFS 系统既可以退化到一维情况，仅在实轴上进行变换，也可以加变量而扩展 到高维空间中。m 定理 3.3 设 R ;ωi , i = 1,2,? ? ? ? N 是 m 维空间 R 上的双曲迭代函数系统， A m{}是它的吸引子。假定对于每个 i ，ωi 的压缩因子为 si 。如果双曲迭代函数系统是完 全不相连的，则吸引子 A 具有分形维数 D ( A) = D ，其中 D 是下面方程的惟一解：∑si =1ND i= 1 ，D ∈ [0, m](3.5)如果迭代函数是有界的，则 D ( A) = D ，其中 D 是下面方程的解：- 27 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建∑si =1ND i= 1 ， D ∈ [0, m](3.6)3.2.2 IFS 系统生成图形的基本原理 二维空间 R 2 上的线形变换 ω 具有如下形式 [ 10 ] ：?x ? ?a b ? ? x ? ?c ? ω? ? = ? + ? ? ? ? ? ?e f ? ? y ? ? y? ?g?对于 x ， y ∈ R2a , b, c, e, f , g ∈ R， 若 存 在 压 缩 因 子 s 满 足 0& s &1 ， 使 得 下 式ω x ? ω y ≤ s ? x ? y 成立，则称 ω 为收缩仿射变换。该变换又可表示为 ?Tx ? ?x ? ?r cos θ s ? sin ? ? ? x ? ω? ? = ? + ? ? ? ? ? ? y? ?r sin θ s ? cos ? ? ? y ? ?T y ?(3.7)() ()ω 迭代函数系统由一组收缩仿射变换 { 1 , ω2 , ω3 ? ? ? ? ? ??, ωn }组成，二维 IFS 可以表示为?ai bi ? ? x ? ? ci ? ?x ? ωi? ? = ? ? ? y? + ?g ? ? y? ?ei f i ? ? ? ? i?生成图形时，调用各变换的概率： Pi =i = 1,2,? ? ? ? ??, N(3.8)ai f i ? bi ei∑ak =1nkf k ? bk ekPi & 0∑P = 1i =1 in(3.9)通过式(3.8)可以生成许多构成分形图形的点，式(3.9)主要是由规则的概率控 制生成图形的形态。 3.2.2 IFS 吸引子 定理(吸引子定理)3.4 设 {X ωi , i = 1,2,? ? ??, N }为一双曲 IFS，压缩因子为 s ，- 28 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建则映射 W : H ( X ) → H ( X ) ：W ( B ) = U ωi ( B ) = ω1 ( B ) U ω2 ( B ) U ? ? ? ? Uω N ( B ) ，B ∈ H ( X )i =1N(3.10)是 ( H ( X ), h ( d )) 上的压缩因子为 s 的压缩映射，即h(W ( B ), W (C )) ≤ s ? h( B, C ) ，?B, C ∈ H ( X )且 W 存在惟一不动点 A ∈ H ( X ) ，即：(3.11)A = W ( A) = U ωi ( A)i =1N(3.12)并且 A 可以由下面的式子给出：A = lim W n ( B ) ， B ∈ H ( X ) ?n→∞(3.13)A 称为该 IFS 的吸引子。式(3.12)表明： 对吸引子中的任意一点， 应用映射 ωi 所得的点仍在此吸引子中。 生成 IFS 吸引子的算法也主要是以此为依据的。IFS 的基本思想并不复杂，它认定 几何对象的全貌与局部，在仿射变换的意义下，具有自相似结构。这样一来，集合 对象的整体被定义之后，迭代若干仿射变换，将整体形态变换到局部，并且这一过 程可以迭代地进行下去，直至得到满意的造型。在实现中具体技巧相当重要，例如 仿射变换的选取，往往由用户通过交互方式在计算机上逐个调整来实现。当用户注 重几何对象的总体时，使用 IFS 是相当出色的。 对于 IFS 吸引子的生成方法， 利用压缩映射定理和吸引子定理可以建立绘制 IFS 吸引子的两种算法：①确定性算法，②随机迭代法。实际上，只要把注意力限制在ωi (i = 1,2,? ? ??, N ) 都是式(3.10)的仿射变换的双曲 IFS {R 2 , ωn , n = 1,2,? ? ? ? N }就足够了。因为平面上的许多分形都可以表示成式 3.8 的形式。下面详细地讲解确定性 算法和随机迭代法。 ①确定法 定理 3.4 已经表述了 IFS 吸引子的概念，为了叙述的方便，在这里我们再换另 一种方法进行描述。设 {X ωi , i = 1,2,? ? ??, N }是一个双曲的迭代函数系统。取 X 的- 29 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建一个非空紧集 A ，由An +1 = U ωi ( An ) ，n = 1,2 ? ? ? ?i =1 nN(3.14)递 归 构 造 一 个 序 列 { An , n = 0,1,2,? ? ??} ， 其 中 An = W ( A0 ) 。 计 算 序 列{ An , n = 0,1,2,? ? ??} 的极限集 E ，则 E 就是迭代函数系统 {X ; ω1 , ω2 , ω3 ? ? ? ? ? ??, ω N }的吸引子。 现在以 Koch 曲线为例，用确定性算法实现 Koch 曲线的主要步骤： (1)任意确定一个初始集 B0 ∈ P ( X ) ，并将这个点集中的各个点放置到屏幕上 面； (2) 根 据 Bn +1 = W ( Bn ) =Uω (B )i n i =1N， n = 0,1,2 ? ? ? ， 直 接 计 算 集 序 列{Bn= W n ( B0 )}。压缩映射定理保证在 Hausdorff 度量下， {Bn }收敛到双曲 IFS 的吸引子 A 。在 n = 1,2 ? ? ? ? 的每一步，都将 Bn 的点集中的各个点放置到屏幕上面。 Koch 曲线所用的 IFS 的映射如下：? x ? ? 1 / 3 0 ?? x ? ? x ? ? 1 / 6 ? 3 / 6 ?? x ? ? 1 / 3 ? ?? ? + ? ω1 ? ? = ? ? y ? ? 1 / 3 0 ?? y ? ， ω 2 ? y ? = ? ?? ? ? ? ? ? ?? y ? ? 0 ? ? ? ? ?? ? ? ? ? ? 3 / 6 1/ 6 ?? ? ?确定性算法原理简单明了，易于掌握，但是由于这种算法不考虑 ωi 的区别，在 迭代中使它们处于平等的地位，这就会造成系统不必要的浪费，所以执行起来比较 费时，而且在执行过程中需要存储每一步的生成结果，这样会占用大量的内存空间， 造成系统资源浪费。为此有一种改进的形式，即是下面将要介绍的随机迭代法。 ②随机迭代法 这是一个随机的选取 IFS 中仿射变换的方法。首先需要对每一个仿射变换 ωi 都 附 上 一 个 概 率 Pi (i = 1,2,? ? ??, N ) ， 则 IFS 变 成 了 含 概 率 的 IFS ， 形 成 为{X ;ωi , i = 1,2,? ? ? ? N }。带有概率的 IFS 是由双曲 IFS {X , ωn , n = 1,2,? ? ??, N }和数系- 30 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建{P1 , P2 ,? ? ? ? ?, PN } 组 成 的 。 其 中 概 率 Pi 对 应 变 换 ωi 。 概 率 的 选 择 必 须 满 足Pi & 0, ∑ Pi = 1 ，具体的 Pi 值可以通过公式(3.9)计算得到。i =1 N注意，有可能对某个 i ，式(3.9)中 a i f i ? bi ei = 0 。对此，实际操作时可以把 相应的 Pi 设置为一个较小的正数，比如 0.00001，我们称这种带概率的 IFS 为随机 迭代函数系统。 用随机迭代算法绘制分形图形的基本思想是使 ωi 的作用次数与相应的 Pi 成正 比 ， 这 样 保 证 了 压 缩 快 速 并 且 同 步 的 进 行 。 任 取 x0 ∈ R ， 根 据 概 率 分 布2{P1 , P2 ,? ? ? ? ?, PN } ， 从 {ωi , i = 1,2,? ? ??, N } 中 独 立 地 随 机 地 选 取 一 个 ω j∞ ∞，令x1 = ω j ( x0 ),? ? ? ? ，如此下去，就可以得到序列 {x n }n =1 ，将 {x n }n =1 绘出即为分形图形。 由于 Koch 的带有概率 IFS 的 Pi =1/4 (i = 1,2,3,4) ，所以其随机迭代算法的效果 与确定性算法的效果相同。 3.2.3 IFS 吸引子在迭代函数系统中的作用 定理 3.5 对于给定的压缩型 IFS，其吸引子与初始点无关而且惟一存在。 对于由压缩映射构成的 IFS，根据上面的定理，它存在惟一的吸引子。仿射变 换是由一组方程组成，每个方程都有一组不动点，通常把不动点称为吸引子，把一 组仿射映射 ω = { i ,1 ≤ i ≤ N }中所有不动点的集合，称为仿射映射 ω 的吸引子集。 ω 求仿射映射 ωi 的吸引子，相当于求 ωi 对应一组方程的根。 在执行函数迭代过程中， 迭代点必然向吸引子靠拢。 如果 IFS 只有一个映射 ω ， 则所有迭代点将落在 ω 所对应的吸引子的领域中。如果有两个或者两个以上的吸引 子，则迭代点将落在由吸引子所控制的区域中。这时各个吸引子所起作用的强弱，- 31 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建决定于各映射的压缩比 si 的大小及执行该吸引子所对应的映射 ωi 次数的多少， 即概 率 Pi 的大小。当各映射压缩因子 si 一旦确定，则吸引子所起作用的强弱只能由执行 映射 ωi 的次数来调节了。由 IFS 的定义知道，每个映射有一个伴随概率 Pi ， Pi 的大 小决定了在整个迭代过程中映射 ωi 实施的次数的多少。显然， Pi 大小的选择可以调 节各吸引子所起作用的强弱，但不影响分形图形的形状。 相应的概率 Pi 控制该仿射变换在随机迭代中被选中的机率，即落入图像各部分 中点的数目。一般 {Pi , i = 1,2,? ? ? ? ?N }的取值与仿射变换子图的面积成正比，即子图 面积越大，落入该子图的点数就会越多，此子图所对应的仿射变换被选中的机率就 会越大，也就是此子图对应的概率越大。 由仿射变换的几何特性可以知道，子图变换后，它的面积为变换前的 af ? bd 倍。故可以将仿射变换子图的面积看成 a n f n ? bn d n ， a n , f n , bn , d n 是其仿射变换 系数。因各子图对应的概率之和为 1，所以计算概率的公式如(3.9)所示。 这种取值方法考虑的是均匀绘制图形，也是目前所采用的主要方法。如何最好 的选择 Pi 是困难的，至今也没有完全解决。只是因为 IFS 的吸引子与给定集之间存 在着 Hausdorff 距离， Pi 的选择既要使迭代尽快地逼近吸引子，又要使公式(3.1) 中的 Hausdorff 距离 h ( A, B ) 尽可能的小。一般地，对于均匀分布的情况，即落入 吸引子各部分的点数与区域面积的大小呈线性关系，同时 IFS 是非重叠的，则可以 用公式(3.9)对 IFS 中的第 i 个压缩映射 ωi 定义 Pi 。 对于有些仿射变换参与迭代， 因 此要进行一些补偿，对此，一般给相应的 Pi 赋一个小一点的值，比如 δ = 0.0001 ， 那么公式(3.9)可以写成：- 32 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建Pi =max(δ , ai f i ? bi d i )∑ max(δ , | ai =1N(3.15)if i ? bi d i |)当给定集经过各个 ωi 变换后有较大重叠的时候，还要考虑到重叠区域补偿问题，要 最终使 Pi 归一化，使∑ P = 1 成立。i =1 iN如果有意识地改变某部分的概率，可以使图形发生改变，得到另外一种效果， 即吸引子形状不变，而吸引子中点的疏密程度不发生变化。合理地渐变所有的或者 某一些参数，将会看到现实中逼真的图形效果。 随机 IFS 已经用来产生出各种形态的植物、丛林、山川和云烟等图形。而确定 这些物体图形的随机 IFS 仅有很少的几个仿射变换参数。 定义 3.7 一个随机 IFS 是由一个完备的度量空间 ( X , d ) ,一个有限的压缩映射 集 合{fi : X→ X , i = 1,? ? ? ? ??, N } 和一个伴随概率集合{pi: pi & 0, i = 1,? ? ? ? ??, N , ∑ pi = 1}构成，记为 {X ; pi : i = 1,? ? ? ? ? ? ? N } 。随机IFS 的压缩因子 s = max {si : i = 1,? ? ? ? ? ? ?, N }，其中 si (0 ≤ si & 1) 为对应映射 f i 的 压缩系数。 si 是指满足式 d ( f i ( x1 ), f i ( x2 ) ) ≤ si d ( x1 , x2 ), ?x1 , x 2 ∈ X 的常数，把 所有随机 IFS 的集合记为随机 IFSs。 定理 3.6(拼贴定理)[11]令 ( X , d ) 为一完备的度量空间，给定图像 T， ε &0，选 一 个 压 缩 因 子 为 s (0 ≤ s & 1) 的 随 机 IFS {X ; pi : i = 1,? ? ? ? ? ? ? N } 使? N ? ε h ?T , U f i (T )? ≤ ε ， 其中 h (d ) 是子集之间的 Hausdorff 度量， h (T , A) ≤ 则 ， 1? s ? i =1 ?即 h (T , A) ≤ 吸引子。? N ? 1 h ?T , U f i (T )? ，其中 A 是随机 IFS {X ; pi : i = 1,? ? ? ? ? ? ? N } 的 1 ? s ? i =1 ?- 33 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建随机性 IFS 中，各个规则都有它的概率，概率分配不同，那么产生的分形图形 也不相同。图 3-7 是在不同的概率条件下生成的分形图形。(a)p1 =0.1 p2 =0.2 p3 =0.3 p4 =0.4(b)p1 =0.11 p2 =0.45 p3 =0.27 p4 =0.17(c)p1 =0.01 p2 =0.85 p3 =0.07 p4 =0.07图 3-7 随机 IFS 生成的分形3.2.4 迭代函数图像的快速生成方法- 34 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建定理 3.7 如果 ω1 , ω2 ,? ? ? ? ? ? ω N 是分形图像 f 的 IFS 码， ωi 是 ωi 的逆。定义 算子“?”为 (ωi ? ω j?1) (x ) = ω (ω (x ))，则 ω ? ωi j ij? ωi 是子图像 ωi ( f ) 的 IFS?1码，其中 j = 1,2,? ? ??, N 。 证明：根据压缩变换不动点定理，若 F 是一个完备度量空间，ω : F → F 是一 个压缩变换， 那么对于任意初始的 B ， 存在一个唯一的不动点 A = lim ω ( B ) ，A 是i i →∞一个固定点，因此 A =U ω ( A) = ω ( A) U ω ( A) U ? ? ? ? ? ? Uωi 1 2 i =1NN( A) = ω ( A) 。定理中的不动点 A 亦称为 IFS 的吸引子，IFS 的吸引子一般都是确定性分形。对 于分形图像 f 有f = Uω j ( f )j =1N(3.16)对公式(3.16)两端进行变换可得ωi ( f ) = U ωi (ω j ( f )) = U (ωi ? ω j )( f ) = U (ωi ? ω j ? ωi?1 )(ωi ( f ))j =1 j =1NN(3.17)定理 3.8 如果点 f i 是压缩仿射变换 ωi 的不动点，则 f i ∈ ωi ( f ) 。 由定理 3.8，对于分形图像 f 有 f i = Ai f i + Bi ，解此方程，即可求出不动点f i = ( I ? Ai ) ?1 Bi ， I 是单位矩阵。当选用 f i 作为迭代函数系统的初始点时，就是无逃逸行为的生成过程。 根据定理 3.7，可以将图像分解为 N 个子图像，由算法并行生成，达到快速生 成的目的。 已知 ωi ? ω j ? ωi 是子图像 ωi ( f ) 的 IFS 码，将 ωi ，ω j 和 ωi 以向量形式代 入 ωi ? ω j ? ωi 后，即可通过图像 f 的 IFS 码得到子图像 ωi ( f ) 的变换矩阵，具 体转换公式为：?1 ?1 ?1- 35 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建τ ij ( x ) = ( ωi ? ω j ? ωi )( x ) = Ai A j Ai?1 x + ( Bi + Ai B j ? Ai A j Ai?1 Bi ) j = 1,2,? ? ??, N ，当 j = i 时，有 τ ii = ωi ，转换计算可以省略。对于 τ ij ( j = 1,2,? ? ??, N ) 应用无逃逸行为算法能单独生成各 ωi ( f ) 子图像，若 将各子图像并行生成后加以合成即可生成整体图像。当然，子图像还可以按照上述 过程继续分解成更小的子图像进行图像生成。并行生成算法不仅能加快生成速度， 而且能逐个生成子图像，直观地表现图像生成的拼贴过程。 无逃逸行为算法中由于迭代点存在重复的情况，生成速度还可以进一步提高。 最少点绘制的图像生成算法采用队列结构保存已绘制点的象素地址，通过迭代计算 已绘制点的临近点，最终绘制生成吸引子图像。由于该算法避免了吸引子点的重复 绘制，从而减少了图像的生成时间。若将算法并行进行，则可以到达实时生成的目 的。 实际上，无逃逸行为的随机迭代算法直接以不动点作为初始点，与一般的随机 迭代算法选择任意初始点相比，生成的图像更精确，且算法并行执行更有利于图像 的快速生成和直观的显示图像的生成过程。 3.2.5 IFS 系统主要算法 通过上面的分析，我们可以看出对于 IFS 系统生成分形图像来说随机迭代算法 是一种高效的算法。鉴于此，在程序的实现过程中，采用了随机迭代算法。现在以 该算法的核心程序来简单地介绍随机迭代算法是如何应用于分形图形的生成。 随机迭代算法是产生许多的点来构成整个的图像，这些点是循环不断地、随机 地生成。因此，在程序的编制中，我们采用线程的方法来控制点的产生速度以及控 制点什么时候产生和什么时候结束。当然，运用线程会大量消耗 CPU 的时间。值得 一提的是 CPU 的速度决定点生成的快慢。 表 2 运用线程控制点的生成class FrameCanvas extends Canvas implements Runnable { Thread huihua=//定义huihua为线程，并初始化为空 public void init() {} public void start() { if(huihua==null)?1- 36 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建{ huihua=new Thread(this);//给huihua赋值为当前对象 huihua.start();//启动线程 } } public void run() { while(huihua!=null) { 利用随机函数生成一个随机数，把该随机数和某个规则的概率值加以比 较，当满足条件时，利用这个规则产生点 } public void stop() {//使画点操作暂停 huihua.yield(); huihua= } }分析这个程序段，开始把 huihua 定义为线程，由它来控制什么时候画点，什么 时候停止。Huihua 的初始值为空(既是画点操作还没有准备好)，一旦由下面表 3 的 程序段启动后，huihua 会被赋值，其线程的参数是当前对象。接着开始进入 while 循环，如果没有表 4 的程序段终止画点操作，那么该循环会一直运行下去，也既是 说程序将不停地产生点、画点。 其中， 3 中的 start 和 buttonStart 以及表 4 中的 stop 和 buttonStop 分别 表 是程序下拉菜单中和工具栏上的按钮，而 canvas 是类 FrameCanvas 的别称， FrameCanvas 又是画布类 Canvas 的继承。由于所有的点都绘制在画布上，所以 huihua=new Thread(this)语句中的 this 实际上是以画布为对象启动线程的。 表 3 启动线程if(e.getSource()==start||e.getSource()==buttonStart) { g=canvas.getGraphics(); canvas.start();//启动 }表 4 终止线程if(e.getSource()==stop||e.getSource()==buttonStop) {- 37 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建canvas.stop();//终止 }既然线程已经启动了，下面就是具体如何生成分形点了，这部分程序段是 IFS 系统的核心。产生点的规则如表 5 所示。 表 5 核心程序段(生成点，并绘制在画布上)while(huihua!=null) { u=0; double E = Math.random();//生成随机数 for(int i=0;i&ruleNi++) { if(E &= pp[i] && E& pp[i+1])//随机数和规则概率比较 {//如果随机数在pp[i]和pp[i+1]之间，则取规则rule[x][i] u=rule[i][0]*x+rule[i][1]*y+rule[i][2];//生成点的横坐标 y=rule[i][3]*x+rule[i][4]*y+rule[i][5];//生成点的纵坐标 x=u; if(colorLock)//颜色锁定，产生伪三维图形，实现真实感效果 { g=canvas.getGraphics(); g.setColor(new Color(0,130+i*20,0)); } } } g.fillRect(width/2+(int)(scale*x)+offset,height+10-(int)(scale* y)+offset,1,1);//画点 }u 是中间变量，每次循环它都要重新赋值为零。通过一个随机函数产生一个随 机数 E，它决定该次循环会采用哪条规则。for 循环主要实现把每个规则的概率和 E 进行比较，如果满足条件，则使用符合条件的规则进行运算，同时退出 for 循环。 接下来，把生成的点的横坐标和纵坐标带入公式中画出点。由程序可以看出，画出 的点是一个填充的矩形框，这是由于显示器是由很多很小的方格构成的光栅，每个 象素点就是一个小方格，所以这个填充的矩形框也就是一个象素点。 3.2.6 IFS 系统的实验数据- 38 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建下面是 IFS 系统程序中的事例数据，以及一些验证的数据，如下表 6 所示。表 1 中包含有事例名称、生成规则和各个规则的参数。 表 6 IFS 系统实验数据一览表叶子参数表 R 1 2 3 4 a 0 0.85 0.2 -0.15 b 0 0.04 -0.26 0.28 c 0 0 0 0 山川参数表 R 1 2 3 4 a 0.5 0.5 -0.4 -0.5 b 0 0 0 0 c 0 2.0 0 2.0 e 0 0 -0.4 0 f 0.5 0.5 0.4 0.5 g 0 0 1.0 1.0 P 0.25 0.25 0.25 0.25 e 0 -0.04 0.23 0.26 f 0.16 0.85 0.22 0.24 g 0 1.6 1.6 0.44 P 0.01 0.85 0.07 0.07Sierpinski 三角参数表 R 1 2 3 a 0.5 0.5 0.5 b 0 0 0 c 1.0 50.0 50.0 竹叶参数表 R 1 2 3 4 a 0.29 0.33 0.42 0.61 b 0.4 -0.34 0 0 c -0.4 0.39 0 0 金字塔参数表 R 1 2 3 a 0.5 0.5 0.5 b 0 0 0 c 0 1.0 0.5 e 0 0 0 f 0.5 0.5 0.5 g 0 0 0.5 P 0.33 0.33 0.34 e 0 0.4 0.63 0.61 f 0.28 0.41 0.29 0.19 g 0.44 0 0.36 0.23 P 0.25 0.25 0.25 0.25 e 0 0 0 f 0.5 0.5 0.5 g 1.0 1.0 50.0 P 0.4 0.2 0.4巴恩斯利蕨参数表 R 1 a 0 b 0 c 0 e 0.16 f 0 g 0 P 0.01- 39 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建2 3 40.85 0.2 -0.150.04 -0.26 0.28-0.04 0.23 0.26 树叶 B 参数表0.85 0.22 0.240 0 01.6 1.6 0.440.85 0.07 0.07R 1 2 3 4a 0 0.12 0.12 0.1b 0 -0.82 0.82 0c 0 0.42 -0.42 0e 0.5 0.42 0.42 0.1f 0 0 0 0g 0 0.2 0.2 0.2P 0.05 0.4 0.4 0.153.3 本章小结L 系统以其高度简洁性和多级结构，为描述植物树木的生长和增殖过程的形态 和结构特征，提供了行之有效的理论与方法。但目前 L 系统也存在一定的局限性， 如 L 系统的字符串， 既不能提供植物分枝的长度， 也不能提供三维拓扑信息。 因此, L 系统在实用中还必须进一步充实和发展，才能更好地描述现实世界的三维植物树 木。 目前已有人将 L 系统与分枝几何描述相结合，以便对各种分枝情况复杂的植物 树木及形态进行模拟。 L 系统的理论与方法正不断地发展，其应用领域也在不断地 扩大，相信在 21 世纪，人们在该研究领域一定会取得令人瞩目的成果。 迭代函数系统是分形图案的生成方法之一，它的分形重构方面取得的进展引起 了图像压缩技术的革新，达到了用常规压缩方法无法达到的高压缩比。其主要的思 想在于存储生成图像的 IFS 系统而不存储生成的图像，恢复时根据 IFS 系统用专门 的硬件生成图像。作为产生分形的方法之一，迭代函数系统在自然景物模拟以及图 像压缩方面具有独到之处，是一个可行的，有价值的研究领域。第四章 三维图形的实现从生成的分形图像来看，二维图形显得很呆板，与生活中的实物相差甚多。为 了更逼真的模拟出自然界中的物体，现在讨论用一些方法进行实现。4.1 L 系统的三维化4.1.1 随机颜色算法 随机颜色在模拟三维图形中是一种非常简单、有效的方法。我们只要在绘制分- 40 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建形图形的时候改变线段的颜色，使画出来的线段的颜色不是固定不变的，而是颜色 参数在某一个范围中随机产生的。 下面是 L 系统随机颜色产生的算法(表 7)， 表 7 随机颜色生成算法变量 Count：整型，控制颜色参数的范围 if(colorLock)//将颜色参数锁定 { if(Count&75) Count=0; g=canvas.getGraphics(); g.setColor(new Color(0,180+(75-Count++)%75,0));//将颜色参数值控制//在 180∽255之间 }当程序处于颜色锁定状态时，则进入随机颜色生成算法。其中，Count 控制颜 色参数是在哪个范围之间变动。由于该 L 系统是模拟植物形态的，所以就把颜色锁 定在 180∽255 之间，即是深绿和浅绿之间。图 4-0 是用随机颜色算法和不用该算法 分别生成的分形图形的比较。(a) 一般性算法生成的图形- 41 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建(b) 随机颜色生成的图形图 4-0 不同算法生成图形的比较尽管这种方法实现很简单， 但是从图 4-0 可以看出图(a)和图(b)有很大的差别， 视觉效果比不用随机颜色算法强了许多。当然，随机颜色算法也有其缺点，那就是 它是一种伪三维的算法，看起来像是三维立体图形，实际上它仍然是二维的，只是 视觉上的一种错觉。 4.1.2 空间拓扑算法 L 系统是一种线形描述方法，它的特点是生成简洁、高效，但是 L 系统只是描 述了植物的生长过程，并不能反映植物全面的特征信息，比如树枝的粗细、长度等。 如果对 L 系统进行适当的拓展，即在绘制图形的过程中添加一些参数变量，通过这 些参数对植物的特征进行描述，最终会生成更加逼真的物体。 很显然，一般植物的生态结构都符合树状结构，在植物的逻辑树结构表示中， 主枝及旁枝是逻辑树中的节点，主枝与旁枝的连接关系是逻辑树的边。植物造型描 述离不开逻辑树结构，而逻辑树结构是建立在三维 L 系统描述的基础上，下面给出 一个简单 L 系统的逻辑定义及操作。 ω ：F P ：F=F[1F 2F]F[3F]F 其中，1F、2F、3F 表示主枝长出的三个旁枝。 把产生式 P 多次作用于 F，即可得到一个植物的简单描述。例如，把 P 两次作- 42 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建用于 F 后，产生的植物描述为： F[1F 2F]F[3F]F[1F[1F 2F]F[3F]F 2F[1F 2F]F[3F]F] F[1F 2F]F[3F]F[3F[1F 2F]F[3F]F]F[1F 2F]F[3F]F 改变产生式 P 即可得到不同形状的植物造型描述。 在此基础上，可以建立植物的拓扑结构。进一步，可以计算植物各段树枝的空 间位置，给出植物的空间结构描述，如图 4-1 所示。图 4-1 植物的三维空间结构示意图以上给出的是植物造型的简单描述，要逼真地表现植物形态，还要进行深层次 的研究。设计合理的公理 ω ，依靠上述算法，可完成逼真的三维植物模型建造。 4.1.3 三维空间描述算法 在 3.1.1 节 L 系统生成图形的基本原理中，介绍了二维龟形的生成方法，若要 绘制三维树形结构，需要将二维龟形命令扩展到三维空间上。首先给出描述龟形当 前方向的三个向量 H ， L ， U ，它们分别表示龟形的向前、向左和向上的方向， 均是单位长度，且满足方程 H Х L = U 。旋转龟形表示如下。[H ' ，L' ，U '] = [ H ，L ，U ] R ，其中 R 是 3Х3 旋转矩阵。关于向量 H ， L ，U ，旋转 α 的矩阵表示如下：- 43 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建?cos α sin α 0? RU (α ) = ?? sin α cos α 0? ， ? ? ?0 0 1? ? ??cos α 0 ? sin α ? ?， RL (α ) = ?0 1 0 ? ? ?sin α 0 cos α ? ? ?(4.0)0 ?1 0 ? ?0 cos α ? sin α ? RH (α ) = ? ? ?0 sin α cos α ? ? ?用下列带参数的符号控制龟形的空间方向： + (δ ) ：用旋转矩阵 RU (δ ) 表示向左旋转 δ 角； - (δ ) ：用旋转矩阵 RU ( ?δ ) 表示向右旋转 δ 角； & (δ ) ：用旋转矩阵 RL (δ ) 表示向下旋转 δ 角； ∧ (δ ) ：用旋转矩阵 RL ( ?δ ) 表示向上旋转 δ 角； \ (δ ) ：用旋转矩阵 RH (δ ) 表示向左滚动 δ 角； M (δ ) ：用旋转矩阵 RH ( ?δ ) 表示向右滚动 δ 角； 例如一个 L 系统描述如下：r1 =0.9 r2 =0.9树主枝的缩短比例 树分枝的缩短比例 旁枝与主枝间的夹角 旁枝上各分枝间的夹角α 0 =45 ° α 2 =45 °d =137.5 ° 旁枝与旁枝间的夹角ωr =0.707 树枝宽度的比例 ω ： A(1,10) ；- 44 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建P1 ： A(l , ω ) →! (ω ) F (l )[&(α 0 ) B(l × r2 , ω × ωr )] /(d ) A(l × r2 , ω × ωr ) ； P2 ： B(l , ω ) →! (ω ) F (l )[ ?(α 2 )$C (l × r2 , ω × ωr )]C (l × r1 , ω × ω r ) ； P3 ： C (l , ω ) →! (ω ) F (l )[ +(α 2 )$ B(l × r2 , ω × ωr )]B(l × r1 , ω × ωr ) ；其中 ! (ω ) 设置线宽为 ω ，子枝与母枝之间宽度比为 ωr =0.707；符号 $ 是沿自身轴 旋转龟形，使指向龟形左边的向量 L 转到水平位置， $ 按下列公式修改龟形在空间 的方向L=V ×H V ×H和H Х L =U(4.1)其中 V 是重力的相反方向，| A |表示向量 A 的长度，在确定分支平面时，以母枝 方向作为子枝的向前方向 H ， H 与 V 叉乘得到子枝的向左方向 L ，然后在 L 与 H 确定的平面上，用二分法找到与 H 夹角为 ? α 2 和 α 2 的向量，这就是子枝的方向。4.2 IFS 系统的三维化4.2.1 生成三维 IFS 代码的理论基础定义 4.1 自仿射变换 W ：三维欧氏空间 R → R 具有形式：3 3W ( X ) = A( X ) + b(4.2)的变换，这里 A 是 R 3 上的线性变换，且 b 是 R 3 中的向量。因此，仿射变换 W 是平 移，旋转，膨胀或者是反射的合成。这里公式(4.2)的具体形式是：? x ? ?a11 a12 a13 ? ? x ? ?b1 ? W ? y ? = ?a 21 a 22 a 23 ? ? y ? + ?b2 ? ? ? ? ? ? ? ? ? ? z ? ?a31 a32 a 33 ? ? z ? ?b3 ? ? ? ? ? ? ? ? ?(4.3)- 45 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建其中 aij ， bi 是实数， A 表示矩阵 aij ， (i, j = 1,2,3) ， X 表示矢量 ( x, y , z ) T ， b 表 示矢量 ( b1 , b2 , b3 ) ， T 是转置操作。 定义 4.2 在空间 R 3 中，设 D ? R 3 为一闭子集， d 为距离函数，若存在数T0 & c & 1 ，使得对所有 X , Y ∈ D ，有d (W ( X ), W (Y )) ≤ cd ( X , Y )(4.4)则自仿射变换 W : D → D 称为 D 上的压缩映射。式中的 c 称为映射 W 的 Lipshitz 常数 定义 4.3 设 W1 ,? ? ??, Wn 是 D ? R 3 上的一组压缩仿射变换，使得d (Wi ( X ), Wi (Y )) ≤ ci d ( X , Y )( X ,Y ) ∈ D(4.5)对每个 i, ci & 1 成立， 则称此一组自仿射变换 W = {Wi , i = 1,2,? ? ??, n} 是绝对收缩的。 定 义 4.4 设 D 是 R 3 上 的 一 个 紧 致 空 间 ， D ? R 3 ， 存 在 一 组 压 缩 变 换W = {Wi , i = 1,2,? ? ??, n} ， 其 特 性 为 D → D ， 伴 随 W 有 一 个 概 率 集 合 P = {Pi , i = 1,2,? ? ? ? ?, n} ，且 P & 0, ∑ Pi = 1 ，则称 {D, W , P} 组成一个迭代函数系统，有时也称它为一个 IFS 代码。 定理 4.1 设 W = {Wi , i = 1,2,? ? ??, n} 是 R 上的仿射压缩变换，则存在一个唯一3非空紧集 A ，它满足A = U Wi ( A)i =1n(4.6)则称 A 为 IFS 的吸引集，并且与起始点 X 无关。 定理 4.2 对欧几空间 R 3 上所有 Borel 子集：B ∈ B ( R 3 ) ， P ( X , B ) 是 Borel 设 集 B 上的转移概率，如果给定一个概率测度 ? 有- 46 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建? ( B ) = ∫ P( X , B )d? ( X ) = ∑ Pi ? (Wi ?1 ( B ))( K ? R 3 )k i =1n(4.7) 则称 ? 是 IFS 的 P ? 平衡测度。 伴随着每一个迭代函数系统都有一个唯一的吸引集 A ，和一个特别的概率机P ? 平衡测度，它作用在吸引集 A 上，其中 A 的结构由 W 控制，它是 R 3 上若干随机点的集合，但在随机行走时点的轨迹不会离开吸引集，它在屏幕上显示出来就是 一幅由模糊到清晰的三维分形图形。 在吸引集中， 某处轨迹停留的次数由平衡测度 ? 决定，而 P 直接决定平衡测度 ? ，该测度对随机行走来讲是稳定分布，它提供了图 像的层次信息，使 A 成为一个有灰度的图像。 迭代函数系统 {R 3 , W , P} 中的每个 Wi 由代码 aij ，bi ，i = 1,2,3, j = 1,2,3 决定， 则对应的 Pi 的均匀分配可以由下面公式的绝对值得到( a11 ) i ( a12 ) i (a13 ) i ( a 21 ) i (a 22 ) i ( a 23 ) i (a 31 ) i ( a 32 ) i ( a 33 ) i Pi = ( a11 ) k ( a12 ) k ( a13 ) k n ∑ (a21 ) k (a22 ) k (a23 ) k k =1 ( a31 ) k ( a 32 ) k ( a 33 ) k(4.8)由上式可知， Pi 的分配与每个拷贝的大小有关即与 Wi 有关，有了上式后，可以 在此基础上再对 Pi 进行调节，便可得到我们需要的 {Pi , i = 1,2,? ? ??, n} 。由此得到了 一组三维 IFS 代码。 4.2.2 三维交互设计算法 我们知道，交互式生成二维 IFS 代码是比较容易的，其过程为：首先确定要创 建的景物图形，比如海岸线，山峰，树等，然后，把该景物的大致轮廓用鼠标器、 键盘、光笔等器件在屏幕上画出，然后在该轮廓上取相应的点，通过拼和定理产生 一组 IFS 代码，最后利用随机迭代过程，产生一个分数维图形，如果产生的图形效 果不好，则返回修改 IFS 代码，直到满意为止。- 47 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建但是，要交互生成三维 IFS 代码就远非如此简单了，因为屏幕坐标是二维的， 而要求输入的分形景物的大致轮廓是三维的。那么要采用什么方法来输入呢？在这 里，我们采用立体测量系统方法来完成这一工作。 立体测量系统，它由一对摄像镜头和一个可以旋转的工作台组成，镜头控制器 可以控制镜头的光圈，方位，仰角等等。两镜头间的角度 ? 可以调整。指针系统建 立被测物体的三维点与二维透视投影点之间的关系，指针控制器控制指针指向需要 测量的点。一旦完成摄像，就建立了测试点与两幅图像上二维透视投影点之间的对 应关系。调整镜头的变焦装置，可以得到原图的子拷贝，从而得到被测物体的两个 屏幕投影轮廓图及两个子拷贝图，然后进行平移，旋转，使子图部分覆盖原图。可 以 知 道 要 生 成 一 组 三 维 代 码 ， 首 先 要 知 道 一 组 三 维 坐 标 点 ( x, y , z ) 和(W ( x ), W ( y ), W ( z )) ，在这里，可以采用如下的方法来获取三维坐标数据 [13] 。由计算机图形学中透视投影变换的知识可以知道，三维物体上的点 ( x, y , z ) 和 它透视投影后的像点 ( x ′, y ′) 可用下面的公式表示：?T11 T12 ?T T22 ? 21 ?0 0 ? ?T31 T32T13 T14 ? ? x ? ? X ? ? x ′H ? ? ? y? ?Y ? ? y ′H ? T23 T24 ? ? ? =? ?=? ? 0 0 ? ?z ? ?0 ? ?0 ? ? ? ? ? ? ? ? T33 T34 ? ?1 ? ?H ? ?H ?(4.9)将上式两边展开，消去 H ，可得(T11 ? T31 x ′) x + (T12 ? T32 x ′) y + (T13 ? T33 x ′) z + (T14 ? T34 x ′) = 0 (T21 ? T31 y ′) x + (T22 ? T32 y ′) y + (T23 ? T33 y ′) z + (T24 ? T34 y ′) = 0(4.10)如果知道 T 与 ( x ′, y ′) ，则可以反过来求 ( x, y , z ) 。但是由于两个方程无法决定三个 未知数， 因此， 我们需要从不同的视点拍摄至少两幅图像， 也就是说同样的 ( x, y , z ) 由变换 Ti 可以得到投影点 ( xi ′, yi ′)(i = 1,2,? ? ? ? k ) ， 于是由(4.10)式得到下列形状的2k 个方程 (k ≥ 2)ai1 x + ai 2 y + ai 3 z = bi (i = 1,2,? ? ??,2k )- 48 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建用矩阵表示为 A ? X = B 。 其中a12 a13 ? ?b1 ? ? a11 ?x? A = ?? ? ? ? ? ? ? ? ?? ， X = ? y ? ， B = ?b2 ? ? ? ? ? ? ? ?b3 ? ? a 2 k 1 a 2 k 2 a2 k 3 ? ?z ? ? ? ? ? ? ?由于 k ≥ 2 ，因此方程个数多于未知数 x, y , z 的个数。通常，用最小二乘法求解， 即求 ( x, y , z ) ，使误差E = ∑ ( ai1 x + ai 2 y + ai 3 z ? bi ) 2i =12k最小。为此，必须满足，eE / ex = ο , eE / ey = ο , eE / ez = ο不难知道，它等价于 A ? A ? X = A ? B 这里 AT 是 A 的转置矩阵。从而T TX = [ AT A]?1 ? [ AT B ]回过来讨论如何决定变换矩阵 T 。利用(4.10)式，如果已知几个点 ( xi , yi , zi ) 的透 视投影点 ( xi ′, yi ′)(i = 1,2,? ? ? ? k ) ，那么就可以得到求 12 个未知数( T 有 12 元素) 的 2n 个方程。 有了变换矩阵 T 后，通过计算机就可以自动获得三维坐标数据，然后根据上面 的公式，反复运用拼合定理就可以生成一组三维 IFS 代码，最后运用随机迭代过程， 同时配合计算机图形学中的图形生成、投影透视、变换、消隐等常规算法，一幅十 分逼真的三维几何图形便生成了。 4.2.3 随机颜色算法 这种算法在上文中已经提到，它是一种伪随机的方法。该方法实现简单，但是 它不是真正的三维图形，看起来也不是非常的逼真。下面简单介绍它的程序实现。- 49 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建if(colorLock)//颜色锁定，产生伪三维图形，实现真实感效果 { g=canvas.getGraphics(); g.setColor(new Color(0,130+i*20,0)); }如果程序运行到该程序段，并且 colorLock 的值为真，那么就执行。首先， g=canvas.getGraphics() 获 取 画 布 的 图 形 属 性 ， 接 着 g.setColor(new Color(0,130+i*20,0))设置画布新的画图颜色，这个颜色参数是随机的，它的随机 性受规则的概率约束。4.3 本章小结本章简要的讨论了由 L 系统和 IFS 系统生成的图形如何实现真实感效果，并给 出了一些算法。在植物的模拟实验中，为了生成逼真的三维图形，无论是 L 系统， 还是 IFS 系统模型都应建立在对真正的植物的仔细的观察的基础上。只有根据事物 的特征，比如树的主枝与分枝有长短、粗细等区别，通过引入随机性，并用概率方 法进行控制，使不同的规则在使用中更加灵活、合理。当然，三维模拟算法不是唯 一的，它会随着时间的推移不断进行更新，完善。参考文献[1]张济忠著.分形.北京：清华大学出版社，2001. [2][英]肯尼思?法尔科内著， 曾文曲等译.分形几何--数学基础及其应用.沈阳： 东北大学出版社，2003. [3]齐东旭著.分形及其计算机生成.北京：科学出版社，1996. [4][法]B.Mandelbrot 著. 文志英等译.分形对象―形，机遇和维数.北京：世 界图书出版公司，1999 [5]刘华杰著.分形艺术(电子版).长沙：湖南科学技术出版社，1997. [6]李后强，汪富泉编.分形理论及其发展历程.http://www. [7] 贾 建 . 迭 代 函 数 系 统 与 分 形 图 形 融 合 技 术 研 究.http://202.200.59.5:90/mst.dll? [8]高旭，姜楠编.分形 L 系统理论与植物图像的计算机模拟.扬州大学学报， 2000，11. [9]张树兵，王建中编.基于 L 系统的植物建模方法改进.中国图象图形学报，- 50 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建2002，5. [10]高旭，徐永安编.迭代函数系统及其应用.南京理工大学学报，1996，8. [11]熊勇，史定华编.随机迭代函数系统的仿射变换.应用数学和力学，2001， 7. [12]王方石编.L 系统在植物模拟中的应用.北方交通大学学报，1998，6. [13]方志伟，马燕编.三维迭代函数系统代码生成算法分析与实验研究.上海师 范大学学报(自然科学版)，1994，3. [14]周晓萍编.迭代函数系统分形图的计算.郑州大学学报，2000，11. [15]陈天滋编.植物模拟技术的研究.计算机应用研究，2000，11. [16]王兴元编.三维奇怪吸引子透视图的计算机模拟.东北大学学报(自然科学 版)，1999，1. [17]刘向东等编.迭代函数系 IFS 吸引子的参数控制与树木的模拟.计算机工程 与应用，2000，5. [18]魏小鹏等编.三维非线性 IFS 分形的可视化问题研究.工程图学学报， 2000， 1. [19]曾文曲等著.植物的枝的分形算法.(摘自《分形理论与分形的计算机模 拟》).http://www. [20]Paul Martz 著 ， 品 雪 译 . 三 维 随 机 分 形 地 形 生 成 . http://www. [21]曾文曲等著.分形的字符串替换算法(摘自《分形理论与分形的计算机模 拟》).http://www. [22]刘式达等著.自然科学中的混沌和分形.北京：北京大学出版社，2003. [23]J?布里格斯和 F?D?皮特著.刘华杰等译.分形的秘密.商务印书馆， 1998.- 51 -PDF 文件以 &FinePrint pdfFactory Pro& 试用版创建
分形_专业资料。我们应该知道的知识谁不知道 熵 概念就不能被认为是科学上的文化人 ,将来谁不知道分形概念 ,也不能称 为有知识 。”――物理学家 惠勒 物理学...分形的概念_信息与通信_工程科技_专业资料。分形的概念分形理论是人们在自然界和社会的实践活动中所遇到的不完全规则事物的 一种数学抽象。分形理论自从 20 世纪 70...100页 免费 分形理论 10页 免费 分形理论基础 2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...分形图形求助编辑百科名片 请输入图片说明 分形理论是非线性科学的主要分支之一,它在计算机科学、化学、生物学、天文 学、地理学等众多自然科学和经济学等社会科学中...分形的源码: ho:=h&ref(h,1) and h&ref(h,2) and h&=refx(h,1) and if(h=refx(h,2),h&refx(h,3),h&refx(h,2)); fxh:=cross(ho,0.9)...分形理论_物理_自然科学_专业资料。分形理论的概述,分形理论的一些应用实例,分形理论在一些领域的应用毕 业 论 文 题学专 目: 分形理论 院: 物理与电子工程学院...各种有趣的分形我们看到正方形,圆,球等物体时,不仅头脑里会迅速反映出它是 什么,同时,只要我们有足够的数学知识,我们头脑中也反映出它的数 学概念,如正方形是...分形技术_能源/化工_工程科技_专业资料。分形技术一、基本概念及原则 经典的欧氏几何学只研究直线、矩形、圆、三角形、圆锥面、锥体、椭球体 等规则的形状,而对于...(2)部分与整体以某种形式相似的形, 称为分形。然而,经过理论和应用的检验,人们发 现这两个定义很难包括分形如此丰富的内容。实际 上,对于什么是分形,到目前为止...7 附 4: §4 分形作为艺术 4.1 什么叫分形图形艺术 分形图形艺术是计算机图形艺术的一种。计算机图形(绘画)艺术一般分作两大流派: 计算机绘画艺术 = 波普(...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。