RANSAC

Fischler와 Bolles가 1981년에 도입한 **RANSAC (Random Sample Consensus)**은 SLAM과 다중 뷰 기하학에서 지배적인 강건 추정 방법이다. 이는 거짓 특징 매칭, 가림, 움직이는 물체 같은 이상치로 오염된 데이터에 파라메트릭 모델(본질 행렬, 호모그래피, 카메라 자세, 평면 등)을 적합시키는데, 작은 무작위 샘플로부터 모델을 반복적으로 가정하고 이를 합의(consensus)로 평가하는 방식을 사용한다.

알고리즘

1. $s$개의 대응점으로 이루어진 최소 샘플 $S$를 균일한 무작위로 뽑는다($s$는 모델을 결정하는 데 필요한 최소 개수: 본질 행렬은 5점, 호모그래피는 4점, P3P는 3점, 선형 8점 알고리즘을 사용하는 기본 행렬은 8점).
2. 샘플에 모델 $\theta_S$를 적합시킨다.
3. 인라이어를 센다: 오차 임계값 $\epsilon$ 이내에서 $\theta_S$와 일치하는 데이터 점들(예: 샘슨 거리 또는 몇 픽셀의 재투영 오차).
4. $N$번 반복하며, 가장 큰 인라이어 집합을 갖는 모델을 유지한다.
5. 선택적으로, 모든 인라이어에 대해 최소제곱법으로 모델을 재적합한다(그리고 종종 재적합을 반복한다).

핵심 통찰: 이상치가 50%라 해도, 충분히 여러 번 시도하면 상당한 확률로 전부 인라이어인 작은 샘플이 뽑히며, 올바른 모델은 오염된 샘플에 적합된 모델보다 훨씬 더 많은 합의를 모은다.

몇 번 반복해야 하는가?

인라이어 비율을 $w$라 하자. $s$개의 점으로 이루어진 하나의 샘플이 전부 인라이어일 확률은 $w^s$이므로, $N$개의 샘플 중 적어도 하나가 전부 인라이어일 확률은

$P(\text{success}) \geq 1 - \eta$(예: 99% 신뢰도를 위한 $\eta = 0.01$)를 요구하면 다음이 얻어진다

$w = 0.5$, $\eta = 0.01$에서의 예:

반복 횟수는 샘플 크기에 대해 지수적으로 증가한다 — 이것이 바로 최소 솔버(5점 E, P3P)가 RANSAC 안에서 더 큰 선형 솔버보다 선호되는 이유다.

적응형 RANSAC은 $N$을 미리 고정하지 않는다: 지금까지 발견된 최적 인라이어 집합으로부터 $w$를 다시 추정하고, $N$을 재계산하며, 현재 추정치에 충분한 샘플이 뽑히면 조기에 종료한다 — 보통 쉬운 장면에서는 훨씬 적은 반복으로 끝난다.

실용적 노트

• 임계값 $\epsilon$은 측정 잡음(픽셀)을 반영해야 한다; 너무 엄격하면 좋은 데이터를 거부하고, 너무 느슨하면 이상치를 받아들인다.
• 퇴화된 샘플(일부 모델에서 공선/공면인 점들)은 감지되어 다시 뽑혀야 한다.
• 변형: PROSAC(품질 순위가 매겨진 매칭을 먼저 샘플링), LO-RANSAC(유망한 모델의 지역 최적화), MLESAC(인라이어 개수 대신 우도로 평가), 그리고 MaxCon 합의 최대화 같은 전역적으로 최적인 대안들.
• RANSAC 이후 남아있는 작은 오차는 비선형 정제(refinement) 내부의 M-추정기/강건 커널로 처리된다.

SLAM에서의 의미

• 특징 기반 파이프라인의 모든 기하학적 추정 단계는 RANSAC 안에서 실행된다: 초기화와 2D–2D 운동을 위한 본질/기본 행렬, 평면 장면을 위한 호모그래피, 추적과 재위치추정을 위한 PnP, ICP 대응점 정리, 그리고 루프 클로저 검증.
• 디스크립터 매칭 단독으로는 20–50%의 잘못된 매칭이 일상적으로 발생한다; RANSAC이 없다면 최소제곱 추정치는 임의로 오염될 것이다(최소제곱법은 이상치에 대한 붕괴 허용도가 0이다).
• 장소 인식으로부터 얻어진 루프 클로저 후보는 포즈 그래프에 추가되기 전에 RANSAC으로 기하학적으로 검증된다 — 하나의 거짓 루프 제약이 전체 맵을 파괴할 수 있다.

실습

• RANSAC 실습

관련 문서

• PROSAC
• PnP (Perspective-n-Point)
• M-estimator
• MaxCon
• Epipolar geometry