一、SIFT算子介绍

在之前的学习中，我们学习了角点的基本知识，并对Harris角点检测算法应用到了图像的角点检测。
当我们在观察图像中的物体时，物体所在的图像不论背景或者角度如何变换，我们依然能很快的识别出图像中的目标物体。对机器来说，则需要定义图像上的关键特征并且能够根据这些特征搜索到一张新的图片。
SIFT，即尺度不变特征变换（Scale-invariant feature transform，SIFT）。是在计算机视觉任务中特征提取算法。

二、SIFT算子特点

这种描述具有尺度不变性，可在图像中检测出关键点，是一种局部特征描述子。SIFT特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、微视角改变的容忍度也相当高。基于这些特性，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。
SIFT算法可以解决的问题：
• 目标的旋转、缩放、平移（RST）
• 图像仿射/投影变换（视点viewpoint）
• 弱光照影响（illumination）
• 部分目标遮挡（occlusion）
• 杂物场景（clutter）
• 噪声

三、SIFT算子应用

SIFT算子可以帮助定位图像中的局部特征，应用于计算机视觉应用，例如图像匹配，物体检测，场景检测等。
还可以将通过SIFT生成的关键点用作模型训练期间的图像特征。与边缘特征或单一特征相比，SIFT特征的主要优势在于它们不受图像大小或方向的影响。

四、SIFT特征点提取算法

1. 构建尺度空间，检测极值点，获得尺度不变性

• 构建尺度空间——特征点的性质之一就是对尺度的变化保持不变性。因此寻找的特征点要在不同尺度下都能被检测出来.根据文献可知，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：$L（x,y,σ)$是由可变尺度的高斯函数$G(x,y,σ)$与输入图像$I（x,y）$卷积得到
  即： $L（x,y,σ)=G(x,y,σ)*I（x,y）$
  其中：$G(x,y,σ)$=${\frac{1}{2πσ^2}} e^{\frac{-(x_+^2 y^2 )}{2σ^2}}$
  $(x,y)$是尺度坐标，σ大小决定图像的平滑程度，大尺度对应图像的概括特征，小尺度对应图像的细节特征，大的σ对应粗糙尺度（低分辨率），小σ对应高分辨率。为使计算相对高效，真正使用的是差分高斯尺度空间
  $D(x,y,σ)$:
  

        D是两个相邻的尺度在尺度上相差一个相乘系数k。
  

• 高斯模糊——降低图像中的噪点，强调了图像的重要特征。进行高斯模糊之和，纹理和次要细节将从图像中删除，并且保留形状和边缘之类的相关信息。

• 实现DOG——初始图像与不同σ值的高斯函数卷积，得到一垛模糊后图像，然后将这一垛图像临近两两相减得到对应的DOG。一副图像可以产生几组图像，一组图像包括几层图像。s为每组层数一般为3~5层，最后可以将s和k的关系确立为$k=2^{{1}/{s}}$。
  

• 尺度空间检测极值点——DOG上某个像素要和本尺度的八个像素以及上下相邻尺度各9个相邻像素共26个像素值进行比较，以确定是否为局部最大或最小值。如果它是相邻像素中最高或者最低的像素，则确定该像素点是尺度空间的极值点之一。

2. 筛选关键点，剔除不稳定的极值点
   此时已经存在了尺度不变的关键点，但是要对这些关键点进行筛选，去掉对比度度的以及处于不理想边缘处的关键点，得到符合要求的特征关键点。

3. 在特征点处提取特征描述符，为特征点分配方向值
   在此阶段为每个关键点指定一个方向使他们不变，并将该方向纳入关键点子特性描述当中，那么这个关键点就具有了旋转不变性。
   对于已经检测到的特征点，我们可以得到该特征点的尺度值σ ，所以确定该参数可以得到该尺度下的高斯图像：
   
   我们通过每个极值点的梯度来为极值点赋予方向，梯度幅值等于上下两点像素值差的平方加上左右两点像素值差的平方，梯度方向则为上下两点像素值差与左右两点像素值差的商。
   
   确定关键点的方向采用梯度直方图统计法，统计以关键点为原 点，一定区域内的图像像素点对关键点方向生成所作的贡献。

4. 生成特征描述符，利用特征描述符寻找匹配特征点
   在前面我们已经指定了特征关键点的位置、尺度和方向。这样特征点就已经对这些参数变化保持了不变性。这时则要生成一种能够描述这样特征的描述符，尽可能让其对于其他变化也有一定不变性，比如光照和三维视角变化。
   首先在关键点周围采用16×16的邻域。将该16×16区域进一步划分为4×4子块，对于这些子块中的每一个小块，使用幅度和方向生成柱状图。
   
   在此阶段，bin的大小增加，只占用8个bin(不是36个)。每一个箭头代表8个bin，箭头的长度定义了幅度。因此，每个关键点总共有128个bin值。

5. 关键点匹配——为了对这些特征点进行匹配，需要对这些特征点运用适当的比较方法来找到相应关系。
   特征点的匹配可以采用穷举法来完成，但是这样耗费的时间太多，一 般都采用kd树的数据结构来完成搜索。搜索的内容是以目标图像的特征点为基准，搜索与目标图像的特征点最邻近的原图像特征点和次邻 近的原图像特征点。

五、SIFT算法特征匹配实验

实验1：构建图像的数据集

实验2：图片的SIFT特征提取，并展示特征点

小结：SIFT从理论上是一种相似不变量，即对图像尺度变化和旋转是不变量。同时，SIFT算法对图像的复杂变化和光照变化有了较强的适应性，其在构造描述子时，以子区域的统计特性，而不是以的单个像素作为研究对象，提高了局部变形的适应能力，定位的精确度比较高。
实验3：SIFT特征匹配
SIFT特征匹配代码：

from PIL import Image
from pylab import *
import sys
from PCV.localdescriptors import siftif len(sys.argv) >= 3:im1f, im2f = sys.argv[1], sys.argv[2]
else:
#  im1f = '../data/sf_view1.jpg'
#  im2f = '../data/sf_view2.jpg'im1f = r'D:\CVphoto\022512.jpg'im2f = r'D:\CVphoto\022510.jpg'
#  im1f = '../data/climbing_1_small.jpg'
#  im2f = '../data/climbing_2_small.jpg'
im1 = array(Image.open(im1f))
im2 = array(Image.open(im2f))sift.process_image(im1f, 'out_sift_1.txt')
l1, d1 = sift.read_features_from_file('out_sift_1.txt')
figure()
gray()
subplot(121)
sift.plot_features(im1, l1, circle=False)sift.process_image(im2f, 'out_sift_2.txt')
l2, d2 = sift.read_features_from_file('out_sift_2.txt')
subplot(122)
sift.plot_features(im2, l2, circle=False)#matches = sift.match(d1, d2)
matches = sift.match_twosided(d1, d2)
print '{} matches'.format(len(matches.nonzero()[0]))figure()
gray()
sift.plot_matches(im1, im2, l1, l2, matches, show_below=True)
show()

SIFT特征匹配结果：

小结：通过上一小节的学习，可以发现Harris角点的匹配数很多，SIFT匹配点数量少一些。
SIFT匹配点因为有通过当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。
筛选去掉低对比度或非常靠近边缘的关健点，所以在sift的特征匹配中，匹配的关健点虽然数量减少，但是准确度提高很多。对于不同角度拍摄的图像能够很好的进行匹配。

实验4：给定数据集，进行图像检索，输出与其匹配度最高的三张图片

# -*- coding: utf-8 -*-from PIL import Imagefrom pylab import *from numpy import *import osfrom PCV.tools.imtools import get_imlist  # 导入原书的PCV模块import matplotlib.pyplot as plt  # plt 用于显示图片import matplotlib.image as mpimg  # mpimg 用于读取图片def process_image(imagename, resultname, params="--edge-thresh 10 --peak-thresh 5"):""" 处理一幅图像，然后将结果保存在文件中"""if imagename[-3:] != 'pgm':# 创建一个pgm文件im = Image.open(imagename).convert('L')im.save('tmp.pgm')imagename = 'tmp.pgm'cmmd = str("sift " + imagename + " --output=" + resultname + " " + params)os.system(cmmd)print 'processed', imagename, 'to', resultnamedef read_features_from_file(filename):"""读取特征属性值，然后将其以矩阵的形式返回"""f = loadtxt(filename)return f[:, :4], f[:, 4:]  # 特征位置，描述子def write_featrues_to_file(filename, locs, desc):"""将特征位置和描述子保存到文件中"""savetxt(filename, hstack((locs, desc)))def plot_features(im, locs, circle=False):"""显示带有特征的图像输入：im（数组图像），locs（每个特征的行、列、尺度和朝向）"""def draw_circle(c, r):t = arange(0, 1.01, .01) * 2 * pix = r * cos(t) + c[0]y = r * sin(t) + c[1]plot(x, y, 'b', linewidth=2)imshow(im)if circle:for p in locs:draw_circle(p[:2], p[2])else:plot(locs[:, 0], locs[:, 1], 'ob')axis('off')def match(desc1, desc2):"""对于第一幅图像中的每个描述子，选取其在第二幅图像中的匹配输入：desc1(第一幅图像中的描述子)，desc2(第二幅图像中的描述子)"""desc1 = array([d / linalg.norm(d) for d in desc1])desc2 = array([d / linalg.norm(d) for d in desc2])dist_ratio = 0.6desc1_size = desc1.shapematchscores = zeros((desc1_size[0], 1), 'int')desc2t = desc2.T  # 预先计算矩阵转置for i in range(desc1_size[0]):dotprods = dot(desc1[i, :], desc2t)  # 向量点乘dotprods = 0.9999 * dotprods# 反余弦和反排序，返回第二幅图像中特征的索引indx = argsort(arccos(dotprods))# 检查最近邻的角度是否小于dist_ratio乘以第二近邻的角度if arccos(dotprods)[indx[0]] < dist_ratio * arccos(dotprods)[indx[1]]:matchscores[i] = int(indx[0])return matchscoresdef match_twosided(desc1, desc2):"""双向对称版本的match()"""matches_12 = match(desc1, desc2)matches_21 = match(desc2, desc1)ndx_12 = matches_12.nonzero()[0]# 去除不对称的匹配for n in ndx_12:if matches_21[int(matches_12[n])] != n:matches_12[n] = 0return matches_12def appendimages(im1, im2):"""返回将两幅图像并排拼接成的一幅新图像"""# 选取具有最少行数的图像，然后填充足够的空行rows1 = im1.shape[0]rows2 = im2.shape[0]if rows1 < rows2:im1 = concatenate((im1, zeros((rows2 - rows1, im1.shape[1]))), axis=0)elif rows1 > rows2:im2 = concatenate((im2, zeros((rows1 - rows2, im2.shape[1]))), axis=0)return concatenate((im1, im2), axis=1)def plot_matches(im1, im2, locs1, locs2, matchscores, show_below=True):""" 显示一幅带有连接匹配之间连线的图片输入：im1, im2(数组图像), locs1,locs2（特征位置）,matchscores(match()的输出)，show_below（如果图像应该显示在匹配的下方）"""im3 = appendimages(im1, im2)if show_below:im3 = vstack((im3, im3))imshow(im3)cols1 = im1.shape[1]for i in range(len(matchscores)):if matchscores[i] > 0:plot([locs1[i, 0], locs2[matchscores[i, 0], 0] + cols1], [locs1[i, 1], locs2[matchscores[i, 0], 1]], 'c')axis('off')# 获取project2_data文件夹下的图片文件名(包括后缀名)filelist = get_imlist(r'D:\CVphoto\0306')# 输入的图片im1f = r'D:\CVphoto\0306\03062.jpg'im1 = array(Image.open(im1f))process_image(im1f, 'out_sift_1.txt')l1, d1 = read_features_from_file('out_sift_1.txt')i = 0num = [0] * 30  # 存放匹配值for infile in filelist:  # 对文件夹下的每张图片进行如下操作im2 = array(Image.open(infile))process_image(infile, 'out_sift_2.txt')l2, d2 = read_features_from_file('out_sift_2.txt')matches = match_twosided(d1, d2)num[i] = len(matches.nonzero()[0])i = i + 1print '{} matches'.format(num[i - 1])  # 输出匹配值i = 1figure()while i < 4:  # 循环三次，输出匹配最多的三张图片index = num.index(max(num))print index, filelist[index]lena = mpimg.imread(filelist[index])  # 读取当前匹配最大值的图片# 此时 lena 就已经是一个 np.array 了，可以对它进行任意处理# lena.shape  # (512, 512, 3)subplot(1, 3, i)plt.imshow(lena)  # 显示图片plt.axis('off')  # 不显示坐标轴num[index] = 0  # 将当前最大值清零i = i + 1show()

实验结果：

匹配结果：

小结：输入图片和数据集中图片匹配的特征点匹配值存放在num中，可以通过对num进行排序后取最大值得到匹配值最多的图像。
SIFT特征检索是基于内容的图像检索技术是基于图像自身的内容特征来检索图像，这免去人为标注图像的过程。基于内容的图像检索技术是采用某种算法来提取图像中的特征（SIFT,SURF,CNN等），并将特征存储起来，组成图像特征数据库。当需要检索图像时，采用相同的特征提取技术提取出待检索图像的特征，并根据某种相似性准则计算得到特征数据库中图像与待检索图像的相关度，最后通过由大到小排序，得到与待检索图像最相关的图像，实现图像检索。
SIFT算法是提取特征的一个重要算法，该算法对图像的扭曲，光照变化，视角变化，尺度旋转都具有不变性。SIFT算法提取的图像特征点数不是固定值，维度是统一的128维。

六、总结

1.出现的问题：empire.sift文件为空
解决方法：Python 2实现SIFT匹配需要下载 VLFeat 工具包,建议下载vlfeat-0.9.20-bin.tar.gz,解压之后，需要将vlfeat-0.9.20/bin/win64文件夹下的sift.exe和vl.dll复制到当前项目目录下。
2.出现的问题：无opencv的工具包
解决方法：Opencv的版本需要和python的版本对应，我的python版本是anaconda2下的python2，所以需要安装64位的opencv_python-2.4.13.7-cp27-cp27m-win_amd64.whl（cp27的意思是python2.7.x，如果是python3则需要安装opencv_python-3.4.5+contrib-cp37-cp37m-win_amd64.whl）
如果在opencv 的官网
https://www.lfd.uci.edu/~gohlke/pythonlibs/
下载速度比较慢可以去找国内的镜像文件。
将whl文件移动到anaconda\Lib\site-package这个文件夹下面，再在cmd里面cd到该目录下面执行语句pip install opencv_python-2.4.13.7-cp27-cp27m-win_amd64.whl

3.出现的问题：sift = cv2.xfeatures2d.SIFT_create()不可执行
需要先下载opencv-python3.4.2.16这个版本才能执行这个函数
在下载opencv时最好下载+contrib这个部分的，这个版本里面有更多的图像处理功能。
4.实验总结：在本次实验中对利用sift算法对图像的特征点进行提取和检测，通过实验我们可以发现，sift算法对于特征点的检测的准确性高于harris算法，不但对于旋转、尺度缩放、亮度变化保持不变性，而且对视角变化、仿射变换、噪声也保持一定程度的稳定性。且该方法对特征点的个数和有效点的比例没有要求。当特征点不是很多时，经优化的SIFT匹配算法甚至可以达到实时的要求。而且可以很方便的与其他形式的特征向量进行联合。
但是sift特征点在识别对称图形，或者没有纹理的图片时，容易造成误差。因为其是方法通过对特征点构造128维的向量，然后对向量进行匹配，这样图像就得满足足够多的纹理，否则构造出的128维向量区别性就不是太大，极限情况如指纹图像的匹配，星图识别等这类图像特征点周围根本没有什么纹理。