图像特征

一、SIFT

尺度不变特征转换即SIFT (Scale-invariant feature transform)
它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量
SIFT特征的信息量大，适合在海量数据库中快速准确匹配。
SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等

figure 1

特征点及描述子提取流程

1、构建图像高斯金字塔(Gaussian Pyramid)，通过高斯函数对图像进行模糊及降采样处理，每一个金字塔由几层构成，每一层的高斯模糊程度不同，上面塔的第0层由下面塔的第3层downsample得到。(figure 1) --> 尺度不变

根据3σ原则，使用NxN的模板在图像每一个像素点处操作，N=[（6σ+1）]且向上取最邻近奇数。直接与图像卷积，速度比较慢，图像边缘信息损失严重。可以使用分离的高斯卷积（先用1xN的模板沿着X方向对图像卷积一次，然后用Nx1的模板沿着Y方向对图像再卷积一次，N=[（6σ+1）]且向上取最邻近奇数），省时，减小直接卷积对图像边缘信息的严重损失。

2、构建DOG(Difference of Gaussian)空间，差分金字塔是在高斯金字塔基础上建立：高斯金子塔每组中相邻两层相减（下一层减上一层）生成高斯差分金字塔。(figure 2)

figure 2

3、计算极值点，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，该点是图像在该尺度一个特征点。(figure 3)

figure 3

4、精确确定极值点位置，离散空间极值点并不是真正的极值点，(figure 4)显示二维函数离散空间得到的极值点与连续空间极值点的差别。利用已知的离散空间点插值得到的连续空间极值点的方法叫做子像素插值。(Taylor展开，拟和三维二次函数)
过小的点易受噪声干扰，不稳定，将小于某个经验值(0.03，0.04/S)的极值点删除。(去除低对比度的关键点)
此过程获取特征点的精确位置(原位置加上拟合的偏移量)以及尺度(σ)。

figure 4

5、去除边缘响应
不好的高斯差分算子极值在横跨边缘的地方有较大主曲率，在垂直边缘的方向有较小主曲率。DOG算子会产生较强的边缘响应，需要剔除不稳定边缘响应点。获取特征点处Hessian矩阵，主曲率通过一个2x2 的Hessian矩阵H求出（D的主曲率和H的特征值成正比）。
增强匹配稳定性、提高抗噪声能力。以下公式是是否剔除边缘响应点的条件，不满足条件的点剔除。r=10

6、确定特征的方向，每个特征点计算一个方向，依照这个方向做进一步计算， 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。
下图公式为(x,y)处梯度模值和方向公式。L所用的尺度为每个关键点各自所在的尺度。
每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。
梯度直方图的范围是0～360度，每10度一个柱，共36个柱。
计算时，以关键点为中心的邻域窗口内采样，用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，每45度一个柱，共8个柱, 或每10度一个柱，共36个柱。随距中心点越远的领域对直方图贡献响应减小(高斯函数对直方图平滑，减少突变的影响)。直方图的峰值代表该关键点处邻域梯度的主方向，即该关键点的方向。

7、特征描述子生成，将坐标轴旋转为关键点的方向，确保旋转不变性。以关键点为中心取8×8的窗口。

图左中央为关键点位置，每小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表像素的梯度方向，箭头长度代表梯度模值，用高斯窗口对其进行加权运算。蓝色圈代表高斯加权范围（越靠近关键点的像素梯度方向信息贡献越大）。在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，形成一个种子点，如图右。图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声能力，对于含有定位误差的特征匹配提供较好的容错性。
实验表明：下图448=128维的描述子综合效果最好，之后将向量归一化，保证光照不变性

8、Match，提取A、B两幅图描述子，将两图各个scale（所有scale）的描述子进行匹配，匹配上128维即表示两个特征点match。匹配时，欧式距离作为关键点的相似性判定度量。取图像A中某个关键点，找出其与图像B中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，接受这对匹配点。降低比例阈值，SIFT匹配点数目减少，更加稳定，排除因图像遮挡和背景混乱产生的无匹配关系的关键点。对于错误匹配，由于特征空间的高维性，相似的距离可能有大量其他的错误匹配，从而它的ratio值比较高。
ratio=0. 4　对于准确度要求高的匹配；
ratio=0. 6　对于匹配点数目要求比较多的匹配；
ratio=0. 5　一般情况下。
最近邻距离 < 200 ==> ratio = 0. 6，反之ratio = 0. 4。ratio取值策略能排除错误匹配点。

总结特征点提取过程：

图像去噪(模糊) --> 构建高斯金字塔 --> 构建高斯差分金字塔 --> 提取空间极值点 --> 获取主梯度方向

二、SURF

SIFT实时性相对不高
SURF(Speeded Up Robust Features)改进了特征提取和描述方式，用一种更为高效的方式完成特征点的提取和描述。
SURF算法采用快速Hessian算法检测关键点，SURF算子通过一个特征向量来描述关键点周围区域情况。与SIFT算法相似，SIFT算法分别采用DoG和SIFT算子检测关键点和提取关键点的描述符。

SURF特征检测的步骤：

1、构建Hessian矩阵：构建Hessian矩阵的过程对应SIFT算法中的DoG过程。

对于图像f(x, y)，Hessian矩阵如下：

H矩阵行列式值判断点(x,y)是否是极值点：

在构建Hessian矩阵前需要对图像进行高斯滤波，因为高斯核可以构造出不同尺度下的响应图像，在尺度σ下，点 X=(x,y) 处，对应的Hessian矩阵表达式为：

Lxx是标准高斯函数g(x,y,σ)的二阶偏导数与图像在点（x,y）处卷积的结果

由于高斯核是服从正态分布的，从中心点往外，系数越来越低，为了提高运算速度，Surf使用了盒式滤波器来近似替代高斯滤波器，提高运算速度。
盒式滤波器（Boxfilter）对图像的滤波转化成计算图像上不同区域间像素和的加减运算问题，只需要简单几次查找积分图就可以完成。

如上图，图1是y方向的二阶高斯微分模板，图3采用盒子滤波器对其进行近似，数字表示对应颜色区域的权值，灰色区域权值为0，采用盒子滤波器与图像卷积的结果记为Dxx，Dyy，Dxy。因为盒子滤波器在积分图像上更快。

由于对原Hessian矩阵近似，相关推导采用以下公式更接近真实值。不同的尺度下，对应的值(0.9）不同，为了统一，计算盒子滤波响应时，对模板盒子进行归一化处理。

2、构造金字塔尺度空间（主要加速）

SIFT：原始图像作为最底层，对图像高斯模糊再降采样（2倍）作为下一组图像，循环迭代。高斯金字塔是对原图像的尺寸是不断变化，高斯模板尺寸不变。
缺点：每组建立必须等到上一层构造完后才能进行，依赖性强，速度慢
SURF：不同组间原图像大小不变，不同组间盒式滤波器模板尺寸逐渐增大，同一组不同层间使用相同尺寸滤波器，但滤波器模糊系数逐渐增大。
优势：SURF可以并行运算，对金字塔中的每层图像同时处理。通过逐渐盒式滤波器模板尺寸与积分图像卷积产生Hessian矩阵行列式的响应图像，构造出金字塔。

3、特征点定位
特征点的定位过程Surf和Sift保持一致，将经过Hessian矩阵处理的每个像素点((即获得每个像素点Hessian矩阵的判别式值))与二维图像空间和尺度空间邻域内的26个点进行比较，初步定位出关键点，再经过滤除能量比较弱的关键点以及错误定位的关键点，筛选出最终的稳定的特征点。
Hessian阈值设置为20000，阈值越高，能识别的特征就越少

4、计算特征点主方向
SIFT算法特征点主方向是采用在特征点邻域内统计其梯度直方图
SURF算法，统计特征点圆形邻域内Harr小波特征，在特征点的圆形邻域内，统计60度扇形内所有点的水平、垂直Harr小波特征总和，然后扇形以0.2弧度大小的间隔进行旋转并再次统计该区域内Harr小波特征值，最后将值最大的扇形的方向作为该特征点的主方向：

5、生成特征描述
SIFT算法：先以特征点为中心，在附近邻域内将坐标轴旋转θ（特征点的主方向、旋转不变性）角度，然后提取特征点周围4×4个区域块，统计每小块内8个梯度方向，一个关键点产生128维的SIFT特征向量。
SURF算法：提取特征点周围4×4个矩形区域块，矩形区域方向是沿着特征点的主方向，不是像SIFT算法旋转θ角度。每个子区域统计25个像素点水平方向和垂直方向的Haar小波特征，水平和垂直方向都是相对主方向。Harr小波特征为水平方向值之和、垂直方向值之和、水平方向值绝对值之和以及垂直方向绝对之和4个方向。把这4个值作为每个子块区域的特征向量，一共4×4×4=64维向量作为SURF特征的描述子，比SIFT特征的描述子减少一半。