RANSAC과 같은 강건(Robust) 추정 기법

강건 추정 기법의 배경

최소제곱법은 오차의 제곱합을 최소화하는 방식으로 계수나 모델 파라미터를 추정한다. 그러나 실제 계측 데이터에는 이상값이 포함되어 있을 가능성이 많다. 이상값이 발생하는 원인은 다양하며, 센서 노이즈나 환경적 요인, 측정 장치의 오작동 등이 그 원인이 될 수 있다. 일반적인 최소제곱법은 이상값이 포함된 상황에서 모델을 추정하면 극단적인 데이터에 의해 결과가 크게 왜곡될 수 있다. 이러한 취약성을 극복하기 위해 이상값에 둔감한 강건(Robust) 추정 기법이 연구되어 왔다. 강건 추정 기법은 데이터 중 일부가 심각한 노이즈로 훼손되어 있더라도 올바른 모델 추정을 수행하도록 설계된다.

강건 추정의 핵심은 이상값을 효과적으로 처리해 추정 과정에서 이상값이 주는 영향력을 줄이거나 무시하는 것이다. 이를 위해 잔차(residual) 분포를 분석하거나 이상값 판별 기준을 설정하는 다양한 접근 방법이 연구된다. 예를 들어 M-추정(M-estimation), L-추정(L-estimation), RANSAC(Random Sample Consensus) 등이 자주 활용된다.

표준 최소제곱법의 취약성

표준 최소제곱법은 오차가 가우시안 분포를 따른다고 가정하며, 모든 데이터 점에 동일한 가중이 부여된다. 관측 데이터가 $x_i, y_i$로 주어지고 모델이 어떤 파라미터 벡터 $\mathbf{p}$에 의해

$$y = f(x; \mathbf{p})$$

형태로 나타난다고 가정하자. 측정된 값 $y_i$와 모델 예측값 $f(x_i; \mathbf{p})$ 간의 잔차를

$$r_i = y_i - f(x_i; \mathbf{p})$$

라 하면 최소제곱법은 다음과 같은 최적화 문제를 푼다.

$$\begin{align} \min_{\mathbf{p}} \sum_{i=1}^{n} r_i^2 \end{align}$$

이때 자료 $(x_i, y_i)$에 이상값이 존재하면 $r_i$ 중 극단적으로 큰 값이 생성될 수 있고, 그 하나의 값에 의해 전체 오차 합이 지배되어 파라미터 추정에 치명적인 영향을 미친다.

이상값과 강건성

강건 추정 기법에서는 이상값의 존재하에서도 모델 추정이 안정적으로 수행되길 원한다. 이상값 비율이 높지 않다면 강건 추정법이 제대로 동작하도록 구성하는 것이 가능하다. 이러한 기법들은 다양한 측면에서 정의되지만, 한 가지 중요한 개념은 브레이크다운 점(breakdown point)이다. 브레이크다운 점은 추정량이 망가지는 데 필요한 이상값의 비율을 말한다. 예를 들어 표준 최소제곱법의 브레이크다운 점은 매우 낮으므로 극소수의 이상값만 있어도 추정 결과가 왜곡되기 쉽다.

강건 추정에서는 이상값이 차지하는 비율이 브레이크다운 점 이하일 경우 신뢰할 수 있는 모델을 찾아내도록 알고리즘을 설계한다. M-추정과 같은 방식은 잔차에 대한 가중 함수를 적절히 설정해 이상값이 큰 잔차 항을 갖더라도 그 영향이 제한되도록 한다. RANSAC은 표본을 반복적으로 무작위 추출해 전체 자료 중 최대 합의(consensus)를 얻는 방식으로 이상값의 영향을 최소화한다.

RANSAC 기법의 기본 아이디어

RANSAC(Random Sample Consensus)은 무작위로 선택된 소수의 데이터만을 이용해 모델을 추정한 뒤, 해당 모델과 잘 맞는지를 기준으로 합의 집합(consensus set)을 형성하고, 합의 집합 크기가 충분히 크면 그 모델을 강건하게 추정하는 기법이다. 이 아이디어의 배경에는 이상값이 소수에 불과하다는 가정이 깔려 있다.

표준 최소제곱법과 달리, RANSAC은 우선 적은 수의 표본을 택하여 모델을 만들기 때문에 이상값이 섞여 들어갈 확률이 낮은 표본을 뽑아낼 때까지 반복을 수행한다. 이후 선택된 모델에 대해 전체 데이터 점 중에서 잔차가 특정 임계값 이하로 떨어지는 점들을 합의 집합이라고 부른다. 합의 집합이 가장 큰 모델을 찾아내고, 최종적으로는 이 합의 집합만을 대상으로 모델 파라미터를 재추정하여 이상값의 영향을 배제한다.

RANSAC 알고리즘의 수식적 정리

관측 데이터가 $(x_i, y_i)$로 주어졌다고 하자. 어떤 모델 $f(x; \mathbf{p})$를 가정하고, 파라미터 집합을 $\mathbf{p}$라 할 때, 개별 데이터 점이 모델에 잘 부합하는지 평가하기 위한 기준으로 오차 함수 $r_i$를 정의한다. 특정 모델 $\mathbf{p}$에 대해

$$r_i = | y_i - f(x_i; \mathbf{p}) |$$

가 작은 점은 모델에 부합한다고 할 수 있다. 임계값 $\tau$를 정하여 $r_i \leq \tau$를 만족하는 점을 모델의 합의 집합(consensus set)에 포함시킨다. RANSAC 과정에서 무작위 추출로 구한 어떤 후보 모델 $\mathbf{p}_k$가 있을 때, 합의 집합의 크기를

$$C(\mathbf{p}_k) = \sum_{i=1}^{n} \delta(\tau, r_i)$$

라고 두자. 여기서 $\delta$는 임계값보다 잔차가 작으면 1, 아니면 0을 반환하는 함수이다. 여러 번의 무작위 시도 중에서

$$\mathbf{p}_\text{best} = \arg \max_{\mathbf{p}_k} C(\mathbf{p}_k)$$

로 정의되는 $\mathbf{p}_\text{best}$가 가장 많은 합의 집합을 형성하는 모델로 결정된다. 이를 바탕으로 최종 파라미터 추정을 위해 다시 한 번 세밀한 최적화를 수행하거나, 합의 집합에 대해 최소제곱이나 다른 강건 추정 알고리즘을 적용하여 최종 모델 파라미터를 도출한다.

전형적인 RANSAC 흐름

시작 단계에서 전체 데이터 중 소수의 표본을 무작위로 선택한다. 그 표본으로부터 모델을 추정한 다음 전체 데이터에 대해 잔차를 계산한다. 일정 기준 이하의 잔차를 주는 점들을 합의 집합으로 묶고, 합의 집합 크기가 가장 큰 모델을 갱신한다. 해당 과정을 여러 번 반복 수행하면서 합의 집합이 가장 큰 모델을 찾으면, 그 합의 집합에 대해서만 다시 세밀한 추정을 적용한다.

샘플 크기 선택과 이상값 비율 추정

RANSAC의 반복 횟수와 무작위로 추출해야 할 표본 개수는 이상값의 최대 비율에 대한 추정에서 영향을 받는다. 모델을 추정하기 위해 필요한 최소 표본 크기를 $s$라 하고, 이상값 비율을 $\epsilon$이라 예측하면, 이상값이 전혀 포함되지 않은 샘플을 추출할 확률은 $(1-\epsilon)^s$가 된다. 이 확률이 특정 신뢰도로 달성되도록 반복 횟수를 설정하면, 충분한 횟수 안에 이상값이 전혀 없는 소수 표본을 뽑아낼 수 있게 된다.

RANSAC은 데이터 양이 충분히 많고 이상값 비율이 낮은 상황에서 큰 효과를 발휘한다. 그러나 이상값 비율이 매우 높아지면 무작위 추출로 순수한 표본을 뽑기가 어려워지는 단점이 있다. 또한 임계값 $\tau$의 선정 방법도 데이터의 노이즈 정도와 이상값 분포에 따라 달라지므로 사전에 적절한 분석이나 경험적 조정이 필요하다.

RANSAC 알고리즘의 파생 기법과 고급 주제

RANSAC은 이상값이 적은 환경에서 단순하고 강력한 방식으로 모델을 찾을 수 있지만, 다양한 상황에서 더 정확하거나 효율적인 해법을 요구하기도 한다. 이러한 요구에 부응하기 위해 RANSAC 알고리즘을 개선하거나 변형한 여러 기법이 제안되었다. 그중 대표적인 방법으로 MLESAC, MSAC, LMedS, Preemptive RANSAC 등이 있으며, 각 기법마다 모델 적합도 측정 방식 혹은 추정 과정에서의 최적화가 다르다.

강건 추정이 필요한 문제는 선형 모델뿐 아니라 다항 회귀, 이미지 처리, 컴퓨터 비전 등 매우 다양한 분야에서 발생한다. 예를 들어 컴퓨터 비전에서 두 영상 간 특징점 매칭에 포함된 이상값(오검출 매칭)을 제거해 기하 변환(예: 호모그래피, 에센셜 행렬)을 추정하거나, 구조광 스캐닝으로 획득한 포인트 클라우드에서 평면 혹은 곡면을 추정할 때에도 RANSAC이 활용된다.

파생 기법으로 넘어가기 전, RANSAC의 근본적 특징과 한계를 구체적으로 살펴볼 필요가 있다. RANSAC은 무작위 표본 추출에 기반하기 때문에 모든 시도에서 이상값이 전혀 포함되지 않은 깨끗한 표본을 추출할 확률을 높이는 것이 관건이다. 표본 개수를 $s$라 하고, 이상값 비율을 $\epsilon$이라 할 때, 이상값이 없는 샘플을 뽑을 확률은 $(1 - \epsilon)^s$이다. 원하는 확률 $p$ 이상으로 이상값이 전혀 없는 샘플을 한 번 이상 뽑으려면 반복 횟수 $N$을

$$\begin{align} 1 - p = \bigl(1 - (1-\epsilon)^s \bigr)^{N}\\ \implies N \ge \frac{\ln(1 - p)}{\ln\bigl(1 - (1 - \epsilon)^s\bigr)}\\ \end{align}$$

와 같이 설정한다. 이를 통해 RANSAC의 반복 횟수를 결정하게 된다. 실제로는 이상값 비율 $\epsilon$이 사전에 알려지지 않는 경우가 많으므로, 초기 추정치나 실험적으로 측정된 잔차 분포 등을 토대로 $\epsilon$을 가정하여 반복 횟수를 잡는다.

모델을 판별하는 임계값 $\tau$ 역시 매우 중요한 하이퍼파라미터다. $\tau$의 설정이 너무 작으면 정상 데이터조차 모델에서 배제될 수 있고, 너무 크면 이상값도 모델에 포함되어 합의 집합이 부정확해진다. 이 값은 데이터의 잡음 정도나 실제 측정 분포, 센서 해상도 등 물리적·실험적 근거를 종합해 결정하는 것이 좋다.

모델의 형태가 복잡해질수록(예: 다항식 차수가 높거나, 고차원 파라미터 공간에서 모델을 추정해야 하는 상황 등) 무작위 표본 추출 과정에서 필요한 $s$도 증가하고, 합의 집합 판별에도 계산량이 많이 든다. 따라서 고차원 모델의 추정에는 RANSAC을 직접 적용하기보다는, 문제 구조를 세분화하거나 다른 기법과 혼합하여 효율성을 높이기도 한다.

RANSAC이 단순히 최대합의집합을 찾는 데 주력한다면, MLESAC(Maximum Likelihood Estimation SAmple Consensus)은 합의 집합뿐 아니라 잔차 분포 자체를 확률모델로 간주해 우도(likelihood)를 최대화하는 접근을 시도한다. MSAC(M-estimator SAmple Consensus)은 RANSAC의 합의 집합 개념을 M-추정에서 쓰이는 비용 함수(cost function)로 대체해, 잔차가 작은 점들에게는 작은 비용을 부여하고 잔차가 매우 큰 이상값에게는 큰 비용을 부여하여 최적 모델을 찾는다. LMedS(Least Median of Squares)는 합의 집합 개념 대신 잔차들의 중간값(median)이 최소가 되도록 모델을 추정함으로써 이상값의 영향을 최소화한다. 각 기법은 잡음과 이상값 분포에 따른 적응성이 달라질 수 있어, 문제 상황에 맞추어 기법을 선택해야 한다.

RANSAC을 여러 차례 실행해도 이상값이 계속 포함된 표본이 추출되어 모델 품질이 저하될 수 있는데, 이를 방지하고자 Preemptive RANSAC처럼 초기 단계에서 많은 수의 모델을 빠르게 평가하여 유망하지 않은 모델을 조기에 탈락시키는 방식을 도입하기도 한다. 이러한 변형 기법은 고차원 파라미터 추정이나 실시간 영상 처리처럼 연산 부하가 큰 문제에서 효과적일 수 있다.

RANSAC 구현 시, 합의 집합 크기가 최대가 되는 모델이 최종 해로 선정된 뒤에는 이 합의 집합만을 대상으로 다시 한 번 세밀하게 최소제곱 추정 등을 적용한다. 이것을 refinement 단계라 하며, 이상값이 배제된 상태에서 모델 계수를 보다 정밀하게 추정하는 과정이다. 예를 들어 일차 직선 모델에서 합의 집합에 속하는 점들만을 대상으로

$$\begin{align} \min_{\mathbf{p}} \sum_{(i \in \text{합의 집합})} \bigl(y_i - f(x_i; \mathbf{p})\bigr)^2 \end{align}$$

방식으로 회귀를 실행한다면, 초기 RANSAC 추정치보다 훨씬 정확하고 안정적인 결과가 나올 것이다.

강건 추정의 더 일반적인 방식으로 M-추정(M-estimator)이 있다. RANSAC과 달리 M-추정은 재식별 과정 없이 한 번의 최적화 스텝으로 모델을 추정한다. 표준 최소제곱법이 오차의 제곱에 가중 1을 주었다면, M-추정은 오차가 일정 이상 크면 그 점의 가중을 줄이는 형태의 강건 비용 함수를 사용한다. 예를 들어 Huber 함수, Cauchy 함수 등이 널리 쓰이는데, M-추정도 이상값의 영향을 어느 정도 줄여주지만 RANSAC처럼 분명히 이상값을 제외하는 방식과는 다르다. 실제 응용에서는 M-추정과 RANSAC을 혼합 사용하거나, RANSAC으로 이상값을 제거한 뒤 M-추정을 하는 식으로 결합해 쓰기도 한다.

모델 파라미터 공간이 커질수록, 혹은 이상값 비율이 아주 커질수록 RANSAC의 수행 시간이 길어질 수 있으며, 반복 횟수를 늘려도 깨끗한 표본을 찾지 못할 위험이 커진다. 또 데이터가 여러 군집으로 나뉘거나, 서로 다른 여러 모델이 동시에 존재하는 복합적인 상황에서는 RANSAC을 단순 적용하기 어려울 수 있다. 이때는 모델 선택 단계를 늘리거나, 각 군집별로 RANSAC을 독립적으로 실행하는 방법 등 다양한 확장이 가능하다.

이미지 처리나 컴퓨터 비전 과제에서 RANSAC이 인기도가 높은 이유 중 하나는, 대응점 매칭 단계에서 필연적으로 상당수의 이상값 매칭이 발생하기 때문이다. 에센셜 행렬, 기본 행렬, 호모그래피 등의 추정을 위해선 무작위 표본 선택으로 초기 근사치를 빠르게 구한 뒤, 합의 집합 기반의 강건화로 이상값의 악영향을 줄여 모델의 정확도를 높인다. 그러나 영상 크기가 커지거나 특징점 매칭 수가 매우 많아질수록, 효율적인 전처리나 M-추정 방식의 혼합 등이 더욱 강조된다.

어떤 강건 추정 기법을 선택할지 결정할 때는 자료 크기, 이상값 비율, 잡음 분포, 모델 차원 등의 요소를 모두 고려해야 한다. RANSAC 계열 알고리즘은 이상값의 분포가 특정 구간에 집중되어 있거나, 간헐적으로 발생하는 경우에 탁월하다. 추정해야 하는 모델의 자유도가 낮고, 노이즈가 상대적으로 균질한 경우에는 M-추정도 좋은 선택이 될 수 있다. 혹은 두 기법을 적절히 혼합해 성능을 높이는 방법도 있다.

다중 모델 추정(Multi-model Fitting)과 확장

RANSAC은 하나의 모델만 가정할 때 뛰어난 강건성으로 이상값을 걸러낼 수 있다. 그러나 실제 데이터에는 여러 개의 서로 다른 모델(예: 서로 다른 평면, 여러 직선 세트 등)이 공존할 수 있으며, 부분집합마다 다른 모델에 잘 부합하는 상황이 발생하기도 한다. 이를 다중 모델 추정 문제라고 부른다. 이 경우에도 이상값이 섞여 있을 수 있으므로 강건 추정이 필요하지만, 단순 RANSAC을 그대로 적용하기엔 어려움이 있다.

하나의 모델만을 찾는 RANSAC으로 여러 모델을 처리하려면, 우선 첫 번째 모델을 RANSAC으로 추정하고 합의 집합에 해당하는 데이터들을 제거한 뒤 남은 자료로 다시 RANSAC을 적용하는 과정을 반복하는 방법이 가장 단순하다. 그러나 데이터가 복잡하게 섞여 있는 경우 합의 집합이 서로 간섭하기 쉽고, 특정 모델이 다른 모델의 데이터 점들을 잘못 흡수하게 되어 추정 성능이 나빠질 수 있다. 따라서 다중 모델을 한 번에 효율적으로 추정하기 위한 다양한 확장 기법(예: MultiRANSAC, PEARL, J-Linkage 등)이 연구되고 있다.

여러 모델이 존재하는 경우에는 간단히 말해 “합의 집합들이 서로 다른 모델에 속한 점들을 많이 공유하지 않도록” 분할하는 것이 핵심이다. 이를 위해 각 점들 사이의 모델 파라미터 적합성을 유사도로 삼아 클러스터링(예: linkage-based clustering)을 수행하거나, 점들이 어떤 모델에 속하는지 확률 분포를 추정하는 통계적 접근(Mixture-of-Gaussians 유사 아이디어) 등이 시도된다. 복합적인 상황에서는 단순 RANSAC보다 계산량이 늘어나지만, 고급 기법을 통해 여러 모델을 동시에 강건하게 추정할 수 있다.

가이드 샘플링(Guided Sampling)과 효율성 개선

무작위 표본 추출은 직관적이지만, 이상값 비율이 높을수록 “정상 데이터만 들어간 깨끗한 표본”을 뽑을 확률이 매우 낮아져 많은 반복이 필요하다. 이때 일부 사전 정보나 데이터 특성을 이용해 이상값의 가능성이 낮은 점들만 선별적으로 표본을 추출하면 전체 반복 횟수를 줄일 수 있다. 이를 가이드 샘플링이라고 부르며, PROSAC(Progressive Sample Consensus) 같은 기법이 대표적이다.

가령 컴퓨터 비전의 특징점 매칭 문제에서, 매칭 점들의 신뢰도(점수)가 높은 순으로 우선해서 표본을 뽑는 식의 접근이 가능하다. 이 경우 단순 무작위 추출보다 빠르게 깨끗한 표본을 뽑을 확률이 높아지고, 필요한 전체 반복 횟수가 감소해 효율이 개선된다. 다만, 가이드 샘플링을 잘못 적용하면 어떤 구간에서 지역 최소해나 노이즈에 묶일 가능성도 있으므로, 기존 RANSAC의 무작위성도 일정 수준 유지해야 하는 트레이드오프가 있다.

LO-RANSAC(Local Optimization RANSAC)

RANSAC 계열의 또 다른 주류 변형으로 LO-RANSAC(Local Optimization RANSAC)이 있다. LO-RANSAC은 표본 기반 모델 추정 이후, 합의 집합에 대해 추가적인 지역 최적화(local optimization) 단계를 수행해 더 정확한 모델을 얻는다. 기본 RANSAC에서도 합의 집합만으로 최소제곱 추정을 다시 하는 refinement 단계가 있지만, LO-RANSAC은 이를 반복적으로 개선하여 합의 집합을 더욱 키우는 식으로 동작한다. 따라서 부정확한 임계값으로 인해 일부 정상 데이터가 배제되었거나, 이상값이 섞여 들어가 있더라도 모델이 점차 개선될 수 있도록 설계된다.

RANSAC 구현 예시 (Python)

직선 방정식 $y = ax + b$를 강건하게 추정하는 RANSAC 예시를 Python 코드로 살펴보자. 노이즈와 이상값이 섞인 자료를 생성하고, RANSAC으로 모델 계수를 찾는다.

코드 예시 (Python):

import numpy as np
import random
import matplotlib.pyplot as plt

def generate_data(num_points=100, a=2.0, b=1.0, noise_sigma=1.0, outlier_ratio=0.3):
    x = np.linspace(-10, 10, num_points)
    y = a * x + b + np.random.normal(0, noise_sigma, num_points)
    num_outliers = int(num_points * outlier_ratio)
    outlier_indices = np.random.choice(num_points, num_outliers, replace=False)
    # 이상값을 무작위로 크게 벗어나도록 조작
    y[outlier_indices] += np.random.normal(0, 20*noise_sigma, num_outliers)
    return x, y

def fit_line_least_squares(x, y):
    # X = [[x_i, 1], [x_i, 1], ...]
    X = np.column_stack((x, np.ones_like(x)))
    # p = (X^T X)^-1 X^T y
    pseudo_inv = np.linalg.inv(X.T @ X) @ X.T
    p = pseudo_inv @ y
    return p[0], p[1]

def compute_residual(a, b, x, y):
    return np.abs(y - (a*x + b))

def ransac_line_fitting(x, y, max_iter=1000, dist_thresh=2.0, sample_size=2):
    best_a, best_b = 0, 0
    best_inliers = []
    n = len(x)

    for _ in range(max_iter):
        # 무작위로 sample_size만큼의 표본을 뽑아 선형 모델 추정
        indices = random.sample(range(n), sample_size)
        x_sample, y_sample = x[indices], y[indices]
        try:
            a_est, b_est = fit_line_least_squares(x_sample, y_sample)
        except np.linalg.LinAlgError:
            continue

        # 추정된 모델에 대해 모든 점들의 잔차 계산
        residuals = compute_residual(a_est, b_est, x, y)
        inliers_idx = np.where(residuals < dist_thresh)[0]

        # 이번 추정치가 더 많은 합의 집합을 제공하면 갱신
        if len(inliers_idx) > len(best_inliers):
            best_inliers = inliers_idx
            best_a, best_b = a_est, b_est

    # 합의 집합에 대해 한 번 더 정밀 추정(refinement)
    if len(best_inliers) > 0:
        final_a, final_b = fit_line_least_squares(x[best_inliers], y[best_inliers])
    else:
        final_a, final_b = best_a, best_b

    return final_a, final_b, best_inliers

np.random.seed(0)
x_data, y_data = generate_data()
est_a, est_b, inliers = ransac_line_fitting(x_data, y_data)

print("Estimated line: y = {:.4f} x + {:.4f}".format(est_a, est_b))

plt.scatter(x_data, y_data, color='gray', label='Data')
plt.scatter(x_data[inliers], y_data[inliers], color='green', label='Inliers')
plt.plot(x_data, est_a*x_data + est_b, 'r-', label='RANSAC fit')
plt.legend()
plt.show()

코드를 간단히 살펴보면 먼저 데이터 생성 단계에서 이상값을 일부러 삽입한다. 이후 표본 크기를 2로 두어 무작위로 두 점을 골라 선형 회귀를 수행한 다음, 해당 모델과 잘 맞는(잔차가 일정 거리 이하인) 점들을 합의 집합으로 정의한다. 이를 여러 번 반복해 합의 집합이 가장 많은 모델을 찾은 뒤, 그 합의 집합으로 최소제곱법을 다시 적용해 최종 모델 계수를 구한다.

RANSAC의 성능은 max_iter, dist_thresh, sample_size와 같은 파라미터, 그리고 데이터의 이상값 분포에 의해 크게 좌우된다. 실제 응용에서는 합의 집합에 대한 재추정 방법, 이상값 비율에 대한 추정, 임계값 설정 등 다양한 측면을 세밀하게 결정해야 한다.

추가 논의

RANSAC 및 강건 추정 기법은 다음과 같은 고급 문제 설정에도 널리 확장된다.

• 모델 파라미터 공간이 고차원이거나 비선형일 경우, 무작위로도 깨끗한 표본을 얻기 쉽지 않다.

• 실시간(online) 추정이 필요한 경우, 데이터가 순차적으로 들어올 때마다 RANSAC을 빠르게 업데이트해야 한다.

• 합의 집합 결정 시, 단순히 임계값을 두고 잔차를 비교하기보다는 잔차 확률분포를 추정하는 통계적 접근을 적용할 수 있다.

이 외에도 이미지 처리, 3D 스캐닝, 자율 주행, 로보틱스 등 여러 분야에서 RANSAC 계열 알고리즘이 오랜 기간 쓰이고 있으며, M-추정 등과 결합해 다양한 하이브리드 방식을 시도하는 연구도 많다. 현실 상황에서의 노이즈 특성과 이상값 분포를 잘 파악해, RANSAC과 파생 기법을 적절히 활용하는 것이 중요하다.

강건 오차 함수(Robust Loss Function)와 M-추정과의 관계

강건 추정을 논할 때 자주 거론되는 또 하나의 축은 M-추정(M-estimation)이다. 전통적 최소제곱법은 오차의 제곱합 $\sum r_i^2$을 최소화하지만, 이상값이 존재하는 경우 몇 개의 큰 오차가 전체 해를 왜곡할 수 있다. 반면 M-추정은 오차가 일정 임계 범위를 넘어서면 그 기여도가 제한되도록 고안된 강건 오차 함수를 사용한다. 예를 들어 Huber 함수, Cauchy 함수, Tukey 함수 등 다양한 강건 오차 함수가 제안되어 있다. M-추정의 일반적 형태는

$$\begin{align} \min_{\mathbf{p}} \sum_{i=1}^{n} \rho\bigl(r_i(\mathbf{p})\bigr) \end{align}$$

처럼 표현할 수 있으며, 이때 $\rho(\cdot)$가 강건 오차 함수를 의미한다. 예컨대 Huber 함수는 작은 잔차 구간에서는 제곱 오차 형태로 작용하지만, 잔차가 일정 임계값 $\delta$ 이상 커지면 선형 구간으로 전환되어 큰 오차에 대한 가중을 작게 만든다. 따라서 이상값의 영향력이 제한된다.

M-추정은 각 잔차에 대해 연속적이며 부드러운 방법으로 가중을 조정하는 반면, RANSAC은 임계값을 통해 “합의 집합 안 vs. 밖”을 가르는 이분적 접근을 취한다. 그 결과, RANSAC은 이상값을 아예 배제해버리는 반면, M-추정은 이상값 잔차를 줄여주는 방향으로 탐색하려 한다. 응용 상황에 따라 RANSAC은 빠르게 합의 집합을 구분해내는 장점이 있고, M-추정은 잔차 함수가 연속적이므로 미분 가능성을 이용한 해석적 접근 및 최적화 기법 활용이 용이하다는 강점이 있다.

IRLS(Iteratively Reweighted Least Squares)

M-추정은 비선형 최적화의 일종으로 볼 수 있으며, 이를 반복 가중 최소제곱(IRLS) 방식으로 구현할 수 있다. IRLS는 오차 함수의 미분(또는 유도된 표준화된 잔차)을 통해 각 데이터 점에 대한 가중치를 업데이트하는 식으로 반복 수행한다. 구체적으로, M-추정의 목적 함수를 최소화하는 문제에서, 각 단계에서 현재 추정치에 기반한 잔차의 크기에 따라 점별 가중을 산출하고, 그 가중을 반영해 가중 최소제곱법을 한 번 더 푼 뒤 새로운 추정치를 얻는다.

RANSAC과 IRLS는 상호 배타적인 기법이 아니라, 전처리에 RANSAC을 적용해 극단 이상값을 걸러낸 뒤 그 나머지 점들로 IRLS를 수행하면 더 정밀한 결과를 얻을 수 있다는 식으로도 결합할 수 있다.

Truncated Least Squares

또 다른 강건 접근으로 Truncated Least Squares(TLS)가 있다. 이는 오차 $r_i^2$가 일정 임계값보다 클 때는 비용 함수에 더 이상 반영되지 않도록(즉 상한을 두어 절단) 하는 방식이다. 모양만 다를 뿐, M-추정에서의 Cauchy 함수를 쓰는 것과 유사한 철학을 갖는다. 원리는 “매우 큰 오차는 어차피 이상값일 가능성이 높으니 추가적인 페널티를 부여할 필요가 없다”는 것이다.

RANSAC과의 차이는, RANSAC은 합의 집합 밖의 점을 완전히 배제하는 것이고, TLS는 잔차가 임계 이상인 점의 비용을 상한선(Truncation)으로 고정하는 방식이다. 이 두 방법 역시 중간 지점에서 조합해 사용할 수 있다.

부분공간(Subspace) 기반 강건 추정

데이터가 고차원 공간에 놓여 있을 때, 노이즈와 이상값을 견디며 저차원 부분공간(예: 주성분 분석) 구조를 추정하는 문제도 중요하다. 이 분야에서 RANSAC과 같은 강건 기법을 부분공간 추정에 적용하기도 하며, 특히 컴퓨터 비전 영역에서 3D 포인트 클라우드를 이용해 어떤 기하학적 구조(평면, 원뿔, 구, 실린더 등)를 찾는 데 활용된다. 예컨대 한 평면에 놓여 있는 점들을 추출하려면, 무작위로 3점(or 최소 필요 점)을 뽑아 평면을 정의하고, 그 평면에 가까운 점들의 개수를 합의 집합으로 보는 식이다.

머신러닝과의 결합

최근엔 딥러닝 및 머신러닝 기술과 RANSAC을 결합하는 연구도 많다. 예를 들어 네트워크가 추정해야 할 파라미터 범위를 가이드하거나, 특징 공간에서 이상값 가능성이 높은 점들을 사전에 걸러내 표본 추출 효율을 높이는 접근이 시도된다. 반면 RANSAC의 결과물을 학습 데이터의 정제나 이상값 제거에 활용해, 머신러닝 모델이 더 깨끗한 데이터를 학습하도록 만드는 방법도 가능하다.

그래프 기반 접근

컴퓨터 비전 문제 등에서, 데이터 점들 사이에 어떤 “연결” 혹은 관계가 존재할 때 그래프 기반 접근을 통해 강건 추정을 수행하기도 한다. 예를 들어 서로 다른 점쌍이 동일한 모델 파라미터를 지지하는지, 혹은 상충하는지에 대한 정보를 그래프로 표현하고 클러스터링이나 최적화 기법을 적용하면, RANSAC처럼 단순한 표본 추출 반복 대신 전역적 방식으로 이상값을 분리할 수 있다. 그러나 그래프 기반 방법은 문제에 따라 계산 복잡도가 매우 커질 수 있고, 구현 난이도도 높아지는 단점이 있다.

RANSAC의 이론적 통계 특성

RANSAC은 통계적으로는 “이상값이 (1) 충분히 적을 것, (2) 무작위 표본 추출 반복 횟수가 많을 것” 등을 가정하는 방법이므로, 엄밀하게는 확률적 추정 기법이다. 따라서 RANSAC으로 얻은 모델이 전역적 최소 오차를 만족한다는 보장은 없다. 대신 일정 확률 수준에서 이상값이 없는 샘플을 뽑아낼 가능성이 충분히 높아지도록 반복 횟수를 설정함으로써, “높은 확률로 적절한 모델을 찾을 수 있다”라는 형태의 확률론적 보증을 제공한다.

이러한 접근은 작은 이상값 비율($\epsilon$)에서는 적은 반복만으로도 높은 신뢰도를 확보할 수 있지만, $\epsilon$이 커질수록 반복 횟수 $N$이 지수적으로 증가해 실용적이지 않을 수 있다. 따라서 실제 문제에서 $\epsilon$이 매우 큰(예: 절반 이상) 경우엔 M-추정처럼 잔차 함수를 계속 업데이트해가는 방식이 더 적합할 때도 있다.

실제 적용 시 고려 사항

실제 응용에서 RANSAC이나 그 파생 기법들을 적용할 때는 다음과 같은 점을 고려해야 한다.

• 모델 복잡도: 추정해야 하는 모델의 파라미터 차원이 높을수록, 깨끗한 표본을 얻기가 어려워진다.

• 데이터 양: 데이터가 충분하면 무작위 표본에서 이상값이 섞일 확률이 상대적으로 낮아진다.

• 이상값 비율 추정: 이상값 비율이 매우 높으면 RANSAC 반복 횟수가 기하급수적으로 커진다. 대안으로, 가이드 샘플링이나 사전 필터링 등이 필요할 수 있다.

• 임계값 설정: 합의 집합을 정의하는 임계값 $\tau$가 너무 크면 이상값까지 포함되고, 너무 작으면 정상점도 제외된다. 데이터 분포와 노이즈 특성에 맞춰 적절히 설정하거나, 자동화 방안을 고려한다.

• 연산 부하: 무작위 추출, 모델 피팅, 합의 집합 검사 과정을 반복하기 때문에, 대규모 데이터나 실시간 처리에서는 최적화가 필요하다.

---

RANSAC은 간단하면서도 강력한 강건 추정 기법으로서, 다양한 상황에서 이상값의 악영향을 줄이고 신뢰할 수 있는 모델을 찾도록 도와준다. 이에 대한 변형 기법들(MLESAC, MSAC, LO-RANSAC 등)과, 다른 강건 추정 방식(M-추정, IRLS, Truncated LS 등)과의 결합을 통해, 노이즈 환경에 최적화된 알고리즘을 구현하는 것이 가능하다. 모델 복잡도와 이상값 비율이 높아질수록 반복 횟수나 계산 부담이 커질 수 있으므로, 가이드 샘플링, 그래프 기반 접근, 머신러닝 기반 사전 필터링 등의 고급 방법을 병행하여 RANSAC을 보완한다.