????????SIFT算法用于检测特征点，SIFT算法对旋转、尺度缩放、亮度变化等保持不变性，对视角变换、仿射变化、噪声也保持一定程度的稳定性，是一种非常优秀的局部特征描述算法。但是其实时性相对不高。SURF(Speeded Up Robust Features)算法改进了特征了提取和描述方式，用一种更为高效的方式完成特征点的提取和描述。

SURF算法原理

SURF特征检测的步骤

尺度空间的极值检测：搜索所有尺度空间上的图像，通过Hessian来识别潜在的对尺度和选择不变的兴趣点。
?特征点过滤并进行精确定位。
特征方向赋值：统计特征点圆形邻域内的Harr小波特征。即在60度扇形内，每次将60度扇形区域旋转0.2弧度进行统计，将值最大的那个扇形的方向作为该特征点的主方向。
?特征点描述：沿着特征点主方向周围的邻域内，取4×4个矩形小区域，统计每个小区域的Haar特征，然后每个区域得到一个4维的特征向量。一个特征点共有64维的特征向量作为SURF特征的描述子。

构建Hessian

????????构建Hessian矩阵的目的是为了生成图像稳定的边缘点(突变点)，跟Canny、拉普拉斯边缘检测的作用类似，为特征提取做准备。构建Hessian矩阵的过程对应着SIFT算法中的DoG过程。

????????黑塞矩阵(Hessian Matrix)是由一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率。由德国数学家Ludwin Otto Hessian于19世纪提出。

????????对于一个图像I(x,y)，其Hessian矩阵如下：

????????H矩阵的判别式是：?

?????????在构建Hessian矩阵前需要对图像进行高斯滤波，经过滤波后的Hessian矩阵表达式为：

?????????

????????其中(x,y)为像素位置, L(x,y,σ)=G(σ)?I(x,y),代表着图像的高斯尺度空间，是由图像和不同的高斯卷积得到。

????????我们知道在离散数学图像中，一阶导数是相邻像素的灰度差：

????????二阶导数是对一阶导数的再次求导：

?????????

????????反过来看Hessian矩阵的判别式，其实就是当前点对水平方向二阶偏导数乘以垂直方向二阶偏导数再减去当前水平、垂直二阶偏导的二次方：

????????通过这种方法可以为图像中每个像素计算出其H行列式的决定值，并用这个值来判别图像局部特征点。Hession矩阵判别式中的L(x,y)是原始图像的高斯卷积，由于高斯核服从正太分布，从中心点往外，系数越来越小，为了提高运算速度，SURF算法使用了盒式滤波器来替代高斯滤波器L，所以在Lxy上乘了一个加权系数0.9，目的是为了平衡因使用盒式滤波器近似所带来的误差，则H矩阵判别式可表示为：

????????盒式滤波器和高斯滤波器的示意图如下：

????????上面两幅图是9×9高斯滤波器模板分别在图像垂直方向上二阶导数Lyy和Lxy对应的值，下边两幅图是使用盒式滤波器对其近似，灰色部分的像素值为0，黑色为-2，白色为1。

????????那么为什么盒式滤波器可以提高运算速度呢？这就涉及到积分图的使用，盒式滤波器对图像的滤波转化成计算图像上不同区域间像素的加减运算问题，这正是积分图的强项，只需要简单积分查找积分图就可以完成。

构造尺度空间

????????同SIFT算法一样，SURF算法的尺度空间由O组S层组成，不同的是,SIFT算法下一组图像的长宽均是上一组的一半，同一组不同层图像之间尺寸一样，但是所使用的尺度空间因子(高斯模糊系数σ)逐渐增大；而在SURF算法中，不同组间图像的尺寸都是一致的，不同的是不同组间使用的盒式滤波器的模板尺寸逐渐增大，同一组不同层图像使用相同尺寸的滤波器，但是滤波器的尺度空间因子逐渐增大。如下图所示：?

特征点过滤并进行精确定位

????????SURF特征点的定位过程和SIFT算法一致，将经过Hessian矩阵处理的每个像素点(即获得每个像素点Hessian矩阵的判别式值)与其图像域（相同大小的图像）和尺度域（相邻的尺度空间）的所有相邻点进行比较，当其大于（或者小于）所有相邻点时，该点就是极值点。如图所示，中间的检测点要和其所在图像的3×3邻域8个像素点，以及其相邻的上下两层3×3邻域18个像素点，共26个像素点进行比较。

????????初步定位出特征点后，再经过滤除能量比较弱的关键点以及错误定位的关键点，筛选出最终的稳定的特征点：

计算特征点主方向

????????SIFT算法特征点的主方向是采用在特征点邻域内统计其梯度直方图，横轴是梯度方向的角度，纵轴是梯度方向对应梯度幅值的累加，取直方图bin最大的以及超过最大80%的那些方向作为特征点的主方向。

????????而在SURF算法中，采用的是统计特征点圆形邻域内的Harr小波特征，即在特征点的圆形邻域内，统计60度扇形内所有点的水平、垂直Harr小波特征总和，然后扇形以0.2弧度大小的间隔进行旋转并再次统计该区域内Harr小波特征值之后，最后将值最大的那个扇形的方向作为该特征点的主方向。该过程示意图如下：

生成特征描述

????????在SIFT算法中，为了保证特征矢量的旋转不变性，先以特征点为中心，在附近邻域内将坐标轴旋转θ（特征点的主方向）角度，然后提取特征点周围4×4个区域块，统计每小块内8个梯度方向，这样一个关键点就可以产生128维的SIFT特征向量。

????????SURF算法中，也是提取特征点周围4×4个矩形区域块，但是所取得矩形区域方向是沿着特征点的主方向，而不是像SIFT算法一样，经过旋转θθ角度。每个子区域统计25个像素点水平方向和垂直方向的Haar小波特征，这里的水平和垂直方向都是相对主方向而言的。该Harr小波特征为水平方向值之和、垂直方向值之和、水平方向值绝对值之和以及垂直方向绝对之和4个方向。该过程示意图如下：

????????把这4个值作为每个子块区域的特征向量，所以一共有4×4×4=64维向量作为SURF特征的描述子，比SIFT特征的描述子减少了一半。

BRIEF和SIFT、SURF对比：?

?????????SIFT算法以及SURF算法由于受到了专利的保护，在高版本的OpenCV中是没法使用的，BRIEF算法简单还免费。

BRIEF算法原理

????????在SIFT算法使用128维的描述符，因为使用float类型描述，所以需要512字节的内存。

????????在SURF算法中，以64维描述符来计算，至少需要256字节的内存。

????????在创建一个含有数千个特征的向量会消耗大量的内存，这种情况在资源的有限的设备上不实用，尤其是嵌入式设备。?此外，它们计算时间也非常漫长。

????????但是在实际的匹配过程中，不是所有的维数都需要。我们可以使用一些方法来对维数进行压缩，例如PCA（主成分分析）算法，和LDA（线性判别式分析）算法等等。甚至使用LSH（局部敏感哈希）算法，把SIFT的描述符从浮点数类型转化成二进制字符串，然后对这些字符串使用汉明距离来进行匹配。由于韩明距离的计算方法只需要使用亦或位运算和位计数，在带有SSE指令的现代的CPU上计算速度很快。

????????BRIEF算法由此产生，该算法提供了一个很简介的手段在不寻找描述符的情况下，去寻找二进制字符串。

大致过程如下：

为减少噪声干扰，先对图像进行高斯滤波（方差为2，高斯窗口为9x9）
以特征点为中心，取SxS的邻域大窗口。在大窗口中随机选取一对（两个）5x5的子窗口，比较子窗口内的像素和（可用积分图像完成），进行二进制赋值.（一般S=31），其中，p(x)，p(y)分别随机点x=(u1,v1),y=(u2,v2)所在5x5子窗口的像素和.
在大窗口中随机选取N对子窗口，重复步骤2的二进制赋值，形成一个二进制编码，这个编码就是对特征点的描述，即特征描述子.（一般N=256）

????????非常重要的一点是：BRIEF?是一种特征描述符，它不提供查找特征的方法。所以我们不得不使用其他特征检测器，比如?SIFT?和?SURF?等。原始文献推荐使用?CenSurE?特征检测器，这种算法很快。而且?BRIEF?算法对?CenSurE关键点的描述效果要比?SURF?关键点的描述更好。
简单来说?BRIEF?是一种对特征点描述符计算和匹配的快速方法。这种算法可以实现很高的识别率，除非出现平面内的大旋转。?

????????BRIEF虽然免费，不过由于其本身并不具有特征检测的功能，并且BRIEF的描述符在旋转的图像下表现很差劲。

?ORB算法

ORB算法和SIFT、SURF算法关系：

????????ORB是2011年ICCV上作者Rublee所提出，主要针对目前主流的SIFT或者SURF等算法的实时性进行改进。当然在实时性大为提升的基础上，匹配性能也在一定程度较SIFT与SURF算法降低。但是，在图像Two Views匹配对之间变换关系较小时，能够匹配性能逼近SIFT算法，同时计算耗时极大降低。ORB算法实时性在移动端设备上提供很好的应用，当下比较流行SLAM中采用较多的ORB-SLAM算法主要就是青睐于ORB算法实时性同时匹配精度并不差。

论文对ORB算法主要贡献如下：

在FAST角点算子快速提取角点基础上，添加主方向信息。
通过方向BRIEF描述算子高效计算FAST角点提取的特征点描述符。
分析方向BRIEF描述符的方差与相关性。
提出一种在旋转不变情况下去除相关性的BRIEF描述子的学习方式，在最近邻应用中获得更好的效果。

????????ORB特征通过增加了FAST检测子所没有的方向性，利用计算速度特快的描述子BRIEF，这就使得提取图像特征时速度加快了很多。在以往提取一帧图像特征点的实验中，在提取相同数量的特征点情况下，提取SURF点耗时时间大约是提取ORB特征点的14倍，而提取SIFT点耗时更大，大概比提取ORB特征点多三百多倍。由此可知提取ORB特征点比提取SIFT, SURF特征点所需要的计算量小得多。所以对于需要实时运行视觉SLAM算法的系统，其前端提取ORB特征点比较合适，且ORB特征点具有两个特性:一是尺度不变，二是旋转不变性。

????????下面几种特征点检测的效果图：

????????现在我们来进行原理解读。

原理：

????????ORB?是?Oriented Fast and Rotated Brief?的简称，可以用来对图像中的关键点快速创建特征向量，这些特征向量可以用来识别图像中的对象。
其中，Fast?和?Brief?分别是特征检测算法和向量创建算法。ORB?首先会从图像中查找特殊区域，称为关键点。关键点即图像中突出的小区域，比如角点，比如它们具有像素值急剧的从浅色变为深色的特征。然后?ORB?会为每个关键点计算相应的特征向量。ORB?算法创建的特征向量只包含?1?和?0，称为二元特征向量。1?和?0?的顺序会根据特定关键点和其周围的像素区域而变化。该向量表示关键点周围的强度模式，因此多个特征向量可以用来识别更大的区域，甚至图像中的特定对象。
????????ORB?的特点是速度超快，而且在一定程度上不受噪点和图像变换的影响，例如旋转和缩放变换等。

FAST?算法

????????ORB?特征检测的第一步是查找图像中的关键点，而关键点检测算法即使用?FAST?算法。

FAST?是?Features from Accelerated Segments Test?的简称，可以快速选择关键点，算法步骤如下：

????????给与一个像素点?p，FAST?比较目标?p?圆圈范围中的?16?个像素，每个像素按高于?p，小于?p，或者与?p?相似，分为三类。

????????注意这里的比较是带有阈值?h?的。对于给定的阈值?h，更亮的像素将是亮度超过?Ip+h?的像素，更暗的像素将是亮度低于?Ip-h?的像素，相似像素将是亮度在这两个值之间的像素。在对像素分类后，?如果圈圈上有?8?个以上的相连像素，暗于或亮于?p?则将像素?p?选作关键点。

????????而?FAST?如此高效的原因是，仅将?p?与圆圈中的?4?个等距像素相比。这种方法已经证明和比较?16?个周围像素的效果相同。如果至少有一对连续像素的亮度高于或低于?p，则将?p?选作关键点。这种优化使得在整个图像中搜索关键点的时间缩短了四倍。

????????但是，这些关键点可以像我们提供什么样的信息？对比邻近像素的亮度有何意义？首先观察一下 FAST 算法标记关键点的图像：

????????可以看出关键点位于亮度有变化的区域，此类区域通常确定了某种边缘，例如猫的爪子。边缘定义了猫的界限，以及脸部区域的界限，因此这些关键点使我们能够识别这只猫，而不是图像中的任何其他对象或背景。

????????第二个则为BRIEF算法，我们在上一节已经讲过，这里就不在赘述了。

缩放不变性和旋转不变性

????????ORB?使用?FAST?检测图像中的关键点，并且通过额外的几个步骤确保无论对象的大小或位置如何都能检测到图像中的对象。

????????给定一个图像?ORB?算法首先开始构建图像金字塔。

????????图像金字塔是单个图像的多尺度表示法，由一系列原始图像的不同分辨率版本组成。金字塔的每个级别都由上个级别的图像下采样版本组成。下采样是指图像分辨率被降低，比如图像按照?1/2?比例下采样。因此一开始的?4x4?正方形区域现在变成?2x2?正方形。图像的下采样包含更少的像素，并且以?1/2?的比例降低大小。?

????????这是一个包含?5?个级别的图形金字塔示例，在每个级别图像都以?1/2?的比例下采样。到了第四级别图像的分辨率是原始图像的?1/16。ORB?创建好图像金字塔后，它会使用?FAST?算法从每个级别不同大小的图像中快速找到关键点。因为金字塔的每个级别由原始图像的更小版本组成，因此原始图像中的任何对象在金字塔的每个级别也会降低大小。
????????通过确定每个级别的关键点?ORB?能够有效发现不同尺寸的对象的关键点，这样的话?ORB?实现了部分缩放不变性。这一点很重要，因为对象不太可能在每个图像中的大小都完全一样，尤其是像猫这样的对象某个时刻可能靠近相机，在另一个时刻离相机很远。

????????例如朝左或朝右，取决于该关键点周围的强度是如何变化的。
????????我们详细了解下背后原理。ORB?首先选择金字塔Level 0?中的图像，对于该图像?ORB?将计算关键点的方向。

????????方法是首先计算以该关键点为中心的方框中的强度形心。强度形心可以看做给定?patch?中的平均像素强度的位置。计算强度形心后，通过画一条从关键点到强度形心的向量，获得该关键点的方向，如上图所示。这个关键点的方向是向下并朝左，因为这个区域的亮度朝着这个方向增强。
为金字塔级别?0?的图像中的每个关键点分配方向后，ORB?现在为所有其他金字塔级别的图像重复相同流程。需要注意的是，在每个图像金字塔级别，Patch?大小并没有缩减，因此相同?Patch?在每个金字塔级别覆盖的图像区域将更大，导致关键点的大小各不相同。

????????可以从此处看出这一点。在此图中，圆圈表示每个关键点的大小，更高的金字塔级别中的关键点大小更大。
????????找到关键点并为其分配方向后，ORB?现在使用修改后的?BRIEF?版本创建特征向量，这个修改后的?BRIEF?版本称为?rBRIEF，即?Rotation-Aware BRIEF。无论对象的方向如何，它都可以为关键点创建相同的向量，使得?ORB?算法具有旋转不变性，意味着它可以在朝着任何角度旋转的图像中检测到相同的关键点。和?BRIEF?一样?rBRIEF?首先在给定关键点周围的已界定?patch?中随机选择?256?个像素对，以构建?256?位向量。然后根据关键点的方向角度旋转这些随机像素对，使随机点的方向与关键点的一致。最后, rBRIEF?对比随机像素对的亮度并相应地分配?1?和?0?创建对应的特征向量，为图像中的所有关键点创建的所有特征向量集合称之为?ORB?描述符。

再次详细看下FAST算法：?

? ? ? ? 之前几个特征检测器从实时的角度来说，它们的速度还不够快，FAST（加速段测试的特征）算法是一个解决方案。

????????FAST?全称?Features from accelerated segment test,一种用于角点检测的算法，该算法的原理是取图像中检测点，以该点为圆心的周围的16个像素点判断检测点是否为角点，通俗的讲就是中心的的像素值比大部分周围的像素值要亮一个阈值或者暗一个阈值则为角点：

实现步骤：

一个以像素p为中心，半径为3的圆上，有16个像素点（p1、p2、...、p16）
定义一个阈值，计算p1、p9与中心p的像素差，若它们绝对值都小于阈值，则p点不可能是特征点，直接pass掉，否则，当做候选点
若p是候选点，则计算p1、p9、p5、p13与中心p的像素差，若它们的绝对值有至少3个超过阈值，则当做候选点，否则，直接pass掉
若p是候选点，则计算p1到p16这16个点与中心p的像素差，若它们有至少9个超过阈值，则是特征点，否则，直接pass掉
对图像进行非极大值抑制：计算特征点出的FAST得分值（即score值，也即s值），判断以特征点p为中心的一个邻域（如3x3或5x5）内，计算若有多个特征点，则判断每个特征点的s值（16个点与中心差值的绝对值总和），若p是邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点（角点），则保留，得分计算公式如下（公式中用V表示得分，t表示阈值）：