SIFT特征匹配算法.doc

SIFT特征匹配算法

尺度不变特征变换（ScaleInvariantFeatureTransform，SIFT）是DavidGLowe在1999年提出的基于不变量描述子的匹配算法，SIFT具有以下特征：（1）SIFT特征是图像的局部特征，对平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好的不变性，对视觉变化、仿射变换也保持一定程度的稳定性；（2）独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；（3）多量性，即使少数的几个物体也可以产生大量SIFT特征向量；（4）速度相对较快，经优化的SIFT匹配算法甚至可以达到实时的要求。
SIFT特征匹配算法主要包括两个阶段，一个是SIFT特征向量的生成，第二阶段是SIFT特征向量的匹配。

1SIFT特征向量的生成
1.1构建尺度空间，检测极值点
由于Koendetink证明了高斯核是实现尺度变换的唯一变换核，所以对图像在不同尺度下提取图像特征，从而达到了尺度不变性。首先建立高斯金字塔，然后再建立DOG（DifferenceOfGaussian）金字塔，最后在DOG金字塔的基础上进行极值检测。
（1）建立高斯金字塔
根据二维高斯滤波函数，对图像进行高斯滤波：
（1）
一幅图像I(x,y)，在不同尺度空间下的表示可以由图像与高斯核卷积得到Gaussian图像：
（2）
其中：（x,y）为图像I上的点，L表示尺度空间，σ为尺度空间因子。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。σ值越小表示图像被平滑得越大，即分辨率越高。
根据尺度函数来建立高斯金字塔，高斯金字塔的第一阶的第一层是原始图像。高斯金字塔有o阶、s层，在同一阶上的两个相邻层之间的尺度比例为k，例如第1阶第2层的尺度因子为σ，则第1阶第3层的尺度因子为kσ，并且每一阶图像是前一阶图像大小的1/2。如图1左边的高斯金字塔。

图1由高斯金字塔建立DOG金字塔
关于尺度空间的理解说明：如图2所示，尺度空间是连续的。在Lowe的论文中，将第0层的初始尺度定为1.6，图片的初始尺度定为0.5.在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。

图2空间尺度变化
（2）建立DOG高斯金字塔
在高斯金字塔的基础上，利用同一阶上的两个相邻的两层的尺度空间函数之差得到DOG高斯金字塔的一层。
DOG的表达式定义为：
（3）
由此图1可以看出如何由高斯金字塔得到DOG金字塔。
（3）检测极值点
为了检测到DOG空间的局部极值点，每一个采样点要和它所有的相邻点比较。如图3所示，中间的检测点需要与它同层的8个，上层和下层各9个像素点进行比较，以确保在尺度空间和二维图像控件都检测到极值点。如果该检测点为最大值或者最小值，则该点为图像在该尺度下的一个候选关键点。

图3检测极值点
在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了3幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像.

1.2特征点过滤及精确定位
关键点的选取要经过两步：①它必须去除低对比度和对噪声敏感的候选关键点；②去除边缘点。
（1）去除低对比度的点
对局部极值点进行三维二次函数拟合以精确确定特征点的位置和尺度，尺度空间函数的泰勒展开式如公式（4）所示：
（4）
令上式对x的偏导数等于0，可得极限点位置
（5）
把公式（5）代入公式（4）中，可得：
（6）
若，该特征点就保留下来，否则丢弃。
（2）去除边缘点
一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率由海森矩阵求出：
（7）
D的主曲率和H的特征值成正比，令α为最大特征值，β为最小特征值，则
（8）
（9）
令α=αβ，则：
（10）
如果，曲率小于(r+1)2/r，保留该特征点，否则丢弃。
1.3为关键点分配方向值
利用特征点领域像素的梯度方向分布特征来定关键点的方向，公式如下：
（11）
（12）
m(x,y)表示(x,y)处梯度的模值，θ(x,y)表示方向，L是关键点所在的空间尺度函数。用梯度直方图来统计邻域像素的梯度方向，如图4所示，梯度直方图的横轴代表了邻域像素的梯度方向的大小，纵轴代表了邻域像素梯度值的大小。梯度直方图的横轴的取值范围是0°~360°，每10°为一个单位。总共有36个单位。梯度方向的直方图的主峰值则代表了该关键点的主方向，如果有相当于主峰值的80%大小的其他峰值，则为该关键点的辅方向。可以看出关键点的方向就由一个主峰值方向和多个次峰值的方向决定。这样可以减少图像旋转对特征关键点的影响。

图4