基于Z型結(jié)構(gòu)的低存儲(chǔ)二維DWT硬件結(jié)構(gòu)

陶 鈞，虞玉龍，沈海斌＋

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

0 引 言

傳統(tǒng)的信號(hào)理論是建立在傅立葉分析基礎(chǔ)上的，但是傅立葉變換作為一種全局性的變化，有某些局限性，于是小波變換產(chǎn)生了。小波變換的優(yōu)點(diǎn)是能夠?qū)π盘?hào)進(jìn)行由粗到精的多尺度分析，現(xiàn)在被大量不同的應(yīng)用領(lǐng)域采納，包括信號(hào)分析、圖象處理、量子力學(xué)、理論物理、軍事電子對(duì)抗與武器的智能化、醫(yī)學(xué)成像與診斷、地震勘探數(shù)據(jù)處理、大型機(jī)械的故障診斷等方面，因此小波變換具有極高的研究?jī)r(jià)值。特別是在圖像處理領(lǐng)域，其良好的時(shí)頻局部特性和去相關(guān)能力使得小波變換得到了廣泛的使用。

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

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

1 基于提升的DWT及部分參數(shù)的選擇

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

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

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

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

圖1 9／7小波變換

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

1.2 邊界延拓算法

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

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

實(shí)驗(yàn)表明，當(dāng)采用對(duì)稱延拓算法進(jìn)行5級(jí)小波變換時(shí)，圖像恢復(fù)的質(zhì)量相對(duì)較好。

1.3 定點(diǎn)長(zhǎng)度的選擇

硬件電路的數(shù)據(jù)運(yùn)算有浮點(diǎn)和定點(diǎn)之分，浮點(diǎn)運(yùn)算的精度較高，但相應(yīng)的電路較復(fù)雜，速度也較慢，而定點(diǎn)運(yùn)算則電路簡(jiǎn)單，速度較快。本文采用定點(diǎn)運(yùn)算做DWT 運(yùn)算。但定點(diǎn)運(yùn)算必須先預(yù)估運(yùn)算時(shí)中間值和結(jié)果的最大長(zhǎng)度來避免溢出。

對(duì)于9／7濾波器來說，其低通濾波器的時(shí)域沖擊響應(yīng)系數(shù)之和為

假設(shè)一幅圖像的最大灰度值為M，然后經(jīng)過N 級(jí)的小波變換之后，其最低的子帶系數(shù)（LL）有可能出現(xiàn)的MAX 值

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

2 DWT結(jié)構(gòu)設(shè)計(jì)

2.1 一維DWT結(jié)構(gòu)

由上一節(jié)中提升DWT的計(jì)算步驟可知，一維DWT的硬件結(jié)構(gòu)一般可以分為圖2并行運(yùn)算，同時(shí)處理所有的輸入信號(hào)和圖3串行運(yùn)算，每周期處理一對(duì)輸入信號(hào)。由于存儲(chǔ)器的端口問題，一般選取圖3使用流水結(jié)構(gòu)以節(jié)省硬件資源。

2.2 行DWT的硬件結(jié)構(gòu)

由于本文設(shè)計(jì)的二維并行機(jī)制，使得行DWT 運(yùn)算類似于基于行（Line－based）DWT的運(yùn)行方式，故而采用較為常見的一種二輸入的流水結(jié)構(gòu)來作為行DWT 結(jié)構(gòu)［10］，具體結(jié)構(gòu)見圖4。

圖4 行DWT的硬件結(jié)構(gòu)

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

2.3 列DWT的硬件結(jié)構(gòu)

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

圖5 列DWT的硬件結(jié)構(gòu)

3 二維并行過程

普通二維DWT 計(jì)算過程在計(jì)算過程中需要存儲(chǔ)大量的緩沖數(shù)據(jù)，會(huì)造成大量的硬件開銷，所以本文提出了一種新的基于Z型結(jié)構(gòu)的運(yùn)行方法，老減少中間的存儲(chǔ)單元，并且使得行列并行。

因?yàn)椴捎玫氖菍?duì)稱邊界的方式，所以只需圖像第一行的前5個(gè)信號(hào)數(shù)據(jù)就可以得到第一組2個(gè)小波系數(shù)，同理只要先完成前五行的第一組小波系數(shù)就可以開始列方向的DWT，故而如圖6所示，本文提出的二維DWT 運(yùn)行方式為首先對(duì)前五行的前5個(gè)信號(hào)進(jìn)行運(yùn)算得到列方向所需的兩列數(shù)據(jù)，此時(shí)列方向的DWT 同時(shí)開始進(jìn)行，然后行方向回到第一行繼續(xù)得到兩個(gè)數(shù)據(jù)，與之前保存的邊界數(shù)據(jù)一起運(yùn)算得到新的兩個(gè)小波系數(shù)，再依次運(yùn)算第二到第五行，從而得到列變換所需的下兩列數(shù)據(jù)直到前5行信號(hào)都完成行變換后，從第6行開始行變換只需連續(xù)兩行得到的小波系數(shù)就可滿足列變換所需，由此可以實(shí)現(xiàn)行列的并行運(yùn)算，提高運(yùn)算效率。

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

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

與行變換類似，由列變換的結(jié)構(gòu)可以看出，每周期有三個(gè)數(shù)據(jù)進(jìn)入流水線，故而當(dāng)?shù)谝淮?個(gè)數(shù)據(jù)完成運(yùn)算后，每次將行變換所得的兩個(gè)結(jié)果和之前緩存的一個(gè)值同時(shí)送入流水線進(jìn)行操作，因此，需要緩存4個(gè)邊界值，如圖8中黑色標(biāo)記的數(shù)據(jù)。

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

表1與幾個(gè)不同的二維DWT 結(jié)構(gòu)的存儲(chǔ)單元數(shù)量做了個(gè)比較，依照本文所述方法，可得到一個(gè)較少中間緩存單元的設(shè)計(jì)方法。

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

當(dāng)列變換完成后將LL的結(jié)果存放直外部存儲(chǔ)器中，等待下一級(jí)分解，直到完成指定的分解級(jí)數(shù)為止。

4 實(shí)驗(yàn)結(jié)果與分析

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

表2 與傳統(tǒng)方式的比較（N＝256）

表3 與傳統(tǒng)方式的比較（N＝512）

由表2和表3的數(shù)據(jù)可看出，實(shí)驗(yàn)結(jié)果與之前的結(jié)論相吻合，即依照本文的方法可以實(shí)現(xiàn)一種低存儲(chǔ)（4＊N 單端口RAM）的二維DWT 結(jié)構(gòu)。并且當(dāng)N 越大時(shí)可節(jié)省的面積越多，所以本文所提出的二維并行DWT 結(jié)構(gòu)具有一定的優(yōu)越性。本設(shè)計(jì)在100MHZ時(shí)鐘下，每秒可以處理65幀1024＊1024＊10位的圖像。

5 結(jié)束語

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

［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.