豪斯多夫维数及其计算方法详解
豪斯多夫维数及其计算方法详解
豪斯多夫维数是描述分形几何中对象复杂度的重要概念，它可以帮助我们理解自然界中许多看似不规则的形状。本文将从豪斯多夫测度出发，逐步介绍豪斯多夫维数的定义，并通过计盒维数法近似计算豪斯多夫维数。最后，我们将使用Python实现计盒维数法，计算五阶科赫雪花的豪斯多夫维数。
前言
我们先介绍豪斯多夫测度的定义，再导出豪斯多夫维数，然后介绍一种近似求出豪斯多夫维数的方法：计盒维数法，最后通过Python来实现计盒维数法。如果不想看概念和公式，可直接阅读第四部分。
一、豪斯多夫测度
1.1 定义
设$F$为$\mathbb{R}^n$中的任何子集，$s$为一非负数，对任何$\delta > 0$，定义
$$
\mathscr{H}{\delta}^{s}(F) = \inf\Big{ \sum{i = 1}^{\infty} | U_{i} |^{s} : {U_{i}} \text{为 }F \text{的} \delta{-} \text{覆盖} \Big}
$$
于是考察所有直径不超过$\delta$的$F$的覆盖，并试图使这些直径的$s$次幂的和达到最小。当$\delta$减少时，上式中能覆盖$F$的集类是减少的，所以下确界$\mathscr{H}^{s}( F )$随着增加且当$\delta \to 0$时趋于一极限。记
$$
\mathscr{H}^{s}( F )=\lim_{\delta\to0}\mathscr{H}_{\delta}^{s}( F )
$$
对$\mathbb{R}^n$中的任何子集$F$这个极限都存在，但极限值可以是(并且通常是)$0$或$\infty$。我们称$\mathscr{H}^{s}( F )$为$F$的$s-$维豪斯道夫测度。
- inf：表示求下确界
- $|U_i|$：表示集合$U_i$的直径。$U$的直径定义为$|U|=\sup{|x-y|:x,y\in U$，即$U$内任意两点距离的最大值。
- 𝛿- 覆盖：如果$U_i$为可数（或有限）个直径不超过$\delta$的集构成的覆盖$F$的集类，即$F\subset\bigcup_{i=1}^\infty U_i$，且对每一$i$都有$0 < |U_i|\leqslant\delta$，则称${U_i}$为$F$的一个$\delta-$覆盖。
1.2 命题1
若$F\subset\mathbb{R}^n,\lambda>0$，则
$$
\mathscr{H}^{s}(\lambda F)=\lambda^{s}\mathscr{H}^{s}(F)
$$
这里$\lambda F=\left{\lambda x:x\in F\right}$，即$F$按比例放大$\lambda$倍。
1.3 命题2
设$F\subset\mathbb{R}^n, f : F \rightarrow \mathbb{R}^m$为一映射，使得对常数$c > 0$和$\alpha > 0$，有
$$
|f(x)-f(y)|\leqslant c|x-y|^a. (x,y\in F)
$$
则对每一$s$
$$
\mathscr{H}^{s/a}(f(F))\leqslant c^{s/a}\mathscr{H}^{s}(F)
$$
二、豪斯多夫维数
$\mathscr{H}^s(F)$关于$s$的图表明，存在$s$的一个临界点使得$x^s(F)$从$\infty$“跳跃”到 $0$。这个临界值称为$F$的豪斯多夫维数，记为$\dim_{\mathrm{H}}F$。
其用数学语言的描述方法为
$$
\dim_{\mathrm{H}}F=\inf{s:\mathscr{H}^{s}(F)=0}=\sup{s:\mathscr{H}^{s}(F)=\infty}
$$
三、计盒维数
计盒维数或称盒维数(Box-counting or Box dimension)是应用最广泛的维数之一，它的普遍应用主要是由于这种维数的数学计算及经验估计相对容易一些。
3.1 定义
设$F$是$\mathbb{R}^n$上任意非空的有界子集，$N_\delta(F)$是直径最大为$\delta$，且可以覆盖$F$的集的最少个数，则$F$的下、上计盒维数分别定义为
$$
\begin{aligned}
\underline{\dim}{B}F=\underline{\lim}{\delta\to0} \frac{\log N_{\delta}(F)}{-\log\delta}\
\overline{\dim}{B}F=\overline{\lim}{\delta\to0}\frac{\log N_{\delta}(F)}{-\log\delta}
\end{aligned}
$$
如果这两个值相等，则称这共同的值为$F$的计盒维数或盒维数，记为
$$
\dim_{B}F=\lim_{\delta\to0}\frac{\log N_{\delta}(F)}{-\log\delta}
$$
一种常用的覆盖方法是：把一个分形图案放在一个均匀分割的网格上，数一数最小需要几个格子来覆盖这个分形。通过对网格的逐步精化，使格子的边长不断逼近于0，查看所需覆盖数目的变化，从而计算出计盒维数。
3.2 计盒维数与豪斯多夫维数的关系
计盒维数与豪斯多夫维数的关系为
$$
\dim_{\mathrm{H}}F\leq\underline\dim_{B}F\leq\overline\dim_{B}F
$$
一般情况下，我们可以认为计盒维数近似等于豪斯多夫维数。
四、Python实现
我们使用计盒维数法来计算五阶科赫雪花的豪斯多夫维数。
程序如下：
import numpy as np
from PIL import Image
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei'] # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False # 用来正常显示负号
def box(img, threshold=0.1):
# 只能计算2维图像的豪斯道夫维度
assert(len(img.shape) == 2)
def boxcount(Z, k):
S = np.add.reduceat(
np.add.reduceat(Z, np.arange(0, Z.shape[0], k), axis=0),
np.arange(0, Z.shape[1], k), axis=1)
# 我们统计非空（0）的盒子。
return len(np.where((S > 0))[0])
# 将 img 转换为一个二进制数组
img = (img < threshold)
# 图像的短边长度
p = min(img.shape)
# 小于或等于 p 的最大 2 的幂
n = 2**np.floor(np.log(p)/np.log(2))
# 提取指数
n = int(np.log(n)/np.log(2))
# 当网格边长太大时，计算的精度会下降
if n >= 7:
n = 7
# 构建连续的盒子尺寸（从 2**n 递减至 2）
sizes = 2**np.arange(n, 1, -1)
#sizes = np.floor(sizes).astype(int)
# 随着尺寸减小的实际盒计数。
counts = []
for size in sizes:
counts.append(boxcount(img, size))
# 将连续的对数(尺寸)与对数(计数)相拟合。
x = -np.log(sizes)
y = np.log(counts)
hauf, b= np.polyfit(x, y, 1)
# 作对数图
fig, ax = plt.subplots()
ax.set_title('盒计数法')
ax.scatter(x, y,label='data')
plt.plot(x, hauf*x+b, color="green",label='豪斯道夫维数:'+str(round(hauf,3)))
ax.legend()
ax.set_xlabel('log(size)')
ax.set_ylabel('log(N)')
plt.show()
return hauf
img = Image.open("Koch curve_5.png")
img = img.convert("L")
img = np.array(img)/255
box(img)
运行结果：
已知科赫雪花的豪斯多夫维数为
$$
\frac{\ln(4)}{\ln(3)} \approx 1.262
$$
可见我们使用计盒维数法计算得到的结果还是比较精确的。
本文原文来自CSDN博客