《第五部分小波图像压缩技术教学课件.ppt》由会员分享，可在线阅读，更多相关《第五部分小波图像压缩技术教学课件.ppt（33页珍藏版）》请在三一文库上搜索。
1、第五章 小波图像压缩技术, 二维正交多分辨分析 EZW编码 SPIHT编码,小波分析及其工程应用-清华大学计算机系-孙延奎-2005春,二维正交多分辨分析,空间,正交多分辨分析,若记,则,构成,的一个标准正交基。,构成,的一个多分辨分析。,二维正交多分辨分析,由,容易推出：,从而,令,则,构成,的一个标准正交基。,二维Mallat算法,二维Mallat分解算法,一维行变换,一维列变换,二维Mallat算法,一维行小波变换,一维列小波变换,可分离的二维小波变换,二维Mallat算法,确定LL,另一种计算方法:,2. 确定HL,注意: 在Matlab中，可以用函数dwt2()和idwt2()实现二
2、维离散小波变换的小波分解与重构。,二维Mallat算法,二维重构算法:,二维Mallat算法,一维行小波变换,一维列小波变换,双正交滤波器的情况,二维小波变换的塔式结构,简单的压缩方案:,方案1: 只保留低频部分.,方案2: 全局阈值 法.,方案3: 保留绝对值较大的若干小波系数,二维小波变换的塔式结构图,图像块的三级小波分解系数,嵌入式零树小波图像压缩技术-EZW编码,小波图象编码的一般结构,小波树状结构 （1992，Lewis and Knowles ）,几个重要的概念: 重要系数、不重要系数、零树根、孤立点,如何组织小波系数及其位置信息？ 如何处理小波系数及其位置信息？,EZW编码,子带
3、及小波系数的扫描顺序,通过多遍扫描编码多分辨图像，其中每一遍扫描包含以下的处理步骤：,选择阈值,2. 主扫描,3. 辅扫描,4. 重新排序,5. 输出编码信号,EZW编码,选择阈值,对于L级小波变换，EZW算法应用一系列的阈值,，,，,来确定小波系数的重要性，其中,，,为扫描次数，,初始阈值的选择方法如下：,1，2，.，L1。,EZW编码,2. 主扫描,在扫描过程中，用一个主扫描表记录这些输出符号。当一个系数的输出符号为T时，它的所有子孙系数就不再扫描，并用表示。 第i次主扫描结束后，将输出符号为P或N的系数的相应位置加标记或将这些系数置为零，以免在下次主扫描时再对它们编码。,：PNZTPTT
4、TTZTTZZZZZPZZ,EZW编码,3. 辅扫描,对主扫描表进行顺序扫描，对其中输出符号为P或N的小波系数进行量化。,表5.1 第一次辅扫描量化表,量化符号组成的位流为,：1010,系数量化器,4. 重新排序,为便于设置第,次扫描所用的量化间隔，以提高解码的精度，对输出符号为P或N的,数据重新排序。,EZW编码,5. 输出编码信息,编码器输出两类信息： 一类是给解码器的信息，包括阈值、主扫描表和辅扫描表；,第二类是用于下次扫描的信息，包括阈值及第4步中重新排序过的重要系数序列。,，,：PNZTPTTTTZTTZZZZZPZZ；,：1010,，,，,小波图像数据。,EZW编码,第二次编码：,
5、设置新阈值：,主扫描：,：NPTTTTTTTTTTTZZZZ,辅扫描：,表5.2 第二次辅扫描量化表,：100110,重新排序：,EZW编码,第二次编码输出结果：,a）为解码器提供的信息,，,：NPTTTTTTTTTTTZZZZ；,：100110,b）为下一次扫描的信息,，,，,小波图像数据。,表5.3 二次编码的输出结果,EZW解码,解码过程的主要步骤包括：接收编码器发送的解码信息后，设置阈值，构造逆量化器。解读位流中包含的位置信息和小波系数信息。,第一次解码,解码器接收到的信息：32/ PNZTPTTTTZTTZZZZZPZZ/1010,重要的小波系数与其量化符号有如下的对应关系：,EZW
6、解码,第二次解码,解码器接收到的信息：16/NPTTTTTTTTTTTZZZZ /,100110,其中S2的前4位表示第一次解码时得到的S1中的量化符号，它们的重构值依次为 。,第二次解码过程由两步组成：,1）应用新的量化器，提高第一次解码得到的重要系数的重构精度。,2）求解在第一次解码时尚未恢复的系数。,中由系数输出符号组成的位流与,中后两位量化符号间的对应关系如下：,EZW解码,第二次解码后的结果,小波零树算法具有显著编码性能的原因：,（1）离散小波变换,（2）零树编码,（3）累进逼近,（4）自适应算法编码。,EZW编解码算法的实现:,http:/perso.wanadoo.fr/poly
7、valens/clemens/ezw/ezw.html,SPIHT编码,SPIHT算法是EZW算法的改进算法. SPIHT算法采用与EZW算法相似的零树结构，但它在系数子集的分割和重要信息的传输方式上采用了独特方法，能够在实现幅值大的系数优先传输的同时，不显式传送系数的排序信息。其基本依据是：任何排序算法的执行路径都是使用分支点的比较结果进行定义的，如果编码器和解码器使用相同的排序算法，则对于编码器输入的系数比较结果，解码器通过执行相同的路径就可获得排序信息。,SPIHT编码,分集规则,是重要的,是不重要的,：节点(i,j)所有孩子的坐标集；,：节点(i,j)所有子孙的坐标集；,：所有树根的坐
8、标集。,：节点(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）排序
9、扫描,由以下两个大的步骤构成：,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：
10、1 0（符号位） LSP（0,0）,（0,1） LIP（1,0） ,（1,1） Is （1,0） significant？no： 0 Is （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,
11、 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, ou
12、tput 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,
13、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
14、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）D LSP= ,的当前状态信息.,、三个有序表LIP,LSP,LIS,SPIHT解码过程,为获得SPIHT解码器算法，只需将编码器输出的位流、初始值以及三个控制表LIS、LIP、LSP的初始化信息提供给解码器，并执行编码器的相同路径即可。为此，只需将SPIHT编码器代码中的输出（output）
15、改为输入（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）,
16、 （1,1） LIS= （0,1）D, （1,0）D, （1,1）D LSP= ,解码器的执行过程： 排序扫描1： 设定阈值T=25=32 %对LIP中的每个表项顺次进行处理 %对LIS中每个表项顺次进行处理 精细扫描1： 从精细扫描表读取位数据，修改LSP 中相应系数的重构值。,电子资源,http:/www.cipr.rpi.edu/research/SPIHT/spiht3.html http:/dcl.ee.washington.edu/amiguel/spiht.html http:/ 该习题的说明：写出第二次编码与解码过程按1题计算；进一步写出第三次编码与解码过程按2题计算。 希望对图象压缩感兴趣的同学考虑选做此题。,