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.

• McMannus: Do you know something more about the matrix structure, e.g. the maximum distance between two points?
• Univers3: @McMannus The matrix is always an 4x4 matrix. In the image is NOT always present the matrix, but is not important, i need to extrapolate the best matching matrix. (of course if i find LESS than 16 points, I will not elaborate it). The distance is not costant. The matrix can be found in any given ratio.
• McMannus: Well, a first direction for this kind of problem could be Template Matching algorithms en.wikipedia.org/wiki/Template_matching
• Katana314: Another question: Is it too much of a performance draw to first, find all points in the image? (and then determine which ones form the matrix from there)

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