计算机视觉——SIFT图像匹配算法
全称Scale Invariant Feature Transform，尺度不变特征变换，由加拿大教授David G.Lowe提出的。SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是一种非常稳定的局部特征。
SIFT算法的实质可以归为在不同尺度空间上查找特征点（关键点）的问题。
多量性，即使是很少几个物体也可以产生大量的SIFT特征 高速性，经优化的SIFT匹配算法甚至可以达到实时性 扩招性，可以很方便的与其他的特征向量进行联合。
1.尺度空间的极值检测： 搜索所有尺度空间上的图像，通过高斯微分函数来识别潜在的对尺度和选择不变的兴趣点。
2.特征点定位： 在每个候选的位置上，通过一个拟合精细模型来确定位置尺度，关键点的选取依据他们的稳定程度。
3.特征方向赋值： 基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向，后续的所有操作都是对于关键点的方向、尺度和位置进行变换，从而提供这些特征的不变性。
4.特征点描述： 在每个特征点周围的邻域内，在选定的尺度上测量图像的局部梯度，这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变换。
我们可以通过图像的模糊程度来模拟人在距离物体由远到近时物体在视网膜上成像过程，距离物体越近其尺寸越大图像也越模糊，这就是高斯尺度空间，使用不同的参数模糊图像（分辨率不变），是尺度空间的另一种表现形式。
σ称为尺度空间因子，它是高斯正态分布的标准差，反映了图像被模糊的程度，其值越大图像越模糊，对应的尺度也就越大。L(x,y,σ)代表着图像的高斯尺度空间。
图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金子塔的第一层，每次降采样所得到的新图像为金字塔的一层(每层一张图像)，每个金字塔共n层。
图像金字塔是同一图像在不同的分辨率下得到的一组结果，其生成过程一般包括两个步骤：
1.对原始图像进行平滑
2.对处理后的图像进行降采样
什么是降采样：在数位信号处理领域中，降采样，又作减采集,是一种多速率数字信号处理的技术或是降低信号采样率的过程，通常用于降低数据传输速率或者数据大小。
降采样后得到一系列不断尺寸缩小的图像。显然,一个传统的金字塔中，每一层的图像是其上一层图像长、高的各一半。多分辨率的图像金字塔虽然生成简单，但其本质是降采样，图像的局部特征则难以保持，也就是无法保持特征的尺度不变性。
为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。将图像金字塔每层的一张图像使用不同参数做高斯模糊，使得金字塔的每层含有多张高斯模糊图像，将金字塔每层多张图像合称为一组(Octave)，金字塔每层只有一组图像，组数和金字塔层数相等，每组含有多张(也叫层Interval)图像。另外，降采样时，高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第三张图像隔点采样得到的。
为什么要搭建高斯金字塔：高斯金字塔模仿的是图像的不同的尺度，尺度应该怎样理解？对于一副图像，你近距离观察图像，与你在一米之外观察，看到的图像效果是不同的，前者比较清晰，后者比较模糊，前者比较大，后者比较小，通过前者能看到图像的一些细节信息，通过后者能看到图像的一些轮廓的信息，这就是图像的尺度，图像的尺度是自然存在的，并不是人为创造的。好了，到这里我们明白了，其实以前对一幅图像的处理还是比较单调的，因为我们的关注点只落在二维空间，并没有考虑到“图像的纵深”这样一个概念，如果将这些内容考虑进去我们是不是会得到更多以前在二维空间中没有得到的信息呢？于是高斯金字塔横空出世了，它就是为了在二维图像的基础之上，榨取出图像中自然存在的另一个维度：尺度。因为高斯核是唯一的线性核，也就是说使用高斯核对图像模糊不会引入其他噪声，因此就选用了高斯核来构建图像的尺度。
高斯金字塔的组数和层数：
在高斯金字塔中，有两个参数很重要，一个是第几组o，一个是某一组中的第几层s，这两个量合起来（o，s）就构成了高斯金字塔的尺度空间。变量o控制的是金字塔中尺寸这个尺度，s用来区分同一个尺寸尺度下的图像，s确定了一个组中不同的模糊成度。这样，（o，s）就可以确定高斯金字塔中的唯一一副图像。
根据lowe论文中指出，（o，s）作用于一幅图像是通过下列公式实现的：
σ=σ0∗2o+sS\sigma=\sigma_0*2^{o+\frac{s}{S}}σ=σ0∗2o+Ss
其中σ0\sigma_0σ0为高斯模糊的初始值，S为每层的层数。
D(x,y,σ)=[G(x,y,kσ)−G(x,y,σ)]∗I(x,y)=L(x,y,kσ)−L(x,y,σ)D(x,y,\sigma)=[G(x,y,k\sigma)-G(x,y,\sigma)]*I(x,y)=L(x,y,k\sigma)-L(x,y,\sigma)D(x,y,σ)=[G(x,y,kσ)−G(x,y,σ)]∗I(x,y)=L(x,y,kσ)−L(x,y,σ)
其中，L(x,y,σ)是图像的高斯尺度空间。从上式可以知道，将相邻的两个高斯空间的图像相减就得到了DoG的响应图像。为了得到DoG图像，先要构建高斯尺度空间，而高斯的尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数σ进行高斯模糊，使每层金字塔有多张高斯模糊过的图像。 DoG金字塔：高斯金字塔构建成功后，将每一组相邻的两层相减就可以得到DoG金字塔.DoG图像描绘的是目标的轮廓
通过比较检测得到的DoG的局部极值点所在离散的空间搜索得到的，由于离散空间是对连续空间采样得到的结果，在离散空间找到的极值点不一定是真正意义上的极值点，因此要设法将不满足条件的点剔除掉。可以通过尺度空间DoG函数进行曲线拟合寻找极值点，这一步的本质是去掉DoG局部曲率非常不对称的点。
要剔除掉的不符合要求的点主要有两种：
为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间的Taylor展开式(拟合函数)为：
D(X)=D+αDrαX+12Xrα2DαX2XD(X)=D+\frac{\alpha D^r}{\alpha X}+\frac{1}{2}X^r\frac{\alpha ^2D}{\alpha X^2}XD(X)=D+αXαDr+21XrαX2α2DX
其中，X=(x,y,σ)rX=(x,y,\sigma)^rX=(x,y,σ)r求导并让方程等于零，可以得到极值点的偏移量为：
X^=−α2D−1αX2α2DαX\hat{X}=-\frac{\alpha^2 D^-1}{\alpha X^2}\frac{\alpha^2 D}{\alpha X}X^=−αX2α2D−1αXα2D
对应极值点，方程的值为：
D(X^)=D+12αDrαXX^D(\hat{X})=D+\frac{1}{2}\frac{\alpha D^r}{\alpha X}\hat{X}D(X^)=D+21αXαDrX^
其中,X^=(x,y,σ)r\hat{X}=(x,y,\sigma)^rX^=(x,y,σ)r代表相对插值中心的偏移量，当它在任一维度上的偏移量大于0.5时（即x或y或），意味着插值中心已经偏移到它的邻近点上，所以必须改变当前关键点的位置。同时在新的位置上反复插值直到收敛；也有可能超出所设定的迭代次数或者超出图像边界的范围，此时这样的点应该删除，在Lowe中进行了5次迭代。另外，∣D(x)∣|D(x)|∣D(x)∣过小的点易受噪声的干扰而变得不稳定，所以将∣D(x)∣|D(x)|∣D(x)∣小于某个经验值(Lowe论文中使用0.03，Rob Hess等人实现时使用0.04/S)的极值点删除。同时，在此过程中获取特征点的精确位置(原位置加上拟合的偏移量)以及尺度(σ(o,s)和σoct(s)\sigma(o,s)和\sigma_oct(s)σ(o,s)和σoct(s))。
4.2.2不稳定的边缘响应点一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。
DOG算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。获取特征点处的Hessian矩阵，主曲率通过一个2x2 的Hessian矩阵H求出：
H=[DxxDxyDxyDyy]H=\begin{bmatrix}
D_{xx} & D_{xy}\\D_{xy} & D_{yy}
\end{bmatrix}H=[DxxDxyDxyDyy]
H的特征值α和β代表x和y方向的梯度
Tr(H)=Dxx+Dyy=α+β T_r(H)= D_{xx} +D_{yy} =\alpha+\betaTr(H)=Dxx+Dyy=α+β
Det(H)=Dxx+Dyy−Dxy2=α∗βD_{et}(H)= D_{xx} +D_{yy} -D_{xy}^2=\alpha*\betaDet(H)=Dxx+Dyy−Dxy2=α∗β
其中Tr(H)T_r(H)Tr(H)为矩阵H的迹（对角线元素之和) Det(H)D_{et}(H)Det(H)表示矩阵H的行列式.为了避免求具体的值，可使用H特征值得比例。假设是α较大的特征值，而是β较小的特征值，令γ=αβ\gamma=\frac{\alpha}{\beta}γ=βα表示最大特征值和最小特征值的比值，则Tr(H)2Det(H)=(α+β)2αβ2=(γβ+β)2γβ2=(γ+1)2γ\frac{T_r(H)^2}{D_{et}(H)}=\frac{(\alpha+\beta)^2}{\alpha\beta^2}=\frac{(\gamma\beta+\beta)^2}{\gamma\beta^2}=\frac{(\gamma+1)^2}{\gamma}Det(H)Tr(H)2=αβ2(α+β)2=γβ2(γβ+β)2=γ(γ+1)2
上式的结果与两个特征值的比例有关，和具体的大小无关，当两个特征值相等时其值最小，并且随着γ\gammaγ的增大而增大，因此为了检测主曲率是否在某个阈值TrT_rTr下，只需要检测Tr(H)2Det(H)>(Tr+1)2Tr\frac{T_r(H)^2}{D_{et}(H)}>\frac{(T_r+1)^2}{T_r}Det(H)Tr(H)2>Tr(Tr+1)2
如果上式成立，则剔除该特征点，否则保留。（论文中TrT_rTr取10）
经过上面的步骤已经找到了在不同尺度下都存在的特征点，为了实现图像旋转不变性，需要给特征点的方向进行赋值。利用特征点邻域像素的梯度分布特性来确定其方向参数，再利用图像的梯度直方图求取关键点局部结构的稳定方向。
找到了特征点，也就可以得到该特征点的尺度σ，也就可以得到特征点所在的尺度图像：
L(x,y,σ)=G(x,y,σ)∗I(x,y)L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)L(x,y,σ)=G(x,y,σ)∗I(x,y)
计算以特征点为中心、以3×1.5σ3×1.5σ为半径的区域图像的幅角和幅值，每个点L(x,y)的梯度的模m(x,y)以及方向θ(x,y)可通过下面公式求得
梯度方向：
计算得到梯度方向后，就要使用直方图统计特征点邻域内像素对应的梯度方向和幅值。
梯度方向的直方图的横轴是梯度方向的角度（梯度方向的范围是0到360度，直方图每36度一个柱共10个柱，或者没45度一个柱共8个柱），纵轴是梯度方向对应梯度幅值的累加。
主方向：在直方图的峰值就是特征点的主方向
辅助方向：当存在一个相当于主峰值80%能量的柱值时，则可以将这个方向认为是该特征点辅助方向。所以，一个特征点可能检测到多个方向（也可以理解为，一个特征点可能产生多个坐标、尺度相同，但是方向不同的特征点）。Lowe在论文中指出15%的关键点具有多方向，而且这些点对匹配的稳定性很关键。
在Lowe的论文还提到了使用高斯函数对直方图进行平滑以增强特征点近的邻域点对关键点方向的作用，并减少突变的影响。为了得到更精确的方向，通常还可以对离散的梯度直方图进行插值拟合。具体而言，关键点的方向可以由和主峰值最近的三个柱值通过抛物线插值得到。
得到特征点的主方向后，对于每个特征点可以得到三个信息(x,y,σ,θ)，即位置、尺度和方向。由此可以确定一个SIFT特征区域，一个SIFT特征区域由三个值表示，中心表示特征点位置，半径表示关键点的尺度，箭头表示主方向。具有多个方向的关键点可以被复制成多份，然后将方向值分别赋给复制后的特征点，一个特征点就产生了多个坐标、尺度相等，但是方向不同的特征点。
通过以上的步骤已经找到了SIFT特征点位置、尺度和方向信息，下面就需要使用一组向量来描述关键点也就是生成特征点描述子，这个描述符不只包含特征点，也含有特征点周围对其有贡献的像素点。描述子应具有较高的独立性，以保证匹配率。
特征描述符的生成大致有三个步骤：1.校正旋转主方向，确保旋转不变性。
2.生成描述子，最终形成一个128维的特征向量
3.归一化处理，将特征向量长度进行归一化处理，进一步去除光照的影响。
为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转θ（特征点的主方向）角度，即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为：
旋转后以主方向为中心取 8×8的窗口。下图所示，左图的中央为当前关键点的位置，每个小格代表为关键点邻域所在尺度空间的一个像素，求取每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，长度代表梯度幅值，然后利用高斯窗口对其进行加权运算。最后在每个4×4的小块上绘制8个方向的梯度直方图，计算每个梯度方向的累加值，即可形成一个种子点，如右图所示。每个特征点由4个种子点组成，每个种子点有8个方向的向量信息。这种邻域方向性信息联合增强了算法的抗噪声能力，同时对于含有定位误差的特征匹配也提供了比较理性的容错性。
Lowe实验结果表明：描述子采用448=128维向量表征，综合效果最优（不变性与独特性）
通过对特征点周围的像素进行分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。
小结： 我这里拍摄了多个场景以及同一个场景的不同角度的照片。 第一张图和第二张图片是同一个建筑物的不同尺度，但标记的SIFT点在很大程度上相同，比如门和窗这样细小的部分中标记的位置都相似，可以看出SIFT算法的局部特征非常的稳定。 SIFT和Harris 相比较：从结果来直接看，发现SIFT算法的特征点比Harris角点的特征点保留的更多，它需要建立高斯图像金字塔和高斯差分金字塔之后再检测极值，而Harris角点只是对原图进行角点检测和变化，Harris特征点检测存在角点信息丢失与偏移的现象。在运行程序时，与Harris的效率相比，SIFT的效率有大的提升，程序的运行很快。
将此部分测试分类为以下3种：
同一场景不同角度的匹配 完全不同场景的匹配 较为相似的场景匹配（可能是同一建筑可能不是）1.同一场景不同角度的匹配：
小结：
2.完全不同场景的匹配：
小结：
3.较为相似的场景匹配：
小结：
输入：
输出：
小结： 这组代码测试我又挑选了同一片街区但是场景最丰富的一组，输入的图片是更远处的2栋高楼，输出的结果非常正确。第一张图片是匹配到了咖色楼的部分较多，而第二张图片匹配到了较远处的那2栋高楼，第三张图片是匹配到了路对面的高楼。 输入图片与数据集中图片两两进行特征匹配后的匹配数保存在数组中，要找到与输入图片匹配特征点最多的图，最后将矩阵中数值最大的三个位置输出。SIFT在大量数据库中速度也非常快。 匹配的结果非常精确，可见SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是一种非常稳定的局部特征。
作者：Nikki_du
