图像基础技术处理 5

第八章数小波图像处理《数字图像处理》李俊山编著.《数字图像处理（第5版）》

小波变换(wavelettransform）是20世纪80年代中后期逐渐发展起来的一种新的数学工具，在图像压缩、图像去噪、图像边缘提取和纹理分析，以及语音识别与合成、地震信号处理等领域得到了非常广泛的应用。

1、傅立叶等变换的局限性（1）仅适用于那些变化规律呈周期性变化的信号。（2）不能描述随时间变化的频率特性。8.0引言

如何分析那些变化规律呈非周期性变化，且频率随时间变化的频率信号呢？8.0引言8.0引言

（1）短时傅立叶变化的思想是：选择一个时频局部化的窗函数，假设分析窗函数g(t)在一个短时间间隔内是平稳的，移动窗函数g(t)

使f(t)g(t)在不同的有限时间宽度内是平稳信号，从而可计算出各个不同时刻的功率谱。

2、短时傅立叶变换(STFT)

：一种时变信号及其局部段落弦波成份的频率与相位分析方法

（2）通过短时傅立叶变换得出的时频图存在的问题是：当分析频率较高部分的信号时，应该用更窄的窗；反之择用宽窗。但一旦选定窗过后，分辨率就固定了；若要其他分辨率，则需要更换窗。8.0引言

2、短时傅立叶变换(STFT)

：一种时变信号及其局部段落弦波成份的频率与相位分析方法

（3）针对短时傅立叶变换的这个不足，人们就想：能不能用一个窗函数的伸缩和平移来分析信号，且要求这个变换是可以完全重构的和保持能量守恒的；如果存在这样的窗函数，该窗函数应满足什么条件呢？答案是，这个窗函数就是连续小波，只要它满足容许条件，即可达到完全重构。8.0引言

2、短时傅立叶变换(STFT)

：一种时变信号及其局部段落弦波成份的频率与相位分析方法

8.1小波变换与图像小波变换

1、小波的概念和特性

小波是指小区域的波，又称为子波，是一个长度有限，均值为0的振荡波形。8.1.1小波的概念和特性

（a）小波示例

（b）小波的特性示例

图8.1小波及其特性

1、小波的概念和特性

小波的“小”：

一是相对于傅里叶波而言，傅里叶波指的是在时域空间无穷震荡的正弦波或余弦波。

二是指它是一种能量在时域非常集中的波，其能量都集中在某一点附近，而且积分的值为零。

三是指它具有衰减性，即局部非0性，其非0系数的个数多少，反映了高频成分的丰富程度。8.1.1小波与小波变换

1、小波的概念和特性

也就是说，小波必须具备两个特性：

（1）小波必须是振荡的；（2）小波的振幅只能在一个很短的区间上非零，也即是局部化的。

8.1.1小波与小波变换

小波例1小波例2时间时间振幅振幅1、小波的概念和特性8.1.1小波与小波变换

1、小波的概念和特性按照小波的定义及特性，图8.2所示的波不是小波。（a）周期波示例

（b）不具震荡性示例

图8.2不是小波的示例

8.1.1小波与小波变换

8.1.1小波与小波变换

1、小波的概念和特性—小波基表示发生的时间和频率运用小波基，可以提取信号中的“指定时间”（时间A或时间B）的变化。

顾名思义，小波是在某时间发生的小的波动。时间A时间B8.1.1小波与小波变换

1、小波的概念和特性—小波基表示发生的时间和频率运用小波基，也可以提取信号中的“指定频率”的变化。

提取信号中时间A的比较慢速的变化，称较低频率成分

提取信号中时间B的比较快速地变化，称较高频率成分。时间A时间B2、小波变换

小波变换是指基于小波的变换，其基本思想是通过一个母函数在时间上的平移和在尺度上的伸缩得到一个函数簇，然后利用这簇函数去表示或逼近信号或函数，获得一种能自动适应各种频变成分的有效的信号分析手段。8.1.1小波与小波变换

小波变换的优势：（1）小波变换弥补了傅里叶变换不能描述随时间变化的频率特性的不足，特别适合于那些在不同时间窗内具有不同频率特性，而且其应用目的是为了得到信号或图像的局部频谱信息而非整体信息的信号或图像处理问题。8.1.1小波与小波变换

小波变换的优势：（2）由于小波变换在时域和频域同时具有良好的局部化特征，利用小波的多分辨率分析特性既可高效地描述图像的平坦区域，又可有效地表示图像信号的局部突变(即图像的边缘轮廓部分）。再加上小波变换在计算上的低复杂性，因此在图像处理领域具有十分广阔的应用前景。8.1.1小波与小波变换

1、能量有限函数空间

设为实数集合(实直线)，也即=（-∞，+∞），则可将定义在实数集合上的可测函数f的空间定义为：8.1.2连续小波变换

（8.1）

（1）可测连续时间信号函数f的空间

称为能量有限函数空间。（2）<f，g>代表内积，其含义是：是的复共轭。当和都是实函数时:

8.1.2连续小波变换

定义8.1：设函数,且，则称为基本小波函数或母小波函数。对基本小波函数做伸缩和平移变换，就可得到一个函数簇，则称其为连续小波（也称分析小波），且

：

(8.4)

2、连续小波8.1.2连续小波变换

定义8.1：设函数,且，则称为基本小波函数或母小波函数。对基本小波函数做伸缩和平移变换，就可得到一个函数簇，则称其为连续小波（也称分析小波），且

：

(8.4)

其中1，

意味着小波函数的能量是有限的，意味着基本小波函数是一个积分为零的

函数，其能量集中在以t=0为中心的邻域内。

2、连续小波定义8.1中，

其中，a称为尺度因子（也称为伸缩因子），b称为平移因子（也称为位置因子）。使用系数是为了在不同尺度间规范化能量。归一化因子时间平移参数尺度伸缩参数(8.4)8.1.2连续小波变换

8.1.2连续小波变换

3、连续小波变换

定义8.2：设，为基本小波函数，则连续小波变换(ContinueWaveletTransform，简写为CWT)定义为：(8.5)

其中，函数称为小波；当尺度因子a＞1时，函数具有伸展作用；当a＜1时，函数具有收缩作用；函数族为积分核。也即：能量有限函数空间中的函数f与连续小波函数的内积。8.1.2连续小波变换

定义8.2说明：

（1）小波变换是指基于基本小波函数的变换。（2）小波变换的实质是把一个称为基本小波的函数在时间上平移b，然后在不同的尺度a下与待分析的信号做内积。（3）尺度因子a是一个频率参数，低频对应于信号的全局信息（一般贯穿于整个信号之中），伸缩信息高，尺度因子a的值大；高频对应于信号的细节信息(通常仅持续较短的时间)，伸缩信息低，尺度因子a的值小。8.1.2连续小波变换

尺度因子（频率参数）a的特性及其对小波函数的影响如图8.3所示。

图8.3尺度因子(频率参数)a的特性及其对小波函数的影响示例

小a大a8.1.2连续小波变换

（4）平移因子b是一个时间参数。参数b和a在时-频平面给出了一个可变的时间-频率窗。由于信号的频率与其周期成反比，所以对于高频谱信息，时间间隔变小，可以给出较好的精度；对于低频信息，时间间隔变大，可以给出完全的信息。所以在式（8.5）关于某个“基小波”的小波变换中，由参数b和a给出的时间-频率窗就可使在高中心频率随其时间窗自动变窄，在低中心频率时其时间窗自动变宽，具有类似调焦距的伸缩能力。

比如，设有小波函数。当a=2,b=15时，ψ2,15(t)的波形从原点向右移至t=15，且波形展宽。当a=0.5，b=-10时，ψ1/2,-10(t)的波形从原点向左移至t=-10,且波形收缩。如下图.

8.1.2连续小波变换

8.1.3离散小波变换

1、能量有限序列空间

设为整数集合，且={…,-2,-1,0,+1,+2,…}，则能量有限平方和序列空间定义为：其中，内积<c，c>定义为：

（8.6）

（8.7）

2、离散小波

把式(8.4)的连续小波中的参数a、b离散化，并令尺度因子，；平移因子，则可得到离散小波：

(8.8)

8.1.3离散小波变换

(8.4)8.1.3离散小波变换

3、离散小波变换

定义8.3

设，且为基本小波函数，其离散小波变换（DiscretWaveletTransform,简写为DWT）定义为：(8.9)

8.1.4二进小波

1、二进小波

在实际应用中，通常是对小波变换进行二进制离散化，所以当，

时，对应于式（8.8）的二进（离散）小波表示为：

（8.10）

对于一维小波函数来说，式(8.10)中的n决定了

在t轴上的位置，j决定了的宽度，即沿t轴的宽或窄的程度，而用于控制其高度或幅度。

8.1.4二进小波

2、二进小波变换

与式(8.9)离散小波变换对应的二进小波变换表示为：

（8.11）

8.1.5塔式分解与Mallat算法

研究表明，能够分解为子空间的直接和：(8.12)其中，符号“”表示“直接和”。在上述意义下，每个都有唯一的分解：

(8.13)其中，对于所有成立。8.1.5塔式分解与Mallat算法

1、的分解8.1.5塔式分解与Mallat算法

1、的分解(续)

如果是一个正交小波，那么的子空间相互是正交的，即：

（8.14）

这时，公式（8.12）的“直接和”就变成正交和了，即：并可表示为：

（8.15）

（8.16）

8.1.5塔式分解与Mallat算法

1、的分解(续)

公式（8.16）所表示的意义是：任一分解为函数的（无限）和不仅是唯一的，而且如同公式（8.13）所描述的那样，f的分量还是相互正交的。公式（8.16）的分解通常称为的一种正交分解。（8.16）

（8.13）

8.1.5塔式分解与Mallat算法

2、塔式分解

在公式（8.12）的有关空间的分解基础上，把（8.17）

定义为中的闭子空间（尺度空间）的一个嵌套序列。且由式（8.12）和式（8.17）可知有：（8.18）

和

（8.19）

8.1.5塔式分解与Mallat算法

2、塔式分解(续)

由式（8.19）可知，捕捉了逼近时丢失的信息；子空间是嵌套的，也即尺度子空间具有递归嵌套关系：8.1.5塔式分解与Mallat算法

2、塔式分解(续)

各之间的嵌套关系如图8.5所示。

……图8.5

各之间的嵌套关系示例

8.1.5塔式分解与Mallat算法

2、塔式分解(续)

由可知，对于任意整数N与I>0，有如下的塔式分解：

（8.20）

8.1.5塔式分解与Mallat算法

3、Mallat算法

在实际应用中，对于信号，总可以找到适当的尺度函数，并生成，从而，有唯一的分解：(8.21)

其中:

(8.22)

3、Mallat算法(续)

对于，只有唯一的级数表示，即：(8.23)

(8.24)

这样，公式（8.21）中的分解就可唯一地用公式（8.23）和公式（8.24）中的序列和来确定。

8.1.5塔式分解与Mallat算法

3、Mallat算法(续)

由可得：（8.25）

根据的直接和分解公式（即，）成立的充要条件定理和小波理论的有关定理，就可以得到Mallat分解算法为：（8.26）

8.1.5塔式分解与Mallat算法

其中，是一个低通滤波系数，是一个高通滤波系数。比较图8.6可知，的初值应取。

……图8.6Mallat分解过程

3、Mallat算法(续)8.1.5塔式分解与Mallat算法

图8.6是一维信号的Mallat多分辨率分解过程示意图。根据Mallat分解算法，设为一维输入序列，分解过程由低通滤波器和高通滤波器对信号滤波，然后对输出结果进行下二采样来实现正交小波分解，多级分解通过级联的方式进行，每一级的分解都是在前一级分解产生的低频分量上继续进行，分解的结果使信号的时域分辨率减半，即产生了长度减半的两个部分，一个是由低通滤波器产生的原始信号的平滑部分，另一个则是由高通滤波器产生的原始信号的细节部分。但由于分解时滤波器使得半数的采样信号占用了全部的信号频带，所以分解操作使信号的频率分辨率加倍，上述操作便是通常所说的子带编码。经过

次低通滤波得到的输出是，经过次高通滤波得到的输出是。8.1.5塔式分解与Mallat算法

由图8.6可知，正整数N实质上是对一维信号进行Mallat多分辨率分解的最大层数；且在式(8.20)至式(8.22)中，应有I=N。根据式(8.26)，图8.6中的每一步分解过程的实现原理如图8.7所示。

图8.7Mallat分解算法

用类似于信号分解的思路同样可以推出小波系数重构公式为：

(8.27)8.1.5塔式分解与Mallat算法

图8.8是一维信号的Mallat多分辨率重构过程示意图。重构时使用一对合成滤波器和对小波分解的结果进行滤波，再进行上二采样，即通过在的的样本之间插入零、滤波，可逐步重构出每个信号。多级合成通过级联的方式进行，合成是分解的逆运算。……8.1.5塔式分解与Mallat算法

图8.8Mallat重构过程根据式(8.27)，图8.8中的每一步重构过程的实现原理如图8.9所示。8.1.5塔式分解与Mallat算法

图8.9Mallat重构算法

4、

Mallat算法在二维图像处理中的应用可以用矢量积的方式把一维小波变换推广到二维空间，也就是把不同空间方向的对象联合起来。8.1.5塔式分解与Mallat算法

4、

Mallat算法在二维图像处理中的应用8.1.6图像的小波变换

图像信源的最大特点是非平稳特性，也就是不能用一种确定的数学模型来描述，而小波的多分辨率分析特性使之既可高效地描述图像的平坦区域，又可有效地表示图像信号的局部突变（即图像的边缘轮廓部分），它在空域和频域良好的局部性，使之能够聚焦到图像的任意细节，相当于一个具有放大和平移功能的“数学显微镜”。因此小波非常适合于进行图像处理。

8.1.6图像的小波变换

1、二维离散小波变换及其算法基础设是一维尺度函数，是相应的小波函数，则可得到二维小波变换的基础函数为：（8.29）

1、二维离散小波变换及其算法基础设是一维尺度函数，是相应的小波函数，则可得到二维小波变换的基础函数为：（8.29）

8.1.6图像的小波变换

1、二维离散小波变换及其算法基础(续)设图像的大小为M×N，且M=2m，N=2n。对图像每进行一次二维离散小波变换，就可分解产生一个低频子图(子带）LL和3个高频子图，即水平子带HL、垂直子带LH和对角子带HH（当i=1，即对图像进行一次小波变换后，各子带的分布如图8.10所示，每个子带分别包含了各自相应频带的小波系数）。LL1HL1HH1LH1图8.10对图像进行一次小波变换后的小波系数分布示意图

8.1.6图像的小波变换

1、二维离散小波变换及其算法基础(续)下一级小波变换在前级产生的低频子带LL的基础上进行，依次重复，即可完成图像的（i=1，2，…，-1,）级小波分解，对图像进行级小波变换后，产生的子带数目为3i+1。8.1.6图像的小波变换

1、二维离散小波变换及其算法基础(续)由于对图像每进行一次小波变换，就相当于在水平方向和竖直方向进行隔点采样，所以变换后的图像就分解成4个大小为前一级图像（或子图）尺寸的1/4的频带子图，图像的时域分辨率就下降一半（相应地使尺度加倍），在对图像进行i级小波变换后，所得到的i级分辨率图像的分辨率是原图像分辨率的1/2i。8.1.6图像的小波变换

1、二维离散小波变换及其算法基础(续)图8.11给出了对图像进行3层小波变换（即对图像的3尺度的分解）后的系数分布示意图。

LL3HL3HH3LH3LH2HH2HL2HL1HH1LH1图8.118.1.6图像的小波变换

1、二维离散小波变换及其算法基础(续)图8.12给出了与图8.11对应的一个对图像进行3层小波变换的结果示例。

图像多尺度分解示例3（i=3）（a）原图像

（b）1层小波变换结果

（c）2层小波变换结果

（d）3层小波变换结果

图8.12

(a)一层分解(b)二层分解

图像多尺度分解示例1（i=2）低频系数水平系数垂直系数对角系数8.1.6图像的小波变换

二层小波分解后的小波系数示意（i=2）。8.1.6图像的小波变换

二层小波分解后的小波系数示意（i=2）。8.1.6图像的小波变换

2、二维离散小波变换原理对于二维图像信号，二维Mallat算法是利用一维滤波器分别对图像数据的行和列进行一维小波变换。

二维离散小波变换的Mallat实现原理如图8.13所示。图8.13二维离散小波变换的Mallat实现——

二维离散小波分解

二维离散小波分解：8.1.6图像的小波变换

2、二维离散小波变换原理其中：LL(x,y)—原始图像的（粗）逼近子图HL(x,y)—原始图像的水平方向细节子图LH(x,y)—原始图像的垂直方向细节子图HH(x,y)—原始图像的对角线方向细节子图LLHLHHLH二维离散小波分解：

在图8.13(a）中，图中标注的说明是以对图像进行第一次Mallta分解为例。在第一层首先用h和g与图像的每行作变换(对应于图8.13(a)的行滤波)，并丢弃奇数行（设最左一列为第0列）；接着，对行变换后的M/2×N阵列的每列再与h和g相卷积，并丢弃奇数列(设最上一行为第0行)；其结果就是该层变换所有求的4个M/2×N/2阵列。此时，LL子带为，HL子带为，LH子带为，HH子带为。接着进行的分解过程原理相同。图8.13(a）二维离散小波分解-图像的滤波采样HHHLLL8.1.6图像的小波变换

2、二维离散小波变换原理8.1.6图像的小波变换

2、二维离散小波变换原理利用二维Mallat算法，对分解后的图像进行二维离散小波重构的实现原理为：（b）二维离散小波重构图8.13二维离散小波变换的Mallat实现--二维离散小波重构

一个3级（i=3）分解重构的例子。8.1.6图像的小波变换

3、二维离散小波变换快速算法把一维Mallat分解与重构算法推广到二维，通过对图像数据的行和列分别进行变换，就可得到二维Mallat分解与重构算法。对一幅M×N的图像进行分解的算法为：

（8.30）

（8.30）

其中：

①第一次分解时，中的k=M，=N。②是一个低频子带，对应于图8.11中的LL1（左上角的1/4子带）；是水平方向的高频子带，对应于图8.11中的HL1；

是垂直方向的高频子带，对应于图8.11中的LH1；是对角线方向的高频子带,对应于图8.11中的HH1。同理，可以把低频子带进一步分解而得到、、和，分别对应于图8.11中的LL2、HL2、LH2和HH2。进一步可把分解得到、和，分别对应于图8.11中的LL3、HL3、LH3和HH3。8.1.6图像的小波变换

二维Mallat重构算法为：（8.31）

8.1.6图像的小波变换

4、图像小波变换的几个关键问题

在对图像进行小波变换中有一个小波变换层数的选择，另一个关键技术问题就是小波基的选取。8.1.6图像的小波变换

1）小波变换层数的选择离散小波变换是将原始图像分解成一个近似信号和3个细节信号，即每一层分解成4个子带信号，近似信号又可以进一步分解成4个子带信号，故总的子带数为3i＋1，其中i就是分解的层数。分解层数的选择一方面要看图像的复杂程度和滤波器的长度，另一方面要从子带信息量来分析：当一个子带分成4个子带时，若4个子带的熵值和很小，就不值得再分解了。例如，给定子带B要进一步分解成LL、HL、LH和HH4个子带，其熵分别记为H(LL）,H(HL）,H(LH）,H(HH）,即：（8.32）

式中，为给定的门限值。

8.1.6图像的小波变换

1）小波变换层数的选择（续）有学者已经证实：对于512×512像素的标准测试图像Cronkite，前面的4层分解都可以显著地减少熵值，但4层之后的熵值曲线变得非常平稳，所以，作多于4层的分解就没有必要了。由于计算图像的熵过于复杂，为了节省时间和提高编码效率，在实际应用过程中一般只根据原始图像的大小和一些经验数据来确定分解层数。在目前的应用中，大多数情况下取变换层数为3。8.1.6图像的小波变换

2）小波基数的选取有与傅里叶(Fourier）变换相比，小波变换具有很大的灵活性，其中一个重要的方面就是傅里叶变换具有唯一的正弦型基函数，其数学性质比较简单，而小波变换在理论上有很多小波基可供选择。选用不同的小波基对于图像处理的效果有很大的影响，这种灵活性一方面使小波变换的性能比傅里叶变换有了根本提高，另一方面，也给小波变换的应用带来了难题。

8.1.6图像的小波变换

2）小波基数的选取（续）

小波基的选取一般要考虑以下因素：（1）线性相位。如果小波具有线性相位或至少具有广义线性相位，则可以避免小波分解和重构时的图像失真，尤其是图像在边缘处的失真。8.1.6图像的小波变换

2）小波基数的选取（续）

小波基的选取一般要考虑以下因素：（2）紧支性和衰减性。若函数在区间[a,b]外恒为零，则称函数在这个区间上紧支，称[a,b]为的支集，[a,b]越小，支集越小，具有该性质的小波称为紧支撑小波。支集宽度越小的小波，其局部化能力越强，计算复杂度也越低，更便于快速实现。

8.1.6图像的小波变换

2）小波基数的选取（续）

小波基的选取一般要考虑以下因素：（3）正交性。用正交小波基对图像做多尺度分解，可得一正交的镜像滤波器。低通子带数据和高通子带数据分别落在相互正交的子空间中，使各子带数据相关性减少。8.1.6图像的小波变换

5、几种最基本的小波基

1）Haar小波（8.33）

8.1.6图像的小波变换

5、几种最基本的小波基

1）Haar小波（续）Harr小波的尺度函数为：

Haar小波具有紧（最短的）支集，支集长度为1，滤波器长度为2，具有正交性和对称性。

（8.34）

8.1.6图像的小波变换

5、几种最基本的小波基2）墨西哥草帽（MexicoHat）小波

MexicoHat小波如图8.15所示，其解析表达式为：（8.35）

MexicoHat小波为连续小波，不存在尺度函数，也不具备正交性，不存在紧支集，有效支集区间为[-5，5]，时频均具有很好的局部性。

8.1.6图像的小波变换

5、几种最基本的小波基3）Morlet小波

Morlet小波如图8.16所示，其解析表达式为：

（8.36）

Morlet小波为连续小波，不存在尺度函数，也不具备正交性，不存在紧支集，有效支集区间为[-4，4]，时频均具有很好的局部性。8.1.6图像的小波变换

应当指出的是，虽然已有很多文献对如何选取小波基的问题进行了理论研究和论述，但小波基的选取问题并没有从根本上得到解决。在很长一段时间内，小波基的选取仍将是小波应用研究中的一个难点。在实际应用中，许多小波基的选取往往都是通过实验来确定的。

8.2基于图像小波变换的嵌入式零树编码

小波变换因其良好的空间——频率局部特性和与人眼视觉特性相符的变换机制，在图像压缩编码方面得到了广泛的应用；而基于小波变换的嵌入式零树小波编码算法（EmbeddedZerotreeWaveletAlgorithm，简称EZW）以其压缩比高、便于控制压缩率和失真率、便于实现图像的渐进传输和较好的图像恢复质量等优点，已经成为一种非常重要的图像压缩方法，并以此为基础衍生出了多种有效的图像压缩编码方法。

小波变换编码的基本思想是将原始图像经二维小波变换后，转换成小波域上的小波系数。由于小波变换后能使原始图像的能量集中在少数的小波系数上，因此最简单的系数量化方法就是只保留那些能量较大的小波系数，而将小于某一阈值的系数略去，或者将其表示为恒定常数，从而达到数据压缩的目的。因此，基于小波变换的图像压缩过程是由量化过程和编码过程实现的。8.2.1基于小波变换的图像压缩基本思想

一幅图像的小波变换编码压缩过程如图8.17所示。图8.17图像小波变换编码示意图

8.2.1基于小波变换的图像压缩基本思想

如果不考虑计算误差，小波变换过程是无损和可逆的。由于量化过程要略去小于某一阈值的系数，或将其置为恒定常数，所以量化过程是有损的和不可逆的，也即基于小波变换的图像压缩编码是有损压缩编码。8.2.1基于小波变换的图像压缩基本思想

图像的小波变换解压缩（简称解码）恢复过程是图8.17所示的图像小波变换编码过程的逆过程，如图8.18所示。图8.18小波图像编解码示意图

8.2.1基于小波变换的图像压缩基本思想8.2.2嵌入式编码与零树概念

研究表明，如果一个低频小波系数小于某个阈值T，则其子系数也极有可能小于T，利用这种相关性，可以由低频子带系数来预测高频子带系数，EZW算法的零树编码正是基于这种相关性的编码方法。下面详细地介绍EZW算法的有关概念和编码方法。

1.嵌入式编码的概念所谓嵌入式编码，就是编码器将待编码的比特流按重要性的不同进行排序，根据目标码率或失真度的大小要求确定迭代次数或随时结束编码；同样，对于给定的解码流，解码器也可据此随时结束解码，并可以得到相应码流截断处的目标码率的恢复图像。

8.2.2嵌入式编码与零树概念

1.嵌入式编码的概念（续）嵌入式编码实质上是一种比特连续逼近的图像编码方法，也即按位平面分层，首先编码传输最重要的信息，也就是传输幅值最大的变换系数的位信息（因为越高层的位平面的信息权重越大，对编码越重要），通过对判决阈值逐层折半递减，实现逐次从最重要的位（最高位）到最不重要的位（最低位）的逐个传输，直到达到所需精度（码率）时停止。8.2.2嵌入式编码与零树概念

◆

图像的渐进式传输（数据下载）连续效果示例

◆

图像的渐进式传输分帧效果示例

2.零树及相关概念8.2.2嵌入式编码与零树概念

图8.19三级小波分解子带树及其系数的关联关系8.2.2嵌入式编码与零树概念

2.零树及相关概念

树根是最低频子带的LL3结点，它与3个分别位于水平方向、垂直方向、对角线方向的次低分辨率子带的小波系数相关联。8.2.2嵌入式编码与零树概念

2.零树及相关概念对于其余子带（最高分辨率子带除外）的结点，都与其下一级尺度子带（也即高一级分辨率子带）的相同方向的相同空间位置的4个小波系数相关联。8.2.2嵌入式编码与零树概念

2.零树及相关概念

粗尺度上的系数称为与其关联的下一级细尺度系数的父亲（父系数）；

细尺度上的系数称为与其关联的上一级粗尺度系数的孩子。8.2.2嵌入式编码与零树概念2.零树及相关概念对应地把比当前子带尺度大的上一级子带称为父子带；把比当前子带尺度小的下一级子带称为孩子子带。6.2.2嵌入式编码与零树概念

2.零树及相关概念

对于某个给定的父系数，把相同方向、相同空间位置（水平、垂直、右下）的所有细尺度上的系数称为子孙；对于某个给定的孩子，把相同方向、对应于相同空间位置的所有粗尺度上的系数称为祖先。

2.零树及相关概念（续）基于以上所描述的各尺度上小波系数的关联关系，就形成了一系列根在最低分辨率的树型结构，如图8.19所示。8.2.2嵌入式编码与零树概念

2.零树及相关概念（续）8.2.2嵌入式编码与零树概念图8.19三级小波分解子带树及其系数的关联关系

2.零树及相关概念（续）零树则是指当前系数和他的所有后代都为零（或都小于某个阈值）的树。8.2.2嵌入式编码与零树概念1.重要的小波系数和不重要的小波系数在基于小波变换的嵌入式零树编码中，用一个给定的阈值T来决定小波系数x是否是重要的。如果一个小波系数x的绝对值不小于给定的阈值T，即当abs(x)≥T时，称该小波系数x是重要的；反之，当abs(x)<T时，称该小波系数x是不重要的。8.2.3重要小波系数及扫描方法

1.重要的小波系数和不重要的小波系数（续）

如果一个在粗尺度子带上的小波系数x关于给定的阈值T是不重要的，并且与其关联的较细尺度子带上相同方向、相同空间位置的所有小波系数也关于给定的阈值T是不重要的，这时就称从粗尺度子带的小波系数到细尺度子带上的所有小波系数构成了一棵零树（由于这些系数不重要，当把这些系数值都置为零值时就和上面的零树概念相同了）。零树中粗尺度上的那个小波系数就称为零树根。8.2.3重要小波系数及其扫描方法

1.重要的小波系数和不重要的小波系数（续）

如果一个在粗尺度上的小波系数x关于给定阈值T是不重要的，但它在较细尺度子带上相同方向、相同空间位置的小波系数关于给定的阈值T至少存在一个重要的子孙，则粗尺度子带上的这个系数就称为孤立零点。8.2.3重要小波系数及其扫描方法

1.重要的小波系数和不重要的小波系数（续）

根据重要系数的判别方式abs（x）≥T，说明x可能为正或可能为负，所以，图像的小波分解子带树中的小波系数可以用4种符号表示成一串符号流：①P，正的重要系数（POSitive）。②N，负的重要系数（Negative）。③I，孤立零点（IsolatedZero-point）。④T，零树根（ZeroTreeRoot）。8.2.3重要小波系数及其扫描方法

1.重要的小波系数和不重要的小波系数（续）

基于小波变换的零树编码的理论基础主要是统计概率。该方法假设，如果小波系数x是不重要的，那么x对应的子孙为不重要系数的概率非常大。记住零树根的位置（只对零树根编码），就可以忽略零树根以下的零点，从而达到压缩的目的。形成零树的棵数越多，零树根出现越早，编码效率就越高。

8.2.3重要小波系数及其扫描方法

2.小波变换系数的扫描方法采用主扫描和精细扫描二次扫描来完成对零树和重要系数的判定。

◆主扫描是对小波系数的扫描，遵循先父结点，后孩子结点的原则。对于一个M级尺度的变换来说，扫描从标注为LLM的最低频子带开始，依次精细扫描HLM、LHM和HHM，接下来依次精细扫描M-1层、M－2层等。8.2.3重要小波系数及其扫描方法

图8.20对小波分解子带树中子带的扫描顺序2.小波变换系数的扫描方法(续)8.2.3重要小波系数及其扫描方法

2.小波变换系数的扫描方法(续)每一个子带的扫描：按zig-zag(之字形-急转)顺序进行扫描。

图8.21三级分解各子带中小波变换系数的扫描顺序8.2.3重要小波系数及其扫描方法

◆嵌入式零树编码通过逐次使用阈值序列T1,T2,…,TN来决定重要系数的逼近量化过程完成嵌入式编码，量化层数N（也即逼近量化的循环次数）一般按照压缩比和失真率折中的原则来事先确定。

◆整个逐次逼近量化过程包括主扫描、精细扫描和符号编码三个子过程。

◆编码过程中一般假设在编码前已经知道或已经获得了子带树中具有最大值的小波系数。8.2.4嵌入式零树编码方法

编码过程的步骤：

1）构建用于主扫描和精细扫描的主表和辅表。8.2.4嵌入式零树编码方法

2）设置初始阈值T1初始阈值T1（k=1，Tk=T1）的选取要同时满足：对于所有的小波系数x应有abs(x)≤2T1；T1是一个2的整次幂的整数；2abs(T1)的值应不小于且最接近于最大小波系数max(abs(x))。并设Tk-1=T0=2abs(T1)，T0为第一次扫描时的区间上限，在精细扫描中用于区间的分割。8.2.4嵌入式零树编码方法

例8.1

图8.22(a)给出了一幅8×8图像的三级小波变换的矩阵

值。

63-34501014-13713-127346-15-7394-232-31231514-9-73-12-148-59-14530-322-36-45115646-223-204363603-44（a）三级小波变换矩阵

分析：①设置初始阈值T

依据abs(x)≤2T1

。变换矩阵中最大的系数值为63，比63大且为2的整次幂的整数是64，所以选取T1=32，T0=64。8.2.4嵌入式零树编码方法

编码过程的步骤：

1）首先，构建主表如表8.1和辅表如表8.2（开始时，构建的仅是表8.1和表8.2的架构，其中的数据是在其后的扫描过程中填入的。表8.1中的最右一列是为了配合下面的主扫描过程说明而增加的）。

为了直观起见，将第一次主扫描的输出符号和未扫描位置标注在图8.22（b）中。8.2.4嵌入式零树编码方法

编码过程的步骤：

2）首先，构建主表如表8.1和辅表如表8.28.2.4嵌入式零树编码方法

63-34501014-13713-127346-15-7394-232-31231514-9-73-12-148-59-14530-322-36-45115646-223-204363603-44（a）三级小波变换矩阵

P

（b）第1次主扫描输出符号和未搜索位置2）第一次主扫描（T1＝32）

如果abs(x)≥T，则认为小波系数x是重要的，输出x的符号；2）第一次主扫描（T1＝32）

0-34501014-13713-127346-15-7394-232-31231514-9-73-12-148-59-14530-322-36-45115646-223-204363603-44（a）三级小波变换矩阵

PN

（b）第1次主扫描输出符号和未搜索位置如果abs(x)≥T，则认为小波系数x是重要的，输出x的符号；2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

00501014-13713-127346-15-7394-232-3123

1514-9-73-12-148

-59-14530-322-36-45115646-223-204363603-44（a）三级小波变换矩阵

PN

I

（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

00501014-13713-127346-15-7394-232-31231514-9-7

3-12-148-59-14530-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PN

IT

••••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

00501014-13713-127346-15-7394-232-31231514-9-7

3-12-148-59-14530-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PN

P

IT

••••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)≥T，则认为小波系数x是重要的，输出x的符号；2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127

346-1

5-7394-232-31231514-9-7

3-12-148-59-14530-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

••

••IT

••••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014-13713-127346-1

5-739

4-232-31231514-9-7

3-12-148-59-14530-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

T

••••

••

••

IT

••••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127346-1

5-7

39

4-2

32-31231514-9-7

3-12-148-59-14530-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

T

T

••••

••

••

••

••IT

••••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127

346-1

5-7394-232-31231514-9-7

3-12-148

-59-145

30-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

T

T

••

••

••••••••ITT

••••

••

••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127

346-1

5-7394-232-312315

14-9-7

3-12-148

-59

-145

30

-322-36-451156

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

T

T

••

••

••••••••IT

T

I

••••

••

••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127

346-1

5-7394-232-312315

14

-9

-7

3-12-148

-59-145

30-32

2-3

6-4

511

56

46-223-204363603-44（a）三级小波变换矩阵

PNP

T

T

T

••

••

••••••••IT

T

I

T

••••

••

••

••

••

••••••••••••••••（b）第1次主扫描输出符号和未搜索位置如果abs(x)<T，则：如果x位于子带树的最低尺度子带（HL1，HL1，HH1），则输出IZ；否则在结点为x的四叉树上搜索：如果该四叉树是零树，则输出ZTR；否则输出IZ(子孙中至少存在一个重要系数)。2）第一次主扫描（T1＝32）

2）第一次主扫描（T1＝32）

63-3450

1014

-13713-127

346-1

5-7394-232-312315

14-9-7

3-12-148

-59-145

30-322-36-451156

46-2