SIFT特征提取算法的FPGA實時實現

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

(1.南京理工大學電光學院，江蘇南京210094;2.濟源職業技術學院，河南濟源454650)

SIFT特征提取算法的FPGA實時實現

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

(1.南京理工大學電光學院，江蘇南京210094;2.濟源職業技術學院，河南濟源454650)

為了在運動目標檢測與跟蹤系統中能夠實時地提取目標的特征點，從而完成圖像實時匹配操作，提出了在FPGA實現SIFT特征提取算法。該算法采用SRAM復用技術簡化程序，合理設計FPGA各模塊結構。此外，該算法采用定點小數來保證算法的精度要求。整個算法在Virtex－5硬件平臺上實現，采用verilog語言進行程序的編寫和調試。結果分析表明，優化后的SIFT算法能夠穩定地在FPGA上實現，同時算法的復雜度得到了降低并達到了精度要求，且具有良好的實時性。

FPGA;特征提取算法;SRAM;Virtex－5;實時性

運動目標檢測與跟蹤系統［2］涉及到圖像匹配［3］的問題。考慮到復雜場景中拍攝的圖像容易發生平移、旋轉或者尺度的變換，所以采用SIFT算法［1］可以較好地解決這一問題。

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

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

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

1 算法介紹及參數選擇

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

1.1 算法優化

因為高斯卷積在SIFT算法中是影響運算速度的關鍵因素，為了使算法在FPGA平臺上易于實現，本文對高斯濾波部分進行了優化:

1)采用級聯方式搭建高斯金字塔

2)二維高斯卷積的拆分

二維高斯卷積公式如下

對于二維的高斯卷積，如果采用7×7模板，每次都要采用49個乘法器，硬件邏輯資源消耗較多。考慮到二維高斯卷積的公式可以拓展為一維高斯卷積的乘積

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

1.2 參數選擇

SIFT算法在硬件平臺上實時實現的同時，為了保證求取的特征描述子精度能夠滿足后端算法匹配要求，要對系統參數進行合理選取:

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

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

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

圖1 一維高斯卷積曲線

圖2 資源占用圖

2 算法的FPGA實現

本設計以Xilinx公司的Virtex－5系列的XC5VFX30T為核心主芯片，它可以提供較為豐富的內部存儲資源和邏輯資源，同時外部選擇適量異步單端口SRAM作為存儲芯片。利用硬件平臺提供的千兆網端口，可以使圖像數據傳輸速率達到1 000 Mbit/s，所以系統可以利用千兆網實現數據的實時傳送。

在本設計中，實時圖像(320×256)以25 f/s(幀/秒)的速度通過PAL口傳輸到FPGA平臺上，通過SIFT算法模塊求得特征描述子后，利用千兆網將結果發送至PC端供后端算法匹配處理。為了便于結果分析，也同時將特征點及其主方向通過千兆網傳輸到PC端進行顯示。

如圖3所示，本文將算法主要分為以下幾個模塊:高斯濾波級聯和高斯差分模塊、梯度計算模塊、極值點檢測模塊，以及求取主方向和特征描述子模塊。

圖3 算法模塊流程圖

2.1 具體結構設計

大部分文章用FPGA實現SIFT時考慮的一個主要方面是節省內部存儲空間，而本文利用FPGA中空間換取時間的概念，充分利用Virtex－5開發板外置多片SRAM的特點，巧妙地利用SRAM復用技術，有效地提高SIFT算法的運算速度。

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

圖4 FPGA具體結構框架

2.2 定點數選取

原始灰度圖像數據為8位無符號數，但因為高斯卷積模板中包含小數，卷積后的數據寬度會相應增加，因此采用定點小數表示。本文通過對比各模塊數據的大小，合理選擇定點數的位寬，從而有效提高利用率和速度。系統中各部分的數據位寬如表1所示。

表1 不同模塊數據類型及寬度表

2.3 高斯濾波級聯與高斯差分模塊

2.3.1 框架結構

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

圖5 高斯濾波級聯模塊和高斯差分模塊流程圖

2.3.2 二維高斯卷積的實現

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

圖6 二維高斯卷積計算流程圖

2.4 極值點檢測模塊

如圖7所示，從數據緩存器1中讀取要尋找極值的高斯差分圖像數據，輸入比較器的同時，根據中心點的坐標從數據緩存器2中讀出中心點相鄰26個點的高斯差分值，然后依次與中心點的值進行比較，若判斷是極值則存儲到數據緩存器3中;若不是極值則繼續從數據緩存器1中讀出數據進行上述操作。這里的3個數據緩存器均用FIFO實現。

圖7 極值點檢測模塊流程圖

2.5 梯度計算模塊

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

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

主方向和特征描述子求取主要工作分為讀取SRAM梯度信息和直方圖統計兩塊。根據FPGA讀取坐標的特點，選取鄰域為方形區域進行統計直方圖;另外由于每一個特征點相互不影響，所以可以采用高速時鐘從SRAM讀取特征點鄰域值，然后用并行的方式進行統計直方圖。

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

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

3 實驗結果

本文討論的SIFT算法在Xilinx的Virtex－5硬件平臺上的實現，采用ISE13.1軟件和verilog語言來編寫程序，將計算得到的特征點和其主方向以及特征描述子利用千兆網傳送到PC上進行顯示和后續匹配。

下面從特征點的準確性和實時性以及FPGA資源消耗三方面來對結果進行分析。

3.1 準確性分析

3.1.1 特征點有效性分析

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

圖8 不同場景下特征點效果圖

為了充分觀察SIFT算法在硬件平臺上求取特征點的有效性，將上述4組場景圖像在FPGA中求取的特征點個數和在MATLAB中求取的特征點個數進行對比，如表2所示。

表2 FPGA特征點與MATLAB特征點對比表

從表2可以看出，對于4種不同的場景，采用FPGA求得的特征點個數與MATLAB求得的特征點個數相近，而且重合點數較多，說明重合率較高，有效性好。

3.1.2 特征描述子準確性分析

以圖8b為例，對FPGA和MATLAB重合的228個特征點在兩個平臺上分別求取特征描述子，然后歸一化取模進行對比，比較曲線如圖9所示。

為了計算FPGA與MATLAB實驗結果的相對誤差，利用誤差公式

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

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

圖10 相對誤差曲線

3.1.3 特征點匹配可行性分析

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

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

圖11 平移、旋轉、尺度變換特征點匹配圖

3.2 實時性分析

為了檢驗SIFT算法在FPGA上實現的加速效果，將本文算法與主頻為2.1 GHz的Intel平臺下算法以及其他在FPGA平臺下實現的算法進行耗時對比，如表3所示。

表3 SIFT算法耗時對比表

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

3.3 FPGA資源消耗

由表4可以看出，在系統搭建完成后，FPGA剩余邏輯資源和存儲資源較多，可以為后端算法提供足夠的空間裕量。

表4 FPGA資源占用表

4 結論

本文主要研究了SIFT特征提取算法在Virtex－5平臺上的實現方式，通過合理選擇參數以及復用SRAM技術在保證特征點精度的同時保證了算法的實時性。相比之前學者們在FPGA平臺上對SIFT的研究，本文改變了高斯金字塔的搭建方式，從并聯轉為級聯的同時確保了算法的并行性;同時通過適量緩存器保證了模塊之間的銜接性，保證了時序的穩定。最后驗證得到本文提出的方法圖像處理速度可以達到38 f/s，具有較好的實時性，同時精度也滿足后端匹配的要求。

［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下的算法優化［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算法特征點檢測［J］.電視技術，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

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

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