SIFT特征提取算法的FPGA實(shí)時(shí)實(shí)現(xiàn)

陸愷立，耿俊梅，顧國華，錢惟賢，徐富元

(1.南京理工大學(xué)電光學(xué)院，江蘇南京210094;2.濟(jì)源職業(yè)技術(shù)學(xué)院，河南濟(jì)源454650)

SIFT特征提取算法的FPGA實(shí)時(shí)實(shí)現(xiàn)

陸愷立1，耿俊梅2，顧國華1，錢惟賢1，徐富元1

(1.南京理工大學(xué)電光學(xué)院，江蘇南京210094;2.濟(jì)源職業(yè)技術(shù)學(xué)院，河南濟(jì)源454650)

為了在運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤系統(tǒng)中能夠?qū)崟r(shí)地提取目標(biāo)的特征點(diǎn)，從而完成圖像實(shí)時(shí)匹配操作，提出了在FPGA實(shí)現(xiàn)SIFT特征提取算法。該算法采用SRAM復(fù)用技術(shù)簡化程序，合理設(shè)計(jì)FPGA各模塊結(jié)構(gòu)。此外，該算法采用定點(diǎn)小數(shù)來保證算法的精度要求。整個(gè)算法在Virtex－5硬件平臺(tái)上實(shí)現(xiàn)，采用verilog語言進(jìn)行程序的編寫和調(diào)試。結(jié)果分析表明，優(yōu)化后的SIFT算法能夠穩(wěn)定地在FPGA上實(shí)現(xiàn)，同時(shí)算法的復(fù)雜度得到了降低并達(dá)到了精度要求，且具有良好的實(shí)時(shí)性。

FPGA;特征提取算法;SRAM;Virtex－5;實(shí)時(shí)性

運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤系統(tǒng)［2］涉及到圖像匹配［3］的問題。考慮到復(fù)雜場(chǎng)景中拍攝的圖像容易發(fā)生平移、旋轉(zhuǎn)或者尺度的變換，所以采用SIFT算法［1］可以較好地解決這一問題。

文獻(xiàn)［4］提出了SIFT算法的改進(jìn)方法，通過PCA分析來對(duì)特征描述符作降維處理，以及使用塊狀濾波(Boxlet)和積分圖像來取代SIFT算法中計(jì)算復(fù)雜的高斯濾波，降低了算法的復(fù)雜度，但是實(shí)時(shí)性較差;文獻(xiàn)［5］提出了在基于TI多核C6000 DSP芯片上實(shí)現(xiàn)SITF算法，采用多核DSP可以提高SIFT算法運(yùn)算精度，且可移植性強(qiáng)，但是占用內(nèi)存資源較大，且實(shí)時(shí)性沒有得到徹底改善。

為了使得算法實(shí)時(shí)運(yùn)行，學(xué)者們提出了采用FPGA來實(shí)現(xiàn)SIFT算法。文獻(xiàn)［6］提出了用FPGA+NIOS II相結(jié)合的思路，將主方向和特征描述子的求取用軟件［7］來實(shí)現(xiàn)，在一定程度上減少了FPGA的工作量，但是涉及到軟件與硬件協(xié)同工作，實(shí)時(shí)效果相對(duì)差一些;文獻(xiàn)［8］采用雙端口DDR2存儲(chǔ)器技術(shù)提高存取速率，減少運(yùn)算時(shí)間，但是程序?qū)崿F(xiàn)時(shí)復(fù)雜度高。

因此，本文提出了在1片Virtex－5芯片中實(shí)現(xiàn)SIFT算法的方法，通過充分利用外部SRAM存儲(chǔ)資源，從而達(dá)到簡化程序、減少內(nèi)部資源占用率以及實(shí)時(shí)的效果。

1 算法介紹及參數(shù)選擇

SIFT特征提取算法是一種同時(shí)具有平移、旋轉(zhuǎn)、尺度不變性的特征檢測(cè)和匹配算法，對(duì)光照和仿射變換也具有一定程度的魯棒性。SIFT特征提取算法主要包括以下步驟:1)搭建高斯金字塔;2)構(gòu)造DOG尺度空間;3)尺度空間極值點(diǎn)檢測(cè);4)特征點(diǎn)主方向確定;5)生成特征點(diǎn)描述子。

1.1 算法優(yōu)化

因?yàn)楦咚咕矸e在SIFT算法中是影響運(yùn)算速度的關(guān)鍵因素，為了使算法在FPGA平臺(tái)上易于實(shí)現(xiàn)，本文對(duì)高斯濾波部分進(jìn)行了優(yōu)化:

1)采用級(jí)聯(lián)方式搭建高斯金字塔

2)二維高斯卷積的拆分

二維高斯卷積公式如下

對(duì)于二維的高斯卷積，如果采用7×7模板，每次都要采用49個(gè)乘法器，硬件邏輯資源消耗較多?？紤]到二維高斯卷積的公式可以拓展為一維高斯卷積的乘積

將二維高斯卷積化解為化簡為對(duì)行和列分別進(jìn)行一維高斯卷積，這樣使得每個(gè)高斯模板計(jì)算時(shí)乘法器減少為14個(gè)，可以節(jié)省FPGA的邏輯資源，同時(shí)降低算法復(fù)雜度，縮短處理時(shí)間。

1.2 參數(shù)選擇

SIFT算法在硬件平臺(tái)上實(shí)時(shí)實(shí)現(xiàn)的同時(shí)，為了保證求取的特征描述子精度能夠滿足后端算法匹配要求，要對(duì)系統(tǒng)參數(shù)進(jìn)行合理選取:

1)高斯金字塔的組數(shù)和層數(shù)。高斯尺度空間是關(guān)于尺度的連續(xù)空間，當(dāng)金字塔層數(shù)越多時(shí)，所得結(jié)果越精確，但由于層數(shù)增加所帶來的計(jì)算量會(huì)成倍增加，因此要適當(dāng)選擇高斯金字塔的組數(shù)和層數(shù)。本文選定的組數(shù)為2組，每組5層，有效地降低算法的計(jì)算量。

2)尺度和層間距。為了省去對(duì)原始圖像進(jìn)行插值的步驟，本文直接用標(biāo)準(zhǔn)差較小的高斯函數(shù)對(duì)原始圖像進(jìn)行濾波，從而等效得到較高的尺度層，所以選取初始尺度σ0為1.2。另外根據(jù)文獻(xiàn)［1］，最佳的尺度層間距為21/3，次優(yōu)為21/2。假如選擇前者，每一層尺度相比后者較大，中間數(shù)據(jù)會(huì)相應(yīng)增大，因此會(huì)占用更大的存儲(chǔ)空間來存儲(chǔ)數(shù)據(jù)，所以選擇21/2。

3)高斯卷積核長度。如圖1所示，由一維高斯卷積函數(shù)曲線可知當(dāng)σ0為1.2，最佳卷積模板長度w為w= 2×Round(3.5σ)+1=9。如圖2所示，當(dāng)卷積核長度的增加會(huì)導(dǎo)致卷積計(jì)算量的大幅增加，擴(kuò)大FPGA總的資源占用率。當(dāng)選用模板長度為7時(shí)高斯模板卷積資源占用率為18%，相比模板長度為9時(shí)減少了7%。同時(shí)在本文后續(xù)結(jié)果驗(yàn)證中可知模板長度為7也可以達(dá)到滿足精度要求，所以本文選用7×7作為二維高斯卷積模板大小，并在卷積時(shí)通過乘以比例系數(shù)進(jìn)行修正。

圖1 一維高斯卷積曲線

圖2 資源占用圖

2 算法的FPGA實(shí)現(xiàn)

本設(shè)計(jì)以Xilinx公司的Virtex－5系列的XC5VFX30T為核心主芯片，它可以提供較為豐富的內(nèi)部存儲(chǔ)資源和邏輯資源，同時(shí)外部選擇適量異步單端口SRAM作為存儲(chǔ)芯片。利用硬件平臺(tái)提供的千兆網(wǎng)端口，可以使圖像數(shù)據(jù)傳輸速率達(dá)到1 000 Mbit/s，所以系統(tǒng)可以利用千兆網(wǎng)實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)傳送。

在本設(shè)計(jì)中，實(shí)時(shí)圖像(320×256)以25 f/s(幀/秒)的速度通過PAL口傳輸?shù)紽PGA平臺(tái)上，通過SIFT算法模塊求得特征描述子后，利用千兆網(wǎng)將結(jié)果發(fā)送至PC端供后端算法匹配處理。為了便于結(jié)果分析，也同時(shí)將特征點(diǎn)及其主方向通過千兆網(wǎng)傳輸?shù)絇C端進(jìn)行顯示。

如圖3所示，本文將算法主要分為以下幾個(gè)模塊:高斯濾波級(jí)聯(lián)和高斯差分模塊、梯度計(jì)算模塊、極值點(diǎn)檢測(cè)模塊，以及求取主方向和特征描述子模塊。

圖3 算法模塊流程圖

2.1 具體結(jié)構(gòu)設(shè)計(jì)

大部分文章用FPGA實(shí)現(xiàn)SIFT時(shí)考慮的一個(gè)主要方面是節(jié)省內(nèi)部存儲(chǔ)空間，而本文利用FPGA中空間換取時(shí)間的概念，充分利用Virtex－5開發(fā)板外置多片SRAM的特點(diǎn)，巧妙地利用SRAM復(fù)用技術(shù)，有效地提高SIFT算法的運(yùn)算速度。

如圖4所示，按照SIFT基本步驟，需要SRAM存儲(chǔ)的地方主要分為兩個(gè)部分:一維高斯濾波值的暫存、高斯圖像梯度值暫存。由于本文每一組高斯層數(shù)為5，所以對(duì)于搭建一組5層得高斯金字塔需要復(fù)用5次SRAM1，由于輸入數(shù)據(jù)時(shí)鐘為25 MHz，對(duì)SRAM1操作時(shí)鐘提高為125 MHz可以滿足實(shí)時(shí)要求。另外需要用SRAM2存儲(chǔ)梯度值，由于組數(shù)為2，所以總共需要4片SRAM。而模塊之間的緩存以及極值尋找時(shí)比較窗口的搭建可以通過FIFO緩存方式實(shí)現(xiàn)。

圖4 FPGA具體結(jié)構(gòu)框架

2.2 定點(diǎn)數(shù)選取

原始灰度圖像數(shù)據(jù)為8位無符號(hào)數(shù)，但因?yàn)楦咚咕矸e模板中包含小數(shù)，卷積后的數(shù)據(jù)寬度會(huì)相應(yīng)增加，因此采用定點(diǎn)小數(shù)表示。本文通過對(duì)比各模塊數(shù)據(jù)的大小，合理選擇定點(diǎn)數(shù)的位寬，從而有效提高利用率和速度。系統(tǒng)中各部分的數(shù)據(jù)位寬如表1所示。

表1 不同模塊數(shù)據(jù)類型及寬度表

2.3 高斯濾波級(jí)聯(lián)與高斯差分模塊

2.3.1 框架結(jié)構(gòu)

接收到圖像數(shù)據(jù)后，如圖5所示，采用級(jí)聯(lián)的方式進(jìn)行5次高斯卷積，每次卷積都需要用125MHz時(shí)鐘對(duì)SRAM進(jìn)行讀取操作。由于每次計(jì)算高斯濾波值都是從第一個(gè)輸入值開始計(jì)算，所以相鄰層之間延時(shí)較小，用寄存器進(jìn)行緩存后可以直接作差求出高斯差分值。并且由于高斯差分圖像的同步性，所以不需要緩存可以直接輸出求取極值。

圖5 高斯濾波級(jí)聯(lián)模塊和高斯差分模塊流程圖

2.3.2 二維高斯卷積的實(shí)現(xiàn)

如圖6所示，在FPGA中先按行對(duì)輸入數(shù)據(jù)進(jìn)行一維高斯卷積，一維高斯卷積的結(jié)果通過過數(shù)據(jù)選擇模塊1后轉(zhuǎn)置的同時(shí)乒乓緩存到SRAM的不同存儲(chǔ)空間中。利用數(shù)據(jù)選擇模塊2從SRAM的不同存儲(chǔ)空間中讀出數(shù)據(jù)后再進(jìn)行一維高斯卷積，得到二維高斯卷積的值。每次二維高斯卷積得到的結(jié)果在進(jìn)行下一層二維高斯卷積的同時(shí)讀入梯度計(jì)算模塊求取梯度值。

圖6 二維高斯卷積計(jì)算流程圖

2.4 極值點(diǎn)檢測(cè)模塊

如圖7所示，從數(shù)據(jù)緩存器1中讀取要尋找極值的高斯差分圖像數(shù)據(jù)，輸入比較器的同時(shí)，根據(jù)中心點(diǎn)的坐標(biāo)從數(shù)據(jù)緩存器2中讀出中心點(diǎn)相鄰26個(gè)點(diǎn)的高斯差分值，然后依次與中心點(diǎn)的值進(jìn)行比較，若判斷是極值則存儲(chǔ)到數(shù)據(jù)緩存器3中;若不是極值則繼續(xù)從數(shù)據(jù)緩存器1中讀出數(shù)據(jù)進(jìn)行上述操作。這里的3個(gè)數(shù)據(jù)緩存器均用FIFO實(shí)現(xiàn)。

圖7 極值點(diǎn)檢測(cè)模塊流程圖

2.5 梯度計(jì)算模塊

在極值點(diǎn)檢測(cè)的同時(shí)，并行計(jì)算高斯金字塔中每一個(gè)點(diǎn)的梯度值。由于FPGA不容易實(shí)現(xiàn)根號(hào)以及三角函數(shù)的運(yùn)算，所以本文采用cordic算法的向量模式求取梯度值，通過基本的加和移位運(yùn)算代替乘法運(yùn)算，完成直角坐標(biāo)向極坐標(biāo)的轉(zhuǎn)換，使得矢量的旋轉(zhuǎn)和方向的計(jì)算不再需要平方、開方、反三角等函數(shù)，也相比調(diào)用IP核節(jié)省了很多FPGA資源。本系統(tǒng)中cordic算法采用16次迭代，最后求得的梯度誤差在0.1%左右，并且可以根據(jù)實(shí)際精度的需要和資源的損耗來改變迭代次數(shù)。

2.6 主方向和特征描述子生成模塊

主方向和特征描述子求取主要工作分為讀取SRAM梯度信息和直方圖統(tǒng)計(jì)兩塊。根據(jù)FPGA讀取坐標(biāo)的特點(diǎn)，選取鄰域?yàn)榉叫螀^(qū)域進(jìn)行統(tǒng)計(jì)直方圖;另外由于每一個(gè)特征點(diǎn)相互不影響，所以可以采用高速時(shí)鐘從SRAM讀取特征點(diǎn)鄰域值，然后用并行的方式進(jìn)行統(tǒng)計(jì)直方圖。

考慮到直方圖統(tǒng)計(jì)時(shí)主要是根據(jù)角度值進(jìn)行幅值疊加然后判斷，所以本文提出一種內(nèi)部RAM存取機(jī)制，把角度值作為RAM的存儲(chǔ)地址，幅值作為RAM的存儲(chǔ)數(shù)據(jù)進(jìn)行累加，這樣只要每次對(duì)角度取整后按照角度地址進(jìn)行幅值存儲(chǔ)即可很容易統(tǒng)計(jì)得到直方圖，而不需要另外開辟寄存器進(jìn)行緩存。

最后求得的特征描述子歸一化后用20位有符號(hào)數(shù)表示并緩存到FIFO中，再用流水線方式通過千兆網(wǎng)輸出。

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

本文討論的SIFT算法在Xilinx的Virtex－5硬件平臺(tái)上的實(shí)現(xiàn)，采用ISE13.1軟件和verilog語言來編寫程序，將計(jì)算得到的特征點(diǎn)和其主方向以及特征描述子利用千兆網(wǎng)傳送到PC上進(jìn)行顯示和后續(xù)匹配。

下面從特征點(diǎn)的準(zhǔn)確性和實(shí)時(shí)性以及FPGA資源消耗三方面來對(duì)結(jié)果進(jìn)行分析。

3.1 準(zhǔn)確性分析

3.1.1 特征點(diǎn)有效性分析

如圖8所示，為了觀察實(shí)際場(chǎng)景中圖像特征點(diǎn)提取的效果，本文拍攝了兩組室外場(chǎng)景圖8a、圖8b和室內(nèi)場(chǎng)景圖像圖8c、圖8d，并將特征點(diǎn)和主方向傳遞到PC中在原圖上進(jìn)行顯示。

圖8 不同場(chǎng)景下特征點(diǎn)效果圖

為了充分觀察SIFT算法在硬件平臺(tái)上求取特征點(diǎn)的有效性，將上述4組場(chǎng)景圖像在FPGA中求取的特征點(diǎn)個(gè)數(shù)和在MATLAB中求取的特征點(diǎn)個(gè)數(shù)進(jìn)行對(duì)比，如表2所示。

表2 FPGA特征點(diǎn)與MATLAB特征點(diǎn)對(duì)比表

從表2可以看出，對(duì)于4種不同的場(chǎng)景，采用FPGA求得的特征點(diǎn)個(gè)數(shù)與MATLAB求得的特征點(diǎn)個(gè)數(shù)相近，而且重合點(diǎn)數(shù)較多，說明重合率較高，有效性好。

3.1.2 特征描述子準(zhǔn)確性分析

以圖8b為例，對(duì)FPGA和MATLAB重合的228個(gè)特征點(diǎn)在兩個(gè)平臺(tái)上分別求取特征描述子，然后歸一化取模進(jìn)行對(duì)比，比較曲線如圖9所示。

為了計(jì)算FPGA與MATLAB實(shí)驗(yàn)結(jié)果的相對(duì)誤差，利用誤差公式

式中:yFPGA為在FPGA中檢測(cè)到得特征描述子的值; yMATLAB為在MATLAB中檢測(cè)到得特征描述子的值，得到相對(duì)誤差曲線，如圖10所示。由相對(duì)誤差曲線可以看出，用FPGA計(jì)算特征描述子和MATLAB計(jì)算特征描述子的平均誤差僅為3.15%，在可允許的誤差范圍之內(nèi)。因此用FPGA計(jì)算特征描述子準(zhǔn)確性較好。

圖9 特征描述子y比較曲線

圖10 相對(duì)誤差曲線

3.1.3 特征點(diǎn)匹配可行性分析

除了判斷特征點(diǎn)重合率以及特征描述子的誤差外，判斷FPGA所求的的特征點(diǎn)準(zhǔn)確性的關(guān)鍵因素在于是否可供后端進(jìn)行匹配。下面利用FPGA求得3組分別進(jìn)行了平移變換、角度變換和尺度變換的圖像的特征描述子，然后利用千兆網(wǎng)輸入到PC端進(jìn)行匹配，從而來判斷FPGA求得的特征點(diǎn)準(zhǔn)確性高低。

由圖11可以看出，在圖像進(jìn)行了平移、旋轉(zhuǎn)以及尺度變換的前提下，由FPGA求得的特征點(diǎn)同樣可以用于進(jìn)行較準(zhǔn)確的特征點(diǎn)匹配，特征點(diǎn)準(zhǔn)確匹配率達(dá)到了94%，所以進(jìn)一步說明FPGA求取SIFT特征點(diǎn)準(zhǔn)確性較好。

圖11 平移、旋轉(zhuǎn)、尺度變換特征點(diǎn)匹配圖

3.2 實(shí)時(shí)性分析

為了檢驗(yàn)SIFT算法在FPGA上實(shí)現(xiàn)的加速效果，將本文算法與主頻為2.1 GHz的Intel平臺(tái)下算法以及其他在FPGA平臺(tái)下實(shí)現(xiàn)的算法進(jìn)行耗時(shí)對(duì)比，如表3所示。

表3 SIFT算法耗時(shí)對(duì)比表

由表3可以看出，相比于在主頻為2.1 GHz的Intel CPU上運(yùn)行SIFT基本算法，本文提出的基于Virex－5硬件平臺(tái)的SIFT算法速度提高了126多倍;相比于文獻(xiàn)［7］中FPGA+DSP方案以及文獻(xiàn)［9］提出的方案，總體速率有所提高;而相比于文獻(xiàn)［8］DDR2方案，速度只是略微不及。因此通過對(duì)比可以得知在本文的平臺(tái)上實(shí)現(xiàn)SIFT算法實(shí)時(shí)性較好。

3.3 FPGA資源消耗

由表4可以看出，在系統(tǒng)搭建完成后，F(xiàn)PGA剩余邏輯資源和存儲(chǔ)資源較多，可以為后端算法提供足夠的空間裕量。

表4 FPGA資源占用表

4 結(jié)論

本文主要研究了SIFT特征提取算法在Virtex－5平臺(tái)上的實(shí)現(xiàn)方式，通過合理選擇參數(shù)以及復(fù)用SRAM技術(shù)在保證特征點(diǎn)精度的同時(shí)保證了算法的實(shí)時(shí)性。相比之前學(xué)者們?cè)贔PGA平臺(tái)上對(duì)SIFT的研究，本文改變了高斯金字塔的搭建方式，從并聯(lián)轉(zhuǎn)為級(jí)聯(lián)的同時(shí)確保了算法的并行性;同時(shí)通過適量緩存器保證了模塊之間的銜接性，保證了時(shí)序的穩(wěn)定。最后驗(yàn)證得到本文提出的方法圖像處理速度可以達(dá)到38 f/s，具有較好的實(shí)時(shí)性，同時(shí)精度也滿足后端匹配的要求。

［1］ LOWE D.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［2］PAUL V，MICHAEL J.Robust real－time object detection［S］.2001.

［3］GONZALEZ R，WOODSR.Digital image processing［M］.［s.n.］:Addison－Wesley Publishing Company，1992.

［4］YAN K，RAHUL S.PCA－SIFT:amore distinctive respresentation for local image descriptors［C］//Proc.Conf.Computer Vision and Pattern Recognition.［S.l.］:IEEE Press，2004:511－517.

［5］許飛，劉威.多核DSP下的算法優(yōu)化［J］.信息通信，2012，121(5): 42－46.

［6］BONATO V，MARQUESE，CONSTANTINIDESG.A parallel hardware architecture for scale and rotation invariant feature detection［J］.IEEE Trans.Circuits and Systems for Video Technology，2008，18(12):1703－1712.

［7］薛順瑞，高原，唐湘成，等.基于FPGA并行處理SIFT算法特征點(diǎn)檢測(cè)［J］.電視技術(shù)，2013，36(23):188－192.

［8］QIU J，HUANG T，IKENAGA T.A FPGA－based dual－pixel processing pipelined hardware accelerator for feature point detection Part in SIFT［C］//Proc.the 5th International Joint Conference on INC，IMS and IDC.［S.l.］:IEEE Press，2009:1668－1674.

［9］HUANG F，HUANG S，KER J，etal.High－performance sifthardware accelerator for real－time image feature extraction［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，22(3):340－351.

Real－time Im plementation of Sift Feature Extraction Algorithm s in FPGA

LU Kaili1，GENG Junmei2，GU Guohua1，QIANWeixian1，XU Fuyuan1
(1.College of Electric＆Optic，Nanjing University of Science and Technology，Nanjing 210094，China; 2.Jiyuan Vocational and Technical College，Henan Jiyuan 454650，China)

In order to extract real－time feature point of target in the system ofmoving target detection and tracking system，thus completing the realtime imagematching operation，the feature extraction algorithm is proposed to achieve SIFT in FPGA.The SRAM reuse technology is used to simplify the procedures，and themodule structure of FPGA is designed reasonably.Besides the fixed－point decimal is used to ensure the accuracy of algorithm.The whole algorithm is realized in the Virtex－5 hardware platform and the verilog language isused for thewriting and debugging of programs.The resultshows that the optimized SIFT algorithm can be realized in FPGA stably，butalso the complexity of algorithm is reduced and accuracy is achieved，which imshows the algorithm has a good real time feature.

FPGA;feature extraction algorithm;SRAM;Virtex－5;real－time

TN391

A

?? 雯

2014－03－03

【本文獻(xiàn)信息】陸愷立，耿俊梅，顧國華，等.SIFT特征提取算法的FPGA實(shí)時(shí)實(shí)現(xiàn)［J］.電視技術(shù)，2014，38(13).

國家自然科學(xué)基金項(xiàng)目(61271332);江蘇省“六大人才高峰”支持計(jì)劃項(xiàng)目(2010－DZXX－022)