| 查看: 459 | 回复: 0 | ||||
| 当前主题已经存档。 | ||||
霹雳旋风荣誉版主 (著名写手)
|
[交流]
分形的概念及应用
|
|||
|
【前沿】分形的概念及应用 技术专题 导读:你可能有点纳闷-这期技术专题是"多媒体数据压缩"，可几篇文章乍一看 离题甚远。其实，它们折射了多媒体数据压缩的原理、标准、应用等多个侧面。 最初，从五彩斑斓的蝴蝶身上，人们发现了分形的概念。你可以将它简单理解 为：云朵、海岸线等无法用常规的、传统的几何方法描述的图形。寻找这种"不规 则"图形的规律与特性的思路，对图形压缩、气象、生态，直到城市规划等许多相 距甚远的领域具有启发作用。 听CD、看VCD已是现代人普遍的消遣娱乐方式。目前，它们大多采用MPEG-2编 码标准。但熟悉的东西未必就是最好的，为了适应通信与信息处理的需要， MPEG-4编码标准正在紧锣密鼓地完善之中。 视频点播（VOD）并不是一个新鲜的名词，但绝大多数人都是听说过没见过。 这里你将了解到视频点播的概念和硬件组成部分。随着网络性能的提高，视频点播 正一步步走近我们。没有人怀疑它广阔的应用前景。 分形的概念及应用 ★ 中国人民大学信息学院 陈禹 分形(Fractal)是20世纪科学思想的大变革中，十分引人⒛康囊欢淦孑狻４? 理论上讲，它是数学思想的新发展，是人类对于维数、点集等概念的理解的深化与 推广，所以人们把它称为是一种新的几何学-分形几何学。然而，它又与现实的物 理世界紧密相连，成为研究混沌(Chaos)现象的重要工具。众所周知，对混沌现象 的研究正是现代理论物理学的前沿和热点之一。除了理论上的意义之外，在实际应 用中，分形也显示了巨大的潜力。从气象、生态，直到图形压缩、城市规划，在许 多相距甚远的领域里，都发现了分形的概念与方法的用武之地。人们惊奇地发现， 分形现象在自然界是普遍地、大量地存在着。对于从事计算机技术的人员来说，分 形还是计算机技术的发展与应用的一项重要成果。事实上，关于分形的认识和研究 ，是一步也离不开计算机的。反过来，分形的思想与方法又在计算机技术的发展中 产生了人们意想不到的影响和作用。分形概念的产生与发展，进一步拓宽了我们的 视野，使人类的科学思想登上了一个新的台阶。因此，作为从事软件技术的科技人 员，应当对于科学万花丛中的这一朵奇葩有所认识、有所了解。这无论对于我们开 拓思路，还是对于软件开发的实际工作都将是十分有益的。 一、分形的概念 分形是一个新的概念，不同的专家有不同的定义方法。当然，不同的说法所描 述的还是同一件事物，只是强调其不同的侧面，不同的属性而已。 从直观上来看，所谓分形是指一些无法用常规的、传统的几何方法描述的图形 。例如天空的云彩、曲折的江河和海岸线、树叶、山峰等。它们不同于正方形、圆 、直线等规则的几何图形，表现出某种混乱和不规则。通常的度量概念，如长度、 面积等，对它们来说，不仅很难计算，而且有时根本是无法计算的。例如，曾有科 学家提出了这样一个似乎荒谬的命题："英国的海岸线的长度是无穷大。"他的论证 思路是这样的：海岸线是破碎曲折的，我们测量时总是以一定的尺度去量得某个近 似值，例如，每隔100米立一个标杆。这样，我们测得的是一个近似值，是沿着一 条折线计算而得出的近似值，这条折线中的每一段是一条长为100米的直线线段。 如果改为每10米立一个标杆，那么实际量出的是另一条折线的长度，它的每一个片 段长10米。显然，后一次量出的长度将大于前一次量出的长度。(注意，这种测量 结果与尺度有关的现象，对于通常的直线线段，正方形，圆和椭圆都是没有的。) 如果我们不断缩小尺度，所量出的长度将会越来越大。这样一来，海岸线的长度不 就成为无穷大了吗?这个例子直观地显示出了分形与我们习惯的几何图形的区别。 几千年来，人们的视野局限于所谓"常规"的几何图形上，而忽视了这些"非常规"的 、"不规则"的图形。然而，本世纪中叶以来，人们发现，在这些"非常规"的、"不 规则"的图形中蕴藏着丰富的、有趣的规律和性质。 从理论上说，分形可以定义为"非整数维数的点集"。当然，要理解这个概念， 必须先推广维数的概念。一般来说，维数都是整数，直线线段是一维的图形，正方 形是二维的图形等等。那么，如上所说的海岸线是几维的呢?如果不确切地描述一 下，那就可以说，由于海岸线的曲折和不规则，作为一个点集，它所包含的点比直 线线段上的点要更"多"一些，当然，它并没有铺满平面，所以它比平面(例如一个 正方形或圆)上的点要"少"一些。如果从点的"多少"来理解维数的话，那么海岸线 的维数应当是大于1而小于2的一个数，即具有非整数的维数，所以海岸线是一个分 形图案(近期的研究表明，海岸线的维数大约是1.2)。在下一节里，我们会看到几 个典型的分形图案，并进一步体会分形的含义。当然，确切的、非整数维数的定义 需要专门的、建立在集合论和数理逻辑基础之上的讨论，这里无法详细叙述。有兴 趣的读者可以参看本文后面所介绍的有关文献，例如文献［1］。 另一方面，我们可以从分形图案的特点去理解它。分形图案有一系列有趣的特点， 如自相似性、对某些变换的不变性、内部结构的无限性等。所谓自相似性是指分形 图案往往和它自身的一部分相似，换句话说，把它的一部分按一定的尺度放大，就 又会得到它自身(可能是确切地，也可能是近似地)。内部结构的复杂与精细也是分 形图案的共同特点。此外，分形图案往往和一定的几何变换相联系，在这些变化下 ，图案保持不变，从任意的初始状态出发，经过若干次的这种变换，图形将固定在 这个特定的分形图案上，而不再发生变化。这些特征，我们可以从后面的几个例子 中体会。 二、典型的分形 上面的概念也许过于抽象，难以理解。我们通过几个例子来体会一下分形的含 义。 例一：康托尔点集 我们设想一条单位长的直线线段，去掉它的中间的三分之一，这样留下的部分 将是两段长度分别为三分之一的线段，总长度为2/3。接下去我们再把这两条线段 去掉中间的三分之一，这时留下的部分将是四条长度各为九分之一的线段，总长度 为4/9。如此不断地循环操作，最终将得到一个名为康托尔点集的集合。这就是一 个分形图案。(见图1)注意，它不是一个空集，在原线段的1／3，2／3，1／9，2／ 9，7／9，8／9……处的点将永远留在这个点集中，然而留下部分的长度显然将趋 近于零。读者不难验证一下刚才提到的三点性质在康托尔点集中都有体现。它是一 个维数在1和0之间的分形图案。 例二：柯克曲线 同样从一条单位长的直线线段出发，以它的中间三分之一为底，画出一个等边三角 形，并去掉这个底边。在这个变换中，线段的总长度将增加三分之一，成为4/3。 (如图2所示)继续这个变换，即对上一步所得图案中的每一条线段进行同样的处理 ，这时，曲线的总长度将按4/3的n次方递增而趋于无穷大，然而它并没有铺满平面 。这就是柯克曲线，一种维数大于1而小于2的分形图案。细心的读者不难看出，其 实它就是上面的海岸线问题的模拟与抽象。 例三：西尔宾斯基三角形 假定我们从一个平面图形出发，把它的长、宽都缩小一半，并分别放在正上方、左 下方和右下方。对于这样一个变换，如何反复做下去（如图3-1），则会得到所谓 西尔宾斯基三角形(见图3-2)。以上三个例子，读者可以用任意一种计算机语言编 成程序，在计算机上自己动手去实验，去观察与体会分形图案的产生及其有趣的特 性。这些程序都很简单，顶多几十行。但是当它们运行起来的时候，显示出来的奇 妙性质却是十分富有启发的。有兴趣的读者可以从本文后面所列的参考文献中找到 有关的程序。 例四：巴斯利(Barnsley)树叶 这也是一个典型的分形图案，是由澳大利亚学者M.Barnsley首先得到的。(见图4) 令人惊奇的是，这个仅由四个最基本的线性变换出发，经过反复迭代而得出的图形 竟与现实的蕨类植物的叶子几乎一模一样。它令人信服地表明，Barnsley等人所提 出的MRCM(多重压复制机制)方法确实反映了大自然中生命现象的某些规律。相比之 下，人类以前对于这些机制的了解和认识实在是太少了。 当然，产生分形图案的途径和算法还有许多。然而，仅从以上几个简单的例子，我 们已经可以体会到它给我们带来的启发。同时，我们也可以看出，计算机在分形研 究中的巨大作用。上述工作如果没有计算机，则几乎是无法想象的。 三、分形的应用 有人认为分形只是一种纯理论研究的对象，似乎和实际应用距离很远。这是一 种误解。事实上，近10年来，分形已经在许多领域中得到了非常有效的实际应用。 应用范围之广、效益之明显远远超过了十几年前的任何预测。 分形技术在数据压缩中的应用就是一个非常典型的例子。美国数学会的会刊在 1996年6月号上发表了巴斯利的文章："利用分形进行图形压缩"［5］，他介绍了把 分形用于光盘制作中，实现图形压缩的成功实践。一般来说，我们总是把一个图形 作为像素的集合来加以存储和处理。一张最普通的图片也常常涉及几十万以至上百 万个像素，从而占据大量的存储空间，传输速度也大大受到限制。巴斯利运用了分 形中的一个重要思想-分形图案是与某种变换相联系的，可以把图案看作某种变换 反复迭代的产物，这样就开辟了这样的可能性。需要存储的是有关这些变换过程的 信息，而不是存储静止的图形的像素信息。只要抓住了变换过程，图形就可以准确 地再现出来，而不必去存储大量的像素信息。在实际的应用中，已经达到了压缩存 储空间八倍以至更多的效果。有兴趣的读者可以详细阅读巴斯利的文章。 类似地，在本文所列的参考书刊中，已经报导了大量的应用案例。这些案例涉 及的领域包括：生命过程分进化过程的研究，生态系统的研究，在编码和解码中的 应用，在数论研究中的应用，在动力系统研究中的应用，在理论物理(如流体力学 和湍流)研究中的应用，在人工生命、元胞自动机和遗传算法方面的应用，在神经 生理学方面的应用，在城市规则方面的应用，在断裂力学方面的应用，在地震预报 方面的应用，在晶体生长规律方面的应用，等等。目前关于分形的书籍、文章正在 以非常快的速度增长，已有专门的网站介绍这方面的进展。如果说，十几年前，分 形还只是一种有趣的新生事物的萌芽的话，那么今天它已经成为一个令人瞩目的前 沿学科。 在大量实际应用的同时，分形给科学思想带来的启发，也是十分值得注意的。 由于分形的研究，人们对于随机性和确定性的辩证关系有了进一步的理解。同样对 于过程和状态的联系，对于宏观和微观的联系，对于层次之间的转化，对于无限性 的丰富多采，也都产生了有益的影响，提供了启发。在这方面的影响也是非常深远 ，非常重要的。 总之，对于从事计算机技术研究的人来说，分形是一个值得注意的前沿学科， 有必要了解它的思想与方法。这对于计算机科学与技术的进步和发展，无疑将是十 分有益的。 [ Last edited by 幻影无痕 on 2006-11-24 at 09:03 ] |
回复此楼» 收录本帖的淘帖专辑推荐
 科研辅助-咔咔小男人 |
» 猜你喜欢
垃圾破二本职称评审标准
已经有18人回复
-
职称评审没过，求安慰
已经有53人回复
-
毕业后当辅导员了，天天各种学生超烦
已经有5人回复
-
26申博自荐
已经有3人回复
-
A期刊撤稿
已经有4人回复
-
EST投稿状态问题
已经有7人回复