Classification of multispectral or hyperspectral satellite imagery using clustering of sparse approximations on sparse representations in learned dictionaries obtained using efficient convolutional sparse coding

• US 9,858,502 B2
• Filed: 04/21/2016
• Issued: 01/02/2018
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: TRIAD National Security, LLC
• Original Assignee: Los Alamos National Security LLC (Government of the United States of America)
• Inventors: Moody, Daniela, Wohlberg, Brendt
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US15/134,437
• Publication Number:
  US 20170213109A1
• Time in Patent Office: 621 Days
• CPC Class Codes: G06F 17/14 Fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms for correlation function computation G06F17/156; spectrum analysers G01R23/16
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06V 10/513 Sparse representations
• CPC Class Codes: G06V 20/13 Satellite images
• CPC Class Codes: H03M 7/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

An approach for land cover classification, seasonal and yearly change detection and monitoring, and identification of changes in man-made features may use a clustering of sparse approximations (CoSA) on sparse representations in learned dictionaries. The learned dictionaries may be derived using efficient convolutional sparse coding to build multispectral or hyperspectral, multiresolution dictionaries that are adapted to regional satellite image data. Sparse image representations of images over the learned dictionaries may be used to perform unsupervised k-means clustering into land cover categories. The clustering process behaves as a classifier in detecting real variability. This approach may combine spectral and spatial textural characteristics to detect geologic, vegetative, hydrologic, and man-made features, as well as changes in these features over time.

Claims

1. A computer-implemented method, comprising:

learning representative land features, by a computing system, from multi-band images comprising image data to form a learned dictionary {g_m};

computing a sparse representation with respect to the learned dictionary;

clustering features of the sparse representation of the image, by the computing system, into land cover categories;

performing land cover classification and change detection in a sparse domain, by the computing system, after the image is clustered; and

outputting results of the land cover classification and change detection in the sparse domain, by the computing system.

2. The computer-implemented method of claim 1, wherein the learning of the representative land features further comprises using available spectral bands in the image data in combinations to form normalized band difference indices.

3. The computer-implemented method of claim 1, wherein the clustering of the features in the image sparse representation comprises using unsupervised k-means clustering.

4. The computer-implemented method of claim 1, wherein a plurality of different spatial resolutions is used to learn multiple distinct dictionaries.

5. The computer-implemented method of claim 1, further comprising:

extracting, by the computing system, values for each pixel in a given cluster for available band indices R, comprising a normalized difference vegetation index (NDVI), a normalized difference wetness index (NDWI), a normalized difference soil index (NDSI), and a nonhomogeneous feature distance (NHFD) band ratio;

representing the given cluster, by the computing system, in R-dimensional space, such that the representation is defined by (NDVI, NDWI, NDSI, NHFD); and

using, by the computing system, a distance metric in a band difference index R-dimensional space as a separability and performance metric.

6. The computer-implemented method of claim 1, wherein the change detection is performed by calculating a relative change given by:

relative_change=(cluster_size_t2−

cluster_size_t1)/cluster_size_t1

where time t₂ is subsequent to time t₁.

7. The computer-implemented method of claim 1, wherein the change detection is determined by relative percent changes in label count comprising a change in area, given by:

8. The computer-implemented method of claim 1, further comprising:

interleaving updates, by the computing system, on sparse coding and dictionary learning such that g_m represent the dictionary in sparse coding steps and y_k,m represent sparse coding in dictionary steps; and

outputting coefficient maps {y_m}, by the computing system, when the stopping tolerances are met.

9. The computer-implemented method of claim 8, further comprising:

deriving efficient convolutional sparse coding in a frequency domain, by the computing system, within an alternating direction method of multipliers (ADMM) framework using fast Fourier transforms (FFTs).

10. The computer-implemented method of claim 9, wherein the coefficient maps {y_m} are determined with an efficiency of O(MN log N), where N is a dimensionality of the data and M is a number of elements in a dictionary.

11. The computer-implemented method of claim 9, wherein the coefficient maps {y_m} are computed using only inner products, element-wise addition, and scalar multiplication as vector operations.

12. The computer-implemented method of claim 1, wherein the dictionary in the frequency domain is concatenated as a set of block matrices and each block matrix is a diagonal.

13. The computer-implemented method of claim 1, further comprising:

clustering, by the computing system, features in a first image of an area taken at a first time and cluster features in a second image of the area taken at a second time, wherein the second time is after the first time;

calculating, by the computing system, a relative change in pixel labels and/or cluster size between clusters from the first image and clusters from the second image; and

outputting, by the computing system, results of the calculation of the relative change in the pixel labels and/or the cluster size.

18. The computer program of claim 1, wherein the dictionary in the frequency domain is concatenated as a set of block matrices and each block matrix is a diagonal.

14. A computer program embodied on a non-transitory computer-readable medium, the program configured to cause at least one processor to:

form a learned dictionary by computing the dictionary in a frequency domain by using coefficient maps, using an iterated Sherman-Morrison algorithm for a dictionary update, and output a dictionary when stopping tolerances are met;

compute a sparse representation with respect to the learned dictionary;

cluster feature vectors extracted from the sparse representation into land cover categories;

perform land cover classification and change detection in a sparse domain after the image is clustered; and

output results of the land cover classification and change detection in the sparse domain.

15. The computer program of claim 14, wherein a plurality of different spatial resolutions is used to learn distinct dictionaries.

16. The computer program of claim 14, wherein the program is further configured to cause the at least one processor to:

extract values for each pixel in a given cluster for available band indices R, comprising a normalized difference vegetation index (NDVI), a normalized difference wetness index (NDWI), a normalized difference soil index (NDSI), and a nonhomogeneous feature distance (NHFD) band ratio;

represent the given cluster in R-dimensional space, such that the representation is defined by (NDVI, NDWI, NDSI, NHFD); and

use, a distance metric in a band difference index R-dimensional space as a separability and performance metric.

17. The computer program of claim 15, wherein the program is further configured to cause the at least one processor to:

interleave updates on sparse coding and dictionary learning; and

output coefficient maps when the stopping tolerances are met.

19. An apparatus, comprising:

memory storing computer program instructions; and

at least one processor configured to execute the stored computer program instructions, wherein the at least one processor, by executing the stored computer program instructions, is configured to;

form a learned dictionary by computing the dictionary in a frequency domain by using coefficient maps, using an iterated Sherman-Morrison algorithm for a dictionary update, and output a dictionary when stopping tolerances are met,

compute a sparse representation with respect to the learned dictionary,

perform land cover classification and/or change detection in a sparse domain, and

output results of the land cover classification and/or change detection in the sparse domain.

20. The apparatus of claim 19, wherein the dictionary in the frequency domain is concatenated as a set of block matrices and each block matrix is a diagonal.