基于FAST和BRIEF的图像匹配算法

周莉莉，姜 枫

（1.南京理工大学 泰州科技学院 电子电气工程学院，江苏 泰州225300；2.南京理工大学 泰州科技学院 计算机科学与技术系，江苏 泰州225300）

0 引 言

图像匹配的一般步骤分为三步：首先从图像中提取“兴趣点”，即特征点；然后使用特定的描述器对提取的特征点进行特征描述；最后根据特征描述器进行图像匹配［1－5］。

特征点提取的算法最早使用的是Moravec角点检测器、Harris角点检测器等［6］，角点检测器不仅能检测图像中的角点，而且可以检测图像中像素梯度较大的点。然而Har－ris角点检测器对图像的尺度敏感，不能用于匹配不同尺寸的图像。Lowe等提出了一种基于尺度不变性的特征提取方法［7］，称为尺度不变特征变换 （scale invariant feature transform，SIFT）方 法，SIFT 算 法 中 采 用DOG （difference of Gaussian）算子近似LOG （Laplacian of Gaussian）算子求取图像中特征点，并据此构建梯度直方图判断局部图像主方向，以实现尺度和旋转不变性。在SIFT 算法的基础上，又改进形成了PCA－SIFT、GLOH （gradient location and orientation histogram）等算法。著名的SURF （speeded up robust features）算 法 是SIFT 算 法 的 快 速 实 现 版 本［8］，当中使用了快速Hessian检测器简化了复杂的DOG 计算，以快速定位特征点，其运算速度远快于SIFT。最近，Rosten等提出了可用于实时系统进行特征提取的FAST （features from accelerated segment test）算法［9］，不 同于SIFT和SURF算法，FAST 通过直接计算图像中心像素点和周围像素点的关系即可找出图像中的关键点，其运算速度远快于SIFT 和SURF算法。

关于特征描述算法，最著名的当属SIFT 特征描述器，它是利用关键点附近区域像素的梯度直方图进行运算的，使用了128维的向量来描述图像局部特征，虽然该算法区分度极高，但其计算、存储复杂性高，不适用于实时场合。SURF特征描述器原理和SIFT 描述器基本相同，也是基于局部图像的梯度直方图计算，该描述器维数为64 维。Ke采用PCA 算法对特征向量维数进行压缩，减少了计算复杂性和存储量，但该描述器的区分度不如SIFT。GLOH 描述器也属于SIFT 一类，其性能好于SIFT 描述器，但计算更为复杂。最近提出的BRIEF （binary robust independent elementary features）是一种高速的特征描述器［10］，使用二进制字符串描述特征。除了表述简单之外，BRIEF 表述器的另一大优势在于特征匹配时只需计算海明距离 （Hamming distance），运算速度远快于最近邻等算法。

本文提出的图像特征匹配主要基于FAST 和BRIEF算法。FAST 算法用于提取图像中的特征点，为了进一步提高提取速度，使用了简化的特征测试模板；再将特征点附近的图像片段使用BRIEF 算法进行特征描述，为了克服BRIEF自身不支持图像旋转的不足，利用强度质心的方法计算图像片段的主方向，并据此对特征描述器进行旋转，以达到旋转鲁棒性；最后通过计算特征描述器间的海明距离匹配图像。

1 FAST算法及其改进

FAST 算法起源于SUSAN 算法，其原理描述如下：对于图像中某个中心点p，使用Bresenham 画圆法检测以之为圆心、半径为3.4像素的圆上16个像素点的强度值，如图1所示，下文将该检测模板称作M16。测试准则为，在这16个点中，如果有N 个连续点的强度值均大于p 的强度值Ip加上阈值t，或均小于Ip－t，则认为p 是一个角点（即特征点）。为了加速角点检测速度，可以取N 的值为12，这样只需要先检测图1中1、5、9和13这4个点的强度值，如果p 为角点，则这4个点中至少有3个点的强度值均大于Ip＋t或者均小于Ip－t。只有在上述检测通过后才需要检测剩余的12个点。这种方法虽然方便，但只适用于N 为12的情况，为了开发一个更为普适的算法，FAST算法中引入了机器学习方法。第一步，针对特定的N 和阈值t，使用上述分割测试准则从图像集中检测出所有角点，这个过程中需要检测每个点周围的所有16个点，将检测过的图像作为训练样本。第二步，利用第一步得到的训练样本，根据信息增益最大原则使用ID3算法，训练得到可以对角点进行正确分类的决策树。训练完成后使用决策树对图像中的点进行分类，得到角点和非角点。

图1 FAST 算法角点检测模板

FAST 算法中推荐使用如图1所示的M16模板，相比SIFT 和SURF算法而言其特征点检测速度得到了极大提升。文献 ［11］中指出，可以选择不同的模板进行角点检测。本文在M16模板的基础上进行简化，在角点检测使用3种模板，如图2所示。

图2 角点检测的3种模板

为了评估不同模板的角点响应效果，使用了如图3所示的不同视角的图片集进行测试。

图3 不同模板角点响应实验

图4表示分别采用M16 （连续像素点数目N 分别为9，10，11），M12S，M12D 和M8模板对图3所示的图集进行角点检测得到的效果。分析可发现，FAST 算法中使用的模板尺寸越大，得到的角点数也越多。在模板尺寸相同的情况下，N 值越大则生成的角点越少，且更接近真实角点位置，图4 （a）、（b）在角点位置附件产生了多重响应，图4 （c）产生的角点数少且更靠近真实位置。图4 （f）中的检测结果表明，M8模板的角点响应能力较强。在进行角点检测时，根据Harris角点量［6］施加非最大约束 （non－maxi－mal suppression），以减少角点附近位置的多重响应。

图4 不同模板的角点响应对比

此外，文中还对各种模板的算法运行时间进行比较。如表1 所示，FAST 算法比SIFT 和SURF 算法速度快很多，M16模板的FAST 算法运行时间基本相当，随着模板尺寸的减少，算法运行时间呈逐步递减趋势，M8模板的运行时间约为M16模板运行时间的1/3左右。

表1 不同模板的角点检测时间对比

2 BRIEF算法及其改进

BRIEF是一种图像特征描述器，不同于SIFT 等基于局部图像梯度直方图的计算，BRIEF 算法在S×S 像素大小的图像片段p 上定义了测试τ

式中：x，y——图像片段p中的任意两个像素点，p（x），p（y）——点x 和y 的强度值。接着，在图像片段p中选择n个点对 （x，y），定义一个二进制测试集，BRIEF描述器即为n维的比特字符串，定义如下

n 在实际使用时可以选择128，256或512，对应描述器的长度分别为16字节，32字节和64字节，远低于SIFT描述器的512字节 （128维实数）。

由于点对测试对噪声非常敏感，因此在进行测试前需要对图像进行平滑处理，文献 ［10］中推荐使用高斯滤波器，并对不同的方差σ以及滤波窗口大小进行对比，得出方差为2，窗口大小为9×9比较合适。另外一个问题是如何在图像片段p中选择n 个点对，文献 ［10］中给出了5种不同方案并通过实验进行详细比较，本文中选择方案2，即 （X，Y）服从 （0，S2/25）的高斯分布。

BRIEF是一个高效的局部图像特征描述器，其运算速度快、占用内存资源少，然而其缺陷在于对旋转较敏感。本文采取的改进措施如下，在片段p中使用高斯分布选择出n个点对

然后，将其根据特征点的主方向进行旋转。计算特征点主方向使用强度质心 （intensity centroid）方法［12］，其原理是认为图像片段主方向由其中心和质心间的偏移决定，图像片段的矩定义为

式中：（x，y）——图像中的像素点的坐标，I（x，y）——该点的强度值，为通过矩的计算可以得到质心

在中心和质心之间的向量方向决定了特征点的主方向

将选出的点对S 进行旋转得到Sr＝RθS，其中Rθ为根据θ计算出的旋转矩阵，接着在Sr上进行测试τ即可。

为了测试改进BRIEF算法的旋转不变性，对测试图像进行了人工旋转并增加高斯噪声，比较几种常见算法。如图5所示，SIFT 算法的旋转不变性最优，BRIEF算法对旋转最敏感，本文提出的改进BRIEF算法对抗旋转能力略好于SURF算法。

图5 各种算法旋转不变性测试

3 实 验

为了检验算法的有效性，分别使用人工合成图像以及真实图像数据库对比SIFT、SURF、FAST＋BRIEF和本文算法。实验在Windows 7和Visual Studio 2010环境下，使用OpenCV 2.2自带的SIFT 和SURF算法进行测试。

3.1 算法旋转不变性实验

图6显示了在图像上施加5%的高斯噪声和在不同旋转角度时特征匹配率的情况。由于标准的BRIEF算法不具备旋转不变性，因此当旋转角度大于20度时匹配率下降非常明显。SIFT 算法使用梯度方向直方图计算特征点旋转方向，从实验结果观测，其算法特征匹配率最高，且稳定性能好。SURF算法是基于Haar小波响应的描述子，因此在旋转角度为45度整数倍时性能下降最为明显。本文算法比SIFT 算法匹配率略低，稳定性也较好，抗噪和抗旋转能力都强于SURF算法。

图6 各种算法在噪声和不同旋转角度下的匹配率对比

3.2 真实图像匹配实验

为了测试本文算法在实际图像的运行效果，采用了如图7 （a）所示的两幅图像，两幅图像中包括了尺度、旋转和光照的变换，图7 （b）是进行图像匹配后得到的结果。可以看出尽管存在一些误匹配，但总体匹配效果良好。

3.3 算法性能及运行时间实验

图像数据库多种算法中使用标准测试库，其下载地址为http：//www.robots.ox.ac.uk/～vgg/research/affine/，其中包含了8组不同的图像，每组图像包含了相同场景下的6张图像，这些图像涉及到图像模糊、视角、旋转、尺度、光照、压缩等变化，以综合测试算法的放射不变性能。实验结果列在表2中。

表2 各种算法在真实图像集的匹配率及时间

图7 真实图像匹配

实验中，SIFT 算法采用5组金字塔，每组3层，采用128维向量描述特征，结果表明，该算法的平均匹配率最高，但是由于计算多尺度DOG 耗费了大量的运算时间，不适用于实时检测。SURF算法采用64维的特征描述器，其匹配率较SIFT 稍差，但由于使用快速Hessian检测代替了DOG 计算，整体运行时间比SIFT 算法快。FAST＋BRIEF算法采用普遍使用FAST9 角点检测器，找到的特征数较多，BRIEF采用64位特征描述器，运行时间最短，但由于其对旋转较敏感，匹配率不高。采用本文算法分别使用了3种不同模板，如表2参数一栏所示，其匹配率介于SIFT 算法和SURF算法之间，远高于FAST＋BRIEF 算法，而由于增加了特征点方向计算，运算时间略有增加，但仍低于SIFT 和SUFR 算 法。

4 结束语

本文选择FAST 算法作为图像特征检测器，使用BRIEF算法描述图像局部特征。在此基础上，对FAST 算法的模板进行改进，分别采用12点正方形、12点菱形、8点正方形模板，实验结果表明改进模板的角点检测器在保持角点响应能力的同时计算速度得到进一步提升。同时，为了解决BRIEF算法不支持旋转的问题，通过强度质心的方法计算给特征点标注方向，使得特征描述器具有旋转不变性。最后，通过对人工合成图像以及标准测试图像集的实验，验证本文算法和一些经典的算法相比，在各种视角、尺度、光照、压缩变换等各种情形下，保持了和SIFT 算法近似的高匹配率，优于SURF 算法，而算法运行时间远低于二者，是一种低计算量、性能强的特征匹配算法。

［1］FU Lisi，LIU Pengwei，LI Dandan.Improved moment invariant characteristics and object recognition ［J］.Computer Engineering and Applications，2012，48 （31）：183－185 （in Chinese）.［付立思，刘朋维，李丹丹.一种改进的不变矩特征与物体识别 ［J］.计算机工程与应用，2012，48 （31）：183－185.］

［2］HU Qiong，QIN Lei，HUANG Qingming.A survey on visual human action recognition ［J］.Chinese Journal of Computers，2013，36 （12）：2512－2524 （in Chinese）.［胡琼，秦磊，黄庆明.基于视觉的人体动作识别综述 ［J］.计算机学报，2013，36 （12）：2512－2524.］

［3］FAN bo，YANG Xiaomei，HU Xueshu.Super－resolution image reconstruction algorithms based on compressive sensing［J］.Journal of Computer Applications，2013，33 （2）：480－483 （in Chinese）. ［樊博，杨晓梅，胡学姝.基于压缩感知的超分辨率图像重建 ［J］.计算机应用，2013，33 （2）：480－483.］

［4］ZHANG Mingjie，KANG Baosheng.Modified object detection and automatic tracking method ［J］.Computer Engineering and Design，2014，35 （4）：1308－1311 （in Chinese）.［张明杰，康宝生.改进的目标检测与自动跟踪方法研究 ［J］.计算机工程与设计，2014，35 （4）：1308－1311.］

［5］JIAO Lilong，HAN Xie，LI Dingzhu.Improved image mosaic algorithm based on feature points matching［J］.Computer Engineering and Design，2014，35 （3）：918－922 （in Chinese）. ［焦丽龙，韩燮，李定主.改进的基于特征点匹配的图像拼接融合算法［J］.计算机工程与设计，2014，35 （3）：918－922.］

［6］ZHANG Yong，JI Dongsheng.Improved Harris feature point detection algorithm ［J］.Computer Engeering，2011，37（13）：196－198 （in Chinese）. ［张永，纪东升.一种改进的Harris特征点检测算法 ［J］.计算机工程，2011，37 （13）：196－198.］

［7］HANG Long，GUO Li，LI Yuyun.SIFT algorithm parallel implementation and application ［J］.Computer Engineering and Applications，2010，46 （20）：56－59 （in Chinese）. ［韩龙，郭立，李玉云.SIFT 算法的并行实现及应用 ［J］.计算机工程与应用，2010，46 （20）：56－59.］

［8］SHOU Zhaoyu，OUYANG Ning，ZHANG Huajun，et al.Research on real－time video stitching based on SURF and dynamic ROI［J］.Computer Engineering and Design，2013，34（3）：998－1003 （in Chinese）. ［首照宇，欧阳宁，张华俊，等.基于SURF和动态ROI的实时视频拼接 ［J］.计算机工程与设计，2013，34 （3）：998－1003.］

［9］Rosten E，Porter R，Drummond T.Faster and better：A machine learning approach to corner detection ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32 （1）：105－119.

［10］Calonder M，Leptit V，Strecha C.BRIEF：Binary robust independent elementary features ［G］.LNCS 6314：Computer Vision－ECCV.Berlin：Springer Berlin Heidelberg，2010：778－792.

［11］Mair E，Hager G，Burschka D，et al.Adaptive and generic corner detection based on the accelerated segment test ［G］.LNCS 6312：Computer Vision－ECCV.Berlin：Springer Berlin Heidelberg，2010：183－196.

［12］Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF ［C］//In International Confe－rence of Computer Vision，2011：2564－2571.