改进SIFT算法的图像双向配准技术

刘清清，李士心，孙夏丽，王 坤

（天津职业技术师范大学大学电子工程学院，天津 300222）

近年来，图像配准技术被广泛应用于医学图像分析、遥感图像处理、计算机视觉、集成电路图像拼接等领域，随着对图像配准研究的不断深入，多领域的应用场景对图像配准技术的需求也越来越高。目前，实现图像配准技术的算法主要分为基于灰度信息、变换域和特征匹配。其中，基于特征的图像配准根据选取特征属性的不同可细分为若干方法，如基于线特征的Hough变换、基于轮廓特征的Log算子、Sobel边缘提取算子、Canny边缘检测算子等，以及目前应用最为广泛的基于特征点配准的SIFT算法等[1]。本文主要针对基于尺度不变特征变换（scale-invariant feature transform，SIFT）算法的k-d树配准算法进行分析并改进。SIFT是一种具有尺度不变性的局部特征描述子，可以检测并描述输入图像中的极值点[2]，该特征点对待配准图像的旋转、尺度、亮度等因素保持不变性，因此该算法适用于多种场景[3]。但是，由于一个特征点具有多维描述子，且特征描述子的数量与图像配准的速度成正比，故传统的k-d树单向匹配算法易出现错误匹配，同时也无法满足实际应用的实时性。因此，本文在SIFT描述子匹配阶段，采用准欧氏距离代替欧氏距离，匹配效率显著提高。

1 基于SIFT算法的图像配准

1.1 特征点检测

1.1.1 构建尺度空间

SIFT算法在构建尺度空间时采取高斯核函数进行滤波来模拟各个尺度下的特征情况，使待配准图像保留更多的信息以便后续进行特征的提取与匹配[4]。通过将待配准图像与具有可变核的高斯滤波进行卷积，从而得到图像的高斯金字塔Log。高斯卷积核是唯一可以实现尺度变换的线性变换核，尺度空间图像即为初始图像与不同尺度参数σ进行卷积运算所产生的图像，图像I（x，y）的尺度空间L（x，y，σ）表达式为

式中：G（x，y，σ）为二维高斯函数；I（x，y）为原始图像中某点的像素值；σ为尺度因子，σ值越大，代表初始图像被平滑得越多，对应的图像尺度越大[5]。

1.1.2 构建高斯金字塔

为了在尺度空间有效检测到稳定的关键点，SIFT算法使用了高斯差分尺度空间算子DOG（difference of Gaussian），DOG算子定义为不同尺度的高斯差分核与图像卷积，其是归一化高斯拉普拉斯算子Log的近似[6]，表示为

高斯差分金字塔的生成如图1所示。图像的金字塔模型是指将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小、从下到上构成的塔状模型。初始图像为金字塔的第一层，每组中相邻上下两层图像相减，下一层的图像是由上一层图像降采样而得。

图1 高斯差分金字塔的生成

1.1.3 DOG局部极值点检测

SIFT算法中的特征点是由高斯差分尺度空间中的局部极值点组成，在建立高斯差分金字塔尺度空间后，将每个像素点与其同一尺度以及上下相邻尺度的26个像素点作比较，局部极值点检测如图2所示。

图2 局部极值点检测

若某检测点比其图像域与尺度域的相邻点大或小，该点即为该尺度上的局部极值点[7]。对于每组图像的首尾两层需人为使用高斯模糊生成2幅图像，以寻找首尾两层的极值点，满足尺度变化的连续性。

1.1.4 消除不合格关键点

DOG算子会产生较强的边缘响应，为了提高图像配准的稳定性和准确性，通过对检测出的极值点进行差分处理，拟合3位二次函数确定特征点的位置和尺度，消除低对比度和不稳定的边缘响应点。

利用DOG函数在尺度空间的Taylor展开式对尺度空间DOG函数进行曲线拟合，其拟合函数表示为

式中：X=（x，y，σ）T。

对Taylor展开式求导，并令其导数为0，得到极值点的偏移量为

通过控制偏移量，可以消除低对比度的极值点。

由于DOG对图像中的边缘有比较强的响应值，如果极值点在图形的边缘上，这些点就是不稳定的点。在边缘梯度的横向方向上主曲率值比较大，而沿着边缘垂直方向则主曲率值较小，主曲率可以通过2×2的Hessain矩阵H求出

式中：Dxx、Dxy、Dyy是由极值点邻域对应位置的差分得到的。

令H的特征值α和β表示x和y方向的梯度，特征值α较大、β较小，D的主曲率与H的特征值成正比，则

Tr（H）是矩阵H的对角线元素之和，Det（H）是矩阵H的行列式。令α=γβ，则

若上式成立，则保留该极值点，否则剔除该极值点[8]。

1.1.5 关键点的方向分配

上述步骤确定了特征点的尺度和位置，保证了SIFT算子的尺度不变性。此外，特征点还具有旋转不变性，通过利用图像的局部结构特征计算关键点的方向。采集特征点所在DOG金字塔图像3σ邻域像素的梯度m（x，y）和方向θ（x，y）分布特征，如

计算出特征点的梯度后，通过直方图统计邻域像素的梯度和幅值。直方图以梯度方向角为横轴，将0°～360°划分为若干个区间，以各梯度方向角所对应的幅值累加值为纵轴[9]。直方图的峰值即为该像素点的主方向，大于主峰值80%的方向为辅方向。

1.2 生成特征点描述子

为保证特征点的独特性，提高图像配准的准确率，对于每个特征点用一组向量描述，生成特征点描述子。旋转坐标轴的方向使坐标轴与特征点方向保持一致，选取以特征点为中心的16×16大小的区域窗口。特征描述子的生成如图3所示。

图3 特征描述子的生成

从图3可知，特征点位于正中间，特征点邻域所在尺度空间的像素由左侧的每一个小方格表示，像素的梯度模值和梯度方向分别由右侧的每个箭头的长度和方向表示。对每个像素进行高斯加权运算，邻域像素越靠近特征点，梯度方向信息的价值就越大[10]。计算左侧每4×4个方格区域中8个方向的梯度方向直方图，根据梯度方向形成如右侧的种子点。每个特征点最终由4×4个种子点组成，每个种子点共包含8个方向的梯度信息。对于每个特征点形成一个4×4×8=128维的描述子，每一维都可以代表相应4×4方格的尺度或方向，即生成了128维的特征向量描述子。

1.3 基于k-d树的单向配准

SIFT特征点的相似度可以由特征向量的欧氏距离度量，欧氏距离是一个经常引用的距离定义，是指在n维空间中向量的自然长度（即该点到原点的距离）或2个点的真实距离。以待配准图像中的某个特征点为基准，找到原图像中与待配准图像的特征点欧氏距离最邻近的特征点和次邻近的特征点，若最近的距离除以次邻近的距离的值低于设定的阈值时，则即为匹配点[11]。通常以0.8为比例阈值，但实际应用中该阈值由待配准图像的大小、亮度等因素决定，合理的阈值可以提高配准的准确度。

搜索最邻近点和次邻近点通常采用穷举策略，即根据原图像中的某一特征点与待配准图像中的特征点逐一匹配，该策略需要遍历所有特征描述子，搜索效率不高。本文采用k-d树对邻近点进行搜索匹配，先建立k-d树，对特征描述子数据进行分类整理，从根节点出发，根据索引树朝邻近点所在的方向逼近，直至找到包含目标点的的叶子节点，计算叶子节点的欧氏距离，找到最邻近和次邻近的特征点进行匹配。

构建k-d树是一个逐级展开的递归过程[12]。首先确定分割域的取值，计算特征描述子的特征向量在每个维度上的数据方差，方差最大的值相对应的维数即为分割域的值；确定节点数据的域值，所有特征描述符向量按照分割域的值排序，中位数即为节点数据；确定左子空间和右子空间，分割平面将整个空间分为2部分，分割域中小于节点数据的特征描述符向量对应的特征点为左子空间，大于节点数据的特征描述符向量对应的特征点则为右子空间。对左、右子空间内的数据分别重新遍历根节点，即可得到下一级的子节点，同时将空间和数据集再进一步细分，如此反复直到空间中只包含1个数据点。从根节点到叶子节点所遍历的所有节点构成了叶子节点的索引。

特征匹配另一个重要环节是在k-d树中查找数据，其目的是找到在k-d树中与特征点距离最近的数据点。从k-d树的根节点开始搜索，若待查询节点小于k-d树节点分割域的值，则优先搜索左子树分支，反之，则搜索右子树分支。顺着搜索路径找到叶子节点，该叶子节点对应的特征点为最近邻特征点的概率最大。沿搜索路径回溯到其父节点，在该父节点的其他分支反向查找是否有距离特征点更近的数据点和次邻近点，若无更近的数据点，则该叶子节点为最近邻特征点；若有更近的数据点，则需继续搜索其他路径，直至搜索路径全部回溯完毕。

2 改进算法与实验结果

2.1 改进算法

传统的配准算法是从k-d树的父节点开始向下搜索至叶子节点，根据原图像中的特征点搜索待配准图像中对应的特征点，具有单向匹配性。每个像素点具有多个方向向量，方向不同属于不同的特征描述子，但实际为同一像素点，匹配时易出现同一点重复匹配的情况，采取双向匹配即可消除大部分重复的匹配点[13]。

传统的图像匹配采用欧氏距离度量特征点的相似性，在二维图像中欧氏距离定义为

本文采用准欧氏距离进行图像配准，准欧氏距离定义为

根据定义可以看出，计算准欧氏距离明显比计算欧氏距离运算简单，求得的数值普遍偏小，采用准欧氏距离可明显缩短运算时间，提高了算法的匹配效率[14]。

双向匹配即在传统的配准算法基础上，反向搜索已被匹配的特征点在原图像中与之匹配的特征点，若正向匹配与反相匹配中2点的准欧氏距离小于设定的阈值，则该2点即为正确的匹配点。

式中：D（xi，yj）、D（yj，xi）分别为原图像和待配准图像中一对匹配点的正向和反向的准欧氏距离；r1和r2分别为正向阈值和反向阈值，若满足上式，则xi和yj为一对正确的匹配点[15]。

2.2 实验结果与分析

实验在Widows 10环境下采用Matlab 2017和C编程对本文提出的改进SIFT算法的图像双向配准算法进行实现，2组实验图片分别通过室外自然光和室内光线下手机拍摄获取，对2幅不同光照、不同角度的图片进行特征匹配，通过特征点匹配正确率进行定量分析[16-17]。室外自然光线下和室内光线下基于SIFT特征的图像配准分别如图4、图5所示。

图4 室外自然光线下基于SIFT特征的图像配准

图5 室内光线下基于SIFT特征的图像配准

在室外光线下，通过平移、对焦等操作采集具有重叠部分的图片，原图像共检测出866个特征点，待配准图像共检测出977个特征点。在室内光线下，拍摄时通过平移、旋转、缩放等操作采集具有重叠部分的图片，原图像共检测出572个特征点，待配准图像共检测出724个特征点。室外、室内拍摄的2组图片分别基于SIFT特征的传统单向配准结果与改进的SIFT特征的图像双向匹配的数据结果如表1所示。

表1 图像匹配数据（基于欧氏距离的单向配准/基于准欧氏距离的双向配准）

通过对比不同光线下的2组图片采用2种方法匹配的数据可以看出，改进后的算法在匹配点对数上分别减少68对、30对，错误匹配点数分别为52对、36对，与传统配准方法相比，匹配正确率约提高6%，但时间却缩短为原来的69%。故本文提出的改进算法在实际应用中有效提高了图像配准技术的效率和质量。

3 结语

本文分析了SIFT特征的提取、描述过程，介绍了SIFT特征基于k-d树单向配准的方法，并提出一种改进的配准算法，采用准欧氏距离代替欧氏距离进行运算，缩短了运算时间，提高了配准的速度，且使用双向配准的方法进行特征点匹配，有效消除了部分误匹配点与重复匹配点，提高了图像配准的准确度。实验结果表明，本文提出的改进算法在保证特征点匹配性能的前提下，有效提高了图像配准的速度和正确率，对日后基于SIFT算法的图像配准技术在各领域的应用研究具有一定的借鉴意义。