内蒙古工业大学 多媒体技术(第5章)

第五章小波变换和小波图像编码

小波介绍一维哈尔小波变换二维哈尔小波变换小波图像编码5.1小波介绍小波分析是近二十年才发展起来、并迅速应用到图像处理和语音分析等众多领域的一种数学工具。它是继一百多年前的傅立叶分析之后的一个重大突破，无论对古老的自然科学还是对新兴的高新技术应用都产生了强烈冲击。小波理论是应用数学的一个新领域。要深入理解小波理论需要到比较多的数学知识。本章企图从工程应用角度出发，用比较直观的方法来介绍小波变换和它的应用，为读者深入研究小波理论和应用提供一些背景材料。小波简史傅立叶理论指出，一个信号可以表示成一系列正弦和余弦函数之和，叫做傅立叶展开式。用傅立叶展开式表示一个信号时，只有频率分辫率而没有时间分辨率，这就意味我们可以确定信号中包含的所有频率，但不能确定具有这些频率的信号出现在什么时候。为了继承博立叶分析的优点，同时又克服它的缺点，人们一直在寻找新的方法。

20世纪初，哈尔(AlfredHaar)对在函数空间中寻找一个与傅立叶基类似的基非常感兴趣。1909年他发现了小波，并被命名为哈尔小波(Haarwavelets)，他最早发现和使用了小波。20世纪70年代，当时在法国石油公司工作的年轻的地球物理学家JeanMorlet提出了小被变换(wavelettransform，WT)的概念。进入20世纪80年代，法国的科学家Y．Meyer和他的同事开始为此开发系统的小波分析方法。Meyer于1986年创造性地构造出具有一定衰减性的光滑函数，他用缩放(dilations)与平移(transltions)均为2j(j＞0的整数)的倍数构造了L2(R)空间的规范正交基，使小波得到真正的发展。

小波变换的主要算法则是由法国的科学家StephaneMallat在19884年提出。他在构造正交小波基时提出了多分辨率的概念，从空间上形象地说明了小波的多分辨率的特件、提出了正交小波的构造方法和快速算法，叫做Mallat算法。该算法统一了在此之前构造正交小波基的所有方法。它的地位相当于快速傅立叶变换在经典傅立叶分析中的地位。InridDaubechies，RonaldCoifman和VictorWickerhaser等著名科学家把这个小波理论引入到工程应用方面做出了极其重要的贡献。例如，InridDubechies于1988年最先揭示了小波变换和滤波器组(filterbanks)之间的内在关系，使离散小被分析变成为现实。 在信号处理中，自从S.Mallat和InridDaubchies发现滤波器组与小波基函数有密切关系之后，小波在信号(如声音信号，图像信号等)处理中得到极其广泛的应用。小波概念小波是定义在有限间隔而且其平均值为零的一种函数，它的波形如图8-1(b)所示。图8-1(a)是大家所熟悉的正弦波，图8-1(b)是从许多使用比较广泛的小波中挑选出的几种一维小波。(1)首先把原始图象顺序分割成8×8子块;(2)采样精度为P位(二进制),把[0,2P-1]范围的无符号数变换成[-2P-1,2P-1]范围的有符号数,作为离散余弦正变换(FDCT)的输入;(3)在输出端经离散余弦逆变换(IDCT)后又得到一系列8×8子块,需将数值范围[-2P-1,2P-1]变换回[0,2P-1]来重构图象。

量化的作用:在一定主观保真度图象质量前提下,丢掉那些对视觉影响不大的信息,通过量化可调节数据压缩比。

在众多的小波中，选择什么样的小波对信号进行分析是一个至关重要的问题。使用的小波不同，分析得到数据也不同，这是关系到能否达到使用小波分析的目的问题。如果没有现成的小波可用，那么还需要自己开发适用的小波。

小波函数在时域和领域中都应该具有某种程度的平滑度(smoothness)和集中性(concentration)，这个复杂的概念在数学上使用消失矩(vanishingmoments)来描述，用N表示小波的消失矩的数目。例如，Daubechies小波简写成bdN，N数日的大小反映了Daubechies小波的平滑度和集中性。信号分析一般是为了获得时间和频率域之间的相互关系。傅立叶变换提供了有关频率域的信息，但时间方面的局部化信息却基本丢失。与傅立叶变换不问，小波变换通过平移母小波(motherwavelet)可获得信号的时间消息，而通过缩放小波的宽度(或者叫做尺度)可获得信号的频率特性。 对母小波的缩放和平移操作是为了计算小波的系数，这些系数代表小波和局部信号之间的相互关系。本小节将介绍小波分析中常用的3个基本概念：连续小波变换、离散小波变换和小波重构。小波分析信号分析一般是为了获得时间和频率域之间的相互关系。傅立叶变换提供了有关频率域的信息，但时间方面的局部化信息却基本丢失。与傅立叶变换不问，小波变换通过平移母小波(motherwavelet)可获得信号的时间消息，而通过缩放小波的宽度(或者叫做尺度)可获得信号的频率特性。 对母小波的缩放和平移操作是为了计算小波的系数，这些系数代表小波和局部信号之间的相互关系。本小节将介绍小波分析中常用的3个基本概念：连续小波变换、离散小波变换和小波重构。连续小波变换傅立叶分折是把一个信号分解成各种不同频率的正弦波，因此正弦波是博立叶变换的基函数。同样，小波分析是把一个信号分解成将原始小波经过移位和缩放之后的一系列小波，因此小波同样可以用作表示一些函数的基函数。可以说，几乎能够用傅立叶分析的函数都可以用小波分析，因此小波变换也可以理解为用经过缩放和平移的一系列函数代替傅入叶变换的正弦波。仔细观察图所示的正弦波和小波可以发现，用不规则的小波分析变化激烈的信号也许比用平滑的正弦波更有效，或者说对信号的基本特性描述得更好。数学上傅立叶分析的过程实际上是用傅立叶变换表示：这个式子的含义就是，傅立叶变换是信号f(t)与复数指数e-jwt(e-jwt=coswt-jsinwt)之积在信号存在的整个期间里求和。博立叶变换的结果是傅立叶系数F(w)，它是频率w的函数。同样，连续小波变换(continuouswavelettransform,CWT)用下式表示：这个式子的含义就是，小波变换是信号f(t)与被缩放和平移的小波函数ψ之积在信号存在的整个期间里求和。CWT变换的结果是许多小波系数C，这些系数是缩放因子(scale)相位置(position)的函数。CWT的变换过程可分成如下5个步骤：步骤1：把小波ψ(t)和原始信号f(t)的开始部分进行比较。步骤2；计算系数C。该系数表示该部分信号与小波的近似程度。系数C的值越高表示信号与小波越相似，因此系数C可以反映这种波形的相关程度。步骤3：把小波向右移，距离为k，得到的小波函数为ψ(t-k)，然后重复步骤1和2。再把小波向右移，得到小波ψ(t-2k)，重复步骤1和2。按上述步骤一直进行下去，直到信号f(t)结束。步骤4：扩展小波ψ(t)，例如扩展一倍，得到的小波函数为ψ(t/2)。步骤5：重复步骤1~4。小波变换完成之后得到的系数是在不同的缩放因子下由信号的不同部分产生的。这些小波系数、缩放因子和时间之间的关系和它们的含义可以用图表示。该图是用MATLAB软件绘制的。小波的缩放因子与信号频率之间的关系可以这样来理解：缩放因子小，表示小波比较窄，度量的是信号细节，表示频率w比较高；相反缩放因子大，表示小波比较宽，度量的是信号的粗糙程度，表示频率w比较低。离散小波变换在计算连续小波变换时，实际上也是用离散的数据进行计算的，只是所用的缩放因子和平移参数比较小而已。不难想象，连续小波变换的计算量是惊人的。为了解决计算量的问题，缩放因子和平移参数都选择2j(j＞0的整数)的倍数。使用这样的缩放因子和平移参数的小波变换叫做双尺度小波变换(dyadicwavelettransform)，它是离散小波变换(discretewavelettransform,DWT)的一种形式。从文献看，离散小波变换通常指的就是双尺度小波变换。使用离散小波分析得到的小波系数、缩放因子和时间关系如图8-5所示。图8-5(a)是20世纪40年代使用Gabor开发的短时博立叶变换(shorttimeFouriertransform,STFT)得到的时间-频率关系图，图8-5(b)是20世纪80年代使用Morlet开发的小波变换得到的时间-缩放因子(反映频率)关系图。执行离散小波变换的有效方法是使用滤波器。该方法是Mallat在1988年开发的，叫做Mallat算法。这种方法实际上是一种信号的分解方法，在数字信号处理中称为双通道子带编码。用滤波器执行离散小波变换的概念如图8-6所示。图中，S表示原始的输入信号，通过两个互补的滤波器产生A和D两个信号，A表示信号的近似值(approximations)，D表示信号的细节值(Detail)。在许多应用中，信号的低频部分是最重要的，而高级部分起一个“添加剂”的作用。在小波分析中，近似值是大的缩放因子产生的系数，表示信号的低频分量，而细节值是小的缩放因子产生的系数，表示信号的高频分量。由此可见，离散小波变换可以表示成由低通滤波器和高通滤波器组成的一棵树。原始信号通过这祥的一对滤波器进行的分解叫做一级分解。信号的分解过程可以叠代，也就是说可进行多级分解。如果对信号的高频分量不再分解，而对低频分量连续进行分解，就得到许多分辨率较低的低频分量，形成如图8-7所示的一棵比较大的树。这种树叫做小波分解树(waveletdecompositiontree)。分解级数的多少取决于要分析的数据和用户的需要。小波分解树表示只对信号的低频分量进行连续分解。如果不仅对信号的低频分量进行连续分解，而且对高频分量也进行连续分解，这样不仅可得到许多分辨率较低的低频分量。而且也可得到许多分辨率较低的高频分量。这样分解得到的树叫做小波包分解树(waveletpacketdecompositiontree)，这种树是一个完整的二进制树。图8-8表示的是一棵三级小波包分解树。小波包分解方法是小波分解的一般化，可为信号分析提供更丰富和更详细的信息。例如，小波包分解树允许信号S表示为

S=A1+AAD3+DAD3+DD2顺便要提及的是，在使用滤波器对真实的数字信号进行变换时，得到的数据将是原始数据的两倍。例如，如果原始信号的数据样本为1000个，通过滤波之后每一个通道的数据均为1000个，总共为2000个。于是，根据尼奎斯特(Nyquist)采样定理就提出了降采样(downsampling)的方法，即在每个通道中每两个样本数据取一个，得到的离散小波变换的系数(coefficient)分别用cD和cA表示。如图8-9所示。图中的符号表示降采样。小波重构离散小波变换可以用来分析或者叫做分解信号，这个过程叫做分解或者分析。把分解的系数还原成原始信号的过程叫做小波重构(waveletreconstruction)或者叫做合成(synthesis)，数学上叫做逆离散小波变换(inversediscretewavelettransform,IDWT)。 在使用滤波器做小波变换时包含滤波和降采样两个过程。在小波重构时要包含升采样(upsampling)和滤波过程。小波重构的方法如图8-10所示，图中的符号表示升采样。升采样是在两个样本数据之间插入“0”，目的是把信号的分量加长。升采样的过程如图8-11所示。重构过程中滤波器的选择也是一个重要的研究问题，这是关系到能否重构出满意的原始信号的问题。在信号的分解期间，降采样会引进畸变，这种畸变叫做混叠(aliasing)。这就需要在分解和重构阶段精心选择关系紧密但不一定一致的滤波器才有可能取消这种混叠。低通分解滤波器(L)和高通分解滤波器(H)以及重构滤波器(L’和H’)构成一个系统，这个系统叫做正交镜像滤波器(quadraturemirrorfilters,QMF)系统，如图8-12所示。小波定义在数学上，小波定义为对给定函数局部化的函数。小波可由一个定义在有限区间的函数ψ(x)来构造，ψ(x)称为母小波(motherwavelet)或者叫做基本小波。一组小波基函数，{ψa,b(x)}，可通过缩放和平移基本小波ψ(x)来生成，其中，a为进行缩放的缩放参数，反映特定基函数的宽度(或者叫做尺度)；b为进行平移的平移参数，指定沿x轴平移的位置。当a=2j和b=ia的情况下，一维小波基函数序列定义为：或者：本教材采用下面的表示法：其中，i为平移参数，j为缩放因子。函数f(x)以小波ψ(x)为基的连续小波变换定义为函数f(x)和ψa,b(x)的内积，在1984年，A.Grossman和Morlet连续小波的逆变换为：其中，Cψ为母小波ψ(x)的允许条件(admissiblecondition)，其中，是在平方可积的实函数空间L2(R)。为的傅立叶，而5.2一维哈尔小波变换哈尔小波是小波系列中最简单的小波。因此本节将从哈尔小波入手，首先介绍用来构造任意给定信号的哈尔基因数，然后介绍表示任意给定信号的哈尔小波函数，最后介绍函数的规范化和哈尔基的构造。基函数是一组线性无关的函数，可以用来构造任意给定的信号。例如，用基函数的加权和表示。最简单的基函数是哈尔基函数(Haarbisisfunction)。啥尔基函数在1909年提出，它是由一组分段常值函数组成的函数集。这个函数集定义在半开区间：[0,1)上，每一个分段常值函数的数值在一个小范围里是“1”，其他地方为“0”，现以图像为例并使用线性代数中的矢量空间来说明哈尔基函数。如果一幅图像仅由20＝1个像素组成．这幅图像在整个[0,1)区间中就是一个常值函数。用表示这个常值函数，用V0表示由这个常值函数生成的矢量空间，即这个常值函数也叫做框函数(boxfunction)，它是构成矢量空间V的基。如果一幅图像内21＝2个像素组成，这幅图像在[0,1)区间中有两个等间隔的子区间：[0,1/2)和[1/2,1)，每一个区间中各有1个常值函数，分别用表示。用V1表示由2个子区间中的常值函数生成的矢量空间，即这2个常值函数就是构成矢量空间V1

的基。如果一幅图像由2j＝22＝4个像素组成，这幅图像在[0,1)区间中被分成4个等间隔的子区间：[0,1/4),[1/4,1/2),[1/2,3/4),[3/4,1)，它们的常值函数分别用表示，用V2

表示由4个子区间中的常值函数生成的矢量空间。4个常值函数就是构成矢量空间V2的基。 可以按照这种方法继续定义基函数和由它生成的矢量空间。总而言之，为了表示矢量空间中的矢量，每一个矢量空间Vj

都需要定义一个基(basis)。为生成矢量空间Vj

而定义的基函数也叫做尺度函数，这种函数通常用符号 表示。哈尔基函数定义为哈尔基尺度函数定义为其中，j为尺度因子，改变j使函数图形缩小或者放大；i为平移参数，改变i使函数沿x轴方向平移。空间矢量Vj定义为：其中，sp表示线性生成(linearspan)。需要注意的是：有些文章使用负整数来定义尺度函数并且使用不同的符号规则。因此在阅读有关小波方面的文章时要注意作者使用的符号规则。由于定义了基和矢量空间，就可以把由2j个像素组成的一维图像看成为矢量空间Vj中的一个矢量。由于这些矢量都是在单位区间[0,1)上定义的函数，所以在Vj矢量空间中的每一个矢量也包含在Vj+1矢量空间中。这说明矢量空间Vj是嵌套的，即矢量空间Vj的这个性质可写成小波函数通常用 表示。与框函数相对应的小波称为基本哈尔小波函数(Haarwaveletfunctions)，并由下式定义：哈尔小波尺度函数定义为用小波函数构成的矢量空间用Wj表示根据哈尔小波函数的定义，可以写出生成W0，W1和W2等矢量空间的小波函数。用哈尔小波生成的矢量空间Wj包含在矢量Vj+1空间，这个性质用下式表示： 在小波变换中，有时要对基函数和小波函数进行规范化。在半开区间[0,1)中，如果函数的内积：则称和是规范化的函数哈尔基和哈尔小波分别使用下面两个式子进行规范化：

函数的规范化其中，常数因子2j/2用来满足标准内积(innerproduct)等于1的条件。如果小波函数不是在[0,1)区间中定义的函数，常数因子将改变。哈尔基的结构 使用哈尔基函数和哈尔小波函数生成的矢星空间Vj和Wj具有下面的性质：其中，符号“⊕”表示直和。这就是说，在矢量空间Vj+1中，根据所选择的内积，生成矢量空间Wj的所有函数与生成矢量空间Vj的所有函数都是正交的，即子空间Wj是子空间Vj的正交补。上式表明，在矢量空间Vj+1中，矢量空间Wj中的小波可用来表示一个函数在矢量空间Vj中不能表示的部分。因此，小波可定义为生成矢量空间Wj的一组线性无关的函数的集合。这些基函数具有两个重要件质：

(1)生成矢量空间Wj的基函数与生成矢量空间Vj的基函数构成矢量中间Vj+1的—个基。

(2)生成矢量空间Wj的每—个基函数与生成矢量空间Vj的每—个基函数正交。哈尔小波变换 小波变换的基本思想是用一组小波函数或者基函数表示一个函数或者信号，例如图像信号。为了理解什么是小波变换，下面用具体的例子来说明小波变换的过程。[例8.1]假设有一幅分辨率只有4个像素p0,p1,p2,p3的一维图像，对应的像素值或者叫做图像位置的系数分别为：

[9735]计算它的哈尔小波系数。计算步骤如下：步骤1：求均值。[84]步骤2：求差值。[841-1]步骤3：重复步骤1和2。

[621-1]求有限信号的均值和差值由此可见，通过上述分解就把由4个像素组成的一幅图像用一个平均像素值和3个细节系数表示，这个过程就叫做哈尔小波变换，也称哈尔小波分解。这个概念可以推广到使用其他小波基的变换。从这个例子中我们可以看到：(1)变换过程中没有丢失信息，因为能够从所记录的数据中重构出原始图像。(2)对这个给定的变换，可以从所记录的数据中重构出各种分辨率的图像。例如，在分辨率为1的图像基础上重构出分辨率为2的图像，在分辨率为2的图像基础上重构出分辨率为4的图像。(3)通过变换之后产生的细节系数的幅度值比较小，这就为图像压缩提供了一种途径。例如，去掉一些微不足道的细节系数并不影响对重构图像的理解。既： 在例8.1中，求均值和差值的过程实际上就是一维小波变换的过程，现在用数学方法重新描述小波变换的过程。

(1)用V2中的哈尔基表示 图像I(x)=[9735]有2j=22=4像素，因此可以用生成矢量空间V2中的框基函数的线性组合表示(2)用V1和W1中的函数表示根据因此，I(x)可表示为(3)用V0，W1和W2中的函数表示根据I(x)可表示成其中，4个系数c00,d00,d01,d11就是原始图像通过哈尔小波变换所得到的系数，用来表示整幅图像的平均值和不同分辨率下的细节系数。4个函数Φ00(x),Ψ00(x),Ψ01(x),Ψ11(x)就构成V2空间的基。规范化算法规范化的小波变换与非规范化的小波变换相比，唯一的差别是在规范化的小波变换中需要乘一个规范化的系数。下面用例8.2说明。[例8.2]对函数

f(x)=[2,5,8,9,7,4,-1,1]作哈尔小波变换。 哈尔小波变换实际上是使用求均值和差值的方法进行分解。把f(x)看成是矢量空间V3中的一个向量，尺度因子j=3,因此最多可分解为3层，如图8-22所示。fcA1cA2分解过程如下：步骤1：步骤2：步骤3：根据这个例子，可以归纳出规范化的哈尔小波变换的一般算法。假设一维阵列C有h个元素，h等于2的幂，执行一维哈尔小波变换的伪代码如下：procDecomposeArray(C:array[0…h-1]ofxolor):whileh>1do: h←h/2 fori←0toh-1do: C’[i]←(C[2i]+C[2i+1])/21/2 C’[h+i]←(C[2i]-C[2i+1])/21/2 endfor C←C’ endwhileendproc 5.3二维哈尔小波变换 前面已经介绍了一维小波变换的基本原理和变换方法。这节将结合具体的图像数据系统地介绍如何使用小波对图像进行变换。 已经知道，一幅图像可看成是由许多像素组成的一个大矩阵，在进行图像压缩时，为降低对存储器的要求，人们通常把它分成许多小块。例如，以8×8个像素为一块．并用矩阵表示，然后分别对每一个图像块进行处理。在小波变换中，由于使用的基函数的长度是可变的，虽然无需像以离散余弦变换(DCT)为基础的JPEG标准算法那样，把输人图像进行分块，以避免产生JPEG图像那样的“块效应”，但为便于理解小被变换的奥妙，还是从一个小的图像块入手，并且继续使用哈尔小波对图像进行变换。图像矩阵的计算假设有一幅灰度图像，其中的一个图像块用阵列A表示为一个图像块是一个二维的数据阵列，进行小波变换时可以对阵列的每一行进行变换，然后对行变换之后的阵列的每一列进行变换，最后对经过变换之后的图像数据阵列进行编码。在图像块阵列A中，第一行的像素值为：R0:[642361606757]N0:[3332333231-2927-25]N1:[32.532.50.50.531-2927-25]N2:[32.500.50.531-2927-25]使用求均值和求差值的方法，对矩阵的每一行进行计算，得到AR

：其中，每一行的第一个元素是该行像素值的平均值，其余的是这行的细节系数。使用同样的方法，对AR的每一列进行计算，得到ARC

：其中，左上角的元素表示整个图像块的像素值，其余是该图像块的细节系数。根据这个事实，如果从矩阵中去掉表示图像的某些细节系数，事实证明重构的图像质量仍然可以接受。具体做法是设置一个阈值δ，例如δ≤5的细节系数就把它当作“0”看待。这样经过变换之后的矩阵ARC就变成Aδ

：Aδ与ARC相比，“0”的数目增加了18个，也就是去掉了18个细节系数。这样做的好处是可提高小波图像编码的效率。对Aδ

矩降进行逆变换．得到了重构的近似矩阵：使用线性代数由于图像可用矩阵表示，使用3个矩阵M1，M2和M3同样可以对矩阵A进行求平均值和求差值。这3个矩阵分别是第1、第2和第3次分解图像时所构成的矩阵。现以矩阵A的第1行的数据为例，

[642361606757] 为简化计算，可把3个矩阵相乘之后再计算。3个矩阵相乘的结果为：W=M1M2M3=如果使用规格化的小波进行计算，则W=M1M2M3=以上计算哈尔小波正变换的步骤就简化成．

T=((AW)’W)’=(W’A’W)’=W’AW计算哈尔小波的逆变换简化为：

(W’)-1TW-1=A (W-1)’TW-1=A变换实例 为进一步理解小波变换的基本原理和在图像处理中的应用，可使用MATLAB软件中的小波变换工具箱(wavelettoolbox)编写小波变换程序，对原始图像进行分解和重构。 图8-25表示图像分解和重构过程。利用小波变换，用户可以按照应用要求获得不问分辨率的图像，如图8-26所示。图8-26(a)表示原始的Lena图像；图8-26(b)表示通过一级小波变换可得到1/4分辨率的图像；图8-26(c)表示通过二级小波变换可得到1/8分辨率的图像；图8-26(d)表示通过3级小波变换可得到1/16分辨率的图像。阈值处理可用于去除图像中的噪声。在取不同阈值的情况下重构图像，可观察到图像质量发生的变化。如图8-27所示。图8-27(a)表示原始的Lena图像；图8-27(b)表示阈值δ≤5的重构图像；图8-27(c)表示阈值δ≤10的重构图像，而图8-27(d)表示阈值δ≤20的重构图像。从图中可以看到。随着阈值的增大，图像质量也随之降低。二维小波变换方法用小波对图像进行变换有两种方法：一种叫做标准分解(standarddecomposition)，另一种叫做非标准分解(nonstandarddecomposition)。标准分解力法是指首先使用一维小波对图像每一行的像素值进行变换、产生每一行像素的平均值和细节系数；然后使用一维小波对这个经过行变换的图像的列进行变换．产生这个图像的平均值和细访系数。标准分解的过程如下：图8-28表示标准分解方法，图像是使用MATLAB编写的程序分解得到的。非标准分解是指使用一维小波交替地对每一行和每一列像素值进行变换。首先对图像的每一行计算像素对的均值和差值；然后对每一列计算像素对的均值和差值。这样得到的变换结果只有1/4的像素包含均值。再对这1/4的均值重复计算行和列的均值和差值。依此类推。非标唯分解的过程如下：图8-29表示非标准分解方法，图像是使用MATLAB编写的程序分解得到的。标准分解方法和非标准分解方法相比，它们得到的变换结果是完全相同的，只是非标准算法的计算量可以少一些。5.4小波图像编码由于小波变换技术在20世纪90年代初期已经比较成熟，因此从那时起就开始出现各称新颖的小波图像编码方法。这些编码方法包括EZW（embeddedzerotreewavelet,嵌入式零树小波算法），在EZW算法基础上改进的SPIHT（setpartitioninginhierarchicaltrees层树分集算法）和EBCOT（embeddedblockcodingwithoptimizedtruncation,最佳截断嵌入码块编码）等。由于EZW算法的开拓给后来者带来很大的启发，它是一种有效而且计算简单的图像压缩技术，因此本节将重点介绍。从子带编码到小波编码子带编码(subbandcoding,SBC)的基本概念是把信号的频率分成几个子带，然后对每个子带分别进行编码，并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代，子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点，20世纪80年代中期开始在图像编码中使用。1986年Woods,J.W.等科学家曾经使用一维正交镜像滤波器组(quadraturemirrorfilterbanks,QMF)把信号的频带分解成4个相等的子带，如图9-1所示。图9-1(a)表示分解方法，图9-1(b)表示其相应的频谱。这个过程可以重复，直到符合应用要求为止。这样的滤波器组称为分解滤波器树(decompositionfiltertrees)。多分辨率分析S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolutionanalysis)的概念。从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法，叫做Mallat算法。根据Mallat和Meyer等科学家的理论，使用一级小波分解方法得到的图像如图9—2所示。如果在一级分解之后继续进行分析，这种分解过程叫做多分辨率分析，实际上就是多级小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像，这些图像叫做多分辨率图像(multiresolutionimages)。图9-3表示Lena的多分辨率图像。其中，粗糙图像1的分辨率是原始图像的l/4，粗糙图像2的分辨率是粗糙图像1的1/4。滤波器组与多分辨率为了压缩语音数据，在1976年Croisier,Esteban和Galand介绍了一种可逆滤波器组(invertiblefilterbank)，使用滤波和子采样(subsampling)的方法用来把离散信号f(n)分解成大小相等的两种信号，并且使用叫做共轭镜像滤波器(conjugatemirrorfilters)的一种特殊滤波器来取消信号的混叠(aliasing)，这样可从子采样的信号中重构原始信号f(n)。这个发现使人们花费了10多年的努力来开发一套完整的滤波器组理论。正交小波的多分辨率理论(multiresolutiontheory)已经证明，任何共轭镜像滤波器都可以用来刻画一种小波ψ(t)，它能够生成L2(R)实数空间中的正交基，而且快速离散小波变换可以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示了数字信号处理和谐波分析之间关系，这就便人们一直在致力于解决它们之间的关系问题。从子带编码到小波编码在过去的年代里，人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波编码(waveletcoding,WC)技术的旗号下，人们提出了许多与子带编码技术非常类似和密切相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的小波基函数系列可以在连续的时间域中构造，但如何在离散的时间域中构造是一个现实问题。在众多的研究者中，Inrid

Daubechies在离散的时间域中构造小波基函数方而做出了杰出的贡献。她于1988年最先揭示了小波变换和滤波器组之间的内在关系：离散时间滤波器(discrete-timefilters)或者正交镜像滤波器(quadraturemirrorfilter,QMF)可以被叠代，并在某一种匀称(regularity,可粗略理解为函数的平滑性)条件下可获得连续小波。这是一个非常实际和极其有用的发现，意味着可使用有限冲击响应(finiteimpulseresponse,FIR)的离散时间滤波器来执行小波分解，使用相同的滤波器可重构小波分解之后的信号。由此可见，早期开发的子带编码实际上是一种小波变换。在Daubechies揭示小波变换和滤波器组之间的关系之前，在图像编码中小波技术并不流行。从20世纪90年代开始，Cohen,Daubechies和Feauveau,简称为CDF,系统地开发了构造紧支持双正交小波(compactlysupportedbiorthogonalwavelets)的方法，以及其他学者提出的各种算法，使小波技术在图像编码中得到广泛的应用。在构造小波和开发小波变换算法中，比利时成长的年轻学者WimSweldens在1994年的博士论文中首先提出了“TheLiftingScheme”，简称Lifting/lifting(提升法)。该方法的基本思想是首先把信号分成偶数号样本和奇数号样本。根据信号本身的相关性，奇数样本使用偶数样本进行预测，由预测丢失的信号叫做信号的细节信息，然后调整偶数样本以保存原始信号的粗糙信息和细节信息。该方法保留了小波分析的特性(时间频率局部化和快速计算)，通过放弃小波的平移和缩放，并且放弃用傅立叶分析来构造小波，从而解决了非无限信号或者非周期信号的小波和小波变换问题。也使计算速度得到很大的提高，因此被称为第二代小波(secondgenerationwavelets)，现在也成为制定JPEG2000标准中小波部分的基础。小波分解图像方法使用小波变换把图像分解成各种子带的方法有很多种。例如，均匀分解(uniformdecomposition)，非均匀分解(non-uniformdecomposition)，八带分解(octave-banddecomposition)和小波包分解(wavelet-packetdecomposition)，根据不同类型的图像选择不同小波的自适应小波分解(adaptivewaveletdecomposition)等。其中，八带分解是使用最广泛的一种分解方法。这种分解方法属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分解的高频部分不再进一步分解。图9-4表示Lena图像的数据分解。失真的度量方法 在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比(peaksignaltonoiseratio,PSNR)来衡量，定义为最大像素值与均方差(meansquareerror,MSE)之比，对8位二进制图像，其中，其中，为原始图像的像素值，为解压缩之后的像素值。 在文献中，评估编码系统性能还使用其他方法。这些方法包括使用规格化均方差(normalizedmeansquareerror,NMSE)、信号噪声比(signaltonoiseratio,SNR)和平均绝对误差(meanabsoluteerror,MAE)来度量，分别定义为：其中，为原始图像的像素值，为解压缩之后的像素值。在电子工程中，信号噪声比(SNR)一直是最流行的误差度量指标，在大多数情况下可提供很有价值的信息，在数学上也比较容易计算。信号噪声比虽然也用在图像编码中，但由于它的数值与图像编码系统中高压缩比的关系不容易体现，因此提出了其他的几种度量方法，包括平均主观评分(meanopinionscore，MOS)。5.4.1EZW编码在1992年，Lewis,A.S.和Knowles,G.首先介绍了一种树形数据结构来表示小波变换的系数。在1993年，Shapiro,J.M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(embeddedzerotreewavelet,EZW)算法。EZW主要用于与小波变换有关的二维信号的编码、但不局限于二维信号。嵌入(式)零树小波中的“小波”是指该算法以离散小波变换为基础，以大的小波变换系数比小的小波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实为背景。“零树”是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法。每一级分解都会产生表示图像比较租糙(低频图像)和比较精细(高额图像)的小波系数；在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(threshold)，那么这棵树就叫做零树。“嵌入”是渐进编码(progressiveencoding)技术的另一种说法。其含义是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像，图像合成的过程与分解的过程相反，使用子图像生成许辨率不同的图像。EZW编码指的是，按照用户对图像分辨率的要求，编码器可以进行多次编码；每进行一次编码，阈值降低1/2，水平和垂直方向上的图像分辨率各提高1倍。编码从最低分辨率图像开始扫描，每当遇到幅度大于阈值的正系数就用符号P表示，幅度的绝对值大于阈值的负系数用符号N表示，树根节点上的系数幅度小于阈值而树枝中有大于阈值的非零树用符号Z表示，零树用符号T表示。小波图像编码(waveletimagecoding)的一般结构如图9-5所示，它主要由小波变换(wavelettransform)、量化(quantization)和熵编码(entropyencoding)等3个模块组成。小波变换不损失数据，但它是EZW算法具有渐进特性的基础；量化模块对数据会产牛损失，数据损失的程度取决于量化阈值的大小，EZW算法指的就是这个模块的算法，它的输出是符号集{P,N,T,Z,0,1}中的一系列符号；熵编码模块对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流(codestream)小于输入的码流。EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次，生成一种分辨率图像，编码一次叫做一遍扫描。每一遍扫描大致包含3个步骤：设置阈值、每个小波系数与阈值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表，一种是小波系数的符号表，另一种是量化表。零树回顾二维小波变换的计算过程，不难想象各级子图像中的系数是相关的。在说明零树的概念之前，需要对小波变换得到的系数名称和符号加以说明。现以3级分解的离散小波变换为例，图9-6表示Lena图像使用三级滤波器组做小波变换输出的子图像(subimage)。需要注意的是：分解之后的图像的名称在文献上有很多种，除了子图像之外，有的叫做子带图像(sub-bandimage)，有的把子图像进一步区分为高频子图像和低频子图像，或者粗糙图像和精细图像等名称。这些名称从不同的角度反映图像的特性，在不同的场合下使用可以收到异曲同工的效果。图9-6中的数字1，2和3表示分解的级数编号，LL3表示第3级的低频子图像，在这个例子中，它是分辨率最低的子图像。HL3表示第3级分解在水平方向上的子图像，LH3表示第3级分解在垂直方向上的子图像，HH3表示第3级分解在对角线方向上的子图像，其他的组合符号依此类推。由于低频于图像的系数要比高频子图像的系数大，零树编码技术就是利用这个事实来设计编码／解码过程中每一级使用的量化器。各级子图像中的系数之间的关系可以用树的形式描述。如图9-7(a)所示，最低频率的子图像在左上角，最高频率的子图像在右下角，由同一方向和相同空间位置上的所有小波系数组成一棵树。例如，从第3级子图像HH3、第2级子图像HH2到第1级子图像HH1的相应位置上的所有系数构成一棵下降树。按箭头所指的方向，各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼。举例来说，LL3的系数为{63}，HH2和HH1中的系数分别为{3}和{4,6,3,-2}，由这些系数构成的树如图9-7(b)所示。如果把{63}指定为父系数,{3}就称为子系数，而{4,6,3,-2}中的4个系数就称为孙系数。现在再来看零树的概念。为便于比较，把图9-7(b)所示的两棵树用图9-8(a)和图9-8(b)表示。假设编码时开始的阈值T0＝32，由于63比32大，这样的树叫做非零树，如图9-8(a)所示。假设下一次编码时的阈值T1＝16，把-13当作父系数，它的幅度比16小，而它的所有4个子系数的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图9-8(b)所示。根据以上的分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。 顺便要指出的是，小波图像系数结构的形式不只是上面介绍的一种，也可能不是最好的一种。扫描方法EZW算法对小波系数进行编码的次序叫做扫描。扫描子图像系数的方法有两种：一种叫做光栅扫描(rasterscan)，如图9-9(a)所示；另一种叫做迂回扫描(mortonscan)，如图9-9(b)所示。算法EZW算法可归纳为下面几个主要步骤。(1)阈值T的选择开始时的阈值T0通常按下式估算，其中，MAX(.)表示最大的系数值，Xi表示小波变换分解到第i级时的系数。以后每扫描一次，阈值减少一半。(2)给系数分配符号使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第一种扫描叫做主扫描(dominantpass)，它的任务是把小波系数X与阈值T进行比较，然后指定表9-1中的4个符号之一，笔者把这种符号叫做系数符号，对整幅图像扫描之后产生系数符号序列。第二种扫描叫做辅扫描(subordinatepass)，其任务是对主扫描取出的带有符号P或者N的系数进行量化，产生代表对应量化值的符号“0”和“1”，笔者把这种符号称为量化符号。主扫描：扫描每一个系数以产生系数符号。

(1)如果系数幅度大于阈值(T)且为正数，输出符号P(positive)，

(2)如果系数幅度的绝对值大于阈值(T)且为负数，输出符号N(negative)，

(3)如果系数是零树根，输出T(zerotree)，

(4)如果系数幅