SIFT特征庖丁解牛

1. SIFT背景

SIFT（Scale Invariant Feature Transform）：尺度不变特征转换匹配算法，1999年由David Lowe提出，官网地址：https://www.cs.ubc.ca/~lowe/keypoints/，是计算机视觉方向经典特征提取算法。SIFT用于获取图像中的局部特征点，这些特征点具备较好的尺度、光照、旋转不变性，广泛用于计算机视觉方向，比如图像匹配、物体检测等。其步骤可简要理解为下图：

简要流程包括：

l  关键点查找：关键点可粗略理解为不会因光照、尺度、旋转等因素而消失的点，例如角点、边缘点、暗区域的亮点以及亮区域的暗点等。该步骤在多个尺度空间上通过高斯微分函数来识别潜在的具有尺度和旋转不变性的兴趣点。

l  关键点定位和特征方向确定：关键点检测主要是用了高斯差分DoG技术，在不同尺度的高斯差分图像上，纹理复杂的区域或像素点比如边缘、点、角之类区域变化较大，变化大的点即为潜在的关键点。最终特征点选择依据于关键点的稳定程度。基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。后续所有操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。

l  特征点描述：从检出的关键点提取出128维的特征向量，作为后续特征点计算实体。

l  特征点匹配：基于各特征点描述子两两比较找出相互匹配的若干对特征点，建立图像间对应关系。

2. 详细流程

2.1高斯模糊/平滑

高斯模糊（Gaussian Blur）常用来图像降噪。对于图像中的每个像素，高斯模糊核会基于当前像素的周边相邻像素点计算出一个新的值，如下图所示：

SIFT中与高斯模糊搭配使用是图像金字塔，即高斯图像金字塔。高斯金字塔是通过高斯平滑和亚采样技术获得一系列的下采样图像，也就是说第K层高斯金字塔通过平滑、亚采样就可以获得K+1层高斯图像，层间从下到上进行编号，详细流程如下图所示：

2.2 高斯差分

在不同尺度图像组成的图像金字塔的基础上，可使用高斯差分DoG技术实现特征增强。DoG通过从前一个图像中以相同比例尺减去每个图像，为每个octave创建另一组图像，如下图所示：

在DOG图像的基础上进行关键点查找，并生成可计算的描述子。

2.3 关键点查找

有了DoG图像，下一步为关键点定位查找，即找到图像的局部最大值和最小值：局部极值。

为了定位局部最大值和最小值，需要检查图像中的每个像素，并将其与相邻像素进行比较，包括该图像的周围像素及其相邻Octave上一张和下一张图像的九个像素。每个像素值将与其他26个像素值进行比较，以确定是否为局部最大值/最小值。如下图所示，标记为x的像素为待计算像素点，与相邻像素（绿色）进行比较，如果它是相邻像素中最高或最低的像素，则将其选择为候选关键点。

    从较多的候选关键点中选出真正稳定的SIFT特征点，需要消除对比度低或非常靠近边缘的关键点。为了处理低对比度关键点，将为每个关键点计算二阶泰勒展开（second-order Taylor expansion）。如果结果值小于0.03（大小），则剔除该关键点。在边缘梯度的方向上主曲率值比较大，而沿着边缘方向则主曲率值较小。候选特征点的DoG函数D(x)的主曲率与2×2Hessian矩阵H的特征值成正比。
其中，D_xx, D_xy, D_yy是候选点邻域对应位置的差分。

H的特征值α和β代表x和y方向的梯度：

表示矩阵H对角线元素之和，表示矩阵H的行列式。假设是α较大的特征值，而是β较小的特征值，令，则

该值在两特征值相等时达最小。Lowe论文中建议阈值T为1.2，则保留，反之则丢弃。

2.4 特征点描述

每个图像都有一组稳定的关键点，即特征点。每个特征点都需要经过以下计算从而得到具体可计算的描述子。

1)  计算幅度和方向

要找到上图中心像素值的大小和方向，通过提取55和46与56和42之间的差值来计算x和y方向上的梯度。得出的分别是Gx = 9和Gy = 14。有了梯度就可以计算幅度和方向：

大小表示像素的强度，方向表示像素的方向。

2) 关键点描述

算法采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点确定关键点方向。在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向。梯度直方图将0~360度的方向范围分为36个柱，其中每柱10度。如下图所示，直方图的峰值方向代表了关键点的主方向，方向直方图的峰值则代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。就得到了下面的柱状图：

  对于每一个关键点，都拥有位置、尺度以及方向三个信息。为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有贡献的像素点，并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。从稳定的关键点（不变的比例以及旋转角度）生成可计算和存储的描述子。由于使用周围的像素，因此描述符对于图像的照度或亮度部分不变。

  首先在关键点周围的16×16区域划分为4×4子块，子块中的每一个小块，使用幅度和方向生成柱状图。在此阶段，bin的大小增加，只占用8个bin(不是36个)。每一个箭头代表8个bin，箭头的长度定义了幅度。因此，每个关键点总共有128个bin值，从而得到可计算的SIFT特征描述子。

3. 特征匹配

基于OPENCV可较容易实现SIFT特征提取和匹配，简要实例代码如下：

import cv2

import numpy as np

img_1 = cv2.imread('image_to_detect1.png', cv2.IMREAD_GRAYSCALE)

img_2 = cv2.imread('image_to_detect2.png', cv2.IMREAD_GRAYSCALE)

# SIFT特征计算

sift = cv2.xfeatures2d.SIFT_create()

kp1, des1 = sift.detectAndCompute(img_1, None)

kp2, des2 = sift.detectAndCompute(img_2, None)

# 特征匹配

FLANN_INDEX_KDTREE = 1

index_params = dict(algorithm=FLANN_INDEX_KDTREE, trees=5)

search_params = dict(checks=50)

flann = cv2.FlannBasedMatcher(index_params, search_params)

matches = flann.knnMatch(psd_des1, psd_des2, k=2)

goodMatch = [] # 筛选特征点，如果配对中第一匹配的距离小于第二匹配的距离的1/2，则说明第一配对是两幅图像中独特不重复的特征点,保留

for m, n in matches:

    if m.distance < 0.50*n.distance:

        goodMatch.append(m)

goodMatch = np.expand_dims(goodMatch, 1)

img_out = cv2.drawMatchesKnn(img_1, kp1, img_2, kp2, goodMatch[:50], None, flags=2)

cv2.imshow('SIFT-Demo', img_out)

cv2.waitKey(0)

cv2.destroyAllWindows()