RANSAC(Random Sample Consensus)

* RANSAC : 무작위 하게

* SAMPLE : 데이터 샘플을  뽑아서 모델을 추정하고

* CONSENSUS : 모델에 대한 데이터의 합의도를 구해 정확한 모델임을 평가 

* RANSAC을 하는 이유? 

* Inlier  데이터 : 기하학적으로나 통계적으로 올바른 데이터

* Outlier 데이터 - 기하학적으로나 통계적으로 잘못된 데이터 

 - 단순히 데이터만 봐서는 inlier/outlier 구분하기 어려움

 - model parameter를 정확하게 계산하기 위해서는 Inlier 데이터만 사용해야함 

  -> Inlier 데이터로만 model parameter 계산하면 좋은 모델 파라미터가 나온다

  -> Outlier 데이터를 포함해서 model parameter를 계산하면 잘못된 모델 파라미터가 나옴 

   * Outlier가 생길 수 있는 원인들 

     - 조명 변화

    - 부분적 가려짐

    - 회전

    - 모션 블러 등등.. 

 

 

* Outlier removal란?

 - Model paramer를 계산하기 위해, 전체 데이터 중 inlier와 outlier를 구분하여 inlier 데이터만 계산에 사용해야함

  --> 특히, 컴퓨터 비전에서 사용하는 least-squres 최적화 방식은 outlier 데이터에 굉장히 취약함 

   

 

* 작동 방식 

 1. 전체 데이터로부터 무작위로 minimal set의 데이터를 추출

 2. 뽑은 데이터로 모델 추정

 3. Score 추정

 4. 1로 돌아감

 

* RANSAC 공식 

 - T : 샘플링의 갯수

 - P : 우리가 고른 데이터가 inlier일 확률

 - e : 전체 데이터의 inlier : outlier 비율

 - s : minimal set을 만들기 위한 데이터의 갯수

 - p , e, s는 보통 우리가 고름 

 

T = log(1 - P) / log(1-(1-e)^s) 

 

* 장점

 - 성공 시 outlier를 효과적으로 걸러낼 수 있음

 - 대략적인 성공 시간을 알 수 있음 ( i.e. x번의 iteration 후 Y% 확률로 정확한 모델 추론 ) 

 - 일찍 끝나면 그만큼 시간을 벌음

 - 이해하기 쉬움 

 

 

* 단점 

 - 무작위 샘플이라 매번 결과가 다름 

   -> 이 때문에 deterministic test를 할 때 seed 고정을 해 주어야 함

 - outlier의 비중이 많아지면 돌아야 하는 iteration 수가 급격히 늘어남

 - 실패할 경우 model 추론에 완전히 실패함

 - Threshold 값을 유저가 직접 tuning 해야함

 - Multi-model 추론을 할 수가 없음