RANSAC

Type of data

* Inlier data

   : 우리가 기대했던 값이며, 실제로도 맞는 값

* Outlier data

   : 우리가 기대하지않았던 값이며, 실제로도 틀린 값

 

이 식에 의해 왼쪽 포인터에 F (Fundamental matrix)를 곱하면 epipolar lane을 알 수 있습니다.

Inlier data는 초록색, Outlier data는 빨간색으로 나타냈습니다.

 

Outlier data 픽셀은 descriptor matching을 할 때 이것도 match다라고 평가가 되었을테지만 motion 정보를 기반으로

fundamental matrix를 가지고 추론했을 때는 부정확한 값이 됩니다.

---

Outlier rejection

 

Outlier data는 어떻게 생길까요?

- 급격한 조명 변화, 회전, 가려짐, 모션블러, 기하학적 조건이 깨지게 될 때 나타납니다. 

 

Computer vision에서 두 가지 알고리즘으로 나뉜다고 합니다. 

- Closed-form algorithm

    : 정확한 기하학적 조건을 가지고 있을 때 작동하도록 설계되어있는 알고리즘들.

      -> 예를 들어 : 8-Point algorithm 같은 경우 하나라도 잘 매칭되지않는 거라면 잘못된 결과가 나타나게 됩니다.

- Iterative optimization

    : 데이터 분포 속에 패턴을 찾아서 좋은 결과를 내는 알고리즘들. 

     -> Inlier data 사이에서 패턴을 찾아서 결과를 냅니다. 이 결과를 따르지 않는 데이터가 있다면 잘못된 패턴을 추론하게 됩니다.

 

따라서 알고리즘을 수행하기 전에 outlier data를 제거하는 것이 중요합니다.

 

 

Model fitting

-> Need for outlier rejection

 

Line fitting

SSE 혹은 SAE 값을 구하여 평균값이나 총합이 최솟값이 되는 라인이 가장 정확한 라인일 것 입니다.

 

Outlier data 존재할 때 M1오차가 더 커서 잘못된 결과가 나오는 모습

이처럼 절대 다수가 좋은 모델을 가지고 있어도 하나의 Outlier data 때문에 잘못된 모델이 추론될 수 있습니다. 

 

 

RANSAC ( : RANdom SAmple Consensus)

-> "무작위하게 데이터 샘플을 뽑아 모델을 만들고, 모델에 대한 데이터의 합의도를 알아봄."

 

 작동방식

1. minimal set of data(모델을 추론하기 위한 최소한의 데이터의 수)를 무작위로 뽑습니다. 

 (ex: 8-point algorithm은 8개가 필요)

2. 샘플데이터를 바탕으로 모델을 추론합니다. 

3. 모델 score를 평가합니다. 만약 현재 score가 이전 best score보다 높은 경우 업데이트를 해줍니다. 

4. step1로 돌아갑니다.

 

작동방식 예 (Homography에 RANSAC을 돌린 예제)

1. 수 많은 데이터들 중에 4개의 feature match를 뽑습니다. (Homography를 구하기 위해서는 필요한 데이터는 4쌍의 feature match입니다.)

2. 이 데이터를 기반으로 Homography matrix를 추론합니다. 

3. 왼쪽 이미지의 픽셀값들에 Homography matrix를 곱해줍니다. 그러면 오른쪽 이미지에 feature correspondence 위치에 픽셀들이 올라와야 하는데 데이터의 노이즈가 있으면 정확하게 올라오진 않습니다. 이 픽셀 거리를 전부 측정해서 더할 건데 이걸 reprojection error라고 합니다.

아니면 error threshold값을 설정하여 두 픽셀 이상 떨어진 것들만 reprojection error로 판단하는 것도 있습니다.

따라서 최근 score가 이전 best score보다 높다면 업데이트를 해줍니다.

4. step1로 돌아갑니다.

 

이 반복문을 언제까지 돌려야 할까요?

T : 최적의 모델을 얻기 위해서 돌려야 할 루프의 횟수

P : 뽑은 모델이 전부 Inlier data로 이루어져야 할 확률 

e : 전체 데이터 속에 inlier와 outlier 비율 

s : 매 루프마다 샘플링할 수 

 

예시)

우리가 99% 의 정확도를 원한다면 p=0.99

inlier와 outlier의 비율이 50%      e=0.5

s는 알고리즘 마다 다름(P3P : 3, Homography : 4, Essential matrix : 5, Fundamental matrix : 8)

Homography를 사용한다면 s = 4

따라서 T를 구할 수 있습니다.

 

RANSAC 장/단점

 

장점

•  RANSAC은 성공할 경우 Inlier만으로 모델을 추론한 다음 dataset에서 성공적으로 outlier을 제거할 수 있습니다.
• 데이터 분포를 분석하는 작업 없이도 가능합니다.
• 전체 프로세스 시간을 어느정도 예측 가능합니다.
• 이해하기 쉽습니다.

단점

• 돌릴 때마다 결과값이 다르게 나타납니다. (동일한 데이터로도 어떨 땐 성공, 어떨 땐 실패를 나타내기도 합니다.)
• 전체 dataset에 Inlier보다 Outlier의 수가 더 많아지게 되면 실행시간이 오래 걸리게 됩니다.
• 실패하면 모든 가능성을 검색하는 것으로 수렴됩니다.
• 하나의 dataset에서 여러 모델을 추출할 수 없습니다.

 

Modern RANSACs

기존 RANSAC은 데이터의 분포를 알고있어도, prior 데이터를 알고 있어도 이것들을 전혀 활용할 수 없는 알고리즘이었습니다.

하지만 하나의 dataset에서 여러 모델을 추출할 수 없는 문제는 여전히 불가능합니다.

여러가지의 개량 RANSACs 종류는 이러합니다.

-MSAC, MLESAC, Lo-RANSAC, NAPSAC, P-NAPSAC, DEGENSAC, PROSAC, MAGSAC, APRANSAC

 

OpenCV 4.5 버전 이상부터 개량된 RANSACs을 쓸 수 있다고 합니다.

 

E값과 F값을 구할 때 강사님께서 자주 쓰시는 조합입니다.

- Early stop

- PROSAC

- Lo-RANSAC

 

1. Early stop

RANSAC이 좋은 모델을 운좋게 빨리 찾았을 경우 바로 RANSAC을 바로 끝내는 방법.

그만큼 CPU cycle이 비게 되는데 다른 CPU core에서 CPU cycle을 가지고 올 수 있게 해주거나, 다음 프로세스를 빨리 가져와서 실행시키는 방법이 있습니다.

 이 방식을 구현하기 위해서는 3가지 변수를 미리 정의해야 합니다.    1. 최소한의 퀄리티를 보장하기 위한 RANSAC 루프의 수    2. 최대 루프의 수 제한     3. RANSAC이 추론한 모델이 성공지표를 넘어서게 되면 즉시 종료

 

2. PROSAC

: 이미지 매칭에 특화된 RANSAC기법, 데이터의 Prior를 잘 이용한 알고리즘

 

전제조건

• descriptor match를 할 때 L2norm이나 Hamming Distance를 측정하게 되는데 이러한 feature descriptor간의 distance가 적은 match일수록 모델 추론을 할 때 Inlier일 경우가 큽니다.
• RANSAC의 random sampling 과정을 좀 더 낮은 distance를 가진 descriptor match를 sampling하는 기법으로 바꿨습니다.

진행방식

1. 두 개의 이미지를 desciptor matching을 수행합니다. (이 과정에서 match마다 기록을 해줍니다.)

2. 이 match들을 담아둔 vector가 있다고 한다면 오름차순 정렬 합니다. 

3. PROSAC에서 몇 개씩 탐색을 할건지 pool size를 지정해줍니다.

4. 이후에는 RANSAC 과정이 실행됩니다.

    1. n개의 search pool 내부에서 데이터를 sampling 합니다. 

    2. 이 데이터를 통해 모델을 추론하고 평가합니다.

    3. 만약 score가 더 높다면 갱신을 해주고 낮다면 pool size를 키워줍니다.

    4.RANSAC루프를 반복합니다.

 

 

3. Lo-RANSAC

: Inlier가 서로 밀집해있다는 특징을 잘 이용한 알고리즘

   -> Inlier데이터를 사용해서 모델를 찾고나면 정답은 근처에 있다는 것이고, 랜덤한 위치를 이동할 필요가 없다는 뜻입니다.

        그래서 Lo-RANSAC은 한 번 cycle을 돌릴 때 한 번의 루프 속에서 또 작은 inner -RANSAC을 만들어서 더욱 정확한 값을 얻으려고          합니다.

 

진행방식

1. minimal-set data를 sampling합니다.

2. 그 sampling 데이터로부터 모델을 추론합니다.

    *기존 best score가 좋다면 다시 step1로 갑니다. 새로운 모델이 더 좋다면 Inner-RANSAC을 실행합니다.

    1. Inlier라고 판단되었던 데이터들을 새로운 dataset로써 다루면서 새 RANSAC을 시작합니다. (Inlier 데이터들로 RANSAC을 진행하         는 것이기에 정확도가 높아질 것 입니다.)

   2. 이 sampling 된 데이터로부터 모델을 추론하고 평가합니다.

        * 현재 score가 기존 best score보다 높으면 갱신, 낮으면 step2-1로 갑니다.

        * 루프 수가 maximum loop에 도달하면 step3에 갑니다.

 

3. (Gauss-Newton method, Levenberg-Marquardt method과 같은) 최적화 방식을 통해 더욱 더 정답에 가까이 다가갑니다.

4. step1로 갑니다.