본문 바로가기
[Public] 신호처리/영상 객체검출

[Corner Detection] #3 RANSAC(RANdom Sample Consensus)

by 차출발 2012. 6. 24.
반응형

SIFT, SURF알고리즘을 이용하고

가장 마지막 단계에서 RANSAC을 이용하는 것을 볼 수 있다.

이 놈RANSAC(RANdom SAmple Consensus) 에 대해서 알아보자

 

 

RANSAC의 뜻은?

RANdom Sample Consensus의 약자를 따서 만든 알고리즘이다.

FischlerBolles에 의해서 제안된 RANSAC은 1981년 논문

"Random Sample Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography"

<Martin A. Fischler and Robert C. Bolles, Communications of the ACM, Volume 24 Number 6, June 1981.>

발표되었습니다.

이 논문을 한번 읽어보시길 바라며 내용은 다음과 같습니다.

측정 노이즈(Noise)가 심한 원본 데이터로부터 모델 파라메타(Parameta)를 예측하는 방법을 제안하고 있다.

 

 

 

RANSAC에 대해서 자세히 알고 싶어요!!

전체적인 내용은 다음과 같다.

측정된 원본 데이터 중에는 당연히 노이즈(Noise)

거짓정보(Outlier)가 포함되어 있다.

이러한 Outlier를 제거할 수 있어야 한다.

그래서 데이터 셋(Data Set)으로 부터 수학적 모델을 찾아야 한다.

이러한 모델을 결정을 하려면 우리는 일반적

초기의 해를 획득하기 위하여 많은 데이터를 사용하고

그 결과를 찾고 유효하지 않는 데이터를 제거하는 게 일반적이다.

데이터가 많을수록 좀더 정확해 지지 않겠는가?

하지만

RANSAC은 모델을 결정하는데

초기 데이터를 최소로 이용을 한다.

그리고 일관된 데이터의 집합(consensus Set)을 확장시켜 나아가면서

반복적인 작업을 통하여 해를 예측하며 해를 찾는 방법이다.

그래서

이는 일정 확률로 합리적인 결과를 도출해내기 때문에

비 결정알고리즘(Non-Deterministic Algorithm)이고 해당하고

확률은 반복이 더 많이 될수록 정확해진다.

 

 

 

그럼 전제 조건은 없나요?

  1. 데이터 셋은 참인 정보(Inlier)를 포함하고 있다고 가정한다.

     

  2. 데이터 셋이 수학적 모델 인자들로 표현이 가능하다고 가정한다.

     

  3. 해당 모델에 맞지 않는 거짓 정보(Outlier)가 존재한다.

     

  4. Inlier데이터가 Outlier로 잘못된 판명 날 수도 있다.

(극 값이나, 데이터의 잘못된 측정, 혹은 데이터의 해석에 대한 잘못된 가정으로 인하여)

 

  1. 주어진 Inlier 셋에서 최적이거나 데이터에 딱 맞는 모델의 인자들을 예측하는 알고리즘이 존재한다는 것을 가정한다.

     

 

 

도통 무슨 말인지 예를 들어서 설명해 주삼!!!

예를 들어보면 아래 그림은

왼쪽 데이터 셋에서 직선을 검출한 것이다.

 

이 데이터 셋은

inlier(직선에 딱 맞는 관찰 결과 셋)        (1번 전제조건)

Outlier(해당 직선에 맞지 않는 데이터)    (3번 전제 조건)

나누어 지는데

LSM(Least Square Method)를 이용하여 직선을 예측할 수 있다.            (2번 전제조건)

해당 직선이 Outlier를 포함한 모든 점에 대해서 최적으로 맞기 때문이다.        

RANSAC은 또한 데이터 셋에서 선택된 Inlier들이 충분히 많을 경우 Inlier로부터만 계산 가능한 모델을 생성할 수 있다.    (5번 전제조건)

그러나 이러한 경우는 장담할 수 없으며 인자들을 예측확률을 충분히 높게 유지하도록 신중히 선택해야만 하는 많은 알고리즘이 있다.    

(4번 전제조건은 당연한 것이기 때문에 pass)

 

 

 

아하 그렇다면 어떻게 구현한답니까?

추정(Hypothesis)

  1. 원본 데이터에서 임의로 N개의 샘플 데이터를 선택한다.
  2. 이 데이터를 정상적인 데이터로 보고 모델 파라미터를 예측한다.

검사(Verification)

  1. 원본데이터가 예측된 모델에 잘 맞는지 검사한다.
  2. 만일 원본데이터가 유효한 데이터인 경우 유효한 데이터 집합에 더한다.
  3. 만일 예측된 모델이 잘 맞는다면, 유효한 데이터 집합으로부터 새로운 모델을 구한다.

     

위의 추정과 검사 단계를

여러 번 거쳐서 반복 수행을 통하여 구하게 됩니다.

 

 

 

어랏! 반복 수행이면 언제 끝이 나는 건가요?

당연히 이 반복횟수에 따라 결과가 다르게 나타날 수 있다.

그래서 반복횟수 N을 설정을 해야 하는데

반복횟수 N은 확률 P를 보장할 수 있도록 충분히 높게 설정 되야 한다. (일반 적으로 P는 0.99로 설정)

 

 

 

먼저 확률 P가 먼데여?

확률 p는 최소한 하나의 샘플 집합이 유효한 데이터(Inlier) 만을 포함할 확률이다.

그럼 유효한 데이터(Inlier)의 확률을 u 라고 하면

유효하지 않는 데이터(Outlier)의 확률 은 v 라고 하자

당연히 확률이기 때문에 v = 1 – u로 표현이 가능하다.

그리고

샘플데이터 수를 m 이라고 설정하고

우리가 찾으려는 샘플데이터에 대한 반복횟수에 대한 반복 횟수를 N이라고 설정하고

N만 구하면된다.

 

 

 

그럼 N은 어떻게 구하나요 ?

먼저 전체 샘플 데이터 수에 대해서 샘플데이터가 모두 유효한 데이터인 경우Inliers 인 경우의 확률을 구한다.

아래의 그림과 같이 유효한 데이터(Inlier) 확률 u 그런데 임의의 점 m개의 데이터이기 때문에     

전체가 유효해야 하기 때문에 곱의 규칙에 따라

여기서 여집합을 생각을 하면1 -

적어도 하나 이상의 Outlier를 포함하는 확률이 되는 것이다.

하지만 여기서 N번 수행을 해서 실패의 결과를 얻어야 기 때문에

위 그림에 따라서 인 적어도 하나 이상 Outlier를 포함하는 확률을 얻을 수 있다.

다시 이전으로 돌아가

이전에 확률 p는

최소한 하나의 샘플 집합이 유효한 데이터(Inlier) 만을 포함할 확률이다.

그럼 당연히 1 – p 는

하나의 샘플집합이 유효하지 않는 데이터(Outlier)를 적어도 하나 이상 포함하는 확률이기 때문에

이를 같다고 높으면

얻을 수 있는 것이다. 이를 N에 대해서 다시 정리를 하면

수행횟수 N을 구할 수가 있다.

 

 

쉽게 도출 결과를 다시 보면

        = 전체 샘플 데이터 수에 대해서 샘플 데이터가 모두 유효한 데이터인 경우Inliers 인 경우의 확률이다. (곱의 법칙)

1 -         = 적어도 하나 이상의 Outlier를 포함하는 확률이다. (여집합)

    = N번 수행 후 실패 결과 (곱의 법칙)

1- p        = 하나의 샘플집합이 유효하지 않는 데이터(Outlier)를 적어도 하나 이상 포함하는 확률이기 때문에 (여집합)

 

그래서 결론은

N에대해서 정리하면

 

 

그럼 꼭 N번을 수행해야 하는 건가요?

아니다 그래서 RANSAC알고리즘을 변형시킨 것도 있다.

먼저

N번 수행 전 충분히 좋은 모델이 발견될 수 도 있다.

즉 충분히 적은 오류가 발생된 경우 Loop를 빠져나와

추가적인 계산에 따른 시간을 절약 할 수도 있다.

다음으로

그래서 error를Consensus Set 으로부터 모델을 재 예측하지 않고

예측 model로부터 바로 계산한다.

그래서 적은 수의 관찰점들로부터 예측된 모델에 관련된 오류 비교에서 발생할 수 있는 시간을

줄일 수 있는 방법도 있다.

 

 

 

 

어느 정도 이해가 갔는데 프로그래밍으로 구현을 해봐야 이해가 갈 듯싶네요!!!

자 먼저 Pseudo Code를 봐보자

 

 

이해가 가셨는가?

자 그럼 직접 구현을 해보자 !!!

 

 

 

 

 

도움이 되셨다면

리플 하나 달아주는 센스 *^^*