python实现sift算法

A. 如何计算sift每幅图像提取多少特征点

一、特征点（角点）匹配
图像匹配能够应用的场合非常多，如目标跟踪，检测，识别，图像拼接等，而角点匹配最核心的技术就要属角点匹配了，所谓角点匹配是指寻找两幅图像之间的特征像素点的对应关系，从而确定两幅图像的位置关系。
角点匹配可以分为以下四个步骤：
1、提取检测子：在两张待匹配的图像中寻找那些最容易识别的像素点（角点），比如纹理丰富的物体边缘点等。
2、提取描述子：对于检测出的角点，用一些数学上的特征对其进行描述，如梯度直方图，局部随机二值特征等。检测子和描述子的常用提取方法有：sift，harris，surf，fast，agast，brisk，freak，brisk，brief/orb等。
3、匹配：通过各个角点的描述子来判断它们在两张图像中的对应关系，常用方法如 flann等。
4、消噪：去除错误匹配的外点，保留正确的匹配点。常用方法有KDTREE，BBF，Ransac，GTM等。
二、SIFT匹配方法的提出
为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点，SIFT的作者Lowe提出了比较最近邻距离与次近邻距离的SIFT匹配方式：取一幅图像中的一个SIFT关键点，并找出其与另一幅图像中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离得到的比率ratio少于某个阈值T，则接受这一对匹配点。因为对于错误匹配，由于特征空间的高维性，相似的距离可能有大量其他的错误匹配，从而它的ratio值比较高。显然降低这个比例阈值T，SIFT匹配点数目会减少，但更加稳定，反之亦然。
Lowe推荐ratio的阈值为0.8，但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6 之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点，所以建议ratio的取值原则如下:
ratio=0. 4：对于准确度要求高的匹配；
ratio=0. 6：对于匹配点数目要求比较多的匹配；
ratio=0. 5：一般情况下。
三、常见的SIFT匹配代码
1、vlfeat中sift toolbox中的vl_ubcmatch.c使用的是普通的欧氏距离进行匹配（该SIFT代码贡献自Andrea
Vedaldi）。
2、Lowe的C++代码中使用的是欧氏距离，但是在matlab代码中为了加速计算，使用的是向量夹角来近似欧氏距离：先将128维SIFT特征向量归一化为单位向量（每个数除以平方和的平方根），然后点乘来得到向量夹角的余弦值，最后利用反余弦（acos函数）求取向量夹角。实验证明Lowe的办法正确率和耗时都很不错。
同样，也可以采用knnsearch函数求最近点和次近点：knnsearch采用euclidean距离时得到的结果与lowe采用的近似方法结果几乎一致，正好印证了模拟欧氏距离的效果。
3、Rob Hess的OpenSIFT采用了KDTREE来对匹配进行优化。
4、CSDN大神v_JULY_v实现了KDTREE+BBF对SIFT匹配的优化和消除错误匹配：从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 结构之法 算法之道 - 博客频道 - CSDN.NET。
5、OpenCV中features2d实现的SIFT匹配有多种matcher：VectorDescriptorMatcher，BFMatcher（Brute-force descriptor matcher），FernDescriptorMatcher，OneWayDescriptorMatcher，FlannBasedMatcher 等等。目前只知道采用knnsearch，提供了多种距离度量方式，具体区别不懂。

B. 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

C. sift算法是什么

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

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

sift算法的应用

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

D. 使用OpenCV和Python进行图像拼接

么是图像拼接呢？简单来说，对于输入应该有一组图像，输出是合成图像。同时，必须保留图像之间的逻辑流。

首先让我们了解图像拼接的概念。基本上，如果你想捕捉一个大的场景，你的相机只能提供一个特定分辨率的图像（如：640×480），这当然不足以捕捉大的全景。所以，我们可以做的是捕捉整个场景的多个图像，然后把所有的碎片放在一起，形成一个大的图像。这些有序的照片被称为全景。获取多幅图像并将其转换成全景图的整个过程称为图像拼接。

首先，需要安装opencv 3.4.2.16。

接下来我们将导入我们将在Python代码中使用的库：

在我们的教程中，我们将拍摄这张精美的照片，我们会将其分成两张左右两张照片，然后我们会尝试拍摄相同或非常相似的照片。

因此，我将此图像切成两个图像，它们会有某种重叠区域：

在此，我们将列出我们应采取的步骤，以取得最终的结果:

因此，从第一步开始，我们将导入这两个图像并将它们转换为灰度，如果您使用的是大图像，我建议您使用cv2.resize，因为如果您使用较旧的计算机，它可能会非常慢并且需要很长时间。如果要调整图像大小，即调整50％，只需将fx = 1更改为fx = 0.5即可。

我们还需要找出两幅图像中匹配的特征。我们将使用opencv_contrib的SIFT描述符。SIFT (Scale constant Feature Transform)是一种非常强大的OpenCV算法。这些最匹配的特征作为拼接的基础。我们提取两幅图像的关键点和sift描述符如下:

kp1和kp2是关键点，des1和des2是图像的描述符。如果我们用特征来画这幅图，它会是这样的:

左边的图像显示实际图像。右侧的图像使用SIFT检测到的特征进行注释：

一旦你有了两个图像的描述符和关键点，我们就会发现它们之间的对应关系。我们为什么要这么做?为了将任意两个图像连接成一个更大的图像，我们必须找到重叠的点。这些重叠的点会让我们根据第一幅图像了解第二幅图像的方向。根据这些公共点，我们就能知道第二幅图像是大是小还是旋转后重叠，或者缩小/放大后再fitted。所有此类信息的产生是通过建立对应关系来实现的。这个过程称为registration。

对于匹配图像，可以使用opencv提供的FLANN或BFMatcher方法。我会写两个例子证明我们会得到相同的结果。两个示例都匹配两张照片中更相似的特征。当我们设置参数k = 2时，这样我们就要求knnMatcher为每个描述符给出2个最佳匹配。“matches”是列表的列表，其中每个子列表由“k”个对象组成。以下是Python代码：

FLANN匹配代码：

BFMatcher匹配代码：

通常在图像中，图像的许多地方可能存在许多特征。所以我们过滤掉所有的匹配来得到最好的。因此我们使用上面得到的前2个匹配项进行比值检验。如果下面定义的比值大于指定的比值，则考虑匹配。

现在我们定义在图像上绘制线条的参数，并给出输出以查看当我们在图像上找到所有匹配时的样子：

这是输出的匹配图像：

这部分完整Python代码：

因此，一旦我们获得了图像之间的最佳匹配，我们的下一步就是计算单应矩阵。如前所述，单应矩阵将与最佳匹配点一起使用，以估计两个图像内的相对方向变换。

在OpenCV中估计单应性是一项简单的任务，只需一行代码:

在开始编码拼接算法之前，我们需要交换图像输入。所以img_现在会取右图像img会取左图像。

那么让我们进入拼接编码:

因此，首先，我们将最小匹配条件count设置为10(由MIN_MATCH_COUNT定义)，并且只有在匹配良好的匹配超出所需匹配时才进行拼接。否则，只需显示一条消息，说明匹配不够。

因此，在if语句中，我们将关键点(从匹配列表)转换为findHomography()函数的参数。

只需在这段代码中讨论cv2.imshow（“original_image_overlapping.jpg”，img2），我们就会显示我们收到的图像重叠区域：

因此，一旦我们建立了单应性，我们需要扭曲视角，我们将以下单应矩阵应用于图像：

所以我们使用如下：

在上面两行Python代码中，我们从两个给定的图像中获取重叠区域。然后在“dst”中我们只接收到没有重叠的图像的右侧，因此在第二行代码中我们将左侧图像放置到最终图像。所以在这一点上我们完全拼接了图像：

剩下的就是去除图像的黑色，所以我们将编写以下代码来从所有图像边框中删除黑边：

这是我们调用修剪边界的最终定义函数，同时我们在屏幕上显示该图像。如果您愿意，也可以将其写入磁盘：

使用上面的Python代码，我们将首先收到原始图片：

这是完整的最终代码：

在本教程中，我们学习了如何使用OpenCV执行图像拼接和全景构造，并编写了最终的图像拼接代码。

我们的图像拼接算法需要四个主要步骤：检测关键点和提取局部不变描述符; 获得图像之间的匹配描述符; 应用RANSAC估计单应矩阵; 使用单应矩阵应用warping transformation。

当仅为两个图像构建全景图时，该算法在实践中工作良好。

E. 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

F. 图像特征之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特征对灰度、对比度变换、旋转、尺度缩放等保持不变性，对视角变化、仿射变化、噪声也具有一定的鲁棒性。但其实时性不高，对边缘光滑的目标无法准确提取特征点

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