**20 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(3x)
sin(5x)
sin(7x)
(c)
Figure 2.5: Fourier transform. (a) square wave; (b) spectrum; (c) partial sums.
23
and u 0 is the fundamental frequency. Note that since f (x) is periodic, the integral in Eq.
(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
counterparts. Whereas a periodic signal is expressed in terms of a sum of frequency
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
**PRELIMINARIES **
f (x) IF(u)[
(a) (b)
VII
VIII
.5 L5 2
(c)
Figure 2.6: Fourier transform. (a) aperiodic signal; (b) spectrum; (c) partial sums.
.5n 1.5n 2g
**2.1 FUNDAMENTALS 2 **
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
Even
Odd
Real and Even
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
Odd
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.
**26 PRELIMINARIES **
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)
f (x)e 12r. ox
g(x)=f (x)* h(x)
g(x)=f (x)h(x)
Frequency Domain, F (u)
oqFl(u)+o2F2(u)
al-F()
F(au)
F (u) e -i2,,,,
F(u-a)
G (u) = F (u) H (u)
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
for 0 $ u,x < N -1, where N is the number of input samples. The 11N factor that appears
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)
Digitiz
Image
Figure 2.8: Image acquisition system.
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)
is the two-dimensional comb function, depicted in Fig. 2.9, and 5 (x,y) is the impulse
**Share with your friends:** |