Automated compound structure characterization in overhead imagery

Abstract

A system for automatically characterizing areas of interest (e.g., urban areas, forests, and/or other compound structures) in high resolution overhead imagery through manipulation of a dictionary of visual words. The pixels of an input overhead image are initially clustered into a plurality of hierarchically-arranged connected components of a first hierarchical data structure. Image descriptors (e.g., shape, spectral, etc.) of the connected components are then clustered into a plurality of hierarchically-arranged nodes of a second hierarchical data structure. The nodes at a particular level in the second hierarchical data structure become a dictionary of visual words. Subsets of the visual words may be used to label the cells of a grid over the geographic area as falling into one of a number of areas of interest. Categorization information from the grid may be mapped into a resultant image whereby pixels depict their respective type of area of interest.

What is claimed is: 
     
         1 . A method for use in characterizing areas of interest in overhead imagery, comprising:
 organizing, using a processor, a plurality of pixels of at least one input overhead image into a plurality of components of a first hierarchical data structure, wherein the input image is associated with a geographic area;   deriving, using the processor, at least one image descriptor for each of the components;   constructing, using the processor with at least some of the image descriptors, a second hierarchical data structure that includes a plurality of hierarchically-arranged levels of nodes, wherein the nodes of the second hierarchical data structure are arranged into a plurality of leaf paths that each extend from a root node to one of a plurality of leaf nodes, wherein each of the image descriptors depends from one of the plurality of leaf nodes, wherein at least one node at a particular one of the levels is a respective visual word, and wherein all of the visual words at the particular one of the levels collectively comprise a visual dictionary;   determining, for each cell of at least some cells of a grid of cells disposed over the geographic area, a frequency of each of one or more of the visual words in the cell; and   generating, for the cell, a vector that includes a plurality of entries, wherein each entry includes a value that represents a respective one of the frequencies.   
     
     
         2 . The method of  claim 1 , further including:
 for each cell of the least some of the cells, using the cell vector to categorize a type of compound structure found within the cell.   
     
     
         3 . The method of  claim 2 , wherein the using includes comparing the cell vector to each of a plurality of different compound structure vectors. 
     
     
         4 . The method of  claim 1 , wherein the determining step includes:
 identifying at least one of the plurality of components within the cell;   ascertaining a smallest distance between the at least one image descriptor of the identified component and each of the at least one image descriptor depending from each of a plurality of the visual words; and   classifying, based on the ascertaining step, the component as a particular one of the visual words associated with the smallest distance, wherein the classifying step contributes to the frequency of the particular one of the visual words in the cell vector.   
     
     
         5 . The method of  claim 4 , wherein the determining step further includes:
 identifying another of the plurality of components within the cell;   ascertaining a smallest distance between the at least one image descriptor of the identified another component and each of the at least one image descriptor depending from each of the plurality of the visual words; and   classifying, based on the ascertaining step, the another component as another particular one of the visual words associated with the smallest distance, wherein the classifying step contributes to the frequency of the another particular one of the visual words in the cell vector.   
     
     
         6 . The method of  claim 1 , wherein the grid of cells are defined by a width parameter that sets forth a width of each of the cells and an overlap parameter that sets forth a displacement between adjacent cells of the grid of cells. 
     
     
         7 . The method of  claim 6 , wherein the grid of cells is a first grid, wherein the method further includes:
 generating, for each cell of a plurality of cells of a second grid of the geographic area, a vector that includes a plurality of entries, wherein each entry includes a value that represents a respective frequency of one of the visual words in the cell.   
     
     
         8 . The method of  claim 7 , wherein one of the entries of the cell vectors of the first grid includes a value that represents a frequency of a first of the visual words in the cell, wherein one of the entries of the cell vectors of the second grid includes a value that represents a frequency of a second of the visual words in the cell, and wherein the first and second visual words are different. 
     
     
         9 . The method of  claim 7 , further including:
 using the cells vectors of the first grid to determine whether or not the respective cells of the first grid represents a first area of interest; and   using the cells vectors of the second grid to determine whether or not the respective cells of the second grid represents a second area of interest, wherein the first and second areas of interest are different.   
     
     
         10 . The method of  claim 1 , further including:
 identifying a subset of visual words of the visual dictionary that corresponds to an area of interest in the input overhead image;   identifying a subset of the plurality of components classified by one of the visual words in the subset of visual words; and   identifying a subset of the plurality of cells that each fully contain at least one of the components in the subset of components, wherein the determining and generating steps are performed only with respect to the subset of visual words and the subset of cells.   
     
     
         11 . The method of  claim 10 , wherein each of at least some of the components in the subset of components is fully contained within at least two of the cells. 
     
     
         12 . The method of  claim 10 , further including:
 assigning respective weighting values to each of the visual words in the subset of visual words, wherein each weighting value represents a degree to which the respective visual word indicates an area of interest;   for each cell of the subset of cells:
 obtaining, for each entry in its cell vector, a product of the entry and a corresponding one of the weighting values to obtain a plurality of products; 
 summing the plurality of products to obtain a sum; 
 identifying the cell as the area of interest if the sum has one of i) reached or exceeded a threshold and b) not reached the threshold; and 
 identifying the cells as not the area of interest of the sum has the other of i) reached or exceeded the threshold and b) not reached the threshold. 
   
     
     
         13 . The method of  claim 10 , further including:
 classifying each of the plurality of components as one of the plurality of visual words;   storing, in a storage device, each of the plurality of components in a data structure that is indexed according to the plurality of visual words;   extracting the components indexed according to the subset of visual words, wherein the extracted components are the subset of components; and   loading the extracted components and subset of visual words into memory, wherein the determining and generating steps are performed with respect to the extracted components and subset of visual words as loaded into memory.   
     
     
         14 . The method of  claim 1 , further including:
 classifying each of the plurality of components as one of the plurality of visual words;   storing, in a storage device, each of the plurality of components in a data structure that is indexed according to the plurality of visual words.   
     
     
         15 . The method of  claim 1 , wherein the visual dictionary is a first visual dictionary, and wherein all of the visual words at another particular one of the levels collectively comprise a second visual dictionary at least partially different than the first visual dictionary. 
     
     
         16 . A method of characterizing areas of interest in overhead imagery, comprising:
 organizing, with a processor, an input overhead image associated with a geographic area into a plurality of components of a first hierarchical data structure;   clustering, with the processor, a plurality of image descriptors derived from the plurality of components into a plurality of visual words of a visual dictionary;   categorizing, with the processor, each of at least some of a plurality of cells of the geographic area as one or more areas of interest based on one or more respective ones of the visual words in the cell.   
     
     
         17 . The method of  claim 16 , further including:
 determining, for each of at least some cells of the plurality of cells of the geographic area, a frequency of each of one or more of the visual words in the cell;   generating, for each of the cells, a vector that includes a plurality of entries, wherein each entry includes a value that represents a respective one of the visual word frequencies; and   characterizing a type of one or more portions of interest within each of the plurality of cells based on the respective cell vector.   
     
     
         18 . The method of  claim 17 , wherein the characterizing step utilizes less than all of the entries in the vector. 
     
     
         19 . The method of  claim 17 , further including:
 mapping the plurality of cells into a resultant image that is associated with the geographic area, wherein each cell in the resultant image depicts its respective characterized type.   
     
     
         20 . The method of  claim 17 , further comprising:
 selecting a sample of one of the areas of interest in the input overhead image;   determining, for the sample, a frequency of each of one or more of the visual words in the sample; and   generating, for the sample, a vector that includes a plurality of entries, wherein each entry includes a value that represents a respective one of the visual word frequencies, wherein the categorizing uses the sample vectors and the cell vectors.