Signal Processing - September 2016 - 86

in (4), then we must choose A = H 12·2 10 so that A 7 SRB {B}
is N # N. Suppose that we completely sample the four lowest
sequency blocks associated with the signature tiles outlined in
the red-dashed line in Figure 1. The low-resolution previews of
the scene filtered through these signature tiles can be seen in
Figure 1. These signature previews reveal that the buildings in
the observed city skyline have strong vertical and horizontal
components. In general, any a priori information will dictate
which SRBs to focus on.
Returning to the goal of CI, we selected modes from each
of the 64 SRBs of the 2-D Hadamard domain such that the
total number of measurements M was 15% of N, as shown
in Figure 2(a). Besides the four completely sampled SRBs,
the other 60 SRBs were partially sampled at random with
a canonical variable density described in [21]. Most natural scenes have their energy focused in the lower sequency
modes, so we sampled more densely in these SRBs. Note
that the measurements had additive white Gaussian noise
with an SNR of 30 dB. We used these measurements in
conjunction with a reconstruction algorithm that minimized the total variation (TV) that resulted in the recovered image seen in Figure 2(b). Compared to the ground
truth in Figure 1, good detail can be seen even though only
15% of the possible Hadamard modes were used to observe

the scene. Furthermore, the algorithm converged in just
13 iterations. This approach has some similarity to hybrid
sampling methods that gather low-frequency measurements, followed by higher-frequency detail measurements.
A somewhat related strategy is to assemble a union of bases
consisting of chirp or Reed-Muller sequences as the sensing matrix [27].
Next, we examine how our structured SRB sensing matrix
compares with a typical CI sensing matrix. We used the same
2-D Hadamard domain, but the sensing modes were chosen
uniformly at random, again such that M/N = 15% as seen in
Figure 2(d). Note that sensing in this manner usually results in
extremely poor reconstructions. We ameliorated this by scrambling each of the Hadamard patterns before sensing so that they
appeared as binary noise. (In this sense, the comparison with the
SRB method is not exact but is the most fair.) As before, white
Gaussian noise was added to the measurements such that the
SNR was 30 dB. However, now the TV-minimization algorithm
required 88 iterations to converge to the solution in Figure 2(e).
Compared to Figure 2(b), we see that the SRB technique produces a slightly sharper image and does so in more than six-fold
fewer iterations, which is a significant improvement. In addition,
the SRB technique, by providing low-resolution signature previews, demonstrates how intelligent sampling of the transform
domain can offer simultaneous supplementary information.
Although the Hadamard coefficients
CI Using Signature Row Block Sampling
with the highest energy tend to be concentrated in the lowest-sequency blocks,
this is not always the case. Further, a
canonical variable density strategy is not
always ideal. It is possible to use the SRB
structure to find out which are the best
blocks to sense as well as what the ideal
subsampling density is for each block
[21]. By simply subsampling just a few
(a)
(b)
(c)
Hadamard modes (e.g., much less than
1%) from each SRB, we can assemble
CI Using Random Sampling
a sufficient statistic that can guide us to
the blocks with the most energy, which
should have the best SNR. Hence, we
can adapt to an observed scene by doing
a fast initial query of the transform measurement domain and thereby get the
most bang for the buck.
Overall, we see that the SRB Kro(d)
(e)
(f)
necker product provides a structure that
enables flexible sensing strategies. By
properly designing the matrix and choosFigure 2. (a) The 2-D Hadamard domain partitioned by 64 SRBs (the 8 × 8 sequency patterns unique
ing which SRBs to use, important local
to each block are shown in Figure 1). The white dots indicate which Hadamard modes were used to
information can be gleaned from the
observe the ground truth in Figure 1. The number of white dots equals M, the number of samples,
such that M/N = 15% . (b) The resulting reconstructed image using TV minimization with insets shown global measurements of an observed
in (c). Note how, in spite of the high compression, certain signatures like horizontal and vertical stripes
scene. The previous example shows how
are well preserved. (d) The 2-D Hadamard domain uniformly sampled at random as is done in typical
it can be used for imaging in a CS manCS. (e) The resulting reconstructed image using the same TV minimization with insets shown in (f).
ner as well as in providing low-resolution
The quality is slightly degraded and took more than six times as long to converge. (Figure courtesy
signature previews. However, the SRB
of www.dpreview.com.)
86

IEEE SIgnal ProcESSIng MagazInE

September 2016

http://www.dpreview.com

Table of Contents for the Digital Edition of Signal Processing - September 2016