sift算法提取特征点

‘壹’ sift算法是什么

Sift算法是David Lowe于1999年提出的局部特征描述子，并于2004年进行了更深入的发展和完善。Sift特征匹配算法可以处理两幅图像之间发生平移、旋转、仿射变换情况下的匹配问题，具有很强的匹配能力。

这一算法的灵感也十分的直观，人眼观测两张图片是否匹配时会注意到其中的典型区域（特征点部分），如果我们能够实现这一特征点区域提取过程，再对所提取到的区域进行描述就可以实现特征匹配了。

sift算法的应用

SIFT算法目前在军事、工业和民用方面都得到了不同程度的应用，其应用已经渗透了很多领域，典型的应用如下：物体识别；机器人定位与导航；图像拼接；三维建模；手势识别；视频跟踪；笔记鉴定；指纹与人脸识别；犯罪现场特征提取。

‘贰’ 图像特征之SIFT特征匹配

SIFT具有尺度不变性和旋转不变性。具体分为：

尺度规范化的Laplacian of Gaussian(LoG)算子具有尺度不变性。在具体实现中，可用Difference of Gaussian(DoG)算子近似LoG算子，在构建的尺度空间中检测稳定的特征点。

因此尺度空间的构架包含：

sigma越大丢失的高频越多

每个像素要和周围的26个像素比较，确定它是当前尺度下，相邻频率信息的一个峰值。

为什么要精确定位，因为我们这个不论是x、y、sigma方向上都是离散的，要在连续的变化上求得极值点。

DoG函数D(X)=D(x,y,σ)在尺度空间的的Taylor展开式为：

令D(X)导数为0，得到极值点的偏移量：

若X^=(x,y,σ)T在任意一个维度大于0.5，说明极值点精确位置距离另一个点更近，应该改变当前关键点的位置，定位到新点后执行相同操作，若迭代5次仍不收敛，则认为该检测点不为关键点。精确关键点处函数值为：

|D(X^)|过小易受噪声点的干扰而变得不稳定，若其小于某个阈值(例如0.03或者0.04/S)，则将该极值点删除旅哪。

为了得到稳定的特征点，只是删除DoG响应值低的点是不够的。由于DoG对图像中的边缘有比较强的响应值，而一旦特征点落在图像的边缘上，这些点就是不稳定的点。一方面图像边缘上的点是很难定位的，具有定位歧义性；另一方面这样的点很容易受到噪声的干扰而变得不稳定。

一个平坦的DoG响应峰值往往在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。而主曲率可以通过2×2的Hessian矩阵H求出

D 的主曲率和H的特征值成正比，令α为较大特征值，β为较小特征值，且α/β=r，则

(r+1)2/r在两个特征值相等时最小，随着r的增大而增大，r值越大，说明两个特征值的比值越大，正好对应边缘的情况。因此，设定一个阈值rt，若满足

则认为该关键点不是边缘，否则予以剔除。

好了，到这一步，我们已经完成了特征点的筛选，并且通过高斯金字塔的设计实现了尺度不变性。接下来，就该去搞定旋转不变性了。

这里的旋转不变性跟咱们角点自带的旋转不变性有一些不同。Harris的角点不变性靠的是旋转后，该是角点的轿乎地方还是角点，所以对于整张图对应的所有角点这个尺度看，它是具备旋转不变性的。但是SIFT中，我们希望给每个特征点赋值一个方向，这样，对于单个特征点来说，不管是如何缩放、旋转，这个方向作为它的一个属性都不会变。

为了使特征描述子具有旋转不变性，需要利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数。对于在DoG金字塔中检测出的关键点，在其所在高斯金字塔图像的3σ邻域窗口内计算每个像素的梯度幅值和方向，公式如下：

L为关键点所在尺度空间的灰度值，m(x,y)为梯度拆帆码幅值，θ(x,y)为梯度方向。对窗口内的像素的模值m(x,y)按σ=1.5σoct、邻域窗口为3σ=3×1.5σoct的高斯分布加权。

在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向，梯度直方图将梯度方向(0,360∘)分为36柱(bins)，如下图所示，直方图的峰值所在的方向代表了该关键点的主方向。

梯度方向直方图的峰值代表了该特征点处邻域梯度的主方向，为了增强鲁棒性，保留峰值大于主方向峰值80%的方向作为该关键点的辅方向，因此，在相同位置和尺度，将会有多个关键点被创建但方向不同，可以提高特征点匹配的稳定性。

至此，将检测出的含有位置、尺度和方向的关键点即是该图像的SIFT特征点。

是用128维向量对每个关键点进行描述。

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

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

特征描述子与特征点所在的尺度有关，因此，对梯度的求取应在特征点对应的高斯图像上进行。将关键点附近的邻域划分为d*d(Lowe建议d=4)个子区域，每个子区域做为一个种子点，每个种子点有8个方向。每个子区域的大小与关键点方向分配时相同。

每一个小格都代表了特征点邻域所在的尺度空间的一个像素 ，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在4×4的窗口内计算8个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点。

这样两幅图的特征坐标系都是以关键点的方向为准了，旋转不变性。

如上统计的4 4 8=128个梯度信息即为该关键点的特征向量。特征向量形成后，为了去除光照变化的影响，需要对它们进行归一化处理，对于图像灰度值整体漂移，图像各点的梯度是邻域像素相减得到，所以也能去除。

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

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

对两幅图像中检测到的特征点，可采用特征向量的欧式距离作为特征点相似性的度量，取图像1中某个关键点，并在图像2中找到与其距离最近的两个关键点，若最近距离与次近距离的比值小于某个阈值，则认为距离最近的这一对关键点为匹配点。降低比例阈值，SIFT匹配点数量会减少，但相对而言会更加稳定。阈值ratio的取值范围一般为0.4~0.6。

SIFT是一种检测、描述、匹配图像局部特征点的算法，通过在尺度空间中检测极值点，提取位置、尺度、旋转不变量，并抽象成特征向量加以描述，最后用于图像特征点的匹配。SIFT特征对灰度、对比度变换、旋转、尺度缩放等保持不变性，对视角变化、仿射变化、噪声也具有一定的鲁棒性。但其实时性不高，对边缘光滑的目标无法准确提取特征点

旋转不变性是计算关键点方向并旋转得到的；尺度不变性是图像下采样获得高斯金字塔得到的。

‘叁’ SIFT算法提取特征点，怎样得到正确的特征点空间坐标，网上实现的程序里loc(i,1),loc(i,2)说是特征点的坐标

为了更加准确，大卫劳氏推荐用了subpixel也就是子像素坐标，
但是这里的话你直接取整形就是了。
有warning能通了不就行了？

‘肆’ sift特征向量的维数

基于不变量技术的特征检测方法的基础上，提出的一种基于尺度空间的、对图像缩放、旋转、仿射变换、光照变化保持稳定性的图像局部特征描述算法-SIFT算子。SIFT特征点向量的生成由以下四步骤组成：1、在尺度空间中检测极值点；2、去除低对比度的极值点和不稳定的边缘极值点，得到特征点；3、计算特征点的方向参数；4、生成SIFT特征点向量，向量维数一般为128维。运用SIFT算法提取的SIFT特征点向量具有如下优点：1、SIFT特征是图像的局部特征，对旋转、尺度缩放、亮度变化保持不变化性，对视角变化、仿射变换、噪音也保持一定程度的稳定性；2、独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；3、多量性，即使少数的几个物体也可以产生大量SIFT特征向量。现有的SIFT算法具有一定的缺陷，对于图像的检测效率和检测精度较差。
技术实现思路
有鉴于此，本专利技术实施例的目的在于提供一种基于改进SIFT的图像特征检测方法及装置，以解决上述技术问题。第一方面，本专利技术实施例提供了一种基于改进S...

【技术保护点】
1.一种基于改进SIFT的图像特征检测方法，其特征在于，包括：获取待检测图像和对应的标准图像；利用尺度不变特征变换SIFT算法对所述待检测图像和所述标准图像进行图像匹配，获得多对匹配点；计算所述匹配点之间的邻域直径比和方向角度差；根据所述邻域直径比和所述方向角度差对所述匹配点进行剔除，获得正确匹配点，以获得所述待检测图像中的特征。

‘伍’ 图像特征提取-SIFT

滤波一般指就是一个二维矩阵（卷积核），卷积就是用这个矩阵与原图像进行卷积运算得到一个新的图像。

尺度是一个视觉问题，不是数学问题，简单的来讲就是你在不同距离上观察一个物体，产生的视觉感受是不同的。比如你站在不同距离观察一片雪花，离的越远你感受的形状越接近于a->b->c->d的顺序，就是越远，你看到的越是一个大概的轮廓。

一幅图像的SIFT特征提取，分为4个步骤：

SIFT特征点其实就是尺度空间中稳定的点/极值点，那么，为了得到这些稳定点

对于一幅输入图像，为了进行sift特征检测、实现scale-invariant（任何尺度下都能够有对应的特征点），需要对该图像的尺度空间进行分析，即建立高斯金字塔图像、得到不同scale的图像，这里的高斯金字塔与最原始的高斯金字塔稍微有点区别，因为它在构造尺度空间时，将这些不同尺度图像分为了多个Octave、每个Octave又分为了多层。下图给出了Sift中的高斯金字塔的结构图；

构造完尺度空间（差分高斯金字塔）后，接下来的任务就是“在尺友友宽度中间中检测出图像中的稳定特征点”：

对于DoG中每一个采样点（每一个Octave中每一层），将其与它邻域内所有像素点（8+18=26）进行比较，判断其是否为局部极值点（极大或者极小），更加具体地：如下图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。但要注意：这种相邻层之间的极值点的寻找是在同一Octave中的相邻尺度之间进行寻找的，而不要跨组！

通过拟和“三维二次函数”可以精确确定关键点的位置和尺度（达到亚告猜像素精度），具体方法还未知，可以得到一系列的SIFT候选特征点集合，但由于这些关好亮键点中有些具有较低的对比对，有些输属于不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，所以，为了增强匹配稳定性、提高抗噪声能力，应该将这2类关键点去除，实现对候选SIFT特征点集合的进一步净化：

上面只是得到了每个关键点的方向，接下来，需要确定每个关键点的特征向量，具体方式如下：

现有A、B两幅图像，分别利用上面的方法从各幅图像中提取到了k1个sift特征点和k2个特征点及其对应的特征描述子，即k1 * 128维和k2 * 128维的特征，现在需要将两图中各个scale（所有scale）的描述子进行匹配。
接下来采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。

[1] SIFT特征提取及匹配
[2] 图像处理之特征提取

‘陆’ OpenCV-Python之——图像SIFT特征提取

在一定的范围内，无论物体是大还是小，人眼都可以分辨出来。然而计算机要有相同的能力却不是那么的容易，在未知的场景中，计算机视觉并不能提供物体的尺度大小，其中的一种方法是把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中，要考虑的就是在图像在不同的尺度下都存在的特征点。

在早期图像的多尺度通常使用图像金字塔表示形式。图像金字塔是同一图像在不同的分辨率下得到的一组结果其生成过程一般包括两个步骤：

多分辨率的图像金字塔虽然生成简单，但其本质是降采样，图像的局部特征则难以保持，也就是无法保持特征的尺度不变性。

我们还可以通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间，使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。

构建尺度空间的目的是为了检测出在不同的尺度下都存在的特征点，而检测特征点较好的算子是Δ^2G(高斯拉普拉斯，LoG)
使用LoG虽然能较好的检测到图像中的特征点，但是其运算量过大，通常可使用DoG（差分高斯，Difference of Gaussina）来近似计算LoG。

从上式可以知道，将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。为了得到DoG图像，先要构建高斯尺度空间，而高斯的尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数σ进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。
如下图，octave间是降采样关系，且octave(i+1)的第一张（从下往上数）图像是由octave(i)中德倒数第三张图像降采样得到。octave内的图像大小一样，只是高斯模糊使用的尺度参数不同。

对于一幅图像，建立其在不同尺度scale下的图像，也称为octave，这是为了scale-invariant，也就是在任何尺度都能有对应的特征点。下图中右侧的DoG就是我们构建的尺度空间。

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。下图中将叉号点要比较的26个点都标为了绿色。

找到所有特征点后， 要去除低对比度和不稳定的边缘效应的点 ，留下具有代表性的关键点（比如，正方形旋转后变为菱形，如果用边缘做识别，4条边就完全不一样，就会错误；如果用角点识别，则稳定一些）。去除这些点的好处是增强匹配的抗噪能力和稳定性。最后，对离散的点做曲线拟合，得到精确的关键点的位置和尺度信息。

近来不断有人改进，其中最着名的有 SURF（计算量小，运算速度快，提取的特征点几乎与SIFT相同）和 CSIFT（彩色尺度特征不变变换，顾名思义，可以解决基于彩色图像的SIFT问题）。

其中sift.detectAndCompute()函数返回kp，des。

上图dog的shape为(481, 500, 3)，提取的特征向量des的shape为(501, 128)，501个128维的特征点。

该方法可以在特征点处绘制一个小圆圈。

https://blog.csdn.net/happyer88/article/details/45817305
https://www.jianshu.com/p/d94e558ebe26
https://www.cnblogs.com/wangguchangqing/p/4853263.html

‘柒’ SIFT特征

参考了几位大佬的博文：

参考1

参考2

SIFT特征也叫做尺度不变特征，SIFT特征最后是把输入的图像表现成为以128维的特征向量集合，SIFT特征具有 旋转，缩放，平移，光照 不变形，SIFT特征检测的步骤：

1. 尺度空间的极值检测：高斯金字塔->DOG->极值检测

2. 关键点的准确定位：二阶泰勒展开+边缘点过滤

3. 关键点主方向确定

4. 生成特征向量

目的：我们的目的是要找到一些特征，这些特征具有尺度不变形，也就是说一张图在不同的尺寸下面，我们仍然可以找到这些特征

方法：我们可以通过对图像连续的尺度变化，生成图像的尺度空间，具体的做法就是对图像进行多次的高斯模糊，为什么用高斯核呢，因为高斯核：是唯一可以产生多尺度的核，那么在这里，我们其实也可以直接通过计算图像的二阶导数，可以在不同尺度下找到比较稳定的极值点（图像的高斯拉普拉斯算子LOG），但是LOG的计算复杂，我们可以通过计算高斯差分（DOG）的方法来近似LOG，下面是证明过程

高斯函数：

LOG(高斯拉普拉斯算子LoG(Laplacian of Gaussian):

再看DOG：

 --(1)

同时：

--(2)

令(1)=(2)，可得：

以上可以证明，我们可以用DOG来近似LOG

其中Octave成为组，组数一般取4，但实际上跟输入图像的大小(M*N)有关

每一个组中的层数s，一般为3～5，模型的初始参数 ，高斯金字塔的形成过程是这样的：

1. 由原始的输入图像开始进行高斯模糊，生成第0组的隔层图像  ,其逗指中

2. 第1组的的第0层图像由第0组的倒数第三层图像下采样得到，第0层的倒数第三层图像：

所以第1组的第0层图像尺度为： ,于是我们可以得到规律，第o组的第r层图像相对于输入的图像的尺度可以用用下面的计算公式得到：

3. 之后就可以根据高斯金字塔，计算DOG，也就是根据高斯金字塔连续的两层相减得到，若高斯金字塔中的一组有s+2 层，那么DOG对应的组就有s+2层

4. 最后计算尺度空间的极值点，对于每个点，对比其周围的8个点以及上下两层的共18个点，如果是最大值/最小值，则被选定为极值点

上一部找到的极值点是在离散空间找到的，离散空间的极值点并不一定是真真的连续空间的极值点，对此我们可以对尺度空间的DOG函数函数进行曲线拟合，从而找到极值点的更准确的定位，同时我们还需要对边缘位置进行处理提高关键点的稳定性。

利用已知的离散空间点插值得到的连续空间极值点的方法叫做子像素插值，利用尺度空间DOG函数山腊配进行曲线拟合，然后对其函数利用泰勒展开式，求得一个偏移量，从而实现对行（x），列（y）以及尺度（sigma）进行修正，一般认为，偏移量小于0.5则调整完毕.

之后我们还要对边缘点进行过滤，SIFT认为边缘点容易受到噪音的影响，因此需要剔除，对于边缘点的检测是通过曲率来判读的，边缘点在横跨边缘的地方曲率较大，而在垂直边缘的方向有较小的曲率，候选特征点的曲率与2*2的海森矩阵的特征值成正比,可以通过以下的公式进行筛选：

其中Tr表示海森矩阵对角线元素之和，Det表示海森矩阵的行列式，Tgamma表示一个阀值，默认取10，如果上式成立，那我们就可以剔除该候选关键点

上面找到的关键点保证了尺度不变形，为了实现旋转不变形，我们需要给特征点的方向进行赋值，利用特征点周围的像素点的梯度分布，统计生成一个梯度直方图从而方便来确定特征点的主方向，我们上面已经找到了特征点的尺度，那也就可以得到特征点所在的尺度图像：

对于一个特征点，我们要去计算以该特征点为中心， 为半径的区域内的像素点的梯度向量的幅度和方向：

之后统计一个梯度直方图，我们以10度为一个bin，共分了36个bin，每个采样点按照其梯度方向加权统计到直方图中，权重为幅度m和贡献因子的乘积，贡献因子是采样点到关键点的距离的反比。

当直方图确定以后，任何大于峰值80%的的方向，可以看作是该特征点的辅助方向，以此来提高匹配的稳定性。 最后我们可以用方向的峰值和左右两个幅值拟合二次曲线，来更准确的定位峰值的位置。

通过之前的步骤，我们已经得到了特征点的尺度，位置已局州经方向信息，这一步我们需要用一个特征向量来表示它。我们可以通过三步来生成特征向量：

我们以关键点为中心，取一个16*16的window，对于里面的每一个像素点，我们都要计算其幅度和角度，然后我们以4*4作为一个种子点，把里面的像素点的梯度进行统计并生成一个梯度直方图，对于每一个梯度直方图，我们以45度作为一个bin在360度的范围内共有8个方向区间，于是，对每个关键点，我们取4*4共16个种子点来描述，每个描述子由8个方向的梯度信息，所以对于每个特征点，我们生成了一个4*4*8=128维的向量

最后我们对生成的特征向量进行归一化处理，该处理可以去除光照的影响

通过SIFT提取的特征有着旋转平移不变形，尺度不变形，光照不变形，其中：

1. 旋转不变形是因为在生成特征向量之前，我们需要将坐标轴做一个映射使其旋转到主方向，因此有了一定的旋转不变形

2. 平移不变形是因为SIFT在计算特征向量的时候，提取关键点周围的区域的样本点，所以如果该特征点移动到任何处于该区域内的位置都可以被提取出来，这就有点像CNN中的pooling

3. 尺度不变形是首先因为我们通过DOG拟合LOG，而LOG又经前人的证明可以在不同尺度下检测到图像的特征，其次通过DOG我们可以拟合出来不同的尺度的情况，在这种情况下求出来的关键点，自然是具有尺度不变形的

4.光照不变形是因为我们对最后的特征向量进行了归一化

1. SIFT高度依赖局部区域像素的梯度，有可能这个区域取得不合适，导致我们找的主方向不准确，从而导致计算出来的特征向量误差很大，从而不能成功匹配

2. 另外我们在进行SIFT特征选取之前，可以看一下图像的像素值分布，如果像素值分布过于集中，那么SIFT的表现也不会很好，对此我们可以做一些图像均衡化的处理

‘捌’ 图像处理中sift特征可以用来进行训练吗

按理来说，任何特征都可以用于训练的。但是sift提取的是一个点，一个点进行训练，好像没啥意租槐义。一般来说，友型基都是用sift提取特征点，然后通过其他的匹配算法找到另一幅对好谨应点(比如：立体匹配)，然后重建三维等。

‘玖’ HartSift: 一种基于GPU的高准确性和实时SIFT

尺度不变特征变换 (SIFT) 是最流行和最强大的特征提取算法之一，因为它对尺度、旋转和光照保持不变。它已被广泛应用于视频跟踪、图像拼接、同时定位和映射（SLAM）、运动结构（SFM）等领域。然而，高计算复杂度限制了其在实时系统中的进一步应用。这些系统必须在准确性和性能之间进行权衡以实现实时特征提取。他们采用其他更快但精度较低的算法，如 SURF 和 PCA-SIFT。为了解决这个问题，本文提出了一种使用 CUDA 的 GPU 加速 SIFT，命名为 HartSift，充分利用单机CPU和GPU的计算资源，实现高精度、实时的特征提取。实验表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根据图像的大小在 3.14-10.57ms (94.61-318.47fps) 内处理图像。此外，HartSift 分别比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同时，HartSift 的性能和 CudaSIFT（迄今为止最快的 GPU 版本）的性能几乎相同，而 HartSift 的准确度远高于 CudaSIFT。

SIFT算法可以提取大量显着特征，这些特征在缩放、旋转、光照和3D视点保持不变，还提供了跨越噪声和仿射失真的稳健匹配。但SIFT的高计算复杂度限制了其在大规模数据和实时系统中的进一步应用。而复杂度较低的算法，如SURF、PCA-SIFT的准确性又不太高。因此，在主流计算平台上实现高精度、实时的SIFT是一个重要而有意义的研究课题。

而SIFT算法具有很好的并行性，可以正确移植到GPU上。因此，在配备GPU的异构计算系统上实现高性能的SIFT具有重要的实用价值。

SIFT 算法包含三个阶段，包括高斯差分（DoG）金字塔的构建、精确的关键点定位和 128 维描述符生成。由于每个阶段都有自己的并行特性，因此必须使用不同的并行粒度和优化来实现高性能。尤其是后两个阶段，负载不平衡不利于GPU优化，会导致性能下降。

本文的主要贡献和创新可以概括如下：

有许多工作尝试在GPU上使用SIFT算法。

然而，为了实现高性能，他们省略了 SIFT 算法的一些重要步骤，例如将输入图像加倍、保持尺度变化的连续性和拟合二次函数以定位准确的关键点信息。作者的实验表明，这些遗漏会导致 SIFT 丢失很多关键点和准确性。

Lowe将输入图像尺寸加倍作为高斯金字塔 的最底层，每个尺度 通过高斯卷积产生：

高斯金字塔确定之后，利用相同Octave的层级相减，得到差分金字塔：

其中 ，在本文中， .

检测尺度空间极值

将DoG金字塔每个像素与相邻像素比较，同层8个，上下层9个，若像素是局部最大值或局部最小值，将其视为关键点候选。

去除无效关键点

去除较低对比度和不稳定边缘响应的候选关键点，通过将3D二次函数拟合到附近数据执行子像素插值，以获取精确的位置、比例和主曲率比。

方向分配

将候选关键点周围的梯度累积到36 bins的直方图中，根据每层的尺度计算搜索半径。每个紧邻像素由一个高斯加权窗口加权，梯度方向累计到36 bins的方向直方图中。峰值为主要梯度方向，同时超过峰值80%的局部峰值bin也被视为关键点方向。

对关键点周围像素计算梯度直方图，搜索半径比上一步骤大得多，同样用一个高斯加权函数用于为每个邻居的梯度值分配权重。

根据梯度方向将最终的梯度值累积到一个 360-bin 的圆形方向直方图。最后，直方图将被归一化、平滑并转换为 128D 描述符。

构建金字塔应该保持顺序，以保证尺度空间变化连续性。Acharya和Bjorkman为加快这一过程，牺牲准确性打破构建顺序。考虑到不能使准确性降低，构建顺序在HartSift中保留。

分离卷积核

对于 大小的卷积核处理 大小的图像需要进行 次运算，如果将2D卷积核拆解为两个1D的卷积核，计算量减少至 . 通过使用共享内存和向量化方法，更容易实现合并全局内存访问并减少一维卷积的冗余访问。

Uber 内核

Uber内核将多个不同任务放到一个物理内核中，在一个内核中并行处理任务，而不需要在内核之间切换。差分金字塔第 层由高斯金字塔第 和第 层决定。将高斯差分金字塔和高斯卷积核封装在单个核中，可以充分挖掘并行性。

线程不需要重复读取高斯金字塔第 层的值，这是由于第 层的值计算完后，结果会放在寄存器内而不是全局内存中。借助Uber内核的优势，我们可以节省 的空间和 的内核运行时间

异构并行

HartSift 采用异构并行方法来加速这一阶段。CPU 和 GPU 将并行协作，构建 DoG 金字塔。

由于GPU处理小图像没有优势，作者将 以下的图像放到CPU处理，大图像放到GPU处理。用户也可以自行设置分离点，确保CPU和GPU负载平衡。

存在两个问题：

负载均衡

Warp是GPU最小并行执行单元，即以锁步方式执行的 32 个线程的集合。若负载不均衡，则warp执行时间取决于最后一个线程完成的时间，warp负载不均衡会导致GPU效率降低。

由于候选关键点分布的随机性，几乎所有经线都包含不同数量的空闲线程。如果这些warp继续处理以下部分，就会出现两个级别的负载不平衡.

在去除无效的候选关键点部分时，线程将进行亚像素插值以获得准确的候选关键点信息，从而去除具有低对比度或不稳定边缘响应的关键点候选。换句话说，一些线程会比其他线程更早返回一次。负载不平衡会变得更加严重。

为了突破性能瓶颈，HartSift 引入了重新平衡工作负载和多粒度并行优化。

重新平衡工作负载

当检测到负载不平衡时，HartSift 将通过启动具有适当粒度的新内核并分派每个具有 32 个活动线程的新经线来重新平衡工作负载。

此外，启动三个内核分别处理这三个部分，不仅可以重新平衡工作量，还可以根据不同部分的并行特性提供多粒度的并行。

多粒度并行

重新平衡工作负载优化保证每个内核中的线程和经线被完全加载，多粒度并行优化保证工作负载将平均分配到线程和经线。此外，不同内核的并行粒度取决于工作负载的特性。

HartSift通过将一个线程映射到一个或多个像素，采用与关键点候选检测部分和无效关键点去除部分并行的线程粒度。然而，线程粒度并行会导致方向分配部分的负载不平衡，因为不同关键点的相邻区域半径不同。线程粒度并行会为单个线程分配过多的工作，这在某些情况下限制了硬件资源的利用率。所以在这部分应用混合粒度并行：扭曲粒度构建直方图，线程粒度找出并将主导方向分配给相应的关键点。

基于扭曲的直方图算法

作者针对每个关键点提出了一种基于扭曲粒度和原子操作的高性能直方图算法，以充分利用局部性。

该阶段关键点的邻域半径远大于前一阶段。需要为每个关键点累积数千个邻居到一个 360-bin 直方图。如果采用前一阶段的基于原子扭曲的直方图算法，会对这一阶段的性能产生不同的影响。

HartSift引入了一种atomic-free的直方图算法，进一步提升了这一阶段的性能。

该算法包含三个步骤：

为了消除线程间的负载不平衡，实现全局合并访问，HartSift 使用一个warp 来处理一个keypoint 的所有邻居。当线程计算出它们的方向 bin 时，它们需要根据bin变量的值将梯度值累加到局部直方图。考虑到有如此多的邻居并且一个经线的一些线程可能具有相同的 bin，算法1引入了一种无原子的多键约简方法来累积每个经线的部分和。这种方法可以利用warp级shuffle和vote指令完全消除原子操作和本地同步。它根据bin对经纱的线程进行分组并指定每组具有最低车道的线程作为队长线程。队长线程将保存他们自己的 bin 的部分总和，并将它们并行地累积到驻留在共享内存中的本地直方图，而不会发生 bank 冲突和同步。在遍历所有邻居后，HartSift 将最终的局部直方图复制到驻留在全局内存中的全局直方图。

本文提出了一种GPU上的并行SIFT，命名为Hart-Sift，它可以在单机内同时使用CPU和GPU来实现高精度和实时的特征提取。HartSift根据每个阶段的不同特点，通过适当采用不同的优化策略来提升性能，例如负载均衡、基于warp的直方图算法和不同尺度样本的atomic-free直方图算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）内提取高精度特征，轻松满足高精度和实时性的苛刻要求。另外，与OpenCV-SIFT和SiftGPU相比，HartSift获得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分别。同时，HartSift 和 CudaSIFT 的性能几乎相同，但 HartSift 远比 CudaSIFT 准确。

‘拾’ OpenCV+Python特征提取算法与图像描述符之SIFT / SURF / ORB

算法效果比较博文

用于表示和量化图像的数字列表，简单理解成将图片转化为一个数字列表世灶表示。特征向量中用来描述图片的各种属性的向量称为特征矢量。

参考
是一种算法和方法，输入1个图像，返回多个特征向量（主要用来处理图像的局部，往往会把多个特征向量组成一个一维的向量）。主要用于图像匹配（视觉检测），匹配图像中的物品。

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

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

对现实中物体的描述一定要在一个十分重要的前提下进行，这个前提就是对自然界建模时的尺度。当用一个机器视觉系统分析未知场景时，计算机没有办法预先知道图像中物体的尺度，因此我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。图像的尺度空间表达指的是图像的所有尺度下的描述。

KeyPoint数据结构解析

SURF论文
原理
opencv官网解释
SURF是SIFT的加速版，它善于处理具有模糊和旋转的图像，但是不善于处理视角变化和光照变化。在SIFT中使用DoG对LoG进行近似，而在SURF中使用盒子滤波器对LoG进行近似，这样就可以使用积分图像了（计算图像中某个窗口内所有像素和时，计算量的大小与窗口大小无关）。总之，SURF最大的特点在于采用了Haar特征以及积分图改团像的概念，大大加快了程序的运行效率。

因为专利原因，OpenCV3.3开核返橘始不再免费开放SIFT\SURF，需要免费的请使用ORB算法

ORB算法综合了FAST角点检测算法和BRIEFF描述符。

算法原理
opencv官方文档
FAST只是一种特征点检测算法，并不涉及特征点的特征描述。

论文
opencv官方文档
中文版
Brief是Binary Robust Independent Elementary Features的缩写。这个特征描述子是由EPFL的Calonder在ECCV2010上提出的。主要思路就是在特征点附近随机选取若干点对，将这些点对的灰度值的大小，组合成一个二进制串，并将这个二进制串作为该特征点的特征描述子。文章同样提到，在此之前，需要选取合适的gaussian kernel对图像做平滑处理。

1：不具备旋转不变性。
2：对噪声敏感
3：不具备尺度不变性。

ORB论文
OpenCV官方文档

ORB采用了FAST作为特征点检测算子，特征点的主方向是通过矩（moment）计算而来解决了BRIEF不具备旋转不变性的问题。
ORB还做了这样的改进，不再使用pixel-pair，而是使用9×9的patch-pair，也就是说，对比patch的像素值之和，解决了BRIEF对噪声敏感的问题。
关于计算速度：
ORB是sift的100倍，是surf的10倍。

对图片数据、特征分布的一种统计
对数据空间(bin)进行量化

Kmeans

边缘：尺度问题->不同的标准差 捕捉到不同尺度的边缘
斑点 Blob：二阶高斯导数滤波LoG

关键点(keypoint)：不同视角图片之间的映射，图片配准、拼接、运动跟踪、物体识别、机器人导航、3D重建

SIFT\SURF