基于FPGA的Harris算法移植以及資源預評估

李龍勛，唐普英，唐湘成，劉 怡，黃自力

(1.電子科技大學，四川 成都 611731;2.西南技術物理研究所，四川 成都 610041)

責任編輯:時 雯

FPGA是在CPLD可編程器件的基礎上進一步發展起來的新型高性能可編程邏輯器件。與ASIC相比，它具有設計開發周期短、制造成本低、開發工具先進以及可實時在線檢驗等優點，所以被廣泛應用于產品的原型設計和生產之中［1］。傳統上FPGA只能實現相對較小的邏輯電路，隨著工藝技術的提高，FPGA的容量和性能也不斷提高，如今FPGA已經被用于實現大的邏輯電路甚至整個系統。

在實現大的邏輯電路設計時，應對一些較為復雜或者重復性工作模塊多的情況，為了達到資源的有效利用，FPGA資源就需要進行預評估。對設計進行一個有效的資源評估能夠更好得利用FPGA芯片的資源。本文著重于FPGA上的算法的實現以及進行資源使用的預評估，以及多層次地評估算法在FPGA資源上的占用。

1 FPGA資源預評估的意義

FPGA可以在片內實現細粒度、高度并行運算結構，所以FPGA最大優勢在于硬件實現已及通過并行處理實現的效率增益。相比DSP，FPGA最大的優勢是能夠在同一時間能處理大量不同的任務，因而在涉及到復雜計算時可把DSP的一些任務轉移到FPGA中處理。

未來人們對通信的傳輸數據、圖像處理等方面要求越來越高，傳輸速率要求能達到100 Mbit/s～1 Gbit/s，這就對無線技術、帶寬、數據處理能力等提出更高要求。通過采用FPGA去做復雜的數據處理，可以實現更高的速率傳輸。

在FPGA應對復雜的數據處理時，因為要消耗大量的Register和LUT等邏輯資源來實現復雜運算，所以有必要在編寫程序之前對算法資源進行預評估。提前的資源評估不僅可以更好地選擇芯片的型號，還可以對算法程序有較詳細的估計，在硬件選定的前提下能夠有更好的優化算法。

2 對Harris算法的資源的評估

2.1 Harris角點檢測原理

角點是圖像的一個重要局部特征，它集中了圖像上很多重要形狀信息，且具有旋轉不變性，幾乎不受光照條件影響［2］，本文采用的是Harris角點檢測算法。Harris算法是基于圖像灰度的角點檢測算法，若像素點所在位置的z方向梯度與y方向梯度的絕對值均比較大，則將該像素點判定為角點。

式中:w為高斯濾波進行去除噪聲處理;Ix和Iy分別為需要計算的像素在水平方向和垂直方向的一階灰度梯度［3］。

其中，式(1)、式(2)為計算相關函數，然后使用式(3)的角點函數計算出圖像中的角點。最后根據角點檢測原理可以得到算法計算步驟如圖1所示。

圖1 算法流程圖

2.2 模板構造

Harris算法在FPGA實現中需要構造圖像數據矩陣，假設采用5×5的模板如圖2所示，即需要通過緩存4行4列的數據，然后在通過模板進行相應的計算。

圖2 5×5的模板實現

其中r11，r12等為移位寄存器;FIFO是先進先出存儲器，圖像數據一次串行輸入，利用行、場信號來控制讀寫信號，FIFO用來存儲每一行的數據，使得 R11，R12，…，R55正好是5×5模板所對應的圖像數據［4］。

2.3 資源的預評估

FPGA芯片主要由以下部分組成:可編程輸入輸出單元、基本可編程邏輯單元、數字時鐘管理模塊、嵌入式塊RAM、豐富的布線資源、底層嵌入功能單元和內嵌專用硬核等［5］。

在算法未實現之前，在單一算法模塊中，能夠進行預評估的資源有RAM資源、邏輯資源(時序邏輯資源和組合邏輯資源)以及DSP模塊使用情況。由上面的算法流程可以得知在計算過程中使用到的是FIFO資源、移位寄存器資源、加法器、減法器和乘法器。

如圖3所示24位的 FIFO占用24個 LUT、6個M4KRAM資源和126的Register資源。一個16位的D觸發器占用16個LUT資源。

圖3 FIFO資源和D觸發器資源

如圖4所示，24位的加法器占用24LUT資源，24位減法器占用25LUT資源，12位乘法器占用2個DSP的9位模塊資源，本算法中沒有涉及到除法器所以沒有使用到除法器。

圖4 加法器、減法器和乘法器資源

2.3.1 RAM資源預評估

在Harris角點檢測算法中，采用的是5×5的模板窗口進行檢測，使用到FIFO資源。如圖3、圖4得知，FIFO占用了M4K的塊RAM資源。從FPGA的資源介紹中知道，塊RAM資源屬于FPGA定制資源，受M4K數量限制。

1)在對Ix進行計算中，5×5模板需要利用4個FIFO進行存儲，位寬和深度主要取決于圖像像素(這里取FIFO位寬為24 bit、深度為1024)。計算Iy和Ix的為相同模板，所以和Ix計算占用同樣資源。

2)在高斯濾波中，要針對Ix，Iy，Ixy三個值使用三個高斯濾波模塊。高斯濾波也使用5×5的模板，在資源的占用上，使用了4個FIFO(位寬24 bit、深度1024)。具體預評估資源如表1所示。

表1 RAM資源預評估

2.3.2 邏輯資源預評估

1)在Harris算法程序中，計算Ix，Iy時使用到了5個D觸發器進行移位，其中每個觸發器的位寬為16 bit(位寬受像素影響)同樣在計算高斯濾波時也使用5個D觸發器，位寬16 bit，一共使用20個D觸發器，位寬16 bit。在圖3、圖4可知，FIFO也會占用時序邏輯資源。具體預評估資源如表2所示。

表2 時序邏輯資源預評估

2)加減法器占用組合邏輯資源，受計算數據位寬的影響，每一位占用一個邏輯資源，由圖3、圖4中得知，FIFO也占用了LUT資源。具體預評估資源如表3所示。

表3 組合邏輯資源預評估

3)乘法器占用DSP elements資源，乘法器中位寬為36×36的占用8個DSP elements，18×18是占用2個DSP elements。在算法中乘法器中有3個24位的，有5個12位的，總共占用DSP elements 34個。如果是類似2×A的數字和數據相乘，而不是A×B的兩個數據相乘，此時的乘法相當于加法，只占用組合邏輯資源而不占用DSP模塊。

2.4 Harris算法在FPGA的實現

根據圖2的算法流程，構造的圖像數據矩陣，先計算出圖像像素在水平方向和垂直方向的一階灰度梯度Ix以及Iy。然后計算出m值再進行高斯濾波，最后根據M值計算R值求得角點。其中計算Ix，Iy值的時候注意Ix，Iy的非負性。下面為在FPGA中用Verilog語言計算Ix，Iy的值。

實現平臺采用的是Stratix系列的EP2S60F672C4芯片，其中含有的等效邏輯單元為60440，RAM資源為2544，192 bit，DSP 模塊有36 個，鎖相環 PLL 有6 個，全局時鐘有16個。表4為StratixII系列芯片的資源［6］。

表4 StratixII芯片的資源

3 實驗結果

3.1 仿真結果和預評估比較

在Quartus 8.1軟件中完成Harris算法的FPGA程序，在軟件中仿真綜合可以得到結果如圖5、圖6、圖7所示。

如圖所示，在對比由軟件得到的RAM資源仿真結果和預評估的資源可以知道，ALUTs占用2666和預估計的4016相差1350，而Delicated logic registers占用2623和預估計的2262相差361，占用的RAM資源308353 bit和估計的393216 bit等相比相差84863 bit。理論預估計的要比實際占用的要多，其中ALUTS實際和估計差距較大原因在于FIFO在實際仿真中占用的ALUTS資源要比理論上要多。其他資源的預估計在仿真中得到相仿的結果。

3.2 實現圖像

最后將程序在FPGA的硬件平臺上實現，輸入圖像是CCD實時灰度圖像，在閾值不大的情況下，得到圖8的實時圖像的Harris角點檢測。其中圖中的十字叉為檢測到的角點。

圖8 實時圖像的Harris角點檢測

4 小結

本文對Harris算法進行FPGA上的移植實現，及對其在FPGA上資源的占用進行了預評估。從最后的圖像可以看出，在小閾值的情況下Harris算法在FPGA上實現了實時的角點檢測。從仿真的結果可以看出，預評估的各項參數和實際仿真出來的相差不大，其中的誤差取決于程序中流程編寫中使用到的其他邏輯門，以及FIFO實際應用中占用的ALUT也比理論上的多。由此可以看出，只要知道算法的具體流程，在RAM資源和邏輯資源的預評估上是能有效提供參考價值的。

［1］俞吉波，孔雪.FPGA實際可用性評估與發展趨勢分析［J］.計算機工程，2011，37(13):282-284.

［2］劉闖，龔聲蓉.基于角點采樣的多目標跟蹤方法［J］.中國圖象圖形學報，2008，13(10):1873-1877.

［3］何豐，胡俊.一種改進的圖像快速高精度角點檢測算法［J］.電視技術，2011，35(15):57-60.

［4］王鵬，向厚振.基于FPGA的動態可重構邊緣檢測系統設計［J］.電視技術，2011，35(7):32-35.

［5］徐洋，黃智宇，李彥，等.基于Verilog HDL的FPGA設計與工程應用［M］.北京:人民郵電出版社，2009.

［6］Alter Product Catalog［EB/OL］.［2012-05-13］.http://www.altera.com.cn/literature/sg/product-catalog.pdf.