基于特征的图像匹配方法笔记

关键词：

1. 基于特征点的图像匹配算法：Harris、SUSAN、SIFT、SURF、FAST、BRIEF、ORB、BRISK、FREAK、AGAST、KAZE、AKAZE
2. 改进SIFT：SSIFT、PCA_SIFT、CSIFT
3. 消除错误关键点：RANSAC、PROSAC、MLESAC、NAPSAC、GASAC、VFC
4. GPU加速：CuML

背景：

图像特征匹配（1）——问题定义&研究背景与意义

图像特征匹配（2）——研究现状及发展趋势

[toc]

问题的定义

图像匹配主要包含匹配目标和匹配准则两个部分，即以什么信息为目标载体和以何种规则或策略进行匹配。最直接的匹配目标便是整张图像或以截取的图像块（Image Patch），一般被称为基于区域 （Area-Based）的方法，其主要分为两种：i）直接根据图像或图像块灰度信息进行像素上的对齐，该方法主要思想是直接最小化图像信息差异，一般包括交叉相关法（或互相关法），相关系数度量法，互信息法等；ii）基于图像域变换的图像匹配，其先将图像信息进行域变换，然后在变换域中对图像进行相似性匹配，包括傅里叶变换法， 相位相关法，沃尔什变换法等。基于区域的图像匹配方法对成像条件、图像形变（特别是要求图像对具有极高的重叠度）以及噪声极其敏感，同时具有较高的计算复杂度，从而限制了其应用能力。

为解决上述问题，基于特征（Feature-Based）的图像匹配方法得到了广泛研究。其首先从图像中提取的具有物理意义的显著结构特征，包括特征点、特征线或边缘以及具有显著性的形态区域，然后对所提取的特征结构进行匹配并估计变换函数将其他图像内容进行对齐。尽管特征的提取需要额外的算力消耗，但针对整个基于特征的匹配框架而言，由于特征可以看做整张图像的精简表达，减少了许多不必要的计算，同时能够减少噪声、畸变及其他因素对匹配性能的影响，是目前实现图像匹配的主要形式。

对于特征而言，点特征通常表示图像中具有显著特性的关键点（Key Point）或兴趣点（Interest Point） [19]，因而最为简单且稳定，同时其他特征的匹配均可转化为基 于点特征来进行，如线的端点、中点、或离散采样形式，形态区域中心等。因此，特征点匹配在图像匹配中是一个最为基本的问题，而我们所说的特征匹配（Feature Matching）通常意义上指基于特征点的匹配问题，待匹配的点一般由图像像素空间的坐标点表示，而相应的图像匹配则转化为从两幅图像中提取对应的点集并配对的问题。

在图像处理领域中，特征点又被称为兴趣点或者角点，它通常具有旋转不变性和光照不变性和视角不变性等优点，是图像的重要特征之一，寻找同一场景或物体的两幅图像之间的点对应关系是许多计算机视觉应用的一部分，常被应用到目标匹配、目标跟踪、三维重建等应用中。点特征主要指图像中的明显点，如突出的角点、边缘端点、极值点等等，用于点特征提取的算子称为兴趣点提取（检测）算子，常用的有Harris角点检测、SIFT特征检测、FAST特征检测及SURF特征检测等。

离散图像点对应的搜索可分为三个主要步骤。首先，在图像中的不同位置选择“兴趣点”，例如角点、斑点和T形交叉点。兴趣点检测器最有价值的特性是其可重复性。重复性表示探测器在不同观察条件下寻找相同物理兴趣点的可靠性。然后，用特征向量表示每个兴趣点的邻域。该描述符必须是独特的，同时对噪声、检测位移、几何和光度变形具有鲁棒性。最后，在不同的图像之间匹配描述符向量。匹配基于向量之间的距离，例如马氏距离或欧氏距离。描述符的维数直接影响到匹配所需的时间，对于快速兴趣点匹配，需要更小的维数。然而，低维特征向量通常没有高维特征向量那么独特。

背景及意义

如何理解多个视觉目标之间的区别与联系，并根据特定的需求对感知的信息作相应的处理已然成为整个计算机视觉领域的研究热点之一，而特征匹配作为其中的一个基础而关键的过程，连接着具有相同或相似属性的两个图像目标，是低层视觉通往高层视觉的纽带，是实现信息识别与整合以及从低维图像恢复高维结构的有效途径。

特征匹配的定义和任务目标极为简单且明确，它是一项底层视觉处理技术，直接对图像本身进行特征提取与配对，是许多具体大型视觉任务的首要步骤。据美国自动 成像协会（Automated Imaging Association）统计，40% 以上的视觉感知应用依赖于图像匹配的精度与效率，包括计算机视觉、模式识别、遥感、军事安防以及医学诊断等各领域。具体来讲，根据数据获取条件或者成像条件的差异，特征匹配问题可以划分 为不同时间、不同视角以及不同传感器，或者进行模板图像的匹配，并且每一类 型的图像获取形式都有着对应的应用目的：1）基于不同成像时间的特征匹配。主要是对同一场景或目标在不同时间拍摄的图像进行匹配，一般用于场景的变化检测，安防监控与目标跟踪，以及医学诊断治疗中病情跟踪等。2）基于不同视角的特征匹配。其主要目的是匹配从不同视角拍摄的同一目标或场景的序列图像进行匹配，旨在从低维的图像内容恢复高维结构，如恢复相机姿态并建立相机移动轨迹，目标或场景的三维 重建，以及遥感全景影像拼接等。3）基于不同传感器的特征匹配。鉴于不同传感器所获取的图像有着各自的优势且包含不同的感知信息，因而对不同的图像信息进行整合并得到更全面的场景或目标表示是十分必要的，而特征匹配便是将包含多源信息的图像进行关键点配对并估计变换函数从而将图像进行逐像素对齐，便于后续的信息融合，因而又称为多源图像特征匹配。这类匹配常用于医学图像分析中多模图像匹配，安防及军事领域中如红外可见光配准，遥感图像处理中不同分辨率且包含不同光谱信息的 影像配准与融合等。4）基于模板的特征匹配。这类匹配一般给定图像模板，然后将获取的图像与模板进行比较与匹配，常用于模板识别、差异检测或内容检索，如基于视觉的模式识别（字符识别，车牌识别）、图像检索，医学图像分析中病情诊断，标本分类以及遥感图像中航空或卫星图像在已知的其他地理信息地图中的匹配与定位等。

由此可见，特征匹配作为一项基础而关键的技术在诸多领域有着重要地位，因而对其展开深入研究有着重要实际应用价值。此外，作为许多高层视觉任务的底层输入，基于特征点的图像匹配问题也面临着多方面的挑战，其中包括准确性、鲁棒性（普适性）和高效性。

首先，特征匹配精度在许多基于匹配的精准估计应用上有着极高的要求，匹配误差会保留在后续处理环节中并逐渐累积从而严重制约最终视觉任务的有效实施。例如 根据特征点匹配结果求解相机运动参数从而恢复高维结构（Structure From Motion， SFM）的任务, 错误的匹配将产生相机姿态的错误估计，使得类似于三维重建和同 步定位与建图（Simultaneous Localization and Mapping，SLAM）等任务的结果 严重偏离于真实情形，同时图像融合、图像拼接和变化检测等任务同样严重依赖于图像配准的结果。精度问题通常来自于两个方面——特征提取精度和特征匹配精度。特征点匹配一般需要对从图像中提取出来的关键点进行定位，即以像素坐标的形式表示，通常该坐标要精确到亚像素级且两个待匹配点集应具有较高的重复率，保证所检测的特征点是真正意义上可匹配的 ；特征匹配精度则表现为所配对的两个特征点在真实空间中应当属于精确的同名位置，或者具有相同的语义特征，同时匹配结果中需要保证尽可能多的正确匹配以及尽可能少的错误匹配。其次，设计一种鲁棒的特征匹配方法以满足多方面的需求是十分必要的。待匹配图像通常来自不同时间、不同视角和不同传感器，成像条件多样性不可避免地造成了图像的匹配难度，况且图像本身的局部形变或畸变，以及图像之间的复杂变换等因素同样对特征匹配问题造成了严重阻碍。除此之外，如何减少因噪声、畸变、重复图像内容以及遮挡等问题造成的错误匹配也是特征匹配中亟需解决的问题。另一方面，为了满足大规模以及具有实时性要求的视觉任务，特征匹配方法应当满足较少的时间和空间消耗。然而特征点的匹配问题本质上是一个复杂组合优化难题，为了将 N 个特征点与另外 N 个特征点对齐，尽管这两组点是完全可匹配的，同样也需要 N! 种排列组合，况且离群点和噪声的引入将大大增加问题的求解难度，因而在建模求解过程中，如何减少解的搜索空间，降低问题的计算复杂度也是特征匹配的重要难题。

综上所述，基于特征的图像匹配技术存在多方面的难题，有待进一步深入的研究，以满足众多视觉任务的应用需求，因而开展特征匹配相关的课题具有重要的理论研究与实际应用价值。

1、Harris角点检测（1988）

1.1 理论推导

https://github.com/o0o0o0o0o0o0o/image-processing-from-scratch

思想：从图像局部的小窗口观察图像特征

角点定义：窗口向任意方向的移动都导致图像灰度的明显变化。

• $(x,y)$：固定大小窗口中的坐标
• $w(x,y)$：窗口权值，当为高斯分布时指离中心点越远的点对表示中心点周围梯度变化的贡献越小
• $I(x+u,y+v)$：x方向移动u，y方向移动v后，窗口所选中的图像的灰度值
• $I(x,y)$：原图像

根据泰勒展开公式：

$f(x+u,y+v)\approx f(x,y)+uf_x(x,y)+vf_y(x,y)$

对$E(u,v)$展开：

式中，$I_x$是指原图像在x方向上求导，使用sobel算子即可

E(u,v)是u、v的函数，目标是当$(u,v)$取任意值时，寻找最大的E

根据实对称矩阵可正交相似对角化：

其中$\lambda_1、\lambda_2$是M正交相似对角化后的特征值，由上式可以看出E(u,v)是一个椭圆形：

根据$\lambda$的变化有如下总结：

根据：

$det M = \lambda_1\lambda_2\\ trace M = \lambda_1+\lambda_2$

为了体现$\lambda_1、\lambda_2$同时很大，并且差不多大，定义如下响应函数：

$R=detM-k(traceM)^2$

其中k是自己调的参数，一般设置在区间 [0.04, 0.06] （？），对于角点，$|R|$的值很大。

最后通过设定阈值来选择角点。

1.2 总结

Harris角点检测的特性如下：

1. 阈值决定角点的数量

2. 光照不变性：Harris角点检测算子对亮度和对比度的变化不敏感（光照不变性）在进行Harris角点检测时，使用了微分算子对图像进行微分运算，而微分运算对图像密度的拉升或收缩和对亮度的抬高或下降不敏感。换言之，对亮度和对比度的仿射变换并不改变Harris响应的极值点出现的位置，但是，由于阈值的选择，可能会影响角点检测的数量。

   

3. 旋转不变性：Harris角点检测算子具有旋转不变性，Harris角点检测算子使用的是角点附近的区域灰度二阶矩矩阵。而二阶矩矩阵可以表示成一个椭圆，椭圆的长短轴正是二阶矩矩阵特征值平方根的倒数。当特征椭圆转动时，特征值并不发生变化，所以判断角点响应值也不发生变化，由此说明Harris角点检测算子具有旋转不变性。

   

4. 缺点：不具有尺度不变性：Harris角点检测算子不具有尺度不变性，尺度的变化会将角点变为边缘，或者边缘变为角点，Harris的理论基础并不具有尺度不变性。

2、SIFT尺度不变特征变换(2004)

SIFT图像匹配及其python实现 - 知乎 (zhihu.com)

SIFT算法详解_zddhub的博客-CSDN博客_sift

【计算机视觉】2. 特征点检测：Harris, SIFT, SURF, ORB - 知乎 (zhihu.com)

补充知识

尺度空间理论

尺度空间理论简介 | Jack Huang’s Blog (huangwang.github.io)

现实世界中物体只有具备一定的尺度才能够倍人眼所察觉，尺度空间就是试图在图像领域中模拟人眼观察物体的概念与方法。

图像的尺度空间是指图像的模糊程度，而非图像的大小。近距离看一个物体和远距离看一个物体，模糊程度是不一样的；从近到远，图像越来越模糊的过程，也是图像的尺度越来越大的过程。

为什么需要尺度空间

图像的尺度空间是一幅图像经过几个不同高斯核后形成的模糊图片的集合，用来模拟人眼看到物体的远近程度以及模糊程度。 图像尺度的改变不等于图像分辨率的改变。

对象的大小（尺度）取决于与相机的距离，在没有先验知识的前提下，视觉系统应准备好以所有可能的尺度“看到”物体，图像应同时在所有尺度级别上进行处理。

为什么使用高斯核

看起来似乎有很多方法可以构造尺度空间，但实际上有相关论文可以证明，高斯核是实现尺度变换的唯一线性核。

图像金字塔

为什么需要多分辨率

观察图像时，看到的通常是由相似纹理和灰度级连成的区域，它们相结合就形成了物体。如果物体的尺寸较小或对比度较低，那么我们需要以较高的分辨率来研究它们；如果物体的尺寸较大或对比度较高，则以低分辨率进行粗略的观察就已足够。如果较小物体和较大物体（或对比度较低和对比度较高的物体）同时存在，那么以不同分辨率来研究它们将更具优势，这就是多分辨率处理的基本动机。

即图像分辨率越低，伴随的细节就越少。图像的低分辨率级别用于分析较大的结构或图像的整体内容；而高分辨率级别适合于分析物体的细节特性。这种由粗到细的分析策略在模式识别中特别有用。

比如上图中右下角的图像更适合于识别这是个花盆，而左边的图像更适合于识别这是什么叶子。

多尺度和多分辨率

多尺度：
我们通常将现实世界视为连续的，真实图像具有连续的空间位置。尺度的概念至少来源于两个想法：1.视觉系统有局限性，只能以一定的尺度（通过某种模糊算子）来捕获真实图像；2.物体由于和视觉系统的距离不同而发生尺度变化，以不同的尺度观察连续的图像有助于理解其内容。一般应用高斯核（高斯模糊）进行多尺度变换。

多分辨率：
分辨率的概念使得空间离散化。具有一定长度（宽度）的对象可以通过对其物理空间进行一定的采样来重新表示，即每个长度（宽度）具有多少个像素。采样会引起连续空间的损失，但如果先进行平滑操作，则可以得到更好的低分辨率图像。从平滑后连续或原始离散的图像，建立具有不同分辨率（并因此具有不同大小）的离散版本的层次结构（图像金字塔），通常可以用于在不同尺度（和方向）上的图像重建。

多分辨率可以视为某种多尺度表示的离散化。但实际上，由于我们所处理的数据始终是离散的，并且多分辨率可以以不同的尺度重建图像，所以人们会交替使用这两个术语。

2.1 概述

SIFT具有缩放、平移、旋转不变性，对照明变化和仿射或三维投影保持部分不变。

SITF算法，即尺度不变特征变换(Scale-invariant feature transform)算法，是由David G.Lowe于1999年提出，并在2004年加以完善。是一种CV的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量。

分为特征点提取、特征点描述、特征点匹配

2.2 尺度空间极值检测

第一步是搜索所有比例和图像位置。通过使用高斯函数的差分来识别对尺度和方向不变的潜在兴趣点

2.2.1 高斯模糊处理

使用级联过滤方法检测关键点，该方法使用高效算法来识别候选位置，然后进一步详细检查。关键点检测的第一阶段是识别在同一对象的不同视图下可重复分配的位置和比例。通过使用称为尺度空间的连续尺度函数，在所有可能的尺度上搜索稳定的特征，可以实现对图像尺度变化不变的位置的检测（Witkin，1983）.

已经被Koenderink（1984）和Lindeberg（1994）证明的是，唯一可能的尺度空间核是高斯函数**(唯一可以模拟近处清晰远处模糊的核）**，因此，图像的尺度空间被定义为一个函数L（x，y，σ），由可变尺度高斯G（x，y，σ）与输入图像I（x，y）的卷积产生：

$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$

其中*表示在x和y方向上的卷积,$\sigma$表示高斯卷积核的参数。使用高斯模糊对图像进行高斯平滑且降低图像细节，对图像进行2x2降采样处理，即图像长宽都降低为原来的一半，如此实现图像尺度的降低。

$G(x,y,\sigma)=\frac{1}{2\pi\sigma^2}e^{-(x^2+y^2)/2\sigma^2}$

2.2.2 DOG尺度空间的构建

为了检测稳定特征点的位置，SIFT算法用DOG尺度空间来代替尺度空间函数 $L(x,y,\sigma)$。通过对两幅相邻高斯尺度空间图像相减，得到DOG尺度空间。用$D(x,y,\sigma)$函数来表示DOG空间，则该尺度空间的计算公式如下：

$D(x,y,\sigma)=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)=L(x,y,k\sigma)-L(x,y,\sigma)$

通过上式也可以看出 DOG 尺度空间中的图像可以反映图像像素的变化，有变化的地方才有特征的存在，因此利用DOG尺度空间来定位特征点。

2.2.3 高斯金字塔

图中左侧是高斯金字塔，金字塔的每一层是图片进行不同尺度的高斯模糊的结果，每一层中的不同层是高斯卷积核不同的结果，也就是说$\sigma$不同（$\sigma$的不同是通过k来控制的）。

图中右侧是DOG空间，通过相邻层之间的差分得到的。

实际上进行差分后的图像人眼难以分别，但对这些DOG图像进行归一化，可以很明显的看到差分图像所蕴含的特征，并且有一些特征是在不同模糊程度、不同尺度下都存在的，这些特征正是Sift所要提取的稳定特征。

2.2.4 相关参数确定

组数$o=[log_2(min(M,N))]-3$，(M,N)原始图像的长宽

每组内的层数$S=n+3$，n表示每组想要提取特征的图像数目

初始高斯核$\sigma_0=\sqrt{1.6^2-0.5^2}=1.52$，这里原作者认为相机拍摄的图像自带0.5高斯核的模糊，根据高斯模糊的性质，对一个已经进行过0.5高斯模糊的图像再次进行1.52高斯模糊，就会得到一个直接用1.6高斯模糊的图像（勾股数的关系）

高斯核系数$k=2^{1/n}$

注：原文中建议使用4组5个尺度（模糊度）

示例：

2.3 关键点定位

尺度空间中的所有检测点都与其同尺度相邻的8个点和上下尺度各相邻的9个点进行比较，只保留局部极值点，即该点是否是这27点中的最大值或最小值。之后去除其中不好的关键点，通过阈值化、子像元插值、剔除对比度低的点以及不稳定的边缘响应点来对精化检测到的关键点。

2.3.1 阈值化

判断噪声点

$|f(X)|>0.5*T/n$

若选取点满足上述条件则认为不是噪声点，原文中T=0.04

2.3.2 泰勒展开求亚像素极值点位置（子像元插值）

对特征点进行子像元插值，是因为特征点的寻找是在离散空间中进行，找的特征点也是离散的，但是对于连续空间来说，离散的极值点不一定就是函数的最终极值点，所以需要用插值来找到真正的极值点。

因为是先进行下采样，然后进行极值点计算，如果不精确找到亚像素位置的极值点，那么在返回原图像时会出现位置误差。

用函数$f()$来表示尺度空间的像素值，那么$f(x,y,\sigma)$是一个关于坐标(x,y)和尺度$\sigma$的三元函数。

对$f(x,y,\sigma)$在检测到的极值点$X_0(x_0,y_0,\sigma_0)$进行三元二阶泰勒展开

转化为矢量形式：

式中$\hat{X}$表示$X-X_0$，即$X$相对于插值中心$X_0$的偏移量。这里的$f(X)$拟合了$X_0$周围的尺度空间函数

目标是寻找该函数的极值点，则对$f(X)$求导：

令导数为零得：

代回f(X)：

这里需要注意的问题是：

1. 当求出的偏移量大于0.5（只要x，y，$\sigma$任意一个大于0.5）时，表示该插值点偏移了插值中心，此时需要改变插值中心继续上述的泰勒展开，直到插值偏移量小于0.5（三个量都小于）。当偏移量过大时，则说明精确的极值点完全偏移了离散比较得到的极值点，此时应去除该极值点。（0.5是原文设定值）
2. 由于上述是一个迭代的过程，所以需要设定一个迭代次数来终止（文中进行了5次迭代）
3. 当$|f(X)|$的值过小时，容易受到噪声影响，所以当其小于一定值时去除（原文使用0.03，另有使用0.04/n）

2.3.3 舍去低对比度的点

若$|f(X)<T/n$,则舍去点X

2.3.4 舍去边缘点

边缘响应较强的点就是横跨边缘处有较大的主曲率且垂直边缘处有较小主曲率的点，首先边缘上的点容易出现二义性，不能确定到底属于哪一个区域，其次易受噪声影响而变得不稳定，所以边缘响应的点一定要去除掉。

主曲率可以用Hessian矩阵H表示：

Hessian 就是描述的一个点周围像素梯度大小的变化率，其极值就是生成图像稳定的边缘点（突变点），其两个特征值，代表这其在两个相互垂直方向是的梯度的变化率，当两个特征值越大时，其图像中的像素点的像素值波动越大。我们用两个特征值相加即 Hessian的判别式（即行列式的值）来量化。

这里的$D_{xx}$指$\frac{\partial^2f}{\partial x\partial x}$

H的特征值与主曲率成正比，主曲率的变化公式如下：设$\alpha$和$\beta$是H的特征值，$r=\alpha /\beta$，其中$\alpha>\beta$。则

$Tr=D_{xx}+D_{yy}=\alpha+\beta$

$Det=D_{xx}D_{yy}-((D_{xy})^2)=\alpha \beta$，若Det<0，则直接舍去

$\frac{Tr^2}{Det}=\frac{(\alpha+\beta)^2}{\alpha \beta}=\frac{(r\beta+\beta)^2}{r\beta^2}=\frac{(r+1)^2}{r}$

通过计算特征值的比率来表示主曲率的变化。如果要去除边缘响应点的话，就需要垂直和横跨边缘方向上差别不是很大的点，如果差别很大的话，则说明是边缘响应点。因此要求 小于一定值。因为r为1时，$\frac{(r+1)^2}{r}$最小，当$r$增加时，$\frac{(r+1)^2}{r}$也会增大，所以只要控制 $r$小于阈值，这样$\frac{(r+1)^2}{r}$会小于一定阈值，$Tr^2/Det$ 也会小于一定的阈值，那么两个方向上的主曲率差别不大，就去除了边缘响应点。

因此，可以将满足以下公式的特征点保留，否则剔除掉。

$\frac{Tr^2}{Det}<\frac{(r+1)^2}{r}$

2.4 计算关键点主方向

特征描述子包含了该描述子所在的尺度、描述子的位置以及描述子的方向。因此生成特征点描述子需要求出描述子的这三个值。尺度是已知的，这里主要说明如何求关键点的方向信息。因为关键点还要满足尺度不变性以及一定的光照和视角不变性等，因此在描述关键点描述子的时候，要综合考虑关键点及其周围像素点的信息，这里的像素点应当是会影响关键点信息的像素点，即对关键点描述子生成有贡献的点。

为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的稳定方向。对于在DOG金字塔中检测出的关键点点，采集其所在高斯金字塔图像**3$\sigma$邻域窗口(?)**内像素的梯度和方向分布特征。梯度的模值和方向如下：

梯度幅值及梯度方向计算如下：

L()为关键点所在尺度空间的图像灰度值

统计以特征点为圆心（在最接近关键点尺度值$\sigma$的高斯图像上统计），以该特征点所在的高斯图像的尺度$\sigma_{oct}$的3*1.5倍（原文建议）为半径的圆内的所有的像素的梯度方向及其梯度幅值(?)，并做1.5$\sigma_{oct}$的高斯滤波（对圆内的梯度进行高斯加权，离关键点近的权重越高），即梯度幅值m(x,y)按1.5$\sigma_{oct}$高斯分布加权。

计算关键点的主方向会用到梯度直方图，直方图会统计出各个方向上的像素点的个数，像素点个数最多的那个方向就是关键点的主方向（一般10度为一柱，共36柱）。之后将坐标轴方向和关键点主方向保持一致，便能够满足旋转不变性。（辅方向>0.8主方向）

对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。实际编程实现中，就是把该关键点复制成多份关键点，并将方向值分别赋给这些复制后的关键点。

考虑到此时的直方图代表方向是一个范围，于是需要对离散的梯度方向直方图要进行插值拟合处理，来求得更精确的方向角度值。利用抛物线进行插值，如图：

至此，SIFT关键点被描述为（坐标，尺度，主方向）的4维向量

2.5 关键点描述符

通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有贡献的像素点，并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。

SIFT描述子是关键点邻域高斯图像梯度统计结果的一种表示。通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。

原文指出最好的结果是使用一个4x4的直方图数组(子区域、种子点），每个数组中有8个方向的梯度信息。因此，原文的实验对每个关键点使用4x4x8=128个元素的特征向量。

2.5.1 确定计算描述子所需的图像区域

特征描述子与特征点所在的尺度有关，因此，对梯度的求取应在特征点对应的高斯图像上进行。将关键点附近的邻域划分为d*d(原文建议d=4)个子区域，每个子区域做为一个种子点，每个种子点有8个方向。每个子区域的大小与关键点方向分配时相同，即每个区域有**$3\sigma_{oct}$（？）**个子像素，为每个子区域分配边长为$3\sigma_{oct}$的矩形区域进行采样(个子像素实际用边长为$\sqrt{3\sigma_{oct}}$的矩形区域即可包含，,考虑到这个值不大，为了简化计算所以取$3\sigma_{oct}$作为边长，并且采样点宜多不宜少)。

考虑到需要对这个d*d的子区域进行双线性插值，所以需要用边长为$3\sigma_{oct}\times (d+1)$的窗口采样。又考虑到旋转因素(方便下一步将坐标轴旋转到关键点的方向)，所以实际需要计算的区域半径为：

$radius = \frac{3\sigma_{oct}*\sqrt{2}*(d+1)}{2}$

计算结果取整。

2.5.2 旋转坐标轴

将坐标轴旋转为关键点的方向，以确保旋转不变性。即把主方向作为方向基准，以此来固定梯度信息与主方向的相对位置。（需要注意的是，旋转的是窗口，图像并没有旋转，所以说后续计算的坐标(x’’,y’’)可以理解为样本点(x,y)在旋转后的窗口中的坐标。）

旋转后邻域内采样点的新坐标为：

然后将邻域内的采样点分配到对应的子区域内，将子区域内的梯度值分配到8个方向上，计算其权值。

旋转后的采样点坐标在半径为radius的圆内被分配到d*d的子区域，计算影响子区域的采样点的梯度和方向，分配到8个方向上。

旋转后的采样点（x‘，y’）落在子区域的下标（坐标）为：

这里除以$3\sigma_{oct}$（类似去量纲）是以关键点为原点建立新的坐标系，加d/2是平移坐标原点

原文建议子区域的像素的梯度大小按$\sigma =0.5d$的高斯加权计算，即

$w=m(a+x,b+y)*e^{-\frac{(x')^2+(y')^2}{2\times(0.5d)^2}}$

其中a，b为关键点在高斯金字塔图像中的位置坐标。x，y为以关键点为原点的旋转前的采样点坐标。

2.5.3 插值计算种子点的梯度

将采样点(x,y)的梯度代入坐标(x’’,y’’)，然后对采样点进行插值，计算其对每个种子点的贡献值。

如图中红点落在第0行和第1行之间，对这两行都有贡献。对第0行第3列种子点的贡献因子为dr，对第1行第3列的贡献因子为1-dr，同理，对邻近两列的贡献因子为dc和1-dc，对邻近两个方向的贡献因子为do和1-do。则最终累加在每个方向上的梯度大小为：

其中k,m,n为0或1。

2.5.4 归一化处理

上述128个梯度信息组成了该关键点的特征向量。关于光照不变性。对于图像灰度值整体漂移，图像各点的梯度是邻域像素相减得到，所以能去除此类光照影响。对于灰度值的尺度变换，此处对特征向量进行归一会处理（即建立梯度信息间的相对关系，从而一定程度上去除光照影响）。得到的描述子向量为$H=(h_1,h_2,..,h_{128})$，归一化处理后为$l=(l_1,l_2,..,l_{128})$:(为什么要开根号？)

描述子向量门限：非线性光照，相机饱和度变化对造成某些方向的梯度值过大，而对方向的影响微弱。因此设置门限值(向量归一化后，一般取0.2)截断较大的梯度值。然后，再进行一次归一化处理，提高特征的鉴别性。

最后按特征点的尺度对特征描述向量进行排序。

2.6 特征点匹配（图像配准）

使用欧氏距离来判断两幅图像特征点的相似性。在匹配过程中，SIFT算法使用的是Kd-tree（或KNN)算法，即找出待配准图像中与参考图像特征点A距离最近的点B和距离次近的点C，则判断特征点A与B是一对匹配点的公式为：

$\frac{d(A,B)}{d(A,C)}<Threshold$

其中d(A,B)为A和距离A最近的点B之间的距离，d(A,C)为A和距离A次近的点C之间的距离。

之后用**RANSAC算法（？）**消除错误匹配点，至此SIFT特征点提取和匹配工作已经完成。

2.7 总结

SIFT用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量。其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。

局部影像特征的描述与侦测可以帮助辨识物体，SIFT 特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。

SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。

SIFT算法的优点：

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

SIFT可以解决的问题：

考虑到目标的自身状态、场景所处的环境和成像器材的成像特性等因素影响图像配准/目标识别跟踪的性能。

而SIFT算法在一定程度上可解决：

1. 目标的旋转、缩放、平移
2. 图像的仿射、投影变换：用梯度信息生成描述子，由于梯度的稳定性，这本身就具备了一定的抵抗仿射的能力。另外生成梯度直方图时都用了高斯加权，距离特征点近的梯度幅值有较大权重，弥补了没有考虑仿射不变性带来的特征点不稳定。（可以使用椭圆的仿射归一化（参见Surf[31]）将描述符扩展到仿射不变区域，尽管这会影响计算时间。？）
3. 光照影响
4. 目标遮挡
5. 杂物场景
6. 噪声

SIFT的缺点：

1. 初始版本的实时性不高
2. 有时特征点较少
3. 对边缘光滑的目标无法准确提取特征点

如下图所示，SIFT对模糊的图像和边缘平滑的图像，检测出的特征点过少

3、SURF（2008）

SURF特征提取算法 - 知乎 (zhihu.com)

【CV学习5】SURF算法详解 - 苟富贵 - 博客园 (cnblogs.com)

(26条消息) SURF算法_菜鸟知识搬运工的博客-CSDN博客_surf算法

Speeded Up Robust Features（SURF，加速稳健特征），是一种稳健的局部特征点检测和描述算法。Surf是对David Lowe在1999年提出的Sift算法的改进，提升了算法的执行效率，为算法在实时计算机视觉系统中应用提供了可能。

SURF相对于SIFT的两大改进为

1. 使用积分图和盒式滤波计算hessian矩阵来代替SIFT的DOG尺度空间
2. 使用统计特征点圆形邻域内的haar小波特征来代替统计梯度直方图

SURF的思想就是：用积分图来简化卷积，以及怎么用不同的模板来近似原来尺度空间中的高斯滤波器。

3.1 关键点定位

在关键点的定位上，SURF使用积分图和Boxfilter计算hessian矩阵，通过比较hessian矩阵行列式的大小来选择特征点的位置和尺度,而不是SIFT所使用的DOG算子，金字塔构建时通过改变boxfilter的尺寸和滤波器的方差来实现不同的尺度图像的获取。

3.1.1 积分图计算

SIFT图像金字塔构建时，使用不同尺度的高斯模板和原图卷积后的图像进行差分来生成DOG尺度空间。

而SURF图像金字塔构建时，使用不同尺度的高斯模板和原图卷积后计算每个点处的hessian值。

注：至于为什么选择Hessian来进行尺度选择，详见T. Lindeberg, Feature detection with automatic scale selection, IJCV 30 (2) (1998) 79–116.

在尺度$\sigma$下，点$X=(x,y)$处的hessian值为

其中$L_{xx}(X,\sigma)$是X处图像和二阶级高斯模板$\frac{\partial^2}{\partial x^2}g(\sigma)$的卷积。

实际计算时，SURF并不会用到$\frac{\partial^2}{\partial x^2}g(\sigma)$和图像卷积，而是使用盒式滤波器Boxfilter近似。

下图展示的是盒式滤波器Boxfilter对$L_{yy}(X,\sigma)$和$L_{xy}(X,\sigma)$的近似情况。（这是一种近似，所以必然伴随信息的缺失）

左上是使用先高斯滤波然后二阶求导的结果，左下是使用盒式滤波模板的近似。高斯核尺度越大，则盒式滤波的尺度就越大。

SURF构成DOG图像的方式是用原图每个像素的Hessian矩阵行列式的近似值构成：

$det(Happrox)=L_{xx}L_{yy}-(0.9L_{xy})^2$

由于高斯核实服从正态分布的，从中心点往外，系数越来越低，为了提高运算速度，Surf使用了盒式滤波器来近似替代高斯滤波器，所以在Dxy上乘了一个加权系数0.9，目的是为了平衡因使用盒式滤波器近似所带来的误差。

使用盒式滤波的目的是引入积分图来提高计算速度。

Boxfilter就是这样一种优化方法，它可以使复杂度为O(MN)的求和，求方差等运算降低到O(1)或近似于O(1)的复杂度，它的缺点是不支持多尺度。

一旦计算出积分图像，需要三次加法来计算任何垂直矩形区域上的强度总和。因此，计算时间与其大小无关。这在Surf中很重要，因为Surf使用了大尺寸的过滤器。

3.1.2 构建尺度空间

同Sift一样，Surf的尺度空间也是由O组L层组成。

不同的是，Sift中下一组图像的尺寸是上一组的一半，同一组间图像尺寸一样，但是所使用的高斯模糊系数逐渐增大；

由于采用了盒子滤波和积分图像，在Surf中，不同组间图像的尺寸都是一致的，但不同组间使用的盒式滤波器的模板尺寸逐渐增大，同一组间不同层间使用相同尺寸的滤波器，但是滤波器的模糊系数逐渐增大。

在sift中，通过不断地减小图像尺寸来模拟远近变化，而SURF是通过改变滤波模板的尺寸来实现不同尺度的获得。

对于尺寸为L的模板，当用它与积分图运算来近似二维高斯核的滤波时，对应的二维高斯核的参数σ=1.2×(L/9)

使用9×9的模板对图像进行滤波，其结果作为最初始的尺度空间层（此时，尺度值为s=1.2×(L/9)，近似σ=1.2的高斯微分），后续的层将通过逐步放大滤波模板尺寸，以及放大后的模板不断与图像进行滤波得到。由于采用盒子滤波和积分图像，因为在卷积时仅仅是查找积分图中的四个角处的数值，所有层的计算代价都是相同的。

将尺度空间划分为O组L层。一个组代表了逐步放大的滤波模板对同一输入图像进行滤波的一系列响应图。每个组又由若干固定的层组成。由于积分图像离散化的原因，两个层之间的最小尺度变化量是由高斯二阶微分滤波器在微分方向上对正负斑点响应长度$l_0$决定的，它是盒子滤波器模板尺寸的1/3。对于9×9的模板，它的$l_0$=3。下一层的响应长度至少应该在$l_0$的基础上增加2个像素，以保证一边一个像素，即$l_0$=5。这样模板的尺寸就为15×15。以此类推，我们可以得到一个尺寸增大模板序列，它们的尺寸分别为：9×9，15×15，21×21，27×27，黑色、白色区域的长度增加偶数个像素，以保证一个中心像素的存在。

采用类似的方法来处理其他几组的模板序列。其方法是将滤波器尺寸增加量翻倍（6，12，24，38）。这样，可以得到第二组的滤波器尺寸，它们分别为15，27，39，51。第三组的滤波器尺寸为27，51，75，99。如果原始图像的尺寸仍然大于对应的滤波器尺寸，尺度空间的分析还可以进行第四组，其对应的模板尺寸分别为51，99，147和195。下图显示了第一组至第三组的滤波器尺寸变化。

在通常尺度分析情况下，随着尺度的增大，被检测到的关键点数量迅速衰减。所以一般进行3-4组就可以了，与此同时，为了减少运算量，提高计算的速度，可以考虑在滤波时，将采样间隔设为2。

特征点的定位过程Surf和Sift保持一致，将经过Hessian矩阵处理的每个像素点与二维图像空间和尺度空间邻域内的26个点进行比较，初步定位出关键点，再经过滤除能量比较弱的关键点以及错误定位的关键点，筛选出最终的稳定的特征点。

3.2 特征点精确定位

3.2.1 非极大值抑制

在每一组中选取相邻的三层Hessian行列式图像，对于中间层的每一个Hessian行列式值都可以做为待比较的点，在空间中选取该点周围的26个点进行比较大小，若该点大于其他26个点，则该点为特征点。从上诉过程可以知道，当尺度空间每组由四层构成时，非极大值抑制只会在中间两层进行，相邻的组之间不进行比较。

3.2.2 设定Hessian行列式的阀值

低于Hessian行列式阀值的点不能作为最终的特征点。在实际选择阀值时，根据实际应用中对特征点数量和精确度的要求改变阀值。阀值越大，得到的特征点的鲁棒性越好。在处理场景简单的图像时，其阀值可以适当的调低。在复杂的图像中，图像经旋转或者模糊后特征点变化的数量较大，测试需要适当提高阀值。

设置阈值是为了降低噪声的影响

3.3 方向分配（主方向）

哈尔小波变换的原理及其实现(Haar) (360doc.com)

Sift特征点方向分配是采用在特征点邻域内统计其梯度直方图，而在Surf中，采用的是统计特征点圆形邻域内的haar小波特征。

以特征点为中心，以$6s(s=1.2\times L/9为特征点的尺度)$为半径的圆形区域，对图像进行haar小波响应运算。这样做实际上就是对图像进行梯度运算只不过是我们需要利用积分图像，提高计算图像梯度的效率，因此选择haar小波响应运算。在SIFT中求取特征点主方向时，以是特征点为中心，在以4.5σ为半径的邻域内计算梯度方向直方图。事实上，两种方法在求取特征点主方向时，考虑到Haar小波的模板带宽，实际计算梯度的图像区域是相同的。用于计算梯度的Harr小波的尺度为4s。

其中左侧模板计算X方向的响应，右侧模板计算y方向的响应，黑色表示-1，白色表示+1。用其对圆形领域进行处理后，就得到了该领域内每个点对应的x,y方向的响应，然后用以兴趣点为中心的高斯函数（$\sigma=2s)$对这些响应进行加权。

为了求取主方向值，需要设计一个以特征点为中心，张角为60度的扇形滑动窗口，统计这个扇形区域内的haar小波特征总和。以步长为0.2弧度左右，旋转这个滑动窗口，再统计小波特征总和。小波特征总和最大的方向为主方向。特征总和的求法是对图像Harr小波响应值dx、dy进行累加，得到一个矢量($m_w,\theta_w$):

$m_w=\sum_wdx+\sum_wdy\\ \theta_w=arctan(\sum_wdx/\sum_wdy)$

主方向为最大Harr响应累加值所对应的方向，也就是最长矢量所对应的方向，即

$\theta=\theta_w|max(m_w)$

主方向的选取与SIFT相同。

3.4 特征描述子

在SIFT中关键点描述是选取了关键点周围16x16的领域，又将其划分为4x4的区域，每个区域统计8个方向梯度，最后得到128维度的描述向量。

SURF中，在关键点周围选取一个正方形框，方向为关键点的主方向，边长为20S。将其划分为16个区域（边长为5S），每个区域统计25个像素的水平方向和垂直方向的Haar小波特性（均相对于正方形框的主方向确定的）

生成特征点描述子，需要计算图像的Haar小波响应。在一个矩形区域来计算Haar小波响应。以特征点为中心，沿上一节讨论得到的主方向，沿主方向将20s×20s的图像划分为4×4个子块，每个子块利用尺寸2s的Harr模板进行响应值计算，然后对响应值进行统计$\sum dx,\sum|dx|,\sum dy,\sum|dy|$形成特征矢量。图中以特征点为中心，以20s为边长的矩形窗口为特征描述子计算使用的窗口，特征点到矩形边框的线段表示特征点的主方向。

将20s的窗口划分成4×4子窗口，每个子窗口有5s×5s个像素。使用尺寸为2s的Harr小波对子窗口图像进行其响应值计算，共进行25次采样，分别得到沿主方向的dy和垂直于主方向的dx。然后，以特征点为中心，对dy和dx进行高斯加权计算，高斯核的参数为σ=3.3s(即20s/6)。最后分别对每个子块的响应值进行统计，得到每个子块的矢量：

$V_{子块}=[\sum dx,\sum |dx|,\sum dy,\sum|dy|]$

由于共有4×4个子块，因此，特征描述子共由4×4×4=64维特征矢量组成。SURF描述子不仅具有尺度和旋转不变性，而且对光照的变化也具有不变性。使小波响应本身就具有亮度不变性，而对比度的不变性则是通过将特征矢量进行归一化来实现。图3 给出了三种不同图像模式的子块得到的不同结果。

为了充分利用积分图像进行Haar小波的响应计算，我们并不直接旋转Haar小波模板求得其响应值，而是在积分图像上先使用水平和垂直的Haar模板求得响应值dy和dx，然后根据主方向旋转dx和dy与主方向保持一致，如下图所示。为了求得旋转后Haar小波响应值，首先要得到旋转前图像的位置。旋转前后图间的位置关系，可以通过点的旋转公式得到：

$x=x_0-j\times scale\times sin(\theta)+i\times scale \times cos(\theta)\\ y=y_0-j\times scale\times cos(\theta)+i\times scale \times sin(\theta)$

在得到点(j,i)在旋转前对应积分图像的位置(x,y)后，利用积分图像与水平、垂直Harr小波，求得水平与垂直两个方向的响应值dx和dy。对dx和dy进行高斯加权处理，并根据主方向的角度，对dx和dy进行旋转变换，从而，得到旋转后的dx’和dy’。其计算公式如下：

$dx'=w(-dx\times sin(\theta)+dy\times cos(\theta))\\ dy'=w(-dx\times cos(\theta)+dy\times sin(\theta))$

3.5 特征描述子的维数

一般而言，特征矢量的长度越长，特征矢量所承载的信息量就越大，特征描述子的独特性就越好，但匹配时所付出的时间代价就越大。对于SURF描述子，可以将它扩展到用128维矢量来表示。具体方法是在求$\sum dx,\sum |dx|$时区分dy<0和dy>=0的情况,$\sum dy,\sum|dy|$时区分dx<0和dx>=0的情况。这样，每个子块就产生了8个梯度统计值，从而使描述子特征矢量的长度增加到128维。

为了实现快速匹配，SURF在特征矢量中增加了一个新的变量，即特征点的拉普拉斯响应正负号。在特征点检测时，将Hessian矩阵的迹的正负号记录下来，作为特征矢量中的一个变量。这样做并不增加运算量，因为特征点检测进已经对Hessian矩阵的迹进行了计算。在特征匹配时，这个变量可以有效地节省搜索的时间，因为只有两个具有相同正负号的特征点才有可能匹配，对于正负号不同的特征点就不进行相似性计算。

简单地说，我们可以根据特征点的响应值符号，将特征点分成两组，一组是具有拉普拉斯正响应的特征点，一组是具有拉普拉斯负响应的特征点，匹配时，只有符号相同组中的特征点才能进行相互匹配。显然，这样可以节省特征点匹配的时间。

3.6 总结

1. 最大的创新是引入了积分图来加快运算，但在实际应用中还是很慢（秒级的，现在的速度要求是微秒级以下）
2. 在特征维数（64）上比SIFT（128）低

各种二进制特征提取算子（ORB 、BRIEF 、 FREAK、 BRISK）

4. FAST特征点检测（2006，2010）

【特征检测】FAST特征点检测算法

OpenCV特征点提取----Fast特征

FAST算子总结

SURF特征算是为了提高运算效率对SIFT特征的一种近似，虽然在有些实验环境中已经达到了实时，但是实践工程应用中，特征点的提取与匹配只是整个应用算法中的一部分，所以我们对于特征点的提取必须有更高的要求，从这一点来看前面介绍的的那些特征点方法都不可取。

4.1 概述

FAST角点定义为：若某像素与其周围邻域内足够多的像素点相差较大，则该像素可能是角点。

步骤：

1. 以像素p为中心，半径为3的圆上，有16个像素点（p1、p2、…、p16）。

2. 定义一个阈值。计算p1、p9、p5、p13与中心p的像素差，若它们的绝对值有至少3个超过阈值，则当做候选角点，再进行下一步考察；否则，不可能是角点；

3. 若p是候选点，则计算p1到p16这16个点与中心p的像素差，若它们有至少连续9个超过阈值，则是角点；否则，不可能是角点。

4. 对图像进行非极大值抑制：计算特征点处的FAST得分值（即score值，也即s值），判断以特征点p为中心的一个邻域（如3x3或5x5）内，计算若有多个特征点，则判断每个特征点的s值（16个点与中心差值的绝对值总和），若p是邻域所有特征点中响应值最大的，则保留；否则，抑制。若邻域内只有一个特征点（角点），则保留。得分计算公式如下（公式中用V表示得分，t表示阈值）：

   $V=max \begin{cases} \sum(pixel\ values-p)&,(value-p)>t\\ \sum(p-pixel\ values)&,(p-calue)>t \end{cases}$

上述步骤为FAST-9，还有FAST-10、-12等，与FAST-9同理，只是超过阈值的个数不同。

4.2 机器学习的角点检测器

1. 选取进行角点提取的应用场景下的一组训练图像。

2. 使用FAST角点检测算法找出训练图像上的所有角点。

3. 对于每一个角点，将其周围的16个像素存储成一个向量。对所有图像都这样做构建一个特征向量。

4. 每一个角点的16像素点都属于下列三类中的一种。

   $S_{p\to x}= \begin{cases} d&,&I_{p\to x}\leq I_p-t&(darker)\\ s&,I_p-t\leq&I_{p\to x}< I_p+t&(similar)\\ b&,I_p+t\leq&I_{p\to x}&(brighter) \end{cases}$

5. 根据这些像素点的分类，特征向量被分为3个子集

6. 定义一个新的布尔变量p，如果p是角点就设置为True，否则就设置为False。

7. 使用ID3算法来查询每一个子集。（ID3，决策树的一种，核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。）

8. 递归计算所有的子集直到它的熵为0。

9. 被构建好的决策树用于其它图像的FAST检测。

4.3 总结

FAST的步骤简单，实现速度快。但是当图像中的噪点较多时，它的健壮性并不好，而且算法的效果还依赖于阈值t。并且FAST算子不产生多尺度特征而且FAST角点没有方向信息，这样就会失去旋转不变性。

fast以其高计算效率和高可重复性成为CV中流行的角点检测算法。

2005年，Rosten在SUSAN基础上提出了FAST[2]

2006年，Rosten使用机器学习[3]对FAST进行改进。在2009年提出性能增强（可重复增强、计算效率下降)的FAST-ER[4]。

2010年，Mair在ECCV会议论文[5]中提出AGAST特征。对FAST底层的the accelerated segment test进行改进，通过在扩展配置空间寻找最优决策树，使用特定树的组合获得自适应并且通用的accelerated segment test。对FAST 9-16 detector提速约13%，对FAST 7-12 detector提速最高30%，对FAST 5-8 detector提速最高50%。

2011年， Leutenegger在BRISK描述子[6]中提出multi-scale AGAST detector, 并用实验证明与SURF detector有等效的可重复性(equivalentrepeatability)。对Graffiti序列的第一幅图检测时间为17.20ms,约为SURF detector消耗时间的16%，SIFT detector消耗时间的1%.

参考文献详见OpenCV特征点提取----Fast特征 - 吴一达 - 博客园 (cnblogs.com)

5. BRIEF特征点检测（2010）

BRIEF特征提取(理解篇)

BRIEF是一种特征描述子提取算法，并非特征点的提取算法，一种生成二值化描述子的算法，不提取代价低，匹配只需要使用简单的汉明距离(Hamming Distance)利用比特之间的异或操作就可以完成。因此，时间代价低，空间代价低，效果还挺好是最大的优点。

5.1 概述

由于BRIEF仅仅是特征描述子，所以事先要得到特征点的位置，可以利用FAST特征点检测算法或Harris角点检测算法或SIFT、SURF等算法检测特征点的位置。接下来在特征点邻域利用BRIEF算法建立特征描述符。

算法步骤如下：

1. 为减少噪声干扰，先对图像进行高斯滤波（方差为2，高斯窗口为9x9，原文认为方差在$1<\sigma <3$时，辨识率效果好）。

2. 以特征点为中心，取SxS的邻域窗口。在窗口内随机选取一对（两个）点，比较二者像素的大小，进行如下二进制赋值。（原文取S=31）

   

   $\tau(p|x,y)= \begin{cases} 1&,p(x)<p(y)\\ 0&,otherwise \end{cases}$

   其中，p(x),p(y)分别是随机点x=(u1,v1),y=(u2,v2)的像素值。

3. 在窗口中随机选取N对随机点，重复步骤2的二进制赋值，形成一个二进制编码，这个编码就是对特征点的描述，即特征描述子。（一般N=256）

其中对于随机点的选择方法有：

1. $x_i,y_i$都是均匀分布[-S/2,S/2]
2. $x_i,y_i$都是高斯分布[0,$S^2$/25]
3. $x_i$服从高斯分布[0,$S^2$/25]，$y_i$服从高斯分布[$x_i,S^2/100$]，采样分为两步：先在原点处为$x_i$进行高斯采样，然后以$x_i$为中心对$y_i$进行高斯采样
4. $x_i,y_i$在空间量化极坐标下的离散位置处进行随机采样
5. $x_i=(0,0)^T,y_i$在空间量化极坐标下的离散位置处进行随机采样

原文作者测试后发现方法2的效果最好

下图是五种方法生成的点对

计算$n_d$维的特征点描述子：

$f_{n_d}(p)=\sum_{1\leq i\leq n_d}2^{i-1}\tau(p|x_i,y_i)$

其中，$n_d$为点对数（描述子位数），一般取128，256，512。（原作者通过实验发现取512效果最好）

经过大量实验数据测试，不匹配特征点的描述子的Hamming距离在128左右，匹配点对描述子的Hamming距离则远小于128。（256位为例）

5.2 总结

优点：

1. 占用内存小
2. 具有很好的辨别性能
3. 运行时间短

缺点：

1. 不具备旋转不变性（角度大于30时，效果极差）
2. 不具备尺度不变性
3. 对噪声敏感

总结：

1. BRIEF抛弃了传统的用梯度直方图描述区域的方法，改用检测随机响应，大大加快了描述子建立速度；生成的二进制描述子便于高速匹配（计算Hamming距离只需通过异或操作加上统计二进制编码中“1”的个数的操作，即两个字符串对应位置的不同字符的个数，这些通过底层的运算即可实现），且便于在硬件上实现。其次、本描述子的缺点很明显就是旋转不变性较差，需要通过新的方法来改进。
2. 结果比较：第一、在旋转不是非常厉害的图像里，用BRIEF生成的描述子的匹配质量非常高，作者测试的大多数情况中都超越了SURF。但在旋转大于30°后，BRIEF的匹配率快速降到0左右；第二、BRIEF的耗时非常短，在相同情形下计算512个特征点的描述子时，SURF耗时335ms,BRIEF仅8.18ms；匹配SURF描述子需28.3ms，BRIEF仅需2.19ms。在要求不太高的情形下，BRIEF描述子更容易做到实时。
3. 虽然文章说x,y点是随机选择的，但是OpenCV中源码实现时，y是通过x的值通过一个公式计算出的
4. 实现旋转不变性的本质就是：先计算关键点的主方向，然后将窗口的u轴旋转到主方向上，即可实现旋转不变性。本质就是寻找基准方向，进行旋转操作也会加入一定的计算量。

6. BRISK特征提取算法（2011）

【特征检测】BRISK特征提取算法

BRISK算法是2011年ICCV上《BRISK:Binary Robust Invariant Scalable Keypoints》文章中，提出来的一种特征提取算法，也是一种二进制的特征描述算子。

它具有较好的旋转不变性、尺度不变性，较好的鲁棒性等。在图像配准应用中，速度比较：SIFT<SURF<BRISK<FREAK<ORB，在对有较大模糊的图像配准时，BRISK算法在其中表现最为出色。

6.1 特征点检测

BRISK算法主要利用FAST9-16进行特征点检测，要解决尺度不变性，就必须在尺度空间进行特征点检测，于是BRISK算法中构造了图像金字塔进行多尺度表达。

6.1.1 建立尺度空间

构造n个octave层（用ci表示）和n个intra-octave层（用di表示），文章中n=4，i={0,1,…,n-1}。假设有图像img，octave层的产生：c0层就是img原图像，c1层是c0层的2倍下采样，c2层是c1层的2倍下采样，以此类推。intra-octave层的产生：d0层是img的1.5倍下采样，d1层是d0层的2倍下采样（即img的2*1.5倍下采样），d2层是d1层的2倍下采样，以此类推。

则ci、di层与原图像的尺度关系用t表示为：$t(c_i)=2^i,t(d_i)=2^i\times1.5$

所以ci、di层与原图像的大小关系为：

由于n=4，所以一共可以得到8张图，octave层之间尺度（缩放因子）是2倍关系，intra-octave层之间尺度（缩放因子）也是2倍关系。

6.1.2 寻找特征点

对这8张图进行FAST9-16角点检测，得到具有角点信息的8张图，对原图像img进行一次FAST5-8角点检测（当做d(-1)层，虚拟层），总共会得到9幅有角点信息的图像。

6.1.3 非极大值抑制

对这9幅图像，进行空间上的非极大值抑制（同SIFT算法的非极大值抑制）：特征点在位置空间（8邻域点）和尺度空间（上下层2x9个点），共26个邻域点的FAST的得分值要最大，否则不能当做特征点；此时得到的极值点还比较粗糙，需要进一步精确定位。

6.1.4 亚像素插值

进过上面步骤，得到了图像特征点的位置和尺度，在极值点所在层及其上下层所对应的位置，对FAST得分值（共3个）进行二维二次函数插值（x、y方向），得到真正意义上的得分极值点及其精确的坐标位置（作为特征点位置）；再对尺度方向进行一维插值，得到极值点所对应的尺度（作为特征点尺度）。

6.2 特征点描述

现在已经得到了特征点的位置和尺度（t），接下来要对特征点计算其描述符。

6.2.1 高斯滤波

均匀采样模式：以特征点为中心，构建不同半径的同心圆，在每个圆上获取一定数目的等间隔采样点（所有采样点包括特征点，一共N个），由于这种邻域采样模式会引起混叠效应，所以需要对同心圆上的采样点进行高斯滤波。

采样模式如下图，蓝圈表示；以采样点为中心，$\sigma$为方差进行高斯滤波，滤波半径大小与高斯方差的大小成正比，红圈表示。最终用到的N个采样点是经过高斯平滑后的采样点。下图是尺度t=1时的。（文章中：N=60)

6.2.2 局部梯度计算（算主方向）

由于有N个采样点，则采样点两两组合成一对，共有N(N-1)/2钟组合方式，所有组合方式的集合称作采样点对，用集合$A={(p_i,p_j)\in \R^2\times\R2|i<N\and j<i\and\ i,j\in\N} $表示,其中像素分别是$I(P_i,\sigma_i)、I(p_j,\sigma_j)$,$\sigma$表示尺度。用$g(p_i,p_j)$表示特征点局部梯度集合，则有：

$g(p_i,p_j)=(p_j-p_i)\times \frac{I(p_j,\sigma_j)-I(p_i,\sigma_i)}{\lVert p_j-p_i\rVert^2 }$

定义短距离点对子集、长距离点对子集（L个）：

其中，$\sigma_{max}=9.75t,\sigma_{min}=13.67t$，t是尺度

现在要利用上面得到的信息，来计算特征点的主方向（此处只用到了长距离子集L），如下：

6.2.3 特征描述符

要解决旋转不变性，则需要对特征点周围的采样区域进行旋转到主方向，旋转后得到新的采样区域，采样模式同上。BRISK描述子是二进制的特征，由采样点集合可得到N(N-1)/2对采样点对，就可以得到N(N-1)/2个距离的集合（包含长、短距离子集），考虑其中短距离子集中的512个短距离点对，进行二进制编码，判断方式如下：

其中，$I(p_j^\alpha,\sigma_j)$表示旋转$\alpha$角度后的，新的采样点。由此可得到，512Bit的二进制编码，也就是64个字节（BRISK64）。

6.3 匹配方法

汉明距离进行比较，与其他二进制描述子的匹配方式一样。

6.4 总结

BRISK是FAST和BRIEF的结合，具有较好的旋转不变性、尺度不变性，较好的鲁棒性等。在图像配准应用中，速度比较：SIFT<SURF<BRISK<FREAK<ORB，在对有较大模糊的图像配准时，BRISK算法在其中表现最为出色。

7. FREAK特征检测（2012）

【特征检测】FREAK特征提取算法

[ Freak特征描述+BruteForceMatcher匹配+RANSAC剔除误匹配_劲(https://blog.csdn.net/lcb_coconut/article/details/52145293)

基于FREAK特征描述子的分析、仿真与思考

FREAK算法是2012年CVPR上《FREAK: Fast Retina Keypoint》文章中，提出来的一种特征提取算法，也是一种二进制的特征描述算子。

与BRISK算法非常相似，是在BRISK算法上的改进，FREAK依然具有尺度不变性、旋转不变性、对噪声的鲁棒性等。

7.1 采样模式

在BRISK算法中，采样模式是均匀采样模式（在同一圆上等间隔的进行采样）；FREAK算法中，采样模式发生了改变，它采取了更为接近于人眼视网膜接收图像信息的采样模型。图中展示了人眼视网膜拓扑结构，Fovea区域主要是对高进度的图像信息进行处理，Para主要是对低精度的图像信息进行处理。采样点为：6、6、6、6、6、6、6、1，那个1是特征点。

从图中可以看出，该结构是由很多大小不同并有重叠的圆构成，最中心的点是特征点，其它圆心是采样点，采样点离特征点的距离越远，采样点圆的半径越大，也表示该圆内的高斯函数半径越大

7.2 特征描述

F表示二进制描述子，Pa是采样点对（与BRISK同理），N表示期望的二进制编码长度。

$I(P_a^{r_1})$表示采样点对Pa中前一个采样点的像素值，同理，$I(P_a^{r_2})$表示后一个采样点的像素值。

7.3 降维

当然得到特征点的二进制描述符后，也就算完成了特征提取。但是FREAK还提出，将得到的Nbit二进制描述子进行筛选，希望得到更好的，更具有辨识度的描述子，也就是说要从中去粗取精。（也就是降维）

1. 建立矩阵D，D的每一行是一个FREAK二进制描述符，即每一行有N个元素；在上图的采样模式中公有43个采样点，可以产生N=43*(43-1)/2=903个采样点对，也就是说矩阵D有903列
2. 对矩阵D的每一列计算其均值，由于D中元素都是0/1分布的，均值在0.5附近说明该列具有高的方差；
3. 每一列都有一个均值，以均值最接近0.5的排在第一位，均值离0.5越远的排在越靠后，对列进行排序；
4. 选取前512列作为最终的二进制描述符。(也可以是256、128、64、32等)

最终D的每一行仍然是一个特征点的描述符，只是更短小精悍而已，即降低了维度。

由于FREAK描述符自身的圆形对称采样结构使其具有旋转不变性，采样的位置好半径随着尺度的变化使其具有尺度不变性，对每个采样点进行高斯模糊，也具有一定的抗噪性能，像素点的强度对比生成二进制描述子使其具有光照不变性。因此由上述产生的二进制描述子可以用来进行特征匹配。在匹配之前，再补充一下特征点的方向信息。

7.4 特征方向

由于特征点周围有43个采样点，可产生43*(43-1)/2=903个采样点对，FREAK算法选取其中45个长的、对称的采样点对来提取特征点的方向，采样点对如下：

用O表示局部梯度信息，M表示采样点对个数，G表示采样点对集合，Po表示采样点对的位置，则：

同BRISK算法，可得到特征点的方向。

7.5 特征匹配

在特征描述中，我们得到了512bit的二进制描述符，该描述符的列是高方差——>低方差的排列，而高方差表征了模糊信息，低方差表征了细节信息，与人眼视网膜相似，人眼先处理的是模糊信息，再处理细节信息。因此，选取前128bit即16bytes进行匹配（异或），若两个待匹配的特征点前16bytes距离小于设定的阈值，则再用剩余的位信息进行匹配。这种方法可以剔除掉90%的不相关匹配点。注意：这里的16bytes的选取是建立在并行处理技术（SIMD）上的，并行处理技术处理16bytes与处理1bytes的时间相同；也就是说，16bytes并不是固定的，如果并行处理技术能处理32bytes与处理1bytes的时间相同的话，那么也可以选取前32bytes。

7.6 总结

FREAK是在BRISK的基础上进行的改进，具备BRISK的所有优点，而且在BRISK的基础上对特征描述进行了降维处理，以便于对特征点匹配阶段进行加速。

现在采用的二进制描述算子在提高计算速度方面给出了不错的思路，但是采用FAST特征检测的鲁棒性并没有SIFT那么强，因此导致使用FAST的FREAK没有使用SIFT的强，但是在有的论文中提出FREAK的综合性能更好（有待验证）。

8. ORB（2011）

特征点检测-ORB

ORB（Oriented FAST and Rotated BRIEF）是Oriented FAST + Rotated BRIEF的缩写（感觉应该叫OFRB）。是目前最快速稳定的特征点检测和提取算法，许多图像拼接和目标追踪技术利用ORB特征进行实现。

据论文中提供，ORB要比SIFT快两个数量级。

ORB是在FAST和BRIEF的基础上进行改进。

8.1 Oriented FAST

FAST快是快，但是无法体现出一个优良特征点的尺度不变性和旋转不变性。

Fast角点本不具有方向，由于特征点匹配需要，ORB对Fast角点进行了改进，改进后的 FAST 被称为 Oriented FAST，具有旋转和尺度的描述。

类比SIFT的处理方法：

1. 尺度不变性：可以用金字塔解决
2. 旋转不变性：可以用质心标定方向解决；

8.1.1 尺度不变性

和BRISK的处理方法一样

1. 对图像做不同尺度的高斯模糊
2. 对图像做降采样(隔点采样)
3. 对每层金字塔做FAST特征点检测
4. n幅不同比例的图像提取特征点总和作为这幅图像的oFAST特征点。

8.1.2 旋转不变性

引入了图像矩的概念

1、在一个小的图像块 B 中，定义图像块的矩。

$m_{pq}=\sum_{x,y}x^py^qI(x,y)$

2、通过矩可以找到图像块的质心

$C=(\frac{m_{10}}{m_{00}},\frac{m_{01}}{m_{00}})$

3、连接图像块的几何中心 O 与质心 C，得到一个方向向量$\vec{OC}$ ，这就是特征点的方向

$\theta=atan2(m_{01},m_{10})$

实验表明，灰度质心在人工旋转噪声影响下，与直方图算法和MAX算法相比，具有最好的恢复主方向的性能。

8.2 Rotated BRIEF

8.2.1 预处理

1. ORB算法进一步增强描述子的抗噪能力，采用积分图像来进行平滑；
2. 在特征点的31x31邻域内，产生随机点对，并以随机点为中心，取5x5的子窗口。
3. 比较两个随机点的子窗口内25个像素的大小进行编码（而不仅仅是两个随机点了）

8.2.2 为BRIEF增加旋转不变性（Steered BRIEF）

ORB算法采用关键点的主方向来旋转BEIEF描述子。

1. 对于任意特征点，在31x31邻域内位置为$(x_i,y_i)$ 的n对点集，可以用2 x n的矩阵来表示：

   

2. 利用FAST求出的特征点的主方向$\theta$和对应的旋转矩阵 $R_\theta$，算出旋转的$S_\theta$来代表$S$：

   

3. 计算旋转描述子（steered BRIEF）：

   

使用steeredBRIEF方法得到的特征描述子具有旋转不变性，但是却在描述符的可区分性（或相关性）上不如BRIEF。

8.2.3 rBRIEF-改进特征点描述子的相关性

原始的BRIEF算法有5种去点对的方法，原文作者使用了方法2。为了解决描述子的可区分性和相关性的问题，ORB论文中没有使用5种方法中的任意一种，而是使用统计学习的方法来重新选择点对集合。

8.2.3.1 建立300k个特征点测试集

对于测试集中的每个点，预处理参考第一个步骤。考虑其31x31邻域。这里不同于原始BRIEF算法的地方是，这里在对图像进行高斯平滑之后，使用邻域中的某个点的5x5邻域灰度平均值来代替某个点对的值，进而比较点对的大小。这样特征值更加具备抗噪性。另外可以使用积分图像加快求取5x5邻域灰度平均值的速度。

8.2.3.2 特征点选取

从上面可知，在31 x 31的邻域内共有(31-5+1)x(31-5+1)=729个这样的子窗口，那么取点对的方法共有M=205590种，我们就要在这Ｍ种方法中选取256种取法，选择的原则是这256种取法之间的相关性最小。

步骤如下：

1. 在300k特征点的每个31x31邻域内按M种方法取点对，比较点对大小，形成一个300k x M的二进制矩阵Q。矩阵的每一列代表300k个点按某种取法得到的二进制数。
2. 对Q矩阵的每一列求取平均值，按照平均值到0.5的距离大小重新对Q矩阵的列向量排序，形成矩阵T。
3. 将T的第一列向量放到R中
4. 取T的下一列向量和R中的所有列向量计算相关性，如果相关系数小于设定的阈值，则将T中的该列向量移至R中。
5. 按照第四步的方式不断进行操作，直到R中的向量数量为256。

通过这种方法就选取了这256种取点对的方法。这个算法是对均值靠近0.5的不相关测试进行贪婪搜索，结果称为rBRIEF。rBRIEF在方差和相关性上与旋转BRIEF相比有明显进步。

8.3 总结

1. FAST是用来寻找特征点的。ORB在FAST基础上通过金字塔、质心标定解决了尺度不变和旋转不变。即oFAST。
2. BRIEF是用来构造描述子的。ORB在BRIEF基础上通过引入oFAST的旋转角度和机器学习解决了旋转特性和特征点难以区分的问题。即rBRIEF。

各种二进制特征提取算子（ORB 、BRIEF 、 FREAK、 BRISK）

ORB解决了BRIEF的旋转不变性和对噪声敏感的问题：

1. 对于旋转不变性：

   在ORB的方案中，特征点的主方向是通过矩（moment）计算而来。有了主方向之后，就可以依据该主方向提取BRIEF描述子。但是由此带来的问题是，由于主方向会发生变化，随机点对的相关性会比较大，从而降低描述子的判别性。解决方案也很直接，采取贪婪的，穷举的方法，暴力找到相关性较低的随机点对。

2. 对于噪声敏感：

   BRIEF使用的是pixel跟pixel的大小来构造描述子的每一个bit；这样的后果就是对噪声敏感。ORB的方案中，做了这样的改进，不再使用pixel-pair，而是使用9×9(5x5)的patch-pair，也就是说，对比patch的像素值之和。（可以通过积分图快速计算）。

3. 对于尺度不变性:

   ORB没有试图解决尺度不变性，（因为FAST本身就不具有尺度不变性。）但是这样只求速度的特征描述子，一般都是应用在实时的视频处理中的，这样的话就可以通过跟踪还有一些启发式的策略来解决尺度不变性的问题。

4. 关于计算速度：

   ORB是sift的100倍，是surf的10倍。

补充

1、尺度空间函数求导（有限差分法求导）

2、汉明距离

汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。