[Multiple View Geometry] RANSAC

출처 : https://www.youtube.com/watch?v=v3322cNhCTk&list=PLxg0CGqViygP47ERvqHw_v7FVnUovJeaz&index=9 

---

 

RANSAC : Line Fitting Example

• n개의 점에 가장 잘 피팅되는 선을 찾을 때 쓰는 방법임
• least-squares method 의 경우 outlier가 많을 때 robust하지 않음
• RANSAC은 outlier가 많은 데이터에서 쓸수있는 robust 한 모델임

 

RANSAC Steps

1. Randomly select minimal subset of points
   • 예를 들어, y=mx + c를 구하기 위해 2개의 점을 임의로 잡는다.
2. hypothesize a model
   • 예를 들어, (x1, y1), (x2, y2)를 이용해 m,c를 특정한다.
3. compute error function
   • 예를 들어, 가장 shortest distance
4. select s number of points consistent with (threshold = t) model
5. Repeat hypothesize-and-verify loop (N-trials)
6. Select the hypothesis with the highest number of consistent points (i.e. inliers)

 

Choosing the parameters

• s개의 points
  • 주로 어떤 모델을 특정하기까지 필요한 최소의 점으로 잡는다.
  • line일때는 2개, homography matrix일 때는 4개가 필요하다.
• t threshold
  • 실험적인 값으로 정한다.
  • measurement error가 알려져있으면 다음과 같이 잡는다.

• N개의 sample 개수

RANSAC을 수행할 샘플 개수 N을 정하는 방법

• p = 샘플 중 적어도 하나의 점이 outlier가 아닐 확률
• w = 어떤 점을 잡아도 그게 inlier일 확률 (일반적으로 판단하기 힘들다)

샘플사이즈 s에 따른 N의 개수, s를 작게 가져가는 것이 좋다.

w를 근사치로 구하는 방법, 이를 이용한 adaptive RANSAC 알고리즘