1

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
  • 2
    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
2

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
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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