PRELIMINARIES 2.1 FUNDAMENTALS 21

In visual data, that same transition corresponds to the spectrum between blurred imagery

and images rich in visual detail. Note that high frequencies refer to wild intensity excur-

sions. This tends to correspond to visual detail like edges and texture in high contrast

images. High frequencies that are subjectively determined to add nothing to the informa-

tion content of the signal are usually referred to as noise. Since blurred images have

slowly varying intensity functions, they lack significant high frequency information. In

either case, music and images are time- and spatially-varying functions whose informa-

tion content is embedded in their frequency spectrum. The conversion between the spa-

tial and frequency domains is achieved by means of the Fourier transform.

We are familiar with other instances in which mathematical transforms are used to

simplify a solution to a problem. The logarithm is one instance of such a transform. It

simplifies problems requiring products and quotients by substituting addition for multi-

plication and subtraction for division. The only tradeoff is the accuracy and time neces-

sary to convert the operands into logarithms and then back again. Similar benefits and

drawbacks apply to the Fourier transform, a method introduced by the French physicist

Joseph Fourier nearly two centuries ago. He derived the method to transform signals

between the spatial (or time) domain and the frequency domain. As we shall see later,

using two representations for a signal is useful because some operations that are difficult

to execute in one domain are relatively easy to do in the other domain. In this manner,

the benefits of beth representations are exploited.

2.1.5.2. Fourier Transforms

Fourier transforms are central to the study of signal processing. They offer a

powerful set of analytical tools to analyze and proc$ss singi a0d multidimensional sig-

napd_syse_ms: The great impact thakEom'ier_tra snsfformsha_s_ha_d on sgnal proih

is dug:, in large part, to the fundamental understandiog ginned by exarmmng a sgnalTTom

 entirely different viewpoint7

We had earlier considered an arbitrary input function f (x) to be the sum of an

infinite number of impulses, each scaled and shiftdi'sish[ 'in  gr]lap ofitriagihfi-

ti /ou'i'scovered that an alternfi- u-n'lpo-sible: f (x)earr be tafffi

the sum of'hn 'ififihit'hurlr. o 'mus0idai x.' "f'hi 'rivvi(Jnt ]S'jSfiflable

bce ie 'eln}e o/5-ax linear, spae-invariant system to a complex exponential

(sinusoid) is another cmpllOx exponential of the same frequency but altered amplitude

and phase. DeLe`minrgtheptde-sand-phase-iftsfr`upd-`!s ).e.central

topic of F'ier analgi_S,.. Conversely, the act of adding these scaled and shi8'--

FtiaOiSqOdih-df'i':own a Fourier synthesis. Fourier analS,i and yfithesi'e

made possible by the Fourier transform pair:

where i =',/21-, and

F(u) = f f (x)e-i2WC dx (2.1.13)

f (x) = i F(u)e+ianUX du (2.1.14)

e i2nux = cos2gux _+ isin2gux (2.1.15)

is a succinct expression for a complex exponential at frequency u.

The definition of the Fourier transform, given in Eq. (2.1.13), is valid for any

integrable function f (x). It decomposes f (x) into a sum of complex exponentials. The

complex function F (u) specifies, for each frequency u, the amplitude and phase of each

complex exponential. F(u) is commonly known as the signal's frequency spectrum.

This should not be confused with the Fourier transform of a filter, which is called the fre-

quency response (for 1-D filters) or the modulation transfer function (for 2-D filters).

The frequency response of a filter is computed as the Fourier transform of its impulse

response.

It is important to realize that f (x) and F (u) are two different representations of the

same function. In particular, f(x) is the signal in the spatial domain and F(u) is its

counterpart in the frequency domain. One goes back and forth between these two

representations by means of the Fourier transform pair. The transformation from the fre-

quency domain back to the spatial domain is given by the inverse Fourier transform,

defined in Eq. (2.1.14).

Although f (x) may be any complex signal, we are generally interested in real func-

tions, i.e., standard color images. The Fourier transform of a real function is usually

complex. This is actually a clever encoding of the orthogonal basis set, which consists of

sine and cosine functions. Together, they specify the amplitude and phase of each fre-

quency component, i.e., a sine wave. Thus, we have F(u) defined as a complex function

of the form R (u) + i! (u), where R (u) and 1 (u) are the real and imaginary components,

respectively. The amplitude, or magnitude, of F (u) is defined as

[F (u) l = 5]R2(u) + 12(u) (2.1.16)

It is often referred to as the Fourier spectrum. This should not be mistaken with the

Fourier transform F(u), which is itself commonly known as the spectrum. In order to

avoid confusion, we shall refer to [F(u) l as the magnitude spectrum. The phase spec-

trum is given as

[I(u) ] (2.1.17)

½(u) = tan -1 [ R'J

This specifies the phase shift, or phase angle, for the complex exponential at each fre-

quency u.

PRELIMINARIES'>22 PRELIMINARIES

The Fourier transform of a signal is often plotted as magnitude versus frequency,

ignoring phase angle. This form of display has become conventional because the bulk of

the information relayed about a signal is embedded in its frequency content, as given by

the magnitude spectrum IF (u)[. For example, Figs. 2.5a and 2.5b show a square wave

and its spectrum, respectively. In this example, it just so happens that the phase function

(u) is zero for all u, with the spectrum being defined in terms of the following infinite

1  1 . 1 _

F(u) = cosu - cos.u + -cos u - cosu + ... (2.1.18)

1 1 sin7u+ '"

= sinu + -sin3u + sin5u +

Consequently, the spectrum is real and we display its values directly. Note that both

positive and negative frequencies are displayed, and the amplitudes have been halved

accordingly. An application of Fourier synthesis is shown in Fig. 2.5c, where the first

five nonzero components ofF(u) are added together. With each additional component,

the reconst'ucted function increasingly takes on the appearance of the original square

wave. The ripples that persist are a consequence of the oscillatory behavior of the

sinusoidal basis functions. They remain in the reconstruction unless all frequency com-

ponents are considered in the reconstruction. This artifact is known as Gibbs

phenomenon which predicts an overshoot/undershoot of about 22% near edges that are

not fully reconstructed [Antoniou 79].

A second example is given in Fig. 2.6. There, an arbitrary waveform undergoes

Fourier analysis and synthesis. In this case, F(u) is complex and so only the magnitude

spectrum IF(u) l is shown in Fig. 2.6b. Since the spectrum is defined over infinite fre-

quencies, only a small segment of it is shown in the figure. The results of Fourier syn-

thesis with the first ten frequency components are shown in Fig. 2.6c. As before, incor-

porating the higher frequency components adds finer detail to the reconstructed function.

The two examples given above highlight an important property of Fourier

transforms that relate to periodic and aperiodic functions. Periodic signals, such as the

square wave shown in Fig. 2.5a, can be represented as the sum of phase-shifted sine

waves whose frequencies are integral multiples of the signal's lowest nonzero frequency

component. In other ._..,r_d a periodic signal contains all the frequencies that are har-

monics of the fundamental frequency. We normally associate the analysis of periodic

signals with Fourier series rather than Fourier transforms. The Fourier series can be

expressed as the following summation

f (x) = a c(nuo)ei2nux (2.1.19)

where c (nuo) is the nth Fourier coefficient

c(nuo) = f f (x)e-i2nnuX dx (2.1.20)

2.1 FUNDAMENTALS

f (x) F (u)

(a) (b)

sin(x)

sin(5x)

(c)

23

(2.1.20) that is used to compute the Fourier coefficients must only integrate over period

X0.

Aperiodic signals do not enjoy the same compact representation as their periodic

components that are integer multiples of some fundamental frequency, an aperiodic sig-

nal must necessarily be represented as an integral over a continuum of frequencies, as in

Eq. (2.1.13). This is reflected in the spectra of Figs. 2.5b and Fig. 2.6b. Notice that the

square wave spectrum consists of a discrete set of impulses in the frequency domain,

while the spectrum of the aperiodic signal in Fig. 2.6 is defined over all frequencies. For

this reason, we distinguish Eq. (2.1.13) as the Fourier integral. It can be shown that the

Fourier series is a special case of the Fourier integral. In summary, periodic signals have

discrete Fourier components and are described by a Fourier series. Aperiodic signals

24

f (x) IF(u)[

(a) (b)

VII 

.5 L5 2

(c)

Figure 2.6: Fourier transform. (a) aperiodic signal; (b) spectrum; (c) partial sums.

have continuously varying Fourier components and are described by a Fourier integral.

There am several other symmetries that apply between the spatial and frequency

domains. Table 2.2 lists just a few of them. They refer to functions being real, ima-

ginary, even, and odd. A function is real ifJhe imaginary component is set to zero.

Simlariy, a function is imaginary if its real component is zero. A function f (x) is even

iff(-x):f(x). Iff(-x)=-f(x), then f(x) is said to be an odd function. Finally,

F*(u) refers to the complex conjugate of F(u). That is, if F(u)=R(u)+il(u), then

F* (u)=R(u)-il(u).

Spatial Domain, f (x)

Real

Imaginary

Odd

Real and Odd

Imaginary and Even

Imaginary and Odd

Periodic

Periodic Sampling

Frequency Domain, F (u)

F(-u) =F*(u)

F(-u) = -F*(u)

Even

Real and Even

Imaginary and Odd

Imaginary and Even

Real and Odd

Discrete

Periodic Copies

Table 2.2: Symmetries between the spatial and frequency domains.

The last two symmetries listed above are particularly notable. By means of the

Fourier series, we have already seen periodic signals produce discrete Fourier spectra

(Fig. 2.5). We shall see later that periodic spectra correspond to sampled signals in the

spatial domain. The significance of this symmetry will become apparent when we dis-

cuss discrete Fourier transforms and sampling theory.

In addition to the symmetries given above, there are many properties that apply to

the Fourier transform. Some of them are listed in Table 2.3. Among the most important

of these properties is linearity because it reflects the applicability of the Fourier transform

to linear system analysis. Spatial scaling is of significance, particularly in the context of

simple warps that consist only of scale changes. This property establishes a reciprocal

relationship between the spatial domain and the frequency domain. Therefore, expansion

(compression) in the spatial domain corresponds to compression (expansion) in the fre-

quency domain. Furthermore, the frequency scale not only contracts (expands), but the

amplitude increases (decreases) vertically in such a way as to keep the area constant.

Finally, the property that establishes a correspondence between convolution in one

domain and multiplication in the other is of gmat practical significance. The proofs of

these properties are left as an exercise for the reader. A detailed exposition can be found

in [Bracewell 86], [Brigham 88], and most signal processing textbooks.

Property

Lineafity

Spatial Scaling

Frequency Scaling

Spatial Shifting

Frequency Shifting

(Modulation)

Convolution

Multiplication

Spatial Domain, f (x)

(Zlf 1 (X)+Ov2f:(x)

f(ax)

f (x-a)

g(x)=f (x)* h(x)

g(x)=f (x)h(x)

Frequency Domain, F (u)

oqFl(u)+o2F2(u)

al-F()

F (u) e -i2,,,,

F(u-a)

G (u) = F (u) H (u)

Table 2.3: Fourier transform properties.

The Fourier transform can be easily extended to multidimensional signals and sys-

tems. For 2-D images f (x,y) that are integrable, the following Fourier transform pair

exists:

F(u,v) : f f f (x,y)e-i2n(ta+vY' dxdy (2.1.21)

f(x,y) = f f V(u,v)e+i2(m+Y) dudv (2.1.22)

where u and v are frequency vaxiables. Extensions to higher dimensions are possible by

simply adding exponent terms to the complex exponential, and integrating over the addi-

tional space and frequency vaxiables.

2.1.5.3. Discrete Fourier Transforms

The discussion thus far has focused on continuous signals. In practice, we deal with

discrete images that are both limited i_n._extent _and sampl a_[is9rete points. The results

d'evetoped-sfrstee mdified to beeful in this domain. We thus come to define

the discrete Fourier tradofln pair:

F (u ) = ' x=O f '.x ) e  2ux/l (2.1.23)

f (x) =  F (u)e 12r"xl (2.1.24)

u=0

in front of the forward transform serves to normalize the spectrum with respect to the

length of the input. There is no strict rule which requires the normalization to be applied

to F(u). In some sources, the lIN factor appears in front of the inverse transform

instead. For reasons of symmetry, other common formulations have the forward and

2.1 FUNDAMENTAL 27

inverse transforms each scaled by 1/,f. As long as a cumulative I/N factor is applied

somewhere along the transform pair, the final results will be properly normalized.

The discrete Fourier transform (DFT), defined in Eq. (2.1.23), assumes thatf (x) is

an input array consisting of N regularly spaced samples. It maps these N complex

numbers into F(u), another set of N complex numbers. Since the frequency domain is

now discrete, the DFT must treat the input as a periodic signal (from Table 2.2). As a

result, we have let the limits of summation change from (-N/2, N/2) to (0, N-l), bearing

in mind that the negative frequencies now occupy positions N/2 to N-1. Although nega-

tive frequencies have no physical meaning, they are a byproduct of the mathematics in

this process. It is noteworthy to observe, though, that the largest reproducible frequency

for an N-sample input is N/2. This corresponds to a sequence of samples that alternate

between black and white, in which the smallest period for each cycle is two pixels.

The data in f (x) is treated as one period of a periodic signal by replicating itself

indefinitely, thereby tiling the input plane with copies of itself. This makes the opposite

ends of the signal adjacent by virtue of wraparound from f (N-i) to f (0). Note that this

is only a model of the infinite input, given only the small (aperiodic) segment f (x), i.e.,

no physical replication is necessary. While this permits F(u) to be defined for discrete

values of u, it does introduce artifacts. First, the transition across the wraparound border

may be discontinuous in value or derivative(s). This has consequences in the high fre-

quency components of F(u). One solution to this problem is windowing, in which the

actual signal is multiplied by another function which smoothly tapers off at the borders

(see Chapter 5). Another consideration is the value ofN. A small N produces a coarse

approximation to the continuous Fourier transform. However, by choosing a sufficiently

high sampling rate, a good approximation to the continuous Fourier transform is obtained

for most signals.

The i-D discrete Fourier transform pairs given in Eqs. (2.1.23) and (2.1.24) can be

extended to higher dimensions by means of the separability property. For an NxM

images, we have the following DFT pair:

F(u,v) = -   f(x,y)e (2.1.25)

f(x,y) =   F(u,v)e i2nOtx/N+vyM) (2.1.26)

The DFT pair given above can be expressed in the separable forms

1 M-I N-I }

f(x,y) =   F(u,v)e i2mtxlN e i2vylM (2.1.28)

for u,x =0,1,...,N-I, and v,y =0,1,...,M-1.

28 PRELIMINARIE

The principal advantage of this reformulation is that F (u,v) and f (x,y) can each be

obtained by successive applications of the 1-D DFT or its inverse. By regrouping the

operations above, it becomes possible to compute the xansforms in the following

manner. First, transform each row independently, placing the results in intermediate

image 1. Then, transform each column of/independently. This yields the correct results

for either the forward or inverse transforms. In Chapter 7, we will show how separable

algorithms of this kind have been used to greatly reduce the computational cost of digital

image warping.

Although the DFT is an important tool that is amenable for computer use, it does so

at a high price. For an N-sample input, the computational cost of the DFT is O (N2).

This accounts for N summations, each requiring N multiplication operations. Even with

high-speed computers, the cost of such a transform can be overwhelming for large N.

Consequently, the DFT is often generated with the fast Fourier transform (FFT), a com-

putational algorithm that reduces the computing time to O (N log2N). The FFT achieves

large speedups by exploiting the use of partial results that combine to produce the correct

output. This increase in computing speed has completely revolutionized many facets of

scientific analysis. A detailed description of the FFT algorithm, and its variants, are

given in Appendix 1. In addition to this review, interested readers may also consult

[Brigham 88] and [Ramirez 85] for further details.

The development of the FFT algorithm has given impetus to filtering in the fre-

quency domain. There are several advantages to this approach. The foremost benefit is

that convolution in the spatial domain corresponds to multiplication in the frequency

domain. As a result, when a convolution kernel is sufficiently large, it becomes more

cost-effective to transform the image and the kemel into the frequency domain, multiply

them, and then transform the product back into the spatial domain. A second benefit is

that important questions relating to sampling, interpolation, and aliasing can be answered

rigorously. These topics are addressed in subsequent chapters.

2.2. IMAGE ACQUISITION

Before a digitaputer can begin to process an image, that image must first be

available in digital 1hrm This is made possible by a digital image acquisition system, a

device that scans the scene and generates an array of numbers representing the light

intensities at a discrete set of points. Also known as a digitizer, this device serves as the

front-end to any image processing system, as depicted in Fig. 2.7.

Digital image acquistion systems consist of three basic components: an imaging

sensor to measure light, scanning hardware to collect measurements across the entire

scene, and an analog-to-digital converter to disaretize the continuous values into finite-

precision numbers suitable for computer processing. The remainder of this chapter is

devoted to describing these components. However, since a full description that does jus-

tice to this topic falls outside the scope of this book, our discussion will be brief and

incomplete. Readers can find this material in most image processing textbooks. Useful

reviews can also be found in [Nagy 83] and [Schreiber 86].

2.2 IMAGE ACQUISITION 29

Digitizer

Input  n, Digital

Scene I ....... ' ' I image ICom. puter I

Figure 2.7: Elements of an image processing system.

Consider the image acquisition system shown in Fig. 2.8. The entire imaging pro-

cess can be viewed as a cascade of filters applied to the input image. The scene radiance

f (x,y) is a continuous two-dimensional image. It passes through an imaging subsystem,

which acts as the first stage of data acquisition. Section 2.3 describes the operation of

several common imaging systems. Due to the point spread function of the image sensor,

h (x,y), the output g (x,y) is a degraded version off (x,y).

Scene r [ Subsytem Subsystem

* h (x,y) * s (x,y)

Quantizer

ga(x,y)

Image

By definition,

g(x,y) = f (x,y) * h(x,y) (2.2.1)

where * denotes convolution. If the PSF profile is identical in all orientations, the PSF is

said to be rotationally-symmetric. Furthermore, if the PSF retains the same shape

throughout the image, it is said to be spatially-invariant. Also, if the two-dimensional

PSF can be decomposed into two one-dimensional filters, e.g., h (x,y) = hx(x,y) hy(x,y), it

is said to be separable. In practice, though, point spread functions are usually not

rotationally-symmetric, spatially-invaxiant, or separable. As a result, most imaging dev-

ices induce geometric distortion in addition to blurring.

0 PRELIMINARIE

The continuous image g (x,y) then enters a sampling subsystem, generating the

discrete-continuous image gs(x,y). The sampled image gs(x,y) is given by

gs(x,y) = g (x,y) s (x,y) (2.2.2)

where

s(x,y) =   5(x-m,y-n) (2.2.3)