RANSAC 알고리즘

RANdom SAmple Consensus

 

 

특정 임계값 이상의 데이터를 완전히 무시해버리는 특성이 있어 outlier(이상점)에 강건한 알고리즘

= 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법

 

outlier : 데이터의 분포에서 현저하게 벗어나 있는 관측값

 

 

Hypothesis - 가설 단계

전체 데이터에서 N개의 샘플을 선택하고, 선택된 샘플을 통해 모델을 예측한다.

 

Verification - 검증단계

데이터셋에서 모델과 일치하는 데이터의 수를 센 후, 최대 값일 경우 모델 파라미터를 새롭게 저장한다.

 

위 두가지 단계를 반복하여 진행

 

 

파라미터

 

샘플링 과정을 몇 번 (N) 반복할 것인지, 그리고 inlier와 outlier의 경계를 (T) 어떻게 정할 것인지

RANSAC 반복회수를 N, 한번에 뽑는 샘플 개수를 m, 입력 데이터들 중에서 inlier의 비율을 α라 할 때, N번 중 적어도 한번은 inlier에서만 샘플이 뽑힐 확률 p는 다음과 같다.

보통 p는 99.99% 이상으로 설정

만일 T를 너무 크게하면 모델간의 변별력이 없어지고 T를 너무 작게하면 RANSAC 알고리즘이 불안정해진다.

일반적인 방법으로는 inlier들의 residual 분산을 σ^2이라 할때, T = 2σ ~ 3σ 정도로 설정

 

 

참고

https://gnaseel.tistory.com/33

중학생도 이해할 수 있는 RANSAC 알고리즘 원리

https://darkpgmr.tistory.com/61

RANSAC의 이해와 영상처리 활용