US 8,941,652 B1Granted

Incremental surface hole filling

AssigneeGoogle Inc.

InventorsBrett Allen, Joshua Sam Schpok

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems, methods, and computer storage mediums are provided for filling missing data in a spatially distributed, graphically represented data set. An example method includes dividing the data set into a first plurality of tiles along a first plurality of boundary lines. For each of the first plurality of tiles, a first set of fill data is generated to fill missing data in the data set. Then, for each of a determined number of dimensions of the tiles, the data set is divided into a new plurality of tiles along a new plurality of boundary lines offset from the last immediately determined plurality of boundary lines and a new set of fill data is generated to fill the missing data. A portion of the new set of fill data includes a portion of the last immediately generated set of fill data that fall along the boundary of the respective new tile.

Claims20

Dependent claims

A computer-implemented method for filling missing data in a spatially distributed, graphically represented data set, comprising:

determining, by at least one computer processor, tiling grid dimensions that describes the dimensions of the tiling grid to use in processing the data set;
dividing, by the at least one computer processor, the data set into a first plurality of tiles along a first plurality of boundary lines, each tile including a different spatial region of the data set, wherein the number of tiles, the size of the tiles, and the dimensions of the tiles are based on the tiling dimensions;
for each of the first plurality of tiles, generating, by the at least one computer processor, a first set of fill data to fill at least a portion of the missing data in the spatial region of the data set included in each of the respective first plurality of tiles;
for a number of iterations that equal the number of dimensions indicated by the tiling grid dimensions:
dividing, by the at least one computer processor, the data set into a new plurality of tiles along a new plurality of boundary lines offset from the last immediately determined plurality of boundary lines, each tile comprising a different special region of the data set;
and
for each of the new plurality of tiles, generating, by the at least one computer processor, a new set of fill data to fill at least a portion of the missing data in the spatial region of the data set included in the respective tile, wherein a portion of the missing data included in the respective tile is filled in with a portion of the last immediately generated set of fill data that falls along the new plurality of boundary lines that surround the respective tile;
and
adding the new set of fill data to the data set to thereby fill in at least some missing portions of the data set.

6 more elements

A computer system for filling missing data in a spatially distributed, graphically represented, two-dimensional data set, the system comprising:

a first tile processor configured to:
divide the data set into a first plurality of tiles along a first plurality of boundary lines, each tile including a different spatial region of the data set;
for each of the first plurality of tiles, generate a first set of fill data to fill at least a portion of the missing data in the data set included in each of the respective first plurality of tiles;
a second tile processor configured to, after the first tile processor generates the first set of fill data:
divide the data set into a second plurality of tiles along a second plurality of boundary lines offset from the first plurality of boundary lines, each tile comprising a different spatial region of the data set;
for each of the second plurality of tiles, generate a second set of fill data to fill at least a portion of the missing data in the data set included in the second plurality of tiles, wherein the missing data included in the second plurality of tiles includes the missing data in the data set filled in with a portion of the first set of fill data that fall along the second plurality of boundary lines;
a third tile processor configured to, after the second tile processor generates the second set of fill data:
divide the data set into a third plurality of tiles along a third plurality of boundary lines offset from both the first and second plurality of boundary lines, each tile comprising a different spatial region of the data set;
for each of the third plurality of tiles, generate a third set of fill data to fill the missing data in the data set included in the third plurality of tiles, wherein the missing data included in the third plurality of tiles include the missing data in the data set filled in with a portion of the second set of fill data that fall along the third plurality of boundary lines, and wherein the third set of fill data, when added to the data set, fills in at least some missing portions of the data set;
a memory unit configured to store at least one of the first, second, or third tile processors;
and
a computer processor configured to execute at least one of the first, second, or third tile processors.

9 more elements

Dependencies are inferred from the claim text.