第八章 小波分析理论及应用
利用提升方案进行小波变换具有可进行同址运算优点，这样在具体实现时可省去大量在存贮器开销，在进行图像处理时，这个优点更为明显。它的另一个优点是可提高小波变换的速度。所以把现存的有限长小波滤波器分解成基本的提升步骤，可加快小波变换的进行，根据Daubechies的分析，随滤波器长度的增加，运算速度趋于常规小波变换的2倍，换言之，在同等的硬件条件下，对一维小波变换而言，运算时间降低一半，对二维小波变换则降为原来的四分之一。这个优点在实时性要求比较高的场合有很大的实用价值。
8.4.3 整数小波变换[13] 提升方案为扩展小波变换的应用领域提供了更多的灵活性。常规的小波变换都是采用浮点运算的，但利用提升方案所带来的便利，可十分方便地构造整数到整数的小波变换。将整数小波变换用于图像压缩就可以用小波变换进行无失真的图像压缩。 最早的整数到整数小波变换是S变换，是哈尔（Haar）变换的整数形式：
d1,l?s0,2l?1?s0,2ls1,l?s1,l??d1,l/2? (8.4-13)
Said和Pearlman提出了S+P( tranSform + Prediction)，就是在S变换之后，利用低通滤波器的系数来产生一个新的高通滤波器系数，它的一般形式是：
d1?,1l??s0,2l?1?s0,2ld1,l?d1?,1l?????1?s1,l?2?s1,l?1???0?s1,l?1?s1,l???1?s1,l?s1,l?1???1d1?,1l??1?式中??1?0,?0?2/8,?1?3/8,?1??2/8。 S和S+P变换的逆变换由式(8.4-13)、(8.4-14)把执行顺序变动一下，再改变一下相关项的符号就可以获得。 通常小波滤波器的系数都是浮点数，只能把整数映射成浮点数，要进行无失真变换，必须构造把整数映射成整数的小波变换，提升方案（Lifting scheme）为此提供了一种有效的方法，所有正交或双正交小波滤波器，用提升方案进行分解后，都可用与S+P类似的方式来构造变换的整数版本。 用提升方案构造小波变换有如下优点：
1） 同址计算：即不需要辅助存储器，原信号（图像）可被小波变换的结果覆盖。 2） 更快的小波变换：传统上，快速小波变换首先把信号分解成高通和低通成份，
并进行下抽样，然后对低通成份重复进行该过程直到所需要的变换级数。提升方案可把变换速度提高1倍。
3） 不需借助傅氏分析便可获得逆变换。实际上，只要简单地调整一下正变换中的
正负号即可。此优点使得不需要很强的傅氏分析的背景便可理解小波的特性和小波变换。
S-变换的逆变换非常容易得到：
s1,l?s0,2l??d1?,1l?/2? (8.4-14)
36
第八章 小波分析理论及应用
?d?s0,2l?s1,l??1,l2??? (8.4-15)
s0,2l?1?d1,l?s0,2l表8.4-1列出了几个常用的可逆整数到整数小波变换。
表8.4-1 可逆整数小波变换
Name (4,4) (2+2,2) Wavelet Transform d1,l?s0,2l?1?s1,l?s0,2l???916(s0,2l?s0,2l?2)?116(s0,2l?2?s0,2l?4)?12?9321(d1,l?1?d1,l)?132(d1,l?2?d1,l?1)?122?? )d1(,1l?s0,2l?1?(s0,2l?s0,2l?2)?12? s1,l?s0,2l??14)(1)1(d1(,1l?d1,l?1)?2?)11d1,l?d1(,1l???(?2s1,l?1?s1,l?2s1,l?1))1??(?12s1,l?s1,l?1?12s1,l?2)??d1(,1l?1?2? D4 d1(,1l)?s0,2l?1?s1,l?s0,2l???343s0,2l?12d1(,1l)???? 3?2?d(1)?1 421,l?1?d1,l?d1(,1l)?s1,l?1 (9,7) )d1(,1??s0,2l?s0,2l?2??l?s0,2l?1??)(1)s1(,1l)?s0,2l??d1(,1l?d1,l?1?1d1,l?d(1)1,l??????s(1)1,l?s(1)1,l?1s1,l?s1(,1l)????d1,l?d1,l?1
??????1212?12?2 表中(4,4)表示分析小波和综合小波的消失矩(Vanishing Moments)均为4。(2+2,2)表示通过一个额外的提升步骤使(2,2)变换的消失矩增加到4。D4是常见的4系数紧支撑Daubechies正交小波变换的整数变换形式。(9,7)是常用于图像压缩的7/9小波变换的整数形式，它的分析和综合滤波器的消失矩也都为4。
8.5小波图像编码
8.5.1 小波变换图像编码的基本框架 当前所有常规小波编码器都是变换编码形式，主要由三部分构成：解相关变换过程、量化过程和熵编码过程,下面分别进行描述。 8.5.1.1 解相关变换过程 首先要解决的问题是小波基的选择。但是，对于图像编码，很难确定哪种小波基是最优的，因为诸如光滑性、小波基支撑的尺寸以及频率选择性等指标都很重要，在不同
37
第八章 小波分析理论及应用
的要求下会产生不同的结果。另外，现在几乎所有的小波编码器采用的都是可分离二维小波变换，这使得可把二维小波基的设计转化为一维小波基本的设计，由于可分离性所具有的局限，有理由认为不可分离二维小波基将更为有效。 在最优基的选择方面，研究者们已经做了大量的工作。Unser[14]的研究表明样条小波对基于近似理论的编码应用较为有效。Rioul[15]的实验结果说明在压缩应用中，正交基的光滑性比较重要。Antonini等人[16]的实验表明光滑性和消失矩都很重要，而且光滑性显得比消失矩要稍微重要一些。Vetterli和Herley[17]又指出“正则性对信号处理的重要性如何仍然是一个公开问题(An Open Question)”。实际中常使用的小波基介于一阶和二阶连续可微，更多的光滑性似乎并不能对编码产生明显的改善。 Billasenor等人系统地研究了所有长度不大于36的双正交小波滤波器组的性能，结果表明7/9小波滤波器性能最好[18]。该滤波器正是在实际中应用最广泛的一种。然而在应用双正交小波基时要注意，与正交小波基不同，它在变换域的平方误差与图像域的平方误差并不相等，也就是说在进行量化时，在变换域使平方误差最小并不能保证在图像域也是最小的。 另一个重要问题是边界的处理。由于实际的图像都是有限尺寸的，在把滤波器应用于边界时，简单的周期扩展或者加零都会由于引入了不连续性，导致降低编码性能，一个有效的方法是采用反射来扩展图像，它使边界保持连续。
8.5.1.2 量化过程 由于小波变换具有良好的解相关性能，大多数编码器都采用标量量化。如果我们事先知道各子带系数的分布特性，可以采用熵约束下的Lloyd-Max量化器对各子带进行量化，但遗憾的是，通常我们并不具有这些先验知识。实际中经常使用的量化器是均匀量化器，而且在高码速率下，均匀量化器是最优的[19]。均匀量化器具有简单、有效的特点，在性能上与Lloyd-Max量化器也很接近，还有一个额外的优点是它可以产生出嵌入式的编码比特流。 比特分配决定了每个子带量化的精细程度。最优比特分配是在一定的约束条件下，决定各子带应如何量化，以使误差最小。本文随后将给出一个利用模拟退火算法进行最优比特分配的方案。如前所述，对双正交小波，变换域的误差与图像域的误差并不相同，为使二者一致，要对变换域的各子带的误差进行加权，不过对常用的7/9小波，加权系数都接近1，所以在实用中对7/9小波不进行加权。
8.5.1.3 熵编码过程 典型的熵编码有游程编码、Huffman编码和算术编码，游程编码通常用于对二值图像的编码[20]，Huffman需要在编码前进行概率统计或者使用固定的编码表，在小波编码器中不常用，算术编码可以进行自适应编码，且一般认为它的效率要比Huffman编码的效率高，常用在小波编码器中。使用自适应算术编码时，通过使用有效的自适应概率估计技术可使编码效率得到提高。有效的自适应估计过程在文献[97]和[98]中进行了讨论。 8.6 SPIHT算法、性能分析及其实现
38
第八章 小波分析理论及应用
在嵌入式零树编码算法EZW(Embedded Zerotree Wavelet)出现前，图像压缩，特别是有失真压缩，它的计算复杂性与编码效率是同步增长的，然而，在1993年，J. M. Shapiro所提出的EZW[21]算法突破了该限制，它既十分有效，计算效率又高，近年，Amir Said 和William A. Pearlman提出的SPIHT(Set Partitioning in Hierarcical Trees)算法[22]在此基础上性能又有所提高，而且，即使不加算术编码，SPIHT算法仍可与许多复杂算法的性能相当。这两种方法都基于有效树量化(Significance Tree Quantization:STQ)技术，由于它们的性能优良，即将在下世纪初出台的JPEG2000标准已经把小波变换选作基本变换方法，就如同DCT在上一版JPEG标准中的地位一样。 8.6.1 嵌入式零树编码（EZW）算法 Shapiro的EZW算法的主要特点是：
1）EZW利用了一幅图像的小波变换在不同级之间的相似性。Shapiro假定：如果在
粗分辨率一个小波系数是无效的，所有在同一空间位置和方向上的系数也极有可能是无效的。结果表明，这个假定是相当有效的。Shapiro把小波系数组织成一系列的四叉树形结构，如下图8.6-1所示。零树根节点意味着所有在此子树上的小波系数都是不重要的，因而除了要对树根进行编码外，其他的节点都不需要编码。为了获得很低的比特率，零树根符号的概率必须很高。各系数编码的顺序如图8.6-2所示。扫描从最低频率子带LL3（假定是三级分解）开始，结束于HH1。在移到下一子带之间，要把当前子带的系数全部扫描完，所有的父节点先于子节点被扫描。显然，这种扫描方式在编码端和译码端都是一样的。
LL3 HL3 LH1 HH1 HL2 HL1 LH2 HH2
LH1 HH1
图8.6-1 三级DWT时的父子依赖关系
39
第八章 小波分析理论及应用
LL3 HL3 HL2 LH3 HH3 HL1 LH2 HH2
LH1 HH3
图8.6-2 三级小波的扫描顺序
2）在按图8.6-2所定义的扫描顺序对意义图（即有效小波系数的位置）进行主编码
过程，使用了如下码字： i) POS(positive significant), ii) NEG(negative significant) iii) IZ(isolated zero/insignificant),and iv) ZTR(root of a zerotree).
在辅助编码过程中，对单个比特信息进行编码，该单比特信息用于解码时确定某小波系数是否被认为是有效的。
3）EZW是一种嵌入式编码，所谓嵌入式编码，就是量化过程隐含在编码过程中，
它使得可逐步进行编码或译码，可在任何时候结束编译码过程，因而可精确地控制比特率。
8.6.2 在层次树中的集划分（SPIHT）算法 SPIHT算法继承了EZW算法的特点，但在两个方面有本质的不同：分割系数的方式和如何传输有效系数的位置信息。SPIHT算法把对有效系数位置的传输隐含在算法的执行过程之中，并因此可以在允许峰值信噪比下降0.3~0.6dB时不采用算术编码，使执行速度更快。
8.6.2.1 算法所用的数据结构及集合操作 算法中用到以下集合：
? H：所有空间方向树的树根的坐标的集合；
? O(i, j)：节点(i, j)的子节点集合，子节点指直接后继；
40
小波分析及其应用（精品教程）
