摘要：由于Canny算法自身的復(fù)雜性，使得其做邊緣檢測(cè)的處理時(shí)間較長(zhǎng)。針對(duì)這個(gè)問題，提出和實(shí)現(xiàn)了一種Canny算法的硬件加速功能。加速功能的設(shè)計(jì)是以FPGA為硬件基礎(chǔ)，并采用了流水線技術(shù)來對(duì)系統(tǒng)的結(jié)構(gòu)改進(jìn)和優(yōu)化。最后通過對(duì)有加速器和無加速器的系統(tǒng)分別做圖像處理，并對(duì)統(tǒng)計(jì)時(shí)間對(duì)比分析。結(jié)果表明經(jīng)過加速改進(jìn)的系統(tǒng)相對(duì)節(jié)約了處理時(shí)間，并能實(shí)時(shí)高效地處理復(fù)雜圖像的邊緣。
關(guān)鍵詞：Canny算子；邊緣檢測(cè)；加速器；現(xiàn)場(chǎng)可編程門陣列

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

1 Canny算子的邊緣檢測(cè)
    邊緣是指在其周圍像素灰度有明顯變化的那些像素的組合，它是具有幅值和方向的矢量，在圖像中表現(xiàn)為灰度的突變。早在1986年Canny就提出了邊緣檢測(cè)應(yīng)該滿足的三個(gè)最優(yōu)準(zhǔn)則：
    (1)重要的邊緣不能丟失，沒有虛假的邊緣，并且誤差檢測(cè)率是最小的。
    (2)實(shí)際邊緣與檢測(cè)到的邊緣位置之間的變差最小。
    (3)對(duì)單一邊緣應(yīng)具有惟一的響應(yīng)。
    Canny算子首先使用高斯濾波器來平滑圖像，再計(jì)算圖像梯度的強(qiáng)度和方向，接著對(duì)梯度圖像進(jìn)行非極大值抑制，最后采用雙閾值方法從候選邊緣點(diǎn)中檢測(cè)和連接邊緣。
1．1 Canny算子原理
    Canny算子是把邊緣檢測(cè)問題轉(zhuǎn)換為函數(shù)極大值的問題加以處理。提取邊緣首先要進(jìn)行高斯濾波，其目的是對(duì)原始圖像進(jìn)行平滑處理，以減弱或除去圖像中的噪聲。其高斯濾波的基本思想是將一個(gè)對(duì)稱的二維高斯函數(shù)與原始的圖像做卷積運(yùn)算，再沿其梯度方向做微分，這樣就形成了一個(gè)簡(jiǎ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是通過高閾值得到的，噪聲和偽邊緣很少，但也造成了一些真實(shí)邊緣信息的丟失；而圖像T1保留的邊緣信息相對(duì)全面，但是存在一些虛假的邊緣信息。所以以圖像T2為基礎(chǔ)，圖像T1為補(bǔ)充可以獲得相對(duì)全面的邊緣圖像。
1．2 算法的模板
    本文算法中的高斯濾波器和梯度強(qiáng)度計(jì)算時(shí)都采用3×3的方形移動(dòng)窗口，同時(shí)梯度強(qiáng)度計(jì)算選用Sobel算子。在對(duì)圖像進(jìn)行平滑處理時(shí)，需要使用高斯模板與原圖像中的像素點(diǎn)值做矩陣的卷積運(yùn)算。本文選取高斯模板的模板系數(shù)為0．062 5，且σ=1。模板如下所示：

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

2 加速功能設(shè)計(jì)
    本文對(duì)圖像的快速處理采用了流水線技術(shù)。所謂流水線技術(shù)是把規(guī)模較大、層次較多的組合邏輯電路分為幾個(gè)級(jí)，在每一級(jí)插入寄存器組并暫存中間數(shù)據(jù)。對(duì)于每個(gè)步驟只依賴于前面步驟的運(yùn)算結(jié)果的順序處理來說，流水線技術(shù)能大大地提高系統(tǒng)的性能。在本文的算法中，可將處理過程分為以下幾個(gè)任務(wù)：圖像平滑、梯度計(jì)算、非極大值抑制和圖像邊緣判定檢測(cè)。任務(wù)與任務(wù)之間都是順序執(zhí)行的，即就是說下一任務(wù)的執(zhí)行需要上級(jí)任務(wù)的結(jié)果輸出數(shù)據(jù)，因此總的時(shí)間花銷為各個(gè)任務(wù)所需時(shí)間的總和。要使系統(tǒng)使用的處理時(shí)間最小，也就是使每個(gè)任務(wù)所花費(fèi)的時(shí)間最短。
2．1 加速器設(shè)計(jì)實(shí)現(xiàn)
    本文使用了一種能運(yùn)用于高斯平滑濾波和梯度計(jì)算的加速器的數(shù)據(jù)路徑結(jié)構(gòu)。由于這兩種計(jì)算過程均采用相同大小的方形移動(dòng)窗口，故其加速設(shè)計(jì)具有極大的相似性。對(duì)此，這里選取3×3的Sobel模塊來解釋說明。

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

    在加速器的執(zhí)行過程中，像素每4個(gè)為一組進(jìn)行讀寫，這樣在高速處理過程中大大縮減了對(duì)相同像素點(diǎn)的多次重復(fù)讀取而浪費(fèi)的時(shí)間；同時(shí)，在處理過程中不需要在處理每個(gè)像素點(diǎn)時(shí)都對(duì)其鄰域的8個(gè)像素點(diǎn)更新，這樣節(jié)省了大量的讀取時(shí)間；并且由于FPGA的并行特性，像素的讀、移位及寫操作和乘法器的運(yùn)算是同時(shí)進(jìn)行的，使得處理速度有一定的提升。
2．2 加速器的地址產(chǎn)生
    在系統(tǒng)的連續(xù)處理過程當(dāng)中，加速器沒有專門的等待時(shí)間用來對(duì)數(shù)據(jù)進(jìn)行讀取和存儲(chǔ)，這兩類運(yùn)算都是并行進(jìn)行的。因此加速器需要具有自動(dòng)選通的讀／寫地址電路。對(duì)于一幅512×512圖像來說，從偏移值0開始計(jì)數(shù)，一次加1，以便于從內(nèi)存中讀一組4個(gè)像素值，把偏移地址和基地址加起來形成前一行的像素地址，把它加上512／4就形成當(dāng)前行的讀地址，再加上1 024／4就形成了下一行的讀地址。對(duì)于寫地址來說，從偏移值512／4開始計(jì)數(shù)，一次加1形成每次的寫地址。地址發(fā)生器的部分代碼如下：
   

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

    高斯濾波器采用與Sobel加速器相似的設(shè)計(jì)原理，具有流水線的加速功能。圖中RAM是FPGA中自帶的Block RAM塊，其大小配置為僅存儲(chǔ)當(dāng)前被處理圖像的三行像素值，對(duì)于512×512的8位圖像來說RAM應(yīng)配置為512×3×8 b。因?yàn)楦咚篂V波的存儲(chǔ)和Sobel加速器在讀取的時(shí)候都是每4個(gè)像素點(diǎn)即32 b數(shù)據(jù)來進(jìn)行，所以配置為32位寬的同時(shí)讀寫操作的雙口RAM。
    梯度運(yùn)算之后，進(jìn)行非極大值的抑制，在非極大值抑制之前需要計(jì)算梯度的方向。梯度方向的計(jì)算分為四個(gè)方向：水平、垂直、45°方向及135°方向，且每個(gè)方向上都包含兩個(gè)45°的范圍。通過Ex和Ey的比值及正負(fù)可以確定梯度方向落在上面規(guī)定的四個(gè)方向之一。判斷四個(gè)方向的具體如下：
   
    在FPGA中，直接做除法運(yùn)算是很復(fù)雜的過程；為了減少資源的開銷，把式(5)～式(8)中的除法變換成乘法，再做比較來判斷梯度的方向。對(duì)于tan 22．5°和tan 67．5°做如下處理：
   
    非極大值的抑制在系統(tǒng)中通過選擇器和比較器來實(shí)現(xiàn)。根據(jù)輸入的梯度值和梯度方向，用非極大值抑制條件(式(5)～(8))和高低閾值條件對(duì)輸出的數(shù)據(jù)進(jìn)行比較選擇，強(qiáng)邊緣點(diǎn)輸出為255，弱邊緣點(diǎn)輸出為0。由于硬件流水線的特點(diǎn)，邊界像素的計(jì)算結(jié)果是無效的，所以將邊界上的行列都置為0。重復(fù)以上步驟，直到整幅圖像掃描完成，最終得出邊緣圖像。

4 系統(tǒng)驗(yàn)證和結(jié)果分析
    為了能清楚直觀地驗(yàn)證加速的加速效果，本文在系統(tǒng)平臺(tái)上對(duì)相同的圖像分別用加速／未加速的系統(tǒng)做處理，記錄相應(yīng)時(shí)間并比較。
    本文采用的驗(yàn)證系統(tǒng)平臺(tái)以Altera公司CycloneⅡ系列中的EP2C20F484C8芯片為核心搭建而成，如圖4所示。在驗(yàn)證系統(tǒng)設(shè)計(jì)中實(shí)現(xiàn)一個(gè)串口用來和PC機(jī)中的上位機(jī)通信，把處理完后的數(shù)據(jù)經(jīng)過串口傳輸給上位機(jī)。數(shù)據(jù)在串口的傳輸過程中的延遲時(shí)間是固定的，故從上位機(jī)接收到第一個(gè)數(shù)據(jù)到最后一個(gè)數(shù)據(jù)的時(shí)間差即為一幀圖像處理所花費(fèi)的時(shí)間。

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

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

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

5 結(jié)論
    本文提出并實(shí)現(xiàn)了一種基于FPGA的加速Canny算法邊緣檢測(cè)系統(tǒng)。該系統(tǒng)充分發(fā)揮和利用FPGA的優(yōu)良并行處理能力及流水線技術(shù)，從而實(shí)現(xiàn)功能加速。
    在加速過程中通過狀態(tài)機(jī)的控制作用能使模板的運(yùn)算處理和數(shù)據(jù)的讀／寫操作得以同時(shí)進(jìn)行，一定程度上節(jié)約了因大量的讀／寫數(shù)據(jù)操作而占用的時(shí)間。此系統(tǒng)充分利用了FPGA中的硬件資源，大大提高了系統(tǒng)算法的運(yùn)算效率，且設(shè)計(jì)結(jié)構(gòu)較為靈活。最終通過邊緣檢測(cè)實(shí)驗(yàn)，驗(yàn)證了設(shè)計(jì)的正確性。