结合Huffman 编码和SPIHT 算法实现高效图像压缩方法
摘要：在低速通道中传递图像在许多领域中都非常关键。本文阐述了一种基于SPIHT 算法对高品质图像进行压缩的方法。该方法能给远距离无线通信应用提供递进的图像传输能力。这和JPEG 标准非常不同。JPEG 标准必须先将图像压缩到一定程度后再开始传送。而我们的方法中，数据头和图片数据被从目标图像中区分开来。头信息经过了必要的修改后先被传送。然后图像数据使用SPIHT 压缩并传送。实验表明我们的方法可以得到更好的压缩率和传输时间。
关键词：图像压缩；JPEG ；SPIHT ；小波；霍夫曼编码
1、 引言 小波变换（wavelet transform ，WT ）是一种新的变换分析方法，它继承并且发展了短时傅立叶变换局部化的思想，同时又克服了窗口大小不随频率变化等缺点，能够提供一个随频率改变的“时间-频率”窗口，是进行信号时频分析和处理的理想工具[1]。它的主要特点是通过变换能够充分突出问题某些方面的特征，能对时间（空间）频率的局部化分析，通过伸缩平移运算对信号（函数)逐步进行多尺度细化，最终达到高频处时间细分，低频处频率细分，能自动适应时频信号分析的要求，从而可聚焦到信号的任意细节，解决了Fourier 变换的困难问题，成为继Fourier 变换以来在科学方法上的重大突破[2]。 这一技术已被广泛应用于图像处理和压缩领域。Shapiro M Jerome 将小波变换引入到图像压缩领域中来，并提出了嵌入式零树小波编码方法(Embedded Zerotree Wavelet ，EZW)，取得了良好的压缩效果。1996年Pearlman W A 和Said A 在Shapiro 的EZW 算法的基础上，提出了SPIHT 算法[3]，解决了EZW 算法的一些缺点，但多级树集合分裂(Set Partitioning in Hierarchical Trees, SPIHT)算法依然需要大量计算和传输时间，对于在低速通道上图像的实时传送提出了挑战。 本文重点介绍了一种简单有效的方法结合霍夫曼编码实现进一步的压缩。实验结果显示压缩率为0.35978，相较于为量化前的0.21191有较大提升，说明这一方法可以节省大量的传输比特，进而增强压缩性能。
2、 SPIHT 算法 本质上来说SPIHT 使用了子波段编码以产生一个塔式结构，从而一个图像被功率互补的低通和高通滤波器连续地分解了，然后再抽取结果图像。那么整个图像分解成四个子带： LL ，LH ，HL 以及HH ，其中LL 为低频，LH 、HL 、HH 为分别为水平、垂直和对角线上的高频分量。三层分解的小波变换小波系数的树结构如图1。在每个子带中，用一个小方格表示一个小波系数。为简洁阐述，用,,m d
i j C 表示第m 层、在d 方向的子带内的一个系数，i 、j 是本子带内的下标，m HL ，m LH ，m HH 子带的方向序号d 依次分别取一、二、三。低分辨层的一个系数同它的同一方向高一级的分辨层的四个系数，还有更高两级分辨层的十六个系数，大体反映了同空域内相同方向子带的性质，并且这类系数间有着很强的相似性。因此，可将d 方向各子带中表示同位置的小波系数集合比喻为一颗方向树，最低分辨率（最高层的
子带）只取一个系数，可以作为树的根节点，每一高层子带的一个系数对应同方向第一层子带的四个系数为其子节点，依此类推。
图1 三层小波变换系数的树结构
在图1中，3HL 为该方向子带中最低分辨率子带，它的1个系数3,1
,i j C 为一颗方向树的根节点，它的子节点是2HL 子带内的0,1{2,2}p q i p j q ≤≤++共4个系数，它的孙节点是1HL 子带内的0,3{4,4}p q i p j q ≤≤++共十六个系数。这样，以3,1
,i j C 为根节点的一颗方向树包含了二十一个系数值，有二十个子孙。对于2m ≥层分解，m HL 子带内的一个根节点共有的子孙节
点个数为
11
44(41)3m
l
m l -==-∑ （1） 由根节点在最高层方向子带内一个系数为根的方向树也称为最大方向树，并记为
,(,)L d T i j ，它表示树上系数的合集。其他层的系数也可以为根，构成一颗子方向树，记为,(,)m d T i j 。
3、 SPIHT 算法特性
多级树集合分裂算法（SPIHT ）能够生成一个嵌入位流（embedded bit stream ），使接收的位流在任意点中断时，都能解压并重构图像，具有良好的渐进传输特性；算法的初始化过程、细化过程类似于EZW 算法，它改进了EZW 重要图的表示方法，也就是重要系数在表中的排序信息，使得集合的表示更为精简，从而提高了编码效率和图像压缩率。SPIHT 算法在不同的比特率下比EZW 算法的PSNR （峰值信噪比）都有所提高，具有计算复杂度低、位速率易控制的特点。如图2所示，这个金字塔状小波系数被按照重要程度排序，最重要的比特可以先传输，然后才是下一个位平面（bit plane ），依此类推，直到最低重要性的位平面到达。这种先进的传输方式可以有效地减小每个位平面均方误差失真。 比特行 位标记 s s s s s s s s s 最高位 5 1 1 0 0 0 0 0 0 0 4 1 1 0 0 0 0 0 3 1 1 1 0 0 2
LH 1 HL 2 HH 2 LH 2
HH 1
HL 1 HL 3
1 最低位
图2 比特平面顺序及传输图
为了能更好的利用不同层和频带系数之间的空间关系，SPIHT 编码算法使用式（2）来给
小波系数排序：
,(,)max 2m
n i j i j C τ∈≥ （2）
C 是第n 个位面的小波系数，它在,m i j τ像素子集的(i,j)位置，代表一个父节点及其子节点。如果重要性测试的结果为“yes ”，一个S 标记会被设置为1，这就表示该系数是重要的。如果测试结果为”no“，则S 标记会被置为0，表示该系数不重要。这一过程由式（3）来表示：
,(,)1,max
2()0,m
n i j i j n C S otherwise
ττ∈⎧≥⎪=⎨⎪⎩ （3） 在第N 个位平面不重要的小波系数可能在第N-1个或者更低位平面是重要的。 这些信
息会根据其重要性被组织成3个列表：LIP 不重要系数表、LIS 不重要子集表、LSP 重要系数表。
在解码器中，SPIHT 算法会复制相同的列表。该算法使用了一个基本原则，即任何排序算法的执行路径都是使用分支点的比较结果进行定义的。若编码器与解码器有同样的排序算法，则解码器会更容易恢复顺序信息。对编码器输入的系数分析比较，解码器通过执行同一路径就能获得排序信息。其算法流程如下：
1）初始化
将链表LSP 置空，把低频区域H 中的所有节点的坐标(i, j)放到链表LIP 中，并把H 中有后代的节点坐标(i, j)放入LIS 中，标记为A 类型集合：输出|}]),(max{|[
log 2
j i c n =。
2）分类过程一
对LIP 中的每一个节点坐标(i, j)，输出),(j i S n 。如果),(j i S n =1，则输c(i, j)的符号，并把它放至LSP 末端。
3）分类过程二
对链表LIS 中的每一个(i, j)：
（1）如果该集合属于A 类型集合，则输出)),((j i D S n 。如果)),((j i D S n =1，则：
（a ）对O(i, j)中的每一个节点(k, l)，输出),(l k S n 。如果),(l k S n =1，则输出该节点c(k, l)的符号。并把它移至LSP 末尾，否则将它移至LIP 末端。
（b ）删除该集合。若L(i, j)存在，把(i, j)移至LIS 的末端，并将该集合定义为B 类型集合。
（2）若此集合属于B 类型，则输出)),((j i L S n ，如果)),((j i L S n =1，那么删除此
集合，尔后将所有的(k, l)（其中),(),(j i O l k ∈）放到LIS 的末端，同时把这些集合统称为B 类型。 4）精确过程
针对LSP 链表内的任何一个(i, j)（在本次扫描中产生的(i, j)以外），输出c(i, j)的第n 位比特值。
5）循环过程
若n=0，过程终止；否则使n=n-1，并转到步骤2进行下一步执行。 4、结合Huffman 编码的SPIHT 算法
这里是具体的SPIHT 编码算法输出码流分析。接下来是SPIHT 编码的3层小波分解系数。
2[log max{(,)}]5n c i j ==，所以初始化的阈值是T0=25。对于T0来说输出二进制流为：
