Matrix Pattern Recognition Algorithm for a 2D space

Question

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

There is a matrix represented in the image. In an ideal test I would get only the sixteen central points of each square of the matrix. But in actual tests I have some 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.

• Example of found points:
  

• Example of desired result:
  

How to do this?

Note: The matrix in the image can be rotated a little too, so a rotation-independent algorithm would be great.

Answer 1

Now I'm using an algorithm that worked very well for me.

This is the pseudo code:

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