尺度不变特征转换(Scale-invariant feature transform 或 SIFT)是一种机器视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变数，融特征点和描述于一体。

SIFT算子——算法

尺度空间极值检测

图像在不同的尺度下用高斯滤波器进行卷积，然后利用连续高斯模糊化图像差异来找出关键点。

高斯金字塔构建

图像的尺度空间被定义为一个函数 $L(x,y,\sigma)$，它是由可变尺度高斯函数$G(x,y,\sigma)$与输入图像$I(x,y)$的卷积产生的。

$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$ $G(x,y,\sigma)=\frac1{2\pi \sigma^2}e^{-\frac{x^2+y^2}{2\sigma ^2}}$

$\sigma$是尺度坐标(尺度变化因子)，$\sigma$大小决定图像的平滑程度，$\sigma$值越大图像模糊得越严重。大尺度对应图像的概貌特征，小尺度对应图像的细节特征。一般根据$3\sigma$原则，高斯核矩阵的大小设为$(6\sigma +1)\times (6\sigma +1)$。

SIFT算子中的高斯金字塔由多个组（Octave）组成，而每个组（Octave）由多层（Interval）组成。

每组图像的第一层由上一组的第一层高斯金字塔降采样而得，每组的下一层由上一层高斯滤波而得。

先按高斯金字塔将原图像化为多组（Octave），后一组的尺寸是前一组的$\frac 12$。每组再由第一层进行高斯滤波，同组的图像尺寸相同。

在降采样时，高斯金字塔中一组(Octive)的底层图像是由前一组图像的倒数第3张图像隔点采样得到。

金字塔组数（Octave）可由原始图像和塔顶图像的大小之比算得。

$Octave = \log_2 \frac {min(width_0,height_0)}{min(width,height)}$

式中，$width_0、height_0$分别为原始图像的宽高，$width、height$为塔顶图像的宽高。

每组分为$S$个尺度间隔（做$S$次高斯滤波），相邻两个尺度的$\sigma$之比为：

$k=2^{\frac 1S}$

则每一组包含$1$，$2^{\frac 1S}$，$2^{\frac 2S}$，…，2，一共$(S+1)$幅图像（即$(S+1)$层）。

尺度参数$\sigma$的取值与金字塔的组数和层数相关。设第一组第一层的尺度参数取值为$\sigma (0,0) = \sigma _0$，则第$m$组第$n$层的$\sigma$取值为

$\sigma(0,0)=\sigma_0,\quad\sigma(o,s)=2^{o}\times k^{s}\times \sigma_0 = 2^{o}\times 2^{\frac sS}\times \sigma_0=2^{o+\frac sS}\times \sigma_0$

高斯差分金字塔（DoG金字塔）

DoG金字塔计算简单，提供了LoG算子良好的近似，LoG算子的极值相较于Hessian、Harris等算子，能提供更稳定的图像特征，且具有尺度不变性。

高斯差分图像由高斯金字塔中同一组(Octave)内相邻层(Interval)的图像作差得到。

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

高斯金字塔一级$S$个图像，将得到DoG金字塔一级$(S-1)$个图像。

空间极值点检测

对DoG金字塔中的每个像素，在三维领域内判断是否是极值点（最大值/最小值）。如果是极值点，则该点暂定为图像在该尺度下的一个特征点。

三维领域：中间检测点与其同尺度的8个邻域像素点以及上下相邻两层对应的$9\times 2$个像素点一共$3\times 9-1=26$个点作比较。

该步的极值点检测可以确定极值点的位置（像素级）和尺度，极值点的大小反映了极值处的对比度（反差）。

为了每组（Octave）得到$S$个尺度的极值结果，需要DoG金字塔每组$S+2$个图像，需要高斯金字塔每组$S+3$个图像。

关键点定位

亚像素（子像素）精确定位

在DoG尺度空间检测到的极值点是离散的，通过三元二次函数拟合来精确确定关键点的位置和尺度，达到亚像素精度。

将原点移到极值点处，并将高斯差分在该极值点处展开，保留一阶项及二阶项，得到：

$D(X)=D+\frac {\partial D^T}{\partial X}+\frac 12 X^T\frac {\partial ^2 D}{\partial X^2}X$

其中，$X=(x,y,\sigma )^T$

令$D’(X)=0$，得极值点的偏移量

$\hat X = -(\frac {\partial^2 D}{\partial X^2})^{-1}\frac {\partial D}{\partial X}$

如此得到亚像素精度的极值点$\hat X$。

利用$\hat X$得到新的高斯差分值$D(\hat X)$

$D(\hat X)=D+\frac 12 \frac {\partial D^T}{\partial X}\hat X$

设置对比度阈值$T$，当$|D(\hat X)|<T$时，去除该对比度低的不稳定极值点$\hat X$。

去除边缘点

由于DoG算子对边缘点很敏感，在边缘处也有很大的响应值，需要剔除不稳定的边缘响应点。

在极值点处，利用$D(X)$计算Hessian矩阵

$H= \begin{bmatrix} D_{xx}&D_{xy}\\ D_{yx}&D_{yy} \end{bmatrix}$

$D(X)$的主曲率与$H$的特征值成正比，在边缘梯度方向比较大，对应一个大的特征值$\alpha$；在沿着边缘的方向上比较小，对应一个小的特征值$\beta$。（两个特征值的之比为$r = \alpha/\beta$）

两特征值的和等于$H$的迹$Tr(H)$

$Tr(H)=D_{xx}+D_{yy}=\alpha + \beta$

两特征值的积等于$H$的行列式$det(H)$

$det(H)=D_{xx}D_{yy}-D_{xy}D_{yx}$

则有

$\frac {Tr^2(H)}{det(H)}=\frac {(\alpha + \beta)^2}{\alpha \beta}=\frac {(r+1)^2}{r}$

当两特征值相等，即$r=1$时，$\frac {(r+1)^2}{r}$最小。$r$越大，$\frac {(r+1)^2}{r}$越大。

边缘点对应的特征值之比$r$比其他的点大，所以设置一个关于$r$的阈值$T_r$，当$\frac {Tr^2(H)}{det(H)} > \frac {(T_r+1)^2}{T_r}$时，判断该极值点为边缘点，去除该点。

获取关键点主方向

为了使特征描述子具有旋转不变性，需要利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数。

根据关键点的尺度，在高斯金字塔对应图像的关键点位置处的局部区域计算梯度方向直方图，计算每个点的梯度幅值和方向。（一般取大小为$3\sigma$的领域）

梯度幅值$m$：

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

梯度方向$\theta$：

$\theta (x,y)=\tan^{-1}\frac {L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}$

将$[0\circ, 360\circ]$分为多个柱，梯度幅值加到对应的梯度方向的柱上，选出直方图的峰值为该关键点的主方向。

关键点描述

到上述步骤已经获得了关键点的位置、尺度以及方向。关键点的描述利用关键点及其周围像素，计算块内梯度直方图，生成特征向量，用于描述每个关键点。

确定用于计算关键点描述的局部区域

描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生，局部区域的半径$radius$：（$\sigma_{oct}$为关键点所在组的组内尺度）

$radius = \frac {3\sigma_{oct}\times \sqrt2 \times (d+1)}{2},\quad d = 4$

除上面的方法以外，还可以直接使用直径$diameter$：（$\sigma 为关键点所在尺度$）

$diameter = 6\sigma +1$

根据关键点主方向变换坐标系

将坐标轴旋转至关键点主方向，以确保旋转不变性。旋转后采样点的新坐标为

$\begin{bmatrix} x'\\ y' \end{bmatrix} = \begin{bmatrix} \cos \theta&-\sin \theta\\ \sin \theta&\cos \theta \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} ,\quad x,y \in [-radius,radius]$

计算关键点描述

在局部区域内对每个像素点求其梯度幅值和方向，生成方向直方图。

梯度幅值高斯（$\sigma$为局部区域大小的一半）加权：离关键点越近，对关键点描述的作用越大。

基于像素位置和梯度方向的三线性插值：将梯度方向和位置分解再加权。避免梯度方向直方图在分块边界和梯度方向量化的边界处的突然变化。

归一化关键点描述

向量归一化：克服光照的影响，主要是增益的影响。

方向直方图每个方向上梯度幅值限制在一定门限值以下（门限一般取0.2，像素灰度值在0~1范围内）：克服相机饱和、光照对3D表面不同方位影响不同等非线性光照情形。

SIFT算子——应用

关键点匹配
场景匹配
全景拼接
图像检索
笔迹鉴定