Finding lines between several points

Question

I'm programming to make a image processing application I extract several points from an image as depicted below:

As it can be seen, there are several white points and red lines. White points shows location of key points? I want to extract lines for each group of pixels having this properties:

1- distance among pixels must be almost equal.
2- they must be close together.

Is there any method or approach such as regression or other interpolations to extract lines between pixels? An example of lines that I imagine is depicted in the figure.

Any idea will be appreciated.

Answer 1

You could create a square matrix with each cell representing the distance between two points. To further explain, suppose you have 4 points: $a,b,c,d$ then the rows are labeled $a,b,c,d$ and the columns are labeled $a,b,c,d$. The diagonal of the matrix is zeroes, because the distance of a point to itself is zero.

Then you could iterate through the rows (or columns) doing the following for each:

1. Sort the row in ascending order. The first element will always be zero. Discard it.

2. For each distance in the row, $dist_i$, first check if it is small enough (ie the two points are close enough). Then check to see if there is a sequence of subsequent distances that are close (within a certain tolerance) to a multiple of $dist_i$. The sequence of distances would also need to be long enough to be considered a legitimate line. For example, you may only want to consider a sequence of 4 or more distances (ie 5 points) to be a line. You also need to have a parameter to specify how close to co-linear the points need to be. Therefore you've got four parameters: maximum distance between points (close enough), tolerance of distances between points (distance almost equal), co-linearity, and enough points to be considered a line.

   • After you collect a set of points that are close enough and distances are "regular" enough, you can perform linear least square regression of the points. Then you can decide whether the points should all be part of the line based on either 1) the sum of the residuals is small enough or 2) whether each point is close enough to the calculated line. If you use 2) then you'll need to iterate if you take out points that are too far from the calculated line.

   • Note that it is possible to have more than one line associated with a single row, so even after a line is detected in a given row, you need to keep iterating through $dist_i$, skipping any points already part of any lines associated with that row.

   • As an example suppose the third distance in a row is $2.2$. Then you find that the fifth distance is $4.47$, the seventh is $6.53$, and the twelfth is $8.83$ and $4.47,6.53,8.83$ are all with your tolerance and $2.2$ is close enough. Then you have a possible line with five points. If all these points, except the last are close to co-linear, then the least squares of this data might show a slope of $1.3$ and a $y$ intercept of $-0.2$. You then might find that the last point is a significantly larger distance from the fitted line than the other four points. If you delete the last point, the slope might be $1$, and y intercept $0$, and the remaining four points are close to the fitted line. But if you have to keep deleting points and are left with fewer than the minimum number of points parameter, then those points don't make a line.

3. If the current row doesn't match the 4 criteria, then the point that row represents is not part of a line.

4. As you iterate through the rows keep track of points that have already been found to be part of a line and to make sure you don't create the same line twice. But also allowing for the case that two intersecting lines may have a one (or more) points in common. (Depending on your parameters you could have intersecting lines with 2 or 3 or more points in common.)

Or instead of all this, you might want to google for "image processing detecting lines".

Answer 2

1. Use a clustering algorithm to divide points into clusters.
2. For each cluster, run a linear regression to generate the equation of the best-fit line.