RANSAC算法原理与应用

一、RANSAC 是解决什么问题的https://www.bilibili.com/video/BV1tM41187br/?spm_id_from333.337.search-card.all.clickvd_source52997da921a43b4ed3611981bbdf91a4https://www.bilibili.com/video/BV1sj411v7Vo/?spm_id_from333.337.search-card.all.clickvd_source52997da921a43b4ed3611981bbdf91a4在含有大量离群点Outliers的数据中鲁棒地估计模型参数典型场景特征匹配中错误匹配很多点云中噪声 伪点拟合直线 / 平面 / 单应矩阵 / 基础矩阵PnP 前的 2D–3D 对应点中有假点普通最小二乘LS的问题对离群点极其敏感一个坏点就能“拉歪”整个模型RANSAC 的思想是宁可只用一小撮“干净点”也不被脏点污染宁可只用一小撮“干净点”也不被脏点污染宁可只用一小撮“干净点”也不被脏点污染二、RANSAC核心思想随机抽最小样本 → 拟合模型 → 统计内点 → 重复 → 选内点最多的模型利用随机采样和一致性检验的方法来取分数据中的内点和外点内点是指符合模型的数据外点是指不符合模型的数据。三、RANSAC 算法流程标准版设模型参数为 θStep 1随机采样Minimal Sample Set随机选最小数量的点例如直线2 点平面3 点单应矩阵4 对点基础矩阵8 点8-point分别计算所有点到当前模型的距离Step 2模型估计用最小样本估计模型通常是解析解 / DLTStep 3一致性检测Inlier Test对所有点计算误差Step 4统计内点数记录内点数量Step 5重复 N 次找到内点最多的模型Step 6可选模型重估用所有内点再做一次最小二乘 / LMRANSAC LM 工程黄金搭档四、RANSAC 数学本质1️⃣ 目标不是最小误差而是2️⃣ 内点概率驱动迭代次数若内点比例w最小样本数s成功概率p所需迭代次数案例一RANSAC 拟合二维直线最经典1️⃣ 构造数据含离群点clc; clear; close all; % 真实直线 y 2x 1 x_in linspace(0,10,50); y_in 2*x_in 1 randn(size(x_in))*0.3; % 离群点 x_out rand(1,20)*10; y_out rand(1,20)*20; x [x_in x_out]; y [y_in y_out]; figure; hold on; grid on; scatter(x, y, b); title(原始数据含离群点);2️⃣ RANSAC 实现clc; clear; close all; % 真实直线 y 2x 1 50个直线上的点 x_in linspace(0,10,50); y_in 2*x_in 1 randn(size(x_in))*0.3; % 离群点 20个离群点 x_out rand(1,20)*10; y_out rand(1,20)*20; % 直线点离群点70 个 x [x_in x_out]; y [y_in y_out]; figure; hold on; grid on; scatter(x, y, b); title(原始数据含离群点); % 迭代次数 num_iter 1000; % 点到直线的距离阈值判断 threshold 0.5; % 把最好的内点集合起来 best_inliers []; for i 1:num_iter % 随机选2个点 idx randperm(length(x), 2); x1 x(idx(1)); y1 y(idx(1)); x2 x(idx(2)); y2 y(idx(2)); % 拟合直线 ax by c 0 a y2 - y1; b x1 - x2; c x2*y1 - x1*y2; % 计算所有这里是70个点点到直线距离 dist abs(a*x b*y c) / sqrt(a^2 b^2); inliers find(dist threshold); if length(inliers) length(best_inliers) best_inliers inliers; end end x_in x(best_inliers); y_in y(best_inliers); % 拟合 p polyfit(x_in, y_in, 1); x_fit linspace(0,10,100); y_fit polyval(p, x_fit); figure; hold on; grid on; scatter(x, y, b); scatter(x_in, y_in, r); plot(x_fit, y_fit, k, LineWidth,2); legend(All points,Inliers,RANSAC Line); title(RANSAC 直线拟合结果);案例二 RANSAC 拟合圆原理1️⃣ 圆的一般方程2️⃣ 最小样本数Minimal Sample Set3 个不共线点这是圆的解析最小解3️⃣ 点到圆的误差RANSAC 判据常用误差实例1构造测试数据含离群点clc; clear; close all; % 真实圆参数 a0 5; b0 4; r0 3; theta linspace(0,2*pi,80); x_in a0 r0*cos(theta) randn(size(theta))*0.05; y_in b0 r0*sin(theta) randn(size(theta))*0.05; % 离群点 x_out rand(1,30)*10; y_out rand(1,30)*10; x [x_in x_out]; y [y_in y_out]; figure; hold on; axis equal; grid on; scatter(x, y, b); title(原始数据含离群点);2、RANSAC 拟合圆核心代码num_iter 2000; threshold 0.1; best_inliers []; best_circle []; N length(x); for k 1:num_iter % 随机选 3 个点 idx randperm(N,3); x1 x(idx(1)); y1 y(idx(1)); x2 x(idx(2)); y2 y(idx(2)); x3 x(idx(3)); y3 y(idx(3)); % 判断是否共线行列式 if abs(det([x1 y1 1; x2 y2 1; x3 y3 1])) 1e-3 continue; end % 解析求圆心和半径 A 2*[x2-x1, y2-y1; x3-x1, y3-y1]; B [x2^2y2^2 - x1^2-y1^2; x3^2y3^2 - x1^2-y1^2]; C A\B; a C(1); b C(2); r sqrt((x1-a)^2 (y1-b)^2); % 计算内点 dist abs(sqrt((x-a).^2 (y-b).^2) - r); inliers find(dist threshold); % 更新最优模型 if length(inliers) length(best_inliers) best_inliers inliers; best_circle [a b r]; end end3、用内点进行最小二乘精修强烈推荐xin x(best_inliers); yin y(best_inliers); % 代数最小二乘线性 A [2*xin(:), 2*yin(:), ones(length(xin),1)]; B xin(:).^2 yin(:).^2; param A\B; a param(1); b param(2); r sqrt(param(3) a^2 b^2);4、可视化theta linspace(0,2*pi,200); xc a r*cos(theta); yc b r*sin(theta); figure; hold on; axis equal; grid on; scatter(x, y, b); scatter(x(best_inliers), y(best_inliers), r); plot(xc, yc, k, LineWidth,2); legend(All points,Inliers,RANSAC Circle); title(RANSAC 圆拟合结果);案例三、RANSAC 拟合平面典型应用点云地面分割无人车工件基准面结构光参考平面ICP / PnP / BA 前的几何约束平面数学模型1️⃣ 平面一般式2️⃣ 最小样本数Minimal Sample Set3 个不共线点3️⃣ 点到平面距离RANSAC 判据实例构造测试点云含离群点clc; clear; close all; % 真实平面z 0.5x 0.2y 1 [xg, yg] meshgrid(linspace(0,5,20)); zg 0.5*xg 0.2*yg 1 randn(size(xg))*0.05; % 转为点集 pts_in [xg(:), yg(:), zg(:)]; % 离群点 pts_out rand(80,3)*6; pts [pts_in; pts_out];RANSAC 主循环num_iter 2000; threshold 0.1; best_inliers []; best_plane []; N size(pts,1); for k 1:num_iter % 随机选3点 idx randperm(N,3); p1 pts(idx(1),:); p2 pts(idx(2),:); p3 pts(idx(3),:); % 共线判断 v1 p2 - p1; v2 p3 - p1; n cross(v1,v2); if norm(n) 1e-6 continue; end % 平面参数 n n / norm(n); d -dot(n,p1); % 点到平面距离 dist abs(pts*n d); inliers find(dist threshold); if length(inliers) length(best_inliers) best_inliers inliers; best_plane [n d]; end end用内点进行最小二乘精修SVDin_pts pts(best_inliers,:); % 去中心 centroid mean(in_pts,1); Q in_pts - centroid; % SVD [~,~,V] svd(Q,0); n V(:,end); d -dot(n,centroid); best_plane [n d];结果可视化figure; hold on; grid on; axis equal; scatter3(pts(:,1),pts(:,2),pts(:,3),b.); scatter3(in_pts(:,1),in_pts(:,2),in_pts(:,3),r.); % 绘制平面 [xp,yp] meshgrid(linspace(0,5,10)); zp -(best_plane(1)*xp best_plane(2)*yp best_plane(4)) / best_plane(3); surf(xp,yp,zp,FaceAlpha,0.5,EdgeColor,none); legend(All points,Inliers,Plane); title(RANSAC 平面拟合);HALCON / PCL 对应参数segment_planes_object_model_3d( ObjectModel3D, distance_threshold, DistanceThreshold, min_support, MinSupport, ObjectModel3DPlanes, PlaneInfo ) pcl::SACSegmentationpcl::PointXYZ seg; seg.setModelType(pcl::SACMODEL_PLANE); seg.setMethodType(pcl::SAC_RANSAC); seg.setDistanceThreshold(0.01); seg.setMaxIterations(1000); seg.setProbability(0.99);案例四、