Transcript Remote Object Classification using Spectral Data

Nonnegative Tensor Factorization for
Object Identification using
Hyperspectral Data
Bob Plemmons
Wake Forest University
• Joint work with:
- Peter Zhang, Han Wang, Paul Pauca: WFU
• Interactions:
– Kira Abercromby: NASA JSC
– Maj. Travis Blake: U.S. Air Force
• Related Papers at: http://www.wfu.edu/~plemmons
Outline
• Object Identification from Spectral Data (SOI)
• Nonnegative Matrix Factorization (NMF) Methods for
Spectral Unmixing
• Nonnegative Tensor Factorization (NTF), and Applications
• 3-D Tensor Factorization: Applications to SOI, using
Hyperspectral Data
– Compression
– Material identification
– Spectral abundances
– Another Application (Medical)
2
Space Object Identification and Characterization from
Spectral Reflectance Data
More than 15,000 known man-made objects in orbit: various
types of military and commercial satellites, rocket bodies,
residual parts, and debris – need for space object database
mining, object identification, clustering, classification, etc.
3
The creation and observation of a reflectance spectrum
Satellite
SUN
B
A
Oceanit, Maui Research and Technology Center, 590 Lipoa Parkway, Ste. 264, Kihei, HI 96753
Zenith
At
m
os
ph
er
e
Z
C
EL
Day
Night
D
4
Sample Spectral Scan
5
Pixel (Semi) Blind Source Separation for
Finding Hidden Components (Endmembers)
Mixing of Sources
…basic physics often leads to linear mixing…
X = [X1,X2, …,Xn] –column vectors (1-D spectral scans)
Approximately factor
X  W H = 1k w(j)± h(j)
±
wj
X
W
H
denotes outer product
is jth col of W, hj is jth col of HT
sensor readings (mixed components – observed data)
separated components (feature basis matrix, unknown, low rank)
hidden mixing coefficients (unknown), replaced later with
abundances of materials that make up the object.
6
Nonnegative Matrix Factorization (NMF)
Actually an approximate decomposition
7
Overview of the Object Identification Problem
• Problem solution by learning the parts of objects (hidden components)
by low rank nonnegative sparse representation
• Basis representation (dimension reduction) can enable near real-time
object (target) recognition, object class clustering, and
characterization. (ill-posed inverse problem)
• Match recovered hidden components with known spectral signatures
from substances such as mylar, aluminum, white paint, kapton, and
solar panel materials, etc. This is classification.
• Fundamental difficulty: Find from spectral measurements:
– Endmembers: types of constituent materials
– Fractional abundances: proportion of materials that comprise the object.
8
An Approach to Selecting Endmembers and
Computing Fractional Abundances
•
•
Vectorize the spectral scans of space objects into columns of a matrix Y
Cluster the columns of Y using a NMF scheme
Y  WH, W ≥ 0, H ≥ 0
(Enforce smoothness on W and sparsity on H.)
•
Classify the basis vectors in W using lab data from Jorgersen and an
information theoretic scoring method (Kullback-Leibler divergence, i.e., relative
entropy). Represent these endmembers by a matrix B.
•
B represents a compressed database for Y and has a variety of uses, e.g., ....
•
Determine the spectral abundances of the space object spectral scans in
columns of Y by iteratively solving nonlinear least squares problems with matrix
B containing the classified endmembers.
(We use a nonlinear least squares scheme to compute material abundancies.)
9
Sample Results from Prior Work (P. Pauca)
Formed Simulated Satellites from NASA Data
10
A Few Combined Traces
(time varying mixtures)
11
Blind Source Separation Using NMF –
Guided Blind Source Separation
12
Original
Recovered
13
Hyperspectral Imaging
• Hyperspectral remote sensing technology allows
one to capture images objects (multiple pixels),
using a range of spectra from ultraviolet and visible
to infrared.
• Multiple images of a scene or object are created
using light from different parts of the spectrum.
• Hyperspectral images can be used to:
– Detect and identify militarily important objects at a
distance.
– Identify surface minerals, objects, buildings, etc. from
space.
– Enable space object identification from the ground.
14
A Matrix of Hyperspectral Data
15
A Better Approach?
Tensors
Multi-way Arrays
in Multilinear Algebra
Applications to Hyperspectral Data Analysis
Extend NMF: Nonegative Tensor Factorization
(NTF)
• Our interest: 3-D data. 2-D images stacked into
3-D Array, forming a “box”
17
Tensors in a Nutshell
• A matrix is an order-2 tensor, a 2-array of elements
• An order-k tensor is simply a k-array of elements
• 1920s: tensor analysis became immensely popular after
Einstein used tensors as the natural language to describe
laws of physics in a way that does not depend on the initial
frame of reference.
• Standard concepts for matrices, such as rank, eigenvalues,
etc. - more complicated for tensors
• Our concern is tensors in a multilinear algebra context:
T = [tj1…jk] 2 Rd1 £ … £ dk
18
Multilinear NMF = Nonnegative
Tensor Factorization (NTF)
19
NTF (for 3-D Arrays)
20
Datasets of images modeled as tensors
Goal: Extract features from a tensor dataset (naively, a
dataset subscripted by multiple indices). Image samples
with diversities, e.g., eigenviews.
m £ n £ p tensor T
Tensor (outer product) rank can be defined as the
minimum number of rank 1 factors.
21
Properties of Matrix Rank
• Rank of A 2 Rm £ n easy to determine (Gauss elimination).
• Optimal rank-r approximation to A always exists, and easy
to find ( SVD).
• Pick A 2 Rm £ n at random, then A has full rank with
probability 1, i.e., rank(A) = min{m,n}.
• Rank A is is the same whether we consider A as an element
in Rm £ n or in Cm £ n.
• Every statement above is false for order-k tensors, k ¸ 3.
22
NTF and Applications to
Analysis of Massive Data Sets
Stanford MMDS workshop, June 2006 See:
http://www.stanford.edu/group/mmds/
23
Datasets of images modeled as tensors
m £ n £ p tensor T
24
PALSIR:
Projected Alternating Least Squares with
Initialization and Regularization
by
Boutsidis/Zhang/Gallopoulis/Ple.
Presented at Stanford MMDS Workshop, June 2006
25
Data from Maui Imaging Site
Space Shuttle Columbia in Orbit
Separation by Parts using NTF – Peter Zhang
26
Clustering for segmentation using
NTF
27
AEOS Spectral Imaging Sensor (ASIS)
• Capable of collecting spatially resolved
imagery of space objects in up to 100
spectral bands.
• Collects adaptive optics compensated
hyperspectral images on the 3.67 meter
telescope at AMOS on Maui.
28
Simulated True Hyperspectral Data Cube for Hubble
Telescope Simulated Hypercube
29
Our Purpose
• SOI using tensor analysis
• 3-D Tensor Factorization: Applications to
SOI, using Hyperspectral Data
– Compression
– Material identification
– Spectral abundances
30
Again, the Basic Idea
31
NTF Algorithm
32
Simulated Data
• 177 x 193 x 100
3-D model of Hubble satellite.
• Assign each pixel a certain spectral signature from
lab data supplied by Kira Abercromby (NASA).
8 materials used.
• Bands of spectra ranging from .4 m to 2.5 m,
with 100 evenly distributed spectral values.
• Spatial blurring followed by Gaussian and Poisson
noise and applied over the spectral bands.
33
Images from Data Cube at 1.4 m
34
Materials Assigned to Pixels
35
Spectral Scans of 8 Materials Used
36
Compression
• k is the number of factors used in the tensor
decomposition
• Choosing k = 100
Original array 177x193x100 3,416,100 bytes
X
177x100
17,700 bytes
Y
193x100
19,300 bytes
Z
100x100
10,000 bytes
total 47,000 bytes
– Compression factor (3,416,100/47,000) = 72.68
About 73 to 1.
37
Reconstruction of Blurred & Noisy Data at
wavelengths: .42, .68, 1.55, 2.29 m
Top row
– Original Images
Bottom row – Reconstructions
Illustrates need for deblurring, especially at short wavelengths.
38
Recovered Spectral Abundances of 8
materials in Hubble Simulation
39
Some Spectral Scan Matching Graphs
Red is original, Blue is matched endmember scan matched from Z-factors.
Black rubber edge (8%) not as well matched. Blurred and noisy data cube.
40
Potential Applications using Spectral Imaging
and Tensor Analysis with NTF
• DTO-ITIC: Hyperspectral imaging of objects at a
distance (cars, buildings, people) for identification
using lenslet array camera with spectral filters.
• DTO: Burn and wound assessment (with team
members at CUA)
1st degree
burn
3rd degree
burn
2nd degree
burn
41
Papers on my web page on medical applications of
NMF/NTF – joint with researchers at the
Riken Brain Science Institute, Tokyo
• Novel Multi-layer Nonnegative Tensor Factorization with
Sparsity Constraints.
A. Cichocki, R. Zdunek, S. Choi, R. Plemmons, and S.
Amari. Preprint. To appear in Proc. of the 8th
International Conference on Adaptive and Natural
Computing Algorithms, Warsaw, Poland, April 2007.
•
Nonnegative Tensor Factorization using Divergencies.
A. Cichocki, R. Zdunek, S. Choi, R. Plemmons, and S.
Amari. Preprint. To appear in Proc. of the 32nd
International Conference on Acoustics, Speech, and
Signal Processing (ICASSP), Honolulu, April 2007.
42
Summary
• NMF and NTF, SOI applications
• Compression and reconstruction of image
data using tensors
• Hyperspectral data analysis
• Tensor enabled classification and
identification of space objects in terms of
material features and spectral abundances
• Some medical applications of NMF and NTF
43