RANdom Sample Consensus (RANSAC) in C#

/ cesarsouza / 42 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.

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.

ransac-7

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.

ransac-8

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).

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.

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.

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.

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.

ransac-9

References

42 Comments

  1. 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

  2. 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

  3. 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

  5. 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

  6. 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

  7. 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

  8. 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

  12. 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

  13. 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

  14. 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

  15. (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

  16. 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

  17. 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

  18. 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

  19. 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

  20. // 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

  21. 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

  22. 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

  24. 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

  30. 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

  32. 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

  33. 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

  34. 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

  37. 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

  38. 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. 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
  40. Pingback: A good approach for detecting lines in an image? – inneka.com

Leave a Reply

Your email address will not be published. Required fields are marked *