3.8 小波变换编码

小波变换与正交变换类似，是对信号进行分析的一种工具。我们知道，信号经傅氏变换（或余弦变换）后被分解成许多不同频率的分量，即分析的结果在频域内有精细的分辨率；但是从理论上讲正弦波在时域（空间域）上是无限伸展的函数，因此傅氏分析在时域上不具有分辨能力，它只能刻画信号在整个时间域（－∞，＋∞）上的频谱特性，而不能反映信号在时间的局部区域上的频率特征。与傅氏分析不同，小波分析在时域和频域上同时具有良好的局部化性质，可以通过伸缩和平移对信号进行多尺度分析，解决傅氏变换等无法解决的许多问题。小波变换也因此被誉为“数学显微镜”。

3.8.1 多尺度分析

设函数Ψ∈L2（R），R为实数集，若Ψ满足允许条件：

其中为Ψ（x）的傅氏变换，则称Ψ为基小波，或母小波。由允许条件可知Ψ满足）＝0和＝0，因此Ψ实质上为一带通滤波器。

相应于Ψ的小波变换为

而

称为小波，不难看出它是母小波经平移和伸缩后的结果，其中a和b分别为伸缩及平移因子。若将a，b离散化（a＝a0m，b＝nb0a0m），就可以得到离散的小波函数，例如取a0＝2，b0＝1时，就得到一个二进小波，，m，n∈Z，Z为整数集。二进小波变换是数字图像处理中最常用的一类小波。

由（3-118）式可得，二进小波变换的变换系数为

由小波系数重构的原始信号则为

（3-120）式所示的变换称为小波级数，其中小波系数为离散的，但信号f（x）仍为连续函数。当输入信号f（x）和小波伸缩及平移因子（a和b）均为离散时，则变换称为离散小波变换DWT（Discrete Wavelet Transform）。

设平方可积函数空间L2（R）上的闭子空间序列｛Vm｝，m∈Z，若满足：

①…V1V0V－1…，即每一个子空间都包含在下一个尺度（分辨率增加一倍）的子空间内；

②＝L2（R），即子空间的并集在L2（R）中是稠密的；

③（∩m∈ZVm）＝0，即L2（R）中的每一个非零f（x）都具有非零尺度，当m→∞时，它的投影f（m）（x）在L2（R）意义上收敛于0；

④f（x）∈Vm→f（2x）∈Vm－1，m∈Z，即子空间Vm中的函数尺度增加一倍，则成为较高尺度Vm－1内的函数；

⑤f（x）∈Vmf（x-2mn）∈Vm，m，n∈Z，即Vm中的函数平移后仍在此子空间内（分辨率不变）；

⑥存在函数Φ（x）∈L2（R），使得｛Φ0，n（x）：n∈Z｝构成V0的一组标准正交基，其中Φm，n（x）＝；

则｛Vk｝形成一个二进多尺度分析，Φ（x）称为尺度函数（Scalingfunction）。

由④、⑤、⑥可知，固定m，｛Φm，n（x）：n∈Z｝构成了Vm的一组正交基。Φ（x）的存在性也是显而易见的，例如取Φ（x）区间[0，1]上的示性函数，即当x∈[0，1]时，Φ（x）＝1，其他情况Φ（x）＝0），就构成了V0的一组标准正交基。

当一组闭子空间序列满足上述（1）～（6）时，可以证明存在L2（R）的一组小波正交基｛Ψm，n（x）：m，n∈Z｝，使得｛Ψm，n（x）：n∈Z｝为Vm－1中关于Vm的正交补空间Wm的一组标准正交基，即

既然m是任意整数，因此有

我们还可以以此类推，因此由多尺度分析可得或。

上面的式子说明，某一子空间中的任意函数（信号）可以分解为在较低尺度子空间的该信号的一个近似值，再加上一系列由小波分解产生的函数，后者可以认为是信号在Wm上的投影，代表了信号取近似值后损失的细节信息。

可以证明，尺度函数与小波函数之间存在双尺度关系：

｛Ψm，n（x）：m，n＝∈Z｝构成L2（R）的标准正交小波基，也就是说，通过多尺度分析的尺度函数Φ（x）可以构造标准正交母小波Ψ（x）。（3-124）式和（3-125）式是下一节介绍的级联算法的一个基础，其中｛hn｝和｛gn｝是对应的数字低通滤波器和高通滤波器的冲激响应。

3.8.2 二进小波变换

1.二进小波分解

设｛c0，n｝，L0≤n≤L1为初始信号，｛hn｝和｛gn｝分别为二进小波分解低通滤波器和高通滤波器，也称为分析滤波器，则有小波分解公式：

其中｛cm，n｝为第m次小波分解后所得到的低通信号，即在Vm上信号的近似值；｛dm，n｝为相应的高通信号，即在Wm上的细节信息。由于二进小波分解的每一个尺度分辨率降低一倍，所以两个输出信号分别以简单的“2抽1”方式进行下取样，然后对于在m尺度上的信号近似值cm，n进行m＋1尺度上的继续分解……图3-35的左侧给出了一个三层的级联分解过程。

2.二进小波重构

设和分别为二进小波重构低通滤波器和高通滤波器，也称为综合滤波器，m次小波分解后的信号如（3-126）式和（3-127）式，则有小波重构公式：

图3-35右侧给出了信号的重构过程。

对于正交小波，重构滤波器与分解滤波器是相同的。但是，由于对称的正交小波只有简单的Haar小波，而对称小波滤波器在数字信号处理中具有保持线性相位和降低小波变换复杂度等优势，所以在进行数字滤波时往往采用对称双正交小波滤波器，常用的有Daubechies5-3滤波器组和9-7滤波器组。

3.二维信号的小波分解

对于二维图像信号的小波分解，通常先对二维信号按行做一维小波分解，然后再按列做一维小波分解。重构时，依次进行相应的列信号重构与行信号重构即可恢复原信号。

图3-36（a）表示出二维小波分解过程。行方向分解生成左边为低通子带、右边为高通子带的中间结果；再经列方向分解后形成LL、LH、HL和HH4个子带，其中LL是原始图像的粗略近似，LH、HL和HH分别包含水平、垂直和45°倾斜的高频分量。图（b）给出两层分解的子带分布情况；图（c）则给出一个实际图像经过2层小波分解后的结果。由图（c）看出，经小波变换后能量多集中在LL子带内。

图3-36 二维信号的小波分解

3.8.3 变换系数的排序和编码

经小波变换后信号能量已经集中在少数系数上，将幅值很小的其他系数忽略（量化到0），则可达到数据压缩的目的。不过在利用小波变换进行图像编码时一个值得注意的问题是，量化后的变换系数矩阵是一个具有少量非零值和大量零值的稀疏矩阵，在将此矩阵转换成一维序列时，如何有效地组织非零系数和有效地表达零系数所在的位置，对数据压缩的效率有重要的影响。本节讨论与此有关的问题。

1.嵌入零树小波编码

人们发现，如果低频子带中某个系数为非零值，则在高频子带对应位置上的系数也为非零值的概率很大。根据这个特点，Lewis和Knowles在1992年提出了小波零树编码算法。在小波零树编码算法中，图像经过N层离散二维小波变换后得到小波系数，这些系数按照子带的相同方向形成小波树结构。图3-37为图像经过三层离散二维小波变换后形成的小波树结构示意图。其中：

①低频子带LL3的每一个小波系数为树的根节点，它在同层小波变换的高频子带HL3、LH3和HH3中相同空间位置上均有一个子节点；

②每个高频子带的小波系数在同方向较高频子带上具有4个子节点；

③最高频子带的每个小波系数没有子节点，因此也被称为叶节点；

④父节点是与子节点相对的一个称呼，B是A的子节点，则称A为B的父节点；

⑤一个节点的子节点及其子节点的子节点等称为该节点的后代；

⑥一个节点的父节点及父节点的父节点等称为该节点的祖先；

⑦小波系数与它的后代组成一个小波树。

小波零树编码就是利用小波树的强相关性，将父节点的绝对值与门限值进行比较，当父节点绝对值小于门限值时，认为该小波树均不是显著系数，因此将该小波树都以零值编码，形成大量的小波零树，从而减少数据。零树编码不是十分完美，譬如父节点不显著时，也存在后代节点是重要的情形，此时忽略子孙节点将造成较大的误差。

1993年Shapiro在小波零树编码算法的基础上提出了嵌入零树小波编码（Embedded Zerotree Wavelet，EZW）算法。在EZW算法中，用5种符号表示小波系数：正符号、负符号、孤立零值、小波零树和零符号。正符号（PositiveSymbol，POS）表示绝对值大于门限值，且值为正的小波系数；负符号（NegativeSymbol，NEG）表示绝对值大于门限值，且值为负的小波系数；孤立零值（Isolated Zero，IZ）表示绝对值小于门限值，但是存在后代节点的绝对值大于门限值的小波系数；小波零树（Zero tree，ZTR）表示绝对值小于门限值，且后代节点的绝对值都小于门限值的小波系数；零符号（Zero Symbol，Z）表示绝对值小于门限值的叶节点。由于在规定的扫描顺序下小波树的位置能完全确定下来，所以在实际编码中小波零树和零符号可以用同一符号来表示。

（1）门限值的选取

初始门限值；，其中VDWT表示小波系数，「·」表示取不超过该数的最大整数值。此后每次扫描的门限值：，n＝1，2，…。

（2）扫描顺序

在编码过程中，对小波系数通常采用如图3-38所示的Zig-Zag（Z）顺序进行多次扫描，前一次扫描获得的数据比后一次更重要。

（3）编码过程

编码主要分为三个过程：主扫描过程（dominant pass），主要确定小波系数的符号；辅扫描过程（refinement pass），对小波显著系数（正符号和负符号）进行加细量化；符号编码过程（symbol encode），对符号进行熵编码。

首先，在第i次主扫描过程中，根据门限Ti－1确定每个系数对应的符号。绝对值大于门限值的系数，称为显著系数，依据它的正、负赋予符号POS或NEG。绝对值小于门限值的系数，如果其子孙节点系数的绝对值均小于门限值，则它们构成零树，赋予该节点ZTR，并不再对其子孙节点进行扫描；如果其子孙节点中有一个系数的绝对值大于门限值，则赋予该节点IZ，对其子孙节点的扫描照常进行。将扫描得到的符号按顺序记录在显著系数表中。

第i次辅助扫描是对当前的显著系数表进行扫描，以对符号为POS和NEG的系数的绝对值进行加细量化。将[Ti－1，2T0）划分成[Ti－1，2Ti－1）大小的若干个区间，若系数的绝对值落入某一个区间的下半部（小于区间中点值），输出“0”；否则，输出“1”。将输出的“0”和“1”按扫描顺序记录在加细量化表中。

然后，在新门限值Ti下进行第i＋1次主扫描和辅扫描。在这次主扫描中，前面已经确定为显著系数的节点将不再扫描，同时将该节点的系数看成0，以确保更多的零树产生。主扫描和辅扫描得到的结果将分别存入显著系数表和加细量化表中（附加在第i次扫描结果之后）。

上述的两步扫描过程继续进行，直至门限值为1。最后，对所得的两个表进行熵编码得到EZW码流。编码中的符号IZ和Z可以合并为Z。

由上看出，EZW编码对数据进行逐次逼近量化，将重要性高的数据优先编码（在表的前面），而且可以在任意一点停止扫描编码，形成重建质量不同的码流，保留码流越长，系数量化精度越细，重建图像质量越高。这种编码方式称为嵌入式编码。多尺度分析的特性使小波变换编码具备良好的嵌入式编码性能。

2.其他高性能的小波编码算法

Said和Pearlman受EZW算法的启发，在1996年提出了多级树集合分裂算法（Set Partitioning In Hierarchical Trees，SPIHT）。SPIHT算法依然利用小波零树特性进行编码，尽管与EZW算法有很多相似之处，但也存在一些明显的区别。第一，SPIHT算法在小波树结构上与EZW算法有所不同，同时定义了两种零树，比EZW划分的更为细致；第二，EZW编码的扫描顺序是一种固定的光栅扫描，而SPIHT编码的扫描顺序取决于以前编码的树的显著性；第三，显著性扫描过程与加细量化过程与EZW算法的顺序相反。与EZW算法一样，SPIHT算法也是一种嵌入式编码方法，它可以在任意点截断比特流，得到不同质量的图像数据。

EZW算法和SPIHT算法都利用了小波变换中存在的父－子节点的相关性。然而更进一步的研究表明，基于小波变换的图像编码算法编码增益更多的得益于小波变换的能量压缩性质，而不是特定的图像数据的相关性。因此，对每个子带进行独立的编码也可以获得良好的编码性能。

Taubman在2000年提出的基于优化截断嵌入式块编码（Embedded Block Coding with Optimal Truncation，EBCOT）就是一种对各子带进行独立编码的方法。EBCOT算法将每个子带分成相对较小的块（64×64或32×32），这些块称为“码块（code-block）”，每个码块独立进行编码，产生基本的嵌入式流。最后由这些基本嵌入式比特流可以合成一个总嵌入式流，称为“组合流（pack-et-stream）”。合成组合流时，每个码块截断点比特流长度与失真的关系是已知的，可以根据这种关系优化截断各码块比特流以获得效率更高的组合流，这种优化截断方法称为压缩后率失真优化（Post-Compression Rate-Distortion optimization，PCRD-opt）方法。EBCOT算法是对每个码块进行独立编码的，因此通过EBCOT算法不仅可以实现失真的可伸缩性，通过选择不同子带的码块比特流还可以实现分辨率的可伸缩性，结构比EZW和SPIHT算法要更灵活。同时对每个码块进行独立编码也为在硬件中实现并行算法提供了可能性。当压缩比特流出现误码时，误码的影响也仅出现在相应的码块中，并不影响其他码块的解码，因此EBCOT算法还具有良好的抗误码性能，适合在网络中进行传输。EBCOT算法的这些特性促成了JPEG2000采用EBCOT编码方法。