什么是分形.pdf

1 引言引言 自然界是宇宙万物的总称 是各种物质系统相互作用相互联系的总体 它包括 大至宇宙天体的形成演化 小到微观世界中基本粒子的运动 随着牛顿经典力学的 创立 爱因斯坦相对论 以及量子力学的发展 人类在自然科学方面已经取得了辉 煌的成就 随着天体物理学以及其他相关学科的迅速发展 人类已经登上月球 进 入太空 人类对微观世界由质点组成的简单系统的运动规律也有了全面而正确的认 识 尽管如此 如果人们稍微注意一下周围环境中发生的大量非线形不可逆现象 就会发现 人们对这些现象知之甚少 对许多问题甚至于束手无策 举一个通俗的 例子 当你仰望蔚蓝的天空 常常可以看到天空中漂浮着一团团白云 尽管它的形 态是千变万化的 但是如果用不同倍数的望远镜来观察云团时 它的形态几乎是保 持不变 也既是说白云的形态和望远镜的放大倍数无关 分形的原文 Fractal 是 Mandelbrot 用拉丁词根进行拼造出来的单词 意思是细 片 破碎 分数等等 它是描述不规则几何形态的有效的工具 自然界中 绝大部 分物体形态不是有序的 稳定的和确定性的 而是处于无序的 不稳定的 非平衡 的和随机的状态之中 然而 曲折绵长的海岸线 凹凸不平的地表 变幻无常的浮 云 错综复杂的血管等等 诸如此类的不规则几何形态都是传统数学和物理学难以 描述和表达的 也正是于此 当 Mandelbrot 提出分形的概念后 才会引起科学界的 极大兴趣和轰动 人们对这一新兴学科感到震惊 因为它是如此的贴近生活 如此 具有诱人的发展前景 如此具有巨大的应用价值 分形理论使人们能以新的观念 新的手段来处理这些难题 透过扑朔迷离的无 序的混乱现象和不规则的形态 揭示隐藏在复杂现象背后的规律 局部和整体之间 的本质联系 分形理论在某些学科的成功尝试 极大地激发了科学研究工作者的兴 趣 他们把分形理论逐渐扩展到其它的学科领域 更进一步的促进了分形学的发展 无论是国内还是国外都不定期的召开一些关于分形的学术会议 一时间关于分形理 论的学术论文如火如荼的发表在各种期刊杂志上 分形所涉及的领域极为广泛 包括哲学 数学 生物学 物理学 材料科学 医学 农学 气象学 天文学 计算机图形学等 可以说如今的分形无处不在 分 形的发展 一部分得益于由分形产生的图形让人如痴如醉 但是更多的是因为分形 的实用价值 采用分形方法 可以利用少量的数据生成各种不同的复杂的图形 根 据分形的自相似性 能够对图形图像进行有效的压缩 美国著名物理学家惠勒说过 今后谁不熟悉分形 谁就不能被称为科学上的文化人 尽管分形理论从 Mandelbrot 的提出距今只有短短的三十多年的时间 但是其发 展速度可谓是日新月异 让人刮目相看 分形理论 20 世纪 70 年代末传入我国 在 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 2 我国的科研人员 学者的共同努力下 其理论研究和应用获得了飞速的发展 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 它的含义是不规 则的 琐碎的 支离破碎的等 我国则把它翻译成 分形 曼德尔布罗特使用 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 3 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 通过随机分形模拟出更真实的自然现象 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 4 1 3 自相似性自相似性 一个系统的自相似性自相似性 1 是指某种结构或过程的特征从不同的空间尺度或时间 尺度来看都是相似的 或者某系统或结构的局域性质或局域结构与整体类似 对于 欧氏几何而言 它们的形态是极其规则的 而且是严格对称的 人们描述起来很容 易 例如 我们想要描述一个圆形 那么只要给出圆点和半径 就能很快得出具体 的图形 然而 对于不规则的物体形态 我们就会显得束手无策 凹凸不平的地表 怪石林立的山峰 诸如此类的实物形态 我们是无法用欧氏理论描述的 尽管大自 然的物体形态是千变万化的 但是如果我们从一个分形上任意选取一个局部区域 对其进行放大 再将放大后的图形与原图加以比较 我们发现它们之间形状特征呈 现出令人惊讶的自相似性 举一个例子 对于一支花朵 有主干和支干 如果把支 干掰下来和主干比较 那么它们之间极为相似 如果再仔细地看一看花心的话 又 会发现花瓣和花瓣之间是对称的 而且也是相似的 总而言之 物质的各个部分都 或多或少的具有自相似结构 物体的自相似性为科研人员提供了研究事物新的思路 那就是 既然物体的形 态是有规律可寻的 那么我们就有办法对其进行描述 基于这一思想 我们可以利 用物体的自相似性 定义一个简单的图形规则 再在这个规则的基础上不断的进行 规则迭代 最终会生成让人意想不到的图形 当然 自然界的事物是自相似的 但不是严格的完全的相似 尽管我们观察的 分形体有很多的相似之处 然而 严格的来说它们还是有一定差别的 这就存在一 个问题 即是相似度相似度 1 它用来表示一个分形的局部与局部以及局部与整体之间的 相似程度 另外 相似并不代表相同或者简单的重复 1 如果我们将局部图形用放 大镜放大 X 倍后 不一定会和原图完全吻合 这一点应该值得注意 1 4 分形的维数分形的维数 欧氏几何学具有几千年的历史 它研究的是一些规整的图形 比如 直线 圆 椭圆 菱形 正方形 立方体 长方体 球体等 这些不同类型的曲线和形状都有 一个共同的基础 欧氏几何 即它们可以被定义为代数方程 例如 Ax By Cz D 或微分方程的解集 从欧氏几何测量中 可以看出点 直线 平面图形 空间 图形的维数分别是 0 1 2 和 3 而且都是整数 维数是几何对象的重要特征量 维数包含了集合的几何性质的许多信息 一个 图形维数的大小 表示它占有空间的大小 尤其是在分形中 它对如何准确地描述 图形起到了很大的作用 分形维数是判断两个分形是否一致的度量标准之一 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 5 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 1i i U 且对每一个 i 都有 00 定义 H s F inf 1i U i s U i 为 F 的 覆盖 1 0 式中的 inf 是下确界的缩写 于是考虑所有直径不超过 的 F 的覆盖 并试图使这些直径的 s 次幂的和达到 最小 当 减少时 式 1 0 中能覆盖 F 的集类是减少的 所以下确界 H s F 随着增 加且当 0时趋于一个极限 集合的上确界与下确界直观地被认为是集合的最大值 与最小值 记作 H s F 0 lim H s F 1 1 对 R n 中的任何子集 F 这个极限都存在 但极限值可以是 并且通常是 0 或 H s F 就被称为 F 的 s 维 Hausdorff 测度 长度 面积和体积的比例性质是众所周知的 当它们的比例放大 倍时 曲线 的长度放大 倍 平面区域的面积则放大 2 倍 三维物体的体积则放大 3 倍 同样 Hausdorff 测度也符合这一规律 所以 一个 s 维的 Hausdorff 测度对物体 放大了 s 倍 容易看出对任何给定的集 F 和 s 且 U i 为 F 的 覆盖 则有 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 6 i t i U st i s i U 1 2 取其下确界 得 H s F st H s F 令 0 对于 t s 若 H s F DT 则称该集合为分形集分形集 简称为分形分形 1 定义定义 1 2 组成部分以某种方式与整体相似的形体叫分形分形 1 对于定义1 1的理解需要一定的数学基础 不仅要知道什么是Hausdorff维数 而且要知道什么是拓扑维数 看起来很抽象 也不容易推广 定义 1 2 比较笼统的 说明了自然界中的物质只要局部和局部或者局部和整体之间存在自相似性 那么这 个物质就是分形 正是这一比较 模糊 的概念被人们普遍接受 同时也促进了分 形的发展 根据自相似性的程度 分形可分为有规分形有规分形 1 和无规分形无规分形 1 有规分形是指具 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 8 有严格的自相似性的分形 比如 三分康托集 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 的几何性质难以用传统的术语来描述 它既不是满足某些简单条件的点 的轨迹 也不是任何简单方程的解集 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 9 6 F 的局部几何性质也难以描述的 在它的每点附近都是大量被各种不同间 隔分开的其它点 7 虽然 F 在某种意义上是相当大的集 是不可数无穷的 然而 它的大小不 适合用于用通常的测度和长度的度量 用任何合理定义的长度来度量 F 的长度总 为零 图 2 0 三分康托集的构造过程 推而广之 假如我们在平面上构造康托集 那么最终生成的集合称为康托尘 康托尘的构造和三分康托集的构造很相似 它是将一个正方形分割成 16 个小正方 形 保留其中的四个 去掉其它的小正方形 依次类推 无限的循环下去 康托尘 具有和康托集相似的性质 这里不在论述 如果去掉不同的正方形 所获得的集合 是不同的 前面介绍的是非随机的有规分形 当然也可以构造随机的三分康托集 例如 在构造三分康托集的过程中 每一个区间要分成三个小区间 但是在具体舍弃哪一 个 1 3 线段上不是事先确定好的 而是随机的 每次把线段分成三部分 不是总是 去掉中间的一段 而是靠类似投骰子的方法决定的 随机的三分康托集构造过程如 下图 2 1 所示 由于是随机的 所以生成的集合无数种 这只是其中的一种 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 10 图 2 1 随机三分康托集的构造过程 一般来说 在构造随机的三分康托集时 有两个条件是可以改变的 一是对初 始长度进行多少等份或者不等份的规定 二是留下哪些部分 去掉哪个部分 1 既 然是随机的 那么在构造过程中应该在所有的尺度上也表现其随机性 也就是说应 当在构造过程中每一步 都使用随机的方法 尽管在构造它们的过程中引入了随机 性的概念 但是它们仍然属于分形的范畴 只不过生成的集合的各个元素之间是统 计自相似性的 也既是说把某个局部经过放大后 它与整体有相同的统计分布 2 2 Koch 曲线曲线 1904 年 瑞典数学家柯赫构造了 Koch 曲线 几何图形 Koch 曲线大于一维 具有无限的长度 但是又小于二维 并且生成的图形的面积为零 它和三分康托集 一样 是一个典型的分形 根据分形的次数不同 生成的 Koch 曲线也有很多种 比 如三次 Koch 曲线 四次 Koch 曲线等 下面以三次 Koch 曲线为例 介绍 Koch 曲线 的构造方法 其它的可依此类推 三次 Koch 曲线的构造过程主要分为三大步骤 第一步 给定一个初始图形 一条线段 第二步 将这条线段中间的 1 3 处向外折起 第三步 按照第二步的方 法不断的把各段线段中间的 1 3 处向外折起 这样无限的进行下去 最终即可构造 出 Koch 曲线 其图例构造过程如下图 3 3 所示 迭代了 6 次的图形 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 11 图 2 3 Koch 曲线的生成过程 无可否认 Koch 曲线的生成过程是简单的 但其曲线又是复杂的 首先 它有 很多个折点 而且这些折点是不可微的 当然也就没有切线了 其次 Koch 曲线在 许多方面的性质与三分康托集列出的那些性质类似 它由四个与总体相似的 四分 之一 部分组成 但是比例系数是 1 3 它在任何尺度下的不规则性反映了它的精 细结构 但是这样错综复杂的构造却出自于一个基本的简单结构 现在把图 2 3 的 初始图形改换成三角形 再按照上述的方法进行折叠 那么会得到另外一个分形 也既是 Koch 雪花 它的构造过程将在以后的章节中介绍 三分康托集有随机和非随机两种形式 Koch 曲线也不例外 Koch 也能够构造出 随机的 Koch 曲线 其方法和过程同三分康托集类似 这里不在重复述说 2 3 Julia 集集 Julia 集是由法国数学家 Gaston Julia 和 Pierre Faton 在发展了复变函数迭 代的基础理论后获得的 Julia 集也是一个典型的分形 只是在表达上相当复杂 难以用古典的数学方法描述 Julia 集由一个复变函数 z 2 z c c为常数 迭代生成 尽管这个复变函 数看起来很简单 然而它却能够生成很复杂的分形图形 如图 2 4 所示 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 12 图 2 4 Julia 集 由于c可以是任意值 所以当c取不同的值时 生成的 Julia 集的图形也不相同 2 4 本章小结本章小结 本章简要的介绍了几种典型的分形事例 比较直观的说明了什么是分形 以及 如何来构造分形 通过这些分形实例 我们可以看出构造分形是简单的 但是生成 的集合是复杂的 如三分康托集 图形是绚丽多彩的 Julia 集 第三章第三章 分形的描述分形的描述 图像是人类描述自然界中客观事物直观的 有效的方法 实现客观事物的计算 机模拟是许多科学家一直致力的研究课题 他们孜孜不倦的富有激情的研究如何才 能有效的表示真实的事物 分形的描述也不例外 它的出现同样引起了科学界的极 大兴趣 就其计算机的实现来说 有很多不同的算法 但是具体那种算法更有效 更实 用则要针对不同的情况 分形的描述常用的方法有 L 系统和 IFS 系统两种 从它们 所绘制出的分形来说 L 系统要比 IFS 系统简单 L 系统只是简单的字符串的迭代 而 IFS 系统在这方面要复杂的多 比如 Julia 集等 3 1 L 系统系统 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 13 林氏系统 通常称 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 两个字符 使得画线的方向 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 14 变为沿 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 表示系统中能识别的所有字符 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 系统 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 15 是确定的 记作 DOL 系统 尽管 0L 系统在所有 L 系统类型中是最简单的 但是它却能够生成许多典型的分 形事例 下面结合由 Koch 曲线构成的 Koch 雪花作为例子 详细地介绍 0L 系统如何 生成分形图形 上面已经阐明 L 系统的公理和产生式都是由字符串描述的 并且要使字符串 和图形联系起来 就要把每个字符赋予特定的含义 现在采用龟形加以说明 将龟 形形态定义为三元素集合 x y 其中 x y 是用笛卡儿坐标表示的龟图 位置 表示龟图的方向 给定步长d和角度增量 F d 向前移一步 步长为d 龟形形态变为 x y 其中 x x cosd y y sind 在点 x y 和 x y 之间画一直线段 向左旋转 龟形的下一个状态为 x y 角的正向为逆时 针方向 向右旋转 龟形的下一个状态为 x y 角的负向为顺时 针方向 下面就以典型的 Koch 曲线为例 说明用龟形画分形图形的过程 7 60 F 1 F 1 F 1 初始图 P F d F d 3 F d 3 F d 3 F d 3 生成元 起始有两个图形 一个是初始图形 另一个是生成元 生成元是一个非闭合的 有向折线 因此 构造的每个阶段都从折线开始 用生成元替代每个直的线段 压 缩生成元 并把它们放在与原来直线段有相同端点的位置上 依此类推 Koch 曲线的初始图形是一个边长为 1 的等边三角形 如图 3 1 a 生成元是一 条有四个边长为 1 3 的线段组成的非闭合的有向折线 如图 3 1 b 将初始图形的 每一条线段 即初始图形的每条边 都由生成元替代 得到图形 3 1 c 它是第一次 迭代的结果 再将生成元的每条线段缩小为原来的 1 3 长 依次替代图 3 1 c 中的 每一条线段 则生成图形如 3 1 d 所示 这样周而复始的循环迭代 即可获得 Koch 雪花 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 16 a 初始图形 b 生成元 c 第一次迭代 d 第二次迭代 图 3 1 Koch 曲线的构造 若公理 初始图形 为一个正方形 生成元也很简单 向前走两步 右转走一步 回转 走一步 右转 再走一步 图形结构见图 3 2 规则如下 90 F F F F F P F FF F F F PDF 文件以 FinePrint pdfFactory Pro 试用版创建 17 图 3 2 四方内生树 右图为代入 8 次后的图形 图 3 3 是用 L 系统生成的希尔伯特曲线 生成该曲线的规则有两条 90 Y 初始字符串为任意字母 可以看成是一点 P X YF XFX FY 第一个生成规则 Y XF YFY FX 第二个生成规则 a n 1 b n 2 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 18 c n 3 d n 4 图 3 3 希尔伯特曲线 用 L 系统生成谢尔品斯基四方垫 图形如图 3 4 所示 规则如下 90 F F F F P F FF F F F FF a n 1 b n 2 c n 3 d n 4 图 3 4 谢尔品斯基四方垫 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 19 3 1 2 随机的随机的 L 系统系统 自然界中的物质形态不是固定不变的 而是随机的 尽管它们有一定的规律可 寻 世界上没有完全按相同方式生长的两棵植物 即使是同一种植物 其形态也存 在很大差别 如茎的高矮 开花的位置 种子的形状 等等 尤其是由环境的影响 带来的形态变异 例如 作物由于肥料充足而粒大穗多 基于此 从模拟植物的效 果来说 用上述方法得到的图形显然有些呆板 不那么形象了 如果在保留某种植 物主要特征的情况下 为了产生细节上的不同变化 以求生成的植物图形更加生动 逼真 那么可以引入随机性 它的好处就是模拟出来的植物更加接近真实的事物形 态 随机的 L 系统是有序的四元素集 8 其表达式为 G 其中 V 的意义和三元式相同 然而这里的 P 却是随机的生成规则集 为函数 且有 1 i i P 1 图 3 5 随机 L 系统生成的植物图形 图 3 5 是采用随机 L 系统的数学模型生成的某一植物的图形 它是由如下规则产 生的 V F F 1 P PDF 文件以 FinePrint pdfFactory Pro 试用版创建 20 1 P F F F F F F 2 P 2 P F F F F F F 3 P 3 P F F F F F F F F F 这里取 Pi 1 3 则 1 P 2 P 3 P 1 随机 L 系统模拟自然界植物的形态随机性 对同一符号 存在几个产生规则 选择哪一个要根据其概率分布 这种概率分布可以根据先验概率来确定 随机 L 系 统考虑了在植物的形态生成过程中随机因素的影响 因而丰富了 L 系统的表现力 3 1 3 L 系统的算法系统的算法 L 系统侧重于植物拓扑结构的表达 它试图用抽象出来的规则描述植物的形态 及生长规律 该系统虽然具有定义简洁 结构化程度高 易于实现等优点 通常计 算机生成分形图形的算法大多是所谓的 迭代 在程序中的实现形式是 递归 调 用 众所周知 递归程序与非递归程序的区别在于 递归程序很难用通常的方法来 控制它的流程 虽然这一点是一个问题 但是这也是它的优点之所在 因为它的算 法非常简单 正是基于递归算法的这一优点 在编制 L 系统程序的时候就是采用这 种算法 通过前面的理论分析 L 系统算法的关键在于字符串的生成 下面对这个过程 进行具体的分析 JAVA 语言 L 系统中用到的全局变量 算法中用到的全局变量 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 21 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 return 深度为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 ruleNumber j if c sRule j 0 charAt 0 HuiHua g sRule j 1 depth 若找到公理符合规则 就调用规则 进行递归 break PDF 文件以 FinePrint pdfFactory Pro 试用版创建 22 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 b 前一线段的终点为后一线段的起始点 else if c direction rotation 逆时针转角度 else if c direction rotation 顺时针转角度 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 坐标 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 23 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 次 d 迭代 8 次 图 3 6 开花的草 程序以公理 G 开始 在第二层的 for 循环中满足规则一的条件 进入递归循环 由于递归的深度 递归深度也叫递归次数 不为零 那么继续以字符 G 递归 直到 depth 为零的时候返回 程序返回后 又以 G GFX GFG GFG 规则中的 第二个字符 F 继续递归 它同样递归到深度为零时为止 依此类推 当迭代次数 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 24 是 5 时 最终的图形就如图 3 6 a 所示 3 1 4 L 系统的实验数据系统的实验数据 下面是 L 系统程序中的事例数据 以及一些验证的数据 如下表 1 所示 表 1 中包含有事例名称 角度增量 公理和生成规则 表 1 L 系统实验数据一览表 事例名称 角度增量 公理 生成规则P 斜草 3 G G GFX GFG GFG X F XF 树伞 30 F F F F F F F F F F F F F F 有 花 蕾 的 植物 18 K S G H FFS G G FH F H H FG F K FSF 枝 25 7341 F F F F F F F 蒲公英 30 Y X X FFF FFF FX Y YFX Y Y 灌木丛 30 F F FF F F F F F F 棕榈 18 SLFFF S H G TS G H G L 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 F F FF F F F F F F 树 30 X X F X F X X F FF 对称的树 30 X X F X X FX F FF PDF 文件以 FinePrint pdfFactory Pro 试用版创建 25 3 2 IFS 系统系统 迭代函数系统 IFS 简称迭代函数系统 方法是美国佐治亚理工学院的巴恩斯利 Michael F Barnsly 等人首先应用一组收缩仿射变换生成分形图像 即通过对原始 图形 生成元 的收缩 旋转 平移等变换形成的极限图形而具有自相似的分形结构 并将该仿射变换集称之为 IFS 它与复平面上 z 2 z c z c为复数 迭代产生 的分形存在着内在的联系 只是 z 属于非线形变换 而 IFS 属于线形变换 IFS 系统的理论与方法是分形自然景观模拟及分形图像压缩的理论基础 其基本思想是 认为物体的全局和局部在仿射变换的意义下具有自相似结构 这就形成了著名的拼 接定理 IFS 方法的魅力在于它是分形迭代生成的 反问题 根据拼接定理 collage theorem 对于一个给定的图形 比如一幅图片 求得几个生成规则 就 可以大幅度压缩信息 3 2 1 IFS 的数学基础的数学基础 函数迭代系统是一个比较复杂的生成分形图形的方法 它需要依附很多的数学 知识 下面就 IFS 系统所牵涉到的定义 定理和引理进行简单的论述 定义定义 3 1 设 dX为一完备度量空间 令 XH为X的非空紧子集组成的集 合 XHBA A到B的距离d定义如下 AxBxdBAd max 3 0 其中 ByyxdBxd min 用 表示两数中取其中较大的一个 则BA 之间的 Hausdorff 距离为 ABdBAdBAh 3 1 谢尔品斯基 四方垫 90 F F F F F FF F F F FF Koch 曲线 60 F F F F F F F F 四方内生树 90 F F F F F F FF F F F 希尔伯特曲 线 90 Y X YF XFX FY Y XF YFY FX PDF 文件以 FinePrint pdfFactory Pro 试用版创建 26 可以证明 dhXH同样是一度量空间 定义定义 3 2 变换 22 RR y x e a f b y x g c gfecba R 3 2 称为二维仿射变换 公式 3 2 是 IFS 系统中生成分形点的算法基础 在分形图形的 生成过程中起到重要的作用 定义定义 3 3 设 dX为一度量空间 变换XXf 称为压缩映射 如果存在 着实数s满足条件0 s 1 使得Xyx 有 yfxfd yxsd 3 3 s称为f的压缩因子 定理定理 3 1 设XX 为度量空间 dX上的压缩映射 压缩因子为s 则映 射 XHXHW BXXBW XHB 3 4 是 dhXH上的压缩因子为s的压缩映射 引理引理 3 1 压缩映射XX 是连续映射 引理引理 3 2 压缩映射XX 把X的一个非空紧集映射成X的非空紧集 即 映射 XH到自身 定理定理3 2 压缩映射定理 设XX 是完备度量空间 dX上的压缩映射 则 具 有 惟 一 的 不 动 点Xx 并 且 对 于 任 意 点Xx 序 列 2 1 0 nx n 收敛于 x 即对于每个Xx 有 xx n n lim 这里 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 27 x n 表示映射 的n次复合 即 xx n 定义定义 3 4 一个双曲 Hyperbolic 迭代函数系统 IFS 是由一个完备度量空间 dX及 其 上 的 一 组 压 缩 映 射XX i 组 成 i 的 压 缩 因 子 为 Nisi 2 1 迭代函数系统记为 NiX i 2 1 迭代函数系统的压缩 因子为 2 1 max Niss i 定义定义 3 5 对给定的迭代函数系统 NiX i 2 1 压缩映射集 n 及其中 的系数统称为该迭代函数系统的 IFS 码 定义定义 3 6 给定一个迭代函数系统 NiX i 2 1 称集合E是它的一个 不变集或者吸引子 如果 U N i i EE 1 这里双曲的概念是指映射是压缩的 一般地 我们用压缩仿射变换来表示这些 映射 在这种情况下 IFS 的形式如下 Ni g c y x f b e a y x X i i i i i i i 2 1 IFS 系统既可以退化到一维情况 仅在实轴上进行变换 也可以加变量而扩展 到高维空间中 定理定理 3 3 设 NiR i m 2 1 是m维空间 m R上的双曲迭代函数系统 A 是它的吸引子 假定对于每个i i 的压缩因子为 i s 如果双曲迭代函数系统是完 全不相连的 则吸引子A具有分形维数DAD 其中D是下面方程的惟一解 1 1 N i D i s mD 0 3 5 如果迭代函数是有界的 则DAD 其中D是下面方程的解 PDF 文件以 FinePrint pdfFactory Pro 试用版创建 28 N i D i s 1 1 mD 0 3 6 3 2 2 IFS 系统生成图形的基本原理系统生成图形的基本原理 二维空间 R 2 上的线形变换 具有如下形式 10 y x e a f b y x g c gfecba R 对 于x y R 2 若 存 在 压 缩 因 子s满 足0 s 0 n i i P 1 1 3 9 通过式 3 8 可以生成许多构成分形图形的点 式 3 9 主要是由规则的概率控 制生成图形的形态 3 2 2 IFS