概率论问题征解报告：
（算法分析类）
SIFT算法与RANSAC算法分析
班级：自23
姓名：***
学号：**********
作业号：146
SIFT 算法是用于图像匹配的一个经典算法，RANSAC 算法是用于消除噪声的算法，这两者经常被放在一起使用，从而达到较好的图像匹配效果。

以下对这两个算法进行分析，由于sift 算法较为复杂，只重点介绍其中用到的概率统计概念与方法——高斯卷积及梯度直方图，其余部分只做简单介绍。

一． SIFT
1. 出处：David G. Lowe, The Proceedings of the Seventh IEEE International Conference
on (Volume:2, Pages 1150 – 1157), 1999 2. 算法目的：提出图像特征，并且能够保持旋转、缩放、亮度变化保持不变性，从而
实现图像的匹配 3. 算法流程图：
原图像
4. 算法思想简介：
（1） 特征点检测相关概念：
◆ 特征点：Sift 中的特征点指十分突出、不会因亮度而改变的点，比如角点、边
缘点、亮区域中的暗点等。

特征点有三个特征：尺度、空间和大小 ◆ 尺度空间：我们要精确表示的物体都是通过一定的尺度来反映的。

现实世界的
物体也总是通过不同尺度的观察而得到不同的变化。

尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。

尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。

尺度越大图像越模糊。

◆ 高斯模糊：高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L
（x,y,σ) ,定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,σ) 卷积运算
高斯函数：
高斯卷积的尺度空间：
不难看到，高斯函数与正态分布函数有点类似，所以在计算时，我们也是依据精度及效率的综合考虑，认为在3σ以外的像素都不起作用，而计算
()()()
,,,,*,L x y G x y I x y
σσ=()22221
()(),,exp 22i i i i x x y y G x y σπσσ⎛⎫-+-=- ⎪
⎝⎭
机实现时，一般取（6σ+1）*（6σ+1）。

颜色直方图与梯度直方图：在视觉算法中，直方图是个经常使用的统计概念。

一般用到的都是颜色直方图。

因一幅图像中，往往少数几种颜色就涵盖了图像
的大多数像素，而且不同颜色在图像中的出现概率是不同的，因此，可以通过
统计图像中各种颜色出现的概率，选出最频繁出现的几种做为主色。

使用主色
并不会降低颜色匹配的效果，因为颜色直方图中出现频率很低的哪些颜色往往
不是图像的主要内容，从某种程度上讲，是对图像内容表示的一种噪声。

在sift
算法中使用的梯度直方图也是差不多的想法，只不过统计的是梯度而不是颜色，因为我们要找的特征点是梯度变化大的点。

（2）特征点匹配
DOG算子计算局部极值点。

中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图
像空间都检测到极值点。

（3）特征点方向分配
确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。

（4）特征点的描述
描述子由2×2×8维向量表征，也即是2×2个8方向的方向直方图组成。

左图的种子点由8×8单元组成。

每一个小格都代表了特征点邻域所在
的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像
素的幅值。

然后在4×4的窗口内计算8个方向的梯度方向直方图。

绘制每
个梯度方向的累加可形成一个种子点。

（5）特征点匹配
一般采用kd树进行完成搜索匹配。

二．RANSAC
1.出处：Martin A. Fischler, Robert C. Bolles, Communication of the ACM CACM
Homepage archive (Volume 24 Issue 6, Pages 381-395), June 1981.
2.算法目的：根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，
得到有效样本数据
3.算法思想介绍：
（1）考虑一个最小抽样集的势为n的模型(n为初始化模型参数所需的最小样本数)和一个样本集P，集合P的样本数#(P)>n，从P中随机抽取包
含n个样本的P的子集S初始化模型M；
（2）余集SC=P\S中与模型M的误差小于某一设定阈值t的样本集以及S构成S*。

S*认为是内点集，它们构成S的一致集；
（3）若#(S*)≥N，认为得到正确的模型参数，并利用集S*采用最小二乘等方法重新计算新的模型M*；重新随机抽取新的S，重复以上过程。

（4）在完成一定的抽样次数后，若未找到一致集则算法失败，否则选取抽样后得到的最大一致集判断内外点，算法结束。

三．程序运行结果图
以下四组图片给出了四种不同情况下的程序运行结果。

黑框中三行分别给出了两幅图的特征点数目及匹配点数目。

图像中红色连线表示计算出来的匹配点。

1.图像稍微偏转
2.图像完全翻转
3.图像大小不同
4.不同光线下的图像。