SIFT特征匹配算法.doc

SIFT特征匹配算法尺度不变特征变换（Scale Invariant Feature Transform，SIFT）是David G Lowe 在1999年提出的基于不变量描述子的匹配算法，SIFT 具有以下特征：（1）SIFT特征是图像的局部特征，对平移、旋转、尺度缩放、亮度变化、遮挡和噪声等具有良好的不变性，对视觉变化、 仿射变换也保持一定程度的稳定性；（2）独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；（3）多量性，即使少数的几个物体也可以产生大量SIFT特征向量；（4）速度相对较快，经优化的SIFT匹配算法甚至可以达到实时的要求。SIFT特征匹配算法主要包括两个阶段，一个是SIFT特征向量的生成，第二阶段是SIFT特征向量的匹配。1 SIFT特征向量的生成1.1 构建尺度空间，检测极值点由于Koendetink证明了高斯核是实现尺度变换的唯一变换核，所以对图像在不同尺度下提取图像特征，从而达到了尺度不变性。首先建立高斯金字塔，然后再建立DOG（Difference Of Gaussian）金字塔，最后在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所示，梯度直方图的横轴代表了邻域像素的梯度方向的大小，纵轴代表了邻域像素梯度值的大小。梯度直方图的横轴的取值范围是0360，每10为一个单位。总共有36个单位。梯度方向的直方图的主峰值则代表了该关键点的主方向，如果有相当于主峰值的80%大小的其他峰值，则为该关键点的辅方向。可以看出关键点的方向就由一个主峰值方向和多个次峰值的方向决定。这样可以减少图像旋转对特征关键点的影响。图4 方向参数的确定1.4生成特征向量描述子为了进一步描述关键点的信息，则确定关键点的邻域范围的大小很重要。 如图5所示：每个小方格代表的是关键的邻域像素，小方格内的的箭头代表了该邻域像素的梯度方向，箭头的大小代表了梯度大小。图5(b)中的左上角的小方块由图5(a)中的左上角的四个小方格组成。即：（b）图中的每个小方块的方向是对于（a）图中的方格方向的累积值。 图5显示的是（a）图是88的邻域范围，（b）图显示的是 22 的种子点（每个方格代表一个种子）。 为了增强抗噪能力和匹配的稳健性，通常把邻域的取值范围设成1616，那么就会产生 44 的种子点。 这样每个关键点的信息量就包含在了448=128维特征向量里。图5 特征向量描述子的生成2 SIFT特征向量的匹配对SIFT特征向量进行匹配是根据相似性度量来进行的，常用的匹配方法有：欧式距离和马氏距离等。采用欧氏距离对SIFT的特征向量进行匹配。获取SIFT特征向量后, 采用优先k-d树进行优先搜索来查找每个特征点的近似最近邻特征点。在这两个特征点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受