[VSLAM]RANSAC

Outlier Removal

Data

Types of data

- Inlier data: 정상 범위 내의 데이터

- outlier data: 정상 범위 밖의 데이터

 

두 데이터를 구분하기 위해 에러 값만으로는 판단할 수 없다

노이즈가 높을 수 있다

혹은 완전히 잘못된 과정으로 모은 데이터라도 올바르게 나타날 수 있기 때문이다

 

왼쪽 Point에 F 행렬을 곱하면 epipolar line이 나타난다

초록색 점은 유사도가 높으며, 빨간색 점은 유사도가 낮다

 

F를 통해 유사도를 검증할 수 있다

F를 통해 추론했을 때는 부정확할 수 있으므로 

데이터만을 통해 어떤 매치가 옳은지 확인하기 위해

F 행렬을 통해 검증한다

 

이미지에서 Outlier가 나타나는 원인으로는

갑작스러운 밝기 변화, 움직임 등으로 깨끗한 이미지를 얻을 수 없거나

가려지는 등으로 원하는 point를 찍을 수 없을 때 나타난다

 

Model fitting

outlier 제거의 필요성

통계적으로 부정확하며 SLAM에서도 geometry적으로 정확하지 않다

 

ex) Line fitting

여러 개의 데이터 포인터들을 가로지르는 선 중 가장 정확한 선을 찾는 과정

 

에러를 측정하는 방법

- SSE(sum of squared error): 제곱 오차의 합

- SAE(sum of absolute error): 절대값 오차의 합

 

위 방법들을 통해서 에러를 구할 수 있다

데이터에 outlier가 포함되어 있을 때

아래 같은 경우에서 통계적 에러일 가능성이 높다

하지만 알고리즘의 경우에서는 알 수 없기 때문에

에러를 측정하면서 같이 반영된다

또한 오차의 절대적 크기가 클수록 반영 정도가 다르기 때문에

에러를 구하면서도 문제가 발생할  수 있다

 

 

Outlier 제거 방법

이러한 outlier를 제거하기 위해

대표적으로 RANSAC, M-Estimator, MAXCON 등이 있다

 

 

RANSAC(standard)

Standard RANSAC

RANdom SAmple Consensus

random: 무작위하게

sample: 데이터 샘플을 뽑아 모델을 만들고

consensus: 모델에 대한 데이터의 합의도(일치, 조화)를 구한다

 

RANSAC은 하나의 템플릿 알고리즘으로

내부에서 돌아가는 알고리즘은 별도로 있다

 

작동 방식

1. minimal set of data를 무작위로 뽑는다

minimal set of data는 모델을 추론하기 위한 최소한의 데이터의 수를 의미한다

 

2. 이후 뽑은 데이터를 기반으로 모델을 추론한다

 

3. 추론한 모델을 기반으로 점수를 측정한다

모델 점수를 측정하는 방식은 알고리즘 마다 다르다

 

4. 측정하면서 최고 점수보다 높은 경우(정확한 경우)

이 점수로 업데이터 한다

 

좋은 결과가 나올 때까지 1번부터 4번 과정을 반복한다

 

Homography + RANSAC algorithm

1. 수 많은 데이터에서 4개의 feature match를 뽑는다

homography를 구하기 위해 4쌍의 feature match가 필요하다 

 

2. 이 데이터를 기반으로 homography matrix를 추론한다

 

3. 이후 왼쪽 이미지의 픽셀 값에 homography matrix를 곱한다

오른쪽 이미지의 feature correspondence 위치에 pixel이 올라온다

데이터에 노이즈가 있는 경우 정확하게 올라오지 않는다

픽셀 거리를 전부 측정한 후 모두 더한다(reprojection error)

 

4. 새로 구하는 reprojection error이 기존의 제일 낮은 값보다 낮다면

새 점수를 업데이트한다

 

좋은 결과가 나올 때까지 반복한다

 

최적의 반복 횟수

위에서 말한 RANSAC의 반복횟수를 정하는 식이다

T: 최적의 점수를 얻기 위한 반복 횟수

p: 뽑은 모델이 전부 inlier일 확률, 보통 0.99로 잡는다

e: 정제 데이터의 inlier와 outlier 비율

s: 매 loop마다 샘플링할 데이터의 수

p를 0.99, e는 0.5, s는 4(homography)일 경우와 같이 구할 수 있다

 

장단점

Pros

- 성공할 경우 inlier 데이터 만으로 모델을 추론하여 outlier를 제거할 수 있다(데이터 분포 확인 필요X)

- 전체 프로세스 시간을 예측할 수 있다. 이를 통해 성공 여부와 실패 여부도 예측할 수 있다

- 좋은 모델을 찾은 경우 더욱 빠르게 동작할 수 있다

- 단순하기 때문에 이해하기 쉽다

 

Cons

- 알고리즘이 random하기 때문에 돌릴 때마다 결과값이 다르다 (random seed 를 고정하여 해결)

동일한 데이터라도 실패하기도 하고 성공하기도 한다

- 이에 따라 같은 데이터에서 나온 결과를 통해 피드백을 받아 코드를 수정하기 어렵다

- inlier보다 outlier 수가 많아질 경우 실행 시간이 급격하게 늘어난다

최악의 경우 모든 데이터를 순회하는 것과 같은 시간이 걸린다

- 하나의 데이터셋에서 여러 모델을 동시에 추출할 수 없다

 

 

Modern RANSACs

기존의 RANSAC의 문제점

- 데이터 분포를 고려하지 않는다

- prior data를 사용하지 않는다

- 노이즈를 포함한 데이터를 고려하지 않는다

4.5.0 이전 버전의 OpenCV에서도 standard RANSAC을 사용한다

 

 

Early-stop method

RANSAC에서 성능이 좋은 모델을 빨리 찾은 경우 그 즉시 RANSAC을 끝낸다

 

추가로 변수를 선언해야 한다

- 최소한의 성능을 보장하기 위한 loop의 수, 운 좋게 너무 빨리 끝나는 경우를 막을 수 있다

- 고정된 프로세스의 시간을 보장하기 위한 최대 loop의 수, 실시간성을 지킬 수 있다

- 목표로 하는 성공 점수, 목표치에 도달한다면 RANSAC을 끝낼 수 있다

 

PROSAC

이미지 매칭에 특화된 기법으로 prior를 잘 사용한 기법이다

 

전제조건

discrete한 매치를 할 때 feature descriptor 거리가 적은 match일수록

더욱 정확하게 모델을 추론할 수 있다

 

기존 RANSAC의 랜덤 샘플링 과정을

더 낮은 distance를 가진 descriptor match를 샘플링하는 방법으로 바꿨다

 

점진적으로 높은 distance를 가진 descriptor도 매치하는 방법을 사용했다

 

PROSAC의 성능이 아무리 낮아도 RANSAC과 동일하다

 

 

과정

두 개의 이미지에서 desciptor match를 수행한다

match 마다 distance 값을 기록한다

match의 길이를 저장한 벡터를 오름차순으로 정렬한다

PROSAC에서 몇 개씩 탐색할지 정한다

 

이후 RANSAC을 수행한다

이후 추론하고 평가한 후 점수가 좋을 경우 업데이트한다

이를 반복한다

 

Lo-RANSAC

inlier 데이터끼리는 뭉쳐있고

outlier 데이터끼리는 흩어져있는 특성을 이용한 방식이다

 

한 번 inlier 데이터를 찾고 나면 그 주변의 값을 찾는다

 

RANSAC 루프가 한 번 돌 때 한 번의 루프 속에서 inner-RANSAC을 추가로 만들어 정확한 값을 만들고

optimization을  추가하여 성능을 높인다

 

과정

미니멀 데이터 셋을 샘플링한다

모델을 추론하고 평가한다

점수가 좋아진 경우 새로운 inner-RANSAC을 수행한다

 

inlier 판단되 데이터 내에서 새롭게 RANSAC을 수행하므로 성능이 좋아진다

좋은 값이 나타나면 최적화를 수행하여 정답률을 높인다

 

다시 바깥 루프로 나와 RANSAC을 수행한다

 

위 과정을 반복한다

 

과제

E 행렬과 F 행렬을 구하는 튜토리얼에 사용한 RANSAC을 PROSAC으로 바꾸어 속도 변화를 profiler로 확인한다