特征检测和特征提取算子

特征检测

特征检测是计算机视觉和图像处理中的一个概念。它指的是使用计算机提取图像信息，决定每个图像的点是否属于一个图像特征。特征检测的结果是把图像上的点分为不同的子集，这些子集往往属于孤立的点、连续的曲线或者连续的区域。
主要分类：边缘，角，区域，脊。

特征提取算子

一.HOG特征

1.HOG特征：

方向梯度直方图（Histogram of Oriented Gradient, HOG）特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。
Hog特征结合SVM分类器已经被广泛应用于图像识别中，尤其在行人检测中获得了极大的成功。
（1）主要思想：
在一副图像中，局部目标的表象和形状（appearance and shape）能够被梯度或边缘的方向密度分布很好地描述。（本质：梯度的统计信息，而梯度主要存在于边缘的地方）。
（2）具体的实现方法是：
首先将图像分成小的连通区域，我们把它叫细胞单元。然后采集细胞单元中各像素点的梯度的或边缘的方向直方图。最后把这些直方图组合起来就可以构成特征描述器。
（3）提高性能：
把这些局部直方图在图像的更大的范围内（我们把它叫区间或block）进行对比度归一化，所采用的方法是：先计算各直方图在这个区间（block）中的密度，然后根据这个密度对区间中的各个细胞单元做归一化。通过这个归一化后，能对光照变化和阴影获得更好的效果。
（4）优点：
与其他的特征描述方法相比，HOG有很多优点。首先，由于HOG是在图像的局部方格单元上操作，所以它对图像几何的和光学的形变都能保持很好的不变性，这两种形变只会出现在更大的空间领域上。其次，在粗的空域抽样、精细的方向抽样以及较强的局部光学归一化等条件下，只要行人大体上能够保持直立的姿势，可以容许行人有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。因此HOG特征是特别适合于做图像中的人体检测的。

2、HOG特征提取算法的实现过程：

大概过程：
HOG特征提取方法就是将一个image（你要检测的目标或者扫描窗口）：
1）灰度化（将图像看做一个x,y,z（灰度）的三维图像）；
2）采用Gamma校正法对输入图像进行颜色空间的标准化（归一化）；目的是调节图像的对比度，降低图像局部的阴影和光照变化所造成的影响，同时可以抑制噪音的干扰；
3）计算图像每个像素的梯度（包括大小和方向）；主要是为了捕获轮廓信息，同时进一步弱化光照的干扰。
4）将图像划分成小cells（例如66像素/cell）；
5）统计每个cell的梯度直方图（不同梯度的个数），即可形成每个cell的descriptor；
6）将每几个cell组成一个block（例如33个cell/block），一个block内所有cell的特征descriptor串联起来便得到该block的HOG特征descriptor。
7）将图像image内的所有block的HOG特征descriptor串联起来就可以得到该image（你要检测的目标）的HOG特征descriptor了。这个就是最终的可供分类使用的特征向量了。

3.图像的HOG特征维数

Dalal提出的Hog特征提取的过程：把样本图像分割为若干个像素的单元（cell），把梯度方向平均划分为9个区间（bin），在每个单元里面对所有像素的梯度方向在各个方向区间进行直方图统计，得到一个9维的特征向量，每相邻的4个单元构成一个块（block），把一个块内的特征向量联起来得到36维的特征向量，用块对样本图像进行扫描，扫描步长为一个单元。最后将所有块的特征串联起来，就得到了人体的特征。例如，对于64128的图像而言，每1616的像素组成一个cell，每22个cell组成一个块，因为每个cell有9个特征，所以每个块内有49=36个特征，以8个像素为步长，那么，水平方向将有7个扫描窗口，垂直方向将有15个扫描窗口。也就是说，64128的图片，总共有367*15=3780个特征。

二.SIFT特征

尺度不变特征提取(SIFT)特征

处理两幅图像之间发生平移、旋转、尺度变化、光照变化情况下的特征匹配问题，并能在一定程度上对视角变化具备较为稳定的特征匹配能力。一幅图像的SIFT特征向量的生成主要包括4步：尺度空间极值检测、关键点位置及尺度确定、关键点方向确定、特征向量生成。

SIFT特征提取的方法：

1，构建DOG尺度空间
（1）基础知识
（a）尺度空间：
在视觉信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质特征。尺度空间方法将传统的单尺度视觉信息处理技术纳入尺度不断变化的动态分析框架中，因此更容易获得图像的本质特征。尺度空间的生成目的是模拟图像数据多尺度特征。
尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。大尺度对应图像的概貌特征，小尺度对应图像的细节特征。所以对不同尺度的图像检测关键点，最终得到的sift特征点具有尺度不变性。尺度空间是客观存在的，我们使用高斯卷积的形式来表现尺度空间。
一幅二维图像的尺度空间可以定义为

其中I(x,y)是图像区域，G(x,y,σ)是尺度可变高斯函数，x,y是空间坐标，σ大小决定图像的平滑程度。

参考材料：
http://blog.csdn.net/tanxinwhu/article/details/7048370
（b）高斯模糊：
这里尺度空间的生成需要使用高斯模糊来实现，Lindeberg等人已经证明高斯卷积核是实现尺度变换的唯一线性核。高斯模糊是一种图像滤波器，它使用正态分布(高斯函数)计算模糊模板，并使用该模板与原图像做卷积运算，达到模糊图像的目的。
N维空间正态分布方程为：

其中，是正态分布的标准差，值越大，图像越模糊(平滑)。r为模糊半径，模糊半径是指模板元素到模板中心的距离。如二维模板大小为mn，则模板上的元素(x,y)对应的高斯计算公式为：

对图像做卷积运算可以看做是加权求和的过程，把使用到的图像区域中的每个元素分别与卷积核的每个对应位置的元素相乘，所有乘积之和作为区域中心的像素值。
一个5*5的高斯模板：

可以看出高斯模板是圆对称的，且卷积的结果使原始像素值有最大的权重，距离中心越远的相邻像素值权重也越小。
在实际应用中，在计算高斯函数的离散近似时，在大概3σ距离之外的像素都可以看作不起作用，这些像素的计算也就可以忽略。所以，通常程序只计算(6σ+1)(6σ+1)就可以保证相关像素影响。

参考材料：
http://www.cnblogs.com/slysky/archive/2011/11/25/2262899.html

2.关键点精确定位
以上极值点的搜索是在离散空间进行搜索的，由下图可以看到，在离散空间找到的极值点不一定是真正意义上的极值点。可以通过对尺度空间DoG函数进行曲线拟合寻找极值点来减小这种误差。

利用DoG函数在尺度空间的Taylor展开式：

则极值点为：

3，方向赋值
为了实现图像的旋转不变性，需要根据检测到的关键点的局部图像结构为特征点方向赋值。
（1）梯度直方图
方向直方图的核心是统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。
在上一步，精确定位关键点后，可以得到该特征点的尺度值σ，根据这一尺度值，得到最接近这一尺度值的高斯图像：

使用有限差分，计算以关键点为中心，以3×1.5σ为半径的区域内图像梯度的幅角和幅值，公式如下：

梯度方向直方图的横轴是梯度方向角，纵轴是剃度方向角对应的梯度幅值累加值。梯度方向直方图将0°~360°的范围分为36个柱，每10°为一个柱。

在计算直方图时，每个加入直方图的采样点都使用圆形高斯函数函数进行了加权处理，也就是进行高斯平滑。这主要是因为SIFT算法只考虑了尺度和旋转不变形，没有考虑仿射不变性。通过高斯平滑，可以使关键点附近的梯度幅值有较大权重，从而部分弥补没考虑仿射不变形产生的特征点不稳定。

这里的直方图统计，我在阅读了labelme中实现的源码之后发现具体做法是，把每个梯度向量分解到这8个方向，然后将这8个方向每个方向分到的幅值加在这个方向对应的直方图柱上。

（2）关键点方向
直方图峰值代表该关键点邻域内图像梯度的主方向，当存在另一个相当于主峰值 80%能量的峰值时，则认为这个方向是该关键点的辅方向。所以一个关键点可能检测得到多个方向，这可以增强匹配的鲁棒性。Lowe的论文指出大概有15%关键点具有多方向，但这些点对匹配的稳定性至为关键。

具有多个方向的关键点可以复制成多份，然后将方向值分别赋给复制后的关键点。

至此，我们得到了关键点的位置、尺度、方向信息（x,y,σ,θ）。h(x,y,θ)是一个三维矩阵，但通常经过矩阵压缩后用一个向量表示。

4，关键点描述子的生成
关键点描述子不但包括关键点，还包括关键点周围对其有贡献的像素点。这样可使关键点有更多的不变特性，提高目标匹配效率。在描述子采样区域时，需要考虑旋转后进行双线性插值，防止因旋转图像出现白点。同时，为了保证旋转不变性，要以特征点为中心，在附近领域内旋转θ角，然后计算采样区域的梯度直方图，形成n维SIFT特征矢量（如128-SIFT）。最后，为了去除光照变化的影响，需要对特征矢量进行归一化处理。

SIFT特征提取的优点

SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；
高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
可扩展性，可以很方便的与其他形式的特征向量进行联合；
需要较少的经验主义知识，易于开发。

SIFT特征提取的缺点

实时性不高，因为要不断地要进行下采样和插值等操作；
有时特征点较少（比如模糊图像）；
对边缘光滑的目标无法准确提取特征（比如边缘平滑的图像，检测出的特征点过少，对圆更是无能为力）。

三.SURF特征

SURF（计算量小，运算速度快，提取的特征点几乎与SIFT相同）
SIFT特征描述算子在生成特征矢量时使用的是高斯图像，而SURF特征描述算子在生成特征矢量时使用的则是积分图像。这样做的目的就是要充分利用在特征点检测时形成的中间结果（积分图像），避免在特征矢量生成时对图像进行重复运算。

参考文章：
SIFT：https://www.jianshu.com/p/d94e558ebe26
SIFT：https://blog.csdn.net/happyer88/article/details/45817305
SIFT：https://www.cnblogs.com/pacino12134/p/11368558.html
HOG：https://blog.csdn.net/a133521741/article/details/79237776