[ML] RANdom SAmple Consensus (RANSAC)

1. 정의 및 Key Idea

RANSAC (RANdom SAmple Consensus)는 많은 수의 이상치(outlier)가 있는 dataset에서도

model의 parameters를 강건하게 추정하는 voting based iteration algorithm.

Consensus
합의라는 의미를 가짐.

 

RANSAC의 핵심 아이디어는

• voting (=inlier counting)을 사용하여
• 모델에 잘 맞는 데이터 포인트(inliers)와 맞지 않는 데이터 포인트(outliers)를 구별하는 것임.
• 지지하는 inliers의 수가 많은 모델을 선택: consensus set 이 가장 큰 모델을 지지.

왜 “Consensus”라는 용어를 사용한 이유?
합의(consensus) 라는 용어는 통계적으로 더 많은 데이터 포인트가 해당 모델을 지지하는 경우, 그 모델이 신뢰할 만하다는 것을 의미.
즉, “consensus” 는 “여러 데이터 포인트가 특정 모델에 동의하는 것” 을 의미하며, 모델의 신뢰도를 평가하는 기준으로 사용됩니다.

---

2. RANSAC의 주요 특징:

1. outliers 에 대해 robust!: RANSAC은 데이터셋에 많은 수의 이상치(특정 패턴이 없는)가 있는 상황에서 특히 효과적.
2. 모델 추정 시간 단축: 데이터의 부분집합을 중심으로 작업하기 때문에 모델 파라미터를 추정하는 데 필요한 시간을 줄일 수 있음.
3. 반복 알고리즘: 알고리즘은 hypothesizing 과 validation 과정을 반복.
4. Voting(투표) 방식: 각 가설에 대해 인라이어의 수를 세어 최적의 모델을 결정하는 voting based algorithm.

---

3. Homography에서의 적용.

RANSAC (RANdom SAmple Consensus)는 이미지 Homography(호모그래피)를 추정할 때 매우 유용함.

3-1. 예제: RANSAC을 이용한 이미지 Homography(호모그래피) 추정 단계

1. Feature(특징) 추출:
   • 두 이미지에서 Feature points(특징점)을 추출하는 단계임. 일반적으로 SIFT, SURF, ORB와 같은 알고리즘을 사용함.
2. 잠재적인 Matching set(매칭 세트) 계산:
   • 추출한 Feature points(특징점)을 기반으로 두 이미지 간의 잠재적인 Matching set(매칭 세트)을 계산하는 단계임. 이때 거리 기반 매칭 알고리즘(예: KNN)을 사용함.
3. 반복 단계 (가설 생성 및 검증):
   • 최소 Sample(샘플) 선택:
     • 무작위로 최소 Sample(예: 4개의 점)을 선택하는 단계임.
     • 이 4개의 점은 Homography matrix(행렬)을 추정하는 데 필요함.
   • Homography(호모그래피) 계산:
     • 선택된 Sample(샘플)을 사용하여 Homography matrix(행렬)을 계산하는 단계임.
   • 오차 함수 계산 및 Inlier(인라이어) 식별:
     • 계산된 Homography(호모그래피)를 사용하여 나머지 점들이 얼마나 잘 맞는지 평가하는 단계임.
     • 특정 임계값 이하인 점들을 Inlier(인라이어)로 식별함.
   • 비율 계산:
     • Inlier(인라이어)의 비율을 계산하여 모델의 품질을 평가하는 단계임.
   • 반복:
     • 위 과정을 여러 번 반복하여
     • 가장 많은 Inlier(인라이어)를 포함하는 Homography(호모그래피)를 찾음.
4. 모든 Inlier(인라이어) 기반 Homography(호모그래피) 계산:
   • 가장 많은 Inlier(인라이어)를 포함하는 최적의 모델을 선택한 후,
   • 이 모델을 사용하여 모든 Inlier(인라이어)를 기반으로 Homography(호모그래피)를 다시 계산.
5. 추가 Matching(매칭) 찾기:
   • 4번에서 구한 최적의 Homography(호모그래피) 모델을 사용하여
   • 추가적인 Matching(매칭)을 찾는 단계임.
6. Homography(호모그래피) 정제:
   • 모든 올바른 Matching(매칭)을 기반으로 Homography(호모그래피)를 정제하여
   • 최종 Homography matrix(행렬)을 얻는 단계임.

---

3-2. 정리:

1. Feature 추출 및 Matching:
   • 두 이미지에서 SIFT 알고리즘을 사용하여 Feature points(특징점)을 추출하는 단계임.
   • KNN 매칭 등을 사용하여 잠재적인 Matching pairs(매칭 쌍)을 찾는 단계임.
2. RANSAC 반복:
   • 최소 Sample(샘플)(4개 점)을 무작위로 선택.
   • 이 4개의 점을 사용하여 Homography matrix(행렬)을 계산.
   • 계산된 Homography(호모그래피)를 기반으로 다른 점들을 평가하여 Inlier(인라이어)를 식별하고 카운트.
   • 이 과정을 여러 번 반복하여 가장 많은 Inlier(인라이어)를 포함하는 Homography(호모그래피)를 찾는다.
3. 최적의 Homography(호모그래피) 계산 및 정제:
   • 최종적으로 가장 많은 Inlier(인라이어)의 Homography모델에서의 inlier들을 이용하여
   • Homography(호모그래피)를 다시 계산하고,
   • 이를 통해, 추가적인 Matching(매칭)을 찾아 정제하는 단계임.

---

참고할 동영상

https://youtu.be/EkYXjmiolBg?si=WLmk0GXZONn4j32q

 

다른 컴퓨터 비전에서의 이용사례가 잘 정리된 자료

https://www.ipb.uni-bonn.de/html/teaching/msr2-2020/sse2-11-ransac.pdf

다운로드

---

4. 2D Line Fitting 을 통한 일반적인 RANSAC 에 대한 설명.

다음 동영상을 참고하라.

https://youtu.be/A0ueLmzBgtY?si=jZs9P69zOxAx5rY6

 

RANSAC의 장점 중 하나는 최적의 iteration number를 수학적으로 얻을 수 있다는 점임.

$$N = \frac{\log(1-p)}{\log(1-(1-e)^s)}$$ 

• $N$ : # of iterations
• $p$ : 오직, inlier로 이루어진 sample 을 얻을 확률
• $e$ : ratio of outliers in dataset
• $s$ : # of data sampled per single iteration

---

5. 장점과 단점

장점.

• Outlier에 강한 알고리즘 (RANSAC이 아직까지도 쓰이는 이유).
• 구현 등이 간단함.
• Image stitching 이나 homography에서 매우 쉽게 사용됨.

단점.

• Hyperparameter가 성능에 끼치는 영향을 보여줌.
• Non-deterministic (항상 같은 결과가 나오지 않음).
• Outlier에 강하나, 군집을 이루고 있는 Outlier가 존재(=특정 패턴을 따르는 outlier들로 구성된 그룹이 존재)한다면
  해당 Outlier의 군집의 패턴을 찾아냄. ***
• Gradient Based Algorithm이 아님: 일반적인 GD 기반의 framework등을 적용하기 어려움.

---

6. 같이 보면 좋은 자료들

가장 핵심적인 설명의 동영상.

https://youtu.be/4Dy_Hat63rE?si=exMR0y0ywMTUsRiA

 

좋은 한글자료.

https://gaussian37.github.io/vision-concept-ransac/

RANSAC (RANdom SAmple Consensus) 개념 및 실습

---