PROSAC

Chum과 Matas(2005)가 제안한 **PROSAC (Progressive Sample Consensus)**은, 일반 RANSAC이 버리는 한 가지 사실을 활용하는 RANSAC 변형이다: 대응점은 인라이어일 가능성이 동일하지 않으며, 우리는 보통 이를 예측하는 매칭별 품질 점수 — 디스크립터 거리, 또는 더 좋게는 최근접 이웃과 두 번째 최근접 이웃 사이의 거리 비율인 Lowe의 비율 $d_1 / d_2$ — 를 가지고 있다는 것이다.

아이디어

$n$ 개의 후보 대응점을 품질이 높은 순으로 정렬한다. 모든 $n$ 개의 매칭에서 최소 집합을 균일하게 샘플링하는 대신, PROSAC은 상위 순위 매칭들의 점진적으로 성장하는 부분집합에서 샘플을 뽑는다:

초기 반복에서는 인라이어 밀도가 가장 높은, 최상위 소수의 매칭에서만 샘플링한다(예: 상위 $s+1$ 개, 그 다음 상위 $s+2$ 개, …).
반복이 진행됨에 따라 샘플링 풀은 전체 집합을 향해 커지므로, 극한에서 PROSAC의 샘플링 분포는 모든 매칭에 대한 균일 샘플링으로 수렴한다.

형식적으로는, 성장 함수(growth function)가 풀 크기가 $m$ 에서 $m+1$ 로 증가하기까지 몇 번의 샘플링이 필요한지를 결정한다; 각 샘플은 새로 추가된 매칭 하나와, 상위 $m$ 개에서 뽑힌 $s-1$ 개의 매칭으로 구성된다. 설계 목표는 PROSAC이 RANSAC이 뽑을 것과 (근사적으로) 동일한 샘플 집합을 뽑되, 다른, 품질 기반의 순서로 — 가장 유망한 것부터 — 뽑는 것이다.

알고리즘 개요

대응점을 품질 점수가 높은 순으로 정렬한다.
현재 풀 크기 $m$ (초기값 $m = s$ )과 그 성장 스케줄을 유지한다.
각 반복마다 위에서 설명한 대로 상위 $m$ 개의 매칭으로부터 최소 샘플을 구성하고, 모델을 피팅한 후 전체 $n$ 개의 대응점에 대해 검증한다.
인라이어 개수로 최적 모델을 추적하며, RANSAC 방식의 신뢰도 기준(무작위가 아닌 인라이어 개수와, 현재 인라이어 비율 추정에 충분한 샘플 수)이 충족되면 종료한다.
표준 RANSAC과 마찬가지로, 모든 인라이어에 대해 최소제곱법으로 재적합(refit)한다.

특성

속도: 품질 순위가 유용한 정보를 담고 있을 때(즉, 상위 매칭들이 실제로 대부분 인라이어일 때), 전체 인라이어 샘플은 처음 몇십 번의 시도 안에 발견되며, 이는 전체 인라이어 비율이 낮을 때 균일 RANSAC보다 몇 자릿수 더 빠르다. 전체 인라이어 비율 $w$ 가 매우 낮더라도(예: 10%), 상위 20개 매칭은 90%가 인라이어일 수 있다 — PROSAC이 초기 풀에서 얻는 실효 $w^s$ 는 극적으로 더 높다.
최악의 경우에도 동일한 보장: 점수가 유용한 정보를 담지 않는다면, PROSAC은 표준 RANSAC 동작으로 우아하게 저하되며, 동일한 종료 기준을 유지한다

P(\text{success}) = 1 - (1 - w^s)^N \geq 1 - \eta

동일한 검증 단계: 가설은 여전히 모든 대응점에 대한 인라이어 합의로 평가되므로, 편향된 샘플링 풀이 최종 모델 선택을 편향시키지 않는다.

실용적 노트

품질 척도가 중요하다: Lowe 비율은 원시 디스크립터 거리보다 훨씬 더 나은 인라이어 예측 지표다.
PROSAC은 적응형 종료와 자연스럽게 결합된다 — 가장 먼저 발견된 좋은 모델이 필요한 반복 횟수를 즉시 줄여준다.
OpenCV는 findEssentialMat, findHomography, solvePnPRansac 등에 대해 USAC 프레임워크(cv::USAC_PROSAC)에서 PROSAC 방식 샘플링을 제공한다.
초기 풀의 퇴화(degenerate)에 주의하라: 상위 순위 매칭들은 흔히 텍스처가 강한 하나의 물체나 평면에 집중되는데, 이는 지역적으로는 일관되지만 전역적으로는 잘못된 모델(예: 본질 행렬을 원했는데 하나의 평면에 대한 호모그래피)을 낳을 수 있다; 퇴화 검사는 여전히 적용된다.

SLAM에서의 의미

실시간 예산은 빠듯하다: 추적은 30–60 Hz로 실행되며, 기하학적 검증은 밀리초 단위로 끝나야 한다. PROSAC은 일반적인 장면에서 훨씬 적은 반복으로 RANSAC 수준의 이상치 제거를 제공한다.
SLAM 프론트엔드는 매칭 과정에서 필요한 매칭 점수(디스크립터 거리, 비율 테스트 값)를 이미 계산하므로, 순위 정보는 공짜로 얻어진다.
특히 재위치추정(relocalization)과 루프 클로징에서 가치가 크다. 이 경우 후보 매칭 집합이 크고 심하게 오염되어 있어, 균일 RANSAC은 수천 번의 반복이 필요하다.

PROSAC

아이디어

알고리즘 개요

특성

실용적 노트

SLAM에서의 의미

관련 문서