Large-scale image processing using mass parallelization techniques

• US 8,660,386 B1
• Filed: 09/12/2012
• Issued: 02/25/2014
• Est. Priority Date: 05/19/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zelinka, Stephen D., Praun, Emil C., Ohazama, Chikai J.
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US13/612,775
• Time in Patent Office: 531 Days
• Field of Search: 382/300, 382302-305
• US Class Current: 382/305
• 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.

Claims

1. A method comprising:

identifying 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 associated tile that contain imagery and all pixels in the associated tile that lack imagery;

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

associating, with each tile, each mask fragment extracted from a tile neighboring the tile;

storing the tiles and the mask fragments on multiple storage subsystems, including storing each respective mask fragment on the same storage subsystem as the tile associated with the mask fragment; and

generating a blend mask for each tile from the coverage mask associated with the tile and one or more mask fragments associated with the tile, including obtaining the one or more mask fragments associated with the tile from the storage subsystem on which the tile is stored.

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, wherein generating the blend mask further comprises:

assembling the coverage mask associated with the tile and the mask fragments associated with the tile; and

generating the blend mask from the mask fragments and coverage mask associated with the tile.

5. The method of claim 1, wherein generating the blend mask comprises applying a feathering filter to pixels in the coverage mask associated with the tile and the mask fragments associated with the tile.

6. The method of claim 5, wherein applying the feathering filter comprises:

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

7. The method of claim 1, further comprising:

associating each mask fragment with a tile identifier of the neighboring tile from which the mask fragment was extracted.

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

obtaining the tile and the one or more mask fragments associated with the tile from a single one of the multiple storage subsystems.

9. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

identifying 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 associated tile that contain imagery and all pixels in the associated tile that lack imagery;

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

associating, with each tile, each mask fragment extracted from a tile neighboring the tile;

storing the tiles and the mask fragments on multiple storage subsystems, including storing each respective mask fragment on the same storage subsystem as the tile associated with the mask fragment; and

generating a blend mask for each tile from the coverage mask associated with the tile and one or more mask fragments associated with the tile, including obtaining the one or more mask fragments associated with the tile from the storage subsystem on which the tile is stored.

10. The system of claim 9, wherein the operations further comprise:

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

11. The system of claim 9, wherein 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.

12. The system of claim 9, wherein generating the blend mask further comprises:

assembling the coverage mask associated with the tile and the mask fragments associated with the tile; and

generating the blend mask from the mask fragments and coverage mask associated with the tile.

13. The system of claim 9, wherein generating the blend mask comprises applying a feathering filter to pixels in the coverage mask associated with the tile and the mask fragments associated with the tile.

14. The system of claim 13, wherein applying the feathering filter comprises:

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

15. The system of claim 9, wherein the operations further comprise:

associating each mask fragment with a tile identifier of the neighboring tile from which the mask fragment was extracted.

16. The system of claim 9, wherein generating the blend mask further comprises:

obtaining the tile and the one or more mask fragments associated with the tile from a single one of the multiple storage subsystems.

17. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

identifying 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 associated tile that contain imagery and all pixels in the associated tile that lack imagery;

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

associating, with each tile, each mask fragment extracted from a tile neighboring the tile;

storing the tiles and the mask fragments on multiple storage subsystems, including storing each respective mask fragment on the same storage subsystem as the tile associated with the mask fragment; and

generating a blend mask for each tile from the coverage mask associated with the tile and one or more mask fragments associated with the tile, including obtaining the one or more mask fragments associated with the tile from the storage subsystem on which the tile is stored.

18. The computer-readable medium of claim 17, wherein the operations further comprise:

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

19. The computer-readable medium of claim 17, wherein 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.

20. The computer-readable medium of claim 17, wherein generating the blend mask further comprises:

assembling the coverage mask associated with the tile and the mask fragments associated with the tile; and

generating the blend mask from the mask fragments and coverage mask associated with the tile.

21. The computer-readable medium of claim 17, wherein generating the blend mask comprises applying a feathering filter to pixels in the coverage mask associated with the tile and the mask fragments associated with the tile.

22. The computer-readable medium of claim 21, wherein applying the feathering filter comprises:

replacing one or more pixels in the coverage mask associated with the tile with a function of an average of other pixel values surrounding the one or more pixels.

23. The computer-readable medium of claim 17, wherein the operations further comprise:

associating each mask fragment with a tile identifier of the neighboring tile from which the mask fragment was extracted.

24. The computer-readable medium of claim 17, wherein generating the blend mask further comprises:

obtaining the tile and the one or more mask fragments associated with the tile from a single one of the multiple storage subsystems.