RANSAC

1. 개요[편집]

데이터의 90%가 쓰레기여도 좋다. 나머지 10%를 «우연히» 뽑을 때까지 주사위를 굴리면 되니까.

RANSAC(RANdom SAmple Consensus, 무작위 표본 합의)은 관측 대부분이 이상치(outlier)로 오염된 상황에서, 모형을 결정하는 데 필요한 «최소 개수»의 표본을 무작위로 반복 추출해 매번 모형을 세우고 그 모형에 동의하는 관측 수(합의집합, consensus set)를 세어, 가장 큰 합의를 얻은 모형을 채택하는 강건 추정 기법이다. 피슐러와 볼스가 1981년에 발표했고¹, 40년이 지난 지금도 컴퓨터 비전 파이프라인 어디를 들춰도 나온다.

발상의 전복이 통쾌하다. 최소자승법을 포함한 고전 추정은 가능한 한 많은 데이터로 시작해서 안 맞는 것을 하나씩 버린다. RANSAC은 정반대로 가능한 한 적은 데이터로 시작해서 맞는 것을 불려 나간다. 오염률이 30%만 넘어가도 전자는 이미 무너져 있는데, 후자는 90%에서도 (반복만 견디면) 산다. 제곱합 목적함수가 이상치 하나에 통째로 끌려가는 성질 — 잔차 제곱은 크기가 커질수록 영향력이 무한히 커진다 — 을 아예 회피해 버리는 설계다.

2. 절차[편집]

모형이 미지수 $s$개의 표본으로 유일하게 결정된다고 하자(직선이면 $s=2$, 평면이면 3, 호모그래피면 4).

1. 관측 $n$개 중 $s$개를 균등 무작위로 뽑는다(최소 표본, minimal sample).
2. 그 $s$개만으로 모형을 정확히 푼다. 최소자승이 아니라 연립방정식이다.
3. 전체 관측에 대해 잔차 $e_i$ 를 재고 $\lvert e_i \rvert < t$ 인 것을 내점(inlier)으로 세어 합의집합을 만든다.
4. 지금까지 중 합의집합이 가장 크면 그 모형과 내점 집합을 보관한다.
5. $N$번 반복한 뒤, 최선의 내점 집합 전체로 최소자승 재적합을 한다.

5단계를 빼먹는 구현이 의외로 많다. 최소 표본으로 푼 모형은 잡음이 그대로 전파돼 정밀도가 형편없으니, RANSAC은 최종 추정기가 아니라 이상치 판별기로 보고 마무리는 최소자승법이나 레벤버그-마쿼트 방법에 넘기는 것이 맞다.

왜 최소 표본인가? 표본이 클수록 그 안에 이상치가 하나라도 섞일 확률이 급격히 커지기 때문이다. 내점 비율이 $w$면 $s$개가 전부 내점일 확률은 $w^s$ — $s$가 지수로 들어간다. 정밀도를 위해 표본을 키우고 싶은 유혹은 여기서 정확히 반대 방향으로 작동한다.

3. 반복 횟수 — 왜 이만큼 굴리면 되는가[편집]

한 번의 추출이 «전부 내점»일 확률은 $w^s$이므로, $N$번 중 한 번이라도 깨끗한 표본이 나올 확률은 $1-(1-w^s)^N$ 이다. 이것이 목표 신뢰도 $p$ (보통 0.99) 이상이 되려면

$$N \;\ge\; \frac{\log(1-p)}{\log\!\left(1-w^{s}\right)}$$

이면 된다. 이 공식이 RANSAC의 전부이자, 이 방법이 «무한정 굴리는 노가다»가 아니라 정량적 보증이 있는 무작위 알고리즘인 이유다.

주목할 점은 $n$이 식에 없다는 것이다. 관측이 100개든 100만 개든 필요한 반복 횟수는 같다(한 번의 반복 비용은 $O(n)$ 이지만). 반면 $s$에는 지수적으로 민감하다. $p=0.99$ 기준으로 표를 그려 보면 실감난다.

$s$	대표 모형	$w=0.5$	$w=0.3$
2	2D 직선	17	49
3	3D 평면, 3점 강체정합	35	169
4	호모그래피, 3D 구	72	567
5	본질행렬(5점)	146	1,893
7	기초행렬(7점)	588	21,058
8	기초행렬(선형 8점)	1,177	70,186

기초행렬을 8점 선형 알고리즘으로 풀 때 최소 표본을 7이 아니라 8로 잡는 것만으로 반복이 두 배가 된다. 최소 표본 크기를 1 줄이는 논문이 왜 그렇게 많은지가 이 표에 다 있다.²

문제는 $w$를 미리 모른다는 것이다. 표준 처방은 적응적 갱신이다. $w$를 0(즉 $N=\infty$)으로 시작해, 반복할 때마다 지금까지 최선 모형의 내점 비율 $\hat w = \lvert \text{최선 합의집합} \rvert / n$ 로 $N$을 다시 계산하고, 실제 반복 수가 그 $N$을 넘으면 멈춘다. 오염이 심하면 알아서 오래 돌고, 데이터가 깨끗하면 열 번쯤 돌다 멈춘다. 파라미터 하나를 공짜로 없애는 트릭이라 어지간한 구현은 다 이걸 쓴다.

4. 임계값 $t$ — 유일하게 남는 손잡이[편집]

$t$는 「이 잔차면 내점으로 쳐 준다」는 경계다. 크게 잡으면 이상치가 섞여 들어와 모형이 끌려가고, 작게 잡으면 내점이 버려져 유효 $w$가 떨어지고 반복이 폭발한다. RANSAC 튜닝의 90%는 $t$ 하나다.

원칙적인 방법이 있다. 내점의 측정 잡음이 등방 가우시안 $\mathcal N(0, \sigma^2)$ 이라면 잔차의 제곱을 $\sigma^2$ 로 나눈 양은 자유도 $m$ 의 카이제곱 분포를 따르고($m$ = 잔차가 사는 공간의 차원, 즉 모형이 데이터 공간에서 갖는 여차원), 유의수준 $\alpha$ 로

$$t^2 \;=\; \chi^2_{m,\,\alpha}\,\sigma^2$$

로 잡으면 참 내점을 실수로 버릴 확률이 $1-\alpha$ 이하로 통제된다. $\alpha = 0.95$ 기준으로 자주 쓰이는 값은 두 개다.

• 점-직선 거리, 에피폴라 선까지의 거리처럼 잔차가 1차원이면 $m=1$, $\chi^2_{1,0.95}=3.84$ 이므로 $t = 1.96\,\sigma$.
• 호모그래피 전이 오차처럼 잔차가 2차원 벡터면 $m=2$, $\chi^2_{2,0.95}=5.99$ 이므로 $t = 2.45\,\sigma$.

물론 이 처방은 $\sigma$를 안다는 전제 위에 있고, 현실에서 $\sigma$는 대개 「픽셀 한두 개」 같은 감으로 정해진다. 이 마지막 임의성을 없애려는 것이 아래 MAGSAC 계열이다.

5. 붕괴점 — 50%의 벽을 넘는다는 것[편집]

강건 통계에서 붕괴점(breakdown point)은 추정량을 임의로 망가뜨리는 데 필요한 오염 비율의 최솟값이다. 최소자승법의 붕괴점은 $1/n$ — 관측 하나만 무한대로 보내면 추정값이 따라간다. 강건 추정량의 이론적 상한은 50%이고(오염이 절반을 넘으면 「어느 쪽이 참 모형인지」가 원리적으로 정의되지 않는다), 루소의 최소중앙제곱(LMedS, 1984)이 정확히 그 50%를 달성한다.³

RANSAC이 오염 90%에서도 동작한다는 말은 이 상한을 깼다는 뜻이 아니다. 정의가 다르다. RANSAC은 「이 임계값 안에 든 것이 참 모형」이라는 외부 정보($t$) 를 추가로 받고 있고, 그 대가로 50%를 넘어설 수 있다. 공짜가 아니라 정보를 주고 산 것이다. 세 계열을 나란히 놓으면 성격이 분명해진다.

방법	척도 정보	오염 한계	성격
최소자승	불필요	사실상 0	가우시안 가정 아래 최적, 이상치에 즉사
M-추정	척도 추정 필요	손실함수에 따라 중간	국소 최적화. 초기값이 나쁘면 엉뚱한 곳에 수렴
LMedS	불필요	50%	임계값이 없어 편하지만 가우시안에서 효율이 낮다
RANSAC	$t$ 필요	50% 초과 가능	반복 횟수가 대가. 임계값 민감

실무 조합은 대개 RANSAC으로 내점을 골라 초기값을 만들고, 로버스트 손실(후버·코시)로 재적합하는 2단이다. RANSAC은 전역 탐색을, M-추정은 국소 정련을 맡는 역할 분담이다. 이 조합이 점군 정합에서 전역 정합 → ICP 순서로 나타나는 것과 같은 구조다.

6. 변종 동물원[편집]

원본 RANSAC의 약점은 명확하다. 합의집합 크기만 세느라 잔차의 크기를 무시하고, 최소 표본만으로 세운 모형이라 좋은 표본을 뽑고도 점수를 낮게 받으며, 무작위 추출이라 좋은 후보를 먼저 볼 방법이 없다. 각 약점을 하나씩 때린 것이 변종들이다.

• MSAC / MLESAC(Torr & Zisserman, 2000) — 점수를 개수 대신 절단 잔차합으로 바꾼다. 내점은 $e^2$, 이상치는 상수 $t^2$ 를 비용으로 매기는 절단 이차 손실이라, 같은 개수여도 더 잘 맞는 모형이 이긴다. 공짜 개선이라(비용이 똑같다) MSAC은 사실상 RANSAC의 기본값이 됐다. MLESAC은 여기서 더 나아가 내점 가우시안 + 이상치 균등의 혼합 모형 우도를 최대화한다.
• LO-RANSAC(Chum, Matas, Kittler, 2003) — 새 최선 모형이 나올 때마다 그 내점 위에서 국소 최적화(내부 RANSAC + 반복 재가중 최소자승)를 한 번 돌린다. 이론상 반복 횟수와 실제 필요 반복이 어긋나는 현상(이론보다 훨씬 더 돌려야 하는 문제)을 크게 줄인다.
• PROSAC(Chum & Matas, 2005) — 특징점 매칭 점수처럼 품질 순서가 있으면 상위 후보부터 뽑는다. 좋은 매칭이 정말로 좋으면 몇 번 만에 끝나고, 아니면 서서히 표본 풀을 넓혀 결국 균등 RANSAC으로 수렴한다. 최악의 경우가 원본과 같으면서 평균이 훨씬 빠른, 이상적인 형태의 개선.
• USAC(Raguram 외, 2013) — 위 아이디어들(샘플링·축퇴 검사·조기 종료·국소 최적화)을 하나의 프레임워크로 묶은 통합판.
• MAGSAC / MAGSAC++(Barath 외, 2019/2020) — $\sigma$를 주변화(marginalize)해 임계값 자체를 없앤다. 여러 $\sigma$ 가정에 대한 점수를 가중 평균한 «$\sigma$-합의»를 쓰고, MAGSAC++는 이를 반복 재가중 최소자승 형태로 다시 써서 빠르게 만들었다. OpenCV의 USAC_MAGSAC 이 이것이다.⁴

7. 어디에 쓰이나[편집]

• 다시점 기하. 두 영상의 특징점 매칭에는 오대응이 절반 넘게 섞이는 것이 정상이다. 호모그래피(평면 장면·순수 회전, 최소 4점), 기초행렬(비보정 카메라, 최소 7점 — 선형 8점 알고리즘을 쓰면 8점), 본질행렬(보정 카메라, 니스테르의 5점 알고리즘)을 RANSAC 안에서 푸는 것이 에피폴라 기하 추정의 표준 절차다. 여기서 축퇴(degeneracy)가 큰 함정인데, 장면에 지배적인 평면이 있으면 전부 내점인 표본에서도 기초행렬이 결정되지 않아 엉뚱한 답이 높은 점수를 받는다. 그래서 축퇴 검사를 넣은 DEGENSAC 같은 변종이 따로 있다.
• 점군의 형상 추출. 3점으로 평면, 4점으로 구, 법선까지 쓰면 2점으로 원기둥을 세울 수 있다. 슈나벨 등(2007)의 효율적 RANSAC이 CAD 역설계와 건물 스캔 분할의 사실상 표준이 됐다.
• 라이다 지면 분할. 지면을 평면 하나로 보고 RANSAC으로 뽑아 제거하면 남는 것이 장애물이다. 자율주행 인지 파이프라인 맨 앞에 거의 항상 들어 있는, 가장 흔한 실전 사용례.
• 점군 정합의 전역 초기화. FPFH 같은 기하 서술자로 만든 대응 후보에서 3쌍을 뽑아 강체변환을 세우고 합의를 세는 방식으로 ICP의 초기값을 만든다.

8. 쓸 때 밟는 지뢰[편집]

1. 재적합을 잊지 않는다. 최소 표본 모형은 최종 답이 아니다.
2. 축퇴를 검사한다. 직선 위 3점으로 평면을 세우거나, 거의 공선인 4점으로 호모그래피를 세우면 수치적으로 폭발한다. 표본을 뽑자마자 조건수나 면적을 보고 버려라.
3. $t$를 데이터 스케일에 묶는다. 좌표를 정규화하지 않은 채 절대 픽셀값으로 $t$를 고정하면 영상 해상도가 바뀔 때마다 결과가 바뀐다.
4. 결과가 실행마다 다르다. 무작위 알고리즘이니 당연하다. 재현이 필요하면 시드를 고정하고, 리포트에는 여러 번 돌린 분포를 쓴다. 「한 번 돌렸더니 잘 됐다」는 RANSAC에서 가장 위험한 문장이다.
5. $w$가 아주 작으면 포기가 답일 수 있다. $s=7$, $w=0.1$ 이면 필요한 반복이 수천만 회다. 이 지경이면 RANSAC을 더 돌릴 게 아니라 매칭 단계를 고쳐 $w$를 올리는 것이 정답이다.

9. 관련 문서[편집]

• 최소자승법 · 로버스트 통계 · 레벤버그-마쿼트 방법
• 점군 정합 · KD-트리 · 최근접 이웃 탐색
• 호모그래피 · 에피폴라 기하 · 허프 변환
• 에지 검출 · 이미지 분할 · 스케일 공간
• 몬테카를로 방법 · 부트스트랩
• 특이값 분해 · 가우스-뉴턴법

10. Footnotes[편집]

1. Fischler, M. A. & Bolles, R. C. (1981). “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography.” CACM 24(6). 부제의 «자동 지도제작»이 말해 주듯 원래 동기는 항공사진에서 지상기준점을 찾는 일이었다. 태어난 곳은 측량이고, 자란 곳은 컴퓨터 비전이다. ↩

2. 니스테르의 5점 알고리즘(2004)이 대표적이다. 10차 다항식의 근을 구하는 꽤 험한 계산을 감수하면서까지 표본을 6에서 5로 줄인 이유는 오직 하나 — 표에 있는 저 지수 때문이다. $w=0.3$ 에서 5점과 6점의 반복 수 차이는 대략 세 배가 넘는다. ↩

3. LMedS가 임계값 없이 동작하는 비결은 «잔차의 중앙값을 최소화한다»는 목적 자체가 척도에 대해 자기완결적이기 때문이다. 대신 정확히 50%가 한계라, 오염이 51%면 «이상치들이 이루는 모형»을 당당하게 답으로 내놓는다. 그럴듯한 답을 자신 있게 내놓는 실패 모드가 제일 무섭다. ↩

4. OpenCV의 findHomography·findFundamentalMat 기본 반복 상한이 2000인 것도 이 표와 무관하지 않다. 그런데 사람들은 대개 기본값을 안 건드리고, 그래서 오염이 심한 데이터에서 조용히 실패한 결과를 그대로 다음 단계로 흘려보낸다. 「내점이 몇 개 나왔나」를 찍어 보는 습관이 디버깅 시간의 절반을 아낀다. ↩