[VSLAM 8] RANSAC을 이용한 이상치 제거

Outlier removal

Types of data

1. Inlier data:
   우리가 예상한 데이터 분포 내의 데이터
2. Outlier data:
   데이터 분포에서 벗어난 데이터

Inlier와 Outlier의 구분 방법

Fundamental matrix를 통한 검증 방법

위 사진은 다른 시점에서 찍은 두 사진이 있다. Feature match를 통해 Fundametal matrix를 구하여 camera의 motion을 구한 것이다. 이때 Fundamental matrix를 통해 구한 결과와 다른 특징은 빨간색으로 그렇지 않고 잘 연결된 특징은 초록색으로 연결한 것이다.

사전에 정의된 조건들과 다른 변화(밝기, 회전, 가림, 블러 등)들은 outlier가 될 수 있다.

Types of algorithm

1. Closed-form algorithm:
   Miniaml solver 알고리즘, 정확한 기하학적 조건을 가지고 있는 경우에만 잘 작동
   사전에 정의된 조건과 다른 데이터에 대해 성능이 보장되지 않음

2. Iterative optimization:
   훨씬 더 많은 데이터로 작동하며, 모든 데이터가 포함되는 답을 지속적으로 찾아가는 방법으로 작동
   데이터를 기준으로 하기 때문에 데이터가 잘못되면 결과도 잘못되는 특징이 있음
   대부분의 VSLAM 알고리즘이 이 방식으로 동작하기 때문에 outlier를 제거하여 일관된 데이터로부터 학습할 수 있도록 만들어야하는 과정이 필요

RANdom SAmple Consensus (1981)

무작위로 샘플링한 데이터로 모델을 만들고 데이터들 간의 합의도를 계산하여 다른 데이터들로 해당 모델이 정확한지 아닌지를 평가하는 과정을 거친다.

RANSAC은 template algorithm으로 실제로 안에서 돌아가는 알고리즘은 따로있다. 예를 들어 Fundamental matrix를 구한다고 할 때, 먼저 랜덤하게 추출된 데이터를 가지고 8-point algorithm을 구한다. 이 단계에서 구한 matrix를 model이라고 한다. 이렇게 만들 model을 통해 다른 데이터들을 통해 평가를 수행하는 과정을 거치게 된다. 평과 과정에서 이전에 가장 높은 Score 보다 높다면, 이번 iteration에서 구한 모델과 socre를 기록한다. 그렇지 않으면 버린다. 위 과정을 계속 반복해서 가장 좋은 결과를 찾는다.

최적의 Iteration

T: Number of samplings required to get optimal model
p: Probability of sampled data to be inlier
-> 뽑은 모델이 전부 inlier로 이루어져야 할 확률
e: Ratio of inliers : outliers of the entire dataset
-> 전체 데이터 안의 inlier와 outlier의 비율
s: Minimal number of data to be a minimal set
-> 매 loop 마다 sampling 할 데이터의 수

Example

p=0.99 (We want 99% accuracy)
e = 0.5 (Roughtly the dataset is make of 50% inliers and 50% outliers)
s = 3, 4, 5, 8(P3P, Houmography, Essential matrix, Fundamental matrix)

추가적으로 실제 연산에 필요한 시간을 곱해주면 전체 프로세스의 대략적인 시간을 구할 수 있다.

Modern RANSACs

PROSAC

이미지 매칭에 특화된 방법 중 하나이다. 데이터의 prior를 잘 이용한 방법이다. PROSAC은 RANSAC의 data sampling 과정에서 데이터의 유사성을 판단하는 지표(유사도, 거리 등)가 좋은 데이터를 우선적으로 sampling 하기 때문에 progressive하게 동작한다. 만약, 주어진 반복을 못 마치고 최적화되지 못하더라도 기존의 RANSAC과 같은 성능을 보여준다.

1. 두 이미지에서 얻은 Feature를 통해 Descriptor macthcing 수행, 이때 각 Descriptor 간의 거리를 저장한다.
2. 이때 거리가 가까운 순으로 정렬을 수행한다.
3. 초기 sampling 크기 n을 지정한다.
4. 상위 (가장 가까운) n개에 대하여 sampling 한다.
5. model을 평가한다.
6. 최고 성능보다 좋으면 이를 업데이트하고, 그렇지 않으면 n을 증가시킨다.
7. 4번부터 반복한다.

Lo-RANSAC

dataset 내부의 데이터 pattern을 활용하는 방법이다. inlier 데이터의 경우 뭉쳐있고, outlier의 경우 떨어져있는 특징을 갖는데, Lo-RANSCA은 이러한 특성을 활용하는 방법이다. 이 말은 즉, 정답을 찾았다면 random하게 sampling 할 것이 아니라 정답 주변에서 sampling 하는 것이 유리하다는 의미이다. inner-RANSAC과 optimization 방법을 사용해서 보다 정교한 모델을 만드는데 기여한다.

1. Minimal-set을 샘플링 한다.(RANSAC과 동일)
2. model을 평가한다.
3. 만약, 최고 점수보다 나쁘면, 1번으로 돌아간다. 그렇지 않으면 다음의 절차를 진행한다.
   3.1. 샘플링된 데이터에서 inner data를 다시 sampling한다. (inner-RANSAC)
   3.2. model을 평가한다.
   3.3. 만약, 최고 점수보다 좋으면 이를 업데이트한다. 그렇지 않으면, 3.1로 돌아간다. 이 과정에서 최소 반복 횟수를 넘어간다면 다음 단계로 넘어간다.
4. iterative local optimization을 수행한다.(Gauss-Newton method, Levenberg-Marquardt method)
   4.1. 만약 최고 점수보다 높다면 이를 업데이트한다.
5. 1로 돌아간다.