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
    Commented May 24, 2013 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
    Commented May 24, 2013 at 9:53
  • 2
    Well, a first direction for this kind of problem could be Template Matching algorithms en.wikipedia.org/wiki/Template_matching
    – McMannus
    Commented May 24, 2013 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
    Commented May 24, 2013 at 14:46

1 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:
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.