论文部分内容阅读
摘要： 提出了一种基于现场可编程门阵列（FPGA）的高速9/7二维离散小波变换（2-D DWT）设计。在实现一维离散小波变换（1-D DWT）时采用多级流水线技术，并使用了改进的提升算法。同时，使用正则符号编码（CSD编码）和优化的移位加法操作实现乘法器，使其便于通过硬件实现，且加快了处理速度。在进行二维离散小波变换时采用改进的基于行的结构，只需完成3行行变换即可开始列变换，减少了系统资源的占用。设计通过MATLAB与ModelSim联合仿真，可以稳定运行在60 MHz时钟频率下，完全能够满足高速图像实时处理的要求。
关键词： 离散小波变换（DWT）； 提升算法； 现场可编程门阵列（FPGA）
引言
小波变换具有多分辨率分析特性和良好的时频特性，因而广泛应用于图像编码、模式识别、视频处理等领域[1]。
在实时的图像处理系统中，由于离散小波变换（DWT）需要的运算量较大，软件实现有时无法满足实时性要求，这使得人们对DWT的硬件实现产生了极大的兴趣。近年来，许多作者对硬件实现DWT进行了研究。文献[2]中提出了一种基于提升算法的直接映射结构。该结构简单明了，易于硬件实现，但关键路径延迟较高。文献[3]中提出了一种Mesh结构，可以行列变换同时进行，从而达到较高的处理速度，但需要消耗较多的硬件资源。本文采用模块化设计思想，在1-D DWT中使用改进的提升算法和多极流水线设计以提高系统运行速度，在2-D DWT中使用基于行的结构，以减少缓存器的使用。现场可编程门阵列（FPGA）具有设计周期短，灵活性好，集成程度高，处理速度快等特点[4]，被广泛应用在数字信号处理领域。因此，本文基于Altera公司的FPGA芯片进行设计，并用Quartus II、ModelSim等软件进行综合、仿真。
1基于提升算法的离散小波变换
1.1提升算法的基本原理基于提升算法的离散小波变换结构如图1所示，通常由一个分裂环节、一个预测环节和一个更新环节构成。
1.2改进提升算法
在流水线设计方法中，关键路径在两个寄存器之间的传播延迟中占主导地位。为了减少该延迟，使系统可以运行在更高的频率之下，提出了一种针对DWT的快速流水线结构[5]。由于在直接映射的硬件结构中，传播延迟主要存在于预测和更新步骤，本文将式（3）代入式（4）之中，将预测和更新合并成一个表达式。由此，可以使得流水线中的每一级只有一次加法或乘法。
s0i+（βd1i-1）+（βd1i）（9）在式（9）中，第一次提升步骤的低通信号s0i可以直接得到，而高通信号d1i则乘以了一个因子β。然后，将式（5）代入式（6），作为第二次提升步骤。
2基于FPGA的9/7小波变换的实现
本设计使用Verilog HDL语言实现，其系统结构如图2所示，其流程图如图3所示。
2.1地址产生模块地址产生模块的主要作用是对原始图像进行边界延扩。在用提升方法进行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）。在地址产生模块中，就是按如上顺序产生地址。
2.2行变换模块行变换模块即对图像的每一行分别进行DWT变换，即1-D DWT。DWT变换有两次提升变换，因为两次提升变换计算公式相似，本文对第一次提升变换进行研究。通过改进后的计算公式，第一次提升变换的数据流图如图4所示。根据该数据流图，本文构建了新的流水线结构，如图5所示。每级流水线通过虚线相隔，并将此定义为一个处理单元，其中包含了2个乘法器和4个加法器。一个完整的9/7小波变换结构包含两个处理单元。此外，需要2个额外的乘法器完成归一化步骤。从图5中可以看出，关键路径中两个寄存器之间只有1个乘法器或加法器，和传统直接映射结构的2个加法器加1个乘法器相比大为减少，因此可以工作在更高的时钟频率下。
在行变换模块中，使用到了乘法器，而由于传统乘法器消耗硬件资源多，且耗时较长，因此，可以改用移位加法来实现常数乘法。同时，采用正则符号编码（CSD编码）来表示滤波器的系数[7]，可以减少移位加法器的数量。各滤波器系数的CSD编码如表1所示。图6CSD乘法器结构图
Fig.6The CSD multiplier structure diagram如图6所示，以系数βα为例说明CSD编码实现乘法操作的方式。图6（a）为系数βα的CSD编码的直接表示，其中表示左移；为了减少硬件资源的消耗，可以对表达式中具有相似次数的乘积相进行组合相加，如2-3-2-5可以由x3-x5改写成（x1-x3）2。同时，可以引入流水线结构，以增加系统吞吐量，改进结构如图6（b）所示。
2.3列变换模块
因为图像都是二维的，所以在完成行变换后，还需要对图像的每一列进行DWT变换，即2-D DWT。目前，主要实现方法有两种：可分离与不可分离结构。可分离结构是指重复使用1-D DWT以实现2-D DWT；不可分离结构是指将图像分成几个子图像，对各个子图像同时进行行列DWT变换，但这种方法大为增加硬件消耗。图7列变换数据组织
Fig.7The column transform data organization本文选择第一种方法。对于可分离结构，最常见的是先进行行变换，待行变换完成后再进行列变换，这样做的好处是实现简单，但需要大量额外存储空间对行变换结果进行缓存。同时，因为行变换完成后才开始列变换，这会使系统产生延迟。因此，本文使用基于行的结构，即在行变换的同时进行列变换。因为得到一组DWT输出需要9个输入数据，所以在得到9行行变换结果后，才可以进行列变换。本文提出了一种改进方案，如图7所示，只需要完成3行行变换，即可开始列变换，从而极大地减少了存储器的消耗与系统的延迟。如图7所示，列变换模块的具体步骤为：在T2时刻，读取缓存器1中的计算上一组数据时得到的寄存器r3中的值。在T3时刻，将寄存器r3中的值存入缓存器1中以供下一组数据使用。在T5时刻，读取缓存器2中的计算上一组数据时得到的寄存器r9中的值。在T6时刻，将寄存器r9中的值存入到缓存器2中，同时，读取缓存器3中计算上一组数据时得到的寄存器r11中的值。在T7时刻，即可得到最终输出s2i，δd2i了；同时将寄存器r11中的值存入缓存器3中。本文中使用了3个缓存器，可以通过FPGA上的FIFO来实现。3系统仿真与验证本文采用ModelSim和MATLAB联合仿真进行验证，先编写testbench读取数据，并在ModelSim中仿真，最后将仿真结果送入MATLAB进行图像重构。其中，行变换模块的仿真波形如图8所示。图中ZHIA为输入数据，q为行变换结果。q经过25 h的潜伏期后开始输出有效值，将其与直接使用式（9）、式（10）计算输入数据所得结果进行比较，可发现两者相同。这表明了设计的正确性。 Fig.9The test results在MATLAB中将列变换模块处理后的数据进行重构，所得结果如图9所示。从图9（b）中可以看出，左上角低频分量包含了图像的主要信息，而右上角、左下角、右下角的高频水平、垂直、对角线分量则包含了原图在水平、垂直和对角线部分的边缘信息。经过试验，本设计可以稳定运行在60 MHz下，对800×600的图像来说，处理速度为125帧/s，完全可以达到高速图像处理的要求。本设计使用的LEs数为745，这对于当今拥有几千至上万LEs的FPGA来说，所消耗的资源是很少的。
4结论
本文设计了一种新的基于FPGA的高速9/7提升小波变换结构，通过使用流水线结构，改进提升算法，使用CSD乘法器，满足了系统高速运行的要求。在二维小波变换中，采用改进的基于行的变换方法，减少了存储空间的消耗及系统延迟。
参考文献：
[1]孔德照，沈学举，林超，等.基于分数小波变换的双随机相位光学图像加密技术[J].光学仪器，2013，35（4）：17-21.
[2]SILVA S V，BAMPI S.Area and throughput trade-offs in the design of pipelined discrete wavelet transform architectures[J].IEEE Design，Automation and Test in Europe，2005，3：32-37.
[3]朱斌杰，杜慧敏，杨晓强，等.二维9/7小波变换VLSI设计[J].电子设计工程，2009，17（2）：11-16.
[4]韩建，何学兰，魏运峰.基于FPGA的FIR数字滤波器算法的改进及仿真[J].光学仪器，2013，35（5）：56-59.
[5]WU B.F，LIN C.F.A rescheduling and fast pipeline VLSI architecture for lifting-based discrete wavelet transform[C].Proceedings of the 2003 International Symposium on Circuits and Systems，2003，2：732-735.
[6]钟广军，成礼智，陈火旺.基于提升方法的简单9/7小波滤波器[J].计算机工程与科学，2003，25（1）：35-55.
[7]熊承义，田金文，柳建.基于CSD编码的高速乘法器IP设计[J].计算机工程与应用，2003（31）：38-40.
关键词： 离散小波变换（DWT）； 提升算法； 现场可编程门阵列（FPGA）
引言
小波变换具有多分辨率分析特性和良好的时频特性，因而广泛应用于图像编码、模式识别、视频处理等领域[1]。
在实时的图像处理系统中，由于离散小波变换（DWT）需要的运算量较大，软件实现有时无法满足实时性要求，这使得人们对DWT的硬件实现产生了极大的兴趣。近年来，许多作者对硬件实现DWT进行了研究。文献[2]中提出了一种基于提升算法的直接映射结构。该结构简单明了，易于硬件实现，但关键路径延迟较高。文献[3]中提出了一种Mesh结构，可以行列变换同时进行，从而达到较高的处理速度，但需要消耗较多的硬件资源。本文采用模块化设计思想，在1-D DWT中使用改进的提升算法和多极流水线设计以提高系统运行速度，在2-D DWT中使用基于行的结构，以减少缓存器的使用。现场可编程门阵列（FPGA）具有设计周期短，灵活性好，集成程度高，处理速度快等特点[4]，被广泛应用在数字信号处理领域。因此，本文基于Altera公司的FPGA芯片进行设计，并用Quartus II、ModelSim等软件进行综合、仿真。
1基于提升算法的离散小波变换
1.1提升算法的基本原理基于提升算法的离散小波变换结构如图1所示，通常由一个分裂环节、一个预测环节和一个更新环节构成。
1.2改进提升算法
在流水线设计方法中，关键路径在两个寄存器之间的传播延迟中占主导地位。为了减少该延迟，使系统可以运行在更高的频率之下，提出了一种针对DWT的快速流水线结构[5]。由于在直接映射的硬件结构中，传播延迟主要存在于预测和更新步骤，本文将式（3）代入式（4）之中，将预测和更新合并成一个表达式。由此，可以使得流水线中的每一级只有一次加法或乘法。
s0i+（βd1i-1）+（βd1i）（9）在式（9）中，第一次提升步骤的低通信号s0i可以直接得到，而高通信号d1i则乘以了一个因子β。然后，将式（5）代入式（6），作为第二次提升步骤。
2基于FPGA的9/7小波变换的实现
本设计使用Verilog HDL语言实现，其系统结构如图2所示，其流程图如图3所示。
2.1地址产生模块地址产生模块的主要作用是对原始图像进行边界延扩。在用提升方法进行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）。在地址产生模块中，就是按如上顺序产生地址。
2.2行变换模块行变换模块即对图像的每一行分别进行DWT变换，即1-D DWT。DWT变换有两次提升变换，因为两次提升变换计算公式相似，本文对第一次提升变换进行研究。通过改进后的计算公式，第一次提升变换的数据流图如图4所示。根据该数据流图，本文构建了新的流水线结构，如图5所示。每级流水线通过虚线相隔，并将此定义为一个处理单元，其中包含了2个乘法器和4个加法器。一个完整的9/7小波变换结构包含两个处理单元。此外，需要2个额外的乘法器完成归一化步骤。从图5中可以看出，关键路径中两个寄存器之间只有1个乘法器或加法器，和传统直接映射结构的2个加法器加1个乘法器相比大为减少，因此可以工作在更高的时钟频率下。
在行变换模块中，使用到了乘法器，而由于传统乘法器消耗硬件资源多，且耗时较长，因此，可以改用移位加法来实现常数乘法。同时，采用正则符号编码（CSD编码）来表示滤波器的系数[7]，可以减少移位加法器的数量。各滤波器系数的CSD编码如表1所示。图6CSD乘法器结构图
Fig.6The CSD multiplier structure diagram如图6所示，以系数βα为例说明CSD编码实现乘法操作的方式。图6（a）为系数βα的CSD编码的直接表示，其中表示左移；为了减少硬件资源的消耗，可以对表达式中具有相似次数的乘积相进行组合相加，如2-3-2-5可以由x3-x5改写成（x1-x3）2。同时，可以引入流水线结构，以增加系统吞吐量，改进结构如图6（b）所示。
2.3列变换模块
因为图像都是二维的，所以在完成行变换后，还需要对图像的每一列进行DWT变换，即2-D DWT。目前，主要实现方法有两种：可分离与不可分离结构。可分离结构是指重复使用1-D DWT以实现2-D DWT；不可分离结构是指将图像分成几个子图像，对各个子图像同时进行行列DWT变换，但这种方法大为增加硬件消耗。图7列变换数据组织
Fig.7The column transform data organization本文选择第一种方法。对于可分离结构，最常见的是先进行行变换，待行变换完成后再进行列变换，这样做的好处是实现简单，但需要大量额外存储空间对行变换结果进行缓存。同时，因为行变换完成后才开始列变换，这会使系统产生延迟。因此，本文使用基于行的结构，即在行变换的同时进行列变换。因为得到一组DWT输出需要9个输入数据，所以在得到9行行变换结果后，才可以进行列变换。本文提出了一种改进方案，如图7所示，只需要完成3行行变换，即可开始列变换，从而极大地减少了存储器的消耗与系统的延迟。如图7所示，列变换模块的具体步骤为：在T2时刻，读取缓存器1中的计算上一组数据时得到的寄存器r3中的值。在T3时刻，将寄存器r3中的值存入缓存器1中以供下一组数据使用。在T5时刻，读取缓存器2中的计算上一组数据时得到的寄存器r9中的值。在T6时刻，将寄存器r9中的值存入到缓存器2中，同时，读取缓存器3中计算上一组数据时得到的寄存器r11中的值。在T7时刻，即可得到最终输出s2i，δd2i了；同时将寄存器r11中的值存入缓存器3中。本文中使用了3个缓存器，可以通过FPGA上的FIFO来实现。3系统仿真与验证本文采用ModelSim和MATLAB联合仿真进行验证，先编写testbench读取数据，并在ModelSim中仿真，最后将仿真结果送入MATLAB进行图像重构。其中，行变换模块的仿真波形如图8所示。图中ZHIA为输入数据，q为行变换结果。q经过25 h的潜伏期后开始输出有效值，将其与直接使用式（9）、式（10）计算输入数据所得结果进行比较，可发现两者相同。这表明了设计的正确性。 Fig.9The test results在MATLAB中将列变换模块处理后的数据进行重构，所得结果如图9所示。从图9（b）中可以看出，左上角低频分量包含了图像的主要信息，而右上角、左下角、右下角的高频水平、垂直、对角线分量则包含了原图在水平、垂直和对角线部分的边缘信息。经过试验，本设计可以稳定运行在60 MHz下，对800×600的图像来说，处理速度为125帧/s，完全可以达到高速图像处理的要求。本设计使用的LEs数为745，这对于当今拥有几千至上万LEs的FPGA来说，所消耗的资源是很少的。
4结论
本文设计了一种新的基于FPGA的高速9/7提升小波变换结构，通过使用流水线结构，改进提升算法，使用CSD乘法器，满足了系统高速运行的要求。在二维小波变换中，采用改进的基于行的变换方法，减少了存储空间的消耗及系统延迟。
参考文献：
[1]孔德照，沈学举，林超，等.基于分数小波变换的双随机相位光学图像加密技术[J].光学仪器，2013，35（4）：17-21.
[2]SILVA S V，BAMPI S.Area and throughput trade-offs in the design of pipelined discrete wavelet transform architectures[J].IEEE Design，Automation and Test in Europe，2005，3：32-37.
[3]朱斌杰，杜慧敏，杨晓强，等.二维9/7小波变换VLSI设计[J].电子设计工程，2009，17（2）：11-16.
[4]韩建，何学兰，魏运峰.基于FPGA的FIR数字滤波器算法的改进及仿真[J].光学仪器，2013，35（5）：56-59.
[5]WU B.F，LIN C.F.A rescheduling and fast pipeline VLSI architecture for lifting-based discrete wavelet transform[C].Proceedings of the 2003 International Symposium on Circuits and Systems，2003，2：732-735.
[6]钟广军，成礼智，陈火旺.基于提升方法的简单9/7小波滤波器[J].计算机工程与科学，2003，25（1）：35-55.
[7]熊承义，田金文，柳建.基于CSD编码的高速乘法器IP设计[J].计算机工程与应用，2003（31）：38-40.