Signal Processing - January 2017 - 53

number of pixels being reconstructed. Given these measurements, an image is recovered by searching for the image that
is sparsest in some transform basis (wavelets, DCT, or other)
while being consistent with the measurements.
In essence, CS provides a framework to sense signals with
far fewer measurements than their ambient dimensionality (i.e.,
Nyquist rate), which translates to practical benefits including
decreased sensor cost, bandwidth, and time of acquisition. These
benefits are most compelling for imaging modalities where sensing is expensive; examples include imaging in the nonvisible
spectrum (where sensors are costly), imaging at high spatial and
temporal resolutions (where the high bandwidth of sensed data
requires costly electronics), and medical imaging (where the time
of acquisition translates to costs or where existing equipment is
too slow to acquire certain dynamic events). In this context, architectures like the single-pixel camera (SPC) [27] provide a promising proof of concept that still images can be acquired using a
small number of coded measurements with inexpensive sensors.
There are numerous applications where it is desirable to
extend the CS imaging framework beyond still images to incorporate video. After all, motion is ubiquitous in the real world,
and capturing the dynamics of a scene requires us to go beyond
static images. A hidden benefit of video is that it offers tremendous opportunities for more dramatic undersampling (the ratio
of signal dimensionality to measurement dimensionality). That

is, we can exploit the rich temporal redundancies in a video to
reconstruct frames from far fewer measurements than is possible with still images. Yet the demands of video CS in terms
of the complexity of imaging architectures, signal models, and
reconstruction algorithms are significantly greater than those of
compressive still-frame imaging.
There are three major reasons that the design and implementation of CS video systems are significantly more difficult
than those of CS still-imaging systems. The first challenge is
the gap between compression and CS. State-of-the-art video
models rely on two powerful ideas: first, motion fields enable
the accurate prediction of image frames by propagating intensities across frames; second, motion fields are inherently more
compressible than the video itself. This observation has led
to today's state-of-the-art video compression algorithms (not
to be confused with CS of videos) that exploit motion information in one of many ways, including block-based motion
estimation (MPEG-1), per-pixel optical flow (H.265), and
wavelet lifting (LIMAT). Motion fields enable models that
can be tuned to the specific video that is being sensed/processed. This is a powerful premise that typically provides an
order of magnitude improvement in video compression over
image compression.
The use of motion fields for video CS raises an important
challenge. Unlike the standard video compression problem,

What Is the Nyquist Rate of a Video Signal?
Conventional videos, sampled at 24-60 frames/second
(fps), may, in fact, be highly undersampled in time-
objects in the scene can move multiple pixels between
adjacent frames. Some compressive sensing (CS) architectures, however, measure a video at a much higher temporal rate. For example, the single-pixel camera (SPC) may
take tens of thousands of serial measurements per second.
In such cases, the scene may change very little between
adjacent measurements. This raises some interesting questions: what is the Nyquist rate of a video signal, and how
does it compare to CS measurement rates?
One can gain insight into these questions by considering
the three-dimensional analog video signal that arrives at a
camera lens; both conventional and CS imaging systems
can be viewed as blurring this signal spatially (due to the
optics and the pixelated sensors) and sampling or measuring
it digitally. If a video consists of moving objects with sharp
edges, then the analog video will actually have infinite bandwidth in both the spatial and temporal dimensions. However,
it can be argued that the support of the video's spectrum will
tend to be localized into a certain bowtie shape, as shown
in blue in Figure S1. The salient feature of this shape is that
high temporal frequencies coincide only with high spatial
frequencies. Thus, because of the limited spatial resolution of

Temporal Frequency
Spectral Support
of Analog Video
Spatial Frequency

Temporal
Bandwidth
of Sampled
Video
Spatial
Resolution
of Optics

FIGURE S1. The limited spatial resolution of an imaging system may
also limit its temporal bandwidth.
both the camera optics and the pixel sensors, when the spatial bandwidth of the video is limited, so too is its temporal
bandwidth, as illustrated by the black rectangle in the figure.
This suggests that the video sensed by architectures such as
the SPC may in fact have a finite temporal bandwidth, and
this fact can be used to reduce the computational complexity
of sensing and reconstructing the video. In particular, it is not
necessary to reconstruct at a rate of thousands of fps.
Additional details are provided in [62].

IEEE SIgnal ProcESSIng MagazInE

January 2017

Table of Contents for the Digital Edition of Signal Processing - January 2017