RANSAC

RANSAC

개요

• RANSAC(RANdom SAmple Consensus) 은 관측 데이터에 노이즈나 이상치(outlier)가 많이 포함되어 있을 때, 델의 강인한(robust) 파라미터 추정을 가능하게 하는 반복적 최적화 알고리즘.
• 최소자승법(Least Square) 과 달리, 전체 데이터를 모두 신뢰하지 않고 반복적으로 랜덤하게 선택한 소수의 샘플(subset) 로 모델을 가설(hypothesis) 형태로 생성한 뒤, 나머지 데이터 중 해당 모델과 일치하는 inlier의 수를 평가하여 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법.
• 직선/평면 추정, 호모그래피 추정, 기본 행렬 추정 등 컴퓨터 비전 및 로보틱스 분야에서 널리 사용되며, 다양한 변형 알고리즘(MLESAC, MSAC, LO-RANSAC 등)을 통해 성능이 확장됨.

무작위(Random)로 일부 데이터(Sample)를 뽑아 단일 모델을 추정하고, 이를 반복해 그중 가장 합의(Consensus)된 모델을 찾는 알고리즘

필요성

• 아래 포물선 예시에서, 실제 관측 데이터가 일정한 노이즈(가우시안 등)를 띄고 있는 형태에서는 최소자승법을 적용하면 훌륭한 결과를 얻을 수 있다.
• 하지만, 균일한 노이즈가 아니라 데이터가 이상적인 분포에서 벗어난 이상점(outlier)이 포함되어 있으면 최소자승법은 전체 데이터를 모두 고려하므로 아래와 같이 이상적인 결과가 나오지 않는다.
• 그런데, 이것을 outlier에 강건한 RANSAC을 사용하면 아래와 같이 이상적인 결과를 얻을 수 있다.
• 즉, RANSAC은 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법이다.

---

RANSAC 알고리즘

알고리즘 구조

• 아래 두가지 단계를 반복하여 진행함.

Hypothesis - 가설 단계

• 전체 데이터에서 n개의 샘플을 선택하고, 선택된 샘플 데이터를 inlier로 가정하고 모델 파라미터 예측.

Verification - 검증단계

• 데이터셋에서 예측된 모델과 일치하는 데이터의 수를 센 후, 최대 값일 경우 모델 파라미터를 새롭게 저장한다.

알고리즘 과정

1. 입력 데이터 준비

• 관측 데이터 집합 $D=\{x_1,x_2,\dots ,x_n\}$ 에서 모델을 결정하기 위한 최소 샘플 개수 $s$ 를 정의함.
• 예를 들어, 직선 모델은 최소 2개의 샘플이 필요하며, 평면은 3개, 호모그래피는 4개의 샘플이 필요함.
• 이때, 필요 이상으로 샘플 수를 늘리면 outlier를 포함할 확률이 폭증하고 가설 모델 대부분이 망가지기 때문에 RANSAC 효율이 급격히 떨어짐.

2. 랜덤 최소 샘플 선택

• 전체 데이터 중에서 랜덤으로 최소 샘플 $s$개를 선택함.

3. 모델 파라미터 추정

• 선택된 샘플로부터 모델 파라미터(직선의 기울기, 호모그래피 행렬 등)을 계산한다.
• 이 단계에서 계산된 모델은 “가설 모델(hypothesis model)“이다.

4. 모델 평가

• 전체 데이터에 대해 다음을 수행한다.
  1. 각 데이터 포인트와 모델 사이의 오차(error) 계산
  2. 오차가 threshold 이하라면 inliner로 분류
• 이렇게 얻은 inlier 개수 $I$를 저장함.

5. 최적 모델 업데이트

• 지금까지 중 가장 많은 inlier 수를 갖는 모델을 최적 모델로 유지함.
• 경우에 따라 inlier 집합으로 모델을 다시 최적화(refit)할 수도 있음. (LO-RANSAC 같은 변형에서 수행)

6. 반복 종료 조건 확인

• 다음 중 하나가 만족하면 반복을 종료한다.
  1. 최대 반복 횟수 $N_{iter}$에 도달
  2. 충분히 많은 inlier를 찾았음

하이퍼파라미터의 설정

• RANSAC 하이퍼파라미터는 경험적으로 정하는 경우가 많지만, 이론적 근거를 바탕으로 수학적으로 최적화가 가능하다.
• RANSAC이 성공하기 위해서는 N번의 시도 중 적어도 한번은 inlier들에서만 샘플 데이터가 뽑혀야 하며, 이러한 확률은 N을 키우면 키울수록 증가할 것이지만 무한정 RANSAC을 돌릴 수는 없기 때문에 확률적으로 반복 횟수를 결정한다.
• 반복횟수 $N$ 번 중 적어도 한번은 inlier에서만 샘플이 뽑힐 확률 $p$는 다음과 같다.

$$\begin{array}{r}\\ p=1-(1-{\alpha }^s{)}^N\\ \end{array}$$

• $\alpha$ : 전체 데이터에서 inlier의 비율
• $s$ : 최소 샘플 개수
• 이때, $N$은 다음과 같이 표현 할 수 있다.

$$\begin{array}{rl}& \\ p=& 1-(1-{\alpha }^s{)}^N\\ & \\ 1-p& =(1-{\alpha }^s{)}^N\\ & \\ \log (1-p)& =\log ((1-{\alpha }^s{)}^N)\\ & \\ \log (1-p)& =N\log (1-{\alpha }^s)\\ & \\ N& =\frac{\log (1-p)}{\log (1-{\alpha }^s)}\\ & \end{array}$$

• 위 식을 토대로, 만약 inlier의 비율이 0.8 이고, 성공확률을 0.999 로 맞추려면 반복횟수 $N$은 아래와 같이 계산된다.

$$N=\frac{\log (1-0.999)}{\log (1-0.8^s)}=9.6283$$

• 수학적 확률로는 10번 정도 반복하면 99.9%의 확률로 해를 찾을 수 있다는 해석이지만, 이는 이상치(outlier)와 inlier를 완벽히 구분할 수 있다고 가정한 값이며, 랜덤 샘플링의 특징으로 인해 확신할 수는 없다.
• inlier 를 판단하는 임계값인 $T$ 의 경우 너무 크게하면 모델간의 변별력이 없어지고, 너무 작게하면 알고리즘이 불안정해지므로 데이터의 경향을 보고 적절한 값을 설정해야한다.
• 일반적인 방법으로 inlier들의 residual 분산을 ${\sigma }^2$ 이라 할때, $T=2\sigma$ 또는 $3\sigma$ 로 설정한다. (미리 inlier 데이터들 만의 residual을 구해야함)

---

Code (Python - Numpy)

2D Line Fitting

• 모델 : $ax+by+c=0$ 형태의 직선 방정식
• 오차 : 점과 직선 사이 거리

import numpy as np
 
def ransac_line_fitting(points, iter=1000, threshold=1.0):
    """
    points: (N, 2) numpy array
    """
    best_inliers = []
    N = len(points)
 
    for _ in range(iter):
        # 1. 최소 샘플 2개 선택
        idx = np.random.choice(N, 2, replace=False)
        p1, p2 = points[idx]
 
        # 2. 직선 모델 파라미터 계산 (ax + by + c = 0)
        x1, y1 = p1
        x2, y2 = p2
        
        # 직선 계수 (두 점을 지나는 직선)
        a = y2 - y1
        b = x1 - x2
        c = x2*y1 - x1*y2
        
        # 정규화
        norm = np.sqrt(a**2 + b**2)
        if norm == 0:
            continue
        a, b, c = a/norm, b/norm, c/norm
 
        # 3. 점-직선 거리 계산
        distances = np.abs(a*points[:,0] + b*points[:,1] + c)
 
        # 4. inlier 판별
        inliers = np.where(distances < threshold)[0]
 
        # 5. 최적 모델 업데이트
        if len(inliers) > len(best_inliers):
            best_inliers = inliers
            best_model = (a, b, c)
 
    return best_model, best_inliers

3D Plane Fitting

• 모델 : $ax+by+cz+d=0$ 형태의 3D 평면
• 오차 : 점과 평면 사이의 거리

import numpy as np
 
def ransac_plane_fitting(points, iter=1000, threshold=0.01):
    """
    points: (N, 3) numpy array
    """
    best_inliers = []
    N = len(points)
 
    for _ in range(iter):
        # 1. 최소 샘플 3개 선택
        idx = np.random.choice(N, 3, replace=False)
        p1, p2, p3 = points[idx]
 
        # 2. 평면 법선 벡터 계산
        v1 = p2 - p1
        v2 = p3 - p1
        normal = np.cross(v1, v2)
 
        # 법선이 0 벡터면 스킵
        if np.linalg.norm(normal) == 0:
            continue
 
        a, b, c = normal / np.linalg.norm(normal)
        d = -np.dot([a, b, c], p1)
 
        # 3. 점-평면 거리 계산
        distances = np.abs(a*points[:,0] + b*points[:,1] + c*points[:,2] + d)
 
        # 4. threshold 기반 inlier
        inliers = np.where(distances < threshold)[0]
 
        # 5. 최적 모델 갱신
        if len(inliers) > len(best_inliers):
            best_inliers = inliers
            best_model = (a, b, c, d)
 
    return best_model, best_inliers

---

Code (Python - OpenCV)

• Opencv에서 사용되는 fitLine() 함수는 RANSAC이 아니라 M-estimator 기반의 robust/least-squares 계열 피팅이며, RANSAC을 이용한 Line Fitting 이나 Plane Fitting은 직접 구현해야함.

2D Line Fitting

import cv2
 
# RANSAC 기반 직선 추정
vx, vy, x0, y0 = cv2.fitLine(points, cv2.DIST_L2, 0, 0.01, 0.01)
# vx, vy, x0, y0 = cv2.fitLine(points, distType, param, reps, aeps)
# cv2.DIST_L2 : L2 거리 기반
# param : 일부 distType(특히 M-estimator들)에 대한 수치 파라미터.0으로 두면 자동 최적값.
# reps : 반경(거리)에 대한 허용 오차(종료 조건)
# aeps : 각도(orientation)에 대한 허용 오차(종료 조건)
# reps와 aeps는 알고리즘의 정밀도/종료 기준을 정하는 값으로, 작게 하면 더 정밀하지만 시간이 오래 걸리고, 너무 크게 하면 부정확짐.
 
# - vx, vy : 방향 벡터
# - x0, y0 : 위치 벡터
 
# 직선 방정식 a, b, c 형태로 변환
# 방향 벡터: (vx, vy)
# 법선 벡터: (-vy, vx)
a = -vy
b = vx
c = -(a * x0 + b * y0)

---

참고

• 다크 프로그래머 : RANSAC의 이해와 영상처리 활용
• cs.cmu.edu/~16385/s17/Slides/10.3_2D_Alignment__RANSAC.pdf
• [25편] 회귀 분석 - RANSAC : 네이버 블로그
• 중학생도 이해할 수 있는 RANSAC 알고리즘 원리
• 짧은 머신러닝 안내서: RANSAC - YouTube