CODEWITHSUNDEEP
clinelinear-regression
Morgoth
Morgoth

Reputation: 5174

Line fit from an array of 2d vectors

I have a problem in some C code, I assume it belonged here over the Mathematics exchange.

I have an array of changes in x and y position generated by a user dragging a mouse, how could I determine if a straight line was drawn or not.

I am currently using linear regression, is there a better(more efficient) way to do this?

EDIT: Hough transformation attempt:

#define abSIZE 100
#define ARRAYSIZE 10
int A[abSIZE][abSIZE]; //points in the a-b plane
int dX[10] = {0, 10, 13, 8, 20, 18, 19, 22, 12, 23};
int dY[10] = {0,  2,  3, 1, -1, -2,  0,  0,  3,  1};
int absX[10]; //absolute positions
int absY[10];
int error = 0;
int sumx = 0, sumy = 0, i;

//Convert deltas to absolute positions
for (i = 0; i<10; i++) {
    absX[i] = sumx+=dX[i];
    absY[i] = sumy+=dY[i];
}

//initialise array to zero
int a, b, x, y;
for(a = -abSIZE/2; a < abSIZE/2; a++) {  
    for(b = -abSIZE/2; b< abSIZE/2; b++) {
            A[a+abSIZE/2][b+abSIZE/2] = 0;
    }
}

//Hough transform
int aMax = 0;
int bMax = 0;
int highest = 0;
for(i=0; i<10; i++) {
    x = absX[i];
    y = absX[i];
    for(a = -abSIZE/2; a < abSIZE/2; a++) {  
        for(b = -abSIZE/2; b< abSIZE/2; b++) {
            if (a*x + b == y) {
                A[a+abSIZE/2][b+abSIZE/2] += 1;
                if (A[a+abSIZE/2][b+abSIZE/2] > highest) {
                    highest++; //highest = A[a+abSIZE/2][b+abSIZE/2]
                    aMax = a;
                    bMax = b;
                }
            }
        }
    }
}

printf("Line is Y = %d*X + %d\n",aMax,bMax);
//Calculate MSE
int e;
for (i = 0; i < ARRAYSIZE; i++) {
    e = absY[i] - (aMax * absX[i] + bMax);
    e = (int) pow((double)e, 2);
    error += e;
}
printf("error is: %d\n", error);

Upvotes: 2

Views: 276

Answers (1)

Pavel
Pavel

Reputation: 7562

Though linear regression sounds like a perfectly reasonable way to solve the task, here's another suggestion: Hough transform, which might be somewhat more robust against outliers. Here is a very rough sketch of how this can be applied:

  • initialize a large matrix A with zeros
  • transform your deltas to some absolute coordinates (x, y) in a x-y-plane (e.g. start with (0,0))
  • for each point
    • there are non-unique parameters a and b such that a*x + b = y. All such points (a,b) define a straight line in the a-b-plane
    • draw this "line" in the a-b-plane by adding ones to the corresponding cells in A, which represents the quantized plane
  • now you can find a maximum in the a-b-plane-matrix A, which will correspond to the parameters (a, b) of the straight line in the x-y-plane that has most support by the original points
  • finally, calculate MSE to the original points and decide with some threshold if the move was a straight line

More details e.g. here:

http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARSHALL/node32.html

Edit: here's a quote from Wikipedia that explains why it's better to use a different parametrization to deal with vertical lines (where a would become infinite in ax+b=y):

However, vertical lines pose a problem. They are more naturally described as x = a and would give rise to unbounded values of the slope parameter m. Thus, for computational reasons, Duda and Hart proposed the use of a different pair of parameters, denoted r and theta, for the lines in the Hough transform. These two values, taken in conjunction, define a polar coordinate. polar form

Thanks to Zaw Lin for pointing this out.

Upvotes: 2

Related Questions