SIFT特征匹配+RANSAC滤除_sift+ransac

SIFT原理介绍

步骤分为两步：

1. 特征点检出
2. 特征点描述

特征点检出

主要是用了DoG，就是把图像做不同程度的高斯模糊blur，平滑的区域或点肯定变化不大，而纹理复杂的比如边缘，点，角之类区域肯定变化很大，这样变化很大的点就是特征点。当然为了找到足够的点，还需要把图像放大缩小几倍（Image Pyramids）来重复这个步骤找特征点。可代替特征点检出的还有很多其他方法，如MSER等。

1. 候选关键点
   Koenderink（1984）和Lindeberg（1994）已经证明，在各种合理的假设下，高斯函数是唯一可能的尺度空间核。因此，图像的尺度空间被定义为函数​，它是由一个可变尺度的高斯核和输入图像生成， ​ 其中高斯核为， ​ 为了有效检测尺度空间中稳定的极点，Lowe于1999年提出在高斯差分函数(DOG)中使用尺度空间极值与图像做卷积，这可以通过由常数乘法因子​分隔的两个相邻尺度的差来计算。用公式表示就是， ​ 由于平滑区域临近像素之间变化不大，但是在边、角、点这些特征较丰富的地方变化较大，因此通过DOG比较临近像素可以检测出候选关键点。
   
   （1）Octave组数 = [log₂(min(M, N))] - 3，层数S = n + 3，其中n代表想要在DOG空间上使用几个图片来计算特征点
   （2）
   （3）
   
   

2. 关键点定位
   检测出候选关键点之后，下一步就是通过拟合精细的模型来确定位置和尺度。 2002年Brown提出了一种用3D二次函数来你和局部样本点，来确定最大值的插值位置，实验表明，这使得匹配和稳定性得到了实质的改进。 他的具体方法是对函数​进行三元二阶泰勒展开， ​ 上述的展开式，就是所要的拟合函数。 极值点的偏移量为， ​ 如果偏移量在任何一个维度上大于0.5时，则认为插值中心已经偏移到它的邻近点上，所以需要改变当前关键点的位置，同时在新的位置上重复采用插值直到收敛为止。如果超出预先设定的迭代次数或者超出图像的边界，则删除这个点。
   这部分数学太多

特征点描述

就是一个简单版的HOG，即以检出的特征点为中心选16x16的区域作为local patch，这个区域又可以均分为4x4个子区域，每个子区域中各个像素的梯度都可以分到8个bin里面，这样就得到了4x4x8=128维的特征向量。特征点检出以后还需要一个很重要的步骤，就是归一化，计算这个patch的主方向，然后根据这个主方向把patch旋转到特定方向，这样计算的特征就有了方向不变性，也需要根据patch各像素梯度大小把patch缩放到一定的尺度，这样特征就有了尺度不变性。

1. 方向分配
   根据图像的图像，可以为每个关键定指定一个基准方向，可以相对于这个指定方向表示关键点的描述符，从而实现了图像的旋转不变性。 关键点的尺度用于选择尺度最接近的高斯平滑图像，使得计算是以尺度不变的方式执行，对每个图像​，分别计算它的梯度幅值和梯度方向， ​ ​ 然后，使用方向直方图统计关键点邻域内的梯度幅值和梯度方向。将0~360度划分成36个区间，每个区间为10度，统计得出的直方图峰值代表关键点的主方向。

2. 局部特征描述
   通过前面的一系列操作，已经获得每个关键点的位置、尺度、方向，接下来要做的就是用已知特征向量把它描述出来，这是图像特征提取的核心部分。为了避免对光照、视角等因素的敏感性，需要特征描述子不仅仅包含关键点，还要包含它的邻域信息。
   
   SIFT使用的特征描述子和后面要讲的HOG有很多相似之处。它一检测得到的关键点为中心，选择一个1616的邻域，然后再把这个邻域再划分为44的子区域，然后对梯度方向进行划分成8个区间，这样在每个子区域内就会得到一个4x4x8=128维的特征向量，向量元素大小为每个梯度方向区间权值。提出得到特征向量后要对邻域的特征向量进行归一化，归一化的方向是计算邻域关键点的主方向，并将邻域旋转至根据主方向旋转至特定方向，这样就使得特征具有旋转不变性。其实这一步，是在得到稳定直方图之前做的，然后才能得到128维特征向量。然后再根据邻域内各像素的大小把邻域缩放到指定尺度，进一步使得特征描述子具有尺度不变性。

3. 最后匹配的时候，使用KNN来进行匹配，算法复杂度是O(nlogn)
   opencv中knnMatch是一种蛮力匹配，基本原理是将待匹配图片的sift特征与目标图片中的全部sift特征一对n的遍历，找出相似度最高的前k个。当待匹配的图片增多时，需要的计算量太大，所以考虑是否可以通过降维的方式减少计算过程中的时间花费。
   https://blog.csdn.net/yhyhbo/article/details/54620178

具体使用的是opencv的这个——BFMatcher
https://blog.csdn.net/GAN_player/article/details/78285771

其实确切来说，SIFT是指第二步的特征，而SIFT features或SIFT descriptor的说法应该比较准确。

RANSAC原理介绍

链接

随机抽样一致算法（random sampleconsensus,RANSAC）

步骤如下：

STEP1

从样本集中随机选取一组足以计算模型参数的子样本，计算得到模型参数
比如两个点确定一条直线。

STEP2

判断模型参数的质量
比如最小二乘，计算每个点到当前直线的距离，设置一个阈值，在阈值范围内的点的数量作为评价直线质量的指标

STEP3

重复上述步骤，记录质量最好的模型；满足迭代条件时退出（达到迭代次数）

总之

由于通过SIFT的match，比如knn算法，已经得到两张图的特征点匹配，于是可以得到一个图到另一个图的单应性矩阵。RANSAC的作用其实就是选点对，我们任意四个点都可以算出一个旋转矩阵，但我们想要一个好的变换矩阵，相当于说将点变换到另一幅图，然后算误差，误差小的就是支持这个模型参数的点对。支持最多的就是最好的变换矩阵。

1. 参数介绍

nm：总的匹配点个数；

内点：正确匹配点；

外点：错误匹配点；

p_badxform：允许的错误概率=0.01；

in：当前内点集中元素个数，即符合当前矩阵的匹配点数；

in_min：内点集中元素个数允许的最小值，即保证RANSAC最终计算出的转换矩阵的错误概率小于p_badxform所需的最小内点数目；

in_max：最优内点集(最大一致集)中元素的个数，初始值为0；

in_frac：内点占总的匹配个数的比例，初始值设为0.25；

k：迭代次数，与计算当前模型的错误概率有关；

M：变换矩阵；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 具体步骤：
   https://blog.csdn.net/masibuaa/article/details/9145441
   RANSAC算法在SIFT特征筛选中的主要流程是：

(1) 从样本集中随机抽选一个RANSAC样本，即4个匹配点对

(2) 根据这4个匹配点对计算变换矩阵M

(3) 根据样本集，变换矩阵M，和误差度量函数计算满足当前变换矩阵的一致集consensus，并返回一致集中元素个数

(4) 根据当前一致集中元素个数判断是否最优(最大)一致集，若是则更新当前最优一致集

(5) 更新当前错误概率p，若p大于允许的最小错误概率则重复(1)至(4)继续迭代，直到当前错误概率p小于最小错误概率

参考链接

Ransac和最小二乘的区别
RANSAC与最小二乘区别：最小二乘法尽量去适应包括局外点在内的所有点。相反，RANSAC能得出一个仅仅用局内点计算出模型，并且概率还足够高。但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，必须小心的选择算法的参数（参数配置）。