分形理论在图形学中的应用信息管理与信息系统

分形理论在图形学中的应用信息管理与信息系统内容摘要：

hirlwind I）计算机的附件诞生。 1958 年美国 Cal p 公司发明了滚筒式绘图仪， Gerber 公司研制出了平板式绘图仪。 1962 年， MIT林肯实验室的 ()发表了一篇题为“ Sketchpad:一个人 机通信的图形系统 ” 的博士论文，首次使用了计算机图 形学（ Computer Graphics）这个术语。 60年代中期，美国的 MIT、通用汽车公司、贝尔实验室和洛克希德等众多的公司纷纷开展了计算机图形学的应用和研究。 70年代是计算机图形学技术进入实用化阶段，美国苹果公司的 Macintosh、IBM 公司的 PC， Apollo、 SUN 公司的工作站都配备了图形系统。 在 80 年代，配备有光栅图形显示器的个人计算机和工作站已相当普及，不仅在工业、管理、艺术领域发挥巨大的作用，而且图形系统已进入了家庭，如计算机家庭教育和游戏。 90 年代至今，计算机图形学朝着标准化、集 成化和智能化的方向发展。 丰富多彩的 Web 网页更加激励了计算机图形学的应用，科学计算的可视化、虚拟现实技术等新兴课题又向计算机图形学提出了更新更高的要求。 . 计算机图形学的发展趋势 计算机图形学狭义上是一种研究基于物理定律、经验方法以及认知原理，使用各种数学算法处理二维或三维图形数据，生成可视数据表现的科学。 它是 计算机科学 的一个分支领域与应用方向，主要关注数字合成与操作视觉的图形 内容。 广义上来看，计算机图形学不仅包含了从三维图形建模、绘制到动画的过程，同时也包括了对二维矢量图形以及图像视频融合处理的研究。 计算机图形学经过将近 40 年的发展，已进入了较为成熟的发展期。 目前，其主要应用领域包括计算机辅助设计与加工，影视动漫，军事仿真，医学图像处理，气象、地质、财经和电磁等的 科学可视化 等。 由于计算机图形学在这些领域的成功运用，特别是在迅猛发展的动漫产业中， 带来了可观的经济效益 [1]。 10 从计算机图形学目前学科发展来看，有以下几个发展趋势 [7]： 1) 与图形硬件的发展紧密结合，突破实时高真实感、高分辨率渲染的技术难点。 2) 研究和谐自然的三维模型建模方法。 3) 利用日益增长的计算性能，实现具有高度物理真实的动态仿真。 4) 研究多种高精度数据获取与处理技术，增强图形技术的表现。 5) 计算机图形学与图像视频处理技术的结合。 6) 从追求绝对的真实感向追求与强调图形的表意性转变。 第一阶段为 18751925 年，在此阶段上人们已经认识了几类典型的分形集，并力图对这类 几何与经典的欧式几何的差别进行描述、分类和刻画。 19世纪初，人们已经能区别连续和可微的曲线，但却普遍认为连续而不可微的点应是极少的。 1872 年，维尔斯特拉斯证明了一种连续函数在任意一点均不具有有限或无限导数，即 Weierstrass 函数。 冯科赫于 1904 年通过初等函数方法构造了如今被称为 Van Koch 曲线的处处不可微的连续函数，并讨论了该曲线的性质 [12]曲线的构造极为简单，改变了人们认为不连续曲线的构造一定非常复杂的这样一种看法。 特别重要的是该曲线是第一个人为构造出的在结构上具有局部与整体相似的例子。 Peano 于 1890 年构造出填充平面的曲线，这一曲线出现后，人们提出应正确考虑以前的长度与面积的概念。 Cantor 于 1872 年引入一类现今称为Cantor 三分集的全不连通的紧集。 在当时，人们认为这类集合在传统的研究中是可以忽略的，但是进一步的研究结果表明，这类集合在像三角级数的唯一性这样重要问题的研究中不仅不能忽略 ,而且起着非常重要的作用。 在分形几何发展的第一阶段，人们已提出了典型分形对象及相关问题，并为讨论这些问题提供了最基本的工具。 第二阶段大致为 1926 年至 1975 年，这一阶段更为系统、深入研究深化了 第一阶段的思想，逐渐形成了理论，并将研究范围扩大到数学的许多分支中。 Besicovitch 等人研究了曲线的维数、分形集的局部性质、分形集的结构以及在 11 数论、调和分析、几何测度论等方面的应用。 这些研究结果极大的丰富了分形几何的理论，同时维数理论也得到了进一步发展并日臻成熟。 1928 年至 1959 年先后引入了 Bouligand 维数、覆盖维数、熵 9维数。 刻画集合“大小”的容量及其容量维数亦引入到分析中来。 同时，维数的乘积理论、投影理论、位势方法、网测度技巧、随机技巧均先后建立并成熟，使得分形几何的研究具有自己的特色与方法。 第三阶段为 1975 年至今 ,是分形几何在各个领域的应用取得全面发展 ,并形成独立学科的阶段。 在此之前虽取得许多重要成果，但主要还是局限于纯数学理论的研究，与其它学科未发生联系，同时物理、地质、天文和工程学等学科已产生大量与分形几何有关的问题，迫切需要新的思想与有力的工具来处理。 正是在这种形势下， Mandelbrot 以其独特的思想，系统、深入、创造性的研究了海岸线的结构、具强噪声干扰的电子通讯、月球的表面、银河系中星体的分布、地貌的生成、湍流的几何性质等典型的自然界中的分形现象，取得了一系列令人瞩目的成功。 Mandelbrot 将前人的研究进行总结，集其大成，于 1975 年以“分形 :形状、机遇和维数”为名发表了他的划时代专著，第一次系统地阐述了分形几何的思想、内容、意义和方法。 此专著的发表标志着分形几何作为一门独立的学科正式诞生。 自 1975 年以来，分形理论无论是在数学基础还是在应用方面都有快的发展。 在维数的估计与算法，分形集的生成结构，分形图形的计算机生成，分形的随机理论等方面获得较深入的结果，并在自然科学、材料科学和工程技术中取得巨大成功。 Mandelbrot 在对 19 世纪下半叶到 20 世纪 上半叶出现的当时被人们形象的称为“数学怪物”的数学实例及许多物理和经济现象进行研究后，终于创立了这门重要学科 — 分形几何（ Fractal Geometry）， Fractal 这个词是 Mandelbrot 创造的，来源于拉丁文 Fractus, 其英文意思是 broken。 1975 年， Mandelbrot 在巴黎出版了发文著作《 Les objects fractals： forme， basard et dimension》[12,18]， 1977年他在美国出版了其英文版《 Fractals： Form， Chance， and dimension》，标志着分形理论的正式诞生。 同年，他又出版了《 The Fractal Geometry of 12 Nature》，但这三本书对社会的影响并不大，但到了 1982 年，随着《 The Fractal Geometry of Nature》二版的问世，在美国乃至欧洲，迅速形成了“分形热”。 那么究竟什么是分形呢。 1982 年 Mandelbrot 对分形的定义是“ A fractal is by definition a set for which the HausdorffBesicoritch dimension strictly exceed the topological dimension”，即分形是一个其豪斯道夫 —— 贝西科维奇维数严格大于其拓扑维数的集合。 这个定义包括一大类具有分数维的分形集，但忽略了某些维数为整数的分形集。 1986年 Mandelbrot又给出了分形的另一个定义“ A fractal is a shape made of parts similar to the whole in some way”，即分形集具有某种自相似的特征，有很多分形集没有包括其中。 目前， 最为流行的一个定义是： 分形是一种具有自相似特性的现象、图像或者物理过程。 就像对生命的定义一样，迄今为止对分形尚未有严密的定义，但具有如下的几何特征 [14,16]： （ 1）分形集具有精细的结构，即是说在任意小的尺度之下，它总有复杂的细节。 （ 2）分形集是如此的不规则，以至它的整体和局部都不能用传统的几何语言来描述。 （ 3）分形集通常具有某种自相似性，这种自相似性可以是近似的，也可以是统计意义上的。 （ 4）分形集在某种意义下的分形维数一般大于它的拓扑维数。 （ 5）分形集在多数令人感兴趣的情形下，以非常简单的方法定义，或许以递归过程产 生。 需要说明的是，并不是所有的分形都满足上面的所有性质，有的满足其中的某条或几条性质，或对某个性质有另外。 自然界和各门应用科学中涉及的分形绝大部分是近似的。 当尺度缩小到分子的尺寸，分形性也就消失了，严格的分形只存在于理论研究之中。 分形一般分成两大类，确定性分形和随机性分形。 如果算法的多次重复仍然产生同一个分形图，这种分形称之为确定性分形。 确定性分形具有可重复性，即使在生成过程中可能引入了一些随机性，但最终的图形是确定的。 随机分形指的是尽管产生分形的规则是确定的，但受随机因素的影响，虽然可以使每次生成过 13 程 产生的分形具有一样的复杂度，但是形态会有所不同。 随机分形虽然也有一套规则，但是在生成过程中对随机性的引入，将使得最终的图形是不可预知的。 即不同时间的两次操作产生的图形，可以具有相同的分维数，但形状可能不同，随机分形不具有可重复性。 . 分数维 在欧氏空间中，人们习惯把空间看成三维的，平面或球面看成二维，而把直线或曲线看成一维。 也可以稍加推广，认为点是零维的，还可以引入高维空间，但通常人们习惯于整数的维数。 分形理论把维数视为分数，这类维数是物理学家在研究混沌吸引子等理论时需要引入的重要概念。 为 了定量地描述客观事物的“非规则”程度， 1919 年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从而突破了一般拓扑集维数为整数的界限 [8,12]。 分维的概念我们可以从两方面建立起来：一方面，我们首先画一个线段、正方形和立方体，它们的边长都是 1。 将它们的边长二等分，此时，原图的线度缩小为原来的 1/2，而将原图等分为若干个相似的图形。 其线段、正方形、立方体分别被等分为 2 22和 23个相似的子图形，其中的指数 3，正好等于与图形相应的经验维数。 一般说来，如果某图形是由把原图缩小为 1/a 的相似 的 b 个图形所组成，有： ,baD abD lo glo g （ ） 的关系成立，则指数 D 称为相似性维数， D 可以是整数，也可以是分数。 另一方面，当我们画一根直线，如果我们用 0 维的点来量它，其结果为无穷大，因为直线中包含无穷多个点；如果我们用一块平面来量它，其结果是 0，因为直线中不包含平面。 那么，用怎样的尺度来量它才会得到有限值呢。 看来只有用与其同维数的小线段来量它才会得到有限值，而这里直线的维数 为 1（大于 0、小于 2）。 与此类似，如果我们画一个 Koch 曲线，其整体是一条无限长的线折叠而成，显然，用小直线段量，其结果是无穷大，而用平面量，其结果是 0（此曲线中不包含平面），那么只有找一个与 Koch 曲线维数相同的尺子量它才会得到有限值， 14 而这个维数显然大于 小于 2，那么只能是小数（即分数）了，所以存在分维。 其实， Koch 曲线的维数是： 26 3ln 4ln D。 Mandelbrot 认为维数比起形状和机遇，更易描述集合的不规整度或破碎度，因此，他定义：若一个集合的 Hausdorff 维数 严格大于它的拓扑维数，那么该集合就称为分形集。 Hausdorff 维就是一种分数维，当然，从今天看来这种定义有不令人满意的地方，它排除一些明显应当是分形的集合，但是分数维本身的重要性仍然是不言而喻的，它是分形可以广泛应用于各学科领域的出发点。 数学上的维数并不是一个很简单的、易于理解的东西， Caratheodory1914 年提出了用集的覆盖来定义测度的思想， Hausdorff 于 1919 年用这种方法定义了并以他名字命名的测度和维数。 以此为基础，至今数学家们已经发展出了十多种不同的维数，拓扑维， Hausdorff 维，相似维，盒子维，信息维等等。 . Hausdorff 维 Hausdorff 维数是波恩大学数学家豪斯道夫（ FelixHausdorff）在 1919 年从测量的角度引进了的定义。 要讲解 Hausdorf 维首先要理解什么是 Hausdorff 测度，因为它是以 Hausdorff 测度为基础的，是各种分数维中最基本的一种，Hausdorff 测度的定义如下 [16]： U是 n维 Euclid 空间 Rn的任意非空子集， U的直径 U是这样定义的  UyxyxU  ,:s u p ， () 即 U 中任意两个点的最大距离。 如果集合 F  Ii Ui1，且 Ui 的最大直径为  ，即 0Ui ≤ ,，则说 {Ui }是 F 的一个  覆盖。 假定 F是 Rn的子集， p是非负数，对任意的  0，定义 ，覆盖的是 }F}{:i nf{)( 1    ipi ip UUFH () 并约定空集 0p  ，当  递减时，上式的下确界（缩写为： inf）是非递减的。 记 15 )(lim)( 0 FHFH pp   () 称 )(FHp 为。