Signal Processing - September 2016 - 85

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.2
0.1
0
-0.1
-0.2
(a)

(b)

0.2
0.1
0
-0.1
-0.2
0.1
0.05
0
-0.05
-0.1

(c)

Figure 1. (a) 8 × 8 signature tiles (2-D sequency patterns) corresponding to the 64 SRBs that partition the Hadamard domain. (b) A 768 × 1024 ground
truth scene. (c) Four low-resolution 96 × 128 signature previews from the four lowest-sequency blocks [marked in red in (a)], which all have 100%
complete sampling. (Figure courtesy of www.dpreview.com.)

observed scene, or it could be a standard unitary matrix such
as the DCT.
The SRB Kronecker product (4) can easily be obtained from
either of the typical Kronecker products A 7 B or B 7 A.
That is, there exist permutation matrices P and Q such that
A 7 SRB {B} = P (A 7 B) = (B 7 A) Q. This is significant
because, if observations of a scene with the rows of an SRB
Kronecker product matrix are collected, the typical Kronecker
product and its inverse can be used (and their fast implementations, if they exist) for global processing of the whole image.
Yet, at the same time, the SRB structure lets us group measurements according to the local signatures, which has value since
it is the local information that contains details such as edges,
textures, or anomalies within a signal/scene of interest. This
enables properties such as the ability to view the data either
within the context of particular SRBs or within the context of
the larger transform space, analyze or solve an imaging/inference problem as L separate smaller problems or as one large
problem, assess the SNR of a particular SRB's coefficients and/
or determine optimal bit allocation, quickly generate downsampled previews of the scene filtered through each signature,
and subsample within certain SRBs, e.g., in CI applications.
The last two items are examined in the next section.

Using signature row-block Kronecker products for CI
It is easy to extend the SRB Kronecker product (4) to 2-D
imaging applications. In this case, the SRB structure naturally endows the measurement space with a convenient 2-D partitioning now based on local signature tiles, instead of the
one-dimensional signature rows discussed previously. For
computational imaging, the rows of a Hadamard matrix can
be reshaped into the 2-D spatial modulating waveforms used,
e.g., on the digital micromirror device (DMD) used in the
SPC. In this application, each element of a given row is
mapped to one mirror of the DMD, and the !1 values determines whether it is in an ON or OFF state. Hadamard matrices have been used extensively as sensing matrices in CI since
they have been shown to be incoherent to sparse signals. Further, the fast implementation of many Hadamard transforms

means that the reconstruction algorithms can quickly converge to a solution. Many CI applications also apply a scrambling operation to the Hadamard matrix, e.g., randomly
permuting the columns. This breaks up the structure and
results in pseudorandom binary patterns that can be beneficial
in certain situations. However, this is different than the
approach taken here.
At the same time, Hadamard patterns can be used in a more
traditional transform coding/decoding manner. Power-of-two
Hadamard transforms have good energy compaction properties, similar to the DCT. We can utilize this fact in conjunction with the partitioned block structure provided by the SRB
Kronecker product. Now, with A as a Hadamard matrix, each
individual SRB B j in (4) is an orthogonal basis for a subspace
encoded or filtered by the signature b j . Further, with B also
as a Hadamard matrix, the set of SRBs {B j} are orthogonal to
each other. With B specifically as a power-of-four Hadamard
matrix H 4 n, for some n, the signatures will span all possible
sequencies when observing 2 n # 2 n patches of pixels, which
is similar to the range of spatial frequencies in the 2-D DCT.
For example, if matrix B is a Walsh-Hadamard matrix H 64 in
(4), the measurement space is divided into 64 SRBs associated
with the 2-D signature 8 # 8 tiles shown in Figure 1. Each of
these signature tiles correspond to one row of H 64 that has been
reshaped to 2-D.
The SRB structure of the deterministic sensing matrix
A 7 SRB {B} lends itself to selective and model-based sampling strategies. We are free to choose which SRBs we want
to sample from, and we can choose to sample them partially or completely. This leads to a partial-complete sensing
approach [20] that is essentially a block-structured version
of variable density sampling. Note that SRBs that are completely sampled at 100% can be easily and quickly demodulated by removing the multiplexing effect of matrix A (more
details can be found in [19]). This provides a low-resolution
preview of the scene filtered through the signature tile associated with a particular SRB. To see this, consider the scene
with N = 768 # 1024 = 12·2 16 pixels shown Figure 1. If we
want to construct an SRB Kronecker matrix with B = H 64

IEEE SIgnal ProcESSIng MagazInE

September 2016

http://www.dpreview.com

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