# Matrix Pattern Recognition Algorithm for a 2D space

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.

• Do you know something more about the matrix structure, e.g. the maximum distance between two points? – McMannus May 24 '13 at 8:35
• @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. – Univers3 May 24 '13 at 9:53
• Well, a first direction for this kind of problem could be Template Matching algorithms en.wikipedia.org/wiki/Template_matching – McMannus May 24 '13 at 10:00
• 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) – Katana314 May 24 '13 at 14:46

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
``````