AUTOMATIC EXTRACTION OF BUILT-UP FOOTPRINTS FROM HIGH RESOLUTION OVERHEAD IMAGERY THROUGH MANIPULATION OF ALPHA-TREE DATA STRUCTURES

• US 20150023550A1
• Filed: 08/29/2013
• Published: 01/22/2015
• Est. Priority Date: 07/19/2013
• Status: Active Grant

• Current Assignee: Maxar Intelligence Incorporated (Galileo Parent, Inc.)
• Original Assignee: DigitalGlobe, Inc. (Galileo Parent, Inc.)
• Inventors: Ouzounis, Georgios
• Granted Patent: US 9,031,325 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/454 Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 10/82 using neural networks
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

A system for automatically extracting or isolating structures or areas of interest (e.g., built-up structures such as buildings, houses, shelters, tents; agricultural areas; etc.) from HR/VHR overhead imagery data by way of making as little as a single pass through a hierarchical data structure of input image components (where pixels are grouped into components based on any appropriate definition or measure of dissimilarity between adjacent pixels of the input image) to identify candidate components (e.g., possible structures of interest) free of necessarily having to re-iterate the same operator configured with different threshold parameters for a plurality of values.

Claims

1. A method for use in extracting structures of interest from overhead imagery data, comprising:

identifying, using a processor, a plurality of groups of pixels in at least one input overhead image of a geographical region, wherein each pixel in each group is adjacent to at least one other pixel in the group, wherein adjacent pixels in each group do not differ by more than a predetermined level of a dissimilarity measure between the adjacent pixels, wherein a plurality of such groups of pixels at each of a plurality of successive predetermined levels of the dissimilarity measure are identified, wherein the groups at one of the predetermined levels are hierarchically related to the groups at an adjacent one of the predetermined levels in a hierarchical data structure, and wherein each group is a first component; and

detecting first components in the hierarchical data structure that each include pixels collectively comprising a geometric attribute level greater than a threshold geometric attribute level.

10. The method of claim 1, wherein the detected first components comprise lower predetermined levels of the dissimilarity measure than other of the predetermined levels of the dissimilarity measure.

11. The method claim 1, wherein the geometric attribute comprises geographical area.

12. The method of claim 1, wherein the geometric attribute comprises non-compactness.

13. The method of claim 1, further comprising:

obtaining at least one attribute of each of the detected first components;

ascertaining whether the at least one attribute of each of the detected first components is associated with a structure of interest in the at least one input overhead image;

generating a first mask corresponding to the at least one input overhead image based on the detected first component ascertaining step that includes first regions that are ascertained to be associated with structures of interest and second regions that are ascertained to not be associated with structures of interest; and

using the first mask to remove portions of that are not associated with structures of interest from a resultant image of the geographical region.

14. The method of claim 13, further comprising:

tagging, using the processor, each of the first components based on a number of pixels present in the first components to identify one of a plurality of area zones within which the first component resides, wherein each successive area zone includes first components having a greater number of pixels than do the first components of a previous area zone;

generating for each pixel of the input overhead image, using the processor, a vector including a number of entries corresponding to each of the area zones from the tagging step, wherein each entry comprises a difference between a lowest dissimilarity measure level of a first component within which the pixel is disposed in the corresponding area zone and a lowest dissimilarity measure level of a first component within which the pixel is disposed in a subsequent area zone,

determining for each pixel of the input overhead image, using the processor, a largest entry in the vector corresponding to the pixel, wherein the largest entry is a lifetime parameter value;

clustering pixels in the image layer having common respective lifetime parameters into a plurality of corresponding second components;

obtaining at least one feature element of each of the second components; and

ascertaining whether each of the second components is associated with a structure of interest in the at least one input overhead image based on the at least one feature element.

15. The method of claim 14, wherein the at least one feature element comprises at least one geometric attribute.

16. The method of claim 14, wherein the at least one feature elements comprise contour smoothness, linearity, entropy, moment invariants, area, or compactness.

17. The method of claim 14, further comprising:

generating a second mask corresponding to the at least one input overhead image based on the second component ascertaining step that includes first regions that are ascertained to be associated with structures of interest and second regions that are ascertained to not be associated with structures of interest; and

using the second mask to remove portions that are not associated with structures of interest from the resultant image of the geographical region.

18. The method of claim 14, further comprising:

obtaining at least one additional feature element of each of the second components ascertained to not be structures of interest;

obtaining at least one additional feature element of each of the second components ascertained to be structures of interest;

analyzing the at least one additional feature elements of the second components ascertained to be structures of interest in view of the at least one additional feature elements of the second components ascertained to not be structures of interest; and

removing second components ascertained to not be of interest from the resultant image of the geographical region based on the analyzing.

19. The method of claim 18, wherein the at least one additional feature elements are radiometric attributes.

20. The method of claim 18, further comprising:

color coding each of the mapped pixels in the resultant image based on the lifetime parameter value of the corresponding second component of the mapped pixel.

21. The method of claim 18, further comprising:

generating, with the processor, a rule for removing second components that are not associated with structures of interest in the at least one input overhead image using at least one additional feature element of the detected first components and the at least one additional feature element of the second components ascertained to not be of interest

22. The method of claim 21, wherein each of the at least one additional feature elements are radiometric attributes.

23. The method of claim 21, further comprising:

obtaining at least one additional attribute of each of the second components ascertained to be associated with structures of interest in the at least one input overhead image;

applying, using the processor, the rule against the at least one additional attribute of each of the second components ascertained to be associated with structures of interest in the at least one input overhead image to remove second components that are not associated with structures of interest in the at least one input overhead image.

24. The method of claim 1, wherein the dissimilarity measure is a maximum intensity difference.

25. The method of claim 24, wherein the at least one input overhead image comprises a multispectral image including a plurality of spectral bands, and wherein the dissimilarity measure is a maximum intensity difference among all of the plurality of spectral bands.

36. The method of claim 1, further comprising:

tagging, using the processor, each of the first components based on a number of pixels present in the first component to identify one of a plurality of area zones within which the first component resides, wherein each successive area zone includes first components having a greater number of pixels than do the first components of a previous area zone; and

generating for each pixel of the input overhead image, using the processor, a vector including a number of entries corresponding to each of the area zones from the tagging step, wherein each entry comprises a difference between a lowest dissimilarity measure level of a first component within which the pixel is disposed in the corresponding area zone and a lowest dissimilarity measure level of a first component within which the pixel is disposed in a subsequent area zone.

37. The method of claim 36, further comprising:

determining for each pixel of the input overhead image, using the processor, a largest entry in the vector corresponding to the pixel, wherein the largest entry is a lifetime parameter value.

38. The method of claim 37, further comprising:

generating an image layer that includes the lifetime parameter values of the pixels of the input overhead image.

39. The method of claim 38, further comprising:

mapping the lifetime parameter layer into a resultant image that is associated with the geographical region.

40. The method of claim 39, further comprising:

determining for each pixel of the input overhead image, using the processor, the area zone of the largest entry in the vector corresponding to the pixel, wherein the area zone of the largest entry is a scale parameter value;

generating an image layer that includes the scale parameter values of the pixels of the input overhead image; and

mapping the scale parameter layer into the resultant image that is associated with the geographical region.

41. The method of claim 40, further comprising:

determining for each pixel of the input overhead image, using the processor, the lowest predetermined level of the dissimilarity measure in the area zone of the largest entry in the vector corresponding to the pixel, wherein the lowest predetermined level of the dissimilarity measure in the area zone of the largest entry in the vector corresponding to the pixel is a dissimilarity parameter value;

generating an image layer that includes the dissimilarity parameter values of the pixels of the input overhead image; and

mapping the dissimilarity parameter layer into the resultant image that is associated with the geographical region.

42. The method of claim 41, further comprising:

utilizing a color conversion tool to map the lifetime, scale and dissimilarity parameter layers into the resultant image.

2-9. -9. (canceled)

26. A system for extracting structures of interest from overhead imagery, comprising:

a construction engine, executable by a processor, that organizes a plurality of pixels of an input overhead image associated with a geographic area into a plurality of components of a hierarchical data structure, wherein each pixel in each group is adjacent to at least one other pixel in the group, wherein adjacent pixels in each group do not differ by more than a predetermined level of a dissimilarity measure between the adjacent pixels, wherein a plurality of such groups of pixels at each of a plurality of successive predetermined levels of the dissimilarity measure are identified, and wherein each group is a first component; and

a non-target clustering engine, executable by the processor, that;

detects first components in the hierarchical data structure that each include pixels collectively comprising a geometric attribute level greater than a threshold geometric attribute level;

obtains at least one attribute of each of the detected first components;

ascertains whether the at least one attribute of each the detected first components is associated with a structure of interest in the at least one input overhead image; and

generates a mask corresponding to the geographic area based on the detected first component ascertaining step that includes first regions that are ascertained to be associated with structures of interest and second regions that are ascertained to not be associated with structures of interest.

27. The system of claim 35, wherein the DAP engine derives at least one attribute of each pixel by determining a largest entry in the vector corresponding to the pixel, wherein the largest entry is a lifetime attribute.

28. The system of claim 27, wherein the DAP engine derives at least one attribute of each pixel by determining the area zone of the largest entry in the vector corresponding to the pixel, wherein the area zone of the largest entry is a scale attribute.

29. The system of claim 28, wherein the DAP engine derives at least one attribute of each pixel by determining the lowest predetermined level of the dissimilarity measure in the area zone of the largest entry in the vector corresponding to the pixel, wherein the lowest predetermined level of the dissimilarity measure in the area zone of the largest entry in the vector corresponding to the pixel is a dissimilarity attribute.

31. The system of claim 26, wherein the detected first components comprise lower predetermined levels of the dissimilarity measure than other of the predetermined levels of the dissimilarity measure.

32. The system of claim 31, wherein the geometric attribute comprises geographical area.

33. The system of claim 31, wherein the geometric attribute comprises non-compactness.

34. The system of claim 31, further comprising a mapping engine that:

generates an image layer based on the at least one attributes of the pixels;

applies the mask over the image layer to remove regions of the image layer that are not associated with structures of interest; and

maps resulting portions of the image layer into a resultant image that is associated with the geographical region.

35. The system of claim 26, further including:

a differential area profile (DAP) engine, executable by the processor, that;

tags each of the first components to identify one of a plurality of area zones within which the first component resides based on a number of pixels present in the first component, wherein each successive area zone includes first components having a greater number of pixels than do the first components of a previous area zone;

generates, for each pixel of the input overhead image, a vector including a number of entries corresponding to each of the area zones, wherein each entry comprises a difference between a lowest dissimilarity measure level of a first component within which the pixel is disposed in the corresponding area zone and a lowest dissimilarity measure level of a first component within which the pixel is disposed in a subsequent area zone; and

derives, for each pixel of the input overhead image, at least one attribute of the pixel based on the vector of the pixel

30. (canceled)