【特征匹配】RANSAC算法原理与源码解析

article/2025/9/12 20:39:17

 转载请注明出处：http://blog.csdn.net/luoshixian099/article/details/50217655

勿在浮沙筑高台

  随机抽样一致性（RANSAC）算法，可以在一组包含“外点”的数据集中，采用不断迭代的方法，寻找最优参数模型，不符合最优模型的点，被定义为“外点”。在图像配准以及拼接上得到广泛的应用，本文将对RANSAC算法在OpenCV中角点误匹配对的检测中进行解析。



1.RANSAC原理  

  OpenCV中滤除误匹配对采用RANSAC算法寻找一个最佳单应性矩阵H，矩阵大小为3×3。RANSAC目的是找到最优的参数矩阵使得满足该矩阵的数据点个数最多，通常令h33=1来归一化矩阵。由于单应性矩阵有8个未知参数，至少需要8个线性方程求解，对应到点位置信息上，一组点对可以列出两个方程，则至少包含4组匹配点对。


                                                                      其中(x,y)表示目标图像角点位置,(x',y')为场景图像角点位置，s为尺度参数。

  RANSAC算法从匹配数据集中随机抽出4个样本并保证这4个样本之间不共线，计算出单应性矩阵，然后利用这个模型测试所有数据，并计算满足这个模型数据点的个数与投影误差(即代价函数)，若此模型为最优模型，则对应的代价函数最小。


-----------------------------------------------------------------------------------------------------------------

RANSAC算法步骤： 

          1. 随机从数据集中随机抽出4个样本数据 (此4个样本之间不能共线)，计算出变换矩阵H，记为模型M；

          2. 计算数据集中所有数据与模型M的投影误差，若误差小于阈值，加入内点集 I ；

          3. 如果当前内点集 I 元素个数大于最优内点集 I_best , 则更新 I_best = I，同时更新迭代次数k ;

          4. 如果迭代次数大于k,则退出 ; 否则迭代次数加1，并重复上述步骤；

  注：迭代次数k在不大于最大迭代次数的情况下，是在不断更新而不是固定的；

                                       其中，p为置信度，一般取0.995；w为"内点"的比例 ; m为计算模型所需要的最少样本数=4；

-----------------------------------------------------------------------------------------------------------------


2.例程

OpenCV中此功能通过调用findHomography函数调用，下面是个例程：

#include <iostream>
#include "opencv2/opencv.hpp"
#include "opencv2/core/core.hpp"
#include "opencv2/features2d/features2d.hpp"
#include "opencv2/highgui/highgui.hpp"
using namespace cv;
using namespace std;
int main(int argc, char** argv)
{Mat obj=imread("F:\\Picture\\obj.jpg");   //载入目标图像Mat scene=imread("F:\\Picture\\scene.jpg"); //载入场景图像if (obj.empty() || scene.empty() ){cout<<"Can't open the picture!\n";return 0;}vector<KeyPoint> obj_keypoints,scene_keypoints;Mat obj_descriptors,scene_descriptors;ORB detector;     //采用ORB算法提取特征点detector.detect(obj,obj_keypoints);detector.detect(scene,scene_keypoints);detector.compute(obj,obj_keypoints,obj_descriptors);detector.compute(scene,scene_keypoints,scene_descriptors);BFMatcher matcher(NORM_HAMMING,true); //汉明距离做为相似度度量vector<DMatch> matches;matcher.match(obj_descriptors, scene_descriptors, matches);Mat match_img;drawMatches(obj,obj_keypoints,scene,scene_keypoints,matches,match_img);imshow("滤除误匹配前",match_img);//保存匹配对序号vector<int> queryIdxs( matches.size() ), trainIdxs( matches.size() );for( size_t i = 0; i < matches.size(); i++ ){queryIdxs[i] = matches[i].queryIdx;trainIdxs[i] = matches[i].trainIdx;}	Mat H12;   //变换矩阵vector<Point2f> points1; KeyPoint::convert(obj_keypoints, points1, queryIdxs);vector<Point2f> points2; KeyPoint::convert(scene_keypoints, points2, trainIdxs);int ransacReprojThreshold = 5;  //拒绝阈值H12 = findHomography( Mat(points1), Mat(points2), CV_RANSAC, ransacReprojThreshold );vector<char> matchesMask( matches.size(), 0 );  Mat points1t;perspectiveTransform(Mat(points1), points1t, H12);for( size_t i1 = 0; i1 < points1.size(); i1++ )  //保存‘内点’{if( norm(points2[i1] - points1t.at<Point2f>((int)i1,0)) <= ransacReprojThreshold ) //给内点做标记{matchesMask[i1] = 1;}	}Mat match_img2;   //滤除‘外点’后drawMatches(obj,obj_keypoints,scene,scene_keypoints,matches,match_img2,Scalar(0,0,255),Scalar::all(-1),matchesMask);//画出目标位置std::vector<Point2f> obj_corners(4);obj_corners[0] = cvPoint(0,0); obj_corners[1] = cvPoint( obj.cols, 0 );obj_corners[2] = cvPoint( obj.cols, obj.rows ); obj_corners[3] = cvPoint( 0, obj.rows );std::vector<Point2f> scene_corners(4);perspectiveTransform( obj_corners, scene_corners, H12);line( match_img2, scene_corners[0] + Point2f(static_cast<float>(obj.cols), 0), scene_corners[1] + Point2f(static_cast<float>(obj.cols), 0),Scalar(0,0,255),2);line( match_img2, scene_corners[1] + Point2f(static_cast<float>(obj.cols), 0), scene_corners[2] + Point2f(static_cast<float>(obj.cols), 0),Scalar(0,0,255),2);line( match_img2, scene_corners[2] + Point2f(static_cast<float>(obj.cols), 0), scene_corners[3] + Point2f(static_cast<float>(obj.cols), 0),Scalar(0,0,255),2);line( match_img2, scene_corners[3] + Point2f(static_cast<float>(obj.cols), 0),scene_corners[0] + Point2f(static_cast<float>(obj.cols), 0),Scalar(0,0,255),2);imshow("滤除误匹配后",match_img2);waitKey(0);return 0;
}

3. RANSAC源码解析

(1)findHomography内部调用cvFindHomography函数

srcPoints:目标图像点集

dstPoints:场景图像点集

method: 最小中值法、RANSAC方法、最小二乘法

ransacReprojTheshold:投影误差阈值

mask:掩码

cvFindHomography( const CvMat* objectPoints, const CvMat* imagePoints,CvMat* __H, int method, double ransacReprojThreshold,CvMat* mask )
{const double confidence = 0.995;  //置信度const int maxIters = 2000;    //迭代最大次数const double defaultRANSACReprojThreshold = 3; //默认拒绝阈值bool result = false;Ptr<CvMat> m, M, tempMask;double H[9];CvMat matH = cvMat( 3, 3, CV_64FC1, H );  //变换矩阵int count;CV_Assert( CV_IS_MAT(imagePoints) && CV_IS_MAT(objectPoints) );count = MAX(imagePoints->cols, imagePoints->rows);CV_Assert( count >= 4 );           //至少有4个样本if( ransacReprojThreshold <= 0 )ransacReprojThreshold = defaultRANSACReprojThreshold;m = cvCreateMat( 1, count, CV_64FC2 );  //转换为齐次坐标cvConvertPointsHomogeneous( imagePoints, m );M = cvCreateMat( 1, count, CV_64FC2 );//转换为齐次坐标cvConvertPointsHomogeneous( objectPoints, M );if( mask ){CV_Assert( CV_IS_MASK_ARR(mask) && CV_IS_MAT_CONT(mask->type) &&(mask->rows == 1 || mask->cols == 1) &&mask->rows*mask->cols == count );}if( mask || count > 4 )tempMask = cvCreateMat( 1, count, CV_8U );if( !tempMask.empty() )cvSet( tempMask, cvScalarAll(1.) );CvHomographyEstimator estimator(4);if( count == 4 )method = 0;if( method == CV_LMEDS )  //最小中值法result = estimator.runLMeDS( M, m, &matH, tempMask, confidence, maxIters );else if( method == CV_RANSAC )    //采用RANSAC算法result = estimator.runRANSAC( M, m, &matH, tempMask, ransacReprojThreshold, confidence, maxIters);//(2)解析elseresult = estimator.runKernel( M, m, &matH ) > 0; //最小二乘法if( result && count > 4 ){icvCompressPoints( (CvPoint2D64f*)M->data.ptr, tempMask->data.ptr, 1, count );  //保存内点集count = icvCompressPoints( (CvPoint2D64f*)m->data.ptr, tempMask->data.ptr, 1, count );M->cols = m->cols = count;if( method == CV_RANSAC )  //estimator.runKernel( M, m, &matH );  //内点集上采用最小二乘法重新估算变换矩阵estimator.refine( M, m, &matH, 10 );// }if( result )cvConvert( &matH, __H );  //保存变换矩阵if( mask && tempMask ){if( CV_ARE_SIZES_EQ(mask, tempMask) )cvCopy( tempMask, mask );elsecvTranspose( tempMask, mask );}return (int)result;
}

(2) runRANSAC
maxIters:最大迭代次数

m1,m2 :数据样本

model:变换矩阵

reprojThreshold:投影误差阈值

confidence:置信度  0.995

bool CvModelEstimator2::runRANSAC( const CvMat* m1, const CvMat* m2, CvMat* model,CvMat* mask0, double reprojThreshold,double confidence, int maxIters )
{bool result = false;cv::Ptr<CvMat> mask = cvCloneMat(mask0);cv::Ptr<CvMat> models, err, tmask;cv::Ptr<CvMat> ms1, ms2;int iter, niters = maxIters;int count = m1->rows*m1->cols, maxGoodCount = 0;CV_Assert( CV_ARE_SIZES_EQ(m1, m2) && CV_ARE_SIZES_EQ(m1, mask) );if( count < modelPoints )return false;models = cvCreateMat( modelSize.height*maxBasicSolutions, modelSize.width, CV_64FC1 );err = cvCreateMat( 1, count, CV_32FC1 );//保存每组点对应的投影误差tmask = cvCreateMat( 1, count, CV_8UC1 );if( count > modelPoints )  //多于4个点{ms1 = cvCreateMat( 1, modelPoints, m1->type );ms2 = cvCreateMat( 1, modelPoints, m2->type );}else  //等于4个点{niters = 1; //迭代一次ms1 = cvCloneMat(m1);  //保存每次随机找到的样本点ms2 = cvCloneMat(m2);}for( iter = 0; iter < niters; iter++ )  //不断迭代{int i, goodCount, nmodels;if( count > modelPoints ){//在(3)解析getSubsetbool found = getSubset( m1, m2, ms1, ms2, 300 ); //随机选择4组点，且三点之间不共线，(3)解析if( !found ){if( iter == 0 )return false;break;}}nmodels = runKernel( ms1, ms2, models );  //估算近似变换矩阵，返回1if( nmodels <= 0 )continue;for( i = 0; i < nmodels; i++ )//执行一次 {CvMat model_i;cvGetRows( models, &model_i, i*modelSize.height, (i+1)*modelSize.height );//获取3×3矩阵元素goodCount = findInliers( m1, m2, &model_i, err, tmask, reprojThreshold );  //找出内点，(4)解析if( goodCount > MAX(maxGoodCount, modelPoints-1) )  //当前内点集元素个数大于最优内点集元素个数{std::swap(tmask, mask);cvCopy( &model_i, model );  //更新最优模型maxGoodCount = goodCount;//confidence 为置信度默认0.995,modelPoints为最少所需样本数=4,niters迭代次数niters = cvRANSACUpdateNumIters( confidence,  //更新迭代次数，(5)解析(double)(count - goodCount)/count, modelPoints, niters );}}}if( maxGoodCount > 0 ){if( mask != mask0 )cvCopy( mask, mask0 );result = true;}return result;
}

(3)getSubset

ms1,ms2:保存随机找到的4个样本

maxAttempts:最大迭代次数，300

bool CvModelEstimator2::getSubset( const CvMat* m1, const CvMat* m2,CvMat* ms1, CvMat* ms2, int maxAttempts )
{cv::AutoBuffer<int> _idx(modelPoints); //modelPoints 所需要最少的样本点个数int* idx = _idx;int i = 0, j, k, idx_i, iters = 0;int type = CV_MAT_TYPE(m1->type), elemSize = CV_ELEM_SIZE(type);const int *m1ptr = m1->data.i, *m2ptr = m2->data.i;int *ms1ptr = ms1->data.i, *ms2ptr = ms2->data.i;int count = m1->cols*m1->rows;assert( CV_IS_MAT_CONT(m1->type & m2->type) && (elemSize % sizeof(int) == 0) );elemSize /= sizeof(int); //每个数据占用字节数for(; iters < maxAttempts; iters++){for( i = 0; i < modelPoints && iters < maxAttempts; ){idx[i] = idx_i = cvRandInt(&rng) % count;  // 随机选取1组点for( j = 0; j < i; j++ )  // 检测是否重复选择if( idx_i == idx[j] )break;if( j < i )continue;  //重新选择for( k = 0; k < elemSize; k++ )  //拷贝点数据{ms1ptr[i*elemSize + k] = m1ptr[idx_i*elemSize + k];ms2ptr[i*elemSize + k] = m2ptr[idx_i*elemSize + k];}if( checkPartialSubsets && (!checkSubset( ms1, i+1 ) || !checkSubset( ms2, i+1 )))//检测点之间是否共线{iters++;  //若共线，重新选择一组continue;}i++;}if( !checkPartialSubsets && i == modelPoints &&(!checkSubset( ms1, i ) || !checkSubset( ms2, i )))continue;break;}return i == modelPoints && iters < maxAttempts;  //返回找到的样本点个数
}

(4) findInliers & computerReprojError

int CvModelEstimator2::findInliers( const CvMat* m1, const CvMat* m2,const CvMat* model, CvMat* _err,CvMat* _mask, double threshold )
{int i, count = _err->rows*_err->cols, goodCount = 0;const float* err = _err->data.fl;uchar* mask = _mask->data.ptr;computeReprojError( m1, m2, model, _err );  //计算每组点的投影误差threshold *= threshold;for( i = 0; i < count; i++ )goodCount += mask[i] = err[i] <= threshold;//误差在限定范围内，加入‘内点集’return goodCount;
}
//--------------------------------------
void CvHomographyEstimator::computeReprojError( const CvMat* m1, const CvMat* m2,const CvMat* model, CvMat* _err )
{int i, count = m1->rows*m1->cols;const CvPoint2D64f* M = (const CvPoint2D64f*)m1->data.ptr;const CvPoint2D64f* m = (const CvPoint2D64f*)m2->data.ptr;const double* H = model->data.db;float* err = _err->data.fl;for( i = 0; i < count; i++ )        //保存每组点的投影误差，对应上述变换公式{double ww = 1./(H[6]*M[i].x + H[7]*M[i].y + 1.);    double dx = (H[0]*M[i].x + H[1]*M[i].y + H[2])*ww - m[i].x;double dy = (H[3]*M[i].x + H[4]*M[i].y + H[5])*ww - m[i].y;err[i] = (float)(dx*dx + dy*dy);}
}
(5)cvRANSACUpdateNumIters

对应上述k的计算公式

p：置信度

ep:外点比例

cvRANSACUpdateNumIters( double p, double ep,int model_points, int max_iters )
{if( model_points <= 0 )CV_Error( CV_StsOutOfRange, "the number of model points should be positive" );p = MAX(p, 0.);p = MIN(p, 1.);ep = MAX(ep, 0.);ep = MIN(ep, 1.);// avoid inf's & nan'sdouble num = MAX(1. - p, DBL_MIN);  //num=1-p,做分子double denom = 1. - pow(1. - ep,model_points);//做分母if( denom < DBL_MIN )return 0;num = log(num);denom = log(denom);return denom >= 0 || -num >= max_iters*(-denom) ?max_iters : cvRound(num/denom);
}


http://chatgpt.dhexx.cn/article/k757sklT.shtml

相关文章

RANSAC算法详解+Python实现

RANSAC算法详解+Python实现

1.算法描述 RANSAC的基本假设是&#xff1a; &#xff08;1&#xff09;数据由“局内点”组成&#xff0c;例如&#xff1a;数据的分布可以用一些模型参数来解释&#xff1b; &#xff08;2&#xff09;“局外点”是不能适应该模型的数据&#xff1b; &#xff08;3&#xff0…
阅读更多...
RANSAC算法与原理（一）

RANSAC算法与原理（一）

目录 算法介绍举例 算法的基本思想和流程算法的实现流程&#xff1a;迭代次数的推导算法的实现 python代码实现References 算法介绍 首先我们从Random sample consensus - Wikipedia上找到RANSAC原理的介绍。 RANSAC算法的中文名称是随机抽样一致算法(Random Sample Consenus…
阅读更多...
RANSAC算法——看完保证你理解

RANSAC算法——看完保证你理解

目录 1 最小二乘算法的缺陷2 RANSAC算法2.1 原理2.2 实例2.3 参数 参考感谢阅读 RANSAC全程Random sample consensus&#xff0c;中文即“随机抽样一致算法”&#xff0c;该方法采用迭代的方式从一组包含离群&#xff08;outlier或者错误数据&#xff09;的被观测数据中估算出数…
阅读更多...
RANSAC算法介绍

RANSAC算法介绍

一、RANSAC介绍 随机抽样一致算法&#xff08;RANdom SAmple Consensus,RANSAC&#xff09;,采用迭代的方式从一组包含离群的被观测数据中估算出数学模型的参数。RANSAC算法假设数据中包含正确数据和异常数据&#xff08;或称为噪声&#xff09;。正确数据记为内点&#xff08;…
阅读更多...
RANSAC算法讲解

RANSAC算法讲解

RANSAC是“RANdom SAmple Consensus&#xff08;随机抽样一致&#xff09;”的缩写。它可以从一组包含“局外点”的观测数据集中&#xff0c;通过迭代方式估计数学模型的参数。它是一种不确定的算法——它有一定的概率得出一个合理的结果&#xff1b;为了提高概率必须提高迭代次…
阅读更多...
RANSAC介绍（Matlab版直线拟合+平面拟合）

RANSAC介绍（Matlab版直线拟合+平面拟合）

RANSAC介绍&#xff08;Matlab版直线拟合平面拟合&#xff09; 本人邮箱&#xff1a;sylvester0510163.com&#xff0c;欢迎交流讨论&#xff0c; 欢迎转载&#xff0c;转载请注明网址http://blog.csdn.net/u010128736/ 一、RANSAC介绍 随机抽样一致算法&#xff08;RANdom SA…
阅读更多...
RANSAC算法（仅供学习使用）

RANSAC算法（仅供学习使用）

1.定义 RANSAC&#xff08;Random Sample Consensus&#xff09;算法是一种基于随机采样的迭代算法&#xff0c;用于估计一个数学模型参数。它最初由Fischler和Bolles于1981年提出&#xff0c;主要用于计算机视觉和计算机图形学中的模型拟合和参数估计问题。 RANSAC算法的基本…
阅读更多...
前端调试手机app

前端调试手机app

有时候应用在电脑网页端显示是正常的&#xff0c;但是一安装到手机上或者在手机浏览器上打开&#xff0c;就会显示各种问题问题。 在网上找了很长时间&#xff0c;最方便的就是利用在电脑上利用谷歌浏览器进行调试&#xff0c;输入网址chrome://inspect/#devices&#xff0c;进…
阅读更多...
跨平台应用开发进阶(三十七)uni-app前端监控方案 Sentry 探究

跨平台应用开发进阶(三十七)uni-app前端监控方案 Sentry 探究

文章目录 一、前言二、Sentry 简介三、Sentry 部署3.1 docker 的部署 (mac版)3.2 部署 sentry3.3 创建项目3.4 前端部署&#xff0c;注入监控代码 四、sentry 操作界面介绍五、拓展阅读 一、前言 在日益发达的网络时代&#xff0c;web应用也是越来越复杂&#xff0c;尤其是前端…
阅读更多...
uni-app 开发跨平台应用前端框架

uni-app 开发跨平台应用前端框架

前言 uni-app 是一个使用 vue.js 开发跨平台应用的前端框架&#xff0c;由于它具备"编写一次代码可发布到多个平台"的特点&#xff0c;大大的节省了开发成本&#xff0c;极速提升了开发效率。 一、uni-app 简介 uni-app 是一个使用 Vue.js 开发所有前端应用的框架。…
阅读更多...
uni-app开发所有前端应用的框架

uni-app开发所有前端应用的框架

uni-app 是一个使用 Vue.js 开发所有前端应用的框架&#xff0c;开发者编写一套代码&#xff0c;可发布到iOS、Android、H5、以及各种小程序&#xff08;微信/支付宝/百度/头条/QQ/钉钉&#xff09;等多个平台。 DCloud公司拥有420万开发者&#xff0c;几十万应用案例、6.5亿手…
阅读更多...
比较几种热门Hybrid App前端框架

比较几种热门Hybrid App前端框架

作为一种既能够在原生应用程序环境中运行&#xff0c;也能够在 Web 浏览器中运行的应用程序&#xff0c;Hybrid App 主要使用 Web 技术进行开发&#xff0c;如 HTML、CSS 和JavaScript&#xff0c;并使用一个中间层将其封装在原生应用程序中。随着技术的持续推进&#xff0c;Hy…
阅读更多...
APP管理平台--前端篇，首页（三）

APP管理平台--前端篇，首页（三）

作为首页&#xff0c;肯定在打开网址后就看得到对应信息。那么作为APP管理平台&#xff0c;这个信息自然而然的表现成了APP列表。那么依据现有各大应用市场需要分为已上线和未上线。但是在实际做的时候没有区分&#xff0c;这次项目中将所有新增的APP都展示了。区分布局就决定了…
阅读更多...
一天撸一个财务APP系统【安卓端+前端+后端】

一天撸一个财务APP系统【安卓端+前端+后端】

昨天有个粉丝朋友也想学开发Web和小程序、安卓&#xff0c;问可以在大学学会吗&#xff1f; 在学校学到的东西真的有限&#xff1a; 在很多的高校&#xff0c;有一些教授是学院派的&#xff0c;他们没有做过多少开发工作&#xff0c;上课就是照本宣科&#xff0c;讲的知识点都…
阅读更多...
如何查看手机APP使用的前端框架？

如何查看手机APP使用的前端框架？

一、首先获取该APP的apk包&#xff08;长按APP&#xff0c;点击‘分享’&#xff0c;分享到微信‘文件传输助手’&#xff0c;即可获得apk包--参考本博主上篇文章&#xff09;。 二、把apk扩展名改成.zip然后解压。不同的编译软件目录结果也不一样。&#xff08;为方便起见&am…
阅读更多...
【网络协议】IPV4协议介绍

【网络协议】IPV4协议介绍

&#x1f4aa;本节内容&#xff1a;IPV4协议介绍、IPV4地址格式、IPV4数据格式及C项目结构体设计 &#x1f60f;【Qt6网络抓包工具项目实战】总导航目录&#xff08;建议收藏书签~~~&#xff09; ✌️ part1 &#x1f60f;【Qt6网络抓包工具项目实战】1.1Qt6.2.2环境搭建(免费…
阅读更多...
DHCP协议

DHCP协议

目录 1、DHCP协议 2、DHCP的工作过程 动态获取IP地址流程 跟新租期流程 解除租期流程 1、DHCP协议 DHCP(Dynamic Host Configuration Protocol)协议是处于应用层的协议。一个主机如果想正常上网&#xff0c;需要配置IP地址&#xff0c;子网掩码&#xff0c;默认网关基本配置…
阅读更多...
TCP/IP-----协议号、端口号、ARP、icmp

TCP/IP-----协议号、端口号、ARP、icmp

文章目录 一、数据流向过程二、协议详解1&#xff09;ARP协议2&#xff09;ICMP协议 协议号 协议号是存在于IP数据报的首部的20字节的固定部分&#xff0c;占有8bit.该字段是指出此数据报所携带的是数据是使用何种协议&#xff0c;以便目的主机的IP层知道将数据部分上交给哪个处…
阅读更多...
UDP协议

UDP协议

引言 本文中只关于IPv4&#xff1b;UDP是一种保留消息边界的简单的面向数据报的传输层协议。它不提供差错纠正、队列管理、重复消除、流量控制和拥塞控制。总之&#xff0c;能没有的都没了。但它提供了差错检测&#xff0c;是一种端到端的校验和。因此使用它的程序必须自己实现…
阅读更多...
BGP协议

BGP协议

BGP协议 工作层工作原理BGP简单配置———含密码认证配置个人图解BGP 工作层 BGP是工作在应用层的协议&#xff0c;但基于传输层的TCP协议 工作原理 路由协议通常分为内部网关协议&#xff08;IGP: Interior Gateway Protocol&#xff09;和外部网关协议&#xff08;EGP: Ext…
阅读更多...
推荐文章

Copyright @ 2022~2023