一种高效存储多级二维9/7离散小波变换结构

王鑫, 高家明, 梁煜, 张为

(1.公安部天津消防研究所, 300381, 天津; 2.天津大学微电子学院, 300072, 天津)

JPEG2000是一种在图像压缩领域广泛应用的新型图像压缩标准。二维离散小波变换(discrete wavelet transform,DWT)由于其良好的时频局部化性能[1]成为JEPG2000压缩的核心技术之一。二维DWT将图像信息分解为多级高频分量与低频分量,为优化截断嵌入式块编码(embedded block coding with optimized truncation,EBCOT)提供原始数据。EBCOT中位平面编码模块以码块形式读取小波系数并将其处理为上下文信息,之后经熵编码和率失真截断编码形成压缩码流。由于算法计算量较大,为满足高速处理要求,高效的硬件DWT设计优化逐渐成为研究热点。

对于单级9/7 DWT硬件实现,文献[2]提出了一种横向Z型扫描的双输入/双输出结构,其关键路径为一个乘法器延时,但是该结构由于并行度较低导致整体处理时间较长,难以满足高速需求。文献[3]对输入数据进行重排,通过翻转结构进行模块设计降低了图像整体处理时间,然而其内部数据缓存较高同时控制逻辑较为复杂。Hu和Jong在文献[4]中引入基于纵向扫描的并行结构,提高了系统的处理速度,但是该结构需要整张图像存储完成后才能开始处理数据,故存储需求较大。文献[5]中采用流水线并引入正则乘法结构降低关键路径为一个加法器延时,不过其结构中的系数精度较低运算误差较大,难以满足应用要求。文献[6]采用了高系数精度的无乘法器结构以降低数据误差,并消除了片外存储资源消耗,但是该结构并行度同样较低,因此整体处理时间较长不利于高速数据处理应用环境。

对于多级结构优化,文献[7]提出一种通过并行度调整消除级间存储的多级结构,但关键路径延时仍旧较大。文献[8]通过高并行度减低存储面积,同时减低关键路径为一个乘法器延时,不过该结构基于卷积算法进行设计运算复杂度较高。文献[9]通过引入重复扫描的方式设计了新型高并行结构,消除了第一级变换模块内的级内变换缓存,但是该结构运算资源较高且级间处理较为复杂。Lai和Chung提出了一种码块优化的扫描方式[10],生成的多级小波系数可由并行EBCOT直接处理,降低了模块间的存储。然而,该方法由于采用了折叠多级结构,导致模块内暂存极大,同时结构中码块边界的近似处理也降低了压缩质量。文献[11]也基于块扫描对扫描方式进行优化以消除模块间缓存,然而级间缓存过大仍然严重制约了系统性能。

本文通过对已有结构的分析,设计了一种应用于JPEG2000硬件实现的新型高效存储的非折叠多级二维9/7 DWT结构,通过对扫描方式的改进、数据并行度的调整以及模块内数据传递的优化,极大的减少了系统面积,提升了硬件效率。

1　基本模块设计

1.1　优化提升算法

文献[12]根据已有9/7 DWT提升算法,通过一系列变换提出的优化提升算法公式如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

SH=KH(2n+1)

(9)

(10)

式中:D1(n)～D4(n)为4个中间变量;H(2n+1)为归一化前的高频小波系数;L(2n)为归一化前的低频小波系数;x(n)代表原始输入像素值;n为像素点坐标;SH和SL代表变换最终产生的高频小波系数和低频小波系数;α、β、γ、δ和K为变换系数。对于二维变换,数据经过行列变换处理后最终得到4个小波系数即低频-低频系数SLL、高频-低频系数SHL、低频-高频系数SLH和高频-高频系数SHH。

1.2　基本处理单元

列变换模块与行变换模块均采用双输入/双输出流水线结构,两个模块的关键路径延时均为一个乘法器延时,其中列变换模块结构如图1所示。

图1　列变换模块结构

本文设计的数据基本输入方式为横向并行双输入,列变换模块需要对中间变量D1～D4进行存储,对于大小为N×N的输入图像,所需的存储空间为4N。图1中RAM1、RAM2、RAM3、RAM4分别存储中间值D1、D2、D3、D4。当设计并行结构时,4个中间值可由该级的上一个并行模块提供,只需要在并行结构的首尾模块与RAM中进行中间值数据读写。列变换与行变换模块的内部结构一致,对于行变换模块而言,横向并行输入的数据为连续数据,因此每个中间值只需要2个数据暂存即可满足数据缓存需求。

由列变换模块输出的低频与高频系数需要经过转置后进入行变换模块进行处理,该转置模块结构如图2所示。由于列变换与行变换均为双输入双输出结构,且扫描方式为横向并行,因而需3个寄存器即可对列变换输出数据进行转置,满足行变换输入需求。

图2　转置模块结构

由行变换输出数据进行缩放后得到最终的二维离散小波系数。缩放模块将待缩放的小波系数进行单次缩放,缩放模块设计结构如图3所示。

图3　缩放模块结构

1.3　二维变换模块

本文所设计的二维9/7 DWT变换模块结构如图4所示,整体结构为双输入双输出,数据进入后,依次由列变换模块、转置模块、行变换模块和缩放模块进行处理,最终输出离散小波系数。

上述各个模块组成的逻辑单元可单独对输入数据进行离散小波变换处理,也可并行搭建满足任意并行度下的高吞吐率的数据处理。当并行搭建逻辑单元以处理高并行度数据时,任意两单元间的列变换模块所需的大小为4N的暂存可被单元间数据传递所取代,因此无论系统并行度大小,系统所需变换缓存恒为4N。

图4　本文设计的二维9/7 DWT变换模块结构

2　整体结构设计

2.1　非折叠结构

根据JPEG2000算法,输入图像数据经过多级二维9/7 DWT模块处理后得到的小波系数会进入EBCOT模块进行进一步处理。多级9/7 DWT模块分为折叠结构与非折叠结构:折叠结构为每级变换依次处理,级间的SLL分量需要进行全部存储;非折叠结构为多级变换共同进行,通过运算处理单元的增加来加快处理速度、减小缓存面积。由于非折叠结构处理速度更快、数据缓存更小,因此本设计采用非折叠结构。

非折叠结构中多级离散小波系数同时产生,因此可以由并行EBCOT模块即时处理。然而,由于EBCOT采用的编码为基于码块的条带读取编码方式,码块大小为H×H,传统的基于行扫描、列扫描或并行多输入扫描方式所产生的离散小波系数无法满足EBCOT即时编码的需求,因此,仍要经过存储后进行EBCOT编码,通常需N2存储空间进行缓存。

基于块扫描的9/7DWT结构则可以在单级中直接产生块状分布的离散小波系数用于EBCOT即时编码。但是,在多级DWT结构中,每一级的SLL分量在下一级继续处理时数据流破碎,无法在每一级均产生恒定大小的EBCOT编码块。因此传统的基于块的扫描方式需要进行进一步的优化。

2.2　扫描方式优化

对于一级二维结构,基于块扫描的结构可以直接得到离散小波系数码块。因此设定扫描的9/7 DWT码块大小为2H×2H,则可获得4个大小为H×H的可用于即时处理的EBCOT编码块,如图5a所示。图像划分为若干2H×2H的DWT编码单元扫描,得到的系数只需占用4H2的存储空间即可被EBCOT模块处理。

(a)一级变换扫描方式

(b)两级变换扫描方式

(c)三级变换扫描方式图5　优化块组合扫描方式

对于两级二维结构,第一级产生的码块可直接供EBCOT模块处理。而第二级变换的输入数据为H×H的SLL1码块,经变换处理后会得到4个大小为H/2×H/2的小波系数块,这显然不能满足EBCOT的编码需求。需对块扫描方式进行优化,调整DWT码块的扫描顺序使其满足在第二级最快速度产生大小为H×H的EBCOT编码块的需求。因此在数据扫描时,将相邻4个大小为2H×2H的码块组成DWT基本编码单元,以Z型方式进行扫描如图5b所示。第一级处理后每个基本单元均产生大小为H×H的码块,并以Z型顺序进行第二级处理,这样相邻4个大小为H×H的SLL1码块可以在最短时间内产生EBCOT编码块。

对于三级二维结构,为保证在三级变换中同时生成EBCOT编码块,对16个大小为2H×2H的码块进行Z型嵌套扫描,即在4个基本编码单元扫描顺序基础上,以其为单位整体采用Z型方式进行扫描,如图5c所示。则在第三级变换中,毗邻的16个大小为H/2×H/2的SLL2码块可以以最快速度产生EBCOT编码块。

综上,对于级数为L的多级离散小波变换模块,为最大化非折叠结构的优势,多级同时产生可直接用于EBCOT编码的码块,可将图像划分为若干大小为4(L-1)×2H×2H的DWT基本编码单元,在单元内部按照Z型嵌套的扫描方式完成模块扫描。DWT基本编码单元之间横向顺次进入DWT模块即可完成一副图像的高效编码。

2.3　并行度优化

本文所设计的码块内数据采用硬件效率较高的横向并行扫描方式。由于数据每经过一级数据处理并行度即降低为上一级的1/2,因此本结构中每级的二维DWT模块并行度也降为上一级的1/2。以三级系统为例,第一级并行度为S,则第二级并行度为S/2,第三级并行度为S/4。

由于数据并行度与结构并行度一致,因此非折叠结构级间的结构缓存得以消除。对于每一级而言,码块的扫描次序不变而只有码块的大小发生了改变,因此每一级的控制只需修改码块大小参数,极大的降低了系统控制的复杂性。

2.4　边界处理

由于采用优化码块扫描方式,需要对码块数据进行妥善处理以避免降低压缩质量。在本文设计中,每一个码块都需在其上边界和左边界接收数据,在其下边界和右边界传出数据,如图6a所示。由于存储单元为复用,因此总体边界缓存相当于在缓存每个基本编码块两边界,如图6b所示。

(a)边界数据传输　　　(b)基本编码单元边界缓存图6　边界处理方式

(11)

由于DWT基本编码单元横向顺次进入DWT模块列变换,左右边界的数据传输即行变换模块数据寄存只需深度为8个基本处理单元大小的存储空间,用于分别存储H分量与L分量的中间值D1、D2、D3与D4。则J级变换所需行变换暂存为

(12)

在所设计的多级二维非折叠DWT结构中对离散小波系数的存储进行了改进,采用了乒乓存储的策略。这样在并行EBCOT处理速度不足的情况下,当前基本编码单元的系数存入不会对EBCOT读取上一单元的小波系数产生干扰,保证了DWT模块与EBCOT模块数据传输的稳定性与正确性,因此所需离散小波系数存储空间为

nresult=2H2(3(L-1)+4)=(6L+2)H2

(13)

以三级9/7 DWT模块为例,处理单元将会同时产生10个大小为H×H的EBCOT编码块,占据大小为20H2模块间存储空间。

小波系数组织输出后,位平面编码模块以编码块形式读取不同子带的小波系数值并处理为上下文信息对。由于上下文信息对的生成只由当前小波系数编码块决定,因此新型扫描结构不会影响后续算数编码的上下文形成和编码率-失真性能。

3　硬件分析与对比

3.1　硬件消耗

为合理估算硬件资源消耗,设定处理的图像大小为N×N,EBCOT编码块大小为H×H,二维9/7 DWT模块共L级,数据并行度为S(S>1)。

系统中列变换模块间缓存、行变换模块间缓存、级间结构缓存以及DWT-EBCOT模块间数据缓存为大规模数据存储,通过RAM读写实现。由式(11)～(13)可知,所需RAM大小为

(14)

基本处理模块内部缓存通过寄存器实现,根据表1及整体结构设计,L级并行度为S的9/7 DWT系统寄存器数量为

(15)

加法器与乘法器在列变换、行变换与缩放模块中被使用,与计算寄存器数量相同,系统所需加法器与乘法器数量为

(16)

3.2　硬件效果对比

文献[11]也通过块扫描优化的方式来减少小波系数缓存。由于其未提供具体模块结构与运算时间等信息,因此通过对比存储资源消耗得出硬件效果的对比。在图像大小为1024×1024像素、EBCOT码块为典型的32×32像素和64×64像素[13]的情况下,两级小波变换存储资源消耗对比如表1所示。由表1可以看出,本文结构可节约存储资源消耗40%以上。

表1　两种结构存储资源对比

将本文结构与文献[7-9]的多级离散小波变换结构的硬件资源消耗作对比,结果如表2所示,其中所列结构均为输入数据并行度S=8的三级变换结构,输入图像大小为512×512像素,EBCOT码块大小为64×64,存储资源消耗单位为kB。表中处理时间为关键路径延时×处理周期数,单位为ns。本结构的寄存器、加法器、乘法器数量以及资源消耗情况根据式(14)～(16)得出。通过表2的综合对照可以看出,与已有最优结构相比,虽然本文设计的结构运算资源略有增加,但总体存储资源消耗减少了60%以上,同时处理时间优于大部分结构,因此可以认为本文结构的硬件综合效果最优。并且随着图片尺寸的增大或EBCOT码块大小的减小,

本文结构

对DWT模块与EBCOT模块间的存储优化会进一步体现。

4　结束语

本文提出了一种新型多级二维离散小波变换的硬件结构,优化了数据扫描方式,调整了硬件架构与数据处理方式。各项对比结果表明,本文结构对比已有最优结构,可以节约40%以上的存储资源消耗,有着重要的实用价值。

参考文献:

[1]邵婷婷, 白宗文, 周美丽. 基于离散小波变换的信号分解与重构 [J]. 计算机技术与发展, 2014, 24(11): 159-161.

SHAO Tingting, BAI Zongwen, ZHOU Meili. Decomposition and reconstruction of signal based on DWT [J]. Computer Technology and Development, 2014, 24(11): 159-161.

[2]DARJI A, AGRAWAL S, OZA A, et al. Dual-scan parallel flipping architecture for a lifting-based 2-D discrete wavelet transform [J]. IEEE Transactions on Circuits & Systems: IIExpress Briefs, 2014, 61(6): 433-437.

[3]WANG Jianxin, ZHU En. A high-throughput VLSI design for JPEG2000 9/7 discrete wavelet transform [J]. Journal of Southeast University (English Edition), 2015, 31(1): 19-24.

[4]HU Y, JONG C C. A Memory-efficient scalable architecture for lifting-based discrete wavelet transform [J]. IEEE Transactions on Circuits & Systems: IIExpress Briefs, 2013, 60(8): 502-506.

[5]王雨, 马军山, 王华. 基于FPGA的9/7小波变换算法实现 [J]. 光学仪器, 2014, 36(5): 403-408.

WANG Yu, MA Junshan, WANG Hua. FPGA implementation of 9/7 wavelet transform algorithm [J]. Optical Instruments, 2014, 36(5): 403-408.

[6]贾琦, 梁煜, 张为. 一种无片外存储的高性能二维DWT架构 [J]. 西安电子科技大学学报, 2017, 44(4): 150-155.

JIA Qi, LIANG Yu, ZHANG Wei. Hardware efficient 2-D DWT architecture without Off-Chip RAM [J]. Journal of Xidian University, 2017, 44(4): 150-155.

[7]MOHANTY B K, MEHER P K. Memory efficient modular VLSI architecture for high throughput and low-latency implementation of multilevel lifting 2-D DWT [J]. IEEE Transactions on Signal Processing, 2011, 59(5): 2072-2084.

[8]MOHANTY B K, MEHER P K. Memory-efficient high-speed convolution-based generic structure for multilevel 2-D DWT [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(2): 353-363.

[9]HU Y, JONG C C. A memory-efficient high-throughput architecture for lifting-based multi-level 2-D DWT [J]. IEEE Transactions on Signal Processing, 2013, 61(20): 4975-4987.

[10] WU B F, LIN C F. Memory-efficient architecture for JPEG 2000 coprocessor with large tile image [J]. IEEE Transactions on Circuits & Systems: IIExpress Briefs, 2006, 53(4): 304-308.

[11] YE L, HOU Z. Memory efficient multilevel discrete wavelet transform schemes for JPEG2000 [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2015, 25(11): 1773-1785.

[12] ZHANG W, JIANG Z, GAO Z, et al. An efficient VLSI architecture for lifting-based discrete wavelet transform [J]. IEEE Transactions on Circuits & Systems: IIExpress Briefs, 2012, 59(3): 158-162.

[13] GAVVALA R, GOPAL M M, CHANDRA S S. Pass-parallel VLSI architecture of BPC for embedded block coder in JPEG2000 [C]∥Asia Pacific Conference on Postgraduate Research in Microelectronics and Electronics. Washington, DC, USA: IEEE Computer Society, 2012: 111-117.