RANSAC

이게 데이터마이닝인지 참 애매하다,, 영상처리에서 모델피팅에 주로 사용되는 알고리즘이다.

 

어쨋든 유용한 정보만 땡겨내기 때문에 마이닝이라고 하자

 

 

모델 피팅 과정(걍 트래킹)에서 가장 큰 문제가 되는 것들 중 하나는 바로 Outlier (필요하지 않는 튀는 점, 모델과 동떨어진 곳에 위치하는 점)처리 문제이다.

이 Outlier들은 모델 피팅을 할 때 상당히 큰 잡음으로 작용하여 올바른 결과가 산출되는데 방해가 된다.

그래서 이런 Outlier들은 모델피팅하는 과정에서 무시되거나 적은 가중치를 적용하여 알고리즘에 끼치는 영향을 감소시켜야 한다.

이걸 효과적으로 처리할 수 있는게 바로 RANSAC 알고리즘이다.

 

기본적 아이디어는 참 단순하다. 과연그럴까

RANSAC은 피팅하고자 하는 모델을 구성하기 위한 최소 Inlier(Outlier와 반대로, 모델피팅에 필요한 점들)를 찾아가는 것을 컨셉으로 한다.

 - 주어진 데이터에서 임의의 하부 set을 만들고, 그것이 Outlier에 영향을 받는지 체크

 - 영향을 받지 않으면 선택

 - 그것 중 다시 하부를 선택

 - Outlier에 영향을 받지 않는지 체크

요 위의 과정을 반복하면서 데이터를 모델에 피팅시켜 나간다.

 

 

예 : 라인에 대한 RANSAC 슈도코드

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

* Fitting 대상 점들 초기화

 

* Step1 ~ Step2를 미리 정의된 Loop수 (K)만큼 수행

{

    Step 1 : 미리 정의된 loop수 만큼 1) ~ 2) 수행

      1) 점들 중 임의의 두 점(모델 구성을 위한 최소점)을 선택하여 라인을 그린다.

      2) 그려진 라인과 각 점들과의 거리를 계산하여 임의의 threshold보다 크면 inlier로, 작으면 outlier로 결정한다.

        - 이 때 결정된 inlier의 수는 임의로 그려진 라인에 지원(Support : 이하 지원)되는데, 이 값은 그려진 라인을 평가하는데 사용된다.

 

      // 각 Loop마다 임의의 라인과 그에 대한 지원 값이 생성된다.

 

    Step 2 : Step 1에서 생성된 임의의 라인 중 지원 값이 가장 큰 라인을 선택.

 

       // 피팅 대상 점들을 inlier로 바꾸어 다시 Step ! ~ 2 수행

       // 따라서 K의 루프가 반복될 수록 피팅 대상 점의 수가 감소해 나간다.

}

 

* 최종적으로 선택된 임의의 라인과 초기의 모든 피팅 대상 점들을 사용하여 최적화 수행

* 라인 벡터를 리턴

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

RANSAC의 일반적 알고리즘

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

목표 : Outlier를 포함하는 set S를 model에 피팅시킨다.

 

알고리즘

 1) S 안에서 랜덤하게 s개의 점을 가지는 샘플 세트를 선택하고, 이로부터 임의의 모델을 생성시킨다. (모델 구성을 위한 최소점의 수를 미리 알아야 한다.)

 2) 미리 정의된 대상 모델의 distance threshold값 t를 이용하여 Inlier들과 Outlier들을 결정한다. -> inlier들의 세트 Si를 결정한다. Si내의 원소 수가 Support(지원)값이 된다.

 3) 지원 값이 미리 정의된 threshold값 T보다 크면 Si에 대해서 1) ~ 2)를 수행한다.

 4) 지원 값이 미리 정의된 threshold값 T보다 작으면 1) ~ 2)를 다시 수행한다.

 - 만약 정의된 N루프동안 3)을 만족하는 경우가 발생하지 않으면, 그 동안 생성되었던 Si들 중 가장 큰 지원값을 가지는 것을 최종 Si로 정하고 여기에 대해서 다시 1) ~ 2)를 수행한다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

그렇타면,

Distance Threshold t는 어떻게 결정해야 할까? (inlier와의 거리)

 

우리는 주어진 점들에 어떠한 정도로 피팅되는 모델을 찾고자 한다.

 - 우리는 확률 a만큼 주어진 점들이 inlier가 되도록 하는 t를 설정해야 하는 것이다.

실제로 이 t는 실험적으로 결정해야 하지만, 측정 에러가 0평균, 시그마 분산을 가지는 가우시안 분포를 따른다고 한다면, 우리는 t를 계산하여 알고리즘에 자동으로 적용할 수 있게 된다.

구체적인 계산과정은 생략하고, 확률 a = 0.95에 대한 몇가지 모델의 t값을 아래의 표에 제시한다.

 

 

얼마나 많은 샘플이 필요할까?

 

실제로 알고리즘을 적용할 때 사용 가능한 모든 샘플을 사용하는 것은 계산상으로 불가능하기도하고, 그럴 필요도 없다.

그렇타면, 샘플을 얼마나 사용하는 것이 효과적일까?

답을 얻기위해 위에서 제시한 일반화된 알고리즘 중 몇가지 부분을 확인하도록 하자.

위의 알고리즘은 3)의 조건을 만족하는 경우를 찾지 못하는 경우, 최대 N번 루프를 반복한다.

 - 최대 N개의 랜덤 샘플 세트를 생성할 수 있다는 것

이로부터 먼저 N개의 샘플 세트 중 적어도 하나는 3)을 만족 할 확률 p를 정의하자.

 - 3)을 만족한다는 말은 해당 샘플 세트에서 생성한 모델이 우리가 원하는 레벨(T)만큼은 Outlier의 영향을 받지 않았음을 뜻한다.

일반적으로 p = 0.99가 된다. 또한 임의한 data가 inlier일 확률을 w, outlier일 확률을 e = 1 - w라 하자.

그러면, (1 - w^s) * N = 1 - p가 된다.

 - 주어진 s, e, w를 만족하기 위한 루프 수 N은 다음과 같이 정의 된다.

여기서 루프 수 N은 N개의 샘플 세트를 만들 수 있음과 같다는 것을 기억하자

 

  - p = 0.99일 때 몇가지 s, e에 대한 N의 수가 나타나 있다.

 

 

 

적응적으로 필요한 샘플세트의 수 결정하기

 

사실 대부분의 데이터 세트에서는 Outlier가 얼마나 될 지 예측하기 힘들다

 - 때문에 e를 미리 결정해 놓을 수 없고

 - 그래서 N을 상수로 결정할 수 없다.

어쨋든, N을 적응적으로 바꿔 줄 수 있는 알고리즘을 고안해야한다.

 

제안하는 적응적 업데이트 알고리즘은 다음과 같다. 

핵심은 N의 선택에 필요한 변수 중 하나인 e를 매 샘플 세트 생성 때마다 체크하여, N을 실시간으로 업데이트 해 준다는 것이다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

* N을 무한대로, sample_count = 0으로 초기화 한다.

* e를 0.5로 초기화 한다.

 

* while< N > sample_count()

  - 데이터 세트에서 임의로 모델 생성에 필요한 수의 sample을 선택

  - inlier의 수 체크

  - e = 1 - (inlier의 수) / (총 대응점 데이터의 수)

  - N을 다시 계산

* 종료

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

끗