作者：Frank
时间：2016-07-10

---

在Feature-Based类型的SLAM系列中，在计算相机姿态之前，需要得到前后帧或者前后关键帧的特征进行匹配并计算前后帧之间的位姿关系，因此，特征检测在Feature-Based SLAM中起到了不可替代的作用。本节和下一节将介绍两种典型的特征检测算子，即SIFT特征检测算子和ORB特征检测算子的原理。

SIFT特征检测算子

paper来源：Distinctive Image Features from Scale-Invariant Keypoints；
SIFT(Scale-invariant feature transform)是一种在计算机视觉中用来检测局部特征的算法。该算法通过对一幅图像中自定义的图像特征点的计算，求图像中所有的特征点(interest points,corner points)及其有关scale和orientation的描述子得到特征并对图像进行特征点匹配，得到了鲁棒(robust)的效果。此算法由David Lowe在1999年发表，2004年完善总结。SIFT在空间尺度中寻找极值点，并提取出其位置、尺度和旋转不变量。因此其具有尺度不变性和旋转不变性。
该算法主要包括4个步骤来进行特征点的计算和匹配：

1. 构建尺度空间，检测极值点，获得尺度不变性；
2. 特征点过滤并进行精准定位，剔除不稳定的特征点；
3. 在特征点处提取特征描述符，为特征点分配方向值；
4. 生成特征描述子，利用特征描述符寻找匹配点；

以下将围绕着5部分详细展开描述。

1.构建尺度空间

1.1.理论知识

1.1.1.高斯核

为了构造尺度空间，需要在构建尺度空间金字塔时引入高斯核作为尺度变换函数，而Koenerink, Lindeberg,Florack等人用精确的数学形式通过不同的途径都证明了高斯核是实现尺度变换的唯一变换核，具体论文参考：Scale-space theory in computer vision
使用高斯滤波器对图像进行尺度空间金字塔塔图的构建，让这个尺度空间具有以下的性质：

1. 加权平均和有限孔径效应
   信号在尺度t上的表达可以看成是原信号在空间上的一系列加权平均，权重就是具有不同尺度参数的高斯核。
   信号在尺度t上的表达也对应一个无方向性的孔径函数（特征长度为$\sigma = \sqrt t $）来观测信号的结果。这时候信号中特征长度小于$\sigma$的精细结构会被抑制（理解为一维信号上小于$\sigma$的波动会被平滑掉）。

2. 层叠平滑
   也叫高斯核族的半群（Semi-Group）性质：两个高斯核函数的卷积等于另外一个不同核参数的高斯核卷积。
   $$g(\mu ,\sigma _1) * g(\mu ,\sigma _2) = g(\mu ,\sqrt {\sigma _1^2 + \sigma _2^2} ) \tag{1}$$
   这个性质的意思就是说不同的高斯核函数对图像的平滑是连续的。

3. 局部极值递性
   这个特征可以从人眼的视觉原理去理解，人在看一个物体时，离得越远，物体的细节看到的越少。细节特征是在减少的。
   高斯核对图像进行滤波具有压制局部细节的性质。

4. 尺度伸缩不变性
   这里只是个公式推导的问题，对原来的信号加一个变换函数，对变换后的信号再进行高斯核的尺度空间生成，新的信号的极值点等特征是不变的。

申明：该部分引用来源：尺度空间理论

1.1.2.DOG角点检测

DOG（Difference of Gaussian）是灰度图像增强和角点检测的方法，其做法比较简单，但证明比较复杂，具体讲解如下：
Difference of Gaussian（DOG）是高斯函数的差分。在图像处理中，我们可以通过将图像和高斯函数进行卷积得到一幅图像的低通滤波结果，即去噪过程，这里的Gaussian和高斯低通滤波器的高斯一样，是一个函数，即正态分布函数：
$$G(x) = {1 \over \sqrt {2\pi {\sigma ^2}}}{e^{ - {x^2 \over 2{\sigma ^2}}}} \tag{2}$$
那么DOG即高斯函数差分是两幅高斯图像的差，其一维表示为：
$$f(x;\mu ,\sigma _1,\sigma _2) = {1 \over {\sigma _1 \sqrt {2\pi} }}e^ {- {(x - \mu )^2 \over 2\sigma _1^2}}-{1 \over {\sigma _2 \sqrt {2\pi} }}e^ {- {(x - \mu )^2 \over 2\sigma _2^2}} \tag{3}$$
则其二维表示为：
$$f(u,v ,\sigma) = {1 \over { 2\pi \sigma^2 }}e^ {- {(u^2+v^2) \over 2\sigma^2}}- {1 \over { 2\pi \sigma^2 }}e^ {- {(u^2+v^2) \over 2K^2\sigma^2}}\tag{4}$$
具体到图像处理上来说，就是讲两幅不同参数下的高斯滤波结果相减，得到DOG图。

1.2 构建尺度空间

1.2.1.高斯核函数的引入

尺度空间理论的目的是模拟图像数据的多尺度特征以实现图像的尺度不变性。
高斯卷积核是实现尺度变换唯一的线性核，因此一幅图像的尺度空间定义为：
$$L(x,y,\sigma ) = G(x,y,\sigma ) * I(x,y) \tag{5}$$
其中，$ G(x,y,\sigma )$是尺度可变高斯函数，$G(x,y,\sigma)={1 \over { 2\pi \sigma^2 }}e^ {- {(u^2+v^2) \over 2\sigma^2}}$。(x,y)是图像坐标，$\sigma$是尺度坐标。$\sigma$大小决定图像的平滑程度。尺度越大，图像越平滑，则图像上显示出来的细节信息越少。大的$\sigma$值对应低分辨率图像，小的$\sigma$值对应高分辨率。为了有效的在尺度空间检测到稳定的关键点，利用了节1.1.2提出的的高斯差分（DOG）构建了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成：
$$D(x,y,\sigma ) = (G(x,y,k\sigma ) - G(x,y,\sigma )) * I(x,y)
= L(x,y,k\sigma ) - L(x,y,\sigma ) \tag{6}$$
下图表示不同$\sigma$下的图像尺度空间：

1.2.2. 图像金字塔的建立

对于一幅图像I，建立其在不同尺度(scale)下的图像，也称为一个八度(octave)，这是为了实现尺度不变性，也就是在任意尺度都能够有对应的特征点，第一个octave的scale为原图大小，后面的每一个octave为上一个octave下采样的结果（width,height分别为原来的一半，图像为原来的1/4）。

next octave是由first octave下采样得到的。
$$2^{i-1}(\sigma,k \sigma,k^2 \sigma,…,k^{n-1}\sigma), k=2^{1 \over s} \tag{7}$$
式（7）表示尺度空间的所有取值，s为每组层数，一般为3~5。0塔的0层是原始图像（或是原始图像double后的图像）。往下每一层是对其下一层进行Laplacian变换（高斯卷积，其中σ值渐大，例如可以是$\sigma,k\sigma,k^2 \sigma,…$，直观上越往上图片越模糊。

1.2.3.检测极值点

为了寻找尺度空间的极值点，每个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示：

中间的检测点和它同尺度的8个相邻点以及上下相邻尺度（跨尺度）对应的$9 \times 2$个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层（跨尺度）的26个邻域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。
在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，在每组图像的顶层继续用高斯模糊生成了3幅图像，高斯金字塔每组有S+3层图像，DOG金字塔每组有S+2层图像。如果所示：

假设S=3，也就是每个塔里有三层，则$k=2^{1 \over s}=2^{1 \over 3}$，那么按照上图可得高斯空间有3个分量，DOG空间有2个分量，在DOG空间中，1st-octave两项分别为$\sigma,k\sigma$；2nd-octave 两项分别为$2\sigma,2k\sigma$；由于无法取极值，我们必须在高斯空间继续添加高斯模糊项，使得形成$\sigma,k\sigma,k^2 \sigma,k^3\sigma,k^4\sigma $这样可以选择DOG空间的中间三项$k\sigma,k^2 \sigma,k^3\sigma$（因为都有极值），那么下一octave所得三项即为：$2k\sigma,2k^2 \sigma,2k^3\sigma$其首项是$2k\sigma=2^{4 \over 3}$。刚好与上一octave的末项$k^3 \sigma=2^{3 \over 3}$尺度变化连续起来，所以每次要在Gaussian空间添加三项，每组塔共有S+3层图像，对应的DOG金字塔共有S+2层图像。
使用LOG能够很好的找到图像中的特征点，但是需要进行大量的计算，所以引入DOG图像的极大极小值来寻找特征点，极值点检测用的是非最大值抑制准则。

2.特征点过滤及精确定位

关键点的选取要经过两步：(1) 它必须去除低对比度和对噪声敏感的候选关键点；(2)去除边缘点。

2.1. 去除低对比度的点

对局部极值点进行三维二次函数拟合以精确定位特征点的位置和尺度，尺度空间函数$D(x,y,\sigma)$的泰勒展开式为：
$$ D(x) = D + {\partial {D^T} \over \partial x}x + {1 \over 2}x^T{\partial ^2 D \over \partial x^2}x \tag{8}$$
令上式对x的偏导数等于0，可得极值点位置：
$$\hat x = -{ {\partial ^2D^{ - 1}} \over {\partial x^2}}{\partial ^2D \over \partial x^2} \tag{9}$$
把公式(9)代入公式(8)有：
$$D(\hat x)=D(x,y,\sigma)+{1 \over 2}{\partial D^T \over \partial x}\hat x \tag{10}$$
若$|D(\hat x)| \ge 0.03$，则该特征点就保留下来，否则丢弃。

2.2.去除边缘响应点

一个定义不好的高斯差分算子的极值在横跨边缘的区域有较大的主曲率，而在垂直边缘的方向有较小的主曲率（Harris角点检测器中的定义）。主曲率由海森矩阵求出：
$$H=\left[{\matrix{
D_{xx}&D_{xy} \cr
D_{yx}&D_{yy} \cr
}}\right] \tag{11}$$
D的主曲率和H的特征值成正比，令$\alpha$为最大特征值，$\beta$为最小特征值，则：
$$Tr(H)=D_{xx}+D_{yy}=\alpha +\beta \tag{12} $$
$$Det(H)=D_{xx}D_{yy}-(D_{xy})^2=\alpha \beta \tag{13}$$
令$\alpha =\gamma \beta$，则：
$$ {Tr(H)^2 \over Det(H)^2}={(\alpha+\beta)^2 \over \alpha \beta}={(\gamma \beta+\beta)^2 \over \gamma \beta }={(\gamma+1)^2 \over \gamma} \tag{14} $$
如果主曲率小于$(\gamma+1)^2 / \gamma$，保留该特征点，否则丢弃。在Lowe的论文中，取$\gamma =10$。
这部分实际上是结合了Harris角点检测，利用Harris角点检测来对图像边缘进行进一步筛选。

3.特征描述符提取和方向值分配

在节2.中我们通过几个步骤确定了每幅图像中存在的特征点，在这一节中我们需要为特征点提供一个方向值，也就是为每个特征点计算一个方向。依照这个方向做进一步的计算，利用关键点邻域像素的梯度方向分布特性为每个特征点指定方向参数，使得算子具有旋转不变性。梯度方向计算公式如下：
$$m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y))^2+(L(x,y+1)-L(x,y-1))^2} \tag{15} $$
$$\theta(x,y)=\alpha \tan {2({L(x+1,y)-L(x-1,y) \over L(x,y+1)-L(x,y-1)})} \tag{16}$$
其中，$m(x,y)$表示(x,y)处的梯度，$\theta (x,y)$表示方向，L是特征点所在的空间尺度函数。至此，图像的特征点已经检测完毕，每个特征点有三个信息：位置，所处尺度，方向，由此可以确定一个SIFT特征区域。
我们用梯度直方图来统计邻域像素的梯度方向，如下图所示：

梯度直方图的横轴代表了邻域像素的梯度方向的大小，纵轴代表了邻域像素梯度值的大小，梯度直方图的横轴的取值范围为0º~360º，每10º为一个单位，总共有36个单位。梯度方向的直方图的主峰值则代表了该特征点的主方向，如果有相当于主峰值的80%大小的其他峰值，则为关键点的辅方向。可以看出关键点的方向就由一个主峰值方向和多个次峰值方向决定。这样可以减少图像旋转对特征点的影响。

4.关键点描述子的生成

首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取$8 \times 8$的窗口。

图中左边为当前特征点的位置，每个小哥代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度峰值和方向，小箭头方向代表该像素的梯度方向，箭头长度代表了梯度模值，然后用高斯窗口对其进行加权计算。图中右边的左上角小方块由左图中左上角4个小方格组成。右图中一个关键点由$2 \times 2$共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向信息联合的思想增强了算法抗噪性的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。

在计算了前后帧图像的特征点描述子之后，我们就将两帧图像的各个scale的描述子进行匹配，匹配上即可表示两个特征点match上了。

**申明：该部分引用参考来源：SIFT特征提取分析

总结

特征检测算子不仅在SLAM中，同时在各种检测和追踪体系中都起到了很重要的作用，在所有的特征检测算子中，SIFT算是其中的经典，也是鲁棒性最好的一种，然而SIFT算子本身是有专利的，所以在下一节我们会介绍另外一种SIFT检测算子的替代算子—ORB检测算子，同时之后准备引入一些代码的编写和解析，本节结束。
顺便说一句，Rachel-Zhang真是个牛人！！