Java Algorithms – Matrix Pattern Recognition in 2D Space

algorithmsjava

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.

Best Answer

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
Related Topic