2.2.2 分形压缩编码的数学基础_人脸图像信息处理与识别技术-QQ阅读男生科幻网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.2 分形图像编码的基本理论

分形的概念来自于数学学科——分形几何学[2.18b]。众所周知，欧几里得几何学研究的图形都是规则的形状，如圆、正方形、球和软体等。构成这些图形的边缘，都是连续而光滑的。根据欧几里得几何，可以方便地描述砖块、轮子、机器部件以及建筑物等。但是，大自然上的海岸线不是圆弧，山脉不是锥体，这些不规则的几何形状也经常出现在自然科学的各个领域中，如流体力学中的湍流、物理学中的布朗运动、非线性动力学中的奇异吸引子及工程技术中的信号处理等。为了研究这些大自然的几何学，就诞生了一门新的分支——分形几何学。

分形几何学是由B. B. Mandelbrot在20世纪70年代创立的。分形（Fractal）一词，也是由Mandelbrot提出的，它来源于拉丁语“fractus”，含有“不规则”和“破碎”的意义。

大自然中的所有形状和人们考虑的一切图形可以分为两大类：一类是具有特征尺度的，如人的身高，球的半径，建筑物的长、宽、高等；另一类是没有特征尺度的，即必须同时考虑从大到小的许许多多尺度，如夏季天空中翻滚的雨云、北方冬季玻璃窗上的冰霜，这些所谓“无标度”的几何体，其实就是分形。它们具有共同的特性，即自相似性，这也是可以将分形原理运用到图像压缩中的地方。

Mandelbrot[2.20]曾经指出，分形具有三个要素：形状（Form），机遇（Chance），维数（Dimension）。首先，分形的形状是支离破碎、参差不齐的不规则形状；其次，大自然中的海岸线与用以描述它的科克分形曲线之间仍有很大不同，这种差异是由于海岸线受到自然界随机因素的作用而产生的。Barnsley发现，可以对一组给定的规则通过随机迭代而得到分形。对象本身并不依赖随机性，总是以100%的概率得到同一个分形。因此随机性或者机遇仅仅是工具，而结果却是确定性的；第三，分形的维数可以是分数，这是一种新的维数，称为分维。维数是几何对象的一个重要特征量，通常的维数是整数。由于这种定义具有对几何对象在同胚变换下的不变性，因此称为拓扑维。维数研究的突破点是Mandelbrot把一类集合（其维数可以为分数）应用到大自然科学现象的模型中去。

分形几何学仅有简短的历史，以至于迄今为止还没有完善的定义，但这并没有影响它在众多领域里的广泛应用。事实上它已经成为具有广泛应用前景的一门新兴学科。现在分形几何学已被应用于图像分割、分析、综合等图像处理方面。1988年，Barnsley首次提出了利用分形技术进行图像压缩的方法[2.2]，后来他的学生Jacquin又提出了一种自动分形图像压缩方法[2.18]，此后出现了各种类型的分形图像压缩方法。

2.2.1 分形压缩编码的基本概念

分形图像压缩是利用图像的自相似性来进行压缩的一种方法。自相似性（Self-Similarity）是指无论几何尺度怎样变化，景物中任何一小部分的形状都与较大部分的形状相似（如图2.1所示）。

图2.1 自相似分形图像

从数据压缩的观点来看，这种自相似性就是一种信息冗余，因而可用于图像压缩。这种方法的实质是在不同的尺寸、比例上发现自相似部分，去除重复描述。通过对图像进行系统分析，提取出一套代码（这种代码可用来精确地重建图像）来进行存储和传输，从而实现图像压缩。分形图像压缩方法大体可分为两类：一类是分形模型图像压缩编码，即预先对某一类景物建立分形模型；另一类是迭代函数系统（Iterated Function Systems, IFS）分形图像压缩编码，即利用迭代得到原始图像的一个分形近似来实现图像压缩。后一类方法不仅易于实现，而且应用也较为广泛。

2.2.2 分形压缩编码的数学基础

分形图像编码技术有着较为繁杂、深奥的数学基础，包括基本集合论、度量空间、仿射变换、压缩映射定理、拼贴定理等。由于篇幅所限，在这里不可能对其理论体系做详细的讨论，下面只对其主要内容做简单的回顾。

集合是由一些确定的个体对象组成的一个整体，记为M。这些对象是人们感觉到的或想象到的。用来形成集合的对象称为该集合的元素。通常用大写字母表示集合，小写字母表示元素。表示集合有两种方法：列举法和描述法。集合之间可以进行代数运算。

定义2.1 设X是一个空间或一个集合。d:X×X→R是X×X到R的函数。若d满足：

①d（x, y）≥0，d（x, y）=0当且仅当x=y。

②d（x, y）=d（y, x），对所有x,y∈X（对称性）。

③d（x, y） +d（y, z）≥d（x, z），对所有x,y,z∈X（三角不等式）。

则称d为X的度量，有时又称为距离函数，在逼近论中又称为失真测度；（X,d）是带度量空间。

度量空间中有三个非常重要的概念：完备的、紧集和Borel集，下面分别进行介绍。

1.完备的

若X中每一个柯西序列，都有一个极限x∈X，则称该度量空间（X,d）是完备的。

若S是一个完备度量空间（X,d）的子集，则（S,d）是一个度量空间，当且仅当S在X中是闭的，（S,d）才是完备的，否则，（S,d）是不完备的。

2.紧集

一个集合S是紧集，若覆盖S（包含S）的任何一开集都有一个覆盖S的有限子覆盖。

紧性是一种能把条件的无限集化成多个有限的集，就讨论的对象来说，Rn中的紧子集，既是有界又是闭的。

3.Borel集

凡属于可以从开集出发，通过有限次运算，取其余集，或者取有限个或可数个集合的并集或交集得到的集合，统称为Borel集或Borel可测集。

仿射变换是空间直角坐标变换的一种，它是一种二维坐标到二维坐标之间的线性变换，保持二维图形的“平直线”和“平行性”，可以通过一系列的原子变换的复合来实现，包括平移（Translation）、缩放（Scale）、翻转（Flip）、旋转（Rotation）和剪切（Shear）。

仿射变换可以在n维空间中进行，由于要讨论的是图像目标，以二维空间为例，即讨论欧几里得平面上的仿射变换。

一个变换W∶R2→R2，具有如下形式：W(x, y)=(ax +by +e,cx +dy +f )，其中，a、b、c、d、e、f 为实数，则该变换称为二维仿射变换。

上式也可写成矩阵形式，即

其中，；；。

二维仿射变换可以把二维空间中的一点映射为另一点，把二维空间中的一部分映射为另一部分。

仿射变换W 具备尺度、对折、平移、旋转、翻转等特性，这些特性是由参数a、b、c、d、e、f 决定的。

在分形图像编码中，因为每个像素点有灰度值的概念，经常用到三维仿射变换，相当于除了像素点的(x,y) 坐标外，再加上一维灰度坐标。实际采用的重新组合形式为

此仿射变换可看成是(x,y)平面上二维仿射变换与z方向上线性逼近的组合。

首先介绍一下压缩映射的定义。

定义2.2 若存在一常数0≤s＜1使d(f(x),f(y))≤sd(x,y),∀x,y∈X，则称度量空间（X, d）的变换f :X→X为压缩变换或压缩映射。数s称为f的压缩因子。

压缩映射在几何上说明点x和y经过映射后，f有且只有一个不动点（即f(x)=x有且只有一个解）。

证明略。

定理2.1 （不完备度量空间的压缩定理）

设X为一个度量空间，令f为X中的压缩变换。令ε＞0，为簇半径ε的非漫游点，则

（1）闭球B(,2ε)是f的一个吸引集。

（2）任何有限个闭球的交∩B(,2ε)都是变换的吸引集。

证明略。

定理2.1说明对X中的压缩变换f，对任何ε＞0存在形如B(,2ε)的闭吸引球。在反复进行f变换时，X中每一个点都被吸引到该吸引集中。

压缩映射定理在数学分析、微分方程、代数方程的解的存在性与唯一性的证明中起着重要作用。它也是图像压缩分形理论的关键定理。作为图像压缩的分形方法，迭代函数系统（Iterated Function Systems, IFS）和迭代变换理论（Iterated Transform Theory, ITT）编码都注重解决这个问题。设法把一个迭代序列约束在X中，其极限点逼近一个给定的原始点或目标对象xt，或者经过几次迭代就聚集在对象xt附近。只要可以定义函数att，这个编码问题就是在att下寻找xt的近似求逆。

定理2.2 （完备度量空间的拼贴定理）

设（X,d）为一个完备度量空间，xt∈X，f∈F是一个压缩因子为s（0≤s＜1），吸引子为att（f）的变换。

令ε＞0，若d(xt,f(xt))≤ ε，则。

证明略。

该定理有两个直接的推论。

推论2.1f是压缩变换（0≤s＜1），使f(xt)为xt的(1-s)ε近似点，则att（f ）是xt的一个近似点。

推论2.2 若s趋近于1，则对象xt与吸引子att（f ）的误差边界变得很大。

这个拼贴定理是由Barnsley首先提出的，把R2中的非空紧子集空间称为Haus dorff度量空间(H(X),dH)，压缩变换是由具有如下形式的有限个压缩的仿射变换构成的，即

其中，Wt是从R2→R2的压缩仿射变换。

寻找变换W，使W（xt）逼近xt自身的仿射变换的复制物拼起来覆盖xt或拼贴成xt，所以把f(xt)称为xt的拼贴。

对于非完备度量空间的拼贴定理，其基本特点是把整个对象空间X“拖进”一个包含xt的半径为ε/2的小球中。

总之，变换f是一个重构xt的ε近似物的程序，它对初始条件不敏感。最重要的是要使f的复杂性比xt低，否则编码就失去了意义。

2.2.3 迭代函数系统理论

由于研究的对象不同，迭代函数系统（IFS）可以分为确定性IFS和随机性IFS。确定性IFS在压缩黑白图像时可以得到较大的压缩比，而随机性IFS对灰度图像进行分形压缩的效果比较好。下面将一一介绍。

1.黑白图像的迭代函数系统

分形图像压缩所需要研究的空间都是完备的度量空间（X,d）上的非空紧子集表示的空间，用H（X）表示。讨论在R2上的黑白图像子集时，用度量空间H（R2）（欧几里得距离）是很方便的。

可以证明：非空紧子集H（X）及其Hausdorff度量h(d)所构成的Hausdorff空间（H,h）也是完备的度量空间。在X空间中，W :X→X是压缩因子为s的压缩变换；在Hausdorff空间中，W：H→H是压缩因子为s的压缩变换。

在Hausdorff空间中，多个压缩变换的并也是一个压缩变换，其压缩因子是其中最大的一个。

定理2.3 （IFS压缩映射定理）

设{X,Wn,n=1,2,…,N}为一个压缩因子为s的迭代函数系统，则由下式定义的变换：

是完备度量空间[H（X）,h (d)]上的一个压缩变换，其压缩因子为s，即

h (W(B),W(C))≤s·h(B,C) ∀B ,C⊂H（X）

它有一个唯一的不动点集A⊂H（X），且，并对任何B⊂H（X）,A=，有二维空间R2的IFS：

{R2;W1,W2,…,Wn},Wi(X)=Ai+Ti i=1,2,…,N

其中，；。

按照IFS吸引子的测度理论，可以对每个变换Wi分配一个概率Pi。在采用随机迭代算法或灰度复印机算法计算IFS吸引子的图像时，Pi是起作用的。在与随机迭代算法一起使用时，其值可取为

若detAi=0，则可赋予很小的数值如0.001，其余情况可根据经验处理。Wi 中ai、bi、ci、di、ei、fi及Pi的值称为IFS码（有时Pi不必给出，可以直接利用上式求出）。利用随机迭代算法不难算出IFS的吸引子。

定理2.2保证了变换的收敛性，若在压缩因子不变时对Wi的系数略加改动，Wi（T）的变化不大，吸引子A的变化也不大，就是说参数的微小变动通常只引起吸引子的微小变化。所以，可以适当调整变换的参量来连续控制IFS吸引子，也就是找出目标图像的IFS码，这就是图像的IFS压缩。码稳定性理论说明，只要压缩因子s不是接近于1，IFS码就是稳定的。

2.灰度图像的迭代函数系统方法

前面介绍的确定性迭代函数系统只适用于二值（黑白）图像的压缩。可是，通常图像都是彩色的。根据三原色原理，可以把彩色图像分解为三个不同颜色属性的灰度图像，只要找到了灰度图像的压缩方法，就能压缩彩色图像。

随机性迭代函数系统则适用于灰度图像压缩。在随机性迭代函数系统IFS（W1, …,WN;p1, …,pN）中，对每个仿射变换Wi都分配了一个概率pi。先在度量空间（X,d）上构造Borel测度空间P（X）中导出一个马尔可夫（Markov）算子。若X为紧空间，P（X）中采用Hutchinson度量dH，则马尔可夫算子可以是度量空间（P（X）, dH）的一个压缩变换，它有一个唯一的不动点μ（又称为不动测度μ）。

（1）基本数学概念

研究分形必须熟悉测度的基本概念，并理解它所表示的物理含义。测度论是把现实世界的对象（围线、纹理、图像）模化为测度的数学对象。测度概念在R上是长度概念的推广，在R2上是面积概念的推广。一个在Rn的子集上的测度，可简单地归结为一个集合的一种数值的“体积”，若一个集合以某种方式分解为有限个或可数的多块，则整体的“体积”是这些小块“体积”之和。

定义2.3 对Rn的每一个子集，若μ都赋予一个非负的实数或∞，使

①μ(φ)=0；

②μ（A）≤μ（B），若A⊂B；

③ 若A1,A2, …是可数的（或有限的）集序列，则有

则称μ是Rn上的测度。这里要用到下面要介绍的Borel集和Borel测度。

前面讲过，凡属于可以从开集出发，取其余集，取有限个或可数个集合的并集或交集而得到的集合，统称为Borel集或Borel可测集，记作B。在度量空间（X,d）的Borel集上定义的测度μ的支持集是使μ（Rn\X）=0 （A\B=）的最小闭集X。测度的支持集总是闭集。

有时可以用物理的观点来理解测度，把它看成是质量。若Rn的一个有界子集上的测度μ满足0＜μ（Rn）＜∞，则称它是一个质量分布，并称μ（A）为集合的质量。直观来看，把一个有限质量以某种方式散布在一个集合X上便得到X上的一个质量分布，这种分布是满足测度条件的。

（2）随机的迭代函数系统随机的迭代函数系统是一组IFS{X;W1,…,WN}和一组有序数{P1,…,PN}组成，其中,Pi＞0，概率Pi与相应的仿射变换Wi相对应。令μ为R2上的一个Borel测度，若μ（·）=1，则称μ是归一化的。令P表示R2上归一化的Borel测度的一个集合，又称为归一化Borel测度空间，P上的Hutchison度量定义为

dH(μ,ν )=sup{∫fdμ-∫fdν: f :平面是连续的，且服从f(x)-f(y)≤ d(x,y),∀x,y∈平面，∀μ,ν∈P }

并且（P, dH）是一紧的完备的度量空间。

令IFS{X :μ0，W1,…,WN；P1,…,PN}是随机的迭代函数系统，则该系统的马尔可夫算子是由下式定义的函数M：P→P：

若M :P→P为随机迭代函数系统的马尔可夫算子，则由Hutchison定理可知，存在唯一的测度μ∈P，使M(μ)=μ。所以，若ν∈P，则

也就是说，对P上的Hutchison度量，马尔可夫算子是收敛的。

令μ表示马尔可夫算子由Hutchison定理确定的不动点，则μ称为随机的迭代函数系统的不变的测度。

由以上讨论可以引出以下定理。

定理2.4 设IFS{X :μ0，W1,…,WN；P1,…,PN}是随机的迭代函数系统，令μ为相应的不变测度，则μ的支持是IFS{X :W1,…,WN}的吸引子。

证明略。

综上所述，与完备度量空间(X,d)的决定性迭代函数系统IFS{X：W1,…,WN}一样，随机迭代函数系统IFS{X :μ0，W1,…,WN；P1,…,PN}在其Borel测度空间P中，（P,dH）是完备的度量空间。该度量空间上的马尔可夫算子M是一个压缩变换，压缩因子为0≤s＜1，它在P中存在一个唯一的不变测度μ，M(μ)=μ（Hutchison定理）。它说明当压缩因子比1小得多时，不动测度与某测度之间的误差，跟该测度与其通过M变换之间的误差相近。

Elton定理已经证明，只要通过多次迭代，便可以从随机的迭代函数系统中重现数字化图像。所以，与确定性IFS能压缩黑白图像一样，随机的IFS能对灰度图像进行分形压缩。

2.2.4 基于迭代变换理论的分形编码方法

从前述可知，利用灰度图像的测度μ，可以构造度量空间（P,dH），其中，P是对于完备度量空间（X,d）的Borel测度空间，dH是Hutchinson度量。已经证明，由随机IFS构成的马尔可夫算子M 度量空间（P,dH）的一个压缩变换，它有唯一的不变测度μf ，M(μ)f=μf，而且符合拼贴定理。利用这些就可以对灰度图像进行分形压缩。总的来说，迭代函数系统（IFS）理论，构成了分形图像压缩的理论基础。

迭代函数系统（IFS）并没有给出以自动的方式对灰度图像进行编码的构造方法，除非是自相似性或自仿射性很强的图像，否则就很难对一般的单色图像找到合适的迭代函数系统（IFS）变换。但是，如果将一个图像细分成多个小块以后，则小块之间就会具有较大的相似性。只要仔细地找出这些小块之间的变换关系，便可以构成原图像的分形压缩码。下面将根据这种想法，导出分块迭代变换理论（ITT）编码方法。这是一种可以利用计算机对灰度图像进行自动图像压缩的方法。

迭代变换理论（ITT）一般的迭代过程，可以表示为如图2.2所示的一阶递归系统。

图2.2 迭代过程表示为一阶递归系统

迭代变换理论主要是研究以下形式的迭代序列的变化情况：

其中，τ是对象空间中定义的一个变换；μ是一个原始对象，该理论的英文缩写为ITT。

序列的状态可以从完全不可预测（混沌）到完全可以预测，后者有两种情况：

① 在N次迭代以后，变为周期为N的周期运动。

② 收敛于一个吸引对象或对象的一个吸引集。

将迭代变换理论（ITT）用于分形图像压缩时，就是要研究当τ是压缩变换时，吸引对象的类型是什么，以及如何去控制它们。对象空间中的对象可以用称为测度的函数来模化，其中集函数是可加的。由于这些测度的一个重要性质是可分解的，即可以分解为该支持集的若干子集，所以可以用各部分来定义对象的整体。

在测度空间内定义的压缩变换，即马尔可夫算子，使该算子的不动测度接近于原图像。ITT图像压缩理论正是将数字图像作为压缩、仿射和由各部分定义的马尔可夫算子的不动点进行编码，即寻找马尔可夫算子的系数。

对于总体与其各个局部相似的图像，不难找到迭代函数系统（IFS），但是对于一般的单色灰度图像，很难找到迭代函数系统（IFS），这时可以先将图像细分成许多小块，这些小块之间就有相似之处，而且比较容易发现小块之间的相似性。倘若找出各个局部的变换，便可以构造出原图像的分形码。在这个意义上，图像是有冗余度的，所以可以找到比原图像复杂度低的分形码实现对图像的压缩。

对象空间选用二维Borel测度空间P，讨论对象的分割、度量和压缩变换。图像是作为Borel测度空间P中的对象μ，（P,d）则是数字图像的一个度量空间。

对象支持的分割主要考虑基于四叉树分解的分层块状分割。

若将大小为1/L×1/L的单元一分为四，分割后单元的大小为1/2L×1/2L，重复此过程，若有n层分割，就有n种尺寸，其单元尺寸分别为1/L, 1/2L, …, 1/2n-1L。此结构与图像的四叉表示方法密切相关，通常多用二层分割，父本单元为1/L×1/L，子本单元为1/2L×1/2L。

上述两类分割，都可写成，其中，i是单元指标的有限集，Ri称为分割的区单元。

为了比较分割的区单元上的图像之间的相似程度，引入图像模型的距离函数，又称为失真测度。

Hutchison度量与测度函数相对应，相应的PRiP上的Hutchison度量为

∀νν∈PR iP

测度函数fi的选择应与视觉系统的生理特性相适应，只需对函数积分，就能算出距离。

离散化后为LK度量：

经过上述分析，给出基于ITT图像编码过程如下:

① 首先对原始图像进行分块。

设Borig是待编码的原始图像，将Borig分成两种大小的子块，小块的大小为K×K，称之为Range子块（Range Blocks），记为R1,R2, …,RN。当i≠j 时，Ri∩Rj=φ；且R1∩R2∩…∩RN=Borig。大块的大小为L×L，称为D子块（Domain Block），记为D1,D2, ,…DM，D 子块之间允许有部分重叠。一般情况下，L＞K，这主要是为了满足紧缩变换的要求。