Large-scale image processing using mass parallelization techniques

• US 7,965,902 B1
• Filed: 05/19/2006
• Issued: 06/21/2011
• Est. Priority Date: 05/19/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ohazama, Chikai J., Zelinka, Stephen D., Praun, Emil C.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US11/437,553
• Time in Patent Office: 1,859 Days
• Field of Search: 382/284
• US Class Current: 382/284
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Assets of raw geo-located imagery can be divided into tiles and coverage masks can be generated for each tile. For each tile, fragments of pixels from coverage masks of neighboring tiles can be extracted and tagged. The fragments can be sorted and stored in a data structure so that fragments having the same tag can be grouped together in the data structure. The fragments can be used to feather the coverage mask of the tile to produce a blend mask. Multi-resolution imagery and mask pyramids can be generated by extracting fragments from tiles and minified (e.g., down-sampled). The minified fragments can be tagged (e.g., by ancestor tile name), sorted and stored in a data structure, so that fragments having like tags can be stored together in the data structure. The fragments can be assembled into fully minified tiles for each level in the pyramid. Input tiles in a first projection are re-projected into a second projection using techniques that minimize distortion in the re-projected imagery.

Claims

1. A method comprising:

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile; and

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment;

generating a blend mask for a first tile from a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile;

wherein the method steps are performed by one or more computers.

2. The method of claim 1, further comprising:

minifying the tiles to a predetermined size for efficient parallel processing.

3. The method of claim 1, further comprising:

organizing the one or more mask fragments into groups by tags; and

sorting the one or more mask fragments using a parallel sorter.

4. The method of claim 1, where generating the blend mask further comprises:

assembling the first coverage mask and the first mask fragments into an image;

extracting the blend mask from the assembled first mask fragments and the first coverage mask; and

storing the blend mask in a data structure.

5. The method of claim 1, further comprising:

tagging each mask fragment with a tile identifier associated with the neighboring tile from which the mask fragment was extracted.

6. The method of claim 1, where tagging each neighboring mask fragment includes tagging mask fragments from the neighboring tiles with an identifier for the first tile.

7. The method of claim 1, wherein generating the blend mask further comprises:

obtaining the first tile and the one or more first mask fragments from one of the multiple storage subsystems.

8. The method of claim 1, wherein generating the blend mask further comprises:

applying a feathering filter to the pixels of the first coverage mask and the first mask fragments.

9. The method of claim 8, where applying the feathering filter further comprises:

replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

10. A computer-readable storage device having stored thereon instructions which, when executed by a computer, cause the computer to perform operations comprising:

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask for a first tile from a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile.

11. The computer-readable storage device of claim 10, the operations further comprising:

minifying the tiles to a predetermined size for efficient parallel processing.

12. The computer-readable storage device of claim 10, the operations further comprising:

organizing the one or more mask fragments into groups by tags; and

sorting the one or more mask fragments using a parallel sorter.

13. The computer-readable storage device of claim 10, where generating the blend mask further comprises:

assembling the first coverage mask and the first mask fragments into an image;

extracting the blend mask from the assembled first mask fragments and the first coverage mask; and

storing the blend mask in a data structure.

14. The computer-readable storage device of claim 10, the operations further comprising:

tagging each mask fragment with a tile identifier associated with the neighboring tile from which the mask fragment was extracted.

15. The computer-readable storage-device of claim 10, where tagging the each neighboring mask fragment includes tagging mask fragments from the neighboring tiles with an identifier for the first tile.

16. The computer-readable storage device of claim 10, wherein generating the blend mask further comprises:

applying a feathering filter to the pixels of the first coverage mask and the first mask fragments.

17. The computer-readable storage device of claim 16, where applying the feathering filter further comprises:

replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

18. The storage device of claim 10, wherein generating the blend mask further comprises:

obtaining the first tile and the one or more first mask fragments from one of the multiple storage subsystems.

19. A system for generating a blend mask, comprising:

means for dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

means for performing on each tile operations including;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

means for storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

means for generating a blend mask for a first tile from a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile.

20. A system, comprising:

one or more computers; and

a computer readable storage device storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask for a first tile from a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile.

21. The system of claim 20, where tagging each neighboring mask fragment includes tagging mask fragments from the neighboring tiles with an identifier for the first tile.

22. The system of claim 20, where the operations further comprise:

minifying the tiles to a predetermined size for efficient parallel processing.

23. The system of claim 20, where the operations further comprise:

organizing the one or more mask fragments into groups by tags; and

sorting the one or more mask fragments using a parallel sorter.

24. The system of claim 20, where generating the blend mask further comprises:

assembling the first coverage mask and the first mask fragments into an image;

extracting the blend mask from the assembled first mask fragments and the first coverage mask; and

storing the blend mask in a data structure.

25. The system of claim 20, wherein generating the blend mask further comprises:

obtaining the first tile and the one or more first mask fragments from one of the multiple storage subsystems.

26. The system of claim 20, wherein generating the blend mask further comprises:

applying a feathering filter to the pixels of the first coverage mask and the first mask fragments.

27. The system of claim 26, where applying the feathering filter further comprises:

replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

28. The system of claim 20, where the operations further comprise:

tagging each mask fragment with a tile identifier associated with the neighboring tile from which the mask fragment was extracted.

29. A method of generating a blend mask, comprising:

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask for a first tile, including;

assembling a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile,

applying a feathering filter to pixels in the first coverage mask and the first mask fragments to provide a blend mask, and

extracting the blend mask from the feathered coverage mask;

wherein the method steps are performed by one or more computers.

30. The method of claim 29, where applying the feathering filter further comprises replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

31. A system, comprising:

one or more computers; and

a computer-readable storage device storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask for a first tile, including;

assembling a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile into an image,

applying a feathering filter to pixels in the first coverage mask and the first mask fragments to provide a blend mask; and

extracting the blend mask from the feathered coverage mask.

32. The system of claim 31, wherein applying the feathering filter further comprises replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

33. A system comprising:

one or more computers; and

a computer-readable storage device storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask associated with a first tile from a first coverage mask and the one or more first mask fragments having tags identifying the first tile, the generating including assembling the first coverage mask and the one or more first mask fragments and applying a feathering filter to pixels in the first coverage mask and the one or more first mask fragments s to generate a blend mask.

34. The system of claim 33, where applying the feathering filter further comprises replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.

35. A method of generating a blend mask, comprising:

dividing imagery into tiles of pixels, each tile having at least one neighboring tile and each tile having an associated coverage mask, each coverage mask identifying all pixels in the tile that contain imagery and all pixels in the tile that lack imagery;

for each tile;

extracting a respective neighboring mask fragment from the coverage mask associated with each neighboring tile, and

tagging each neighboring mask fragment with a tag identifying the tile;

storing the tiles and the one or more mask fragments on multiple storage subsystems, using the tags to store each respective mask fragment on the same storage subsystem as the tile identified by the tag of the respective mask fragment; and

generating a blend mask for a first tile from a first coverage mask associated with the first tile and one or more first mask fragments having tags identifying the first tile, the generating including applying a feathering filter to the pixels in the first coverage mask and the first mask fragments having the same tags, wherein the same tags correspond to the identifier for the first tile; and

wherein the method steps are performed by one or more computers.

36. The method of claim 35, where applying the feathering filter further comprises replacing one or more pixels in the first coverage mask with a function of the average of other pixels surrounding the pixel.