《SIFT算法与RANSAC算法分析》由会员分享，可在线阅读，更多相关《SIFT算法与RANSAC算法分析（7页珍藏版）》请在装配图网上搜索。
1、概率论问题征解报告:（算法分析类）SIFT算法与RANSAC算法分析班级：自23姓名：学号：作业号：146SIFT算法是用于图像匹配的一个经典算法，RANSAC算法是用于消除噪声的算法，这两 者经常被放在一起使用，从而达到较好的图像匹配效果。以下对这两个算法进行分析，由于sift算法较为复杂，只重点介绍其中用到的概率统计 概念与方法一一高斯卷积及梯度直方图，其余部分只做简单介绍。一. SIFT1. 出处：David G. Lowe, The Proceedings of the Seventh IEEE International Conference on (Volume:2, Pages
2、1150 - 1157), 19992. 算法目的：提出图像特征，并且能够保持旋转、缩放、亮度变化保持不变性，从而 实现图像的匹配3.算法流程图:4.算法思想简介:(1)特征点检测相关概念： 特征点：Sift中的特征点指十分突出、不会因亮度而改变的点，比如角点、边 缘点、亮区域中的暗点等。特征点有三个特征：尺度、空间和大小尺度空间：我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的 物体也总是通过不同尺度的观察而得到不同的变化。尺度空间理论最早在 1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度 下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮
3、 廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺 度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时 目标在视网膜上的形成过程。尺度越大图像越模糊。 高斯模糊：高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间，L(x,y,。)，定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,。)卷积 运算高斯函数:g(%，任)=矗高斯卷积的尺度空间L(x，yqexp(x - x )2 + (y - y )2 ii26 J)=G (x, yq)* I (x, y )不难看到，高斯函数与正态分布函数有点类似，所以在计算时，我们也是 依据精度及效率的综
4、合考虑，认为在3。以外的像素都不起作用，而计算机实现时，一般取(6。+1) * (6。+1)。颜色直方图与梯度直方图：在视觉算法中，直方图是个经常使用的统计概念。一般用到的都是颜色直方图。因一幅图像中，往往少数几种颜色就涵盖了图像 的大多数像素，而且不同颜色在图像中的出现概率是不同的，因此，可以通过 统计图像中各种颜色出现的概率，选出最频繁出现的几种做为主色。使用主色 并不会降低颜色匹配的效果，因为颜色直方图中出现频率很低的哪些颜色往往 不是图像的主要内容，从某种程度上讲，是对图像内容表示的一种噪声。在sift 算法中使用的梯度直方图也是差不多的想法，只不过统计的是梯度而不是颜色， 因为我们要
5、找的特征点是梯度变化大的点。(2) 特征点匹配DOG算子计算局部极值点。中间的检测点和它同尺度的8个相邻点和 上下相邻尺度对应的9x2个点共26个点比较，以确保在尺度空间和二维图 像空间都检测到极值点。(3) 特征点方向分配确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定 区域内的图像像素点对关键点方向生成所作的贡献。(4) 特征点的描述描述子由2X2X8维向量表征，也即是2X2个8方向的方向直方图组 成。左图的种子点由8X8单元组成。每一个小格都代表了特征点邻域所在 的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像 素的幅值。然后在4X4的窗口内计算8个方向的
6、梯度方向直方图。绘制每 个梯度方向的累加可形成一个种子点。(5) 特征点匹配一般采用kd树进行完成搜索匹配。二. RANSAC1. 出处：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为初始化模型参数所需的最小 样本数)和一个
7、样本集P，集合P的样本数#(P)n，从P中随机抽取包 含n个样本的P的子集S初始化模型M；(2) 余集SC=PS中与模型M的误差小于某一设定阈值t的样本集以及S构 成S*。S*认为是内点集，它们构成S的一致集；(3) 若#(S*)NN，认为得到正确的模型参数，并利用集S*采用最小二乘等 方法重新计算新的模型M*；重新随机抽取新的S，重复以上过程。(4) 在完成一定的抽样次数后，若未找到一致集则算法失败，否则选取抽 样后得到的最大一致集判断内外点，算法结束。三. 程序运行结果图以下四组图片给出了四种不同情况下的程序运行结果。黑框中三行分别给出 了两幅图的特征点数目及匹配点数目。图像中红色连线表示
8、计算出来的匹配点。1.图像稍微偏转C:windowssystem 22cm d.,exe.Finding 16? Features in C：XUsers Mdministra ure0-jpg. FindinJ 279 Features utel -.ipg-. Found 61 total matches2,图像完全翻转就 C:vji nd wiE-EystB m3 2cimd.eK&(Finding 167 featuies in C： Useissfirtministratorl)esktopX| ureB-jpg-.ringing 188 features in C： XUseisx
9、flclriinistratOFXDesktopX Lire2 - Jpg -.Fotind 42licit：idles画 Matches3.图像大小不同ISi C:vji ndowsksystem 3 2cmd.exeFinding 167 features in C： xUseiAdninistiatoiDesltapT-； ure0. jpgr. .kindling 139 features In G二 7J占曲咨、0。11：111：1：3：*砒心、1)85：虹叩、习8格率伦1读书报告9：1。七 p.ipe3 . Jpgr. - .ound 56 total nkdtc;hcsE MatchesI T 回4.不同光线下的图像曲 C:wind ows5ystem 32cm d.exeJFindirijgr 167 fccituresin C； SUscissfldiniristrpict0 = jpy 日Finding 127 features in C: Misers fl dm in istratorDesktorX|书报告、。让上iie4-jpgr-.-Found 32 total natchesMatchy. 回 1-
SIFT算法与RANSAC算法分析
