嵌入式零树小波EZW编码及其算法改进

在基于小波变换的图象压缩方案中,嵌入式零树小波 EZW(Embedded Zerotree Wavelets)[1]编码很好地利用小波系数的特性使得输出的码流具有嵌入特性。近年来,在对EZW改进的基础上，提出了许多新的性能更好的算法,如多级树集合分裂算法(SPIHT :Set Partitioning In Hierarchical Trees)[2],集合分裂嵌入块编码(SPECK：Set Partitioned Embedded bloCK coder),可逆嵌入小波压缩算法(CREW:Compression with Reversible Embedded Wavelets)[3] 。本文对这些算法进行了原理分析、性能比较,说明了嵌入式小波图象编码的研究方向。

　　1. 嵌入式零树小波编码算法EZW

　　1. 1算法原理:
 

　　内嵌编码[1](embedded coding)就是编码器将待编码的比特流按重要性的不同进行排序，根据目标码率或失真度大小要求随时结束编码;同样，对于给定码流解码器也能够随时结束解码，并可以得到相应码流截断处的目标码率的恢复图象。内嵌编码中首先传输的是最重要的信息，也就是幅值最大的变换系数的位信息。图1显示了一个幅度值由大到小排序后的变换系数的二进制列表。表中每一列代表一个变换系数的二进制表示，每一行代表一层位平面，最上层为符号位，越高层的位平面的信息权重越大，对于编码也越重要。内嵌编码的次序是从最重要的位(最高位)到最不重要的位(最低位)逐个发送，直到达到所需码率后停止。

　　由图1可知内嵌编码的输出信息主要包括两部分：排序信息和重要象素的位信息。其中，位信息是编码必不可少的有效信息，对应于表中箭头所划过的比特位;而排序信息则是辅助信息，按其重要性从左到右排列，反映了重要象素在原图上的空间位置，用于恢复原始的数据结构。因此，内嵌算法中排序算法的优劣和排序信息的处理决定了整个编码算法的效率。

　　一副图象经过三级小波分解后形成了十个子带，如图2所示。小波系数的分布特点是越往低频子带系数值越大，包含的图象信息越多，如图2中的LL3子带。而越往高频子带系数值越小，包含的图象信息越少。就是在数值相同的情况下，由于低频子带反映的是图象的低频信息，对视觉比较重要，而高频子带反映的是图象的高频信息，对视觉来说不太重要。这样对相同数值的系数选择先传较低频的系数的重要比特，后传输较高频系数的重要比特。正是由于小波系数具有的这些特点，它非常适合于嵌入式图象的编码算法。在JPEG2000标准中以小波变换作为图象编码的变换方法。

　　EZW算法利用小波系数的特点较好地实现了图象编码的嵌入功能，主要包括以下三个过程：零树预测，用零树结构编码重要图，逐次逼近量化。

　　1) 零树预测

　　一副经过小波变换的图象按其频带从低到高形成一个树状结构，树根是最低频子带的结点，它有三个孩子分别位于三个次低频子带的相应位置，见图2左上角，其余子带(最高频子带除外)的结点都有四个孩子位于高一级子带的相应位置(由于高频子带分辨率增加，所以一个低频子带结点对应有四个高频子带结点，即相邻的2×2矩阵，见图2)。这样图2所示的三级小波分解就形成了深度为4的树。

　　定义一个零树的数据结构：一个小波系数x，对于一个给定的门限T，如果|x|

　　2) 用零树结构编码重要图

　　重要图包括三种要素：即重要系数、孤立零和零树根。其中，对于一个给定的阈值T，如果系数X本身和它的所有的子孙都小于T，则该点就称为零树根;如果系数本身小于T，但其子孙至少有一个大于或等于T，则该点就称为孤立零点。在编码时分别用三种符号与之对应。当编码到最高分辨率层的系数时，由于它们没有子孙，零树根不再存在，只需其余两种符号即可。为了有利于内嵌编码，将重要系数的符号与重要图一起编码，这样就要使用四种符号：零树根、孤立零、正重要系数、负重要系数。

　　3) 逐次逼近量化(Successive-Approximation Quantization,SAQ)

　　内嵌编码的核心在于采用了逐次逼近的量化方法(SAQ)。SAQ按顺序使用了一系列阈值T0、T1，┄，TN-1来判决重要性，其中Ti=Ti-1/2，初始阈值T0按如下条件选择，∣Xj∣<2T0,其中Xj表示所有变换系数。

　　在编(译)码过程中，始终保持着两个分离的列表：主表和辅表。主表对应于编码中的不重要的集合或系数，其输出信息起到了恢复各重要值的空间位置结构的作用，而辅表是编码的有效信息，输出为各重要系数的二进制值。编码分为主、辅两个过程：在主过程中，设定阈值为Ti,按上述原理对主表进行扫描编码，若是重要系数，则将其幅值加入辅表中，然后将该系数在数组中置为零，这样当阈值减小时，该系数不会影响新零树的出现;在辅过程中，对辅表中的重要系数进行细化，细化过程类似于比特平面编码。对阈值Ti来说，重要系数的所在区间为[Ti,2Ti]，若辅表中的重要系数位于[Ti，3Ti/2],则用符号“0”表示，否则用符号“1”表示。编码在两个过程中交替进行，在每个主过程前将阈值减半。译码时系数的重构值可以位于不确定区间的任意处，如果采用MMSE准则，则重构值应位于不确定区间的质心处。实际中为简单起见使用区间的中心作为重构值。

　　1. 2算法分析：

　　研究表明，在图象的低比特率编码中，用来表示非零系数所在位置的开销远远大于用来表示非零系数值的开销。零树结构正是一种描述图象经过小波变换后非零数值位置的有效方法。EZW的编码思想是不断扫描变换后的图象，生成多棵零树来对图象编码：一棵零树的形成需要对图象进行两次扫描。在生成第一棵零树时，首先找出变换后图象的最大绝对值系数，用它对应的T0作初始阈值，对图象进行第一次扫描。将图象中绝对值小于阈值系数都看作零，然后按前面的符号定义形成零树。在第二次扫描中，对那些绝对值大于阈值的结点(POS和NEG)按其绝对值是否大于阈值的1.5倍附加一个比特1或0来描述其精度。这样做的目的是减小非零结点系数值的变化范围，使其适应下一次阈值减半后的比特附加(具体细节见文[1])。而后将阈值减半，再经两次扫描生成第二棵零树，在第一次扫描生成零树时，以前已经大于阈值的结点不再考虑，而第二次扫描附加比特时则要考虑以前数值较大的结点以保证精度。如此重复下去，不断生成零树，直到达到需要的编码精度为止。

　　研究发现EZW算法存在的问题是：

　　(1).由于编码时它形成多棵零树，因而要多次扫描图象，造成效率很低。而且每一棵树必须在前一棵树形成之后才能形成，所以也很难用并行算法优化。

　　(2).对所有的频域进行等同重要度的编码，不能充分利用小波变换的特点。改进办法之一是把最低频子图与其它子图分开处理，对其进行单独的无失真编码。

　　(3).在一棵零树中包含的元素越多，则越有利于数据压缩。在EZW算法中存在这样的树间冗余，在SPIHT算法中则进一步利用了这种树间冗余。

　　(4).通过对小波系数的分析发现，在同一子带中相邻元素间有一定的相关性，尤其在高频子带存在大量的低值元素，所以可以通过子带中的集合把大量的这种低值元素组织到一起，达到数据压缩的目的。而EZW算法并没有充分利用这种相关性。在SPECK算法中利用这种相关性达到了数据压缩的目的。

　　2. 多级树集合分裂算法 SPIHT

　　原理分析：

　　EZW算法是一种基于零树的嵌入式图象编码算法，虽然在小波变换系数中，零树是一个比较有效的表示不重要系数的数据结构，但是，在小波系数中还存在这样的树结构，如图2，即它的树根是重要的，除树根以外的其它结点是不重要的。对这样的系数结构零树就不是一种很有效的表示方法。A.Said和W.A.Pearlman根据Shapiro零树编码算法(EZW)的基本思想，提出了一种新的且性能更优的实现方法，即基于分层树集合分割排序(Set Partitioning in Hierarchical Trees,SPIHT)的编码算法。它采用了空间方向树(SOT：spatial orientation tree)、集合D(i,j)和L(i,j)更有效地表示这样的系数结构，从而提高了编码效率。

　　1)SPIHT算法中用到的概念

　　算法中的一些符号和概念说明如下：

　　● H：空间方向树所有根结点的坐标集合;

　　● Z(i,j)：点(i,j)及其所有的后代的坐标集合，即指空间方向树;

　　● D(i,j)：点(i,j)的所有后代(子孙)的坐标集合，不包括(i,j)点本身;

　　● O(i,j)：点(i,j)的直接后代(儿子)的坐标集合，在分层塔形结构的最高层H有O(i,j)={(i+LL,j)，(i，j+LL)，(i+LL,j+LL)},除此之外的结点有O(i,j)={(2i,2j),(2i,2j+1),(2i+1,2j), (2i+1,2j+1)}，这里LL为最高层H的尺度。

　　● L(i,j)：点(i,j)除直接后代外所有后代坐标的集合;[!--empirenews.page--]SPIHT算法是EZW算法的改进，它继承了图2所示的小波系数的零树结构，这里称作“空间方向树”结构。

　　基于以上概念，在SPIHT算法中，集合的分割策略如下式所示：

　　2)排序过程

　　编码中使用了三个表：不重要系数表LIP(the list of insignificant pixels)、重要系数表LSP(the list of significant pixels)和不重要集合表LIS(the list of insiginificant sets)。LSP初始化为空表，LIP用最低频子带系数(如三级分解中的LL3、LH3、HL3、HH3中的系数)初始化，LIS用每一个空间方向树的根结点(如三级分解中的LH3、HL3、HH3中的系数位置)来初始化。

　　对重要图的确定主要是通过空间方向树的多次分裂来实现的。一个三级空间方向树T(i,j)在初始化时分裂成树头结点c(i,j)和剩余集合D(i,j)，见公式(1)。对c(i,j)判断其重要性，若重要则转到LSP中。对集合D(i,j) 进行重要性测试，若D(i,j)是不重要的，则D(i,j)用一个符号就可以表示出来。若D(i,j)是重要的，则D(i,j)继续分裂为两个集合O(i,j)和L(ij),如公式(2)。对O(i,j)中的每个元素分别进行重要性测试，把重要元素转到LSP中。对L(i,j)集合进行重要性测试，若L(i,j)不重要，则用一个符号就可以表示该集合，若L(i,j)重要，则L(i,j)分裂为四部分，每部分由相应空间方向树的位置上的元素构成，每一部分与O(i,j)中的四个元素分别构成四棵新树，由于每棵新树的头结点已经判断，只对新树的剩余部分也就是L(i,j)分裂出的四个集合即进行判断，见公式(3) 。如此重复对每棵树进行分裂和判断直到找出每棵树中的所有重要元素，把它们转到LSP中。可以看到SPIHT算法对重要图的排序是通过一系列的集合分裂完成的，即一棵树T(i,j)分裂成头结点元素c(i,j)和剩余部分D(i,j),对重要的D(i,j)继续分裂成头结点的直接四个孩子O(i,j)和剩余部分L(i,j),对重要的集合L(i,j)再继续分裂为四棵新树的剩余部分。

　　对每棵树的分裂不是一次进行到底的，而是要按照一定的扫描顺序进行。对各个子带的扫描顺序与EZW算法的扫描顺序相同。对由最低频子带(如LL3)和头结点构成的LIP中的元素是按从上到下、从左到右的顺序进行扫描的。而对其它子带则是按2×2的块为单位从上到下、从左到右依次扫描。对每个2×2块中元素还是按从上到下、对每个2×2块中元素还是按从上到下、从左到右顺序扫描。

　　3) 量化过程：

　　SPIHT采用与EZW算法相同的逐次逼近量化。

　　与EZW算法的比较：

　　SPIHT算法继承了EZW算法中的小波系数的零树结构，这里称为“空间方向树结构”。该算法不但把零树作为一个集合，而且把剩余树(即除去头结点的零树)也作为一个集合处理。如图2，假设在HH3中的某个元素C(i,j)是重要的，而其后所对应的HH2、HH1中的元素是不重要的，则在EZW算法中第一次扫描把C(i,j)赋予符号P，对其后的所有元素形成四棵零树ZTR(2i,2j)、ZTR(2i,2j+1)、ZTR(2i+1，2j)、ZTR(2i+1,2j+1)。共用PZZZZ五个符号表示这样的一个结构。在SPIHT中C(i,j)即放在LIP中，又放在LIS中。对LIP中元素的比较之后把C(i,j)转到LSP中。而对LIS比较之后发现D(i,j)是不重要的(D(i,j_)是指以(i,j)为树根的树除去根结点外所有的结点)，可用一个符号来表示。整个结构可用两个符号表示出来。所以该算法比EZW算法提高了压缩率。

　　SPIHT算法初始化过程、细化过程类似与EZW算法，它改进了EZW 重要图的表示方法，也就是重要系数在表中的排序信息，使得集合的表示更为精简，从而提高了编码效率。SPIHT算法在不同的比特率下比EZW算法的峰值信噪比都有所提高[2]。

3.集合分裂嵌入块编码器SPECK

　　3.1原理分析：

　　对小波变换系数的分析可以看出，在系数中存在许多的不重要系数，尤其对于高频子带更是如此。在EZW算法和SPIHT算法中，主要是利用树结构来表示这些不重要系数。这两种方法虽然利用了子带间不重要系数的相关性，但是没有充分利用同一子带中不重要系数的相关性。为此 Asad 和 Pearlman提出了SPECK算法，该算法是近期嵌入式分级图象编码算法中性能较好的一种。

　　1)算法中用到的概念和定义

　　集合定义：LIS——不重要系数集合列表 ，用最低频子带系数初始化(如三级分解中的LL3)。

　　LSP——重要系数列表，存放重要系数以便进一步量化。

　　集合S——放置待处理的块，用最低频子带系数初始化(如三级分解中的LL3)。

　　集合I——放置除了S之外的剩余块集合，I=X-S,X是所有块的集合。

　　块：相应小波分解的每一个子带定义一个相应的块。块可以是只包含单个元素，如8×8系数阵经过三级分解后对应的LL3、HL3、LH3和HH3都只包含一个元素。一般一个块中包含22N(N=0,1,2,…,n)个元素，其中，n-1是小波分解的层数。

　　2)排序过程

　　对于只包含一个元素的块，若重要则把它转到LSP中，以便进行进一步量化。对于包含2N×2N个元素的块，如果是不重要的，可以只用一个符号表示它。对于重要的块，则要等分为四个子块，然后从上到下、从左到右对各个子块进行重要性判断，对重要的子块继续分解，如此重复直到找出块中所有的重要系数，并把它转到LSP表中，以便进一步量化。

　　对各个块的处理顺序是与EZW算法对子带的扫描顺序是相同的，即从低频块(子带)依次到高频块(子带)。具体在SPECK算法中，采用一种称为倍频程分裂的方法，来决定各块扫描顺序。初始化时集合X由所有块构成，集合S是由最低频块(如LL3)来初始化，而剩余集合I=X-S。集合I依次分解出三个最低频的块(如HL3,LH3,HH3)和剩余集合I。然后对剩余集合I再进行一次分裂，分解出三个次最低频的块(如HL2,LH2,HH2)，如此重复直到把所有的块分裂出来，直到剩余集合I变为空集。这样就可以把各个块依次排列，重要图扫描就是以此顺序来进行。

　　通过以上两步，就可以把重要系数重要性放到表LSP中，以便下一步的逐次量化。

　　3)量化过程

　　SPECK算法的量化、求初始阈值与EZW算法相同。

　　SPECK算法的特点如下：①以上三种算法在扫描顺序和量化过程是一样的，差别在于对不重要系数的表示方法，EZW采用零树结构，SPIHT采用空间方向树，SPECK采用块结构。SPIHT算法在一个集合中包含了更多的不重要系数，提高了压缩率，而SPECK算法采用易于计算和并行处理的块结构，提高了编码速度。 ②另外，SPECK算法还有其它一些特点。需要小的动态存储，有强的容错性。因为块间是独立编码的，在传输发生误码时，只有误码所在的块受到影响。而在EZW和SPIHT中误码将影响到整个树结构，对图象的破坏较大。[!--empirenews.page--]4可逆嵌入小波压缩CREW(Compression with Reversible Embedded Wavelets)

　　虽然EZW、SPIHT和SPECK算法提供了从无损到有损的编码方法。编码可以在任何地方截断得到一个有损压缩,也可以一直编码直到一个准无损的压缩文件。在这里使用准无损是因为这三种算法没有考虑使用可逆的小波变换,即整数到整数的变换。这样在小波变换中就引入了量化误差。在一些场合要求实现从有损到无损的渐进传输,如医学图象的传输等。针对这一要求, 可逆嵌入小波压缩(CREW)强调了小波变换在渐进图象编码中的重要性。

　　现在研究用于图象编码的可逆小波变换的越来越多，这些变换在有限算术精度意义上是可逆的，是把整数变换为整数，它们是从准线性小波变换得来的。正是由于这些特性，这种小波变换非常适用于无损编码、最小内存占用、最小计算复杂性的压缩系统中。另外，这些变换对渐进从有损到无损的图象恢复以及有损压缩中感兴趣区的无损恢复特别有利。

　　对无损压缩，图象内容是一个影响变换效率的重要内容。对光滑图象，5/11-C，5/11-A及13/7-T变换最为有效，而5/3变换对含有大量高频信息的图象特别合适。

　　表1 图象编码常用的可逆的小波变换

　　显然，没有一种变换对所有图象不但具有低的计算复杂性还有好的有损和无损压缩性能。所以，使用时要根据具体情况加以选择。例如，在需要低的计算复杂性时，5/3变换是合适的选择，因为它在具有相当好的无损有损压缩性能同时具有低的计算复杂性[18]。

　　CREW是一个包含了有损和无损静态图象压缩系统。它使用了一个最好小波滤波器的可逆近似。对小波系数的编码使用了与EZW相似的Horizon方法,该方法利用了变换域中空间及频率信息的基于内容的编码。它提供了最新的对医学图象的无损压缩(深度大于8比特)的方法,也提供了在一个系统中对8比特深的图象的从有损到无损的压缩.

　　表1是一些常用的用于无损压缩的小波滤波器，根据具体使用可以选择。

　　5 结论:

　　由以上分析可见,在嵌入式小波编码的研究主要从以下三个方面进行。一是对小波系数的合理组织。研究表明，在图象的低比特率编码中，用来表示非零系数所在位置的开销远远大于用来表示非零系数数值的开销[15]。因此，内嵌算法中排序算法的优劣和排序信息的处理决定了整个编码算法的效率[14]。对这些系数进行合理排序,就可以得到更高的压缩比如SPIHT算法以及快的编码速度如SPECK算法。以上三种编码算法的根本区别在于对重要图的排序方法，如何以快的排序速度和少的重要图编码来寻找重要图是嵌入式编码算法研究的一个主要研究方向。二是从对重要系数的量化方法上进行研究，进一步提高数据的压缩率。三是从小波滤波器的构造出发,找出适合具体应用的可逆小波变换,以实现图象的从有损到无损的压缩。