RANSAC: should we always sample with the minimal number of data points? 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


*

*choose 2 points randomly and calculate parameters a and b of the resulting line y = ax + b

*find all points, which are within allowed error eps.

*recalculate a and b using new points

*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?
 A: 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.
