Jan 03, 2019 原创文章
特征检测与匹配 - SIFT 与 SURF
特征检测
一幅图像中总存在着其独特的像素点，这些点我们可以认为就是这幅图像的特征，成为特征点。特征检测（Feature Detection）就是指使用计算机程序提取图像信息，决定每个图像的点是否属于特征点。
在未知场景中，计算机并不能像人眼一样分别物体的大小。解决这该问题的一种方法是把物体不同尺度下的图像都提供给计算机，让计算机能对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中，要考虑的就是在图像在不同的尺度下都存在的特征点。
常用的特征检测算法有：SURF、SIFT、ORB、FAST、AKAZE 等
SIFT Scale Invariant Feature Transform
SIFT 算法由 David Lowe 在1999年所发表，2004年完善总结，专利拥有者为英属哥伦比亚大学。
SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。
Lowe将SIFT算法分解为如下四步：
查找特征点
DoG特征就是在不同参数下的高斯滤波（卷积）结果相减
高斯尺度空间
通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间。使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。
设原始图像为$I(x,y)$，其高斯尺度空间$L(x,y,\sigma)$可由其和不同的高斯卷积得到：
其中$G(x,y,\sigma)$为高斯函数：
$\sigma$称为尺度空间因子，代表了不同的空间尺度。它是高斯正态分布的标准差，反映了图像被模糊的程度，其值越大图像越模糊，对应的尺度也就越小。
LoG/DoG
构建尺度空间的目的是为了检测出在不同的尺度下都存在的特征点，而检测特征点较好的算子是 $\Delta^2G$ (Laplace of Gaussian，LoG）：
使用LoG虽然能较好的检测到图像中的特征点，但是其运算量过大，通常可使用DoG（差分高斯，Difference of Gaussina）来近似计算LoG。
设k为相邻两个高斯尺度空间的比例因子，则DoG的定义式为：
从上式可以知道，DoG函数定义为不同尺度的高斯核与图像卷积结果之差，即：将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。
因此为了得到DoG图像，先要构建高斯尺度空间，而高斯尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对 图像金字塔的每层图像 使用不同的尺度因子$\sigma$进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。
图像金字塔每一层称为一个octave（组），假设σ最终变为原来的2倍，那么相邻两层之间的k的间隔为$k = 2 ^{\frac{1}{S}}$。为了保证首位两张图也能够进行计算差值，我们需要做两张图片的Padding，图中实际的s=2, 也就是说一个octave内的总图像为s+3
高斯金字塔的组数一般是：
o 表示高斯金字塔的层数，m，n分别是图像的行和列。减去的系数a可以在0−log2min(m,n)之间的任意值，和具体需要的金字塔的顶层图像的大小有关。高斯模糊参数σ（尺度空间），可由下面关系式得到：
其中o为所在的组，s为所在的层，σ0为初始的尺度，S为每组的层数。在Lowe的算法实现中$\sigma_0=1.6,o_{min} = -1,S=3,o_{min}=-1$就是首先将原图像的长和宽各扩展一倍。从上面可以得知同一组内相邻层的图像尺度关系：
相邻组之间的尺度关系：
高斯金字塔构建成功后，将每一组相邻的两层相减就可以得到DoG金字塔。
确定特征点的位置
为了寻找尺度空间的特征点（极值点），对得到的（候选）特征点进行稳定度检测，得到特征点的尺度和位置。
DoG空间极值检测
为了寻找尺度空间的极值点，每个像素点要和其图像域（同一尺度空间）和尺度域（相邻的尺度空间）的所有相邻点进行比较，当其大于（或者小于）所有相邻点时，该点就是极值点。如图所示，中间的检测点要和其所在图像的3×3邻域8个像素点，以及其相邻的上下两层的3×3领域18个像素点，共26个像素点进行比较。
删除不好的极值点
通过比较检测得到的DoG的局部极值点是在离散空间中搜索得到的，由于 离散空间是对连续空间采样得到的结果 ，因此在离散空间找到的极值点不一定是真正意义上的极值点，因此要设法将不满足条件的点剔除掉。可以通过尺度空间DoG函数进行曲线拟合寻找极值点，这一步的本质是去掉DoG局部曲率非常不对称的点。 要剔除掉的不符合要求的点主要有两种：1、低对比度的特征点，2、不稳定的边缘响应点
确定特征点的主方向
为了实现图像特征点的旋转不变性，需要确定特征点的主方向。特征点主方向是通过计算尺度图像$L(x,y)$的梯度图，根据局部梯度方向确定的。计算过程如下：
计算以特征点为中心、以3×1.5σ为半径的局部图像变化的幅角和幅值，每个点$L(x,y)$的梯度的幅值$m(x,y)$和$θ(x,y)$可通过下式求得：
计算完成后，使用直方图统计特征点邻域内像素对应的梯度方向和幅值。梯度方向的直方图的横轴是梯度方向的角度（梯度方向的范围是0到360度，直方图每36度一个bin共10个bin，或者每45度一个bin共8个bin），纵轴是梯度方向对应梯度幅值的累加。直方图的峰值所对应的方向为特征点的主方向。
建立特征点描述子
将每个特征点周围的局部梯度作为特征点的描述子，最终构成SIFT特征向量。这个描述符不只包含特征点，也含有特征点周围对其有贡献的像素点。
特征描述符的生成大致有三个步骤：1、校正旋转主方向，确保旋转不变性。2、生成描述子，最终形成一个128维的特征向量。3、归一化处理，将特征向量长度进行归一化处理，进一步去除光照的影响。
校正旋转主方向，确保旋转不变性
为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转θ（特征点的主方向）角度，即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为：
生成描述子，最终形成一个128维的特征向量
旋转后对于每个极值点可以获得位于图像金字塔中的具体层数以及像素点位置，选取其周围16x16大小的区域作为一个Patch，将其分为4x4共计16个cell，每个cell内共有16个像素点。对于每个cell，我们计算它的局部梯度方向直方图，直方图共有8个bin，也就是说每个cell可以得到一个8维的特征向量，将16个cell的特征向量首尾相接，就得到了128维的SIFT特征向量。
归一化处理
将特征向量长度进行归一化处理，进一步去除光照的影响。
与求主方向不同，此时每个种子区域的梯度直方图在0-360之间划分为8个方向区间，每个区间为45度，即每个种子点有8个方向的梯度强度信息。在实际的计算过程中，为了增强匹配的稳健性，Lowe建议通过对特征点周围的像素进行分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。
SURF Speed Up Robust Features
Speeded Up Robust Features（SURF，加速稳健特征），是一种稳健的局部特征点检测和描述算法。最初由Herbert Bay发表在2006年的 ECCV（Europen Conference on Computer Vision）上，并在2008年正式发表在Computer Vision and Image Understanding上。
SURF算法是对David Lowe在1999年提出的SIFT算法的改进，提升了算法的执行效率，为算法在实时计算机视觉系统中应用提供了可能。
SURF 特征的具体实现流程如下：
查找特征点
Hessian Matrix
在SIFT算法中通过建立图像金字塔，在每一层进行高斯滤波并求取图像差(DOG)进行特征点提取。SURF算法则使用Hessian Matrix 进行特征点的提取。
黑塞矩阵（Hessian Matrix）是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率（可以表示二维曲面上点的不同方向变化剧烈程度）。由德国数学家Ludwin Otto Hessian于19世纪提出。
构建Hessian矩阵的目的是为了生成图像稳定的边缘点（突变点），对一个图像 f(x,y) ，其Hessian矩阵如下：
因为特征点须要具备尺度无关性，所以在构造Hessian矩阵前需要对图像进行高斯滤波。经过滤波后的Hessian矩阵表述为：
在构建多尺度空间时，SURF算法使用 Box Filter 近似代替SIFT算法中的二阶高斯函数，然后与原始图像做卷积，并在这一过程中应用了积分图（这个积分图就是计算Haar-Like特征时用到的积分图）。下图为二阶高斯滤波同盒子滤波的对比。
上边左边两幅图是9*9高斯滤波器模板分别在图像上垂直方向上二阶导数Dyy和Dxy对应的值，右边两幅图是使用盒式滤波器对其近似，对于x、y方向上的滤波，黑色区域为-2，白色区域为1，其余灰色区域为0；对于xy方向的滤波，黑色区域赋-1，白色区域1，其余灰色区域为0。
Hessian矩阵可以重新表述为：
Hessian矩阵的判别式为：
Hessian矩阵的判别式为Hessian矩阵的特征值，依据判别式取值正负，来判别该点是或不是极值点。当Hessian矩阵的判别式取得局部极大值时，判定当前点是比周围邻域内其他点更亮或更暗的点，由此来确定特征点的位置。
使用Box Filter，Hessian矩阵的判别式可近似为：
其中w取0.9是作者提出的一个经验值，用来平衡因使用盒式滤波器近似所带来的误差。
SURF特征检测算法中，利用 Box Filter 结合积分图求取尺度空间函数的方法非常巧妙，这也正是该算法比SIFT检测算法更快速的主要原因。
构建尺度空间
由于采用了盒子滤波和积分图像，SURF算法并不需要像SIFT算法那样去直接建立图像金字塔，而是采用不断增大盒子滤波模板的尺寸的间接方法，通过不同尺寸盒子滤波模板与积分图像求取Hessian矩阵行列式的响应图像。然后在响应图像上采用3D非最大值抑制，求取各种不同尺度的特征点。
在SIFT算法中，保持fiter不变，不断增大高斯模糊系数构建尺度空间（相当于一个下采样的过程）。SURF算法中，保持图像大小不变，通过不断增大filter的尺寸，构建尺度空间（相当于一个上采样的过程）。
确定特征点的位置
在SURF特征中，将经过Hessian矩阵处理的每个像素点与二维图像空间和尺度空间邻域内的26个点进行比较，初步定位出关键点，再经过滤除能量比较弱的关键点以及错误定位的关键点，筛选出最终的稳定的特征点。
确定特征点的主方向
在SURF算法中，采用统计特征点圆形邻域内不同方向bin中的的Harr小波特征响应的最大值确定特征点的主方向。即在特征点的圆形邻域内，统计60度扇形内所有点的水平、垂直Harr小波特征总和，然后扇形以0.2弧度大小的间隔进行旋转并再次统计该区域内Harr小波特征值之后，最后将值最大的那个扇形的方向作为该特征点的主方向。
建立特征点描述子
在SURF算法中，沿着特征点的主方向选取特征点周围的4×4个矩形区域块，每个矩形区域统计25个像素的水平方向和垂直方向的Haar小波特征（这里的水平和垂直方向都是相对主方向而言的）。该Haar小波特征为水平方向值之后、垂直方向值之后、水平方向绝对值之后以及垂直方向绝对值之和4个方向。把这4个值作为每个子块区域的特征向量，所以一共有4×4×4=64维向量作为SURF特征的描述子。
