[C#] RANSAC 알고리즘 구현

RANSAC 정의

RANSAC은 실제 데이터를 토대로 모델을 추정하는데 사용되는 가장 기초적인 방법중 하나다. RANSAC은 Random Sample Consensus의 약자이며, 말 그대로 데이터중 모델에 필요한 일부 데이터로 모델을 만들어, 비교한다는 뜻을 포함하고 있다. RANSAC은 컴퓨터 비전, 로보틱스, 빅데이터 등의 분야에서 활용되고 있다.

 

RANSAC 과정

알고리즘 단계는 다음과 같다.

1. 무작위 샘플링: 데이터에서 모델을 생성할 수 있는 최소한의 샘플을 무작위로 선택한다.

2. 모델 추정: 샘플을 기반으로 모델 계수를 계산한다.

3. Inlier 검증: 전체 데이터에 대해 해당 모델과의 오차를 계산한다. 그리고 특정 임계값 (Threshold) 보다 낮은 오차를 갖는 데이터 수를 측정한다.

4. 최적 모델 계산: Inlier의 개수가 가장 많은 모델을 최적 모델로 갱신한다.

5. 반복: 설정한 반복 횟수 (Iterations)만큼 무작위 샘플링, 모델 추정, Inlier 검증 및 최적 모델을 계산한다.

6. 최종 모델 도출: 반복을 완료한 뒤에 Inlier 개수가 가장 높은 최종 모델을 반환한다.

 

RANSAC 모델

RANSAC 모델은 다양하게 선정될 수 있다. 따라서 이 부분은 사용자가 사전에 데이터에 대한 분석을 해야한다. 예를 들어, 1차 함수 모델을 도출할 경우, 기울기 (Slope)와, 절편 (Intercept)을 구할 수 있다.

 

1차 함수는 y = l * x + c 로 나타낼 수 있으며, 두 개의 점을 알고 있다면, 대입하여 l, c 를 구할 수 있다. 이처럼 2차 함수나 그 이상의 다항식도 활용할 수 있으며, 다른 형태의 함수도 활용 가능하다. 예제 코드는 다음과 같다.

 

using System;
using System.Collections.Generic;
using System.Linq;

class Ransac
{
    static void Main(string[] args)
    {
        // 데이터 포인트 예제 (x, y)
        List<(double x, double y)> data = new List<(double x, double y)>
        {
            (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), // Inliers
            (10, 1), (15, 2), (20, 3)              // Outliers
        };

        var (bestModel, inliers) = RansacFit(data, 100, 1.0, 2);

        Console.WriteLine($"Best Model: y = {bestModel.Item1}x + {bestModel.Item2}");
        Console.WriteLine("Inliers:");
        foreach (var point in inliers)
        {
            Console.WriteLine($"({point.x}, {point.y})");
        }
    }

    // RANSAC 알고리즘 구현
    public static ((double slope, double intercept), List<(double x, double y)>) RansacFit(
        List<(double x, double y)> data,
        int iterations,
        double threshold,
        int minInliers)
    {
        Random random = new Random();
        (double slope, double intercept) bestModel = (0, 0);
        List<(double x, double y)> bestInliers = new List<(double x, double y)>();

        for (int i = 0; i < iterations; i++)
        {
            // 무작위로 두 점 선택
            var sample = data.OrderBy(x => random.Next()).Take(2).ToList();

            if (sample.Count < 2) continue;

            // 모델 계산 (직선 방정식 y = mx + b)
            double slope = (sample[1].y - sample[0].y) / (sample[1].x - sample[0].x);
            double intercept = sample[0].y - slope * sample[0].x;

            // 데이터 포인트와의 거리 계산
            List<(double x, double y)> inliers = new List<(double x, double y)>();

            foreach (var point in data)
            {
                double predictedY = slope * point.x + intercept;
                double distance = Math.Abs(predictedY - point.y);

                if (distance < threshold)
                {
                    inliers.Add(point);
                }
            }

            // 최적 모델 갱신
            if (inliers.Count > bestInliers.Count && inliers.Count >= minInliers)
            {
                bestModel = (slope, intercept);
                bestInliers = new List<(double x, double y)>(inliers);
            }
        }

        return (bestModel, bestInliers);
    }
}

 

위 코드는 5개의  Inlier와 4개의 Outlier로 이루어진 data list에 RANSAC 알고리즘을 적용한 사례이다. Inlier란 모델에 잘 맞는 데이터를 의미하며, Outlier는 모델에 잘 맞지 않는 데이터를 의미한다. 이처럼, RANSAC은 이상치를 걸러내는데 효과가 있다.

 

RansacFit이란 함수는 데이터 집합과, 최대반복횟수, Inlier와 Outlier를 구분짓은 threshold값, 모델로 선정되기 위해 필요한 최소 Inlier개수를 받아, 기울기와 절편은 반환하는 함수이다. 위 예시에서 최대반복횟수는 100, threshold값은 1, 필요 최소 Inlier개수는 2로 설정되었다. 

 

5개의 Inlier 값들은 모두, y=x 식에 부합하는 것을 직관적으로 볼 수 있다. 그리고 Outlier 값들은 맞지 않는다. 만양 랜덤 샘플링에  Outlier값이 들어가게 될 경우, 다른 데이터들과 해당 모델간 오차는 커질 것이며, Inlier 개수는 적게 나올 것이다.

 

반면에 Inlier값들로만 랜덤 샘플링하여 모델을 만들 경우, y=x 함수가 생성되고, 많은 Inlier값들이 이에 부합하게 될 것이다. 

 

RANSAC C# 예제코드 실행 결과

 

RANSAC 고려사항

RANSAC를 의미있게 활용하기 위해서는 먼저, 주어진 데이터에 적합한 함수를 사전에 찾아야 한다. 그리고 Outlier와 Inlier의 경향을 보고, 구분할 수 있는 threshold값을 지정하는 것이 필요하다. Inlier와 Outlier간 차이가 크지 않다면, threshold 값을 정하는데 어려움이 있을 수 있다. 최대 반복 횟수의 경우, 클수록 좋은 값을 찾을 확률이 올라가나, 그만큼 계산 시간이 소요될 수 있다.