小波变换具有多分辨率分析特性和良好的时频特性,因而广泛应用于图像编码、模式识别、视频处理等领域^[1]。在实时的图像处理系统中,由于离散小波变换(DWT)需要的运算量较大,软件实现有时无法满足实时性要求,这使得人们对DWT的硬件实现产生了极大的兴趣。近年来,许多作者对硬件实现DWT进行了研究。文献^[2]中提出了一种基于提升算法的直接映射结构。该结构简单明了,易于硬件实现,但关键路径延迟较高。文献^[3]中提出了一种Mesh结构,可以行列变换同时进行,从而达到较高的处理速度,但需要消耗较多的硬件资源。

本文采用模块化设计思想,在1-D DWT中使用改进的提升算法和多极流水线设计以提高系统运行速度,在2-D DWT中使用基于行的结构,以减少缓存器的使用。现场可编程门阵列(FPGA)具有设计周期短,灵活性好,集成程度高,处理速度快等特点^[4],被广泛应用在数字信号处理领域。因此,本文基于Altera公司的FPGA芯片进行设计,并用Quartus II、ModelSim等软件进行综合、仿真。

基于提升算法的离散小波变换结构如图 1所示,通常由一个分裂环节、一个预测环节和一个更新环节构成。

图 1

Fig. 1

图 1 提升小波变换和反变换示意图 Fig. 1 The lifting wavelet transform and inverse transform diagram

从图 1中还可看出,提升变换和提升反变换的结构对称、运算符号相反,因此提升变换可以实现完全重构,是一种可逆变换。

9/7小波的提升步骤:首先,将输入序列x_i分裂成奇偶两个部分s⁰_i和d⁰_i(i=0,1,2，…)

之后,两分裂序列各自进行提升步骤,得到输出sⁿ_i、dⁿ_i(n=1,2)

最后,通过归一化因子k,可以得到低通及高通小波系数s_i、d_i

在流水线设计方法中,关键路径在两个寄存器之间的传播延迟中占主导地位。为了减少该延迟,使系统可以运行在更高的频率之下,提出了一种针对DWT的快速流水线结构^[5]。

由于在直接映射的硬件结构中,传播延迟主要存在于预测和更新步骤,本文将式(3)代入式(4)之中,将预测和更新合并成一个表达式。由此,可以使得流水线中的每一级只有一次加法或乘法。

第一次提升步骤公式可以写成:

在式(9)中,第一次提升步骤的低通信号s⁰_i可以直接得到,而高通信号d¹_i则乘以了一个因子β。然后,将式(5)代入式(6),作为第二次提升步骤。其表达式如下:

最后,归一化步骤可以表示为:

依据修改后的提升算法,提升算法的6个9/7滤波器系数为β,βα,δ/β,δγ,-k/δ,1/k。由于原始的滤波器系数都是无理数,计算复杂,文献^[6]提出了一组新的滤波器系数:

这组系数只需要很少的浮点数计算,极大地方便了硬件实现。将其运用于本文设计之中,如表 1所示。

表 1(Table 1">Table 1)

表 1 DWT系数 Tab. 1 DWT coefficient 系数 系数值 二进制补码 CSD编码 β -0.062 5 1111.1111 －2－4 βα 0.093 75 0000.00011 2－3－2－5 δ/β -7.5 1111.1 －23+2－1 δγ 0.375 0000.011 2－1－2－3 -k/δ -2.413 59 1101.10010111 －21－2－1+2－3－2－5－2－8 1/k 0.883 88 0000.11100010 20－2－3+2－7

表 1 DWT系数 Tab. 1 DWT coefficient

本设计使用Verilog HDL语言实现,其系统结构如图 2所示,其流程图如图 3所示。

图 2

Fig. 2

图 2 系统结构图 Fig. 2 The system structure diagram

图 3

Fig. 3

图 3 系统流程图 Fig. 3 The system flow chart

地址产生模块的主要作用是对原始图像进行边界延扩。在用提升方法进行DWT时,是要求输入信号无限长的,但图像都是有边界的,也就是说图像信号是有限的,因此,就需要解决边界问题。本文选用对称延扩法,以信号端点为对称轴,进行边界延扩。以一组8点数据x(0)、x(1)、x(2)、x(3)、x(4)、x(5)、x(6)、x(7)为例,在最后一个高频系数x(7)右边界延扩倒数第二个数据x(6);在低频小波系数x(0)左边延扩第三、二个数据x(2)、x(1),使序列变成x(2)、x(1)、x(0)、x(1)、x(2)、x(3)、x(4)、x(5)、x(6)、x(7)、x(6)。在地址产生模块中,就是按如上顺序产生地址。

行变换模块即对图像的每一行分别进行DWT变换,即1-D DWT。DWT变换有两次提升变换,因为两次提升变换计算公式相似,本文对第一次提升变换进行研究。通过改进后的计算公式,第一次提升变换的数据流图如图 4所示。根据该数据流图,本文构建了新的流水线结构,如图 5所示。每级流水线通过虚线相隔,并将此定义为一个处理单元,其中包含了2个乘法器和4个加法器。一个完整的9/7小波变换结构包含两个处理单元。此外,需要2个额外的乘法器完成归一化步骤。

从图 5中可以看出,关键路径中两个寄存器之间只有1个乘法器或加法器,和传统直接映射结构的2个加法器加1个乘法器相比大为减少,因此可以工作在更高的时钟频率下。

图 4

Fig. 4

图 4 流水线结构的数据流图 Fig. 4 Pipeline structure of the data flow diagram

根据图 5,可利用Verilog HDL语言编写行变换模块,其关键代码如下所示:

图 5

Fig. 5

图 5 处理单元 Fig. 5 The processing unit

在行变换模块中,使用到了乘法器,而由于传统乘法器消耗硬件资源多,且耗时较长,因此,可以改用移位加法来实现常数乘法。同时,采用正则符号编码(CSD编码)来表示滤波器的系数^[7],可以减少移位加法器的数量。各滤波器系数的CSD编码如表 1所示。

如图 6所示,以系数βα为例说明CSD编码实现乘法操作的方式。图 6(a)为系数βα的CSD编码的直接表示,其中 表示左移;为了减少硬件资源的消耗,可以对表达式中具有相似次数的乘积相进行组合相加,如2^－3－2^－5可以由x 3-x 5改写成(x 1-x 3) 2。同时,可以引入流水线结构,以增加系统吞吐量,改进结构如图 6(b)所示。

图 6

Fig. 6

图 6 CSD乘法器结构图 Fig. 6 The CSD multiplier structure diagram

因为图像都是二维的,所以在完成行变换后,还需要对图像的每一列进行DWT变换,即2-D DWT。目前,主要实现方法有两种:可分离与不可分离结构。可分离结构是指重复使用1-D DWT以实现2-D DWT;不可分离结构是指将图像分成几个子图像,对各个子图像同时进行行列DWT变换,但这种方法大为增加硬件消耗。

本文选择第一种方法。对于可分离结构,最常见的是先进行行变换,待行变换完成后再进行列变换,这样做的好处是实现简单,但需要大量额外存储空间对行变换结果进行缓存。同时,因为行变换完成后才开始列变换,这会使系统产生延迟。因此,本文使用基于行的结构,即在行变换的同时进行列变换。因为得到一组DWT输出需要9个输入数据,所以在得到9行行变换结果后,才可以进行列变换。本文提出了一种改进方案,如图 7所示,只需要完成3行行变换,即可开始列变换,从而极大地减少了存储器的消耗与系统的延迟。

图 7

Fig. 7

图 7 列变换数据组织 Fig. 7 The column transform data organization

如图 7所示,列变换模块的具体步骤为:在T2时刻,读取缓存器1中的计算上一组数据时得到的寄存器r3中的值。在T3时刻,将寄存器r3中的值存入缓存器1中以供下一组数据使用。在T5时刻,读取缓存器2中的计算上一组数据时得到的寄存器r9中的值。在T6时刻,将寄存器r9中的值存入到缓存器2中,同时,读取缓存器3中计算上一组数据时得到的寄存器r11中的值。在T7时刻,即可得到最终输出s²_i,δd²_i了;同时将寄存器r11中的值存入缓存器3中。本文中使用了3个缓存器,可以通过FPGA上的FIFO来实现。

本文采用ModelSim和MATLAB联合仿真进行验证,先编写testbench读取数据,并在ModelSim中仿真,最后将仿真结果送入MATLAB进行图像重构。其中,行变换模块的仿真波形如图 8所示。图中ZHIA为输入数据,q为行变换结果。q经过25 h的潜伏期后开始输出有效值,将其与直接使用式(9)、式(10)计算输入数据所得结果进行比较,可发现两者相同。这表明了设计的正确性。

图 8

Fig. 8

图 8 仿真波形图 Fig. 8 Simulation waveforms

在MATLAB中将列变换模块处理后的数据进行重构,所得结果如图 9所示。从图 9(b)中可以看出,左上角低频分量包含了图像的主要信息,而右上角、左下角、右下角的高频水平、垂直、对角线分量则包含了原图在水平、垂直和对角线部分的边缘信息。

图 9

Fig. 9

图 9 试验结果 Fig. 9 The test results

经过试验,本设计可以稳定运行在60 MHz下,对800×600的图像来说,处理速度为125帧/s,完全可以达到高速图像处理的要求。本设计使用的LEs数为745,这对于当今拥有几千至上万LEs的FPGA来说,所消耗的资源是很少的。

本文设计了一种新的基于FPGA的高速9/7提升小波变换结构,通过使用流水线结构,改进提升算法,使用CSD乘法器,满足了系统高速运行的要求。在二维小波变换中,采用改进的基于行的变换方法,减少了存储空间的消耗及系统延迟。