SIFT算法是一种基于尺度空间的算法。利用SIFT提取出的特征点对旋转、尺度变化、亮度变化具有不变性，对视角变化、仿射变换、噪声也有一定的稳定性。

SIFT实现特征的匹配主要包括四个步骤：

• 提取特征点
• 计算关特征点的描述子
• 利用描述子的相似程度对特征点进行匹配
• 消除误匹配点

1、 提取特征点

构建尺度空间：模拟图像的多尺度特征。经证实，唯一可能的尺度空间核是高斯函数。用L(x,y,σ)表示一幅图像的尺度空间，由可变尺度的高斯函数G(x,y,σ)和图像卷积产生，即，其中，(x,y)表示图像上的点，σ是尺度因子。

 

高斯金字塔：

• 将图像与不同σ的高斯函数做卷积
• 对图像进行降采样

第一阶的第一层是原始图像，同一阶中相邻两层的尺度因子比例为k,其它层依次类推。

第二阶第一层的尺度因子来自于第一阶中间层的尺度因子。

DOG金字塔

Laplace算子：，具有旋转不变性（证明参考）。

LOG算子：将Laplace算子与高斯函数相结合，

为了简化LOG的计算，提出了DOG算子即高斯差分函数：

所以， 而

所以

根据上面可知，高斯差分算子只是比LOG算子多了一个系数(k-1)，并不影响特征点的求解。

所以DOG函数如下：

DOG金字塔通过高斯金字塔相邻尺度空间函数相减得到，第一层的尺度因子与高斯金字塔第一层的尺度因子一致。

检测极值点，初步确定特征点

该步骤检测DOG空间的最大最小值，需要对DOG尺度空间的每个像素点(除去最顶层最底层)与其周围26个像素点(如下图，同层相邻8个，上一层9个，下一层9个)进行比较。若结果是该像素点比其周围26个像素点值都大或都小，则初步判断为局部极值点，记下其位置和尺度因子。若结果是该像素点比其周围26个像素点值都大或都小，则初步判断为局部极值点，记下其位置和尺度因子。

对上一步得到的特征点进行筛选，去除低对比度及边缘的点。

精确定位极值点：

我们找的极值点属于离散空间上的点，不一定是真正极值点，需要一条曲线进行拟合。

设A(x₀,y₀,σ₀)为检测到的极值点，B(x,y,σ)为真正的极值点，在A附近应用泰勒展开公式：

D对x求导，令其为0得：

带入上式得：

若上式求出的中|Δx|或|Δy|或|Δσ|中有一个>0.5,表示该插值点偏离了插值中心，

令x=x+round(Δx)

y=y+round(Δy)

σ=σ+round(Δσ)

继续插值直到达到最大迭代次数或|Δx|、|Δy|、|Δσ|均<0.5。

对得到的极值点B计算D(B)进行低对比度筛选。

消除边缘效应：

目的是消除边缘极值点。边缘极值点满足的条件是：一个方向上变化率非常小，另一个方向上变化率较大(如在黑板上画一条水平线，则水平方向灰度值变化率非常小，垂直方向变化率大，且主曲率与黑塞矩阵的特征值成正比)。根据这一性质，求出黑塞矩阵，设H的特征值为λ₁、λ₂，其中较大的是λ₁。令r=λ₁/λ₂,则边缘极值点即是r比较大的点，设r阈值为thres,对所有的极值点判断其r值是否大于thres,若大于则去除。

更简单的方法是，利用进行筛选，其中λ₁+λ₁=tr(H)，λ₁λ₂=|H|。

寻找特征点主方向：

对于任一像素点(x,y),

其梯度值：

梯度方向：

对于每个特征点，统计以其为中心的邻域内的像素梯度方向，用直方图表示统计结果，直方图的峰值就是该特征点的主方向。

2、特征点描述子：

以特征点x为中心画圆邻域，将该邻域划分成16个子区域。每为一个单位，那么总共有8个刻度，统计每个子区域内8个刻度值，如下图：

则用16x8=128维矢量作为该特征点的描述子。

3、特征匹配：

分别提取图像1、图像2的特征点并计算描述子。对图像1的每个特征点f，在图像2中找到距离其最近的两个特征点k1、k2，并计算f与k1、f与k2之间夹角θ1、θ2,

若，则为一对匹配点。

4、消除误匹配点：使用RANSAC算法消除误匹配点

• 随机找到8个特征点对，使用八点法计算基础矩阵F
• 用F验算剩余特征点对，计算用F验算成功的点对数n
• 重复一定次数，找到使n达到最大值的F，不满足F的特征点对删除。