RANdom SAmple Consensus의 준말이며 Parameter Estimation이라고도 불린다.
일정한 sample에서 sample이 가지고 있는 model을 추정하는 데 주로쓰인다.
다음과 같은 순서로 진행이 되며, 생각보다 간단하다.
1. 원하는 모델을 정한다(line, ellipse, homography 등)
-> 위에서 Parameter estimation이라고도 불린다 했듯이, 원하는 모델의 일반식으로부터 파라메터를 추정하여 model fitting을 한다.
2. 주어진 sample로 부터 random하게 subsample을 추출한다.
-> subsample 추출 시 유의할 사항으로는 반드시 적은 오차로 모델의 일반식을 추정할수 있는 갯수여야 한다.
예를 들면 1개의 sample로 line 모델을 추정할 수는 있지만 model의 개수는 무한히 많다. 하지만 2개의 sample로부터 model을 추정한다면, 경우의 수는 줄어들게 되는것이다.
또한, 주어진 sample들이 model을 추정하는데 적절해야 한다. 예를들어 ellipse model 추정시 10개의 sample을 추출 하였는데, 10개가 하나의 직선 상에 존재하게 되면 신뢰도가 낮은 모델추출하게 되고, 연산시간이 오래 걸린다.
3. subsample로부터 model을 추정한다.
4. 3의 model로 sample간의 신뢰성을 구한다.
-> model과 sample간의 distance를 구한 뒤, 적절한 threshold로 model에 fitting 여부(inlier)를 확인한다.
5. fitting된 sample(inlier) 개수에 따라 iteration의 수를 제한한다.
-> iteration = log(1-p) / log(1-(1-e)^s)
p : probabliity(신뢰도) s: number of points in a sample(2에서 추출한 sample개수) e: probability that a point is an oulier(outlier 수/총 sample 개수)
6. 모든 itheration이 종료 된 후, inlier 개수가 가장 모델이 최종 best 모델이 된다.
기본적인 알고리즘은 위와 같지만, 좀더 나은 결과를 내기 위하여 sample의 normalization 등 여러가지 방법을 추가한 논문들이 소개가 되고있다.
RANSAC 구현시 고려할 사항은 어떤 model을 선정하느냐, subsample 신뢰도 검사를 어떻게 하느냐, 마지막으로 sample과 모델간의 distance를 구하는 방법 등이 되겠다.