具有局部自适应阈值的SIFT快速图像匹配算法

汪崟， 蒋峥， 刘斌

（1.武汉科技大学 信息科学与工程学院， 湖北 武汉 430080；2.武汉科技大学 冶金自动化与检测技术教育部工程研究中心， 湖北 武汉 430080）

1 引言

图像匹配，也称图像配准或响应，旨在从两个或多个图像中识别并对应相同或相似的结构、内容［1］。近年来，随着研究的不断深入，图像匹配技术被广泛应用于位姿估计［2］、医学图像配准［3］、3D重建［4］、人脸识别［5-6］等诸多领域。一般情况下，图像匹配过程会受到尺度、视角、照明等因素的影响［7］。如何快速且准确地对图像进行匹配已逐渐成为图像匹配的一个重要研究热点。

在图像匹配过程中，特征提取是最重要的一环。传统图像特征提取算法能够解决某些特定场景、可人工定义和设计的图像任务。由于该方法在特定场景中具有较好的效果、更强的可解释性和更好的性能，因此仍然具有广泛的应用价值。文献［8］提出的具有尺度变换特征不变性的SIFT（Scale Invariant Features）算法属于经典的传统算法，被广泛运用于图像配准领域［9-10］。传统SIFT算法具有较好的鲁棒性，但是由于其特征描述符是高维的向量，并且利用欧氏距离度量其特征向量之间的相似性，对计算效率和存储性能有很高要求。为了实现快速且准确的图像配准，研究人员提出了诸多改进。文献［11］提出了SURF（Speeded Up Robust Features）算法。该方法利用积分图像和盒式滤波器构建金字塔，避免了SIFT的降采样过程，提高了算法的运算速度，但是其对旋转变化敏感。文献［12］提出的ORB（Oriented FAST and Rotated BRIEF）算法解决了旋转不变性问题，但是其特征描述符的区分性弱，匹配效果一般。文献［13］提出了局部保持匹配方法，通过引入变换向量间的距离比值和角度乘积，构成新的距离损失度量函数进行阈值比较。该方法提高了SIFT算法的匹配精度，但是计算量很大。文献［14］将几何代数理论引入传统SURF框架，计算基于几何代数理论的Hessian矩阵定位兴趣点，并在几何代数空间中进行描述，有效提升了算法速度。文献［15］提出的FAST（Features from Accelerated Segment Test）算法大幅降低了运算时间，能够达到接近实时的运算效率，但是对尺度、旋转等变化很敏感。为了提高复杂场景中合成孔径雷达图像的配准精度，文献［16］利用FAST算法进行检测，能检测到足够数量且稳定性和重复性好的角点，但是在光照变化明显的情况下容易造成误匹配。文献［17］提出了一种SIFT与Canny边缘检测相结合的图像匹配方法。首先通过SIFT检测候选关键点，然后利用Canny算法去除作为错误候选点的边缘点，最后将快速最近邻算法应用于高维空间中的匹配点搜索。尽管该算法能够有效提高图像特征提取的精度和实时性，但是对于光照复杂、边缘模糊的场景效果不佳。

针对已有算法在尺度、旋转以及光照变化方面的诸多问题，为使不同场景下算法同时具备高精度和高速度，本文在SIFT算法的基础上进行了如下改进：（1）对构建的高斯金字塔进行优化，通过缩减金字塔层数降低耗时的高斯模糊和降采样次数；（2）在多尺度空间中，提出局部自适应阈值的FAST-SIFT方法在所有尺度上进行特征点检测，提取出鲁棒性更强的特征点；（3）设计了一种新的特征描述符，对原算法中的高维度描述符进行降维，并在特征匹配环节采用RANSAC算法剔除误匹配。实验结果表明，本文提出的方法可以缩短特征点检测的运行时间且在复杂场景下的图像匹配中具备更高的准确性和鲁棒性。

2 SIFT算法

SIFT算法是一种基于图像尺度空间的局部特征描述子，它在多尺度空间下搜索特征点，通过计算其梯度信息和方向进行描述、匹配的算法。主要步骤如下：

（1） 尺度空间极值检测。SIFT通过在图像高斯尺度空间的差异进行局部极值检测，如图1所示。

图1 差分金字塔的构建Fig.1 Construction of a differential pyramid

图像的尺度空间L(x，y，σ)可定义为原始图像I(x，y)与一个可变尺度的二维高斯函数G(x，y，σ)进行卷积运算的结果，其数学形式如式（1）所示：

其中：σ表示尺度空间因子，也叫模糊系数，σ值越大图像越模糊；G是尺度可变高斯函数。

进一步将高斯金字塔中相邻尺度的高斯图像做差得到高斯差分金字塔，其数学形式如式（3）所示：

其中：D(x，y，σ)是高斯差分金字塔；k为尺度。

将差分金字塔中的每个像素与其同尺度的8个邻域点以及上下相邻尺度各9个邻域点进行比较，判断是否为极值点。

（2） 特征点精确定位。通过上述步骤检测到的极值点是离散空间的极值点，并不是所求特征点，故需要进一步精确定位关键点的位置和尺度。

（3） 特征点主方向确定。为了使生成的描述符具备旋转不变性，通过计算特征点的幅角和幅值的方式来给每个特征点分配一个主方向。对特征点所在的邻域窗口内，计算每个像素点的幅值m(x，y)和幅角θ(x，y)，公式如式（3）、式（4）所示：

（4） 特征点描述。计算关键点邻域的4×4个子区间内的8个方向上每个方向的梯度累计值，最后生成4×4×8=128维的特征向量。

3 局部自适应阈值的SIFT算法

本文所提出的算法流程图如图2所示。本文将从尺度空间构建、关键点检测、特征描述向量生成以及图像匹配4个方面详细介绍所提出的算法。

图2 所提方法流程图Fig.2 Flowchart of the proposed method

3.1 高斯金字塔层数选择

SIFT算法尺度空间通过高斯金字塔来实现。在构建高斯金字塔时，需要对原图像不断进行下采样和高斯模糊，金字塔层数过多会导致图像的特征信息丢失，造成尺度不变性冗余，加大了后续特征点检测的时间损耗。为了验证高斯金字塔的尺度冗余性，从UAV Image Mosaicking数据集中随机采样3组图像进行实验，实验图尺寸为512×767。高斯金字塔层数计算公式如式（5）所示：

其中，M和N分别是图像的行、列数。经计算，采集的图像集可构建O=6层高斯金字塔，对每一层的特征点检测与耗时情况进行统计，结果如表1所示。

表1 不同层SIFT匹配结果Tab.1 SIFT matching results for different layers

从表1可知，随着层数的不断增高，在第5、6层时，提取到的特征点匹配对占比增量逐渐减小，而时间耗损一直存在。因此，通过缩减SIFT算子的尺度空间，即对高斯金字塔层数减少1～2层，可以显著缩短特征检测耗时，同时保证检测到的特征点不会大量丢失。

3.2 局部自适应阈值的FAST-SIFT特征点检测

在构建更高效的尺度空间后，需要进行特征点检测。FAST算法通过以待检测点为圆心的周围邻域内的像素点判断检测点是否为角点，判断依据为一个固定的阈值。然而单一阈值方法在光照变换明显等复杂环境下很难保证图像中提取到的特征点的质量和数量，不利于后续算法的处理。

因此，本文提出一种带有局部自适应阈值的FAST-SIFT特征点检测方法。该方法通过计算待检测点邻域内像素的对比度来定义该区域的阈值，利用自适应阈值的FAST算法在SIFT尺度空间中进行特征检测，使提取到的特征点不仅具备尺度不变性和方向性，且能够在光照变化明显的环境下实现有效的特征点检测。所提出的局部自适应阈值TA定义为：

其中：Ii是模板内像素的灰度；Ij是模板内以Ii为中心的4邻域内像素灰度；Δδ=|Ii-Ij|，即模板内某一像素与其4邻域内像素间的灰度差；Iaver为模板内像素灰度平均值；PΔδ(Ii，Ij)为相邻像素间灰度差为Δδ的概率分布，则该模板区域对比度计算公式为；α为比例系数，代表阈值TA与图像局部对比度的关系，经实验得出α为3～4时，提取出的特征点数量更均衡。

图3给出了光照明暗差异较大的场景图，分别采用固定阈值和自适应阈值的FAST算法进行特征点检测。由结果可知，采用固定阈值提取出的特征点数量较多，产生了特征点冗余、堆积现象，对算法性能影响很大；相比之下，通过局部自适应阈值的方法提取出的特征点分布更均匀，更具有可区分性，对算法运行效率有很大的提升。

图3 改进FAST对比实验。（a） 固定阈值（耗时t=4.5 s）；（b） 自适应阈值（α=2.5，耗时t=3.8 s）；（c） 自适应阈值（α=3.5，耗时t=1.6 s）；（d）自适应阈值（α=4.5，耗时t=0.9 s）。Fig.3 Improved FAST comparison experiment. （a） Fixed threshold （time consumption t=4.5 s）； （b） Adaptive threshold （α=2.5，time consuming t=3.8 s）；（c） Adaptive threshold （α=3.5，time consuming t=1.6 s）； （d） Adaptive threshold （α=4.5，time consuming t=0.9 s）.

所提出局部自适应阈值的FAST-SIFT特征点提取详细步骤如下：

Step 1 在构建尺度空间后，采用局部自适应阈值的FAST算法在每个尺度进行特征点检测，将检测到的特征点作为初始特征点；

Step 2 在高斯差分金字塔中，对上一步筛选出的初始特征点与其8邻域以及上、下尺度的18个点进行极值比较，以确保初始特征点为极大值或极小值；

Step 3 若初始特征点满足上述条件，则将其认定为最终的特征点，否则，在以该初始特征点为中心的8邻域范围内搜索距离中心最近的极值点作为特征点，以此来保证特征点的数量；

Step 4 对提取出的特征点用SIFT描述符进行描述，生成相应特征向量。

3.3 特征向量降维

通过上述方法提取特征点后，需要对特征点所包含信息进行描述。SIFT算法采取特征点邻域16×16的方形区域生成128维特征描述符，会造成区域误差，同时高维度的特征向量在进行匹配时，需要的计算量很大，会严重影响匹配速度。为解决此问题，考虑圆形具有旋转不变性，本文采用圆形窗口来生成特征描述符，在充分保留特征信息的同时，无需确定特征点的主方向。描述符设计如图4所示，主要步骤如下：

图4 改进的描述符Fig.4 Improved descriptor

Step 1 在特征点周围20×20的邻域内，以特征点为中心，取半径为10的圆形区域。

Step 2 将圆形区域由内至外划分为4个圆环子区域，由于特征点周围的像素离特征点越近，对特征点描述符的影响也越大，故每个圆环子区域的步长分别取4，3，2，1。

Step 3 根据式（3）、（4）统计每个圆环区域内像素点8个方向上的梯度直方图。

Step 4 对于每个圆环区域的像素点，根据计算出的每个像素点的幅角值确定其在8个方向的哪一个区间内，每个区间角度划分为0°～45°，根据每个像素点所处位置，再利用高斯窗口进行加权处理，将不同像素点幅值进行累加，加权系数计算公式如式（7）所示：

其中：(x，y)和(x0，y0)为所求像素点和中心像素点在待描述区域的坐标位置，σ为所在尺度，s为所求像素点坐标所在圆环位置步长，r为所求像素点坐标所在圆环半径。通过考虑所求像素点所在区域圆环的步长s与半径r的比值，描述了该点所在圆环区域相对中心特征点区域的位置，进一步细化不同位置像素点对中心特征点的影响权重。

Step 5 通过上述步骤，最终得到4×8=32维的特征描述符。为了减小由于光照变化对匹配效果的影响，需要采用归一化对特征向量进行处理，得到最后的特征描述符向量进行匹配。

3.4 特征点匹配

本文通过计算特征向量之间最近绝对值距离与次近绝对值距离的比值作为匹配依据，即遍历计算出待匹配图像中每个特征点描述符与参考图像中所有特征描述符的欧式距离，找到与某一特征点距离最近和次近的特征点。当最近距离值与次近距离值之比小于阈值时，则定义为正确的匹配点对。为了进一步提高匹配准确度并去除误匹配，本文采用RANSAC算法对特征点进行提纯。

4 实验结果与分析

实验硬件平台为Intel Core i5-10500H处理器，2.50 GHz主频，16 GB内存，RTX 2060显卡，Windows操作系统。利用Matlab2020a的平台进行仿真实验。实验使用的数据集分别为：

（1） Hpatches数据集［18］。该数据集包含多组亮度变化对比图和视点变化对比图，用于测试算法在亮度变化和视点变化情况下的匹配性能。

（2） 牛津大学Mikolajczyk数据集［19］。该数据集包含多组旋转、尺度变化对比图，用于测试算法在旋转、尺度变化情况下的匹配性能。

4.1 描述符降维有效性分析

为了验证本文设计的降维方法在提升匹配效率的同时能否保证匹配准确率，实验对比了传统SIFT算法、PCA-SIFT［20］算法以及传统SIFT算法结合本文降维法的匹配性能。从Hpatches数据集中选取8组图像对进行实验，结果如图5、图6所示。

图5 各算法的执行时间对比Fig.5 Comparison of the execution time of each algorithm

图6 各算法的特征点匹配准确率Fig.6 Feature point matching accuracy of each algorithm

图5显示的是3种算法对图像进行特征点检测所需时间的对比。可以看出，SIFT算法的执行时间最长，PCA-SIFT次之，本文采用圆形窗口进行特征点描述，生成32维特征向量，算法执行时间明显优于另外两种算法。

图6的柱状图显示了3种对比算法对图像进行特征点匹配后得到的匹配准确率。由图6可知，SIFT算法的匹配准确率最低，在第5、7组匹配率只有约60%；PCA-SIFT通过主成分分析法在4组数据图上实现的降维特征描述更具鉴别力，所以表现较好，但该方法通过将特征描述符投影到较低维的子空间降低特征描述符的维数，可能会导致一些原始信息的丢失，所以在剩下几组数据图上，本文降维方法表现效果更好。

由图5、6可知，结合本文降维方法的SIFT算法在执行时间和匹配准确率上均优于传统的SIFT算法。与PCA-SIFT相比，虽然本文方法只有4组数据在匹配准确率上占优势，但是在执行时间上均优于PCA-SIFT算法。总体上本文所设计的降维方法更具优势，在提升匹配效率的同时能保证匹配准确率。

4.2 算法性能比较结果分析

为了验证本文提出的具有局部自适应阈值的SIFT算法的性能，从两种数据集中选取8组图像进行实验，对比SIFT［8］、ORB［12］、GA-SURF［14］、Canny-SIFT［17］以及Pyramid-ORB［21］算法。图7给出了部分用于测试的图像，其中一组各算法的匹配结果如图8所示。进一步统计各类算法的匹配准确率和耗时性，结果如图9所示。

图7 部分用于测试的图像对。 （a） 光照变化； （b） 视点变化； （c） 旋转、尺度变化。Fig.7 Part of the image pairs used for test. （a） Lighting transformation； （b） Viewpoint transformation；（c） Rotation and scale transformation.

图8 各算法匹配结果Fig.8 Matching results of each algorithm

图9 算法匹配性能分析。 （a） 各算法匹配准确率； （b） 各算法执行时间。Fig.9 Algorithm matching performance analysis. （a） Matching accuracy of each algorithm； （b） Execution time of each algorithm.

由图9可知，在具有光照、视点以及旋转和尺度变换的图像匹配中，ORB算法的匹配准确率最低，Pyramid-ORB算法次之，Canny-SIFT算法略优于传统SIFT算法和GA-SURF算法。本文方法通过自适应阈值FAST算法在多尺度空间下提取更稳定的特征点，对待匹配图片的旋转、尺度以及光照变换具有较强鲁棒性，在匹配准确率方面效果显著，优于其他几种算法。在匹配耗时方面，SIFT算法消耗的时间最多；Canny-SIFT算法通过从候选点中筛选出错误的边缘点，减少了匹配点对，匹配耗时比传统SIFT少；Pyramid-ORB算法通过构建高斯金字塔来克服旋转和尺度变化，算法耗时高于ORB算法。本文方法通过采用圆形窗口将SIFT特征描述符降到32维，极大提升了特征点匹配效率，匹配耗时略少于ORB算法，但明显优于其他4种算法。

4.3 算法稳定性分析

4.3.1 尺度、旋转不变性对比

为了检验本文方法对图像旋转和尺度变换时的匹配准确率，从Hpatches数据集中选取待检测图，将图像尺度缩放1.5倍并顺时针旋转30°，如图10所示。

图10 用于尺度、旋转不变性测试的图像对。Fig.10 Image pairs for scale， rotational invariance test.

表2统计了各算法在图像发生旋转、尺度变换情况下的匹配耗时和准确率。从表2可知，在图像发生旋转和尺度变换时，本文方法提取到的特征点具有很好的稳定性，依然能保持较高的匹配准确率。为了进一步对本文方法的旋转性进行验证，对不同旋转角度下各算法的匹配情况进行了记录。由图11可知，随着旋转角度的不断增大，本文方法依然具有较强的稳健性，算法的匹配准确率保持在91%以上。

表2 图像旋转、尺度变换后的比较结果Tab.2 Comparison results after image rotation and scale transformation

图11 图像旋转变换的实验结果Fig.11 Experiment results of image rotation transformation

4.3.2 亮度变换对比

光照强度变化在实际情况中比较普遍，是影响图像匹配的重要因素之一。为了验证本文方法在图像光照强度变换情况下的匹配性能，进一步通过手动设置实验图由暗到亮进行对比实验，结果如图12所示，可以看出本文方法对光照变换具有良好的鲁棒性，正确匹配率均在93%以上。

图12 光照强度变换的实验结果Fig.12 Experimental results of light intensity transformation

5 结论

针对SIFT算法的计算复杂性高、存在误匹配点的问题，本文在传统SIFT算法基础上提出了一种具有局部自适应阈值的SIFT快速图像匹配算法。在SIFT尺度空间理论基础上，通过缩减高斯金字塔层数消除算子的尺度不变冗余性能，在保持匹配性能情况下，显著提高了特征点检测效率；利用局部自适应阈值的FAST算法与SIFT算法的极值比较相结合提取特征点，并使用圆形窗口描述32维特征向量代替SIFT算法的128维高维向量。与其他几种算法进行对比，实验结果表明，本文方法在特征提取速度、准确率方面效果更好。在尺度、旋转以及光照等变换下提取的特征点具有更好的稳定性，能得到较高的正确匹配率。在旋转角度较大的情况下，本文方法的正确匹配率较SIFT提高约23%，算法耗时减少了45.7%，能更好地运用于实时场景中。