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

平面编码。对阈值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)除直接后代外所有后代坐标的集合;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)判断其