郝亞喆,張遠,張為

(1.天津大學微電子學院,300072,天津;2.秦皇島市公安局科技信息化處,066000,河北秦皇島)

因為執(zhí)行原位計算,基于提升的DWT對內(nèi)存需求有所降低。文獻[10]通過優(yōu)化內(nèi)存設(shè)計方案將轉(zhuǎn)置存儲器降低到1.5N個存儲單元,N為圖像每行的像素數(shù),臨時存儲器降低到4N。為進一步減少內(nèi)存,文獻[7-8]采用并行掃描兩行圖像數(shù)據(jù)的方式優(yōu)先進行列濾波器處理,且只需少許寄存器就能完成列濾波器輸出到行濾波器輸入的轉(zhuǎn)置,轉(zhuǎn)置存儲器顯著減小。但這種并行掃描方式仍需要2N大小的輸入存儲器對原始像素點進行存儲。Zhang等提出的三輸入數(shù)據(jù)掃描方案,臨時存儲器減少到3N,但是以增加輸入存儲器為代價[9]。近年來也有一些研究提出了基于條帶以及基于圖像塊的并行處理方法[11-12],但都需要更多內(nèi)存資源存儲整幅圖像像素值。文獻[13]的并行結(jié)構(gòu)同時處理整幅圖像,對于尺寸較大的圖像,消耗過多計算資源。

相較于提升算法,卷積算法計算速度快,但是也消耗更多內(nèi)存資源。Rein等為在內(nèi)存很小的低復(fù)雜性傳感器節(jié)點上實現(xiàn)二維卷積方案,提出了分數(shù)小波濾波(FrWF)算法[14]。每次選擇9行的垂直濾波區(qū)域,其中每行數(shù)據(jù)完成行濾波后,其結(jié)果同時乘以對應(yīng)的列濾波器的系數(shù),得到列變換結(jié)果的一部分;當?shù)?行數(shù)據(jù)完成行濾波,同時列濾波也通過每部分結(jié)果的累加得到最終計算值。將垂直濾波區(qū)域下移兩行,重復(fù)上述操作計算新的列濾波值。通過這種迭代更新列變換結(jié)果的方法,整體二維架構(gòu)內(nèi)存只需2.5N。Tausif等實現(xiàn)了基于5/3小波的FrWF硬件架構(gòu),片上內(nèi)存減少到2N,但是其基于垂直濾波區(qū)域的數(shù)據(jù)掃描方式,大量行數(shù)據(jù)被重復(fù)計算,計算時間達到5N2/2,是提升結(jié)構(gòu)的5倍[15]。

FrWF結(jié)構(gòu)的確為一種低內(nèi)存有效的實現(xiàn)方法,但基于卷積公式,對9/7小波則需重疊7行數(shù)據(jù),計算周期顯著增加。本文提出了基于提升公式的FrWF算法,依賴提升結(jié)構(gòu)就地計算的特點,無需基于垂直濾波區(qū)域重復(fù)計算。設(shè)計的二維提升小波變換硬件架構(gòu),專注于內(nèi)存需求和關(guān)鍵路徑延時的優(yōu)化,有效提高了硬件效率。

1 提升算法及分析

1.1 翻轉(zhuǎn)結(jié)構(gòu)

提升結(jié)構(gòu)分為分裂、預(yù)測、更新3個步驟。Huang等在原有結(jié)構(gòu)上改變乘法系數(shù)位置提出了翻轉(zhuǎn)結(jié)構(gòu),最長延遲路徑中的乘法器被轉(zhuǎn)移,有效縮短了關(guān)鍵路徑[16]。9/7小波變換的翻轉(zhuǎn)結(jié)構(gòu)如下。

首次預(yù)測

(1)

首次更新

(2)

二次預(yù)測

(3)

二次更新

1961年出生的蔡振華，7歲開始練習乒乓球。進入無錫市少體校后，經(jīng)過短短四個月訓(xùn)練，就拿到市少年組冠軍。在1981年的第36屆世乒賽上，蔡振華獲得男雙冠軍、混雙以及男單亞軍。之后的兩屆世乒賽，他的成績依然耀眼。

(4)

縮放

(5)

(6)

式中:α、β、γ、δ為提升系數(shù),α=1.586 134 342,β=0.052 980 118,γ=0.882 911 075,δ=0.443 506 852;K為縮放系數(shù),K=1.230 174 105;x(n)是圖像輸入的原始像素值;y(n)為一次提升中間變量;H(2n+1)、L(2n)為兩次提升后變量;SH(2n+1)、SL(2n)是濾波最終得到的高頻分量和低頻分量。圖像數(shù)據(jù)輸入后首先分裂成奇數(shù)序列x(2n+1)和偶數(shù)序列x(2n),經(jīng)過兩次提升,再乘以歸一化系數(shù)縮放后得到高頻分量和低頻分量。圖1給出了基于提升的9點序列一維DWT小波變換信號流圖,其中邊沿數(shù)據(jù)計算采用對稱延拓。行濾波器結(jié)構(gòu)將按照翻轉(zhuǎn)公式設(shè)計。

圖1 基于提升的9點序列一維小波變換信號流圖Fig.1 The flow graph of lifting-based 1D-DWT of 9-point sequence

1.2 基于FrWF的提升結(jié)構(gòu)

從翻轉(zhuǎn)結(jié)構(gòu)看出,每個公式都通過一次乘法運算和兩次加法運算完成?；贔rWF算法的提升方案,每個公式都分3次迭代累加完成,輸入數(shù)據(jù)逐行到來,逐次累加更新中間變量并在得到第3次輸入后計算出最終結(jié)果。以首次提升過程為例,當x(0)輸入,更新y(1);當x(1)輸入,更新y(1)和y(0);當x(2)輸入,得到y(tǒng)(1)和y(0)結(jié)果,并更新y(3)和y(2)。以翻轉(zhuǎn)公式實現(xiàn)上述算法時,每行數(shù)據(jù)到來時的運算都有兩次加法,但兩次乘法運算都在奇數(shù)行到來時進行。所以本研究對翻轉(zhuǎn)公式中乘法系數(shù)所在位置進行了調(diào)整,以便在奇數(shù)行或偶數(shù)行分別到來時實現(xiàn)乘法器復(fù)用。首次預(yù)測的公式不變,如式(1)所示,式(2)～(6)調(diào)整系數(shù)后如下式。

首次更新

(7)

二次預(yù)測

(8)

二次更新

(9)

縮放

(10)

(11)

具體的乘法器復(fù)用結(jié)構(gòu)將在下一節(jié)說明。

2 硬件實現(xiàn)架構(gòu)

2.1 二維變換整體架構(gòu)

二維離散小波變換的硬件架構(gòu)如圖2所示。圖像數(shù)據(jù)串行進入行濾波器,三序列分裂后進行一維行變換,行濾波器輸出低頻分量SL和高頻分量SH,雙通道并行進入單輸入的列濾波器完成一維列變換,其輸出經(jīng)過縮放模塊后得到SLL、SLH、SHL、SHH這4個子帶的小波系數(shù)結(jié)果。

圖2 二維離散小波變換硬件整體架構(gòu)Fig.2 Proposed overall architecture of 2-D DWT

2.2 行濾波器結(jié)構(gòu)

行濾波器輸入直接逐行逐點進入,傳統(tǒng)結(jié)構(gòu)一般通過奇偶計數(shù)等方式實現(xiàn)奇偶兩序列的分裂。但預(yù)測和更新過程都是通過3個輸入數(shù)據(jù)計算得到。本文選擇將輸入圖像數(shù)據(jù)分裂成三序列,三輸入序列分裂情況如圖3所示,其中clk為圖像數(shù)據(jù)輸入的時鐘信號,Image_data為輸入的圖像數(shù)據(jù),Data_vld是三路數(shù)據(jù)有效信號,可以用作后續(xù)行濾波器工作的時鐘信號。當Data_vld信號為高電平時,三路輸入數(shù)據(jù)x(2n)、x(2n+1)和x(2n+1)同時進入后續(xù)行濾波器電路,可以在一個時鐘周期內(nèi)完成第一次預(yù)測過程的公式計算。避免了傳統(tǒng)奇偶兩序列輸入時需要等待第3個輸入數(shù)據(jù)所造成的寄存器消耗。文獻[9]提出的三輸入結(jié)構(gòu)是針對列濾波器,反而增加了輸入存儲器。

圖3 三輸入序列分裂示例Fig.3 Three-input sequence split example

三輸入行濾波器電路硬件結(jié)構(gòu)如圖4所示,乘法器延遲與兩個加法器延遲時間之和基本一致,所以將乘法運算和兩次加法運算并行執(zhí)行。在第一級流水線開始前、偶數(shù)序列數(shù)據(jù)輸入后增加了必要的寄存器以滿足時序的正確性。每級流水線都實現(xiàn)一個三輸入二輸出單元,電路中緩沖器由寄存器完成,四級流水線分別計算4個公式結(jié)果。整體一維行濾波器只用到了13個寄存器,比文獻[8]中的一維行變換架構(gòu)減少了8個寄存器。

圖4 一維行濾波器電路結(jié)構(gòu)Fig.4 1-D row filters circuit architecture

2.3 列濾波器結(jié)構(gòu)

行濾波器輸出的SL和SH分量直接進入列濾波器處理。圖5給出了基于FrWF方案列變換首次提升過程數(shù)據(jù)流動,T為當前計算的時鐘周期,xk(n)為第k列的輸入數(shù)據(jù),進入列濾波器的SL、SH分量每行為N/2個數(shù)據(jù)。采用隨機存取存儲器(RAM)存儲中間變量,RAM1和RAM2分別承擔y(2n+1)和y(2n)計算時中間變量的緩存。當奇數(shù)行數(shù)據(jù)到來,RAM輸出存儲的中間變量與當前輸入數(shù)據(jù)進行運算得到新的中間量再次存儲到RAM中;當偶數(shù)行數(shù)據(jù)到來,RAM輸出與當前輸入數(shù)據(jù)進行運算得到y(tǒng)(2n+1)和y(2n),同時RAM重新存儲下次計算所需變量。在運算過程中充分利用雙端口RAM同時讀寫的特點以實現(xiàn)最終結(jié)果計算和中間變量更新。這種迭代累加的計算方式無需等待多行數(shù)據(jù)同時計算,消除了二維變換中的轉(zhuǎn)置存儲器。

圖5 基于FrWF方案列變換首次提升的數(shù)據(jù)流動Fig.5 Data flow of the first lifting step of column transform based on FrWF formula

從圖5可以看出在每個時鐘周期下的計算都只需要一個乘法器和兩個加法器,以此實現(xiàn)在奇數(shù)行和偶數(shù)行數(shù)據(jù)計算時乘法器和加法器的復(fù)用,提高硬件利用率?；跀?shù)據(jù)流動圖,推導(dǎo)出提升步驟的基本處理單元(PE),如圖6所示。單輸入列濾波器電路的關(guān)鍵問題在于通過控制奇偶行標識為乘法器和加法器選擇合適的輸入源和輸出目的地,通過加入多個選擇器來控制整體數(shù)據(jù)路徑。

圖6 列濾波器首次預(yù)測和更新的基本處理單元Fig.6 Processing element of the first prediction and update step in column transform

9/7小波變換兩次預(yù)測和更新過程具有相同的計算數(shù)據(jù)路徑,可以通過級聯(lián)兩個基本處理單元實現(xiàn)。一維列濾波器及縮放模塊架構(gòu)如圖7所示,行濾波器輸出的SH、SL分量兩路并行完成列變換,分別再乘以對應(yīng)歸一化系數(shù)得到二維變換的小波系數(shù),其中K1、K2、K3、K4分別為4個分量對應(yīng)的縮放系數(shù)。在偶數(shù)行到來時輸出SLL和SHL分量,在奇數(shù)行到來時輸出SLH和SHH分量。

圖7 一維列濾波器及縮放模塊架構(gòu)Fig.7 1-D column filter and scaling module architecture

3 硬件開銷分析

表1給出了本文結(jié)構(gòu)與其他提升結(jié)構(gòu)硬件開銷對比結(jié)果,其中乘法器、加法器、寄存器均為16 bit,S為并行度,Tm為一個乘法器延時,Ta為一個加法器延時。與本文相比,文獻[7-10]均利用輸入存儲器或轉(zhuǎn)置存儲器為列變換計算提前存儲數(shù)據(jù)。文獻[11]和文獻[13]設(shè)計的并行架構(gòu)輸入緩存消耗較大。文獻[19]的單輸入二維結(jié)構(gòu)吞吐量較低。綜合對比,本文所提架構(gòu)片上內(nèi)存使用減少了11.1%,硬件資源和吞吐量上均有較大提升。

表1 本文結(jié)構(gòu)與其他提升結(jié)構(gòu)的性能對比Table 1 Performance comparison of the proposed architecture with other lifting architectures

文獻[20]提出的晶體管數(shù)-延時-吞吐量(TDP)避免了約束條件、工藝因素等對不同架構(gòu)效率的影響,可以更加直觀地評估架構(gòu)的硬件效率。RTDP由晶體管總數(shù)RTC、關(guān)鍵路徑延時TCPD以及活動周期數(shù)RACT三者相乘所得。架構(gòu)的RTDP越低,表征對于一個確定的數(shù)據(jù)吞吐量,時間和硬件開銷的綜合需求越低,硬件效率越高。文獻[20]給出了基于陣列乘法器和加法器的晶體管總數(shù)計算方法,8位RAM的晶體管數(shù)為48,16位乘法器、加法器、寄存器、RAM和選擇器的晶體管數(shù)分別為5 084、504、256、96和96。表2給出了N為1 024時各結(jié)構(gòu)的預(yù)估硬件效率的對比,其中η表示本文架構(gòu)相對其他架構(gòu)提升的硬件效率,綜合比較硬件資源和處理速度,本文硬件效率至少提高8.24%,其中文獻[9]采用時鐘錯位方法實現(xiàn)三輸入按列掃描結(jié)構(gòu),控制邏輯更為復(fù)雜。

表2 N為1 024時不同結(jié)構(gòu)硬件效率的對比Table 2 Comparison of hardware efficiency among different architectures with N of 1 024

表3給出了本文結(jié)構(gòu)與其他卷積FrWF結(jié)構(gòu)從內(nèi)存需求和計算周期方面的對比結(jié)果。文獻[14]首次提出了卷積FrWF算法,計算周期達到9N2/2。文獻[17]、[18]分別提出了基于分段的分數(shù)小波濾波(SFrWF)和基于塊的分數(shù)小波濾波(BFrWF)結(jié)構(gòu),其中k為分段數(shù),b為數(shù)據(jù)塊數(shù),兩種結(jié)構(gòu)進一步減少了內(nèi)存需求,但計算周期沒有減少,且增加了片外存儲資源。本文采用提升結(jié)構(gòu),基于行而不基于條帶,無需重復(fù)計算。內(nèi)存需求有所增加,但計算時間只有N2/2,相比其他卷積FrWF結(jié)構(gòu)減少到1/9。v將本文結(jié)構(gòu)在型號為Xilinx Kintex7 XC7K325T的現(xiàn)場可編程門陣列(FPGA)上實現(xiàn),吞吐率達到460 MB/s。在Virtex4 XC4VFX100、Virtex5 XC5VLX110T和Zynq XC7Z045上的實現(xiàn)結(jié)果對比見表4。文獻[21]和[23]利用加法器和移位器代替乘法器以提高時鐘頻率,但消耗更多的邏輯資源和塊隨機存儲器(BRAM)。文獻[22]用到了片外存儲器存儲轉(zhuǎn)置數(shù)據(jù)。本文結(jié)構(gòu)消耗FPGA資源最少,且無需片外存儲,具有明顯的硬件資源優(yōu)勢。

表3與其他FrWF結(jié)構(gòu)的內(nèi)存需求和計算周期對比Table 3 Comparison of memory requirements and calculation cycle with other FrWF structure

表4 FPGA實現(xiàn)結(jié)果對比Table 4 Comparison of FPGA implementation results

4 結(jié) 論

本文提出基于提升公式的FrWF結(jié)構(gòu),并給出新的乘法器復(fù)用計算公式。針對行、列變換分別設(shè)計的兩種一維變換架構(gòu)有效降低了存儲器需求。通過并行和流水線方法實現(xiàn)二維變換硬件架構(gòu),在保證處理速度的前提下將片上內(nèi)存降低到4N。與其他架構(gòu)相比,在計算周期和內(nèi)存資源使用上均有較大改進,硬件效率提高8.24%以上。FPGA實現(xiàn)結(jié)果也表明,本結(jié)構(gòu)具有明顯的硬件資源優(yōu)勢。