RANSAC (Random Sample Consensus)

RANSAC

- Outlier(이상치)에 대해 영향을 적게 받도록 만든 line fitting 알고리즘

- 이미지 분석을 할 시에 어떠한 오브젝트의 line을 찾을 때 사용되는 알고리즘

 

위 그림은 RANSAC 알고리즘이 필요한 대표적인 예시이다.

Least-squares fit을 적용한 라인을 그리면 위 그림과 같이 outlier에 영향을 많이 받는것을 볼 수 있습니다.

이러한 outlier에 적게 영향을 받는 알고리즘이 RANSAC입니다.

 

알고리즘 적용 방법

 

1.     랜덤하게 점 두 개를 찾는다.

2.     두 개의 점을 이어주는 선을 그어준다.

3.     나머지 점들이 두 개의 점을 이어주는 선에 대한 inlier(선으로부터 계산된 값 내에 들어오는 점)들을 구해준다.

4.     모든 점들에 대해 반복을 해서 가장 inlier에 많이 들어오는 선을 선정

 

위 그림과 같이 선에서 일정거리의 inlier boundary를 정하고 boundary 내에 가장 많이 들어오는 선을 찾는 과정을 반복한다. 매우 간단해보이는 반복작업이 많이 필요한 알고리즘이지만 이미지분석 등 다양한 데이터분석 분야에서 사용되는 효율적인 회귀분석 방법론이다.

 

장점

- 간단하고 보편적이다.

- 많은 문제에 적용 가능한 알고리즘이다.

- 실제 데이터에 적용할시 좋은 결과를 낸다.

 

단점

- 튜닝할 파라미터가 너무 많다.

- inlier ratio의 수치를 적절하게 세팅하지 않을시 작동이 잘 안된다.

- 데이터의 샘플 수가 적을 시 원하는 결과가 나오지 않을 가능성이 있다.