王雨+馬軍山+王華

摘要： 提出了一種基于現(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）的高速9/7二維離散小波變換（2-D DWT）設(shè)計(jì)。在實(shí)現(xiàn)一維離散小波變換（1-D DWT）時(shí)采用多級(jí)流水線(xiàn)技術(shù)，并使用了改進(jìn)的提升算法。同時(shí)，使用正則符號(hào)編碼（CSD編碼）和優(yōu)化的移位加法操作實(shí)現(xiàn)乘法器，使其便于通過(guò)硬件實(shí)現(xiàn)，且加快了處理速度。在進(jìn)行二維離散小波變換時(shí)采用改進(jìn)的基于行的結(jié)構(gòu)，只需完成3行行變換即可開(kāi)始列變換，減少了系統(tǒng)資源的占用。設(shè)計(jì)通過(guò)MATLAB與ModelSim聯(lián)合仿真，可以穩(wěn)定運(yùn)行在60 MHz時(shí)鐘頻率下，完全能夠滿(mǎn)足高速圖像實(shí)時(shí)處理的要求。

關(guān)鍵詞： 離散小波變換（DWT）； 提升算法； 現(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）

引言

小波變換具有多分辨率分析特性和良好的時(shí)頻特性，因而廣泛應(yīng)用于圖像編碼、模式識(shí)別、視頻處理等領(lǐng)域[1]。

在實(shí)時(shí)的圖像處理系統(tǒng)中，由于離散小波變換（DWT）需要的運(yùn)算量較大，軟件實(shí)現(xiàn)有時(shí)無(wú)法滿(mǎn)足實(shí)時(shí)性要求，這使得人們對(duì)DWT的硬件實(shí)現(xiàn)產(chǎn)生了極大的興趣。近年來(lái)，許多作者對(duì)硬件實(shí)現(xiàn)DWT進(jìn)行了研究。文獻(xiàn)[2]中提出了一種基于提升算法的直接映射結(jié)構(gòu)。該結(jié)構(gòu)簡(jiǎn)單明了，易于硬件實(shí)現(xiàn)，但關(guān)鍵路徑延遲較高。文獻(xiàn)[3]中提出了一種Mesh結(jié)構(gòu)，可以行列變換同時(shí)進(jìn)行，從而達(dá)到較高的處理速度，但需要消耗較多的硬件資源。本文采用模塊化設(shè)計(jì)思想，在1-D DWT中使用改進(jìn)的提升算法和多極流水線(xiàn)設(shè)計(jì)以提高系統(tǒng)運(yùn)行速度，在2-D DWT中使用基于行的結(jié)構(gòu)，以減少緩存器的使用?，F(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）具有設(shè)計(jì)周期短，靈活性好，集成程度高，處理速度快等特點(diǎn)[4]，被廣泛應(yīng)用在數(shù)字信號(hào)處理領(lǐng)域。因此，本文基于A(yíng)ltera公司的FPGA芯片進(jìn)行設(shè)計(jì)，并用Quartus II、ModelSim等軟件進(jìn)行綜合、仿真。

1基于提升算法的離散小波變換

1.1提升算法的基本原理基于提升算法的離散小波變換結(jié)構(gòu)如圖1所示，通常由一個(gè)分裂環(huán)節(jié)、一個(gè)預(yù)測(cè)環(huán)節(jié)和一個(gè)更新環(huán)節(jié)構(gòu)成。

1.2改進(jìn)提升算法

在流水線(xiàn)設(shè)計(jì)方法中，關(guān)鍵路徑在兩個(gè)寄存器之間的傳播延遲中占主導(dǎo)地位。為了減少該延遲，使系統(tǒng)可以運(yùn)行在更高的頻率之下，提出了一種針對(duì)DWT的快速流水線(xiàn)結(jié)構(gòu)[5]。由于在直接映射的硬件結(jié)構(gòu)中，傳播延遲主要存在于預(yù)測(cè)和更新步驟，本文將式（3）代入式（4）之中，將預(yù)測(cè)和更新合并成一個(gè)表達(dá)式。由此，可以使得流水線(xiàn)中的每一級(jí)只有一次加法或乘法。

s0i+（βd1i-1）+（βd1i）（9）在式（9）中，第一次提升步驟的低通信號(hào)s0i可以直接得到，而高通信號(hào)d1i則乘以了一個(gè)因子β。然后，將式（5）代入式（6），作為第二次提升步驟。

2基于FPGA的9/7小波變換的實(shí)現(xiàn)

本設(shè)計(jì)使用Verilog HDL語(yǔ)言實(shí)現(xiàn)，其系統(tǒng)結(jié)構(gòu)如圖2所示，其流程圖如圖3所示。

2.1地址產(chǎn)生模塊地址產(chǎn)生模塊的主要作用是對(duì)原始圖像進(jìn)行邊界延擴(kuò)。在用提升方法進(jìn)行DWT時(shí)，是要求輸入信號(hào)無(wú)限長(zhǎng)的，但圖像都是有邊界的，也就是說(shuō)圖像信號(hào)是有限的，因此，就需要解決邊界問(wèn)題。本文選用對(duì)稱(chēng)延擴(kuò)法，以信號(hào)端點(diǎn)為對(duì)稱(chēng)軸，進(jìn)行邊界延擴(kuò)。以一組8點(diǎn)數(shù)據(jù)x（0）、x（1）、x（2）、x（3）、x（4）、x（5）、x（6）、x（7）為例，在最后一個(gè)高頻系數(shù)x（7）右邊界延擴(kuò)倒數(shù)第二個(gè)數(shù)據(jù)x（6）；在低頻小波系數(shù)x（0）左邊延擴(kuò)第三、二個(gè)數(shù)據(jù)x（2）、x（1），使序列變成x（2）、x（1）、x（0）、x（1）、x（2）、x（3）、x（4）、x（5）、x（6）、x（7）、x（6）。在地址產(chǎn)生模塊中，就是按如上順序產(chǎn)生地址。

2.2行變換模塊行變換模塊即對(duì)圖像的每一行分別進(jìn)行DWT變換，即1-D DWT。DWT變換有兩次提升變換，因?yàn)閮纱翁嵘儞Q計(jì)算公式相似，本文對(duì)第一次提升變換進(jìn)行研究。通過(guò)改進(jìn)后的計(jì)算公式，第一次提升變換的數(shù)據(jù)流圖如圖4所示。根據(jù)該數(shù)據(jù)流圖，本文構(gòu)建了新的流水線(xiàn)結(jié)構(gòu)，如圖5所示。每級(jí)流水線(xiàn)通過(guò)虛線(xiàn)相隔，并將此定義為一個(gè)處理單元，其中包含了2個(gè)乘法器和4個(gè)加法器。一個(gè)完整的9/7小波變換結(jié)構(gòu)包含兩個(gè)處理單元。此外，需要2個(gè)額外的乘法器完成歸一化步驟。從圖5中可以看出，關(guān)鍵路徑中兩個(gè)寄存器之間只有1個(gè)乘法器或加法器，和傳統(tǒng)直接映射結(jié)構(gòu)的2個(gè)加法器加1個(gè)乘法器相比大為減少，因此可以工作在更高的時(shí)鐘頻率下。

在行變換模塊中，使用到了乘法器，而由于傳統(tǒng)乘法器消耗硬件資源多，且耗時(shí)較長(zhǎng)，因此，可以改用移位加法來(lái)實(shí)現(xiàn)常數(shù)乘法。同時(shí)，采用正則符號(hào)編碼（CSD編碼）來(lái)表示濾波器的系數(shù)[7]，可以減少移位加法器的數(shù)量。各濾波器系數(shù)的CSD編碼如表1所示。圖6CSD乘法器結(jié)構(gòu)圖

Fig.6The CSD multiplier structure diagram如圖6所示，以系數(shù)βα為例說(shuō)明CSD編碼實(shí)現(xiàn)乘法操作的方式。圖6（a）為系數(shù)βα的CSD編碼的直接表示，其中表示左移；為了減少硬件資源的消耗，可以對(duì)表達(dá)式中具有相似次數(shù)的乘積相進(jìn)行組合相加，如2-3-2-5可以由x3-x5改寫(xiě)成（x1-x3）2。同時(shí)，可以引入流水線(xiàn)結(jié)構(gòu)，以增加系統(tǒng)吞吐量，改進(jìn)結(jié)構(gòu)如圖6（b）所示。

2.3列變換模塊

因?yàn)閳D像都是二維的，所以在完成行變換后，還需要對(duì)圖像的每一列進(jìn)行DWT變換，即2-D DWT。目前，主要實(shí)現(xiàn)方法有兩種：可分離與不可分離結(jié)構(gòu)?？煞蛛x結(jié)構(gòu)是指重復(fù)使用1-D DWT以實(shí)現(xiàn)2-D DWT；不可分離結(jié)構(gòu)是指將圖像分成幾個(gè)子圖像，對(duì)各個(gè)子圖像同時(shí)進(jìn)行行列DWT變換，但這種方法大為增加硬件消耗。圖7列變換數(shù)據(jù)組織

Fig.7The column transform data organization本文選擇第一種方法。對(duì)于可分離結(jié)構(gòu)，最常見(jiàn)的是先進(jìn)行行變換，待行變換完成后再進(jìn)行列變換，這樣做的好處是實(shí)現(xiàn)簡(jiǎn)單，但需要大量額外存儲(chǔ)空間對(duì)行變換結(jié)果進(jìn)行緩存。同時(shí)，因?yàn)樾凶儞Q完成后才開(kāi)始列變換，這會(huì)使系統(tǒng)產(chǎn)生延遲。因此，本文使用基于行的結(jié)構(gòu)，即在行變換的同時(shí)進(jìn)行列變換。因?yàn)榈玫揭唤MDWT輸出需要9個(gè)輸入數(shù)據(jù)，所以在得到9行行變換結(jié)果后，才可以進(jìn)行列變換。本文提出了一種改進(jìn)方案，如圖7所示，只需要完成3行行變換，即可開(kāi)始列變換，從而極大地減少了存儲(chǔ)器的消耗與系統(tǒng)的延遲。如圖7所示，列變換模塊的具體步驟為：在T2時(shí)刻，讀取緩存器1中的計(jì)算上一組數(shù)據(jù)時(shí)得到的寄存器r3中的值。在T3時(shí)刻，將寄存器r3中的值存入緩存器1中以供下一組數(shù)據(jù)使用。在T5時(shí)刻，讀取緩存器2中的計(jì)算上一組數(shù)據(jù)時(shí)得到的寄存器r9中的值。在T6時(shí)刻，將寄存器r9中的值存入到緩存器2中，同時(shí)，讀取緩存器3中計(jì)算上一組數(shù)據(jù)時(shí)得到的寄存器r11中的值。在T7時(shí)刻，即可得到最終輸出s2i，δd2i了；同時(shí)將寄存器r11中的值存入緩存器3中。本文中使用了3個(gè)緩存器，可以通過(guò)FPGA上的FIFO來(lái)實(shí)現(xiàn)。3系統(tǒng)仿真與驗(yàn)證本文采用ModelSim和MATLAB聯(lián)合仿真進(jìn)行驗(yàn)證，先編寫(xiě)testbench讀取數(shù)據(jù)，并在ModelSim中仿真，最后將仿真結(jié)果送入MATLAB進(jìn)行圖像重構(gòu)。其中，行變換模塊的仿真波形如圖8所示。圖中ZHIA為輸入數(shù)據(jù)，q為行變換結(jié)果。q經(jīng)過(guò)25 h的潛伏期后開(kāi)始輸出有效值，將其與直接使用式（9）、式（10）計(jì)算輸入數(shù)據(jù)所得結(jié)果進(jìn)行比較，可發(fā)現(xiàn)兩者相同。這表明了設(shè)計(jì)的正確性。

Fig.9The test results在MATLAB中將列變換模塊處理后的數(shù)據(jù)進(jìn)行重構(gòu)，所得結(jié)果如圖9所示。從圖9（b）中可以看出，左上角低頻分量包含了圖像的主要信息，而右上角、左下角、右下角的高頻水平、垂直、對(duì)角線(xiàn)分量則包含了原圖在水平、垂直和對(duì)角線(xiàn)部分的邊緣信息。經(jīng)過(guò)試驗(yàn)，本設(shè)計(jì)可以穩(wěn)定運(yùn)行在60 MHz下，對(duì)800×600的圖像來(lái)說(shuō)，處理速度為125幀/s，完全可以達(dá)到高速圖像處理的要求。本設(shè)計(jì)使用的LEs數(shù)為745，這對(duì)于當(dāng)今擁有幾千至上萬(wàn)LEs的FPGA來(lái)說(shuō)，所消耗的資源是很少的。

4結(jié)論

本文設(shè)計(jì)了一種新的基于FPGA的高速9/7提升小波變換結(jié)構(gòu)，通過(guò)使用流水線(xiàn)結(jié)構(gòu)，改進(jìn)提升算法，使用CSD乘法器，滿(mǎn)足了系統(tǒng)高速運(yùn)行的要求。在二維小波變換中，采用改進(jìn)的基于行的變換方法，減少了存儲(chǔ)空間的消耗及系統(tǒng)延遲。

參考文獻(xiàn)：

[1]孔德照，沈?qū)W舉，林超，等.基于分?jǐn)?shù)小波變換的雙隨機(jī)相位光學(xué)圖像加密技術(shù)[J].光學(xué)儀器，2013，35（4）：17-21.

[2]SILVA S V，BAMPI S.Area and throughput trade-offs in the design of pipelined discrete wavelet transform architectures[J].IEEE Design，Automation and Test in Europe，2005，3：32-37.

[3]朱斌杰，杜慧敏，楊曉強(qiáng)，等.二維9/7小波變換VLSI設(shè)計(jì)[J].電子設(shè)計(jì)工程，2009，17（2）：11-16.

[4]韓建，何學(xué)蘭，魏運(yùn)峰.基于FPGA的FIR數(shù)字濾波器算法的改進(jìn)及仿真[J].光學(xué)儀器，2013，35（5）：56-59.

[5]WU B.F，LIN C.F.A rescheduling and fast pipeline VLSI architecture for lifting-based discrete wavelet transform[C].Proceedings of the 2003 International Symposium on Circuits and Systems，2003，2：732-735.

[6]鐘廣軍，成禮智，陳火旺.基于提升方法的簡(jiǎn)單9/7小波濾波器[J].計(jì)算機(jī)工程與科學(xué)，2003，25（1）：35-55.

[7]熊承義，田金文，柳建.基于CSD編碼的高速乘法器IP設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2003（31）：38-40.

Fig.9The test results在MATLAB中將列變換模塊處理后的數(shù)據(jù)進(jìn)行重構(gòu)，所得結(jié)果如圖9所示。從圖9（b）中可以看出，左上角低頻分量包含了圖像的主要信息，而右上角、左下角、右下角的高頻水平、垂直、對(duì)角線(xiàn)分量則包含了原圖在水平、垂直和對(duì)角線(xiàn)部分的邊緣信息。經(jīng)過(guò)試驗(yàn)，本設(shè)計(jì)可以穩(wěn)定運(yùn)行在60 MHz下，對(duì)800×600的圖像來(lái)說(shuō)，處理速度為125幀/s，完全可以達(dá)到高速圖像處理的要求。本設(shè)計(jì)使用的LEs數(shù)為745，這對(duì)于當(dāng)今擁有幾千至上萬(wàn)LEs的FPGA來(lái)說(shuō)，所消耗的資源是很少的。

4結(jié)論

本文設(shè)計(jì)了一種新的基于FPGA的高速9/7提升小波變換結(jié)構(gòu)，通過(guò)使用流水線(xiàn)結(jié)構(gòu)，改進(jìn)提升算法，使用CSD乘法器，滿(mǎn)足了系統(tǒng)高速運(yùn)行的要求。在二維小波變換中，采用改進(jìn)的基于行的變換方法，減少了存儲(chǔ)空間的消耗及系統(tǒng)延遲。

參考文獻(xiàn)：

[1]孔德照，沈?qū)W舉，林超，等.基于分?jǐn)?shù)小波變換的雙隨機(jī)相位光學(xué)圖像加密技術(shù)[J].光學(xué)儀器，2013，35（4）：17-21.

[2]SILVA S V，BAMPI S.Area and throughput trade-offs in the design of pipelined discrete wavelet transform architectures[J].IEEE Design，Automation and Test in Europe，2005，3：32-37.

[3]朱斌杰，杜慧敏，楊曉強(qiáng)，等.二維9/7小波變換VLSI設(shè)計(jì)[J].電子設(shè)計(jì)工程，2009，17（2）：11-16.

[4]韓建，何學(xué)蘭，魏運(yùn)峰.基于FPGA的FIR數(shù)字濾波器算法的改進(jìn)及仿真[J].光學(xué)儀器，2013，35（5）：56-59.

[5]WU B.F，LIN C.F.A rescheduling and fast pipeline VLSI architecture for lifting-based discrete wavelet transform[C].Proceedings of the 2003 International Symposium on Circuits and Systems，2003，2：732-735.

[6]鐘廣軍，成禮智，陳火旺.基于提升方法的簡(jiǎn)單9/7小波濾波器[J].計(jì)算機(jī)工程與科學(xué)，2003，25（1）：35-55.

[7]熊承義，田金文，柳建.基于CSD編碼的高速乘法器IP設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2003（31）：38-40.

Fig.9The test results在MATLAB中將列變換模塊處理后的數(shù)據(jù)進(jìn)行重構(gòu)，所得結(jié)果如圖9所示。從圖9（b）中可以看出，左上角低頻分量包含了圖像的主要信息，而右上角、左下角、右下角的高頻水平、垂直、對(duì)角線(xiàn)分量則包含了原圖在水平、垂直和對(duì)角線(xiàn)部分的邊緣信息。經(jīng)過(guò)試驗(yàn)，本設(shè)計(jì)可以穩(wěn)定運(yùn)行在60 MHz下，對(duì)800×600的圖像來(lái)說(shuō)，處理速度為125幀/s，完全可以達(dá)到高速圖像處理的要求。本設(shè)計(jì)使用的LEs數(shù)為745，這對(duì)于當(dāng)今擁有幾千至上萬(wàn)LEs的FPGA來(lái)說(shuō)，所消耗的資源是很少的。

4結(jié)論

本文設(shè)計(jì)了一種新的基于FPGA的高速9/7提升小波變換結(jié)構(gòu)，通過(guò)使用流水線(xiàn)結(jié)構(gòu)，改進(jìn)提升算法，使用CSD乘法器，滿(mǎn)足了系統(tǒng)高速運(yùn)行的要求。在二維小波變換中，采用改進(jìn)的基于行的變換方法，減少了存儲(chǔ)空間的消耗及系統(tǒng)延遲。

參考文獻(xiàn)：

[1]孔德照，沈?qū)W舉，林超，等.基于分?jǐn)?shù)小波變換的雙隨機(jī)相位光學(xué)圖像加密技術(shù)[J].光學(xué)儀器，2013，35（4）：17-21.

[2]SILVA S V，BAMPI S.Area and throughput trade-offs in the design of pipelined discrete wavelet transform architectures[J].IEEE Design，Automation and Test in Europe，2005，3：32-37.

[3]朱斌杰，杜慧敏，楊曉強(qiáng)，等.二維9/7小波變換VLSI設(shè)計(jì)[J].電子設(shè)計(jì)工程，2009，17（2）：11-16.

[4]韓建，何學(xué)蘭，魏運(yùn)峰.基于FPGA的FIR數(shù)字濾波器算法的改進(jìn)及仿真[J].光學(xué)儀器，2013，35（5）：56-59.

[5]WU B.F，LIN C.F.A rescheduling and fast pipeline VLSI architecture for lifting-based discrete wavelet transform[C].Proceedings of the 2003 International Symposium on Circuits and Systems，2003，2：732-735.

[6]鐘廣軍，成禮智，陳火旺.基于提升方法的簡(jiǎn)單9/7小波濾波器[J].計(jì)算機(jī)工程與科學(xué)，2003，25（1）：35-55.

[7]熊承義，田金文，柳建.基于CSD編碼的高速乘法器IP設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2003（31）：38-40.