Fundamentals of Computer Graphics, 3rd Edition

i

i

i

i

i

i

i

i

9

Signal Processing

In graphics, we often deal with functions of a continuous variable: an image is

the first example you have seen, but you will encounter many more as you con-

tinue your exploration of graphics. By their nature continuous functions can’t be

directly represented in a computer; we have to somehow represent them using

a finite number of bits. One of the most useful approaches to representing con-

tinuous functions is to use samples of the function: just store the values of the

function at many different points and reconstruct the values in between when and

if they are needed.

You are by now familiar with the idea of representing an image using a two-

dimensional grid of pixels—so you have already seen a sampled representation!

Think of an image captured by a digital camera: the actual image of the scene that

was formed by the camera’s lens is a continuous function of the position on the

image plane, and the camera converted that function into a two-dimensional grid

of samples. Mathematically, the camera converted a function of type R

2

→ C

(where C is the set of colors) to a two-dimensional array of color samples, or a

function of type Z

2

→ C.

Another example of a sampled representation is a 2D digitizing tablet such

as the screen of a tablet computer or PDA. In this case the original function is

the motion of the stylus, which is a time-varying 2D position, or a function of

type R → R

2

. The digitizer measures the position of the stylus at many points in

time, resulting in a sequence of 2D coordinates, or a function of type Z → R

2

.A

185

i

i

i

i

i

i

i

i

186 9. Signal Processing

motion capture system does exactly the same thing for a special marker attached

to an actor’s body: it takes the 3D position of the marker over time (R → R

3

)and

makes it into a series of instantaneous position measurements (Z → R

3

).

Going up in dimension, a medical CT scanner, used to non-invasivelyexamine

the interior of a person’s body, measures density as a function of position inside

the body. The output of the scanner is a 3D grid of density values: it converts the

density of the body (R

3

→ R) to a 3D array of real numbers (Z

3

→ R).

These examples seem different, but in fact they can all be handled using ex-

actly the same mathematics. In all cases a function is being sampled at the points

of a lattice in one or more dimensions, and in all cases we need to be able to

reconstruct that original continuous function from the array of samples.

From the example of a 2D image, it may seem that the pixels are enough,

and we never need to think about continuous functions again once the camera has

discretized the image. But what if we want to make the image larger or smaller on

the screen, particularly by non-integer scale factors? It turns out that the simplest

algorithms to do this perform badly, introducing obvious visual artifacts known

as aliasing. Explaining why aliasing happens and understanding how to prevent it

requires the mathematics of sampling theory. The resulting algorithms are rather

simple, but the reasoning behind them, and the details of making them perform

well, can be subtle.

Representing continuous functions in a computer is, of course, not unique to

graphics; nor is the idea of sampling and reconstruction. Sampled representations

are used in applications from digital audio to computational physics, and graphics

is just one (and by no means the first) user of the related algorithms and mathe-

matics. The fundamental facts about how to do sampling and reconstruction have

been known in the field of communications since the 1920s and were stated in

exactly the form we use them by the 1940s (Shannon & Weaver, 1964).

This chapter starts by summarizing sampling and reconstruction using the

concrete one-dimensional example of digital audio. Then we go on to present

the basic mathematics and algorithms that underlie sampling and reconstruction

in one and two dimensions. Finally we go into the details of the frequency-domain

viewpoint, which provides many insights into the behavior of these algorithms.

9.1 Digital Audio: Sampling in 1D

Although sampled representations had already been in use for years in telecom-

munications, the introduction of the compact disc in 1982, following the increased

use of digital recording for audio in the previous decade, was the first highly vis-

ible consumer application of sampling.