RANSAC

RANdom Sample Consensus
데이터셋에서 주어진 모델을 추정하는 알고리즘

Step 1. 샘플 데이터를 선택 후 이를 이용해 모델을 추정
Step 2. 샘플 데이터 외에 나머지 데이터를 이용해 추정 모델과 일치(method)하는 데이터 개수를 계산
method : 점과 직선 사이의 거리
threshold : 일치함을 판단하는 특정 값

$d=\displaystyle\frac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}}\le threshold$

Step 3. 일치하는 데이터의 개수가 일정한 임계치 이상이면 이를 최종 추정 모델로 사용
(일정 개수 이상 & 직전 최종 값보다 높으면 최종 추정 모델로 갱신)
Step 4. 새로운 샘플 선택, 일정 횟수(max_trials)만큼 반복

장단점

장점
예외(Outlier)를 효과적으로 제거 가능
구현 난이도가 낮고 다양한 모델에 대해 적용 가능
단점
Sampling 결과에 따라 비효율적인 결과를 나타낼 수 있음
Prior Sampling을 사용하지 않기 때문에 매 회 처음부터 다시 시작

개선 포인트

max_trials를 고정하지 않고 조기 종료 방법?
Sampling 결과를 제한할 수 있는 방법?