Fast gridding of irregular data

• US 7,864,175 B2
• Filed: 02/28/2007
• Issued: 01/04/2011
• Est. Priority Date: 03/09/2006
• Status: Expired due to Fees

• Current Assignee: AmberCore Software, Inc.
• Original Assignee: AmberCore Software, Inc.
• Inventors: Monastirev, Yuriy, Monastirev, Alexander, De Margerie, Sylvain, Voribiov, Boris
• Primary Examiner(s): BROOME, SAID A
• Application Number:
  US11/680,069
• Publication Number:
  US 20070211077A1
• Time in Patent Office: 1,406 Days
• Field of Search: None
• US Class Current: 345/423
• 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 computer implemented method for producing a gridded data set, having M rows by N columns of grid, from a number of irregularly located P sampling points in a very large data set used for modeling and analysis of spatial data and stored in computer memory, the method comprising:

computing for each sampling point P, corresponding grid indices in an M by N grid pattern by taking a modulus of coordinates associated with each sampling point;

matching each of the P sampling points to a small rectangular pattern of m_i rows by n_i columns, where m_i and n_i define a small region of influence, selected independently of the number of sampling points, distributed around each sample point P;

accumulating grid index values in a first M row by N column computer memory storage array for each P sampling point;

incrementing counters in a second M row by N column computer memory storage array where multiple P sampling points are matched to the same grid index;

scanning the grid a single time, once all P sampling points have been processed, and calculating, for each grid index, a grid value based on the interpolation of the grid index values; and

storing the calculated grid value of the first array to the computer memory storage.

2. The method of claim 1, wherein prior to computing, the method further comprising pre-processing the sampling points, wherein the sampling points are aggregated by assigning samples to a rectangular sub-domain of coarse tiles which then undergo the gridding computation tile by tile.

3. The method of claim 1, further comprising post processing the calculated grid values by further calculating, for each grid index which has not been assigned a grid value, an interpolated grid value, based on the grid value of those of its immediately neighboring grid indices which have already been assigned a grid value.

4. The method of claim 1 further comprising post processing the calculated grid values by further calculating, for each region of adjacent grid indices which have not been assigned a grid value, an interpolated grid value, based on the grid values of the perimeter grid indices bounding each such region.

5. The methods of claim 1 wherein the gridded data set has three or more dimensions;

wherein the three dimensional gridded data set has rows, columns and layers of grid indices which comprises a computer memory storage array;

wherein the method of claim 1 is performed for each layer.

6. The methods of claim 1 wherein each grid index in the gridded data set has two or more associated grid values.

7. The method of claim 1 wherein interpolating the calculated grid values is performed by averaging the grid values wherein each value in the first array is divided by the corresponding value in the second array.

8. The method of claim 1 wherein interpolating the calculated grid values is performed by an inverse distance weighting of values in the first array and second array to calculate the grid value based on surrounding calculated grid values.

9. The method of claim 1 wherein interpolating the calculated grid values is performed by determining a closest grid value to the sampling point P grid point to assign a grid value to the grid point.

10. The method of claim 1 wherein interpolating the calculated grid values is performed by determining maximum or minimum estimates to calculate the grid value where extremes of the sampling points are most relevant to a type of the data set.

11. The method of claim 3 wherein the interpolated grid value determined during post processing is interpolated by one of:

assigning an arbitrary distinctive grid value to unassigned grid indices as an indication that there is not data present;

computing an average grid value of cells bounding each unassigned grid index and assigning this grid value to empty cells; and

filling holes in the gridded data set by performing an inverse distance weighting to interpolate the interior field from the grid values of cells bounding the hole.

12. The method of claim 4 wherein the interpolated value determined during post processing is interpolated by one of:

averaging surrounding grid values;

assigning an arbitrary distinctive value to unassigned regions as an indication that there is not data present;

computing an average grid value of cells bounding each unassigned region and assigning this grid value to empty cells; and

filling holes in the gridded data set by performing an inverse distance weighting to interpolate the interior field from the grid values of cells bounding the hole.

13. The method of claim 1 wherein the values stored in the first and second arrays are stored in the form of compact integers with fixed point representations.

14. The method of claim 1 wherein storing the calculated grid values to memory comprises storing the calculated grid values in the first array and the second array is deleted.