Computer vision - RANSAC (line fitting)

1. Fitting

- 데이터에 잘 맞는 모델의 파라미터를 찾는 것.

- 그림처럼 n개의 데이터를 대표하는 line을 fitting한다고 해보자.

- 그럼 cost 함수를 정의하고 그 값이 최소가 되도록 fitting이 수행될 것이다. 

- 위 예시에서는 y값과 Line의 함수값 차이를 loss로 정의했고 이 값이 최소가 되는 m,b를 찾는다. 이게 fitting이다.

- 행렬식을 풀면 m,b가 나온다.

- 이번에는 cost function을 점과 직선의 거리의 합으로 정의했다.

- E가 최소가 되는 지점을 구하는 것이 fitting이다. 

- 저 행렬식은 SVD를 통해 구할 수 있다.

- 하지만 이런 방법들은 outlier의 영향을 크게 받는다.

- 얘는 outlier가 있어도 robust한 fitting을 하도록 로우 function을 정의한다.

 

- 이렇게 linear fitting은 해를 구할 수 있는 도구가 있다.

- 하지만 non linear function은 solution이 따로 존재하지 않는다. gradient descent같이 반복적 minimization으로 cost가 최소가 되는 지점을 찾아야 한다.

2. RANSAC (RANdom SAmple Consensus)

RANSAC의 이해와 영상처리 활용

- 위에서 살펴본 Linear fitting들은 outlier에 영향을 너무 많이 받는다.

- RANSAC은 컨센서스가 최대인, 즉 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법이다.

- 무작위로 두개의 점을 잇는 직선(model)을 그리고 그 직선에 데이터가 얼마나 많이 해당되는지 투표하는 방식이다. (inlier 수)

- 충분히 좋은 결과가 나올때까지 반복한다.

- RANSAC은 outlier에 robust하다.

- 투표율이 제일 높은 모델을 선택하게 된다.

- 확률적으로 s=2(직선) 모델을 찾는 경우 전체 데이터에 대한 outlier의 비율이 5퍼센트라면 2번만 무작위 선택 후 비교를 해보면 된다.

- 총 12개의 점중에 outlier는 2개이다. 그럼 Outlier의 비율은 20퍼센트보다 크다. 그러면 총 5번 투표를 반복하면 그 결과가 inlier를 잘 포함할 확률이 99퍼센트가 된다.

- 이렇게 구한 inliers만 가지고 Least Squares를 수행하면 더 정확한 결과가 나올 수 있다.