OpenCV 15(SIFT/SURF算法)

一、SIFT

Harris和Shi-Tomasi角点检测算法，这两种算法具有旋转不变性，但不具有尺度不变性，以下图为例，在左侧小图中可以检测到角点，但是图像被放大后，在使用同样的窗口，就检测不到角点了。

尺度不变特征转换即SIFT (Scale-invariant feature transform)。它用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所发表，2004年完善总结。应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对等领域。

Lowe将SIFT算法分解为如下四步：

（1）建立高斯查分金字塔：搜索所有尺度上的图像位置。通过高斯差分函数来识别潜在的对于尺度和旋转不变的关键点。

在不同的尺度空间是不能使用相同的窗口检测极值点，对小的关键点使用小的窗口，对大的关键点使用大的窗口，为了达到上述目的，我们使用尺度空间滤波器。

高斯核是唯一可以产生多尺度空间的核函数。-《Scale-space theory: A basic tool for analysing structures at different scales》。  近处清晰，远处模糊

一个图像的尺度空间L(x,y,σ)，定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ)卷积运算 ，即：

σ是尺度空间因子，它决定了图像的模糊的程度。在大尺度下（σ值大）表现的是图像的概貌信息，在小尺度下（σ值小）表现的是图像的细节信息。

 

下面我们构建图像的高斯金字塔，它采用高斯函数对图像进行模糊以及降采样处理得到的，整个流程如下图所示：

• 高斯金字塔构建过程中，首先将图像扩大一倍，在扩大的图像的基础之上构建高斯金字塔，然后对该尺寸下图像进行高斯模糊，几幅模糊之后的图像集合构成了一个Octave；
• 对该Octave下的最模糊的一幅图像进行下采样的过程，长和宽分别缩短一倍，图像面积变为原来四分之一。这幅图像就是下一个Octave的初始图像，在初始图像的基础上完成属于这个Octave的高斯模糊处理；
• 以此类推完成整个算法所需要的所有Octave构建，这样这个高斯金字塔就构建出来了 

利用LoG(高斯拉普拉斯方法)，即图像的二阶导数，可以在不同的尺度下检测图像的关键点信息，从而确定图像的特征点。但LoG的计算量大，效率低。所以我们通过两个相邻高斯尺度空间的图像的相减，得到DoG(高斯差分)来近似LoG。

为了计算DoG我们构建高斯差分金字塔，该金字塔是在上述的高斯金字塔的基础上构建而成的，建立过程是：在高斯金字塔中每个Octave中相邻两层相减就构成了高斯差分金字塔。如下图所示：

高斯差分金字塔的第1组第1层是由高斯金字塔的第1组第2层减第1组第1层得到的。以此类推，逐组逐层生成每一个差分图像，所有差分图像构成差分金字塔。概括为DOG金字塔的第o组第l层图像是有高斯金字塔的第o组第l+1层减第o组第l层得到的。后续Sift特征点的提取都是在DOG金字塔上进行的。
 

总结：

先用高斯核进行卷积，得到高斯金字塔 --》 差分卷积核

（2）极值点精确定位

 在 DoG 搞定之后，就可以在不同的尺度空间中搜索局部最大值了。对于图像中的一个像素点而言，它需要与自己周围的 8 邻域，以及尺度空间中上下两层中的相邻的 18（2x9）个点相比。如果是局部最大值（26个点），它就可能是一个关键点。基本上来说关键点是图像在相应尺度空间中的最好代表。如下图所示：

在离散空间中寻找到的极值点并不一定是真正的极值点我们用离散值插值的方式，将离散空间转换为连续空间，得到更加准确的极值点。同时去除低对比度的关键点和不稳定的边缘响应点。

（3）关键点方向确定 

经过上述两个步骤，图像的关键点就完全找到了，这些关键点具有尺度不变性。为了实现旋转不变性，还需要为每个关键点分配一个方向角度，也就是根据检测到的关键点所在高斯尺度图像的邻域结构中求得一个方向基准。 

对于任一关键点，我们采集其所在高斯金字塔图像以r为半径的区域内所有像素的梯度特征（幅值和幅角），半径r为：

其中σ是关键点所在octave的图像的尺度，可以得到对应的尺度图像。

梯度的幅值和方向的计算公式为：

关键点的方向，并不是关键点的梯度方向，而是统计关键点邻域内所有点的梯度方向，将0-360度分为8个方向，每45度一个方向。形成的8个方向形成方向柱状图。

峰值代表关键点方向，大于峰值80%的作为辅方向。 

辅方向对特征点匹配的稳定性非常重要

（4）关键点描述

为了保证特征点的旋转不变性，以特征点为中心，将坐标轴旋转为关键点的主方向，如下图所示：

取特征点周围8*8的像素进行梯度方向统计和高斯加权(蓝色圆圈代表高斯加权范围)。每4*4窗口生成8个方向，这样就生成了2*2*8的向量作为特征点的数学描述。

SIFT算法采用4*4*8共128维向量作为特征点的描述子。最后通过描述子的欧式距离进行特征点匹配。

SIFT在图像的不变特征提取方面拥有无与伦比的优势，但并不完美，仍然存在实时性不高，有时特征点较少，对边缘光滑的目标无法准确提取特征点等缺陷，自SIFT算法问世以来，人们就一直对其进行优化和改进，其中最著名的就是SURF算法。

sift = cv.xfeatures2d.SIFT_create()    实例化sift
kp,des = sift.detectAndCompute(gray,None)   检测关键点并计算

参数：

• gray: 进行关键点检测的图像，注意是灰度图像

返回：

• kp: 关键点信息，包括位置，尺度，方向信息
• des: 关键点描述符，每个关键点对应128个梯度信息的特征向量

将关键点检测结果绘制在图像上 

cv.drawKeypoints(image, keypoints, outputimage, color, flags)

• image: 原始图像
• keypoints：关键点信息，将其绘制在图像上
• outputimage：输出图片，可以是原始图像
• color：颜色设置，通过修改（b,g,r）的值,更改画笔的颜色，b=蓝色，g=绿色，r=红色。
• flags：绘图功能的标识设置
  1. cv2.DRAW_MATCHES_FLAGS_DEFAULT：创建输出图像矩阵，使用现存的输出图像绘制匹配对和特征点，对每一个关键点只绘制中间点
  2. cv2.DRAW_MATCHES_FLAGS_DRAW_OVER_OUTIMG：不创建输出图像矩阵，而是在输出图像上绘制匹配对
  3. cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS：对每一个特征点绘制带大小和方向的关键点图形
  4. cv2.DRAW_MATCHES_FLAGS_NOT_DRAW_SINGLE_POINTS：单点的特征点不被绘制

import cv2 as cv 
import numpy as np
import matplotlib.pyplot as plt
# 1 读取图像
img = cv.imread('./image/tv.jpg')
gray= cv.cvtColor(img,cv.COLOR_BGR2GRAY)
# 2 sift关键点检测
# 2.1 实例化sift对象
sift = cv.xfeatures2d.SIFT_create()# 2.2 关键点检测：kp关键点信息包括方向，尺度，位置信息，des是关键点的描述符
kp,des=sift.detectAndCompute(gray,None)
# 2.3 在图像上绘制关键点的检测结果
cv.drawKeypoints(img,kp,img,flags=cv.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
# 3 图像显示
plt.figure(figsize=(8,6),dpi=100)
plt.imshow(img[:,:,::-1]),plt.title('sift检测')
plt.xticks([]), plt.yticks([])
plt.show()

二、SURF

使用 SIFT 算法进行关键点检测和描述的执行速度比较慢， 需要速度更快的算法。 2006 年 Bay提出了 SURF 算法，是SIFT算法的增强版，它的计算量小，运算速度快，提取的特征与SIFT几乎相同，将其与SIFT算法对比如下：