1
$\begingroup$

I have this problem where I have multiple points in a 2D space. A subset of these points makes up a rectangular grid. Some points of the grid might be missing. The shape and number of points the grid consists of are known. Also, the other points not making up the grid are few. The general location and rotation of the grid are also known. But we don't know the exact location or rotation. What would be a good, and most important, efficient way to find this grid?

A perfect grid:

What we are after

The grid can appear as shown below with a missing point:

Scenario example 1

Or with for example a rotation and being split in two as shown below:

Scenario example 2

In the actual problem, the grid is larger but always rectangular, also we can assume the gird is located around the center of the data.

The points come from an image where there is monospaced text. The missing points and noise are due to glare in this image. The points are the centers of the (by preprocessing) found characters (so not exact). The text in the image always consists of the same number of characters and lines. The idea is reconstructing this grid to be able to find the lost characters. We do not know what points are characters and what points are not, but I am aware this could be approximated by analyzing the "blobs" we find in the image.

$\endgroup$
  • 1
    $\begingroup$ The points come from an image where there is monospaced text, The missing points and noise is due to glare in this image. The points are the centers of the (by preprocessing) found characters (so not exact). The text in the image always consists of the same number of characters and lines. The problem is reconstructing this grid to be able to find the lost characters. We do not know what point are characters and what points are not, but I am aware this could be approximated by analyzing the "blobs" we find in the image. I will update my question with this information. $\endgroup$ – Jelle de Fries Nov 15 '18 at 10:29
2
$\begingroup$

You could represent the grid with 5 parameters:

  • (x0, y0) to represent the offset from your image origin to the grid origin
  • (xs, ys) to represent a multiplication factor from your image plane to your grid plane. If your grid is spaced apart every 100 pixels on your image plane, these values might be 100,100
  • theta to represent the rotation of the grid

You could fit the grid to point in image by varying these 5 parameters and optimize these parameters by calculating a cost function at each step.

An example cost function would be the total Euclidean distance between known point and grid points. The grid parameters that best overlap your given point should represent an optimal solution in most cases, especially in cases where you have several "correct points" and few of the "outlier points".

For efficiency you could ensure that your x0 value is [0,xs] and your y0 is [0,ys]. Since it sounds like you have a guess for the size of your grid, you could input a decent guess for xs and ys and also constrain these values from changing too much.

$\endgroup$

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.