How to draw perfect straight line passing through majority of given points in MATLAB?

Question

Can someone help me figure out how to draw a perfect straight line from given set of points passing through majority (may be 5-6 point out of 20) of these points? Please note that this is not a line fit problem, but perfect line should be drawn (horizontal, vertical or somewhat slanted) between majority of the given points.

Here is MATLAB code:

e=[161    162   193   195   155    40   106   102   125   155   189   192   186   188   185   186   147   148   180   183];

f =[138    92    92   115   258   124   218   114   125   232   431   252   539   463   643   571   582   726   726   676];

figure;scatter(f, e, 5, 'red');

axis ij;

and here is image:

Answer 1

Since you want the line to go through the majority of points, it sounds quite like a line fitting problem even though you say it isn't. Have you looked at the Theil-Sen estimator (for example this one on fex), which is a linear regression ignoring up to some 30% of the outliers.

If you simply want a line through the extrema you might do something like this:

% Setup data
e = [161    162   193   195   155    40   106   102   125   155   189   192   186   188   185   186   147   148   180   183];
f = [138    92    92   115   258   124   218   114   125   232   431   252   539   463   643   571   582   726   726   676];
% Create scatterplot
figure(1);
scatter(f, e, 5, 'red');
axis ij;

% Fit extrema
[min_e, min_idx_e] = min(e);
[max_e, max_idx_e] = max(e);
[min_f, min_idx_f] = min(f);
[max_f, max_idx_f] = max(f);
% Determine largest range and draw line accordingly
if (max_e-min_e)>(max_f-min_f)
    line(f([min_idx_e, max_idx_e]), e([min_idx_e, max_idx_e]), 'color', 'blue')
    text(f(max_idx_e), e(max_idx_e), ' Extrema')
else
    line(f([min_idx_f, max_idx_f]), e([min_idx_f, max_idx_f]), 'color', 'blue')
    text(f(max_idx_f), e(max_idx_f), ' Extrema')
end

% Fit using Theil-Sen estimator
[m, e0] = Theil_Sen_Regress(f', e');
line([min_f, max_f], m*[min_f, max_f]+e0, 'color', 'black')
text(max_f, m*max_f+e0, ' Theil-Sen')

However, as you'll notice neither solution automatically fits the points automatically, simply because there are too many outliers, unless you filter those beforehand. Therefore you probably are better off using the RANSAC algorithm as proposed by Shai and McMa.

Answer 2

That's a textbook example for the RANSAC algorithm. This free toolbox for Matlab actually has some very nice examples of line fitting.