多重分形

来自集智百科
跳转到: 导航搜索

现实中的复杂系统一般都具有自相似特征,这种自相似性不仅仅体现为几何形体上的自相似,也体现为某种质量、测度在空间上的分配。例如,当我们考察人类城市中人口或者灯光在空间上的分布的时候,我们实际上在考查一个三维空间中的曲面。其中,曲面的横纵坐标分别是城市空间的经纬度,而高度坐标是对应经纬度点的人口或者灯光的密度值。然而,如果我们真的画出来这样的曲面,就会发现它并不光滑,而是非常地参差不齐,波动涨落非常剧烈的,因此传统的欧几里德几何工具以及微积分数学很难刻画。如果我们做这个曲面的等高线图,就会发现,每个等高线所包围的区域都是非常参差不齐的分形几何体。那么,我们该如何对这类不规则的空间分布进行刻画?多重分形(Multifractal)便是描述这类在不规则的分形空间之上质量分布的定量化工具。

目录

一个例子

为了说清楚什么是多重分形,以及刻画多重分形的多重分形谱(Multifractal spectrum),我们先介绍一个简单的例子。这个例子通过往经典的康托尔集上赋予质量而形成一种非常不规则的一维地形。这种地形具有典型的多重分形特性。为了定量化这种特征,我们引入了多重分形谱这一数学工具。通过简单的计算以及数值试验,我们可以初步了解到多重分形的作用与功能,至于严格的定义与具体的计算方法则留给下一节详细说明。

康托尔尘

康托尔尘(学名康托尔集Cantor Set)是由大数学家乔治·康托尔提出来的一种一维的分形集。它的构造非常简单。我们把[0,1]闭区间三等分,形成三个闭区间:[0,1/3], (1/3,2/3), [2/3,1],把中间的区间去掉,剩下[0,1/3], [2/3,1],然后再对这两个闭区间分别进行同样的操作,即三等分,然后把中间的去掉。这个操作可以一直重复下去,直到无穷。最终形成的那个无穷小测度的集合就是所谓的康托尔集。

下图形象地展示了这个不断重复地构建过程(6步):

Cantorset.png

这里列出了构造康托尔尘的Mathematica代码

NestList[Flatten[Map[Function[x,temp = x[[2]] - x[[1]]; {{x[[1]],x[[1]] + temp/3}, {x[[2]] - temp/3, x[[2]]}}], #], 1] &, {0,1}, n]

其中,n为迭代的步数。该程序能够返回每个步骤的小区间集合。

That saves me. Thanks for being so sebilnse!

多重分形谱

从图上可以看出,随着层次的不断加深,区间变得越来越碎,而质量在这些小区间上的分布就会越来越参差不齐(奇异性Singularity),但是对于每一个给定的层,所有小区间上的质量之和都为1,这是因为在不断加深层次的时候,质量在小区间上的分配都满足守恒律。我们可以用一个被称作多重分形谱的曲线来刻画这种奇异性。

首先,我们知道,在第t步的时候,任意一个小区间i的质量可以写成:


m_i=p^x (1-p)^{t-x}

其中p就表示在每一次划分的时候,分配到左边小区间的质量比率。例如,在上述例子中,每次1/3的质量划分给左侧区间的话,那么p=1/3。x表示的是该小区间i在t步生成过程中共有多少次被分配到了左侧,这样t-x对应的就是分配在右侧区间的次数。如下图所示,红色的线条就表示分到了左侧,绿色线条分配在右侧。

Multifractalpath.png

因此,在T=5这个层次的小区间中,质量为p^x (1-p)^{t-x}的区间可能不止一个,只要从T=1到T=5的任意一条路径中包含x个向左的分支,t-x个右分支,最终的质量就都一样。事实上,我们可以计算出来具有质量m_i=p^x (1-p)^{t-x}的小区间总共有C_t^{x}个。这样,对于层次t来说,我们得到了两个量:一个是小区间的质量m_i=p^x (1-p)^{t-x},另一个是质量为m的小区间个数,我们记为:

N(m_i)=C_t^{x}

通过将上述两个等式中的x消去,我们不难找到N和mi之间的函数关系,这个函数关系刻画了第t层小区间质量的分布情况。如下图所示,我们画出了不同t对应的N(mi)曲线(不同的曲线对应不同的t):

Nmirelation.png

我们看到,当t逐渐变大的时候,这条曲线会变得越来越尖,这表示有很多小区间具有相同的质量值,而大部分区间质量参差不齐。这种图像不方便我们比较,我们需要想办法把这个尖抹平。一种简单易行的方法就是取对数坐标。然而,对数坐标的底取多少合适呢?我们当然可以设这个底为一个常数e,但是,考虑到无论N还是mi以及小区间的大小都会随着t而呈现指数类型的增长或者衰减。因此,我们可以考虑对数底定为t层次每个小区间的长度大小,即3-t。这样一来,我们便可以得到很规整的图形:

Spectrumcantor.png

在该图中,我们画出了不同t所对应的-\log_{(3^{-t})}(N(m_i))\log_{(3^{-t})}(m_i)的曲线(取负号是因为该数值可以被解释为分形维,详见下一节的讨论。)。我们能看到,随着t逐的增大,曲线不仅仅没有出现高高的尖峰,而且逐渐趋近于一条光滑的闭合曲线。这是因为,随着t的增长,我们的对数之底也会快速地衰减,从而使得这条曲线会逐渐稳定。那么,当t趋于无穷大的时候,这条曲线就构成了康托尔集合上质量分布的多重分形谱。

The children will lead the way! Children are amazing in that they don’t feel sorry for themselves and they always try their best. Anthony is an inpinratsoi. Keep showing us how to be amazing, Anthony!

Hi Arrubr,Hhmminguitd and Chameleon are complementary here, we just went with Chameleon in the demo. From what I’ve noticed, Chameleon is a little faster on the adaptive component generation, while Hummingbird has more options for dealing with primitives. White Feet Modeler is used with Hummingbird (it uses the same code from Excel), but not Chameleon.-Erick

多重分型谱应用举例

康托尔尘多重分形谱的计算

为了验证上述程序的正确性,我们对一维康托尔集多重分形进行了计算。首先,在计算机中生成了一个最高层数为9的康托集(即三分线段9次)。然后将这个一维的质量场输入上述程序中,计算出多重分形谱为:

Numcantormulti.png

我们看到,它与理论计算出的多重分形谱具有相似的形状。

数字图像

接下来,我们介绍A method for detecting objects using Legendre transform文章[1] 中的结果。

该文章对比了自然景观和人造物的数字图像多重分形谱,发现自然景观的谱比人造物的谱更宽。于是,作者提议将数字图像划分成不同的子图像,从而利用每个子图像的多重分形谱的宽度,而找出自然景观背景下的人造物体。

首先,作者指出,不能简单地计算三维空间z轴为灰度轴的多重分形谱,因为结果会对灰度的均值非常敏感。我们应先将数字图像转换成所谓的差分图像,然后再计算多重分形谱。具体地,假设原始图像的尺寸为M*M的,那么我们将图像分割成大小为S,(其中1<S<M/2)的三维盒子区域。如图所示:

Imagegrayscale.jpg


现在我们考虑第(i,j)个三维的柱子,这里一共有M个立方体,有些立方体被灰度曲面占据了,有些立方体没有,我们设l为被灰度曲面占据的最高的立方体的下标,k为最矮的立方体的下标,计算:


n(i,j)=l-k+1

这样,我们就构造了一个地形(或场)n(i,j),然后就可以按照上述方法来计算多重分形谱。下面的图展示了自然物体和人造物体对应二维数字图像的多重分形谱。我们可以看到自然图像的多重分形谱非常宽,而人工物体的谱则窄了很多。

Naturalandartificial.jpg

回想一下,多重分形谱的宽度对应了场中数值的差异性程度。而我们研究的场并非灰度值本身,而是灰度的梯度(即变化率)。因此,自然图像的灰度梯度的差异性较均匀,而人工物体的灰度梯度的差异性分布则比较奇异。这样,我们便可以利用这个多重分形谱的宽度来辨别自然物或者人工物。

进一步,作者开发了一种在自然图像背景下辨识出人工物体的方法。他通过将一个数字图像划分成多个区域,分别对每个区域做出多重分形谱,通过寻找谱的宽度最大的区域来定位物体在哪一个区域。

Identification.jpg

右图的两个图形是作者定义的两种指标以反映子图形区块(X,Y坐标)多重分形谱的宽度。我们看到,人工物体所在的子图对应的宽度会更大。

Bill, good link and important topic. Have you noticed a change in demand and the kinds of video being produced over the last couple years? I know yo&8u#217;ve been in the video biz for many years.Also, let me join the others in saying I’m glad to see you back to blogging.
引用错误:<ref>标签存在,但没有找到<references/>标签

个人工具
名字空间
操作
导航
工具箱