图像分形维数计算方法的比较

计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2010 年 第20卷 第 3 期

图像分形维数计算方法的比较①

赵海英1,2，杨光俊3，徐正光1

12

(北京科技大学 信息工程学院，北京 100083) (新疆师范大学 数理信息学院，乌鲁木齐 830054) 3

(云南大学，昆明 650091)

摘 要：分形维数是度量图像纹理粗糙度的一种常用方法，而依据分形维数的定义很难求解图像的分形维数。大量计算图像分形维数的算法被提出，但是这些方法往往基于不同的应用背景，没有总体比较和评价，多局限于差分盒子维的选用和改进，算法普遍存在计算误差较大，适应能力模糊的缺点。基于目前常用图像分形维数的计算方法，测试不同方法对图像粗糙度的敏感程度和时间复杂程度。从而对这些方法的适用范围进行分析和比较，给出应用的推荐模型。

关键词：分形维数(分数维) ；盒子维(数盒子) ；敏感性；纹理粗糙度

Comparison of Calculation Methods-Based Image Fractal Dimension

ZHAO Hai-Ying1,2, YANG Guang-Jun3, XU Zheng-Guang1

12

(School of Information Engineering, University of Science and Technology Beijing, Beijing 100190, China) (College of Math-physics and Information Sciences; Xinjiang Normal University, Urumqi 830054, China) 3

(Yunnan University, Kunming 650091, China)

Abstract: Fractal dimension is a commonly used method to measure texture coarseness. However, the definition of fractal dimension is very difficult to resolve. Many fractal dimension algorithms of image are proposed based on different application backgrounds. But they lack comparison and evaluation of the overall and are only limited to the selection of the box-counting dimension method. This paper makes a testing among these methods in sensitivity and time complexity for texture coarseness of image. Through a comparison and analysis to applicability of these methods, the recommended models are given at last.

Keywords: fractal dimension(FD); box counting dimension (Counting box); sensitivity; texture coarseness

纹理粗糙度是图像的重要视觉特征，对图像的分析、识别和解释有着重要的意义。人们在纹理分析方面作了大量的研究工作，提出了许多纹理粗糙度的测量和描述方法。文献[1]指出大多数自然物体表面在空间上都是分形的，而且这些表面的灰度图像也是分形的，这为分形模型在图像分析领域的应用提供了理论基础。而纹理粗糙度的描述大多采用分形维数法[1]。分形维数是图像稳定性的表示量，可以用来描述图像表面的粗糙程度。但是依据分形维数的理论定义，很 ① 基金项目:国家自然科学基金:(60863010);973前期计划专项课题(2010CB334709);新疆自然科学基金(2010211a19)

收稿时间:2010-05-31;收到修改稿时间:2010-07-06

难求图像的分形维数，为此，大量图像分形维数的计算方法被提出，目前在各种学科领域中应用比较多的方法是：基于灰度差值法[2]、基于分形布朗运动自相似模型的方法[3]、基于差分盒子维法[4]、基于多尺度的分数维法[5]、地毯覆盖法[6]。以上各方法分别基于不同的应用背景提出，没有进行总体比较和评价。更重要的是一幅图像的分形维数值介于2.0-3.5之间，其差别较小，如果分形维数的估算方法精度不够，其分形维数的计算就会有偏差，因此，后来大量的改进分形维

238 专论·综述Special Issue

2010 年 第20卷 第 3 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用

数的计算方法被提出，而盒子维以简单易实现受到人们的青睐，大多改进算法也都是对盒子维的改进。本文目的不是改进图像分形维数的计算方法，而是基于同一组图像(100幅) ，对常用的五种分形维数计算方法进行实验比较，给出各种方法的适用范围和精度范围，并提供有价值的结论和应用参考模型。

1 相关工作

分形维数可以作为度量图像纹理粗糙度的一种度量指标，且保持了与人类视觉感知的一致性，受到广泛应用[2]，但由于分形维数计算方法的差别，人们提出了许多的改进算法，主要是限于盒子维算法的改进，原因是盒子维算法虽然精度不高，适用范围也较小但简单易于实现。盒子维实质是“数盒子”算法，即通过划分图像形成网格，统计出网格中包含的盒子数。其关键在于如何统计盒子的个数，形成了不同的改进的“数盒子”算法。文献[7]指出图像盒子维的计算模型使用固定大小的立方体覆盖分形表面的缺陷。在不违反盒子维定义的前提下, 提出一种使用可变大小长方体取代固定大小立方体盒子维计算方法。实验表明, 这种方法有助于提高盒子维法的计算精度。文献[8]针对差分盒子维法计算精度不高和计算量大等问题，基于动态规划和残差分析的思想，提出了改进的差分盒子维计算方法。文献[9]在分析传统“盒子维”算法测量分形维数缺陷的基础上, 首先通过引入一个新的参数来克服传统算法的局限性，进而提高测量精度。文献[10]针对传统的盒子维算法是基于栅格的方法，其存在图像放大后失真、过程繁琐和迭代次数有限而精度不高等缺陷，提出一种以矢量为载体的矢量盒子维法，实践表明矢量盒子维法具有较高准确性和优越性。

综上所述，大多算法旨在改进分形维数的算法和分形理论的应用推广，没有对各类算法进行统一的比较和分析。

2 五种实验算法及有关计算

本实验采用的算法及编号如下表1所示：

算法简称

程序名称

编号

分形维数FD

差分灰度法FD_differgray 分形布朗运动自相似模型FD_brownmove

差分盒子维法FD_differboxcount多尺度分数维法FD_wavedivider 地毯覆盖法FD_carpetoverlay

2.1 差分灰度维

把盒子维方法在二维平面中进行推广，就是差分灰度法。其原理是把平面的分割方格应用到小立方体得到的。令N(r)表示边长为r ×r ×r 的包含所要估计的图像区域的最少灰度级个数，在这里可以把灰值图像想象成一个在三维空间中的分形曲面。所要估计的图像区域的分形维数D 将由下式决定：

N (r )∗r D =c (1) 其中C 为常数，两边同取对数有：

log N (r )=−D log r +log c (2) 再用线性回归等求出log N (r )相对于log r 的斜率，也就是该图像区域的分形维数——差分灰度维D 。 2.2 分形布朗随机场模型法

对于二维灰度值图像,f(x)是关于像元点X 灰度等级的实值随机函数, 若存在自相似函数H(0

,

F (t )=P +∆x )−f (x ))/∆x H

r ((f (x )

式中f(X)称为分形布朗函数, 则分形维数D 可表示为D =3−H , 其中对分布函数F (t ), 假设满足均值

为零的正态分布N (0, σ2)时, 可得:

F (t )=

∫t

−∞(

1

πσ

)⋅es 2/2σds

(4) 由此, 定义(3)式可写成 E [f (x +∆x )−f (x ]⋅

∆x

h

=c

(5)

式中E 为期望值，C 为常数。由上式两边取对数可据最小二乘法可求出H ，便可求得D 。 2.3 差分盒子维法

将M ×M 大小的图像分割成S ×S 的子块（M/2≥s ＞1,s 为整数），令r =s 。将图像想象成三

维空间中的曲面，x,y 表示平面位置，z 轴表示灰度值。xy 平面被分割成许多ss 的网格。在每个网格上，是一

列s ×s ×s 的盒子。

设图像灰度在第(i , j )网格中的最小值和最大值分别落在第k 和第l 个盒子中，则：

n r (i , j )=l −k +1是覆盖第(i , j )网格中的图像所需的盒子数，而覆盖整个图像所需的盒子数为N r 而N r =∑n r (i , j ) ,

分形维数：D =lim (

log (N r )/log ()) (6)

针对不同的r ，计算N r ，应用最小二乘法，即可求得分形维数D 。

2.4 多尺度分数维法

设一幅M×N的图像, 其中M =2n , N =2n 对其进

行一次小波变换，得到一幅低频近似图像A r

和3幅高频细节图像D 1f , D 2f , D 3f , 图像大小均为2n −1×2n −1。令M 1=2n −1, N 1=2n −1。对四幅图像求

Special Issue 专论·综述 239

计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2010 年 第20卷 第 3 期

取差分盒子维数。 2.5 地毯覆盖法

把灰度图像想象成一个在三维空间中的分形曲面。所上式中, A (r )为分形曲面的表面积,r 为度量时所使用的面积尺度，D 为曲面的分形维数,F 是一常数。曲面的表面积A (r )的求法如下：

把三维空间中的所有距离曲面表面为r 的点, 用厚度为2r 的毯子覆盖，覆盖曲面上表面u r 和下表面b r ，定义为:

u

0(i , j )=

归一化处理。选取100幅图像中的8幅384pixel*256pixel(图3) ，分别求取分形维数，实验结

果如(表4) 。机型：pentium-366。 要估计的图像区域的分形维数D 将由下面的公式确定:

b 0(i , j )=g (i , j ) (7)

u r (i . j )=max ⎧⎨u r −1(i , j )+1,

⎩

(8) max u r −1(m , n )}⎫⎬(m , n )−(i , j )≤1

⎭

b r (i , j )=min ⎧⎨b r −1(i . j )+1,

⎩

(9) {b r −1(m , n )}⎫⎬(m , n )−(i , j )≤1

min

⎭

图1 各种算法的分形维数值

r

该毯子的体积为: 曲面的表面积为:

v r =

∑(u (i . j )−

i , j

b r (i , j ))

(10)

A (r )=

v

r

−v 2

r −1

(11)

对(10)式进行最小二乘拟合，即可求得图像块的维数D 。

3 五种算法的实验结果

本实验的图像是由100多幅含不同内容的图像集组成，其中有森林、草坪、树木、鸟，马、房屋、海水等风景图像，甚至有十多幅不同的人脸图像。图像大小一般为(256～384)×256，实验先对图像进行大小

图

2 各种算法相对于纹理粗糙程度的敏感性的比例

关系

240 专论·综述Special Issue

2010 年 第20卷 第 3 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用

平均时间较秒秒

2.2817 2.2907 5分31秒

9秒 4秒 4秒 4秒 4秒

图3 相对表3的选取的图像

4 实验结果分析和讨论

4.1 各图表内容及坐标的说明

图1，横坐标的10个距离表示2.0至3.0之间的分形维数，每个距离间隔表示0.1；而纵坐标表示的是五种算法在这个区间的出现的概率密度。图2，横坐标是五种算法，纵坐标是五种算法在这3个分形维数范围的分布概率。分析图2可知，盒子维法的适用范围较窄，而且它对粗糙度小的图像较敏感；布朗运动自相似法的适用范围比较宽，对粗糙纹理的敏感性也较强。

4.2 实验结果分析

从实验结果可以看出：

(1) 在图1、图2、表3中，各种算法对纹理粗糙度的敏感性是不同的。相比而言，地毯覆盖法和分形布朗运动自相似模型的估计方法在粗糙度小时其变化平缓，在高粗糙度的情况下的变化比较剧烈，而差分盒子维法对粗糙度小的纹理敏感，粗糙度小时其变化更剧烈。

(2) 在表4和图3中，可以看出，在视觉上感到粗糙度大的，使用上述算法可以非常好地识别出来。但对于低粗糙度的分辨有一定的出入。

(3) 在表2和图2中，还可看出，多尺度分数维法对于小波分解后的图像其分形维数值有一定的差距。

而且对纹理的辨析能力非常有限。

(4) 各种算法均较好地使用FD 反映出纹理的粗糙程度，计算的结果比较满意。在算法的适用范围上，地毯覆盖法和多尺度分数维法是最大的。而其它算法的适用范围并不覆盖整个分形维数的动态范围。

(5) 更值的一提的是借助多尺度理论空间可知多尺度分形维数的度量方法是一种较具应用价值的方法。 4.3 讨论

在许多应用中，如特征提取、分类等，人眼对纹理粗糙度的分辨能力是有限的，换言之，对某些低粗糙度的小变化无法觉察。如何适应这个视觉特性，首先想到的计算图像的分形维数实现对纹理粗糙度的度量。从实验结果很明显看出，所提各种算法对估算高粗糙度纹理的分形维数是很接近的，应用效果也会好 的。再有，就是小波分解的四个分量图像，由于数据信息量的减少，所以计算速度是最快的一种算法，但分形维数有很大的出入，原因可能就是分解后，失出了一部分信息，就不能从综合的角度来评价，但如果是应用在某一个分量方向还是可以的，同时也说明其改进可以借助多尺度理论的度量来减少分形维数的偏差，因为其速度是五种算法中最快的。

(下转第246页)

Special Issue 专论·综述 241

计 算 机 系 统 应 用 http://www.c-s-a.org.cn 2010 年 第20卷 第 3 期

信息管理等系统中；基于本体的知识表示方法将广泛应用于知识库系统、决策支持系统、人工智能系统等系统中。

4.2 构建指标框架的意义

通过构建指标框架，明确各种知识表示方法的优缺点；选择一种或多种知识表示方法更加有效的解决实际问题；帮助构建和评估知识表示方法比较的规范；在旧的知识表示方法的基础上创造新的更符合框架指标的知识表示方法。 4.3 知识表示方法的发展趋势

随着计算机技术的发展, 智能系统理论的不断进步, 将会涌现出更多的适合特定领域的知识表示方法，如基于本体的表示方法，基于云理论的知识表示等。随着知识表示方法不断被普通用户接受和使用，满足用户的个性化需求将是知识表示方法发展的客观要求，即更加灵活的把抽象的概念更形象、更快捷、更方便的通过计算机展现出来。此外，知识表示、知识获取、知识应用三个方面将互相进步、互相促进发展。 (上接第241页)

4.4 建议和意见

在实际解决问题的过程中，智能系统中往往不是单一的采用一种知识表示方法，而是选择多种适合特定领域知识的表示方法，互相弥补不足，发挥各自优势。即使针对同一类的问题，由于不同的目的、不同的应用，采用的表示方法也不一样。所以我们在选择表示方法之前，必须通过严密的需求分析，选择合适的一种或多种知识表示方法，来满足求解和描述问题。

智能系统中，关于各种知识方法比较和评价标准的研究还比较少，多做这方面的理论或实际研究，将有助于知识表示方法的发展和创造出更合适的知识表示法。

参考文献

1 蒋云良. 知识表示综述. 湖州师专学报,1995,(5):18－22. 2 徐宝祥, 叶培华. 知识表示的方法研究. 情报科学,2007, 25(3):690－694.

3 张攀, 王波. 专家系统中多种知识表示方法的集成应用. 微型电脑应用,2004,20(6):4－6.

4 谢和平, 等. 分形几何. 重庆:重庆大学出版社,1992. 5 赵莹, 高隽, 陈果, 冯文刚. 一种基于分形理论的多尺度纹理特征提取方法. 仪器仪表学报,2008,4(29):177－781. 6 Sarkar N, Chaudhuri BB. An Efficient Approach to Estimate Fractal Dimension of Textural Images. Pattern Recognition, 1992,25(9):1035－1041.

7 于子凡, 杜贵君, 林宗坚. 图像盒子维数特征计算方法改进. 测绘科学,2006,1(31):87－89.

8 张涛, 孙林, 黄爱民. 图像分形维数的差分盒方法的改进研究,2007,5(13):55－57.

9 梁东方, 李玉梁, 江春波. 测量分维的“数盒子”算法研究. 中国图象图形学报,2002,5(3):246－250.

10 韩杰, 陆桂华. 测量分维的矢量计盒算法研究. 中国图象图形学报,2008,3(13):525－530.

5 小结

总的来说，分形布朗运动模型法精确性好，可测分形维数适用范围宽，但地毯覆盖法计算量大，尤其用8邻域来覆盖，运算时间过长。盒子维和多尺度分数维法计算时间适中，但当图像的分数维很高时会低估图像的FD ，因而有一定的使用限制。结合适用范围和计算量及准确度三方面来考虑，布朗运动模型和盒子维法较好。

参考文献

1 Pentland P. Fractal-based description of natural scenes. IEEE Transactions on Pattern analysis and Machine Intelligence, 1984,6(6):661－674.

2 杨光俊. 分形的数学(上, 下). 昆明:云南大学出版社,2002.76－189.272－301.

3 Mandelbrot BB, Van Ness J. Fractional Brownian motion. fractional noise and applications. SIAM Review, vol. 10, 1968.

246 专论·综述Special Issue