1
$\begingroup$

I am wondering if it is usual (best?) to choose the initial size of the set of points as the minimum size, which is needed to derive parameters of the fitting model.

For example, imagine that we are trying to fit a set of N = 1000 points on a plane with a line using RANSAC. To draw a line it is enough to have only 2 points. So the simplest implementation of RANSAC would be

  1. choose 2 points randomly and calculate parameters a and b of the resulting line y = ax + b
  2. find all points, which are within allowed error eps.
  3. recalculate a and b using new points
  4. go to step 2 if the new set of points is larger than initial.

Then one chooses again 2 random points and repeats all the steps above.

My question is following: does it make sense to initially choose not 2 points, but more(3, 4, ...?) points? Because my understanding that all people use the minimal number of points as starting set.

Why do I think that one has to use more starting points? Because imagine 2 inlier points (with noise but still inliers), which have close x values, but different y values. Then initial line will be completely wrong. People say: no problem, the step (2) will add close points and will correct this line and the rest of the loop will add more and more valid points and will finally get the job done. But is this indeed the case?

Improve this question
$\endgroup$
1
  • $\begingroup$ My intuition is that using a batch of point pairs will result in smaller variance. It is like with gradient descent: you can use one point at a time to find the direction of steepest change, or use a small batch. In the latter case, the sporadic variations will be smoothed out. $\endgroup$
    – Vladislavs Dovgalecs
    Jan 12, 2018 at 15:38

1 Answer 1

Reset to default
2
$\begingroup$

During a RANSAC sampling iteration, if a non-robust norm (e.g. L2) is used to fit the model, one can only expect the model to be estimated well if all sampled data points are inliers. In your example this means drawing two sample data points which lie close to the 1D line. The reason why the minimal number of data points is usually used is because it increases the likelihood of drawing a sample set that has no outliers. This in turn usually reduces the number of iterations needed to find a good model. Now why might we think of using more than the minimal number of samples? There are two reasons:

Reason 1: If the data is particularly noisy. In this case it can be better to fit the model to more than the minimal number, which reduces the effect of noise on the estimated model parameters. This might allow you to find a good fitting model earlier, compared to using the minimal number of data points (which may be highly affected by noise). More specifically, when we use the minimal number, we require that our random sample contains both inliers and the measurement noise for each point in the sample is sufficiently small, so that the fitted model generalizes well to the other inliers in the dataset. This product effect may require many more iterations until a sample is drawn that satisfies the condition. As ever, there is a trade-off because using more data points to fit the model reduces the likelihood that all data samples will be inliers (significantly if the proportion of outliers is large).

Reason 2: If the model cannot be determined uniquely with the minimal number of data points in many cases. A concrete example of this is the problem in computer vision for estimating the 3D pose of an object in front of a camera's given a set of matches between the object and the camera's image. This problem is called the pnp problem and RANSAC is used frequently to solve it robustly. The minimal case is when there are 3 data points (called the p3p problem). However depending on their values there can be between zero and four real valued solutions. For this reason many implementations, including OpenCV chose to use non-minimal sampling with 4 or 5 points.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for your answer. my formulation was not precise - when I said 2 valid points I meant exactly what you said - noisy inliers. in that case the initial line can be far from real line and what bothers me in that case is that such wrong initial line may never converge to a good line. $\endgroup$
    – John Smith
    Jan 15, 2018 at 8:38
  • $\begingroup$ I thought that was the case, so I expanded Reason 1 with some more details. Reason 2 is also good to know about and it's definitely important in other applications. $\endgroup$
    – Toby Collins
    Jan 15, 2018 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.