高層次綜合特征檢測算法的FPGA實現

謝曉燕，　張玉婷，　劉鎮弢

(西安郵電大學 計算機學院， 西安 710061)

0　引　言

在機器視覺領域中，特征檢測算法被廣泛應用于虛擬場景重建、運動估計、映像配準等視覺處理任務[1]。隨著視覺應用的實時性要求越來越高，近年來基于GPU和FPGA的視覺應用加速器成為機器視覺領域研究的重要內容。GPU具有高度的并行計算能力，可以較好地解決計算速度的問題，然而基于GPU的視覺系統往往存在功耗較高、體積較大的缺點[2]。而嵌入式系統發展要求系統具有小型化、可靠性、高速度、低功耗等特點[3]，FPGA作為一種高性能的可編程邏輯器件，可以通過編程修改其內部的邏輯功能，從而實現高速的硬件計算，是高性能嵌入式視覺系統的一種更加方便的解決方案[4]。目前已有一些工作研究了基于FPGA的特征檢測系統[5-7]，但大都是采用硬件描述語言完成設計，其缺點是描述層次低、開發調試困難，如果更換平臺往往需要大范圍修改邏輯，導致開發周期較長。

面對嵌入式系統性能及功能需求的增長，Xilinx推出的全可編程片上系統(All Programmable System on Chip)Zynq-7000[8]提供了“ARM+FPGA”的單片解決方案。借助Xilinx為Zynq-7000推出的HLS、SDSoC高層次設計工具，能夠利用計算機視覺庫快速開發算法原型，針對特定問題探索最佳的解決方案[9]。為了使特征檢測算法在嵌入式領域達到實時處理并且擁有較高的開發效率，本文選擇Sobel邊緣檢測、Harris角點檢測等兩種經典特征檢測算法作為加速對象，在SDSoC環境下采用流水線優化、循環展開、軟硬件并行等優化方法實現了算法的硬件加速。

1　算法描述

1.1　Sobel算法

Sobel算子是一個主要用于邊緣檢測的離散微分算子，它結合了高斯平滑和微分求導，用來計算圖像灰度函數的近似梯度。該算子包含兩組3×3的矩陣，將它與圖像作平面卷積，即可得出橫向及縱向的亮度差分近似值。如果以A代表原始圖像，橫向及縱向邊緣檢測的圖像灰度值Gx及Gy分別為[10-11]：

圖像每一點的梯度值的大小通過下式來計算，如果某點的梯度G大于給定閾值，則認為該點是邊緣點。

|G|=|Gx|+|Gy|

(3)

1.2　Harris算法

Harris角點檢測是一種直接基于灰度圖像的角點提取算法，穩定性高，尤其對L型角點檢測精度高。計算角點的過程基于下列2×2的矩陣M[12]：

(4)

式中:Ix、Iy分別為圖像在x方向和y方向的導數，在得到矩陣M之后通過M的響應函數來判斷當前點是否為角點。在響應函數中，det(M)代表矩陣M的行列式，trace(M)代表矩陣M的跡，k是一個可調整的參數，取值范圍一般在0.04～0.06內，本文中k的取值為0.04。

R(M)=det(M)-k×trace(M)2

(5)

2　算法加速器設計

基于上節分析，Sobel邊緣檢測算法在一個3×3鄰域中完成每個像素的卷積運算，這就需要對圖像的局部數據進行多次訪問。Harris角點檢測算法不僅要完成卷積運算，在計算角點的過程中還需要較多的乘除計算。對圖像局部數據的多次訪問和較多的計算造成了軟件實現算法時性能不佳。雖然這些算法底層處理的數據量較大，但運算過程相對簡單，并且圖像中的所有像素點均可施以同樣的運算，這些運算可以進行并行操作[13]。因此，使用SDSoC提供的循環流水線優化、循環展開、數據傳輸優化、軟硬件函數并行[14]等方法，通過對指令的合理運用，可以改善系統性能，提高系統效率。

2.1　Sobel算法加速器設計

2.1.1Sobel算法優化

本文描述的Sobel算法是從標準圖像處理庫獲得的軟件實現代碼[15]，其偽代碼為：

voidSobel( IplImage* img, IplImage* dst){

for (inti=1; i〈img-〉height-1; i++){

for (int j=1; j 〈img-〉width-1; j++){

for(int m=-1; m〈=1; m++){

for(int n=-1; n〈=1; n++){

//calculate X direction gradient

}}

for(int m=-1; m〈=1; m++){

for(int n=-1; n〈=1; n++){

//calculate Y direction gradient

}}}}}

以上代碼使用IplImage結構體描述圖像，而SDSoC在綜合時不支持該結構體。因此，本文通過用固定大小的數組替換IplImage指針，并使用sds_lib庫中提供的sds_alloc()[14]函數，確保數組被分配到一個連續的物理地址空間中。由于圖像數據在DDR中存儲，FPGA訪問DDR存儲所花費的時間遠大于CPU對DDR的訪問時間，若每次操作FPGA 都要訪問DDR，將會產生大量的時間開銷。基于此，本文根據文獻[16]的思想，在FPGA端使用3×IMG_WIDTH的行緩沖區和一個3×3的窗口緩沖區來存儲圖像數據。如圖1所示，行緩沖區用來存儲讀入的圖像數據，當行緩沖區中數據滿足卷積操作所需數據時，把這些數據存放在窗口緩沖區中以便進行下一步操作。每完成一次卷積運算，窗口緩沖區右移，然后用行緩沖區中的數據更新窗口緩沖區。通過行緩沖區和窗口緩沖區的協同處理，可以訪問數據流中的局部數據，降低訪問內存的時間開銷，提高系統性能。

圖1緩沖結構及相應操作

在獲取到圖像的局部數據之后，需要進行卷積運算求出X、Y兩個方向的梯度值。原始代碼中分別利用兩個嵌套for循環計算梯度值，由于這兩個循環有相同的界限，并且循環之間不存在數據相關性，本文通過合并循環對該過程進行簡化，減少計算的時延。其偽代碼為：

voidsobel(unsigned char* img_in, unsigned char* img_out, int width, int height){

for(row = 0; row 〈 height; row++){

for(col = 0; col 〈 width; col++){

//load data to win_buf and line_buf

for(i=0; i〈 3; i++){

for(j = 0; j 〈 3; j++){

//calculate X direction gradient

//calculate Y direction gradient

}}}}}

2.1.2軟硬件協同實現

在SDSoC中使用上述中行緩沖和窗口緩沖協同處理的方法獲取像素數據后，用不同的卷積模板求出水平和垂直方向梯度的值并對其絕對值求和得到梯度值，然后對梯度進行閾值處理，最后輸出像素點的值。算法的實現流程如圖2所示，在PS(Processing System)端完成像素數據的讀寫和灰度轉換，在PL(Programmable Logic)端完成Sobel算法的卷積運算和閾值處理。

圖2Sobel算法加速器流程

Sobel邊緣檢測算法需要循環處理圖像的局部像素，在沒有使用循環優化指令的情況下，每次迭代都會使用相同的硬件狀態和資源。由于相鄰像素點的梯度計算不存在數據相關性，為更進一步優化性能，在主循環中使用了SDSoC中提供的AP PIPELINE循環優化指令讓操作進行流水線處理。在計算卷積的過程中，卷積模板與窗口緩沖區內的數據需要進行9次乘法運算。在該循環中使用循環優化指令AP UNROLL，可以對循環內的操作進行展開，同時使用HLS INLINE指令將計算卷積的函數內聯到Sobel頂層函數中。通過這些優化指令的使用，優化了卷積的計算速度，有效地減少了時延。在主循環中使用循環優化指令的偽代碼如下：

for(row = 0; row 〈 height; row++){

for(col = 0; col 〈 width; col++){

pragma AP PIPELINE II = 1

//processing code

}}

2.2　Harris算法加速器設計

2.2.1Harris算法的并行性分析

Harris角點檢測算法由梯度計算、矩陣乘、高斯濾波、計算角點量和閾值化五部分組成，為了充分利用硬件的加速性能，以下對該算法的并行性進行分析。

(1) 流水并行。在處理梯度計算、矩陣乘以及高斯濾波、響應值計算等不同階段時，后一階段無需等待前一階段處理完整幅圖片即可開始，從而構成流水并行方式。各階段可同時處理一幀圖像的不同部分，并且其內部運算結構也可以進一步劃分成更細的流水段。

(2) 任務并行。在角點計算過程中，梯度計算、矩陣乘和高斯濾波每個階段內部的計算是獨立的，沒有相關性，可構成任務級并行。

2.2.2軟硬件協同實現

根據1.2、2.1.1中的算法分析和并行性分析，在SDSoC中角點檢測算法的實現可分為以下幾個步驟來完成，整個算法的實現流程如圖3所示。

(1) 對圖像進行Sobel卷積操作，求出每個像素點所在位置x方向和y方向的梯度值Ix和Iy。Sobel算法的原理和優化見1.1、2.1節。

(2) 對Ix、Iy進行乘法操作，分別得出dxx、dxy和dyy。

(3) 將dxx、dxy和dyy矩陣分別進行高斯濾波得到Ixx、Ixy和Iyy。

高斯濾波是角點檢測中的步驟之一，它是一種線性平滑濾波，主要用來消除高斯噪聲。本文中高斯濾波的實現原理與Sobel邊緣檢測類似，通過使用行緩沖區和窗口緩沖區完成對局部數據的處理。

(4) 根據濾波后Ixx、Ixy和Iyy得到矩陣M，并計算當前點的響應函數R(M)。選取合適的閾值，根據閾值判斷當前點是否為角點。

(5) 根據角點位置在原圖上將其像素值置為255，即用白色點標記出來。

在SDSoC中，如果硬件函數的輸入輸出包含數據

圖3Harris算法加速器流程

流，可以直接把一個硬件函數的輸出流當作另一個硬件函數的輸入流。這樣該硬件函數的數據處理完后無需傳給ARM端處理，而是會按照流水線的方式，從這個函數直接傳入后續的硬件函數繼續被處理。如圖3所示，實現Harris算法需要經過梯度求值、矩陣乘法、高斯濾波和響應函數計算等步驟。將這些函數一起放在FPGA中加速，sdscc工具鏈會自動連接這些硬件函數，在它們之間形成數據流，最后一個硬件函數處理完后通過數據移動器將數據回傳到ARM中。硬件函數直連可以減少數據在傳輸時間上的浪費，從而提高了系統效率。

3　實驗結果及分析

3.1　實驗環境

本文分別使用不同分辨率的bmp格式的圖像對算法結果進行驗證，添加相應的支持庫實現對bmp圖像的讀寫操作。為了更加直觀地驗證算法檢測邊緣和角點的效果，將處理后的圖像二值化，并將二值圖像與OpenCV GPU庫的實驗結果作對比，以此來驗證本文算法的正確性。實驗環境如下：

GPU：NVIDIA GTX650 1 059 MHz，1 024 MB global memory

軟硬件協同(ZC706)[8]：XC7Z045 FFG900-2，ARM Cortex-A9 800 MHz，FPGA 200 MHz，DDR3 1GB

3.2　實驗結果

實驗結果如圖4、5所示。通過對比可以看出本文加速器對算法的實現結果與CUDA庫基本一致，即該設計有良好的邊緣和角點檢測效果。

3.3　算法性能與分析

本文算法的軟件實現在ARM端完成，軟硬件協同同時使用了ARM和FPGA端。為了比較本文提出的算法加速器的加速效果，使用SDSoC提供的sds_clock_counter()函數來對CPU時鐘進行統計。表1為OpenCV視覺庫中兩種特征檢測算法在PC機上的實現、本文ARM軟件實現與FPGA實現處理一幅512×512大小的圖像的時間性能對比。

從表1的數據可以看出FPGA加速器對Sobel、Harris算法的加速性能可以達到2.30 ms、3.78 ms，相比在ARM平臺上的軟件實現方式，加速比分別達到了7.37、19.41。由于Sobel邊緣檢測算法將圖像流數據存儲在行緩沖區和窗口緩沖區之后，分別計算X方向和Y方向的梯度并將其絕對值求和，最后進行閾值運算得到二值圖像。在這個過程中使用的是3×3的卷積核進行卷積運算，因此得到每個像素的輸出值都要經過18個乘加運算。而Harris角點檢測算法由梯度計算、矩陣乘、高斯濾波、計算角點量和閾值化五部分組成，在這個過程中需要較多的乘除運算，因此造成算法在PC和ARM端運行性能不佳。

算法PC機實現/msARM軟件實現/msFPGA實現/msSobel15．3216．942．30Harris37．2573．383．78

使用SDSoC提供的流水線優化指令對算法中計算密集的部分進行優化處理之后可以大幅縮短算法的執行時間，改善算法性能。假設每個卷積操作需要20個時鐘周期，在512×512分辨率下如果沒有使用優化指令則需要5 242 880個時鐘周期，使用流水線優化指令之后僅需要262 164個時鐘，性能提升接近20倍。本文使用sds_clock_counter()函數獲得加速器的執行時間，得到的時間包括數據從DDR傳遞到FPGA端的時間，因此實際加速比小于理論最大值。

本文使用ZC706開發板作為硬件環境，其板載XC7Z045 FFG900-2芯片提供了可編程邏輯陣列單元。在生成的工程報告文件中查看算法加速器的資源占用信息，對一幅512×512大小的圖像進行特征檢測的具體硬件資源使用量和FPGA端資源總量如表2所示。

表2　算法資源占用

從表2中可以看出本文在占用少量FPGA資源的前提下實現了算法的硬件加速。算法加速器對BRAM_18K器件的使用率較低，可見行緩沖區和窗口緩沖區的協同處理對FPGA端存儲資源的節省起到了很大的作用。與Sobel算法相比，Harris算法需要更多的乘除運算，造成DSP48E器件的一些消耗，該器件的使用基本上反應了算法的計算量。

圖6所示為本文FPGA加速器與OpenCV的GPU庫相關函數(即CUDA實現)的加速性能對比，由圖6可知，特征檢測算法的FPGA加速器相比CUDA實現有良好的加速效果，并且NVIDIA GTX650的最大功耗為64 W，而FPGA對一幅512×512大小的圖像進行邊緣檢測和角點檢測僅需0.098 W和0.334 W的功耗，在顯著降低功耗的前提下提高了系統性能。

圖6　FPGA加速與CUDA庫性能對比

Chaple等[5-7]使用硬件描述語言完成了Sobel和Harris算法的FPGA加速器，Monson等[17]使用Vivado HLS將C代碼實現的Sobel算法轉化成RTL實現。表3、4為本文算法加速器處理640×480大小的圖像與文獻[5-7,17]的性能對比。

表3　Sobel算法FPGA加速器性能對比

表4　Harris算法FPGA加速器性能對比

實驗數據表明，本文設計的FPGA加速器在200 MHz的綜合頻率下對Sobel、Harris算法的加速達到了376 f/s和230 f/s，基本可以達到與文獻[5-7,17]中加速器相近的性能。文獻[17]根據HLS綜合報告得出的時間不包括數據傳輸時間，而本文統計的時間性能包括數據從DDR里傳輸到FPGA的時間，因此時間略高。本文與文獻[17]都是基于高層次綜合完成加速器的設計，但是其使用Vivado HLS工具的最終輸出為IP核，如果要實現一個完整的嵌入式系統，還需在Vivado中完成硬件設計，并且要對不同的IP核開發相應的驅動和設備等。而SDSoC環境集成了整套的開發步驟，可以通過對應的軟件算法直接生成在硬件平臺上運行的文件，擁有較高的開發效率。文獻[5-7]中使用硬件描述語言實現算法加速器，需要對硬件執行細節有深入的理解。本文通過高層次綜合工具在更高層次的抽象環境下加速算法，根據應用的不同需求選擇算法運行的平臺，對數據進行簡單運算且需要大量隨機訪問的函數在ARM端實現，若需要進行較多的數值計算則在FPGA端實現，并且通過優化指令控制綜合過程，實現了一個高性能、低功耗的硬件加速器。

4　結　語

本文實現了基于高層次綜合的邊緣檢測和角點檢測的FPGA加速器，并利用SDSoC開發環境提供的優 化指令對算法進行優化。與軟件實現的算法相比，使

用軟硬件協同處理對算法的加速效果很明顯。與CUDA實現方式相比，在降低功耗的同時提高了系統性能。與硬件描述語言實現的加速器相比，擁有較高的開發效率，縮短了開發周期，滿足了機器視覺領域的實時性需求。

參考文獻(References)：

[1]肖漢,周清雷,張祖勛. 基于多GPU的Harris角點檢測并行算法[J]. 武漢大學學報(信息科學版),2012(7):876-881.

[2]Possa P R, Mahmoudi S A, Harb N, et al. A multi-resolution FPGA-based architecture for real-time edge and corner detection[J]. IEEE Transactions on Computers, 2013, 63(10):2376-2388.

[3]沈緒榜. 嵌入式計算機系統的展望[J]. 單片機與嵌入式系統應用,2001(1):5-6.

[4]Todman T J, Constantinides G A, Wilton S J E, et al. Reconfigurable computing: Architectures and design methods[J]. IEE Proceedings - Computers and Digital Techniques, 2006, 152(2):193-207.

[5]Chaple G, Daruwala R D.Design of Sobel operator based image edge detection algorithm on FPGA[C]// International Conference on Communications and Signal Processing. IEEE, 2014:788-792.

[6]Chao T I, Wong K H. An efficient FPGA implementation of the Harris corner feature detector[C]∥Machine Vision Applications (MVA).2015 14th IAPR International Conference, 2015: 89-93.

[7]Hsiao P Y, Lu C L, Fu L C. Multilayered image processing for multiscale harris corner detection in digital realization[J]. Industrial Electronics IEEE Transactions on, 2010, 57(5):1799-1805.

[8]Xilinx, ZynqArchitecture[EB/OL].[2016-1-26].https://www.xilinx.com/products/silicon-devices/soc/zynq-7000.html.

[9]Crockett L H. The Zynqbook:embedded processing with the ARM Cortex-A9 on the Xilinx Zynq-7000 all programmable SoC[M]. Strathclyde Academic Media, 2014.

[10]Qian W,Mei J.Design of video acquisition identification system based on Zynq-7000 Soc Platform[J].Proceedings of International Conference on Informationence & Computer Application,2013,92:208-213.

[12]Harris C. A combined corner and edge detector[J]. ProcAlvey Vision Conf, 1988, 1988(3):147-151.

[13]DonaldG.Bailey. 基于FPGA的嵌入式圖像處理系統設計[M]. 北京：電子工業出版社, 2013.

[14]Xilinx, SDSoC Environment User Guide[EB/OL].[2016-1-26].https://www.xilinx.com/cgi-bin/docs/rdoc?v=2016.2;d=ug1027-sdsoc-user-guide.pdf.

[15]Ramirez G A. (2009, April) sobel.cpp. [EB/OL].[2017-2-24].http://www.cs.utep.edu/ofuentes/AI/sobel.cpp

[16]Abdelgawad H M, Safar M, Wahba A M. High Level Synthesis of Canny Edge Detection Algorithm on ZynqPlatform[J].2015 33rd IEEE International Conference on Computer Design (ICCD).

[17]Monson J, Wirthlin M, Hutchings B L. Optimization techniques for a high level synthesis implementation of the Sobelfilter[C]∥2013 International Conference on Reconfigurable Computing and FPGAs (ReConFig). Cancun, 2013: 1-6.