Line Passing Through Given Points

I am trying t开发者_开发知识库o find the angle of the outer line of the object in the green region of the image as shown in the image above…

For that, I have scanned the green region and get the points (dark blue points as shown in the image)...

As you can see, the points are not making straight line so I can’t find angle easily.

So I think I have to find a middle way and that is to find the line so that the distance between each point and line remain as minimum as possible.

So how can I find the line so that each point exposes minimum distance to it……?

Is there any algorithm for this or is there any good way other than this?

The obvious route would be to do a least-squares linear regression through the points.

The standard least squares regression formulae for x on y or y on x assume there is no error in one coordinate and minimize the deviations in the coordinate from the line.

However, it is perfectly possible to set up a least squares calculation such that the value minimized is the sum of squares of the perpendicular distances of the points from the lines. I'm not sure whether I can locate the notebooks where I did the mathematics - it was over twenty years ago - but I did find the code I wrote at the time to implement the algorithm.

With:

• n = ∑ 1
• sx = ∑ x
• sx2 = ∑ x²
• sy = ∑ y
• sy2 = ∑ y²
• sxy = ∑ x·y

You can calculate the variances of x and y and the covariance:

• v_x = sx2 - ((sx * sx) / n)
• v_y = sy2 - ((sy * sy) / n)
• v_xy = sxy - ((sx * sy) / n)

Now, if the covariance is 0, then there is no semblance of a line. Otherwise, the slope and intercept can be found from:

• slope = quad((vx - vy) / vxy, vxy)
• intcpt = (sy - slope * sx) / n

Where quad() is a function that calculates the root of quadratic equation x² + b·x - 1 with the same sign as c. In C, that would be:

double quad(double b, double c)
{
    double b1;
    double q;

    b1 = sqrt(b * b + 4.0);
    if (c < 0.0)
        q = -(b1 + b) / 2;
    else
        q = (b1 - b) / 2;
    return (q);
}

From there, you can find the angle of your line easily enough.

Obviously the line will pass through averaged point (x_average,y_average).

For direction you may use the following algorithm (derived directly from minimizing average square distance between line and points):

dx[i]=x[i]-x_average;
dy[i]=y[i]-y_average;

a=sum(dx[i]^2-dy[i]^2);
b=sum(2*dx[i]*dy[i]);

direction=atan2(b,a);

Usual linear regression will not work here, because it assumes that variables are not symmetric - one depends on other, so if you will swap x and y, you will have another solution.

The hough transform might be also a good option:

http://en.wikipedia.org/wiki/Hough_transform

You might try searching for "total least squares", or "least orthogonal distance" but when I tried that I saw nothing immediately applicable.

Anyway suppose you have points x[],y[], and the line is represented by a*x+b*y+c = 0, where hypot(a,b) = 1. The least orthogonal distance line is the one that minimises Sum{ (a*x[i]+b*y[i]+c)^2}. Some algebra shows that:

c is -(a*X+b*Y) where X is the mean of the x's and Y the mean of the y's.

(a,b) is the eigenvector of C corresponding to it's smaller eigenvalue, where C is the covariance matrix of the x's and y's