(四)OpenCV中的特征检测之SIFT(尺度不变换特征)

注释：本文翻译自OpenCV3.0.0 document->OpenCV-Python Tutorials，包括对原文档种错误代码的纠正

1.目标

• 学习SIFT算法的概念
• 学习如何找到SIFT关键点和描述符

2.理论

在最后几章，我们看到了一些角落探测器，如Harris Corner等。它们是旋转不变的，这意味着，即使图像旋转，我们也可以找到相同的角落。这是显而易见的，因为角落在旋转中也是角落。但是缩放呢？如果图像缩放，角落可能不是角落。例如，请看下面的简单图片。放大同一个窗口时，小窗内的小图像的一个角落是平坦的。所以Harris Corner的角落是规模不变的。

因此，2004年，不列颠哥伦比亚大学的D.Lower在他的论文中提出了一种新的算法——尺度不变特征变换(SIFT),该算法从尺度不变关键点获取图像的特征，提取这个关键点并计算其描述符。（本文很容易理解，并被认为是SIFT上最好的资料，所以这个解释只是本文的一个简短摘要）。

SIFT算法主要涉及四个步骤，我们将逐一看到它们：

   2.1 尺度空间极值检测(Scale-space Extrema Detection)

        从上图可以看出，我们不能使用相同的窗口来检测不同比例的关键点。小角落也行，但是要检测更大的角落，我们需要更大的窗口。为此，使用缩放空间滤波。其中高斯拉普拉斯是为具有各种值的图像找到的。LoG作为一个斑点检测器，可以检测由于变化而产生的各种大小的斑点。简而言之，作为一个缩放参数，例如，在上面的图像中，低的高斯核为小角赋值较高，而高斯的高斯核适合较大的角。因此，我们可以找到跨尺度和空间的局部最大值，它给出了值的列表，这意味着尺度下(x,y)处存在潜在的关键点。

       但这个LoG花费代价有点大，所以SIFT算法使用高斯差分，这是LoG的近似值。随着这两个不同图像的高斯模糊差异，可以得到高斯差分，让它为和。这个过程是在高斯金字塔的不同八度的图像中完成的。它在下面的图像中表示：

一旦找到这个DoG，图像就会在比例和空间上搜索到局部极值。例如，图像中的一个像素与其8个邻居以及下一个尺度的9个像素和先前尺度的9个像素进行比较。如果它是一个局部极值，这是一个潜在的关键点，它基本上意味着关键点最好在这个范围内表现出来，它显示在下面的图像中：

针对不同的参数，本文给出了一些经验数据，可以总结为八度数(number of octaves)=4,比例级数(number of scale levels)=5,初始，等作为最优值。

   2.2 关键化本地点(Keypoint Localization)

         一旦找到潜在的关键点位置，就必须对其进行改进以获得更准确的结果。他们使用泰勒级数展开的尺度空间来获得更精准的极值位置，并且如果这个极值的强度小于阈值(根据纸张为0.03)，它将被拒绝。该阈值在OpenCV中被称为contrastThreshold。

         DoG对边缘有更高的响应，所以边缘也需要去除。为此，使用类似Harris角点检测器的概念。他们用2*2的Hessian矩阵(H)来计算失真曲线，我们从Harris角点检测器知道，对于边缘，一个特征值比另一个大。所以这里他们使用了一个简单的函数。

          如果此比率比阈值(在OpenCV中称为edgeThreshold)高，则丢弃该关键点。在纸上给出10，因此它消除了任何低对比度关键点和边缘关键点，剩下的就是强烈的兴趣点。

   2.3 方向分配(Orientation Assignment)

        现在为每个关键点分配一个方向以实现图像的旋转不变性。在关键点位置周围取决于尺度，并在该区域计算梯度幅度和方向。创建一个方向直方图，其中36个方框覆盖360度，(用等于关键点尺度的1.5倍的梯度幅度和高斯加权窗口进行加权，得到直方图中的最高峰值，并且在任何高于80%的峰值也被认为是计算方向。)创建具有相同位置和规模但方向不同的关键点，有助于匹配的稳定性。

   2.4 关键点描述符(keypoint Descriptor)

         现在创建关键点描述符。关键点周围有一个16*16的街区(Block)。它分为16个4*4大小的字块。对于每个字块，创建8个方向直方图。所以共有128bin值可用。它被表示为形成关键点描述符的向量。除此之外，它还采取了几项措施来实现对光照变化、旋转等的鲁棒性。

   2.5 关键点匹配(Keypoint Matching)

         两幅图像之间的关键点通过识别它们最近的邻居来匹配。但在某些情况下，第二个最接近的匹配可能非常接近第一个。这可能是由于噪音或其它的原因。在那种情况下，采用最近距离与第二距离的比率，如果它大于0.8，则被拒绝。根据文章，它被排除了大约90%的错误匹配，而丢弃的只有5%的匹配正确。

         所以这是SIFT算法的总结。欲了解更多细节和理解，强烈建议阅读原文。记住一件事，这个算法是获专利的。所以这个算法被包含在OpenCV的非*模块中。

3.OpenCV中的SIFT

现在让我们来看看OpenCV中提供的SIFT函数。让我们从关键点检测并开始绘制它们，首先，我们必须构建一个SIFT对象。我们可以将不同的参数传递给它，这些参数是可选的，并且在文档中有很好的解释。

# -*- coding: utf-8 -*-
'''
SIFT(尺度不变特征变换)介绍
SIFT算法主要涉及四个步骤：
1.尺度空间极值检测(scale-space Extrema Detection)
2.关键点本地化
3.方向分配
4.关键点描述符
5.关键点匹配
下面的demo是OpenCV中的SIFT函数：cv2.SIFT()
'''

import cv2

img = cv2.imread('5.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

'''
在用python使用OpenCV进行SIFT时候，编译出现这样的问题：
AttributeError: module 'cv2' has no attribute 'SIFT'
错误代码如下:
sift = cv2.SIFT()
原因：opencv将SIFT等算法整合到xfeatures2d集合里面了。变更后的写法如下：
sift=cv2.xfeatures2d.SIFT_create()
'''
# sift = cv2.SIFT()
sift = cv2.xfeatures2d.SIFT_create()

# sift.detect()函数是在图像中查找关键点。如果只想收缩图像的一部分，可以传递掩码
# 每个关键点都是一个特殊的结构，具有许多属性。如(x,y)坐标，有意义的领域大小，指定其方向的角度，指定关键点强度的响应等等
kp = sift.detect(gray, None)

# drawKeypoints:第一个参数输入图像，第二个参数关键点，第三个参数输出图像
# cv2.drawKeypoints()用于在关键点位置绘制小圆圈。如果传递一个标志cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS给它，
# 会绘制一个尺寸为关键点的圆，甚至会显示它的方向。
# img = cv2.drawKeypoints(gray, kp, img)
img = cv2.drawKeypoints(gray, kp, img, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
cv2.imwrite('sift_keypoints.jpg', img)

'''
现在计算描述符，OpenCV提供了两种方法：
1.既然已经找到了关键点，可以使用sift.compute()计算关键点描述符，例如：kp,des=sift.compute(gray,kp)
2.如果没有找到关键点，可使用函数sift.detectAndCompute()在一个步骤中直接找到关键点和描述符：如下:
'''
# 这里找出来的kp将是一个关键点列表，des是形状Number_of_Keypoints*128的一个numpy数组
kp, des = sift.detectAndCompute(gray, None)

cv2.imshow('sift_keypoints', img)
cv2.waitKey(0) & 0xFF
cv2.destroyAllWindows()

OpenCV还提供cv2.drawkeyPoints()函数，用户绘制关键点位置上的小圆圈。如果你传递一个cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS给它，它会绘制一个尺寸为关键点的圆，它甚至会显示它的方向。