Coverage mask generation for large images

• US 7,912,296 B1
• Filed: 05/02/2006
• Issued: 03/22/2011
• Est. Priority Date: 05/02/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zelinka, Stephen D., Praun, Emil C.
• Primary Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US11/415,960
• Time in Patent Office: 1,785 Days
• Field of Search: 382/100, 382/181, 382/190, 382/195, 382/209, 382/217, 382/218, 382/219, 358/217, 345/625, 345/626
• US Class Current: 382/209
• CPC Class Codes: G01C 21/3852 Data derived from aerial or satellite images
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 7/0002 Inspection of images, e.g. flaw detection
• CPC Class Codes: G09B 29/003 Maps

Abstract

A computer-implemented method is described. The method includes generating a coarse resolution image from a finer resolution image, generating a coarse coverage mask that identifies valid and non-valid data in the coarse resolution image, and determining whether data in the finer resolution image is valid or non-valid data based on whether corresponding data identified by the coarse coverage mask is valid or non-valid data. In certain embodiments, generating a coarse resolution image can include segmenting the finer resolution image into tiles and compressing each tile. Compressing each tile can be preformed using a lossless compression, and at least two tiles can be transmitted to separate computing devices and compressed in parallel.

Claims

1. A computer-implemented method comprising:

generating a coarse resolution image from a finer resolution image;

generating a coarse coverage mask for the coarse resolution image that identifies valid and non-valid data in the coarse resolution image, wherein data is valid if it corresponds to image data, and data is invalid if it does not correspond to image data; and

determining whether data in the finer resolution image is valid or non-valid data based on whether corresponding data identified by the coarse coverage mask is valid or non-valid data; and

wherein the method is performed by one or more processors.

2. The method of claim 1, wherein generating a coarse resolution image includes segmenting the finer resolution image into tiles and compressing each tile.

3. The method of claim 2, wherein compressing each tile is performed using a lossless compression.

4. The method of claim 2, wherein at least two tiles are transmitted to separate computing devices and compressed in parallel.

5. The method of claim 4, wherein the tiles are recombined to form the coarse resolution image.

6. The method of claim 5, wherein generating the coarse coverage mask comprises flood-filling the coarse resolution image with a value indicating non-valid data.

7. The method of claim 6, wherein generating the coarse coverage mask further comprises preventing the flood-filling from assigning non-valid data values unless an amount of pixels identified for flood-filling is greater than a hole size threshold.

8. The method of claim 6, wherein the flood-filling is performed by a single computing device.

9. The method of claim 1, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as valid data.

10. The method of claim 1, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a non-valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as non-valid data.

11. The method of claim 1, further comprising identifying a section of the coarse resolution image as boundary data if one adjacent section of the image includes valid data and another adjacent section of the image includes non-valid data, and including the identification of the boundary data in the coarse coverage mask.

12. The method of claim 11, further comprising generating a refined mask comprising selecting a portion of the finer resolution image corresponding to a portion of the coverage mask that includes the boundary data identification and initiating a flood-fill of non-valid data values in the selected portion of the finer resolution image at one or more pixels specified by the portion of the coverage mask as having non-valid data.

13. The method of claim 12, wherein generating the refined mask further comprises preventing the flood-fill from assigning non-valid data values to a second pixel in the image portion if the second location is within a predetermined measurement of the identified boundary data.

14. The method of claim 13, wherein the predetermined measurement includes one pixel of the selected portion of the finer resolution image.

15. The method of claim 12, wherein the flood-fill comprises identifying an original value at a pixel location, and filling it with a non-data value indicating the pixel contains non-valid data if the original pixel value is within a predetermined tolerance range.

16. The method of claim 15, wherein the flood-fill further comprises a four-way flood-fill that selects four pixels adjacent to a pixel that has been filled with the non-data value and fills each adjacent pixel with a non-data value if the adjacent pixel has a pixel value within the tolerance range.

17. The method of claim 1, wherein the finer resolution image is a composite image generated from separate finer resolution images.

18. A system comprising:

one or more computers programmed to perform operations comprising;

compressing a high-resolution image into a coarse resolution image;

generating a coarse coverage mask by assigning valid or non-valid statuses to data in the coarse resolution image, wherein data is valid if it corresponds to image data, and data is invalid if it does not correspond to image data; and

applying the mask to the high-resolution image to determine validity or non-validity statuses of data in the high-resolution image.

19. The system of claim 18, further programmed to perform operations comprising segmenting the high-resolution image into tiles that are separately compressed.

20. The system of claim 19, wherein at least two tiles are transmitted to separate computing devices and compressed in parallel.

21. The system of claim 18, wherein generating the coarse coverage mask comprises flood-filling the coarse resolution image with a value indicating non-valid data.

22. The system of claim 21, wherein generating the coarse coverage mask further comprises preventing the flood-filling from assigning non-valid data values unless an amount of pixels identified for flood-filling is greater than a hole size threshold.

23. The system of claim 18, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as valid data.

24. The system of claim 18, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a non-valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as non-valid data.

25. The system of claim 18, further programmed to perform operations comprising identifying a section of the coarse resolution image as boundary data if one adjacent section of the image includes valid data and another adjacent section of the image includes non-valid data, and including the identification of the boundary data in the coarse coverage mask.

26. The system of claim 25, further programmed to perform operations comprising generating a refined mask comprising selecting a portion of the finer resolution image corresponding to a portion of the coverage mask that includes the boundary data identification and initiating a flood-fill of non-valid data values in the selected portion of the finer resolution image at one or more pixels specified by the portion of the coverage mask as having non-valid data.

27. The system of claim 26, wherein generating the refined mask further comprises preventing the flood-fill from assigning non-valid data values to a second pixel in the image portion if the second location is within a predetermined measurement of the identified boundary data.

28. The system of claim 26, wherein the flood-fill comprises identifying an original value at a pixel location, and filling it with a non-data value indicating the pixel contains non-valid data if the original pixel value is within a predetermined tolerance range.

29. The system of claim 28, wherein the flood-fill further comprises a four- way flood-fill that selects four pixels adjacent to a pixel that has been filled with the non-data value and fills each adjacent pixel with a non-data value if the adjacent pixel has a pixel value within the tolerance range.

30. A computer-readable storage device encoded with a computer program, the computer program including instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

compressing a high-resolution image into a coarse resolution image;

generating a coarse coverage mask that identifies non-valid data in the coarse resolution image, where non-valid data is data that does not correspond to image data; and

applying the coarse coverage mask to the high-resolution image to determine whether data in the high-resolution image is non-valid data based on whether corresponding data identified by the coarse coverage mask is non-valid data.

31. The storage device of claim 30, wherein generating a coarse resolution image includes segmenting the finer resolution image into tiles and compressing each tile.

32. The storage device of claim 31, wherein compressing each tile is performed using a lossless compression.

33. The storage device of claim 31, wherein at least two tiles are transmitted to separate computing devices and compressed in parallel.

34. The storage device of claim 33, wherein the tiles are recombined to form the coarse resolution image.

35. The storage device of claim 34, wherein generating the coarse coverage mask comprises flood-filling the coarse resolution image with a value indicating non-valid data.

36. The storage device of claim 35, wherein generating the coarse coverage mask further comprises preventing the flood-filling from assigning non-valid data values unless an amount of pixels identified for flood-filling is greater than a hole size threshold.

37. The storage device of claim 35, wherein the flood-filling is performed by a single computing device.

38. The storage device of claim 30, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as valid data.

39. The storage device of claim 30, wherein determining whether the data in the finer resolution image is valid or non-valid data comprises assigning a non-valid status to a fine pixel value of the finer resolution image if the coarse coverage mask identifies a corresponding coarse pixel value as non-valid data.

40. The storage device of claim 30, the operations further comprising identifying a section of the coarse resolution image as boundary data if one adjacent section of the image includes valid data and another adjacent section of the image includes non-valid data, and including the identification of the boundary data in the coarse coverage mask.

41. The storage device of claim 40, the operations further comprising generating a refined mask comprising selecting a portion of the finer resolution image corresponding to a portion of the coverage mask that includes the boundary data identification and initiating a flood-fill of non-valid data values in the selected portion of the finer resolution image at one or more pixels specified by the portion of the coverage mask as having non-valid data.

42. The storage device of claim 41, wherein generating the refined mask further comprises preventing the flood-fill from assigning non-valid data values to a second pixel in the image portion if the second location is within a predetermined measurement of the identified boundary data.

43. The storage device of claim 42, wherein the predetermined measurement includes one pixel of the selected portion of the finer resolution image.

44. The storage device of claim 41, wherein the flood-fill comprises identifying an original value at a pixel location, and filling it with a non-data value indicating the pixel contains non-valid data if the original pixel value is within a predetermined tolerance range.

45. The storage device of claim 44, wherein the flood-fill further comprises a four-way flood-fill that selects four pixels adjacent to a pixel that has been filled with the non- data value and fills each adjacent pixel with a non-data value if the adjacent pixel has a pixel value within the tolerance range.

46. The storage device of claim 30, wherein the finer resolution image is a composite image generated from separate finer resolution images.