一種新型低存儲二維離散小波變換架構

高家明， 梁　煜， 張　為， 劉艷艷

(1. 天津大學 微電子學院，天津 300072;2. 南開大學 電子信息與光學工程學院，天津 300071)

二維離散小波變換(Discrete Wavelet Transform， DWT)是一種被廣泛應用于數字信號處理、圖像分析、圖像壓縮等領域的信號濾波處理方法，其作用是將信號的主要信息與細節信息分離．對于用硬件實現二維離散小波變換結構，為了低功耗、高效處理信號如數字圖像，在提高系統性能的同時降低硬件資源使用已逐漸成為二維離散小波變換結構優化的主要研究方向．

近年來，大量關于二維離散小波變換的超大規模集成電路(Very Large Scale Integration， VLSI)結構的研究成果被發表．文獻[1]在已有提升算法的基礎上對公式進行優化，提出了新型雙輸入/雙輸出結構，并采用pipeline結構，降低關鍵路徑延時(Critical Path Delay， CPD)為一個乘法器延時(Tm)，內部數據存儲減少為4N(N為輸入圖像長度)．文獻[2]提出了一種橫向Z形掃描的雙輸入/雙輸出結構，關鍵路徑為一個乘法器延時．文獻[3]通過對不同掃描方式的對比，采用圖像分塊掃描的方式降低了資源存儲面積．文獻[4]引入了重復掃描的方法，通過重復掃描1行像素的方法減小了模塊的內存儲面積．重復掃描的方法在文獻[5-9]中也被采用，通過重復掃描1行、3行、5行和7行數據，可在模塊內部分別節省N、2N、3N和4N的數據存儲空間．文獻[9-10]通過提高并行度的方式來增加系統的吞吐率，極大地減小了整體運算時間，但是提高并行度的方法在減少運算時間的同時，會增加輸入數據的寄存空間和運算資源消耗．

通過對已有結構的分析發現，圖像數據大多在片外隨機存取存儲器(Random Access Memory，RAM)進行整體存儲．然而片外隨機存取存儲器的存在既會增加板級系統設計的復雜度，也會對數據接口位寬提出更高的要求．尤其對于實時圖像采集壓縮系統而言，原始數據通常會逐行逐點依次到達，此時若片外緩存數據過多，則不僅面積偏大而且整體延時較長，不利于整體實現效果．采用片內隨機存取存儲器存儲，同時對輸入數據掃描順序進行調整，可以有效地緩解這一問題，有利于提高實時圖像處理性能．同時，已有結構的運算單元也存在延時高與資源消耗大的缺陷，可結合二維離散小波變換提升算法對運算結構進行改進來實現優化．

筆者將基于二維離散小波變換提升算法改進圖像掃描方式，優化輸入圖像存儲需求和模塊內數據存儲需求，提升硬件效率與系統性能．

1　提升算法

二維離散小波變換提升算法最早由Daubechies 和Sweldens所提出，之后文獻[11]對提升算法進行改進．改進算法如下所示．

首次預測與更新:

二次預測與更新:

兩步縮放:

上式中，x表示原始輸入數據，y表示變換中間值，H0表示最終變換得到的高頻小波系數，L0表示最終變換得到的低頻小波系數．α，β，γ，δ，K為常數定值，取值如下[12]:

α=-1.586 134 342，β=-0.052 980 118，γ=0.882 911 075，δ=0.443 506 852，K=1.230 174 105．

2　數據掃描

通過對式(1)～(4)分析可以發現，每一個公式中都包含一個乘法運算和兩個加法運算．且對于式(2)～(4)而言，在流水線結構下每一次加法運算中的待乘加數至少比非待乘加數提前一個周期到達．如式(2)中的待乘加數x2n在第1周期已經到達，而y2n+1與y2n-1至少要在第2周期得到．又因為16位加法器與乘法器的典型延時分別為 3.01 ns 和 6.79 ns[13]，因此基本運算中的乘法運算與加法運算是可以同時進行且不會對關鍵路徑產生影響．

因此，本設計對數據輸入順序進行了調整，使得包括式(1)在內的每一級基本運算均能滿足乘法與加法并行執行的要求．橫向并行三輸入 (2+1，其中一行為重復掃描)掃描為綜合存儲隨機存取存儲器最小的掃描方式，通過調整寫入讀出的時鐘比為2∶1即可完成并行三輸入掃描[14]．在此基礎上，采取數據時鐘錯位的方法，將像素x2n+1點提前于x2n，與x2n+2一個周期進入二維離散小波變換處理模塊，這樣使得每一級的基本運算均可以并行執行．掃描方式如圖1所示，其中CLKN代表當前行的第N個周期，灰色像素點為重復掃描像素點．

圖1　橫向三輸入掃描

3　架構設計

3.1　模塊設計

根據式(1)～(4)及掃描方式，對列變換模塊設計如下．設計采用四級流水線結構，即每一基本運算均在一級流水線中完成．由于x2n+1先于x2n與x2n+2一個周期輸入，因此當x2n與x2n+2進入系統時，x2n+1的乘法操作已于上一周期完成，故而可直接進行連續加法操作，式(1)基本運算的并行處理得以解決．

在式(1)的基本運算通過錯位輸入的方式完成后可以發現，對于式(2)而言，x2n先于y2n+1一個周期到達，因此其乘法運算可提前一周期完成，之后與下一周期到達的y2n+1和由隨機存取存儲器1輸入的y2n-1進行連續加法來實現式(2)的運算．式(3)和式(4)的運算過程與式(2)的完全一致．由于數據錯位輸入后式(1)～(4)的基本運算除了乘法系數外，處理方式完全相同，因此設計乘法路徑與加法路徑相分離的基本運算單元，如圖2中虛線框所示，并通過對基本運算模塊的調用和乘法系數的多路選擇完成一維變換架構的搭建．這樣優化后的運算結構使得每一級基本運算都得以并行處理，在四級流水線結構內完成了一維離散小波變換處理，節省了寄存器數量和運算時間，簡化了控制邏輯．

圖2　列變換模塊

列變換模塊結構設計如圖2所示，圖中帶*項代表下一列的x2n+1值，灰色寄存器為輸出的小波系數．列變換對中間值y2n+1、y2n和H2n+1進行緩存，共需要3N的數據緩存空間．

由列變換模塊輸出的L與H碼流需要經過轉置后進入行變換模塊處理．由于本結構基于行并行掃描方式，因此轉置模塊只需要5個寄存器即可滿足行變換模塊數據錯位的三輸入要求．轉置模塊的架構如圖3所示．

圖3　轉置模塊

如圖4所示，基于錯位三輸入的行變換模塊結構與列變換模塊結構整體相近．不過，由于數據流是連續的，因此不需要隨機存取存儲器進行大量的數據存儲，只需要在每一級使用兩個深度的寄存器(圖中以buffer表示)進行兩周期的數據緩存即可．

圖4　行變換模塊

對于縮放模塊，采用了一次縮放方案，即在行變換與列變換的二維處理結束后對于輸出數據進行單次縮放．由式(1)～(4)可知，經二維變換后待縮放的數據分別為LL/ (αβγδ)2、LH/ ((αβγ)2δ)、HL/ ((αβγ)2δ) 和HH/ (αβγ)2，縮放模塊如圖5所示．

3.2　整體結構

筆者所設計的二維離散小波變換整體結構如圖6所示，輸入像素點逐行依次進入

輸入隨機存取存儲器，之后以并行三輸入方式進入行變換模塊進行二維離散小波變換，最終數據由縮放模塊并行輸出．

圖5　縮放模塊

圖6　離散小波變換整體結構

4　硬件開銷對比

表1中將本結構與其他現有架構進行了對比．由于高并行度架構需要巨大的輸入隨機存取存儲器，使得對比意義不大，因此所列舉架構均取并行度S=1 的二維離散小波變換硬件結構．通常原始像素數據為 8 bit，進入系統前需要拓展為 16 bit，因此表中輸入隨機存取存儲器為 8 bit，暫存隨機存取存儲器為 16 bit，乘法器(mul)、加法器(add)與寄存器(reg)均為 16 bit．Tm表示一個乘法器延時，Ta表示一個加法器延時，N為圖像每行像素個數，輸入數據 (2+1) 表示一行為重復掃描．

表1　整體硬件開銷對比

通過整體硬件開銷對比可以發現，本結構的運算資源消耗少于絕大部分文獻中的列舉結構．文獻[4]雖然寄存器數量少于本結構，但是其關鍵路徑延時約為本結構的1.5倍，綜合考慮硬件效率仍略低于本結構的．為了更加直觀地對各硬件架構的硬件效率進行對比，文獻[15]提出了對晶體管數量-延時-吞吐量(Transistor count Delay Product， TDP)進行綜合對比．TDP值為晶體管總數(Transistor Count， TC)、關鍵路徑延時(CPD)以及活動周期數(Active Cycle Time， ACT)三者的乘積．其中，一個乘法器的延時Tm= 6.79 ns，一個加法器的延時Ta= 3.01 ns，TACT=N2/T(T為吞吐量)．因此可以認為，TDP評價方式考慮了數據吞吐量、架構對于時間和硬件開銷的綜合需求．TDP值越小，代表架構的硬件效率越高．

對于器件中的晶體管數量，文獻[15-16]中提供了一種基于陣列加法器和陣列乘法器的晶體管數量計算方法．其中，8 bit 的乘法器、加法器、寄存器和隨機存取存儲器的晶體管數量分別為 1 085、248、128和48，16 bit 的加法器、寄存器和隨機存取存儲器的晶體管數量分別是504、256和96，16 bit 乘法器的晶體管數量為 5 084．綜合考慮以上因素后，表2對已有結構硬件效率進行了綜合對比，測試圖像大小為 512× 512，表中mul、add、reg和隨機存取存儲器代表乘法器、加法器、寄存器和隨機存取存儲器的晶體管數量．

表2　硬件效率對比

通過對比結果可以發現，同已有最優架構相比，本結構硬件效率優化達到8.4%; 與文獻[4]中同為三輸入的結構相比，本結構硬件效率優化達到30%以上．因此可以得出結論，筆者設計的架構在硬件效率(TDP)上均優于現有架構．

5　總　　結

筆者設計了一種高性能的二維離散小波變換架構，采用了并行三輸入數據錯位的掃描方式，優化了變換模塊內部運算結構，減少了硬件開銷，硬件效率提高8%以上．

參考文獻：

[1] ZHANG W, JIANG Z, GAO Z, et al. An Efficient VLSI Architecture for LIfting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2012, 59(3): 158-162.

[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 and Systems Ⅱ: Express Briefs, 2014, 61(6): 433-437.

[3]YE L N, HOU Z. Memory Efficient Multilevel Discrete Wavelet Transform Schemes for JPEG2000[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2015, 25(11): 1773-1785.

[4]HU Y S, JONG C C. A Memory-efficient Scalable Architecture for Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2013, 60(8): 502-506.

[5]MOHANTY B K, MEHER P K. Area-delay-power-efficient Architecture for Folded Two-dimensional Discrete Wavelet Transform by Multiple Lifting Computation[J]. IET Image Processing, 2014, 8(6): 345-353.

[6]MOHANTY B K, MEHER P K, SRIKANTHAN T. Critical-path Optimization for Efficient Hardware Realization of Lifting and Flipping DWTs[C]//Proceedings of the 2015 IEEE International Symposium on Circuits and Systems. Piscataway: IEEE, 2015: 1186-1189.

[7]TODKAR S, SHASTRY P V S. Flipping Based High Performance Pipelined VLSI Architecture for 2-D Discrete Wavelet Transform[C]//Proceedings of the 2015 International Conference on Applied and Theoretical Computing and Communication Technology. Piscataway: IEEE, 2015: 832-836.

[8]DARJI A D, LIMAYE A. Memory Efficient VLSI Architecture for Lifting-based DWT[C]//Proceedings of the 2014 Midwest Symposium on Circuits and Systems. Piscataway: IEEE, 2014: 189-192.

[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]MOHANTY B K, MAHAJAN A, MEHER P K. Area- and Power-efficient Architecture for High-throughput Implementation of Lifting 2-D DWT[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2012, 59(7): 434-438.

[11]HUANG C T, TSENG P C, CHEN L G. Flipping Structure: an Efficient VLSI Architecture for Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Signal Processing, 2004, 52(4): 1080-1089.

[12]董明巖, 雷杰, 王柯儼, 等. 高效低存儲DWT的VLSI結構設計[J]. 西安電子科技大學學報, 2016, 43(2): 35-40.

DONG Mingyan, LEI Jie, WANG Keyan, et al. Highly Efficient VLSI Architecture for DWT with Low-storage Implementation[J]. Journal of Xidian University, 2016, 43(2): 35-40.

[13]HSIA C H, CHIANG J S, GUO J M. Memory-efficient Hardware Architecture of 2-D Dual-mode Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(4): 671-683.

[14]WU C K, ZHANG W, JIA Q, et al. Hardware Efficient Multiplier-less Multi-level 2D DWT Architecture without off-chip RAM[J]. IET Image Processing, 2017, 11(6): 362-369.

[15]賈琦, 梁煜, 張為. 一種無片外存儲的高性能二維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.

[16]MOHANTY B K, MEHER P K. Memory Efficient Modular VLSI Architecture for Highthroughput and Low-latency Implementation of Multilevel Lifting 2-D DWT[J]. IEEE Transactions on Signal Processing, 2011, 59(5): 2072-2084.