摘 要:为了在图像轮廓处获得更好的压缩效果,在多级树集合分裂(SPIHT)算法的基础上提出了一种优先编码周围邻域中重要系数较多的系数与集合的小波图像压缩算法。在编码之前对系数或集合按照周围重要系数的个数进行排序,而且在扫描完周围有重要系数的集合后,就精细扫描已经得到的重要系数。这种编码次序是自适应确定的,不需要任何额外的存储空间,而且在到达指定压缩比时能够编码更多的重要系数。实验结果表明,对比原来的SPIHT算法,该方法能提高峰值信噪比并改善主观视觉感受。
关键词:图像压缩;多级树集合分裂算法;自适应扫描次序;小波变换;人类视觉系统
中图分类号: TP391.41;TP301.6 文献标志码:A
�
Improved set partitioning in hierarchical trees algorithm based on�
adaptive coding order
�
HUANG Ke�kun���*�
�(
Department of Mathematics, Jiaying University, Meizhou Guangdong 514015, China
)�
Abstract:
In order to obtain better compression on image edge, an improved Set Partitioning In Hierarchical Trees (SPIHT) algorithm based on prior scanning the coefficients around which there were more significant coefficients was proposed. The coefficients or sets were sorted according to the number of surrounding significant coefficients before being coded, and the previous significant coefficients were refined as soon as the sets around which there existed any significant coefficients had been scanned. The scanning order was confirmed adaptively and did not need any extra storage. It can code more significant coefficients at a specified compression ratio. The experimental results show that the method can improve PSNR and the subjective visual experience compared with SPIHT.
�Key words:
image compression; Set Partitioning In Hierarchical Trees (SPIHT) algorithm; adaptive coding order; wavelet transform; Human Visual System (HVS)
�
0 引言�
人们的注意力常集中于图像的边缘,为了能获取图像的边缘信息,要求分析工具有较好的时域、频域表征信号局部特征的能力。小波变换是20世纪80年代中期出现的一种具有时频局部表达能力的分析方法。自1989年Mallat首次将小波变换引入图像处理以来,小波变换以其优异的多分辨率分析特性,在图像编码领域得到了广泛的应用,并取得了良好的效果。其中Shapiro于1993年提出的嵌入式零树小波(Embedded Zerotree Wavelet, EZW)编码算法��[1]�是一种基于小波变换的里程碑式的图像压缩算法,它通过不同尺度的小波系数在每个比特平面的空间相似性构造零树,从而用一个零树根成功地预测了大量非重要系数,取得了良好的压缩效果。1996年Said和Pearlman提出了多级树集合分裂(Set Partitioning In Hierarchical Trees, SPIHT)算法��[2]�,对EZW算法做了重要的改进,其具有更高的压缩效率、更快的执行速度等优点,成为目前基于零树结构的压缩算法中的最优算法框架。�
后来,人们又提出了各种各样的改进算法，文献[3]提出了集合分裂嵌入块(Set Partitioning Embedded bloCK, SPECK)编码算法,利用了子带内相连系数块的关系；文献[4]在保持较高信噪比和不增加码元数量的基础上,使解码器具有简单误码检错能力；文献[5]提出了一种基于SPIHT算法的感兴趣区域编码方法,取得了较好的效果；文献[6]提出了一种低复杂度和低内存熵编码器(Low�complexity and Low�memory Entropy Coder, LLEC)算法,具有很快的执行速度；文献[7]通过引入系数块,减少了重要性判断次数,降低了编码冗余；文献[8]提出了一种无链表感兴趣区域优先编码算法, 能实现感兴趣区域的重建质量的精确控制, 并降低了存储需求；文献[9]提出了一种以提高图像熵编码效率为目的的图像预处理方法；文献[10]提出了一个基于图形处理单元加速的解码系统,使得卫星图像可以用SPIHT算法压缩后实时传输。�
以上的改进方法在不同方面提高了算法的性能,但都忽视了人类视觉系统。人眼对图像边缘的失真比其他区域的失真敏感很多,为此人们也提出了一些方法加以改进。例如：文献[11]对图像的边缘即小波系数的方差较大的地方给予了更多的关注,提高了压缩效果；文献[12]提出了一种基于高频子带自适应扫描的图像编码算法, 通过小波系数的绝对值大小及所处背景亮度,自适应确定同一高频子带小波系数的扫描次序,取得了一定的效果；文献[13-15]利用人眼视觉特性对小波系数进行加权。以上方法虽然考虑了人类视觉特性,但计算复杂,而且效果不好。本文提出一种新的基于SPIHT的编码方法,该方法优先编码周围邻域中重要系数较多的系数与集合的小波图像压缩算法,使得在图像轮廓处获得更好的压缩效果,并且在到达指定压缩比时能够编码更多的重要系数。虽然本文和文献[11-15]一样关注人类视觉,但是方法却不同。文献[11-15]都需要在码流中记录扫描次序或加权的位置,额外增加一些存储空间,降低了编码效率;而本文的编码次序是根据以前的重要系数自适应确定的,不需要任何额外的存储空间。�
1 SPIHT算法简介�
SPIHT算法定义了3个表: 重要系数表(List of Significant Pixels, LSP)、不重要系数表(List of Insignificant Pixels, LIP)和不重要集合表(List of Insignificant Set, LIS)。LSP初始化为空表, LIP用最低频子带系数坐标(如三级分解中的LL3、LH3、HL3、HH3中的系数坐标) 的集合初始化, LIS用每一个空间方向树的根节点的坐标(如三级分解中的LH3、HL3、HH3中的系数坐标) 的集合来初始化,代表方向树上某些系数的集合。 和EZW算法不同的是,SPIHT中的LIS分为两种集合:�D(i, j)表示系数(i, j)的所有后代系数的集合;L(i, j)表示系数(i, j)�的不包括直接孩子的所有后代系数的集合。 在不同的比特层面上, 依次对LIP、LIS和LSP中的记录进行编码,就可以渐进地对图像进行逼近。其中编码LIS时的规则如下。�
先依次遍历LIS的每一记录,然后进行判断:�
1)如果LIS当前的记录是�D(i, j)并且包含重要系数,则D(i, j)进一步分解成为L(i, j)和4个直接孩子,并把L(i, j)�加入LIS的尾部,同时根据这4个孩子的重要性加入LSP或LIP中。�
2）如果LIS当前的记录是�L(i, j)并且包含重要系数,则继续分解为D(2i,2j)、D(2i+1,2j)、D(2i,2j+1)和D(2i+1,2j+1),�并它们都加入LIS的尾部。�
3)如果�D(i, j)或L(i, j)�是不重要的,那么只需要存储一个比特就可以描述整个集合的系数。如果这种情况出现得越多,集合里的系数越多,就能得到越高的压缩比。 �
实验结果表明,对大多数自然图像,SPIHT能获得很好的压缩效果。然而,SPIHT算法对LIP和LIS中的记录进行编码时,采用了固定的扫描次序,这种次序并不能及时地找到重要系数进行编码,从而影响编码的效率。而且, SPIHT算法是在全部扫描完LIS后才精细扫描LSP,这种比特分配并不是最优的。为了克服这两个缺点,本文提出了一种新的编码次序,提高算法的效率。�
2 基于自适应编码次序的SPIHT算法�
2.1 算法原理�
人眼对图像轮廓信息的失真比较敏感,而高频子带的连续的重要系数所在位置一般就是图像轮廓,如果能够统计得到重要系数出现概率较大的空间位置,优先编码这些位置,无疑可以提高算法的效率。文献[11-12]的方法正是基于这样的思想去考虑的,但是由于重要系数的空间分布一般比较散乱,所以文献[11-12]的方法的效果不是很好,而且计算复杂,并且需要额外的空间存储扫描次序。�
由于自然图像在物体轮廓附近的灰度通常有个渐变的过程,所以在附近的高频子带小波系数的绝对值都会比较大。图1是对Lena图像进行小波分解得到的其中一个高频子带的示意图,其中白色表示绝对值大于32的系数,灰色表示绝对值大于16但小于32的系数,黑色代表绝对值小于16的系数。可以看到,白色的周围出现灰色的概率很大。�
用SPIHT算法对Lena图像进行编码, 在阈值�T=16�时,在LIP中对每一2×2小块��[2]�为单位的系数进行统计, 可以发现当2×2小块已经有较多重要系数(绝对值大于32)时,剩余的系数(即在LIP中的系数)在当前阈值下重要的概率(绝对值大于16)比较大,如表1所示。为了方便描述,如果系数的绝对值大于上一层的阈值,本文把该系数称为以前重要的;如果系数的绝对值小于上一层的阈值但大于当前阈值,把该系数称为当前重要的。
2.2 算法步骤�
本文算法的初始化和原始SPIHT算法一样,其余的主要步骤如下:�
1)编码LIP。首先对LIP中的系数进行排序,使得周围有越多以前重要的系数的记录排在越前面,然后才依次对LIP的系数进行编码:如果该系数重要则输出一个二进制编码1,并把该系数移到LSP中;否则输出0。�
2)编码LIS。首先对LIS中的记录进行排序,使得周围有越多以前重要的系数的记录排在越前面,然后才依次对LIS的系数进行编码。 当分裂得到新的�L(i, j)或D(i, j)�时, 也要按照周围重要系数的个数插入到LIS表中的合适位置, 不过以下两种记录例外: LIS中上一个阈值下留下的记录要优先扫描;分裂得到的�D(i, j)要放在L(i, j)前面。�这是因为大阈值下留下的LIS记录所代表的系数集合一般比较大,在当前阈值下很可能包含重要系数。�而对L(i, j)进行分裂时需要先得到D(i, j)才能找到重要系数,所以需要把分裂得到的D(i, j)要放在L(i, j)前面。��
3)编码LSP。在扫描完重要的概率较大的LIS的记录后（即扫描完LIS中周围含有以前重要的系数的记录后）,就对LSP进行精细扫描,然后再继续扫描LIS中剩余的记录。这样可以更好地优化比特分配。�
值得注意的是,上述扫描次序是根据以前重要的记录自适应确定的,不需要任何额外的存储空间。由于高频子带的连续的重要系数所在位置及其周围一般就是图像轮廓的位置,而本文算法优先编码了这些位置,从而能在图像轮廓处获得更好的视觉效果。�
3 实验结果 �
为了验证本文算法的效率,将本文算法与几种相关算法进行了对比。以512×512×8位的标准测试图像Lena、Barbara、Boats、Goldhill为例,使用双正交9/7小波对图像进行小波分解,结果如表3所示。其中小波分解时采用对称边界延拓，
加下划线的数字表示的是不同算法在相应压缩比下的最大值，有些算法的数值没有列出是因为原文中没有相应参数下的结果。�
从表3可看出：在相同的压缩比下,对Lena图像,本文算法的峰值信噪比(Peak Signal�to�Noise Ratio, PSNR)比原始SPIHT��[2]�提高0.1�dB左右,比SPECK��[3]�和LLEC��[6]�平均高�0.3�dB�左右,在高比特率时�PSNR�也比文献[11]和文献[12]的方法高。对Barbara图像,在5种压缩比下本文算法的【:原为“R��PSNR�”�PSNR�比原始SPIHT平均提高了0.1�dB,也比其余的算法高。对Boats和Goldhill图像,本文算法的效率是最好的。�
其中文献[11-12]使用了熵编码的,而SPIHT、SPECK、LLEC和本文算法都没有使用熵编码。由于熵编码占了一半以上的编码时间��[2]�,所以本文算法的执行速度和SPIHT一样快。在所有不使用熵编码的快速算法中,本文算法的效率是最高的。�