图像分形维数的计盒方法改进

吕泽昆

（华北电力大学（北京）控制与计算机工程学院 北京市 102206）

1 概述

简单的对象可以用理想的形状来描述，如立方体、锥和圆柱体。但是，大多数的自然生物是复杂和不稳定的，不能用简单的整数维度来描述，于是诞生了分形的概念。分形(fractal)学是Mandelbrot于1975 年创立的，分形一词的原意是不规则的、支离破碎的[1]。Mandelbrot 提出了自然界的分形几何，并提出了对复杂而不规则的形状以及这些形状中部分与整体之间自相似性描述，所以分形几何学是一门以非规则几何形态为研究对象的几何学。分形学的提出为自然界中存在的几个明显复杂的结构提供了数学和描述模型。

分形是指一类混乱但其局部与整体却具有相似结构的图案。换言之，分形对象具有“标度不变性”规律。对部分与整体自相似性的度量涉及到分形维数的概念，这是分形学一个重要的概念，它反映了复杂形体占有空间的有效性，它是复杂形体不规则性的量度。日常中不规则形状：云、山和海岸线等无法由传统几何(欧几里得几何)简单定义的。它们往往随放大率的变化而具有显著的不变性。这种自相似性的本质在分形理论中能得到很好的衡量。

在日常的研究过程中，研究对象的信息可以通过多种方法加以记录，从而得到对研究对象的描述。随着近年来图像领域的发展，人们的手机像素越来越高，图像的清晰度越来越高，图像已经成为描述研究对象的一个优秀的载体。随着信息处理技术和计算机技术的发展，无数的图形图像对象可以转化为数字图像。数字图像的本质是存储在计算机中的矩阵。对图像的处理，归根到底是对矩阵的处理。因此我们可以将要研究的对象拍摄为图像，对图像进行操作，方便研究。其中利用分形理论对图像进行研究已经成为一部分重要的内容。

分形理论指出大多数自然物体表面在空间上都是分形的，这为分形模型在图像分析领域的应用提供了理论基础。自分形维数提出至今，它在各个领域都起到了重要的作用。在地理方面，文献[2]利用分形维数对山体遥感图像进行计算，通过计算结果对山体植被的覆盖情况进行评估，并取得良好结果。在植物学的图像方面，文献[3]通过计算植物枝干横截面的分形维数，判断枝干内部是否腐朽。在地质方面，文献[4]利用电镜扫描花岗岩，得到图像并计算其分形维数，揭示出花岗岩在断裂断口处复杂的非线性特性，并做出定量描述。在生物种群研究方面，文献[5]利用分形维数计算兴安落叶松种群的格局分布，并取得良好结果。在图图像学领域，已有学者利用分形的概念提出了图像分割的理论[6]。在图像数据压缩与编码方面，分形理论也展现出优秀的能力[7]。

2 分形维数计算方法

目前已经有许多关于分形维数的计算方法，主要包括Hasdorff方法、尺码法、计盒法等。Hauslorff维数是分形几何理论的基础，但其只适合分形几何的理论推导。对于实际应用中的计算无能为力。

2.1 尺码法

图1：改进后的算法原理示例图

图2：谢尔宾斯基地毯图

利用计盒法进行计算的过程如下：

（1）选用某个固定尺码ri沿着曲线的轮廓（如：海岸线）进行测量，并保证尺码的两个端点始终落在测量曲线的轮廓上。如此测量完全部的曲线，记录总测量次数ni，完成一遍的测量之后，利用测量时的尺码与测量结果数目进行乘积计算出曲线的长度di，即di=ri×ni。

（2）变化测量尺码ri的大小，重复步骤（1），得到多组ni，从而计算出多组di。

（3）对于得到的每组数据对[r1，d1]，[r2，d2]，[r3，d3]…，在双对数坐标中采用最小二乘法原理对数据进行回归分析，计算的直线的斜率即为分形维数的值。

通过对尺码法的流程分析，可以发现尺码法存在以下的弊端。第一，尺码法适合在生活中对分形维数进行粗略的计算，对于特殊的地形或者天空中的云等难以人为接近的对象束手无策。第二，由于每次选定测量尺码时候，会受到人的主观因素的影响，因此，利用该方法进行定量的测量会产生较大的误差。故，尺码法的应用在许多场景中会受到限制。

2.2 计盒法

为了解决尺码法的弊端，研究人员提出了计盒法。近年来，计盒法因为计算方法相对简单，测量误差小且是对研究对象在图像角度进行研究。因此，计盒法是目前计算分形维数时应用最为广泛的方法之一。计盒法计算的分形维数也被称为计盒维数。

目前在分形理论的研究中提出的许多维数的概念都是基于计盒法。利用计盒法进行计算的过程如下：

（1）将彩色图像转化为灰度图像并选择合适的阈值将图像进行二值化操作，得到二值化之后的图像（图像矩阵中仅包含0 和1）。

（2）将上述预处理后的图像矩阵分为盒子边长为 r 的若干个盒子( r=2i， i=1，2，3 … 2i＜d，其中d 为图像长度和宽度的最小值)。

（3）计算不同r 时图像矩阵中包含1(分形图像块)的盒子数目，记作 N(r)，从而得到多组数据对(r, N(r))。

（4）对上述数据对在双对数坐标中进行曲线拟合, 其中lgr～IgN(r)曲线的直线部分的斜率即为所求的计盒维数D。

3 计盒方法的改进

虽然目前计盒法在分形维数计算方面达到了很高的准确度以及很快的速度。但是，对计盒法的计算流程进行编程实现的过程中，我们发现，在进行上述的过程中存在需要优化的部分。优化的思路如为：上述过程中r=2，4，8…。即r 每次的取值为2 的幂次方。如当r=2 时，计算N(r)的值，记为N(2)，当r=4 时，记为N(4)。我们发现，对于r 的每次取值，都需要遍历一次图像矩阵以计算矩阵中包含1 的盒子数目，因此每次的遍历计算过程中都存在大量的重复计算内容，这对于计算图像分形维数是很耗时的操作。尤其在图像分辨率较高，从而图像矩阵较大的情况下，这种耗时现象更加明显。为此本文提出了对于计盒维数计算方法的优化算法，具体过程如下：

（1）将彩色图像转化为灰度图像并选择合适的阈值将图像进行二值化操作，得到二值化之后的图像。

（2）将上述预处理后的图像矩阵分为盒子边长为 r 的若干个盒子( r =2i， i=1，2，3 … 2i＜d，其中d 为图像长度和宽度的最小值)。

（3）当r 取值为2，4，8…时，首先以盒子边长r=2 对图像进行划分，将图像分为若干块，统计此时图像矩阵中包含1(分形图像块)的盒子数目，记作N(2)，记录并保存N(2)。

（4）当盒子边长r=4 时，不再遍历原始图像的矩阵，而是遍历上一步N(2)中的值，从中统计包含1 的盒子数目，记作N(4)，记录并保存N(4)。

（5）当盒子边长继续以2 的幂次方增长时，依次在上一步保存的记录中统计包含1 的盒子数目，而非每次遍历原始图像的矩阵。依次得到多组数据对(r, N(r))。

（6）对上述数据对在双对数坐标中进行曲线拟合, 其中lgr～IgN(r)曲线的直线部分的斜率即为所求的计盒维数D。

上述过程的核心步骤可以用图1 表示。

图1 模拟了一个具有16×16 个像素点的二值图像的矩阵，因为是二值图像，所以矩阵中仅包含0 和1。当盒子边长r=2 时，此时每个盒子的大小为2×2，如绿色圆圈所示，程序统计并保存此时包含1 的盒子个数N(2)。当r=4 时，此时每个盒子的大小为4×4，如蓝色框所示，此时只需要在N(2)的基础上统计并保存包含1 的盒子个数N(4)即可。同理r=8 时，此时每个盒子的大小为8×8，如红色框所示，在N(4)基础上统计并保存包含1 的盒子个数N(8)即可。此时r 已经达到了矩阵长度的1/2，故r 不再继续增长，对得到的3 组数据对进行最小二乘法的模拟，求得分形维数D。

4 试验及结果

对改分形维数的改进进行理论的分析后，通过编写程序进行了验证。本文通过同一张图像对计盒维数程序的优化前后的进行测试。本文采用1024×1024 像素的谢尔宾斯基地毯图进行测试。谢尔宾斯基地毯图是由波兰数学家谢尔宾斯基年提出的，它是自相似集中的一个典型例子，其分形维数的理论值为log(8)/log(3)≈1.893。

在计算准确度方面，用未改进的计盒方法计算其计盒维数的结果为1.892，用改进后的方法计算其计盒维数的结果为1.892，改进前后的计算结果一致且与理论值1.893 之间的误差为0.1%。这表明本文对程序的改进在计算结果的准确度方面与原有方法一致。

在运行时间方面，未改进的计盒方法计算其计盒维数用时0.264秒，利用本文改进后的程序进行计算，用时0.218 秒。计算速度提升了17.42%。

5 结论

本文通过对分形维数的计盒方法进行研究，针对该方法运行时间方面提出了改进方案，并通过实验进行了验证。结果表明，改进后的程序仍能保证计盒维数的计算准确度，且对计算速度有17.42%的提升。这对于计算图像计盒维数方面的研究有重要意义。