Recognize matrix in point group

Question

I have an image that I am developing with my program to get a list of coordinates.

The image shows a matrix. In an ideal test, I would get only sixteen center points of each square of the matrix. But in real tests, I accept quite a few noise points.

I want to use the extrapolation algorithm from the list of coordinates, a group formed by 16 coordinates that best represent the matrix.

The matrix can have any aspect ratio (between the range) and can lead to slight rotation. But there is always a 4x4 matrix. The matrix is ​​not always present in the image, but this is not a problem, I only need a better match. Of course, the based point is always greater than 16 (or I skip)

Example based points:

An example of the expected result:

If anyone can suggest me that there is a preferred way to do this, it would be great.

Im thinking about the Euclidean distance between points.

For each point in the list: 1. calculate the euclidean distance (D) with the others 2. filter that points that D * 3 > image.widht (or height) 3. see if it have at least 2 point at the same (more or less) distance, if not skip 4. if yes put the point in a list and for each same-distance founded points: go to 2nd step. 

in the end, if I have 16 points in the list, it could be a matrix.

Any better suggestion?

thanks

Answer 1

This is the algorithm that comes to mind:

 for each pair of points (p1, p2): let d be the distance vector (x and y) between them if dx > (image.width-p1.x)/3 or dy > (image.height-p1.y)/3: continue let d_t be d turned 90 degrees (dy, -dx) for i from 0 to 3: for j from 0 to 3: if there is no point at p1 + i*d + j*d_t: continue outer loop if you get here, you have a 4*4 grid 

To shorten the run time in half (on average), you can just look at p2, which are to the right of p1.

Answer 2

Depending on how much processor power you want to use, and assuming that "small rotation" means very little, you can try the following: 1) taking only the X-coordinates of the points, we look for clusters of size 4.

2) For each cluster, look at each cluster on the left with a distance d, if there are two more with distances 2 * d and 3 * d.

3) If yes, compare the y coordinates for each of these clusters to make sure they are approximately equal.

Depending on the data, you can get better performance by completing step three before the second step and using it to trim the parameters you consider.