第9章 小波图像编码
由于小波变换技术在20世纪90年代初期已经比较成熟，因此从那时起就开始出现各种新颖的小波图像编码方法。这些编码方法包括EZW,在EZW算法基础上改进的SPIHT和EBCOT等。由于EZW算法的开拓给后来者带来很大的启发，它是一种有效而且计算简单的图像压缩技术，因此本章将重点介绍。
9.1 从子带编码到小波编码
9.1.1 子带编码子带编码(subband coding，SBC)的基本概念是把信号的频率分成几个子带，然后对每个子带分别进行编码，并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代，子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点，20世纪80年代中期开始在图像编码中使用。1986年Woods,J,W.等科学家曾经使用一维正交镜像滤波器组(quadrature mirror filterbanks，QMF)把信号的频带分解成4个相等的子带，如图9-01所示。图9-01(a)表示分解方法，图9-01(b)表示其相应的频谱。图中的符号表示频带降低1/2，HH表示频率最高的子带，LL表示频率最低的子带。这个过程可以重复，直到符合应用要求为止。这样的滤波器组称为分解滤波器树(decomposition filter trees)。
(a) 分解法 (b) 频谱图9-01 Lena图的子带编码(1984年)
9.1.2 多分辨率分析
S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolution analysis)的概念，从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法，叫做Mallat算法。根据Mallat和Meyer等科学家的理论，使用一级小波分解方法得到的图像如图9-02所示。
图9-02 Lena的两种分辨率分析图像(1986年)
如果在一级分解之后继续进行分析，这种分解过程叫做多分辨率分析，实际上就是多级小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像，这些图像叫做多分辨率图像(multiresolution images)。图9-03表示Lena的多分辨率图像。其中，粗糙图像1的分辨率是原始图像的1/4，粗糙图像2的分辨率是粗糙图像1的1/4。
图9-03 Lena的多分辨率分析图像(1986年)
9.1.3 滤波器组与多分辨率为了压缩语音数据，在1976年Croisier,Esteban和Galand介绍了一种可逆滤波器组(invertible filter bank)，使用滤波和子采样(subsampling)的方法用来把离散信号分解成大小相等的两种信号，并且使用叫做共轭镜像滤波器(conjugate mirror filters)的一种特殊滤波器来取消信号的混叠(aliasing)，这样可从子采样的信号中重构原始信号。这个发现使人们花费了10多年的努力来开发一套完整的滤波器组理论。
正交小波的多分辨率理论(multiresolution theory)已经证明，任何共轭镜像滤波器都可以用来刻画一种小波，它能够生成实数空间中的正交基，而且快速离散小波变换可以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示了数字信号处理和谐波分析之间关系，这就使人们一直在致力于解决它们之间的关系问题。
9.1.4 从子带编码到小波编码在过去的年代里，人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波编码技术(wavelet coding，WC)的旗号下，人们提出了许多与子带编码技术非常类似和密切相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的小波基函数系列可以在连续的时间域中构造，但如何在离散的时间域中构造是一个现实问题。
在众多的研究者中，Inrid Daubechies在离散的时间域中构造小波基函数方面做出了杰出的贡献。她于1988年[1]最先揭示了小波变换和滤波器组之间的内在关系：离散时间滤波器(discrete-time filters)或者正交镜像滤波器(quadrature mirror filter,QMF)可以被叠代，并在某一种匀称(regularity，可粗略理解为函数的平滑性)条件下可获得连续小波。这是一个非常实际和极其有用的发现，这就意味着可使用有限冲击响应(finite impulse response，FIR)的离散时间滤波器来执行小波分解，使用相同的滤波器可重构小波分解之后的信号。由此可见，早期开发的子带编码实际上是一种小波变换。
在Daubechies揭示小波变换和滤波器组之间的关系之前，在图像编码中小波技术并不流行。从20世纪90年代开始，Cohen,Daubechies和Feauveau，简称为CDF，系统地开发了构造紧支持双正交小波(compactly supported biorthogonal wavelets)的方法[2]，以及其他学者提出的各种算法，使小波技术在图像编码中得到广泛的应用。
在构造小波和开发小波变换算法中，比利时成长的年轻学者Wim Sweldens在1994年的博士论文中首先提出了“The Lifting Scheme”[3][4]，简称Lifting/lifting(提升法)。该方法的基本思想是首先把信号分成偶数号样本和奇数号样本，根据信号本身的相关性，奇数样本使用偶数样本进行预测，由预测丢失的信号叫做信号的细节信息，然后调整偶数样本以保存原始信号的粗糙信息和细节信息。该方法保留了小波分析的特性(时间频率局部化和快速计算)，通过放弃小波的平移和缩放，并且放弃用傅立叶分析来构造小波，从而解决了非无限信号或者非周期信号的小波和小波变换问题，也使计算速度得到很大的提高，因此被称为第二代小波(second generation wavelets)，现在也成为制定JPEG 2000标准中小波部分的基础。
9.1.5 小波分解图像方法使用小波变换把图像分解成各种子带的方法有很多种。例如，均匀分解(uniform decomposition)，非均匀分解(non-uniform decomposition)，八带分解(octave-band decomposition)和小波包分解(wavelet-packet decomposition)，根据不同类型的图像选择不同小波的自适应小波分解(adaptive wavelet decomposition)等。其中，八带分解是使用最广泛的一种分解方法。这种分解方法属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分解的高频部分不再进一步分解。图9-04表示Lena图像的数据分解。
图9-04 Lena图像的数据分解
9.2 失真的度量方法在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比(peak signal to noise ratio,PSNR)来衡量,定义为最大像素值与均方差(mean square error，MSE)之比[5]，
(db)
对8位二进制图像，
(db)
其中，
其中，为原始图像的像素值，为解压缩之后的像素值。
在文献中，评估编码系统性能还使用其他方法，这些方法包括使用规格化均方差(normalized mean square error，NMSE)、信号噪声比(signal to noise ratio，SNR) 和平均绝对误差(mean absolute error，MAE)来度量，分别定义为
其中，为原始图像的像素值，为解压缩之后的像素值。
在电子工程中，信号噪声比(SNR)一直是最流行的误差度量指标，在大多数情况下可提供很有价值的信息，在数学上也比较容易计算。信号噪声比虽然也用在图像编码中，但由于它的数值与图像编码系统中高压缩比的关系不容易体现，因此提出了其他的几种度量方法，包括平均主观评分(mean opinion score，MOS)。
9.3 EZW编码
9.3.1 介绍在1992年，Lewis，A,S.和Knowles,G.首先介绍了一种树形数据结构来表示小波变换的系数[6]。在1993年，Shapiro,J,M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(embedded zerotree wavelet，EZW)算法[7]。EZW主要用于与小波变换有关的二维信号的编码，但不局限于二维信号。
嵌入(式)零树小波中的“小波”是指该算法以离散小波变换为基础，以大的小波变换系数比小的小波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实为背景。“零树”是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙(低频图像)和比较精细(高频图像)的小波系数，在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(threshold)，那么这棵树就叫做零树。“嵌入”是渐进编码技术(progressive encoding)的另一种说法，其含义是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像。图像合成的过程与分解的过程相反，使用子图像生成许多分辨率不同的图像。EZW编码指的是，按照用户对图像分辨率的要求，编码器可以进行多次编码，每进行一次编码，阈值降低1/2，水平和垂直方向上的图像分辨率各提高1倍。编码从最低分辨率图像开始扫描，每当遇到幅度大于阈值的正系数就用符号P表示，幅度的绝对值大于阈值的负系数用符号N表示，树根节点上的系数幅度小于阈值而树枝中有大于阈值的非零树用符号Z表示，零树用符号T表示。
小波图像编码(wavelet image coding)的一般结构如图9-05所示，它主要由小波变换(wavelet transform)、量化(quantization)和熵编码(entropy encoding)等3个模块组成。小波变换不损失数据，但它是EZW算法具有渐进特性的基础；量化模块对数据会产生损失，数据损失的程度取决于量化阈值的大小，EZW算法指的就是这个模块的算法，它的输出是符号集{P,N,T,Z,0,1}中的一系列符号；熵编码模块对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流(code stream)小于输入的码流。
图9-05 EZW算法结构
9.3.2 算法
EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次，生成一种分辨率图像，编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤：设置阈值、每个小波系数与阈值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表，一种是小波系数的符号表，另一种是量化表。
1,零树回顾二维小波变换的计算过程，不难想象各级子图像中的系数是相关的。在说明零树的概念之前，需要对小波变换得到的系数、名称和符号加以说明。现以3级分解的离散小波变换为例，图9-06表示Lena图像使用三级滤波器组做小波变换输出的子图像(sub image)。需要注意的是，分解之后的图像的名称在文献上有很多种，除了子图像之外，有的叫做子带图像(sub-band image)，有的把子图像进一步区分为高频子图像和低频子图像，或者粗糙图像和精细图像等名称。这些名称从不同的角度反映图像的特性，在不同的场合下使用可以收到异曲同工的效果。图9-06中的数字1,2和3表示分解的级数编号，LL3表示第3级的低频子图像，在这个例子中，它是分辨率最低的子图像。HL3表示第3级分解在水平方向上的子图像，LH3表示第3级分解在垂直方向上的子图像，HH3表示第3级分解在对角线方向上的子图像，其他的组合符号依此类推。由于低频子图像的系数要比高频子图像的系数大，零树编码技术就是利用这个事实来设计编码/解码过程中每一级使用的量化器。
图9-06 Lena三级分解图像
各级子图像中的系数之间的关系可以用树的形式描述。如图9-07(a)所示，最低频率的子图像在左上角，最高频率的子图像在右下角，由同一方向和相同空间位置上的所有小波系数组成一棵树。例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树。按箭头所指的方向，各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼。举例来说，LL3的系数为{63},HH2和HH1中的系数分别为{3}和{4,6,3,-2},由这些系数构成的树如图9-07(b)所示。如果把{63}指定为父系数，{3}就称为子系数，而{4,6,3,-2}中的4个系数就称为孙系数。
(a) 构造方法 (b) 小波系数举例图9-07 EZW编码树的构造
现在再来看零树的概念。为便于比较，把图9-07(b)所示的两棵树用图9-08(a)和(b)表示。假设编码时开始的阈值，由于63比32大，这样的树叫做非零树，如图9-08(a)所示。假设下一次编码时的阈值，把-13当作父系数，它的幅度比16小，而它的所有4个子系数的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图9-08(b)所示。根据以上的分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。
顺便要指出的是，小波图像系数结构的形式不只是上面介绍的一种，也可能不是最好的一种。
(a) 非零树例子 (b) 零树例子图9-08 非零树与零树的概念
2,扫描方法
EZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种，一种叫做光栅扫描(raster scan)，如图9-09(a)所示，另一种叫做迂回扫描(morton scan)，如图9-09(b)所示。
(a) 光栅扫描 (b) 迂回扫描图9-09 小波变换系数扫描方法
3,算法
EZW算法可粗略地归纳为下面几个主要步骤。
(1) 阈值的选择开始时的阈值通常按下式估算，
其中，MAX(.)表示最大的系数值，表示小波变换分解到第级时的系数。以后每扫描一次，阈值减少一半。
(2) 给系数分配符号使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第一种扫描叫做主扫描(dominant pass)，它的任务是把小波系数与阈值进行比较，然后指定表9-1中的4个符号之一，笔者把这种符号叫做系数符号，对整幅图像扫描之后产生系数符号序列。第二种扫描叫做辅扫描(subordinate pass)，其任务是对主扫描取出的带有符号P或者N的系数进行量化，产生代表对应量化值的符号“0”和“1”，笔者把这种符号称为量化符号。
主扫描：扫描每一个系数以产生系数符号如果系数幅度大于阈值()且为正数，输出符号P(positive)，
如果系数幅度的绝对值大于阈值()且为负数，输出符号N(negative)，
如果系数是零树根，输出T(zerotree)，
如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号Z(isolated zero)。
为了确定一个系数是否为零树根T或者是孤立零Z，需要对整个4叉树进行扫描，这样就需要花时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入一个标记或者零，这样做可防止对它们再编码。
辅扫描：量化带符号P和N的系数在量化系数之前要构造量化器。量化器的输入间隔为，该间隔被1.5分成两个部分：和，量化间隔为0.5,其中为第次编码。量化器的输出为量化符号“0”和“1”，“0”对应量化值为，“1”对应量化值为。
例如，第一次扫描时的阈值，量化器的间隔就为，该间隔被48分成两个相等的部分：和，量化间隔为16。对系数进行量化时，如果幅度在的范围里，该系数的量化值为“0”，对应的量化值为；如果幅度在的范围里，该系数的量化符号为“1”，它的量化值为，详见图9-13。
表9-1 EZW系数符号集判断条件
输出符号
P(positive)：表示正，重要系数
N(negative)：表示负，重要系数
所有子孙系数，
叫做零树的根
T：零树根，不重要系数
至少有一个子孙系数
Z：孤立的零，不重要系数
9.3.3 算法举例为进一步理解EZW算法，综合了C,Valens[8]和在读博士生Ghassan Al-Regib[9]提供的一个例子[7]。假设有一幅8×8的图像，离散小波变换矩阵为，经过小波变换之后的图像为，小波图像系数和扫描方式分别如图9-10(a)和(b)所示。另外还假设，图9-10(a)所示的数据是经过3级分解的小波图像系数。
(a) 小波图像数据 (b) 迂回扫描图9-10 8×8小波变换图像
1,树结构为叙述方便，图9-10(a)中的系数用组合符号(YM/YYN)表示。最低分辨率子图像(即第3级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关，它们之间构成的树如图9-11(b)所示。说明如下：
X1/LL3表示子带LL3的系数，它与第2级子图像中相关的子系数有3个：X1/HL2,X1/LH2和 X1/HH2。
X2/HL3表示子带HL3的系数，它与第2级子图像中相关的子系数有3个：X2/HL2,X2/LH2和X2/HH2。
X3/LH3表示子带LH3的系数，它与第2级子图像中相关的子系数有3个：X3/HL2,X3/LH2和X3/HH2。
X4/HH3表示子带HH3的系数，它与第2级子图像中相关的子系数有3个：X4/HL2,X4/LH2和 X4/HH2。
(a) 8×8子图像小波变换系数 (b) 最低频带小波变换系数树图9-11 编码树的结构(1)
在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它们之间构成的树如图9-12(b)所示，图中只表示了一部分的树。从图中可以看到，
X1/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X1/HL1,X2/HL1,X5/HL1和X6/HL1。
X2/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X3/HL1,X4/HL1,X7/HL1和X8/HL1。
X3/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X09/HL1,X10/HL1,X13/HL1和X14/HL1。
X4/HL2 表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X11/HL1,X12/HL1,X15/HL1和X16/HL1。
(a) 8×8子图像小波变换系数 (b) 2级子图像小波变换部分系数树图9-12 编码树的结构(2)
2,编码根据对图像分辨率的要求，编码时可对小波图像系数进行多次扫描。每一次扫描包括主扫描和辅扫描。
第一次扫描：
步骤1,选择初始阈值。最大的系数为63，因此选择。
步骤2,指定系数的符号。假设存放系数符号的缓冲存储器为D1，存放量化符号的缓冲存储器的符号为S1。扫描每一个系数并且与阈值32进行比较。在比较过程中对每一个系数指定一个符号，并把符号放在D1中。当一个系数被指定为符号T时，所有的子孙系数就不再扫描，并用“×”表示，扫描结果如图9-13(a)所示。图中，输出符号的下标表示系数被标识的次序，仅仅是为了叙述方便。对扫描结果作如下说明：
X1/LL3的系数是63，它大于阈值32，因此输出的符号为P1。
X2/HL3的系数是-34,它的符号输出为是N2。
③ X3/LH3的系数是-31,它的幅度相对于阈值32来说是不重要的，它下属子系数{X3/HL2,X3/LH2和X3/HH2}，孙系数{X9/HL1,X10//HL1,X13//HL1,X14//HL1},{X9//LH1,X10/LH1,X13/LH1,X14/LH1}和{X9//HH1,X10/HH1,X13/HH1,X14/HH1}的幅度都比它小，因此它输出的符号为零树符号T3。
④ X2/LH2的系数是14，它小于阈值32。在它的子系数{X3/LH1,X4/LH1,X7/LH1,X8/LH1}中,X4/LH1的系数是47,它大于阈值32,因此X2/LH2输出符号为孤立零符号Z8。
⑤ X4/LH1的系数是47，相对于阈值32是重要的，产生符号P16。
第一次主扫描之后，缓冲存储器D1中的系数符号为：
D1,P N T T P T T Z T T T T T T T P T T
(a) 系数符号和标记 (b)系数量化图9-13 第一次主扫描
步骤3,量化系数。对带符号P/N的系数进行量化。在第一次主扫描期间的阈值是32，幅度大于32的有4个系数{63，34，49，47}。用48把间隔分成两个部分,如图9-13(b)所示。幅度在间隔中的系数指定为符号“0”,幅度在间隔中的系数指定为符号“1”，于是这4个系数被编码成如表9-2所示的量化符号。顺便指出，由于解码器重构的系数幅度按进行计算，因此重构数据的绝对误差在1～7之间，即小于。
在第一次辅扫描之后，4个系数{63-P,34-N,49-P,47-P}的量化符号所组成的位流为：
S1,1 0 1 0
表9-2 第一次辅扫描量化表系数幅度
量化符号
重构幅度
63
1
56
34
0
40
49
1
56
47
0
40
步骤4,重新排列带P/N符号的数据。为便于设置第二次扫描时所用的量化间隔，以提高解码的系数精度，编码器对本次扫描取出的4个系数作重新排列，把系数集{63-P,34-N,49-P,47-P}排列成{63-P,49-P,34-N,47-P}。对于重新排序的问题也有人指出，从他们的实验结果看，精度提高不大但付出的计算代价却很高。
步骤5：输出编码信息。编码器输出两类信息，一类给解码器的系数符号系列等信息，另一类用于下一次扫描的阈值和大于阈值的系数值等信息。
① 给解码器的信息包含下面三种：
HEADER (即),D1,P N T T P T T Z T T T T T T T P T T,AND” S1,1 0 1 0.
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,34-N,47-P},AND”子带图像。
此处的“AND”仅为强调它们之间的对应关系
(2) 第二次扫描步骤1,设置新阈值：。
步骤2,指定系数的符号。使用“0”代替第一次扫描时被标识的系数，这些系数就不再被扫描，在图9-14中，用符号表示。然后扫描其余的系数，并与新的阈值进行比较。假设第二次存放系数符号的缓冲存储器为D2,存放量化符号的缓冲存储器S2，采用与第一次类似的扫描方法，得到的系数符号为，
D2：N P T T T T T T T T T T T T T T T
步骤3,量化系数。由于阈值是16,因此量化器的间隔有3个：，和，如图9-14所示。按照这次构造的量化器，对第二次主扫描得到的系数集{63-P,49-P,34-N,47-P,31-N,23-P}进行编码，得到的量化符号位流如下，
S2,1 0 0 1 1 0
图9-14 第二次主扫描步骤4,重新排列带P/N符号的数据。将系数集{63-P,49-P,34-N,47-P,31-N,23-P}排成{63-P,49-P,47-P,34-N,31-N,23-P}。
步骤5,输出编码信息。
① 给解码器的信息包含下面两种：
D2,N P T T T T T T T T T T T T T T T,AND” S2,1 0 0 1 1 0,
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,47-P,34-N,31-N,23-P},AND”子带图像.
(3) 第三次扫描步骤1,设置新阈值：。
步骤2,指定系数的符号。使用“0”代替第二次扫描时被标识的系数，这些系数就不再被扫描，在图9-15中，用符号表示。然后扫描其余的系数，并与新的阈值进行比较。假设第三次存放系数符号的缓冲存储器为D3,存放量化符号位流的缓存存储器为S3，采用与第一次类似的扫描方法，得到的系数符号为，
D3：PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
步骤3,量化系数。由于阈值是8,因此量化器有7个间隔：,,，，，和，如图9-15所示。按照这次构造的量化器，对第三次主扫描得到的系数集{63-P,49-P,47-P,34-N,31-N,23-P,10-P,14-P,13-N,15-P,14-P,9-N,12-N,14-N,8-P,13-P,12-N,9-P,9-P,11-P}进行编码，得到的量化符号位流如下，
S3,1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
图9-15 第三次主扫描
步骤4,重新排列带P/N符号的数据。将系数集{63-P,49-P,47-P,34-N,31-N,23-P,10-P,14-P,13-N,15-P,14-P,9-N,12-N,14-N,8-P,13-P,12-N,9-P,9-P,11-P}排成{63-P,49-P,47-P,34-N,31-N,23-P,14-P,13-N,15-P,14-P,12-N,14-N,13-P,12-N,10-P,9-N,8-P,9-P,9-P,11-P}。
步骤5,输出编码信息。
① 给解码器的信息包含下面两种：
D3,PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
“AND”
S3,1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0,
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,,47-P,34-N,31-N,23-P,14-P,13-N,,15-P,14-P,12-N,14-N,13-P,
12-N,10-P,9-N,8-P,9-P,9-P,11-P},AND”子带图像.
根据对图像的压缩率或者数据的传送率等应用要求可决定是否继续编码。如果从此不再编码，编码器的输出流就为：Header-D1-S1-D2-S2-D3-S3。现把每次编码扫描输出的内容归纳在表9-3中。
表9-3 三次编码的输出名称
内容
Header
32
D1 /?S1
P N T T P T T Z T T T T T T T P T T /?1 0 1 0
D2 /?S2
N P T T T T T T T T T T T T T T T?/?1 0 0 1 1 0
D3 /?S3
PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT/
1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
请注意，这里所指的编码器输出是指没有经过熵编码的输出，这仅仅是为了便于说明EZW的算法。
3,解码
EZW的解码过程是EZW编码的逆过程，编码时扫描多少次，解码时也可以解多少次，这要取决于对图像分辨率或者传输环境的要求。解码过程大致分为三个步骤：在接收到编码器发送的信息之后，解码器首先设置阈值，构造逆量化器，然后开始解读位流中包含的位置和小波系数值。
由于解码时用的逆量化器与编码时用的量化器没有什么差别，因此简称为量化器。像编码时那样，在EZW解码过程中每次解码都需要构造量化器。
(1) 第一次解码解码器开始时的阈值，它接收到来自编码器第一次扫描输出的系数符号是，
P N T T P T T Z T T T T T T T P T T / 1 0 1 0
这个信息相当于量化符号所组成的位流与系数符号之间有如下的对应关系，
D1
P
N
T
T
P
T
T
Z
T
T
T
T
T
T
T
P
T
T
S1
1
0
1
0
解码码器要按照编码时的扫描和量化方法进行解码。输入位流的第1个系数符号是P，对应的量化符号位是“1”，因此第1个系数是56；第2个系数符号是N，对应的量化符号位是“0"，因此第2个系数是-40；第3个系数符号是T，在相应的图像系数位置上用“0”表示它的系数。第一次解码的结果如图9-16所示。用“0”表示的系数表示已经扫描过，它们对应符号T或者Z，用“×”表示的系数表示不需要扫描的系数，因为它们是零树根的子孙。
图9-16 第一次解码在第一次解码之后，解码器需要判断是否要进一步重构比较精细的图像。如果不需要，则退出解码，如果需要则进入第二次解码。
(2) 第二次解码第二次解码分两步。第一步：提高第一次解码时得到的系数的精度，第二步：求解未解码的系数。解码器将使用编码器生成的第二次编码时的扫描信息，
D2,N P T T T T T T T T T T T T T T T
S2,1 0 0 1 1 0
解码器首先修改阈值，使，然后构造一个如图9-17所示的量化器。开始时，解码器只看S2中用下划线表示的量化符号位流的前4位(1 0 0 1)，而不看D2中的符号，因为在第一次解码时已经知道了4个系数值是{56,-40,52,40}。S2的第1位是“1”，第一次译码之后的系数是56，现在使用新的量化器，56就变成60；S2的第2位是“0”，第一次译码之后的系数是-40，使用新的量化器之后的系数就变成-36。同样，其他2个系数分别由52变成56，40变成44。
在处理完前4个系数之后，解码器就开始求解在第一次解码时没有还原的系数，使用的间隔为，即。D2的第1个系数符号是N，表示负数，对应S2的量化符号是“1”，因此解码输出的系数为-28，把它放到图像的相应位置上；D2的第2个系数符号是P，表示正数，对应S2的量化符号是“0”，因此解码输出的系数为20，把它放到图像的相应位置上；其余的符号都是T，因此在相应的位置上用“0”表示。
下一步确定是否继续进行解码以得到更精细的图像。如果要退出，则把两次解码的结果合成之后就可退出。如果继续，则进入第三次解码。
图9-17 第二次解码
(3) 第三次解码解码器将使用编码器第三次扫描产生的信息，
D3,PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
S3,?1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
S3中用下划线表示在第二次解码时已经得到的系数。解码器首先修改阈值，使新的阈值，然后构造如图9-18所示的量化器，进入第三次解码。
按照第二次解码步骤，首先提高第二次解码已经得到的系数的精度，然后求解其余的系数，最后把它与第二次解码得到的结果进行合成，得到如图9-18 所示的小波图像的重构系数。图中的符号“×”表示没有还原的系数，显示图像时可用一个幅度等于或者小于的数值取代。
图9-18 第三次解码
9.4 SPIHT编码
9.4.1 介绍受EZW算法和Amir Said本人开发的IEZW(improved embedded zerotree wavelet)算法的启发，Amir Said和William Pearlman在1996年发表了他们对EZW的改进算法[10]，叫做SPIHT(set partitioning in hierarchical trees)算法，可考虑译成“层树分集”算法。SPIHT算法具有人们所期望的特性，例如，图像的渐进传输，比较高的PSNR，复杂度比较低，计算量比较少，位速率容易控制等。
图像经过小波变换之后，大部分能量都集中在低频子带。SPIHT算法就是从这个事实出发，最先传送幅度大的系数，这样解码器即使在低速率应用环境下也可得到图像的大部分信息。编码树的结构与EZW算法的结构类似，每一个节点要么没有子节点，要么有4个子节点。在编码过程中，使用三个列表变量存储重要系数和不重要系数。
9.4.2 渐进图像的传输小波图像编码方法的开发与渐进图像(progressive image)如何传输有着密切的关系。传输渐进图像的方法很多，SPIHT算法采用的方法是幅度大的系数先传送，其理由说明如下。
假设原始图像由一组像素组成，用表示经过小波变换之后产生的系数，其中为像素的坐标，也是小波图像系数的坐标。为简化符号，使用字母表示二维图像，用表示小波变换之后的系数，因此一幅图像的小波变换可表示成，
表示单式(unitary)分层子带变换，经过小波变换之后的二维阵列具有与相同的维数。每一个元素可用二进制数的格式表示，例如典型的位数为16位。
在渐进图像传送中，解码器开始设置的重构矢量通常为零，然后按照接收到的编码信息进行修改。在接收到系数的近似值或者精确值之后，解码器可以得到重构的图像，
其中，表示小波变换的逆变换。为使接收端能够尽快看到图像的主要内容，就需要对图像的内容进行选择。选择的原则是解码器重构的图像与原始图像最接近。如果用均方差(mean square error，MSE)指标来衡量，则失真程度可表示为，
其中为图像的像素数目，是由系数重构的像素值。由于欧几里得范数(Euclidean norm)即向量的长度相对于单式变换是不变的，因此可以证明，
(去掉一个)
该式表明，解码器开始使用的系数近似值为零时，最大的系数对减少均方差最重要，因此幅度比较大的系数需要先传送。
根据幅度大的系数先传送的原则，就需要对系数进行排序。如何排序就是SPIHT编码方法想解决的问题。假设传送的系数已经按要求排了序，当系数用二进制的形式表示时，同样根据幅度大的系数先传送的原则，自然而然地会按照最高有效位最先传送的原则进行传输。在渐进图像传输中，这个方法叫做位平面(bit plane)方法。这个原则也体现在SPIHT编码中。
9.4.3 分集排序算法
SPIHT编码算法的一个特点是不单独传输系数的排序信息。这样做的基本依据是任何排序算法的执行路径都是使用分支点的比较结果进行定义的，如果编码器和解码器使用相同的排序算法，解码器就可重复编码器的执行路径，因此排序信息可从执行路径中重新获得。
根据这种思想，分集排序算法(set partitioning sorting algorithm)不对所有系数进行排序，而是按照一种规则选择发送的系数，这个规则是
其中，实际上就是EZW算法中的阈值。编码时每扫描一遍，新的阈值就设置为。对给定的，如果，就称系数是重要(significant)的，否则就称系数是不重要的(insignificant)
按照参数选择规则，分集算法把像素集分成许多子集，并且对子集中的系数幅度作如下的测试，
吗？
如果对这个问题的回答是“否”，说明这个子集不重要，解码器接收到这个信息也就知道这个子集中所有系数是不重要的；如果对这个问题的回答是“是”，说明这个子集重要，解码器接收到这个信号之后，按照编码器的规则把这个子集分成新的子集，然后对这个新的子集做相同的测试。这个子集分割过程一直到对所有重要子集完成幅度测试为止，目的是标识每一个重要系数。
幅度比较和比较结果之间的关系使用下面的函数表示，
为简化单个系数集的记号，用表示。
9.4.4 类型和变量
SPIHT算法定义的编码树的结构如图9-19所示。树的每一个节点与一个系数相对应，并且用坐标来标识，每一个节点的直接子孙(offspring)或者叫做子节点与相同空间方向的高一级子带的系数相对应。编码树定义为每一个节点有4个直接子孙或者没有直接子孙。最低子带的一个系数(图中用“*”标记)和最高子带的系数都没有子孙(descendant)。如果是父节点，它的子节点定义为，，和。
图9-19 父子(parent-offspring)关系在SPIHT算法中，使用坐标标记的方法，定义了四种坐标集来表示小波系数的类型，并用下面的符号表示：
：所有子节点的坐标集。
：所有子孙节点的坐标集。
：所有树根的坐标集。
：除子节点之外的所有子孙节点的坐标集。
在SPIHT编码算法中，使用最频繁的坐标集是和。因此，如果说或者坐标集是重要的，就意味着这个坐标集中至少有一个系数的幅度大于或者等于阈值。或者反过来说，如果或者坐标集中至少有一个系数的幅度大于或者等于阈值，那么该坐标集是重要的。
由于测试重要系数的次序很重要，在实际执行SPIHT算法的过程中，重要信息存储在三种次序列表变量中，因此执行SPIHT算法就变成了对三种表格的维护。定义的三种次序列表变量是：
LIP (List of Insignificant Pixels),不重要像素表，用于存放单个不重要的系数。用低通(或者叫做DC)子带的系数初始化。
LIS (List of Insignificant Sets)：不重要子集列表，用于存放不重要的系数树。用DC子带中不重要的系数集的坐标初始化。
LSP (List of Significant Pixels)：重要像素表，用于存放重要系数。初始化成空集。
在这三种列表中，每一个表项都使用坐标来标识。在LIP和LSP中，坐标用来代表单独的系数；在LIS列表中，坐标用来代表所有子孙节点的坐标集，或者代表除子节点之外的所有子孙的坐标集。为便于描述LIS中的坐标集，又把坐标集命名为A型(Type A)树，把坐标集命名为B型(Type B)树：
A型树也称D型树：LIS代表坐标集，编码时需要检查所有的子孙系数以确定是否重要。
B型树也称L型树：LIS代表坐标集，编码时需要检查除子系数之外的所有子孙系数以确定是否重要。
9.4.5 算法为了更好地理解SPIHT算法，下面引用的是Amir Said和William Pearlman开发的原始算法，笔者仅对它作了些注释。
******************************************************************************
符号：
= {the 4 offspring of } //系数的4个子系数组成的坐标集
= {all descendants of } //系数的所有子孙系数组成的坐标集
//除子节点之外的所有子孙节点的坐标集
= 1 if some element of has magnitude ,
//在子孙坐标集中有幅度大于或者等于阈值的坐标集
0 otherwise // 在子孙坐标集中没有幅度大于或等于阈值的坐标集
// 重要系数测试方法：
=1 if {} has magnitude,
// 在系数集{}中有幅度大于或等于阈值的系数
0 otherwise // 在系数集{}中没有幅度大于或等于阈值的系数变量：
LIP (List of Insignificant Pixels) // 存放单个不重要的系数
LIS (List of Insignificant Sets) // 存放不重要的系数树
Entries are, of type A； // 是A型树
of type B // 是B型树
LSP( List of Significant Pixels) // 存放重要系数
******************************************
1,Initialization: // 初始化
output n =?log2(largest coefficient)? 确定阈值
set LSP = {} // 设置LSP为空集
set LIP = {| is a root } // 把坐标加到LIP
set LIS = {of type A | is a root } // 把所有树指定为类型A，加到LIS
2,Sorting Pass:
// 排序扫描主要是检查LIP和LIS中的系数是否重要，然后把重要的系数移到LSP
for each entry in LIP do // 检查LIP中的所有系数以确定是否重要
output
if = 1 then move to LSP,output sign()
for each entry in LIS do // 检查LIS中的所有D型树以确定是否重要
if entry has type A then
output
if = 1 then
for each in do
output
if =1 then
add to LSP and output sign of
else
add to the end of LIP.
if is not empty then
move to end of LIS as entry of type B
else
delete from LIS and go around the loop.
if entry has type B then // 检查LIS中的所有L型树以确定是否重要
output
if = 1 then
for each in do
add to end of LIS as entry of type A
remove from LIS
3,Refinement Pass: // 精细扫描主要是处理LSP中的系数以增加它的精度
for each in LSP do
if was not added in the last sorting pass then
output the n-th most significant bit of .
4,Quantization Step:
decrement n,go back to Sorting Pass.
******************************************************************************
9.4.6 算法举例为进一步理解SPIHT算法，选用了Agnieszka C,Miguel在1999年攻读博士期间分析SPIHT算法时提供的一个例子[11]，笔者对她使用的坐标系统作了修改。
1．执行SPIHT算法的步骤：
(1) 计算阈值和初始化。初始化把低通子带中的所有根节点的系数赋给LIP，把所有树(指定为D型树)赋给LIS，把LSP初始化为空集。
(2) 检查LIP中的所有系数以确定是否重要：
① 如果重要，输出“1”和符号位，然后把该系数移到LSP。
② 如果不重要，输出“0”
(3) 按照树的类型，检查LIS中所有重要的树：
① D型树：
如果该树是重要的，输出“1”，然后对子节点的系数进行编码：
如果子节点的系数是重要的，输出“1”和符号位，然后把它移到LSP中。
如果子节点的系数是不重要的，输出“0"，然后把它移到LIP中。
如果子节点有后裔，就把这棵树移到LIS列表的末端，并作为L型树。
如果该树不重要，输出“0”
② 对L型树：
如果该树是重要的，输出“1”，把每一个子节点移到LIS的末端作为D型树，然后把父树从LIS中删除。
如果该树不重要，输出“0”。
(4) 减少阈值，然后返回到(2)。
2,小波图像系数的编码一幅4×4图像经过小波变换的两次分解后的系数为：
创建如图9-20所示的一棵编码系数树:
图9-20 编码系数树
******************************************************************************
计算初始阈值T＝16。初始化,LIP = { (0,0) },LIS = { (0,0)D },LSP = { }
-----------------------------------------------------------------------------------------------------------
主扫描1:
T = 16
输出
Is (0,0) significant? yes,
1
LSP = {(0,0)}
1 (sign bit)
Is D(0,0) significant? no,
0
LIP = {},LIS = { (0,0)D },LSP = { (0,0) }
3 bits
-----------------------------------------------------------------------------------------------------------
辅扫描1:
没有符号要处理
-----------------------------------------------------------------------------------------------------------
主扫描2:
T = 8
Is D(0,0) significant? yes,
1
Is (1,0) significant? no,
0
Is (0,1) significant? no,
0
Is (1,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1) },LIS = { (0,0)L }
Is L(0,0) significant? yes,
1
LIS = { (1,0)D,(0,1)D,(1,1)D }
Is D(1,0) significant? yes,
1
Is (2,0) significant? yes,
1
LSP = { (0,0),(2,0) }
1 (sign bit)
Is (2,1) significant? yes,
1
LSP = { (0,0),(2,0),(2,1) }
1 (sign bit)
Is (3,0) significant? no,
0
Is (3,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1),(3,0),(3,1) },LIS = { (0,1)D,(1,1)D }
Is D(0,1) significant? no,
0
Is D(1,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1),(3,0),(3,1) },LIS = { (0,1)D,(1,1)D },
LSP = { (0,0),(2,0),(2,1) }
14 bits
-----------------------------------------------------------------------------------------------------------
辅扫描 2:
同EZW算法的辅扫描
1 bit
-----------------------------------------------------------------------------------------------------------
主扫描3:
T = 4
Is (1,0) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0)}
1 (sign bit)
Is (0,1) significant? no,
0
Is (1,1) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1)}
0 (sign bit)
Is (3,0) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0)}
1 (sign bit)
Is (3,1) significant? no,
0
LIP = { (0,1),(3,1) }
Is D(0,1) significant? no,
0
Is D(1,1) significant? yes,
1
Is (2,2) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2)}
0 (sign bit)
Is (2,3) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2),(2,3)}
1 (sign bit)
Is (3,2) significant? no,
0
LIP = { (0,1),(3,1),(3,2) }
Is (3,3) significant? no,
0
LIP = { (0,1),(3,1),(3,2),(3,3) }
LIP = { (0,1),(3,2),(3,2),(3,3) },LIS = { (0,1)D },
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2),(2,3)}
16 bits
-----------------------------------------------------------------------------------------------------------
辅扫描3,
同EZW算法的辅扫描
3 bits
-----------------------------------------------------------------------------------------------------------
如果不再继续编码，总的位数为37位。
9.5 EBCOT编码简介
9.5.1 介绍最佳截断嵌入码块编码 (embedded block coding with optimized truncation，EBCOT)是David Taubman在1999年发表的一种编码算法[12]，现正处在进一步开发之中。该方法与早期的EZW，SPIHT以及Taubman和Zakhor开发的LZC(layered zero coding)等算法有着不同程度的联系。
EBCOT算法是一种对小波变换产生的子带系数进行量化和编码的方法。它的基本思想是把每一个子带的小波变换系数分成独立编码的码块(code-block)，并且对所有的码块使用完全相同的编码算法。如图9-21所示，图(a)表示使用小波变换进行三级分解之后的图像子带，图(b)表示经过这种变换之后各个子带的Lena图像，EBCOT算法的基本出发点就是把每一个图像子带的系数分成独立编码的码块。
(a) 图像子带划分法 (b) Lena图像子带图9-21 独立编码的码块对每一个码块进行编码时，编码器不用其他码块的任何信息，只是用码块自身的信息产生单独的嵌入位流(bitstream)。每一码块的嵌入位流可以被截断成长度不等的位流，生成不同的位速率，这就是EBCOT编码算法中“截断”的含义。
每一码块的嵌入位流应该截断到什么程度才符合特定的目标位速率、失真限度或者其他衡量图像质量的指标，也就是在给定一个目标位速率的情况下，使重构图像的失真程度最小，David Taubman提出了一种认为是“最佳”的方法来截断每一个独立码块的位流，这就是EBCOT编码算法中“最佳”的含义。
概括地说，EBCOT编码的主要想法是把嵌入码块编码方法与码块位流的最佳截断方法结合在一起，使重构图像的失真最小，它的主要特性包括分辨率可变(resolution,scalability)、信噪比可变(SNR scalability)和随机访问(random access)。这些特性比较适合包括大图像的远程浏览，但在具体实施过程中，普遍感到实现这些特性的算法比较复杂些。
9.5.2 质量层的概念
EBCOT编码算法引入了一个“质量层(quality layers)”的概念。图像的最终码块位流以质量层的形式组织，每一层都包含每一个码块对图像质量的贡献，如图9-22所示。为简单起见，图9-22中只画了7个码块的位流，每一个码块的质量层只画了5层，其中某些码块对质量没有贡献的层用“空”表示。
图9-22 EBCOT质量层的概念
EBCOT算法包含两种不同的编码器(coding engine)来体现它的性能。这两种编码器分别叫做层1编码器T1(Tier 1)和层2编码器T2(Tier 2)，如图9-23所示。T1编码器处理变换图像的小波变换系数，并把截断点放到码块中。后者把来自T1编码器的零碎码块放到不同的质量层，与不同的位速率相对应，并生成实际的压缩位流和文件。
图9-23 EBCOT两层编码系统
9.5.3 位速率失真最佳
EBCOT算法把表示图像的子带分成相对比较小的许多码块，表示第个码块。每一个码块中的位流可以被截断成各种长度的位流，在重构图像时计算由这些截断位流引起的失真。对重构图像产生的失真用表示，并假设失真度量是相加的，整个图像的失真表示为，
其中，表示码块选择的截断点。相加性的失真度量可用均方差或者加权的均方差。
对某一组截断点{}，位流中某一层的位速率用表示
EBCOT算法的目的就是在的限制条件下找一组截断位流使失真最小。这个问题可使用拉格朗日(Lagrange)乘法求解，把问题就转化为求解使函数
最小化的问题。其中的值必须进行调整，直到使该函数最小时的截断位流产生的速率满足。期待总是能够找到使实际的位速率与目标位速率完全相等的值是不现实的，但可以找到使函数最小的某个值，使相应的位流产生的失真最小。
9.6 JPEG 2000简介
9.6.1 JPEG 2000是什么
JPEG 2000是由ISO/IEC JTC1 SC29标准化小组负责并正在制定的新的静态图像编码国际标准。该标准从1996年1月开始启动，企图在2000年基本完成。由于它想获得的功能强大，因此受到信息技术界的广泛关注，期待着它的早日出台，同时也想在标准中加入自己的研究工作。为便于阅读JPEG 2000的文献，需要对文献中涉及到的一些组织作一个简单的介绍。
JPEG是Joint Picture Expert Group的缩写，即联合图像专家组；ISO(International Standard Organization)—国际标准化组织是1946年成立的一个自愿参加和无条约约束的国际组织，主要负责制定包括计算机、通信等众多领域的国际标准，以方便国际间信息、科学、技术、经济等活动领域的相互交流合作，其成员为各个国家的国家标准化组织，目前共有89个国家参加了该组织；IEC (International Electrotechnical Commission)—国际电工技术委员会是1906年成立的制订国际性的电、电子器件和系统标准的一个委员会，有40多个国家参加。实际上，有许多工程师 既是ISO的成员，又是IEC的成员。因此，它们的很多标准是一样的。而JTC1就是它们的合作领导小组，其中的SC 29负责JPEG 2000系列标准的制定。
SC29分WG1、WG11和WG12三个小组。WG1是负责JBIG和JPEG标准的制定，其中JBIG(Joint Binary Image Group)的中文术语叫做“联合二值图像专家组”，负责制定二值图像的压缩标准；WG11负责MPEG标准的制定，MPEG(Move Picture Expert Group)的中文术语叫做“运动图像专家组”。WG12负责MHEG标准的制定，MHEG(Multimedia Hypertext Expert Group)的中文术语叫做“多媒体超文本专家组”。
9.6.2 JPEG 2000的基本结构
JPEG 2000编码器的方框图如图9-24(a)所示。首先对源图像数据进行变换，再对变换的系数进行量化，然后在形成代码流(codestream)或者叫做位流(bitstream)之前进行熵(entropy)编码。解码器与编码器正好相反，如图9-24(b)所示。首先对码流进行熵解码，然后进行逆量化和逆向变换，最后进行图像的重构。
图9-24 JPEG 2000的基本结构
JPEG 2000标准是以图像块作为单元进行处理的。这就意味着图像数据在进入编码器之前要对它进行分块。如图9-25所示，左图表示对图像进行分块，右图表示对每一个图像块进行处理，中间的方框表示在对每个图像块进行正向变换之前，图像块分量的所有样本都减去一个相同的量，这叫做直流电平(DC)变换。图像分块处理时，对图像块的大小没有限制，图像的变换、量化和熵编码等所有的处理都是以图像块为单元。这样做有两个明显的好处，一是可以降低对存储器的要求，二是便于抽出一幅图像中的部分图像。其缺点是图像质量有所下降，但不明显。
图9-25 图像分块、直流电平变换和图像块变换图像变换使用离散小波变换。JPEG 2000标准使用子带分解，把样本信号分解成低通样本和高通样本。低通样本表示减低了分辨率的图像数据样本，高通样本表示降低了分辨率的图像数据样本，用于需要从低通样本重构出分辨率比较高的图像。离散小波变换可以是不可逆的小波变换，也可以是可逆的小波变换。JPEG 2000标准默认的不可逆小波变换是Daubechies 9-tap/7-tap[13][14]，默认的可逆变换采用5-tap/3-tap滤波器。JPEG 2000标准支持两种滤波方式：基于卷积(convolution-based)和基于(lifting-based)。
JPEG 2000的基本编码方法是在EBCOT算法基础上开发的。
9.6.3 JPEG 2000的主要功能与过去的图像压缩标准相比，JPEG 2000标准既提高了性能又增加了功能。在相同质量的前提下与JPEG标准相比，JPEG 2000标准的压缩比可提高20%以上。
JPEG 2000能实现渐进传输(progressive transmission)，这是JPEG 2000的一个重要特性。它可先传输低分辨率的图像或者是图像的轮廓，然后逐步传输其他数据，不断提高图像质量，以满足用户的需要。这个特性在多媒体网络应用中有重要的意义。例如，当下载一幅图像时，可比较快地看到这幅图像的概貌，根据对图像质量的要求和可用的网络带宽控制下载图像的数据量。
JPEG 2000另一个重要特性是支持兴趣区(region of interest,ROI)的编码。用户利用这个特性可指定感兴趣的图像区域，在压缩时对这些图像区指定特定的压缩质量，或在恢复时指定特定的解压缩要求，这给用户带来了极大的方便。例如，在有些情况下图像中只有一小块区域对用户是有用的，对这些区域采用低压缩比，而其他区域采用高压缩比，在保证不丢失重要信息的同时能有效地压缩数据量。
练习与思考题什么叫做零树？
解释EZW的含义。
如果条件允许，用MATLAB或者其他语言编写执行EZW算法的编码和解码程序解释SPIHT的含义。
如果条件允许，用MATLAB或者其他语言编写执行SPIHT算法的编码和解码程序。
请用因特网搜索工具，查找并阅读EBCOT的详细说明。
如果条件允许，用MATLAB或者其他语言编写执行EBCOT算法的编码和解码程序
JPEG 2000有许多功能，请用因特网搜索工具调查和描述它的详细功能。
参考文献和站点
Daubechies,I.,Orthonormal Bases of Compactly Supported Wavelets,Comm,Pure and Applied Math.,vol,41,Nov,1988,pp,909-996.
A,Cohen,I,Daubechies and J.C.Feauveau,Biorthogonal bases of compactly supported wavelets,Communications on Pure and Applied Mathematics,45(5)：485-560,June 1992.
Wim Sweldens，The Construction and Application of Wavelets in Numerical Analysis，May 18,1995
Sweldens,W,The Lifting Scheme,A Construction Of Second Generation Wavelets,Siam J,Math,Anal,Vol,29,No,2,1997.
A,K,Jain,Fundamentals of Digital Image Processing,Prentice-Hall,Englewood Cliffs,New Jersey,1989.
Lewis,A,S,and Knowles,G,Image Compression Using the 2-D Wavelet Transform,IEEE Trans,IP,vol,1,no,2,April 1992,pp,244-250,
Shapiro,J,M,Embedded Image Coding Using Zerotrees of Wavelet Coefficients,IEEE Trans,SP,vol,41,no,12,Dec,1993,pp,3445-3462.
http://perso.wanadoo.fr/polyvalens/clemens/clemens.html(访问日期:2001年8月2日)
Ghassan Al-Regib,Embedded Zerotree Wavelet Encoding (EZW) Based on Sharipo’s Paper,04/05/2000,Georgia Institute of Technology,Atlanta,GA.
A,Said and W,Pearlman,A new,fast and efficient image codec based on set partitioning in hierarchical trees,IEEE Trans,Circuits System,Video Technology,vol,6,pp,243–250,June 1996.
Agnieszka C,Miguel，Teaching Notes,Set Partitioning in Hierarchical Trees (SPIHT)，1999.
David Taubman,High performance scalable image compression with EBCOT,Image Processing,IEEE Transactions on,Volume,9 Issue,7,July 2000,Page(s),1158 - 1170.
M,Antonini,M,Barlaud,P,Mathieu and I,Daubechies,Image Coding Using the Wavelet Transform,IEEE Trans,Image Proc.,pp,205-220,April 1992.
C,Christopoulos,A,Skodras and T,Ebrahimi,The JPEG 2000 still image coding system,An Overview,IEEE Transactions on Consumer Electronics,2000,Vol 46,No,4,pp,1103-1127,November 2000,
Vetterli,M,and Herley,C.,Wavelets and Filter Banks,Theory and Design,IEEE Trans,SP,vol,40,no,9,Sep,1992,pp,2207-2232,
Ramchandran,K.,Vetterli,M.,Herley,C.，Wavelets,subband coding,and best bases，Proceedings of the IEEE,Volume,84 Issue,4,April 1996，Page(s),541 -560.
Ingrid Daubechies，Wim Sweldens，Factoring Wavelet Transforms into Lifting Steps，J,Fourier Anal,Appl.,Vol,4,Nr,3,pp,247-269,1998,
由于小波变换技术在20世纪90年代初期已经比较成熟，因此从那时起就开始出现各种新颖的小波图像编码方法。这些编码方法包括EZW,在EZW算法基础上改进的SPIHT和EBCOT等。由于EZW算法的开拓给后来者带来很大的启发，它是一种有效而且计算简单的图像压缩技术，因此本章将重点介绍。
9.1 从子带编码到小波编码
9.1.1 子带编码子带编码(subband coding，SBC)的基本概念是把信号的频率分成几个子带，然后对每个子带分别进行编码，并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代，子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点，20世纪80年代中期开始在图像编码中使用。1986年Woods,J,W.等科学家曾经使用一维正交镜像滤波器组(quadrature mirror filterbanks，QMF)把信号的频带分解成4个相等的子带，如图9-01所示。图9-01(a)表示分解方法，图9-01(b)表示其相应的频谱。图中的符号表示频带降低1/2，HH表示频率最高的子带，LL表示频率最低的子带。这个过程可以重复，直到符合应用要求为止。这样的滤波器组称为分解滤波器树(decomposition filter trees)。
(a) 分解法 (b) 频谱图9-01 Lena图的子带编码(1984年)
9.1.2 多分辨率分析
S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolution analysis)的概念，从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法，叫做Mallat算法。根据Mallat和Meyer等科学家的理论，使用一级小波分解方法得到的图像如图9-02所示。
图9-02 Lena的两种分辨率分析图像(1986年)
如果在一级分解之后继续进行分析，这种分解过程叫做多分辨率分析，实际上就是多级小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像，这些图像叫做多分辨率图像(multiresolution images)。图9-03表示Lena的多分辨率图像。其中，粗糙图像1的分辨率是原始图像的1/4，粗糙图像2的分辨率是粗糙图像1的1/4。
图9-03 Lena的多分辨率分析图像(1986年)
9.1.3 滤波器组与多分辨率为了压缩语音数据，在1976年Croisier,Esteban和Galand介绍了一种可逆滤波器组(invertible filter bank)，使用滤波和子采样(subsampling)的方法用来把离散信号分解成大小相等的两种信号，并且使用叫做共轭镜像滤波器(conjugate mirror filters)的一种特殊滤波器来取消信号的混叠(aliasing)，这样可从子采样的信号中重构原始信号。这个发现使人们花费了10多年的努力来开发一套完整的滤波器组理论。
正交小波的多分辨率理论(multiresolution theory)已经证明，任何共轭镜像滤波器都可以用来刻画一种小波，它能够生成实数空间中的正交基，而且快速离散小波变换可以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示了数字信号处理和谐波分析之间关系，这就使人们一直在致力于解决它们之间的关系问题。
9.1.4 从子带编码到小波编码在过去的年代里，人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波编码技术(wavelet coding，WC)的旗号下，人们提出了许多与子带编码技术非常类似和密切相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的小波基函数系列可以在连续的时间域中构造，但如何在离散的时间域中构造是一个现实问题。
在众多的研究者中，Inrid Daubechies在离散的时间域中构造小波基函数方面做出了杰出的贡献。她于1988年[1]最先揭示了小波变换和滤波器组之间的内在关系：离散时间滤波器(discrete-time filters)或者正交镜像滤波器(quadrature mirror filter,QMF)可以被叠代，并在某一种匀称(regularity，可粗略理解为函数的平滑性)条件下可获得连续小波。这是一个非常实际和极其有用的发现，这就意味着可使用有限冲击响应(finite impulse response，FIR)的离散时间滤波器来执行小波分解，使用相同的滤波器可重构小波分解之后的信号。由此可见，早期开发的子带编码实际上是一种小波变换。
在Daubechies揭示小波变换和滤波器组之间的关系之前，在图像编码中小波技术并不流行。从20世纪90年代开始，Cohen,Daubechies和Feauveau，简称为CDF，系统地开发了构造紧支持双正交小波(compactly supported biorthogonal wavelets)的方法[2]，以及其他学者提出的各种算法，使小波技术在图像编码中得到广泛的应用。
在构造小波和开发小波变换算法中，比利时成长的年轻学者Wim Sweldens在1994年的博士论文中首先提出了“The Lifting Scheme”[3][4]，简称Lifting/lifting(提升法)。该方法的基本思想是首先把信号分成偶数号样本和奇数号样本，根据信号本身的相关性，奇数样本使用偶数样本进行预测，由预测丢失的信号叫做信号的细节信息，然后调整偶数样本以保存原始信号的粗糙信息和细节信息。该方法保留了小波分析的特性(时间频率局部化和快速计算)，通过放弃小波的平移和缩放，并且放弃用傅立叶分析来构造小波，从而解决了非无限信号或者非周期信号的小波和小波变换问题，也使计算速度得到很大的提高，因此被称为第二代小波(second generation wavelets)，现在也成为制定JPEG 2000标准中小波部分的基础。
9.1.5 小波分解图像方法使用小波变换把图像分解成各种子带的方法有很多种。例如，均匀分解(uniform decomposition)，非均匀分解(non-uniform decomposition)，八带分解(octave-band decomposition)和小波包分解(wavelet-packet decomposition)，根据不同类型的图像选择不同小波的自适应小波分解(adaptive wavelet decomposition)等。其中，八带分解是使用最广泛的一种分解方法。这种分解方法属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分解的高频部分不再进一步分解。图9-04表示Lena图像的数据分解。
图9-04 Lena图像的数据分解
9.2 失真的度量方法在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比(peak signal to noise ratio,PSNR)来衡量,定义为最大像素值与均方差(mean square error，MSE)之比[5]，
(db)
对8位二进制图像，
(db)
其中，
其中，为原始图像的像素值，为解压缩之后的像素值。
在文献中，评估编码系统性能还使用其他方法，这些方法包括使用规格化均方差(normalized mean square error，NMSE)、信号噪声比(signal to noise ratio，SNR) 和平均绝对误差(mean absolute error，MAE)来度量，分别定义为
其中，为原始图像的像素值，为解压缩之后的像素值。
在电子工程中，信号噪声比(SNR)一直是最流行的误差度量指标，在大多数情况下可提供很有价值的信息，在数学上也比较容易计算。信号噪声比虽然也用在图像编码中，但由于它的数值与图像编码系统中高压缩比的关系不容易体现，因此提出了其他的几种度量方法，包括平均主观评分(mean opinion score，MOS)。
9.3 EZW编码
9.3.1 介绍在1992年，Lewis，A,S.和Knowles,G.首先介绍了一种树形数据结构来表示小波变换的系数[6]。在1993年，Shapiro,J,M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(embedded zerotree wavelet，EZW)算法[7]。EZW主要用于与小波变换有关的二维信号的编码，但不局限于二维信号。
嵌入(式)零树小波中的“小波”是指该算法以离散小波变换为基础，以大的小波变换系数比小的小波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实为背景。“零树”是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙(低频图像)和比较精细(高频图像)的小波系数，在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(threshold)，那么这棵树就叫做零树。“嵌入”是渐进编码技术(progressive encoding)的另一种说法，其含义是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像。图像合成的过程与分解的过程相反，使用子图像生成许多分辨率不同的图像。EZW编码指的是，按照用户对图像分辨率的要求，编码器可以进行多次编码，每进行一次编码，阈值降低1/2，水平和垂直方向上的图像分辨率各提高1倍。编码从最低分辨率图像开始扫描，每当遇到幅度大于阈值的正系数就用符号P表示，幅度的绝对值大于阈值的负系数用符号N表示，树根节点上的系数幅度小于阈值而树枝中有大于阈值的非零树用符号Z表示，零树用符号T表示。
小波图像编码(wavelet image coding)的一般结构如图9-05所示，它主要由小波变换(wavelet transform)、量化(quantization)和熵编码(entropy encoding)等3个模块组成。小波变换不损失数据，但它是EZW算法具有渐进特性的基础；量化模块对数据会产生损失，数据损失的程度取决于量化阈值的大小，EZW算法指的就是这个模块的算法，它的输出是符号集{P,N,T,Z,0,1}中的一系列符号；熵编码模块对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流(code stream)小于输入的码流。
图9-05 EZW算法结构
9.3.2 算法
EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次，生成一种分辨率图像，编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤：设置阈值、每个小波系数与阈值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表，一种是小波系数的符号表，另一种是量化表。
1,零树回顾二维小波变换的计算过程，不难想象各级子图像中的系数是相关的。在说明零树的概念之前，需要对小波变换得到的系数、名称和符号加以说明。现以3级分解的离散小波变换为例，图9-06表示Lena图像使用三级滤波器组做小波变换输出的子图像(sub image)。需要注意的是，分解之后的图像的名称在文献上有很多种，除了子图像之外，有的叫做子带图像(sub-band image)，有的把子图像进一步区分为高频子图像和低频子图像，或者粗糙图像和精细图像等名称。这些名称从不同的角度反映图像的特性，在不同的场合下使用可以收到异曲同工的效果。图9-06中的数字1,2和3表示分解的级数编号，LL3表示第3级的低频子图像，在这个例子中，它是分辨率最低的子图像。HL3表示第3级分解在水平方向上的子图像，LH3表示第3级分解在垂直方向上的子图像，HH3表示第3级分解在对角线方向上的子图像，其他的组合符号依此类推。由于低频子图像的系数要比高频子图像的系数大，零树编码技术就是利用这个事实来设计编码/解码过程中每一级使用的量化器。
图9-06 Lena三级分解图像
各级子图像中的系数之间的关系可以用树的形式描述。如图9-07(a)所示，最低频率的子图像在左上角，最高频率的子图像在右下角，由同一方向和相同空间位置上的所有小波系数组成一棵树。例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树。按箭头所指的方向，各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼。举例来说，LL3的系数为{63},HH2和HH1中的系数分别为{3}和{4,6,3,-2},由这些系数构成的树如图9-07(b)所示。如果把{63}指定为父系数，{3}就称为子系数，而{4,6,3,-2}中的4个系数就称为孙系数。
(a) 构造方法 (b) 小波系数举例图9-07 EZW编码树的构造
现在再来看零树的概念。为便于比较，把图9-07(b)所示的两棵树用图9-08(a)和(b)表示。假设编码时开始的阈值，由于63比32大，这样的树叫做非零树，如图9-08(a)所示。假设下一次编码时的阈值，把-13当作父系数，它的幅度比16小，而它的所有4个子系数的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图9-08(b)所示。根据以上的分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。
顺便要指出的是，小波图像系数结构的形式不只是上面介绍的一种，也可能不是最好的一种。
(a) 非零树例子 (b) 零树例子图9-08 非零树与零树的概念
2,扫描方法
EZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种，一种叫做光栅扫描(raster scan)，如图9-09(a)所示，另一种叫做迂回扫描(morton scan)，如图9-09(b)所示。
(a) 光栅扫描 (b) 迂回扫描图9-09 小波变换系数扫描方法
3,算法
EZW算法可粗略地归纳为下面几个主要步骤。
(1) 阈值的选择开始时的阈值通常按下式估算，
其中，MAX(.)表示最大的系数值，表示小波变换分解到第级时的系数。以后每扫描一次，阈值减少一半。
(2) 给系数分配符号使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第一种扫描叫做主扫描(dominant pass)，它的任务是把小波系数与阈值进行比较，然后指定表9-1中的4个符号之一，笔者把这种符号叫做系数符号，对整幅图像扫描之后产生系数符号序列。第二种扫描叫做辅扫描(subordinate pass)，其任务是对主扫描取出的带有符号P或者N的系数进行量化，产生代表对应量化值的符号“0”和“1”，笔者把这种符号称为量化符号。
主扫描：扫描每一个系数以产生系数符号如果系数幅度大于阈值()且为正数，输出符号P(positive)，
如果系数幅度的绝对值大于阈值()且为负数，输出符号N(negative)，
如果系数是零树根，输出T(zerotree)，
如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号Z(isolated zero)。
为了确定一个系数是否为零树根T或者是孤立零Z，需要对整个4叉树进行扫描，这样就需要花时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入一个标记或者零，这样做可防止对它们再编码。
辅扫描：量化带符号P和N的系数在量化系数之前要构造量化器。量化器的输入间隔为，该间隔被1.5分成两个部分：和，量化间隔为0.5,其中为第次编码。量化器的输出为量化符号“0”和“1”，“0”对应量化值为，“1”对应量化值为。
例如，第一次扫描时的阈值，量化器的间隔就为，该间隔被48分成两个相等的部分：和，量化间隔为16。对系数进行量化时，如果幅度在的范围里，该系数的量化值为“0”，对应的量化值为；如果幅度在的范围里，该系数的量化符号为“1”，它的量化值为，详见图9-13。
表9-1 EZW系数符号集判断条件
输出符号
P(positive)：表示正，重要系数
N(negative)：表示负，重要系数
所有子孙系数，
叫做零树的根
T：零树根，不重要系数
至少有一个子孙系数
Z：孤立的零，不重要系数
9.3.3 算法举例为进一步理解EZW算法，综合了C,Valens[8]和在读博士生Ghassan Al-Regib[9]提供的一个例子[7]。假设有一幅8×8的图像，离散小波变换矩阵为，经过小波变换之后的图像为，小波图像系数和扫描方式分别如图9-10(a)和(b)所示。另外还假设，图9-10(a)所示的数据是经过3级分解的小波图像系数。
(a) 小波图像数据 (b) 迂回扫描图9-10 8×8小波变换图像
1,树结构为叙述方便，图9-10(a)中的系数用组合符号(YM/YYN)表示。最低分辨率子图像(即第3级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关，它们之间构成的树如图9-11(b)所示。说明如下：
X1/LL3表示子带LL3的系数，它与第2级子图像中相关的子系数有3个：X1/HL2,X1/LH2和 X1/HH2。
X2/HL3表示子带HL3的系数，它与第2级子图像中相关的子系数有3个：X2/HL2,X2/LH2和X2/HH2。
X3/LH3表示子带LH3的系数，它与第2级子图像中相关的子系数有3个：X3/HL2,X3/LH2和X3/HH2。
X4/HH3表示子带HH3的系数，它与第2级子图像中相关的子系数有3个：X4/HL2,X4/LH2和 X4/HH2。
(a) 8×8子图像小波变换系数 (b) 最低频带小波变换系数树图9-11 编码树的结构(1)
在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它们之间构成的树如图9-12(b)所示，图中只表示了一部分的树。从图中可以看到，
X1/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X1/HL1,X2/HL1,X5/HL1和X6/HL1。
X2/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X3/HL1,X4/HL1,X7/HL1和X8/HL1。
X3/HL2表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X09/HL1,X10/HL1,X13/HL1和X14/HL1。
X4/HL2 表示子带HL2的系数，它与第1级子图像中相关的子系数有4个：X11/HL1,X12/HL1,X15/HL1和X16/HL1。
(a) 8×8子图像小波变换系数 (b) 2级子图像小波变换部分系数树图9-12 编码树的结构(2)
2,编码根据对图像分辨率的要求，编码时可对小波图像系数进行多次扫描。每一次扫描包括主扫描和辅扫描。
第一次扫描：
步骤1,选择初始阈值。最大的系数为63，因此选择。
步骤2,指定系数的符号。假设存放系数符号的缓冲存储器为D1，存放量化符号的缓冲存储器的符号为S1。扫描每一个系数并且与阈值32进行比较。在比较过程中对每一个系数指定一个符号，并把符号放在D1中。当一个系数被指定为符号T时，所有的子孙系数就不再扫描，并用“×”表示，扫描结果如图9-13(a)所示。图中，输出符号的下标表示系数被标识的次序，仅仅是为了叙述方便。对扫描结果作如下说明：
X1/LL3的系数是63，它大于阈值32，因此输出的符号为P1。
X2/HL3的系数是-34,它的符号输出为是N2。
③ X3/LH3的系数是-31,它的幅度相对于阈值32来说是不重要的，它下属子系数{X3/HL2,X3/LH2和X3/HH2}，孙系数{X9/HL1,X10//HL1,X13//HL1,X14//HL1},{X9//LH1,X10/LH1,X13/LH1,X14/LH1}和{X9//HH1,X10/HH1,X13/HH1,X14/HH1}的幅度都比它小，因此它输出的符号为零树符号T3。
④ X2/LH2的系数是14，它小于阈值32。在它的子系数{X3/LH1,X4/LH1,X7/LH1,X8/LH1}中,X4/LH1的系数是47,它大于阈值32,因此X2/LH2输出符号为孤立零符号Z8。
⑤ X4/LH1的系数是47，相对于阈值32是重要的，产生符号P16。
第一次主扫描之后，缓冲存储器D1中的系数符号为：
D1,P N T T P T T Z T T T T T T T P T T
(a) 系数符号和标记 (b)系数量化图9-13 第一次主扫描
步骤3,量化系数。对带符号P/N的系数进行量化。在第一次主扫描期间的阈值是32，幅度大于32的有4个系数{63，34，49，47}。用48把间隔分成两个部分,如图9-13(b)所示。幅度在间隔中的系数指定为符号“0”,幅度在间隔中的系数指定为符号“1”，于是这4个系数被编码成如表9-2所示的量化符号。顺便指出，由于解码器重构的系数幅度按进行计算，因此重构数据的绝对误差在1～7之间，即小于。
在第一次辅扫描之后，4个系数{63-P,34-N,49-P,47-P}的量化符号所组成的位流为：
S1,1 0 1 0
表9-2 第一次辅扫描量化表系数幅度
量化符号
重构幅度
63
1
56
34
0
40
49
1
56
47
0
40
步骤4,重新排列带P/N符号的数据。为便于设置第二次扫描时所用的量化间隔，以提高解码的系数精度，编码器对本次扫描取出的4个系数作重新排列，把系数集{63-P,34-N,49-P,47-P}排列成{63-P,49-P,34-N,47-P}。对于重新排序的问题也有人指出，从他们的实验结果看，精度提高不大但付出的计算代价却很高。
步骤5：输出编码信息。编码器输出两类信息，一类给解码器的系数符号系列等信息，另一类用于下一次扫描的阈值和大于阈值的系数值等信息。
① 给解码器的信息包含下面三种：
HEADER (即),D1,P N T T P T T Z T T T T T T T P T T,AND” S1,1 0 1 0.
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,34-N,47-P},AND”子带图像。
此处的“AND”仅为强调它们之间的对应关系
(2) 第二次扫描步骤1,设置新阈值：。
步骤2,指定系数的符号。使用“0”代替第一次扫描时被标识的系数，这些系数就不再被扫描，在图9-14中，用符号表示。然后扫描其余的系数，并与新的阈值进行比较。假设第二次存放系数符号的缓冲存储器为D2,存放量化符号的缓冲存储器S2，采用与第一次类似的扫描方法，得到的系数符号为，
D2：N P T T T T T T T T T T T T T T T
步骤3,量化系数。由于阈值是16,因此量化器的间隔有3个：，和，如图9-14所示。按照这次构造的量化器，对第二次主扫描得到的系数集{63-P,49-P,34-N,47-P,31-N,23-P}进行编码，得到的量化符号位流如下，
S2,1 0 0 1 1 0
图9-14 第二次主扫描步骤4,重新排列带P/N符号的数据。将系数集{63-P,49-P,34-N,47-P,31-N,23-P}排成{63-P,49-P,47-P,34-N,31-N,23-P}。
步骤5,输出编码信息。
① 给解码器的信息包含下面两种：
D2,N P T T T T T T T T T T T T T T T,AND” S2,1 0 0 1 1 0,
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,47-P,34-N,31-N,23-P},AND”子带图像.
(3) 第三次扫描步骤1,设置新阈值：。
步骤2,指定系数的符号。使用“0”代替第二次扫描时被标识的系数，这些系数就不再被扫描，在图9-15中，用符号表示。然后扫描其余的系数，并与新的阈值进行比较。假设第三次存放系数符号的缓冲存储器为D3,存放量化符号位流的缓存存储器为S3，采用与第一次类似的扫描方法，得到的系数符号为，
D3：PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
步骤3,量化系数。由于阈值是8,因此量化器有7个间隔：,,，，，和，如图9-15所示。按照这次构造的量化器，对第三次主扫描得到的系数集{63-P,49-P,47-P,34-N,31-N,23-P,10-P,14-P,13-N,15-P,14-P,9-N,12-N,14-N,8-P,13-P,12-N,9-P,9-P,11-P}进行编码，得到的量化符号位流如下，
S3,1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
图9-15 第三次主扫描
步骤4,重新排列带P/N符号的数据。将系数集{63-P,49-P,47-P,34-N,31-N,23-P,10-P,14-P,13-N,15-P,14-P,9-N,12-N,14-N,8-P,13-P,12-N,9-P,9-P,11-P}排成{63-P,49-P,47-P,34-N,31-N,23-P,14-P,13-N,15-P,14-P,12-N,14-N,13-P,12-N,10-P,9-N,8-P,9-P,9-P,11-P}。
步骤5,输出编码信息。
① 给解码器的信息包含下面两种：
D3,PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
“AND”
S3,1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0,
② 给下一次扫描用的信息包含下面三种：
,{63-P,49-P,,47-P,34-N,31-N,23-P,14-P,13-N,,15-P,14-P,12-N,14-N,13-P,
12-N,10-P,9-N,8-P,9-P,9-P,11-P},AND”子带图像.
根据对图像的压缩率或者数据的传送率等应用要求可决定是否继续编码。如果从此不再编码，编码器的输出流就为：Header-D1-S1-D2-S2-D3-S3。现把每次编码扫描输出的内容归纳在表9-3中。
表9-3 三次编码的输出名称
内容
Header
32
D1 /?S1
P N T T P T T Z T T T T T T T P T T /?1 0 1 0
D2 /?S2
N P T T T T T T T T T T T T T T T?/?1 0 0 1 1 0
D3 /?S3
PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT/
1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
请注意，这里所指的编码器输出是指没有经过熵编码的输出，这仅仅是为了便于说明EZW的算法。
3,解码
EZW的解码过程是EZW编码的逆过程，编码时扫描多少次，解码时也可以解多少次，这要取决于对图像分辨率或者传输环境的要求。解码过程大致分为三个步骤：在接收到编码器发送的信息之后，解码器首先设置阈值，构造逆量化器，然后开始解读位流中包含的位置和小波系数值。
由于解码时用的逆量化器与编码时用的量化器没有什么差别，因此简称为量化器。像编码时那样，在EZW解码过程中每次解码都需要构造量化器。
(1) 第一次解码解码器开始时的阈值，它接收到来自编码器第一次扫描输出的系数符号是，
P N T T P T T Z T T T T T T T P T T / 1 0 1 0
这个信息相当于量化符号所组成的位流与系数符号之间有如下的对应关系，
D1
P
N
T
T
P
T
T
Z
T
T
T
T
T
T
T
P
T
T
S1
1
0
1
0
解码码器要按照编码时的扫描和量化方法进行解码。输入位流的第1个系数符号是P，对应的量化符号位是“1”，因此第1个系数是56；第2个系数符号是N，对应的量化符号位是“0"，因此第2个系数是-40；第3个系数符号是T，在相应的图像系数位置上用“0”表示它的系数。第一次解码的结果如图9-16所示。用“0”表示的系数表示已经扫描过，它们对应符号T或者Z，用“×”表示的系数表示不需要扫描的系数，因为它们是零树根的子孙。
图9-16 第一次解码在第一次解码之后，解码器需要判断是否要进一步重构比较精细的图像。如果不需要，则退出解码，如果需要则进入第二次解码。
(2) 第二次解码第二次解码分两步。第一步：提高第一次解码时得到的系数的精度，第二步：求解未解码的系数。解码器将使用编码器生成的第二次编码时的扫描信息，
D2,N P T T T T T T T T T T T T T T T
S2,1 0 0 1 1 0
解码器首先修改阈值，使，然后构造一个如图9-17所示的量化器。开始时，解码器只看S2中用下划线表示的量化符号位流的前4位(1 0 0 1)，而不看D2中的符号，因为在第一次解码时已经知道了4个系数值是{56,-40,52,40}。S2的第1位是“1”，第一次译码之后的系数是56，现在使用新的量化器，56就变成60；S2的第2位是“0”，第一次译码之后的系数是-40，使用新的量化器之后的系数就变成-36。同样，其他2个系数分别由52变成56，40变成44。
在处理完前4个系数之后，解码器就开始求解在第一次解码时没有还原的系数，使用的间隔为，即。D2的第1个系数符号是N，表示负数，对应S2的量化符号是“1”，因此解码输出的系数为-28，把它放到图像的相应位置上；D2的第2个系数符号是P，表示正数，对应S2的量化符号是“0”，因此解码输出的系数为20，把它放到图像的相应位置上；其余的符号都是T，因此在相应的位置上用“0”表示。
下一步确定是否继续进行解码以得到更精细的图像。如果要退出，则把两次解码的结果合成之后就可退出。如果继续，则进入第三次解码。
图9-17 第二次解码
(3) 第三次解码解码器将使用编码器第三次扫描产生的信息，
D3,PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT
S3,?1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0
S3中用下划线表示在第二次解码时已经得到的系数。解码器首先修改阈值，使新的阈值，然后构造如图9-18所示的量化器，进入第三次解码。
按照第二次解码步骤，首先提高第二次解码已经得到的系数的精度，然后求解其余的系数，最后把它与第二次解码得到的结果进行合成，得到如图9-18 所示的小波图像的重构系数。图中的符号“×”表示没有还原的系数，显示图像时可用一个幅度等于或者小于的数值取代。
图9-18 第三次解码
9.4 SPIHT编码
9.4.1 介绍受EZW算法和Amir Said本人开发的IEZW(improved embedded zerotree wavelet)算法的启发，Amir Said和William Pearlman在1996年发表了他们对EZW的改进算法[10]，叫做SPIHT(set partitioning in hierarchical trees)算法，可考虑译成“层树分集”算法。SPIHT算法具有人们所期望的特性，例如，图像的渐进传输，比较高的PSNR，复杂度比较低，计算量比较少，位速率容易控制等。
图像经过小波变换之后，大部分能量都集中在低频子带。SPIHT算法就是从这个事实出发，最先传送幅度大的系数，这样解码器即使在低速率应用环境下也可得到图像的大部分信息。编码树的结构与EZW算法的结构类似，每一个节点要么没有子节点，要么有4个子节点。在编码过程中，使用三个列表变量存储重要系数和不重要系数。
9.4.2 渐进图像的传输小波图像编码方法的开发与渐进图像(progressive image)如何传输有着密切的关系。传输渐进图像的方法很多，SPIHT算法采用的方法是幅度大的系数先传送，其理由说明如下。
假设原始图像由一组像素组成，用表示经过小波变换之后产生的系数，其中为像素的坐标，也是小波图像系数的坐标。为简化符号，使用字母表示二维图像，用表示小波变换之后的系数，因此一幅图像的小波变换可表示成，
表示单式(unitary)分层子带变换，经过小波变换之后的二维阵列具有与相同的维数。每一个元素可用二进制数的格式表示，例如典型的位数为16位。
在渐进图像传送中，解码器开始设置的重构矢量通常为零，然后按照接收到的编码信息进行修改。在接收到系数的近似值或者精确值之后，解码器可以得到重构的图像，
其中，表示小波变换的逆变换。为使接收端能够尽快看到图像的主要内容，就需要对图像的内容进行选择。选择的原则是解码器重构的图像与原始图像最接近。如果用均方差(mean square error，MSE)指标来衡量，则失真程度可表示为，
其中为图像的像素数目，是由系数重构的像素值。由于欧几里得范数(Euclidean norm)即向量的长度相对于单式变换是不变的，因此可以证明，
(去掉一个)
该式表明，解码器开始使用的系数近似值为零时，最大的系数对减少均方差最重要，因此幅度比较大的系数需要先传送。
根据幅度大的系数先传送的原则，就需要对系数进行排序。如何排序就是SPIHT编码方法想解决的问题。假设传送的系数已经按要求排了序，当系数用二进制的形式表示时，同样根据幅度大的系数先传送的原则，自然而然地会按照最高有效位最先传送的原则进行传输。在渐进图像传输中，这个方法叫做位平面(bit plane)方法。这个原则也体现在SPIHT编码中。
9.4.3 分集排序算法
SPIHT编码算法的一个特点是不单独传输系数的排序信息。这样做的基本依据是任何排序算法的执行路径都是使用分支点的比较结果进行定义的，如果编码器和解码器使用相同的排序算法，解码器就可重复编码器的执行路径，因此排序信息可从执行路径中重新获得。
根据这种思想，分集排序算法(set partitioning sorting algorithm)不对所有系数进行排序，而是按照一种规则选择发送的系数，这个规则是
其中，实际上就是EZW算法中的阈值。编码时每扫描一遍，新的阈值就设置为。对给定的，如果，就称系数是重要(significant)的，否则就称系数是不重要的(insignificant)
按照参数选择规则，分集算法把像素集分成许多子集，并且对子集中的系数幅度作如下的测试，
吗？
如果对这个问题的回答是“否”，说明这个子集不重要，解码器接收到这个信息也就知道这个子集中所有系数是不重要的；如果对这个问题的回答是“是”，说明这个子集重要，解码器接收到这个信号之后，按照编码器的规则把这个子集分成新的子集，然后对这个新的子集做相同的测试。这个子集分割过程一直到对所有重要子集完成幅度测试为止，目的是标识每一个重要系数。
幅度比较和比较结果之间的关系使用下面的函数表示，
为简化单个系数集的记号，用表示。
9.4.4 类型和变量
SPIHT算法定义的编码树的结构如图9-19所示。树的每一个节点与一个系数相对应，并且用坐标来标识，每一个节点的直接子孙(offspring)或者叫做子节点与相同空间方向的高一级子带的系数相对应。编码树定义为每一个节点有4个直接子孙或者没有直接子孙。最低子带的一个系数(图中用“*”标记)和最高子带的系数都没有子孙(descendant)。如果是父节点，它的子节点定义为，，和。
图9-19 父子(parent-offspring)关系在SPIHT算法中，使用坐标标记的方法，定义了四种坐标集来表示小波系数的类型，并用下面的符号表示：
：所有子节点的坐标集。
：所有子孙节点的坐标集。
：所有树根的坐标集。
：除子节点之外的所有子孙节点的坐标集。
在SPIHT编码算法中，使用最频繁的坐标集是和。因此，如果说或者坐标集是重要的，就意味着这个坐标集中至少有一个系数的幅度大于或者等于阈值。或者反过来说，如果或者坐标集中至少有一个系数的幅度大于或者等于阈值，那么该坐标集是重要的。
由于测试重要系数的次序很重要，在实际执行SPIHT算法的过程中，重要信息存储在三种次序列表变量中，因此执行SPIHT算法就变成了对三种表格的维护。定义的三种次序列表变量是：
LIP (List of Insignificant Pixels),不重要像素表，用于存放单个不重要的系数。用低通(或者叫做DC)子带的系数初始化。
LIS (List of Insignificant Sets)：不重要子集列表，用于存放不重要的系数树。用DC子带中不重要的系数集的坐标初始化。
LSP (List of Significant Pixels)：重要像素表，用于存放重要系数。初始化成空集。
在这三种列表中，每一个表项都使用坐标来标识。在LIP和LSP中，坐标用来代表单独的系数；在LIS列表中，坐标用来代表所有子孙节点的坐标集，或者代表除子节点之外的所有子孙的坐标集。为便于描述LIS中的坐标集，又把坐标集命名为A型(Type A)树，把坐标集命名为B型(Type B)树：
A型树也称D型树：LIS代表坐标集，编码时需要检查所有的子孙系数以确定是否重要。
B型树也称L型树：LIS代表坐标集，编码时需要检查除子系数之外的所有子孙系数以确定是否重要。
9.4.5 算法为了更好地理解SPIHT算法，下面引用的是Amir Said和William Pearlman开发的原始算法，笔者仅对它作了些注释。
******************************************************************************
符号：
= {the 4 offspring of } //系数的4个子系数组成的坐标集
= {all descendants of } //系数的所有子孙系数组成的坐标集
//除子节点之外的所有子孙节点的坐标集
= 1 if some element of has magnitude ,
//在子孙坐标集中有幅度大于或者等于阈值的坐标集
0 otherwise // 在子孙坐标集中没有幅度大于或等于阈值的坐标集
// 重要系数测试方法：
=1 if {} has magnitude,
// 在系数集{}中有幅度大于或等于阈值的系数
0 otherwise // 在系数集{}中没有幅度大于或等于阈值的系数变量：
LIP (List of Insignificant Pixels) // 存放单个不重要的系数
LIS (List of Insignificant Sets) // 存放不重要的系数树
Entries are, of type A； // 是A型树
of type B // 是B型树
LSP( List of Significant Pixels) // 存放重要系数
******************************************
1,Initialization: // 初始化
output n =?log2(largest coefficient)? 确定阈值
set LSP = {} // 设置LSP为空集
set LIP = {| is a root } // 把坐标加到LIP
set LIS = {of type A | is a root } // 把所有树指定为类型A，加到LIS
2,Sorting Pass:
// 排序扫描主要是检查LIP和LIS中的系数是否重要，然后把重要的系数移到LSP
for each entry in LIP do // 检查LIP中的所有系数以确定是否重要
output
if = 1 then move to LSP,output sign()
for each entry in LIS do // 检查LIS中的所有D型树以确定是否重要
if entry has type A then
output
if = 1 then
for each in do
output
if =1 then
add to LSP and output sign of
else
add to the end of LIP.
if is not empty then
move to end of LIS as entry of type B
else
delete from LIS and go around the loop.
if entry has type B then // 检查LIS中的所有L型树以确定是否重要
output
if = 1 then
for each in do
add to end of LIS as entry of type A
remove from LIS
3,Refinement Pass: // 精细扫描主要是处理LSP中的系数以增加它的精度
for each in LSP do
if was not added in the last sorting pass then
output the n-th most significant bit of .
4,Quantization Step:
decrement n,go back to Sorting Pass.
******************************************************************************
9.4.6 算法举例为进一步理解SPIHT算法，选用了Agnieszka C,Miguel在1999年攻读博士期间分析SPIHT算法时提供的一个例子[11]，笔者对她使用的坐标系统作了修改。
1．执行SPIHT算法的步骤：
(1) 计算阈值和初始化。初始化把低通子带中的所有根节点的系数赋给LIP，把所有树(指定为D型树)赋给LIS，把LSP初始化为空集。
(2) 检查LIP中的所有系数以确定是否重要：
① 如果重要，输出“1”和符号位，然后把该系数移到LSP。
② 如果不重要，输出“0”
(3) 按照树的类型，检查LIS中所有重要的树：
① D型树：
如果该树是重要的，输出“1”，然后对子节点的系数进行编码：
如果子节点的系数是重要的，输出“1”和符号位，然后把它移到LSP中。
如果子节点的系数是不重要的，输出“0"，然后把它移到LIP中。
如果子节点有后裔，就把这棵树移到LIS列表的末端，并作为L型树。
如果该树不重要，输出“0”
② 对L型树：
如果该树是重要的，输出“1”，把每一个子节点移到LIS的末端作为D型树，然后把父树从LIS中删除。
如果该树不重要，输出“0”。
(4) 减少阈值，然后返回到(2)。
2,小波图像系数的编码一幅4×4图像经过小波变换的两次分解后的系数为：
创建如图9-20所示的一棵编码系数树:
图9-20 编码系数树
******************************************************************************
计算初始阈值T＝16。初始化,LIP = { (0,0) },LIS = { (0,0)D },LSP = { }
-----------------------------------------------------------------------------------------------------------
主扫描1:
T = 16
输出
Is (0,0) significant? yes,
1
LSP = {(0,0)}
1 (sign bit)
Is D(0,0) significant? no,
0
LIP = {},LIS = { (0,0)D },LSP = { (0,0) }
3 bits
-----------------------------------------------------------------------------------------------------------
辅扫描1:
没有符号要处理
-----------------------------------------------------------------------------------------------------------
主扫描2:
T = 8
Is D(0,0) significant? yes,
1
Is (1,0) significant? no,
0
Is (0,1) significant? no,
0
Is (1,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1) },LIS = { (0,0)L }
Is L(0,0) significant? yes,
1
LIS = { (1,0)D,(0,1)D,(1,1)D }
Is D(1,0) significant? yes,
1
Is (2,0) significant? yes,
1
LSP = { (0,0),(2,0) }
1 (sign bit)
Is (2,1) significant? yes,
1
LSP = { (0,0),(2,0),(2,1) }
1 (sign bit)
Is (3,0) significant? no,
0
Is (3,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1),(3,0),(3,1) },LIS = { (0,1)D,(1,1)D }
Is D(0,1) significant? no,
0
Is D(1,1) significant? no,
0
LIP = { (1,0),(0,1),(1,1),(3,0),(3,1) },LIS = { (0,1)D,(1,1)D },
LSP = { (0,0),(2,0),(2,1) }
14 bits
-----------------------------------------------------------------------------------------------------------
辅扫描 2:
同EZW算法的辅扫描
1 bit
-----------------------------------------------------------------------------------------------------------
主扫描3:
T = 4
Is (1,0) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0)}
1 (sign bit)
Is (0,1) significant? no,
0
Is (1,1) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1)}
0 (sign bit)
Is (3,0) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0)}
1 (sign bit)
Is (3,1) significant? no,
0
LIP = { (0,1),(3,1) }
Is D(0,1) significant? no,
0
Is D(1,1) significant? yes,
1
Is (2,2) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2)}
0 (sign bit)
Is (2,3) significant? yes,
1
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2),(2,3)}
1 (sign bit)
Is (3,2) significant? no,
0
LIP = { (0,1),(3,1),(3,2) }
Is (3,3) significant? no,
0
LIP = { (0,1),(3,1),(3,2),(3,3) }
LIP = { (0,1),(3,2),(3,2),(3,3) },LIS = { (0,1)D },
LSP = { (0,0),(2,0),(2,1),(1,0),(1,1),(3,0),(2,2),(2,3)}
16 bits
-----------------------------------------------------------------------------------------------------------
辅扫描3,
同EZW算法的辅扫描
3 bits
-----------------------------------------------------------------------------------------------------------
如果不再继续编码，总的位数为37位。
9.5 EBCOT编码简介
9.5.1 介绍最佳截断嵌入码块编码 (embedded block coding with optimized truncation，EBCOT)是David Taubman在1999年发表的一种编码算法[12]，现正处在进一步开发之中。该方法与早期的EZW，SPIHT以及Taubman和Zakhor开发的LZC(layered zero coding)等算法有着不同程度的联系。
EBCOT算法是一种对小波变换产生的子带系数进行量化和编码的方法。它的基本思想是把每一个子带的小波变换系数分成独立编码的码块(code-block)，并且对所有的码块使用完全相同的编码算法。如图9-21所示，图(a)表示使用小波变换进行三级分解之后的图像子带，图(b)表示经过这种变换之后各个子带的Lena图像，EBCOT算法的基本出发点就是把每一个图像子带的系数分成独立编码的码块。
(a) 图像子带划分法 (b) Lena图像子带图9-21 独立编码的码块对每一个码块进行编码时，编码器不用其他码块的任何信息，只是用码块自身的信息产生单独的嵌入位流(bitstream)。每一码块的嵌入位流可以被截断成长度不等的位流，生成不同的位速率，这就是EBCOT编码算法中“截断”的含义。
每一码块的嵌入位流应该截断到什么程度才符合特定的目标位速率、失真限度或者其他衡量图像质量的指标，也就是在给定一个目标位速率的情况下，使重构图像的失真程度最小，David Taubman提出了一种认为是“最佳”的方法来截断每一个独立码块的位流，这就是EBCOT编码算法中“最佳”的含义。
概括地说，EBCOT编码的主要想法是把嵌入码块编码方法与码块位流的最佳截断方法结合在一起，使重构图像的失真最小，它的主要特性包括分辨率可变(resolution,scalability)、信噪比可变(SNR scalability)和随机访问(random access)。这些特性比较适合包括大图像的远程浏览，但在具体实施过程中，普遍感到实现这些特性的算法比较复杂些。
9.5.2 质量层的概念
EBCOT编码算法引入了一个“质量层(quality layers)”的概念。图像的最终码块位流以质量层的形式组织，每一层都包含每一个码块对图像质量的贡献，如图9-22所示。为简单起见，图9-22中只画了7个码块的位流，每一个码块的质量层只画了5层，其中某些码块对质量没有贡献的层用“空”表示。
图9-22 EBCOT质量层的概念
EBCOT算法包含两种不同的编码器(coding engine)来体现它的性能。这两种编码器分别叫做层1编码器T1(Tier 1)和层2编码器T2(Tier 2)，如图9-23所示。T1编码器处理变换图像的小波变换系数，并把截断点放到码块中。后者把来自T1编码器的零碎码块放到不同的质量层，与不同的位速率相对应，并生成实际的压缩位流和文件。
图9-23 EBCOT两层编码系统
9.5.3 位速率失真最佳
EBCOT算法把表示图像的子带分成相对比较小的许多码块，表示第个码块。每一个码块中的位流可以被截断成各种长度的位流，在重构图像时计算由这些截断位流引起的失真。对重构图像产生的失真用表示，并假设失真度量是相加的，整个图像的失真表示为，
其中，表示码块选择的截断点。相加性的失真度量可用均方差或者加权的均方差。
对某一组截断点{}，位流中某一层的位速率用表示
EBCOT算法的目的就是在的限制条件下找一组截断位流使失真最小。这个问题可使用拉格朗日(Lagrange)乘法求解，把问题就转化为求解使函数
最小化的问题。其中的值必须进行调整，直到使该函数最小时的截断位流产生的速率满足。期待总是能够找到使实际的位速率与目标位速率完全相等的值是不现实的，但可以找到使函数最小的某个值，使相应的位流产生的失真最小。
9.6 JPEG 2000简介
9.6.1 JPEG 2000是什么
JPEG 2000是由ISO/IEC JTC1 SC29标准化小组负责并正在制定的新的静态图像编码国际标准。该标准从1996年1月开始启动，企图在2000年基本完成。由于它想获得的功能强大，因此受到信息技术界的广泛关注，期待着它的早日出台，同时也想在标准中加入自己的研究工作。为便于阅读JPEG 2000的文献，需要对文献中涉及到的一些组织作一个简单的介绍。
JPEG是Joint Picture Expert Group的缩写，即联合图像专家组；ISO(International Standard Organization)—国际标准化组织是1946年成立的一个自愿参加和无条约约束的国际组织，主要负责制定包括计算机、通信等众多领域的国际标准，以方便国际间信息、科学、技术、经济等活动领域的相互交流合作，其成员为各个国家的国家标准化组织，目前共有89个国家参加了该组织；IEC (International Electrotechnical Commission)—国际电工技术委员会是1906年成立的制订国际性的电、电子器件和系统标准的一个委员会，有40多个国家参加。实际上，有许多工程师 既是ISO的成员，又是IEC的成员。因此，它们的很多标准是一样的。而JTC1就是它们的合作领导小组，其中的SC 29负责JPEG 2000系列标准的制定。
SC29分WG1、WG11和WG12三个小组。WG1是负责JBIG和JPEG标准的制定，其中JBIG(Joint Binary Image Group)的中文术语叫做“联合二值图像专家组”，负责制定二值图像的压缩标准；WG11负责MPEG标准的制定，MPEG(Move Picture Expert Group)的中文术语叫做“运动图像专家组”。WG12负责MHEG标准的制定，MHEG(Multimedia Hypertext Expert Group)的中文术语叫做“多媒体超文本专家组”。
9.6.2 JPEG 2000的基本结构
JPEG 2000编码器的方框图如图9-24(a)所示。首先对源图像数据进行变换，再对变换的系数进行量化，然后在形成代码流(codestream)或者叫做位流(bitstream)之前进行熵(entropy)编码。解码器与编码器正好相反，如图9-24(b)所示。首先对码流进行熵解码，然后进行逆量化和逆向变换，最后进行图像的重构。
图9-24 JPEG 2000的基本结构
JPEG 2000标准是以图像块作为单元进行处理的。这就意味着图像数据在进入编码器之前要对它进行分块。如图9-25所示，左图表示对图像进行分块，右图表示对每一个图像块进行处理，中间的方框表示在对每个图像块进行正向变换之前，图像块分量的所有样本都减去一个相同的量，这叫做直流电平(DC)变换。图像分块处理时，对图像块的大小没有限制，图像的变换、量化和熵编码等所有的处理都是以图像块为单元。这样做有两个明显的好处，一是可以降低对存储器的要求，二是便于抽出一幅图像中的部分图像。其缺点是图像质量有所下降，但不明显。
图9-25 图像分块、直流电平变换和图像块变换图像变换使用离散小波变换。JPEG 2000标准使用子带分解，把样本信号分解成低通样本和高通样本。低通样本表示减低了分辨率的图像数据样本，高通样本表示降低了分辨率的图像数据样本，用于需要从低通样本重构出分辨率比较高的图像。离散小波变换可以是不可逆的小波变换，也可以是可逆的小波变换。JPEG 2000标准默认的不可逆小波变换是Daubechies 9-tap/7-tap[13][14]，默认的可逆变换采用5-tap/3-tap滤波器。JPEG 2000标准支持两种滤波方式：基于卷积(convolution-based)和基于(lifting-based)。
JPEG 2000的基本编码方法是在EBCOT算法基础上开发的。
9.6.3 JPEG 2000的主要功能与过去的图像压缩标准相比，JPEG 2000标准既提高了性能又增加了功能。在相同质量的前提下与JPEG标准相比，JPEG 2000标准的压缩比可提高20%以上。
JPEG 2000能实现渐进传输(progressive transmission)，这是JPEG 2000的一个重要特性。它可先传输低分辨率的图像或者是图像的轮廓，然后逐步传输其他数据，不断提高图像质量，以满足用户的需要。这个特性在多媒体网络应用中有重要的意义。例如，当下载一幅图像时，可比较快地看到这幅图像的概貌，根据对图像质量的要求和可用的网络带宽控制下载图像的数据量。
JPEG 2000另一个重要特性是支持兴趣区(region of interest,ROI)的编码。用户利用这个特性可指定感兴趣的图像区域，在压缩时对这些图像区指定特定的压缩质量，或在恢复时指定特定的解压缩要求，这给用户带来了极大的方便。例如，在有些情况下图像中只有一小块区域对用户是有用的，对这些区域采用低压缩比，而其他区域采用高压缩比，在保证不丢失重要信息的同时能有效地压缩数据量。
练习与思考题什么叫做零树？
解释EZW的含义。
如果条件允许，用MATLAB或者其他语言编写执行EZW算法的编码和解码程序解释SPIHT的含义。
如果条件允许，用MATLAB或者其他语言编写执行SPIHT算法的编码和解码程序。
请用因特网搜索工具，查找并阅读EBCOT的详细说明。
如果条件允许，用MATLAB或者其他语言编写执行EBCOT算法的编码和解码程序
JPEG 2000有许多功能，请用因特网搜索工具调查和描述它的详细功能。
参考文献和站点
Daubechies,I.,Orthonormal Bases of Compactly Supported Wavelets,Comm,Pure and Applied Math.,vol,41,Nov,1988,pp,909-996.
A,Cohen,I,Daubechies and J.C.Feauveau,Biorthogonal bases of compactly supported wavelets,Communications on Pure and Applied Mathematics,45(5)：485-560,June 1992.
Wim Sweldens，The Construction and Application of Wavelets in Numerical Analysis，May 18,1995
Sweldens,W,The Lifting Scheme,A Construction Of Second Generation Wavelets,Siam J,Math,Anal,Vol,29,No,2,1997.
A,K,Jain,Fundamentals of Digital Image Processing,Prentice-Hall,Englewood Cliffs,New Jersey,1989.
Lewis,A,S,and Knowles,G,Image Compression Using the 2-D Wavelet Transform,IEEE Trans,IP,vol,1,no,2,April 1992,pp,244-250,
Shapiro,J,M,Embedded Image Coding Using Zerotrees of Wavelet Coefficients,IEEE Trans,SP,vol,41,no,12,Dec,1993,pp,3445-3462.
http://perso.wanadoo.fr/polyvalens/clemens/clemens.html(访问日期:2001年8月2日)
Ghassan Al-Regib,Embedded Zerotree Wavelet Encoding (EZW) Based on Sharipo’s Paper,04/05/2000,Georgia Institute of Technology,Atlanta,GA.
A,Said and W,Pearlman,A new,fast and efficient image codec based on set partitioning in hierarchical trees,IEEE Trans,Circuits System,Video Technology,vol,6,pp,243–250,June 1996.
Agnieszka C,Miguel，Teaching Notes,Set Partitioning in Hierarchical Trees (SPIHT)，1999.
David Taubman,High performance scalable image compression with EBCOT,Image Processing,IEEE Transactions on,Volume,9 Issue,7,July 2000,Page(s),1158 - 1170.
M,Antonini,M,Barlaud,P,Mathieu and I,Daubechies,Image Coding Using the Wavelet Transform,IEEE Trans,Image Proc.,pp,205-220,April 1992.
C,Christopoulos,A,Skodras and T,Ebrahimi,The JPEG 2000 still image coding system,An Overview,IEEE Transactions on Consumer Electronics,2000,Vol 46,No,4,pp,1103-1127,November 2000,
Vetterli,M,and Herley,C.,Wavelets and Filter Banks,Theory and Design,IEEE Trans,SP,vol,40,no,9,Sep,1992,pp,2207-2232,
Ramchandran,K.,Vetterli,M.,Herley,C.，Wavelets,subband coding,and best bases，Proceedings of the IEEE,Volume,84 Issue,4,April 1996，Page(s),541 -560.
Ingrid Daubechies，Wim Sweldens，Factoring Wavelet Transforms into Lifting Steps，J,Fourier Anal,Appl.,Vol,4,Nr,3,pp,247-269,1998,
