Signal Processing - September 2016 - 88

estimate of the scene motion. The motion estimate can then
(UU) @ amplifies all three sources of errors in (6), eventually
be used to recover the video at its full resolution. In addition,
resulting in a poor estimate. For virtually all sensing matrices
the use of fast DSS matrices can be beneficial in various other
U commonly used in CS, such as i.i.d. (sub)Gaussian matriways, including as a digital viewfinder.
ces, right multiplying them with an upsampling operator U
often results in an ill-conditioned matrix or even a rank-deficient matrix. This is a consequence of the smallest singular
Motion flow-based video CS
value of square random matrices approaching zero when the
State-of-the-art video compression methods rely on estimatsize of the matrix is large [34].
ing the motion in the scene, compress a few reference frames,
A novel class of sensing matrices, referred to as DSS matriand use the motion vectors that relate the remaining parts of a
ces, achieve good CS recovery performance and have miniscene to these reference frames. While this approach is possimum noise enhancement when computing
ble in the context of video compression, i.e.,
a low-resolution preview V
where the algorithm has prior access to the
b L according to
Hadamard matrices have
entire video, it is significantly more difficult
(6). These matrices will satisfy the RIP to
fast inverse transforms
in the context of CS.
enable CS and remain well-conditioned
A general strategy to enable the use
that can significantly
when right multiplied by a given up-samof
motion
flow-based video CS is to use a
pling operator U. One approach to the
speed up the recovery
two-step
approach
[28]. In the first step, an
design of DSS matrices U (see Figure 4)
of the low-resolution
initial estimate of the video is generated by
relies on upsampling low-resolution Hadpreview frames.
recovering each frame individually using
amard matrices. A simple way is to start
sparse wavelet or gradient priors. The initial
with a W # W Hadamard matrix H and
estimate is used to derive motion flow between consecutive
to write the CS matrix as U = HD + F, where F ! R W # N is a
frames, which enables a powerful description in terms of relat!1 matrix such that FU = 0, i.e., each block of F should sum
ing similar intensities at pixels across frames. In the second
to zero. A powerful example of such a construction is the sostep, the video is re-estimated with the aid of enforcing the
called sum-to-one transform [15], where a Hadamard matrix
extracted motion-flow constraints in addition to the measureis carefully designed to satisfy the dual scale property across
ment constraints. The success of this two-step strategy critiany pairs of scales.
cally depends on the ability to obtain reliable motion estimates,
which, in turn, depends on obtaining robust initial estimates.
Preview mode
Further, since we are upsampling the motion estimates, this
The use of Hadamard matrices for the low-resolution part in
approach only works for scenes where the moving objects
the proposed DSS matrices has an additional benefit. Hadoccupy a few pixels in the low-resolution preview. We can
amard matrices have fast inverse transforms that can signifiobtain such robust initial estimates by using the DSS matrices.
cantly speed up the recovery of the low-resolution preview
Figure 5 illustrates the outline of a video CS algorithm [31]
frames. Such a fast DSS matrix has the key capability of genthat uses the DSS matrices to enable robust previews, compute
erating a high-quality preview of the scene (see Figure 4) with
motion flow using the previews, and exploit the motion flow to
very low computational complexity. This is beneficial for
sense videos at high compressions.
video CS as it allows one to easily and quickly extract an

Windmill

High-Frequency
Sparse Pattern
Row of the
Hadamard Matrix

Pendulum
Row of the
DSS Matrix

Upsampling (NN)

Hand
Process of Generating Rows of DSS Matrices

Previews of Three Scenes

Figure 4. Generating DSS patterns and previews. DSS matrices are generated such that downsampling each row produces a row of a low-resolution
Hadamard matrix. Also shown are previews generated for three different scenes with real data. (Figure adapted from [31].)
88

IEEE SIgnal ProcESSIng MagazInE

September 2016

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