RANSAC이란? Robust-estimator란? M-estimator란?

Posted on Edited on In , ,

모바일로 글을 보신다면 ‘데스크탑 버전으로 보기’를 누르시면 좀 더 보기 쉽습니다

예상 면접 질문

  1. Outlier란 무엇인가요? 어떻게 제거할 수 있을까요?
  2. RANSAC이란 무엇인가요? RANSAC의 작동 방식을 설명해주세요. RANSAC의 장단점도 설명해주세요.
  3. RANSAC 외로 사용할 수 있는 outlier removal 기법들에는 무엇이 있나요?

답

Outlier 데이터란?

  • 컴퓨터 비전에서 우리는 Homography matrix, Fundamental matrix, Essential matrix 등 특정 model에 대한 정보를 계산해야함.
    • 이 때, 우리는 input 데이터로부터 (e.g. keypoint correspondence) model 정보를 계산함.
  • Input 데이터에는 두가지 종류의 데이터가 섞여있음.
    • Outlier 데이터 - 기하학적으로나 통계적으로 잘못된 데이터.
    • Inlier 데이터 - 기하학적으로나 통계적으로 올바른 데이터.
    • 단순히 데이터만 봐서는 inlier / outlier 구분하기 어려움.
  • Model parameter를 정확하게 계산하기 위해서는 Inlier 데이터만 사용해야함.
    • Inlier 데이터로만 model parameter를 계산하면 좋은 모델 파라미터가 나옴.
    • Outlier 데이터를 포함해서 model parmater를 계산하면 잘못된 모델 파라미터가 나옴.
  • Outlier가 생길 수 있는 원인들
    • 조명 변화
    • 부분적 가려짐
    • 회전
    • 모션 블러 등등…

 

Outlier removal이란?

  • Model parameter를 계산하기 위해, 전체 데이터 중 inlier와 outlier를 구분하여 inlier 데이터만 계산에 사용해야함.
    • 특히, 컴퓨터 비전에서 사용하는 least-squares 최적화 방식은 outlier 데이터에 굉장히 취약함.
  • RANSAC, M-estimator 등 다양한 방법이 있음.
    • [이번 글에서는 LkOS, Certifiable algorithms는 다루지 않음].

 

RANSAC이란?

  • “Fischler & Bolles 1981, Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography” 논문에서 제안된 방식.
  • RANdom SAmple Consensus를 줄여서 RANSAC.
    • Random - 무작위하게
    • Sample - 데이터 샘플을 뽑아서 모델을 추정하고
    • Consensus - 모델에 대한 데이터의 합의도를 구해 정확한 모델임을 평가함.
  • RANSAC은 하나의 프레임워크임 (C++에서 템플릿 클래스로 자주 구현함).
    • Homography in RANSAC framework
    • F matrix in RANSAC framework
    • E matrix in RANSAC framework…

 

RANSAC 작동 방식

  1. 전체 데이터로부터 무작위로 minimal set의 데이터를 추출
  2. 뽑은 데이터로 모델 추정
  3. Score 측정
    • If (현재 score > 이전 score), Update score
  4. 1로 돌아감.
예시: Homography in RANSAC framework --- ##### 예시: Homography in RANSAC framework 1. 전체 데이터로부터 무작위로 4개의 데이터를 추출 (i.e. Homography matrix를 추정하는데 필요한 최소한의 데이터의 수는 4개) 2. 뽑은 데이터로 Homography matrix 추정 3. 해당 모델을 기반으로 전체 데이터에 대한 Reprojection error를 측정하고, error threshold를 넘지 않은 데이터의 수를 Score로 저장. - If (현재 score > 이전 score), Update score 4. 1로 돌아감. - 100개의 input 데이터가 (i.e. keypoint correspondence) 있다고 해보자. 그리고 Error threshold는 3.0으로 셋팅했다고 해보자. - 첫번째 루프에서 100개 데이터 중 4개를 무작위로 뽑는다. - 이 4개의 데이터를 기반으로 Homography matrix를 계산한다. - 해당 Homography matrix를 모든 input 데이터에 적용한다. Keypoint correspondence이기 때문에, 1번 이미지로부터 나온 keypoint의 위치 값에 homography matrix를 곱하면 2번 이미지 위의 keypoint 위치를 추정할 것이다. 하지만 실제 위치와는 조금 차이가 있을 것인데 (i.e. reprojection error), 이 차이를 구하여 error threshold를 넘는지 확인한다. - 계산을 해봤더니 10개의 데이터가 error treshold를 넘지 않았다고 해보자. 우리는 이 데이터의 갯수를 'inlier의 수'로 취급하며, 이 값을 우리는 'best model score'로 저장한다. - 두번째 루프를 시작한다. 다시 100개 데이터 중 4개를 무작위로 뽑는다. - 이 4개의 데이터를 기반으로 Homography matrix를 계산한다. - 다시 해당 homography matrix를 모든 input 데이터에 적용하고 inlier의 수를 측정한다. - 이번에는 50개의 inlier 데이터가 측정되었고, 지난 루프의 10개보다 더 많다. 즉, 이 모델은 지난 루프보다 더 정확한 모델이니, 이 값을 'best model score'로 저장한다. - 세번째 루프를 시작한다. 다시 100개 데이터 중 4개를 무작위로 뽑는다. - 이 4개의 데이터를 기반으로 Homography matrix를 계산한다. - 다시 해당 homography matrix를 모든 input 데이터에 적용하고 inlier의 수를 측정한다. - 이번에는 25개의 inlier 데이터가 측정되었고, 지난 루프의 50개보다 적다. 즉, 이 모델은 지난 루프보다 더 부정확한 모델이니, 'best model score'는 변하지 않는다. - 이 과정을 반복한다. ---

 

RANSAC 공식

  • T: 샘플링의 횟수
  • p: 우리가 고른 데이터가 inlier인 확률
  • e: 전체 데이터의 inlier:outlier 비율
  • s: Minimal set을 만들기 위한 데이터의 갯수
  • p, e, s는 보통 우리가 고름.
    • 예시…
    • p = 0.99 (99%의 확률로 정확한 모델을 얻고싶다)
    • e = 0.50 (전체 데이터 중 inlier:outlier 비율이 50:50이다. [물론 절대로 이 값은 정확하게 알 수 없다.])
    • s = 3,4,5,7,8… (p3p? Homography? Nister E? 7-point F? 8-point F?)

 

RANSAC의 장/단점

  • 장점:

    • 성공 시 Outlier를 효과적으로 걸러낼 수 있음.
    • 대략적인 성공 시간을 알 수 있음 (i.e. X번의 iteration 후 Y%의 확률로 정확한 모델 추론~)
    • 일찍 끝나면 그만큼 시간을 벌음
    • 이해하기 쉬움

  • 단점:

    • 무작위 샘플링이라 매번 결과가 다름 (i.e. 동일한 input 데이터임에도, seed 값에 따라서 다른 결과가 나옴.)
      • 이 때문에 deterministic test를 할 때는 seed를 고정해야함.
    • Outlier의 비중이 많아지면 돌아야하는 iteration 수가 급격하게 늘어남
    • 실패할 경우 model 추론에 완전히 실패함
    • Threshold 값을 유저가 직접 튜닝해야함 (i.e. 유저의 경험에 의존함)
    • Multi-model 추론을 할 수 없음.

 

개량 RANSAC?

@19:05초 부터…

[다른 글에서 좀 더 제대로 설명할게요 :)]

M-Estimator란?

  • 컴퓨터 비전에서는 종종 Least-squares optimisation을 통해 Maximum-likelihood Estimation (MLE)를 수행하여 model parameter를 추정하기도 한다.
    • Least-sqaures는 모든 데이터 포인트가 unbias한 노이즈를 가진다는 것을 전제로 삼는다.
    • 하지만 bias가 포함된 데이터 포인트가 계산에 포함되면 least-squares 과정이 무너지게 된다.
  • 이러한 bias를 가진 데이터 포인트를 찾아내고 계산에서 제외하는 기술들을 robust estimation이라고 한다.
    • 이 중, kernel 기법을 사용하여 데이터 포인트들의 residual 값에 weight를 걸어 optimisation을 수행할 수 있게 해주는 기술이 M-estimator이다.

사용하는 방법

  • 기존의 방식은 어떤 model parameter 을 추정하고, 해당 모델의 정확도는 모든 데이터 에 대해 residual 를 구해 평가하였다.
    • 수식으로 표현하면 다음과 같다:
    • (하지만 이 값은 bias를 가진 데이터에서는 1. 큰 값을 가지며, 2. 패턴을 가지며 나타났고, 이는 optimisation을 어렵게 하였다).
  • M-estimator는 사전에 정해둔 커널의 모양을 따라, residual 값에 따른 weight를 새로 지정한다.
    • 수식으로 표현하면 다음과 같다.
  • 커널의 모양은 이 링크, 그리고 아래 그림에도 표현되어있다.
    • 아무런 kernel도 사용하지 않은 pure least-squares의 경우, residual 값은 형태로 계산된다.
      • 이는 전체다수의 residual이 어떠한 optimal 값을 향하고 있어도, 어떤 높은 값을 가진 outlier 데이터가 나타난다면 전체적인 optimisation 방향은 이 outlier의 값을 줄이기 위한 방향으로 흘러간다는 것이다 (이것은 좋지 않다).
    • Hard-redescender로 잘 알려진 Tukey나 Gemen-McClure kernel의 경우, 특정 값 이상부터는 constant로 바꿔버린다.
      • 이는, 특정 값 이상부터는 모든 값들이 outlier로 표현되며, 단일 값이 높다고 해도 전체적인 optimisation 방향에 크게 영향을 끼치지 못한다. 전체적인 optimisation의 방향이 바뀌기 위해서는 전체다수의 residual이 특정한 방향에 optimal 값이 있다고 동의할 때만 가능하다.
Related Posts