Automatic generation of built-up layers from high resolution satellite image data

• US 9,230,168 B2
• Filed: 07/31/2013
• Issued: 01/05/2016
• Est. Priority Date: 07/31/2013
• Status: Active Grant

• Current Assignee: Maxar Intelligence Incorporated (Galileo Parent, Inc.)
• Original Assignee: DigitalGlobe, Inc. (Galileo Parent, Inc.)
• Inventors: Gueguen, Lionel
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): SHIN, SOO JUNG
• Application Number:
  US13/955,268
• Publication Number:
  US 20150036874A1
• Time in Patent Office: 888 Days
• Field of Search: None
• US Class Current: 1/1
• 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/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

A system for automatically extracting interesting structures or areas (e.g., built-up structures such as buildings, tents, etc.) from HR/VHR satellite imagery data using corresponding LR satellite imagery data. The system breaks down HR/VHR input satellite images into a plurality of components (e.g., groups of pixels), organizes the components into a first hierarchical data structure (e.g., a Max-Tree), generates a second hierarchical data structure (e.g., a KD-Tree) from feature elements (e.g., spectral and shape characteristics) of the components, uses LR satellite imagery data to categorize components as being of interest or not, uses the feature elements of the categorized components to train the second data structure to be able to classify all components of the first data structure as being of interest or not, classifies the components of the first data structure with the trained second data structure, and then maps components classified as being of interest into a resultant image.

Claims

1. A method of extracting built-up structures from satellite imagery data, comprising:

organizing, using a processor, pixels of an input satellite image into a plurality of components of a first hierarchical data structure, wherein the input image is associated with a geographic area, and wherein each of the components is characterized by a vector of feature elements;

constructing, using the processor, a second hierarchical data structure that includes a plurality of hierarchically-arranged nodes, wherein each of the feature elements depends from at least one of the plurality of nodes, and wherein the constructing includes;

disposing the feature elements of the vectors of the components of the first hierarchical data structure into a feature space; and

recursively partitioning the feature elements in the feature space to create the plurality of hierarchically-arranged nodes of the second hierarchical data structure;

deriving training components from the plurality of components of the first hierarchical data structure that indicate built-up and non-built-up structures in the input image using a first reference image data set that is associated with the geographic area;

training, with the processor, the second hierarchical data structure with the vector of feature elements of each of the training components for detecting built-up structures;

classifying, with the processor and using the trained second hierarchical data structure, the plurality of components of the first hierarchical data structure as identifying built-up structures or non-built-up structures; and

mapping components of the plurality of components that identify built-up structures as classified during the classifying step into a resultant image that is associated with the geographic area.

2. The method of claim 1, further comprising:

deriving additional training components from the plurality of components of the first hierarchical data structure that indicate built-up and non-built-up structures in the input image using the first reference image data set;

training, with the processor, the second hierarchical data structure with the vector of feature elements of each of the additional training components for detecting built-up structures; and

classifying, with the processor and using the second hierarchical data structure as trained with the additional training components, the plurality of components of the first hierarchical data structure as identifying built-up structures or not identifying built-up structures.

3. The method of claim 1, further comprising:

ascertaining error rates between components that identify built-up structures from the classifying step and corresponding portions of a second reference image data set that identify built-up structures; and

mapping components that identify built-up structures that are associated with error rates below a threshold error rate into the resultant image that is associated with the geographic area.

4. The method of claim 3, wherein the first and second reference data sets are different.

5. The method of claim 3, wherein the first and second reference data sets are the same.

6. The method of claim 3, wherein the input image comprises a first input image, wherein the method further comprises:

organizing, using the processor, pixels of a second input image into a plurality of components of a first hierarchical data structure, wherein the second input image is associated with the geographic area, wherein each of the components is characterized by a vector of feature elements, and wherein the first and second input images are at least one of multi-temporal or captured from different locations;

constructing, using the processor, a second hierarchical data structure that includes a plurality of hierarchically-arranged nodes, wherein each of the feature elements of the second input image depends from at least one of the plurality of nodes; and

deriving training components from the plurality of components of the first hierarchical data structure that indicate built-up and non-built-up structures in the second input image using the first reference image data set;

training, with the processor, the second hierarchical data structure with the vector of feature elements of each of the training components of the second input image for detecting built-up structures;

classifying, with the processor and using the second hierarchical data structure as trained with the training components of the second input image, the plurality of components of the second input image of the first hierarchical data structure as identifying built-up structures or non-built-up structures;

ascertaining error rates between components of the second input image that identify built-up structures from the classifying step and corresponding portions of the second reference data set that identify built-up structures; and

mapping components that identify built-up structures in the second input image that are associated with error rates below a threshold error rate into the resultant image, wherein the resultant image comprises components from the first and second input images.

7. The method of claim 6, further comprising:

continuing to perform the organizing, constructing, deriving, training, classifying, ascertaining, and mapping steps with respect to additional input images that are at least one of multi-temporal relative to the first and second input images or captured from locations different than those from which the first and second input images were captured.

8. The method of claim 1, wherein one of the training components identifies built-up structures when the training component falls within a built-up area as indicated by the first reference data set.

9. The method of claim 1, wherein the plurality of feature elements comprises at least two of contrast, area, compactness, linearity, average spectral response, eccentricity or inertia of a respective one of the plurality of components.

10. A method of extracting built-up structures from satellite imagery data, comprising:

organizing, using a processor, an input satellite image into a plurality of components of a first hierarchical data structure, wherein the input image is associated with a geographic area and has a first resolution, and wherein each of the components is characterized by a plurality of feature elements;

constructing, using the processor, a second hierarchical data structure that includes a plurality of hierarchically-arranged nodes, wherein each of the feature elements depends from at least one of the plurality of nodes, and wherein the constructing includes;

disposing the feature elements of the vectors of the components of the first hierarchical data structure into a feature space; and

recursively partitioning the feature elements in the feature space to create the plurality of hierarchically-arranged nodes of the second hierarchical data structure; and

deriving training components from the plurality of components of the first hierarchical data structure that indicate built-up and non-built-up structures in the input image using a first reference image data set that is associated with the geographic area and has a second resolution lower than the first resolution.

11. The method of claim 10, further comprising:

training, with the processor, the second hierarchical data structure with the plurality of feature elements of each of the training components for detecting built-up structures; and

classifying, with the processor and using the trained second hierarchical data structure, the plurality of components of the first hierarchical data structure as identifying built-up structures or non-built-up structures.

12. The method of claim 11, wherein the training step comprises:

updating class counters of nodes of the second hierarchical data structure in response to feature elements of the training components corresponding to built-up or non built-up structures, wherein each node of the second hierarchical data structure comprises a built-up structure counter and a non built-up structure counter, and wherein the updating steps comprises;

increasing the count of one of the built-up structure counter and the non built-up structure counter.

13. The method of any of claim 11, further comprising:

mapping components of the plurality of components that identify built-up structures as classified during the classifying step into a resultant image that is associated with the geographic area and that has a third resolution that is greater than the second resolution.

14. The method of claim 13, further comprising:

deriving additional training components from the plurality of components of the first hierarchical data structure that indicate built-up and non-built-up structures in the input image using the first reference image data set, wherein the training components are non-overlapping with the additional training components;

training, with the processor, the second hierarchical data structure with the plurality of feature elements of each of the additional training components for detecting built-up structures; and

classifying, with the processor and using the second hierarchical data structure as trained with the additional training components, the plurality of components of the first hierarchical data structure as identifying built-up structures or not identifying built-up structures.

15. The method of claim 11, further comprising:

ascertaining error rates between components that identify built-up structures from the classifying step and corresponding portions of a second reference image data set that identify built-up structures; and

mapping components that identify built-up structures that are associated with error rates below a threshold error rate into a resultant image that is associated with the geographic areas and that has a third resolution that is greater than the second resolution.

16. The method of claim 15, wherein the second reference image set is associated with the geographic area and has a fourth resolution lower than the first resolution.

17. A system for extracting structures of interest from optical images, comprising:

a construction engine, executable by a processor, that organizes the pixels of an input image associated with a geographic area and having a first resolution into a plurality of components, generates a first hierarchical data structure from the plurality of components that includes a plurality of k-dimensional feature elements of each of the components, and creates a second hierarchical data structure that includes a plurality of hierarchically-arranged nodes, wherein each of the feature elements depends from at least one of the plurality of nodes, and wherein the construction engine creates the second hierarchical data structure by disposing the feature elements of the vectors of the components of the first hierarchical data structure into a feature space and recursively partitioning the feature elements in the feature space to create the plurality of hierarchically-arranged nodes of the second hierarchical data structure; and

a training engine that uses feature elements of a first portion of the plurality of components of the first hierarchical data structure to train the second hierarchical data structure to detect components of the plurality of components in the first hierarchical data structure that correspond to structures of interest in the input image.

18. The system of claim 17, further comprising:

a classification engine, executable by the processor, that uses the trained second hierarchical data structure to extract a second portion of the plurality of components of the first hierarchical data structure that corresponds to the structures of interest in the input image, wherein the second portion encompasses the first portion.

19. The system of claim 18, further comprising:

a mapping engine that maps the second portion into a resultant image associated with the geographic area.

20. The system of claim 17, wherein the training engine utilizes a portion of a reference information layer associated with the geographic area to identify the first portion, wherein the input image has a first resolution and the reference image has a second resolution lower than the first resolution, and wherein the system further comprises:

a mapping engine that maps the second portion into a resultant image that is associated with the geographic area and that has a third resolution that is greater than the second resolution.