第4章小波图像编码 第4章小波图像编码 (征求意见稿) 清华大学计算机科学与技术系 智能技术与系统国家重点实验室 林福宗,2001-10-19 由于小波变换技术在20世纪90年代初期已经比较成熟,因此从那时起就开始出现各种新 颖的小波图像编码方法。这些编码方法包括FzW,在FW算法基础上改进的SPHT和 EBCOT 等。由于EZW算法的开拓给后来者带来很大的启发,它是一种有效而且计算简单的图像压缩 技术,因此本章将重点介绍 4.1从子带编码到小波编码 4.1.1子带编码 子带编码( subband coding,SB)的基本概念是把信号的频率分成几个子带,然后对每个 子带分别进行编码,并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代, 子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点,20 世纪80年代中期开始在图像编码中使用。1986年 Woods,Jw等人曾经使用一维正交镜像滤 波器组( quadrature mirror filterbanks,QMF)把信号的频带分解成4个相等的子带,如图401 所示。图a)表示分解方法,图(b)表示其相应的频谱。图中的符号2表示频带降低1/2,HH 表示频率最高的子带,LL表示频率最低的子带。这个过程可以重复,直到符合应用要求为 止。这样的滤波器组称为分解滤波器树( decomposition filter trees) HHH -thlfll-HL 水平方向 垂直分析 图4-01Lena图的子带编码(1984年) 41.2多分辨率分析 SMallat-1988年在构造正交小波基时提出了多分辨率分析( multiresolution analysis)的概 念,从空间上形象地说明了小波的多分辨率的特性,提出了正交小波的构造方法和快速算法 叫做Malt算法。根据 Mallat和 Meyer等人的理论,使用一级小波分解方法得到的图像如图402 所示
第4章 小波图像编码 1 第4章 小波图像编码 (征求意见稿) 清华大学计算机科学与技术系 智能技术与系统国家重点实验室 林福宗，2001-10-19 由于小波变换技术在20世纪90年代初期已经比较成熟，因此从那时起就开始出现各种新 颖的小波图像编码方法。这些编码方法包括EZW, 在EZW算法基础上改进的SPIHT和EBCOT 等。由于EZW算法的开拓给后来者带来很大的启发，它是一种有效而且计算简单的图像压缩 技术，因此本章将重点介绍。 4.1 从子带编码到小波编码 4.1.1 子带编码 子带编码(subband coding，SBC)的基本概念是把信号的频率分成几个子带，然后对每个 子带分别进行编码，并根据每个子带的重要性分配不同的位数来表示数据。在20世纪70年代， 子带编码开始用在语音编码上。由于子带编码可根据子带的重要性分别进行编码等优点，20 世纪80年代中期开始在图像编码中使用。1986年Woods, J. W.等人曾经使用一维正交镜像滤 波器组(quadrature mirror filterbanks，QMF)把信号的频带分解成4个相等的子带，如图4-01 所示。图(a)表示分解方法，图(b)表示其相应的频谱。图中的符号 表示频带降低1/2，HH 表示频率最高的子带，LL表示频率最低的子带。这个过程可以重复，直到符合应用要求为 止。这样的滤波器组称为分解滤波器树(decomposition filter trees)。 图4-01 Lena图的子带编码(1984年) 4.1.2 多分辨率分析 S.Mallat于1988年在构造正交小波基时提出了多分辨率分析(multiresolution analysis)的概 念，从空间上形象地说明了小波的多分辨率的特性，提出了正交小波的构造方法和快速算法， 叫做Mallat算法。根据Mallat和Meyer等人的理论，使用一级小波分解方法得到的图像如图4-02 所示
皮图像编 粗栏图像 原始图像 图像细节 图4-02Lena的两种分辨率分析图像(1986年) 如果在一级分解之后继续进行分析,这种分解过程叫做多分辨率分析,实际上就是多级 小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像,这些图像叫做多分 辨率图像( multiresolution images)。图4-03表示Lena的多分辨率图像。其中,粗糙图像1的分辨 率是原始图像的14,粗糙图像2的分辨率是粗糙图像1的1/4。 原始图像 粗糙图像1 粗糙图像2 图4-03Lena的多分辨率分析图像(1986年) 41.3滤波器组与多分辨率 为了压缩语音数据,在1976年 Crosier, Esteban和 Galand介绍了一种可逆滤波器组 ( invertible filter bank),使用滤波和子采样( subsampling)的方法用来把离散信号∫(n)分解成大 小相等的两种信号,并且使用叫做共轭镜像滤波器( conjugate mirror filters)的一种特殊滤波器 来取消信号的混叠( aliasing),这样可从子采样的信号中重构原始信号∫(m)。这个发现使人 们花费了10多年的努力来开发一套完整的滤波器组理论 正交小波的多分辨率理论( multiresolution theory已经证明,任何共轭镜像滤波器都可以用 来刻画一种小波ψ(1),它能够生成L(R)实数空间中的正交基,而且快速离散小波变换可 以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示了 数字信号处理和谐波分析之间关系,这就使人们一直在致力于解决它们之间的关系问题
第4章 小波图像编码 2 图4-02 Lena的两种分辨率分析图像(1986年) 如果在一级分解之后继续进行分析，这种分解过程叫做多分辨率分析，实际上就是多级 小波分解的概念。使用多级小波分解可以得到更多的分辨率不同的图像，这些图像叫做多分 辨率图像(multiresolution images)。图4-03表示Lena的多分辨率图像。其中，粗糙图像1的分辨 率是原始图像的1/4，粗糙图像2的分辨率是粗糙图像1的1/4。 图4-03 Lena的多分辨率分析图像(1986年) 4.1.3 滤波器组与多分辨率 为了压缩语音数据，在1976年Croisier, Esteban和Galand介绍了一种可逆滤波器组 (invertible filter bank)，使用滤波和子采样(subsampling)的方法用来把离散信号 f n( ) 分解成大 小相等的两种信号，并且使用叫做共轭镜像滤波器(conjugate mirror filters)的一种特殊滤波器 来取消信号的混叠(aliasing)，这样可从子采样的信号中重构原始信号 f n( ) 。这个发现使人 们花费了10多年的努力来开发一套完整的滤波器组理论。 正交小波的多分辨率理论(multiresolution theory)已经证明，任何共轭镜像滤波器都可以用 来刻画一种小波y ( )t ，它能够生成 2 L (R) 实数空间中的正交基，而且快速离散小波变换可 以使用串联这些共轭镜像滤波器来实现。连续小波理论和离散滤波器组之间的等效性揭示了 数字信号处理和谐波分析之间关系，这就使人们一直在致力于解决它们之间的关系问题
第4章小波图像编 4.1.4从子带编码到小波编码 在过去的年代里,人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波 编码技术( wavelet coding,wo)的旗号下,人们提出了许多与子带编码技术非常类似和密切 相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的 小波基函数系列可以在连续的时间域中构造,但如何在离散的时间域中构造是一个现实问 在众多的研究者中, Inrid Daubechies在离散的时间域中构造小波基函数方面做出了杰出 的贡献。她于1988年[最先揭示了小波变换和滤波器组之间的内在关系:离散时间滤波器 ( discrete-time filters或者QMF可以被叠代,并在某一种匀称( (regularity,可粗略理解为函数的 平滑性)条件下可获得连续小波。这是一个非常实际和极其有用的发现,这就意味着可使用 有限冲击响应( finite impulse response.,FR)的离散时间滤波器来执行小波分解,使用相同 滤波器可重构小波分解之后的信号。由此可见,早期开发的子带编码实际上是一种小波变换 在 Daubechies揭示小波变换和滤波器组之间的关系之前,在图像编码中小波技术并不流 行。从20世纪90年代开始, Cohen, Daubechies和 Feauveau,简称为CDF,系统地开发了构造 紧支持双正交小波( compactly supported biorthogonal wavelets)的方法[2],以及其他学者提出 的各种算法,使小波技术在图像编码中得到广泛的应用。 在构造小波和开发小波变换算法中,比利时成长的年轻学者 Wim sweldens在1994年的博 士论文中首先提出了“ The Lifting scheme”[3][4],简称 Lifting/ Hifting(提升法)。该方法的基 本思想是首先把信号分成偶数号样本和奇数号样本,根据信号本身的相关性,奇数样本使用 偶数样本进行预测,由预测丢失的信号叫做信号的细节信息,然后调整偶数样本以保存原始 信号的粗糙信息和细节信息。该方法保留了小波分析的特性(时间频率局部化和快速计算), 通过放弃小波的平移和缩放,并且放弃用傅立叶分析来构造小波,从而解决了非无限信号或 者非周期信号的小波和小波变换问题,也使计算速度得到很大的提高,因此被称为第二代小 波 second generation wavelets),现在也成为制定PEG2000标准中小波部分的基础。 41.5小波分解图像方法 使用小波变换把图像分解成各种子带的方法有很多种。例如,均匀分解( uniform ecomposition),非均匀分解(non- uniform decomposition),八带分解( octave- band decomposition) 和小波包分解( wavelet-packet decomposition),根据不同类型的图像选择不同小波的自适应小 波分解( adaptive wavelet decomposition)等。其中,八带分解是使用最广泛的一种分解方法 这种分解方法属于非均匀频带分割方法,它把低频部分分解成比较窄的频带,而对每一级分 解的高频部分不再进一步分解。图4-04表示Lena的各种子带图像,使用CDF-9/7的双正交小 波( biorthogonal wavelet)三级分解得到的图像。其中,双正交小波系主要用在信号和图像的重 构中,通常的用法是用一个小波函数进行分解,用另一个小波函数进行重构,是一个正交小 波的扩展集 近似值)(水平细节) 水平细节) (垂直细节)(对角细节) (垂直細节)(对角细节) (b)三级分解 )Lena三级分解图 图4-04Lena图像数据分解 3
第4章 小波图像编码 3 4.1.4 从子带编码到小波编码 在过去的年代里，人们做了许多的努力来改进滤波器组的设计和子带编码技术。在小波 编码技术(wavelet coding，WC)的旗号下，人们提出了许多与子带编码技术非常类似和密切 相关的方法。小波编码技术中的一个重要的问题是如何构造正交的小波基函数系列。正交的 小波基函数系列可以在连续的时间域中构造，但如何在离散的时间域中构造是一个现实问 题。 在众多的研究者中，Inrid Daubechies在离散的时间域中构造小波基函数方面做出了杰出 的贡献。她于1988年[1]最先揭示了小波变换和滤波器组之间的内在关系：离散时间滤波器 (discrete-time filters)或者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)，现在也成为制定JPEG2000标准中小波部分的基础。 4.1.5 小波分解图像方法 使用小波变换把图像分解成各种子带的方法有很多种。例如，均匀分解(uniform decomposition)，非均匀分解(non-uniform decomposition)，八带分解(octave-band decomposition) 和小波包分解(wavelet-packet decomposition)，根据不同类型的图像选择不同小波的自适应小 波分解(adaptive wavelet decomposition)等。其中，八带分解是使用最广泛的一种分解方法。 这种分解方法属于非均匀频带分割方法，它把低频部分分解成比较窄的频带，而对每一级分 解的高频部分不再进一步分解。图4-04表示Lena的各种子带图像，使用CDF-9/7的双正交小 波(biorthogonal wavelet)三级分解得到的图像。其中，双正交小波系主要用在信号和图像的重 构中，通常的用法是用一个小波函数进行分解，用另一个小波函数进行重构，是 一个正交小 波的扩展集。 图4-04 Lena图像数据分解
第4章小波图像编 4.2失真的度量方法 在图像编码系统中,评估编码系统性能的一种方法是失真度量法,用峰值信号噪声比 ( peak signal to noise ratio,PSNR)来衡量,定义为最大像素值与均方差( mean square erroi MsSE之比[5], PSNR=10logjo Peak signalvalue) MSE 对8位二进制图像, PSNR=10log,o MSE 其中, MSE= ∑∑k(mn,n)-mn MN m=00 其中,x(m,n)为原始图像的像素值,x(m,n)为解压缩之后的像素值。 在文献中,评估编码系统性能还使用其他方法,这些方法包括使用规格化均方差 ( normalized mean square error,NMSE)、信号噪声比( signal to noise ratio,SNR)和平均绝对 误差( mean absolute error,MAE来度量,分别定义为 ∑∑[xm,n)-X(m,n NMSE aun ∑∑[xm,m SNR=10log1o NMSE MAE=,∑∑[x(m,n)-Xmn MN= 其中,x(m,n)为原始图像的像素值,x(m,n)为解压缩之后的像素值。 在电子工程中,信号噪声比(SNR)一直是最流行的误差度量指标,在大多数情况下可提 供很有价值的信息,在数学上也比较容易计算。信号噪声比虽然也用在图像编码中,但由于 它的数值与图像编码系统中高压缩比的关系不容易体现,因此提出了其他的几种度量方法 包括平均主观评分( mean opinion score,MOS)。 43EZW编码 43.1介绍 在1992年, Lewis,A.S.和 Knowles,G首先介绍了一种树形数据结构来表示小波变换 系数[6]。在1993年, Shapiro,JM把这种树形数据结构叫做“零树( zerotree)”,并且开发了 个效率很高的算法用于熵编码,他的这种算法叫做嵌入(式)零树小波( embedded zerotree 4
第4章 小波图像编码 4 4.2 失真的度量方法 在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比 (peak signal to noise ratio, PSNR)来衡量, 定义为最大像素值与均方差(mean square error， MSE)之比[5]， 2 10 ( ) 10log Peak SignalValue 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 xmn MN - - = = = - å å % 其中， xmn (,) 为原始图像的像素值， xmn %(,) 为解压缩之后的像素值。 在文献中，评估编码系统性能还使用其他方法，这些方法包括使用规格化均方差 (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 xmn NMSE xmn - - = = - - = = - = å å å å % 10 1 SNR 10log NMSE æ ö = ç ÷ è ø 1 1 0 0 1 [(, ) ( , )] M N m n MAE x m n xmn MN - - = = = - å å % 其中， xmn (,) 为原始图像的像素值， xmn %(,) 为解压缩之后的像素值。 在电子工程中，信号噪声比(SNR)一直是最流行的误差度量指标，在大多数情况下可提 供很有价值的信息，在数学上也比较容易计算。信号噪声比虽然也用在图像编码中，但由于 它的数值与图像编码系统中高压缩比的关系不容易体现，因此提出了其他的几种度量方法， 包括平均主观评分(mean opinion score，MOS)。 4.3 EZW编码 4.3.1 介绍 在1992年，Lewis，A. S.和Knowles, G.首先介绍了一种树形数据结构来表示小波变换的 系数[6]。在1993年，Shapiro, J. M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了 一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(embedded zerotree
第4章小波图像编 wavelet,EZw算法[门]。EZW主要用于与小波变换有关的二维信号的编码,但不局限于二维 信号。 嵌入(式)零树小波中的“小波”是指该算法以离散小波变换为基础,以大的小波变换系 数比小的小波变换系数更重要,以及高频子带中的小系数可以被抛弃的事实为背景。“零树 是指小波变换系数之间的一种数据结构,因为离散小波变换是一种多分辨率的分解方法,每 一级分解都会产生表示图像比较粗糙(低频图像)和比较精细(高频图像)的小波系数,在同 方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示,如果树根和它的 子孙的小波系数的绝对值小于某个给定的阈值T( threshold),那么这棵树就叫做零树。“嵌入 是渐进编码技术( progressive encoding)舶另一种说法,其含义是指一幅图像可以分解成一幅 低分辨率图像和分辨率由低到高的表示图像细节的许多子图像,图像合成的过程与分解的过 程相反,使用子图像生成许多分辨率不同的图像。EZW编码指的是,按照用户对图像分辨率 的要求,编码器可以进行多次编码,每进行一次编码,阈值降低12,水平和垂直方向上的 图像分辨率各提高1倍。编码从最低分辨率图像开始扫描,每当遇到幅度大于阈值的正系数 就用符号P表示,幅度小于阈值的系数用符号N表示,树根节点上的系数幅度小于阈值而树 枝中有大于阈值的非零树用符号Z表示,零树用符号T表示 小波图像编码( wavelet image coding)的一般结构如图4-05所示,它主要由小波变换 ( Wavelet transform)、量化( Quantization)和熵编码( Entropy Encoding)等3个模块组成。小波变 换不损失数据,但它是EW算法具有渐进特性的基础:量化模块对数据会产生损失,数 据损失的程度取决于量化阈值的大小,EwW算法指的就是这个模块的算法,它的输出 是符号集{P,N,TZ,0,1}中的一系列符号;熵编码模块对每个输入数据值精确地确定它 的概率,并根据这些概率生成一个合适的代码,使输出的码流( code stream)小于输入的码流 量化 波变换 EZW中的 熵编码 Zerotree Embedd 图405EZW算法结构 43.2算法 ZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次,生成一种分辨率图像 编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤:设置阈值、每个小波系数与阈值进 行比较、量化系数和重新排序。在扫描过程中需要维护两种表,一种是小波系数的符号表, 另一种是量化表。 1.零树 回顾二维小波变换的计算过程,不难想象各级子图像中的系数是相关的。在说明零树的 概念之前,需要对小波变换得到的系数、名称和符号加以说明。现以3级分解的离散小波变 换为例,图4-06表示Lena图像使用三级滤波器组做小波变换输出的子图像( (sub image)。需要 注意的是,分解之后的图像的名称在文献上有很多种,除了子图像之外,有的叫做子带图像 (sub- band image),有的把子图像进一步区分为高频子图像和低频子图像,或者粗糙图像和精 细图像等名称。这些名称从不同的角度反映图像的特性,在不同的场合下使用可以收到异曲 同工的效果。图中的数字1,2和3表示分解的级数编号,L3表示第3级的低频子图像,在这 个例子中,它是分辨率最低的子图像,HL3表示第3级分解在水平方向上的子图像,LHB表示 第3级分解在垂直方向上的子图像,HHB表示第3级分解在对角线方向上的子图像,其他的组 合符号依此类推。由于低频子图像的系数要比高频子图像的系数大,零树编码技术就是利用 这个事实来设计编码/解码过程中每一级使用的量化器
第4章 小波图像编码 5 wavelet，EZW)算法[7]。EZW主要用于与小波变换有关的二维信号的编码，但不局限于二维 信号。 嵌入(式)零树小波中的“小波”是指该算法以离散小波变换为基础，以大的小波变换系 数比小的小波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实为背景。“零树” 是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每 一级分解都会产生表示图像比较粗糙(低频图像)和比较精细(高频图像)的小波系数，在同一 方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的 子孙的小波系数的绝对值小于某个给定的阈值T(threshold)，那么这棵树就叫做零树。“嵌入” 是渐进编码技术(progressive encoding)的另一种说法，其含义是指一幅图像可以分解成一幅 低分辨率图像和分辨率由低到高的表示图像细节的许多子图像，图像合成的过程与分解的过 程相反，使用子图像生成许多分辨率不同的图像。EZW编码指的是，按照用户对图像分辨率 的要求，编码器可以进行多次编码，每进行一次编码，阈值降低1/2，水平和垂直方向上的 图像分辨率各提高1倍。编码从最低分辨率图像开始扫描，每当遇到幅度大于阈值的正系数 就用符号P表示，幅度小于阈值的系数用符号N表示，树根节点上的系数幅度小于阈值而树 枝中有大于阈值的非零树用符号Z表示，零树用符号T表示。 小波图像编码(wavelet image coding)的一般结构如图4-05所示，它主要由小波变换 (Wavelet Transform)、量化(Quantization)和熵编码(Entropy Encoding)等3个模块组成。小波变 换不损失数据，但它是EZW算法具有渐进特性的基础；量化模块对数据会产生损失，数 据损失的程度取决于量化阈值的大小，EZW算法指的就是这个模块的算法，它的输出 是符号集{P, N, T, Z, 0, 1}中的一系列符号；熵编码模块对每个输入数据值精确地确定它 的概率，并根据这些概率生成一个合适的代码，使输出的码流(code stream)小于输入的码流。 小波变换 量化 EZW中的 熵编码 Zerotree, Embedding 图4-05 EZW算法结构 4.3.2 算法 EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次，生成一种分辨率图像， 编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤：设置阈值、每个小波系数与阈值进 行比较、量化系数和重新排序。在扫描过程中需要维护两种表，一种是小波系数的符号表， 另一种是量化表。 1. 零树 回顾二维小波变换的计算过程，不难想象各级子图像中的系数是相关的。在说明零树的 概念之前，需要对小波变换得到的系数、名称和符号加以说明。现以3级分解的离散小波变 换为例，图4-06表示Lena图像使用三级滤波器组做小波变换输出的子图像(sub image)。需要 注意的是，分解之后的图像的名称在文献上有很多种，除了子图像之外，有的叫做子带图像 (sub-band image)，有的把子图像进一步区分为高频子图像和低频子图像，或 者粗糙图像和精 细图像等名称。这些名称从不同的角度反映图像的特性，在不同的场合下使用可以收到异曲 同工的效果。图中的数字1, 2和3表示分解的级数编号，LL3表示第3级的低频子图像，在这 个例子中，它是分辨率最低的子图像，HL3表示第3级分解在水平方向上的子图像，LH3表示 第3级分解在垂直方向上的子图像，HH3表示第3级分解在对角线方向上的子图像，其他的组 合符号依此类推。由于低频子图像的系数要比高频子图像的系数大，零树编码技术就是利用 这个事实来设计编码/解码过程中每一级使用的量化器