骆开庆， 杨 坤， 张 健， 肖 化

(华南师范大学物理与电信工程学院，广州 510006)

特征点指的是图像灰度值发生剧烈变化的点或者在图像2个边缘上的交点，是图像中重要的局部特征，其提取效果的好坏将直接影响应用的结果.

原则上，优秀的算法不仅保证在严格要求下的实验精度，也要考虑其计算速度. 目前已有许多特征提取的算法. 如：SIFT(Scale-Invariant Feature Transform)算法[1]，该算法具有良好尺度、旋转和亮度的不变性，但存在计算量大、运算时间长的问题；SURF(Speeded Up Robust Features)算法[2]，该算法利用积分图像和盒状滤波来近似高斯滤波的方法对SIFT算法进行改进，虽然比SIFT算法提取速度更快，但是仍需要较长时间构建描述子；ORB(Oriented FAST and Rotated BRIEF)算法[3]，该算法最大的优势在于计算速度非常快，但是当图像变化较大时效果不好；BRISK特征提取算法[4]，该算法平衡了高质量的描述子和低计算需求这2个相互矛盾的目标. 为了提高BRISK特征点的性能，近些年来，学者们做了大量的研究. 如：黄钰雯等[5]提出了改进的SURF-BRISK的算法；赵婷等[6]提出了结合区域分块的改进BRISK算法；CEN等[7]提出了基于GMS算法的改进BRISK算法. 这些改进的BRISK算法均提高了特征匹配的精度，但提取到的特征点都存在分布不均匀的现象，导致图像局部信息丢失. 2015年，MUR-ARTAL等[8]首次指出使用四叉树的方法来改善这种特征点分布不均匀的现象.

基于上述分析，为提取均匀分布的特征点、提高特征点匹配精度和降低算法的运行时间，本文提出了基于四叉树的改进BRISK特征提取算法(Quad-BRISK算法)，并选取3个具有代表性的算法(SIFT、ORB、BRISK算法)与Quad-BRISK算法进行测试对比实验.

1 Quad-BRISK特征提取算法

Quad-BRISK特征提取算法采用四叉树均匀化FAST(Features from Accelerated Segment Test)算法[9]在图像金字塔[10]上提取的特征点;运用灰度质心法[11]替换传统BRISK算法，采用长距离点集计算特征点的方向；通过在图像局部区域内建立BRISK特征描述符，最终用于图像匹配.

1.1 提取特征点

FAST特征点检测主要检测局部像素灰度变化明显的地方(图1):取图像中的某个像素点K，并以点K为圆心选取半径为3的Bresenham圆上的16个像素点，如果这16个点中有连续12个点的灰度值I(x)与点K的灰度值I(K)的灰度距离大于设定的阈值T，那么点K为特征点. 如果图像中每个像素点都与其Bresenham圆上的12个点的灰度值比较，会耗时较多. 因此，可以增加一个预测试步骤，以快速剔除大多数不是角点的像素：对每一个像素，先计算圆上序号为 1、5、9、13的4个像素点与像素点K的灰度值差的绝对值，其中至少要有3个点的结果大于阈值T，才接着检测圆上其他像素点，否则舍弃点K.

图1 FAST特征点检测[9]

但是，特征点是具有尺度的，在不同尺度下对同一个点进行检测，检测的结果可能有所不同. 所以，需要构建图像金字塔，在图像金字塔的每层图像上进行FAST特征点检测，从而得到具有尺度的特征点.

1.2 划分特征点

使用FAST算法提取的特征点存在扎堆的情况[12]，为了将图像中提取的特征点均匀化，需要采用四叉树对特征点进行划分:在图像二维空间上利用四叉树的结构，将这个二维空间按特征点的分布情况进行分块，再对每个块中的特征点进行处理. 其处理步骤如下：第一步，设整幅图像为一个大块，则其为初始节点，可得到初始的四叉树结构. 第二步，对图像中所有的节点进行划分操作：如果节点里面的特征点数为0，则删去这个节点；否则，将这个节点分成4个子节点. 第三步，重复进行第二步，直到最终生成的节点个数不小于设置提取特征点的个数或者达到最大的节点个数，则结束划分节点. 第四步，从每个节点中选取Harris响应值[13]最高的特征点.

对已经提取FAST特征点的图像，采用四叉树方法划分特征点，划分前图像中提取出的特征点明显分布不均匀(图2A). 按照上述步骤对图像中的特征点进行四叉树划分后(图2C)，每个节点中特征点至少大于1个，在节点中选取1个特征点作为该节点下的特征点，使得图像中的特征点均匀分布(图2D).

图2 四叉树方法划分特征点

1.3 计算特征点的方向

FAST特征点检测出来的特征点不具备旋转不变性，当图像发生旋转时检测效果较差. 为了使图像发生旋转后还能检测出是同一个特征点，使用灰度质心法将提取到的特征点设置为带方向的特征点，具体步骤如下：

(1)以特征点为中心的图像块B的矩为：

(1)

其中，p,q={0,1}，mpq为图像块的矩，qp为矩的阶数的系数，x和y为图像块B中像素点的坐标值，I(x,y)为像素点(x,y)处的灰度值；

(2)通过以下公式计算该图像块的质心：

(2)

其中，m00是图像块的0阶矩，m01和m10是图像块的1阶矩；

(3)将图像块的几何中心O与质心C相连，得到方向向量OC，于是特征点的方向定义为：

(3)

通过以上步骤，计算出特征点的方向. 在建立该特征点描述符的时候，采用此处计算的方向将该特征点进行旋转，使该点具有旋转的描述，从而提高了在不同图像之间表达的稳定性.

1.4 建立BRISK特征点描述符

通过FAST算法检测确定了特征点在图像中位置信息之后，为了能够与另外一张图片进行特征点匹配，需要提取特征点周围的环境信息，即建立BRISK特征点描述符. 通过对比2张图片中特征点的周围环境信息的相似度来判定是否为同一个特征点.

1.4.1 采样模式 BRISK特征点描述符是利用关键点的邻域进行采样，其采样模式如图3所示，一共采样N个点.

为了避免混叠效果，对采样模式中的采样点Pi进行高斯平滑，标准差σi正比于每个采样点对应于各自中心的距离，定位和扩展模式在图像中相应地为关键点K模式化，考虑一个N(N-1)/2个采样点对，用集合(Pi,Pj)表示. 这些点的平滑像素值分别为I(Pi,σi)和I(Pj,σj)，用于估计局部梯度值g(Pi,Pj)的公式为：

(4)

所有组合方式的集合称为采样点对：

A={(Pi,Pj)2×2|i

(5)

短距离点对子集S为：

(6)

其中，阈值距离设置为：δmax=9.75t，t是特征点K所在的尺度.

(7)

1.5 描述符匹配

将采样的短距离子集中的512个点对，根据式(7)得到该特征点的512 Bit的二进制描述符. 在匹配2个BRISK特征点时，通过2个特征点描述符之间的汉明距离来表示这2个特征点周围的环境信息的相似性：汉明距离越小，相似性越高.

1.6 Quad-BRISK算法步骤

Quad-BRISK算法与传统BRISK算法的不同之处在于：提取BRISK特征点时采用四叉树方法划分特征点,使特征点均匀分布；特征匹配时采用分块区域匹配，减小了匹配范围，提高了匹配的精度；使用灰度质心法给每个特征点计算方向；使用旋转一致性原则剔除部分误匹配点，进一步提高了特征点的匹配精度. 主要步骤如下：

(1)将图像构造8层尺度为1.2的图像金字塔，设置图像金字塔中每层图像要提取的特征点数量；

(2)将图像金字塔的每一层图像划分为N个边长为30像素的矩形区域(图像边缘进行融合处理)，分别在这N个区域中做FAST关键点提取，当检测到FAST关键点的数量为0时，降低算法阈值并重新进行关键点提取，使得在弱纹理区域也能提取到关键点；

(3)将图像金字塔的每层图像中提取到的特征点按层进行四叉树划分；

(4)剔除每个节点中Harris响应值非极大值的特征点；

(5)采用灰度质心法计算每个特征点的方向；

(6)计算特征点的BRISK描述符；

(7)将特征点划分在图像中对应的网格区域内，并在2幅图像对应的网格区域内做特征点匹配；

(8)根据劳氏算法[1]，使用比较最近邻距离与次近邻距离的方法剔除误匹配点，最后采用RANSAC算法[14]，得到精匹配图像.

2 实验结果与分析

为了验证本文算法(Quad-BRISK算法)匹配精度的优越性，选取3个近期具有代表性的算法(SIFT、ORB、BRISK算法)与Quad-BRISK算法进行测试对比，比较各种算法在不同图像上的处理时间.

2.1 实验数据

选择Mikolajczyk和Schmid的特征对比试验图集[15]中的5组图像(图4)，每组6幅图像. 其中：利用Graf图像组测试各算法在仿射变化下的匹配效果；利用Boat图像组测试各算法在尺度和旋转变化下的匹配效果；利用Trees图像组测试各算法在模糊变化下的匹配效果；利用Leuven图像组测试各算法在光照变化下的匹配效果；利用UBC图像组测试各算法在不同压缩程度下的匹配效果.

图4 Oxford标准图集

2.2 实验环境与评价标准

本文的实验平台为：操作系统为Linux 16.04 64位的台式电脑，Intel(R) Core(TM)i7-7700 CPU@3.60 GHz 8 GB内存，运行环境为CLion 2.0和Opencv2.4.9.

本文的实验评价指标为：(1)算法消耗的时间. 用此指标来评价算法进行特征检测和匹配的速度,消耗的时间越短表明其速度越快. (2)特征点匹配正确率(Correct Matching Rate，CMR)[16]. 其计算公式为：

(8)

其中，mc为RANSAC之后正确匹配个数，m为最近邻与次近邻距离和旋转一致性筛选后匹配个数. CMR值越大，表示该算法的匹配效果越好.

2.3 结果分析

本文选择5组测试图像对各算法进行测试，以第1幅图为标准图像，后面5幅图像为待匹配图像. 以下各表中，组号1表示第1幅图与第2幅图的匹配结果，组号2表示第1幅图与第3幅图的匹配结果，以此类推. 其中，SIFT、ORB、Quad-BRISK算法提取每张图像中的1 000个特征点，BRISK算法提取每张图像中的所有特征点.

2.3.1 仿射不变性实验 Graf图像组的每个图像具有不同的视角，故用于测试SIFT、ORB、BRISK、Quad-BRISK算法对于仿射变化的适应性.

从实验结果(表1)可以看出：在第1组和第2组实验中，Quad-BRISK算法的匹配率高于其他算法；在第3～5组的这些仿射变换较大的实验组中，各种算法的鲁棒性都不是很好. 由Graf图像组中第1幅图和第2幅图的特征点匹配效果(图5)可以看出：SIFT、ORB、Quad-BRISK算法同时提取相同个数的点，由于Quad-BRISK算法采取更加严格地剔除误匹配点的方式，所以匹配点也减少了；虽然，BRISK算法提取的特征点较多，最终匹配的特征点也较多，但其匹配正确率最低.

表1 4种算法在图像仿射变化下特征点的匹配正确率

Table 1 The correct matching rate of feature points in four algorithms under image affine changes %

组号SIFTORBBRISKQuad-BRISK182.3990.7582.0392.78267.1872.8266.4591.433----4----5----

注：“-”表示特征点匹配正确率过低或者算法失效，无意义.

2.3.2 尺度和旋转不变性实验 Boat图像组的每个图像具有不同的尺度和旋转变换，故用于测试SIFT、ORB、BRISK、Quad-BRISK算法对于尺度和旋转变化的适应性.

图5 4种算法在Graf图像中的特征点匹配效果

Figure 5 The feature point matching effect images of four algorithms in Graf images

由测试结果(表2)可以看出：在第1组和第2组实验中，Quad-BRISK算法对尺度和旋转不变性实验图像的匹配正确率分别为91.57%和100%，除在第1组实验中略低于ORB算法，均高于其他算法；其他尺度和旋转变化较大的实验中，各种算法的鲁棒性都不是很好. 由Boat图像组中第1幅图和第2幅图的特征点匹配效果(图6)可看出：Quad-BRISK算法提取的体征点分布更加均匀，不存在明显的扎堆现象；其他3种算法提取的特征点均存在聚集的现象，且ORB算法提取的特征点的扎堆现象最明显.

表2 4种算法在图像尺度和旋转变化下特征点的匹配正确率

Table 2 The correct matching rate of feature points in four algorithms under image scale and rotation changes

%

注：“-”表示特征点匹配正确率过低或者算法失效，无意义.

图6 4种算法在Boat图像中的特征点匹配效果

Figure 6 The feature point matching effect images of four algorithms in Boat images

2.3.3 光照不变性实验 Leuven图像组的每个图像具有不同的光照强度，故用于测试SIFT、ORB、BRISK、Quad-BRISK算法对于光照变化的适应性.

由测试结果(表3)可以看出：SIFT、ORB、Quad-BRISK算法在不同光照的情况下都可以正常运行；Quad-BRISK算法的匹配正确率最高，其次为ORB算法. 由Leuven图像组中第1幅图和第2幅图的特征点匹配效果(图7)可以看出：Quad-BRISK算法提取的特征点分布更加均匀，不存在明显的扎堆现象；SIFT算法和ORB算法在图片的下方提取的特征点很少，都在图片的上方提取，扎堆现象较明显.

表3 4种算法在图像光照变化下特征点的匹配正确率

Table 3 The correct matching rate of feature points in four algorithms under image lighting changes

%

注：“-”表示特征点匹配正确率过低或者算法失效，无意义.

图7 4种算法在Leuven图像中的特征点匹配效果

Figure 7 The feature point matching effect images of four algorithms in Leuven images

2.3.4 模糊不变性实验 Trees图像组的每个图像具有不同的模糊程度，故用于测试SIFT、ORB、BRISK、Quad-BRISK算法对于模糊程度变化的适应性.

由测试结果(表4)可以看出：Quad-BRISK算法在不同模糊程度的情况下都可以较好地运行，特征点的匹配精度大部分时候高于其他算法. 由Trees图像组中第1幅图和第2幅图的特征点匹配效果(图8)可以看出：4种算法提取的特征点都没有较严重的扎堆现象，其中Quad-BRISK算法提取的特征点分布更加均匀.

表4 4种算法在图像模糊变化下特征点的匹配正确率

Table 4 The correct matching rate of feature points in four algorithms under image blur changes

%

注：“-”表示特征点匹配正确率过低或者算法失效，无意义.

2.3.5 压缩不变性实验 UBC图像组的每个图像具有不同的压缩程度，故用于测试SIFT、ORB、BRISK、Quad-BRISK算法对于不同压缩程度的适应性.

图8 4种算法在Trees图像中的特征点匹配效果

Figure 8 The feature point matching effect images of four algorithms in Trees images

由测试结果(表5)可以看出：在图像具有不同压缩程度的情况下，4种算法提取的特征点的匹配精度都较好，其中Quad-BRISK算法的匹配精度高于BRISK算法和SIFT算法，与ORB算法的匹配精度相似. 由UBC图像组中第1幅图和第2幅图的特征点匹配效果(图9)可以看出：SIFT算法和ORB算法提取的特征点存在明显的聚集现象，而Quad-BRISK算法提取的特征点分布较均匀，不存在明显的扎堆现象.

表5 4种算法在图像压缩下特征点的匹配正确率

Table 5 The correct matching rate of feature points in four algorithms under image compression %

组号SIFTORBBRISKQuad-BRISK185.6899.6797.5099.46280.2699.4495.3498.97375.6298.3191.0198.12465.3295.5780.5297.43557.7893.1759.2793.37

图9 4种算法在UBC图像中的特征点匹配效果

Figure 9 The feature point matching effect images of four algorithms in UBC images

2.3.6 运行时间分析 为评估Quad-BRISK算法与SIFT、ORB、BRISK算法的时间复杂度，选取Graf、Boat、Trees、Leuven和UBC图像组的第1、2幅图像(即第1组)，统计分析使用4种算法在每张图片中提取1 000个特征点需消耗的平均时间. 由结果(表6)可知：SIFT算法耗时最多；ORB算法耗时最少；Quad-BRISK算法相比于传统的BRISK算法耗时更少，因为Quad-BRISK算法是先将特征点划分到图像中相应的网格区域内，然后再对2幅图像对应区域内的特征点做匹配，加速了特征点的匹配效率，所以，Quad-BRISK算法在提高精度的同时也减少了运行时间. 此外，对每个图像组中的其他图像的消耗时间也进行了对比分析实验，最终的时间对比分析趋势与此类似，不一一赘述.

表6 4种算法的运行时间分析

Table 6 The analysis of the running time of four algorithms ms

图集SIFTORBBRISKQuad-BRISKGraf469.929.16121.983.89Boat564.439.38144.0113.80Trees746.656.16224.7154.90Leuven495.227.12118.076.47UBC498.232.82120.698.95

3 结论

本文提出了基于四叉树的BRISK特征提取算法(Quad-BRISK算法)：针对原始BRISK算法提取的图像特征点分布不均匀的缺点，采用了四叉树方法划分特征点；使用灰度质心法替换传统BRISK采用长距离点集计算主方向的方法，提高了旋转一致性的稳定性；在粗匹配结果中采用旋转一致性剔除误匹配点，进一步提高特征匹配的精度. 在Mikolajczyk和Schmid的5组特征对比试验图集上，使用Quad-BRISK算法与SIFT、ORB、BRISK算法分别进行了5种不同变化场景下的对比实验，并且分析了运行时间. 实验结果表明：Quad-BRISK算法性能优于其他算法，不仅能够提取更加稳定的特征点，同时提高了特征点匹配精度和计算速度. Quad-BRISK算法可进一步应用于更复杂或者更高一级的算法中，如图像拼接算法、三维重建算法及SLAM算法.