RANSAC (RANdom SAmple Consensus)는 많은 수의 이상치(outlier)가 있는 dataset에서도
model의 parameters를 강건하게 추정하는 voting based iteration algorithm.
RANSAC의 핵심 아이디어는
- voting (=inlier counting)을 사용하여
- 모델에 잘 맞는 데이터 포인트(inliers)와 맞지 않는 데이터 포인트(outliers)를 구별하는 것임.
RANSAC의 주요 특징:
- outliers 에 대해 robust!: RANSAC은 데이터셋에 많은 수의 이상치(특정 패턴이 없는)가 있는 상황에서 특히 효과적.
- 모델 추정 시간 단축: 데이터의 부분집합을 중심으로 작업하기 때문에 모델 파라미터를 추정하는 데 필요한 시간을 줄일 수 있음.
- 반복 알고리즘: 알고리즘은 hypothesizing 과 validation 과정을 반복.
- 투표 방식: 각 가설에 대해 인라이어의 수를 세어 최적의 모델을 결정하는 voting based algorithm.
Homography에서의 적용.
RANSAC (RANdom SAmple Consensus)는 이미지 Homography(호모그래피)를 추정할 때 매우 유용함.
RANSAC을 이용한 이미지 Homography(호모그래피) 추정 단계:
- Feature(특징) 추출:
- 두 이미지에서 Feature points(특징점)을 추출하는 단계임. 일반적으로 SIFT, SURF, ORB와 같은 알고리즘을 사용함.
- 잠재적인 Matching set(매칭 세트) 계산:
- 추출한 Feature points(특징점)을 기반으로 두 이미지 간의 잠재적인 Matching set(매칭 세트)을 계산하는 단계임. 이때 거리 기반 매칭 알고리즘(예: KNN)을 사용함.
- 반복 단계 (가설 생성 및 검증):
- 최소 Sample(샘플) 선택:
- 무작위로 최소 Sample(예: 4개의 점)을 선택하는 단계임.
- 이 4개의 점은 Homography matrix(행렬)을 추정하는 데 필요함.
- Homography(호모그래피) 계산:
- 선택된 Sample(샘플)을 사용하여 Homography matrix(행렬)을 계산하는 단계임.
- 오차 함수 계산 및 Inlier(인라이어) 식별:
- 계산된 Homography(호모그래피)를 사용하여 나머지 점들이 얼마나 잘 맞는지 평가하는 단계임.
- 특정 임계값 이하인 점들을 Inlier(인라이어)로 식별함.
- 비율 계산:
- Inlier(인라이어)의 비율을 계산하여 모델의 품질을 평가하는 단계임.
- 반복:
- 위 과정을 여러 번 반복하여
- 가장 많은 Inlier(인라이어)를 포함하는 Homography(호모그래피)를 찾음.
- 최소 Sample(샘플) 선택:
- 모든 Inlier(인라이어) 기반 Homography(호모그래피) 계산:
- 가장 많은 Inlier(인라이어)를 포함하는 최적의 모델을 선택한 후,
- 이 모델을 사용하여 모든 Inlier(인라이어)를 기반으로 Homography(호모그래피)를 다시 계산.
- 추가 Matching(매칭) 찾기:
- 4번에서 구한 최적의 Homography(호모그래피) 모델을 사용하여
- 추가적인 Matching(매칭)을 찾는 단계임.
- Homography(호모그래피) 정제:
- 모든 올바른 Matching(매칭)을 기반으로 Homography(호모그래피)를 정제하여
- 최종 Homography matrix(행렬)을 얻는 단계임.
예시:
- Feature 추출 및 Matching:
- 두 이미지에서 SIFT 알고리즘을 사용하여 Feature points(특징점)을 추출하는 단계임.
- KNN 매칭 등을 사용하여 잠재적인 Matching pairs(매칭 쌍)을 찾는 단계임.
- RANSAC 반복:
- 최소 Sample(샘플)(4개 점)을 무작위로 선택.
- 이 4개의 점을 사용하여 Homography matrix(행렬)을 계산.
- 계산된 Homography(호모그래피)를 기반으로 다른 점들을 평가하여 Inlier(인라이어)를 식별하고 카운트.
- 이 과정을 여러 번 반복하여 가장 많은 Inlier(인라이어)를 포함하는 Homography(호모그래피)를 찾는다.
- 최적의 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
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
장점과 단점
장점.
- Outlier에 강한 알고리즘 (RANSAC이 아직까지도 쓰이는 이유).
- 구현 등이 간단함.
- Image stitching 이나 homography에서 매우 쉽게 사용됨.
단점.
- Hyperparameter가 성능에 끼치는 영향을 보여줌.
- Non-deterministic (항상 같은 결과가 나오지 않음).
- Outlier에 강하나, 군집을 이루고 있는 Outlier가 존재(=특정 패턴을 따르는 outlier들로 구성된 그룹이 존재)한다면 해당 Outlier의 군집의 패턴을 찾아냄. ***
- Gradient Based Algorithm이 아님: 일반적인 GD 기반의 framework등을 적용하기 어려움.
- RANSAC 자체에에 대한 좋은 동영상.
같이 보면 좋은 자료들
가장 핵심적인 설명의 동영상.
https://youtu.be/4Dy_Hat63rE?si=exMR0y0ywMTUsRiA
좋은 한글자료.
'Programming > ML' 카테고리의 다른 글
[ML] Constrained Least Squares: Lagrangian 을 활용. (1) | 2024.07.16 |
---|---|
[Fitting] Total Least Square Regression (1) | 2024.06.22 |
[ML] Feature Scaling (0) | 2024.05.04 |
[ML] Underfit (0) | 2023.09.21 |
[Fitting] Ordinary Least Squares : OLS, 최소자승법 (0) | 2022.04.28 |