一种高效二维小波分解算法的FPGA实现

张传雨，杨梦达

（1.哈尔滨工业大学 电气工程系，黑龙江 哈尔滨150001；2.清华大学 交叉信息研究院，北京100084）

在对数字图像进行多分辨率观察和处理时，离散小波变换（DWT）是首选的数学工具。小波提升算法[1]作为小波变换的快速实现方法，使滤波过程被分解为几个提升步骤，运算量大为减少，便于实现即位计算，同时节省了存储空间，非常适合进行硬件实现。

目前普遍应用的实现二维提升小波变换的硬件架构包括基于帧的硬件架构和基于行的硬件架构[2]。随着大量相关研究工作[3-5]的不断进行，新的VLSI架构不断产生，电路整体性能逐渐提高，但在降低电路控制复杂度和对存储空间的耗费的兼顾上仍存在不足。本文提出一种直接二维提升小波变换VLSI架构，可有效降低控制电路的复杂度，明显地节省片上存储空间，使得设计的电路具有较好的综合性能。

1 小波提升算法

1.1 提升小波变换

通过提升框架实现小波变换分为三个步骤：分裂、预测和更新[3]。离散情况下，给定输入的离散信号数据集pk(pk代表序列p中的第k个数)，并将其分为奇数集合和偶数集合，经过完整提升步骤后，分解成数据集sk和dk。其中sk表示尺度系数，dk表示小波系数。以Le Gall 5/3小波为例，1-D整数小波变换分解步骤如图1所示。

常用的5/3整数小波变换计算公式如下：

式中，pk为原图像素数据，dk为变换结果高频成分，sk为变换结果低频成分。

完成二维变换过程如下：图像在经过一次行变换后就分成2个子带(sub-band)；再经过一次列变换后，2个子带就变成了4个子带，每个子带的大小变为原图1/4；要进行下一级小波变换，只要对LL子带以同样先行后列变换的方法处理即可。二级小波变换的原理的示意图如图2所示。

由于列变换是沿着列的方向进行，需要把行变换的结果逐列输入，因此通常需要先对图像进行行变换，存储行变换结果，再进行列变换。因此，需要存储大量的中间结果，增加了硬件的开销，限制了芯片的数据处理速度。

1.2 二维变换公式的进一步推导

为设计出性能更好的二维变换VLSI架构，将式(2)代入式(1)进行合并：

为实现对一幅图片二维变换处理，对公式进行进一步推导，设图片中第i行、第j列数据为pi，j，在进行行变换后得出结果，再将公式应用于竖直方向进行列变换，以两次低通滤波结果为例，得到如下结果：

将其乘法系数写成行列式，如图3(a)所示。

图3 二维变换乘法系数阵列

同理，为获得先高通后低通滤波结果HL、先低通后高通滤波结果LH及两次高通滤波结果HH数据，可将式(1)和式(3)通过同样的方式应用于二维变换。以行列式方式表达，如图 3(b)、(c)、(d)所示。

2 架构设计

2.1 整体架构

对于2-D DWT，本文以图3推导出的公式为基础，设计直接进行二维变换的提升小波变换实现方式。系统结构框图如图4所示。图像数据从外部存储器中读出，经地址拓展单元进行边界延拓后，写入缓冲单元；之后将数据送入二维DWT处理模块，产生4个子带数据，进行降2采样后，结果数据送至VGA显示器进行显示输出。系统控制模块产生各种控制信号约束系统各部分在特定的时序下工作。

2.2 内部结构

在进行数字图像的二维小波分解过程中，二维变换处理器是核心，它将影响整个系统的时序设计和综合性能。

通过图3中给出的参数行列式可以得出结论，二维变换过程实际上是一个5×5的采样窗口中数据的加权求和，其包含的运算主要为乘法运算和加法运算。

根据图3中行列式参数二维变换设计处理器具体结构，如图5所示。

该结构包含15个加法器、18个移位器和34个延迟单元(D)，不再需要额外的乘法器。可以估计，该一维5/3小波变换架构在FPGA中的实现需要占用逻辑单元数量约为40A(A为原始数据位宽)。完成一幅大小为N×N的图像的L级分解所需时钟周期数为：

其中，W为除去延时，处理器进行实际运算产生有效数据所需时钟周期个数；Ld为行变换和列变换之间的延迟。Ld=0，即在此过程中行列变换同时完成，不会产生中间数据，节省了大量片上存储空间，消除了行列变换的延时。另外，外部存储器读取次数有所增加，但处理器工作时间明显缩短，大大降低了系统总功耗。

3 实验结果和分析

为对本设计中的二维小波变换架构进行功能验证并直观地观察进行小波分解后的图像效果，通过ModelSim软件对处理器模块进行了仿真，如图6所示。

表1分别就所需的硬件复杂度、存储空间占用量、延迟时间以及控制电路的复杂度等方面的性能给出本文设计架构与现存其他二维DWT架构的对比情况。

本文以Le Gall 5/3小波为例，提出了一种直接二维提升小波变换VLSI架构。作为基于行的变换架构的一种改进，该架构具有结构简单、节省片上存储空间、灵活性高等优点，为硬件电路实现二维提升小波变换提出了新的思路。纯计算逻辑下，其处理速度可达到157.78 MHz。

为对文中提出的架构进行功能验证，采用Cyclone II系列 FPGA-EP2C35F672C6搭建其硬件电路。通过实验证实能较好地完成预定的设计功能。

表1 5/3小波二维离散小波变换架构性能比较

[1]SWELDENS W.The lifting scheme：a custom-design construction of biothogonal wavelets[J].Data Compression Conference，1996，3(2)：186-200.

[2]CHRYSAFIS C，ORTEGA A.Line based，reduced memory，wavelet image comperssion[C].IEEE Trans.on Image Processing，Washington，DC，USA，1998：398-407.

[3]ANDRA K，CHAKRABARTI C，ACHARYA T.A VLSI architecture for lifting-based forward and inverse wavelet transform[J].IEEE Trans.Signal Process.，2002，50(4)：966-977.

[4]LIAO H，MANDAL M K，COCKBURN B F.Efficient architectures for 1-D and 2-D lifting-based wavelet transforms[J].IEEE Trans.Signal Process.，2004，52(5)：1315-1326.

[5]BARUA S，CARLETTA J E，KOTTERI K A.An efficient architecture for lifting-based two-dimensional discrete wavelet transform，Integr[J].VLSI J.，2005，38(3)：341-352.

[6]MAAMOUN M，BRADAI R，MERAGHNI A，et al.Low cost VLSI discrete wavelet transform and FIR filters architectures for very high-speed signal and image processing[C].IEEE 9th International Conference on Cybernetic Intelligent Systems，2010：1-6.