RANSAC (Random Sample Consensus) 개념 및 실습
RANSAC 이란
RANSAC(Random Sample Consensus)는 데이터를 최소한의 random sample로 모델을 fitting하여, 전체 데이터에서 가장 적절한 모델을 반복하여, 찾는 알고리즘이다.
RANSAC의 필요성
- outlier가 많은 상황에서도 안정적인 파라미터 추정이 가능하다.
- 구현이 단순하고 응용이 쉽다.
- 선형/다항/비선형 등 다양한 모델과 결합 가능하다.
RANSAC 개념
데이터에서 최소표본 크기 $s$개를 무작위로 뽑아 모델 $\theta$를 추정하고, 에러 $e(x,\theta)$가 임곗값 $\tau$ 이하인 점들의 집합 $\mathcal I(\theta)$ 크기를 평가한다. 가장 큰 $\lvert \mathcal I \rvert$를 주는 $\theta^\ast$를 기록하면서 반복하고, 마지막에 $\mathcal I(\theta^\ast)$만으로 재추정(refit)해 정밀도를 높인다.
RANSAC의 파라미터 셋팅법
성공확률과 반복횟수
inlier 비율을 $\eta$, 최소표본 크기를 $s$, 목표 신뢰도 $p$라 하면, 필요한 반복 횟수 $N$는
\[\begin{aligned} N= \frac{\log(1-p)}{\log(1-\eta^s)} \end{aligned}\]$\eta$를 모르면 보수적으로 0.5부터 가정하고, 반복 중 $\hat\eta = \lvert \mathcal I \rvert/\lvert \mathcal D \rvert$로 $N$을 동적 갱신하면 평균 연산량을 크게 줄일 수 있다.
임곗값
센서/피처 잔차의 표준편차 $\sigma$가 알려졌다면 보통 $\tau \approx k\sigma$ ($k=2\sim3$). 픽셀/미터 등 단위가 섞이는 문제를 피하려면 기하적으로 의미 있는 에러(예: 수선거리, 리프로젝션 에러, Sampson 에러)를 사용한다.
최소표본 크기 s
가능한 “최소”가 유리하다. 선형 s=2s=2, 2차 다항식 s=3s=3, 평면 s=3s=3등. 단, 퇴화(degeneracy)를 피하기 위한 샘플 간격/기하 제약을 두는 것이 좋다.
Early Stop 사용법
- min_iterations: 너무 이르게 종료하지 않도록 하는 최소 반복횟수
- max_iterations: $N$ 공식을 기반으로 설정.
- stop_inlier_ratio: $\lvert \mathcal I \rvert/\lvert \mathcal D \rvert$ 가 이 비율을 넘으면 즉시 종료. 실전에서는 min을 작게, stop 비율을 보수적으로 두고, 좋은 모델이 나오면 즉시 끝내는 것이 빠르고 효과적이다.
RANSAC의 장단점
장점
- 이상치에 매우 강건.
- 구현과 이식이 쉬움.
단점/주의
- 난수성으로 재현성 관리가 필요(시드 고정).
- $\tau$에 민감. 너무 작으면 inlier 과소평가, 너무 크면 outlier 유입.
- 특정 구조적 outlier(편향 분포)가 많으면 그 분포를 적합해버릴 수 있음 → 사전 필터링/검정 필요.
RANSAC Python Code (다항식 예제)
import numpy as np
from numpy.typing import ArrayLike
from dataclasses import dataclass
from typing import Tuple, Optional
@dataclass
class RansacResult:
coeffs: np.ndarray # np.polyfit 계수 (고차항이 앞)
inlier_idx: np.ndarray # inlier 인덱스 (bool mask 또는 정수 배열)
tau: float # 사용한 임곗값
iterations: int # 실제 반복 횟수
inlier_ratio: float # 최종 inlier 비율
def _poly_fit_safe(x: np.ndarray, y: np.ndarray, deg: int) -> Optional[np.ndarray]:
try:
return np.polyfit(x, y, deg)
except np.linalg.LinAlgError:
return None
def ransac_polyfit(
x: ArrayLike,
y: ArrayLike,
deg: int,
tau: float,
p: float = 0.99,
min_iterations: int = 0,
max_iterations: Optional[int] = None,
stop_inlier_ratio: Optional[float] = None,
rng: Optional[np.random.Generator] = np.random.default_rng(0),
) -> RansacResult:
"""
RANSAC으로 1D 다항식을 추정한다. error는 |y - polyval(c, x)|.
Parameters
----------
deg : 다항 차수 (선형=1, 이차=2, …)
tau : inlier 임곗값
p : 원하는 신뢰도
min_iterations, max_iterations, stop_inlier_ratio : Early stop 제어
"""
x = np.asarray(x).ravel()
y = np.asarray(y).ravel()
n = x.size
s = deg + 1 # 최소표본 크기
# 초기 inlier 비율 가정으로 N 계산
if max_iterations is None:
eta_guess = 0.5
max_iterations = int(np.ceil(np.log(1 - p) / np.log(1 - eta_guess**s)))
max_iterations = max(max_iterations, 100)
best_coeffs = None
best_inliers = None
best_count = -1
N = max_iterations
for it in range(N):
# 무작위 최소 샘플
idx = rng.choice(n, size=s, replace=False)
coeffs = _poly_fit_safe(x[idx], y[idx], deg)
if coeffs is None:
continue
y_pred = np.polyval(coeffs, x)
resid = np.abs(y - y_pred)
inliers = resid <= tau
count = int(inliers.sum())
# 최고 기록 갱신
if count > best_count:
best_count = count
best_inliers = inliers
best_coeffs = coeffs
# 동적 N 갱신
eta_hat = np.clip(best_count / n, 1e-6, 0.999)
N_new = int(np.ceil(np.log(1 - p) / np.log(1 - eta_hat**s)))
N = min(N, max(N_new, it + 1))
# early stop
if it + 1 >= max(min_iterations, 1) and stop_inlier_ratio is not None:
if eta_hat >= stop_inlier_ratio:
break
# 리피팅(정제): inlier만으로 재적합
if best_inliers is None or best_count < s:
raise RuntimeError("유효한 모델을 찾지 못했습니다.")
coeffs_refined = np.polyfit(x[best_inliers], y[best_inliers], deg)
inlier_ratio = float(best_inliers.mean())
return RansacResult(coeffs_refined, np.where(best_inliers)[0], tau, it + 1, inlier_ratio)
사용 예시
# 예제 데이터
rng = np.random.default_rng(42)
X = np.linspace(-10, 10, 200)
Y_true = 2*X + 5
Y = Y_true + rng.normal(0, 1.0, size=X.size)
# outlier 추가
out_idx = rng.choice(X.size, size=40, replace=False)
Y[out_idx] += rng.normal(0, 15.0, size=out_idx.size)
res = ransac_polyfit(
X, Y, deg=1, tau=3.0, p=0.99,
stop_inlier_ratio=0.7, rng=rng
)
print(res.coeffs, res.inlier_ratio, res.iterations)
---
[1.99085194 4.9955631 ] 0.82 1
시각화
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 6))
plt.scatter(X, Y, label='Original Data', alpha=0.6)
plt.plot(X, Y_true, 'r--', label='True Line')
# Plot the RANSAC fitted line
X_fit = np.linspace(X.min(), X.max(), 100)
Y_fit = np.polyval(res.coeffs, X_fit)
plt.plot(X_fit, Y_fit, 'g-', label='RANSAC Fitted Line')
# Highlight inliers
plt.scatter(X[res.inlier_idx], Y[res.inlier_idx], color='cyan', label='RANSAC Inliers')
plt.xlabel('X')
plt.ylabel('Y')
plt.title('RANSAC Polynomial Fit')
plt.legend()
plt.grid(True)
plt.show()
Lo-RANSAC 개념
기본 RANSAC은 “전 데이터”에서만 반복 샘플링한다. LO-RANSAC(Locally Optimized RANSAC)은 최고 모델이 갱신될 때마다 그 inlier 집합 안에서 한 번 더 샘플링/재적합(내부 RANSAC)하고, 이어서 inlier 전부를 사용한 로컬 최적화(예: 최소제곱/LM)를 수행해 품질과 수렴속도를 끌어올리는 기법이다. 좋은 결과가 나왔을때, 주변(local)에서 더 파고드는 전략이다.
Lo-RANSAC Python Code (다항식 예제)
from typing import Callable
def lo_ransac_polyfit(
x: ArrayLike,
y: ArrayLike,
deg: int,
tau: float,
p: float = 0.99,
min_iterations: int = 0,
max_iterations: Optional[int] = None,
stop_inlier_ratio: Optional[float] = None,
rng: Optional[np.random.Generator] = np.random.default_rng(0),
) -> RansacResult:
"""
LO-RANSAC: 최고 모델이 갱신될 때 inlier 집합 내에서 추가 샘플링 후,
inlier 전체로 로컬 정제를 수행한다.
"""
# 1) 바깥 RANSAC 한 번 수행 (초기 해)
outer = ransac_polyfit(
x, y, deg, tau, p, min_iterations, max_iterations, stop_inlier_ratio, rng
)
X = np.asarray(x).ravel()
Y = np.asarray(y).ravel()
n = X.size
s = deg + 1
best_coeffs = outer.coeffs.copy()
y_pred = np.polyval(best_coeffs, X)
inliers = np.abs(Y - y_pred) <= tau
best_inliers = inliers
best_count = int(inliers.sum())
# 2) inlier 집합에서 한 번 더 RANSAC
if best_count >= s:
idx_in = np.where(inliers)[0]
# 내부 반복 횟수: inlier 비율 기반으로 축소
eta = best_count / n
if max_iterations is None:
N_inner = int(np.ceil(np.log(1 - p) / np.log(1 - max(eta,1e-3)**s)))
N_inner = max(min(N_inner, 200), 50)
else:
N_inner = max_iterations // 3
for _ in range(N_inner):
if idx_in.size < s:
break
sub = rng.choice(idx_in, size=s, replace=False)
coeffs = _poly_fit_safe(X[sub], Y[sub], deg)
if coeffs is None:
continue
resid = np.abs(Y - np.polyval(coeffs, X))
in2 = resid <= tau
cnt2 = int(in2.sum())
if cnt2 > best_count:
best_count = cnt2
best_inliers = in2
best_coeffs = coeffs
# 3) 로컬 최적화: inlier 전체로 재적합(+옵션: 가중 최소제곱/Huber)
if best_inliers.sum() >= s:
best_coeffs = np.polyfit(X[best_inliers], Y[best_inliers], deg)
return RansacResult(best_coeffs, np.where(best_inliers)[0], tau, outer.iterations, best_inliers.mean())
언제 LO-RANSAC이 이득인가
- inlier가 한 덩어리로 잘 모여 있고, 한 번 모델이 크게 갱신된 후 그 주변 탐색이 유의미할 때. Early stop과 결합하면 전체 반복 수가 줄면서 정확도는 올라간다.