上星期我们讨论了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) 如下:
ifmax{| Cr,c |}>= 2 ^ nthenSn (X) = 1
elseSn (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 —— 所有树根的坐标集。(对N级小波分解,H就是LL_N、HL_N、LH_N和HH_N中所有系数的坐标构成的集合)
根据SPIHT算法树结构的特点,除了LL_N、LL_1、HL_1、LH_1和HH_1之外,对任意系数的坐标(r,c),都有:(由于Matlab矩阵下标起始值为1,公式作了相应调整)
O (r,c) = { (2*r-1,2*c-1), (2*r-1,2*c), (2*r,2*c-1), (2*r,2*c) }
SPIHT算法的分集规则如下:
(1) 初始坐标集为{(r,c) | (r,c)∈H }、{D(r,c) | (r,c)∈H }。
(2) 若D(r,c) 关于当前阈值是重要的,则D(r,c) 分裂成 L (r,c) 和O (r,c)。
(3) 若L (r,c) 关于当前阈值是重要的,则L (r,c) 分裂成 4 个集合 D (rO,cO), (rO,cO) ∈O (r,c)。
3、有序表
SPIHT算法引入了三个有序表来存放重要信息:
(1) LSP —— 重要系数表;
(2) LIP —— 不重要系数表;
(3) LIS —— 不重要子集表。
这三个表中,每个表项都使用坐标(r,c)来标识。在LIP和LSP中,坐标(r,c)表示单个小波系数;而LIS中,坐标(r,c)代表两种系数集,即D(r,c) 或L (r,c),分别称为D型表项、L型表项,在Matlab实现时,用一个新的列表 LisFlag 来标识 LIS 中各个表项的类型,LisFlag的元素有‘D’、‘L’两种字符。
分享到:
相关推荐
【老生谈算法】多级树集合分裂(SPIHT)算法的过程详解与Matlab实现.docx
为了在图像轮廓处获得更好的压缩效采,在多级树集合分裂( SPIHT)算法的基础上提出了一种优先编码周围邻域中重要系数较多的系数与集合的小波图像压缩算法。在编码之前对系数或集合按照周围重要系数的个数进行排序,...
多级树集合分裂(SPIHT)算法的过程详解与Matlab实现实例演示
在matlab中实现了对SPIHT算法的编写
实现SPIHT算法!!!!使用MATLAB 实现程序
matlab开发-SPIHT算法图像压缩。在所有情况下,用于开发SPIHT算法的matlab程序都必须比jpeg版本好得多。
标准的SPIHT无损压缩算法,便于改进!
用matlab实现spiht的算法,具有很好的参考意义,能够直接用于自己的系统。
SPIHT算法源代码 MATLAB版本,已经备注好了,可以直接运行使用,特别适合新手
基于小波变换的图像压缩SPIHT算法的matlab实现程序
本代码为MATLAB代码,是经典的图像压缩算法SPIHT算法的完整实现。包含了该算法的全过程,能正常运行。
这是在linux平台下实现的spiht算法,对于初学者很有帮助,欢迎大家下载
这是一个spiht算法的改进程序,是由matlab实现,比spiht算法的psnr有很大提高
SPIHT压缩算法,代码简洁,注释清楚,已调试可运行
1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到...
这是一个很好的源代码,它是在linux平台下编程,主要是实现SPIHT算法,有极大的参考价值,对于图像压缩算法的初学者来说,很有帮助,欢迎大家下载。
在matlab中实现了对SPIHT算法的编写
SPIHT多级树集合分裂算法的基础知识,讲解详细,适合于入门者理解算法的基本思想。
利用matlab来实现图像压缩,spiht算法作者原版代码,包含了二进制熵编码以及小波变换,自适应分解等级,加入了示例图片。