改进的SIFT邻域投票图像匹配算法

程德强，李腾腾+，郭 昕，白春梦，徐 辉

(1.中国矿业大学 信息与控制工程学院，江苏 徐州 221116；2.内蒙古智能煤炭有限责任公司，内蒙古 准格尔旗 017100)

0 引 言

图像匹配[2-5]主要分为基于区域和基于特征的两类方法[6]。与基于区域的方法相比，基于特征的方法具有更好的鲁棒性，是当前图像匹配的主流方法。在实际应用中，图像的灰度变化、纹理细节和视角变换等都是基于特征匹配方法的不确定因素，导致常见的匹配算法包含大量的误匹配点，因此匹配精度比较低。经典的尺度不变特征变换(scale-invariant feature transform，SIFT)算法[7]对旋转、透视变换、尺度变换和光照变化等保持不变，然而由于特征描述符维度过高造成计算复杂度增加，因此难以满足实时的要求；快速鲁棒特征(speed up robust features，SURF)算法[8]改进了SIFT算法特征提取和描述的方式，用一种更为高效的方式完成特征的提取和描述，但SURF的实时性不高；颜雪军等[9]提出了一种具有仿射不变性的SIFT描述符，将描述符归一化为椭圆邻域；黎剑兵等[10]提出了一种结合环状区域划分的特征描述子CLCGH，将邻域划分为环形同时在局部坐标系上统计梯度方向；Dou等[11]提出了一种基于小波变换和SIFT相结合的鲁棒图像匹配算法，对图像采用离散小波变换提取其低频部分，然后利用Harris来检测感兴趣点。

然而，由于受传感器设置和相机位置等因素的影响，图像间存在较大的几何差异和灰度变化，从而导致传统算法匹配精度较低[12-14]，同时难以满足实时性的要求。为此本文提出一种改进SIFT特征描述符和邻域投票相结合的算法，从特征描述符的生成和误匹配点的剔除两个方面进行改进，实现图像特征点的精确匹配。实验结果表明，本文算法在在显著提高匹配精确度的同时缩短了匹配的时间。

1 SIFT算法原理

SIFT算法的匹配性能较好，能够对图像的尺度变换、仿射变换、图像模糊和光照变化保持很好的鲁棒性。SIFT算法具体包括以下4个步骤。

1.1 尺度空间极值点检测

为了检测图像尺度空间中稳定的极值点，SIFT算法首先使用不同尺度的高斯核对图像进行卷积实现了图像的尺度变换，Lindeberg等证明了高斯核是唯一实现尺度变换的变换核，并且是唯一的线性核[15]，图像的尺度空间L(x,y,σ) 可以表示为

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

其中，(x,y) 表示二维图像的像素坐标，I(x,y) 为输入图像，σ为尺度因子，G(x,y,σ) 是尺度可变的高斯函数，定义如下

(2)

在此基础上，SIFT通过建立高斯差分(difference of Gaussian，DoG)[16]金字塔来检测尺度空间中的极值，两个不同尺度高斯核相减得到DoG算子

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=
L(x,y,kσ)-L(x,y,σ)

(3)

式中：k为尺度参数。

在建立高斯差分尺度空间后，将每个像素点与其同一尺度的8个点和两个相邻尺度中的18个对应点进行比较，提取具有最大值或最小值的点作为候选特征点。

1.2 特征点定位

由于在DoG金字塔中检测到的是离散空间的极值点，而不是真正的极值点，我们必须拒绝对噪声敏感或边缘定位不稳定的特征点。SIFT通过曲线拟合，在尺度空间中对DoG函数泰勒展开来准确定位特征点的位置和尺度

(4)

其中，X=(x,y,σ)T，取D(X) 的导数，并将其设置为零。

1.3 特征点方向分配及特征描述符的生成

SIFT算法根据特征点邻域的梯度分布，为每个特征点分配主方向，使其生成的特征描述符具有旋转不变性。在特征点所在的尺度空间中，计算3σ邻域内每个像素的梯度和方向，任一特征点邻域内像素 (x,y) 的梯度大小m(x,y) 和方向θ(x,y) 定义如下

(5)

(6)

利用在0°-360°范围内取值的梯度直方图来计算特征点邻域像素的梯度和方向，将直方图的峰值作为特征点的主方向，大于80%峰值的其它区间作为特征点主方向的辅助方向。通过以上操作，特征点包含了位置、尺度和方向3个信息。

将坐标轴旋转至与特征点的主方向平行，然后选择以特征点为中心的16*16像素邻域作为采样窗口，在每个 4*4 窗口中计算8个方向的梯度方向直方图，对每个梯度方向的累积值进行绘制，从而生成具有8个数据的种子点。因此，每个特征点由4*4个种子点组成，每个种子点包含8维的特征向量，最终产生一个128维的特征描述符。为了减少光照的影响，需要对128维梯度数据进行归一化。

1.4 特征匹配

SIFT将欧式距离作为特征向量的相似性度量，并且若特征点最近邻距离和次近邻距之比小于某个阈值，则判定此特征点与其最近邻的点正确匹配。最后通过随机抽样一致(random sample consensus，RANSAC)算法[17]剔除误匹配点，完成特征点的匹配。

2 本文算法

2.1 算法流程

传统SIFT算法特征描述符维度过高，易出现误匹配的现象，同时难以满足实时性的要求，为此本文提出了一种基于改进SIFT特征描述符的邻域投票图像匹配算法，首先将参考图像和待配准图像作预处理，分别提取各自的特征点，然后利用Sobel算子进行梯度一致性计算，选择8个仿射形式的同心圆邻域生成64维的特征描述符，采用最近邻比值法获得初始匹配点，最后通过邻域投票方法进一步剔除误匹配点，从而实现图像的精确匹配，其流程如图1所示。

图1 算法流程

2.2 图像去噪和极值点检测

为减少在特征点检测中易受噪声影响的特征点，本文对参考图像和待匹配图像进行均值滤波的预处理。同时利用DoG算子建立高斯金字塔，计算和筛选极值点，但传统SIFT算法的DoG算子对灰度特性变化敏感，容易在灰度变化较大的极值点出现误判。针对这个问题，本文采用极值点周围8个相邻像素的平均值代替原始极值点。

2.3 Sobel算子计算梯度

图像的纹理细节差异、几何畸变和灰度变化降低了SIFT特征描述符的鲁棒性，而特征点邻域的梯度幅度和方向决定特征描述符的生成。为了使描述符对图像的变化有较强的鲁棒性，我们为高斯尺度空间中的每个像素提出了新的梯度定义(包括幅度和方向)。

Sobel算子是一个离散微分算子[18]，它结合了高斯平滑和微分求导，对噪声有平滑滤波的作用，同时受图像变化的影响小，常常用来计算图像的梯度。首先，我们通过Sobel算子计算高斯尺度空间图像的梯度幅度

(7)

新的梯度幅度和方向被定义为

(8)

(9)

2.4 改进的特征描述符

根据SIFT算法原理，在计算特征点的梯度值后，对每个特征点，通过直方图在以特征点为中心的16*16邻域窗口内做梯度分布统计。邻域中加入直方图的每个特征点都由特征点梯度和高斯权重加权，距离特征点越近，对特征点影响越大。

为保持旋转不变性，SIFT将坐标轴旋转至与主方向一致。由于SIFT生成描述符的区域为正方形网格结构，旋转待配准图像区域中的像素使其主方向与参考图像的主方向平行时，该区域中的部分像素不重叠，将会产生较大误差。在SIFT算法实际操作中，采用比参考图像更大的方形区域来旋转，如图2所示，但这种做法使得待旋转图像的像素增加，运算时间也随之增加。将正方形区域替换为圆形区域，即使主方向存在误差，但旋转后图像区域中的像素与之前的像素重叠，如图3所示。

图2 方形区域

图3 圆形区域

由于圆形具有旋转不变的特性，因此本文利用圆形邻域来构建特征描述符，如图4所示。主要步骤如下：

(1)将SIFT算法的16*16特征区域替换为圆形区域，统计邻域像素的等级和梯度方向，以确定主方向和辅助方向；

(2)将圆形邻域区域划分成以1个半径为单位的8个同心圆，即生成8个仿射形式的同心圆邻域，每一个像素都是一个圆，圆的半径的最大值是8个像素。8个环形区域中的像素与特征点的距离越远，像素的权重越小，在匹配阶段被不同地处理；

(3)利用同心环梯度积累法表示特征点描述符，对每个圆周的8个方向进行梯度累积计算，最终生成8*8 = 64维特征点描述符。为了减少光照变化的影响，将上述特征描述符分别进行归一化处理。

图4 描述符的生成

2.5 基于邻域投票方法的特征匹配

首先采用最近邻距离比值法得到初始匹配点。灰度分布、图像细节、几何变换和噪声干扰等都是图像匹配的不确定性因素，采用最近距离比值法去除误匹配的结果中可能存在大量不能正确匹配的点，需要增加新的约束来进一步筛选匹配的点[19]。本文采用邻域投票的方法剔除误匹配点最终得到精确的匹配点。

在正确匹配点邻域存在相似特征点的可能性很大，而在误匹配点邻域存在的可能性很小，甚至可能不存在正确的匹配点。邻域投票方法对匹配点邻域在局部主方向和距离上的分布做累积，分别设定方向阈值和距离阈值，判断参考图像和待配准图像对应的匹配点的方向相关度和距离相关度是否在设定阈值范围内，若均小于设定阈值则认为该匹配点为正确匹配点，反之则剔除该点。特征匹配具体过程如下：

(1)首先对参考图像和待配准图像所有特征描述符做内积运算，求对应反余弦值，对通过最近距离比值法确定的参考图像和待配准图像的对应匹配点根据匹配质量进行排序；

(2)对匹配点邻域在局部主方向和距离上的分布做累积，分别设定方向阈值Tθ和距离阈值Td，经过大量实验验证，当Tθ设为0.3，Td设为0.4时，可以得到较多正确的匹配点；

(3)分别计算参考图像和待配准图像同一图像上任意两个初始匹配点的距离值d和主方向夹角差值Δθ

(10)

Δθ=θi-θj

(11)

式中：i、j为同一幅图像上任意两个初始匹配点，(xi,yi,θi) 和 (xj,yj,θj) 表示i、j两点的像素坐标和主方向。

(4)将(3)中得到的任意两个初始匹配点的距离值和主方向夹角差值按行向量分别进行归一化处理，并计算参考图像和待配准图像每对匹配点的距离内积值dot1和方向夹角内积值dot2

dot1=dot(im1(xA,yA),im2(xa,ya))

(12)

dot2=dot(im1(θA),im2(θa))

(13)

式中： (xA,yA,θA) 和 (xa,ya,θa) 分别表示参考图像和待配准图像的对应匹配点的像素坐标和主方向。

(5)根据(2)设定的参考阈值，比较(4)中匹配点的距离内积值和方向夹角内积值和参考阈值，若小于参考阈值则保留匹配点，反之则剔除该点。最终完成对参考图像和待配准图像的精确匹配。

3 实验结果与分析

为验证本文算法的有效性，本文实验中的图像全部来自牛津大学机器人实验室Mikolajczyk和Schmid[20]的数据集。这些数据集由具有不同几何和光照变换以及不同场景类型的真实图像组成。本文使用5组测试图像，图5(a)为相机视角发生了20°变化的Graffiti图像，图5(b)为发生了模糊变化的Bike图像，图5(c)为亮度和对比度发生了变化的Leurven图像，图5(d)为旋转和尺度发生了变化的Boat图像，图5(e)为参考图像5% 左右的UBC图像。

图5 测试图像

本文对实验数据都进行了预处理，所有算法均在Windows10环境下运行，采用CPU为2.8 GHz、内存为16 GB的计算机配置，编程环境为Matlab R2016。在本实验中，特征点最近邻距离和次近邻距离之比的阈值均设为0.7。

3.1 实验结果

图6为本文所提出方法在测试图像上的匹配结果。可见本文方法能够准确地将参考图像与测试图像进行匹配。本文对在提取的参考图像和待配准图像的SIFT特征前，使用8个相邻像素的平均值代替原始极值点，提高了特征点对灰度变化的灵敏度，克服了SIFT对灰度变化的不良影响，而Sobel算子对梯度的计算提高了特征的鲁棒性，使用8个仿射形式的同心圆代替SIFT描述符的方形网格结构，使描述符区分能力更强，增强了描述符的抗旋转能力，同时降低了描述符的维度，将描述符归一化，降低了描述符对仿射变换和光照的敏感性。所以由实验结果可以明显看出，本文算法对图像的仿射变换、模糊、光照变化、旋转与缩放和JPEG压缩都有较强的鲁棒性，能较好地克服图像几何变换产生的伪匹配点，对复杂场景的图像匹配有好的匹配性能。

图6 本文算法匹配结果

3.2 实验分析

表1是本文所提出的算法、SIFT算法[4]、SIFT RANSAC[21]算法和文献[22]对上文的5组测试图像的匹配对比结果。通过对匹配算法的性能(正确匹配率和总匹配时间)进行对比分析，进一步验证本文算法的性能。从表1数据可以明显看出：对于同一测试图像，本文算法匹配率最高，匹配时间最少。由表1可知，对于测试图像5种变换形式下的图像匹配结果，本文算法的匹配准确率明显高于SIFT、SIFT RANSAC和文献[22]的算法，匹配正确率均达到92%以上，稳定性高，说明本文算法具有较好的鲁棒性和抗干扰能力。本文算法使用8个仿射形式的同心圆代替SIFT描述符的方形网状结构，区分能力更强，可以更好地反映图像的局部特征，而且增强了描述符的抗旋转能力，把特征描述符的维数降低到64维，加快了匹配速度。同时将描述符归一化，降低了描述符对仿射变换和光照的敏感性，用邻域投票的方法剔除不满足阈值范围的误匹配点，从而在正确匹配率大幅提高的同时增加了匹配速率。

图7和图8分别是3种算法的正确匹配率和匹配时间的对比结果，横坐标为图5测试图像的序号。由折线图可以看出，本文算法的匹配性能优于传统的SIFT算法、SIFT RANSAC算法和文献[22]的算法。在匹配精度高的情况下，减少了计算的复杂度，匹配速率大幅提高。本文所提出的算法由于改变了描述符的邻域区域同时简化了描述符的维度，使得匹配速度大幅提升。由图6、图7可以看出，本文算法对图像的仿射变换、模糊、光照变化、旋转与缩放和JPG压缩都有较强的鲁棒性，能较好地克服图像几何变换产生的伪匹配点对，对复杂场景的图像匹配有好的匹配性能，算法稳定可靠，在增加正确匹配率的同时提升了匹配速率。

表1 图像匹配对比结果

图7 正确匹配率对比结果

图8 匹配时间对比结果

4 结束语

本文提出了一种改进SIFT和邻域投票相结合的特征匹配方法，从描述符的生成和误匹配点的剔除两个方面进行了改进。利用8个相邻像素的平均值代替原始极值点，Sobel算子进行梯度计算，并结合8个仿射形式的同心圆邻域生成64维描述符，通过最近邻距离比值法和邻域投票的方法剔除误匹配点，完成图像的精确匹配。实验结果表明，本文方法能够在提高匹配精度的同时缩减匹配时间，而且可以有效处理复杂场景的图像匹配问题。但是本文算法还有待改进之处，对于特征点提取方面，如何快速有效地提取显著的特征点，将是我们下一步研究的方向。