基于二进制特征描述器的图像匹配算法＊

姜 枫，周莉莉，李 丛

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

1 引言

图像匹配是计算机视觉中的一个基本问题，在现实生活中有着很多应用，如物体识别、动作识别、三维图像重建、视频目标跟踪、全景图像拼接等。其一般步骤是首先从图像中选出“兴趣点”，即特征点，然后对特征点进行特征描述，最后根据描述的特征进行匹配。

早期使用较多的特征点提取算法是Moravec角点检测器、Harris角点检测器等［1，2］，角点检测器不仅能检测图像中的角点，而且可以检测图像中像素梯度较大的点。然而，Harris角点检测器对图像的尺度敏感，不能用于检测不同尺寸的图像。Lowe D G［3］提出了一种基于尺度不变性的特征提取 方 法，称 为SIFT （Scale Invariant Feature Transform）方法，SIFT 算法中采用DOG（Difference of Gaussian）算 子 近 似LOG（Laplacian of Gaussian）算子求取图像中特征点，并据此构建梯度直方图判断局部图像主方向，以实现尺度和旋转不变性。著名的SURF（Speeded Up Robust Features）算法是SIFT 算法的快速实现版本［4］，当中使用了快速Hessian检测器简化了复杂的DOG 计算来快速定位特征点，其运算速度远快于SIFT。Rosten E 等人［5］提出了可用于实时系统进行特征提取 的FAST（Features from Accelerated Segment Test）算 法，不 同 于SIFT 和SURF 算 法，FAST 通过直接计算图像中心像素点和周围像素点的关系找出图像中的关键点，其运算效率远高于SIFT 和SURF算法。

关于特征描述算法，最著名的当属SIFT 特征描述器［3］，它是基于关键点附近区域像素的梯度直方图进行运算的，使用了128维的向量来描述图像局部特征，虽然该算法区分度极高，然而其计算、存储复杂性高，因此不适用于实时场合。SURF特征描述器原理和SIFT 描述器原理基本相同，也是基于局部图像的梯度直方图计算，该描述器为64维［4］。Ke Y［6］采用PCA 算法对特征向量维数进行压缩，减少了计算复杂性和存储量，但该描述器的区分度不如SIFT。GLOH 描述器［7］也属于SIFT 一类，其性能好于SIFT 描述器，但计算更为复杂。最近提出的BRIEF（Binary Robust Independent Elementary Features）［8］是一种高速的特征描述器，使用二进制字符串描述特征，除了表述简单之外，在特征匹配时直接计算海明距离（Hamming Distance），运算速度远快于最近邻等算法。Rublee E 等 人［9］在BRIEF 的 基 础 上 提 出了ORB（Oriented FAST and Rotated BRIEF）算法，使用强度质心（intensity centroid）方法克服了BRIEF不支持图像旋转的局限性。Trzcinsi T 等人［10］采用增强的二进制哈希函数进行计算得到光照和角度不变性的描述器。BRISK（Binary Robust Invariant Scalable Keypoints）［11］使 用AGAST［12］加速角点检测速度，利用尺度空间金字塔实现图像的尺度不变性，点对的采样不同于BRIEF的随机方式，而是以特征点为中心使用对称模式采样。

本文中，简化FAST 算法模板提取图像中的特征点，通过引入图像金字塔使其具有尺度不变性；根据人类视觉系统原理，改进BRIEF的点对选择方式描述特征，并通过计算特征点方向引入旋转不变性特征；最后通过计算特征间的海明距离匹配图像。

2 FAST算法及其改进

2.1 FAST算法简介

FAST 算 法 起 源 于SUSAN 算 法［13］，其 原 理描述如下：对于图像中某个中心点p，使用Bresenham 画圆法检测以之为圆心、半径为3.4像素的圆上16个像素点的强度值，如图1所示，下文将该检测模板称作M16。测试准则为，在这16 个点中，如果有N个连续点的强度值均大于p的强度值Ip加上阈值t，或均小于Ip－t，则认为p是一个角点（即特征点）。为了加速检测速度，可以取N的值为12，这样只需要先检测图1中1、5、9和13这四个点的强度值，如果p为角点，则这四个点中至少有三个点的强度值均大于Ip＋t或者均小于Ipt。只有在上述检测通过后才需要检测剩余的12个点，从而提高了检测速度。这种方法虽然方便，但只适用于N为12的情况。为了开发一个更为普适的算法，FAST 算法中引入了机器学习方法［5］。

第一步，针对特定的N和阈值t，使用上述分割测试准则从图像集中检测出所有角点，这个过程中需要检测每个点周围的所有16个点，将检测过的图像作为训练样本。

第二步，利用第一步得到的训练样本，根据信息增益最大原则使用ID3算法，训练得到可以对角点进行正确分类的决策树。训练完成后使用决策树对图像中的点进行分类，得到角点和非角点。

Figure 1 FAST corner detection mask图1 FAST 算法角点检测模板

2.2 简化FAST检测模板

文献［14］中指出，用于快速角点检测可以使用多种不同模板，图2中即为本文用于角点检测的三种不同模板。

为了评估不同模板的角点响应效果，使用了如图3所示的不同视角的图片集进行测试。图4表示分别采用M16（连续像素点数目N分别为9、10、11）、M12S、M12D 和M8模板对图3所示的图集进行角点检测得到的效果。分析可发现，FAST算法中使用的模板尺寸越大，得到的角点数越多。在模板尺寸相同的情况下，N值越大则生成的角点越少，且更接近真实位置，图4a和4b在角点位置附近产生了多重响应，图4c产生的角点数少且更靠近真实位置。图4f中的检测结果表明，M8模板的角点响应能力较强。

Figure 2 3masks for corner detection图2 用于角点检测的三种模板

Figure 3 Images for corner response experiments图3 角点响应实验用图

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

Figure 4 Comparison in corner responses among different masks图4 不同模板的角点响应对比

Table 1 Comparison in corner detection time among different masks表1 不同模板的角点检测时间对比

2.3 尺度不变性

FAST 算法虽然检测角点的速度比较快，但也存在着两个缺点：（1）无法衡量角点量（Cornerness）；（2）缺乏对多尺度的支持。因此，在ORB中，使用文献［2］中提出的角点量的概念，结合图像尺度金字塔，在金字塔的每一层根据Harris角点量施加非最大约束（Non－maximal Suppression）。然而，ORB 中仅在金字塔各层层内施加非最大约束，各层之间并未使用，因此可能造成不同层次间潜在的角点重复探测。

在本文中，除了在金字塔各层内部施加非最大约束外，在各层之间也进行非最大约束，具体做法如下：

首先，根据输入图像构造n层的图像金字塔（n取4），第0层金字塔对应原始图像，第1层金字塔为对第0层图像实施1/2的下采样所得，其余层金字塔的构成依此类推。

Figure 5 Keypoints detection in scale space图5 尺度空间特征点检测

在进行角点检测时，先在金字塔的每层使用相同的阈值t运行FAST 算法，计算出所有潜在的特征点区域。接着，对这些区域的点施加非最大约束条件，分为两个步骤：（1）将该点与相邻的8个点比较；（2）将该点与上层9个点及下层9个点进行比较。由于各个层次的尺度不同，因此在计算相邻层次对应点时需要进行插值运算，如图5所示。为了在第0层图像施加非最大约束，需要使用图像上采样，在第0层以下虚拟出一个－1层图像。

图6显示了特征点检测的效果，图6a和图6b中涉及尺度和旋转变化，图中圆的大小表示特征点的尺度，圆中的径向表示特征点的方向，方向的计算在3.3节介绍。

Figure 6 Results of keypoints detection in a boat image set图6 在Boat图像集上进行特征点检测结果

3 BRIEF算法及其改进

3.1 BRIEF算法简介

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

其中，x、y是图像片段p中的任意两个像素点，p（x）、p（y）分别为点x和y的强度值。

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

3.2 点对采样模式

BRIEF描述器中一个重要的问题是如何在图像片段p中选择n个点对，文献［8］中给出了五种不同方案并通过实验进行详细比较，得出结论：当（X，Y）服从（0，S2/25）的高斯分布时，效果最好。Vandergheynst P等人［14］提出在对特征点附近点取样时应模仿人类视觉系统成像原理。在取样时为了匹配人类视网膜模型，越靠近特征点中心区域，取样密度越大，离特征点越远，取样密度越小。同时，为了增加采样点对噪声的鲁棒性，对每一个采样点都进行平滑滤波，为了和视网膜模型相匹配，本文对每个采样点使用不同大小的模板进行滤波。这一点有点类似于BRISK 中的做法，区别在于本文采用的滤波模板大小与采样点到特征点中心的距离呈指数关系，并且各个模板之间有重叠部分，如图7所示。

Figure 7 Sampling pattern similar to the retinal ganglion cells distribution图7 模拟视网膜神经节细胞分布的采样模型

采样之后，可以根据式（2）选择点对进行两两测试，以形成二进制描述器。假设采样点的数目为N，则可能产生的点对数为N×（N－1）/2，一般取N为43，则点对数为903，即生成的二进制描述器为903位，这比ORB和BRIEF中使用的描述器都要复杂。因此，如何尽可能压缩描述器位数，选择最有效、最能描述图像特征的点对是本文研究的另一个问题。文献［9］中指出，可以通过分析BRIEF描述器向量的相关性和方差来选择特征区分度大的点对。根据这一思想，本文采用如下方法从训练数据中选择点对：

（1）根据从图像中提取的特征点建立二维矩阵M，其行数为从图像中提取特征点的数目，每一行对应一个特征描述器，当采样点为43个时，如上所述，描述器为903维的向量。

（2）计算每一列的均值。为了使特征的辨识度最大，应保持方差最大。对于二进制的变量来说，均值为0.5会产生最大方差。

（3）根据方差对矩阵的列进行排序。

（4）选出所有均值为0.5的列，在剩余的列中选择与已选列相关性最小的列加入已选列，直至选择的列数达到期望值。

3.3 旋转不变性

BRIEF是一个高效的局部图像特征描述器，其运算速度快、占用内存资源少，然而其缺陷在于对旋转较敏感。本文采取的改进措施如下：

《中国老年人潜在不适当用药目录》判断PIM情况 在795例社区老年患者中，有230例 （28．9%）存在PIM合计275项，其中存在2项以上PIM的患者36例。202例患者 （25．4%）使用了A级优先警示药物共226项，其中高风险强度29项（12．8%）， 低风险强度 197 项 （87．2%）。 44 例患者（5．5%）使用了B级常规警示药物共49项，其中高风险强度 36项 （75．5%），低风险强度 13项（26．5%）。具体情况见表 6和表 7。

在提取的特征点附近使用3.2节所介绍的方法选出n个点对。然后，将其根据特征点的主方向进行旋转。ORB 中使用强度质心（Intensity Centroid）方法计算特征点主方向，其原理是认为图像片段主方向由其中心和质心间的偏移决定。BRISK 中提出，将采样点对分为短距离点对和长距离点对，其中长距离点对的局部梯度之和用于计算特征点主方向。本文在BRISK 的基础上加以改进，如图8 所示，以特征点为中心，选取对称点对（图中用直线表示的45个点对）用于计算主方向，计算公式为：

式（3）中，P表示用于计算特征点方向所选择的所有点对，D为P的数量，Ki是点的空间二维坐标，I（·）表示某个点的像素值。

为了测试本文算法的旋转不变性，对测试图像进行了人工旋转并增加高斯噪声，并将几种常见算法加以对比。图9表明，本文算法的旋转鲁棒性最强。

3.4 特征描述器匹配

Figure 8 Illustration of the selection of pairs for calculating main orientation of the keypoints图8 计算特征点主方向的点对选择示意图

Figure 9 Rotation invariance tests of different algorithms图9 各种算法旋转不变性对比测试

对二进制描述器进行匹配是通过计算两个描述器二进制串之间的海明距离直接进行的，其中海明距离定义为两个二进制串之间对应位置不同比特的数目，在实际计算时可直接使用计算机的异或操作（XOR）。

4 实验结果及分析

在本节中，使用文献［7］中推荐的标准测试图像库，将本文所提算法与SIFT、ORB、BRISK 等进行测试对比。测试库中包含八个图像集，如图10所示，每个图像集中包含相同场景不同条件下的六张图像，如boats和bark 中是旋转和尺度变换，graffiti和wall中包含视角变换，trees和bikes为图像失真，leuven是光照变化，ubc是JPEG 压缩。

实验中，SIFT 算法采用五组金字塔，每组三层，采用128 维实数向量描述特征；ORB 中使用256位 特 征 描 述 器；BRISK 采 用AGAST 算 法［12］检测特征点，512位向量描述特征点；本文算法采用M8模板结合FAST 算法，并在图像金字塔各层间施加非最大约束条件，256位的特征描述器。实验环境使用opencv 2.4.2以及visual studio 2010。

Figure 10 Test image set for experiments图10 实验用测试图像集

测试算法性能使用了文献［7］中推荐的recall/1－precison曲线图。为使测试尽量公平，需要调整不同检测算法的阈值，使检测出的特征点数目尽可能相同。从图11的实验结果表明，本文算法性能在所有测试图像集上均要优于其他算法，算法性能的总体性能排名为本文算法＞BRISK＞ORB＞SIFT。而SIFT 算法总体表现不佳，尤其在trees、ubc、boats等图像库表现更差，是因为SIFT 检测出的特征点可重复性较低。通过图11b和图11d分析可知，本文算法对于图像旋转和尺度变化适应性较其他算法强，而ORB 算法由于不支持图像的尺度变化，因此表现最差。图11中显示，所有算法在光照变化和图像压缩时均表现出较好的适应性。在图像失真情况下，尤其在图11e中，bikes图像库总体表现比trees图像库要好，原因是为了平衡各种算法提取的特征点数目，前者提取的特征点数比后一个图像库提取出的多，因此查全率高。

从表2和表3不难发现，在特征点的检测中，ORB使用了FAST 算子，因此速度远比SIFT 快，BRISK 中使用了AGAST、本文算法简化了FAST检测模板，所以速度又优于ORB。在特征点描述中，ORB、BRISK 和本文算法都使用二进制描述器，因此速度都比SIFT 快，BRISK 和本文算法的点对匹配有固定模式，所以耗时小于ORB。在特征匹配中，SIFT 由于描述器长度最长（512字节），因此平均耗时最长，ORB、BRISK 和本文算法均是根据二进制间的海明距离匹配，所以速度较快，BRISK 描述器长度为512位，而ORB 和本文算法描述器长度为256，所以匹配速度相对较快。

Figure 11 Performance evaluation for different algorithms图11 几种算法性能测试对比

Table 2 Time of detection and descriptor for keypoints表2 特征点检测和描述时间

Table 3 Matching time for keypoints of boat－1and boat－3images表3 boat－1和boat－3图像特征点匹配时间

5 结束语

本文以FAST 算法作为图像特征检测器，使用BRIEF算法描述图像局部特征。在此基础上，对FAST 算法的模板进行简化，实验表明，简化模板的特征点检测器在保持特征点响应能力的前提下计算速度得到进一步提升，并通过构造图像金字塔的方法提升了算法的尺度不变性。同时，模仿视网膜模型改进了BRIEF 算法中点对的采样方式，通过点对之间局部梯度的计算为特征点标注方向，使得特征描述器的旋转不变性更强。最后，通过对标准测试图像集的实验表明，和一些经典的算法相比，本文所提出的算法是一种性能强、运算速度快的特征匹配算法。

［1］ Moraver H.Rover visual obstacle avoidance［C］∥Proc of International Joint Conference on Artificial Intelligence，1981：785－790.

［2］ Harris C，Stephens M.A combined corner and edge detector［C］∥Proc of the 4th Alvey Vision Conference，1988：147－151.

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

［4］ Bay H，Tuytelaars T，Gool L V.SURF：Speeded up robust features［C］∥Proc of European Conference on Computer Vision，2006：404－417.

［5］ 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.

［6］ Ke Y，Sukthankar R.Pca－sift：A more distinctive representation for local image descriptors［C］∥Proc of Computer Vision and Pattern Recognition，2004：506－513.

［7］ Mikolajajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615－1630.

［8］ Calonder M，Leptit V，Strecha C.BRIEF：Binary robust independent elementary features［C］∥Proc of European Conference on Computer Vision，2010：778－792.

［9］ Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF［C］∥Proc of International Conference on Computer Vision，2011：2564－2571.

［10］ Trzcinski T，Christoudias M，Fua P，et al.Boosting binary keypoint descriptors［C］∥Proc of Computer Vision and Pattern Recognition，2013：510－517.

［11］ Leutenegger S，Chli M，Siegwart R.BRISK：Binary Robust Invariant Scalable Keypoints［C］∥Proc of International Conference on Computer Vision，2011：2548－2555.

［12］ Mair E，Hager G，Burschka D，et al.Adaptive and generic corner detection based on the accelerated segment test［C］∥Proc of European Conference on Computer Vision，2010：183－196.

［13］ Smith S M，Brady J M.SUSAN—a new approach to low level image processing［J］.International Journal of Computer Vision，1997，23（1）：45－78.

［14］ Vandergheynst P，Ortiz R，Alahi A.FREAK：Fast retina keypoint［C］∥Proc of Computer Vision and Pattern Recognition，2012：510－517.