[2기 광주 박이근] Feature Extraction (RANSAC)

안녕하세요 

광주멤버십 21-2기 박이근 입니다.

특징 추출(Feature Extraction)

캐니 에지 (Canny Edge)에 이어서 RANSAC에 대해서 적어보려고 합니다.

Feature Extraction에는 약간 거리가있을 수 있으나

일반적으로 SIFT나 SURF를 수행한 후 

이미지 결합을 할 때 RANSAC을 많이 이용하기 때문에 

이렇게 아는대로 적어 보려고 합니다.

RANSAC(RANdom SAmple Consensus) 이란 무엇일가요? 

 

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

Fischler와 Bolles에 의해서 제안된 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은 모델을 결정하는데

초기 데이터를 최소로 이용을 하여 수학적인 모델을 구한다는것이 RANSAC의 핵심입니다.

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

반복적인 작업을 통하여 해를 예측하며 해를 찾는 방법이라 할 수 있습니다. 

그래서

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

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

확률은 반복이 더 많이 될수록 정확해지는 모습을 볼 수 있습니다.

 

 

 

자 그렇다면 아무 데이터셋에서 적용할 수 있을가여? 전제조건은 없나요?

당연히 전제조건은 존재합니다. 

다음과 같은 조건을 만족을 한다하는 정의 하에 이루어질 수 있습니다.

1. 데이터 셋은 참인 정보(Inlier)를 포함하고 있다고 가정한다.
    (참인정보가 없으면 안되겠죠)

    

2. 데이터 셋이 수학적 모델 인자들로 표현이 가능하다고 가정한다.
    (수학적인 모델로 표현이 가능해야 초기에 수학적 모델을 적용을 하죠)

    

3. 해당 모델에 맞지 않는 거짓 정보(Outlier)가 존재한다. 
   (거짓정보 즉 잡음이 존재해야 겠죠)

    

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

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

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

이 5가지조건을 갖추어야 이 알고리즘을 적용할 수 있다는 것입니다.

역시 말로 표현하면 도통 무슨 말인지 모르겠습니다. 예를 들어서 설명해 주세요!!!

예를 들어보면 아래 그림은

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

이 데이터 셋은

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을 구할 수가 있다.

 

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

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

먼저

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

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

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

다음으로

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

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

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

줄일 수 있는 방법도 있다.

참고 문헌

[1]  Martin A. Fischler and Robert C. Bolles, "Random Sample Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography", Communications of the ACM, Volume 24 Number 6, June, 1981.