什么是局部图像描述子
所谓局部特征描述子就是用来刻画图像中的局部特征的，是以图像中的一个像素点的周围像素点的分布特征来获取该点的局部特征的算法。我们可以使用局部特征的特征点来代表图像的内容包括运动目标跟踪，物体识别，图像配准，全景图像拼接，三维重建等。如果我们想匹配同一个场景中的两幅图像。首先，我们检测每幅图像中的特征，然后提取他们的描述子。第一幅图像中的每一个特征描述子向量都会与第二幅图中的描述子进行比较，得分最高的一对描述子，也就是两个向量的距离最近，将被视为那个特征的最佳匹配。这些图像的局部特征需要以下性质：
- 位移不变性
- 旋转不变性
- 尺度不变性
- 光照不变性
- 以及更多
我们学习 Harris 角点检测算法，用于提取图像的特征点；学习 SIFT（尺度不变特征转换），用于解决图像缩放、旋转、曝光、噪声等因素对特征匹配的影响。
Harris角点检测算法
角点（corner points）：
- 局部窗口沿各方向移动，均产生明显变化的点
- 图像局部曲率突变的点
??
角点特征:
- 轮廓之间的交点。
- 对于同一场景，即使视角发生变化，通常具备稳定性质的特征。
- 该点附近区域的像素点无论在梯度方向上还是其梯度幅值上有着较大变化。
- 角点处的一阶导数最大，二阶导数为0。
- 角点指示了物体边缘变化不连续的方向。
Harris 角点检测算子：
Harris 算子是一种简单的点特征提取算子，这种算子受信号处理中自相关函数的启发，给出与自相关函数相联系的矩阵M。M阵的特征值是自相关函数的一阶曲率，如果两个曲率值都高，那么就认为该点是特征点。为了消除噪声对于角点检测的影响，可以使用一个高斯滤波器来平滑图像。
Harris 角点检测算法的基本思想：
利用矩形窗在图像上移动，若窗内包含有角点，则窗口向各个方向移动时，窗内的灰度值都会发生变化。从而达到检测图像角点的目的。如果像素周围显示存在多于一个方向的边，我们认为该点为兴趣点。该点就称为角点。
Harris 角点检测算法的数学表达：
?
总的来说，算法的核心就是是利用局部窗口在图像上进行移动，判断灰度是否发生较大的变化。如果窗口内的灰度值（在梯度图上）都有较大的变化，那么这个窗口所在区域就存在角点。
这样就可以将 Harris 角点检测算法分为以下三步：
- 当窗口（局部区域）同时向 xx （水平）和 yy（垂直） 两个方向移动时计算窗口内部的像素值变化量 E(x,y)E(x,y) ；
- 对于每个窗口，都计算其对应的一个角点响应函数R；
- 然后对该函数进行阈值处理，如果 R>threshold，表示该窗口对应一个角点特征。
Harris角点检测实例
from pylab import *
from PIL import Image
from PCV.localdescriptors import harris
# 读入图像
im = array(Image.open('image/tingzi.jpg').convert('L'))
# 检测harris角点
harrisim = harris.compute_harris_response(im)
# Harris响应函数
harrisim1 = 255 - harrisim
#画出Harris响应图
figure()
gray()
imshow(harrisim1)
print (harrisim1.shape)
title('Harris')
axis('off')
axis('equal')
threshold = [0.01,0.05,0.1,]
for i, thres in enumerate(threshold):
filtered_coords = harris.get_harris_points(harrisim, 6, thres)
# subplot(1, 4, i+2)
# subplot(4, 1, i + 2)
figure()
gray()
title('threshold='+str(thres))
imshow(im)
print(im.shape)
plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*')
axis('off')
show()
角点检测结果如下：
从上图可以明显看出，随着阈值从0.01增到0.05再到0.1，检测出的角点越来越少，并且角点检测算子对亮度的变化更敏感，在亮区域角点更多。可以看出，Harris角点检测获取的角点在图像中分布不均匀（对比度高的区域角点多）。
Harris 角点检测算法下实现的图像匹配?
Harris 角点检测器仅仅能够检测出图像中的兴趣点，但是没有给出通过比较图像间的兴趣点来寻找匹配角点的方法。我们需要在每个点上加入描述子信息，并给出一 个比较这些描述子的方法。
兴趣点描述子是分配给兴趣点的一个向量，描述该点附近的图像的表观信息。描述子越好，寻找到的对应点越好。我们用对应点或者点的对应来描述相同物体和场景点在不同图像上形成的像素点。
实现代码：
from pylab import *
from PIL import Image
from PCV.localdescriptors import harris
from PCV.tools.imtools import imresize
im1 = array(Image.open('image/tingzi1.jpg').convert("L"))
im2 = array(Image.open('image/tingzi.jpg').convert("L"))
# resize加快匹配速度
im1 = imresize(im1, (im1.shape[1]//2, im1.shape[0]//2))
im2 = imresize(im2, (im2.shape[1]//2, im2.shape[0]//2))
wid = 5
harrisim = harris.compute_harris_response(im1, 5)
filtered_coords1 = harris.get_harris_points(harrisim, wid+1)
d1 = harris.get_descriptors(im1, filtered_coords1, wid)
harrisim = harris.compute_harris_response(im2, 5)
filtered_coords2 = harris.get_harris_points(harrisim, wid+1)
d2 = harris.get_descriptors(im2, filtered_coords2, wid)
print('starting matching')
matches = harris.match_twosided(d1, d2)
figure()
gray()
harris.plot_matches(im1, im2, filtered_coords1, filtered_coords2, matches)
show()
匹配结果：
该算法的结果存在一些不正确匹配。这是因为，与现代的一些方法（SIFT特征检测等）相比，图像像素块的互相关矩阵具有较弱的描述性。实际运用中，我们通常使用更稳健的方法来处理这些对应匹配。这些描述符还有一个问题，它们不具有尺度不变性和旋转不变性，而算法中像素块的大小也会影响对应匹配的结果。?
小结
Harris角点检测算法优缺点
优点：
- 旋转不变性，椭圆转过一定角度但是其形状保持不变（特征值保持不变）。
- 对于图像灰度的仿射变化具有部分的不变性，由于仅仅使用了图像的一介导数，对于图像灰度平移变化不变；
- 对于图像灰度尺度变化不变。
?缺点：
- 它对尺度很敏感，不具备几何尺度不变性。
- 提取的角点是像素级的
SIFT算法（尺度不变特征变换）?
SIFT简介
?尺度不变特征转换即SIFT (Scale-invariant feature transform)是一种计算机视觉的算法。它用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所发表，2004年完善总结。
? ? ? ?其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。
? ? ? 局部影像特征的描述与侦测可以帮助辨识物体，SIFT特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用 SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。
? ? ? SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。
SIFT算法可以的解决问题：
- 目标的旋转、缩放、平移（RST）
- 图像放射/投影变换（视点viewpoint）
- 光照影响（illumination）
- 部分目标遮挡（occlusion）
- 杂物场景（clutter）
-
噪声
SIFT算法流程图?
?
SIFT特征检测基本步骤
1. DoG尺度空间的极值检测：
首先构造DoG尺度空间，在SIFT中使用不同参数的高斯模糊来表示不同的尺度空间，而构造尺度空间是为了检测在不同尺度下都存在的特征点，特征点的检测比较常用的方法是高斯拉普拉斯，但是LoG的运算量是比较大的，Marr和Hidreth指出可以使用DoG（高斯差分）来近似计算LoG，所以在DoG的尺度空间下检测极值点。
2. 删除不稳定的极值点：
低对比度的极值点+不稳定的边缘响应点
3. 确定特征的的主方向：
以特征点的为中心、以3×1.5σ3×1.5σ为半径的领域内计算各个像素点的梯度的幅角和幅值，然后使用直方图对梯度的幅角进行统计。直方图的横轴是梯度的方向，纵轴为梯度方向对应梯度幅值的累加值，直方图中最高峰所对应的方向即为特征点的方向。
4. 生成特征描述子：
首先将坐标轴旋转为特征点的方向，以特征点为中心的16x16的窗口的像素的梯度幅值和方向，将窗口内的像素分为16块，每块是其像素内8个方向的直方图统计，共可以形成128维的特征向量。
?SIFT算法原理
1.检测尺度空间的极值
检测尺度空间极值就是搜索所有尺度上的图像位置，通过高斯微分函数来识别对于尺度和旋转不变的兴趣点。其主要步骤可以分为建立高斯金字塔、生成DOG高斯差分金字塔和DOG局部极值点检测。为了让大家更清楚，我先简单介绍一下尺度空间，再介绍主要步骤。
（1）尺度空间
一个图像的尺度空间
定义为一个变化尺度的高斯函数
与原图像
的卷积?
?
?其中，*表示卷积计算。?
?其中，m、n表示高斯模版的维度，(x,y)代表图像像素的位置。σ?为尺度空间因子，σ 值越小表示图像被平滑的越少，相应的尺度就越小。小尺度对应于图像的细节特征，大尺度对应于图像的概貌特征，效果如下图所示，尺度从左到右，从上到下，一次增大。??
?（2）建立高斯金字塔
?尺度空间在实现时，使用高斯金字塔表示，高斯金字塔的构建分为两部分：
1.对图像做不同尺度的高斯模糊
2.对图像做降采样（隔点采样）
图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金子塔的第一层，每次降采样所得到的新图像为金字塔的上一层(每层一张图像)，每个金字塔共n层。金字塔的层数根据图像的原始大小和塔顶图像的大小共同决定。
为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。如上图所示，将图像金字塔每层的一张图像使用不同参数做高斯模糊，使得金字塔的每层含有多张高斯模糊图像，将金字塔每层多张图像合称为一组(Octave)，金字塔每层只有一组图像，组数和金字塔层数相等，每组含有多层Interval图像。
高斯图像金字塔共o组、s层， 则有：
其中，σ表示尺度空间坐标，s表示sub-level层坐标，
表示初始尺度，S表示每组层数（一般为3~5）?
?（3）建立DOG高斯差分金字塔
为了有效提取稳定的关键点，利用不同尺度的高斯差分核与卷积生成。
DOG函数：
（4）DOG局部极值检测
特征点是由DOG空间的局部极值点组成的。为了寻找DOG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域 的相邻点大或者小。
?2.关键点方向分配
3.关键点的描述?
?4.关键点的匹配
SIFT算法实例
?1.VLFeat的配置
为了计算图像的SIFT特征，我们要用开源工具包VLFeat。
?VLFeat的下载地址：Index of /download (vlfeat.org)?
选择 vlfeat-0.9.20-bin.tar.gz?安装包下载，下载完成解压出来，找到bin目录下的win32文件夹，复制出来,放到你想放的位置（我放在了D:\VLfleat-bin,win32文件夹可改成你想要的名字，我改成win32vlfeat）
?然后打开win32vlfeat文件，复制它的位置路径（我的是D:\VLfleat-bin\win32vlfeat）,接着找到PCV库里的sift.py文件打开修改下面的process_image方法（sift.exe后面要有一个空格）即可完成配置
2.检测感兴趣点
# -*- coding: utf-8 -*-
from PIL import Image
from pylab import *
from PCV.localdescriptors import sift
from PCV.localdescriptors import harris
# 添加中文字体支持
from matplotlib.font_manager import FontProperties
font = FontProperties(fname=r"C:\Windows\Fonts\simsun.ttc", size=16)
#设置字体为楷体
matplotlib.rcParams['font.sans-serif'] = ['KaiTi']
imname = 'image/tingzi1.jpg'
im = array(Image.open(imname).convert('L'))
sift.process_image(imname, 'ting1.sift')
l1, d1 = sift.read_features_from_file('ting1.sift')
figure()
gray()
subplot(131)
sift.plot_features(im, l1, circle=False)
title(u'SIFT特征', fontproperties=font)
subplot(132)
sift.plot_features(im, l1, circle=True)
title(u'用圆圈表示SIFT特征尺度', fontproperties=font)
# 检测harris角点
harrisim = harris.compute_harris_response(im)
subplot(133)
filtered_coords = harris.get_harris_points(harrisim, 6, 0.1)
imshow(im)
plot([p[1] for p in filtered_coords], [p[0] for p in filtered_coords], '*')
axis('off')
title(u'Harris角点', fontproperties=font)
show()
可以看到，与Harris角点检测相比，sift提取出来的特征点信息更多，而且更加精准，这是因为sift的特征点提取步骤比Harris的步骤复杂的多，它需要建立高斯图像金字塔和高斯差分金字塔之后再检测极值，而Harris角点只是对原图进行角点检测和变化。?
3.匹配描述子
对于将一幅图像中的特征匹配到另一幅图像的特征，一种稳健的准则（同样是由Lowe提出的）是使用者两个特征距离和两个最匹配特征距离的比率。相比于图像中的其他特征，该准则保证能够找到足够相似的唯一特征。使用该方法可以使错误的匹配数降低。下面的代码实现了匹配函数。
from PIL import Image
from pylab import *
import sys
from PCV.localdescriptors import sift
from PIL import Image
from pylab import *
from numpy import *
import os
if len(sys.argv) >= 3:
im1f, im2f = sys.argv[1], sys.argv[2]
else:
im1f = 'image/shu1.jpg'
im2f = 'image/shu2.jpg'
im1 = array(Image.open(im1f))
im2 = array(Image.open(im2f))
sift.process_image(im1f, 'out_sift_3.txt')
l1, d1 = sift.read_features_from_file('out_sift_3.txt')
figure()
gray()
subplot(121)
sift.plot_features(im1, l1, circle=False)
sift.process_image(im2f, 'out_sift_4.txt')
l2, d2 = sift.read_features_from_file('out_sift_4.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()
Harris匹配结果：
可以看到SIFT算法的匹配效果比?Harris匹配效果好非常多，同一场景，尺度稍微改变了一下，Harris算法肉眼可见出现很多匹配错误点，而SIFT算法肉眼完全看不到匹配错误点，这是因为SIFT算法具有尺度和旋转不变性，即使两张图大小不一样、角度不一致也不会影响匹配结果，而Harris角点对尺度变化非常敏感，当遇到尺度变化较大时，很多正确特征点无法检测出来。
地理标记图像匹配
小结
SIFT算法的优点:
- 特性独特性，也就是特征点可分辨性高，类似指纹，适合在海量数据中匹配。
- 多量性，提供的特征多。
- 高速性，就是速度快。
- 可扩展，能与其他特征向量联合使用。
SIFT算法的缺点
- ?实时性不高。
- ?有时特征点较少。
- ?对边缘光滑的目标无法准确提取特征点。
- SIFT采用henssian矩阵获取图像局部最值还是十分稳定的，但是在求主方向阶段太过于依赖局部区域像素的梯度方向，
- 有可能使得找到的主方向不准确，后面的特征向量提取以及匹配都严重依赖于主方向，即使不大偏差角度也可以造成后面特征匹配的放大误差，从而匹配不成功；
- 另外图像金字塔的层取得不足够紧密也会使得尺度有误差，后面的特征向量提取同样依赖相应的度，发明者在这个问题上的折中解决方法是取适量的层然后进行插值。
- SIFT是一种只利用到灰度性质的算法，忽略了色彩信息.
