第五部分小波图像压缩技术教学课件

第五章第五章 小波图像压缩技术小波图像压缩技术 二维正交多分辨分析二维正交多分辨分析 EZW编码编码 SPIHT编码编码小波分析及其工程应用小波分析及其工程应用-清华大学计算机系清华大学计算机系-孙延奎孙延奎-2005春春二维正交多分辨分析二维正交多分辨分析空间空间正交多分辨分析正交多分辨分析 若记,则构成的一个的一个标准正交基。准正交基。构成的一个多分辨分析。的一个多分辨分析。二维正交多分辨分析二维正交多分辨分析由容易推出：容易推出：从而,令令则则构成的一个的一个标准正交基。准正交基。二维二维Mallat算法算法二维维Mallat分解算法分解算法一维行变换一维行变换一维列变换一维列变换二维二维Mallat算法算法 一维行小波变换一维行小波变换 一维列小波变换一维列小波变换可分离的二维小波变换可分离的二维小波变换二维二维Mallat算法算法1.确定LL另一种计算方法另一种计算方法:2.确定确定HL注意注意:在在Matlab中，可以用函数中，可以用函数dwt2()和和idwt2()实现二维离散小波实现二维离散小波变换的小波分解与重构。变换的小波分解与重构。二维二维Mallat算法算法二维重构算法二维重构算法:二维二维Mallat算法算法 一维行小波变换一维行小波变换 一维列小波变换一维列小波变换双双正正交交滤滤波波器器的的情情况况二维小波变换的塔式结构二维小波变换的塔式结构 简单的压缩方案简单的压缩方案:方案方案1:只保留低频部分.方案方案2:全局阈值 法.方案方案3:保留绝对值较大的若干小波系数二维小波变换的塔式结构图二维小波变换的塔式结构图 图像像块的三的三级小波分解系数小波分解系数 嵌入式零树小波图像压缩技术嵌入式零树小波图像压缩技术-EZW编码编码 小波图象编码的一般结构小波图象编码的一般结构 小波树状结构小波树状结构（1992，Lewis and Knowles）几个重要的概念几个重要的概念:重要系数、不重要系数、零树根、孤立点重要系数、不重要系数、零树根、孤立点如何组织小波系数及如何组织小波系数及其位置信息？其位置信息？如何处理小波系数及如何处理小波系数及其位置信息？其位置信息？EZW编码编码 子带及小波系数的扫描顺序子带及小波系数的扫描顺序 通过通过多遍扫描多遍扫描编码多分辨图像，其中编码多分辨图像，其中每一遍扫描每一遍扫描包含以下的包含以下的处理步骤：处理步骤：1.选择阈值2.主扫描3.辅扫描4.重新排序5.输出编码信号 EZW编码编码 1.选择阈值选择阈值对于于L级小波小波变换，EZW算法算法应用一系列的用一系列的阈值，来确定小波系数的重要性，其中来确定小波系数的重要性，其中，为扫描次数，初始初始阈值的的选择方法如下：方法如下：1，2，.，L1。EZW编码编码 2.主扫描主扫描 在扫描过程中，用一个主扫描表记录这些输出符号。当一个系数的输出符号为在扫描过程中，用一个主扫描表记录这些输出符号。当一个系数的输出符号为T时，它的所有子孙系数就不再扫描，并用时，它的所有子孙系数就不再扫描，并用表示。表示。第第i次主扫描结束后，将输出符号为次主扫描结束后，将输出符号为P或或N的系数的相应位置加标记或将这些系数的系数的相应位置加标记或将这些系数置为零，以免在下次主扫描时再对它们编码。置为零，以免在下次主扫描时再对它们编码。：PNZTPTTTTZTTZZZZZPZZ EZW编码编码 3.辅扫描辅扫描对主扫描表进行顺序扫描，对其中输出符号为P或N的小波系数进行量化。表5.1 第一次辅扫描量化表系数幅值 量化符号 重构幅值 63 1 56 34 0 40 49 1 56 47 0 40量化符号量化符号组成的位流成的位流为：1010 系数量化器系数量化器4.重新排序重新排序为便于设置第次扫描所用的量化间隔，以提高解码的精度，对输出符号为P或N的数据重新排序。EZW编码编码 5.输出编码信息输出编码信息编码器输出两类信息：编码器输出两类信息：一类是给解码器解码器的信息，包括阈值、主扫描表和辅扫描表；第二类是用于下次扫描下次扫描的信息，包括阈值及第4步中重新排序过的重要系数序列。，：PNZTPTTTTZTTZZZZZPZZ；：1010，小波图像数据。小波图像数据。EZW编码编码 第二次编码：第二次编码：设置新阈值：主扫描：NPTTTTTTTTTTTZZZZ辅扫描：表5.2 第二次辅扫描量化表系数幅值 量化符号 重构幅值 63 1 60 49 0 52 34 0 36 47 1 44 31 1 28 23 0 20：100110 重新排序：EZW编码编码 第二次编码输出结果：第二次编码输出结果：a）为解码器提供的信息，：NPTTTTTTTTTTTZZZZ；：100110b）为下一次扫描的信息，小波图像数据。表表5.3 二次二次编码的的输出出结果果T032PNZTPTTTTZTTZZZZZPZZ/1010NPTTTTTTTTTTTZZZZ/100110EZW解码解码 解码过程的主要步骤包括：接收编码器发送的解码信息后，设置阈值，构造逆量化器。解读位流中包含的位置信息和小波系数信息。第一次解码第一次解码 解码器接收到的信息解码器接收到的信息：32/PNZTPTTTTZTTZZZZZPZZ/1010 重要的小波系数与其量化符号有如下的对应关系：重要的小波系数与其量化符号有如下的对应关系：EZW解码解码 第二次解码第二次解码 解码器接收到的信息解码器接收到的信息：16/NPTTTTTTTTTTTZZZZ/100110 其中S2的前4位表示第一次解码时得到的S1中的量化符号，它们的重构值依次为 。第二次解码过程由两步组成：第二次解码过程由两步组成：1）应用新的量化器，提高第一次解码得到的重要系数的重构精度。2）求解在第一次解码时尚未恢复的系数。中由系数输出符号组成的位流与中后两位量化符号间的对应关系如下：EZW解码解码 第二次解码后的结果第二次解码后的结果 小波零树算法具有显著编码性能的原因：小波零树算法具有显著编码性能的原因：（1）离散小波变换（2）零树编码（3）累进逼近（4）自适应算法编码。EZW编解码算法的实现:http:/perso.wanadoo.fr/polyvalens/clemens/ezw/ezw.html SPIHT编码编码 SPIHT算法是算法是EZW算法的改进算法算法的改进算法.SPIHT算法采用与算法采用与EZW算法相似的零树结构，但它在系数子集的算法相似的零树结构，但它在系数子集的分割和重要信息的传输方式上采用了独特方法，能够在实现幅值分割和重要信息的传输方式上采用了独特方法，能够在实现幅值大的系数优先传输的同时，不显式传送系数的排序信息。其基本大的系数优先传输的同时，不显式传送系数的排序信息。其基本依据是：任何排序算法的执行路径都是使用分支点的比较结果进依据是：任何排序算法的执行路径都是使用分支点的比较结果进行定义的，如果编码器和解码器使用相同的排序算法，则对于编行定义的，如果编码器和解码器使用相同的排序算法，则对于编码器输入的系数比较结果，解码器通过执行相同的路径就可获得码器输入的系数比较结果，解码器通过执行相同的路径就可获得排序信息。排序信息。SPIHT编码编码 分集规则分集规则 是重要的 是不重要的：节点(i,j)所有孩子的坐标集；：节点(i,j)所有子孙的坐标集；：所有树根的坐标集。：节点(i,j)所有非直系子孙的坐标集；一般地,SPIHT编码编码 分集规则分集规则 1)最初坐标集由最初坐标集由 和和 组成；组成；2)若若 是重要的，则是重要的，则 分成分成 及4个单节点 3)若若 是重要的，则是重要的，则 分成分成 4个集个集，有序表有序表 LIP不重要系数表；不重要系数表；LSP重要系数表；重要系数表；LIS不重要子集表。不重要子集表。每一个表每一个表项都使用坐都使用坐标标识 在在LIS中，坐标中，坐标 代表代表 或者或者分别用分别用(i,j)D和(i,j)L 表示表示SPIHT编码的主要步骤编码的主要步骤（1）阈值和有序表的初始化）阈值和有序表的初始化设阈值，其中 LSP为空集为空集 其中其中LIP和和LIS中小波系数中小波系数的排列的排列顺序序与零树的扫描顺序相同。与零树的扫描顺序相同。例例:小波系数最大幅值为63，故n5，阈值 SPIHT编码的主要步骤编码的主要步骤（2）排序扫描）排序扫描由以下两个大的步骤构成：由以下两个大的步骤构成：1）顺次检查顺次检查LIP中的所有小波系数中的所有小波系数，确定其是否重要，确定其是否重要 如果是重要的系数，则输出如果是重要的系数，则输出“1”及其符号位，其中正、负小波及其符号位，其中正、负小波系数的符号位分别采用系数的符号位分别采用“1”和和“0”表示，然后将该系数从表示，然后将该系数从LIP中删除，并添加到有序表中删除，并添加到有序表LSP的尾部。的尾部。如果如果 是不重要的系数，则输出是不重要的系数，则输出“0”。排序扫描1 输出T32对LIP中的每个表项顺次进行处理 Is（0,0）significant？yes：1 1（符号位）/将（0，0）从LIP中删除，添加到LSP的尾部/LSP（0,0）LIP（0,1）,（1,0）,（1,1）SPIHT编码的主要步骤编码的主要步骤 Is（0,1）significant？yes：1 0（符号位）LSP（0,0）,（0,1）LIP（1,0）,（1,1）Is（1,0）significant？no：0Is（1,1）significant？no：0（2）排序扫描）排序扫描2)对对LIS中的每个表项顺次处理，并对中的每个表项顺次处理，并对D型表项和型表项和L型表项分别采用不型表项分别采用不同的处理方法，具体算法如下：同的处理方法，具体算法如下：SPIHT编码的主要步骤编码的主要步骤 Check the significance of all trees in the LIS according to the type of tree type:For a tree of type D:If it is significant,output 1,and code its children:If a child is significant,output 1,then a sign bit and add it to the LSP If a child is insignificant,output 0 and add it to the end of LIP.If the children have descendants,move the tree to the end of LIS as type L,otherwise remove it from LIS.If it is insignificant,output 0.For a tree of type L:If it is significant,output 1,add each of the children to the end of LIS as an entry of type D and remove the parent tree from the LIS.If it is insignificant,output 0.SPIHT编码的主要步骤编码的主要步骤 三个有序表三个有序表LIP,LSP,LIS的的当前状态信息当前状态信息,即即LSP=（0,0）,（0,1）,（0,2）,（4,3）LIP=（1,0）,（1,1）,（0,3）,（1,2）,（1,3）,（2,0）,（2,1）,（3,0）,（3,1）,（4,2）,（5,2）,（5,3）LIS=（1,1）D,（0,1）L,（2,0）D,（3,0）D,（3,1）D（3）精细扫描）精细扫描对于LSP中的每个表项，若（2）中新添加的，不是在刚刚进行过的扫描过程则输出 的第n个最重要的位，其中 过程中设定的阈值。是扫描例子例子(续续):由于排序扫描由于排序扫描1进行之前，进行之前，LIS=,故没有符号位输出。故没有符号位输出。（4）进行下一次排序扫描和精细扫描）进行下一次排序扫描和精细扫描 例例5.6第一次第一次SPIHT编码后输出的信息编码后输出的信息 第一次编码过程完成后，编码器输出两类信息：第一次编码过程完成后，编码器输出两类信息：1)给解码器的信息给解码器的信息，包括域值，包括域值、排序扫描的输出位流、排序扫描的输出位流 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0、：精细扫描位流及三个有序表的精细扫描位流及三个有序表的初始化信息初始化信息，即，即LIP,LIS和和LSP 2)用于下次扫描的信息用于下次扫描的信息，包括域值，包括域值 LIP（0,0）,（0,1）,（1,0）,（1,1）LIS=（0,1）D,（1,0）D,（1,1）DLSP=的的当前状态信息当前状态信息.、三个有序表三个有序表LIP,LSP,LISSPIHT解码过程解码过程 为获得为获得SPIHT解码器算法，只需将编码器输出的位流、初始值以及三个控解码器算法，只需将编码器输出的位流、初始值以及三个控制表制表LIS、LIP、LSP的初始化信息提供给解码器，并执行编码器的相同的初始化信息提供给解码器，并执行编码器的相同路径即可。为此，只需将路径即可。为此，只需将SPIHT编码器代码中的输出（编码器代码中的输出（output）改为输）改为输入（入（input）即可。这样，解码器可恢复数据的排序信息。）即可。这样，解码器可恢复数据的排序信息。解码器需要做的另一项工作是更新重构的图像。对于阈值解码器需要做的另一项工作是更新重构的图像。对于阈值，当一当一个坐标个坐标 移到LSP中时，这表明，。再由随后输入的。再由随后输入的 符号位信息，可获得符号位信息，可获得 的重构值。进一步根据。进一步根据精细扫描过程中精细扫描过程中 二进表示的位信息二进表示的位信息 以获得更精确的重构信息。以获得更精确的重构信息。SPIHT解码过程举例解码过程举例-例例5.7 SPIHT解码器第一次编码为解码器提供的信息如下：解码器第一次编码为解码器提供的信息如下：位流 S5:1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0精细扫描表：空集初始n:n=5控制表初始化信息：LIP（0,0）,（0,1）,（1,0）,（1,1）LIS=（0,1）D,（1,0）D,（1,1）DLSP=解码器的执行过程：解码器的执行过程：排序扫描1：设定阈值T=25=32%对LIP中的每个表项顺次进行处理%对LIS中每个表项顺次进行处理精细扫描1：从精细扫描表读取位数据，修改LSP中相应系数的重构值。电子资源http:/www.cipr.rpi.edu/research/SPIHT/spiht3.htmlhttp:/dcl.ee.washington.edu/amiguel/spiht.htmlhttp:/