Recognize a Matrix in a group of points

Question

I have a picture that I elaborate with my program to obtain a list of coordinates.

Represented in the image there is a matrix. In an ideal test i would get only the sixteen central points of each square of the matrix. But in actual tests i take pretty much noise points.

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

The matrix can have any aspect ratio (beetween a range) and can result a little rotated. But is always an 4x4 matrix. The matrix is not always present in the image, but is not a problem, i need only the best matching. Of course the founded point are always more than 16 (or i skip)

Example of founded points:

Example of desidered result:

If anyone can suggest me a preferred way to do this would be great.

Im thinking about the euclidean distance beetween 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.

at the end if i have 16 points in the list, this could be a matrix.

Any better suggestion?

Thank you

Answer 1

This is the algorithm that springs to mind:

for each pair of points (p1, p2):
    let d be the distance vector (x and y) between them
    if d.x > (image.width-p1.x)/3 or d.y > (image.height-p1.y)/3:
        continue
    let d_t be d turned 90 degrees (d.y, -d.x)
    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 cut the running time in half (on average), you could just consider the p2's that are to the right of p1.