目录
这篇文章写的比较匆忙，还有很多算法没有写进去，而且也有很多算法没有写完整，大家可以先看看我下面放的参考文献，也可以先收藏我的文章，我在后续的学习中还会更新完善这篇文章。谢谢大家的支持～
(2) 而梯度可分解为 x 方向的梯度 G{x} 和 y 方向的梯度 G{y} 。
?3.cell、block、windowsSize、stride的关系。
Harris角点检测原理详解
1、算法基本思想
??????? 算法基本思想是使用一个固定窗口在图像上进行任意方向上的滑动，比较滑动前与滑动后两种情况，窗口中的像素灰度变化程度，如果存在任意方向上的滑动，都有着较大灰度变化，那么我们可以认为该窗口中存在角点。
2、用数学思想去刻画角点特征
公式解释：
>[u,v]是窗口的偏移量
>(x,y)是窗口内所对应的像素坐标位置，窗口有多大，就有多少个位置
>w(x,y)是窗口函数，最简单情形就是窗口内的所有像素所对应的w权重系数均为1。但有时候，我们会将w(x,y)函数设定为以窗口中心为原点的二元正态分布。如果窗口中心点是角点时，移动前与移动后，该点的灰度变化应该最为剧烈，所以该点权重系数可以设定大些，表示窗口移动时，该点在灰度变化贡献较大；而离窗口中心(角点)较远的点，这些点的灰度变化几近平缓，这些点的权重系数，可以设定小点，以示该点对灰度变化贡献较小，那么我们自然想到使用二元高斯函数来表示窗口函数，这里仅是个人理解，大家可以参考下。
?根据上述表达式，当窗口处在平坦区域上滑动，可以想象的到，灰度不会发生变化，那么E(u,v) = 0；如果窗口处在比纹理比较丰富的区域上滑动，那么灰度变化会很大。算法最终思想就是计算灰度发生较大变化时所对应的位置，当然这个较大是指针任意方向上的滑动，并非单指某个方向。
4.E(u,v)表达式进一步演化
?
椭圆函数特征值与图像中的角点、直线（边缘）和平面之间的关系如下图所示。共可分为三种情况：
- 图像中的直线。一个特征值大，另一个特征值小，λ1?λ2λ1?λ2或λ2?λ1λ2?λ1。自相关函数值在某一方向上大，在其他方向上小。
- 图像中的平面。两个特征值都小，且近似相等；自相关函数数值在各个方向上都小。
- 图像中的角点。两个特征值都大，且近似相等，自相关函数在所有方向都增大。
矩阵M的关键性
??????? 难道我们是直接求上述的E(u,v)值来判断角点吗？Harris角点检测并没有这样做，而是通过对窗口内的每个像素的x方向上的梯度与y方向上的梯度进行统计分析。这里以Ix和Iy为坐标轴，因此每个像素的梯度坐标可以表示成(Ix,Iy)。针对平坦区域，边缘区域以及角点区域三种情形进行分析：
下图是对这三种情况窗口中的对应像素的梯度分布进行绘制
如果使用椭圆进行数据集表示，则绘制图示如下
?
??????? 不知道大家有没有注意到这三种区域的特点，平坦区域上的每个像素点所对应的(IX,IY)坐标分布在原点附近，其实也很好理解，针对平坦区域的像素点，他们的梯度方向虽然各异，但是其幅值都不是很大，所以均聚集在原点附近；边缘区域有一坐标轴分布较散，至于是哪一个坐标上的数据分布较散不能一概而论，这要视边缘在图像上的具体位置而定，如果边缘是水平或者垂直方向，那么Iy轴方向或者Ix方向上的数据分布就比较散；角点区域的x、y方向上的梯度分布都比较散。我们是不是可以根据这些特征来判断哪些区域存在角点呢？
?????? 虽然我们利用E(u,v)来描述角点的基本思想，然而最终我们仅仅使用的是矩阵M。让我们看看矩阵M形式，是不是跟协方差矩阵形式很像，像归像，但是还是有些不同，哪儿不同？一般协方差矩阵对应维的随机变量需要减去该维随机变量的均值，但矩阵M中并没有这样做，所以在矩阵M里，我们先进行各维的均值化处理，那么各维所对应的随机变量的均值为0，协方差矩阵就大大简化了，简化的最终结果就是矩阵M，是否明白了？我们的目的是分析数据的主要成分，相信了解PCA原理的，应该都了解均值化的作用。
??????? 如果我们对协方差矩阵M进行对角化，很明显，特征值就是主分量上的方差，这点大家应该明白吧？不明白的话可以复习下PCA原理。如果存在两个主分量所对应的特征值都比较大，说明什么？ 像素点的梯度分布比较散，梯度变化程度比较大，符合角点在窗口区域的特点；如果是平坦区域，那么像素点的梯度所构成的点集比较集中在原点附近，因为窗口区域内的像素点的梯度幅值非常小，此时矩阵M的对角化的两个特征值比较小；如果是边缘区域，在计算像素点的x、y方向上的梯度时，边缘上的像素点的某个方向的梯度幅值变化比较明显，另一个方向上的梯度幅值变化较弱，其余部分的点都还是集中原点附近，这样M对角化后的两个特征值理论应该是一个比较大，一个比较小，当然对于边缘这种情况，可能是呈45°的边缘，致使计算出的特征值并不是都特别的大，总之跟含有角点的窗口的分布情况还是不同的。
因此可以得出下列结论：
>特征值都比较大时，即窗口中含有角点
>特征值一个较大，一个较小，窗口中含有边缘
>特征值都比较小，窗口处在平坦区域
Harris角点算法实现?
?
????? 其中k是常量，一般取值为0.04~0.06，这个参数仅仅是这个函数的一个系数，它的存在只是调节函数的形状而已。
?????? 但是为什么会使用这样的表达式呢？一下子是不是感觉很难理解？其实也不难理解，函数表达式一旦出来，我们就可以绘制它的图像，而这个函数图形正好满足上面几个区域的特征。 通过绘制函数图像，直观上更能理解。绘制的R函数图像如下：
?
?Harris角点的性质
由此，可以得出这样的结论：增大αα的值，将减小角点响应值RR，降低角点检测的灵性，减少被检测角点的数量；减小αα值，将增大角点响应值RR，增加角点检测的灵敏性，增加被检测角点的数量。?
2. Harris角点检测算子对亮度和对比度的变化不敏感
?????? 这是因为在进行Harris角点检测时，使用了微分算子对图像进行微分运算，而微分运算对图像密度的拉升或收缩和对亮度的抬高或下降不敏感。换言之，对亮度和对比度的仿射变换并不改变Harris响应的极值点出现的位置，但是，由于阈值的选择，可能会影响角点检测的数量。
3. Harris角点检测算子具有旋转不变性
???????? Harris角点检测算子使用的是角点附近的区域灰度二阶矩矩阵。而二阶矩矩阵可以表示成一个椭圆，椭圆的长短轴正是二阶矩矩阵特征值平方根的倒数。当特征椭圆转动时，特征值并不发生变化，所以判断角点响应值RR也不发生变化，由此说明Harris角点检测算子具有旋转不变性。
4. Harris角点检测算子不具有尺度不变性
????? 如下图所示，当右图被缩小时，在检测窗口尺寸不变的前提下，在窗口内所包含图像的内容是完全不同的。左侧的图像可能被检测为边缘或曲线，而右侧的图像则可能被检测为一个角点
参考文章：Harris角点检测原理详解_lwzkiller的专栏-CSDN博客_harris角点检测
susan角点检测算法
? ? ? ? SUSAN算法是1997年牛津大学的Smith等人提出的一种处理灰度图像的方法,它主要是用来计算图像中的角点特征。SUSAN算法选用圆形模板(如图1所示)。将位于圆形窗口模板中心等待检测的像素点称为核心点。核心点的邻域被划分为两个区域:亮度值相似于核心点亮度的区域即核值相似区(Univalue SegmentAs-similatingNueleus,USAN)和亮度值不相似于核心点亮度的区域。
??????? USAN的典型区域如图2所示。模板在图像上移动时,当圆形模板完全在背景或者目标区域时，其USAN区域最大,如图2(a)；当核心在边缘时,USAN区域减少一半,如图2(c)；当核心在角点时, USAN区域最小，如图2(d)。基于这一原理, Smith提出了最小核值相似区角点检测算法。
?SUSAN角点检测算法的具体步骤如下:
(1)在图像上放置一个37个像素的圆形模板，模板在图像上滑动，依次比较模板内各个像素点的灰度与模板核的灰度，判断是否属于USAN区域。判别函数如下：
(2)统计圆形模板中和核心点有相似亮度值的像素个数n(r0)。
其中，D(r0)是以r0为中心的圆形模板区域
(3)使用如下角点响应函数。若某个像素点的USAN值小于某一特定阈值，则该点被认为是初始角点，其中，g可以设定为USAN的最大面积的一半。
(4)对初始角点进行非极值抑制来求得最后的角点。
参考文章：https://blog.csdn.net/u013989576/article/details/49226611
LBP算法
?????? LBP（Local Binary Pattern，局部二值模式）是一种用来描述图像局部纹理特征的算子；它具有旋转不变性和灰度不变性等显著的优点。它是首先由T. Ojala, M.Pietik?inen, 和D. Harwood 在1994年提出，用于纹理特征提取。而且，提取的特征是图像的局部的纹理特征；
1、LBP特征的描述
?????? 原始的LBP算子定义为在3*3的窗口内，以窗口中心像素为阈值，将相邻的8个像素的灰度值与其进行比较，若周围像素值大于中心像素值，则该像素点的位置被标记为1，否则为0。这样，3*3邻域内的8个点经比较可产生8位二进制数（通常转换为十进制数即LBP码，共256种），即得到该窗口中心像素点的LBP值，并用这个值来反映该区域的纹理信息。如下图所示：
LBP的改进版本：
?????? 原始的LBP提出后，研究人员不断对其提出了各种改进和优化。
（1）圆形LBP算子：
??????? 基本的 LBP 算子的最大缺陷在于它只覆盖了一个固定半径范围内的小区域，这显然不能满足不同尺寸和频率纹理的需要。为了适应不同尺度的纹理特征，并达到灰度和旋转不变性的要求，Ojala 等对 LBP 算子进行了改进，将 3×3 邻域扩展到任意邻域，并用圆形邻域代替了正方形邻域，改进后的 LBP 算子允许在半径为 R 的圆形邻域内有任意多个像素点。从而得到了诸如半径为R的圆形区域内含有P个采样点的LBP算子；
（2）LBP旋转不变模式
?????? 从 LBP 的定义可以看出，LBP 算子是灰度不变的，但却不是旋转不变的。图像的旋转就会得到不同的 LBP值。
???????? Maenpaa等人又将 LBP 算子进行了扩展，提出了具有旋转不变性的 LBP 算子，即不断旋转圆形邻域得到一系列初始定义的 LBP 值，取其最小值作为该邻域的 LBP 值。
?????? 图 2.5 给出了求取旋转不变的 LBP 的过程示意图，图中算子下方的数字表示该算子对应的 LBP 值，图中所示的 8 种 LBP模式，经过旋转不变的处理，最终得到的具有旋转不变性的 LBP 值为 15。也就是说，图中的 8 种 LBP 模式对应的旋转不变的 LBP 模式都是00001111。
（3）LBP等价模式
?????? 一个LBP算子可以产生不同的二进制模式，对于半径为R的圆形区域内含有P个采样点的LBP算子将会产生P2 种模式。很显然，随着邻域集内采样点数的增加，二进制模式的种类是急剧增加的。例如：5×5邻域内20个采样点，有220＝1,048,576种二进制模式。如此多的二值模式无论对于纹理的提取还是对于纹理的识别、分类及信息的存取都是不利的。同时，过多的模式种类对于纹理的表达是不利的。例如，将LBP算子用于纹理分类或人脸识别时，常采用LBP模式的统计直方图来表达图像的信息，而较多的模式种类将使得数据量过大，且直方图过于稀疏。因此，需要对原始的LBP模式进行降维，使得数据量减少的情况下能最好的代表图像的信息。
??????? 为了解决二进制模式过多的问题，提高统计性，Ojala提出了采用一种“等价模式”（Uniform Pattern）来对LBP算子的模式种类进行降维。Ojala等认为，在实际图像中，绝大多数LBP模式最多只包含两次从1到0或从0到1的跳变。因此，Ojala将“等价模式”定义为：当某个LBP所对应的循环二进制数从0到1或从1到0最多有两次跳变时，该LBP所对应的二进制就称为一个等价模式类。如00000000（0次跳变），00000111（只含一次从0到1的跳变），10001111（先由1跳到0，再由0跳到1，共两次跳变）都是等价模式类。除等价模式类以外的模式都归为另一类，称为混合模式类，例如10010111（共四次跳变）（这是我的个人理解，不知道对不对）。
?????? 通过这样的改进，二进制模式的种类大大减少，而不会丢失任何信息。模式数量由原来的2P种减少为 P ( P-1)+2种，其中P表示邻域集内的采样点数。对于3×3邻域内8个采样点来说，二进制模式由原始的256种减少为58种，这使得特征向量的维数更少，并且可以减少高频噪声带来的影响。
2、LBP特征用于检测的原理
?????? 显而易见的是，上述提取的LBP算子在每个像素点都可以得到一个LBP“编码”，那么，对一幅图像（记录的是每个像素点的灰度值）提取其原始的LBP算子之后，得到的原始LBP特征依然是“一幅图片”（记录的是每个像素点的LBP值）。
从上图可以看出LBP对光照具有很强的鲁棒性
??????? LBP的应用中，如纹理分类、人脸分析等，一般都不将LBP图谱作为特征向量用于分类识别，而是采用LBP特征谱的统计直方图作为特征向量用于分类识别。
?????? 因为，从上面的分析我们可以看出，这个“特征”跟位置信息是紧密相关的。直接对两幅图片提取这种“特征”，并进行判别分析的话，会因为“位置没有对准”而产生很大的误差。后来，研究人员发现，可以将一幅图片划分为若干的子区域，对每个子区域内的每个像素点都提取LBP特征，然后，在每个子区域内建立LBP特征的统计直方图。如此一来，每个子区域，就可以用一个统计直方图来进行描述；整个图片就由若干个统计直方图组成；
??????? 例如：一幅100*100像素大小的图片，划分为10*10=100个子区域（可以通过多种方式来划分区域），每个子区域的大小为10*10像素；在每个子区域内的每个像素点，提取其LBP特征，然后，建立统计直方图；这样，这幅图片就有10*10个子区域，也就有了10*10个统计直方图，利用这10*10个统计直方图，就可以描述这幅图片了。之后，我们利用各种相似性度量函数，就可以判断两幅图像之间的相似性了；
3、对LBP特征向量进行提取的步骤
（1）首先将检测窗口划分为16×16的小区域（cell）；
（2）对于每个cell中的一个像素，将相邻的8个像素的灰度值与其进行比较，若周围像素值大于中心像素值，则该像素点的位置被标记为1，否则为0。这样，3*3邻域内的8个点经比较可产生8位二进制数，即得到该窗口中心像素点的LBP值；
（3）然后计算每个cell的直方图，即每个数字（假定是十进制数LBP值）出现的频率；然后对该直方图进行归一化处理。
（4）最后将得到的每个cell的统计直方图进行连接成为一个特征向量，也就是整幅图的LBP纹理特征向量；
然后便可利用SVM或者其他机器学习算法进行分类了。
Reference：
黄非非，基于 LBP 的人脸识别研究，重庆大学硕士学位论文，2009.5
https://blog.csdn.net/xidianzhimeng/article/details/19634573
HOG特征
?????? 方向梯度直方图（Histogram of Oriented Gradient, HOG）特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。Hog特征结合SVM分类器已经被广泛应用于图像识别中，尤其在行人检测中获得了极大的成功。需要提醒的是，HOG+SVM进行行人检测的方法是法国研究人员Dalal在2005的CVPR上提出的，而如今虽然有很多行人检测算法不断提出，但基本都是以HOG+SVM的思路为主。
（1）主要思想：
?????? 在一副图像中，局部目标的表象和形状（appearance and shape）能够被梯度或边缘的方向密度分布很好地描述。（本质：梯度的统计信息，而梯度主要存在于边缘的地方）。
（2）具体的实现方法是：
?????? 首先将图像分成小的连通区域，我们把它叫细胞单元。然后采集细胞单元中各像素点的梯度的或边缘的方向直方图。最后把这些直方图组合起来就可以构成特征描述器。
（3）提高性能：
?????? 把这些局部直方图在图像的更大的范围内（我们把它叫区间或block）进行对比度归一化（contrast-normalized），所采用的方法是：先计算各直方图在这个区间（block）中的密度，然后根据这个密度对区间中的各个细胞单元做归一化。通过这个归一化后，能对光照变化和阴影获得更好的效果。
（4）优点：
?????? 与其他的特征描述方法相比，HOG有很多优点。首先，由于HOG是在图像的局部方格单元上操作，所以它对图像几何的和光学的形变都能保持很好的不变性，这两种形变只会出现在更大的空间领域上。其次，在粗的空域抽样、精细的方向抽样以及较强的局部光学归一化等条件下，只要行人大体上能够保持直立的姿势，可以容许行人有一些细微的肢体动作，这些细微的动作可以被忽略而不影响检测效果。因此HOG特征是特别适合于做图像中的人体检测的。
算法流程图
HOG特征提取方法就是将一个image（你要检测的目标或者扫描窗口）：
1）灰度化（将图像看做一个x,y,z（灰度）的三维图像）；
2）采用Gamma校正法对输入图像进行颜色空间的标准化（归一化）；目的是调节图像的对比度，降低图像局部的阴影和光照变化所造成的影响，同时可以抑制噪音的干扰；
3）计算图像每个像素的梯度（包括大小和方向）；主要是为了捕获轮廓信息，同时进一步弱化光照的干扰。
4）将图像划分成小cells（例如8*8像素/cell）；
5）统计每个cell的梯度直方图（不同梯度的个数），即可形成每个cell的descriptor；
6）将每几个cell组成一个block（例如3*3个cell/block），一个block内所有cell的特征descriptor串联起来便得到该block的HOG特征descriptor。
7）将图像image内的所有block的HOG特征descriptor串联起来就可以得到该image（你要检测的目标）的HOG特征descriptor了。这个就是最终的可供分类使用的特征向量了。
具体每一步的详细过程如下：
（1）标准化gamma空间和颜色空间
???? 为了减少光照因素的影响，首先需要将整个图像进行规范化（归一化）。在图像的纹理强度中，局部的表层曝光贡献的比重较大，所以，这种压缩处理能够有效地降低图像局部的阴影和光照变化。因为颜色信息作用不大，通常先转化为灰度图；
(2) 而梯度可分解为 x 方向的梯度 G{x} 和 y 方向的梯度 G{y} 。
?????? 某个像素点的 x 方向的梯度的计算可以通过这个像素点左右两边的像素值的差值的绝对值计算出来，而 y 方向的梯度可以通过该像素点上下两边的像素值的差值的绝对值计算。而根据下面的两个公式可以计算每一个像素点的梯度方向和梯度幅值。
???? 最常用的方法是：首先用[-1,0,1]梯度算子对原图像做卷积运算，得到x方向（水平方向，以向右为正方向）的梯度分量gradscalx，然后用[1,0,-1]T梯度算子对原图像做卷积运算，得到y方向（竖直方向，以向上为正方向）的梯度分量gradscaly。然后再用以上公式计算该像素点的梯度大小和方向。
（3）为每个细胞单元构建梯度方向直方图
??????? 第三步的目的是为局部图像区域提供一个编码，同时能够保持对图像中人体对象的姿势和外观的弱敏感性。
?????? 我们将图像分成若干个“单元格cell”，例如每个cell为8*8个像素。假设我们采用9个bin的直方图来统计这8*8个像素的梯度信息。也就是将cell的梯度方向360度分成9个方向块，如图所示：例如：如果这个像素的梯度方向是20-40度，直方图第2个bin的计数就加一，这样，对cell内每个像素用梯度方向在直方图中进行加权投影（映射到固定的角度范围），就可以得到这个cell的梯度方向直方图了，就是该cell对应的9维特征向量（因为有9个bin）。
??????? 像素梯度方向用到了，那么梯度大小呢？梯度大小就是作为投影的权值的。例如说：这个像素的梯度方向是20-40度，然后它的梯度大小是2（假设啊），那么直方图第2个bin的计数就不是加一了，而是加二（假设啊）。
? ?? HOG是通过上面公式计算出来的梯度方向的角度是一个范围在0-360度的弧度值，为了计算简单，将梯度向的范围约束为0-180度，并且分割为9个方向，每个方向20度，再将约束后的角度除以20，则现在的梯度方向角度值就变为范围在[0,9)。
?细胞单元可以是矩形的（rectangular），也可以是星形的（radial）。
?3.cell、block、windowsSize、stride的关系。
??????? 上图中单个cell的为8X8个像素，把cell对应的方向直方图转换为单维向量，按规定组距对对应方向梯度个数进行编码，得到单个cell的9个特征，每个block包含2X2个cell,那么每个block包含2X2个cell也就是2X2X9=36个特征，而每个block移动（stride）这里选择overlap，就是为2分之一重叠，一个64X128大小的图像横着有15个block,坚着有7个，最后得到的特征数为36X7X15=3780维。
参考文章：https://blog.csdn.net/matt45m/article/details/85325897
????????????????? https://blog.csdn.net/zouxy09/article/details/7929348
FAST角点检测
1、在图像中任选一点p， 假定其像素（亮度）值为 Ip
2、以3为半径画圆，覆盖p点周围的16个像素，如下图所示
3、设定阈值t，如果这周围的16个像素中有连续的n个像素的像素值都小于 Ip?t或者有连续的n个像素都大于Ip+t， 那么这个点就被判断为角点。 在OpenCV的实现中n取值为12（16个像素周长的 3/4）.
4、一种更加快的改进是： 首先检测p点周围的四个点，即1， 5， 9， 12四个点中是否有三个点满足超过Ip+t， 如果不满足，则直接跳过，如果满足，则继续使用前面的算法，全部判断16个点中是否有12个满足条件。
以上算法的缺点：很可能大部分检测出来的点彼此之间相邻，我们要去除一部分这样的点。为了解决这一问题，我们采用了非极大值抑制的算法
非极大值抑制
对一个角点P建立一个3*3（或5*5，7*7）的窗口，如果该窗口内出现了另一个角点Q，则比较P与Q的大小，如果P大，则将Q点删除，如果P小，则将P点删除。
1、在速度上要比其他算法速度快很多
2、受图像噪声以及设定的阈值影响很大
3、FAST不产生多尺度特征而且FAST特征点没有方向信息，这样就会失去旋转不变性
?2、opencv-Fast角点检测算法C++版代码
#include <QCoreApplication> //该行为Qt环境使用。VS下请注释或删除该行。
#include <opencv2/opencv.hpp>
using namespace cv;
using namespace std;
//**********************************************************************************************
// 【fast角点检测算法】
//**********************************************************************************************
int main()
{
string path = "/home/jason/1.jpg"; //图片路径
cv::Mat img, gray;
img = cv::imread(path); //读取图片
cv::cvtColor(img, gray, cv::COLOR_BGR2GRAY); //转换为灰度图
std::vector<KeyPoint> kp; //特征点向量
cv::FastFeatureDetector fast(32); //FAST特征检测器， 32为阈值，阈值越大，特征点越少
fast.detect(gray, kp); //检测fast特征点
cv::drawKeypoints(img, kp, img, cv::Scalar(0, 255, 0), cv::DrawMatchesFlags::DRAW_OVER_OUTIMG); //画特征点
cv::namedWindow("img", cv::WINDOW_NORMAL);
cv::imshow("img", img);
cv::waitKey(0);
cv::imwrite("/home/jason/1.jpg", img);
return 0;
}
3、opencv-Fast角点检测算法python版代码
# -*- coding: utf-8 -*-
"""
Created on Mon Mar 13 21:06:59 2017
@author: lql0716
"""
import cv2
img = cv2.imread('D:/photo/01.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
fast = cv2.FeatureDetector_create('FAST')
kp = fast.detect(gray, None)
img2 = cv2.drawKeypoints(img, kp, (0, 0, 255))
cv2.namedWindow('img', cv2.WINDOW_NORMAL)
cv2.imshow('img', img2)
cv2.imwrite('D:/photo/01_1.jpg', img2)
cv2.waitKey(0)
SIFT算法
1、SIFT综述
??????? 尺度不变特征转换(Scale-invariant feature transform或SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所发表，2004年完善总结。
其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。
此算法有其专利，专利拥有者为英属哥伦比亚大学。
?????? 局部影像特征的描述与侦测可以帮助辨识物体，SIFT 特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用 SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。
SIFT算法的特点有：
1. SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
2. 独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
3. 多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；
4. 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
5. 可扩展性，可以很方便的与其他形式的特征向量进行联合。
SIFT算法可以解决的问题：
目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。而SIFT算法在一定程度上可解决：
1. 目标的旋转、缩放、平移（RST）
2. 图像仿射/投影变换（视点viewpoint）
3. 光照影响（illumination）
4. 目标遮挡（occlusion）
5. 杂物场景（clutter）
6. 噪声
?????? SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。
Lowe将SIFT算法分解为如下四步：
1. 尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。
2. 关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。
3. 方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。
4. 关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。
本文沿着Lowe的步骤，参考Rob Hess及Andrea Vedaldi源码，详解SIFT算法的实现过程。
2. 尺度空间
?????? 在一定的范围内，无论物体是大还是小，人眼都可以分辨出来。然而计算机要有相同的能力却不是那么的容易，在未知的场景中，计算机视觉并不能提供物体的尺度大小，其中的一种方法是把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中，要考虑的就是在图像在不同的尺度下都存在的特征点。
2.1 多分辨率图像金字塔
在早期图像的多尺度通常使用图像金字塔表示形式。图像金字塔是同一图像在不同的分辨率下得到的一组结果，其生成过程一般包括两个步骤：
- 对原始图像进行平滑
- 对处理后的图像进行降采样（通常是水平、垂直方向的1/2）
降采样后得到一系列不断尺寸缩小的图像。显然，一个传统的金字塔中，每一层的图像是其上一层图像长、高的各一半。多分辨率的图像金字塔虽然生成简单，但其本质是降采样，图像的局部特征则难以保持，也就是无法保持特征的尺度不变性。
2.2 高斯尺度空间
?????? 我们还可以通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间，使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。
我们知道图像和高斯函数进行卷积运算能够对图像进行模糊，使用不同的“高斯核”可得到不同模糊程度的图像。一副图像其高斯尺度空间可由其和不同的高斯卷积得到：
其中，𝐿(𝑥,𝑦,𝜎)是图像的高斯尺度空间。
从上式可以知道，将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。为了得到DoG图像，先要构建高斯尺度空间，而高斯的尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数𝜎进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。降采样时，金字塔上边一组图像的第一张是由其下面一组图像倒数第三张降采样得到。
易知，高斯金字塔有多组，每组又有多层。一组中的多个层之间的尺度是不一样的（也就是使用的高斯参数𝜎是不同的），相邻两层之间的尺度相差一个比例因子𝑘。如果每组有𝑆层，则𝑘=21𝑆。上一组图像的最底层图像是由下一组中尺度为2𝜎的图像进行因子为2的降采样得到的（高斯金字塔先从底层建立）。高斯金字塔构建完成后，将相邻的高斯金字塔相减就得到了DoG金字塔。
高斯金字塔的组数一般是
?
3. DoG空间极值检测
为了寻找尺度空间的极值点，每个像素点要和其图像域（同一尺度空间）和尺度域（相邻的尺度空间）的所有相邻点进行比较，当其大于（或者小于）所有相邻点时，改点就是极值点。如图所示，中间的检测点要和其所在图像的3×3
邻域8个像素点，以及其相邻的上下两层的3×3领域18个像素点，共26个像素点进行比较。
从上面的描述中可以知道，每组图像的第一层和最后一层是无法进行比较取得极值的。为了满足尺度变换的连续性，在每一组图像的顶层继续使用高斯模糊生成3幅图像，高斯金字塔每组有𝑆+3层图像，DoG金字塔的每组有𝑆+2组图像。
?
3.1 尺度变化的连续性
设𝑆=3
，也就是每组有3层，则𝑘=21𝑆=213，也就是有高斯金字塔每组有(𝑆?1)3层图像，𝐷𝑜𝐺金字塔每组有(S-2)2层图像。在DoG金字塔的第一组有两层尺度分别是𝜎,𝑘𝜎，第二组有两层的尺度分别是2𝜎,2𝑘𝜎，由于只有两项是无法比较取得极值的（只有左右两边都有值才能有极值）。由于无法比较取得极值，那么我们就需要继续对每组的图像进行高斯模糊，使得尺度形成𝜎,𝑘𝜎,𝑘2𝜎,𝑘3𝜎,𝑘4𝜎，这样就可以选择中间的三项𝑘𝜎,𝑘2𝜎,𝑘3𝜎。对应的下一组由上一组降采样得到的三项是2𝑘𝜎,2𝑘2𝜎,2𝑘3𝜎，其首项2𝑘𝜎=2?213𝜎=243𝜎，刚好与上一组的最后一项𝑘3𝜎=233𝜎的尺度连续起来。
?
?
4. 删除不好的极值点（特征点）
通过比较检测得到的DoG的局部极值点实在离散的空间搜索得到的，由于离散空间是对连续空间采样得到的结果，因此在离散空间找到的极值点不一定是真正意义上的极值点，因此要设法将不满足条件的点剔除掉。可以通过尺度空间DoG函数进行曲线拟合寻找极值点，这一步的本质是去掉DoG局部曲率非常不对称的点。
要剔除掉的不符合要求的点主要有两种：
- 低对比度的特征点
- 不稳定的边缘响应点
?
?
6. 生成特征描述
通过以上的步骤已经找到了SIFT特征点位置、尺度和方向信息，下面就需要使用一组向量来描述关键点也就是生成特征点描述子，这个描述符不只包含特征点，也含有特征点周围对其有贡献的像素点。描述子应具有较高的独立性，以保证匹配率。
特征描述符的生成大致有三个步骤：
- 校正旋转主方向，确保旋转不变性。
- 生成描述子，最终形成一个128维的特征向量
- 归一化处理，将特征向量长度进行归一化处理，进一步去除光照的影响。
为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转𝜃
（特征点的主方向）角度，即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为：
?
?7. 总结
SIFT特征以其对旋转、尺度缩放、亮度等保持不变性，是一种非常稳定的局部特征，在图像处理和计算机视觉领域有着很重要的作用，其本身也是非常复杂的，下面对其计算过程做一个粗略总结。
- DoG尺度空间的极值检测。 首先是构造DoG尺度空间，在SIFT中使用不同参数的高斯模糊来表示不同的尺度空间。而构造尺度空间是为了检测在不同尺度下都存在的特征点，特征点的检测比较常用的方法是Δ2𝐺
- （高斯拉普拉斯LoG），但是LoG的运算量是比较大的，Marr和Hidreth曾指出，可以使用DoG（差分高斯）来近似计算LoG，所以在DoG的尺度空间下检测极值点。
- 删除不稳定的极值点。主要删除两类：低对比度的极值点以及不稳定的边缘响应点。
- ** 确定特征点的主方向**。以特征点的为中心、以3×1.5𝜎
- 为半径的领域内计算各个像素点的梯度的幅角和幅值，然后使用直方图对梯度的幅角进行统计。直方图的横轴是梯度的方向，纵轴为梯度方向对应梯度幅值的累加值，直方图中最高峰所对应的方向即为特征点的方向。
- 生成特征点的描述子。 首先将坐标轴旋转为特征点的方向，以特征点为中心的16×16
- 的窗口的像素的梯度幅值和方向，将窗口内的像素分成16块，每块是其像素内8个方向的直方图统计，共可形成128维的特征向量。
?
?
?
?原文链接：https://blog.csdn.net/zddblog/article/details/7521424
SIFT python代码实现
import cv2
import numpy as np
from matplotlib import pyplot as plt
img = cv2.imread('test30.jpg')
img1 = img.copy()
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
sift = cv2.xfeatures2d.SIFT_create()
kp = sift.detect(gray, None)
cv2.drawKeypoints(gray, kp, img)
cv2.drawKeypoints(gray, kp, img1, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
plt.subplot(121), plt.imshow(img),
plt.title('Dstination'), plt.axis('off')
plt.subplot(122), plt.imshow(img1),
plt.title('Dstination'), plt.axis('off')
plt.show()