基于FPGA的Canny算法的硬件加速設(shè)計

0 引言

邊緣檢測是圖像分析過程中非常基礎(chǔ)和重要的研究領(lǐng)域，邊緣提取的好壞將直接影響到后續(xù)處理的準(zhǔn)確性和難易程度。用于邊緣檢測的方法有Roberts，Sobel，Laplace，Canny，PreWitt等眾多算法。在這些算法當(dāng)中，由于具有良好的邊緣檢測能力而使得Canny算法在數(shù)字圖像處理中得到了廣泛的應(yīng)用。然而由于計算量的龐大，處理的時間又比較長，往往很難滿足系統(tǒng)的要求。因為FPGA對數(shù)據(jù)的并行處理，能達(dá)到系統(tǒng)的實時性要求，且開發(fā)的周期短，采用電子設(shè)計的EDA技術(shù)使得開發(fā)、調(diào)試和驗證更為直接和簡單可行。
本文在FPGA基礎(chǔ)上研究Canny算法的邊緣檢測，并對它進(jìn)行了加速改進(jìn)，且在數(shù)據(jù)處理過程中使用了流水線設(shè)計，更深入地挖掘了FPGA在數(shù)據(jù)處理速度中的優(yōu)勢。仿真實驗證明了該方法的可行性，并且實現(xiàn)了良好的實時性。

1 Canny算子的邊緣檢測

邊緣是指在其周圍像素灰度有明顯變化的那些像素的組合，它是具有幅值和方向的矢量，在圖像中表現(xiàn)為灰度的突變。早在1986年Canny就提出了邊緣檢測應(yīng)該滿足的三個最優(yōu)準(zhǔn)則：

(1)重要的邊緣不能丟失，沒有虛假的邊緣，并且誤差檢測率是最小的。
(2)實際邊緣與檢測到的邊緣位置之間的變差最小。
(3)對單一邊緣應(yīng)具有惟一的響應(yīng)。

Canny算子首先使用高斯濾波器來平滑圖像，再計算圖像梯度的強(qiáng)度和方向，接著對梯度圖像進(jìn)行非極大值抑制，最后采用雙閾值方法從候選邊緣點中檢測和連接邊緣。

1．1 Canny算子原理

Canny算子是把邊緣檢測問題轉(zhuǎn)換為函數(shù)極大值的問題加以處理。提取邊緣首先要進(jìn)行高斯濾波，其目的是對原始圖像進(jìn)行平滑處理，以減弱或除去圖像中的噪聲。其高斯濾波的基本思想是將一個對稱的二維高斯函數(shù)與原始的圖像做卷積運(yùn)算，再沿其梯度方向做微分，這樣就形成了一個簡單且有效的方向算子。
f(x，y)為原始圖像，G(x，y)是二維高斯函數(shù)，則平滑濾波后的圖像I(x，y)為：
I(x，y)=G(x，y)*_f(x，y) (1)
定義方向n為邊緣方向的法向方向，則n可由下式得出：

式(3)說明了如何尋找局部最大值，在非極大值抑制之后，還要通過閾值化處理來尋找極大值。先設(shè)定一低閾值Th1，然后選取高閾值Th2≈2*Th1，將極大值抑制后的圖像按Th1，Th2進(jìn)行兩次閾值化處理，得到圖像T1和T2。由于圖像T2是通過高閾值得到的，噪聲和偽邊緣很少，但也造成了一些真實邊緣信息的丟失；而圖像T1保留的邊緣信息相對全面，但是存在一些虛假的邊緣信息。所以以圖像T2為基礎(chǔ)，圖像T1為補(bǔ)充可以獲得相對全面的邊緣圖像。

1．2 算法的模板

本文算法中的高斯濾波器和梯度強(qiáng)度計算時都采用3×3的方形移動窗口，同時梯度強(qiáng)度計算選用Sobel算子。在對圖像進(jìn)行平滑處理時，需要使用高斯模板與原圖像中的像素點值做矩陣的卷積運(yùn)算。本文選取高斯模板的模板系數(shù)為0．062 5，且σ=1。模板如下所示：

式中：h為水平方向上的模板；v為垂直方向上的模板。h與圖像做卷積得到水平方向上的梯度強(qiáng)度Ex；v與圖像做卷積得到垂直方向上的梯度強(qiáng)度Ev。然后通過式(4)計算梯度強(qiáng)度Gr為：
Gr=|Ex|+|Ey| (4)
在FPGA中，卷積的運(yùn)算是通過移位和加法來實現(xiàn)的。對于8位的圖像來說，在移位和加法的運(yùn)算中，由于存在正負(fù)號的運(yùn)算，像素值的大小會被調(diào)整為11位，在最后做完絕對值的加法運(yùn)算后要把11位縮回8位并得到最終的像素導(dǎo)數(shù)值。

2 加速功能設(shè)計

本文對圖像的快速處理采用了流水線技術(shù)。所謂流水線技術(shù)是把規(guī)模較大、層次較多的組合邏輯電路分為幾個級，在每一級插入寄存器組并暫存中間數(shù)據(jù)。對于每個步驟只依賴于前面步驟的運(yùn)算結(jié)果的順序處理來說，流水線技術(shù)能大大地提高系統(tǒng)的性能。在本文的算法中，可將處理過程分為以下幾個任務(wù)：圖像平滑、梯度計算、非極大值抑制和圖像邊緣判定檢測。任務(wù)與任務(wù)之間都是順序執(zhí)行的，即就是說下一任務(wù)的執(zhí)行需要上級任務(wù)的結(jié)果輸出數(shù)據(jù)，因此總的時間花銷為各個任務(wù)所需時間的總和。要使系統(tǒng)使用的處理時間最小，也就是使每個任務(wù)所花費(fèi)的時間最短。

2．1 加速器設(shè)計實現(xiàn)

本文使用了一種能運(yùn)用于高斯平滑濾波和梯度計算的加速器的數(shù)據(jù)路徑結(jié)構(gòu)。由于這兩種計算過程均采用相同大小的方形移動窗口，故其加速設(shè)計具有極大的相似性。對此，這里選取3×3的Sobel模塊來解釋說明。

Sobel的加速數(shù)據(jù)結(jié)構(gòu)如圖1所示。它是一個具有以下功能的流水線：先從原始的圖像中讀取像素值存入圖中右方的3組12寄存器中，數(shù)據(jù)流過中間的3×3的乘法器陣列，即像素值與模板值做乘法運(yùn)算；然后向下流過加法器，在加法器中完成和運(yùn)算，至此實現(xiàn)了像素值與模板的卷積運(yùn)算，之后到達(dá)Ex和Ey寄存器，通過絕對值電路和加法器(實現(xiàn)式(4))到達(dá)寄存器，最終流入最下面的寄存器。圖中負(fù)號表示取反，數(shù)值1和2表示右移的位數(shù)。
為使得加速器能夠有序地按照確定的步驟進(jìn)行，本文使用了有限狀態(tài)機(jī)。如圖2所示為加速器的簡單狀態(tài)轉(zhuǎn)換圖。在加速器的執(zhí)行過程中，當(dāng)檢測到3組寄存器中的數(shù)據(jù)為空時，讀信號使能re_en置1，自動讀入新的3組數(shù)據(jù)；且在下方寄存器存儲滿時，寫信號使能wr_en置1，數(shù)據(jù)被提取進(jìn)行寫操作。

在加速器的執(zhí)行過程中，像素每4個為一組進(jìn)行讀寫，這樣在高速處理過程中大大縮減了對相同像素點的多次重復(fù)讀取而浪費(fèi)的時間；同時，在處理過程中不需要在處理每個像素點時都對其鄰域的8個像素點更新，這樣節(jié)省了大量的讀取時間；并且由于FPGA的并行特性，像素的讀、移位及寫操作和乘法器的運(yùn)算是同時進(jìn)行的，使得處理速度有一定的提升。

2．2 加速器的地址產(chǎn)生

在系統(tǒng)的連續(xù)處理過程當(dāng)中，加速器沒有專門的等待時間用來對數(shù)據(jù)進(jìn)行讀取和存儲，這兩類運(yùn)算都是并行進(jìn)行的。因此加速器需要具有自動選通的讀／寫地址電路。對于一幅512×512圖像來說，從偏移值0開始計數(shù)，一次加1，以便于從內(nèi)存中讀一組4個像素值，把偏移地址和基地址加起來形成前一行的像素地址，把它加上512／4就形成當(dāng)前行的讀地址，再加上1 024／4就形成了下一行的讀地址。對于寫地址來說，從偏移值512／4開始計數(shù)，一次加1形成每次的寫地址。地址發(fā)生器的部分代碼如下：


3 Canny算法加速設(shè)計

為了使得整個算法的計算速度得到提高，使算法既滿足高速要求也不會耗費(fèi)大量的硬件資源，本文對高斯濾波和梯度強(qiáng)度計算兩個任務(wù)模塊做了加速設(shè)計組合，流程圖如圖3所示。

高斯濾波器采用與Sobel加速器相似的設(shè)計原理，具有流水線的加速功能。圖中RAM是FPGA中自帶的Block RAM塊，其大小配置為僅存儲當(dāng)前被處理圖像的三行像素值，對于512×512的8位圖像來說RAM應(yīng)配置為512×3×8 b。因為高斯濾波的存儲和Sobel加速器在讀取的時候都是每4個像素點即32 b數(shù)據(jù)來進(jìn)行，所以配置為32位寬的同時讀寫操作的雙口RAM。

梯度運(yùn)算之后，進(jìn)行非極大值的抑制，在非極大值抑制之前需要計算梯度的方向。梯度方向的計算分為四個方向：水平、垂直、45°方向及135°方向，且每個方向上都包含兩個45°的范圍。通過Ex和Ey的比值及正負(fù)可以確定梯度方向落在上面規(guī)定的四個方向之一。判斷四個方向的具體如下：

在FPGA中，直接做除法運(yùn)算是很復(fù)雜的過程；為了減少資源的開銷，把式(5)～式(8)中的除法變換成乘法，再做比較來判斷梯度的方向。對于tan 22．5°和tan 67．5°做如下處理：

非極大值的抑制在系統(tǒng)中通過選擇器和比較器來實現(xiàn)。根據(jù)輸入的梯度值和梯度方向，用非極大值抑制條件(式(5)～(8))和高低閾值條件對輸出的數(shù)據(jù)進(jìn)行比較選擇，強(qiáng)邊緣點輸出為255，弱邊緣點輸出為0。由于硬件流水線的特點，邊界像素的計算結(jié)果是無效的，所以將邊界上的行列都置為0。重復(fù)以上步驟，直到整幅圖像掃描完成，最終得出邊緣圖像。

4 系統(tǒng)驗證和結(jié)果分析

為了能清楚直觀地驗證加速的加速效果，本文在系統(tǒng)平臺上對相同的圖像分別用加速／未加速的系統(tǒng)做處理，記錄相應(yīng)時間并比較。

本文采用的驗證系統(tǒng)平臺以Altera公司CycloneⅡ系列中的EP2C20F484C8芯片為核心搭建而成，如圖4所示。在驗證系統(tǒng)設(shè)計中實現(xiàn)一個串口用來和PC機(jī)中的上位機(jī)通信，把處理完后的數(shù)據(jù)經(jīng)過串口傳輸給上位機(jī)。數(shù)據(jù)在串口的傳輸過程中的延遲時間是固定的，故從上位機(jī)接收到第一個數(shù)據(jù)到最后一個數(shù)據(jù)的時間差即為一幀圖像處理所花費(fèi)的時間。

本文選取了不同大小的3幅圖片做實驗驗證，系統(tǒng)時鐘頻率為100 MHz。其處理時間結(jié)果如表1所示，系統(tǒng)1為有加速功能的系統(tǒng)，系統(tǒng)2為未經(jīng)加速的系統(tǒng)。

由表1可見，經(jīng)過加速改進(jìn)后的系統(tǒng)在處理時間上得到了很大的節(jié)約，隨圖像尺寸變大，總的節(jié)約時間顯然是增加的；且經(jīng)計算知：當(dāng)尺寸變4倍(表1第2列256圖與第3列512圖)，節(jié)約時間大約增加3．9倍；640×480圖比512×512圖尺寸大1．17倍，節(jié)約時間是1．23倍，實際結(jié)果與理論計算相吻合。隨著圖像尺寸的增加，節(jié)約時間亦按比例增加，因此該加速功能在處理大容量高速的圖像時具有更大的優(yōu)勢和廣闊的應(yīng)用前景。

圖5為一幅在FPGA中經(jīng)過加速器系統(tǒng)處理后使用Matlab呈現(xiàn)的邊緣圖像。該算法處理的圖像結(jié)果基本得到所有的邊緣信息，完全能滿足應(yīng)用需求。

5 結(jié)論

本文提出并實現(xiàn)了一種基于FPGA的加速Canny算法邊緣檢測系統(tǒng)。該系統(tǒng)充分發(fā)揮和利用FPGA的優(yōu)良并行處理能力及流水線技術(shù)，從而實現(xiàn)功能加速。

在加速過程中通過狀態(tài)機(jī)的控制作用能使模板的運(yùn)算處理和數(shù)據(jù)的讀／寫操作得以同時進(jìn)行，一定程度上節(jié)約了因大量的讀／寫數(shù)據(jù)操作而占用的時間。此系統(tǒng)充分利用了FPGA中的硬件資源，大大提高了系統(tǒng)算法的運(yùn)算效率，且設(shè)計結(jié)構(gòu)較為靈活。最終通過邊緣檢測實驗，驗證了設(shè)計的正確性。