RANSAC Algorithm

어떤 현상을 설명하는 이론 모델을 만들려면 현상에서 관측 데이터를 수집해야 한다. 그런데 관측 데이터에는 측정 오차에 의한 잡음뿐만 아니라, 모델의 가정을 크게 벗어나는 이상치(outlier)가 포함되는 경우가 많다. 특히 outlier는 모델 파라미터의 추정을 크게 왜곡하므로 일반적인 최소제곱법만으로는 신뢰할 수 있는 결과를 얻기 어렵다. 이런 상황에서 관측 데이터로부터 robust한 모델을 추정하기 위해 제안된 알고리즘이 RANSAC(Random Sample Consensus)이다. 이 알고리즘은 1981년 Fischler와 Bolles에 의해 제안되었다.

RANSAC의 입력은 관측된 데이터, 모델을 결정하는 데 필요한 최소 샘플 수, 모델의 형태, inlier를 판정하기 위한 거리 임계값, 그리고 원하는 성공 확률(또는 허용 실패 확률)이다.

RANSAC 알고리즘은 주어진 원본 데이터에서 일부를 임의로 선택하는 과정을 반복하여서 최적의 파라미터를 예측하는 프러시저의 형태를 가진다. 전체의 관측 데이터가 $M$개 있고, 모델 파라미터를 예측하는 데 $N$개의 데이터가 필요한 경우, 알고리즘의 동작은

     1. 임의로 관측 데이터에서 $N$개의 부분 데이터를 선택한다.
     2. 선택 데이터를 (가상의) inlier로 생각하고 모델을 예측한다.
     3. 원본 데이터($M$) 중에서 예측된 모델에 잘 맞는가를 체크한다. 잘 맞는 데이터 수를 $K$라고 한다.
     4. 현재까지 가장 많은 inlier를 갖는 모델이면 이를 최적 후보로 저장한다.

     5. 정해진 반복 횟수만큼 1~4를 반복한다.

     6. 최종적으로 가장 많은 inlier를 갖는 모델을 선택하고, 필요하면 이들 inlier만을 이용하여 모델을 다시 추정한다.

1. 모델이 유효하다고 판단하기 위한 최소 Inlier의 개수 K는 주어진 전체 데이터 중에서 어느 정도의 비율로 찾는 모델에 잘 맞는가로 판단하는 기준인데, 사용자가 결정해야 한다. 대략적으로 주어진 샘플에서 inlier의 비율을 $P_g$ 정도라고 생각되면 다음 정도로 잡으면 된다:

  $$K = M P_g$$
2. 얼마나 많은 반복을 해야하는가? 주어진 관측 데이터에서 inlier일 확률이 $P_g$인 경우에 $L$번의 모델 예측 시도가 실패할 확률을 계산하여서 이것이 주어진 설정값, $p_\text{fail}$ 보다도 작은 경우에 모델 예측의 실패로 처리하므로,
\begin{align}p_\text{fail} &= L\text{번의 모델 예측 실패 확률} \\  &= (\text{한 번 시도가 실패할 확률})^L \\ &= \left(1-\text{한 번 시도가 성공할 확률}\right)^L \\  &= \left( 1- P_g^N \right)^{L} \end{align}이 사실로부터 최대 반복 횟수는 
\begin{align} L = \frac{\log p_\text{fail} }{\log (1-P_g^N)}\end{align}로 주어진다.
전체 데이터의 절반이 inlier인 경우  $P_g$(=주어진 데이터중에서 inlier일 확률)=$0.5$, $p_\text{fail} = 0.01$인 경우, $N = 3$(세 점만 있으면 모델 구성이 가능한 원의 피팅이 한 예)이면 최대 반복 횟수는 윗 식에 적용하면,
$$L = 35\text{회}$$
RANSAC은 많은 outlier가 존재하는 경우에도 모델을 안정적으로 추정할 수 있는 매우 강건한 알고리즘이다. 그러나 반복 횟수는 inlier의 비율 $P_g$를 알아야 결정할 수 있으며, 실제로는 $P_g$를 미리 알 수 없는 경우가 대부분이다. 따라서 $P_g$는 경험적으로 추정하거나 반복 과정에서 갱신하며, 설정한 최대 반복 횟수 안에 최적의 모델을 찾지 못할 가능성도 존재한다.

 

RANSAC의 가장 큰 장점은 outlier의 비율이 매우 높더라도 안정적으로 모델을 추정할 수 있다는 점이다. 반면 반복적으로 랜덤 샘플링을 수행하므로 계산량이 비교적 크며, inlier 비율이 매우 낮으면 필요한 반복 횟수가 급격히 증가한다. 또한 항상 최적의 해를 보장하는 것은 아니며, 확률적으로 최적해를 찾는 알고리즘이라는 점도 한계이다.

 

예제 코드:
ransac을 이용한 라인 피팅: http://blog.naver.com/helloktk/80029006029
ransac을 이용한 원 피팅: http://kipl.tistory.com/32

RANSAC: Circle Fit

ransac을 이용한 타원 피팅: kipl.tistory.com/110

RANSAC Ellipse Fitting