Linear Least Square Fit - Line

[pal...@gmail.com]

Continued from the circle fitting...

I suddenly got a straight line fitting problem...

Math first:
a line in slope-intercept form: y = m * x + b
and we want to find m and b. Written in matrix form:
[ m ]
[ x 1 ] * [ b ] = [ y ]

So we have the matrix:
[ x1 1 ] [ y1 ]
[ x2 1 ] [ m ] [ y2 ]
[ x3 1 ] * [ b ] = [ y3 ]
[ ... ] [ ... ]
[ xn 1 ] [ yn ]
-----------------------------
A t B

First multiply both sides for AT:
A' = AT * A;
B' = AT * B;
we get
A' * t = B'

then solve for t.

here are the codes:

public static Line FitLine(List<IntPoint> points)
{
double[,] A = new double[points.Count, 2];
double[,] B = new double[points.Count, 1];

for (int i = 0; i < points.Count; ++i)
{
A[i, 0] = points[i].X;
A[i, 1] = 1;
B[i, 0] = points[i].Y;
}

double[,] AT = A.Transpose();
double[,] Ap = AT.Multiply(A);
double[,] Bp = AT.Multiply(B);

double[,] t = Matrix.Solve(Ap, Bp, true);

double m = t[0, 0];
double b = t[1, 0];

return Line.FromSlopeIntercept((float)m, (float)b);
}

[César]

Hi there!

It seems you are good at suddenly finding nice problems! Thanks for also providing the detailed explanations!

By the way, did you by any chance compared your method to the recently introduced one at https://code.google.com/p/accord/source/browse/trunk/Sources/Accord.MachineLearning/Geometry/RansacLine.cs#209 ? I suppose I really should have made this method more publicly accessible rather than burying it inside the ransac wrapper. Hope it can also be useful to you!

Best regards,

Cesar

[pal...@gmail.com]

RansacLine is slow.
Because it's a machine learning method and tries to iterate and fit as best as it can.

Linear Least Square Fitting is an pure mathematical approach that doesn't do so much iterations.

and it provides the SAME answer EVERY TIME... unlike RANSAC...
fitting by "LUCK"... and when u're outta karma u just get a strange line landing in the middle of nowhere......

=== cut here ===

only comparing the line finding algorithms, I think they're same methods, just different representations.

I'm not such a math genius so I'm using the method that's closer to what I learned in elementary... XD

[César]

Hi there!

Well, not exactly by luck; it is supposed to produce a robust estimate of the line even in the presence of outliers (i.e. points which do not really belong to the line, but instead could be attributed to noise). Internally, the RANSAC uses the same fitting method, but it tries with different sets of points to see which one fits best within the data points. But I suppose the current version of the RansacLine might not be working as well as the RANSAC line fitting example in the statistics sample applications. I still need to check on that one.

As always, thanks for sharing!

Best regards,

Cesar