该算法转载自：https://blog.csdn.net/czl389/article/details/60580574
RANSAC为Random Sample Consensus的缩写，它是根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，得到有效样本数据的算法。它于1981年由Fischler和Bolles最先提出。RANSAC算法经常用于计算机视觉中。例如，在立体视觉领域中同时解决一对相机的匹配点问题及基本矩阵的计算。
RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声。这些异常数据可能是由于错误的测量、错误的假设、错误的计算等产生的。同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法。
RANSAC基本思想描述如下：
①考虑一个最小抽样集的势为n的模型(n为初始化模型参数所需的最小样本数)和一个样本集P，集合P的样本数#(P)>n，从P中随机抽取包含n个样本的P的子集S初始化模型M；
②余集SC=P\S中与模型M的误差小于某一设定阈值t的样本集以及S构成S*。S*认为是内点集，它们构成S的一致集(Consensus Set)；
③若#(S*)≥N，认为得到正确的模型参数，并利用集S*(内点inliers)采用最小二乘等方法重新计算新的模型M*；重新随机抽取新的S，重复以上过程。
④在完成一定的抽样次数后，若未找到一致集则算法失败，否则选取抽样后得到的最大一致集判断内外点，算法结束。
假设已知一组特征匹配点，使用RANSAC算法剔除其中外点。建立RANSACFit函数如下：
RANSACFit(p1, p2, match, maxIter, seedSetSize, maxInlierError, goodFitThresh )
其中输入参数：p1，N1×2矩阵，每行都是一个特征点坐标；p2，N2×2矩阵，每行都是一个特征点坐标；match，M×2矩阵，每行代表一组匹配关系[index of p1, index of p2]；maxIter，RANSAC算法将执行的迭代次数；seedSetSize，随机抽取的样本点数；maxInlierError，最大内点偏差，如果这个匹配不在内点集中，将其看作内点最大可以容忍的误差；goodFitThresh，用于评判得到的模型是否足够优异的阈值。
输出：H，p1对p2进行鲁棒性仿射变换的单应估计。
MATLAB代码：
function H = RANSACFit(p1, p2, match, maxIter, seedSetSize, maxInlierError, goodFitThresh ) N = size(match, 1); if N<3 error(\'not enough matches to produce a transformation matrix\') end if ~exist(\'maxIter\', \'var\'), maxIter = 200; end if ~exist(\'seedSetSize\', \'var\'), seedSetSize = ceil(0.2 * N); end seedSetSize = max(seedSetSize,3); if ~exist(\'maxInlierError\', \'var\'), maxInlierError = 30; end if ~exist(\'goodFitThresh\', \'var\'), goodFitThresh = floor(0.7 * N); end H = eye(3); iota = Inf; kappa = 0; lambda = iota; alpha = seedSetSize; for i = 1 : maxIter, [beta, gamma] = part(match, alpha); eta = ComputeAffineMatrix(p1(beta(:, 1), :), p2(beta(:, 2), :)); delta = ComputeError(eta, p1, p2, gamma); epsilon = (delta <= maxInlierError); if sum(epsilon(:)) + alpha >= goodFitThresh, zeta = [beta; gamma(epsilon, :)]; eta = ComputeAffineMatrix(p1(zeta(:, 1), :), p2(zeta(:, 2), :)); theta = sum(ComputeError(eta, p1, p2, zeta)); if theta < iota, H = eta; kappa = lambda; iota = theta; end end end if sum(sum((H - eye(3)).^2)) == 0, disp(\'No RANSAC fit was found.\') end end function dists = ComputeError(H, pt1, pt2, match) dists = zeros(size(match,1),1); transform_pt1=H*[pt1(match(:,1),:)\';ones(1,size(match,1))]; subtract=pt2(match(:,2),:)-transform_pt1(1:2,:)\'; dists=sqrt(subtract(:,1).^2+subtract(:,2).^2); if size(dists,1) ~= size(match,1) || size(dists,2) ~= 1 error(\'wrong format\'); end end function [D1, D2] = part(D, splitSize) idx = randperm(size(D, 1)); D1 = D(idx(1:splitSize), :); D2 = D(idx(splitSize+1:end), :); end
2021-05-16 18:10:23 哲
请发表评论