Large-scale image processing using mass parallelization techniques

• US 8,346,016 B1
• Filed: 06/13/2011
• Issued: 01/01/2013
• 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): ZARKA, DAVID PETER
• Application Number:
  US13/159,216
• Time in Patent Office: 568 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 performed by one or more computers, the method comprising:

receiving a plurality of input tiles of first imagery, the first imagery being in a first projection;

generating, from each of the plurality of input tiles of first imagery, one or more respective fragments for each of one or more output resolution levels, each fragment being a re-projection of imagery from the first projection to a second projection at the respective output resolution level, including;

approximating vertical stretch for each tile at each respective output resolution level, and

selecting a zoom factor for counter-balancing the vertical stretch;

tagging each fragment with a tag identifying an output tile and an output resolution level to which the fragment will contribute imagery;

storing the fragments on multiple storage subsystems, wherein all fragments having a same tag are stored on a same storage subsystem; and

assembling fragments with the same tag to produce output tiles in the second projection for each of the one or more output resolution levels.

2. The method of claim 1, where the first projection is a latitude-longitude projection and the second projection is a Mercator projection.

3. The method of claim 1, wherein assembling fragments with the same tag to produce output tiles in the second projection comprises obtaining the all the fragments that are tagged with a first tag from one of the multiple storage subsystems.

4. The method of claim 1, wherein the first imagery is geo-located imagery.

5. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a plurality of input tiles of first imagery, the first imagery being in a first projection;

generating, from each of the plurality of input tiles of first imagery, one or more respective fragments for each of one or more output resolution levels, each fragment being a re-projection of imagery from the first projection to a second projection at the respective output resolution level, including;

approximating vertical stretch for each tile at each respective output resolution level, and

selecting a zoom factor for counter-balancing the vertical stretch;

tagging each fragment with a tag identifying an output tile and an output resolution level to which the fragment will contribute imagery;

storing the fragments on multiple storage subsystems, wherein all fragments having a same tag are stored on a same storage subsystem; and

assembling fragments with the same tag to produce output tiles in the second projection for each of the one or more output resolution levels.

6. The computer program product of claim 5, where the first projection is a latitude-longitude projection and the second projection is a Mercator projection.

7. The computer program product of claim 5, wherein assembling fragments with the same tag to produce output tiles in the second projection comprises obtaining the all the fragments that are tagged with a first tag from one of the multiple storage subsystems.

8. The computer program product of claim 5, wherein the first imagery is geo-located imagery.

9. A method performed by one or more computers, the method comprising:

receiving a plurality of input tiles of first imagery, the first imagery being a first projection;

generating, from each of the plurality of input tiles of first imagery, one or more respective fragments for each of one or more output resolution levels, each fragment being a re-projection of imagery from the first projection to a second projection at the respective output resolution level, including;

approximating vertical stretch for each tile at each respective output resolution level, and

selecting a zoom factor for counter-balancing the vertical stretch;

associating each fragment with an output tile and an output resolution level to which the fragment will contribute imagery;

storing the fragments on multiple storage subsystems, including storing each fragment associated with a particular output tile on a same storage subsystem as all other fragments associated with the particular output tile; and

assembling fragments associated with the particular output tile to produce second imagery in the second projection for the particular output tile.

10. The method of claim 9, wherein the first projection is a latitude-longitude projection and the second projection is a Mercator projection.

11. The method of claim 9, wherein assembling fragments associated with the particular output tile to produce second imagery in the second projection for the particular output tile comprises obtaining the all the fragments that are associated with the particular output tile from one of the multiple storage subsystems.

12. The system of claim 9, wherein the first imagery is geo-located imagery.

13. 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;

receiving a plurality of input tiles of first imagery, the first imagery being in a first projection;

generating, from each of the plurality of input tiles, one or more respective fragments for each of one or more output resolution levels, each fragment being a re-projection of imagery from the first projection to a second projection at the respective output resolution level, including;

approximating vertical stretch for each tile at each respective output resolution level, and

selecting a zoom factor for counter-balancing the vertical stretch;

tagging each fragment with a tag identifying an output tile and an output resolution level to which the fragment will contribute imagery;

storing the fragments on multiple storage subsystems, wherein all fragments having a same tag are stored on a same storage subsystem; and

assembling fragments with the same tag to produce output tiles in the second projection for each of the one or more output resolution levels.

14. The system of claim 13, wherein the first projection is a latitude-longitude projection and the second projection is a Mercator projection.

15. The system of claim 13, wherein assembling fragments with the same tag to produce output tiles in the second projection comprises obtaining the all the fragments that are tagged with the first tag from one of the multiple storage subsystems.

16. 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;

receiving a plurality of input tiles of first imagery, the first imagery being in a first projection;

generating, from each of the plurality of input tiles, one or more respective fragments for each of one or more output resolution levels, each fragment being a re-projection of imagery from the first projection to a second projection at the respective output resolution level, including;

approximating vertical stretch for each tile at each respective output resolution level, and

selecting a zoom factor for counter-balancing the vertical stretch;

associating each fragment with an output tile on an output resolution level to which the fragment will contribute imagery;

storing the fragments on multiple storage subsystems, including storing each fragment associated with a particular output tile on a same storage subsystem as all other fragments associated with the particular output tile; and

assembling fragments associated with the particular output tile to produce second imagery in the second projection for the particular output tile.

17. The system of claim 16, wherein the first projection is a latitude-longitude projection and the second projection is a Mercator projection.

18. The system of claim 16, wherein assembling fragments associated with the particular output tile to produce second imagery in the second projection for the particular output tile comprises obtaining the all the fragments that are associated with the particular output tile from one of the multiple storage subsystems.