RANSAC
최소 자승법과 RANSAC
어떤 모델의 파라미터를 구하는 한 방법
- 최소 자승법 정의 : 데이터와의 residual^2의 합을 최소화하도록 모델의 파라미터를 구하는 방법
- 최소 자승법 단점 : 데이터에 outlier가 있으면 적용이 어려움
- 치소 자승법 대안
- LMedS
- M-estimator
- RANSAC
목적 : 측정 노이즈(Noise)가 심한 원본 데이터로부터 모델 파라메타(Parameta)를 예측하는 방법
- 직선(모델 : y=ax+b)을 찾는 예시에서는 RANSAC은 이 모델의 매개변수 a와 b를 추정해준다.
출처: https://carstart.tistory.com/190 [나이 서른에 햇병아리 프로그래머]
- 임이의 점 2개를 선택하여 직선의 방정식 L(a,b)을 계산 한다.
- 직선상에 점들이 오차범위(t)내의 점들을 선택 하여 inlier로 설정 한다. 그외는 outlier
- inlier의 갯수가 임계치(d) 갯수 이내 이면, inlier만으로 다시 직선의 방정식New_L을 추정한다.
- New_L이 적합 오차 e안에 속하면 후보 모델에 추가 한다.
- n번 반복 수행 한후 후보중 최적의 모델(=파라미터)값을 선택 한다.
오일석, 컴퓨터 비젼
다시 살펴 보기
https://carstart.tistory.com/190
Object detection in 3D point clouds의 20page참고
Random sample consensus algorithm (RANSAC)
UDACITY : https://classroom.udacity.com/courses/ud810/lessons/3189558841/concepts/31679389240923
"Random Sample Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography", 1981 by Martin A. Fischler and Robert C. Bolles
RANSAC의 이해와 영상처리 활용
A. 정의
- 무작위로 샘플 데이터들을 뽑은 다음에 최대로 컨센서스가 형성된 녀석을 선택
- Robust Estimation의 대표적인 알고리즘
B. 최소 자승법 Vs. RACSAC
- 최소자승법(least square method)은 데이터들과의 ∑residual2을 최소화하도록 모델을 찾지만,
- RANSAC은 컨센서스가 최대인, 즉 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택
 |
 |
|
|---|---|---|
| 노이즈 데이터 | 최소 자승법 | RANSAC |
 |
 |
 |
| 아웃라이어 데이터 | 최소 자습법(해결 못함) | RANCAS(해결) |
C. RANSAC 개선버젼 들
- MLESAC algorithm
- Local optimized RANSAC (LO-RANSAC),
- randomized RANSAC algorithm (RRANSAC)
D. RANSAC의 활용예
- local feature matching을 이용하여 영상에서 특정 물체를 찾을 때
- Visual Odometry (인접한 영상프레임에서 카메라 모션을 추정할 때)
- 위치인식을 위해 scene matching을 수행할 때
- 물체 추적을 위해 인접한 영상프레임에서 이동체의 모션을 추정할 때
E. 기본 동작과정
- 최대값이 없도록 c_max = 0으로 초기화작업을 한다.
- 무작위로 2점을 뽑는다. (p1, p2) (만약 2차함수면 포물선이기 때문에 3개를 뽑아야 한다.)
- 두 점을 지나는 직선 f(x)를 구한다.
- 임계값 T를 설정한다.
- 구해진 f(x)와 데이터들간의 거리를 구한다. 거리는 $$ r_i = \mid y_i - f(x_i) \mid $$ 같다. 이 거리가 T를 넘지 않는다면 개수를 Counting 하라.
- 개수인 C가 c_max와 비교해 더 크다면 현재 f(x)를 저장하고 그렇지 않으면 버린다.
- 2~6을 N번 반복한 후 최종 저장된 f(x)를 반환한다.
- (선택사항) 최종 f(x)를 지지하는 데이터들에 대해 최소자승법을 적용하여 결과를 refine한다.
F. 파라미터
임계값 T : inlier(참인정보)와 outlier(거짓정보)의 경계
반복수 N : 샘플링 과정을 몇 번 (N) 반복
G. 문제점
- 매번 결과가 달가 질수 있음
#include <iostream>
#include <thread>
#include <pcl/console/parse.h>
#include <pcl/filters/extract_indices.h>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/sample_consensus/ransac.h>
#include <pcl/sample_consensus/sac_model_plane.h>
#include <pcl/sample_consensus/sac_model_sphere.h>
#include <pcl/visualization/pcl_visualizer.h>
int
main(int argc, char** argv)
{
// initialize PointClouds
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);
pcl::PointCloud<pcl::PointXYZ>::Ptr final (new pcl::PointCloud<pcl::PointXYZ>);
// cloud에 랜덤 포인트 생성
std::vector<int> inliers;
// created RandomSampleConsensus object and compute the appropriated model
pcl::SampleConsensusModelPlane<pcl::PointXYZ>::Ptr model_p (new pcl::SampleConsensusModelPlane<pcl::PointXYZ> (cloud));
pcl::RandomSampleConsensus<pcl::PointXYZ> ransac (model_p);
ransac.setDistanceThreshold (.01);
ransac.computeModel();
ransac.getInliers(inliers);
// copies all inliers of the model computed to another PointCloud
pcl::copyPointCloud<pcl::PointXYZ>(*cloud, inliers, *final);
/// ...
return 0;
}
[추천] UDACITY강좌 :컴퓨터 비젼 - RANSAC