分形的尺寸:装箱数，hausdorff，在R ^ n空间中的装箱 [英] Dimensions of fractals: boxing count, hausdorff, packing in R^n space

问题描述

我想计算写为0和1的n维数组的分形维数.它包括装箱数，hausdorff和包装尺寸.

I would like to calculate dimensions of fractal written as a n-dimensional array of 0s and 1s. It includes boxing count, hausdorff and packing dimension.

我只知道如何对装箱计数尺寸进行编码(只需在n维矩阵中计数1，然后使用以下公式即可:

I have only idea how to code boxing count dimensions (just counting 1's in n-dimensional matrix and then use this formula:

boxing_count=-log(v)/log(n);

其中n-number of 1's和n-space dimension (R^n) 此方法模拟对最小分辨率框1 x 1 x ... x 1进行计数，因此其数值类似于limit eps->0.您如何看待这种解决方案?

where n-number of 1's and n-space dimension (R^n) This approach simulate counting minimal resolution boxes 1 x 1 x ... x 1 so numerical it is like limit eps->0. What do you think about this solution?

您对计算hausdorff或装箱尺寸有任何想法(或代码)吗?

Do you have any idea (or maybe code) for calculating hausdorff or packing dimension?

推荐答案

Hausdorff和装箱尺寸是纯粹基于度量理论的数学工具.在这种情况下，它们具有出色的性能，但不适合用于实验.简而言之，没有理由期望您可以基于对某些集合的单个矩阵近似来估计它们的值.

The Hausdorff and packing dimension are purely mathematical tools based in measure theory. They have wonderful properties in that context but are not well suited for experimentation. In short, there is no reason to expect that you can estimate their values based on a single matrix approximation to some set.

盒计数尺寸非常适合于数值研究.具体来说，让N(e)表示覆盖分形集所需的边长e的平方数.如您所知，您的集合的盒子计数维度是e->0 of

Box counting dimension, by contrast, is well suited for numerical investigation. Specifically, let N(e) denote the number of squares of side length e required to cover your fractal set. As you seem to know, the box counting dimension of your set is the limit as e->0 of

log(N(e))/log(1/e)

但是，我不认为仅选择e的最小可用值通常是个好主意.据我了解，物理学文献中的标准解释是假定N(e)和e之间的关系应在很宽的数值范围内保持.计算盒计数维度的标准方法是为e的某些选择计算N(e)，这些选择是从几何趋于零的序列中选择的.然后，我们将一条直线拟合为N(e)对1/e的对数-对数图中的点.盒计数尺寸应大约为该直线的斜率.

However, I don't think that just choosing the smallest available value of e is generally a good idea. The standard interpretation in the physics literature, as I understand it, is to presume that the relationship between N(e) and e should be maintained over a broad range of values. A standard way to compute the box-counting dimension is compute N(e) for some choices of e chosen from a sequence that tends geometrically to zero. We then fit a line to the points in a log-log plot of N(e) versus 1/e The box-counting dimension should be approximately the slope of that line.

作为一个具体示例，以下Python代码生成一个描述分形结构的二进制矩阵.

As a concrete example, the following Python code generates a binary matrix that describes a fractal structure.

import numpy as np

size = 1024
first_row = np.zeros(size, dtype=int)
first_row[int(size/2)-1] = 1
rows = np.zeros((int(size/2),size),dtype=int)
rows[0] = first_row
for i in range(1,int(size/2)):
    rows[i] = (np.roll(rows[i-1],-1) + rows[i-1] + np.roll(rows[i-1],1)) % 2
m = int(np.log(size)/np.log(2))
rows = rows[0:2**(m-1),0:2**m]

我们可以通过简单地将每个1解释为黑色像素，将每个0解释为白色像素来查看分形结构.

We can view the fractal structure by simply interpreting each 1 as a black pixel and each zero as white pixel.

import matplotlib.pyplot as plt
plt.matshow(rows, cmap = plt.cm.binary)

此矩阵可以进行很好的测试，因为它可以证明存在一个实际的限制对象，其分形维数为log(1+sqrt(5))/log(2)或约为1.694，但它的复杂程度足以使盒计数估算有些棘手.

This matrix makes a nice test since it can be shown that there is an actual limiting object whose fractal dimension is log(1+sqrt(5))/log(2) or approximately 1.694, yet it's complicated enough to make the box counting estimate a little tricky.

现在，此矩阵为512行x 1024列；它自然分解为512 x 512的2个矩阵.每个自然分解为256 x 256的4个矩阵，依此类推.对于每个这样的分解，我们需要计算具有至少一个非零值的子矩阵的数量元素.我们可以执行以下分析:

Now, this matrix is 512 rows by 1024 columns; it decomposes naturally into 2 matrices that are 512 by 512. Each of those decomposes naturally into 4 matrices that are 256 by 256, etc. For each such decomposition, we need to count the number of sub matrices that have at least one non-zero element. We can perform this analysis as follows:

cnts = []
for lev in range(m):
    block_size = 2**lev
    cnt = 0
    for j in range(int(size/(2*block_size))):
        for i in range(int(size/block_size)):
            cnt = cnt + rows[j*block_size:(j+1)*block_size, i*block_size:(i+1)*block_size].any()
    cnts.append(cnt)
data = np.array([(2**(m-(k+1)),cnts[k]) for k in range(m)])
data

# Out:
# array([[  512, 45568],
#       [  256, 22784],
#       [  128,  7040],
#       [   64,  2176],
#       [   32,   672],
#       [   16,   208],
#       [    8,    64],
#       [    4,    20],
#       [    2,     6],
#       [    1,     2]])

现在，您的想法是简单地计算log(45568)/log(512)或大约1.7195，这还不错.我建议我们检查这些数据的对数-对数图.

Now, your idea is to simply compute log(45568)/log(512) or approximately 1.7195, which is not too bad. I'm recommending that we examine a log-log plot of this data.

xs = np.log(data[:,0])
ys = np.log(data[:,1])
plt.plot(xs,ys, 'o')

这的确确实接近线性，表明我们可能希望我们的盒算技术可以正常工作.首先，尽管如此，排除似乎离群的那一点可能是合理的.实际上，这是此方法的理想特性之一.这样做的方法如下:

This indeed looks close to linear, indicating that we might expect our box-counting technique to work reasonably well. First, though, it might be reasonable to exclude the one point that appears to be an outlier. In fact, that's one of the desirable characteristics of this approach. Here's how to do so:

plt.plot(xs,ys, 'o')
xs = xs[1:]
ys = ys[1:]
A = np.vstack([xs, np.ones(len(xs))]).T
m,b = np.linalg.lstsq(A, ys)[0]
def line(x): return m*x+b
ys = line(xs)
plt.plot(xs,ys)
m

# Out: 1.6902585379630133

嗯，结果看起来还不错.特别是，这是一个明确的例子，与仅使用一个数据点的简单想法相比，此方法 可以更好地工作.公平地说，不难发现简单方法效果更好的示例.而且，此集合足够有规律，我们可以得到一些不错的结果.通常，不能真正期望盒数计算过于可靠.

Well, the result looks pretty good. In particular, this is a definitive example that this approach can work better than the simple idea of using just one data point. In fairness, though, it's not hard to find examples where the simple approach works better. Also, this set is regular enough that we get some nice results. Generally, one can't really expect box-counting computations to be too reliable.

这篇关于分形的尺寸:装箱数，hausdorff，在R ^ n空间中的装箱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！