Detect aligned points in set of points OpenCV

Question

Given a set of points on an image, I want to detect groups of aligned points as shown in the figure:

How can I do this? Any help will be appreciated.

Answer 1

This is a good potential application of the Hough Transform. The Hough space for lines is (r, \theta) where r is the distance from origin to closest point on line and \theta is its orientation.

Each point in x-y space becomes a sinusoid in Hough space as shown in the Wiki article.

The places where all the sinusoids intersect corresponds to a single line that passes through all the points. If the points are not perfectly colinear, the intersection will be "fuzzy".

The simplest algorithm to fit lines to points is to make a rectangular (r, \theta) accumulator array set to zero initially. Then trace a sinusoid for each point into this discrete (r, \theta) space, incrementing each accumulator element by a fixed amount. Find prospective line fits by looking for large array elements. The element coordinates give (r, \theta) for the fit.

Tracing the sinusoid is straightforward. If you have T accumulator bins on the \theta axis then each corresponds to an angle k(\pi)/N for some 0 <= k < T. So for k in this range, calculate the distance from the origin to the closest point of a line with this orientation passing through the point. This provides an r value. If there are R bins on the R axis and Rmax is the maximum value of r, then increment bin (floor(r/rMax*R), k).