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

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

責(zé)任編輯:時(shí) 雯

FPGA是在CPLD可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展起來(lái)的新型高性能可編程邏輯器件。與ASIC相比，它具有設(shè)計(jì)開(kāi)發(fā)周期短、制造成本低、開(kāi)發(fā)工具先進(jìn)以及可實(shí)時(shí)在線(xiàn)檢驗(yàn)等優(yōu)點(diǎn)，所以被廣泛應(yīng)用于產(chǎn)品的原型設(shè)計(jì)和生產(chǎn)之中［1］。傳統(tǒng)上FPGA只能實(shí)現(xiàn)相對(duì)較小的邏輯電路，隨著工藝技術(shù)的提高，F(xiàn)PGA的容量和性能也不斷提高，如今FPGA已經(jīng)被用于實(shí)現(xiàn)大的邏輯電路甚至整個(gè)系統(tǒng)。

在實(shí)現(xiàn)大的邏輯電路設(shè)計(jì)時(shí)，應(yīng)對(duì)一些較為復(fù)雜或者重復(fù)性工作模塊多的情況，為了達(dá)到資源的有效利用，F(xiàn)PGA資源就需要進(jìn)行預(yù)評(píng)估。對(duì)設(shè)計(jì)進(jìn)行一個(gè)有效的資源評(píng)估能夠更好得利用FPGA芯片的資源。本文著重于FPGA上的算法的實(shí)現(xiàn)以及進(jìn)行資源使用的預(yù)評(píng)估，以及多層次地評(píng)估算法在FPGA資源上的占用。

1 FPGA資源預(yù)評(píng)估的意義

FPGA可以在片內(nèi)實(shí)現(xiàn)細(xì)粒度、高度并行運(yùn)算結(jié)構(gòu)，所以FPGA最大優(yōu)勢(shì)在于硬件實(shí)現(xiàn)已及通過(guò)并行處理實(shí)現(xiàn)的效率增益。相比DSP，F(xiàn)PGA最大的優(yōu)勢(shì)是能夠在同一時(shí)間能處理大量不同的任務(wù)，因而在涉及到復(fù)雜計(jì)算時(shí)可把DSP的一些任務(wù)轉(zhuǎn)移到FPGA中處理。

未來(lái)人們對(duì)通信的傳輸數(shù)據(jù)、圖像處理等方面要求越來(lái)越高，傳輸速率要求能達(dá)到100 Mbit/s～1 Gbit/s，這就對(duì)無(wú)線(xiàn)技術(shù)、帶寬、數(shù)據(jù)處理能力等提出更高要求。通過(guò)采用FPGA去做復(fù)雜的數(shù)據(jù)處理，可以實(shí)現(xiàn)更高的速率傳輸。

在FPGA應(yīng)對(duì)復(fù)雜的數(shù)據(jù)處理時(shí)，因?yàn)橐拇罅康腞egister和LUT等邏輯資源來(lái)實(shí)現(xiàn)復(fù)雜運(yùn)算，所以有必要在編寫(xiě)程序之前對(duì)算法資源進(jìn)行預(yù)評(píng)估。提前的資源評(píng)估不僅可以更好地選擇芯片的型號(hào)，還可以對(duì)算法程序有較詳細(xì)的估計(jì)，在硬件選定的前提下能夠有更好的優(yōu)化算法。

2 對(duì)Harris算法的資源的評(píng)估

2.1 Harris角點(diǎn)檢測(cè)原理

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

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

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

圖1 算法流程圖

2.2 模板構(gòu)造

Harris算法在FPGA實(shí)現(xiàn)中需要構(gòu)造圖像數(shù)據(jù)矩陣，假設(shè)采用5×5的模板如圖2所示，即需要通過(guò)緩存4行4列的數(shù)據(jù)，然后在通過(guò)模板進(jìn)行相應(yīng)的計(jì)算。

圖2 5×5的模板實(shí)現(xiàn)

其中r11，r12等為移位寄存器;FIFO是先進(jìn)先出存儲(chǔ)器，圖像數(shù)據(jù)一次串行輸入，利用行、場(chǎng)信號(hào)來(lái)控制讀寫(xiě)信號(hào)，F(xiàn)IFO用來(lái)存儲(chǔ)每一行的數(shù)據(jù)，使得 R11，R12，…，R55正好是5×5模板所對(duì)應(yīng)的圖像數(shù)據(jù)［4］。

2.3 資源的預(yù)評(píng)估

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

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

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

圖3 FIFO資源和D觸發(fā)器資源

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

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

2.3.1 RAM資源預(yù)評(píng)估

在Harris角點(diǎn)檢測(cè)算法中，采用的是5×5的模板窗口進(jìn)行檢測(cè)，使用到FIFO資源。如圖3、圖4得知，F(xiàn)IFO占用了M4K的塊RAM資源。從FPGA的資源介紹中知道，塊RAM資源屬于FPGA定制資源，受M4K數(shù)量限制。

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

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

表1 RAM資源預(yù)評(píng)估

2.3.2 邏輯資源預(yù)評(píng)估

1)在Harris算法程序中，計(jì)算Ix，Iy時(shí)使用到了5個(gè)D觸發(fā)器進(jìn)行移位，其中每個(gè)觸發(fā)器的位寬為16 bit(位寬受像素影響)同樣在計(jì)算高斯濾波時(shí)也使用5個(gè)D觸發(fā)器，位寬16 bit，一共使用20個(gè)D觸發(fā)器，位寬16 bit。在圖3、圖4可知，F(xiàn)IFO也會(huì)占用時(shí)序邏輯資源。具體預(yù)評(píng)估資源如表2所示。

表2 時(shí)序邏輯資源預(yù)評(píng)估

2)加減法器占用組合邏輯資源，受計(jì)算數(shù)據(jù)位寬的影響，每一位占用一個(gè)邏輯資源，由圖3、圖4中得知，F(xiàn)IFO也占用了LUT資源。具體預(yù)評(píng)估資源如表3所示。

表3 組合邏輯資源預(yù)評(píng)估

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

2.4 Harris算法在FPGA的實(shí)現(xiàn)

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

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

表4 StratixII芯片的資源

3 實(shí)驗(yàn)結(jié)果

3.1 仿真結(jié)果和預(yù)評(píng)估比較

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

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

3.2 實(shí)現(xiàn)圖像

最后將程序在FPGA的硬件平臺(tái)上實(shí)現(xiàn)，輸入圖像是CCD實(shí)時(shí)灰度圖像，在閾值不大的情況下，得到圖8的實(shí)時(shí)圖像的Harris角點(diǎn)檢測(cè)。其中圖中的十字叉為檢測(cè)到的角點(diǎn)。

圖8 實(shí)時(shí)圖像的Harris角點(diǎn)檢測(cè)

4 小結(jié)

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

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

［2］劉闖，龔聲蓉.基于角點(diǎn)采樣的多目標(biāo)跟蹤方法［J］.中國(guó)圖象圖形學(xué)報(bào)，2008，13(10):1873-1877.

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

［4］王鵬，向厚振.基于FPGA的動(dòng)態(tài)可重構(gòu)邊緣檢測(cè)系統(tǒng)設(shè)計(jì)［J］.電視技術(shù)，2011，35(7):32-35.

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

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