基于SIFT算法的图像拼接技术研究

何惠洋，韩 军

（西安工业大学 光电工程学院，西安710021）

图像拼接是指将两幅或者两幅以上的具有比较明显重叠区域的图像，拼接成一幅宽视野、无缝的质量较高的高分辨率图像，目前，图像拼接技术被广泛应用于计算机视觉、医疗诊断、军事探测、车辆辅助驾驶等诸多的领域。

图像拼接的步骤有图像配准、图像融合，其中以图像配准为最重要的步骤，图像配准算法的好坏直接决定了图像拼接的质量和效率，经过对几种具有代表性的图像配准算法进行性能评估，发现SIFT算法是目前图像处理领域最有效的图像配准算法[1]。然而，SIFT算法在细节比较丰富的图像区域会提取到过多的特征点即无用特征点，导致在匹配时产生较多的误匹配，针对这一问题，在研究SIFT算法的基础上，加入RANSAC算法对特征点进行筛选，在不影响算法鲁棒性的前提下提高匹配正确率，从而整体优化图像配准的效果。

1 SIFT算法原理

SIFT算法[2]是一种局部特征提取方法，最早是由哥伦比亚大学的David Lowe 提出，并在2004年得到完善，大量研究证明，其在特征提取阶段相比于同类型的其他算法性能更加优良，在目前的图像处理领域应用十分广泛。

SIFT算法的核心理论[3]是尺度空间理论，其步骤如下：①尺度空间极值检测；②剔除不合格关键点；③关键点方向分配；④生成关键点描述子。

首先，定义二维高斯函数为

由高斯函数推出尺度空间为

式中：σ为尺度空间因子；I（x，y）为图像在某一点的像素值；L（x，y，σ）定义为有着尺度变换的高斯函数和图像的卷积。

1.1 尺度空间极值检测

为了在尺度空间检测出稳定的关键点，SIFT算法使用高斯差分尺度空间DoG（difference of Gaussians）算子，即

DoG 尺度空间生成如图1所示。由图可见，DoG空间是通过在图像高斯金塔的每个尺度上减去相邻金字塔来获得的。

图1 DoG 尺度空间生成Fig.1 DoG scale space generation

SIFT 极值点检测如图2所示，为找到极值点，需要将每个采样点的中间点与其本层同一尺度以及相邻上下两层尺度共26个点进行比较，如果该点为最大值或最小值，就认为该点是图像在该尺度上的一个极值点，作为待选特征点。

图2 SIFT 极值点检测Fig.2 SIFT extreme point detection

值得注意的是，在寻找极值点的过程中，每一组图像的首末两层无法进行极值比较，为满足尺度变化的连续性，人为地在每一组图像的首尾两层用高斯模糊生成2 幅图像，从而保证不会在首位两层漏选某些有用的极值点。

1.2 剔除不合格关键点

对所检测得到的极值点执行差分处理，确定极值点的位置和尺度，同时需要剔除不合格的关键点，如低对比度极值点和不稳定的边缘响应点。

用插值处理来剔除低对比度的极值点，DoG 函数在尺度空间的Taylor 展开式为

其中

式中：X为样本的像素点，对式（4）求导并令导数为0，可获得插值后极值像素点偏移量X^，通过对偏移量进行控制可筛选掉低对比度的极值点。

当需要消除边缘相应区域内不稳定的极值点时，可以对2×2的Hessian 矩阵H 求导，得出主曲率：

假设，特征值α 较大且特征值β 较小，并且H特征值与D的主曲率成比例，则

令α=γβ，可得

利用式（9）可以检测主曲率是否低于某个阈值γ，从而进行极值点筛选。

1.3 关键点方向分配

用图像的局部区域特征来计算每个点的方向，从而使特征描述向量具有方向上旋转不变的特性。所计算的梯度m（x，y）和方向θ（x，y）为

式中：L（x，y）为关键点的尺度空间值。

实际计算时，在以关键点为中心的邻域窗口内进行采样，并用直方图来统计邻域像素的梯度方向。梯度直方图的范围为0～360°，其中可以每10°一个柱，共36个柱；也可以每45°一个柱，共8个柱，实际计算一般多使用8个柱来统计，直方图的峰值表示该关键点处邻域梯度的主方向，即作为该关键点的方向，当存在另一个峰值达到主峰值80%的能量时，则将这个方向认为是该关键点的辅方向，因此，一个关键点的方向并不是固定的，它可能会被指定具有多个方向，这样增强了匹配算法的鲁棒性[4]。

至此，图像的特征点已检索完毕，每个特征点具有3个信息，即尺度信息、位置信息和方向信息。

1.4 生成关键点描述子

首先将坐标轴旋转为关键点的方向，以确保旋转不变性，然后以关键点为中心取一个8×8的窗口。生成特征子描述如图3所示，图3a的中央黑点为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，箭头方向为该像素的梯度方向，箭头长度代表该像素的梯度模值，在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点（如图3b所示），图3b 中，一个关键点由2×2 共4个种子点组成，每一个种子点都有8个方向的向量信息，可产生2×2×8 共32个数据，即产生一个32维的SIFT 特征向量对特征点进行描述。

图3 生成特征子描述Fig.3 Generate feature sub-description

在实际计算过程中，为增强匹配的稳健性，Lowe 建议对每个关键点使用4×4 共16个种子点来描述，这样，对于一个关键点就可以产生4×4×8共128个数据，即最终形成一个128维的SIFT 特征向量。

2 k-d树与RANSAC算法

2.1 k-d树算法

在SIFT算法中利用k-维树k-d（dimensional）树进行搜索匹配特征点，k-d树算法由2部分组成，一是建立k-d树数据结构，二是在k-d树这种数据结构上进行数据查找的算法。

2.1.1 构建k-d树

k-d树是一个二叉树的数据结构。k-d树上每一个节点代表着一个空间范围，通过分割平面将整个空间分割成左右2个子空间，1）确定分割域，对于所有描述子数据（特征向量），统计它们在每个维上的数据方差，选取出最大值，而对应的维数k 即为分割域的值；2）确定节点数据域，数据点集按照前面的分割域的值进行排序，位于中间的那个数据点即为节点数据；3）确定左子空间和右子空间，分割平面（k等于节点数据值）将整个空间分割成2个子空间，k-d树的构建是一个递归的过程，对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点，如此反复到空间只包含一个数据点，构建k-d树的流程如图4所示。

图4 k-d树构建流程Fig.4 k-d tree construction flow chart

2.1.2 k-d树最近邻查找的算法

首先，通过二叉树搜索（比较待查询节点和k-d树节点最大方差维数的值，小于时进入左子树分支，大于等于时则进入右子树分支直到叶子结点），进行二叉树查找后可以得到最近邻的相似点，即在二叉树的叶子节点，然后，这个叶子节点返回到父节点查找是否有距离查询节点更近的节点，如果没有则说明该子节点就是最近邻点，否则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径），重复该过程直至搜索路径为空。

2.2 RANSAC算法

随机抽样一致性RANSAC（RANdom SAmple Consensus）算法是一种鲁棒的变换估计算法，利用特征集合的内在集合约束关系进一步剔除错误的配准，提高配准正确率，该算法的主要思想是先随机选取2个点来确定一条直线，将这条直线一定距离范围内的点称为这条直线的支撑，随机选择重复多次，具有最大支撑特征集的直线被确认为是样本点集的拟合，在拟合的误差距离范围内的点称为内点，反之则为外点，将外点剔除掉，增强图像配准算法的稳健型，利用这种方法能减少误匹配的点，使配准效果更佳，提高了正确率。

RANSAC算法假设给定一组数据，存在可以计算出符合这些数据的模型参数的方法，估计模型参数的过程如下：

步骤1从一个有N个数据的集合P 中随机抽取模型求解要求最少的n个数据，根据这些抽取的n个数据计算出一个估计模型M；

步骤2然后对其余的N-n个数据，计算它们与估计模型M 之间的距离，保存这个集合中在估计模型M的误差允许范围内的数据个数c；

步骤3步骤1和步骤2 不断迭代k次，对应最大c值的估计模型即为所求的模型，这c个数据即为内点；

实际应用中需要确定一个适当的迭代次数k，迭代次数是保证模型估计需要的n个数据都是内点的概率p所需要的迭代次数，迭代次数k 需要满足的条件为

式中：w为该数据是数学模型内点的概率；n为确定模型参数的最少点数。

3 算法试验结果与分析

在此，试验硬件环境为酷睿i5 处理器，4 GB内存的PC，采用32位Windows 10 操作系统，编译环境为VS 2010和OpenCV 2.4.9。

3.1 室外场景拼接试验

图5 室外试验图像Fig.5 Outdoor experimental images

该组试验图像为室外拍摄，如图5所示，室外拍摄图像色彩较为单一，匹配到的特征点较少，使用所研究的SIFT算法可使匹配效果更佳，特征点数据见表1。

表1 室外试验特征点数据Tab.1 Outdoor experimental feature point data

将匹配到一起的特征点连线，再进行拼接，结果见图6，图7。

图6 匹配两幅图像Fig.6 Matching two image

图7 室外试验结果图Fig.7 Outdoor experimental result

3.2 室内场景拼接试验

该组试验图像为室内拍摄，如图8所示，室内拍摄的图像色彩较为丰富，故匹配到的特征点比室外图像多，采用SIFT算法仍可获得较好的拼接效果，特征点数据见表2。

图8 室内试验图像Fig.8 Indoor experiment images

表2 室内试验特征点数据Tab.2 Indoor experimental feature point data

最终试验结果见图9，图10。

图9 匹配两幅图像Fig.9 Matching two image

图10 室内试验结果图Fig.10 Indoor experimental result

4 结语

本文主要研究了图像拼接过程中的SIFT算法，并以此为基础加入了中k-d树匹配算法，匹配完成后再使用RANSAC算法去除误匹配，经过试验分析，虽然SIFT算法的特征点提取较复杂，计算时间相对较长，但是SIFT算法检测出的特征点具有尺度不变性，可以处理图像间发生的平移、旋转、仿射变换的匹配，再经过RANSAC算法提高匹配精度，使该算法具有匹配能力强、精确度高的特征。