文档介绍：图形与图像复杂性的定量描述
范爱民张永斌
摘要本文用分形维数图形与图像的复杂程度进行定量描述,使我们很容易对不同图形和图像的复杂程度进行量化和分析。该算法易于计算机实现,为我们研究图形图像的复杂程度与数字化误差之间的关系提供了一种有效的手段。测绘信息网
关键词分形分形维数(分维) 图形图像
不论是手扶跟踪数字化还是自动扫描数字化,数字化工作底图(图形、图像)的复杂程度将影响其数字化误差的大小。这一观点可以从文献[1]中得到证明。文献[1]给出了一种用曲线的曲折差和曲折率来定量描述地图曲线的复杂性。但实际工作中我们更需要了解图形或图像的复杂程度,以确定图形或图像的复杂性与数字化误差间的关系。有关学者曾提出了确定遥感图像[5]和自然地表[6]分形维数的方法。他们所采用的方法实现起来比较困难,本文提出用一种更易于用计算机实现的方法——网格分形,来确定图形、图像的分维数。
1 从“海岸线的长度”问题开始
《科学》杂志上提出“英国海岸线有多长?”,这个貌似简单的问题,而答案却是海岸线长度不确定[2],要完全精确地确定形状无限复杂的海岸线是办不到的,其长度只能“近似”估算。这一命题充分揭示了自然现象的分维性质,分维(而不是整数维)更能精确地描述与刻划这种复杂性。分形理论与量子力学、相对论和DNA双螺旋结构模型一起被称为20世纪最著名的四大科学概念。在Mandelbrot的开创性工作之后,分形理论以其强大的数学手段和大量的分形应用对普通制图学,特别是分析制图学产生了巨大的影响[5][6]。分形理论是非线性科学研究中十分活跃的一个分支,它的研究对象是自然界和非线性系统中出现的不光滑和不规则的几何形体[3]。而这种不光滑和不规则的程度可以由分形维数来表征。
图形或图像可以说是自然现象的一种映射,它们的不光滑和不规则的程度(复杂性)同样可以用分形维数来表征,下面我们从Minkowski分形入手来讨论图形或图像复杂性的定量描述。
测绘信息网
2 Minkowski分维及其离散形式
Minkowski分形与网格分形
设Rn上的紧致集X,分形基元B为一包含原点内部非空的紧致集;B的相似变换rB={rb∶b∈B},0<r<1;x∈Rn,rBx表示rB的原点平移到点x 上去,即rBx={x+rb∶b∈B}。令

Xr={rBx∶x∈X},(X为索引集)
集类Xr是集合Xr的分裂。当r→0时,
|rBx|=r|B|→0
而Xr→X
所以,Xr是X关于分形基元B的一般分形,而集合X是集类族Xr(r>0)的一般分形极限集。这种分形称为Minkowski分形[2]。
Minkowski分形是一种连续分形。为了便于计算机处理,我们常用离散的网格分形(Minkowski分形的变种)来处理自然景观和图像的分形。网格分形的定义如下[2]:
设Rn上的紧致集X,将X置入Rn上的r网格。令Xr表示与X相交的格子全体,即
Xr={Xrj∶j=1,…,Nr},Xrj是r网格上的一个格子,其中j为索引号;而测绘信息网
Xr=UNr j=1 Xrj
当r→0时,Xr→X
所以,称Xr是X关于r网格的网格分形,而X为Xr的网格分形极限集。
分形维数的确定
对Minkowski分形