[2023-07-17] 2. RANSAC

RANSAC

Outlier Rejection

• 올바른 현상임에도 불구하고 데이터가 높은 노이즈를 갖고 있을 때, 데이터 분포에서 벗어나는 경우도 있음

• 완전히 잘못된 현상을 거쳐서 나타난 데이터임에도 불구하고 데이터 분포안에 있는 경우도 있음

• 단순히 에러치만을 갖고 Inlier와 Outlier을 구분할 수 없으므로 다음과 같이 정의함

  • Inlier data : Data that is Expected, and is Correct

  • Outlier data : Data that is Unexpected, and is Incorrect

    • 급격한 조명 변화, 회전, 가림, 모션 블러, 기존에 산정한 조건이 깨질 때 등 다양한 원인에 의해 나타남
• feature match를 진행하고 이를 기반으로 fundamental matrix를 구해서 카메라들간의 모션값을 추정함
• 왼쪽에 검출된 픽셀에 fundamental matrix를 곱하면 오른쪽에 있는 correspondence 위치가 나옴
• descriptor match의 값을 fundamental matrix를 통해서 검증하고 잘못된 값들은 빨간색 선으로 표시

2 Types of Computer Vision Algorithms

• Closed-form Algorithms :
  • 문제를 공식, 방정식 또는 수학적 식으로 직접 해결하는 계산 절차로 반복 프로시스나 근사값을 사용하지 않고 특정 문제를 효율적이고 정확하게 해결
  • Only Accepts Geometrically Consistent Data
• Iterative Optimization
  • 최적화 문제를 해결하기 위해 반복적인 과정을 사용하는 방법
  • Only Accepts Statistically Consistent Data

Line Fitting

• Error Metrics(성능을 측정하고 비교하기 위해 사용되는 측정 항목이나 척도)
  • SSE : Sum of Squared Error
  • SAE : Sum of Absolute Error

• 사람이 봤을때는 M1이 더 정확한 라인인 것을 알 수 있고 밑에 동 떨어져 있는 데이터는 통계적 이상치로 생각해 계산에서 제외하는 판단이 가능함
• 알고리즘 입장에서는 다 같은 데이터 포인트라 뭐가 이상한지 모름
  • SSE, SAE로 이상치 데이터도 함께 계산을 하고 에러의 총합을 비교하면 억울하게도 M1 에러 값이 M2 에러 값보다 커서 M2가 더 좋은 모델로 평가가 됨

• 이렇게 데이터 사이에 Outlier 데이터가 있으면 모델 추정이 어려워짐(좋은 데이터들이 많아도 단 하나의 Outlier 데이터 때문에 완전히 잘못된 모델이 추론될 수 있음 )
• 어쩔 수 없이 Outlier 제거 과정을 필수적으로 거쳐야 함
  • RANSAC
  • M-Estimator
  • MAXCON

RANSAC

• RANdom SAmple Consensus
  • Random : 무작위하게
  • Sample : 데이터 샘플을 뽑아 모델을 만들고
  • Consensus : 모델에 대한 데이터의 합의도를 알아봄
• template algorithm
  • RANSAC 자체로는 아무것도 할 수 없음(Framework)
  • 실제로 안에서 돌아가는 알고리즘은 따로 있음
    • Compute Homography(in RANSAC Framework)
    • Compute Essential Matrix(in RANSAC Framework)
    • Compute Fundamental Matrix(in RANSAC Framework)

작동방식

1. 최소한의 데이터 수(minimal set of data, e.g. 8 point algorithm : 8개)를 무작위하게 뽑음
2. 뽑은 데이터를 기반으로 모델을 추론
3. 추론한 모델을 기반으로 score을 측정함 (알고리즘 마다 측정방식이 다름)
4. 현재까지의 Best score 보다 높은 경우 갱신하고 아닐 경우 이전 모델의 정보가 더 정확한 것이니 버림
5. 다시 1번 단계로 돌아감

• 이런식으로 계속 루프를 도는 알고리즘으로 좋은 모델이 나올 때 까지 알고리즘을 돌림

작동방식(with Homography)

1. 최소한의 데이터 수 4개(Homography를 구하기 위해서 필요한 데이터 : 4개) 를 무작위하게 뽑음
2. 뽑은 데이터를 기반으로 Homography Matrix를 추론함
3. 왼쪽 이미지의 픽셀 값에 Homography Matrix를 곱하고 오른쪽 이미지 feature correspondence 위치에 픽셀이 올라오는데, 데이터 노이즈가 있으면 바로 정확하게 위에 올라오지 않음
4. 이 픽셀간의 거리 차이(reprojection error)를 전부 측정하여 더함 -> 여기서 특정 threshold를 추가할 수 있음 (예를 들어 2pixel 이상 떨어진 것들만 reprojection error로 인정)
5. 이 reprojection error가 지금까지 추론한 모델보다 낮으면 Best Score 모델로 갱신함
6. 다시 1번으로 돌아가서 루프를 돌음

루프를 돌린다면 언제까지 돌려야하는가?

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

p :뽑은 모델이 전부 inlier로 이루어져야할 확률

e : 전체 데이터 속의 inlier과 outlier의 비율

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

• e.g.
  • 99% 확률로 inlier 데이터로 이루어진 모델이길 원함
    • p = 0/99
  • 전체 데이터셋은 inlier : 50%, outlier : 50% 의 비율로 갖고 있음
    • e - 0/50
  • 사용하는 알고리즘에 따라 고를 수 있는데 Homography를 사용하고 있으니 4로 설정 (P3P : 3, Homography : 4, Essential Matrix : 5, Fundamental Matrix : 8)
    • s = 4
  • 위에서 정한 p, e, s를 토대로 T를 구하면 됨’

RANSAC 장점

• 성공할 경우 inlier만으로 모델을 추론하고 dataset에서 outlier을 제거할 수 있음
  • 데이터 분포를 직접 분석하는 것 없이도 가능한 점은 인상적임
• 전체 Process 시간을 어느정도 예측할 수 있게 해주는 것은 엔지니어 입장에서 도움이 되는 정보
  • 언제 작업이 끝나는지 아는 것은 성공과 실패의 여부를 알 수 있는 좋은 지표
• RANSAC을 조금 개량 시켜서, 좋은 모델을 운좋게 빠르게 찾은 경우 조금 더 빠르게 끝내게 해주는 기법을 추가할 수 있음 (early-exit)
• 굉장히 심플하여 이해하기 쉬움

RANSAC 단점

• 알고리즘 자체가 랜덤성을 갖고 있어 돌릴때 마다 결과 값이 다르게 나타남

  • 동일한 데이터로도 성공, 실패할 수 있음
  • 알고리즘 엔지니어 입장에서는 이 점은 여간 귀찮은 점이 아님
    • 알고리즘의 성능이 좋아졌는지 아닌지 파악하기 위해, 코드를 수정하고 실행하는 과정을 반복하는데 매번 결과가 랜덤하게 나오므로 코드를 수정해서 다시 실험했을 때, 이게 코드를 바꿔서 결과가 좋아졌는지, 나빠졌느지 아니면 단순히 RANSAC의 랜덤성에 의해 결과가 바뀐 것인지 알 수 없음

• 전체 데이터셋에서 inlier 데이터보다 outlier 데이터가 더 많을 경우 실행시간이 급격하게 늘어남

  • outlier 데이터셋이 80% 일 때 모델을 추론해야하는 경우가 있는데 이런 경우에는 RANSAC이 상당히 힘들고 오래 걸림 -> outlier의 데이터가 많아 outlier데이터를 뽑을 확률이 높기 때문

  • RANSAC이 실패할 경우 모든 데이터의 조합의 가능성을 순회하는 속도로 수렴함

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

  • “이 데이터셋으로 가장 정확한 3개의 Fundamental Matrix를 동시에 추출해줘’’ 이런 작업은 RANSAC을 통해서 불가능함

Modern RANSACs

• 기존 RANSAC의 단점을 보완함
• 여러가지 개량된 RANSAC이 존재함

Early-Stop Method

• RANSAC이 좋은 모델을 운좋게 빨리 찾았을 경우, 바로 그 자리에서 RANSAC을 끝냄
  • RANSAC을 바로 끝내면 차지한 만큼 CPU 사이클이 비게되고, 다른 CPU 코어에서 CPU 사이클을 가져올 수 있게 하거나 다음 프로세스를 빠르게 가져와서 실행시킬 수 있음
• 미리 정의해야 하는 것들
  • 퀄리티를 보장하기 위한 RANSAC 루프의 최소 수
    • 어느 정도 좋은 결과를 내놓아도 혹시 모를 더 좋은 결과를 내기 위해 x번을 더 돌게 만듬
  • 고정된 프로세스의 시간을 보장하기 위한 RANSAC 루프의 최대 수
    • 아무리 좋은 모델이 안 찾아진다해도 x번 이상 루프를 돌고 나면 멈추고 터트림 -> RANSAC 실패 (실시간 제약상황을 지키기 위한 방법)
  • 성공의 지표(Success Score)
    • RANSAC이 추론한 모델이 설정한 지표를 넘어서는 순간 성공으로 판단하여 RANSAC을 끝내서 탐색을 중단

PROSAC

• 이미지 매칭에 특화된 데이터의 PRIOR를 아주 잘 이용한 예시
• 전제조건으로는 Descriptor 매칭을 할때 L2 Norm이나 Hamming Distance 같은 Distance를 측정함
  • Feature Descriptor간에 Distance가 적은 match 일 수록 모델 추론할 때 더 정확하게 추론할 가능성이 높다고 판단(inlier 데이터일 확률이 높다고 판단)
• 기존 RANSAC의 Random Sampling 과정을 좀 더 낮은 Distance를 가진 Descriptor match를 Sampling하는 기법으로 바꿈
• 그러면서 점진적으로 점점 더 높은 Distance를 가진 Descriptor match를 Sampling함

• Progressively 하게 찾으므로 PROSAC임

• PROSAC이 운이 나빠서 완전히 실패하는 케이스도 기존 RANSAC의 성능으로 수렴함
  • PROSAC은 무조건 기존의 RANSAC 보다 성능이 좋을 수 밖에 없음

진행방식

1. 2개의 이미지의 Descriptor Match를 수행함
2. 1번 과정에서의 Match들 마다 Distance 값을 기록
3. Distance 값들을 낮은 Distance에서 높은 Distance로 오름차순 Sorting 해줌
4. PROSAC 에서 몇 개씩 탐색할 것인지 pool size n을 설정함
5. n 개의 search pool에서 데이터를 sampling 함
6. 데이터를 토대로 모델을 추론하고 평가함
7. 좋은 결과가 나오면 score 값을 업데이트하고 나쁜 값이 나오면 search pool을 한번 더 키워줌
8. 5번으로 돌아가서 루프를 돌음

Lo-RANSAC

• 데이터 셋 내부의 데이터 패턴을 잘 이용하는 예시
• inlier 데이터 끼리는 뭉쳐있고 outlier 데이터는 산개하는 특징을 갖는 경우가 많은데 이러한 특징을 잘 이용함
  • inlier 데이터를 사용해서 모델을 찾고 나면, 정답은 그 근처에 있으니 랜덤한 다른 위치로 이동할 필요 x
• RANSAC 사이클을 한번 돌릴 때 한번의 루프속에서 작은 Inner-RANSAC을 만들어 더 정확한 값을 얻으려 함
  • optimization까지 추가를 해서 최대한 정답과 가깝게 가려함

진행방식

1. 최소한의 데이터 수를 무작위하게 뽑음
2. 뽑은 데이터를 기반으로 모델을 추론
3. 추론한 모델을 기반으로 score을 측정했을 때 best score보다 낮으면 1번으로 가고 높으면 inner-RANSAC을 실행함(방금 전 모델 score을 평가할 때 inlier라고 판단한 데이터셋을 새로운 데이터셋으로써 다루면서 새로운 RANSAC을 실행하는 것 = inlier 데이터들만 갖고 RANSAC을 진행하는 것이므로 더 좋은 결과가 나타날 확률이 높음 )
4. 좋은 값이 나타났다면 Gauss-Newton Method나, Levenberg-Marquardt Method Iterative Optimization(최적화 방법)을 통해 더욱 더 정답에 가까이 다가감
5. 다시 1번으로 감

• 추가되는 과정이 많아 Standard RANSAC보다 느릴 것 같지만 실제로는 정답에 재빠르게 도달하려 하기 때문에 더 적은 루프수를 돌기 때문에 훨씬 더 빠름

• PROSAC처럼 Descriptor match score가 없는 경우 Lo-RANSAC을 사용하기 적합함

  • PROSAC을 사용할 수 있는 경우에서도 inner-RANSAC과 Iterative Optimization을 조합하여 사용하면 상당히 좋은 성능을 냄