`
grunt1223
  • 浏览: 423243 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

我的数学之美(一)——RANSAC算法详解

阅读更多
给定两个点p1与p2的坐标,确定这两点所构成的直线,要求对于输入的任意点p3,都可以判断它是否在该直线上。初中解析几何知识告诉我们,判断一个点在直线上,只需其与直线上任意两点点斜率都相同即可。实际操作当中,往往会先根据已知的两点算出直线的表达式(点斜式、截距式等等),然后通过向量计算即可方便地判断p3是否在该直线上。

生产实践中的数据往往会有一定的偏差。例如我们知道两个变量X与Y之间呈线性关系,Y=aX+b,我们想确定参数a与b的具体值。通过实验,可以得到一组X与Y的测试值。虽然理论上两个未知数的方程只需要两组值即可确认,但由于系统误差的原因,任意取两点算出的a与b的值都不尽相同。我们希望的是,最后计算得出的理论模型与测试值的误差最小。大学的高等数学课程中,详细阐述了最小二乘法的思想。通过计算最小均方差关于参数a、b的偏导数为零时的值。事实上,在很多情况下,最小二乘法都是线性回归的代名词。

遗憾的是,最小二乘法只适合与误差较小的情况。试想一下这种情况,假使需要从一个噪音较大的数据集中提取模型(比方说只有20%的数据时符合模型的)时,最小二乘法就显得力不从心了。例如下图,肉眼可以很轻易地看出一条直线(模式),但算法却找错了。



RANSAC算法的输入是一组观测数据(往往含有较大的噪声或无效点),一个用于解释观测数据的参数化模型以及一些可信的参数。RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点,并用下述方法进行验证:

  • 有一个模型适应于假设的局内点,即所有的未知参数都能从假设的局内点计算得出。
  • 用1中得到的模型去测试所有的其它数据,如果某个点适用于估计的模型,认为它也是局内点。
  • 如果有足够多的点被归类为假设的局内点,那么估计的模型就足够合理。
  • 然后,用所有假设的局内点去重新估计模型(譬如使用最小二乘法),因为它仅仅被初始的假设局内点估计过。
  • 最后,通过估计局内点与模型的错误率来评估模型。
  • 上述过程被重复执行固定的次数,每次产生的模型要么因为局内点太少而被舍弃,要么因为比现有的模型更好而被选用。


整个过程可参考下图:



关于算法的源代码,Ziv Yaniv曾经写一个不错的C++版本,我在关键处增补了注释:
#include <math.h>
#include "LineParamEstimator.h"

LineParamEstimator::LineParamEstimator(double delta) : m_deltaSquared(delta*delta) {}
/*****************************************************************************/
/*
 * Compute the line parameters  [n_x,n_y,a_x,a_y]
 * 通过输入的两点来确定所在直线,采用法线向量的方式来表示,以兼容平行或垂直的情况
 * 其中n_x,n_y为归一化后,与原点构成的法线向量,a_x,a_y为直线上任意一点
 */
void LineParamEstimator::estimate(std::vector<Point2D *> &data, 
																	std::vector<double> &parameters)
{
	parameters.clear();
	if(data.size()<2)
		return;
	double nx = data[1]->y - data[0]->y;
	double ny = data[0]->x - data[1]->x;// 原始直线的斜率为K,则法线的斜率为-1/k
	double norm = sqrt(nx*nx + ny*ny);
	
	parameters.push_back(nx/norm);
	parameters.push_back(ny/norm);
	parameters.push_back(data[0]->x);
	parameters.push_back(data[0]->y);		
}
/*****************************************************************************/
/*
 * Compute the line parameters  [n_x,n_y,a_x,a_y]
 * 使用最小二乘法,从输入点中拟合出确定直线模型的所需参量
 */
void LineParamEstimator::leastSquaresEstimate(std::vector<Point2D *> &data, 
																							std::vector<double> &parameters)
{
	double meanX, meanY, nx, ny, norm;
	double covMat11, covMat12, covMat21, covMat22; // The entries of the symmetric covarinace matrix
	int i, dataSize = data.size();

	parameters.clear();
	if(data.size()<2)
		return;

	meanX = meanY = 0.0;
	covMat11 = covMat12 = covMat21 = covMat22 = 0;
	for(i=0; i<dataSize; i++) {
		meanX +=data[i]->x;
		meanY +=data[i]->y;

		covMat11	+=data[i]->x * data[i]->x;
		covMat12	+=data[i]->x * data[i]->y;
		covMat22	+=data[i]->y * data[i]->y;
	}

	meanX/=dataSize;
	meanY/=dataSize;

	covMat11 -= dataSize*meanX*meanX;
        covMat12 -= dataSize*meanX*meanY;
	covMat22 -= dataSize*meanY*meanY;
	covMat21 = covMat12;

	if(covMat11<1e-12) {
		nx = 1.0;
	        ny = 0.0;
	}
	else {	    //lamda1 is the largest eigen-value of the covariance matrix 
	           //and is used to compute the eigne-vector corresponding to the smallest
	           //eigenvalue, which isn't computed explicitly.
		double lamda1 = (covMat11 + covMat22 + sqrt((covMat11-covMat22)*(covMat11-covMat22) + 4*covMat12*covMat12)) / 2.0;
		nx = -covMat12;
		ny = lamda1 - covMat22;
		norm = sqrt(nx*nx + ny*ny);
		nx/=norm;
		ny/=norm;
	}
	parameters.push_back(nx);
	parameters.push_back(ny);
	parameters.push_back(meanX);
	parameters.push_back(meanY);
}
/*****************************************************************************/
/*
 * Given the line parameters  [n_x,n_y,a_x,a_y] check if
 * [n_x, n_y] dot [data.x-a_x, data.y-a_y] < m_delta
 * 通过与已知法线的点乘结果,确定待测点与已知直线的匹配程度;结果越小则越符合,为
 * 零则表明点在直线上
 */
bool LineParamEstimator::agree(std::vector<double> &parameters, Point2D &data)
{
	double signedDistance = parameters[0]*(data.x-parameters[2]) + parameters[1]*(data.y-parameters[3]); 
	return ((signedDistance*signedDistance) < m_deltaSquared);
}


RANSAC寻找匹配的代码如下:
/*****************************************************************************/
template<class T, class S>
double Ransac<T,S>::compute(std::vector<S> &parameters, 
													  ParameterEsitmator<T,S> *paramEstimator , 
												    std::vector<T> &data, 
												    int numForEstimate)
{
	std::vector<T *> leastSquaresEstimateData;
	int numDataObjects = data.size();
	int numVotesForBest = -1;
	int *arr = new int[numForEstimate];// numForEstimate表示拟合模型所需要的最少点数,对本例的直线来说,该值为2
	short *curVotes = new short[numDataObjects];  //one if data[i] agrees with the current model, otherwise zero
	short *bestVotes = new short[numDataObjects];  //one if data[i] agrees with the best model, otherwise zero
	

		      //there are less data objects than the minimum required for an exact fit
	if(numDataObjects < numForEstimate) 
		return 0;
        // 计算所有可能的直线,寻找其中误差最小的解。对于100点的直线拟合来说,大约需要100*99*0.5=4950次运算,复杂度无疑是庞大的。一般采用随机选取子集的方式。
	computeAllChoices(paramEstimator,data,numForEstimate,
										bestVotes, curVotes, numVotesForBest, 0, data.size(), numForEstimate, 0, arr);

	   //compute the least squares estimate using the largest sub set
	for(int j=0; j<numDataObjects; j++) {
		if(bestVotes[j])
			leastSquaresEstimateData.push_back(&(data[j]));
	}
        // 对局内点再次用最小二乘法拟合出模型
	paramEstimator->leastSquaresEstimate(leastSquaresEstimateData,parameters);

	delete [] arr;
	delete [] bestVotes;
	delete [] curVotes;	

	return (double)leastSquaresEstimateData.size()/(double)numDataObjects;
}


在模型确定以及最大迭代次数允许的情况下,RANSAC总是能找到最优解。经过我的实验,对于包含80%误差的数据集,RANSAC的效果远优于直接的最小二乘法。

RANSAC可以用于哪些场景呢?最著名的莫过于图片的拼接技术。优于镜头的限制,往往需要多张照片才能拍下那种巨幅的风景。在多幅图像合成时,事先会在待合成的图片中提取一些关键的特征点。计算机视觉的研究表明,不同视角下物体往往可以通过一个透视矩(3X3或2X2)阵的变换而得到。RANSAC被用于拟合这个模型的参数(矩阵各行列的值),由此便可识别出不同照片中的同一物体。可参考下图:







另外,RANSAC还可以用于图像搜索时的纠错与物体识别定位。下图中,有几条直线是SIFT匹配算法的误判,RANSAC有效地将其识别,并将正确的模型(书本)用线框标注出来:




  • 大小: 23.1 KB
  • 大小: 117.6 KB
  • 大小: 1.7 MB
  • 大小: 1.9 MB
  • 大小: 1.9 MB
  • 大小: 105.8 KB
分享到:
评论

相关推荐

    带有线/平面拟合示例 的 RANSAC算法的python实现_python_代码_下载

    RANSAC(Random Sample Consensus,随机样本共识)是一种用于估计数学模型参数的迭代方法,尤其在处理有噪声数据和异常值的情况下非常有效。在计算机视觉、图像处理和机器学习领域,RANSAC广泛用于直线检测、平面...

    基于RANSAC算法的贝赛尔曲线拟合

    贝塞尔曲线是一种在计算机图形学、数学和工程领域广泛应用的参数化曲线。它以其灵活性和易于控制的特性,被广泛用于二维和三维图形的设计中,如CAD系统、游戏开发和动画制作等。RANSAC(Random Sample Consensus,...

    ransac算法经典文章

    RANSAC是一种统计学方法,用于从包含异常值(outliers)的数据集中估计数学模型的参数。其基本思想是通过迭代过程来选择数据集中的随机子集,这些子集被用来估计模型参数,并检查其余数据点是否与该模型一致。这一...

    ransac 算法(matlab)

    ransac(Random Sample Consensus,随机抽样一致)算法是一种在存在噪声数据和异常值的情况下,用于估计模型参数的有效方法。在计算机视觉、图像处理和机器学习领域,ransac算法常用于解决诸如线性拟合、平面检测、...

    使用Verilog语言实现RANSAC算法

    使用Verilog语言实现RANSAC算法 文件结构: RANSCA ——vivado工程目录 ——PYTHON:数据预处理和算法的python实现 ——PIC:工程运行及仿真截图 ——DOC:设计报告及其他 ——设计报告.docx/.pdf ——sc:...

    机器视觉:ransac算法详解

    RANSAC是一种常用的参数估计方法,全称为Random Sample Consensus(随机抽样一致性)。它通过随机选择数据中的一部分,然后根据这些数据拟合模型,统计模型与其他数据的偏差,最终筛选出符合一定阈值的数据,用于...

    RANSAC算法在图像配准中的应用文档

    RANSAC(Random Sample Consensus)算法是一种广泛应用于计算机视觉领域中的鲁棒性估计技术,主要用于模型拟合过程中的异常值检测。在图像处理、机器学习等应用场景中,面对含有大量噪声的数据时,RANSAC能够有效地...

    c ++实现的 RANSAC算法从给定的点中找到 n 个最佳拟合圆_C++_代码_下载

    RANSAC(Random Sample Consensus,随机样本一致)算法是一种在数据中识别模型参数的迭代方法,常用于去除噪声和异常值。它被广泛应用于计算机视觉、图像处理和机器学习领域,例如找到图像中的直线、平面、圆或其他...

    RANSAC算法的c++实现版本

    RANSAC(Random Sample Consensus,随机样本一致)算法是一种在数据中识别模型参数的迭代方法,常用于处理带有噪声的数据。它通过选取随机子集(样本)来估计模型,并计算这些样本与模型的吻合程度,从而排除不匹配...

    RANSAC.rar_RANSAC_RANSAC算法_ransac msac区别

    二维图像中随机抽样一致性RANSAC算法的实现

    RANSAC算法剔除匹配误配点原理

    RANSAC(Random Sample Consensus,随机样本一致)算法是一种在计算机视觉和图像处理领域广泛应用的算法,主要用于去除噪声数据,特别是从不完整的、错误的数据中提取有用的几何模型。RANSAC算法的核心思想是通过...

    RANSAC算法C程序

    RANSAC(Random Sample Consensus,随机抽样一致性)算法是一种在存在噪声数据中的模型估计方法,常用于计算机视觉和图像处理领域。该算法通过反复选取随机子集(样本)来确定一个数学模型,并判断剩余数据对这个...

    RANSAC 算法C++实现

    RANSAC(Random Sample Consensus,随机样本一致)算法是一种在数据集中识别离群值(outliers)并估计模型参数的统计方法。它常用于计算机视觉、图像处理和机器学习领域,例如直线检测、平面估计、相机标定等任务。...

    VC++实现 RANSAC算法

    RANSAC(Random Sample Consensus)算法是一种在存在噪声数据中的模型估计方法,常用于计算机视觉和图像处理领域。在VC++环境下实现RANSAC算法,可以有效地从数据集中识别并剔除异常值,比如在匹配点对中去除误匹配...

    580.rar_RANSAC改进_ransac C_ransac 改进_改进ransac算法_算法改进

    ransac算法及其各种改进算法,以及仿真结果分析

    Ransac算法的c++实现

    RANSAC(Random Sample Consensus,随机样本共识)是一种用于估计数学模型参数的迭代方法,尤其在处理含有噪声数据和异常值的情况下非常有效。在计算机视觉、图像处理和机器学习领域,RANSAC广泛用于估计诸如线、...

    一种投票式并行RANSAC算法及其FPGA实现.pdf

    投票式并行RANSAC算法是在传统的RANSAC算法基础上的一种改进,旨在提高算法在数据量大、局外点比例高和模型复杂等条件下运算速度和效率。RANSAC算法由Fischler等人在1981年提出,其原理简单,具有很强的鲁棒性,被...

    RANSAC算法 MATLAB实现

    国外高手编写的RANSAC算法工具箱,可以对二维和三维数据进行评估,内附例子。-Prepared by foreign experts RANSAC algorithm toolbox, can be two-dimensional and three-dimensional data to assess the attached ...

    Ransac算法

    Ransac算法 Ransac除外点

    RANSAC算法及其源代码解析合集

    RANSAC(Random Sample Consensus)算法是一种在包含噪声数据的集合中寻找可靠模型的迭代方法,常用于计算机视觉和图像处理领域。该算法的基本思想是假设数据中存在一部分“内点”(即符合特定模型的数据点),而...

Global site tag (gtag.js) - Google Analytics