基于FPGA的提升小波变换联合SPIHT编解码方法*

赵柏山，徐 丽，张 帆

（沈阳工业大学，辽宁 沈阳 110870）

0 引 言

随着科学技术的日益发展，图像分辨率提高，图像的数据量逐渐增加，对图像压缩技术的要求也越来越高。近年来，离散小波变换（DWT）已经广泛应用于图像压缩领域，具有良好的自适应时频窗口特性和多分辨率分析特性。Sweldens提出小波变换的提升算法[1]（Lifting Scheme），结构简单、运算量小、所需内存少、易于硬件实现，且能实现整数小波变换，成为目前小波变换的常用算法。

小波变换将图片分解成高频和低频部分。低频部分还可以继续分解，再分别对高频和低频进行编码。小波变换压缩的核心是编码。1993年，Sharpio M Jerome提出了嵌入式零数小波编码算法（EZW）[2]。1996年，said A和 Pearlman W A在EZW算法的基础上提出了SPIHT算法，得到了更好的压缩性能[3]。

本文基于FPGA实现了提升9/7小波变换结合SPIHT编码的图片压缩解压系统，将小波变换和SPIHT算法进行改进，进一步处理高频系数，去除冗余，提高了压缩率。

1 系统总体设计

本设计采用三级9/7提升小波变换SPIHT算法进行实现。压缩编码方案主要包括提升小波变换和SPIHT编码两部分，而数据解压过程就是压缩的逆过程。具体流程如图1所示。

图1 压缩系统流程

FPGA中实现的过程采用流水线结构。使用流水线技术，可以将复杂的操作分步执行，提高系统的并行度，减小每个部分的处理时间，加快系统的处理速度。流水线设计的代价是增加了寄存器逻辑，即增加了芯片资源的耗用。

2 9/7提升小波变换

2.1 提升小波变换

小波变换在图像压缩方面的性能较好，应用广泛。传统的离散小波变换基于卷积进行运算，计算量大，处理速度慢[4]，且对存储的要求高。提升小波变换有效解决了这个问题，不仅计算量小、复杂度低，而且得到的结果与传统的离散小波相同，更易于硬件实现[5]。

提升小波算法由三步基本运算构成：分裂、预测和更新，如图2所示。

图2 提升小波算法

第一步，分裂。把原始离散采样通过间隔抽取采样分裂成奇数采样0和偶数采样。

第二步，预测。分裂后的两组数据具有很大的相关性，需要利用预测来消除分裂后的冗余，即用偶数样本采用插值细分的方法预测奇数样本。奇数样本与测值之差为细节系数：

其中P为预测算子。

第三步，更新。用更新的奇数样本更新偶数样本：

其中U为更新算子。

2.2 9/7小波变换的提升算法

9/7小波在图像压缩方面的性能比较优异。因此，本设计采用的小波为9/7小波。在提升结构中，9/7小波具有两个提升步，结构如图3所示。

图3 9/7小波变换结构

图3 中，P1和P2是预测步的运算，U1和U2是更新步的运算：

图3中的α、β、γ、δ、K1、K2均为滤波器参数，值为：

将预测步和更新步的运算式应用到图3，可得9/7小波的分步骤计算公式。

第一步：分裂，即：

第二步：第一次预测，即：

第三步：第一次更新，即：

第四步：第二次预测，即：

第五步：第二次更新，即：

第六步：伸缩，即：

2.3 9/7提升小波的改进

一维9/7提升小波在FPGA中实现的结构流程，如图4所示。

图4 9/7提升小波的FPGA结构

一个9/7提升小波滤波器由两个提升步级联实现。每个提升步由预测步和更新步组成。图4中，（1）和（3）是预测步，（2）和（4）是更新步。

小波变换的每一级都是将待变换部分的图像分量分别进行变换和列变换，分解成LL、HL、LH、HH四个子带，分别代表低频分量和水平、垂直、对角线方向的高频分量。图像的大部分能量集中到LL分量。下一级小波分解是把上一级的LL子带再进行分解产生四个子带，三级9/7整数小波变换将图像分为10个子带。

小波变换的行变换和列变换结构完全一样，只是输入数据不同，通过控制地址变量控制输入行和列的数据。因此，二维小波变换可以拆分为两个一维小波变换，三级二维小波变换就相当于六个一维的小波变换。本设计FPGA的流水线结构，进一步提高了小波变换的压缩速度。

三级的二维图像提升小波变换依次以第一级行变换、第一级列变换、第二级行变换、第二级列变换、第三级行变换、第三级列变换的顺序进行。图5为FPGA中三级小波变换处理数据顺序的结构。

图5 三级小波编码的顺序结构

3 SPIHT编码

3.1 SPIHT传统算法

SPIHT（Set Partitioning in Hierarchical Trees）算法是分级树的集合划分算法，是对嵌入式零树编码（Embedded Zero-tree Wavelet，EZW）算法的改进和扩展[6]。它继承了EZW算法的思想，通过方向树最有效地表示重要系数，并通过对树的划分将尽可能多的非重要系数汇集在一个子集中，用一个单位符号表示[7]。

SPIHT算法是一种很好的渐进传输编码方法。SPIHT算法可以在任意点停止编码，能够满足特定压缩率和失真度的要求；也可以随时解码，在图像解码的任意时刻，所显示的图像质量都是当时解码器输入位数所能获得的最佳数据。

SPIHT算法中采用三个链表保存编码信息：保存重要系数坐标的链表LSP（List of Insignificant Pixels）；保存不重要系数坐标的链表LIP（List of Significant Pixels）；保存不重要系数集合坐标的链表 LIS（List of Insignificant Sets）。

算法中还定义了几个集合，对于任意的节点(i,j)都有：

O(i, j)：节点(i, j)的直接后代；

D(i, j)：节点(i, j)的所有后代；

L(i, j)节点(i, j)的除了直接后代的所有后代，即L(i, j)=D(i, j)-O(i, j)。

SPIHT算法的基本运算是判断一个集合是否重要，即一个集合中所有系数都是重要系数。定义：Sn(T)为T是否重要的标志位：

其中Xi,j表示节点(i, j)的值。集合中如果只包含一个节点，即T={(i, j)}时，简写为Sn(i, j)。

SPIHT编码的流程图如图6所示。

SPIHT算法编码主要分为以下四个步骤。

（1）初始化：将LSP置为空集；将时间方向树的根节点的序号放入LIP，将除最低频子带以外的根节点的序号放入LIS，同时标以A类。设置初始阈值为2n。

（2）排序扫描：应用集合分裂排序规则将小波变换后的系数序号分别送入LIP、LIS和LSP中。

对LIP中的所有节点(i, j)输出Sn(i, j)，若Sn(i,j)=1，则将节点(i, j)移到LSP中，并输出C(i, j)的符号；

对LIS中的所有节点(i, j)：

①如果节点属于A类，则输出Sn(D(i, j))。如果Sn(D(i, j))=1，则对O(i, j)中所有节点(k, l)输出Sn(k, l)；如果Sn(k, l)=1，则将节点(k, l)加入到LSP中并输出X(k, l)的符号；如果L(k, l)非空，则将节点(i, j)移到LIS的尾部，并标记为B类；否则，将节点移出LIS；

②如果该节点属于B类，则输出Sn(L(i, j))。如果Sn(L(i, j))，则将O(i, j)以A类型加入到LIS，并将节点(i, j)移出LIS；

（3）精细扫描：输出LSP所表示的小波系数的最重要的第n位比特值。

（4）更新阈值指数：将阈值指数n减至n-1，返回步骤（2）进行下一级编码扫描。

解码过程中，SPIHT解码器和编码器的扫描工作相同，不同的是根据输入的码流来恢复小波系数表。在同一时刻，解码器的三个链表与编码器的三个链表是相同的，即解码器是根据编码时的搜索路径恢复数据序列的。解码器的每次迭代都更新阈值，在排序扫描和精细扫描过程中改善系数矩阵，从而改善图像质量，等效地减少了失真。

图6 SPIHT编码实现结构

3.2 SPIHT的改进

小波变换后，在SPIHT编码时，当阈值进行判决后，会存在大量无效系数，从而使各个链表的体积呈级数级增加。在链表插入环节进行改进，对高频系数做位宽截取处理。因为小波系数是按照重要程度排序，最重要的比特先输出，所以保留高位数据，舍弃最不重要的低位数据，进一步去除冗余。这个步骤可以表示为：

例如，在FPGA中的二进制处理过程中，有一个不重要系数是32'h0000_0045，进行截位处理，保留高16位，那么该系数就变为0，不参与编码，从而提高了编码效率。

4 实验结果

采用512×512的Lena图，将改进后的压缩算法用MATLAB编写程序，用软件仿真图像的压缩过程，并对压缩以后的码流解压，以验证压缩算法，同时为硬件仿真提供参照依据。然后，利用VerilogHDL编程，在Quartus II中进行验证。图7为FPGA在压缩率0.5的情况下进行压缩，解压后数据用MATLAB恢复的图像与原图像的对比。

图7 压缩前后图像对比

Modelsim的时序仿真图，如图8所示。

本设计将不同压缩率下改进前和改进后的压缩数据进行对比。在原算法压缩率为0.75的情况下，改进后的字符数为177 505，压缩率为0.677 12；原算法压缩率为0.5的情况下，改进后的字符数为114 135，压缩率为0.435 39；原算法压缩率为0.25的情况下，改进后的字符数为56 606，压缩率为0.213 6。表1为改进前后压缩率与PSNR（峰值信噪比）的对比结果。

图8 时序仿真图

表1 改进前后数据对比表

从表1得出的结果可以看出，本设计采用的提升9/7小波变换结合SPIHT改进算法的图像压缩方案切实可行，获得了较改进前高的压缩率，且PSNR没有明显的差异。

5 结 语

基于小波变换和传统SPIHT算法编解码原理，利用FPGA，对传统算法进行改进：将二维提升小波变换改为一维，提高了并行度，减小了运行速度；在SPIHT算法中对不重要的高频系数进行截位处理，提高了SPIHT的编码效率。实验结果表明，与传统SPIHT算法相比，改进系统所得的数据压缩率更高，更易于硬件实现。

[1] Sweldens W.The Lifting Scheme:A Construction of Second Generation Wavelets[J].Journal of Appl. and Comput Harmonic Analysis,1997,29(02):511-546.

[2] Shapiro J M.Embedded Image Coding Using Zerotrees of Wavelet Coefficients[J].IEEE Trans. Signal Processi ng,1993,41(12):3445-3462.

[3] Said A,Pearlman W A.A New,Fast,and Efficient Image Code Based on Set Partitioning in Hierarchical Trees[J].IEEE Trans. Circuits Syst.& Video Technol.,1996,6(03):243-249.

[4] 王纲毅.基于提升机构的二维离散小波的FPGA设计[D].武汉:华中科技大学,2005.WANG Gang-yi.FPGA Design of Two-Dimensional DWT Based on the Lifting Scheme[D].Wuhan:Huazhong University of Science and Technology,2015.

[5] 王鸣哲.星载图像压缩系统中高速小波变换的FPGA设计与实现[D].合肥:中国科学院大学,2017 WANG Ming-zhe.FPGA Design and Implementation of High Speed Discrete Wavelet Transform in Space Image Compression System[D].Hefei:The University of Chinese Academy of Sciences,2017.

[6] 王骥.基于SPIHT算法的图像压缩卡的研制[D].哈尔滨:哈尔滨工业大学,2007.WANG Ji.Design of Image Compression Card Based on SPIHT Algorithm[D].Harbin:Harbin Institute of Technology,2007.

[7] 李玲远,詹翠丽,黄林.基于9-7提升小波的SPIHT编码算法[J].通信技术,2008,41(02):83-85.LI Ling-yuan,ZHAN Cui-li,HUANG Lin.SPIHT Algorithm Based on 9-7 Lifting Wavelet[J].Communications Technology,2008,41(02):83-85.