Opencv之RANSAC算法用于直线拟合及特征点集匹配详解

Opencv之RANSAC算法用于直线拟合及特征点集匹配详解

    1. 讲述Ransac拟合与最小二乘在曲线拟合上的优缺点
    1. 讲述在进行特征点匹配时,最近邻匹配与Ransac匹配的不同之处
    1. 另外,Ransac也被用于椭圆拟合、变换矩阵求解等

1. 直线拟合

1.1 原理

  • RANSAC(RANdom SAmple Consensus,随机采样一致)算法是从一组含有“外点”(outliers)的数据中正确估计数学模型参数的迭代算法。“外点”一般指的的数据中的噪声,比如说匹配中的误匹配和估计曲线中的离群点。故RANSAC也是一种“外点”检测算法。同时RANSAC是一个非确定性算法,在某种意义上说,它会产生一个在一定概率下合理的结果,其允许使用更多次的迭代来使其概率增加。

  • RANSAC算最早是由Fischler和Bolles在SRI上提出用来解决LDP(Location Determination Problem,位置确定问题)问题的。

  • 对于RANSAC算法来说一个基本的假设就是数据是由“内点”和“外点”组成的。“内点”就是组成模型参数的数据,“外点”就是不适合模型的数据。同时RANSAC假设:在给定一组含有少部分“内点”的数据,存在一个程序可以估计出符合“内点”的模型

  • 算法主要思想:

  • 给定一个数据集S,从中选择建立模型所需的最小样本数(空间直线最少可以由两个点确定,所以最小样本数是2,空间平面可以根据不共线三点确定,所以最小样本数为3,拟一个圆时,最小样本数是3),记选择数据集为S1
    使用选择的数据集S1计算得到一个数学模型M1
  • 用计算的模型M1去测试数据集中剩余的点,如果测试的数据点在误差允许的范围内,则将该数据点判为内点(inlier),否则判为外点(outlier),记所有内点组成的数据集为S1*,S1* 称作 S1的一致性集合
  • 比较当前模型和之前推出的最好的模型的“内点”的数量,记录最大“内点”数量时模型参数和“内点”数量
  • 重复1-4步,直到迭代结束或者当前模型已经足够好了(“内点数目大于设定的阈值”);每次产生的模型要么因为内点太少而被舍弃,要么因为比现有的模型更好而被选用
  • 其过程如下图所示:
    取点集中的两点确定一条直线,然后通过设定规则选取筛选内殿,拿最多的内点拟合出来的模型作为最终的可用模型
    在这里插入图片描述

1.2 迭代次数推导

  • 根据上面RANSAC基本原理的介绍,在这算法流程中存在两个重要的参数需要设置,迭代次数(采样次数)和距离阈值。
    迭代的次数我们应该选择多大呢?这个值是否可以事先知道应该设为多少呢?还是只能凭经验决定呢? 这个值其实是可以估算出来的。下面来推算一下。
    在这里插入图片描述

内点的概率t通常是一个先验值。然后P 是我们希望RANSAC得到正确模型的概率。如果事先不知道t 的值,可以使用自适应迭代次数的方法。也就是一开始设定一个无穷大的迭代次数,然后每次更新模型参数估计的时候,用当前的内点比值当成t 来估算出迭代次数。

1.3 与最小二乘区别

  • 最小二乘法尽量去适应包括外点在内的所有点。因此,最小二乘法只适合与误差较小的情况。假使需要从一个噪音较大的数据集中提取模型(比方说只有20%的数据时符合模型的)时,最小二乘法就显得力不从心了。
    在这里插入图片描述
  • RANSAC相当于一个概率模型,它通过计算内点出现的概率,找出噪点之外的点集拟合出的 最优模型,通常更能表示系统属性。其相当于迭代使用最小二乘法+抽样测试。

1.4 代码实现

  • C++实现:
//====================================================================//
//Program:RANSAC直线拟合,并与最小二乘法结果进行对比
//====================================================================//
#include <iostream>
#include <opencv2/opencv.hpp>//RANSAC 拟合2D 直线
//输入参数:points--输入点集
//        iterations--迭代次数
//        sigma--数据和模型之间可接受的差值,车道线像素宽带一般为10左右
//              (Parameter use to compute the fitting score)
//        k_min/k_max--拟合的直线斜率的取值范围.
//                     考虑到左右车道线在图像中的斜率位于一定范围内,
//                      添加此参数,同时可以避免检测垂线和水平线
//输出参数:line--拟合的直线参数,It is a vector of 4 floats
//              (vx, vy, x0, y0) where (vx, vy) is a normalized
//              vector collinear to the line and (x0, y0) is some
//              point on the line.
//返回值:无
void fitLineRansac(const std::vector<cv::Point2f>& points,cv::Vec4f &line,int iterations = 1000,double sigma = 1.,double k_min = -7.,double k_max = 7.)
{unsigned int n = points.size();if(n<2){return;}cv::RNG rng;double bestScore = -1.;for(int k=0; k<iterations; k++){int i1=0, i2=0;while(i1==i2){i1 = rng(n);i2 = rng(n);}const cv::Point2f& p1 = points[i1];const cv::Point2f& p2 = points[i2];cv::Point2f dp = p2-p1;//直线的方向向量dp *= 1./norm(dp);double score = 0;if(dp.y/dp.x<=k_max && dp.y/dp.x>=k_min ){for(int i=0; i<n; i++){cv::Point2f v = points[i]-p1;double d = v.y*dp.x - v.x*dp.y;//向量a与b叉乘/向量b的摸.||b||=1./norm(dp)//score += exp(-0.5*d*d/(sigma*sigma));//误差定义方式的一种if( fabs(d)<sigma )score += 1;}}if(score > bestScore){line = cv::Vec4f(dp.x, dp.y, p1.x, p1.y);bestScore = score;}}
}int main()
{cv::Mat image(720,1280,CV_8UC3,cv::Scalar(125,125,125));//以车道线参数为(0.7657,-0.6432,534,548)生成一系列点double k = -0.6432/0.7657;double b = 548 - k*534;std::vector<cv::Point2f> points;for (int i = 360; i < 720; i+=10){cv::Point2f point(int((i-b)/k),i);points.emplace_back(point);}//加入直线的随机噪声cv::RNG rng((unsigned)time(NULL));for (int i = 360; i < 720; i+=10){int x = int((i-b)/k);x = rng.uniform(x-10,x+10);int y = i;y = rng.uniform(y-30,y+30);cv::Point2f point(x,y);points.emplace_back(point);}//加入噪声for (int i = 0; i < 720; i+=20){int x = rng.uniform(1,640);int y = rng.uniform(1,360);cv::Point2f point(x,y);points.emplace_back(point);}int n = points.size();for (int j = 0; j < n; ++j){cv::circle(image,points[j],5,cv::Scalar(0,0,0),-1);}//RANSAC 拟合if(1){cv::Vec4f lineParam;fitLineRansac(points,lineParam,1000,10);double k = lineParam[1] / lineParam[0];double b = lineParam[3] - k*lineParam[2];cv::Point p1,p2;p1.y = 720;p1.x = ( p1.y - b) / k;p2.y = 360;p2.x = (p2.y-b) / k;cv::line(image,p1,p2,cv::Scalar(0,255,0),2);}//最小二乘法拟合if(1){cv::Vec4f lineParam;cv::fitLine(points,lineParam,cv::DIST_L2,0,0.01,0.01);double k = lineParam[1] / lineParam[0];double b = lineParam[3] - k*lineParam[2];cv::Point p1,p2;p1.y = 720;p1.x = ( p1.y - b) / k;p2.y = 360;p2.x = (p2.y-b) / k;cv::line(image,p1,p2,cv::Scalar(0,0,255),2);}cv::imshow("image",image);cv::waitKey(0);return 0;
}

在这里插入图片描述

  • Python 实现:
#!/usr/bin/env python3
#coding=utf-8#============================#
#Program:RANSAC_Line.py
===========#import numpy as np
import random
import mathimport cv2def fitLineRansac(points,iterations=1000,sigma=1.0,k_min=-7,k_max=7):"""RANSAC 拟合2D 直线:param points:输入点集,numpy [points_num,1,2],np.float32:param iterations:迭代次数:param sigma:数据和模型之间可接受的差值,车道线像素宽带一般为10左右(Parameter use to compute the fitting score):param k_min::param k_max:k_min/k_max--拟合的直线斜率的取值范围.考虑到左右车道线在图像中的斜率位于一定范围内,添加此参数,同时可以避免检测垂线和水平线:return:拟合的直线参数,It is a vector of 4 floats(vx, vy, x0, y0) where (vx, vy) is a normalizedvector collinear to the line and (x0, y0) is somepoint on the line."""line = [0,0,0,0]points_num = points.shape[0]if points_num<2:return linebestScore = -1for k in range(iterations):i1,i2 = random.sample(range(points_num), 2)p1 = points[i1][0]p2 = points[i2][0]dp = p1 - p2 #直线的方向向量dp *= 1./np.linalg.norm(dp) # 除以模长,进行归一化score = 0a = dp[1]/dp[0]if a <= k_max and a>=k_min:for i in range(points_num):v = points[i][0] - p1dis = v[1]*dp[0] - v[0]*dp[1]#向量a与b叉乘/向量b的摸.||b||=1./norm(dp)# score += math.exp(-0.5*dis*dis/(sigma*sigma))误差定义方式的一种if math.fabs(dis)<sigma:score += 1if score > bestScore:line = [dp[0],dp[1],p1[0],p1[1]]bestScore = scorereturn lineif __name__ == '__main__':image = np.ones([720,1280,3],dtype=np.ubyte)*125# 以车道线参数为(0.7657, -0.6432, 534, 548)生成一系列点k = -0.6432 / 0.7657b = 548 - k * 534points = []for i in range(360,720,10):point = (int((i-b)/k),i)points.append(point)# 加入直线的随机噪声for i in range(360,720,10):x = int((i-b)/k)x = random.sample(range(x-10,x+10),1)y = iy = random.sample(range(y - 30, y + 30),1)point = (x[0],y[0])points.append(point)# 加入噪声for i in range(0,720,20):x = random.sample(range(1, 640), 1)y = random.sample(range(1, 360), 1)point = (x[0], y[0])points.append(point)for point in points:cv2.circle(image,point,5,(0,0,0),-1)points = np.array(points).astype(np.float32)points = points[:,np.newaxis,:]# RANSAC 拟合if 1:[vx, vy, x, y] = fitLineRansac(points,1000,10)k = float(vy) / float(vx)  # 直线斜率b = -k * x + yp1_y = 720p1_x = (p1_y-b) / kp2_y = 360p2_x = (p2_y-b) / kp1 = (int(p1_x),int(p1_y))p2 = (int(p2_x), int(p2_y))cv2.line(image,p1,p2,(0,255,0),2)# 最小二乘法拟合if 1:[vx, vy, x, y] = cv2.fitLine(points, cv2.DIST_L2, 0, 0.1, 0.01)k = float(vy) / float(vx)  # 直线斜率b = -k * x + yp1_y = 720p1_x = (p1_y - b) / kp2_y = 360p2_x = (p2_y - b) / kp1 = (int(p1_x), int(p1_y))p2 = (int(p2_x), int(p2_y))cv2.line(image, p1, p2, (0, 0, 255), 2)cv2.imshow('image',image)cv2.waitKey(0)

2. 特征匹配

  • 基于特征的图像匹配中会存在误匹配对,因此为提高匹配率,在粗匹配的基础上实现精匹配,可采用下面两种方法:
    在这里插入图片描述
  • 用RANSAC算法来寻找最佳单应性矩阵H,在此先提取SIFT特征点进行最近邻粗匹配,然后采取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 descriptorsint minHessian = 800; // default: 400Ptr<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 usedPtr<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 testconst 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 matchesMat 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 objectstd::vector<Point2f> obj;std::vector<Point2f> scene;for (size_t i = 0; i < good_matches.size(); i++){//-- Get the keypoints from the good matchesobj.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 RANSACMat 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;
}
  • 只进行knn匹配与加上Ransac匹配的效果对比图如下:
    在这里插入图片描述

参考:

1.https://blog.csdn.net/leonardohaig/article/details/104570965?spm=1001.2014.3001.5506
2.https://blog.csdn.net/H19981118/article/details/122014318?spm=1001.2014.3001.5506

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/167305.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Mysql中的RR 隔离级别,到底有没有解决幻读问题

Mysql 中的 RR 事务隔离级别&#xff0c;在特定的情况下会出现幻读的问题。所谓的幻读&#xff0c;表示在同一个事务中的两次相同条件的查询得到的数据条数不一样。 在 RR 级别下&#xff0c;什么情况下会出现幻读 这样一种情况&#xff0c;在事务 1 里面通过 update 语句触发当…

【CGSSA-BP预测】基于混合混沌-高斯变异-麻雀算法优化BP神经网络回归预测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

手机拍照转机器人末端坐标(九点标定法)

1.打印标定纸&#xff0c;随机九个点 2.让UR机器人末端分别走到P1-P9九个点 在图示位置读取九个点的X&#xff0c;Y坐标 3.手机拍照&#xff08;固定点&#xff09; 测试可以随机拍一张&#xff0c;实用的话需要固定手机的拍照位置&#xff0c;得到的图片如下&#xff1a; 4.…

使用AI编写测试用例——详细教程

随着今年chatGPT的大热&#xff0c;每个行业都试图从这项新技术当中获得一些收益我之前也写过一篇测试领域在AI技术中的探索&#xff1a;软件测试中的AI——运用AI编写测试用例现阶段AI还不能完全替代人工测试用例编写&#xff0c;但是如果把AI当做一个提高效率的工具&#xff…

基于单片机设计的家用自来水水质监测装置

一、前言 本文介绍基于单片机设计的家用自来水水质监测装置。利用STM32F103ZET6作为主控芯片&#xff0c;结合水质传感器和ADC模块&#xff0c;实现对自来水水质的检测和监测功能。通过0.96寸OLED显示屏&#xff0c;将采集到的水质数据以直观的方式展示给用户。 随着人们对健…

图论01-【无权无向】-图的基本表示-邻接矩阵/邻接表

文章目录 1. 代码仓库2. 图的基本表示的比较3. 邻接矩阵&#xff1a;Array和TreeSet3.1 图示3.2 Array主要代码解析3.3 测试输出3.4 使用TreeSet的代码 4. 邻接表&#xff1a;LinkedList4.1 图示4.2 LinkedList主要代码解析4.3 测试输出 5. 完整代码5.1 邻接表 - Array5.2 邻接…

深入理解C++红黑树的底层实现及应用

文章目录 1、红黑树简介1.1 、概述&#xff1a;介绍红黑树的定义、特点和用途。 2、红黑树节点的定义3、红黑树结构3.1、红黑树的插入操作 4、红黑树的验证4.1、红黑树的删除4.2、红黑树与AVL树的比较4.3、红黑树的应用 5、总结 1、红黑树简介 1.1 、概述&#xff1a;介绍红黑…

Linux | 深入浅出冯诺依曼

前言 但凡是科班出生的小伙伴多多稍稍应该都听过冯诺依曼体系吧&#xff0c;这似乎已成为入门计算机的必备知识了&#xff0c;本章就带着大家一起去理解冯诺依曼体系&#xff1b; 一、体系构成 冯诺依曼体系主张计算机由五大部件组成&#xff0c;如下所示&#xff1b; 输入设备…

Java设计模式 | 基于订单批量支付场景,对策略模式和简单工厂模式进行简单实现

基于订单批量支付场景&#xff0c;对策略模式和简单工厂模式进行简单实现 文章目录 策略模式介绍实现抽象策略具体策略1.AliPayStrategy2.WeChatPayStrategy 环境 使用简单工厂来获取具体策略对象支付方式枚举策略工厂接口策略工厂实现 测试使用订单实体类对订单进行批量支付结…

Stable Diffusion WebUI报错RuntimeError: Torch is not able to use GPU解决办法

新手在安装玩Stable Diffusion WebUI之后会遇到各种问题&#xff0c; 接下来会慢慢和你讲解如何解决这些问题。 在我们打开Stable Diffusion WebUI时会报错如下&#xff1a; RuntimeError: Torch is not able to use GPU&#xff1b;add --skip-torch-cuda-test to COMMANDL…

操作系统——吸烟者问题(王道视频p34、课本ch6)

1.问题分析&#xff1a;这个问题可以看作是 可以生产多种产品的 单生产者-多消费者问题 2.代码——这里就是由于同步信号量的初值都是1&#xff0c;所以没有使用mutex互斥信号&#xff0c; 总共4个同步信号量&#xff0c;其中一个是 finish信号量

在Lichee RV Dock上的不成功的烧录尝试

最近在学基于risc-v的简单操作系统&#xff0c;刚好手里有块Lichee RV Dock 的板子&#xff0c;所以在学了基础的"hello, world"程序后&#xff0c;想着能不能把这个程序烧录到板子上&#xff0c;简单的做个实验。 要完成这个任务&#xff0c;需要将程序烧录到sd卡上…

专访 Web3Go 新产品 Reiki:培育 AI 原生数字资产与创意新土壤

从 DeFi 到 NFTFi、SocialFi&#xff0c;web3 从业者在尝试 crypto 与区块链技术能为我们的生活、创作、娱乐和文化带来何种新体验&#xff0c;而生成式人工智能的突破性发展则为我们与链上世界的交互、社区内容创作等带来了新的体验&#xff0c;改变互动、交易和价值创造方式。…

容器技术基础

1. Linux Namespace和Cgroups 对于 Docker 等大多数 Linux 容器来说&#xff0c;Cgroups 技术是用来制造约束的主要手段&#xff0c;而 Namespace 技术则是用来修改进程视图的主要方法。 1.1 PID Namespace //Linux 系统正常创建线程 int pid clone(main_function, stack_s…

Docker数据管理、端口映射、容器互联

目录 一、Docker 的数据管理&#xff1a; 1&#xff0e;数据卷&#xff1a; 1.1 宿主机目录/var/www/html 挂载到容器中的/data1&#xff1a; 1.2 测试&#xff1a; 2&#xff0e;数据卷容器&#xff1a; 2.1 创建一个容器作为数据卷容器&#xff1a; 2.2 挂载a1容器中的数据卷…

《数据结构与算法之美》读书笔记1

Java的学习 方法参数多态&#xff08;向上和向下转型&#xff09; 向上转型&#xff1a; class Text{public static void main(String[] args) {Animals people1 new NiuMa();people1.eat1();//调用继承后公共部分的方法&#xff0c;没重写调用没重写的&#xff0c;重写了调…

Mysql数据库 2.SQL语言 数据类型与字段约束

Mysql数据类型 数据类型&#xff1a;指的是数据表中的列文件支持存放的数据类型 1.数值类型 Mysql当中有多种数据类型可以存放数值&#xff0c;不同的类型存放的数值的范围或者形式是不同的 注&#xff1a;前三种数字类型我们在实际研发中用的很少&#xff0c;一般整数类型…

【C++】:类和对象(中)之拷贝构造函数+赋值运算符重载

拷贝构造函数 概念 在现实生活中&#xff0c;可能存在一个与你一样的自己&#xff0c;我们称其为双胞胎 那在创建对象时&#xff0c;可否创建一个与已存在对象一某一样的新对象呢&#xff1f; 拷贝构造函数&#xff1a;只有单个形参&#xff0c;该形参是对本类类型对象的引用…

OpenP2P实现内网穿透远程办公

OpenP2P是一个开源、免费、轻量级的P2P共享网络。你的设备将组成一个私有P2P网络&#xff0c;里面的设备可以直接访问其它成员&#xff0c;或者通过其它成员转发数据间接访问。如果私有网络无法完成通信&#xff0c;将会到公有P2P网络寻找共享节点协助通信。 相比BT网络用来共享…

【C++】哈希的应用 -- 布隆过滤器

文章目录 一、布隆过滤器提出二、布隆过滤器概念三、布隆过滤器哈希函数个数的选择四、布隆过滤器的实现1.布隆过滤器的插入2.布隆过滤器的查找3.布隆过滤器删除4.完整代码实现 五、布隆过滤器总结1.布隆过滤器优点2.布隆过滤器缺陷3.布隆过滤器的应用4.布隆过滤器相关面试题 一…