RANSAC의 이해와 영상처리 활용

영상처리나 컴퓨터 비전을 하면서 RANSAC을 모르면 간첩일 정도로 RANSAC은 너무나 유명한, 그리고 널리 사용되는 방법이다.

RANSAC이 유명한 만큼 이미 인터넷에 관련된 글들이 꽤 있다. 그럼에도 또 이렇게 RANSAC에 대한 글을 쓰는 건 무언가 다른 플러스 알파(?)가 있기 때문일 것이다. 그 플러스 알파가 무엇인지는 이어지는 글을 살펴보도록 하자 ^^

RANSAC 자체는 특정 분야에 국한되지 않는 일반적인 방법론이다. 하지만 본 블로그가 주로 영상처리에 관련된 주제를 다루기 때문에 영상처리 관점에서 이야기를 풀어가고자 한다.

1. RANSAC의 필요성

2. RANSAC의 이해

3. Inlier와 Outlier

4. RANSAC 알고리즘

5. RANSAC의 활용예

6. RANSAC 알고리즘의 파라미터

7. RANSAC과 robust 파라미터 추정

8. RANSAC에 대한 생각 

1. RANSAC의 필요성

RANSAC의 개념을 설명하기 전에 RANSAC이 왜 필요한지 살펴보겠다. 아래 왼쪽 그림과 같이 관측된 데이터들이 있다고 하자. 이 데이터들을 최소자승법을 이용하여 포물선으로 근사(fitting)시키면 오른쪽 그림과 같은 결과가 나온다. 참고로, 최소자승법이란 모델(여기서는 포물선)과의 ∑residual²을 최소화하도록 모델 파라미터를 정하는 방법을 말한다. 최소자승법에 대한 자세한 내용은 여기를 참조하기 바란다.

그런데, 실제 관측 데이터가 위와 같이 깨끗하게 나오는 경우는 현실 세계에서는 별로 없다. 측정오차나 노이즈(noise) 등으로 인해 아래 왼쪽 그림 같은 경우가 일반적일 것이다. 이때도 최소자승법을 적용하면 오른쪽 그림과 같이 훌륭한 결과를 얻을 수 있다.

그런데, 만일 아래 왼쪽 그림과 같이 약간의 노이즈 정도가 아니라 데이터 자체가 완전히 틀어져 버린 경우는 어떻게 될까? 이렇게 정상적인 분포에서 벗어난, 이상한 데이터들을 이상점(outlier)라고 부르는데, 데이터에 outlier(아웃라이어)가 끼어 있으면 최소자승법은 오른쪽 그림처럼 엉망이 되어 버린다.

그런데, 이것을 RANSAC을 이용해 근사시키면 아래 그림과 같이 깨끗한 결과를 얻을 수 있다.

2. RANSAC의 이해

RANSAC이 왜 필요한지, 그리고 어디에 쓰는 놈인지는 대략 감을 잡았을 것으로 생각한다. 그러면 이제 RANSAC이 무엇인지 좀더 구체적으로 살펴보자.

일단, RANSAC은 영어로 RANdom SAmple Consensus의 대문자들을 딴 약자이다. 글자 그대로 해석해 보면 무작위로 샘플 데이터들을 뽑은 다음에 최대로 컨센서스가 형성된 녀석을 선택한다는 의미이다. 

최소자승법(least square method)은 데이터들과의 ∑residual²을 최소화하도록 모델을 찾지만, RANSAC은 컨센서스가 최대인, 즉 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법이다.

위 포물선 예제에서 최소자승법이 선택한 모델과 RANSAC이 선택한 모델을 비교해 보면 어떤 경우가 좀더 많은 데이터틀로부터 지지를 받는지, 즉 근사된 모델(포물선) 근방에 있는 데이터들이 어느 쪽이 많은지 확인해 보면 된다.

결국, RANSAC과 최소자승법의 차이는 무엇을 기준으로 모델의 파라미터를 찾는가의 차이이다. 이 시점에서 한 가지 짚고 넘어가자. 그건, RANSAC의 기준을 사용하면 관측 데이터에 이상한 애들(outlier)이 많더라도 데이터 근사가 가능하다는 점이다. 그렇지! 하고 고개가 끄떡여지지 않는다면 음... 처음부터 다시 한번 읽어 주시기 바란다..

3. Inlier와 Outlier

RANSAC 알고리즘을 설명하기 전에, 먼저 inlier와 outlier 개념을 정확히 잡고 넘어갔으면 한다. RANSAC과 관련된 여러 미묘한 문제들은 결국 inlier와 outlier의 구분 문제이기 때문이다.

Wikipedia에 보면 Outlier(이상점)는 데이터의 분포에서 현저하게 벗어나 있는 관측값으로 정의되어 있다. 현실 세계에서 관측된 데이터들이 완벽한 경우는 거의 없으며 약간씩의 오차, 편차, 노이즈 등이 있는 경우가 대부분이다. 그렇다면, 오차(에러)가 크면 outlier, 그렇지 않으면 inlier, 이렇게 구분하는 것일까? 대답은 NO! 아니라고 생각한다. 단지 편의상, 또는 별다른 방법이 없기 때문에 그렇게 할 뿐이다.

예를 들어, 일개미들의 특성을 파악하고 싶어서 실험을 했는데 거기에 병정개미의 데이터가 끼어들었다고 하자. 그렇다면 일개미의 데이터는 inlier이고 병정개미의 데이터는 outlier이다. 그런데 일개미의 데이터라 할지라도 조금씩 차이가 있기 때문에 어떤 놈은 편차가 클 것이고 어떤 놈은 편차가 작을 것이다. 그렇더라도 이들은 모두 inlier들이다. 한편, 병정개미 데이터의 경우 어떤 놈은 일개미들과 매우 유사한 값을 가질 수 있다. 하지만 아무리 유사하더라고 그건 여전히 outlier이다.

4. RANSAC 알고리즘

RANSAC 알고리즘은 위에서 설명한 컨센서스가 최대인 모델을 뽑기 위한 절차적 방법을 말한다.

그 방법은 일단 무작위로 샘플 데이터 몇 개를 뽑아서 이 샘플 데이터들을 만족하는 모델 파라미터를 구한다. 이렇게 구한 모델과 가까이에 있는 데이터들의 개수를 세어서 그 개수가 크다면 이 모델을 기억해 둔다. 이러한 과정을 N번 반복한 후 가장 지지하는 데이터의 개수가 많았던 모델을 최종 결과로 반환한다.

이제 위에서 예로 든 포물선 근사 문제를 RANSAC으로 풀어보도록 하자.

관측된 데이터 값들은 (x1, y1), ..., (xn, yn), 포물선의 방정식은 f(x) = ax² + bx + c, 포물선을 결정하기 위해 뽑아야 할 샘플의 개수는 최소 3개이다.

1. c_max = 0 으로 초기화한다.
2. 무작위로 세 점 p1, p2, p3를 뽑는다.
3. 세 점을 지나는 포물선 f(x)를 구한다.
4. 이렇게 구한 f(x)와의 거리 ri = |yi-f(xi)|가 T 이하인 데이터의 개수 c을 구한다.
5. 만일 c가 c_max보다 크다면 현재 f(x)를 저장한다 (과거에 저장된 값은 버린다)
6. 2~5 과정을 N번 반복한 후 최종 저장되어 있는 f(x)를 반환한다.
7. (선택사항) 최종 f(x)를 지지하는 데이터들에 대해 최소자승법을 적용하여 결과를 refine한다.

실제 문제에 따라서, 수식 등은 조금씩 바뀔 수 있지만 기본적인 RANSAC 알고리즘의 구조는 위와 동일하다. 참고로, 위 포물선 예제에 대한 RANSAC matlab 코드는 다음과 같다.

% input data

noise_sigma = 100;

x = [1:100]';

y = -2*(x-40).^2+30;

oy = 500*abs(x-60)-5000;

y([50:70]) = y([50:70]) + oy([50:70]);

y = y + noise_sigma*randn(length(x),1);

% build matrix

A = [x.^2 x ones(length(x),1)];

B = y;

% RANSAC fitting

n_data = length(x);

N = 100;        % iterations

T = 3*noise_sigma;   % residual threshold

n_sample = 3;

max_cnt = 0;

best_model = [0;0;0];

for itr=1:N,

    % random sampling

    k = floor(n_data*rand(n_sample,1))+1;

   % model estimation

    AA = [x(k).^2 x(k) ones(length(k),1)];

    BB = y(k);

    X = pinv(AA)*BB;  % AA*X = BB

   % evaluation

    residual = abs(B-A*X);

    cnt = length(find(residual<T));

    if(cnt>max_cnt),

        best_model = X;

        max_cnt = cnt;

    end;

end;

% optional LS(Least Square) fitting

residual = abs(A*best_model - B);

in_k = find(residual<T);    % inlier k

A2 = [x(in_k).^2 x(in_k) ones(length(in_k),1)];

B2 = y(in_k);

X = pinv(A2)*B2;    % refined model

% drawing

F = A*X;

figure; plot(x,y,'*b',x,F,'r');    

5. RANSAC의 활용예

A. local feature matching을 이용하여 영상에서 특정 물체를 찾을 때

B.Visual Odometry (인접한 영상프레임에서 카메라 모션을 추정할 때)

C. 위치인식을 위해 scene matching을 수행할 때

D. 물체 추적을 위해 인접한 영상프레임에서 이동체의 모션을 추정할 때

6. RANSAC 알고리즘의 파라미터

RANSAC 알고리즘을 돌리기 위해서는 크게 2가지의 파라미터를 결정해야 한다. 샘플링 과정을 몇 번 (N) 반복할 것인지, 그리고 inlier와 outlier의 경계를 (T) 어떻게 정할 것인지이다.

RANSAC이 성공하기 위해서는 N번의 시도 중 적어도 한번은 inlier들에서만 샘플 데이터가 뽑혀야 한다. 이러한 확률은 N을 키우면 키울수록 증가할 것이지만 무한정 RANSAC을 돌릴 수는 없기 때문에 보통은 확률적으로 반복 횟수를 결정한다. RANSAC 반복회수를 N, 한번에 뽑는 샘플 개수를 m, 입력 데이터들 중에서 inlier의 비율을 α라 하면 N번 중 적어도 한번은 inlier에서만 샘플이 뽑힐 확률 p는 다음과 같다.

 --- (1)

예를 들어, 위 포물선 근사 예에서 inlier 비율이 80%라고 했을 때, RANSAC 성공확률을 99.9%로 맞추려면 필요한 반복횟수는 다음과 같이 계산된다.

 --- (2)

수학적 확률이긴 하지만 RANSAC을 10번만 돌려도 99.9% 확률로 해를 찾을 수 있다는 얘기이다. 생각보다 숫자가 작아서 p를 99.99%로 놓고 계산해 봐도 N = 12.8378이 나온다.

이 시점에서 RANSAC의 첫 번째 파라미터 N과 관련된 몇 가지 생각할 질문을 던져본다.

1. 실제로 위 matlab 예제 코드를 돌려보면 N = 100으로 놓고 돌려도 가끔 엉뚱한 해를 찾는다. 수학적 확률은 거의 100%일텐데.. 왜일까?
2. 포물선을 결정하기 위해서는 최소 3개의 점이 필요하다. 하지만 굳이 샘플의 개수를 m = 3으로 맞출 필요가 있을까? 예를 들어, 매 반복에서 샘플을 4개씩 뽑아서 최소자승법으로 포물선을 구할 수도 있을 것이다. 그렇다면 한번에 샘플의 개수를 많이 뽑는게 좋은가 아니면 최소한으로 뽑는게 좋은 것인가? 또한 샘플의 개수에 따라 필요한 반복횟수 N은 어떻게 되는가?
3. RANSAC 반복횟수를 확률적으로 결정하기 위해서는 inlier 비율을 알고 있어야 한다. 그런데, inlier 비율을 모르고 있거나 혹은 입력 데이터마다 inlier 비율이 변할 수 있다면 어떻게 해야 하는가?

RANSAC의 반복회수 N에 대한 내용은 이정도로 하고, 두번째 파라미터인 T에 대해 살펴보자. 사실 N보다는 T가 RANSAC에서 훨씬 중요하고 어려운 파라미터이다.

RANSAC은 지지하는 데이터 개수가 가장 많은 모델을 뽑는 파라미터 추정 방법이다. 지지하는 데이터는 추정된 모델과 가까이 있는 데이터들을 말한다. 그렇다면 얼마나 가까워야 그 모델을 따르는 데이터라고 간주하는 것일까?

RANSAC 알고리즘에서는 데이터 (xi, yi)와 모델 f와의 거리 ri = |yi - f(xi)|가 T 이하이면 그 모델을 지지하는 데이터로 간주한다. 그런데 이 파라미터 T를 우리가 결정해줘야 한다는게 문제이다. 만일 T를 너무 크게하면 모델간의 변별력이 없어지고 T를 너무 작게하면 RANSAC 알고리즘이 불안정해진다.

T를 선택하는 가장 좋은(일반적인) 방법은  inlier들의 residual 분산을 σ2이라 할때, T = 2σ 또는 T = 3σ 정도로 잡는 것이다. 즉, 먼저 RANSAC을 적용하고자 하는 실제 문제에 대해서 inlier들로만 구성된 실험 데이터들을 획득하고, inlier 데이터들에 대해서 최소자승법을 적용하여 가장 잘 근사되는 모델을 구한다. 이렇게 구한 모델과 inlier들과의 residual (ri = yi-f(xi))들을 구한 후, 이들의 분산(또는 표준편차)을 구해서, 이에 비례하게 T를 결정한다. inlier들의 residual이 정규분포를 따른다고 가정했을 때, T = 2σ로 잡으면 97.7%, T = 3σ로 잡으면 99.9%의 inlier들을 포함하게 된다.

T를 정하는데 있어서 정말 어려운 문제는 inlier들의 분산이 동적으로 변하는 경우이다. 이러한 경우에는 T를 데이터마다 유동적으로 결정해주어야 하는데 RANSAC에서는 이러한 문제를 adaptive threshold 또는 adaptive scale 문제라고 부르며, RANSAC에서 주요 연구 이슈중의 하나이다. 참고로, RANSAC에서 adaptive란 용어를 사용하는 경우는 2가지인데, 하나는 N을 adaptive하게 하는 것이고 다른 하나는 T를 adaptive하게 하는 것이다.

7. RANSAC과 robust 파라미터 추정

사실 RANSAC은 robust parameter estimation 방법들 중 하나이다. 어떤 방법 또는 알고리즘이 데이터 중에 outlier가 있어도 처리가 가능하면 이를 robust하다 라고 한다.

Robust한 파라미터 추정(estimation) 방법으로는 RANSAC 외에도, M-estimator, LMedS 등이 있다. 이러한 robust 파라미터 추정 방법들은 Loss 함수에 따라 구분지을 수 있는데, 일단 아래 그림을 살펴보자.

그림출처: Sunglok Choi, "Performance Evaluation of RANSAC Family", BMVC 2009.

우리가 흔히 알고 있는 최소자승법 (Least Square Method)는 그림의 보라색 점선과 같이 Loss 함수가 ρ(r) = r²으로 정의되는 함수이다 (단, ri = yi - f(xi)는 데이터 (xi, yi)의 residual). 반면, RANSAC은 Loss 함수가 위 그림의 초록색 선처럼 residual이 T보다 작으면 0, T보다 크면 1로 정의된다. 즉, RANSAC에서는 residual이 T보다 작으면 에러가 없는 것으로 간주하고, T보다 큰 경우에는 그 크기에 관계없이 모두 1로 간주하는 것이다.

RANSAC을 좀더 개선한 방법으로 MLESAC(Maximum Likelhood SAC)이라는 것이 있다. RANSAC은 T 이내에만 들어오면 에러가 없는 것으로 치기 때문에 Gaussian이나 정규분포처럼 T 내에서도 모델에 가까울수록 데이터들이 좀더 밀집되는 형태는 잘 반영하지 못한다. 하지만, MLESAC에서는 위 붉은색 선처럼 데이터가 모델에 가까울수록 에러를 적게 줌으로써, 데이터들이 가장 밀집된 곳을 찾을 수 있도록 해 준다.

LMedS(Least Median of Squares)는 RANSAC 계열과는 조금 다른 방법으로 robust하게 모델을 추정하는 방법이다. LMedS에서는 residual들의 median (residual들을 순서대로 정렬했을 때 순서상 가운데에 있는 값)이 최소화되는 모델을 찾는다. 단, LMedS는 outlier 비율이 50% 이하일 경우에만 적용할 수 있는 방법이다.

8. RANSAC에 대한 생각 

RANSAC은 데이터에 포함된 outlier 비율에 관계없이 적용할 수 있는 매우 강력하면서도 효과적인 파라미터 추정 방법이지만 random성으로 인한 몇몇 문제점을 가진다.

1. 동일한 입력 데이터에 대해서도 RANSAC 결과가 매번 달라질 수 있다.
2. 아무리 N을 늘려도 해를 못찻을 수 있다. 수학적 확률은 수학적 확률일 뿐이다.
3. outlier들이 random하게 분포되어 있지 않고 structure를 갖는다면 outlier들의 분포를 근사해 버릴 수도 있다.
4. 몇개 샘플만으로 모델을 구하는 방식은 문제에 따라 위험할 수도 있다. 위 포물선 예에서 점 3개를 뽑으면 포물선이 결정된다. 하지만 3 점이 모두 inlier라 할지라도 점 자체에 약간씩의 오차가 포함되어 있기 때문에 결과적으로 여기서 계산된 포물선도 오차를 갖게 된다. 그런데, 이 점들이 서로 인접해 있다면 이 오차가 매우 커질수 있다. 포물선의 한쪽 면에서 뽑힌 인접한 점 3개만 보고 포물선이 어디에서 꺾일지 알 수 있는지 생각해 보기 바란다.

RANSAC을 사용하면서 RANSAC의 장점 뿐만 아니라 이와 같은 한계도 같이 고려하면서 사용한다면 RANSAC을 좀더 잘 사용할 수 있을 것이다.

☞ 이상으로 RANSAC에 대한 정리를 마칩니다. 글 첫머리에 말씀드린 플러스 알파는 글을 충실하게 써 보자는 나름의 다짐, 또는 낚시성(?) 멘트 정도로 해석해 주시면 감사하겠습니다 ^^

by 다크 프로그래머