IEEE Geoscience and Remote Sensing Magazine - June 2016 - 84

[61] has become very popular due to its simplicity and efficiency. For a given X, the K-SVD algorithm seeks to solve
the following optimization problem:
min
X - DZ
D, Z

(a)

(b)

(c)
figure 5. Cloud and sky segmentation via learning OCTOBOS
sparse representation: (a) the original image, (b) the input image
with original pixels clustered as cloud and green pixels clustered as
sky, and (c) the learned two-class OCTOBOS with each row visualized as patches in separate blocks.

Several models for sparsity have been proposed in
recent years, with the most popular being the synthesis
model [61], which suggests that a set of data X can be modeled by a common matrix D ! R N # K and their respective
sparse codes Z:
X = DZ, s.t. z i

# s % K 6i,

(8)

where . 0 counts the number of nonzeros, which is upper bounded by the sparsity level s. The codes " z i ,ni = 1 are
sparse, meaning that the maximum number of nonzeros
s is much smaller than the code dimensionality K. The
matrix D = 6d 1 | d 2 | ... | d K@ is the synthesis dictionary,
with each dj called an atom. This formulation implies that
each xi can be decomposed as a linear combination of
only s atoms. For a particular xi, the selected s atoms also
form its basis. In other words, data that satisfies such a
sparse model live in a union of subspaces spanned by
only a small number of selected atoms of D due to sparsity. The generalized synthesis model allows for small
modeling errors in the data space, which is normally
more practical [58], [61].
Given data X, finding the optimal dictionary is well
known as the synthesis dictionary learning problem. Since
the problem is normally nonconvex, and finding the exact
solution is nondeterministic polynomial-time (NP)-hard,
various approximate methods have been proposed and
have demonstrated good empirical performance. Among
those, the K-singular value decomposition (SVD) algorithm
86

2
F

s.t. z i

# s 6 i, d j

= 16 j,

(9)

where X - DZ 2F represents the modeling error in the original data domain. To solve this joint minimization problem,
the algorithm alternates between sparse coding (solving for
Z, with fixed D) and dictionary update (solving for D, with
fixed Z) steps. K-SVD adopts orthogonal matching pursuit
[65] for sparse coding and updates the dictionary atoms sequentially, while fixing the support of the corresponding Z
component by using SVD.
Besides the synthesis dictionary learning, there are
learning algorithms associated with other models, such as
transform learning [66]. Unlike synthesis dictionary learning, which is normally sensitive to initialization, the transform learning scheme generalizes the use of conventional
analytical transforms, such as DCT or wavelets, to a regularized adaptive transform W as follows:
min
WX - Z
W, Z

2
F

+ o (W) s.t. z i

# s6i,

(10)

where WX - Z 2F denotes the modeling error in the adaptive transform domain. Function o ^ . h is the regularizer
for W [66] to prevent trivial and badly conditioned solutions. The corresponding algorithm [62], [66] provides exact sparse coding and a closed-form transform update with
lower complexity and faster convergence, compared to the
popular K-SVD.
In sparse representation, the sparse codes are commonly
used as features for various tasks such as image reconstruction and denoising. More sophisticated learning formulations also include the learned models (i.e., dictionaries or
transforms) as features for applications such as segmentation and classification. Figure 5 provides a simple cloud/
sky image segmentation example using the overcomplete
sparsifying transform model with block cosparsity (OCTOBOS) [62], which learns a union of sparsifying transforms, to illustrate and visualize the usefulness of sparse
features. We extract 9 # 9 overlapping image patches from
the ground-based sky image shown in Figure 5(a). The color
patches are converted to gray scale and vectorized to form
the 81-dimensional data vectors. The OCTOBOS algorithm
simultaneously learns a union of two transforms, generates the sparse codes, and clusters the image patches into
two classes (i.e., sky class and cloud class) by comparing
the modeling errors [67]. Since the overlapping patches are
used, each pixel in the image typically belongs to multiple
extracted patches. We cluster a pixel into a particular class
by majority voting. The image segmentation result, with
pixels belonging to the sky class, is visualized in Figure 5(b).
In the learning stage, we restrict the sparsity of each vector to be, at most, ten out of 81. The distinct sparsifiers, or
rows of learned OCTOBOS, are visualized as 9 # 9 patches
ieee Geoscience and remote sensing magazine

june 2016

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - June 2016