SIFT，即尺度不变特征变换（Scale-invariant feature transform，SIFT），是用于图像处理领域对局部特征的一种描述方法。主要原理是通过一些数学计算得到图像中特征点的坐标，并根据该点周围像素点的值生成一个用于稳定描述该特征点的向量。该算法常用于特征匹配领域。

SIFT算法具有如下一些特点：

SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
区分性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；
高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
可扩展性，可以很方便的与其他形式的特征向量进行联合。

一、图像尺度空间

在一定范围内，无论物体是大还是小，人眼都能分辨出来；但计算机对不同尺度下的物体分辨能力却很低。所以要让机器能够对物体在不同尺度下有一个统一的认知，就需要考虑图像在不同尺度下都存在的特点。

不同尺度的图像可以通过高斯模糊（或称为高斯滤波）来模拟：

$L(x, y, \sigma)=G(x, y, \sigma)*I(x, y)$

其中I为图像，G为高斯函数：

$G(x, y, \sigma)=\frac{1}{2\pi\sigma^2}e^{\frac{x^2+y^2}{2\sigma^2}}$

其中σ用于控制滤波器权重，σ越大，权重数值分布越均匀，即周边值更大、中心值更小，得到的图像越模糊。

通过这个方法可以得到不同尺度空间的图像，图像越模糊，就相当于得到了更远距离/更小尺度空间的图像。

二、高斯差分金字塔

对于一张图像进行n-1次上/下采样操作，得到的n个不同分辨率的结果可以组合成一个图像金字塔。对金字塔的每一层进行m次不同程度的高斯模糊，最终得到n×m张图像。

之后对金字塔每一层得到的模糊结果分别求差，得到n×(m-1)个二维数组，得到的这个结果就是高斯差分金字塔（Difference of Gaussian, DOG）。DOG中较大的值表示该点对于不同的模糊程度变化更大，该点更有可能是特征的关键点/边缘。找出局部极值点需要对每个点与其周围的26个点（同平面8个，上下各9个）点进行比较。

DOG用数学公式表示如下：

$D(x,y,\sigma)=L(x, y, k\sigma)-L(x, y, \sigma)$

三、特征描述

1 特征点的方向

每个像素点L(x, y)的梯度的模m(x, y)以及方向θ(x, y)计算如下：

$m(x,y)=\sqrt{[L(x+1,y)-L(x-1,y)]^2+[L(x,y+1)-L{(x,y-1)}]^2}\\ \theta(x,y)=arctan \frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}$

每个像素点可以得到位置(x, y)、尺度m和方向θ三个信息。对于每个特征点，统计其邻域所有像素点在8个方向上的尺度和，尺度和最大的方向视为该特征点的主方向，占比超过主方向80%的视为辅方向。具有多个方向的关键点可以被复制成多份，然后将方向值分别赋给复制后的特征点，于是一个特征点就产生了多个坐标、尺度相同，但方向不同的特征点。

2 生成特征描述

本部分将使用邻域像素的方向和尺度为该特征点生成一个唯一的指纹，称为描述符。首先在关键点周围采用16×16的邻域，将该16×16区域进一步划分为4×4子块。由于子块中的每一个像素都具有8个方向中的一个，并且具有尺度。于是对于每一个子块都能用一个长度为8的向量来表示该子块所有像素在8个方向上的尺度和。

最终对于每一个特征点，我们得到了一个总长度为4×4×8=128的特征描述符。

计算两个特征点描述符之间的欧氏距离即可进行匹配。原算法中使用的是kd树进行搜索匹配，这里不作详细描述。

四、OpenCV中的SIFT算法

由于算法版权问题，SIFT算法只能在OpenCV3.4及以下版本才能使用。

特征描述：

1
2
3

sift = cv2.xfeatures2d.SIFT_create()  # 创建一个SIFT对象
kp, des = sift.detectAndCompute(img_gray, None) # 返回关键点对象和以及每个关键点的特征向量
show_kp_img = cv2.drawKeypoints(img_gray, kp, img)  # 在图像中标出关键点

特征匹配：

# 一对一匹配
bf = cv2.BFMatcher(crossCheck=True)  
matchs = bf.match(des1, des2)
matches.sort(key=lambda x: x.distance)
# 可视化匹配结果
matched_img = cv2.drawMatches(img1, kp1, img2, kp2, matches[:10], None, flags=2)