基于FAST检测及SIFT描述的特征检测算法

常旭剑，韩 燮，熊风光

（中北大学 计算机与控制工程学院，山西 太原030051）

0 引 言

通常，提取特征点分为两步：特征点检测和特征点描述。特征点检测就是找到图像中的特征点位置以及该特征点周围像素的信息；特征点描述需要在不同变化因素下依旧保持较好的可匹配性。

本文提出一种FAST－SIFT 局部特征探测算法，首先采用FAST 特征检测算法来检测待测图像中的特征点，根据FAST 获得的特征点采用SIFT 特征描述算法对特征点进行描述；对这些获得的描述特征点，采用基于SNR 验证的特征点匹配进行阐述，有效地提高特征点检测的速度及描述的精度，从而提高匹配度。

1 相关工作

许多论文中提出了很多特征检测算法，Canny［1］，Harris［2］，及多尺度Harris［3］；特 征 描 述 算 法SIFT［4］，Affine SIFT［5］等；以及特征匹配算法FLANN［6］等。通过不同特征检测算法与特征描述算法可以构成不同的组合。

1.1 特征检测

John F Canny提出了多级边缘检测算法，是采用寻找图像中亮度梯度的方法，该方法可以快速地找到图像的边缘，但是却无法有效地提取图像的特征点；Schmid等提出利用Harris角点检测提取局部特征，利用Harris提取的局部特征不但具有抗旋转变化的特性，而且对光照及噪声有很强的鲁棒性，但是通过该方法提出的特征在尺度缩放的应用上效果很差；Dufournaud等基于Harris特征检测方法的基础上提出多尺度Harris的特征检测算法，尽管解决了尺度缩放应用问题，但是会提出大量重复特征，大幅增加错误匹配和匹配时间复杂度。直到Lowe提出基于多尺度下不变特征 （scale invariant feature transform，SIFT），此算法在特征检测过程中采用了DoG （difference－of－Gaussian）算子，来构造尺度空间，在每个尺度下，选取出对应尺度空间所有的极值点，这些极值点信息即为所检测图像的特征点。但是由于采用DoG 建立尺度空间，算法的时间复杂度相对较大，比较耗时。

1.2 特征描述

特征描述向量一般是使用一个n维向量来对每个特征点的信息描述。M K Hu［7］提出基于不变矩理论的统计特征提取方法，广泛应用在彩色图像处理中。SIFT 是Lowe提出的，由于SIFT 对尺度、旋转以及光照等变量的变化具有不变性，使得SIFT 特征描述子具有极强鲁棒性，在特征点检测中应用最为广泛。ASIFT （affine sift）在SIFT 的基础上对所有成像视角下得到的图像进行特征匹配，克服了SIFT 在视角变化情况下，尤其是在特别大的视角变化下匹配度不高的缺点。

1.3 特征匹配

在特征检测获得的特征点后，需要进行特征描述，得到描述特征向量，最后通过分析这些特征向量进行分类匹配。本文采用了K－D树进行特征向量匹配。

2 特征点检测与描述

2.1 FAST特征检测算法

很多传统的检测算法如SIFT，SURF 等很耗时，图像处理中第一步一般都是特征检测，如果在这一步耗时太多，显然得不偿失。Edward Rosen 提出的基于像素搜索的FAST （features from accelerated segment test）［8］是 目 前 公认的检测速度较快的特征点检测方法，速度达到毫秒 （ms）级别。

FAST 特征检测算法是基于角点的定义。FAST 算法主要包含3个步骤：

（1）待检测的点周围的一圈像素的灰度值与候选的点的灰度值差别够大，可以认为这个候选点是一个特征点，在二维图像中任意一点圆心坐标 （x，y）。特征点描述算法公式如下

式中：t——阈值， （一般取t＝10），其中定义圆周上任意一点的灰度为Ix，圆心的灰度为Ip。当中心像素的灰度值Ip小于周围圈点x处像素灰度值Ix＋t时，则认为该灰度像素属于更暗的，则Sp→x＝d；以此类推相似的s和更亮的灰度像素点b。这样在这么一个以候选特征点p 为圆心的圆形区域边缘就找到了3种类型的灰度像素点d、s和b。统计d 或b 的次数，如果大于n （当分割测试点数目为12时，即Ix的个数的3／4），则认为该点为候选特征点。本实验中采用模版半径为3，即需要和周围16个像素比较。

FAST 算法特征点检测算法如图1所示。

图1 FAST 算法特征点检测算法

（2）然后，通过固定半径圆上像素的灰度值进行比较获得候选特征点。利用ID3分类器，根据16个特征，判断此候选特征点是否为特征点。将上面步骤获得的d、s、b记作Pd、Ps、Pb，计算得到的Sp→x必定对应式 （1）的某种情况。令Ip为特征点时kp＝true，否则false。从而判定某个像素是否为特征点。

（3）最后，通过ID3决策树算法训练特征点，使用计算角点响应函数。定义一个响应函数V 如下

可以用常规极大值抑制法对非特征点进行排除。

2.2 SIFT特征描述算法

2.2.1 特征点的方向匹配

检测到的局部特征，描述的重点是局部特征的鲁棒性及可区分性。

通过FAST 特征检测算法，已经找到了待处理图像的特征点位置，下一步通过SIFT 算法所提供的特征描述算法来对特征点进行描述，为下一步的匹配做准备。

SIFT 描述算法是采用SIFT 特征探测算法中获得的DoG 金字塔的特征点，采用在高斯金字塔3σ邻域窗口内像素的梯度和方向特征分布，但是本文提出方法采用的不是尺度空间，故梯度的模值及方向如下

式中：L——特征点所在的尺度空间值，按照尺度采样的3σ原则，邻域半径16×16为采样窗口。

特征点的梯度计算过程如图2 所示。首先如图2 （a）中的特征点把周围像素的梯度方向和幅值分别通过式 （3）、式（4）算出，如图2 （b）所示其邻域像素梯度方向和幅值。进一步分割如图2 （c）所示。在圆周0～360°内分割成梯度直方图，45°一柱，分为8柱，其中每个直方图值代表该点方向，直方图最大值即为该关键点方向，如图2 （d）所示。

图2 特征点产生直方图

2.2.2 特征点的特征描述

通过2.2.1特征点的方向匹配的步骤，对于采用FAST找到的每个特征点，都赋予了每个特征点两个重要的信息：位置 （FAST 获得）、方向 （SIFT 赋予）。

接下来，需要为每个特征点建立一个描述向量。使得这些特征点不随着光照、视角的变化而变化等。这个SIFT描述子不但包括此特征点，也包含了特征点周围对其有贡献的其它像素点，使得该特征点描述子具有较高的唯一性，以便可以提高特征点的正确匹配概率。

特征点描述子在4×4的窗口内计算8个方向的梯度学习，那么就是4×4×8＝128维度的向量表征。

3 特征点临近匹配

3.1 特征点匹配

通过FAST检测算法找到待测图像的特征点后，用SIFT特征描述算法把找到的特征点通过4×4×8＝128维度的向量表示，下一步就要通过匹配来验证找到特征点的正确性。

匹配检索的过程包括了存储SIFT 描述特征点的键值以及鉴别待匹配图像中获得的键值。在这里采用的是最优节点优先算法 （best bin first）算法，此算法是SIFT 的作者Lowe在KD－tree算法的基础上的改进，利用BBF计算可以确定概率高的邻域下的特征点，从而减少计算量。

3.2 基于SNR 验证的特征点匹配

3.2.1 基本思路

如图3所示，每个特征点在二维图像中都有一组对应坐标，设与图像（a）中的特征点是 （xai，yai）对应的图像（b）的特征点为（xbi，ybi），那么对应的Δxi＝｜xai－xbi｜及Δbi＝｜yai－ybi｜应该服从正态分布。

如图4为所对应的匹配的高斯分布，首先确定峰值，好的匹配可以找到一个峰值，如图4 （a）中的P1，P2不是一个好的峰值，因为有次高峰值干扰。然后确定对应面积，图4 （b）对应面积越大越好 （实框好于虚框）。

3.2.2 算法实现

最后，确定信噪比，值越高越好。如图5 所示，目标物体逐次和不同场景图片比对，获得不同信噪比SNRn。

图3 特征点匹配

图4 特征点在x、y轴上的差值直方图

图5 目标物体与不同场景匹配信噪比结果

获得信噪比后，可简单采用Max（SNRx）为最佳匹配，但为了进一步提高匹配的精度以及系统鲁棒性。本文采用朴素贝叶斯分类［10］，此方法基本思想是概率统计推理，在各种条件的已知且知道其出现的概率但是存在不确定哪个出现情况下，来做出决策。

4 实验结果与分析

4.1 实验结果

如图6所示为欲检测物体以及干扰物体。

图6 目标检测物及干扰物体

把目标物体a （书）置于高度杂乱的环境中。运行FAST 检测算法，提取出376个FAST 特征点，利用SIFT描述算法描述FAST 检测到的特征点，如图7所示。

FAST特征算法提取在本实验环境下（8－cores，2.4GHz intel i7，16Gb RAM）提取376个特征点用时8ms，SIFT描述符用时183ms。本文中限制FAST点在30像素（为减少获得的总特征点的点数，增强系统的鲁棒性）。

图7 FAST 特征点提取

这些特征关键点都尝试匹配数据库中每个物体／子物体关键点。匹配所有数据库中物体过程耗时57ms。直方图在x轴以及y轴上位移如图8所示标出了匹配的质量：信噪比（SNR），计算了每一个匹配的信噪比。

最后匹配的概率通过使用朴素贝叶斯分类的方法，把数据库中每个物体进行计算。先对所检测物体所在类别进行初步分类，然后在子类内进行检测。实验结果如图9所示。

图8 x轴及y轴上的匹配差值直方图

图9 数据库中物体与场景中物体匹配结果

4.2 实验结果评估

本文提出算法，实验中采用了700 个样本，通过不同的最优化值来计算。本文对FAST 和SIFT 的组合的性能与常见的几个传统组合的速度和性能进行了对比。见表1，可以看到SIFT＋SIFT 的组合是匹配比最高的，但是耗时也是最长的。FAST 是目前检测速度最快的特征提取算法，达到微秒 （μs）级别。其效用比的直方图如图10所示。

5 结束语

本文提出一种全新的FAST－SIFT 局部不变特征的检测和描述算法的组合进行特征点检测的算法，并且将其应用于物体在复杂场景中的匹配。在局部特征检测方面采用速度快的FAST 来进行检测，获得目标图像中的极值点。再采用SIFT 特征描述算法，对获得的特征极值点进行描述，得到了128维的描述向量。在基于SNR 朴素贝叶斯分类的分类匹配，不但结合了FAST 检测快速性，SIFT 描述的准确性，以及贝叶斯分类的鲁棒性，由于前期FAST 检测的简单快速性，大幅度提高了图像匹配的速度，大量图像匹配和减速的实验结果验证了本文算法的有效性。

表1 常见特征点探测描述算法间不同组合耗时对比

图10 常见特征点探测描述算法间不同组合对比效用比

［1］Deng Caixia.Image edge detection algorithm based on improved canny operator ［C］／／International Conference on Wavelet Analysis and Pattern Recognition，2013：168－172.

［2］Wang Xiangyang.Invariant image watermarking using multiscale Harris detector and wavelet moments［J］.Computers ＆Electrical Engineering，2010，36 （1）：31－44.

［3］XU Xianfeng.An improved multi－scale Harris feature point detection method ［J］.Computer Engineering，2012，38 （17）：65－68 （in Chinese）.［徐贤锋.一种改进的多尺度Harris特征点检测方法 ［J］.计算机工程，2012，38 （17）：65－68.］

［4］Lowe D.Distinctive image features from scale－invariant keypoints［J］.International Journal of Computer Vision，2004，60 （2）：91－110.

［5］Morel JM，Yu G.ASIFT：An algorithm for fully affine invariant comparison ［J］.SIAM Journal on Imaging Sciences，2009，2 （2）：1597－1600.

［6］Zhang Xuejie.A physical system for binocular vision through saccade generation and vergence control［J］.Cybernetics and Systems：An International Journal，2009，40 （6）：549－568.

［7］DOU Jianfang.Automatic registration of visible and infrared images based on corners and Hu invariant［J］.Infrsred，2011，32 （7）：23－27（in Chinese）.［窦建方.基于角点和Hu矩不变量的可见光和 红 外 图 像 自 动 配 准 方 法 ［J］.红 外，2011，32 （7）：23－27.］

［8］F rstner W，Gülch.Adaptive and generic corner detection based on the accelerated segment test［G］.LNCS 6312：Proceedings of the European Conference on Computer Vision，2010：183－196.

［9］Jiang Liangxiao.A novel Bayes model：Hidden naive Bayes［J］.Knowledge and Data Engineering，2009 （21）：1361－1371.

［10］Abel G，Nuria L.Improving the assessment of the outcome of nonsynonymous SNVs with a consensus deleteriousness score，condel［J］.American Journal of Human Genetics，2011，88（4）：440－449.