Image and Video Compression

157

8

Compressive Sensing

8.1 Introduction

Compressed or compressive sensing (CS) is a mathematical theory of mea-

suring and retaining the most important part of the signal while sensing it.

It effectively performs dimensionality reduction of a signal in a linear man-

ner. It is one of the most exciting domains of modern times, and there is a

deluge of papers and research outcomes available to the researcher. It has

opened up new application vistas in the domains of computer science, elec-

trical engineering, applied mathematics, remote sensing, medical imaging,

communication, pattern recognition, and many more. Compressive sensing

is an interdisciplinary eld and draws its power from linear algebra, statis-

tics and random processes, signal processing, optimization, communication

theory, and space theory. This chapter is aimed at both the theorists and the

practitioners. It will be a review for novice practitioners who would be inter-

ested in peeping through the domain, and also act as a quick reference to the

theorist. This chapter will focus on the nite dimensional sparse signals and

will provide an overview of the basic theory underlying the ideas of com-

pressive sensing. Later in the chapter, we will discuss application based on

the compressive sensing theory covered in the former part. We will develop

a fragile domain watermarking application using CS. And nally, we present

a further line of investigation in this domain: exploiting signal and measure-

ment structure (i.e., use prior knowledge about the signal or physical process

to be sensed for further reduction in the sampling rate). For more tangible

discussions and simplicity, limited dimensional noncomplex signals are cov-

ered in this chapter.

8.2 Motivation for Compressive Sensing

This author has an eternal question in mind: Are the days of analog signal

processing over? This question has arisen due to the digital revolution we

are going through. Every walk of human as well as animal life has been

158 Image and Video Compression

touched by this revolution. Modern digital gadgets used by today’s toddlers

were only imagined in science ction half a century ago. But, thankfully the

consumer of this information to a very large extent remains Homo sapiens.

Humans consume and deliver analog information (think of a person com-

municating emotions using numbers instead of a language like Hindi). Thus,

a need for analog information and processing is going to prevail until the

time when human and machine are alike. At the same time, the digital revo-

lution is improving all walks of life. This essentially means that for getting

a digital advantage, analog information is converted to the digital domain for

processing and then converted back to the analog domain for human con-

sumption. This human-centric conversion process is depicted in Figure8.1.

The digitization is realized by exploiting the limits of human perception.

But it is capable of providing nearly natural like signals to the human senses.

With the advancement of these technologies, the gap between real signals

and its digitally synthesized variants is minimizing. The terms hi- (high

delity), stereophonic, true pictures, and HDTV (high-denition television) are

now a part of daily life. Music players synthesize pure acoustics and three-

dimensional (3D) TVs are capable of producing real-like pictures. Billions

of bits are buzzing and running around us to make our life simpler and more

exciting. As seen in Figure8.1, the heart of this conversion process is analog-

to-digital converters (ADCs) and digital-to-analog converters (DACs) . ADCs

form the front end and convert the analog real-world signal into the streams

of bits. These bits are then processed in the digital domain using software

algorithms running on digital signal processors. ADCs have to deal with a

wide range of analog input signals, and they have to sample these input sig-

nals. These samples are spaced in time and thus signal information between

them is lost. The sampling rate has to be fast enough so that an analog signal

can be regenerated from these samples. How fast this sampling rate should

be is answered by the fundamental Shannon-Whitakker-Nyquist theorem

(Shannon 1949).

Theorem 8.1 (Shannon 1949): An analog signal whose frequency is band

limited to B Hz, can be completely recovered from its samples which are

spaced at

B

1

2

seconds (secs) apart.

Analog

DAC

ADC

DSP

DigitalDigital

Analo

g

FIGURE 8.1

Analog-to-digital (ADC)–digital signal processing (DSP)–digital-to-analog (DAC) process.

The text below the arrows indicates the domain of information processing.