Automatic extraction of built-up footprints from high resolution overhead imagery through manipulation of alpha-tree data structures
View Patent ↗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.
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;
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.
2. The method of claim 1 , 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.
3. The method of claim 2 , further comprising:
generating an image layer that includes the lifetime parameter values of the pixels of the input overhead image, and mapping the lifetime parameter layer into a resultant image that is associated with the geographical region.
4. The method of claim 3 , 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.
5. The method of claim 4 , 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.
6. The method of claim 3 , further comprising:
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, wherein the detected first components comprise lower predetermined levels of the dissimilarity measure than other of the predetermined levels of the dissimilarity measure.
7. The method of claim 6 , 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 image layer 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;
applying the first mask over the image layer to remove portions of the image layer that are not associated with structures of interest; and
mapping resulting portions of the image layer into a resultant image that is associated with the geographical region.
8. The method of claim 7 , further comprising:
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, wherein the at least one feature element comprises at least one geometric attribute; 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.
9. The method of claim 8 , further comprising:
generating a second mask corresponding to the image layer 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
applying the second mask over the image layer to remove portions of the image layer that are not associated with structures of interest.
10. The method of claim 9 , further comprising:
obtaining at least one additional feature element of each of the second components ascertained to not be structures of interest, wherein the at least one additional feature elements are radiometric attributes;
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 based on the analyzing.
11. The method of claim 10 , 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, wherein each of the at least one additional feature elements are radiometric attributes.
12. The method of claim 11 , 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.
13. A system for extracting structures of interest from overhead imagery, comprising:
a construction engine, executable by a processor, that decomposes 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;
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.
14. The system of claim 13 , 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.
15. The system of claim 14 , 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.
16. The system of claim 15 , 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.
17. The system of claim 14 , further comprising:
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 of 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 image layer 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.
18. The system of claim 17 , wherein the detected first components comprise lower predetermined levels of the dissimilarity measure than other of the predetermined levels of the dissimilarity measure.
19. The system of claim 18 , 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.