多级树集合分裂(spiht算法的过程详解与matlab实现多级树集合分裂(spiht)算法的过程详解与matlab实现多级树集合分裂(spiht)算法的过程详解与matlab实现多级树集合分裂(spiht)算法的过程详解与matlab实现.doc

多级树集合分裂（SPIHT）算法的过程详解与Matlab实现 上星期我们讨论了EZW算法，很高兴收到了一些朋友的email，对算法进行探讨、交流。这也是我开这个博客的源动力之一，学习就应该开诚布公、交流互助，在探讨中加深对所学知识的理解和掌握。在弄懂了EZW算法原理并用Matlab实现后，我继续学习EZW的改进算法。至今有一周的时间没更新博客、写新文章了，其实就是把时间用在EZW的一个改进算法——多级树集合分裂（Set Partitioning in Hierarchical Trees, SPIHT）算法的研究和Matlab实现。由于EZW是SPIHT的基础，所以在EZW算法的Matlab代码的基础上，我很快就完成了SPIHT的代码编写，但最痛苦的是一开始没吃透算法原理，程序在初始分集上出了错，调试了两天找不出根本问题，昨天从头再看一次算法原理，才发现问题所在……呵呵，小小的粗心就耽搁了我两三天的时间和精力！问题解决后，就编写程序注释了，上次EZW算法的代码都没写注释，让大家看着辛苦，不好意思哦！好，接下来就开始讨论SPIHT算法的原理，然后给出具体的Matlab代码。 一、SPIHT算法与EZW算法 EZW算法是一种基于零树的嵌入式图象编码算法，虽然在小波变换系数中，零树是一个比较有效的表示不重要系数的数据结构，但是，在小波系数中还存在这样的树结构，它的树根是重要的，除树根以外的其它结点是不重要的。对这样的系数结构，零树就不是一种很有效的表示方法。A.Said和W.A.Pearlman根据Shapiro零树编码算法(EZW)的基本思想，提出了一种新的且性能更优的实现方法，即基于多级树集合分裂排序（Set Partitioning in Hierarchical Trees, SPIHT）的编码算法。它采用了空间方向树（SOT：spatial orientation tree）、全体子孙集合D（i,j）和非直系子孙集合L(i,j)的概念以更有效地表示上述特征的系数结构，从而提高了编码效率。 SPIHT算法能够生成一个嵌入位流（embedded bit stream），使接收的位流在任意点中断时，都可解压和重构图像，具有良好的渐进传输特性；算法的初始化过程、细化过程类似于EZW算法，它改进了EZW 重要图的表示方法，也就是重要系数在表中的排序信息，使得集合的表示更为精简，从而提高了编码效率和图像压缩率。SPIHT算法在不同的比特率下比EZW算法的峰值信噪比（PSNR）都有所提高，具有计算复杂度低、位速率容易控制的特点。 SPIHT算法在系数子集的分割和重要信息的传输方面采用了独特的方法，能够在实现幅值大的系数优先传输的同时，隐式地传送系数的排序信息。这个隐式传送是什么意思呢？我们知道，任何排序算法的执行路径都是使用分支点的比较结果进行定义的！如果解码器和编码器使用相同的排序算法，则对于编码器输入的系数比较结果，解码器通过执行相同的路径就可获得排序信息，这就是所谓的“隐式传送排序信息”了。后面我们将会看到，SPIHT算法的解码、编码程序大部分代码是相同的，只在输入输出和分支点方面有所区别！ 二、SPIHT算法使用的树结构、分集规则和有序表 1、树结构 SPIHT算法的树结构与EZW算法的树结构基本相同，区别在于： 对于一幅N级二维小波分解的图像，在EZW算法的零树结构中，LL_N有三个孩子HL_N、LH_N和HH_N；而SPIHT算法的树结构中，LL_N是没有孩子的！ 挺不好意思的说，我前面说的程序出错，就是没看清这一点，只以为是点（1，1）没有孩子，结果初始化的不重要子集表LIS就包含了具有父子关系的点，造成排序扫描过程中对这些点重复扫描，生成冗余的LSP列表，重构图像失真大……哎，粗心使不得啊！ SPIHT算法的树结构中，树的每个节点与一个小波系数对应，我们用坐标（r,c）来标识节点或系数Cr,c。最低频子带LL_N中的系数和最高频子带中的系数没有孩子。 设X是一个小波系数坐标集：X={| (r,c) |}，对于正整数n，定义函数Sn (X) 如下： if?max{| Cr,c |}= 2 ^ n?then?Sn (X) = 1 else?Sn (X) = 0 如果Sn (X) = 1，则坐标集X关于阈值2 ^ n 是重要的，否则是不重要的。 2、分集规则 首先引入下面四个集合符号： ????? （1）O (r,c) —— 节点(r,c)所有孩子的集合；????? （2）D (r,c) —— 节点(r,c)所有子孙的集合（包括孩子）；????? （3）L (r,c) —— 节点(r,c)所有非直系子孙的集合（即不包括孩子）； L (r,c) = D (r,c) — O (r,c) （4）H —— 所有树根的坐标集。（对