神经网络课系列讲座 分 形 (fractal) 合肥工业大学 图像信息处理研究室 分形展厅 （国内外分形作品） 见山见水 墨韵 纹身 火凤凰的诞生 over 主要内容 分形的产生背景？ 谁是分形理论的创始人？ 什么是分形？特征？ 分形可以应用于哪些领域？ 合肥工业大学 图像信息处理研究室 Tel:2901393 地址：逸夫楼 709 Email:imageshfut.edu.cn http:/www1.hfut.edu.cn/organ/images 分形的产生背景 在经典的欧几里德几何学中，我们可以用直线、立方体、圆锥、球等这一类规则的形状去描述诸如道路、建筑物、车轮等等人造物体，这是极自然的事情。 然而在自然界中，却存在着许许多多极其复杂的形状，如，山不是锥，云不是球，闪电不是折线，雪花边缘也不是圆等等，再如宇宙中的点点繁星所构成集合更非经典集合所能描述的，它们不再具有我们早已熟知的数学分析中的 连续、光滑 （可导）这一基本性质了。 这一类奇形怪状的物体长期以来被认为是“ 不可名状的 ” 或 “ 病态的 ” ，从而很容易被人们忽视了。显然传统的数学已经无法来描述它们，从而使经典数学陷入了危机，于是分形几何 学 （ fractal geometry）便应运而生。 分形几何学是一门以 非规则几何形态 为研究对象的几何学。由于不规则现象在自然界是普遍存在的，因此分形几何又称为 描述大自然的几何学 分形几何与传统几何相比有什么特点 从 整体上 看，分形几何图形是 处处不规则 的。例如，海岸线和山川形状，从远距离观察，其形状是极不规则的。 在 不同尺度 上，图形的 规则性又是相同的。上述的海岸线和山川形状，从近距离观察，其局部形状又和整体形态相似，它们从整体到局部，都是自相似的。 分形人物 Mandelbrot 分形理论创始人美籍法国数学家Mandelbrot。 Mandelbrot 美国 IBM（国际商业机器）公司沃特森研究中心自然科学部高级研究员 哈佛大学应用数学兼职教授 美国国家科学院院士 美国艺术与科学研究员成员 欧洲艺术、科学和人文研究院院士。 1967年发表于美国 科学 杂志上的 “ 英国的海岸线有多长 ” 的划时代论文，是他的分形思想萌芽的重要标志。 1973年，在法兰西学院讲课期间，他提出了分形几何学的整体思想。 1977年，他出版了第一本著作 分形：形态，偶然性和维数 ，标志着分形理论的正式诞生。 五年后，他出版了著名的专著 自然界的分形几何学 ，至此，分形理论初步形成。 Fractal（分形）一词的由来 据曼德勃罗教授自己说， fractal一词是 1975年夏天的一个夜晚，他在冥思苦想之余偶翻他儿子的拉丁文字典时，突然想到的。 取拉丁词 fractus之头，撷英文 fractional之尾，就得到了 fractal一词。本意是 不规则的、破碎的、分数的 。 曼德勃罗是想用此词来描述自然界中传统欧几里德几何学所不能描述的一大类 复杂无规 的几何对象。例如，弯弯曲曲的海岸线、起伏不平的山脉，粗糙不堪的断面，变幻无常的浮云，九曲回肠的河流，纵横交错的血管，令人眼花僚乱的满天繁星等。它们的特点是，极不规则或极不光滑。直观而粗略地说，这些对象都是分形。 什么是分形？ 实例 定义 分形特征 海岸线有多长？ 按照传统的科学方法来考虑，这是一个及其简单的问题，然而曼德勃罗教授在其名为 英国海岸线有多长？ 的文章中作出了令人惊诧的答案： “ 英国海岸线的长度是不确定的 !其原因在于海岸线的长度依赖于测量时所使用的尺度。 ” 以 1km为单位测量海岸线，得到的近似长度将短于 1km的迂回曲折都忽略掉了，若以1m为单位测量，则能测出被忽略掉的迂回曲折，长度将变大，测量单位进一步变小，测得的长度将愈来愈大，这些愈来愈大的长度将趋近于一个确定值，这个极限值就是海岸线的长度。 问题似乎解决了，但 Mandelbrot发现：当测量单位变小时，所得的长度是无限增大的。他认为 海岸线的长度是不确定 的，或者说，在一定意义上海岸线是无限长的。为什么？ 答案也许在于海岸线的极不规则和极不光滑。此时，长度也许已不能正确概括海岸线这类不规则图形的特征 。 几种典型的分形图案 KOCH曲线 返回 Sierpinski三角形 什么是分形？ 实例 定义 分形特征 分形定义 分形： 是一种具有 自相似特性 的现象、图像或者物理过程。也就是说，在分形中，每一组成部分都在特征上和整体相似，只仅仅是变小了一些而已。 什么是分形？ 实例 定义 分形特征 分形特征 自相似性 self similarity 指某种结构或过程的特征从不同的空间尺度或时间尺度来看都是相似的或者某系统或结构的局域性质或局域结构与整体相似。 它不但包括严格的几何相似性，而且包括通过大量的统计而呈现出的自相似性。 分形植物 Koch 雪花 Sierpinski 三角形 如果你是个有心人，你一定会发现在自然界中，有许多景物和都在某种程度上存在这种自相似特性，即它们中的一个部分和它的整体或者其它部分都十分形似。 其实，远远不止这些。从心脏的跳动、变幻莫测的天气到股票的起落等许多现象都具有分形特性。这正是研究分形的意义所在。 标度不变性 scale invariance 指在分形上任选一局部区域，对它进行放大，这是得到的放大图又会显出原图的形态特性。因此，对于分形，不论将其放大或缩小，它的形态、复杂程度、不规则性等各种特性均不会发生变化，所以标度不变性又称为伸缩不变性。 分形植物 Mandelbrot集 分形维数 维数是几何学和空间理论的基本概念。例如一维的直线，二维的平面，三维的普通空间，都是人们熟知的。但如果想知道雪花、云彩、山脉、树枝以及烟圈等等复杂自然结构的维数是多少，用传统的数学是难以回答的，至多是定性的描述。而分形理论则给出定量的分析，即可用分维（分形维数、分数维）加以表征。它不是通常欧氏维数的简单扩充，而是赋予了许多崭新的内涵。 你是否听说过世界上存在 2.8126维的物体？ 是的！ 尽管听起来似乎比较荒诞，但这是事实。在这个概念的基础上才有分形学的发展。 让我们先作一个类比。 牛顿的运动学定律可以使人们预测运动物体的运动情况。但是，当运动物体的速度接近光速时，这个定理就变得极不准确。 于是，在 1900初，爱因斯坦发明了相对论。这个成果发展了牛顿定律。如果你去检验相对论，你会发现，在低速的情况下，相对论的结果等同于牛顿定律。 那么，这和分维有什么联系呢？ 像相对论发展了传统力学一样，分维是对传统维数概念的进一步发展。它并不和你所了解的分维知识相冲突，而是一种发展！ 一般情况下，分维是一个分数。它反映了一个分形体的不规则程度，分形维数越大，则分形体越不规则。 这里我们介绍比较常用的三种分形维数： 相似维数 hausdorff 维数 盒子维数 相似维数（ Similarity Dimension）： 如果某图形是由把全体缩小为 1 a的 b个相似图形构成的，那么相似维数 Ds可以由下式给出 ： ab ln/lnD S 例如，对于 koch曲线，可以分成四个部分，每个部分都为原来的 1/3大小，而每一部分又可以同样的细分，则它的相似维数 2 6 1 9.13ln/4ln)( k o c hDsKoch曲线 Hausdorff 维数 设有一条长度为 L的线段，若用一长 r 的 “ 尺 ” 作为单位去量它，量度的结果是 N，我们就说这条线段有 N尺。显然 N的数值与所用尺的大小有关，它们之间具有下列关系： 1/)( rrLrN同理，若测量的是一块面积为 A的平面，这时用边长为 r 的单位小正方形去测量它，有下式成立 ： 22 /)( rrArN同样，可以用半径为 r的小球来填满一块体积 V球体 ，所需小球的数目比例于： 3/ rV 对于任何严格有确定维数的集合体，若用与它具有相同维数的 “ 尺 ” 去量度，则可以得到一确定的数值 N，若用低于它维数的 “ 尺 ” 去量它，结果为无穷大；若用高于它维数的 “ 尺 ” 去量它，结果为零。其数学表达式为 HDrrN )(对上式两边取自然对数，可得： )/1ln (/)(ln rrND H 式中的 DH就称为 Hausdorff 维数，它可以是整数，也可以是分数。它是最古老的也是最重要的一种维数，它对任何集都有意义。然而，计算 Hausdorff 维数是相当困难的。 盒子维数 定义：设 ，在欧氏距离下，用边长为 的小盒子紧邻地去包含 A，设 为表示包含 A所需的最小盒子数，则： nnnAND2ln)(lnlim即为集合 A的盒子维。 计算：逐渐增大 n， 分别计算出 相应的值 ，这样就得到一组 的数据对 ， 再利用线性回归等方法求出 相对于 的斜率 ， 即为所要求的盒子维 。 nRA n2/1)(ANn)(ANn)(ln,2( ln AN nn)(ln ANn n2ln 分形应用领域 图像处理方面 图像分割 目标识别 图像压缩 图像边缘检测 图像分析、合成 图像分割 灰值图像 ， 尤其是基于自然景观的灰值图像 ，可能是由多类具有不同分形性质的物质组成的 。所以我们在对图像提取分数维时一般是按图像分块进行的 ， 即设定一个窗口 ， 尺寸大小一般选成 8 8或 16 16等 ， 提取的是窗口区域的分数维 ， 窗口的移动是从左向右 ， 从上向下移动 。由分形理论我们可以知道：同一分形物质在不同区域一般具有相同的维数 。 所以当我们在同一图像的不同区域求得分数维以后 ， 就可以基于此进行分类 、 分割 。 目标识别 人们把分数维与传统方法结合起来来处理自然背景下的人造物体的识别 ， 例如隐藏在树林山峦间的坦克 、 炮车等等 。 传统的匹配检测方法包括相似度量 ， 匹配点搜索等步骤 ， 这在计算上有很大的时间复杂度 。 现在使用分数维的方法 ， 一般选择窗口的大小同被检测物体的尺寸大致相等 ，这一般是可预知的 ， 一旦某些窗口出现了异常的分数维 ， 比如低于一定的拓扑维数或不同于大多数区域的分数维等等 ， 它们才被送入下一步进行精搜索 。 这里分数维主要起着可疑区域判定的作用 。 图像压缩 1988年 Barnsley采用迭代函数系统 IFS和递归迭代函数系统 RIFS方法，对几幅图像进行压缩编码获得了高达10000:1的压缩比。 1992年的圣诞节，美国微软公