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)