基于Z型結構的低存儲二維DWT硬件結構

陶 鈞，虞玉龍，沈海斌＋

（1.浙江大學 超大規模電路研究所，浙江 杭州 310027；2.浙江杭州谷易科技有限公司，浙江 杭州 310000）

0 引 言

傳統的信號理論是建立在傅立葉分析基礎上的，但是傅立葉變換作為一種全局性的變化，有某些局限性，于是小波變換產生了。小波變換的優點是能夠對信號進行由粗到精的多尺度分析，現在被大量不同的應用領域采納，包括信號分析、圖象處理、量子力學、理論物理、軍事電子對抗與武器的智能化、醫學成像與診斷、地震勘探數據處理、大型機械的故障診斷等方面，因此小波變換具有極高的研究價值。特別是在圖像處理領域，其良好的時頻局部特性和去相關能力使得小波變換得到了廣泛的使用。

JPEG2000標準的核心變換技術就是離散小波變換［1］（DWT）。通過VLSI實現DWT 運算需要盡量減少邏輯結構和存儲單元，來獲得較低的功耗和較小的面積。傳統的離散小波變換采用卷積的模式，需要相對復雜的運算和大量的存儲單元。于是Sweldens在1994年的時候提出了提升算法（Lifting Scheme），從而減少了二維DWT的運算復雜度，方便用于硬件的實現。但通常的實現方法是先進行所有行變換，然后進行所有列變換，這使得中間需要大量的存儲空間來緩存行變換的結果（一般需要N＊N的存儲空間，N為圖像行列數），并且行列運算串行進行，效率不夠高。因此已經提出了不少新的VLSI結構來減少緩存單元和進行行列并行運算，比如基于行［2－4］（Line－based）和基于塊［5－6］（block－based）等結構，但存儲單元數量還是相對較大。特別是當處理的圖像越大時，存儲單元增多帶來的芯片面積增長速度也越明顯。

本文結合基于行和基于塊的二維DWT 設計，采用一種新的Z型調度方式，使得整個過程能夠行列并行運算，并且減少中間緩存單元數量，只需4N個中間存儲單元就能實現二維DWT 運算。同時，采用16位帶符號整數和16位小數精度，使得該設計支持1023級（10位）的灰度等級來滿足數字高清晰度顯示的需要［7］，同時保證DWT 變換過程中的精度。

1 基于提升的DWT及部分參數的選擇

1.1 小波提升系數的選擇及其分解步驟

JPEG2000標準給出了兩種雙正交小波濾波器，CDF9／7（有損）和樣條5／3（無損），對于自然圖形來說，CDF9／7濾波器的壓縮性能比5／3濾波器更好，本文就以9／7濾波器來展開介紹設計流程。

因為CDF9／7小波系數均為比較復雜的無理數，硬件的實現比較復雜，故而鐘廣軍、成禮智等人提出了一組簡單的LS9／7小波提升系數［8］，如式1，并且通過實驗表明采用CDF9／7和LS9／7小波提升系數分解圖像的壓縮性能幾乎相同，但減少了硬件實現的復雜度

提升小波變換由3個部分組成：分裂，預測，更新。分裂指的是將輸入信號分為奇偶兩組數列Xo和Xe；預測是指針對數據間相關性，用Xe與預測算子P來預測Xo，用預測值與Xo的差值來代替Xo，d＝Xo－P（Xe），d表示圖像的高頻細節。更新是指用細節信號來計算低頻近似信號，S＝X＋U（d），通過兩次預測和更新得到近似分量和細節分量。9／7小波變包含兩次預測更新過程組成，如圖1所示。

圖1 9／7小波變換

9／7小波提升算法的分解步驟：

1.2 邊界延拓算法

圖像信號屬于二維信源，一般受到物理約束而有邊界，所以必須考慮它的邊界效應，特別對于分解級數高的子帶來說，一般對其采樣數目較少，邊界處理的好壞對于重建圖像的影響比較大，因此一般需要進行邊界延拓。

常用的邊界延拓算法有邊界元素復制法、周期延拓法、對稱延拓法、0填充延拓法等等，其中邊界元素復制法、0填充法的性能較差，一般使用周期延拓法或者對稱延拓法［9］。對于圖像處理，使用對稱延拓法能得到比較平滑的圖像邊界，故而本文采用對稱延拓法，其表達公式為式（8）

實驗表明，當采用對稱延拓算法進行5級小波變換時，圖像恢復的質量相對較好。

1.3 定點長度的選擇

硬件電路的數據運算有浮點和定點之分，浮點運算的精度較高，但相應的電路較復雜，速度也較慢，而定點運算則電路簡單，速度較快。本文采用定點運算做DWT 運算。但定點運算必須先預估運算時中間值和結果的最大長度來避免溢出。

對于9／7濾波器來說，其低通濾波器的時域沖擊響應系數之和為

假設一幅圖像的最大灰度值為M，然后經過N 級的小波變換之后，其最低的子帶系數（LL）有可能出現的MAX 值

即，當N＝5（5級小波變換），K＝1023（10位灰度）時，Max＝32736，所以此時需要15 位來存儲小波系數的整數部分。目前常見的數字高清晰度顯示可以達到10位以上的灰度等級，同時考慮硬件設計與外圍設備的通用性，所以本文采用15 位來表示小波系數的整數部分。另一方面，小波系數的小數部分對低頻子帶的精確度影響較大，故而本文采用16位來表示小波系數的小數部分，來提高計算的精度，加上最高的一位符號位，本文采用32位來表示單個小波系數值。

2 DWT結構設計

2.1 一維DWT結構

由上一節中提升DWT的計算步驟可知，一維DWT的硬件結構一般可以分為圖2并行運算，同時處理所有的輸入信號和圖3串行運算，每周期處理一對輸入信號。由于存儲器的端口問題，一般選取圖3使用流水結構以節省硬件資源。

2.2 行DWT的硬件結構

由于本文設計的二維并行機制，使得行DWT 運算類似于基于行（Line－based）DWT的運行方式，故而采用較為常見的一種二輸入的流水結構來作為行DWT 結構［10］，具體結構見圖4。

圖4 行DWT的硬件結構

用一個寄存器來作為延遲單元，在圖4中用z－1來表示，在該設計中需要8個加法器，6個乘法器（其中兩個尺度變換時的乘法器未在圖中標識）。每個周期送入兩個數據進入流水線，由于并非是將一整行數據連續輸入，所以按照一次輸入兩個之前保存的邊界值然后下一次輸入兩個該行余下數據的方式運行，詳見第3節中的具體描述。

2.3 列DWT的硬件結構

列方向的DWT 則是一個3 輸入的流水線，如圖5 所示。需要額外的SRAM 來存儲上次計算過程中的邊界數據，總計需要4N個存儲單元。每次（第一次除外）有新的兩個數據進入流水，再額外從SRAM 中讀取對應的一個數據來進行計算，詳見下一節中的具體描述。

圖5 列DWT的硬件結構

3 二維并行過程

普通二維DWT 計算過程在計算過程中需要存儲大量的緩沖數據，會造成大量的硬件開銷，所以本文提出了一種新的基于Z型結構的運行方法，老減少中間的存儲單元，并且使得行列并行。

因為采用的是對稱邊界的方式，所以只需圖像第一行的前5個信號數據就可以得到第一組2個小波系數，同理只要先完成前五行的第一組小波系數就可以開始列方向的DWT，故而如圖6所示，本文提出的二維DWT 運行方式為首先對前五行的前5個信號進行運算得到列方向所需的兩列數據，此時列方向的DWT 同時開始進行，然后行方向回到第一行繼續得到兩個數據，與之前保存的邊界數據一起運算得到新的兩個小波系數，再依次運算第二到第五行，從而得到列變換所需的下兩列數據直到前5行信號都完成行變換后，從第6行開始行變換只需連續兩行得到的小波系數就可滿足列變換所需，由此可以實現行列的并行運算，提高運算效率。

在并行運行過程中，由于行列變換均不是連續進行的，所以行列變換均需要進行邊界緩存，圖7所示為行變換需要保存的邊界值，圖8所示為列變換需要保存的邊界值。

由行變換的結構可知，每周期有兩個圖像數據進入流水線，采用對稱結構的9／7小波變換只需要前5個數據即可計算得第一組小波系數（S0和d0），然后換行繼續計算，故而需要保存其邊界值。如圖7所示，需要保存以黑色標記的5個數據。完成前5行的第一組小波系數計算后，返回第一行繼續計算，將之前保存的X4、X5以及X6、X7按順序送入流水，加上之前的邊界數據即可算的第二組小波系數（S1和d1），并保存新的邊界值。以此類推計算其他行系數。

與行變換類似，由列變換的結構可以看出，每周期有三個數據進入流水線，故而當第一次5個數據完成運算后，每次將行變換所得的兩個結果和之前緩存的一個值同時送入流水線進行操作，因此，需要緩存4個邊界值，如圖8中黑色標記的數據。

由圖6、7、8可以看出，行變換的邊界值保存需要5＊5個寄存器，而計算N＊N的一副圖像則需要4N個存儲單元來存儲列變換的邊界值，又由于列方向的處理速度要快于行方向，所以列方向的流水線并非時時有輸入，故而可以使用單端口的RAM 來作為存儲（4個單端口的RAM）。因為雙端口RAM 面積要明顯大于單端口RAM，這樣可以有效較少芯片的總面積。然后還需要7＊5個寄存器來存放行變換所得的小波系數提供給列變換進行運算。

表1與幾個不同的二維DWT 結構的存儲單元數量做了個比較，依照本文所述方法，可得到一個較少中間緩存單元的設計方法。

表1 不同二維DWT 中間緩存存儲器需求的比較（N＊N 圖像）

當列變換完成后將LL的結果存放直外部存儲器中，等待下一級分解，直到完成指定的分解級數為止。

4 實驗結果與分析

基于本文提出的二維并行DWT 結構，進行了RTL 級Verilog代碼的編寫，并進行了代碼仿真，驗證了該結構的正確性和可實現性。由于該結構可以進一步加深流水線，可以較容易的提高系統運行頻率，本文采用比較通用的100MHZ時鐘對RTL進行DC綜合。表1、2分別顯示了當N＝256和512 時，傳統基于行的一種方法（一種非重疊的，基于2像素寬度圖紋掃描的方式）和本文提供方法的面積比較，采用SMIC0.18um 工藝，100MHZ時鐘，32位內部RAM，32位小波系數。

表2 與傳統方式的比較（N＝256）

表3 與傳統方式的比較（N＝512）

由表2和表3的數據可看出，實驗結果與之前的結論相吻合，即依照本文的方法可以實現一種低存儲（4＊N 單端口RAM）的二維DWT 結構。并且當N 越大時可節省的面積越多，所以本文所提出的二維并行DWT 結構具有一定的優越性。本設計在100MHZ時鐘下，每秒可以處理65幀1024＊1024＊10位的圖像。

5 結束語

在目前的高清圖像處理中，越來越大的圖像尺寸需求必然使得芯片的片上存儲不斷加大，從而使得芯片的面積急速增加，節省片上存儲空間將成為設計者必須面對的問題。本文提出了一種低存儲的二維并行DWT 結構，并證明了其比較高效的運行速率和可實施性，行列運算都實現了流水操作，有較好的硬件利用率，并且使用了16位數據用于存放小波系數的小數部分，有較高的精度保證，該設計非常適合VLSI的實現。

［1］Smorfa S，Olivieri M.HW－SW optimisation of JPEG2000wavelet transform for dedicated multimedia processor architectures［J］.Computers ＆Digital Techniques，IET，2007，1（2）：137－143.

［2］WANG Chao，WU Zhilin，CAO Peng，et al.An effici－ent VLSI architecture for lifting－based discrete wa－velet transform［C］／／Beijing：IEEE International Conference on Multimedia and Expo，2007：1575－1578.

［3］Jain R，Panda P R.An efficient pipelined VLSI architecture for lifting－based 2D－discrete wavelet transform［C］／／New Orleans LA：IEEE International Symposium on ISCAS， 2007：1377－1380.

［4］PENG Cao，XIN Guo，CHAO Wang，et al.Efficient architecture for two－dimensional discrete wavelet transform based on lifting scheme［C］／／Guilin：7th International Confe－rence on ASICON，2007：225－228.

［5］Yang C H，Wang J C，Wang J F，et al.A block－based architecture for lifting scheme discrete wavelet transform［J］.IEICE Transactions on Fundam－entals of Electronics，Communications and Computer Sciences，2007，90（5）：1062－1071.

［6］Salehi S A，Amirfattahi R.A block－based 2Ddiscrete wavelet transform structure with new scan method for overlapped sections［C］／／Sharjah：Middle East Conference on Biomedical Engineering，2011：126－129.

［7］LU Chihwen，HUANG Lungchien.A 10－Bit LCD column driver with piecewise linear digital－to－analog converters［J］.IEEE Journal of Solid－State Circuits，2008，43（2）：371－378.

［8］DO Quan，Yo Sung Ho.Efficient wavelet lifting scheme based on filter optimization and median operator［C］／／Danang：International Conference on Computing and Communication Technologies RIVF，2009：1－6.

［9］HONG Qi，WANG Kanwen，CAO Wei，et al.A reconfigurable VLSI structure for DWT［C］／／Nanjing：International Conference on Information Science and Engineering，2009：465－468.

［10］Hannu Olkkonen.Discrete wavelet transforms algorithms and applications［M］.Rijeka：Intech Open Access publisher，2011：41－56.