Need ideas to fill in missing grid points

Hi,

I am wondering if anyone can point me to a matlab function (or user algorithm) to help me fill in missing points on a grid. What i have is a list of x,y locations for points which correspond to points on an (imperfect, but regular) grid -- e.g. (1.02,1.03), (2.04,0.98),(0.96,1.023), etc...

Many of the points are missing. I'd like to determine the "best fit" grid which describes the points that i have so that i can fill in the missing ones.

This is kind of like a curve fitting approach, but its for a grid.

I've thought of computing some kind of merit function and then running some kind of best-fit optimizer, but I'd like guaranteed convergence on something close.

picture of example imperfect grid is attached.

Also, I do NOT have Z data. I am only interested in identifying a set of uniform lattice points that "Best match" the XY locations of the samples that I do have.

THanks if you have anygood ideas!

[Star Strider]

It might be helpful if you attach a .fig file of your plot. That contains all the (x,y) data, so it will be possible to test code with it.

Answer 1

[Star Strider]

MATLAB has a number of Interpolation functions. Probably the most appropriate in your application is Scattered Data Interpolation.

Answer 2

[John D'Errico]

I'm a bit unsure if you have z values for each of those points or not. If each (x,y) pair has an associated z value, then you should use a code that is designed to do exactly this. Gridfit is on the file exchange for download. It will essentially fit a function of two variables (really, a simple 2-d spline), returning the fitted surface on that grid.

If you are only trying to find a grid itself, in the (x,y) plane, reducing this to a complete lattice of points, then you need to be more specific about your goals. I.e.,

1. Must the lattice fully span all of your points?
2. Must the lattice be a regular one, so uniform spacing?

[brent f]

John, Answers to the refining questions you asked: 1. Yes, lattice should fully span all points 2. Yes, lattice should be regular with uniform spacing Also, I do NOT have Z data. I am only interested in identifying a set of uniform lattice points that "Best match" the XY locations of the samples that I do have. I truly appreciate you pointing me to possible answers thanks again

[John D'Errico]

If the lattice need not have the same spacing in both dimensions, then this is just a pair of independent 1-d problems, thus do it in x, then in y.

A lattice could be defined by the start and end points, and the number of steps between those points. The start and end points are bounded by the first and last point in that lattice. So the problem is a simple optimization in two variables. Assume the number of points in that lattice is known. Try to solve the problem with say n steps, then n+1, then n+2, etc. Take the best result.

Your objective function for the optimization is simple. Associate each data point with the nearest lattice line. Compute the distance to that lattice line, then square those distances and sum the squares over all points. (Note that these steps are all done trivially and efficiently in a vectorized form.)

Since the problem is a two variable one, fminsearch would solve it nicely, although since it is a bounded optimization, you will need to use my fminsearchbnd, as found for download from the file exchange. Alternatively, you could use tools from the optimization toolbox.

If the lattice spacing must be the same for both x and y, then the optimization would run over the start point in x, the start point in y, and the spacing, so essentially a 3 variable problem.

Answer 3

[Image Analyst]

So you have an N-by-2 array where column 1 is the x coordinate and column 2 is the y coordinate. You mention you do not have Z data - what would that even be?

Anyway, if you know how many rows you have, even though they're slightly wiggly, and you know how many columns you have, then you can use kmeans() in the stats toolbox and get the mean x values for all the columns and mean y values for all the rows. So now you have your grid and it's a simple matter to pick a "missing" location and assign the estimated x and y location for that missing point.

[brent f]

Thanks for the feedback. I only mentioned no Z data because some of the ideas suggested I look at "griddata" and other 2D interpolation functions. The approach you described makes sense as long as there is no rotation to the grid which is not omething I can guarantee. however your answer does make me think: I could run the procedure you described at a series of small rotations to the entire field and see where the errors minimize. Kind of brute force, but might be good. Thank you for the ideas.

By the way, since I see you are an image analyst: I am doing this because I am trying to identify the locations of an array of "bright spots" in an image. I began with a BW thresholding procedure to identify the bright regions and then identified the centroid location for each ROI which is how I came up with the (incomplete) field of grid points. Maybe there is a WAY better way for me to do the whole problem -- but this is what I came up with!

Answer 4

[Kelly Kearney]

This function might help you: colinear. I wrote it for exactly the same problem you're facing, to extract a grid based on a set of scattered points along each grid line, with a bit of error.

You may have to fiddle around with the rounding tolerance and angle-limit function. I found that with nearly-regular grids like this one, various diagonals tend to be more linear than the nearly-horizontal and nearly-vertical ones you really want to find.

[Kelly Kearney]

I wrote that function pretty recently and hadn't tested it much... looking at it now, I found a few small bugs. Will update in a few minutes.

[brent f]

This sounds most excellent. I was about halfway through grinding out something ugly of my own, but its performance was looking awful. I was doing a global search check for nearest neighbors to determine grid parameters, which was way too slow. I'll be interested to see how you solved the problem! thanks for offering a solution.

[Kelly Kearney]

The idea behind my code is to compare the angle between sets of points, and consider points colinear if the angle is within a certain tolerance. After looking at it again today, I'm finding that it isn't as robust as it could be (falls apart a little in really dense grids with higher rounding tolerances, where subsets of points could belong multiple lines). I think I should be able to fix that by the end of the day... I'll post here when the new and improved version is uploaded.

[Kelly Kearney]

New version now uploaded. A proper README with examples will be added tomorrow.

[Kelly Kearney]

And now the README is up, with an example very similar to your problem. Hope it helps!