精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

这篇具有很好参考价值的文章主要介绍了精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

精匹配——RANSAC算法思想及优缺点


前言

基于特征的图像匹配中会存在误匹配对,因此为提高匹配率,在粗匹配的基础上实现精匹配,可采用下面两种方法:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比


以下是本篇文章正对RANSAC的学习记录

一、RANSAC简介

RANSAC(RANdom SAmple Consensus随机采样一致性算法),是在一组含有“外点”的数据中,不断迭代,最终正确估计出最优参数模型的算法。
  • 主要解决样本中的外点问题,最多可处理50%的外点情况。
  • 内点:符合最优参数模型的点。
  • 外点:不符合最优参数模型的点,一般指的数据中的噪声或无效点,比如说匹配中的误匹配对和估计曲线中的离群点。
  • 外点检测算法
  • 应用:在计算机视觉的匹配问题中广泛应用,以寻找最佳的匹配模型,达到去除误匹配对,实现精匹配的效果。

二、RANSAC基本思想

1.步骤

 1. 在样本N中随机采样K个点 	
 2. 对这K个点进行模型拟合	
 3. 计算其他点到该拟合模型的距离,并设置阈值,若大于阈值,为外点,则舍弃,小于阈值,为内点,统计内点个数。阈值:为经验值,由具体应用和数据集决定。
 4. 然后以新的内点为基础,再次进行步骤2,得到新的拟合模型,迭代M次,选择内点数最多的模型,此时的模型为最优模型。
 5. 也可以在此基础上,选择出内点数最多的模型,然后对它进行重新估计,估计的时候可以采用最小二乘法来拟合。

2.迭代次数的公式

RANSAC算法中需要进行M次的迭代过程,且迭代的次数也是可以进行估算的。
————————————————————
1、n数据中内点所占的比例(内点的概率p):
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
2、选取的K个点至少有一个是外点的概率:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
3、因此就能得到迭代M次的情况下,选取点都是外点的概率,进而得到迭代M次中,至少有一次选取点k个点都是内点的概率,也就是正确模型的概率:z一般要求满足大于95%即可。
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
4、最终得到迭代次数M:
M = log(1-z)/log(1-p^k )
———————————————————

3.举例(拟合直线,拟合最佳单应性矩阵)

如下(示例1):

用RANSAC算法来拟合直线:

1、首先随机选取K=2个点,且两个点能拟合出一条直线
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
2、根据拟合直线,计算其他点到该拟合模型的距离,并设置阈值,其中绿色点为小于阈值的点,为内点,黄色的为外点,此时绿色内点为9。
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
3、然后通过此时的绿色内点,拟合出新的直线,再次计算该拟合新直线情况下的内点数目,此过程不断迭代,找到内点数最大的模型。
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比


如下(示例2):

用RANSAC算法来寻找最佳单应性矩阵H

在特征匹配中,我们最终要得到一个3*3的单应性矩阵。通常令h33=1来归一化矩阵,因此单应性矩阵有8个自由度h11-h32,求这八个未知数,至少要包含四个匹配点对。
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
其中(x,y)表示目标图像角点位置,(x’,y’)为场景图像角点位置,s为尺度参数。

h33=1来归一化矩阵?
H单应性矩阵,描述两个平面的映射关系,平面中点的坐标是二维的,第三维取1,为了简单化,将h33=1,为最简单的非零值,来归一化矩阵。
——————
步骤:
通过SIFT算法已经进行了粗匹配,然后利用RANSAC算法来进精匹配。

1、首先在得到的匹配点中,随机选择4个匹配点对(不共线),其他匹配点为外点。

2、根据4对内点计算单应性矩阵。

3、根据此矩阵来测试其他匹配点(计算的是其他匹配点与该模型的投影误差),并设置阈值,若小于为新内点,若大于则为外点,也就是误匹配对,因此通过计算出的单应性矩阵,就能实现一次误匹配点的剔除。

4、将所有的内点统计进行内点更新,在此基础上再次进行步骤3,迭代M次,最终得到含有内点最多的模型,此时模型为最优模型,也就是我们最终所需要的单应性矩阵。

———
大体步骤确定后,我们还需要进行两个参数的确定,阈值和迭代次数。
阈值:经验值
迭代次数:根据上述迭代次数M公式计算得到
——
如何用寻找到的单应性矩阵H来测试该模型下的其他匹配点?
根据代价函数计算,代价函数最小的模型为最优模型。
根据统计的内点数目,数目最多的为最优模型。

三、最小二乘法

1、最小二乘法的主要思想

通过确定未知参数(通常是一个参数矩阵),来使得真实值和预测值的误差(也称残差)平方和最小,其计算公式为
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
其中 yi是真实值,yi^是对应的预测值。
下图中,红色为数据点,蓝色为最小二乘法求得的最佳解,绿色即为误差
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
图中有四个数据点分别为:(1, 6), (2, 5), (3, 7), (4, 10)。显然,最佳解(3, 7)

2、最小二乘解

  • 上面介绍了最小二乘法的公式:误差平方和

  • 如下是2-范数:
    精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

  • 根据这两个式子,进行最小二乘解的分析:

  • 已知有一个这样的方程组:Ax=b 其中A∈Rm×n ; x∈Rn×k, b∈Rm×k

  • 因此根据最小二乘法公式,那么求解最小二乘的问题即可等价于:

  • 精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

  • 因此:精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

  • 对 x 求导:
    精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

  • 解得(最小二乘解)
    精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

3、仿射变换最小二乘解的例子

精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

写成矩阵形式:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
每对匹配点,提供两个约束。因此由N对点得到的等式组有2N个约束:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
也可以简单写成:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
总平方误差:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
对每个参数求偏导,并令其为0,即
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
因此可得最小二乘解:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比


拓展小知识:

  • 在线性回归中,通常我们使用均方误差来作为损失函数,同时均方误差可以看作是最小二乘法中的 E /m(m 为样本个数),所以最小二乘法求出来的最优解就是将均方误差作为损失函数求出来的最优解。
  • 因此损失函数即可使用最小二乘法来表示
  • 对于一维特征的样本,拟合函数为
    精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
  • 因此损失函数为:上标(i)表示第 i 个样本
    精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

四、RANSAC 与 Least Squares Fit(最小二乘法)区别

	RANSAC算法:适用于含有较大的噪声或无效点的情况
	
	最小二乘法:适用于误差比较小的情况

如下图所示,在误差比较大的情况下,肉眼也能看出拟合出的直线,但用最小二乘法拟合的直线却是错误的。而用RANSAC算法却能成功拟合。
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

五、RANSAC 算法的优缺点

优点:当数据中有大量的异常数据时,也能高精度的进行估计拟合。

缺点:对于异常数据超过50%的时候,拟合效果不佳。需要设置特定于问题的阈值。迭代次数若受到限制,那么达到迭代次数时拟合出来的模型可能并不是最佳模型。特定数据只能拟合出一个模型,一般多模型拟合采用霍夫变换。

六、Opencv实现RANSAC算法

//RANSAC算法
int main()
{



    Mat img_object = imread("./data/101.png", IMREAD_GRAYSCALE);
    Mat img_scene = imread("./data/100.png", IMREAD_GRAYSCALE);

    if (img_object.empty() || img_scene.empty())
    {
        cout << "Could not open or find the image!\n" << endl;
        return -1;
    }
    //-- Step 1: Detect the keypoints using SURF Detector, compute the descriptors
    int minHessian = 800; // default: 400
    Ptr<SURF> surf = SURF::create(800);
    std::vector<KeyPoint> keypoints_object, keypoints_scene;
    Mat descriptors_object, descriptors_scene;
    surf->detectAndCompute(img_object, noArray(), keypoints_object, descriptors_object);
    surf->detectAndCompute(img_scene, noArray(), keypoints_scene, descriptors_scene);

    //-- Step 2: Matching descriptor vectors with a FLANN based matcher
    // Since SURF is a floating-point descriptor NORM_L2 is used
    Ptr<DescriptorMatcher> matcher = DescriptorMatcher::create(DescriptorMatcher::FLANNBASED);
    std::vector< std::vector<DMatch> > knn_matches;
    matcher->knnMatch(descriptors_object, descriptors_scene, knn_matches, 2);

    //-- Filter matches using the Lowe's ratio test
    const float ratio_thresh = 0.75f;
    std::vector<DMatch> good_matches;
    for (size_t i = 0; i < knn_matches.size(); i++)
    {
        if (knn_matches[i][0].distance < ratio_thresh * knn_matches[i][1].distance)
        {
            good_matches.push_back(knn_matches[i][0]);
        }
    }

    //-- Draw matches
    Mat img_matches;
    drawMatches(img_object, keypoints_object, img_scene, keypoints_scene, good_matches, img_matches, Scalar::all(-1),
        Scalar::all(-1), std::vector<char>(), DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);

    //-- Localize the object
    std::vector<Point2f> obj;
    std::vector<Point2f> scene;

    for (size_t i = 0; i < good_matches.size(); i++)
    {
        //-- Get the keypoints from the good matches
        obj.push_back(keypoints_object[good_matches[i].queryIdx].pt);
        scene.push_back(keypoints_scene[good_matches[i].trainIdx].pt);
    }
    vector<uchar>inliers;
    Mat H = findHomography(obj, scene, inliers, RANSAC);


    //-- Draw matches with RANSAC
    Mat img_matches_ransac;
    std::vector<DMatch> good_matches_ransac;
    for (size_t i = 0; i < inliers.size(); i++)
    {
        if (inliers[i])
        {
            good_matches_ransac.push_back(good_matches[i]);
        }
    }
    drawMatches(img_object, keypoints_object, img_scene, keypoints_scene, good_matches_ransac, img_matches_ransac, Scalar::all(-1),
        Scalar::all(-1), std::vector<char>(), DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);
    namedWindow("img_matches", WINDOW_NORMAL);
    imshow("img_matches", img_matches);
    imwrite("img_matches.jpg", img_matches);

    namedWindow("img_matches_ransac", WINDOW_NORMAL);
    imshow("img_matches_ransac", img_matches_ransac);
    imwrite("img_matches_ransac.jpg", img_matches_ransac);
	waitKey();

	return 0;
}

效果图:
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比
精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比

参考博文

————————

所有无聊的事情都会衍生出很多细节让你觉得它复杂而有趣,投入其中而浑然不知其无聊的本质。
–王小波文章来源地址https://www.toymoban.com/news/detail-459500.html

到了这里,关于精匹配——Opencv实现RANSAC算法进行误匹配对剔除,并和最小二乘法对比的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 计算机视觉的几个经典算法 —— 最小二乘法 + RANSAC + 哈希算法(附DCT) + 图像聚类算法

    在了解最小二乘法之前,我们有必要先说说线性回归,所谓线性回归我们最常见的例子y=2x这个一元线性回归方程中,斜率2就是回归系数,它表示的是x变动时,y与之对应的关系,而线性回归就是表示一些离散的点在总体上是最逼近某一条直线的 这跟最小二乘法有啥关系呢?

    2024年02月08日
    浏览(42)
  • OpenCV Python – 使用SIFT算法实现两张图片的特征匹配

    1.要实现在大图中找到任意旋转、缩放等情况下的小图位置,可以使用特征匹配算法,如 SIFT (尺度不变特征变换) 或 SURF (加速稳健特征)。这些算法可以在不同尺度和旋转情况下寻找匹配的特征点 2.我们使用了 SIFT 算法检测和匹配特征点,然后使用 RANSAC 算法计算透视变换矩阵

    2024年02月06日
    浏览(47)
  • 探索经典算法 拓扑排序,字符串匹配算法,最小生成树

    拓扑排序、字符串匹配算法和最小生成树是计算机科学中常用的数据结构和算法,它们在解决各种实际问题中具有重要的应用价值。在本文中,我将详细介绍这三个主题,并提供相应的示例代码和应用场景,以帮助读者更好地理解和应用这些概念。 一、拓扑排序: 拓扑排序

    2024年02月05日
    浏览(50)
  • 用OpenCV进行模板匹配

    今天我们来研究一种传统图像处理领域中对象检测和跟踪不可或缺的方法——模板匹配,其主要目的是为了在图像上找到我们需要的图案,这听起来十分令人兴奋。 所以,事不宜迟,让我们直接开始吧! 模板匹配的算法的核心十分简单:它将模板与源图像中的每个部分进行

    2024年02月10日
    浏览(43)
  • 随机抽样一致(RANSAC)算法及matlab实现

    RANSAC为 RANdom SAmple Consensus (随机抽样一致)的缩写,它是根据一组包含异常数据的样本数据集,计算出数据的数学模型参数,得到有效样本数据的算法。它于1981年由 Fischler 和 Bolles 最先提出。 RANSAC算法的应用背景是在一堆观察点中估计出某个模型 y y y 。 以2D模型为例,RA

    2024年02月01日
    浏览(43)
  • python+OpenCV笔记(三十五):特征匹配——基于FLANN的匹配、基于FLANN进行单应性匹配

    目录 一、基于FLANN的匹配 FLANN匹配流程: 代码编写 二、基于FLANN进行单应性匹配 什么是单应性? FLANN进行单应性匹配流程 代码编写          FLANN库全称是Fast Library for Approximate Nearest Neighbors,它是目前最完整的(近似)最近邻开源库。不但实现了一系列查找算法,还包含

    2024年02月05日
    浏览(39)
  • opencv特征匹配算法原理

    算法步骤: FAST进行特征点提取是根据当前点领域内的点的差值作为特征点的筛选标准 ( 1 ) 选择像素 p ,该像素值为 I p ,确定筛选阈值 T ( 2 ) 计算以 p 为圆心 3 为半径的 16 个像素点的灰度值 I x 和圆心 p 的灰度值 I p 的差值,如果存在连续 n 个点(算法第一个版本为 12 ) 满

    2024年02月03日
    浏览(43)
  • 【高光谱图像的去噪算法】通过全变异最小化对受激拉曼光谱图像进行去噪研究(Matlab代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 🎉3 参考文献 🌈4 Matlab代码、数据、文章

    2024年02月14日
    浏览(34)
  • 【halcon】特征点匹配proj_match_points_ransac算子

            halcon的许多算子内涵两种以上的理论或算法,proj_match_points_ransac就是其中之一,它至少包含了射影几何和ransac算法两个内容。本篇将讲述三个方面: 1、射影几何的透视投影原理; 2、ransac的回归原理; 3、proj_match_points_ransac如何使用的案例;         该算子有

    2024年02月11日
    浏览(65)
  • RANSAC算法在Python中的实现与应用探索:线性拟合与平面拟合示例

    第一部分:RANSAC算法与其应用 在我们的日常生活和多个领域中,如机器学习,计算机视觉,模式识别等,处理数据是一个非常重要的任务。尤其是当我们需要从嘈杂的数据中获取信息或拟合模型时。有时候,数据可能包含异常值或噪声,这可能会对我们的结果产生重大影响。

    2024年02月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包