嵌入式零树小波

嵌入式零树小波 Embedded Zerotrees of Wavelet transforms (EZW)是一种有损的影像压缩演算法。在高压缩率的情况下，大部分次频带转换(如小波转换)所产生的的系数都会是0，或是非常接近0。这背后的原因是在于真实世界的影像大部分集中在低频的成分。然而，也确实会有一些高频成分，例如影像中边缘的部分。人眼的感知对于这些高频成分特别的敏感，因此在高画质的影像压缩编码中，这些资讯需要被妥当地重建并呈现在解压缩后的影像中。

演算法一开始先把最低频的系数当作树状架构的根节点，每一个节点的子代为其更高层相对应次带位置的系数。由于每个节点都会有其各自延伸的子代，因此又可以称这些节点为子树。由于大部分的资讯被集中在低频，因此越往高频成分走系数的值越容易会是0。如果一个子树的系数的值全部都是0(或者是低于某个门槛值)，那么我们就会称此子树为零树。基于这个原因，在后文中节点和系数会被交错使用，且当提及一个系数的子代时，意指的是该子代所相对应位置的系数值。一个节点的子代意指的是该节点下一层相对应的系数，一个节点的后代指的则是一个节点往后的所有衍生的节点，意即包括其子代的子代，即便与该节点并无直接连结。

基于零树演算法的压缩演算法(如EZW和SPIHT)的目的是在于说希望能够利用每个次带间的统计特性来更有效的对重要的系数进行编码。由于大部分的系数会是近于0的值，我们会花上大部分的位元在表示那些重要的系数值。一个系数的重要性(significance)是由其值的大小是否超过一个门槛值做决定。在编码程序的一开始我们可以先将门槛值定为相当接近整张图片最大的系数值，往后在每个编码的循环中逐步降低该门槛值，如此产生一个渐进式的表示方式。基于次带转换的特性，如果一个系数在其本身的次带为不重要的，那么其后代皆为0的可能性也会相当的大。

EZW有一些重要的特性：第一，这个演算法可以停在编码程序中的任何一点，并产生一个合适的重建影像。因此可以想成是，我们是透过更多的位元数去逐步精炼输出的重建影像；第二，其演算法基本上是透过相当多的渐进式决策手续，因此可以使用算术编码来更进一步的提高它的压缩效率。然而，即便没有使用算术编码，它的编码程序所产生的符号值其实已经相当接近随机分布了，因此通常加上熵编码(如算术编码)的帮助也会有限。

EZW目前已经有很多衍生的演算法，诸如SPIHT等等，都可以达到比它更好的压缩效能。

演算法介绍

嵌入式零树小波(EZW) 为J. Shapiro在1993年提出，为一种可扩展性的影像压缩编码方式。它主要是基于四个想法，第一点：该影像必须先经过小波转换或其他次带转换产生阶层式的架构；第二点：在缺乏一些重要资讯的情况下，该演算法要能够透过影像本身的局部相似性做一些预测；第三点：透过渐进式的量化熵编码；第四点，它必须要能够透过算术编码达到无损压缩。

此外，EZW演算法还包含了以下几个特色：

(1) 透过小波转换可以产生多解析度版本的影像呈现

(2) 零树的编码架构提供了一种多解析度影像的紧致(compact)表示方式

(3) 可以对重要的系数(significant coefficients)做渐进式的估计

(4) 处理系数的优先顺序由其准确度、大小、空间上的相对位置来依序决定

(5) 渐进式层级架构的算术编码为一种相当有效率又同时表现相当优异的编码方式

嵌入式零树小波编码

A. 对重要性数组的系数进行编码

在重要性数组当中，一个系数可以被后述四种符号所代表。透过这些符号我们可以减少压缩一张影像整体的复杂度。

1. 零树的根

如果一个系数的数值比一个门槛值T还小，以及它的所有子代都比T还小，那么这个系数就会被作为零树的根。如果一个系数被标示为零树的根了，代表说他所有的子代都没有重要性了，也就没有必要去标示他的子代了。

2. 分离的零

如果一个系数的值比T还小，但是他的子代还有比T还大的，那么这个系数就会被称为分离的零。

3. 重要的正系数

如果一个系数的值比T还大，而且又是正值，那么这个系数就会被称为重要的正系数。

4. 重要的负系数

如果一个系数的值比T还大，而且又是负值，那么这个系数就会被称为重要的负系数。

B. 定义门槛值

门槛值的定义可以参考如下所述

1. 初始的门槛值 T₀: (假设 C_max 是最大的系数值。)

2. 门槛值T_i 被减少为先前的一半大小。

C. 系数的扫描顺序

逐行扫描是一般常见的影像捕捉和重建所使用的扫描方式。EZW之所以使用这种扫描方式是为了确保所有亲节点都会在子节点之前被处理，以及低层的次带会在高层次带处理完之后才被处理。

D. 两道位元平面编码的程序

(1) 精炼程序(或称 次要程序)

判断该系数是否介于[Ti, 2Ti)之间。且每一个系数经过精炼程序会吐出一个精炼位元。 在这个程序中，每一个重要的系数都会被扫过，扫描顺序为同一个次带中的逐行扫描。

(2) 重要性程序(或称 优势性程序)

这个程序会判断一个系数是否为重要，如果一个系数被判断为重要的，在往后的编码程序中，该系数就会经过精炼程序。反之，如果一个系数被判断为不重要了，该系数就不会再出现在往后的编码程序了。

参见

• 层次树集合分划编码 (SPIHT)

参考来源

• Shapiro, J. M., . IEEE Transactions on Signal Processing, Vol. 41, No. 12 (1993), p. 3445-3462.

外部链接

• http://www.ws.binghamton.edu/fowler/fowler%20personal%20page/EE523_files/Ch_15_4%20EZW%20(PPT)%20revised.pdf （页面存档备份，存于互联网档案馆）
• https://web.archive.org/web/20170118051156/http://140.129.20.249/~jmchen/wavelets/Tutorials/c.valens/ezwe.pdf