第9章 小波图像编码

1、第第9章章 小波图像编码小波图像编码 2022-2-31第第9章章 小波图像编码小波图像编码 第第9章章 小波图像编码小波图像编码 2022-2-329.1 从子带编码到小波编码从子带编码到小波编码 9.1.1 子带编码子带编码 子带编码子带编码(subband coding，SBC) 基本概念是把信号的频率分成几个子带，基本概念是把信号的频率分成几个子带， 然后对每个子带分别进行编码，然后对每个子带分别进行编码， 根据每个子带的重要性分配不同的位数来表示数据。根据每个子带的重要性分配不同的位数来表示数据。 分解滤波器树分解滤波器树(decomposition filter trees) 使用

2、一维正交镜像滤波器组使用一维正交镜像滤波器组(quadrature mirror filterbanks，QMF)把信号的频带分解成把信号的频带分解成4个相等的个相等的子带子带,重复这个过程，直到符合应用要求为止重复这个过程，直到符合应用要求为止,这样的这样的滤波器组称为分解滤波器树滤波器组称为分解滤波器树 。 第第9章章 小波图像编码小波图像编码 2022-2-33图图9-01(a)表示分解方法，图表示分解方法，图9-01(b)表示其相应的频谱。表示其相应的频谱。 图中的符号图中的符号 表示频带降低表示频带降低1/2，HH表示频率最高的子带，表示频率最高的子带，LL表示频率最低的子带。表示频

3、率最低的子带。 第第9章章 小波图像编码小波图像编码 2022-2-34 9.1.2 多分辨率分析多分辨率分析 多分辨率分析多分辨率分析( multiresolution analysis) : 也叫做多级小波分解，就是在一级分解之后继续进也叫做多级小波分解，就是在一级分解之后继续进行分析。行分析。 多分辨率图像多分辨率图像( multiresolution images)： 使用多级小波分解得到的分辨率不同的图像。使用多级小波分解得到的分辨率不同的图像。第第9章章 小波图像编码小波图像编码 2022-2-35图图9-02 用一级小波分解方法得到的图像用一级小波分解方法得到的图像第第9章章 小

4、波图像编码小波图像编码 2022-2-36图图9-03Lena的多分辨率图像的多分辨率图像 第第9章章 小波图像编码小波图像编码 2022-2-37 9.1.3 滤波器组与多分辨率滤波器组与多分辨率 可逆滤波器组可逆滤波器组(invertible filter bank)： 使用滤波和子采样使用滤波和子采样(subsampling)的方法用来把离的方法用来把离散信号分解成大小相等的两种信号，并且使用叫做散信号分解成大小相等的两种信号，并且使用叫做共轭镜像滤波器共轭镜像滤波器(conjugate mirror filters)的一种的一种特殊滤波器来取消信号的混叠特殊滤波器来取消信号的混叠(al

5、iasing)，这样可从，这样可从子采样的信号中重构原始信号子采样的信号中重构原始信号f(n)。 多分辨率理论多分辨率理论(multiresolution theory) 任何共轭镜像滤波器都可以用来刻画一种小波任何共轭镜像滤波器都可以用来刻画一种小波(t)，它能够生成它能够生成L2(R)实数空间中的正交基，而且快速离实数空间中的正交基，而且快速离散小波变换可以使用串联这些共轭镜像滤波器来实散小波变换可以使用串联这些共轭镜像滤波器来实现。现。 第第9章章 小波图像编码小波图像编码 2022-2-38 9.1.4 从子带编码到小波编码从子带编码到小波编码 小波变换和滤波器组之间的内在关系：小波变

6、换和滤波器组之间的内在关系： 离散时间滤波器离散时间滤波器(discrete-time filters)或者正交镜象滤或者正交镜象滤波器波器(quadrature mirror filter,QMF)可以被叠代，并在可以被叠代，并在某一种匀称某一种匀称(regularity，可粗略理解为函数的平滑性，可粗略理解为函数的平滑性)条条件下可获得连续小波。件下可获得连续小波。 作用：作用： 可使用有限冲击响应可使用有限冲击响应(finite impulse response，FIR)的的离散时间滤波器来执行小波分解，使用相同的滤波器可重离散时间滤波器来执行小波分解，使用相同的滤波器可重构小波分解之后

7、的信号。构小波分解之后的信号。 第第9章章 小波图像编码小波图像编码 2022-2-39 第二代小波第二代小波(second generation wavelets) 基本思想基本思想: 首先把信号分成偶数号样本和奇数号样本首先把信号分成偶数号样本和奇数号样本; 根据信号本身的相关性，奇数样本使用偶数样本进行预测，根据信号本身的相关性，奇数样本使用偶数样本进行预测，由预测丢失的信号叫做信号的细节信息由预测丢失的信号叫做信号的细节信息; 然后调整偶数样本以保存原始信号的粗糙信息和细节信息。然后调整偶数样本以保存原始信号的粗糙信息和细节信息。 效果：效果： 解决了非无限信号或者非周期信号的小波和小

8、波变换问题；解决了非无限信号或者非周期信号的小波和小波变换问题； 使计算速度得到很大的提高使计算速度得到很大的提高 第第9章章 小波图像编码小波图像编码 2022-2-310 9.1.5 小波分解图像方法小波分解图像方法*第第9章章 小波图像编码小波图像编码 2022-2-3119.2 失真的度量方法失真的度量方法 失真度量法，失真度量法， 用峰值信号噪声比用峰值信号噪声比(peak signal to noise ratio, PSNR)来衡量来衡量, 定义为最大像素值与均方差定义为最大像素值与均方差(mean square error，MSE)之比，之比， (db)210()10logPe

9、ak Signal ValuePSNRMSE第第9章章 小波图像编码小波图像编码 2022-2-312对对8位二进制图像，位二进制图像， (db)其中，其中，其中，其中，为原始图像的像素值，为原始图像的像素值，为解为解压缩之后的像素值。压缩之后的像素值。21025510logPSNRMSE112001(,)(,)MNmnM S Ex mnx mnM N ( , )x m n( , )x m n第第9章章 小波图像编码小波图像编码 2022-2-313规格化均方差规格化均方差(normalized mean square error，NMSE) 1120011200 ( , )( , ) ( ,

10、 )MNmnMNmnx m nx m nNMSEx m n信号噪声比信号噪声比(signal to noise ratio，SNR) 10110logSNRNMSE平均绝对误差平均绝对误差(mean absolute error，MAE) 11001 ( , )( , )MNmnMAEx m nx m nMN第第9章章 小波图像编码小波图像编码 2022-2-3149.3 EZW编码编码 9.3.1 介绍介绍 嵌入嵌入(式式)零树小波零树小波(embedded zerotree wavelet，EZW)算法算法 : “小波小波” 指该算法以离散小波变换为基础，以大的小波变换系数比小的小指该算法

11、以离散小波变换为基础，以大的小波变换系数比小的小波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实波变换系数更重要，以及高频子带中的小系数可以被抛弃的事实为背景。为背景。 “零树零树” 指小波变换系数之间的一种数据结构，因为离散小波变换是一种指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙(低频图像低频图像)和比较精细和比较精细(高频图像高频图像)的小波系数，在同一方向和相的小波系数，在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，同空间位置上的所有

12、小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(threshold)，那么这棵树就叫做零树。，那么这棵树就叫做零树。 “嵌入嵌入” 指渐进编码技术指渐进编码技术(progressive encoding) 第第9章章 小波图像编码小波图像编码 2022-2-315 小波图像编码小波图像编码(wavelet image coding)的一般的一般结构结构 ： 小波变换小波变换(wavelet transform) 不损失数据，但它是不损失数据，但它是EZW算法具有渐进特性的基础；算法具有渐进特

13、性的基础； 量化量化(quantization) 对数据会产生损失，数据损失的程度取决于量化阈值的大对数据会产生损失，数据损失的程度取决于量化阈值的大小，小，EZW算法指的就是这个模块的算法，它的输出是符号算法指的就是这个模块的算法，它的输出是符号集集P, N, T, Z, 0, 1中的一系列符号；中的一系列符号； 熵编码熵编码(entropy encoding) 对每个输入数据值精确地确定它的概率，并根据这些概率对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流生成一个合适的代码，使输出的码流(code stream)小于小于输入的码流。输入的码流。 第第9章

14、章 小波图像编码小波图像编码 2022-2-316 小波变换 量化 熵编码 EZW中的 Zerotree, Embedding 图图9-05 第第9章章 小波图像编码小波图像编码 2022-2-317 9.3.2 算法算法 每一遍扫描大致包含三个步骤：每一遍扫描大致包含三个步骤： 设置阈值设置阈值 每个小波系数与阈值进行比较每个小波系数与阈值进行比较 量化系数和重新排序量化系数和重新排序 需要维护两种表：需要维护两种表： 小波系数的符号表小波系数的符号表 量化表。量化表。 1. 零树零树第第9章章 小波图像编码小波图像编码 2022-2-318图图9-06 Lena图像使用三级滤波器组做小波变

15、换输出的子图像图像使用三级滤波器组做小波变换输出的子图像(sub image) 第第9章章 小波图像编码小波图像编码 2022-2-319图图9-07 各级子图像中的系数之间的关系各级子图像中的系数之间的关系第第9章章 小波图像编码小波图像编码 2022-2-320图图9-08 非零树与零树的概念非零树与零树的概念 第第9章章 小波图像编码小波图像编码 2022-2-321 2. 扫描方法扫描方法第第9章章 小波图像编码小波图像编码 2022-2-322 3. 算法算法 (1) 阈值的选择阈值的选择 开始时的阈值开始时的阈值T0通常按下式估算，通常按下式估算， 其中，其中，MAX(.)表示最大

16、的系数值，表示最大的系数值，Xi表示小波变换分解到表示小波变换分解到第第i级时的系数。以后每扫描一次，阈值减少一半。级时的系数。以后每扫描一次，阈值减少一半。 log (MAX(|)iXT 202第第9章章 小波图像编码小波图像编码 2022-2-323 (2) 给系数分配符号给系数分配符号 主扫描主扫描(dominant pass) : 扫描每一个系数以产生系数符号扫描每一个系数以产生系数符号 辅扫描辅扫描(subordinate pass) 量化带符号量化带符号P和和N的系数的系数判断条件判断条件输出符号输出符号|X|TX0P(positive)：表示正，重要系数：表示正，重要系数X0N(

17、negative)：表示负，重要系数：表示负，重要系数|X|T所有子孙系数所有子孙系数|X|Xi i|T,X|T|TZ：孤立的零，不重要系数：孤立的零，不重要系数表表9-1 第第9章章 小波图像编码小波图像编码 2022-2-324 9.3.3 算法举例算法举例 1. 树结构树结构图图9-10 第第9章章 小波图像编码小波图像编码 2022-2-325(a) 88子图像小波变换系数子图像小波变换系数 (b) 最低频带小波变换系数树最低频带小波变换系数树图图9-11 编码树的结构编码树的结构(1)第第9章章 小波图像编码小波图像编码 2022-2-326(a) 88子图像小波变换系数子图像小波变

18、换系数 (b) 2级子图像小波变换部分系数树级子图像小波变换部分系数树图图9-12 编码树的结构编码树的结构(2) 第第9章章 小波图像编码小波图像编码 2022-2-327 2. 编码编码 (1) 第一次扫描：第一次扫描： 步骤步骤1: 选择初始阈值。最大的系数为选择初始阈值。最大的系数为63，因此选择，因此选择T0=32。 步骤步骤2: 指定系数的符号。指定系数的符号。 第一次主扫描之后，缓冲存储器第一次主扫描之后，缓冲存储器D1中的系数符号为：中的系数符号为：D1: P N T T P T T Z T T T T T T T P T T第第9章章 小波图像编码小波图像编码 2022-2-

19、328 步骤步骤3: 量化系数。量化系数。 第一次辅扫描之后，第一次辅扫描之后，4个系数个系数63-P, 34-N, 49-P, 47-P的量化符号所组成的位流为：的量化符号所组成的位流为：S1: 1 0 1 0 表9-2 第一次辅扫描量化表系数幅度系数幅度量化符号量化符号重构幅度重构幅度63156340404915647040第第9章章 小波图像编码小波图像编码 2022-2-329 步骤步骤4: 重新排列带重新排列带P/N符号的数据。符号的数据。 步骤步骤5：输出编码信息。：输出编码信息。 给解码器的信息包含下面三种：给解码器的信息包含下面三种：HEADER (即即T0=32), D1:

20、P N T T P T T Z T T T T T T T P T T “AND” S1: 1 0 1 0. 给下一次扫描用的信息包含下面三种：给下一次扫描用的信息包含下面三种： T0=32, 63-P, 49-P, 34-N, 47-P “AND”子带图像。子带图像。 第第9章章 小波图像编码小波图像编码 2022-2-330 (2) 第二次扫描第二次扫描 步骤步骤1: 设置新阈值：设置新阈值：T1=T0/2=16。 步骤步骤2: 指定系数的符号。指定系数的符号。 步骤步骤3: 量化系数。量化系数。 图图9-14 第第2次主扫描次主扫描 第第9章章 小波图像编码小波图像编码 2022-2-3

21、31 步骤步骤4: 重新排列带重新排列带P/N符号的数据。符号的数据。 步骤步骤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. 给下一次扫描用的信息包含下面三种：给下一次扫描用的信息包含下面三种：T1=16, 63-P, 49-P, 47-P, 34-N, 31-N, 23-P “AND”子带图像子带图像. (3) 第三次扫描第三次扫描 步骤步骤1: 设置新阈值：设置新阈值：T2=T1/2=8。 步骤步骤2: 指定系数的符号。指定

22、系数的符号。 第第9章章 小波图像编码小波图像编码 2022-2-332 步骤步骤3: 量化系数。量化系数。 图图9-15 第第3次主扫描（次主扫描（1） 第第9章章 小波图像编码小波图像编码 2022-2-333图图9-15 第第3次主扫描（次主扫描（2） 第第9章章 小波图像编码小波图像编码 2022-2-334 步骤步骤4: 重新排列带重新排列带P/N符号的数据。符号的数据。 步骤步骤5: 输出编码信息。输出编码信息。 给解码器的信息包含下面两种：给解码器的信息包含下面两种：D3: PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT “A

23、ND” 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”子带图像子带图像.第第9章章 小波图像编码小波图像编码 2022-2-335表表9-3 三次编码的输出三次编码的输出名称名称内容内容Header32D1 / S1P N T T P

24、T T Z T T T T T T T P T T / 1 0 1 0D2 / S2N P T T T T T T T T T T T T T T T / 1 0 0 1 1 0D3 / S3PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT/ 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0第第9章章 小波图像编码小波图像编码 2022-2-336 3. 解码解码 解码分为三个步骤：解码分为三个步骤： 首先设置阈值首先设置阈值 构造逆量化器构造逆量化器 解读位流中包含的位置和小波系数值解读位流中包含的位置和小波系

25、数值 (1) 第一次解码第一次解码 解码器开始时的阈值解码器开始时的阈值T0=32，它接收到来自编码器第一次，它接收到来自编码器第一次扫描输出的系数符号是，扫描输出的系数符号是，P N T T P T T Z T T T T T T T P T T / 1 0 1 0 这个信息相当于量化符号所组成的位流与系数符号之间有这个信息相当于量化符号所组成的位流与系数符号之间有如下的对应关系，如下的对应关系，D1PNT T P T T Z T T T T T T T P T TS110 1 0 第第9章章 小波图像编码小波图像编码 2022-2-337图9-16 第一次解码的结果第第9章章 小波图像编码

26、小波图像编码 2022-2-338 (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所示的所示的量化器。量化器。 第第9章章 小波图像编码小波图像编码 2022-2-339如

27、图如图9-17 第第2次解码次解码 第第9章章 小波图像编码小波图像编码 2022-2-340(3) 第三次解码第三次解码 解码器将使用编码器第三次扫描产生的信息，解码器将使用编码器第三次扫描产生的信息，D3： PPNPPNTTNNPTPTTNTTTTTTTTTTTTPTTTTTTTTPTTTTTTTTTTTT S3: 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0S3中用下划线表示在第二次解码时已经得到的系数。中用下划线表示在第二次解码时已经得到的系数。 解码器首先修改阈值，使新的阈值解码器首先修改阈值，使新的阈值T2=T1/2=8，然后构，然后构造如图造如图

28、9-18所示的量化器，进入第三次解码。所示的量化器，进入第三次解码。 第第9章章 小波图像编码小波图像编码 2022-2-341如图如图9-18 第第3次解码次解码 第第9章章 小波图像编码小波图像编码 2022-2-3429.4 SPIHT编码编码 9.4.1 介绍介绍 SPIHT(set partitioning in hierarchical trees)算法算法 译成译成“层树分集层树分集”算法。算法。 具有特性具有特性 图像的渐进传输，最先传送幅度大的系数图像的渐进传输，最先传送幅度大的系数 比较高的比较高的PSNR 复杂度比较低复杂度比较低 计算量比较少计算量比较少 位速率容易控制

29、位速率容易控制第第9章章 小波图像编码小波图像编码 2022-2-343 9.4.2 渐进图像的传输渐进图像的传输 采用幅度大的系数先传送原则的理由：采用幅度大的系数先传送原则的理由： 假设原始图像由一组像素假设原始图像由一组像素pi,j组成，用组成，用ci,j表示经过小波变表示经过小波变换之后产生的系数，其中换之后产生的系数，其中(i,j)为像素的坐标，也是小波图为像素的坐标，也是小波图像系数的坐标。为简化符号，使用字母像系数的坐标。为简化符号，使用字母p表示二维图像，表示二维图像，用用c表示小波变换之后的系数，因此一幅图像的小波变换表示小波变换之后的系数，因此一幅图像的小波变换可表示成，可

30、表示成， 表示单式表示单式(unitary)分层子带变换，经过小波变分层子带变换，经过小波变换之后的二维阵列具有与相同的维数。换之后的二维阵列具有与相同的维数。c = ( p )( )第第9章章 小波图像编码小波图像编码 2022-2-344 在渐进图像传送中，解码器开始设置的重构矢量在渐进图像传送中，解码器开始设置的重构矢量通常通常为零，然后按照接收到的编码信息进行修改。在接收到系为零，然后按照接收到的编码信息进行修改。在接收到系数的近似值或者精确值之后，解码器可以得到重构的图像数的近似值或者精确值之后，解码器可以得到重构的图像，其中，其中，表示小波变换的逆变换。表示小波变换的逆变换。 如果

31、用均方差如果用均方差(MSE)指标来衡量，则失真程度指标来衡量，则失真程度可表示为，可表示为，其中其中N为图像的像素数目，为图像的像素数目，是由系数是由系数重构重构的像素值。的像素值。 c p1( )mse(p p)D2mse,1(pp)()i ji jijDppN,i jp,i jc第第9章章 小波图像编码小波图像编码 2022-2-345 由于欧几里得范数由于欧几里得范数(Euclidean norm)即向量的长度相对于即向量的长度相对于单式变换单式变换 是不变的，因此可以证明，是不变的，因此可以证明， 该式表明，解码器开始使用的系数近似值该式表明，解码器开始使用的系数近似值为零为零时，最

32、大的系数时，最大的系数对减少均方差最重要，因此幅对减少均方差最重要，因此幅度比较大的系数需要先传送。度比较大的系数需要先传送。 ,i jc, i jc第第9章章 小波图像编码小波图像编码 2022-2-346 9.4.3 分集排序算法分集排序算法 分集排序算法分集排序算法(set partitioning sorting algorithm) 按照一种规则选择发送的系数按照一种规则选择发送的系数， 这个规则是这个规则是其中，其中，2n实际上就是实际上就是EZW算法中的阈值。编码时每扫算法中的阈值。编码时每扫描一遍，新的阈值就设置为描一遍，新的阈值就设置为2n-1。对给定的。对给定的n，如果，如

33、果|ci,j|2n，就称系数，就称系数ci,j是重要是重要(significant)的，否则就的，否则就称系数是不重要的称系数是不重要的(insignificant) 幅度比较和比较结果之间的关系幅度比较和比较结果之间的关系用用 表示表示。 , i jc1,22nni jc,( , )1max2( )0ni ji jTncS T其他,nSi j( , )nSi j第第9章章 小波图像编码小波图像编码 2022-2-347 9.4.4 类型和变量类型和变量图9-19 最低子带的一个系数和最最低子带的一个系数和最高子带的系数都没有子孙高子带的系数都没有子孙(descendant) 第第9章章 小波

34、图像编码小波图像编码 2022-2-348 三种次序列表变量三种次序列表变量 LIP (List of Insignificant Pixels): 不重要像素表，用于存放单个不重要的系数。用低通不重要像素表，用于存放单个不重要的系数。用低通(或者叫做或者叫做DC)子带的系数初始化。子带的系数初始化。 LIS (List of Insignificant Sets)： 不重要子集列表，用于存放不重要的系数树。用不重要子集列表，用于存放不重要的系数树。用DC子子带中不重要的系数集的坐标初始化。带中不重要的系数集的坐标初始化。 LSP (List of Significant Pixels)： 重

35、要像素表，用于存放重要系数。初始化成空集。重要像素表，用于存放重要系数。初始化成空集。 A型型(Type A)树树 : 也称也称D型树：型树：LIS代表坐标集，编码时需要检查所有的子代表坐标集，编码时需要检查所有的子孙系数以确定是否重要。孙系数以确定是否重要。 B型型(Type B)树树 : 也称也称L型树：型树：LIS代表坐标集，编码时需要检查除子系数之代表坐标集，编码时需要检查除子系数之外的所有子孙系数以确定是否重要。外的所有子孙系数以确定是否重要。第第9章章 小波图像编码小波图像编码 2022-2-349 9.4.5 算法算法 符号：符号：O(I,j)= the 4 offspring

36、of ci,j /系数系数ci,j的的4个子系数组成的坐标集个子系数组成的坐标集 D(I,j)= all descendants of ci,j /系数系数ci,j的所有子孙系数组成的坐标集的所有子孙系数组成的坐标集 /除子节点之外的所有子孙节点的坐标集除子节点之外的所有子孙节点的坐标集Sn(X)= 1 if some element of X has magnitude 2n, /在子孙坐标集中有幅度大于或者等于阈值的坐标集在子孙坐标集中有幅度大于或者等于阈值的坐标集0 otherwise / 在子孙坐标集中没有幅度大于或等于阈值的坐标集在子孙坐标集中没有幅度大于或等于阈值的坐标集/ 重要系

37、数测试方法：重要系数测试方法：( , )( , )( , )L i jD i jO i j,( , )1max2()0ni ji jXncSX其他第第9章章 小波图像编码小波图像编码 2022-2-350Sn(I,j)=1 if ci,j has magnitude2n,/ 在系数集在系数集ci,j中有幅度大于或等于阈值的系数中有幅度大于或等于阈值的系数0 otherwise/ 在系数集在系数集ci,j中没有幅度大于或等于阈值的系数中没有幅度大于或等于阈值的系数 变量：变量： LIP (List of Insignificant Pixels) / 存放单个不重要的系数存放单个不重要的系数LI

38、S (List of Insignificant Sets) / 存放不重要的系数树存放不重要的系数树Entries are: （i,j) of type A D(i,j)； / 是是A型树型树(i,j) of type BL(i,j) / 是是B型树型树LSP( List of Significant Pixels) / 存放重要系数存放重要系数第第9章章 小波图像编码小波图像编码 2022-2-351 *1. Initialization: / 初始化output n = log2(largest coefficient) / 确定阈值确定阈值set LSP = / 设置设置LSP为空集为

39、空集set LIP = (i,j) | ci,j is a root / 把坐标加到把坐标加到LIPset LIS = (i,j) of type A | ci,j is a root / 把所有树指定为类型把所有树指定为类型A，加到，加到LIS2.Sorting Pass:/ 排序扫描主要是检查排序扫描主要是检查LIP和和LIS中的系数是否重要，然后把重中的系数是否重要，然后把重要的系数移到要的系数移到LSPfor each entry (i,j) in LIP do/ 检查检查LIP中的所有系数以确定是否重要中的所有系数以确定是否重要output Sn(i,j) if Sn(i,j) =

40、1 then move (i,j) to LSP, output sign(ci,j) 2nT 第第9章章 小波图像编码小波图像编码 2022-2-352for each entry (i,j) in LIS do/ 检查检查LIS中的所有中的所有D型树以确定是否重要型树以确定是否重要if entry has type A thenoutput if = 1 then for each in do output if =1 then add (k,l) to LSP and output sign of else add (k,l) to the end of LIP.if L(i,j) is

41、 not empty thenmove (i,j) to end of LIS as entry of type Belsedelete (i,j) from LIS and go around the loop.( ,)nSD i j( ,)nSD i j( , )k l( , )O i j( , )nS k l( , )nSk l第第9章章 小波图像编码小波图像编码 2022-2-353if entry has type B then/ 检查检查LIS中的所有中的所有L型树以确定是否重要型树以确定是否重要output if = 1 thenfor each (k, l) in O (i,

42、j) doadd (k, l) to end of LIS as entry of type Aremove (i, j) from LIS3. Refinement Pass: / 精细扫描主要是处理精细扫描主要是处理LSP中的系数以增加它的精度中的系数以增加它的精度for each (i, j) in LSP doif (i, j) was not added in the last sorting pass thenoutput the n-th most significant bit of .4. Quantization Step:decrement n, go back to S

43、orting Pass.*( ( , )nSL i j( ( , )nSL i j第第9章章 小波图像编码小波图像编码 2022-2-354 9.4.6 算法举例算法举例 A执行执行SPIHT算法的步骤：算法的步骤： 1. 计算阈值和初始化。计算阈值和初始化。 2. 检查检查LIP中的所有系数以确定是否重要：中的所有系数以确定是否重要： 如果重要，输出如果重要，输出“1”和符号位，然后把该系数移到和符号位，然后把该系数移到LSP。 如果不重要，输出如果不重要，输出“0” 3. 按照树的类型，检查按照树的类型，检查LIS中所有重要的树：中所有重要的树： (1) 对对D型树：型树： 如果该树是重要

44、的，输出如果该树是重要的，输出“1”，然后对子节点的系数进行编，然后对子节点的系数进行编码：码： 如果该树不重要，输出如果该树不重要，输出“0” (2) 对对L型树：型树： 如果该树是重要的，输出如果该树是重要的，输出“1”，把每一个子节点移到，把每一个子节点移到LIS的的末端作为末端作为D型树，然后把父树从型树，然后把父树从LIS中删除。中删除。 如果该树不重要，输出如果该树不重要，输出“0”。 4. 减少阈值，然后返回到减少阈值，然后返回到2。第第9章章 小波图像编码小波图像编码 2022-2-355 B. 小波图像系数的编码小波图像系数的编码 一幅一幅44图像经过小波变图像经过小波变换的

45、两次分解后的系数为：换的两次分解后的系数为：创建如图创建如图9-20所示所示的一棵编码系数树的一棵编码系数树:第第9章章 小波图像编码小波图像编码 2022-2-356*计算初始阈值计算初始阈值T16。初始化。初始化: 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:

46、没有符号要处理没有符号要处理 - 第第9章章 小波图像编码小波图像编码 2022-2-357主扫描主扫描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

47、: 1 Is (2,0) significant? yes: 1 第第9章章 小波图像编码小波图像编码 2022-2-358LSP = (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?

48、 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 -第第9章章 小波图像编码小波图像编码 2022-2-359主扫描主扫描3:T = 4 Is (1,0) significant? yes: 1 LSP = (0,0), (2,0), (2,1) , (1,0) 1 (sign bit) Is (0,1) sig

49、nificant? 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: 1Is (2,2)

50、 significant? yes: 1 第第9章章 小波图像编码小波图像编码 2022-2-360LSP = (0,0), (2,0), (2,1), (1,0), (1,1), (3,0), (2,2)0(sign bit) Is (2,3) significant? yes: 1LSP = (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: 0LIP

51、 = (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 - 第第9章章 小波图像编码小波图像编码 2022-2-3619.5 EBCOT编码简介编码简介 9.5.1 介绍介绍 最佳截断嵌入码块编码最佳截断嵌入码块编码 (embedded block coding with optimiz

52、ed truncation，EBCOT) 是一种对小波变换产生的子带系数进行量化和编码是一种对小波变换产生的子带系数进行量化和编码的方法。的方法。 基本思想是把每一个子带的小波变换系数分成独立基本思想是把每一个子带的小波变换系数分成独立编码的码块编码的码块(code-block)，并且对所有的码块使用，并且对所有的码块使用完全相同的编码算法。完全相同的编码算法。第第9章章 小波图像编码小波图像编码 2022-2-362 “截断截断”的含义：的含义： 对每一个码块进行编码时，编码器不用其他码块的任何信对每一个码块进行编码时，编码器不用其他码块的任何信息，只是用码块自身的信息产生单独的嵌入位流息，

53、只是用码块自身的信息产生单独的嵌入位流(bitstream)。每一码块的嵌入位流可以被截断成长度不等。每一码块的嵌入位流可以被截断成长度不等的位流，生成不同的位速率。的位流，生成不同的位速率。 “最佳最佳”的含义：的含义： 每一码块的嵌入位流应该截断到什么程度才符合特定的目每一码块的嵌入位流应该截断到什么程度才符合特定的目标位速率、失真限度或者其他衡量图像质量的指标，也就标位速率、失真限度或者其他衡量图像质量的指标，也就是在给定一个目标位速率的情况下，使重构图像的失真程是在给定一个目标位速率的情况下，使重构图像的失真程度最小，度最小，David Taubman提出了一种认为是提出了一种认为是“最佳最佳”的的方法来截断每一个