RANSAC이란? (+최소자승법)

이번 포스팅은 RANSAC과 최소자승법을 다루도록 하겠습니다.

다크프로그래머님의 블로그를 참고했습니다~

http://darkpgmr.tistory.com/

RANSAC은 Random Sample Consensus의 약자입니다.

RANSAC은 영상처리에 자주 등장하는 알고리즘입니다.

먼저 RANSAC을 다루기 전에 최소자승법을 간단히 알고 넘어가겠습니다.

최소자승법이란 최소제곱법라고도 부르고 영어로 LSM(Least Squared Method) or LMS(Least Mean Square)라고 부릅니다.

논문을 보면 LMS, LSM용어가 많이 등장합니다.

최소자승법은 특정한 데이터의 모델 파라미터를 Residual^2의 합이 최소화 되도록 구하는 방법입니다.

여기서 파란 점들이 데이터고 빨간선이 데이터들을 통해 파악한 모델입니다. 

여기선 모델이 직선으로 판단되었으니 f(x) = ax+b 꼴이 되겠습니다. 여기서 a,b가 파라미터입니다.

그리고 Residual은 데이터가 빨간선에서부터 얼마나 떨어졌는가입니다.

데이터들이 (x1,y1),...,(xi,yi)라고 표현하면 Residual은 yi - f(xi)라고 표현합니다.

여기서 결론은 

를 최소화하는 모델의 파라미터를 구하는 것 입니다.

이런 최소자승법은 영상처리에서 밝기 보정에 쓰일 수 있습니다.

그냥 A4용지를 촬영하면 빛에 의해 그냥 단색으로 보이는게 아니라 어느 부분은 어둡게 어느 부분은 밝게 나오는데

최소자승법을 통해 밝기의 변화를 파악해 단색으로 보정할 수 있습니다.

하지만 최소자승법에는 한계가 있습니다.

바로 Outlier(정상적인 분포에서 동떨어진 예외같은 데이터)가 있으면 이상적인 모델을 얻기 힘듭니다.

이를 해결하기 위한 방법에는 RANSAC이나 M-estimator가 있습니다.

그럼 이제 RANSAC에 대해서 알아보겠습니다!

RANSAC은 무작위로 샘플 데이터를 뽑은 다음 최대로 합의된 것을 선택한다는 의미입니다.

즉, 가장 많은 수의 데이터가 적합하다고 생각하는 모델을 선택하는 기법입니다.

여기서 RANSAC이 선택한 모델에서 많이 벗어나는 데이터들을 Outlier, 그렇지 않은 데이터를 Inlier라고 생각하면 됩니다.

제가 상상한 RANSAC과 최소자승법의 결과값입니다.

모델은 일차 직선으로 잡고 파라미터를 찾을 경우입니다. 데이터 중간에 아래로 치우친 Outlier들이 있습니다. 

따라서 최소자승법은 Outlier들이 영향으로 아래로 치우치게 되었습니다.

하지만 최소자승법은 Outlier들의 영향을 거의 받지 않는 이상적인 값을 찾게 됩니다. 

RANSAC의 절차는 다음과 같습니다.

1. 무작위로 샘플 데이터를 뽑아 모델 파라미터를 구합니다.

2. 모델과 가까이 있는 데이터의 수를 파악하고 이전 값보다 큰 값이면 기억합니다.

(이 과정은 임계값을 잡고 Residual가 그 값보다 작은 데이터의 수를 구하면 됩니다.)

3. 이 과정을 N번 반복해 최대값을 가진 파라미터를 찾습니다.

이 RANSAC은 카메라 모션 추적, 물체 찾기, 비디오 안정화 등 에서 사용됩니다.