小波分析及其应用53579

1、 第八章小波分析及应用8.1 引言把函数分解成一系列简单基函数的表示，无论是在理论上，还是实际应用中都有重要意义。1822年法国数学家傅里叶(J. Fourier 1768-1830)发表的研究热传导理论的“热的力学分析”，提出并证明了将周期函数展开为正弦级数的原理，奠定了傅里叶级数理论的基础1。傅里叶级数理论研究的是把函数在三角函数系下的展开，使得对信号和系统的研究归结为对简单的三角函数的研究。傅里叶级数与傅里叶变换共同组成了平常所说的傅里叶分析2。傅里叶级数用于分析周期性的函数或分布，理论分析时经常假定周期是，定义如式(8.1-1)、(8.1-2)， (8.1-1)其中 (8.1-2)然而

2、，被分析函数的性质并不能完整地由傅里叶系数来刻划，这里有一个例子来说明3：从任一个平方可和的函数出发，为了得到一个连续函数，只需或者增大f(x)的傅里叶系数的模，或者保持它不变并适当地改变系数的位相。因此，不可能仅根据傅里叶系数大小的阶就预知函数的性质（如大小、正则性）。傅里叶变换的定义如式(8.1-3)、(8.1-4) (8.1-3) (8.1-4)通过引入广义函数或分布的概念，可获得奇异函数（如冲击函数）的傅里叶变换的存在。对于时域的常量函数，在频域将表现为冲击函数，表明具有很好的频域局部化性质。由式(8.1-3)可知，为了得到，必须有关于f(x)的过去和未来的所有知识，而且f(x)在时域

3、局部值的变化会扩散到整个频域，也就是的任意有限区域的信息都不足以确定任意小区域的f(x)。在时域，哈尔(Haar)基是一组具有最好的时域分辨能力的正交基，它在时域上是完全局部化的，但在频域的局部化却很不好，这是由于哈尔系的两个缺点：缺乏正则性与缺乏振动性。研究者们希望寻找关于空间变量（或时间变量）与频域变量都同时好的希尔伯特(Hilbert)基，R. Balian认为：“在通讯理论中，人们对于在完全给定的时间内，把一个振动信号表示成由其中每一个都拥有足够确定的位置与有一个频率的小波的叠加这件事感兴趣。事实上，有用的信息常常同时被发射信号的频率与信号的时间结构（如音乐）所传递。当把一个信号表达成

4、时间的函数时，其中的频谱表现并不好；相反地，信号的傅里分析却显示不了信号每一分量发射信号的瞬时与持续时间。一个适当的表示应结合这两者互补描述的优点，并用一个离散的刻划来表示，以适应通讯理论3。”为此，人们提出了短时傅里叶变换（STFT）的概念：定义8.1-1若选择得使W与它的傅里叶变换满足：那么使用W作为窗函数，在式(8.1-5)中引入的窗口傅里叶变换称为“短时傅里叶变换”(STFT)： (8.1-5)当窗函数选择为高斯(Gaussian)函数时，则为Gabor变换2。STFT的缺点是分析窗的大小和形状是恒定的。因为频率与周期成反比，所以反映信号的高频成份需要窄的时间窗，而反映信号的低频成份需

5、要宽的时间窗，STFT无法满足要求，此外，STFT的冗余很大，增加了不必要的计算量。小波变换作为能随频率的变化自动调整分析窗大小的分析工具，自八十代中期以来得到了迅猛的发展，并在信号处理、计算机视觉、图像处理、语音分析与合成等众多的领域得到应用。小波分析方法的出现可以追溯到1910年Haar提出Haar规范正交基，以及1938年Littlewood-Paley对傅里叶级数建立的L-P理论。为克服传统傅里叶分析的不足，在八十年代初，便有科学家使用“小波”的概念来进行数据处理，比较著名的是1984年法国地球物理学家Morlet引入小波的概念对石油勘探中的地震信号进行存贮和表示。在数学方面所做的探索

6、主要是R. Coifman和G. Weiss创立的“原子”和“分子”学说，这些“原子”和“分子”构成了不同函数空间的基的组成部分。L. Carleron使用了非常象“小波”的函数构造了Stein和Weiss的空间的无条件基。直到1986年，法国数学家Meyer成功地构造出了具有一定衰减性的光滑函数，它的二进伸缩与平移构成的规范正交基。此前，人们普遍认为这是不可能的，如Daubechies,Grossman和Meyer都退而研究函数系构成的框架的条件去了。Lemarie和Battle继Meyer之后也分别独立地给出了具有指数衰减的小波函数。1987年，Mallat利用多分辨分析的概念，统一了这之

7、前的各种具体小波的构造，并提出了现今广泛应用的Mallat快速小波分解和重构算法。1988年Daubechies构造了具有紧支集的正交小波基。Coifman, Meyer等人在1989年引入了小波包的概念。基于样条函数的单正交小波基由崔锦泰和王建忠在1990年构造出来。1992年A. Cohen, I. Daubechhies等人构造出了紧支撑双正交小波基。同一时期，有关小波变换与滤波器组之间的关系也得到了深入研究。小波分析的理论基础基本建立起来。近年来，一种简明有效的构造小波基的方法-提升方案(Lifting Scheme)得到很大的发展和重视4,5。利用提升方案可把现存的所有紧支撑小波分解

8、成更为基本的步骤6，另外，它还为构造非线性小波提供了一种有力的手段，所以，利用提升方案构造的小波被认为是第二代小波5。小波理论及其应用仍然处在发展中，其未来将在非线性多尺度方法、非规则集上的小波构造以及非平稳、非均匀、时变信号处理等方面等到更深入的研究。8.2 小波变换及其基本性质连续小波变换，的连续小波变换（有时也称为积分小波变换）定义为： (8.2-1)或用内积形式：(8.2-2)式中要使逆变换存在，要满足允许性条件： (8.2-3)式中是的傅里叶变换。这时，逆变换为 (8.2-4)这个常数限制了能作为“基小波（或母小波）”的属于的函数的类，尤其是若还要求是一个窗函数，那么还必须属于，即故

9、是R中的一个连续函数。由式(8.2-3)可得在原点必定为零，即 (8.2-5)从式(8.2-5)可以发现小波函数必然具有振荡性。连续小波变换具有如下性质：性质1（线性）：设，则性质2（平移不变性）：若，则。平移不变性是一个很能好的性质，在实际应用中，尽管离散小波变换要用得广泛一些，但在需要有平移不变性的情况下，离散小波变换是不能直接使用的。性质3（伸缩共变性）：若，则，其中c>0。性质4（冗余性）：连续小波变换中存在信息表述的冗余度。其表现是由连续小波变换恢复原信号的重构公式不是唯一的，小波变换的核函数存在许多可能的选择。尽管冗余的存在可以提高信号重建时计算的稳定性，但增加了分析和解释小

10、波变换的结果的困难。连续小波变换的离散化由于连续小波变换存在冗余，因而有必要搞清楚，为了重构信号，需针对变换域的变量a ，b进行何种离散化，以消除变换中的冗余，在实际中，常取，这时常简写为：。变换形式为：为了能重构信号，要求是的Riesz基。定义8.2-1一个函数称为一个R函数，如果在下述意义上是一个Risez基：的线性张成在中是稠密的，并且存在正常数A与B，使对所有二重双无限平方可和序列成立，即对于的成立。假定是一个R函数，那么存在的一个唯一的Riesz基，它在意义上与对偶。这时，每个有如式(8.2-6)的唯一级数表示： (8.2-6)特别地，若构成的规范正交基时，有重构公式为： (8.2-

11、7)8.3 多分辨分析与Mallat算法8.3.1 多分辨分析Mallat使用多分辨分析的概念统一了各种具体小波基的构造方法，并由此提出了现今广泛使用的Mallat快速小波分解和重构算法，它在小波分析中的地位与快速傅里叶变换在傅里叶分析中的地位相当7。定义8.3-1空间的多分辨分析是指构造该空间内一个子空间列，使其具有以下性质：（1） 单调性（包容性）（2） 逼近性：（3） 伸缩性：（4） 平移不变性：（5）Riesz基存在性：存在，使得构成的Riesz基。在定义8.3-1中，对应于分辨率，在有些文献中2,8，对应于分辨率，这时，性质（1）、（3）中子空间的下标要做相应的变化。定理8.3-1

12、令是空间的一个多分辨分析，则存在一个唯一的函数使得 (8.3-1)必定是内的一个标准正交基，其中称为尺度函数。式(8.3-1)中的系数是为了使的范数为1。引入尺度函数的目的是为了构造正交小波基，图8.3-1(a)为一指数衰减、连续可微分的尺度函数，图(b)是其傅里叶变换。显然，尺度函数与低通滤波器的形状相同。(a)尺度函数的图形(b)尺度函数的傅里叶变换图8.3-1 DB9尺度函数若生成一个多分辨分析，那么也属于，并且因为是的一个Riesz基，所以存在唯一的序列，它描述尺度函数的两尺度关系： (8.3-2)由性质（1）可知，所以 (8.3-3)反复应用式(8.3-3)，得 (8.3-4)同样，

13、象生成一样，存在一个函数生成闭子空间，且有与式(8.3-2)类似的双尺度方程 (8.3-5)式(8.3-5)称为小波函数双尺度方程。由式(8.3-2)、(8.3-5)可知，尺度函数与小波函数的构造归结为系数的设计，若令，则把尺度函数和小波函数的设计可以归结为滤波器的设计。构造正交小波时滤波器与必须满足以下三个条件： (8.3-6) (8.3-7) (8.3-8)联合求解式(8.3-7)和(8.3-8)可得 (8.3-9)由式(8.3-9)立刻可得 (8.3-10)所以，要设计正交小波，只需要设计滤波器。正交小波变换式(2.2-7)式说明由一个函数的平移和伸缩所构成的正交基在对信号进行分解和重构

14、方面是十分有用的。问题是这样的单个小波母函数是否存在呢？若存在是什么样的呢？这样的小波母函数是存在的，节的多分辨分析给出了具体的构造方法，下面先给出几个具有解析表达式的例子9。Haar小波母函数：Shannon小波母函数：Shannon小波母函数是无限次可导的，这比存在不连续点的Haar小波母函数要优越，可是Haar系函数的支集是紧的，Shannon系的函数不仅不是紧支的，且当时趋于零的速度仅为，故当用Shannon系对函数进行分解时，分解系数不能很好地反映信号的局部特征。Haar小波的缺点是不连续，利用卷积的方法可以将它变得光滑起来，通过正交化方法，这就构成了由B样条函数所生成的正交小波函数

15、。崔锦泰详细研究了用基数-B样条函数构造小波的方法2。下面式(8.3-11)给出一个用B样条构造的正交小波母函数的例子，是用频域表示的，理论上其时域表示可通过傅里叶反变换获得，不过实际中只能通过数值运算获得其时域的函数图形。 (8.3-11)Daubechies构造了目前实际应用中大量使用的具有有限支集的正交小波基，其对应的滤波器是有限长的10。不过无论是频域还是时域，它们都没有显式的表达式，而且，除Haar基外所有其他正交紧支的小波函数、尺度函数关于实轴上的任何点都不具有对称或反对称性，因而所对应的滤波器都不具有线性相位。下面是Daubechies小波滤波器的一个例子D4：。更多的例子请参见

16、附录。8.3.3 双正交小波变换在图像处理中经常希望所用滤波器具有线性相位，Cohen、Daubechies等人放弃了小波、尺度函数的正交性，给出了构造具有对称性的双正交基的方法，这时对应的滤波器具有线性相位11。取代小波函数、尺度函数的正交性的是所谓的双正交条件： (8.3-12) (8.3-13)此时相应的多分辨分析子空间的嵌套序列分为两种： (8.3-14)在双正交的条件下，子空间与不是正交补空间，但是若令则有以下正交补的关系： (8.3-15)相应的双尺度方程为： (8.3-16)依据式(8.3-15)得 (8.3-17)所以，在设计双正交小波滤波器时，实际上只要设计两个尺度滤波器。有

17、关双正交小波滤波器的例子请参见附录。8.3.4 小波包变换短时傅里叶变换是一种等分析窗的分析方法，小波变换相当于等Q滤波器组，语音、图像比较适合用小波变换进行分析，但并非所有信号的特性都与小波变换相适应。以雷达为例，复杂目标的回波，其包络的起伏决定于目标的姿态变化，而多谱勒频率则取决于目标的径向速度，二者并无必然的联系，所以在雷达里也经常使用短时傅里叶变换。当对某类信号，等宽和等Q滤波器都不一定适用时，有必要按信号特性选用相应组合的滤波器，这就引出了小波包的概念。Coifman及Wickerhauser在多分辨分析的基础上提出了小波包的概念，可以实现对信号任意频段的聚焦。小波包的基本思想是对多

18、分辨分析中的小波子空间也进行分解，具体做法是：令 (8.3-18)定义子空间是函数的闭包空间，而是函数的闭包空间，并令满足如下双尺度方程： (8.3-19) (8.3-20)式中即两系数也具有正交关系。其等价表示是： (8.3-21)定义8.3-2（小波包）：由式(8.3-19)、(8.3-20)构造的序列称为由基函数确定的小波包。空间分解的子空间列可以写成，。若n是一个倍频程细划分的参数，即令，则有小波包的简略记号，其中。与小波相比较可知，小波包除了离散尺度和离散平移之外，还增加了一个频率参数n，正是由于这个频率参数的作用，使得小波包克服了小波时间分辨率高时频率分辨率差的缺点。n表示的零交叉

19、个数，也就是其波形的振荡次数。 8.3.5 一维Mallat算法Mallat在著名的用于图像分解的金字塔算法(Pyramidal algorithm)的启发下，结合多分辨分析，提出了信号的塔式多分辨分解与综合算法，常简称为Mallat算法。设，并假定已得到在分辨率下的粗糙象，构成的多分辨分析，从而有，即 (8.3-22)式中，于是 (8.3-23)由尺度函数的双尺度方程可得利用尺度函数的正交性，有 (8.3-24)同理由小波函函数的双尺度方程可得 (8.3-25)由式(8.3-23)、(8.3-24)和(8.3-25)立即可得： (8.3-26) (8.3-27) (8.3-28)引入无穷矩阵

20、，其中则式(8.3-26)、(8.3-27)和(8.3-28)可分别表示为： (8.3-29)和 (8.3-30)其中分别是H和G的共轭转置矩阵。式(8.3-29)为Mallat一维分解算法，式(8.3-30)为Mallat一维重构算法，如图8.3-2所示： H H H G G G(a)分解算法(b)重构算法图8.3-2 Mallat小波分解和重构算法示意图利用Mallat分解与重构算法进行信号处理时，不必知道具体的小波函数是什么样的，此外，在对数字信号进行处理时，通常假定相应的连续函数属于，但即使如此，该函数在空间的投影的系数与由采样得到的离散序列一般不一样，但实际上都是直接把由采样得到的信

21、号作为最高分辨率的信号来处理，这时更多的是把小波变换当作滤波器组来看待。在实际应用Mallat算法时，由于实际信号都是有限长的，存在如何处理边界的问题。比较常用的方法是周期扩展和反射扩展。主要目的是要降低边界不连续性所产生的在边界上变换系数衰减慢的问题。8.3.6 二维Mallat算法 在进行图像处理时要用到二维小波变换，目前研究中主要以可分离小波为主，下面的定理给出了构造二维可分离正交小波基的方法。定理8.3-112令是的可分离多分辨分析，并令是相应的二维尺度函数，是与尺度函数对应的一维标准正交小波。若定义三个“二维小波” (8.3-31)则 (8.3-32) 分别是内的标准正交基。设为待分

22、析的图像信号，其二维逼近图像为 (8.3-33)式中 (8.3-34)利用尺度函数和小波函数的正交性，由式(8.3-32)、(8.3-33)和(8.3-34)立即得 (8.3-35)以及 (8.3-36)引入矩阵算子，令和分别代表用尺度滤波器系数对阵列的行和列作用的算子，和分别表示用小波滤波器系数对行和列作用的算子，二维Mallat分解算法为 (8.3-37)二维Mallat重构算法为： (8.3-38)图8.3-3示出了二维图像的分解和重构算法： 对行滤波 对列滤波 G 2 1 G 2 1 H 2 1 G 2 1 H 2 1 H 2 1 (a) 分解算法示意图 1 2 G 1 2 G 1 2

23、 H 1 2 G 1 2 H 1 2 H (b) 重构算法示意图图例 2 1 下采样：对列滤波时，两列去一列，对行滤波时，两行去一行 1 2 上采样：对列滤波时，两列中加0，对行滤波时，两行中加0图8.3-3 二维Mallat小波分解和重构算法示意图对图2.2-3所示的二维小波分解与重构算法，利用其可分离特性，在算法实现时分别由对行进行一维小波变换，然后再对按行变换后的数据按列进行一维小波变换来完成。与一维的情形类似，在实际应用中，由于图像信号总是有限区域的，也存在如何处理边界的问题。典型的处理方法是周期扩展和反射扩展。在用小波变换进行图像压缩时，由于边界的不连续性，会使得在边界处的小波变换系

24、数的衰减变慢，从而影响图像的压缩比，因而在图像压缩应用中，若使用的是具有对称性质的双正交小波滤波器，一般对边界采用反射扩展的方式，使边界保持连续，以提高压缩性能。8.4 利用提升方案(Lifting Scheme)构造小波8.4.1提升方案的基本原理小波函数通常定义为一个属于空间的母小波的二进伸缩(Dilates)和平移(Translate)： (8.4-1)这样的小波称为第一代小波。然而，在更一般的情况下，小波并不必须是彼此的伸缩与平移，但仍然具有第一代小波的特点，这样的小波称为第二代小波，利用提升方案可以构造它们。第一代小波具有如下性质：P1：是空间的Riesz基，还是Lebesgue、L

25、ipschitz、Sobolev和Besov空间的无条件基。P2：小波及其对偶在空间和频域是局域化的，有些小波还是紧支的。P3：小波分析可纳入多分辨分析的框架，这导致了快速小波变换算法。在研究中常有如下需要：G1：第一代小波提供了定义在上函数的基，但在象数据分割、在一般定义域上的微分和积分方程的求解，需要定义在任意的、可能不光滑的域上的小波。G2：第一代小波典型地只提供具有不变测度的空间的基，而微分方程的对角化、在曲线或表面上的分析等需要可适应加权测度的基。G3：第一代小波隐含对数据进行规则采样，而实际问题经常要处理不规则采样的数据。具有性质P1-P3而又满足G1-G3性质的第一代小波的推广称

26、为第二代小波。这儿的关键问题是平移与伸缩并不是属性P1-P3所必须的，放弃平移和伸缩，隐含着傅里叶变换不能再用作构造工具。下面介绍利用提升方案构造第二代小波的方法。考虑信号，把X分成二个不相交的集合：偶下标采样和奇下标采样，通常情况下这两个集合是紧密相关的，因而从一个集合能很好地建立另一个集合的预测P (8.4-2)知道了d和奇采样值，可立即恢复信号 (8.4-3)若P性能好，则d将是一个稀疏集，换言之，我们期望d的一阶熵小于的。令取 (8.4-4)利用相邻两偶采样对奇采样进行预测，记下差值 (8.4-5)若信号是相关的，则大多数小波系数将很小。在理论上，我们可以继续通过对施加以上操作，然而，

27、上述简单的操作性能并不好，为此引入另一个条件，即希望系数的平均值在每一次分解时保持一致，或者说使，此前所进行的下采样很显然不具有这种特点，我们可通过借助于对进行提升来实现这点： (8.4-6)现在，每一级小波变换由两步构成：首先计算小波系数，其次提升下采样系数。逆变换可立即得到：只需把式(8.4-6)中的加号换成减号，再把式(8.4-5)的等式中的项作一下移动即可。整个计算过程如图8.4-1所示：(a) 小波系数的几何含义 -1/2 -1/2 -1/2 -1/2 1/4 1/4 1/4 1/4 (b) 分解过程图8.4-1 提升方案示意图从图8.4-1中可以看出，在进行小波变换时，可进行同址运

28、算，即不需要辅助存储器，这对硬件实现十分有利。下面的定理给出提升方案的一般方法。定理8.4-1给定双正交滤波器算子的初始集合，那么可通过如下方法获得一个新的双正交滤波器算子集式中是一个从到的算子。证明：利用矩阵形式表示提升方案因为 有 根据双正交滤波器的定义有所以 (8.4-7)另外 (8.4-8)根据定义，满足式(8.4-7)(8.4-8)两式的即为双正交滤波器。 证毕。把小波变换分解成基本的提升步骤6已经证明所有FIR小波滤波器都有能分解成基本的提升步骤6。用矩阵表示时，一个提升步骤对应一个单元(elementary)矩阵。分解的基本理论依据是矩阵代数，根据矩阵代数，任何具有多项式元素项且

29、行列式为1的矩阵都可以分解成一系列的单元矩阵。首先把求自然数的最大公约数的Euclidean算法推广到求两个多项式的最大公因子。两个多项式的公因子取决于因子,而且与自然数不同的是，在多项式的情形下，解并不是唯一的。定理8.4-2 （多项式的Euclidean 算法）。设有两个多项式和，而且。令，从i=0开始循环执行以下步骤那么，如果n是使得的最小数。定理中定义为：若，则。用矩阵形式表示为相应地式中。这样，能整除、，如果是一个单项式的话，那么是互素的。为了把FIR小波滤波器(h, g)分解成基本的提升步骤，我们首先注意到必须是互素的78，而且，利用公约数的不唯一性，总是可以使公约数为常量K，即对

30、于给定的滤波器h，通过如下操作，总可以找到一个互补滤波器，即令 (8.4-9)在式(8.4-9)中 (8.4-10)当i为奇时使用式(8.4-10)的第一个等式，当i为偶时使用第二个等式，有 (8.4-11)通过一个提升步骤可获得滤波器g，由以上分析可得如下定理定理8.4-3给定互补滤波器对(h, g)，那么总是存在多项式和，以及一个常量K，使得与对偶滤波器对相关的多相(polyphase)矩阵为在正交小波滤波器时有，这就对应着两种不同的分解，也就是说，把FIR小波滤波器分解成基本的提升步骤时，分解是不唯一的。利用提升方案进行的小波变换如图8.4-2所示：2 1 1/K LP z 1 2 K

31、HP(a)利用提升方案进行的小波分解示意图 LP K + + 1 2+ HP 1/K + + 1 2 (b) 利用提升方案进行的小波重构示意图图8.4-2 利用提升方案进行分解与重构作为例子，下面给出对具有两阶消失矩的D4正交小波的分解：其中多相矩阵是因式分解是 (8.4-12)使用式(8.4-12)作为P(z)的分解，则分析用的多相矩阵为由此可得小波分解算法由分解算法，通过反向进行操作，并改变相应的符号可得重构算法利用提升方案进行小波变换具有可进行同址运算优点，这样在具体实现时可省去大量在存贮器开销，在进行图像处理时，这个优点更为明显。它的另一个优点是可提高小波变换的速度。所以把现存的有限长

32、小波滤波器分解成基本的提升步骤，可加快小波变换的进行，根据Daubechies的分析，随滤波器长度的增加，运算速度趋于常规小波变换的2倍，换言之，在同等的硬件条件下，对一维小波变换而言，运算时间降低一半，对二维小波变换则降为原来的四分之一。这个优点在实时性要求比较高的场合有很大的实用价值。整数小波变换13提升方案为扩展小波变换的应用领域提供了更多的灵活性。常规的小波变换都是采用浮点运算的，但利用提升方案所带来的便利，可十分方便地构造整数到整数的小波变换。将整数小波变换用于图像压缩就可以用小波变换进行无失真的图像压缩。最早的整数到整数小波变换是S变换，是哈尔（Haar）变换的整数形式： (8.4

33、-13)Said和Pearlman提出了S+P( tranSform + Prediction)，就是在S变换之后，利用低通滤波器的系数来产生一个新的高通滤波器系数，它的一般形式是： (8.4-14)式中。S和S+P变换的逆变换由式(8.4-13)、(8.4-14)把执行顺序变动一下，再改变一下相关项的符号就可以获得。通常小波滤波器的系数都是浮点数，只能把整数映射成浮点数，要进行无失真变换，必须构造把整数映射成整数的小波变换，提升方案（Lifting scheme）为此提供了一种有效的方法，所有正交或双正交小波滤波器，用提升方案进行分解后，都可用与S+P类似的方式来构造变换的整数版本。用提升方

34、案构造小波变换有如下优点：1） 同址计算：即不需要辅助存储器，原信号（图像）可被小波变换的结果覆盖。2） 更快的小波变换：传统上，快速小波变换首先把信号分解成高通和低通成份，并进行下抽样，然后对低通成份重复进行该过程直到所需要的变换级数。提升方案可把变换速度提高1倍。3） 不需借助傅氏分析便可获得逆变换。实际上，只要简单地调整一下正变换中的正负号即可。此优点使得不需要很强的傅氏分析的背景便可理解小波的特性和小波变换。S-变换的逆变换非常容易得到： (8.4-15)表8.4-1列出了几个常用的可逆整数到整数小波变换。表8.4-1 可逆整数小波变换NameWavelet Transform(4,4

35、)(2+2,2)D4(9,7)表中(4,4)表示分析小波和综合小波的消失矩(Vanishing Moments)均为4。(2+2,2)表示通过一个额外的提升步骤使(2,2)变换的消失矩增加到4。D4是常见的4系数紧支撑Daubechies正交小波变换的整数变换形式。(9,7)是常用于图像压缩的7/9小波变换的整数形式，它的分析和综合滤波器的消失矩也都为4。8.5小波图像编码8.5.1 小波变换图像编码的基本框架当前所有常规小波编码器都是变换编码形式，主要由三部分构成：解相关变换过程、量化过程和熵编码过程,下面分别进行描述。.1 解相关变换过程首先要解决的问题是小波基的选择。但是，对于图像编码，

36、很难确定哪种小波基是最优的，因为诸如光滑性、小波基支撑的尺寸以及频率选择性等指标都很重要，在不同的要求下会产生不同的结果。另外，现在几乎所有的小波编码器采用的都是可分离二维小波变换，这使得可把二维小波基的设计转化为一维小波基本的设计，由于可分离性所具有的局限，有理由认为不可分离二维小波基将更为有效。在最优基的选择方面，研究者们已经做了大量的工作。Unser14的研究表明样条小波对基于近似理论的编码应用较为有效。Rioul15的实验结果说明在压缩应用中，正交基的光滑性比较重要。Antonini等人16的实验表明光滑性和消失矩都很重要，而且光滑性显得比消失矩要稍微重要一些。Vetterli和Her

37、ley17又指出“正则性对信号处理的重要性如何仍然是一个公开问题(An Open Question)”。实际中常使用的小波基介于一阶和二阶连续可微，更多的光滑性似乎并不能对编码产生明显的改善。Billasenor等人系统地研究了所有长度不大于36的双正交小波滤波器组的性能，结果表明7/9小波滤波器性能最好18。该滤波器正是在实际中应用最广泛的一种。然而在应用双正交小波基时要注意，与正交小波基不同，它在变换域的平方误差与图像域的平方误差并不相等，也就是说在进行量化时，在变换域使平方误差最小并不能保证在图像域也是最小的。另一个重要问题是边界的处理。由于实际的图像都是有限尺寸的，在把滤波器应用于边界

38、时，简单的周期扩展或者加零都会由于引入了不连续性，导致降低编码性能，一个有效的方法是采用反射来扩展图像，它使边界保持连续。.2 量化过程由于小波变换具有良好的解相关性能，大多数编码器都采用标量量化。如果我们事先知道各子带系数的分布特性，可以采用熵约束下的Lloyd-Max量化器对各子带进行量化，但遗憾的是，通常我们并不具有这些先验知识。实际中经常使用的量化器是均匀量化器，而且在高码速率下，均匀量化器是最优的19。均匀量化器具有简单、有效的特点，在性能上与Lloyd-Max量化器也很接近，还有一个额外的优点是它可以产生出嵌入式的编码比特流。比特分配决定了每个子带量化的精细程度。最优比特分配是在一

39、定的约束条件下，决定各子带应如何量化，以使误差最小。本文随后将给出一个利用模拟退火算法进行最优比特分配的方案。如前所述，对双正交小波，变换域的误差与图像域的误差并不相同，为使二者一致，要对变换域的各子带的误差进行加权，不过对常用的7/9小波，加权系数都接近1，所以在实用中对7/9小波不进行加权。.3 熵编码过程典型的熵编码有游程编码、Huffman编码和算术编码，游程编码通常用于对二值图像的编码20，Huffman需要在编码前进行概率统计或者使用固定的编码表，在小波编码器中不常用，算术编码可以进行自适应编码，且一般认为它的效率要比Huffman编码的效率高，常用在小波编码器中。使用自适应算术编

40、码时，通过使用有效的自适应概率估计技术可使编码效率得到提高。有效的自适应估计过程在文献97和98中进行了讨论。8.6 SPIHT算法、性能分析及其实现在嵌入式零树编码算法EZW(Embedded Zerotree Wavelet)出现前，图像压缩，特别是有失真压缩，它的计算复杂性与编码效率是同步增长的，然而，在1993年，J. M. Shapiro所提出的EZW21算法突破了该限制，它既十分有效，计算效率又高，近年，Amir Said 和William A. Pearlman提出的SPIHT(Set Partitioning in Hierarcical Trees)算法22在此基础上性能又有

41、所提高，而且，即使不加算术编码，SPIHT算法仍可与许多复杂算法的性能相当。这两种方法都基于有效树量化(Significance Tree Quantization:STQ)技术，由于它们的性能优良，即将在下世纪初出台的JPEG2000标准已经把小波变换选作基本变换方法，就如同DCT在上一版JPEG标准中的地位一样。嵌入式零树编码（EZW）算法Shapiro的EZW算法的主要特点是：1） EZW利用了一幅图像的小波变换在不同级之间的相似性。Shapiro假定：如果在粗分辨率一个小波系数是无效的，所有在同一空间位置和方向上的系数也极有可能是无效的。结果表明，这个假定是相当有效的。Shapiro把

42、小波系数组织成一系列的四叉树形结构，如下图8.6-1所示。零树根节点意味着所有在此子树上的小波系数都是不重要的，因而除了要对树根进行编码外，其他的节点都不需要编码。为了获得很低的比特率，零树根符号的概率必须很高。各系数编码的顺序如图8.6-2所示。扫描从最低频率子带LL3（假定是三级分解）开始，结束于HH1。在移到下一子带之间，要把当前子带的系数全部扫描完，所有的父节点先于子节点被扫描。显然，这种扫描方式在编码端和译码端都是一样的。 LL3 HL3 LH1 HH1 HL2 HL1 LH2 HH2 LH1 HH1图8.6-1 三级DWT时的父子依赖关系LL3 HL3 HL2 LH3 HH3 HL

43、1 LH2 HH2 LH1 HH3图8.6-2 三级小波的扫描顺序2） 在按图8.6-2所定义的扫描顺序对意义图（即有效小波系数的位置）进行主编码过程，使用了如下码字：i) POS(positive significant),ii) NEG(negative significant)iii) IZ(isolated zero/insignificant),andiv) ZTR(root of a zerotree).在辅助编码过程中，对单个比特信息进行编码，该单比特信息用于解码时确定某小波系数是否被认为是有效的。3） EZW是一种嵌入式编码，所谓嵌入式编码，就是量化过程隐含在编码过程中，它使得

44、可逐步进行编码或译码，可在任何时候结束编译码过程，因而可精确地控制比特率。 在层次树中的集划分（SPIHT）算法SPIHT算法继承了EZW算法的特点，但在两个方面有本质的不同：分割系数的方式和如何传输有效系数的位置信息。SPIHT算法把对有效系数位置的传输隐含在算法的执行过程之中，并因此可以在允许峰值信噪比下降0.30.6dB时不采用算术编码，使执行速度更快。.1 算法所用的数据结构及集合操作算法中用到以下集合：l H：所有空间方向树的树根的坐标的集合；l O(i, j)：节点(i, j)的子节点集合，子节点指直接后继；l D(i, j)：节点(i, j)的后继的集合；l L(i, j) =

45、D(i, j) O(i, j).除了根节点外，对所有有子节点的节点(i, j)O(i, j) = (2i, 2j), (2i, 2j+1), (2i+1, 2j), (2i+1, 2j+1).集划分规则是：1） 初始分割由集合(i, j)和D(i, j)形成，其中;2） 如果D(i, j)是有效的，则把它分割成L(i, j)和四个单元素集，每个元素；3） 如果L(i, j)是有效的，那么把它分割成四个集合D(k, l)， 其中。它的基本运算是集测试： (8.6-1)判断某集合是否有效就是看式(8.6-1)集测试的结果，若值为1则表示有效，否则表示是无效的。使用了三个链表来记录相关信息：l LI

46、S：无效集合链表(List of insignificant sets)l LIP：无效象素链表(List of insignificant pixels)l LSP：有效象素链表(List of significant pixels)LIP和LSP都是记录坐标信息，而LIS记录的是集合信息，或者为D(i, j)，标记为A， 或者为L(i, j)，标记为B。8.6.2.2 编码算法完整的编码算法是：步骤1. 初始化：输出；置有效系数链表LSP为空，把所有根节点坐标加入无效系数链表LIP中，并且把有后继的根节点标记为类型A加入无效系数集链表LIS中。步骤2. 排序过程步骤2.1 对LIP中的每一

47、表项(i, j)，进行如下操作输出；如果，把(i, j)移至LSP，输出的符号；步骤2.2 对LIS中的每一个表项(i, j)，进行如下操作步骤2.2.1 如果该表项具有类型A，那么，* 输出；* 如果=1，那么对每一个，进行如下操作，- 输出；- 若，那么把(k, l)加入LSP，输出的符号；- 如果，那么把(k, l)加至LIP的尾部；如果，把(i, j)移到LIS的尾部，并且标记为类型B；否则，把(i, j)从LIS中删除；步骤如果该表项具有类型B，那么进行如下操作，* 输出；* 如果，那么，对每一个，将其标记为类型A，并将之加到LIS尾部；把(i, j)从LIS中删除。步骤3. 细化过

48、程：对LSP中的每一个表项(i, j)， 不包含刚才步骤2中加入的，输出系数的二进制表示的第n位有效位；步骤4. 量化级更新：把n减1，并转向步骤2，直到达到要求的压缩比。.3 译码算法A. Said和 W. A. Pearlman并没有明确给出译码算法，为完整起见，这里把译码算法也列出：步骤1. 初始化：读入；置有效系数链表LSP为空，把所有根节点坐标加入无效系数链表LIP中，并且把有后继的根节点标记为类型A加入无效系数集链表LIS中。步骤2. 排序过程步骤2.1 对LIP中的每一表项(i, j)，进行如下操作读出一比特；如果，把(i, j)移至LSP，并且读出的符号；若符号为正，令；若为负，令；步骤2.2 对LIS中的每一个表项(i, j)，进行如下操作步骤2.2.1 如果该表项