基于FPGA的9/7小波變換算法實現(xiàn)

王雨+馬軍山+王華

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

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

引言

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

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

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

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

1.2改進提升算法

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

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

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

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

2.1地址產(chǎn)生模塊地址產(chǎn)生模塊的主要作用是對原始圖像進行邊界延擴。在用提升方法進行DWT時，是要求輸入信號無限長的，但圖像都是有邊界的，也就是說圖像信號是有限的，因此，就需要解決邊界問題。本文選用對稱延擴法，以信號端點為對稱軸，進行邊界延擴。以一組8點數(shù)據(jù)x（0）、x（1）、x（2）、x（3）、x（4）、x（5）、x（6）、x（7）為例，在最后一個高頻系數(shù)x（7）右邊界延擴倒數(shù)第二個數(shù)據(jù)x（6）；在低頻小波系數(shù)x（0）左邊延擴第三、二個數(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行變換模塊行變換模塊即對圖像的每一行分別進行DWT變換，即1-D DWT。DWT變換有兩次提升變換，因為兩次提升變換計算公式相似，本文對第一次提升變換進行研究。通過改進后的計算公式，第一次提升變換的數(shù)據(jù)流圖如圖4所示。根據(jù)該數(shù)據(jù)流圖，本文構(gòu)建了新的流水線結(jié)構(gòu)，如圖5所示。每級流水線通過虛線相隔，并將此定義為一個處理單元，其中包含了2個乘法器和4個加法器。一個完整的9/7小波變換結(jié)構(gòu)包含兩個處理單元。此外，需要2個額外的乘法器完成歸一化步驟。從圖5中可以看出，關(guān)鍵路徑中兩個寄存器之間只有1個乘法器或加法器，和傳統(tǒng)直接映射結(jié)構(gòu)的2個加法器加1個乘法器相比大為減少，因此可以工作在更高的時鐘頻率下。

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

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

2.3列變換模塊

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

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

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

4結(jié)論

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

參考文獻：

[1]孔德照，沈?qū)W舉，林超，等.基于分數(shù)小波變換的雙隨機相位光學圖像加密技術(shù)[J].光學儀器，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]朱斌杰，杜慧敏，楊曉強，等.二維9/7小波變換VLSI設計[J].電子設計工程，2009，17（2）：11-16.

[4]韓建，何學蘭，魏運峰.基于FPGA的FIR數(shù)字濾波器算法的改進及仿真[J].光學儀器，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]鐘廣軍，成禮智，陳火旺.基于提升方法的簡單9/7小波濾波器[J].計算機工程與科學，2003，25（1）：35-55.

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

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

4結(jié)論

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

參考文獻：

[1]孔德照，沈?qū)W舉，林超，等.基于分數(shù)小波變換的雙隨機相位光學圖像加密技術(shù)[J].光學儀器，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]朱斌杰，杜慧敏，楊曉強，等.二維9/7小波變換VLSI設計[J].電子設計工程，2009，17（2）：11-16.

[4]韓建，何學蘭，魏運峰.基于FPGA的FIR數(shù)字濾波器算法的改進及仿真[J].光學儀器，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]鐘廣軍，成禮智，陳火旺.基于提升方法的簡單9/7小波濾波器[J].計算機工程與科學，2003，25（1）：35-55.

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

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

4結(jié)論

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

參考文獻：

[1]孔德照，沈?qū)W舉，林超，等.基于分數(shù)小波變換的雙隨機相位光學圖像加密技術(shù)[J].光學儀器，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]朱斌杰，杜慧敏，楊曉強，等.二維9/7小波變換VLSI設計[J].電子設計工程，2009，17（2）：11-16.

[4]韓建，何學蘭，魏運峰.基于FPGA的FIR數(shù)字濾波器算法的改進及仿真[J].光學儀器，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]鐘廣軍，成禮智，陳火旺.基于提升方法的簡單9/7小波濾波器[J].計算機工程與科學，2003，25（1）：35-55.

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