Detecting aligned points in an OpenCV point set
This is a good potential Hough Transform app . Howe space for lines is (r, \ theta), where r is the distance from the origin to the nearest point on the line and \ theta is its orientation.
Each point in xy space becomes a sinusoid in Hough space, as shown in the Wiki article.
The places where all sinusoids intersect correspond to a single line passing through all points. If the points are not completely collinear, the intersection will be "fuzzy".
The simplest algorithm to match lines to points is to first create a rectangular (r, \ theta) accumulator array equal to zero. Then trace a sinusoid for each point in that discrete (r, \ theta) space, increasing each cell of the accumulator by a fixed amount. Find perspective lines fits by looking for large array elements. Element coordinates give (r, \ theta) to match.
Sine wave tracing is simple. If you have T accumulators on the \ theta axis, then each of them 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 nearest point of the line with this orientation passing through the point. This gives the value r. If there are R-buns on the R-axis and Rmax is the maximum value of r, then the increment is bin (floor (r / rMax * R), k).
source to share
In the beginning, you can try the following:
-
List all lines that can be formed by selecting any two of these points (
n(n-1)/2
for pointsn
). -
For any two of these lines, check to see if they are aligned (for example, the slope of the diff is within 10 degrees).
-
For each aligned pair, you can easily check if other points on these lines are aligned. And these points will be the orientation points you need.
source to share