RANdom Sample Consensus (RANSAC) in C#

June 2, 2010 / cesarsouza / 40 Comments

RANSAC is an iterative method to build robust estimates for parameters of a mathematical model from a set of observed data which is known to contain outliers. The RANSAC algorithm is often used in computer vision, e.g., to simultaneously solve the correspondence problem and estimate the fundamental matrix related to a pair of stereo cameras.

Download sample application and source code
Browse the sample application source code
Browse the RANSAC.cs class source code
Install the Accord.NET machine learning framework.

The code presented here is part of the Accord.NET Framework. The Accord.NET Framework is a framework for developing machine learning, computer vision, computer audition, statistics and math applications in .NET. To use the framework in your projects, install it by typing Install-Package Accord.MachineLearning in your IDE’s NuGet package manager.

Introduction

RANSAC is an abbreviation for “RANdom SAmple Consensus“. It is an iterative method to estimate parameters of a mathematical model from a set of observed data which may contains outliers. It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles in 1981.

The basic assumption is that the data consists of “inliers”, i.e., data whose distribution can be explained by some mathematical model, and “outliers” which are data that do not fit the model. Outliers could be considered points which come from noise, erroneous measurements or simply incorrect data. RANSAC also assumes that, given a set of inliers, there exists a procedure which can estimate the parameters of a model that optimally explains or fits this data.

Example: Fitting a simple linear regression

We can use RANSAC to robustly fit a linear regression model using noisy data. Consider the example below, in which we have a cloud of points that seems to belong to a line. These are the inliers of the data. The other points, which can be seem as measurement errors or extreme noise values, are points expected to be considered outliers.

Linear structure contained in noisy data.

RANSAC is able to automatically distinguish the inliers from the outliers through the evaluation of the linear regression model. To do so, it randomly selects subsets from the data and attempts to fit linear regression models using them. The model which best explains most of the data will then be returned as the most probably correct model fit.

The image below shows the result of fitting a linear regression directly (as shown by the red line) and using RANSAC (as shown by the blue line). We can see that the red line represents poorly the data structure because it considers all points in order to fit the regression model. The blue line seems to be a much better representation of the linear relationship hidden inside the overall noisy data.

Hidden linear structure inside noisy data. The red line shows the fitting of a linear regression model directly considering all data points. The blue line shows the same result using RANSAC.

Source code

The code below implements RANSAC using a generic approach. Models are considered to be of the reference type TModel and the type of data manipulated by this model is considered to be of the type TData. This approach allows for the creation of a general purpose RANSAC algorithm which can be used in very different contexts, be it the fitting of linear regression models or the estimation of homography matrices from pair of points in different images.

This code is available in the class RANSAC of the Accord.NET Framework (source).

    /// &lt;summary&gt;
    ///   Computes the model using the RANSAC algorithm.
    /// &lt;/summary&gt;
    public TModel Compute(TData[] points, out int[] inliers)
    {
        // We are going to find the best model (which fits
        //  the maximum number of inlier points as possible).
        TModel bestModel = null;
        int[] bestInliers = null;
        int maxInliers = 0;

        // For this we are going to search for random samples
        //  of the original points which contains no outliers.

        int count = 0;  // Total number of trials performed
        double N = maxEvaluations;   // Estimative of number of trials needed.

        // While the number of trials is less than our estimative,
        //   and we have not surpassed the maximum number of trials
        while (count &lt; N &amp;&amp; count &lt; maxEvaluations)
        {
            int[] idx;
            TModel model = null;
            int samplings = 0;

            // While the number of samples attempted is less
            //   than the maximum limit of attempts
            while (samplings &lt; maxSamplings)
            {
                // Select at random s datapoints to form a trial model.
                idx = Statistics.Tools.Random(points.Length, s);
                TData[] sample = points.Submatrix(idx);

                // If the sampled points are not in a degenerate configuration,
                if (!degenerate(sample)) 
                {
                    // Fit model using the random selection of points
                    model = fitting(sample);
                    break; // Exit the while loop.
                }

                samplings++; // Increase the samplings counter
            }

            // Now, evaluate the distances between total points and the model returning the
            //  indices of the points that are inliers (according to a distance threshold t).
            idx = distances(model, points, t);

            // Check if the model was the model which highest number of inliers:
            if (idx.Length &gt; maxInliers)
            {
                // Yes, this model has the highest number of inliers.

                maxInliers = idx.Length;   // Set the new maximum,
                bestModel = model;         // This is the best model found so far,
                bestInliers = idx;         // Store the indices of the current inliers.

                // Update estimate of N, the number of trials to ensure we pick, 
                //   with probability p, a data set with no outliers.
                double pInlier = (double)idx.Length / (double)points.Length;
                double pNoOutliers = 1.0 - System.Math.Pow(pInlier, s);

                N = System.Math.Log(1.0 - probability) / System.Math.Log(pNoOutliers);
            }

            count++; // Increase the trial counter.
        }

        inliers = bestInliers;
        return bestModel;
    }

/// <summary>

/// Computes the model using the RANSAC algorithm.

/// </summary>

public TModel Compute(TData[] points, out int[] inliers)

{

// We are going to find the best model (which fits

// the maximum number of inlier points as possible).

TModel bestModel = null;

int[] bestInliers = null;

int maxInliers = 0;

// For this we are going to search for random samples

// of the original points which contains no outliers.

int count = 0; // Total number of trials performed

double N = maxEvaluations; // Estimative of number of trials needed.

// While the number of trials is less than our estimative,

// and we have not surpassed the maximum number of trials

while (count < N && count < maxEvaluations)

{

int[] idx;

TModel model = null;

int samplings = 0;

// While the number of samples attempted is less

// than the maximum limit of attempts

while (samplings < maxSamplings)

{

// Select at random s datapoints to form a trial model.

idx = Statistics.Tools.Random(points.Length, s);

TData[] sample = points.Submatrix(idx);

// If the sampled points are not in a degenerate configuration,

if (!degenerate(sample))

{

// Fit model using the random selection of points

model = fitting(sample);

break; // Exit the while loop.

}

samplings++; // Increase the samplings counter

}

// Now, evaluate the distances between total points and the model returning the

// indices of the points that are inliers (according to a distance threshold t).

idx = distances(model, points, t);

// Check if the model was the model which highest number of inliers:

if (idx.Length > maxInliers)

{

// Yes, this model has the highest number of inliers.

maxInliers = idx.Length; // Set the new maximum,

bestModel = model; // This is the best model found so far,

bestInliers = idx; // Store the indices of the current inliers.

// Update estimate of N, the number of trials to ensure we pick,

// with probability p, a data set with no outliers.

double pInlier = (double)idx.Length / (double)points.Length;

double pNoOutliers = 1.0 - System.Math.Pow(pInlier, s);

N = System.Math.Log(1.0 - probability) / System.Math.Log(pNoOutliers);

}

count++; // Increase the trial counter.

}

inliers = bestInliers;

return bestModel;

}

Besides the generic parameters, the class utilizes three delegated functions during execution.

The Fitting function, which should accept a subset of the data and use it to fit a model of the chosen type, which should be returned by the function;
The Degenerate function, which should check if a subset of the training data is already known to result in a poor model, to avoid unnecessary computations; and
The Distance function, which should accept a model and a subset of the training data to compute the distance between the model prediction and the expected value for a given point. It should return the indices of the points only whose predicted and expected values are within a given threshold of tolerance apart.

Using the code

In the following example, we will fit a simple linear regression of the form x→y using RANSAC. The first step is to create a RANSAC algorithm passing the generic type parameters of the model to be build, i.e. SimpleLinearRegression and of the data to be fitted, i.e. a double array.

In this case we will be using a double array because the first position will hold the values for the input variable x. The second position will be holding the values for the output variables y. If you are already using .NET 4 it is possible to use the Tuple type instead.

    // Create a RANSAC algorithm to fit a simple linear regression
    var ransac = new RANSAC&lt;SimpleLinearRegression, double[]&gt;(minSamples);
    ransac.Probability = probability;
    ransac.Threshold = errorThreshold;
    ransac.MaxEvaluations = maxTrials;

// Create a RANSAC algorithm to fit a simple linear regression

var ransac = new RANSAC<SimpleLinearRegression, double[]>(minSamples);

ransac.Probability = probability;

ransac.Threshold = errorThreshold;

ransac.MaxEvaluations = maxTrials;

After the creation of the RANSAC algorithm, we should set the delegate functions which will tell RANSAC how to fit a model, how to tell if a set of samples is degenerate and how to check for inliers in data.

    // Set the RANSAC functions to evaluate and test the model

    ransac.Fitting = // Define a fitting function
        delegate(double[][] sample)
        {
            // Retrieve the training data
            double[] inputs = sample.GetColumn(0);
            double[] outputs = sample.GetColumn(1);

            // Build a Simple Linear Regression model
            var r = new SimpleLinearRegression();
            r.Regress(inputs, outputs);
            return r;
        };

    ransac.Degenerate = // Define a check for degenerate samples
        delegate(double[][] sample)
        {
            // In this case, we will not be performing such checkings.
            return false;
        };

    ransac.Distances = // Define a inlier detector function
        delegate(SimpleLinearRegression r, double[][] sample, double threshold)
        {
            List&lt;int&gt; inliers = new List&lt;int&gt;();
            for (int i = 0; i &lt; sample.Length; i++)
            {
                // Compute error for each point
                double input = sample[i][0];
                double output = sample[i][1];
                double error = r.Compute(input) - output;

                // If the squared error is below the given threshold,
                //  the point is considered to be an inlier.
                if (error * error &lt; threshold)
                    inliers.Add(i);
            }
            return inliers.ToArray();
        };

// Set the RANSAC functions to evaluate and test the model

ransac.Fitting = // Define a fitting function

delegate(double[][] sample)

{

// Retrieve the training data

double[] inputs = sample.GetColumn(0);

double[] outputs = sample.GetColumn(1);

// Build a Simple Linear Regression model

var r = new SimpleLinearRegression();

r.Regress(inputs, outputs);

return r;

};

ransac.Degenerate = // Define a check for degenerate samples

delegate(double[][] sample)

{

// In this case, we will not be performing such checkings.

return false;

};

ransac.Distances = // Define a inlier detector function

delegate(SimpleLinearRegression r, double[][] sample, double threshold)

{

List<int> inliers = new List<int>();

for (int i = 0; i < sample.Length; i++)

{

// Compute error for each point

double input = sample[i][0];

double output = sample[i][1];

double error = r.Compute(input) - output;

// If the squared error is below the given threshold,

// the point is considered to be an inlier.

if (error * error < threshold)

inliers.Add(i);

}

return inliers.ToArray();

};

Finally, all we have to do is call the Compute method passing the data. The best model found will be returned by the function, while the given set of inliers indices for this model will be returned as an out parameter.

// Finally, try to fit the regression model using RANSAC
int[] inlierIndices; // indices for inlier points in the data set
SimpleLinearRegression rlr = ransac.Compute(data, out inlierIndices);

// Finally, try to fit the regression model using RANSAC

int[] inlierIndices; // indices for inlier points in the data set

SimpleLinearRegression rlr = ransac.Compute(data, out inlierIndices);

Sample application

The accompanying source application demonstrates the fitting of the simple linear regression model with and without using RANSAC. The application accepts Excel worksheets containing the independent values in the first column and the dependent variables in the second column.

References

Wikipedia contributors. RANSAC. Wikipedia, The Free Encyclopedia.
P. D. Kovesi. MATLAB and Octave Functions for Computer Vision and Image Processing. School of Computer Science & Software Engineering, The University of Western Australia.

40 Comments

Krste says:

August 22, 2010 at 10:56 pm

Hi

I am very new into c# programing and so my question is (maybe) a little bit stupid. But I am trying to adapt your code into the .net Micro framework. I know some about RANSAC and I can follow your code, except that I dont really follow how you set up the linear model in your example case, (I intend to use it for laser ranger data so a linear model is what I want) SimpleLinearRegression, is that in some class of the .net Accord or do you define it somewhere?!

Thanks in advance

Reply
César Souza says:

August 23, 2010 at 1:33 am

Hi Krste,

The SimpleLinearRegression is indeed a class from the Accord.NET Framework. However, if you have downloaded the compressed archive containing the source code from the top of the page, you will find it inside the “SourcesAccord.StatisticsModelsRegressionLinear” folder.

The setup of RANSAC to perform linear regression is done using delegates (or lambda functions). The fitting function should accept a function (if you are used to C, think of it as a function pointer) that accepts a set of input/output pairs and then builds a SimpleLinearRegression model using them.

In the example I have used anonymous delegates to keep the code shorter, but you can also define methods as usual, such as:

private SimpleLinearRegression yourFittingFn(double[][] samples)
{
// … your code here
}

and then set up the algorithm as:

ransac.Fitting = yourFittingFn;

I hope I have answered your question. If this was not what you were asking for, or if you need further clarifications, please ask.

Regards,
César

Reply
Krste says:

August 23, 2010 at 1:08 pm

Many Thanks César!

That did help alot and sorted some things out for me, had missed that class in the statisitcs folder while browsing around in visual studio.

Will give this a try now to port it over!

Regards
Krste

Reply
1. sysacad says:
  
  January 3, 2017 at 9:03 am
  
  Thanks for sharing
  
  Reply
Alex says:

December 16, 2010 at 7:24 am

How to use the RANSAC to check another model? Example the round and oval.

Reply
César Souza says:

December 16, 2010 at 10:38 pm

Hi Alex,

It all depends on how you model your problem. The main goal of RANSAC is to produce a robust parameter estimate of any model. If you wish to make RANSAC work with a oval model (I suppose you mean a multivariate Gaussian?) then all it would be just a matter of implementing suitable fitting and distance functions.

The latest version of the Accord.NET Framework does support fitting of multivariate Gaussians and even mixture models. By defining a fitting function which fits such a model instead of a Linear Regression it would be possible to produce robust estimates for your Gaussian model. The distance function could be created such as to consider the probability of each sample in the model.

Best regards,
César

Reply
Alex says:

December 23, 2010 at 4:38 pm

Thanks for your advice, although I do not really understand what you mean, but I will try to read more information.
I now understand that the content is RANSAC if you want to use other models, as long as the change in model formula, for example, would use the round when the model is the circumference of the circle or into the area formula is the only thing on it?
This is an article using the GOOGLE translation, because my English is not very good, resulting in the inconvenience that you read here with your apology.

Reply
Alex says:

December 24, 2010 at 1:10 am

Thanks for the advice, but do not know what I understand right.
RANDAC If you want to use that model to other models as long as the formula into the family to stay with it?
This is an article using the GOOGLE translation, because my English is not very good.

Reply
Anonymous says:

January 4, 2011 at 4:34 pm

Hi!
I’m very interested about this topic and I would like to see your winrar archive where is the source code.
But there is a problem to up archive.

Can you resolve it or send me the two archive ?

Thanks
laugierdamien@yahoo.fr

Reply
César Souza says:

January 4, 2011 at 9:55 pm

Hi Laugier,

Thanks for reporting the broken links. I’ve corrected them and also hosted the sample application directly on the Accord.NET Sample applications page.

Best regards,
César

Reply
Anonymous says:

April 12, 2011 at 3:42 pm

Just wondering if I can use this code for plane fitting. Any ideas?

Reply
César Souza says:

April 12, 2011 at 4:01 pm

Hi Anonymous,

Well, probably yes. Perhaps replacing SimpleLinearRegression with MultipleLinearRegression (and adjusting the fitting and distance functions) should do the trick.

Best regards,
Cesar

Reply
Anonymous says:

May 26, 2011 at 5:18 pm

The code examples you have posted here do not coincide with the current version of the code in the Accord.NET framework. It is difficult to figure out what modifications need to be made to make this work in the current framework. It would be nice if the sample application were open-source as well.

Reply
César Souza says:

May 26, 2011 at 5:34 pm

Hi Anonymous,

The sample applications are open-source. They are available together with the framework under the folder Samples (available in the Start Menu). They can also be viewed online at google code. The code available here is available in the MachineLearning/Ransac sample application.

Best regards,
César

Reply
Anonymous says:

June 10, 2011 at 7:41 pm

Hi Cesar,

i am also looking for a fast and reliable way to determine a plane (plane fitting). Do you have any idea what I would have to change to your code in order to input depth values for a given position (x,y) and determine the plane???

I saw that you suggested above using the MultipleLinearRegression Class but to be honest I don’t have a clue how to use it in order to get for instance two lines or the parameters that describe the plane in which the most depth values are.

It would be great if you have any suggestion how to solve this problem.

Thanks! 🙂

Reply
Anonymous says:

June 10, 2011 at 7:54 pm

(Same Anonymous AA as above 🙂 )

P.S.: How fast is the calculation of the plane? Would it be possible to do it in a real-time stream of depth values???

Best regards,AA

Reply
César Souza says:

June 10, 2011 at 11:30 pm

Hi Anonymous!

Here is a sample on how to use a multiple linear regression to fit a plane. I hope it does not look garbled without the formatting.

// We will try to model a plane as an equation in the form
// “ax + by + c = z”. We have two input variables (x and y)
// and we will be trying to find two parameters a and b and
// an intercept term c.

// Create a multiple linear regression for two input and an intercept
MultipleLinearRegression target = new MultipleLinearRegression(2, true);

// Now suppose you have some points
double[][] inputs =
{
new double[] { 1, 1 },
new double[] { 0, 1 },
new double[] { 1, 0 },
new double[] { 0, 0 },
};

// located in the same Z (z = 1)
double[] outputs = { 1, 1, 1, 1 };

// Now we will try to fit a regression model
double error = target.Regress(inputs, outputs);

// As result, we will be given the following:
double a = target.Coefficients[0]; // a = 0
double b = target.Coefficients[1]; // b = 0
double c = target.Coefficients[2]; // c = 1

// This is the plane described by the equation
// ax + by + c = z => 0x + 0y + 1 = z => 1 = z.

I hope it helps!

Best regards,
César

Reply
Anonymous says:

June 13, 2011 at 4:21 pm

Hi Cesar,

thanks you for your great example of plane fitting.

I still have one more question. This example works if the data is assumed to be correct. If I input let’s say 1000 points with their x,y coordinates and corespondig z value I still need to run the outcome somehow through Ransac if I have outliers.

Am I right? Or is the MultipleLinearRegression already so robust against outliers?

Thansk for your kind help and patience 🙂

Reply
César Souza says:

June 13, 2011 at 4:42 pm

Hi Anonymous,

Yes, you still have to run MultipleLinearRegression through RANSAC in order to build a robust model. The Fitting and Distance functions should be very similar to the ones presented here, tough using MultipleLinearRegression instead of SimpleLinearRegression. In the Degenerate function, you can add a restriction to avoid fitting if there are less than 3 points (at least 3 points are required to define a plane).

Well, I hope it helps! If you eventually get it working, please let me know of your results.

Best regards,
César

Reply
Anonymous says:

June 13, 2011 at 5:46 pm

Hi Cesar,

I am not sure how to adapt the degenerate function to avoid fitting for less than 3 points. What should it return? True or false if the condition that the samples.Length is not at least 3? I will paste the code. Maybe you can tell if this is so correct.

// We will try to model a plane as an equation in the form
// “ax + by + c = z”. We have two input variables (x and y)
// and we will be trying to find two parameters a and b and
// an intercept term c.

// Now suppose you have some points with coordinates x,y
double[][] inputs =
{
new double[] { 1, 1 }, // P0(1,1)
new double[] { 0, 1 }, // P1(0,1)
new double[] { 1, 0 }, // P2(1,0)
new double[] { 0, 0 }, // P3(0,0)
new double[] { 1, 2 }, // P4(1,2)
new double[] { 1, 3 }, // P5(1,3)
new double[] { 1, 4 }, // P6(1,4)
new double[] { 2, 1 } // P7(2,1)
};

// Z depth values for each of the above specified points (in order)
double[] outputs = { 1, 1, 0.9, 1, 1.2, 1.1, 3, 1 };

// Create a multiple linear regression for two input and an intercept
MultipleLinearRegression target = new MultipleLinearRegression(2, true);

// Now we will try to fit a regression model
double errorMLR = target.Regress(inputs, outputs);

// As result, we will be given the following:
double a = target.Coefficients[0]; // a = 0
double b = target.Coefficients[1]; // b = 0
double c = target.Coefficients[2]; // c = 1

// This is the plane described by the equation
// ax + by + c = z => 0x + 0y + 1 = z => 1 = z.

Console.WriteLine(“MultipleLinearRegression plane fitting…”);
Console.WriteLine(“{0} * x + {1} * y + {2} = z”, a, b, c);

// Now, fit simple linear regression using RANSAC
int maxTrials = (int) 500; // numMaxTrials.Value;
int minSamples = (int) 3; // numSamples.Value;
double probability = (double) 0.95; //numProbability.Value;
double errorThreshold = (double)0.1; //numThreshold.Value;

// Create a RANSAC algorithm to fit a simple linear regression
var ransac = new RANSAC(minSamples);
ransac.Probability = probability;
ransac.Threshold = errorThreshold;
ransac.MaxEvaluations = maxTrials;

// Set the RANSAC functions to evaluate and test the model

ransac.Fitting = // Define a fitting function
delegate(int[] sample)
{
// Retrieve the training data
double[][] subInputs = inputs.Submatrix(sample);
double[] subOutputs = outputs.Submatrix(sample);

// Build a MultipleLinearRegression model
var r = new MultipleLinearRegression(2,true);
r.Regress(subInputs, subOutputs);
return r;
};

ransac.Degenerate = // Define a check for degenerate samples
delegate(int[] sample)
{
if (sample.Length < 3)
{
return true; // is the restriction correct????
}
// In this case, we will not be performing such checkings.
return false;
};

ransac.Distances = // Define a inlier detector function
delegate(MultipleLinearRegression r, double threshold)
{
List inliers = new List();
for (int i = 0; i < inputs.Length; i++)
{
// Compute error for each point
double error = r.Compute(inputs[i]) – outputs[i];

// If the squared error is below the given threshold,
// the point is considered to be an inlier.
if (error * error < threshold)
inliers.Add(i);
}
return inliers.ToArray();
};

Reply
Anonymous says:

June 13, 2011 at 5:46 pm

// Finally, try to fit the regression model using RANSAC
int[] idx; MultipleLinearRegression rlr = ransac.Compute(inputs.Length, out idx);

// Check if RANSAC was able to build a consistent model
if (rlr == null)
{
Console.WriteLine(“RANSAC was unsucessfull…”);
return; // RANSAC was unsucessful, just return.
}
else
{
// Compute the output of the model fitted by RANSAC
double[] rlrY = rlr.Compute(inputs);

a = rlr.Coefficients[0]; // a = 0
b = rlr.Coefficients[1]; // b = 0
c = rlr.Coefficients[2]; // c = 1

Console.WriteLine(“RANSAC-fitted plane using MultipleLinearRegression…”);
Console.WriteLine(“{0} * x + {1} * y + {2} = z”, a, b, c);
}

My output in this case is:
MultipleLinearRegression plane fitting…
-0.111842105263157 * x + 0.397697368421053 * y + 0.776315789473682 = z
RANSAC-fitted plane using MultipleLinearRegression…
-8.88178419700125E-16 * x + 0.0999999999999988 * y + 0.9 = z

Do you think that this code and results look Ok?
Is the Degenerate function implemented correctly? Should it return true or false if it should skip in case of samples.Length < 3???

Reply
Anonymous says:

June 13, 2011 at 5:47 pm

Hi Cesar,

I am not sure how to adapt the degenerate function to avoid fitting for less than 3 points. What should it return? True or false if the condition that the samples.Length is not at least 3? I will paste the code. Maybe you can tell if this is so correct.

// We will try to model a plane as an equation in the form
// “ax + by + c = z”. We have two input variables (x and y)
// and we will be trying to find two parameters a and b and
// an intercept term c.

// Now suppose you have some points with coordinates x,y
double[][] inputs =
{
new double[] { 1, 1 }, // P0(1,1)
new double[] { 0, 1 }, // P1(0,1)
new double[] { 1, 0 }, // P2(1,0)
new double[] { 0, 0 }, // P3(0,0)
new double[] { 1, 2 }, // P4(1,2)
new double[] { 1, 3 }, // P5(1,3)
new double[] { 1, 4 }, // P6(1,4)
new double[] { 2, 1 } // P7(2,1)
};

// Z depth values for each of the above specified points (in order)
double[] outputs = { 1, 1, 0.9, 1, 1.2, 1.1, 3, 1 };

// Create a multiple linear regression for two input and an intercept
MultipleLinearRegression target = new MultipleLinearRegression(2, true);

// Now we will try to fit a regression model
double errorMLR = target.Regress(inputs, outputs);

// As result, we will be given the following:
double a = target.Coefficients[0]; // a = 0
double b = target.Coefficients[1]; // b = 0
double c = target.Coefficients[2]; // c = 1

// This is the plane described by the equation
// ax + by + c = z => 0x + 0y + 1 = z => 1 = z.

Console.WriteLine(“MultipleLinearRegression plane fitting…”);
Console.WriteLine(“{0} * x + {1} * y + {2} = z”, a, b, c);

// Now, fit simple linear regression using RANSAC
int maxTrials = (int) 500; // numMaxTrials.Value;
int minSamples = (int) 3; // numSamples.Value;
double probability = (double) 0.95; //numProbability.Value;
double errorThreshold = (double)0.1; //numThreshold.Value;

// Create a RANSAC algorithm to fit a simple linear regression
var ransac = new RANSAC(minSamples);
ransac.Probability = probability;
ransac.Threshold = errorThreshold;
ransac.MaxEvaluations = maxTrials;

// Set the RANSAC functions to evaluate and test the model

ransac.Fitting = // Define a fitting function
delegate(int[] sample)
{
// Retrieve the training data
double[][] subInputs = inputs.Submatrix(sample);
double[] subOutputs = outputs.Submatrix(sample);

// Build a MultipleLinearRegression model
var r = new MultipleLinearRegression(2,true);
r.Regress(subInputs, subOutputs);
return r;
};

ransac.Degenerate = // Define a check for degenerate samples
delegate(int[] sample)
{
if (sample.Length < 3)
{
return true; // is the restriction correct????
}
// In this case, we will not be performing such checkings.
return false;
};

ransac.Distances = // Define a inlier detector function
delegate(MultipleLinearRegression r, double threshold)
{
List inliers = new List();
for (int i = 0; i < inputs.Length; i++)
{
// Compute error for each point
double error = r.Compute(inputs[i]) – outputs[i];

// If the squared error is below the given threshold,
// the point is considered to be an inlier.
if (error * error < threshold)
inliers.Add(i);
}
return inliers.ToArray();
};

Reply
Anonymous says:

June 13, 2011 at 5:49 pm

The two comments above are in the incorrect order… Don’t know why the comments have been reversed. Maximum comment length was 4096 chars so I had to split them.

P.S.: Evtl. we could also communicate via Email if you do not wish to spam your blog here 🙂

Reply
Anonymous says:

June 15, 2011 at 4:44 pm

Hi Cesar,

do you think the above code looks good for plane fitting??

Reply
César Souza says:

June 15, 2011 at 6:16 pm

Hi Anonymous,

For some reason, I haven’t received any notifications about your new comments. Sorry about that.

Reading better our discussion, I see I said it would be nice to check if you have at least three points in the Degenerate function. However, what I really meant was that it would be nice to check that you have at least three points not forming a line (i.e. at least three non collinear points). If this becomes too cumbersome to implement, just ignore it and make the Degenerate function return false as usual. It should work anyways.

If you wish, we can talk by email. My email is available on the top of any of the source codes.

Best regards,
César

Reply
sorna says:

March 1, 2012 at 9:59 am

Wonderful blog & good post.Its really helpful for me, awaiting for more new post. Keep Blogging!

Function Point Estimation Training

Reply
Anonymous says:

October 17, 2012 at 8:23 pm

hello César
plz can you send me the full code of program

Reply
Anonymous says:

October 17, 2012 at 8:25 pm

code of program in c# plzzz

Reply
César Souza says:

October 17, 2012 at 8:42 pm

Hi there,

Sorry for the broken links. The full application, including source code, is available at the RANSAC sample application description page. It is also available as part of the Accord.NET Framework. I will fix the broken links, thanks for letting me know about that.

Best regards,
Cesar

Reply
David Purcell says:

January 6, 2013 at 11:24 pm

Hey Cesar, I just wanted to thank you for the excellent resource. I am curious, have you ever attempted to use RANSAC with the Kinect data streams?

Reply
César Souza says:

January 7, 2013 at 12:32 am

Hi David, thanks for the positive feedback!

Yes, I had in fact tried to use RANSAC for 3D plane detection using Kinect, but I didn’t achieve astonishing results. In principle it was supposed to work, but I did only as a quick attempt for a quick hack to help in the middle of something else. So probably it didn’t work well because of some error on my part, and there wasn’t much motivation to make it work at the time, as I had to focus on some other things as well.

Another thing that I tried was to use the image stitching technique to automatically sync the color and depth images of the Kinect. However, this also involves building a drilled checkerboard or some other kind of material which could help matching depth and intensity interest points. Again, while this would seem to work in practice, I never got to build the wooden/cardboard frame for the calibration to work :/

Perhaps you could have more luck than I in getting those to work!

Best regards,
Cesar

Reply
Reef Neherov says:

January 20, 2013 at 8:21 am

This comment has been removed by the author.

Reply
Giullian Franke says:

May 11, 2014 at 3:00 pm

Hey César Souza,

I actually in the situation. I want to detect a 3D plane from Kinect depth data. You wrote that u started this approach to. Maybe you can give me some starting points for that?

Best regards,
Xantalor

Reply
jamie says:

April 30, 2015 at 8:03 pm

Hi Cesar,
This was really an interesting topic. Thank you for this!
I’m trying to access the source code and application but they seemed to be broken. I tried several other links that you had put in the comments but no luck. Can you please upload them?

Thank you

Reply
jamie says:

April 30, 2015 at 8:25 pm

Hi Cesar,
This was really an interesting topic. Thank you for this!
I’m trying to access the source code and application but they seemed to be broken. I tried several other links that you had put in the comments but no luck. Can you please upload them?

Thank you !

Reply
cesarsouza@gmail.com says:

May 1, 2015 at 7:57 am

Hi Jamie!

The updated links are available here: https://github.com/accord-net/framework/wiki/Sample-applications#random-sample-consensus-ransac

The framework source code site has moved to http://accord-framework.net/ and all the sample applications, including RANSAC, can also be found here.

Sorry for the inconvenience!

Best regards,
Cesar

Reply
jamie says:

May 1, 2015 at 10:15 pm

Thank you Cesar for the prompt response!
I appreciate it!

Reply
Sami says:

June 25, 2015 at 6:34 pm

Dear César Souza,

Let me start first by thanking you for the interesting topic.

I wanted to use RANSAC to detect rectangles in a 3D environment, but I do not know how to begin. I do not have a lot of experience in C#. Please, can you help me.

Best regards,
Sami.

Reply
Donn Hardy says:

August 24, 2016 at 3:29 pm

I find this library very useful! Thanks so much.

However, I notice that the sample code uses several functions that are marked obsolete. Any plans to update that soon? Specifically, SimpleLinearRegression.Regress has been marked as obsolete. Could you give an example of how to replace that with the recommended OrdinaryLeastSquares class?

Reply
1. cesarsouza says:
  
  September 4, 2016 at 4:11 pm
  
  Yes! Definitively, this is in the works. In the meantime, the new way to learn a SimpleLinearRegression is through the OrdinaryLeastSquares.Learn(x, y) method.
  
  Simply create an instance of the OrdinaryLeastSquares class and pass the data to be learned to its .Learn() method. It should then return a Linear Regression object trained estimated from the data.
  
  Hope it helps!
  
  Regards,
  Cesar
  
  Reply