《信息理论与编码》课程教学资源（拓展资料）EZW小波零树编码的原理与应用.pdf

EZW小波零树编码的原理与应用摘要：嵌入式零树小波(EZW）编码算法是基于小波变换的一种图像压缩方法，它可以实现渐进编解码，进行有损或无损压缩，具有较高的压缩比和图像恢复质量。在研究嵌入式零树小波编码算法及原理的基础上，描述了算法的应用过程，阐述了具体的实现思路。结合多组图像数据对算法的过程进行测试，对其性能进行了评价。关键词：嵌入式零树小波：仿真测试Abstract:EZW(embeddedzerotreewavelet)basedonwavelettransform,isakindofimagecoding.Itcarperformbothlossy andlossless compression,and progressivecodec,byproviding high compression rateandimage reconstruction quality.The process of algorithm application is described, and the concrete realizationmentality is elaborate. Finally unifies the multi-groups image data to carry on the test to the algorithm process, andcarry on the appraisal to its performance.Key words: EZW; coding,test嵌入式零树编码是一种利用小波变换对图像和视频进行编码的技术，是Shapiro于1993年提出的。其本质是将原始图像经二维小波变换后转换成小波域上的小波系数，然后对小波系数进行量化编码。由于小波变换后使得原始图像的能量集中在少数部分的小波系数上，因此最简单的系数量化方法就是将某一阈值以下的系数略去，只保留哪些能量较大的小波系数，从而达到数据压缩的目的。1嵌入式编码算法嵌入式编码就是编码器将待编码的比特流按重要性的不同进行排序，根据目标码率或失真度大小要求随时结束编码：同样对于给定码流解码器也能够随时结束解码，并可以得到相应码流截断处的目标码率的恢复图像。嵌入式编码中首先传输的是最重要的信息，也就是幅值最大的变换系数的位信息。内嵌编码的输出信息主要包括两部分：排序信息和重要像素的位信息。其中，位信息是编码必不可少的有效信息；而排序信息则是辅助信息，按其重要性从左到右排列，反映了重要像素在原图上的空间位置，用于恢复原始的数据结构。因此内嵌算法中排序算法的优劣和排序信息的处理决定了整个编码算法的效率。一幅图像经过三级小波分解后形成了10个子带，如图1所示。小波系数的分布特点是越往低频子带系数值越大，包含的图像信息越多，如图1中的LL3子带。而越往高频子带系数值越小，包含的图像信息越少。就是在数值相同的情况下，由于低频子带反映的是图像的低频信息，对视觉比较重要，而高频子带反映的是图像的高频信息，对视觉来说不太重要。这样对相同数值的系数来说，选择先传输较低频系数的重要比特，后传输较高频系数的重要比特。正是由于小波系数具有的这些特点，它非常适合于嵌入式图像的编码。L3L3HL2Lia103LL1HL1HL1HH2LH2HH1LH1HH1LH1(a）一级小波分解示意图(b)三级小波分解示总图

EZW 小波零树编码的原理与应用摘要：嵌入式零树小波(EZW) 编码算法是基于小波变换的一种图像压缩方法，它可以实现渐进编解码，进行有损或无损压缩，具有较高的压缩比和图像恢复质量。在研究嵌入式零树小波编码算法及原理的基础上，描述了算法的应用过程，阐述了具体的实现思路。结合多组图像数据对算法的过程进行测试，对其性能进行了评价。关键词：嵌入式零树小波;仿真测试 Abstract：EZW (embedded zerotree wavelet) based on wavelet transform, is a kind of image coding. It can perform both lossy and lossless compression, and progressive codec, by providing high compression rate and image reconstruction quality. The process of algorithm application is described, and the concrete realization mentality is elaborate. Finally unifies the multi-groups image data to carry on the test to the algorithm process, and carry on the appraisal to its performance. Key words：EZW; coding;test 嵌入式零树编码是一种利用小波变换对图像和视频进行编码的技术，是 Shapiro 于 1993 年提出的。其本质是将原始图像经二维小波变换后转换成小波域上的小波系数，然后对小波系数进行量化编码。由于小波变换后使得原始图像的能量集中在少数部分的小波系数上，因此最简单的系数量化方法就是将某一阈值以下的系数略去，只保留哪些能量较大的小波系数，从而达到数据压缩的目的。 1 嵌入式编码算法嵌入式编码就是编码器将待编码的比特流按重要性的不同进行排序，根据目标码率或失真度大小要求随时结束编码;同样对于给定码流解码器也能够随时结束解码，并可以得到相应码流截断处的目标码率的恢复图像。嵌入式编码中首先传输的是最重要的信息，也就是幅值最大的变换系数的位信息。内嵌编码的输出信息主要包括两部分：排序信息和重要像素的位信息。其中，位信息是编码必不可少的有效信息；而排序信息则是辅助信息，按其重要性从左到右排列，反映了重要像素在原图上的空间位置，用于恢复原始的数据结构。因此内嵌算法中排序算法的优劣和排序信息的处理决定了整个编码算法的效率。一幅图像经过三级小波分解后形成了10 个子带，如图1 所示。小波系数的分布特点是越往低频子带系数值越大，包含的图像信息越多，如图1 中的LL3 子带。而越往高频子带系数值越小，包含的图像信息越少。就是在数值相同的情况下，由于低频子带反映的是图像的低频信息，对视觉比较重要，而高频子带反映的是图像的高频信息，对视觉来说不太重要。这样对相同数值的系数来说，选择先传输较低频系数的重要比特，后传输较高频系数的重要比特。正是由于小波系数具有的这些特点，它非常适合于嵌入式图像的编码

图1小波分解示意图2EZW图像编码原理“零树”是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙的低频图像和比较精细的高频图像的小波系数，在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T（Threshold)，那么这棵树就叫做零树。“嵌入”是渐进编码技术的另一种说法，是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像，图像合成的过程与分解的过程相反，使用子图像生成许多分辨率不同的图像。EZW编码指的是按照用户对图像分辨率的要求，编码器可以进行多次编码，每进行一次编码，阅值降低1/2，水平和垂直方向上的图像分辨率各提高1倍。编码从最低分辨率图像开始扫描，给定一个小波系数xi，如果对于二个给定的门限T，IxiI>T，则称该小波系数为重要系数。正系数就用符号P表示，对于负的重要系数用符号N表示。树根节点上的系数幅度小于阅值而树枝中有大于阅值的非零树用符号Z表示，不属手任何零树的零节点称为抓立零点，零树用符号T表示，零树中位于最低分辨率子带的那个零节点称为零树根。零树根包含相应零树的全部信息，零树根的位置确定了，零树上全部零节点的位置也就确定了。子孙系数都为零的树为零树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。小波图像编码的一般结构主要由小波变换、量化和摘编码等3个模块组成。小波变换不损失数据，是EZW算法具有渐进特性的基础；量化模块对数据会产生损失，数据损失的程度取决于量化阈值的大小，EZW算法指的就是这个模块的算法。它的输出是符号集(P，N，T，Z，O,1中的一系列符号。熵编码模块对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流小于输入的码流。3EZW算法描述嵌入式零树小波编码（EZW编码）采用逐次逼近量化的方式使其具备嵌入特性。逐次逼近量化是选择一组门限T1.T2，TN-1，逐个门限对小波变换系数进行重要性检查。其中门限序列的选取是Ti+1=Ti/2，且TO选择得使所有得小波变换系数xj满足|xjl<2TO。对重要系数的位置编码和幅值编码，这两部分编码分别通过主扫描和副扫描，逐次提高量化精度，交替进行。在编（解）码过程中，相应于主扫描和副扫描需要不断更新这两张表：主表和副表，EZW算法可归纳为下面几个主要步骤。3.1选择阀值对于L级小波变换，EZW算法应用一系列的阈值，TOT1TL-1，T来确定小波系数的重要性，其中Ti=Ti-1/2为扫描次数，i=1,2，，L-1。初始值的选择（如图2所示)方法如下T=2INT(log2(1*mmD),其中xmax|是全体小波系数的绝对值的最大值638-34491013-1271-3112314-134-?367315-12-7514-93-14-2-9-72328-59476-22-10o3230S015

图 1 小波分解示意图 2 EZW图像编码原理 “零树”是指小波变换系数之间的一种数据结构，因为离散小波变换是一种多分辨率的分解方法，每一级分解都会产生表示图像比较粗糙的低频图像和比较精细的高频图像的小波系数，在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示，如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(Threshold)，那么这棵树就叫做零树。“嵌入”是渐进编码技术的另一种说法，是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像，图像合成的过程与分解的过程相反，使用子图像生成许多分辨率不同的图像。EZW 编码指的是按照用户对图像分辨率的要求，编码器可以进行多次编码，每进行一次编码，阈值降低1/2，水平和垂直方向上的图像分辨率各提高1 倍。编码从最低分辨率图像开始扫描，给定一个小波系数xi，如果对于一个给定的门限T，|xi |>T，则称该小波系数为重要系数。正系数就用符号P 表示，对于负的重要系数用符号N 表示。树根节点上的系数幅度小于阈值而树枝中有大于阈值的非零树用符号Z 表示，不属于任何零树的零节点称为孤立零点，零树用符号T表示，零树中位于最低分辨率子带的那个零节点称为零树根。零树根包含相应零树的全部信息，零树根的位置确定了，零树上全部零节点的位置也就确定了。子孙系数都为零的树为零树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。小波图像编码的一般结构主要由小波变换、量化和熵编码等3 个模块组成。小波变换不损失数据，是EZW 算法具有渐进特性的基础；量化模块对数据会产生损失，数据损失的程度取决于量化阈值的大小，EZW 算法指的就是这个模块的算法。它的输出是符号集{P, N, T, Z, 0, 1}中的一系列符号。熵编码模块对每个输入数据值精确地确定它的概率，并根据这些概率生成一个合适的代码，使输出的码流小于输入的码流。 3 EZW算法描述嵌入式零树小波编码(EZW编码)采用逐次逼近量化的方式使其具备嵌入特性。逐次逼近量化是选择一组门限T1,T2,TN-1，逐个门限对小波变换系数进行重要性检查。其中门限序列的选取是Ti+1=Ti/2，且T0 选择得使所有得小波变换系数xj满足|xj|<2T0。对重要系数的位置编码和幅值编码，这两部分编码分别通过主扫描和副扫描，逐次提高量化精度，交替进行。在编(解)码过程中，相应于主扫描和副扫描需要不断更新这两张表：主表和副表，EZW 算法可归纳为下面几个主要步骤。 3.1 选择阈值对于L 级小波变换，EZW算法应用一系列的阈值，T0 T1TL-1，T 来确定小波系数的重要性，其中Ti=Ti-1/2 为扫描次数，i=1,2, ,L-1。初始值的选择(如图2 所示)方法如下 (log ( max )) 2 2INT x T = ,其中 max x 是全体小波系数的绝对值的最大值

图2初始值的选择3.2主扫描扫描每一个系数产生系数符号。如果系数幅度大于阈值T且为正数，输出符号P(Positive)：如果系数幅度小于阈值T且为负数，输出符号N(Negative)：如果系数是零树根，输出T(Zerotree)：如果系数幅度小于阈值但树中有大于阅值的子孙系数，输出孤立零符号Z(Isolated Zero)。在扫描过程中，用一个主扫描表记录这些输出符号。当一个系数的输出符号为T时，它的所有子孙就不再扫描，用×表示。第一次主扫描结束后，将输出符号为P或N的系数的相应位置加标记或将这些系数置为零。以免在下次主扫描时再对他们编码。结果如图3所示。为了确定一个系数是否为零树根T或者是孤立零Z，需要对整个4叉树进行扫描，这样就需要花费时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入一个标记或者零，这样做可防止对它们再编码。PNP,ZT.ZXXT,IZ，ZioX+I, ZoXXXXXXXXXXXZuZXXXXZ,PaXXX+XXXXZi9ZX+XXX+XXXXXXXXXXXD1:PNZTPTTTTZTTZZZZZPZZ图3第一次主扫描结果3.3辅扫描辅扫描是对主扫描取出的带有符号P或者N的系数进行量化，产生代表对应量化值的符号“0”和“1”，这种符号称为量化符号。在量化系数之前要构造量化器。量化器的输入间隔为[Ti-1,2Ti-1]，该间隔被1.5Ti-1分成两个部分：[Ti-1,1.5Ti-1)和[1.5Ti-1.2Ti-1），量化间隔为0.5Ti-1，其中i为第i次编码。量化器的输出为量化符号“0”和“1”：“0”对应量化值为（1.5-0.25)Ti-1；“1”对应量化值为(1.5+0.25)Ti-1，如表1所示。表1第一次辅扫描量化系数幅值量化符号重构幅值63156034404915604740量化符号组成的位流为S,：1010，输出编码信息为T。=32，D,PNZTPTTTTZTTZZZZZPZZ1：1010。编码器输出两类信息，一类是给解码器的信息，包括阈值、主扫描表和辅扫描表：第二类是用于下次扫描的信息，包括阈值及辅扫描中获得的重要系数序列。小波图像的符号数据为：T=32，[63-P,34-N,49-P,47-P)。这些系数未排序。第二次主扫描结果如图4所示

图2 初始值的选择 3.2 主扫描扫描每一个系数产生系数符号。如果系数幅度大于阈值T 且为正数，输出符号P (Positive)；如果系数幅度小于阈值T且为负数，输出符号N(Negative)；如果系数是零树根，输出T(Zerotree)；如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号 Z(Isolated Zero)。在扫描过程中，用一个主扫描表记录这些输出符号。当一个系数的输出符号为T 时，它的所有子孙就不再扫描，用×表示。第一次主扫描结束后，将输出符号为P 或N 的系数的相应位置加标记或将这些系数置为零。以免在下次主扫描时再对他们编码。结果如图3 所示。为了确定一个系数是否为零树根T 或者是孤立零Z，需要对整个4 叉树进行扫描，这样就需要花费时间。此外，为了保护已经被标识为零树的所有系数，需要跟踪它们，这就意味需要存储空间来保存。最后要把绝对值大于阈值的系数取出来，并在图像系数相应的位置上填入一个标记或者零，这样做可防止对它们再编码。 D1：PNZTPTTTTZTTZZZZZPZZ 图3 第一次主扫描结果 3.3 辅扫描辅扫描是对主扫描取出的带有符号P 或者N 的系数进行量化，产生代表对应量化值的符号“0”和“1”，这种符号称为量化符号。在量化系数之前要构造量化器。量化器的输入间隔为[Ti-1,2Ti-1]，该间隔被1.5Ti-1 分成两个部分：[Ti-1,1.5Ti-1)和 [1.5Ti-1,2Ti-1)，量化间隔为0.5Ti-1，其中i 为第i 次编码。量化器的输出为量化符号“0” 和“1”；“0”对应量化值为(1.5-0.25)Ti-1；“1”对应量化值为(1.5+0.25)Ti-1，如表1 所示。表1 第一次辅扫描量化系数幅值量化符号重构幅值 63 1 56 34 0 40 49 1 56 47 0 40 量化符号组成的位流为 1 S :1010，输出编码信息为T0 =32， D1 PNZTPTTTTZTTZZZZZPZZ 1 :1010。编码器输出两类信息，一类是给解码器的信息，包括阈值、主扫描表和辅扫描表；第二类是用于下次扫描的信息，包括阈值及辅扫描中获得的重要系数序列。小波图像的符号数据为：T0 =32，{63-P,34-N,49-P,47-P}。这些系数未排序。第二次主扫描结果如图4 所示