GACS-7205-001 Digital Image Processing Page 181

(Fall Term, 2022-23)

4.6 Some Properties of the 2-D Discrete Fourier Transform

Relationships between Spatial and Frequency Intervals

Suppose that a continuous function f (t, z ) is sampled to form a

digital image f (x, y ) , consisting of M ´ N samples taken in the t-
and z-directions. Let DT and DZ denote the separations between
samples, then, the separations between the corresponding discrete,
frequency domain variables are given by
1
Du = (4.6-1)
M DT
and
1
Dv =
N DZ . (4.6-2)

Translation and Rotation

The Fourier transform pair satisfies the following translation

properties:
f (x, y )e j 2p( u0x / M +v0y / N )  F (u - u0 , v - v0 ) (4.6-3)
and
f (x - x 0 , y - y0 )  F (u, v )e-j 2p( x 0u / M +y0v / N ) (4.6-4)

Using the polar coordinates

x = r cos q y = r sin q u = w cos j v = w sin j ,

we have the following transform pair:

f (r, q + q0 )  F (w, j + q0 ) . (4.6-5)
Equation (4.6-5) indicates that rotating f (x, y ) by an angle q0 will
rotate F (u, v ) by the same angle. Conversely, rotating F (u, v ) will
rotate f (x, y ) by the same angle.
GACS-7205-001 Digital Image Processing Page 182
(Fall Term, 2022-23)

Periodicity

As in the 1-D case, the 2-D Fourier transform and its inverse are
infinitely periodic in the u and v directions:
F (u, v) = F ( u + k1M , v ) = F ( u, v + k2N ) = F ( u + k1M , v + k2N ) (4.6-6)

and
f (x, y ) = f ( x + k1M , y ) = f ( x, y + k2N ) = f ( x + k1M , y + k2N ) (4.6-7)
where k1 and k2 are integers.

The periodicities of the transform and its inverse are important

issues in the implementation of DFT-based algorithms.
GACS-7205-001 Digital Image Processing Page 183
(Fall Term, 2022-23)

Considering Figure 4.23 (b) and referring to

f (x, y )e j 2p( u0x / M +v0y / N )  F (u - u0 , v - v0 ) , (4.6-3)
it follows
f (x )e j 2p( u0x / M )  F (u - u0 ) ,

which indicates that multiplying f (x ) by the exponential term will

show the shifting. If we let u0 = M / 2 , the exponential term becomes
e j px , which is equal to ( -1 )x . It follows
f (x )( -1 )x  F (u - M / 2) .

It means that multiplying f (x ) by ( -1 )x shits the data so that F ( 0 )

is at the center of the interval [ 0, M - 1 ] .

In a case of 2D, if we let ( u0 , v0 ) = ( M / 2, N / 2 ) in

f (x, y )e j 2p( u0x / M +v0y / N )  F (u - u0 , v - v0 ) , (4.6-3)

it will result the expression
f (x, y ) ( -1 )x +y  F (u - M / 2, v - N / 2) (4.6-8)

Using (4.6-8) shifts the data so that F ( 0, 0 ) is at the center of the

frequency rectangle defined in Figure 4.23 (d).
GACS-7205-001 Digital Image Processing Page 184
(Fall Term, 2022-23)

Symmetry Properties

An important result from functional analysis is that any real or

complex function, w(x, y ) , can be expressed as the sum of an even
and an odd part:
w(x, y ) = we (x, y ) + wo (x, y ) (4.6-9)
where
w(x , y ) + w ( -x, -y )
we (x, y )  (4.6-10a)
2
and
w(x, y ) - w ( -x , -y )
wo (x , y )  . (4.6-10b)
2
It follows that
we (x, y ) = we ( -x, -y ) (4.6-11a)
and
wo (x , y ) = -wo ( -x, -y ) (4.6-11b)

Even functions are said to be symmetric and odd functions are

antisymmetric.

Since all indices in DFT and IDFT are positive, when we say
“symmetry (antisymmetry)” we are referring to symmetry
(antisymmetry) about the center point of a sequence.

It is more convenient to think only in terms of nonnegative indices,

in which case
we (x, y ) = we ( M - x , N - y ) (4.6-12a)
and
wo (x , y ) = -wo ( M - x, N - y ) (4.6-12b)
where M and N are the number of rows and columns of a 2-D
array.
GACS-7205-001 Digital Image Processing Page 185
(Fall Term, 2022-23)

We know that the product of two even or odd functions is even, and
the product of an even and an odd is odd. In addition, the only way
that a discrete function can be odd is if all its samples sum to zero.

These lead to the important result of

M -1 N -1

å å we (x, y)wo (x, y) = 0 . (4.6-13)

x =0 y =0

In other words, because the argument of (4.6-13) is odd, the result of

the summations is 0. the functions can be real or complex.

Example 4.10: Even and odd functions

The evenness and oddness of discrete sequences are not as easy

to visualize as those of continuous functions. Consider the 1-D
sequence
f = { f (0) f (1) f (2) f (3)} = { 2 1 1 1}

in which M = 4 . To test for evenness, the condition

f (x ) = f (4 - x ) must be satisfied:

f (0) = f (4) , f (1) = f (3) , f (2) = f (2) , f (3) = f (1) .

Since f (4) is outside the range being examined and it can be

any value, the value of f (0) is immaterial in the test for
evenness.

The next three conditions are satisfied and the sequence is

even.

In fact, any 4-point even sequence has to have the form

{a b c b} .
GACS-7205-001 Digital Image Processing Page 186
(Fall Term, 2022-23)

According to (4.6-10b), the first term of an odd sequence,

wo (0, 0) , is always 0 . Consider the 1-D sequence

g = { g(0) g(1) g(2) g(3)} = {0 - 1 0 1} ,

which satisfies the condition g(x ) = -g(4 - x ) .

Any 4-point odd sequence has the form {0 - b 0 b} .

The evenness and oddness of sequences depend also on the length

of the sequences. For example, although {0 - 1 0 1} is odd,
the sequence {0 - 1 0 1 0} is neither odd nor even.

The same basic considerations hold in 2-D. For example, the

6 ´ 6 2-D sequence
0 0 0 0 0 0
0 0 0 0 0 0
0 0 -1 0 1 0
0 0 -2 0 2 0
0 0 -1 0 1 0
0 0 0 0 0 0

is odd. However, adding another row or column of 0s would give

a result that is neither odd nor even.

Now, we can establish a number of important symmetry properties

of the DFT and its inverse.

The Fourier transform of a real function, f (x, y ) , is conjugate

symmetric:
F * (u, v ) = F (-u, -v ) . (4.6-14)
GACS-7205-001 Digital Image Processing Page 187
(Fall Term, 2022-23)

If f (x, y ) is imaginary, its Fourier transform is conjugate

antisymmetric:
F * (-u, -v ) = -F (u, v ) .

Table 4.1 lists symmetries and related properties of the DFT that
are useful in digital image processing.

Example 4.11

Example 4.12
GACS-7205-001 Digital Image Processing Page 188
(Fall Term, 2022-23)

Fourier Spectrum and Phase Angle

Since the 2-D DFT is complex in general, it can be expressed in

polar form:
F (u, v ) = F (u, v ) e jf( u,v ) , (4.6-15)
where
F (u, v ) = [R2 ( u, v ) + I 2 ( u, v )]1/2 (4.6-16)

is the Fourier (frequency) spectrum, and

é I (u, v ) ù
f ( u, v ) = arctan ê ú (4.6-17)
êë R(u, v ) úû

is the phase angle.

The power spectrum is defined as

P(u, v ) = F (u, v ) 2 = R2 (u, v) + I 2 (u, v) , (4.6-18)
where R and I are the real and imaginary parts of F (u, v) and the
discrete variables u = 0,1,2,..., M - 1 and v = 0,1,2,..., N - 1 .

The spectrum has even symmetry about the origin

F (u, v ) = F (-u, -v ) , (4.6-19)

and phase angle has the odd symmetry about the origin

f(u, v ) = -f(-u, -v ) . (4.6-20)

From the 2-D discrete Fourier transform defined in

M -1 N -1
F (u, v) = å å f (x, y)e-j 2p(ux / M +vy / N ) (4.5-15)
x =0 y =0
GACS-7205-001 Digital Image Processing Page 189
(Fall Term, 2022-23)

we have
M -1 N -1
F (0, 0) = å å f (x, y)
x =0 y =0
M -1 N -1
1
= MN
MN å å f (x, y)
x =0 y =0

= MNf (x, y ) (4.6-21)

where f (x, y ) denotes the average value of f (x, y ) . Then, we have

F (0, 0) = MN f (x , y ) (4.6-22)

Since the constant MN is usually large, F (0, 0) typically is the

largest component of the spectrum (it could be several orders of
magnitude larger than other terms).

F (0, 0) sometimes is called the dc component of the transform.

GACS-7205-001 Digital Image Processing Page 190
(Fall Term, 2022-23)

Example 4.13: The 2-D Fourier spectrum of a simple function

Figure 4.24 (a) shows a simple image and Figure 4.24 (b) shows
its spectrum, whose values were scaled to the range [ 0,255 ] and
displayed in the image form.

The origins of both the spatial and frequency domains are at the
top left. Note that the four corners of the spectrum contain
similarly high values. The reason is the periodicity property
discussed in the previous section.

Figure 4.24 (c) shows the result of multiplying the image in

Figure 4.24 (a) by ( -1 )x +y before computing the DFT.

Figure 4.24 (d) shows the display of log ( 1 + F ( u, v ) ) . The

increased rendition of detail is evident.
GACS-7205-001 Digital Image Processing Page 191
(Fall Term, 2022-23)

According to
f (x - x 0 , y - y0 )  F (u, v )e-j 2p( x 0u / M +y0v / N ) (4.6-4)
and
f (r, q + q0 )  F (w, j + q0 ) , (4.6-5)
the spectrum is insensitive to image translation (the absolute
value of the exponential term is 1), but it rotates by the same
angle of a rotated image. Figure 4.25 illustrates these properties.

Figure 4.25 (a) shows that the rectangle in Figure 4.24 (a) was
translated. Figure 4.25 (b) shows the corresponding spectrum,
which is identical to the spectrum shown in Figure 4.24 (d). Figure
4.25 (c) and Figure 4.25 (d) are the images of rotated rectangle and
the corresponding spectrum.
GACS-7205-001 Digital Image Processing Page 192
(Fall Term, 2022-23)

The images in Figure 4.24 (a) and Figure 4.25 (a) are different. If
their Fourier spectra are the same, according to
F (u, v ) = F (u, v ) e jf( u,v ) , (4.6-15)
their phase angles must be different, as shown in Figure 4.26.

Figure 4.26 (a) and Figure 4.26 (b) are the phase angle arrays of
the DFTs of Figure 4.24 (a) and Figure 4.25 (a).

In general, visual analysis of phase angle images yields little

intuitive information.

The components of the spectrum of the DFT would determine the

amplitudes of the sinusoids that combine to form the resulting image.

At any given frequency in the DFT of an image, a large amplitude

implies a greater prominence of a sinusoid of that frequency in the
image. Conversely, a small amplitude implies that less of that
sinusoid is present in the image.

The phase is a measure of displacement of the various sinusoids

with respect to their origin.
GACS-7205-001 Digital Image Processing Page 193
(Fall Term, 2022-23)

Example 4.14: Further illustration of the properties of the Fourier

spectrum and phase angle

Figure 4.27 (b) is the phase angle of the DFT of Figure 4.27 (a).

Figure 4.27 (c) was obtained by computing the inverse DFT of

F (u, v ) = F (u, v ) e jf( u,v ) (4.6-15)
using only phase information. It shows the importance of the
phase in determining shape characteristics.

Figure 4.27 (d) was obtained by using only the spectrum in (4.6-15)
and computing the inverse DFT.

Figure 4.27 (e) and (f) show the dominance of the phase in
determining the feature content of an image.
GACS-7205-001 Digital Image Processing Page 194
(Fall Term, 2022-23)

The 2-D Convolution Theorem

Extending
M -1
f (x )★ h(x ) = å f (m)h(x - m) (4.4-10)
m =0

to two variables results in the expression for 2-D circular

convolution:
M -1 N -1
f (x, y )★ h(x, y ) = å å f (m, n)h(x - m, y - n) (4.6-23)
m =0 n =0

for x = 0,1,2,..., M - 1 and y = 0,1,2,..., N - 1 . As in (4.4-10),

(4.6-23) gives one period of a 2-D periodic sequence.

The 2-D convolution theorem is given by the expressions

f (x, y )★ h(x, y )  F (u, v )H (u, v ) (4.6-24)

and, conversely,

f (x, y )h(x , y )  F (u, v )★ H (u, v ) (4.6-25)

where F and H are obtained from using the 2-D discrete Fourier
transform
M -1 N -1
F (u, v ) = å å f (x, y)e-j 2p(ux / M +vy / N ) . (4.5-15)
x =0 y =0

As mentioned previously, the double arrow,  , is used to indicate

that the left and right sides of the expressions constitute a Fourier
transform pair.

Equation (4.6-24) is the foundation of linear filtering, and is the

basis for all the filtering techniques discussed in this chapter.
GACS-7205-001 Digital Image Processing Page 195
(Fall Term, 2022-23)

Figure 4.28 shows a 1-D example.

The left column of Figure 4.28 implements convolution of two

functions, f and h , using the 1-D equivalent of
a b
w(x, y )★ f (x, y ) = å å w(s, t )f (x - s, y - t ) , (3.4-2)
s =-a t =-b

which is
399
f (x )★ h(x ) = å f (x )h(x - m) .
m =0
GACS-7205-001 Digital Image Processing Page 196
(Fall Term, 2022-23)

Figure 4.28 (e) shows the convolution of these two functions.

If we use the DFT and the convolution theorem to obtain the same
result as in the left column of Figure 4.28, we must take into account
the periodicity inherent in the expression of DFT.

Figure 4.28 (f) and (g) are two periodic functions. Processing
convolution with these two functions would yield the result shown
in Figure 4.28 (j), which is incorrect. They interfere with each other
to cause the so-called wraparound error.

To solve the wraparound error problem, consider two functions, f (x )

and h(x ) composed of A and B samples. If we append zeros to both
functions so that they have the same length, P , then wraparound is
avoided by choosing
P ³ A + B -1. (4.6-26)

In the example shown in Figure 4.28, each function has 400 points,
so the minimum value we could use is P = 799 . We can achieve
that by appending 399 zeros to the trailing edge of each function.
This process is called zero padding.

We would have the same conclusion regarding to wraparound error

in 2-D. let f (x , y ) and h(x , y ) be two image arrays of sizes A ´ B
and C ´ D pixels. Wraparound error in their circular convolution
can be avoided by padding these functions with zeros, as follows:

ì
ï f (x, y ) 0 £ x £ A - 1 and 0 £ y £ B - 1
ï
fp (x, y ) = í
ï
ï 0 A£x £P or B £ y £ Q (4.6-27)
î

and
GACS-7205-001 Digital Image Processing Page 197
(Fall Term, 2022-23)

ì h(x, y ) 0 £ x £ C - 1 and 0 £ y £ D - 1
ï
hp (x, y ) = ï
í
ï
ï 0 C £x £P or D £ y £ Q (4.6-28)
î

with
P ³ A +C -1 (4.6-29)
and
Q ³ B + D -1. (4.6-30)

The resulting padded images are of size P ´ Q . If both arrays are of

the same size, M ´ N , then we require that
P ³ 2M - 1 (4.6-31)
and
Q ³ 2N - 1 . (4.6-32)

As a rule, DFT algorithms tend to execute faster with arrays of even

size, so it is a good practice to select P and Q as the smallest even
integers that satisfy the above equations.

If the two arrays are the same size, P and Q are selected as twice
the array size.
GACS-7205-001 Digital Image Processing Page 198
(Fall Term, 2022-23)

Summary of 2-D Discrete Fourier Transform Properties

GACS-7205-001 Digital Image Processing Page 199
(Fall Term, 2022-23)