## Fourier Theory

Learn Photo Editing

Get Instant Access

The mathematical theory that Fourier introduced in 1822 was a long way from modern digital image processing. In this section, we examine the four steps that lead from his original series summation to the fast Fourier transform used in image processing: the Fourier series, the Fourier integral, the discrete Fourier series, and the fast Fourier transform. Our goal is not to teach you the math, but to show the chain of reasoning that underlies the Fourier transform.

17.2.1 Periodic Functions: The Fourier Series

Fourier demonstrated that almost any periodic mathematical function could be expressed as the sum of an infinite number of sine and cosine functions. The series is written as:

s(x) = a0 + (bx cosx + cx sinx) + (Z?2cos2x + c2sin2x) + ... (Equ. 17.1) where coefficients a0,bx,b2, ...,bn and cl9c2, • scaled the potentially infinite

Figure 17.3 The basis of the Fourier series is that any periodic function such as a square wave is the sum of a series of sinusoids. The curves shown in white are sinusoids, while their sum—the square wave—is shown in black. In this example, the black curve is the sum of 20 sinusoids.

number of progressively higher-frequency sinusoids to fit the function ,v. The only constraints are that the function s(x) must have a finite number of peaks, valleys, and discontinuities; and the area under the curve must be finite.

The simplest cases are the sine and cosine functions themselves, which require only one term. Combining a few dozen terms can replicate the waveforms produced by musical instruments, even those of the violin, which are rich in overtones. In computing a function using a Fourier series, each point x in the series generates one point, s(x), in the function s.

The Fourier series produces some remarkable results. Although it seems counterintuitive that a series of rounded sinusoids could produce the right-angled profile of a square wave, the following series generates a square one with a period of 2rc:

s(x) = cosx- ^cos3x + ^cos5x - ^cos7x + ... (Equ. 17.2)

Bear in mind that it takes an infinite number of terms to produce a true square wave, but with a few dozen terms, the approximation is fairly close. As more terms are added, the approximation to a square wave becomes more and more accurate. Also bear in mind that to add up to a square wave, the sinusoids must line up properly—that is, their phases must be correct. The minus signs in the -3x and -Ix terms mean their phase is shifted 180°. Each term in the series represents a

Sampled Low-Frequency Function

### Fourier Spectrum of Function

Figure 17.4 The sampled function above could represent a musical tone or one line of pixels from an image. In the spectrum below, low frequencies are to the left and high frequencies are to the right. The energy in the function is concentrated at a single frequency.

point in the frequency spectrum of the square wave.

To complete one full cycle of the square wave, x runs from 0 to 271, so the period of the square wave is 2k , and its fundamental frequency f0 is 1 /2n. In addition to the fundamental frequency/0, the series says that a square wave has harmonics at -3/0, 5/0, -7/0, 9/0 and so on—with harmonics at odd multiples of the fundamental frequency. The minus signs on the terms -3/0 and -7/0 imply that the phase of these frequencies is shifted 180°, or -n radians.

17.2.2 Nonperiodic Functions: The Fourier integral

In the real world, there are no purely periodic functions. Just as sounds began at some time in the past and will inevitably end at some time in the future, images have a finite extent. At some point in time or space after -oo and before +oo, the sound or image function dies away.

However, one way of looking at this is that the function is still periodic, but that the period of the function has become infinitely long, which causes the fundamental frequency to become infinitesimally small. If the harmonics are so close together that they become indistinguishable, the spectrum of the function becomes continuous. The Fourier integral is a reformulation of the Fourier series using continuous functions rather than coefficients in a series of terms.

Sampled Medium-Frequency Function

### Fourier Spectrum of Function

Figure 17.5 This function has a shorter wavelength and higher frequency than that shown in Figure 17.4. The higher frequency changes over a smaller span of samples, and the spectrum shows the energy at correspondingly higher frequencies. As the frequency rises, a cycle contains fewer samples.

The Fourier series looks like this:

s(x) = a0 + ^ (bncos(2nnf0x) + cnsin(2Kn/0x)). (Equ. 17.3)

This equation is simply Equation 17.1 coming back in summation notion. In the Fourier series, n runs through an infinite number of terms. The sine and cosine functions can be rewritten in exponential form:

/271«/qX -iliinf^x cos(27T«/0x) = ----(Equ. 17.4)

2 i where e is the base of natural logarithms, and i is the infamous J^A , the square root of minus one. Substituting these into the series equation:

Sampled Two-Frequency Function

Fourier Spectrum of Function

Figure 17.6 This function is the sum of two sinusoids, the low-frequency one from Figure 17.4 and the medium-frequency one from Figure 17.5. Even with as few as two sinusoids, the eye cannot easily pick out the frequencies—yet the Fourier spectrum clearly reveals the two separate frequencies.

In this form, the series contains an infinite number of terms. To convert the summation to an integral, we allow x to become infinitesimally small, which results in the integral form:

where the function S(f) is the Fourier transform of s(jc). If s(x) is a sound wave, then S(f) is its frequency spectrum.

The Fourier transform can be derived from the original function using the integral:

These equations have something important to say: you can break any one-dimensional function—whether it's a sound wave or a slice through an image— into a spectrum; and given the spectrum, you can apply the inverse Fourier trans-

Sampled Square-Wave Function

### Fourier Spectrum of Function

Figure 17.7 A square wave contains a large number of frequency components, increasing in frequency and declining in amplitude. Just as we built a square wave from sinusoids in Figure 17.3, here we have transformed a sampled square wave into a clearly defined set of frequencies.

form to recover the original function.

Although these equations apply to one-dimensional functions, it is possible to develop equations for two-dimensional functions; that is, for images. In image processing, we transform an image into frequency space, modify its frequency content, and then apply the inverse transform to recover the modified image.

In the two-dimensional Fourier transform, the image exists in spatial coordinate system (jt, y), while the spectrum exists in frequency space, with its frequency axes customarily written as (w, v). Here is the Fourier transform in two dimensions:

Here is the inverse Fourier transform in two dimensions:

OO oo s(x,y) = ^S{u,v)eilK(ux + vy)dudv. (Equ. 17.10)

The two-dimensional equations show that you can break a two-dimensional image into a two-dimensional frequency spectrum in the (u, v) plane; and that giv-