零树编码算法小波系数

零树编码算法一零树编码算法的基本思想众所周知，小波系数的能量集中程度越高，需要编码的系数越少，编码所需的比特数就越少，所以小波压缩都是利用变换分解后的图象能量分布集中这一特性来编码的。小波系数的能量集中程度对图象编码非常重要，而不同层次上，相同空间滤波方向上的小波系数之间的相关性也非常重要。零树编码的基本思想就是基于这种相关性。经过小波变换后的图象被分解成若干个子频带，其中子带HH是低频分量，是原始图象的平滑版本，子带HL是水平方向上的高频，垂直方向上的低频分量；子带LH是垂直方向上的高频，水平方向的低频分量；子带HH是高频分量，揭示了原始图象在斜方向的边缘信息。为了提高对小波系数的压缩性能，JeromeM.Shapiro提出了一种新的数据结构零树（zerotree），如果小波系数x的绝对值小于给定的阈值TJ则此系数是可以忽略的。零树的方法是基于这样一个假设：如果在较粗的级别上，一个小波系数是小于阈值，可以忽略的，则所有在相同方向，相同位置的更高的级别上的系数也基本上是可以忽略不记的。经验证明这个假设通常是正确的。更特殊的情况下，在一个多级的子带系统里，除了最高频的子带之外，在每一级别的每个系数都是和该系数在更高的级别相同方位的系数集合相对应的，我们把在较粗的级别上的系数叫做父亲，而在所有在更高的级别上相应位置的系数都叫做后代，同样的，对于任一给定的后代，在更粗的级别上相同方位上对应的系数叫做祖先。对于一个QMF-金字塔算法的子带分解，如图所示，除了最低频的子带之外,所有的父亲结点都有4个儿子，而最低频的结点是有3个儿子。对系数的扫描顺序的原则是不可以有一个儿子结点是在它的父亲结点之前被扫描。对于一个N级的变换，扫描是先从最低频的子带开始的，这里记作LLn,然后扫描子带HLn,LHn,和HHn,然后扫描第n-1级的系数，以此类推。在金字塔分解中这种扫描模式的图示见下图，可以看到在一个给定的子带每个系数都是在下一个子带的如果一个系数如果一个系数x和它的所有后代都小于阈值，则这个系数X可以看作是零树的一个成员，一个零树的根指的是一个零树中的结点，但是它不是任何一个结点的后代，实践证明对于相同的阈值零树的根的分布并没有可预见性。偶们用一种特殊的记号给一个零树的根编码，则它的所有的后代的结点就都可以被忽略不记了。于是所有的系数都可以被归为3类来编码：1）零树的根，2）孤立的零结点，3）重要的点。当给最高级的系数编码时，由于已经没有后代，所以可以不用零树的记号而直接进行编码。在实践中，偶们通常把系数分成4类：1）零树的根，2）孤立的零结点，3）正的重要系数，4）负的重要系数。这个小改进将有利于嵌入。注意可能还存在着其它两种系数我们没有考虑，那就是“正的/负的重要系数，但是后代是零树”，在实践中，这种系数点出现的比率很低，为了减少编码的数据量，通常不与考虑。我的关于零树编码的算法的实现是用C++语言在VC6.0下实现的，所以在解释算法时，涉及到数据结构和算法的流程时，会一C++语言为例来说明零树编码算法的具体实现方法。二零树的数据结构在小波变换之后，得到的是每个原始图象的像素坐标对应的小波系数。我们要把这些系数都定义成零树的结点，除了最低频的和最高频的结点之外，每个结点都有四个子结点，父结点和子结点之间坐标的对应关系是：父亲（x,y） 儿子（2x2y）,（2x+1,2y）,（2x,2y+1）,（2x+1,2y+1）每个结点的内容包括该点的小波系数,该点的位置坐标，还有指向该结点四个儿子的指针。如下图所示Coeff|(x,y) |Son[4]具体用C++语言定义的数据机构如下：typedefstructnode*zerotree_pointer;typedefstructnode{doublecoeff;unsignedlongx,y;zerotree_pointerson[4];};假设图象经过N次分解，最低频分量最后只剩下一个系数，这个系数就被作为零树的根结点。零树的根结点和上面定义的结点稍有不同，零树的根结点的数据结构如下：系数值HLsonLHsonHHson具体用C++语言定义的数据机构如下：structroot_node{doubleroot_coeff;zerotree_pointerLH_son,HL_son,HH_son;};这样以来一棵零树的结构如下图所示：三．零树的构造定义完基本的数据结构之后，要进行的是零树的构造。即根据经过小波变换后的系数值构造出一棵零树来，零树的构造的依据是父亲结点和儿子结点之间存在着位置坐标的的对应关系：对任何点(x,y){Ovxvlength/2,Ovyvlength/2}父亲(x,y) 儿子(2x,2y),(2x+1,2y),(2x,2y+1),(2x+1,2y+1)根据这种对应关系，我们可以用递归的算法来实现零树构造，我们用类C的语言来描述该算法，Creat_Zerotree(x,y)的功能是构造一个以(x,y)为根结点的零树，算法如下：Creat_Zerotree(x,y){1.if(x>length/2||y>length/2)return;2．申请四个新的结点；3•分别将坐标为(2x,2y),(2x+12y),(2x,2y+1),(2x+1,2y+1)的小波系数添入新申请的结点；4.将(x,y)结点的四个儿子指针指向新建立的四个结点；5．Creat_Zerotree(2x,2y);Creat_Zerotree(2x+1,2y);Creat_Zerotree(2x,2y+1);Creat_Zerotree(2x+1,2y+1);Return;}零树的遍历（扫描算法）在图象编码中，扫描算法是很重要的，直接影响到编码和解码的时间复杂度，根据小波系数的分布特点，低频的部分是能量集中的区域，所以要先给低频的分量编码，扫描顺序也是应该是从低频到高频，这个顺序如图所示，图的扫描顺序对应于零树的遍历顺序，因为整个编码解码过程我们都是在对零树进行操作，如果说要按照先由低频到高频的顺序扫描的话，对应于零树就是遍历的时候，对任何一个结点，在它的父结点被访问之前，它都不可以被访问，即要按树层次从最顶层到最底层的顺序，一层层的遍历，这在数据结构里叫做平序遍历（levelorder），所以对图象的扫描过程其实就是对零树的平序遍历过程。平序遍历的是通过一个队列来实现的，队列的特点是先进先出。这个队列存放的都是指向结点的指针。遍历的时候最先访问的是根结点，然后把根结点的儿子结点都压入队列，下一个要访问的结点就是最先进入队列的那个结点，也就是说，从队列中取出一个元素，作为下一个访问的对象。访问之后，仍然是把该结点的所有儿子结点都压入队列（如果访问到最底层的结点时就没有儿子结点就不需要对队列进行操作），这样一直进行下去，直到队列为空，就证明所有的结点都被访问过了一遍。使用这个队列的目的是为了使每个父亲都能在儿子被访问之前被访问到。具体的算法如下：1．Add_queue(HL_son); //将HL_son加入队列；2．Add_queue(LH_son)； //将LH_son加入队列；3 Add_queue(HH_son)；//将HH_son加入队列；for(;;){root_node=delete_queue(); //从队列中取出一个结点；if(!IsEmpty_queue()) //当队列不为空的时候{map_code(root_node); //访问该结点；for(inti=0;i<4;i++){if(root_node->son[i]) //将该结点的四个儿子结点的指针加入队列中Add_queue(root_node->son[i]);}else{map_code(queue[front]);//访问最后一个结点；上述算法不仅在对图象进行扫描的时候被用到，而且在图象的解码，还有判断一个结点是否是零树的根的时候都要用到，具体差异会在以后提到。五．零树的编码算法在确定了扫描的顺序之后，我们就可以开始真正的编码过程，在零树的遍历过程中，就是每访问到一个结点，就对这个结点进行判断，是否要进行编码。正像在前面提到的那样，我们最后要把有用的结点分成4类：1）正的重要的结点；2）负的重要的结点；3）零树的根；4）孤立的零结点。正的和负的结点就是指大于设定的阈值的点，零树的根是指该点小于阈值，而且它的所有后代也都是小于阈值的，这样我们就可以只对该点进行编码，而忽略所有它的后代，孤立的零结点是指，该结点是小于阈值的，但是它的后代中有大于阈值的重要的结点存在；为了便于操作，我定义了一个双向链表来存放编码后的数据，这个双向链表的数据定义如下：#definePOS1#defineNEG2#defineIZ3#defineZTR4typedefstructtable_node*table_pointer;typedefstructtable_node{doubleCoeff_value;//结点的小波系数；

shortunsignedSymbol;//结点的分类标记；

table_pointerllink; //链表的左指针；table_pointerrlink; //链表的右指针；}Symbol是该结点属于上述四类需要编码的结点中的哪一类的标记。有了这个双向链表，我们就可以开始给零树进行扫描编码，每访问一点，如果是要编码的结点，我们就把它加到双向链表中去。下面是编码的流程图如下：■输入一个系数. 从上面的流程可以看出，编码的过程是先对一个结点进行访问，判断它是否大于阈值，如果大于阈值的话，它就是重要的结点，需要被编码，根据它的正负特性来决定Symbol就可以了，如果它是小于阈值的话，情况要复杂一些，我们要先来判断它的后代是否有大于阈值的点，这个过程是用一个叫做search_descend(zerotree_pointerroot_node)的函数来实现的，它的原理也是遍历以root_node为根结点的零树，如果遇到大于阈值的点就返回ture，如果没有的话就返回false。通过判断我们可以直到该结点是零树的根，还是孤立的零结点。然后做好标记存到双向链表中。值得注意的是，在对零树进行编码的过程，其实也是对零树进行修剪的过程，如果一个结点是零树的根的话，那么它的所有后代都可以忽略不记，我们就可以在这里把该结点的所有儿子指针置空，零树就被剪掉了一枝，这样不断的修剪整棵树。需要遍历的结点会不断减少。可以大大提高算法的复杂程度。读到双向链表中的数据最后是要串行化到磁盘文件中去的，这个过程不是我们讨论的重点，值得注意的是，双向链表中只有coeff和symbol是需要串行化的数据，而且必须按照链表原来的顺序存放，这样才可以正确的解压缩，因为我们并没有保存每个结点的位置信息，所以只能靠扫描编码的顺序来解压缩。这样做的好处是可以减少存放每个点位置的信息，使压缩比更高。六．零树的解码算法解码的过程是编码的逆过程，我们要把存在磁盘文件中的数据按照原来的顺序再从新读到双向链表map_table中去，然后根据这个双向链表来重建零树。再由零树来恢复出原来的小波变换后的图象，再通过小波变换的逆变换来恢复原图。在解码过程中，零树的重建过程是关键所在，因为只要能把零树重建起来，我们就可以把结点一个个添回到原图像中去，而零树的重建的关键是要找出各个结点的位置坐标，因为要把现有的双向链表中的数据填充回去，最难的就是不知道每个结点的位置，不直到该把哪个点添到哪里去，所以就必须按找链表存放的顺序来重建零树，来恢复原图。在图象的编码中，我们是用平序来遍历整棵树的，所以在零树的重建中，我们也要按平序来重建这棵树，也就是说，要从最高层到最低层，一层层的恢复原来的零树，并且在恢复的同时，根据零树的父亲和儿子的位置坐标的对应关系来把每个结点的位置信息也填充进去。这个过程同样要用到一个队列，来调度结点的生成顺序。因为要恢复的零树只能是修剪过的零树，原来完整的零树已经在压缩时被修剪了，不可能全部恢复出来，所以这棵树并不规则，因为凡是遇到零树的根结点(ZTR)，该结点的儿子就要置空。具体的过程是这样的：从链表头开始读数据，第一个结点就是零树的根结点，它的坐标显然是(0,0),然后第二个是HL_son,坐标是(1,0),然后是LH_son(0,l)和HH_son(1,1)这三个儿子结点的数据填充到零树中去之后，再把指向他们的指针压入队列，然后又开始了和解码过程相反的过程，从队列中取出一个结点，假设该结点的位置坐标是(x,y),判断链表当前指针(current)指向的结点的symbol，如果是ZTR的话，就把从队列中取出的结点的四个儿子指针都置