RANSAC
- 다른 이름: Random Sample Consensus
- 카테고리: Sensing › Perception outputs
- 태그: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus: 데이터의 작은 무작위 부분집합에 모델을 반복해서 맞추고 가장 많은 점과 일치하는 모델을 남겨 이상치를 무시하는 강건한 적합 방법.
정의
RANSAC(Random Sample Consensus)은 1981년 Fischler와 Bolles가 제안한 방법으로, 이상치가 많은 데이터에서 모델의 매개변수를 추정한다. 최소제곱 적합은 모든 점을 사용하므로, 몇 개의 큰 오류만으로도 결과가 실제 값에서 크게 벗어날 수 있다. RANSAC은 대신 단순한 루프를 반복한다. 모델을 정의하는 데 필요한 최소 개수의 점(직선은 두 개, 평면은 세 개, 카메라 자세나 기본 행렬은 작은 고정 개수)을 뽑아 모델을 맞추고, 전체 데이터 점 중 그 모델로부터 임계값 이내에 있는 점이 몇 개인지 센다. 그 점들이 합의 집합, 즉 인라이어다. 일정 횟수를 반복한 뒤 합의 집합이 가장 큰 모델을 남기며, 보통 그 모델의 모든 인라이어에 대해 최소제곱으로 다시 적합한다.
반복 횟수는 확률에서 나온다. w가 인라이어 비율이고 s가 샘플 크기이면, 무작위 샘플이 인라이어만 포함할 확률은 wˢ이므로, 신뢰도 p로 깨끗한 샘플을 적어도 하나 뽑는 데 필요한 반복 횟수 k는 k = log(1 − p) / log(1 − wˢ)이다. 이 값은 인라이어 비율이 떨어지거나 샘플 크기가 커지면 빠르게 증가한다. 그래서 5점 상대 자세처럼 더 적은 점으로 풀리는 최소 솔버가 비전에서 중요하다. 인라이어 임계값은 또 하나의 핵심 매개변수다. 임계값은 실제 인라이어의 예상 노이즈와 맞아야 하며, 측정하는 잔차의 단위로 설정해야 한다.
기본 루프를 개선한 변형이 많다. MSAC과 MLESAC은 단순한 인라이어 개수 대신 강건한 비용으로 가설에 점수를 매기고, PROSAC은 가장 유망한 매칭부터 샘플링하며, LO-RANSAC은 좋은 가설을 국소적으로 개선하고, 적응형 버전은 인라이어 비율이 추정되는 대로 k를 갱신한다. 로봇공학에서 RANSAC은 점군에서의 평면 및 기본 도형 분할, 시각 주행거리계와 SLAM에서의 특징 매칭 필터링, Perspective-n-Point 자세 추정, 특징 대응으로부터의 점군 정합, 그리고 캘리브레이션에 쓰인다. 절차가 무작위이므로, 난수 시드를 고정하지 않으면 실행마다 결과가 다를 수 있다.
중요한 이유
실제 센서 데이터에는 잘못된 특징 매칭, 반사, 움직이는 물체, 다른 표면에 속한 점 같은 이상치가 가득하다. RANSAC은 이런 이상치가 있어도 기하 모델을 맞추는 표준 방법이며, 대부분의 시각 주행거리계, SLAM, 캘리브레이션, 점군 분할 파이프라인 안에 들어 있다.
주요 응용
- 점군에서의 평면, 원기둥, 구 분할
- 시각 주행거리계와 SLAM에서 특징 매칭의 이상치 제거
- Perspective-n-Point를 이용한 카메라 자세 추정
- 기본 행렬, 본질 행렬, 호모그래피 행렬 추정
- 특징 대응으로부터의 전역 점군 정합
- 노이즈가 있는 센서 데이터에 직선과 캘리브레이션 모델 맞추기
실제 사례
모바일 매니퓰레이터가 물체를 놓기 전에 깊이 카메라 점군에서 탁자 상판을 찾아야 한다. 소프트웨어는 점군을 다운샘플링하고 RANSAC 평면 적합을 실행한다. 세 점을 반복해서 골라 그 점들을 지나는 평면을 계산하고, 센서의 깊이 노이즈보다 약간 크게 설정한 거리 임계값 안에 있는 점을 센다. 인라이어가 가장 많은 평면을 최소제곱으로 다시 적합하고, 그 인라이어를 제거한 뒤, 평면 위에 남은 점들을 군집화해 물체로 나눈다. 큰 벽이나 바닥이 시야에 있으면 RANSAC이 그 면을 대신 반환할 수 있으므로, 엔지니어들은 평면의 법선이 대략 위를 향하는지 확인하고, 결과를 재현할 수 있도록 테스트에서 난수 시드를 고정한다.
흔한 오해
- RANSAC은 최적 모델을 찾는다 — RANSAC은 우연히 샘플링한 가설 중 가장 좋은 것을 반환하므로, 결과는 확률적이며 실행마다 다를 수 있다
- 반복 횟수를 늘리면 나쁜 임계값을 보완할 수 있다 — 임계값은 무엇을 일치로 볼지 결정하므로, 잘못 고르면 반복을 아무리 많이 해도 결과가 치우친다
- RANSAC은 이상치 비율이 얼마든 감당한다 — 필요한 반복 횟수는 인라이어 비율이 떨어질수록 급격히 늘어나며, 인라이어가 매우 적으면 실패하거나 가짜 구조에 고정될 수 있다
- RANSAC은 모델을 하나만 찾을 수 있다 — 기본 알고리즘은 하나를 찾지만, 순차 변형과 다중 모델 변형은 인라이어를 제거하고 반복하여 여러 구조를 추출한다
알아야 할 사람
- 인식 및 컴퓨터 비전 엔지니어
- SLAM 및 시각 주행거리계 개발자
- 조작을 위해 점군을 처리하는 엔지니어
- 캘리브레이션 및 계측 엔지니어
관련 기술
- 최소제곱 적합(Least-Squares Fitting)
- M-추정량(M-Estimators)
- MSAC 및 MLESAC
- PROSAC
- 허프 변환(Hough Transform)
- Point Cloud Library
관련 용어
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
관련 프로젝트
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
동영상
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision