第9章小波图像编码 由于小波变换技术在20世纪90年代初期已经比较成熟,因此从那时起就开始出现各种新 颖的小波图像编码方法。这些编码方法包括EZW,在EZw算法基础上改进的SPIH和 EBCOT等。由于EZW算法的开拓给后来者带来很大的启发,它是一种有效而且计算简单 图像压缩技术,因此本章将重点介绍。 91从子带编码到小波编码 9.1.1子带编码 子带编码( subband coding,SBC)的基本概念是把信号的频率分成几个子带,然后对每个 子带分别进行编码,并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代, 子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点,20 世纪80年代中期开始在图像编码中使用。1986年 Woods,JW等科学家曾经使用一维正交镜 像滤波器组( quadrature mirror filterbanks,QMF)把信号的频带分解成4个相等的子带,如图 901所示。图901(a)表示分解方法,图9-01(b)表示其相应的频谱。图中的符号2表示频带 降低1/2,HH表示频率最高的子带,LL表示频率最低的子带。这个过程可以重复,直到符合 应用要求为止。这样的滤波器组称为分解滤波器树( decomposition filter trees 水平方向 + 垂直分析 (a)分解法(b)频谱 图9-0Lena图的子带编码(1984年) 9.1.2多分辨率分析 S Mallat1988年在构造正交小波基时提出了多分辨率分析( multiresolution analysis)的 概念,从空间上形象地说明了小波的多分辨率的特性,提出了正交小波的构造方法和快速算 法,叫做Malt算法。根据 Mallat和 Meyer等科学家的理论,使用一级小波分解方法得到的图 像如图9-02所示
第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章小波图像编码 粗糙图像 原始图像 图像细节 图9-02Lena的两种分辨率分析图像(1986年) 如果在一级分解之后继续进行分析,这种分解过程叫做多分辨率分析,实际上就是多级 小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像,这些图像叫做多分 辨率图像( multiresolution images)。图9-03表示Lena的多分辨率图像。其中,粗糙图像l的分 辨率是原始图像的14,粗糙图像2的分辨率是粗糙图像1的14 原始图像 粗糙图像 粗图像2 图9-03Lena的多分辨率分析图像(1986年) 913滤波器组与多分辨率 为了压缩语音数据,在1976年 Crosier, stepan和 Galand介绍了一种可逆滤波器组 ( invertible filter bank),使用滤波和子采样( (subsampling)的方法用来把离散信号∫(n)分解成 大小相等的两种信号,并且使用叫做共轭镜像滤波器( conjugate mirror filters)的一种特殊滤波 器来取消信号的混叠( aliasing),这样可从子采样的信号中重构原始信号∫(mn)。这个发现使 人们花费了10多年的努力来开发一套完整的滤波器组理论。 正交小波的多分辨率理论( multiresolution theory)已经证明,任何共轭镜像滤波器都可以 用来刻画一种小波v(t),它能够生成2(R)实数空间中的正交基,而且快速离散小波变换 可以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示 了数字信号处理和谐波分析之间关系,这就使人们一直在致力于解决它们之间的关系问题
第9章 小波图像编码 2 图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)的方法用来把离散信号 f n( ) 分解成 大小相等的两种信号，并且使用叫做共轭镜像滤波器(conjugate mirror filters)的一种特殊滤波 器来取消信号的混叠(aliasing)，这样可从子采样的信号中重构原始信号 f n( ) 。这个发现使 人们花费了10多年的努力来开发一套完整的滤波器组理论。 正交小波的多分辨率理论(multiresolution theory)已经证明，任何共轭镜像滤波器都可以 用来刻画一种小波 ()t ，它能够生成 L R( ) 2 实数空间中的正交基，而且快速离散小波变换 可以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示 了数字信号处理和谐波分析之间关系，这就使人们一直在致力于解决它们之间的关系问题
第9章小波图像编码 9.1.4从子带编码到小波编码 在过去的年代里,人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波 编码技术( wavelet coding,wo)的旗号下,人们提出了许多与子带编码技术非常类似和密切 相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的 小波基函数系列可以在连续的时间域中构造,但如何在离散的时间域中构造是一个现实问 题 在众多的研究者中, Inrid daubechies在离散的时间域中构造小波基函数方面做出了杰出 的贡献。她于1988年[]最先揭示了小波变换和滤波器组之间的内在关系:离散时间滤波器 ( 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”[3J4],简称 Lifting/lifting(提升法)。该方法的 基本思想是首先把信号分成偶数号样本和奇数号样本,根据信号本身的相关性,奇数样本使 用偶数样本进行预测,由预测丢失的信号叫做信号的细节信息,然后调整偶数样本以保存原 始信号的粗糙信息和细节信息。该方法保留了小波分析的特性(时间频率局部化和快速计 算),通过放弃小波的平移和缩放,并且放弃用傅立叶分析来构造小波,从而解决了非无限 信号或者非周期信号的小波和小波变换问题,也使计算速度得到很大的提高,因此被称为第 二代小波( second generation wavelets),现在也成为制定JPEG200标准中小波部分的基础 915小波分解图像方法 使用小波变换把图像分解成各种子带的方法有很多种。例如,均匀分解( uniform decomposition),非均匀分解( non-uniform decomposition),八带分解( octave- band decomposition) 和小波包分解( wavelet-- packet decomposition),根据不同类型的图像选择不同小波的自适应小 波分解( adaptive wavelet decomposition)等。其中,八带分解是使用最广泛的一种分解方法 这种分解方法属于非均匀频带分割方法,它把低频部分分解成比较窄的频带,而对每一级分 解的高频部分不再进一步分解。图9-04表示Lena图像的数据分解 h 近似值)(水平细节) d(平细节) v 垂直细节)(对角细节) d (垂直细节)(对角细节) (a)一级分解 (b)三级分解 (c)Lena三级分解图 图9-04Lena图像的数据分解
第9章 小波图像编码 3 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章小波图像编码 92失真的度量方法 在图像编码系统中,评估编码系统性能的一种方法是失真度量法,用峰值信号噪声比 ( peak signal to noise ratio,PSNR)来衡量,定义为最大像素值与均方差( mean square error,MSE) 比[S] PSNR= 10log (Peak Signal value)-(db) MSE 对8位二进制图像, PSMR=100o2552 MSE 其中, MSE= MN M=0 x(m, n)-x(m, n 其中,x(m,n)为原始图像的像素值,x(m,n)为解压缩之后的像素值 在文献中,评估编码系统性能还使用其他方法,这些方法包括使用规格化均方差 ( normalized mean square error,NMSE)、信号噪声比( signal to noise ratio,SNR)和平均绝对 误差( mean absolute error,MAE)来度量,分别定义为 M-1N-1 ∑∑[xm,m)-6(m,m NMSE ∑∑[xm,n) SNR=10log oNMSE MAE= ∑∑[x(m,n)-5(m,n MN m=0 n=0 其中,π(m,η)为原始图像的像素值,(m,n)为解压缩之后的像素值。 在电子工程中,信号噪声比(SNR)一直是最流行的误差度量指标,在大多数情况下可提 供很有价值的信息,在数学上也比较容易计算。信号噪声比虽然也用在图像编码中,但由于 它的数值与图像编码系统中高压缩比的关系不容易体现,因此提出了其他的几种度量方法, 包括平均主观评分 mean opinion score,MOS) 93EZw编码 93.1介绍 在1992年, Lewis,A.S.和 Knowles,G首先介绍了一种树形数据结构来表示小波变换的 系数[6]。在1993年, Shapiro,J,M把这种树形数据结构叫做“零树 zerotree)”,并且开发了
第9章 小波图像编码 4 9.2 失真的度量方法 在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比 (peak signal to noise ratio, PSNR)来衡量, 定义为最大像素值与均方差(mean square error，MSE) 之比[5]， 2 10 ( ) 10log Peak Signal Value PSNR MSE = (db) 对8位二进制图像， 2 10 255 PSNR 10log MSE = (db) 其中， 1 1 2 0 0 1 ( , ) ( , ) M N m n MSE x m n x m n MN − − = = = − 其中， x m n ( , ) 为原始图像的像素值， x m n ( , ) 为解压缩之后的像素值。 在文献中，评估编码系统性能还使用其他方法，这些方法包括使用规格化均方差 (normalized mean square error，NMSE)、信号噪声比(signal to noise ratio，SNR) 和平均绝对 误差(mean absolute error，MAE)来度量，分别定义为 1 1 2 0 0 1 1 2 0 0 [ ( , ) ( , )] [ ( , )] M N m n M N m n x m n x m n NMSE x m n − − = = − − = = − = 10 1 SNR 10log NMSE = 1 1 0 0 1 [ ( , ) ( , )] M N m n MAE x m n x m n MN − − = = = − 其中， x m n ( , ) 为原始图像的像素值， x m n ( , ) 为解压缩之后的像素值。 在电子工程中，信号噪声比(SNR)一直是最流行的误差度量指标，在大多数情况下可提 供很有价值的信息，在数学上也比较容易计算。信号噪声比虽然也用在图像编码中，但由于 它的数值与图像编码系统中高压缩比的关系不容易体现，因此提出了其他的几种度量方法， 包括平均主观评分(mean opinion score，MOS)。 9.3 EZW编码 9.3.1 介绍 在1992年，Lewis，A. S.和Knowles, G.首先介绍了一种树形数据结构来表示小波变换的 系数[6]。在1993年，Shapiro, J. M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了
第9章小波图像编码 个效率很高的算法用于熵编码,他的这种算法叫做嵌入(式)零树小波(ε mbedded zerotree wavelet,EZW)算法[门]。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算法指的就是这个模块的算法,它的输出是符号 集{PNT,乙0,1}中的一系列符号;熵编码模块对每个输入数据值精确地确定它的概率, 并根据这些概率生成一个合适的代码,使输出的码流( code stream)小于输入的码流。 量化 小波变换 中的 熵编码 Zerotree Embedding 图9-05EZW算法结构 932算法 EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次,生成一种分辨率图 像,编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤:设置阈值、每个小波系数与阈 值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表,一种是小波系数的符号 表,另一种是量化表。 1.零树 回顾二维小波变换的计算过程,不难想象各级子图像中的系数是相关的。在说明零树的 概念之前,需要对小波变换得到的系数、名称和符号加以说明。现以3级分解的离散小波变 换为例,图906表示Lena图像使用三级滤波器组做小波变换输出的子图像( sub image)。需要 注意的是,分解之后的图像的名称在文献上有很多种,除了子图像之外,有的叫做子带图像 (sub- band image),有的把子图像进一步区分为高频子图像和低频子图像,或者粗糙图像和精 细图像等名称。这些名称从不同的角度反映图像的特性,在不同的场合下使用可以收到异曲 同工的效果。图9-06中的数字1,2和3表示分解的级数编号,LL3表示第3级的低频子图像,在 这个例子中,它是分辨率最低的子图像。H3表示第3级分解在水平方向上的子图像,LH3 表示第3级分解在垂直方向上的子图像,HHB表示第3级分解在对角线方向上的子图像,其他
第9章 小波图像编码 5 一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(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)小于输入的码流。 小波变换 量化 EZW中的 熵编码 Zerotree, Embedding 图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章小波图像编码 的组合符号依此类推。由于低频子图像的系数要比高频子图像的系数大,零树编码技术就是 利用这个事实来设计编码/解码过程中每一级使用的量化器 HL2 H3 HH3 HIL 1 LH2|m2|水平子图像 垂直子图像 对第图像 图9-06Lena三级分解图像 各级子图像中的系数之间的关系可以用树的形式描述。如图9-07(a)所示,最低频率的子 图像在左上角,最高频率的子图像在右下角,由同一方向和相同空间位置上的所有小波系数 组成一棵树。例如,从第三级子图像HH3、第二级子图像HH到第一级子图像HH的相应位 置上的所有系数构成一棵下降树。按箭头所指的方向,各级系数的名称分别用祖系数、父系 数、子系数和孙系数来称呼。举例来说,LL3的系数为{63},HH和HH中的系数分别为{3} 和{4,6,3,-2},由这些系数构成的树如图907(b)所示。如果把{63}指定为父系数,{3}就称为 子系数,而{4,6,3,-2}中的4个系数就称为孙系数 国画m 图十 (a)构造方法 (b)小波系数举例 图9-07EZW编码树的构造 现在再来看零树的概念。为便于比较,把图9-07(b)所示的两棵树用图9-08a)和b)表示 假设编码时开始的阈值T=32,由于63比32大,这样的树叫做非零树,如图9-08(a)所示。 假设下一次编码时的阈值T1=16,把13当作父系数,它的幅度比16小,而它的所有4个子 系数的幅度都比16小,这样的树叫做零树,系数-13叫做零树根,如图9-08(b)所示。根据以 上的分析,零树的定义可概括为一句话:子孙系数都为零的树。定义零树的重要意义在于 如果一棵树是零树,那么这棵树就可以用一个预先定义的符号来代表整棵树,从而提高了压 缩比 顺便要指出的是,小波图像系数结构的形式不只是上面介绍的一种,也可能不是最好的 种
第9章 小波图像编码 6 的组合符号依此类推。由于低频子图像的系数要比高频子图像的系数大，零树编码技术就是 利用这个事实来设计编码/解码过程中每一级使用的量化器。 图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)表示。 假设编码时开始的阈值 T0 = 32 ，由于63比32大，这样的树叫做非零树，如图9-08(a)所示。 假设下一次编码时的阈值 T1 =16 ，把-13当作父系数，它的幅度比16小，而它的所有4个子 系数的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图9-08(b)所示。根据以 上的分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于， 如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压 缩比。 顺便要指出的是，小波图像系数结构的形式不只是上面介绍的一种，也可能不是最好的 一种
第9章小波图像编码 (a)非零树例子 (b)零树例子 图9-08非零树与零树的概念 2.扫描方法 EZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种, 种叫做光栅扫描( raster scan),如图9-0%a)所示,另一种叫做迂回扫描( morton scan),如图 9-09(b)所示。 (a)光栅扫描 (b)迂回扫描 图9-09小波变换系数扫描方法 3.算法 EZW算法可粗略地归纳为下面几个主要步骤 1)阈值T的选择 开始时的阈值石通常按下式估算, T=2Lkg2MXxD)⊥ 其中,MAX()表示最大的系数值,X;表示小波变换分解到第i级时的系数。以后每扫描 次,阈值减少一半 (2)给系数分配符号 使用EZW算法编码图像时每一次扫描需要执行两种扫描,并产生两种输出的符号。第 种扫描叫做主扫描( dominant pass,它的任务是把小波系数Ⅹ与阈值T进行比较,然后指 定表9-1中的4个符号之一,笔者把这种符号叫做系数符号,对整幅图像扫描之后产生系数符 号序列。第二种扫描叫做辅扫描( subordinate pass,其任务是对主扫描取出的带有符号P或者 N的系数进行量化,产生代表对应量化值的符号“0”和“1”,笔者把这种符号称为量化符
第9章 小波图像编码 7 (a) 非零树例子 (b) 零树例子 图9-08 非零树与零树的概念 2. 扫描方法 EZW算法对小波系数的进行编码的次序叫做扫描。扫描子图像系数的方法有两种，一 种叫做光栅扫描(raster scan)，如图9-09(a)所示，另一种叫做迂回扫描(morton scan)，如图 9-09(b)所示。 (a) 光栅扫描 (b) 迂回扫描 图9-09 小波变换系数扫描方法 3. 算法 EZW算法可粗略地归纳为下面几个主要步骤。 (1) 阈值 T 的选择 开始时的阈值 T0 通常按下式估算， log (MAX(| |)) Xi T = 2 0 2 其中，MAX(.)表示最大的系数值， Xi 表示小波变换分解到第 i 级时的系数。以后每扫描一 次，阈值减少一半。 (2) 给系数分配符号 使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第 一种扫描叫做主扫描(dominant pass)，它的任务是把小波系数 X 与阈值 T 进行比较，然后指 定表9-1中的4个符号之一，笔者把这种符号叫做系数符号，对整幅图像扫描之后产生系数符 号序列。第二种扫描叫做辅扫描(subordinate pass)，其任务是对主扫描取出的带有符号P或者 N的系数进行量化，产生代表对应量化值的符号“0”和“1”，笔者把这种符号称为量化符 号
第9章小波图像编码 主扫描:扫描每一个系数以产生系数符号 如果系数幅度大于阈值(T)且为正数,输出符号P( positive), 如果系数幅度的绝对值大于阈值(T)且为负数,输出符号 N(negative), >如果系数是零树根,输出T( zerotree), 如果系数幅度小于阈值但树中有大于阈值的子孙系数,输出孤立零符号Z( isolated zero) 为了确定一个系数是否为零树根T或者是孤立零Z,需要对整个4叉树进行扫描,这样就 需要花时间。此外,为了保护已经被标识为零树的所有系数,需要跟踪它们,这就意味需要 存储空间来保存。最后要把绝对值大于阈值的系数取出来,并在图像系数相应的位置上填入 一个标记或者零,这样做可防止对它们再编码。 辅扫描:量化带符号P和N的系数 在量化系数之前要构造量化器。量化器的输入间隔为[T1,2T1),该间隔被1.571分 成两个部分:[T1,1571)和[1571,2T1),量化间隔为0.571,其中i为第i次编码。量 化器的输出为量化符号“0”和“1”,“0”对应量化值为(1.5-0.25)71,“1”对应量化 值为(1.5+0.25)T1 例如,第一次扫描时的阈值石=32,量化器的间隔就为[32,64),该间隔[32,64)被 48分成两个相等的部分:[32,48)和[48,64),量化间隔为16。对系数进行量化时,如果幅 度在[32,48)的范围里,该系数的量化值为“0”,对应的量化值为(1.5-0.25)1=40 如果幅度在[48,64)的范围里,该系数的量化符号为“1”,它的量化值为 (15+0.25)7=56,详见图913。 表9-1EZW系数符号集 判断条件 输出符号 xl>T X>0 P( positive):表示正,重要系数 X<0 ( negative):表示负,重要系数 所有子孙系数|<T T:零树根,不重要系数 <T X叫做零树的根 至少有一个子孙系数z:孤立的零,不重要系数 T 933算法举例 为进一步理解EZW算法,综合了C. Valens[8]和在读博士生 Ghassan Al- Regibl提供的 个例子[7。假设有一幅8×8的图像P,离散小波变换矩阵为W,经过小波变换之后的图像
第9章 小波图像编码 8 主扫描：扫描每一个系数以产生系数符号 ➢ 如果系数幅度大于阈值( T )且为正数，输出符号 P(positive)， ➢ 如果系数幅度的绝对值大于阈值( T )且为负数，输出符号 N(negative)， ➢ 如果系数是零树根，输出 T(zerotree)， ➢ 如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号 Z(isolated zero)。 为了确定一个系数是否为零树根T或者是孤立零Z，需要对整个4叉树进行扫描，这样就 需要花时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要 存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入 一个标记或者零，这样做可防止对它们再编码。 辅扫描：量化带符号P和N的系数 在量化系数之前要构造量化器。量化器的输入间隔为 [ , ) T T i i − − 1 1 2 ，该间隔被1.5 Ti−1 分 成两个部分： [ , . ) T T i i − − 1 1 1 5 和 [ . , ) 1 5 2 T T i i − − 1 1 ，量化间隔为0.5 Ti−1 , 其中 i 为第 i 次编码。量 化器的输出为量化符号“0”和“1”，“0”对应量化值为 ( . . ) 1 5 0 25 − Ti−1 ，“1”对应量化 值为 ( . . ) 1 5 0 25 + Ti−1。 例如，第一次扫描时的阈值 T0 = 32 ，量化器的间隔就为 [32, 64) ，该间隔 [32, 64) 被 48分成两个相等的部分： [ , ) 32 48 和 [ , ) 48 64 ，量化间隔为16。对系数进行量化时，如果幅 度在 [ , ) 32 48 的范围里，该系数的量化值为“0”，对应的量化值为 ( . . ) 1 5 0 25 40 − = T0 ； 如 果 幅 度 在 [ , ) 48 64 的 范 围 里 ， 该 系 数 的 量 化 符 号 为 “ 1 ” ， 它 的 量 化 值 为 ( . . ) 1 5 0 25 56 + = T0 ，详见图9-13。 表9-1 EZW系数符号集 判断条件 输出符号 X T X 0 P(positive)：表示正，重要系数 X 0 N(negative)：表示负，重要系数 X T 所有子孙系数 X T i ， X 叫做零树的根 T：零树根，不重要系数 至 少 有 一 个 子 孙 系 数 X T i Z：孤立的零，不重要系数 9.3.3 算法举例 为进一步理解EZW算法，综合了C. Valens[8]和在读博士生Ghassan Al-Regib[9]提供的一 个例子[7]。假设有一幅8×8的图像 P ，离散小波变换矩阵为 W ，经过小波变换之后的图像
第9章小波图像编码 为X=WP,小波图像系数X和扫描方式分别如图910(a)和(b所示。另外还假设,图9-10(a) 所示的数据是经过3级分解的小波图像系数 15143-125-739 59.1|47 2|-36-4|3636 115 03-4 (a)小波图像数据 (b)迂回扫描 图9-108×8小波变换图像 1.树结构 为叙述方便,图9-10(a中的系数用组合符号( YMYYN)表示。最低分辨率子图像(即第3 级)中的每一个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关,它们之间构成 的树如图9-11(b)所示。说明如下 Ⅺ1/LL3表示子带LL3的系数,它与第2级子图像中相关的子系数有3个:/HL2, XH2和XHH2。 X2/HL3表示子带HL3的系数,它与第2级子图像中相关的子系数有3个:X2/H2 X∥LH和X2/HH2 B3∥LB3表示子带LH3的系数,它与第2级子图像中相关的子系数有3个:X3/HL2 X3/LH2和X3/HH2 X4/HH3表示子带HHB的系数,它与第2级子图像中相关的子系数有3个:X4HL2 X4∥LH和X4/HH2 x2/1/x21X1/×2x3/×4 LL3 HL3 H2HL2 HL1 HLI HL 4/×5/|X6/x7/|X8 LH3 HH3 HL2 HL2 HL1 HL1HL1 HLI Xx2/x/x2x09x10x14×12|21/ LH2 LH2 HH2 HH2HL1HL1H1H1 闹图 LH2HH2 x3X4x3413814x15161 LH2 LH2 HH2 HH2 HL HL1HL1 X5/X6/7/ X8/ 5/X6/X7/X8 LHI LH1 LH1 HH1 HH1HH1 HH1 HH3 x09X10/X11/X12/X09/X10/x11/×12 LHI LHI LHI LHI HHI HHI HHI HHI Ⅺ1314415X16X13X14/×15/×16 LHILHI LHI LHI HHlHHlHHl HH1 圄鹵圖圄鹵圖 (a)8×8子图像小波变换系数(b)最低频带小波变换系数树 图9-11编码树的结构(1) 在其他子图像中,任何一个系数在高一级分辨率子图像中都有4个子系数与它有关,它 们之间构成的树如图9-12(b)所示,图中只表示了一部分的树。从图中可以看到
第9章 小波图像编码 9 为 X WP = ，小波图像系数 X 和扫描方式分别如图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/2表示子带HL2的系数,它与第1级子图像中相关的子系数有4个:H1/H1 2H1,X5H1和X6/HL1 X/HL2表示子带HL2的系数,它与第1级子图像中相关的子系数有4个:H3/H 4/HL1,MTH1和X8/HLl X3HL2表示子带HL2的系数,它与第1级子图像中相关的子系数有4个:X09/HL1, X1OH1,X13/H1和X4/HL1 X4/H2表示子带HL2的系数,它与第1级子图像中相关的子系数有4个:X1HL1, X12/HL1 X15/HL1 FH X16/HLI 1/x2/1X1 L3H3 H2 L1 HLI HLI 3/x4/1x30 [2 LH2 LH2 HH2 HH2 HLI HL HI LHI LHI LHI HHI HH (a)8×8子图像小波变换系数(b)2级子图像小波变换部分系数树 图9-12编码树的结构(2) 2.编码 根据对图像分辨率的要求,编码时可对小波图像系数进行多次扫描。每一次扫描包括主 扫描和辅扫描 (1)第一次扫描: 步骤1:选择初始阈值。最大的系数为63,因此选择T=32 步骤2:指定系数的符号。假设存放系数符号的缓冲存储器为D1,存放量化符号的缓冲 存储器的符号为S1。扫描每一个系数并且与阈值32进行比较。在比较过程中对每一个系数指 定一个符号,并把符号放在D1中。当一个系数被指定为符号T时,所有的子孙系数就不再扫 描,并用“×”表示,扫描结果如图9-13(a)所示。图中,输出符号的下标表示系数被标识的 次序,仅仅是为了叙述方便。对扫描结果作如下说明: ①X∥L3的系数是63,它大于阈值32,因此输出的符号为P ②X2/HL3的系数是-34,它的符号输出为是N2。 ③M3LH的系数是-31,它的幅度相对于阈值32来说是不重要的,它下属子系数 X3H2,X3H和X3HH2},孙系数{9H1,H10HL1,3∥HL,Ⅺ4HL1},{X9∥LH, 1OLH1,X13LH1,14H}和{X9/HH,XOHH,X13/HH1,X14/HH}的幅度都比它小,因 此它输出的符号为零树符号T ④XDLH2的系数是14,它小于阈值32。在它的子系数{3/LH,X4LH,M7LH,X8/LH} 中,X4/LH的系数是47,它大于阈值32,因此M2LH输出符号为孤立零符号Z ⑤4LH的系数是47,相对于阈值32是重要的,产生符号P6 第一次主扫描之后,缓冲存储器Dl中的系数符号为: DI: PNTTPTTZTTTTTTTPTT
第9章 小波图像编码 10 ➢ 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) 第一次扫描： 步骤1: 选择初始阈值。最大的系数为63，因此选择 T0 = 32 。 步骤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