基于FPGA的Canny算法的硬件加速設計

0 引言

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

1 Canny算子的邊緣檢測

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

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

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

1．1 Canny算子原理

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

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

1．2 算法的模板

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

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

2 加速功能設計

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

2．1 加速器設計實現

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

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

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

2．2 加速器的地址產生

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


3 Canny算法加速設計

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

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

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

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

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

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

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

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

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

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

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

5 結論

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

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