RANSAC의 이해와 영상처리 활용

영상처리 2013.05.03 20:28

영상처리나 컴퓨터 비전을 하면서 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)시키면 오른쪽 그림과 같은 결과가 나온다. 참고로, 최소자승법이란 모델(여기서는 포물선)과의 ∑residual2을 최소화하도록 모델 파라미터를 정하는 방법을 말한다. 최소자승법에 대한 자세한 내용은 여기를 참조하기 바란다.


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


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


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


2. RANSAC의 이해


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


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


최소자승법(least square method)은 데이터들과의 ∑residual2을 최소화하도록 모델을 찾지만, 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) = ax2 + 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) = r2으로 정의되는 함수이다 (단, 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 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • 이전 댓글 더보기
  • Chanhee Jang 2014.09.26 17:49 신고 ADDR 수정/삭제 답글

    블로그에 댓글은 또 처음남기네요.

    얼마전 차선인지 시스템 공부를 시작했는데
    필터, Hough변환, Spline 등등 다른 것들은 이해가 갔는데
    RANSAC은 계속 물음표로 남아있다가 머리가 맑아진 느낌입니다.

    이래서 교수님이 자꾸 쉽다 쉽다 했구나 생각이 들정도로 쏙 들어오네요

    게다가 다른 모델과의 비교, 한계점/문제점 분석까지 정말 감사합니다 :)

    • BlogIcon 다크pgmr 2014.09.26 22:45 신고 수정/삭제

      네 알고나면 쉬운데 모르면 또 어려운게 RANSAC인것 같습니다 ^^

  • Chanhee Jang 2014.12.23 00:15 신고 ADDR 수정/삭제 답글

    안녕하세요:) 지난번에 와서 큰 공부를 하고 간 학생입니다.

    여기서 RANSAC에 대한 개념을 확실히 익힐 수 있었기에 얼마전 졸업작 발표도 무사히 마칠 수 있었습니다. 그래서 감사인사 겸 다시 들렸습니다 :)

    이번에 머신비전이라는 분야를 처음 알게되었는데 정말 흥미롭고 재미있네요. 대학원은 무조건 싫다고 외쳐오던 제가 대학원까지 생각해 볼 정도라니 말이죠.

    곡선 차선 인식 연구를 진행하였었구요, 부족하지만 다크프로그래머님께 배운 지식을 활용한 작품이라 공유하고 갑니다 ^^;
    http://youtu.be/VlH3OEhZnow

    앞으로 종종 공부하러 들리겠습니다. 감사합니다.

    • BlogIcon 다크pgmr 2014.12.23 08:58 신고 수정/삭제

      기분좋은 댓글입니다 ^^
      훌륭하네요. 제 차에도 하나 달아놓으면 좋겠습니다.

  • 영상처리 이슈가 생길 때마다 항상 찾게 되는 것 같습니다.
    좋은 글 감사합니다.
    단번에 이해가 됐어요 ~ 적용하는 것은 좀 더 알아봐야 겠지만요 ;;
    즐거운 크리스마스 보내세요~
    그리고 새해 복 많이 받으세요~~~~~~

    • BlogIcon 다크pgmr 2014.12.25 07:50 신고 수정/삭제

      감사합니다.
      이쁜꽃이피었으면님도 연말 잘 보내시고 새해 복 많이 받으시기 바랍니다^^

  • aaljo2 2015.01.05 09:11 신고 ADDR 수정/삭제 답글

    좋은 글 잘 읽었습니다. 내용이 쉽고 알차게 정리되어 있네요 감사합니다. 자주 들르겠습니다.

  • 무는네코 2015.01.12 16:20 신고 ADDR 수정/삭제 답글

    작성하신 글을 읽다보면 매번 감사한 마음뿐입니다.
    이해가 쉽도록 설명을 해주셔서 매번 문제가 있을때마다 크게 도움이 되고 있습니다.
    정말정말 감사드립니다:D

  • 핵Boom 2015.02.06 13:31 신고 ADDR 수정/삭제 답글

    궁금한게 있는데요...

    ransac에 LS를 적용을 해서 데이터를 근사와 하셨는데 ...(대수적 에러??)

    이 부분에 다른 기하학적인 에러 부분으로 접근을 해도 되는건가요??

    예를 들면 ransac + svd 또는 ransac + 가우스 뉴턴 , ransac + Levenberg–Marquardt

    이런식을 접근을 해서 근사화를 시켜도 무방한건가요??

    • BlogIcon 다크pgmr 2015.02.06 13:43 신고 수정/삭제

      가능하리라 생각합니다. 하지만 ransac으로 초기해를 찾은 후 inlier를 선별하여 ls를 적용하는 정도면 충분하다고 생각합니다.

  • qu 2015.03.14 13:24 신고 ADDR 수정/삭제 답글

    미국에서 공부하는 학생입니다 수업이 좀 어려워서 국문으로 자료를 찾아보는데 웬만한 교과서보다 잘 정리되어 있고 내용도 이해가 잘 되네요. 감사히 보고 갑니다. 종종 들르겠습니다.

    • BlogIcon 다크pgmr 2015.03.14 19:23 신고 수정/삭제

      네, 타지에서 공부하자면 고생이 많겠네요. 종종 들르세요.

  • BlogIcon jjunis 2015.03.18 11:08 신고 ADDR 수정/삭제 답글

    ransac은 outlier 제거 효과를 줄수 있다고하셨습니다. 그래서 활용예 a,b,c,d가 어떻게 적용될지 생각해보았습니다. a와c는 특징점에대해 ransac을하고 outlier 제거, b,d는 ransac을 통한 ransac에 최대 fitting 되는 곳으로 추적하는건가요?

    • BlogIcon 다크pgmr 2015.03.19 06:06 신고 수정/삭제

      ransac은 모델의 파라미터를 구하는 방법중 하나이고 ransac 자체는 동일하지만 문제에 따라 사용하는 모델은 달라질 수 있습니다.
      a,b,c,d 예 모두는 매칭되는 영상좌표들 사이에 어떤 공통 관계가 존재하는지를 ransac을 통해 구하는 예입니다. 이 때, 매핑(mapping) 관계를 호모그래피(homography)로 모델링할지, rigid 변환으로 할지 여부는 문제 특성에 따라 적절히 선택하시면 됩니다. ransac을 사용하지 않고도 이러한 매핑 관계를 구할 수는 있지만 ransac을 사용하면 설혹 잘못 매칭된 픽셀(특징점)들이 있더라도 올바른 매핑 관계를 찾아낼 수 있다는 장점이 있습니다.

  • dodo 2015.11.26 17:03 신고 ADDR 수정/삭제 답글

    안녕하세요 정말 ransac에 대해 이해하기 쉽게 풀어놔서 많은 도움이 되고 있습니다.
    사실 궁금증이 있는데요 저의는 거리측정 필터를 만들때 이 필터를 사용하려고 하는데 모델이 직선이라
    최소자승법으로 역행렬 해서 쓰는 방법을 못쓰겠는데 어떻게 해야하나요 ㅜ.ㅜ 모델이 y=k(상수)와 같은것은 어떻게 해야할지 감이 안잡힙니다 그냥 평균을 구해야하는거 아닌가요?? ㅜ.ㅜ 님이 알려주신 알고리즘을 실현하는데 조금 어려움이 있어서요 ㅜ.ㅜ(c_max, c부분!!)

    • BlogIcon 다크pgmr 2015.11.26 18:41 신고 수정/삭제

      구체적인 방법에 대해서는 도움을 드리기 힘듭니다. http://darkpgmr.tistory.com/56 글 내용을 참고해 보시기 바랍니다.

  • mandu 2016.04.03 19:24 신고 ADDR 수정/삭제 답글

    안녕하세요 정말 유익하고 좋은 글 보았습니다~
    다름이 아니라 RANSAC이나 MLESAC를 측정된 데이터에 대해서 사용하기 위해서는
    원하는 모델의 식을 알고 있어야만 적용을 할 수 있는 것인가요?
    예를 들면 어떤 센서에 의해서 측정된 데이터에 가끔씩 튀는 현상이 발생할때
    그것을 제거하는 과정에서도 쓰일 수 있는 것인가요?
    감사합니다 :)

    • BlogIcon 다크pgmr 2016.04.03 20:44 신고 수정/삭제

      네, 당연히 뭐든지 모델은 있어야 합니다. 하지만 센서에서 값이 튀는 것은 딱히 모델이 없으니 유효범위 체크나 근처의 이웃한 값들과 비교하는게 좋지 않을까요.

  • 안녕하세요 2016.05.13 14:35 신고 ADDR 수정/삭제 답글

    안녕하세요. 질문드리고싶습니다!
    2차원 상에서 한쪽에는 a개의 점, 다른쪽에는 b개의 점이 있습니다 (a<= b)
    이 때 a의 점들을 회전, 평행이동, 스케일 해서 b의 점중에 일부와 정확하게 일치하도록 하는 변환행렬을 계산하고자 합니다. 이런 경우에 RANSAC을 활용하는게 의미가 있을까요?
    b에는 a와 대응하는 점이 모두 있을수도 있지만, 일부만 대응할 수도 있습니다.

    간단하게 요약하자면 P(b,a)의 점간의 대응관계 가능성 중에서 가장 오차가 작은(대응점들간 거리) a-b점들의 대응관계를 찾는 것이 목표입니다. 대응관계만 알게 되면 변환관계는 찾는게 어려워 보이지는 않아보이네요.

    이때 T는 랜덤하게 선택된 대응점들을 이용해서 a의 모든 점을 b쪽으로 변환하였을 때 대응점들간의 거리합정도로 생각해 볼 수 있을 것 같습니다.

    • BlogIcon 다크pgmr 2016.05.13 18:05 신고 수정/삭제

      ransac 보다는 iterative search를 통한 최적화 문제로 접근해야 할 것 같습니다. https://en.wikipedia.org/wiki/Point_set_registration 글의 내용을 참고하시기 바랍니다.

  • 영상처리초짜 2016.06.04 22:28 신고 ADDR 수정/삭제 답글

    안녕하세요 다크프로그래머님. 영상처리에 입문한지 1년갓된 영상처리초짜입니다.
    다름이아니오라, ransac을 공부하며 느낀게 ransac을 이용해서 인라이어 아웃라이어를 정하는걸로 아는데, ransac을 쓰는 장점을 모르겠네요, 지금까지 이해한것을 바탕으로 드는 생각은 랜덤으로 최소한의 점만을 뽑아서 반복하기 때문에 좀더 빠를것이다. 그러나 random적인 것때문에 정확도가 떨어질수 있을것 같은데요.
    정확도적인 측면만 본다면 모든변수에 대하여 in,out을 계산하는것이 더 좋은 방법이 아닐지 의문이 생겨 이렇게 남깁니다.
    다크프로그래머님은 어떻게 생각하시나요?

    • BlogIcon 다크pgmr 2016.06.07 17:05 신고 수정/삭제

      안녕하세요. ransac을 쓰는 이유는 속도와는 큰 관계가 없습니다. 오히려 ransac을 쓰면 일반적인 최소자승법(least squares)을 사용하는 것보다 속도가 훨씬 느립니다. ransac을 사용하는 이유는 데이터에 outlier가 많은 경우(50% 이상)에도 outlier의 영향을 (거의) 받지 않고 inlier의 분포를 근사할 수 있다는 장점 때문입니다. 그리고 모든 경우에 대해 in, out을 일일히 계산하는 것은 물론 가장 결과가 좋겠지만 그렇게 하면 시간이 너무 오래 걸리기 때문에 현실적으로 사용하기는 힘듭니다.

  • 김윤섭 2016.07.07 20:57 신고 ADDR 수정/삭제 답글

    안녕하십니까 다크프로그래머님 석사생활 내내 블로그의 도움을 정말 많이 받은 (이제는 직장인)입니다. 석사시절 레이저스캐너나 센서류를 많이 다루었었는데 영상처리는 OpenCV를 많이 사용한다고 익히 알고있습니다만 매트랩을 이용해서도 많이 하나요? 주로 이용하는건 NI의 Labview인데 랩뷰는 아무래도 유료이고 오픈소스가 많이 없다보니 힘드네요 경험자가 아니라서 한번 여쭤보고싶습니다. 매트랩과 영상처리에 대해서요 ^^ 감사합니다

    • BlogIcon 다크pgmr 2016.07.07 23:08 신고 수정/삭제

      저는 매트랩을 거의 계산기로밖에 안써서 뭐라 드릴 말씀이 없네요.. ㅎㅎ;; 하지만 매트랩을 이용해도 무방하다고 생각합니다. 빠른 프로토타이핑이 가능한 장점에 image processing toolbox, computer vision toolbox도 있고 또 필요하다면 c와 연동도 가능하니 특별히 매트랩이 문제될 건 없다고 생각합니다.

  • 질문이요! 2016.07.18 15:55 신고 ADDR 수정/삭제 답글

    이런걸 RANSAC으로 구현하는데 장점이 있을까요?

    임의의 n개의 model/reference 선분(혹은 점들)들을 임의의 m개의 data선분(혹은 점)들에서 찾고자 합니다. data선분은 model선분중에 일부를 rotation/translation/scale시킨 것입니다

    아주 이상적인 경우라면 4개의 점을 n개에서 선택하고, 대응하는 4개의 점을 m에서 찾아
    homography를 찾으면 r,t,s를 모두 찾을 수 있게 되지만

    보통은 그렇지 않기 때문에 RANSAC을 이용하여 랜덤하게 점 대응관계를 설정하여 homography를 계산하고 오차를 설정하여 가장 잘 맞는것을 찾아보려고 하는데, 장점이 있으려나요..?

    하고자 하는 예제에서 대략적으로 n=20, m=150이고 20개의 n이 모두 대응되면 좋겠지만 평범하게 10개정도가 대응할거라고 생각은 하고 있습니다.

    • BlogIcon 다크pgmr 2016.07.19 07:05 신고 수정/삭제

      point set registration 문제로 보입니다. https://en.wikipedia.org/wiki/Point_set_registration 글을 보시면 도움이 될지 모르겠습니다..

  • meniaa 2016.08.03 15:09 신고 ADDR 수정/삭제 답글

    머신비전 종사자로써 매번 새로운 글이 올라올 때마다 감탄을 하게 됩니다.
    10톤 압착기로 알찬 정보만 꾹꾹 눌러담은것 같습니다.
    매번 감사합니다. 다크pgmr님. ^^

  • 질문입니다!!! 2016.10.25 11:27 신고 ADDR 수정/삭제 답글

    좋은 글 감사합니다.
    질문이 있어서 글을 남깁니다.
    LRF를 이용하여 경사로를 따라서 모바일 로봇을 주행시키며 데이터를 받은 후, RANSAC 알고리즘을 이용해서 후처리를 하면 하나의 벽면으로 깨끗하게 나올까요?
    이렇게 3차원 공간에서 RANSAC 알고리즘을 적용시킬 수 있는지 궁금합니다.
    감사합니다.

  • 질문해도 될까요? 2017.03.21 13:26 신고 ADDR 수정/삭제 답글

    질문 전에 이 글을 읽고 란삭 알고리즘에 대해서 많이 이해하게 되서 감사합니다!
    이 글에 대해서 만드신 opencv 소스를 봤는데요, 한 가지 아리송한 부분이 있어서요.
    x[i] = i;
    y[i] = iA*(x[i] * x[i]) + iB*x[i] + iC;
    이 부분은 데이터 분포도를 위해 만드신 임의의 함수가 맞는거죠...?
    오래된 글이라 기억이 안 나실까봐 소스코드를 올리신 웹사이트도 참고하겠습니다.
    https://github.com/ddorobot/ransac/blob/master/README.md
    그리고 마지막 질문이 있습니다. THRESHOLD를 한 이미지의 여러개의 선분의 경향성을 추적하려고 하는데 주어진 소스를 활용해서 선분들의 경향성을 추적할 수 있을까요?

    • BlogIcon 다크pgmr 2017.03.21 13:51 신고 수정/삭제

      코드는 제가 작성한 것이 아니니 작성자 분께 여쭤보시면 좋을 것 같습니다. ^^

  • 질문해도 될까요? 2017.03.22 00:15 신고 ADDR 수정/삭제 답글

    아 네 감사합니다!!
    그럼 다른 질문으로 넘어가서 코드를 작성할 때요, 위와 같이 포물선인것을 알고 있으면 좋지만 모를경우엔 어떻게 하는 것이 좋나요? 라인 트레킹을 하는 중인데 허프로 하니 곡선을 잡기 힘들어서 란삭을 하려는데 커브를 잡는 부분이 감이 안오네요...

    • BlogIcon 다크pgmr 2017.03.22 08:54 신고 수정/삭제

      차선검출은 워낙 연구가 많이 된 분야이니 조금 검색해 보시면 유사한 문제에 대한 논문들이 많이 있을 것으로 생각됩니다.

  • 메트릭스 2017.07.28 10:46 신고 ADDR 수정/삭제 답글

    신호처리에 잘 써먹을수 있겠네요,..
    혹시 sinusoidal (sin 또는 cos특성) 형태에 적용해보고자 하는데,.. 테일러 함수를 적용한
    모델링도 가능 할까요 ?... 고맙습니다.

  • velvet 2017.08.12 03:58 신고 ADDR 수정/삭제 답글

    안녕하세요. 어쩌다 보니 작년 말부터 연구실에서 의료영상처리 프로그램 개발을 진행하고 있는 학부생입니다. 감사의 인사를 전하고 싶어 덧글 남깁니다. 저는 학부생이다 보니 영상처리 알고리즘에 대한 이해가 부족하여 이 블로그에서 여러가지 정보들을 얻어왔습니다. 그래서 지금은 openCV + openGL + MFC까지 짬뽕(?)된 프로그램까지 만들게 되었습니다. 특히 이 RANSAC 게시글을 보면서 몇 달간 고민했던 outlier가 심한 곡선 보정에 관해 많은 도움을 받았습니다. ^^ 무더운 여름 몸 조심하시고, 앞으로도 종종 들러서 학습하는데 도움을 얻고 가겠습니다.



티스토리 툴바