RANSAC(Random Sample Consensus)

RANSAC이란?

 

관측된 데이터들에 대하여 근사 모델(Fitting Model)의 파라미터를 추정하는 방법 중 하나이며, 무작위로 샘플 데이터를 뽑은 다음 최대로 일치하는 모델을 선택하기 때문에 노이즈 or 이상치(Outlier)에 영향을 덜 받는 방법이다.

 

그러나, 임의의 데이터를 선택하기 때문에 같은 데이터임에도 결과가 매번 달라질수 있으며 Outlier의 분포가 일정한 구조를 갖게 되면 Outlier에 근사할 수 있다.

 

RANSAC 알고리즘

 

N : 반복횟수, t = 모델과의 거리 임계값, max_point = inlier 데이터

 

1. max_point = 0, 모델 파라미터에 근사한 데이터들의 수를 초기화
2. 관측된 데이터 안에서 무작위로 세점을 뽑는다.
3. 세 점을 이용하여 근사한 모델 f(x)을 구한다.
4. 구해진 f(x)와의 거리 r = | y - f(x) | 가 임계값 t이하인 데이터의 수 Count를 구한다.
5. 만일 구해진 Count가 max_point 보다 크다면 현재 f(x)로 저장
6. 2~5를 N만큼 반복한 후, 최종 저장되어 있는 f(x)를 반환
7. f(x)를 지지하는 데이터들에 대해 최소자승법을 적용하여 결과를 개선

참고 자료

 

scikit-learn.org/stable/auto_examples/linear_model/plot_ransac.html

Robust linear model estimation using RANSAC — scikit-learn 0.24.1 documentation

darkpgmr.tistory.com/61#recentEntries

RANSAC의 이해와 영상처리 활용