RANSAC

1. outlier removal

- Inlier data: 예측가능한 data 및 맞는 data

- Outlier data: 예측불가능한 data 및 틀린 data

- 2 types of algorithms

   - Closed-form algorithm: geometrically consistent data -> 필요한 최소치의 data로 한개라도 틀리면 치명적

   - Iterative optimization: statistically consistent data -> 반복해서 Inlier로 최적화

- Error metric

  - L1(SAE) : sum of absolute error

  - L2(SSE) : sum of squared error

- threshold이상의 error는 outlier로 판단하여 제외 시켜줘야 하며, 최악엔 outlier가 inlier보다 많을 경우도 있다.

 

2. RANSAC

RANdom SAmple Consensus: 무작위하게 데이터 샘플을 뽑아 모델을 만들고 합의도를 알아본다.

RANSAC algorithm

1. Randomly sample 'minimal set of data'

2. Estimate model width sampled data

3. Evaluate model score

    - if (Current score > so-far-best score): update score

4. Return to step1

 

$ T = {log(1-p)} / {log(1-(1-e)^{s})}$

T: number of samplings required to get optimal model

p: probability of sampled data to be inliers

e: Ratio of inliers: outliers of the entire dataset

s: minimal number of data to be a minimal set

 

장점: outliers를 제거하지 않아도 결과가 성공적이다

         시간을 예측할수 있다

         조건에따라 일찍 날 수도 있다.

         이해하기 쉽다

단점: 매번 결과가 다르지만 random seed 고정하면 같다.

         outliers가 inliers보다 많으면 실행시간이 급격하게 올라간다. -> 전처리 필요하거나 타 알고리즘 적용

         결과가 실패할경우 모든 data를 탐색한다.

          동시에 1개의 모델만 추정할 수 있다.

 

3. mordern RANSAC

여러 발전된 알고리즘이 있으며 버전별로 조합도 가능하다.

Early-stop method

'minimum iteration', 'maximum iteration', 'success score' 이 설정되어 있어야 조건을 만들 수 있다.

 

- PROSAC

descriptor distance을 기반으로 random sampling한다.

lower distance -> similar descriptor -> better match

 

PROSAC algorithm

- perform descriptor matching

   - during this process, calculate descriptor distance

- Sort data from distance ASCENDING

- set the initial search pool number 'n'

1. sample the tata from 'n' data'

2. estimate model from sample data

3. evaluate score

    - if (current score > so-far-best score), update score

    - if (current score < so-far-best scroe), increase search range by n

4. Return to step 1

 

- Lo-RANSAC 

  - inlier data는 분산이 작고 outliers는 분산이 크다고 가정

  - inner RANSAC을 사용해 정답에 더욱 가까움

    -> for문이 많아 오래걸릴 것 같지만 정답을 빨리 찾기에 짧아짐

 

Lo-RANSAC algorithm

1. sample the minimal-set data

2. Estimate model from sample data

    if (current score < so-far-best score) return t step1

    1. sample the 'minimal-set data' among the inlier data

    2. evaluate model from sampled data

        if (current score > so-far-best score), update score

        if (current score < so-far-best score), return to step2-1

        if (number of loops > maximum loop), go to step 3

    3. perfrom iterative local optimization (e.g Gauss-Newton method, Levenberg-Marquardt method)

         if (current score > so-far-best score) update score

    4. return to step 1