传统图像特征点提取算法

计算机视觉中，很大一部分研究集中在图像特征提取和特征生成算法上。对图像的优化，不同于一般数学问题的优化方法，图像的优化是对像素点，在某一个小的邻域内，进行特征的提取或者图像的分析，该优化主要是进行局部区域的优化，要寻找局部极值，而不像传统的优化算法那样进行全局的优化求解。由于相同物体在不同状态下所产生的图像不同，使得不同图像具有不同亮度，不同旋转方向和不同尺度的差异。想要提取出具有代表性且性质鲁棒的特征点，一直是学术研究的焦点之一。

SIFT与SURF的关系

SIFT（Scale invariant feature Transform）算法是由David Lowe提出的尺度不变特征转换算法，其目标是解决低层次特征提取及其图像匹配中的实际问题。该算法是一种基于尺度空间，对图像缩放变换保持不变性的图像局部特征描述子。其主要分为三部分进行图像的特征点提取和描述。

SIFT算法优点：

特征稳定，对旋转、尺度变换、亮度保持不变性
对视角变换、噪声也有一定程度的稳定性

SIFT算法缺点：

实时性不高
对于边缘光滑目标的特征点提取能力较弱，不够优化

并且。因此，Bay于2006年提出了SURF（Speeded Up Robust Features）特征检测算法(发布于ECCV)。该算法具有较好的尺度不变性和旋转不变性，并且具有快速的计算能力，一直是图像拼接、图像检测和恢复等应用采用的主流算法之一。

SURF算法是对SIFT算法的加强版本，同时能够加速提取更加鲁棒的特征，是SIFT算子的速度的三倍以上，并且提取出的特征点更有代表性。同时也对描述子的生成以及特征点的匹配进行了优化。其主要采用了Harr特征以及积分图像，加快了程序搜索和运行的时间，优化了特征点提取的理论算法。

SIFT算法

Sift全称尺度不变特征变换，是1999年Lowe提出的，是一种基于尺度空间的，对图像缩放、旋转、甚至仿射变换保持不变性的图像局部特征描述算子。

SIFT算法流程：

尺度空间局部极值点定位
关键点精确定位
关键点方向确定
生成特征向量

尺度空间局部极值点定位

Sift的特征点是在DOG金字塔尺度空间中提取的，尺度空间的构建涉及到高斯卷积、图像下采样和高斯差分操作。在尺度空间中先初步提取出在尺度空间和二维图像空间上都是局部极值点的兴趣点，再滤除掉能量低的不稳定的和错误的兴趣点，得到最终稳定的特征点。

尺度空间

特征点检测需要知道特征点的位置和尺度，因为真实世界中的物体只有在一定的尺度下才有意义，寻找的特征点需要找到连续的尺度空间下位置不发生变化的点。构建尺度空间的目的就是找到在尺度变化中具有不变性的位置，可以使用连续的尺度变化，即在尺度空间中所有可能的尺度变化中找到稳定的特征点，通过这种方式找到的极点可以保证在图像缩放和旋转变化中具有不变性。

设 $I(x,y)$ 为原始图像， $G(x,y, \sigma)$ 是尺度空间可变的高斯函数，则一个图像的尺度空间可以定义为：

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

$\sigma$ 表示尺度空间大小。 $\sigma$ 越大，图像越模糊，表示图像概貌； $\sigma$ 越小，图像越清晰，表示图像细节；

其中高斯函数定义为：

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

经过一系列的尺度空间变换和二倍的下采样，最终得到高斯金字塔。

公式(1)中的图像 $I(x,y)$ 具有无限的分辨率，也就是说他的尺度 $σ=0$ ，即 $I(x,y)=L(x,y,0)$ 。也就是说公式(1)得到的尺度空间图像 $L(x,y,\sigma)$ 是由尺度尺度空间为0的图像 $L(x,y,0)$ 生成的，但是现实生活中是不存在尺度空间为0，即具有无限分辨率的图像的。在Lowe的论文中，他们给定原图一个很小的尺度空间，为0.5。因此由一个小尺度空间图像 $L(x,y,\sigma_1)$ 生成一个大的尺度空间图像 $L(x,y,\sigma_2)$ 的过程为:

$L(x,y,\sigma _2) = G(x,y,\sqrt{\sigma^2_2 − \sigma^2_1} )∗L(x,y,\sigma _1)$

由于实际中尺度为0的图像是无法得到的，因此我们得到的尺度图像的基准图像一定是由公式(3)得到的。

高斯差分

为了在尺度空间中找到稳定不变的极值点，在SIFT算法中使用了高斯差分(DOG)函数 $D(x,y,\sigma)$ ，定义为:

$\begin{aligned} D(x,y,\sigma) &= [D(x,y,k\sigma) - D(x,y,\sigma)] \times I(x,y)\\ &= L(x,y, k\sigma) - L(x, y, \sigma) \end{aligned}$

其中 $kσ$ 和 $σ$ 是连续的两个图像的平滑尺度，所得到的差分图像在高斯差分金字塔中。

选择高斯差分函数的原因：

计算简单，因为 $L(x, y, \sigma)$ 可以由上一步计算得到， $D(x,y,\sigma)$ 只需要进行减法计算
LoG（Laplacian of Gaussian）高斯拉普拉斯算子，即图像的二阶导数，能够在不同的尺度下检测到图像的斑点特征，从而检测到图像中尺度变化下的位置不动点，但是LoG的运算效率不高
通过前人的实验证明LoG提取的特征稳定性最强

而DoG是LoG的近似。DoG和LoG的关系如下述所示：

$\begin{aligned} \sigma \nabla ^2 G &= \frac{\partial G}{\partial \sigma}\\ &\approx \frac{G(x,y,k\sigma)−G(x,y,\sigma)}{k\sigma−\sigma} \end{aligned}$

因此，有：

$G(x,y,k\sigma)−G(x,y,\sigma) \approx(k-1) \sigma ^2 \nabla ^2 G$

$\sigma ^2 \nabla ^2 G$ 正是尺度归一化算子的表达形式。在所有的尺度中 $k−1$ 是一个常数，当 $k$ 趋近于1的时候误差趋近于0，但实际上这种误差对于极值的位置检测并没有什么影响。（这里不是很懂）

高斯图像金字塔

高斯图像金子塔和差分金字塔如图所示：

其中需要注意的是：

金字塔的组数，大多数情况下为4，实际上这个值与图像的大小有关，为 $log_2(min(M,N))-3$
每层的组数，为 $S_1 = s + 3$ ，这里的 $s$ 为极值检测需要的层数，一般取值为3到5
$k = 2^{\frac{1}{s}}$ ， $\sigma_0=1.6$

生成过程

输入图像的尺度为0.5，由该图像进行高斯模糊得到的第0组的第0层图像为基准图像，基准图像的尺度为 $\sigma_0$ ，称为基准尺寸，由第0层生成第一层图像，尺度为 $k\sigma_0$ ，第二层为 $k^2\sigma_0$ ，共得到 $s$ 层图像：

$\sigma=k^r \sigma_0, \quad r=0,1,...,s-2$

构建完第0组(octave)后，将第0组的倒数第三层(scale)图像进行下采样得到。由5式可以看出，倒数第三的尺度为 $k^s\sigma_0$ ，其中 $k = 2^{\frac{1}{s}}$ ，则可以得到其尺度为 $2\sigma_0$ 。这样使得DoG满足尺度连续性。

在高斯金字塔中第一组中的不同层中的平滑尺度分别为 $σ$ , $kσ$ , $k^2σ$ , $k^3σ$ ,…, $k^{s+2}σ$ 把 $k=2^{\frac{1}{s}}$ 带入上面的数列中，则第一组中不同层的平滑尺度分别为:

$σ,2^{\frac{1}{s}}σ,2^{\frac{2}{s}}σ,2^{\frac{3}{s}}σ,…,2^{\frac{s}{s}}σ,2^{\frac{s+1}{s}}σ,2^{\frac{s+2}{s}}σ$

一共有 $s+3$ 层，那么取得的高斯差分金子塔有 $s+2$ 层,平滑尺度分别为:

$σ,2^{\frac{1}{s}}σ,2^{\frac{2}{s}}σ,2^{\frac{3}{s}}σ,…,2^{\frac{s}{s}}σ,2^{\frac{s+1}{s}}σ$

最终有极值的只有 $s$ 层，平滑程度为：

$2^{\frac{1}{s}}σ,2^{\frac{2}{s}}σ,2^{\frac{3}{s}}σ,…,2^{\frac{s}{s}}σ$

由第二组的第一层的平滑尺度为 $2σ$ 可知，应该从第一组的倒数第三层开始下采样。按照这样的操作第二组的最终有极值的几层的平滑程度分别为:

$2^{\frac{s+1}{s}},2^{\frac{s+2}{s}},...,2^{\frac{s+s}{s}}$

与第一组的有极值的层的平滑尺度正好相接，满足连续性。

后面的组依次仿照前面的方法生成

DoG金字塔相对较为简单，由高斯金字塔相邻的两层相减得到DoG金字塔中的一层，然后依次得到。高斯金字塔中每组有 $s+3$ 层，所以高斯差分金字塔中每组有 $s+2$ 层。

极值点选取

如上图的最右方所示，只有当前点与其周围26个点值相比，如果是最大值或者最小值则该点为极值点，否则不是。这种比较计算量比较小，因为大多数的点在比较的前几步就已经被pass掉了
这里还有一个问题，对于除第一组以外的其他组中得到的极值点的位置，如何映射到原图中的位置呢？这里我觉得可能是根据位置的对应关系。

关键点精确定位

在Lowe的论文中，使用的是泰勒展开式作为拟合函数。通过局部极值点定位得到的极值点是一个三维向量，包括它所在的尺度 $σ$ 以及所在尺度图像中的位置坐标，即 $X=(x,y,σ)$ .因此需要三维的泰勒展开式进行展开，设 $X_0=(x_0,y_0,σ_0)$ ，则其展开式的矩阵形式为：

写为矢量的形式为：

$f(X) = f(X_0) + \frac{\partial f^T}{\partial X}(X-X_0) + \frac{1}{2}(X-X_0)^T \frac{\partial^2 f}{\partial X^2}(X-X_0)$

在这里 $X_0$ 表示离散的差值中心， $X$ 表示拟合后连续空间的差值点坐标，则设 $\hat{X}=X−X_0$ ，表示偏移量，带入21式，另求得的导数为0，则有:

$\hat{X} = -\frac{\partial^2 f^{-1}}{\partial X^2} \frac{\partial f}{\partial X}$

这里没懂

把该极值带入原公式中，有结果：

$f(\hat{X}) = f(X_0) + \frac{1}{2} \frac{\partial f^T}{\partial X} \hat{X}$

SURF算法过程

构建积分图像

在一个特征点 $x=(x,y)$ 的领域上，计算其积分图像 $I(x,y)$ ：

$I_{\Sigma }(x)=\sum_{i=0}^{i \leq x} \sum_{j=0}^{j \leq y}I(i,j)$