FAST GRIDDING OF IRREGULAR DATA

• US 20070211077A1
• Filed: 02/28/2007
• Published: 09/13/2007
• Est. Priority Date: 03/09/2006
• Status: Active Grant

• Current Assignee: AmberCore Software, Inc.
• Original Assignee: AmberCore Software, Inc.
• Inventors: Monastirev, Yuriy, De Margerie, Sylvain, Voribiov, Boris, Montastirev, Alexander
• Granted Patent: US 7,864,175 B2
• Time in Patent Office: Days
• US Class Current: 345/606
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A method of fast gridding of irregular data, has been developed for spatial interpolation of large irregular spatial point data sets; for example building a 3D geographic terrain grid surface from billions of irregularly spaced xyz coordinates on the earth'"'"'s surface. The method developed typically translates into many orders of magnitude gain in computational speed. For example, to produce a gridded data set (having M rows and N columns) from P irregularly located sampling points, the computational steps required can be reduced from a number of the order of O(M×N×P) to a lesser number of the order of O(M×N+P) operations. The method achieves this by ensuring that each of the P sampling points is visited only once. This is particularly significant since spatial data collection devices typically collect data points in the billions. The method described is readily extendible to any number of dimensions.

Claims

1. A method for producing an M×

N gridded data set from P irregularly located sampling points which requires only O(M×

N+P) operations comprising the steps of;

visiting each of the P sampling points only once;

computing for each sampling point, corresponding grid indices in an M×

N grid pattern by taking the modulus of the point coordinates;

matching each sampling point to one of a single grid index and a pattern of m_i×

n_i grid indices distributed around the sample point;

accumulating values in a first array and incrementing counters in a second array where multiple points are matched to the same grid index;

scanning the grid a single time, once all P sampling points have been processed, and calculating the grid values using one of averaging and interpolation based on surrounding values; and

saving the second array as a point density by-product.

2. The method of claim 1, further comprising the step of pre-processing in which the sampling points are aggregated.

3. The method of any of claims 1 and 2, further comprising the step of post processing which fills holes in the gridded data set with smoothed, interpolated values.

4. The method of any of claims 1, 2 and 3, further comprising the step of post processing which fills holes in the gridded data set with one of an arbitrary null value, an average value and an interpolated value based in the values of the gridded data bordering each of the holes.

5. The methods of any of claims 1, 2, 3 and 4, wherein the gridded data set has three or more dimensions.

6. The methods of any of claims 1, 2, 3, 4 and 5, wherein each grid index in the gridded data set has two or more associated values.