# Hyperspectral Target Detection Based on Low-Rank Background Subspace
Learning and Graph Laplacian Regularization

###### Abstract

Hyperspectral target detection is good at finding dim and small objects based
on spectral characteristics. However, existing representation-based methods
are hindered by the problem of the unknown background dictionary and
insufficient utilization of spatial information. To address these issues, this
paper proposes an efficient optimizing approach based on low-rank
representation (LRR) and graph Laplacian regularization (GLR). Firstly, to
obtain a complete and pure background dictionary, we propose a LRR-based
background subspace learning method by jointly mining the low-dimensional
structure of all pixels. Secondly, to fully exploit local spatial
relationships and capture the underlying geometric structure, a local region-
based GLR is employed to estimate the coefficients. Finally, the desired
detection map is generated by computing the ratio of representation errors
from binary hypothesis testing. The experiments conducted on two benchmark
datasets validate the effectiveness and superiority of the approach. For
reproduction, the accompanying code is available at
https://github.com/shendb2022/LRBSL-GLR.

Index Terms—  Hyperspectral image, target detection, low-rank representation,
graph Laplacian regularization.

##  1 Introduction

Due to the integration of spatial and spectral information, hyperspectral
images (HSIs) facilitate the detection of dim and small targets, which have a
wide range of applications in military and civilian fields[1]. The objective
of hyperspectral target detection (HTD) is to achieve a comprehensive
separation between target and background information by prominently
highlighting targets while effectively suppressing the background. However,
the limited prior knowledge, namely an HSI and a target spectrum, makes this
task challenging.

To achieve this task, various detection methods have been proposed. Euclidean
distance and cosine similarity are simple techniques commonly used for direct
spectral matching. However, in practical scenarios, their performance is often
below expectations due to the inherent diversity and variability of spectra.
Statistical assumption-based methods [2] operate under the hypothesis that the
background follows a multivariate Gaussian distribution, allowing the
estimation of pixel probabilities belonging to targets using statistical
techniques. However, these methods often experience a decline in performance
because the actual distribution of the background is typically complex and
does not align with the underlying assumption. The representation-based
methods model HTD as an optimization problem by combining spectral unmixing
and some common properties such as sparsity, low rank, and smoothness, which
have achieved success in detection performance and physical interpretability.
Nevertheless, there are still two problems. First, a background dictionary
with completeness and purity is difficult to obtain. Researchers usually use
pre-detection[3], clustering[4], or orthogonal projection[5] methods to select
typical background samples to form a background dictionary, in which the atoms
still come from pixel samples, carry noise, and may have mixed redundancy.
Second, spatial information is rarely employed in most representation-based
methods, which limits the detection performance. Some researchers [6, 7]
exploit the total variation to promote the spatial smoothness of coefficients
but only consider the spatial similarity between a pixel and its four
neighbors.

To tackle the aforementioned issues, an efficient optimizing approach using
low-rank representation (LRR) and graph Laplace regularization (GLR) is
proposed. To overcome the problem of obtaining a complete and pure background
dictionary, we propose a low-rank background subspace learning (LRBSL) method
by jointly mining the low-dimensional structure of all pixels. This strategy
not only learns the underlying background atoms but also alleviates the
contamination of target spectra to them. Moreover, in order to mine the
spatial context features and capture the underlying geometric structure, a
local region-based GLR (LRB-GLR) is employed to estimate the coefficients.
Combining this regularization and sparse representation, the spatial-spectral
features can be effectively extracted for detection. Finally, the desired
detection map can be obtained by computing the ratio of representation errors
from binary hypothesis testing. The least squares and proposed LRB-GLR are
responsible for the hypothesis of modeling background and target,
respectively. Experiments are conducted on two benchmark datasets and
illustrate the effectiveness of the proposed method in terms of quantitative
metrics and visualizations.

##  2 Proposed Method

###  2.1 LRBSL

Given an HSI ${\bf X}\in\mathbb{R}^{L\times N}$ and a target spectrum ${\bf
t}\in\mathbb{R}^{L\times 1}$, where $L$ and $N$ denote the number of bands and
pixels, respectively, the linear mixing model is

${\bf X}={\bf A}{\bf S}_{1}+{\bf t}{\bf S}_{2}+{\bf E},$ (1)

where ${\bf A}\in\mathbb{R}^{L\times K}$ is the background subspace with $K$
bases, ${\bf S}_{1}\in\mathbb{R}^{K\times N}$ and ${\bf
S}_{2}\in\mathbb{R}^{1\times N}$ are the encoding coefficients of background
and target components, respectively, and ${{\bf E}\in\mathbb{R}^{L\times N}}$
is the representation error. To separate the background and target components,
the unknown background subspace needs to be estimated. Here, we propose a two-
step optimization method based on sparse representation and LRR.

In the first step, we fix the joint subspace and estimate the coefficients by
incorporating the sparse prior:

$\min_{{\bf S}}{\frac{1}{2}\|{\bf X}-{\bf B}{\bf
S}\|_{F}^{2}}+\lambda_{1}\|{\bf S}\|_{1},$ (2)

where $\|\cdot\|_{F}$ and $\|\cdot\|_{1}$ denote the Frobenius norm and
L1-norm, respectively, ${\bf B}=[{\bf A},{\bf t}]$ is the joint subspace,
${\bf S}=[{\bf S}_{1}^{T},{\bf S}_{2}^{T}]^{T}$ is the joint coefficients, and
$\lambda_{1}$ is a trade-off parameter. To ensure the independencies of
background atoms, ${\bf A}$ is initially generated by truncated singular value
decomposition (SVD):

${\bf A},{\bf\Sigma},{\bf U}^{T}={\rm svd}({\bf X},K),$ (3)

where ${\rm svd}$ is the truncated SVD function keeping the top $K$ largest
singular values, and ${\bf\Sigma}\in\mathbb{R}^{K\times K}$ and ${\bf
U}\in\mathbb{R}^{N\times K}$ are diagonal and semiunitary matrices,
respectively.

In the second step, we divide the estimated coefficients ${\bf S}$ into ${\bf
S}_{1}={\bf S}(:K)$ and ${\bf S}_{2}={\bf S}(K:)$, and employ the low-rank
property to learn the background subspace:

$\min_{{\bf A}}{\frac{1}{2}\|{\bf X}-{\bf A}{\bf S}_{1}-{\bf t}{\bf
S}_{2}\|_{F}^{2}}+\lambda_{2}\|{\bf A}\|_{*},$ (4)

where $\|\cdot\|_{*}$ is the nuclear norm to characterize the low-rank
constraint, and $\lambda_{2}$ is a trade-off parameter.

Models (2) and (4) can be efficiently solved using the alternating direction
method of multipliers (ADMM). By introducing ${\bf Z}={\bf S}$ and ${\bf
D}={\bf A}$, the augmented Lagrangian function can be respectively expressed
as

$\begin{split}{\mathcal{L}}_{1}&=\frac{1}{2}\|{\bf X}-{\bf B}{\bf
S}\|_{F}^{2}+\lambda_{1}\|{\bf Z}\|_{1}+\frac{\mu_{1}}{2}\|{\bf S}-{\bf
Z}+\frac{{\bf G}_{1}}{\mu_{1}}\|_{F}^{2},\\\
{\mathcal{L}}_{2}&=\frac{1}{2}\|{\bf X}-{\bf A}{\bf S}_{1}-{\bf t}{\bf
S}_{2}\|_{F}^{2}+\lambda_{2}\|{\bf D}\|_{*}\\\ &+\frac{\mu_{2}}{2}\|{\bf
A}-{\bf D}+\frac{{\bf G}_{2}}{\mu_{2}}\|_{F}^{2},\end{split}$ (5)

where ${\bf G}_{1}$ and ${\bf G}_{2}$ are two Lagrangian multipliers, and
$\mu_{1}$ and $\mu_{2}$ are two regularization parameters. The models can be
decomposed into the alternated optimization of subproblems. The process of
optimization is summarized in Algorithm 1, where $\rm soft$ denotes the soft
thresholding function, $\rm svt$ denotes the singular value thresholding
function, and ${\bf I}_{j}$ is an identity matrix numbered $j$.

Algorithm 1 Optimization procedure of LRBSL

1:Input: $\bf X$, $\bf t$, $\bf B$, $\lambda_{1}$, $\lambda_{2}$, $K$.

2:Initialize: ${\bf S}^{(0)}={\bf Z}^{(0)}={\bf G}_{1}^{(0)}={\bf 0}$, ${\bf
A}^{(0)}={\bf D}^{(0)}={\bf G}_{2}^{(0)}={\bf 0}$, $\mu_{1}=\mu_{2}=10^{-3}$,
$\mu_{max}=10^{10}$, $\gamma=1.2$, $\epsilon=10^{-6}$, $k=0$, $k_{max}=200$.

3:while $\|{\bf S}-{\bf Z}\|_{F}\geq\epsilon$ and $k<k_{max}$ do

4: ${\bf Z}^{(k+1)}={\rm soft}({\bf S}^{(k)}+{\bf
G}_{1}^{(k)}/\mu_{1},\lambda_{1}/\mu_{1})$;

5: ${\bf S}^{(k+1)}=({\bf B}^{T}{\bf B}+\mu_{1}{\bf I}_{1})^{-1}$

6: $({\bf B}^{T}{\bf X}+\mu_{1}{\bf Z}^{(k+1)}-{\bf G}_{1}^{(k)})$;

7: ${\bf G}_{1}^{(k+1)}={\bf G}_{1}^{(k)}+\mu_{1}({\bf S}^{(k+1)}-{\bf
Z}^{(k+1)})$;

8: $\mu_{1}={\rm min}(\mu_{max},\mu_{1}\times\gamma)$;

9: $k=k+1$;

10:end while

11:${\bf S}_{1}={\bf S}^{(k)}(:K)$, ${\bf S}_{2}={\bf S}^{(k)}(K:)$, $k=0$;

12:while $\|{\bf A}-{\bf D}\|_{F}\geq\epsilon$ and $k<k_{max}$ do

13: ${\bf D}^{(k+1)}={\rm svt}({\bf A}^{(k)}+{\bf
G}_{2}^{(k)}/\mu_{2},\lambda_{2}/\mu_{2})$;

14: ${\bf A}^{(k+1)}=(({\bf X}-{\bf t}{\bf S}_{2}){\bf S}_{1}^{T}+\mu_{2}{\bf
D}^{(k+1)}-{\bf G}_{2}^{(k)})$

15: $({\bf S}{\bf S}^{T}+\mu_{2}{\bf I}_{2})^{-1}$;

16: ${\bf G}_{2}^{(k+1)}={\bf G}_{2}^{(k)}+\mu_{2}({\bf A}^{(k+1)}-{\bf
D}^{(k+1)})$;

17: $\mu_{2}={\rm min}(\mu_{max},\mu_{2}\times\gamma)$;

18: $k=k+1$;

19:end while

20:Output: ${\bf A}^{(k)}$.

###  2.2 LRB-GLR

To depict the spatial similarity between neighboring pixels, a weighted graph
$\mathcal{G}=\\{{\bf V},{\bf R},{\bf W}\\}$ is adopted, where ${\bf V}$, ${\bf
R}$, and ${\bf W}$ represent the vertex set, edge set, and weight matrix,
respectively. To preserve similarity while ignoring dissimilarity, we simply
define ${\bf W}$ as the normalized distance using a threshold: ${\bf
W}_{i,j}=\left\\{\begin{aligned} &1,\;\|x_{i}-x_{j}\|_{2}^{2}<\sigma,\\\
&0,\;{\rm otherwise}\end{aligned}\right.$ where $x_{i}$ and $x_{j}$ are two
pixels in a given region, and $\sigma$ is the threshold.

The similarity in the original image space can be transferred to the feature
space, so the similarity between two coefficients can be expressed as

$\sum_{l=1}^{n_{l}}{{\rm Tr}({\bf S}_{l}{\bf L}_{l}{\bf
S}_{l}^{T})=}\frac{1}{2}\sum_{l=1}^{n_{l}}{\sum_{(i,j)\in\Omega_{l}}{\bf
W}_{l_{i,j}}\|s_{i}-s_{j}\|_{2}^{2}},$ (6)

where the whole image is divided into $n_{l}$ local regions via
$\omega\times\omega$ grid for efficient computation, $\Omega_{l}$ denotes the
$l$th region, ${\bf W}_{l}$ is the weight matrix of $\Omega_{l}$, $s_{i}$ and
$s_{j}$ are the encoding coefficients of $x_{i}$ and $x_{j}$ in $\Omega_{l}$,
${\rm Tr(\cdot)}$ is the trace of a matrix, and ${\bf L}_{l}$ is the graph
Laplacian matrix of $\Omega_{l}$, which is calculated by ${\bf L}_{l}={\bf
D}_{l}-{\bf W}_{l}$ where ${\bf D}_{l}$ is a diagonal matrix formed by the sum
of each row of ${\bf W}_{l}$.

Combining the local spatial similarity and sparse prior of ${\bf S}$, we can
get

$\min_{{\bf S}}{\frac{1}{2}\|{\bf X}-{\bf B}{\bf
S}\|_{F}^{2}}+\lambda_{3}\sum_{l=1}^{n_{l}}{{\rm Tr}({\bf S}_{l}{\bf
L}_{l}{\bf S}_{l}^{T})}+\lambda_{4}\|{\bf S}\|_{1},$ (7)

where the three terms model representation error, local spatial similarity,
and sparsity, respectively, and $\lambda_{3}$ and $\lambda_{4}$ are two trade-
off parameters.

The model (7) can be efficiently solved by ADMM. The companying augmented
Lagrangian function is

$\begin{split}{\mathcal{L}}_{3}&={\frac{1}{2}\|{\bf X}-{\bf B}{\bf
S}\|_{F}^{2}}+\lambda_{3}\sum_{l=1}^{n_{l}}{{\rm Tr}({\bf V}_{1_{l}}{\bf
L}_{l}{\bf V}_{1_{l}}^{T})}+\lambda_{4}\|{\bf V}_{2}\|_{1}\\\
&+{\frac{\mu_{3}}{2}(\|{\bf S}-{\bf V}_{1}+\frac{{\bf
H}_{1}}{\mu_{2}}\|_{F}^{2}+\|{\bf S}-{\bf V}_{2}+\frac{{\bf
H}_{2}}{\mu_{2}}\|_{F}^{2})},\end{split}$ (8)

where ${\bf H}_{1}$ and ${\bf H}_{2}$ are two Lagrangian multipliers, and
$\mu_{3}$ is a regularization parameter. The solver of the model is summarized
in Algorithm 2.

Algorithm 2 Optimization procedure of LRB-GLR

1:Input: $\bf X$, $\bf t$, $\bf A$, $\bf L$, $\lambda_{3}$, $\lambda_{4}$.

2:Initialize: ${\bf B}=[{\bf A},{\bf t}]$, ${\bf S}^{(0)}={\bf
V}_{1}^{(0)}={\bf V}_{2}^{(0)}={\bf H}_{1}^{(0)}={\bf H}_{2}^{(0)}={\bf 0}$,
$\mu_{3}=10^{-3}$, $\mu_{max}=10^{10}$, $\gamma=1.2$, $\epsilon=10^{-6}$,
$k=0$, $k_{max}=200$.

3:while $\|{\bf S}-{\bf V}_{1}\|_{F}+\|{\bf S}-{\bf V}_{2}\|_{F}\geq\epsilon$
and $k<k_{max}$ do

4: ${\bf S}^{(k+1)}=({\bf B}^{T}{\bf B}+2\mu_{3}{\bf I}_{3})^{-1}$

5: $({\bf B}^{T}{\bf X}+\mu_{3}{\bf V}_{1}^{(k)}-{\bf H}_{1}^{(k)}+\mu_{3}{\bf
V}_{2}^{(k)}-{\bf H}_{2}^{(k)})$;

6: for $l=1$ to $n_{l}$ do

7: ${\bf V}_{1_{l}}^{(k+1)}=(\mu_{3}{\bf S}_{l}^{(k+1)}+{\bf
H}_{1_{l}}^{(k)})(2\lambda_{3}{\bf L}_{l}+\mu_{3}{\bf I}_{4})^{-1}$;

8: end for

9: ${\bf V}_{2}^{(k+1)}={\rm soft}({\bf S}^{(k+1)}+{\bf
H}_{2}^{(k)}/\mu_{3},\lambda_{4}/\mu_{3})$;

10: ${\bf H}_{1}^{(k+1)}={\bf H}_{1}^{(k)}+\mu_{3}({\bf S}^{(k+1)}-{\bf
V}_{1}^{(k+1)})$;

11: ${\bf H}_{2}^{(k+1)}={\bf H}_{2}^{(k)}+\mu_{3}({\bf S}^{(k+1)}-{\bf
V}_{2}^{(k+1)})$;

12: $\mu_{3}={\rm min}(\mu_{max},\mu_{3}\times\gamma)$;

13: $k=k+1$;

14:end while

15:Output: ${\bf S}^{(k)}$.

###  2.3 Detection

For binary hypothesis testing, if the target is absent, the pixel can be
represented by the background subspace alone ($H_{0}$), otherwise by the joint
subspace ($H_{1}$). Therefore, the detection result can be obtained by
computing the ratio of representation errors:

$d_{i}=\frac{\|{(\bf X}-{\bf A}{\bf S}_{1})_{:,i}\|_{2}^{2}}{\|{(\bf X}-{\bf
B}{\bf S})_{:,i}\|_{2}^{2}},$ (9)

where $d_{i}$ denotes the detection score of the $i$-th pixel in the image,
and $\|\cdot\|_{2}$ is the L2-norm of vectors. For simplicity, $H_{0}$ is
modeled using least squares and the closed-form solution is ${\bf S}_{1}=({\bf
A}^{T}{\bf A})^{-1}{\bf A}^{T}{\bf X}$ while $H_{1}$ is modeled using LRB-GLR.

Table 1: Quantitative results and running time (in seconds) of competing methods. Bold highlights the best result while underlined the second. |  | SAM | OSP | CSCR | DM-BDL | DSC | Ours
---|---|---|---|---|---|---|---
San Diego I | AUC | 0.9944 | 0.9964 | 0.9986 | 0.9954 | 0.9994 | 0.9983
Time | 0.01 | 0.07 | 21.01 | 4.83 | 40.90 | 5.71
San Diego II | AUC | 0.9945 | 0.9821 | 0.9943 | 0.9855 | 0.9952 | 0.9971
Time | 0.02 | 0.12 | 53.12 | 2.43 | 176.69 | 5.46
Fig. 1: Effect of parameter $K$ on the detection performance.

##  3 Experiments

Two benchmark datasets, San Diego I and San Diego II, are used to evaluate the
proposed approach. They were collected using the Airborne Visible/Infrared
Imaging Spectrometer and consist of $100\times 100$ pixels. After removing
water-absorption bands, the datasets contain 189 bands. The targets to be
detected are three airplanes, with 58 target pixels and 134 target pixels in
each dataset. For simplicity, the average spectrum of all target pixels in
each dataset is selected as the target spectrum.

The receiver operating characteristic (ROC) curve and area under the curve
(AUC) are used to evaluate the detection performance. In our experiments, we
empirically set $\sigma=0.3$, $\lambda_{1}=\lambda_{2}=10^{-4}$, and
$\lambda_{3}=\lambda_{4}=1$ for the two datasets. By analyzing the impact of
parameter $K$ in Fig. 1, we set $K$ as 12 and 10 for the two datasets,
respectively.

Fig. 2: ROC curves of competing methods. Left: San Diego I. Right: San Diego
II.

Fig. 3: Detection maps of competing methods. First two rows: San Diego I. Last
two rows: San Diego II. From left(top) to right (bottom): false-color image,
SAM, OSP, CSCR, DM-BDL, DSC, Ours, ground truth.

For comparison, five competing methods are selected, including SAM, OSP[2],
CSCR [8], DM-BDL[7], and DSC[9]. Table 1 presents the quantitative results,
including AUC and time. Combining detection effectiveness and efficiency, it
is observed that our method can achieve satisfactory and robust performance on
both datasets. In addition, Figures 2 and 3 display the ROC curves and the
final detection maps. It can be found that our method can effectively separate
the background and targets and exhibits a promising performance in background
suppression.

##  4 Conclusion

This paper presents a fully optimization-based approach for HTD. The proposed
approach encompasses a background subspace learning model based on sparse and
low-rank representation, enabling the acquisition of a complete and pure
background dictionary. Additionally, a model leveraging GLR is introduced to
capture the local spatial similarity of coefficients, enabling the employment
of spatial-spectral features. By computing representation error ratios through
binary hypothesis testing, the desired detection results are obtained. The
experimental evaluation of two benchmark datasets validates the effectiveness
and superiority of the proposed approach.

## References

  * [1] Ajay Kaul et al.,  “Hyperspectral imaging and target detection algorithms: a review,”  Multimedia Tools and Applications, pp. 1–66, 2022.
  * [2] Chein-I Chang,  “Orthogonal subspace projection (osp) revisited: A comprehensive study and analysis,”  IEEE transactions on geoscience and remote sensing, vol. 43, no. 3, pp. 502–518, 2005.
  * [3] Xiaoyi Wang, Liguo Wang, Hao Wu, Jiawen Wang, Kaipeng Sun, Anqi Lin, and Qunming Wang,  “A double dictionary-based nonlinear representation model for hyperspectral subpixel target detection,”  IEEE Transactions on Geoscience and Remote Sensing, vol. 60, pp. 1–16, 2022.
  * [4] Yang Xu, Zebin Wu, Jun Li, Antonio Plaza, and Zhihui Wei,  “Anomaly detection in hyperspectral images based on low-rank and sparse representation,”  IEEE Transactions on Geoscience and Remote Sensing, vol. 54, no. 4, pp. 1990–2000, 2015.
  * [5] Yanzi Shi, Jiaojiao Li, Yunsong Li, and Paolo Gamba,  “Hyperspectral target detection using a bilinear sparse binary hypothesis model,”  IEEE Transactions on Geoscience and Remote Sensing, vol. 60, pp. 1–13, 2021.
  * [6] Shuo Yang and Zhenwei Shi,  “Hyperspectral image target detection improvement based on total variation,”  IEEE Transactions on Image Processing, vol. 25, no. 5, pp. 2249–2258, 2016.
  * [7] Tongkai Cheng and Bin Wang,  “Decomposition model with background dictionary learning for hyperspectral target detection,”  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 14, pp. 1872–1884, 2021.
  * [8] Wei Li, Qian Du, and Bing Zhang,  “Combined sparse and collaborative representation for hyperspectral target detection,”  Pattern Recognition, vol. 48, no. 12, pp. 3904–3916, 2015.
  * [9] Dunbin Shen, Xiaorui Ma, Hongyu Wang, and Jianjun Liu,  “A dual sparsity constrained approach for hyperspectral target detection,”  in IGARSS 2022-2022 IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2022, pp. 1963–1966.