Appendix C
The Fast Fourier Transform
We have discussed the Fourier transform and its uses in Chapter 7. However, as we know,
the Fourier transform gains much of its usefulness by the existence of a fast algorithm to
compute it. We look briefly at one version of the fast Fourier transform here. More details
can be found in [13] or [54].
To start, we shall look at the very simple DFT for a two-element vector, where for
convenience we shall omit the scaling factor:
X
0
X
1
=
1 1
1 −1
x
0
x
1
=
x
0
+ x
1
x
0
− x
1
.
We can express this combination with a “butterfly diagram” as shown in Figure C.1. We
x
1
X
1
x
0
X
0
−1
FIGURE C.1: A butterfly diagram
shall see how this butterfly diagram can be extended to vectors of greater length. In general,
a butterfly diagram will consist of nodes joined as shown in Figure C.1, with scaling factors
as shown in Figure C.2. In this figure, we have
b
B
a
A
x
y
FIGURE C.2: A general butterfly
517
518 A Computational Introduction to Digital Image Processing, Second Edition
A = a + xb,
B = a + yb.
By convention, if a scaling factor is not specified, it is assumed to be 1.
We can extend this to the DFT for a four-element vector, starting with its matrix
definition.
X
0
X
1
X
2
X
3
=
1 1 1 1
1 −i −1 i
1 −1 1 −1
1 i −1 −i
x
0
x
1
x
2
x
3
=
x
0
+ x
1
+ x
2
+ x
3
x
0
− ix
1
− x
2
+ ix
3
x
0
− x
1
+ x
2
− x
3
x
0
+ ix
1
− x
2
− ix
3
=
(x
0
+ x
2
) + (x
1
+ x
3
)
(x
0
− x
2
) − i(x
1
− x
3
)
(x
0
+ x
2
) − (x
1
+ x
3
)
(x
0
− x
2
) + i(x
1
− x
3
)
=
x
0
+ x
1
x
2
− ix
3
x
0
− x
1
x
2
+ ix
3
This means we can obtain a four-element DFT by a two-stage process; first we create
“intermediate” values x
i
:
x
0
= x
0
+ x
2
x
1
= x
1
+ x
3
x
2
= x
0
− x
2
x
3
= x
1
− x
3
and use these new values to calculate the final values:
X
0
= x
0
+ x
1
X
1
= x
2
− ix
3
X
2
= x
0
− x
1
X
3
= x
2
+ ix
3
The butterfly diagram for this is shown in Figure C.3. Note that it consists of two simple
butterfly diagrams on the left, joined together with more butterflies on the right.
Note that the order of the original elements x
i
has been changed; we shall discuss this
more below.
To apply the same idea to an eight-element vector, we consider the general term of the
transform:
X
k
= ω
0
x
0
+ ω
k
x
1
+ ω
2k
x
2
+ ω
3k
x
3
+ ··· + ω
7k
x
7
where ω = e
−2πi/8
= ω
0
x
0
+ ω
2k
x
2
+ ω
4k
x
4
+ ω
6k
x
6

even values
+ ω
k
x
1
+ ω
3k
x
3
+ ω
5k
x
5
+ ω
7k
x
7

odd values
= ω
0
x
0
+ ω
2k
x
2
+ ω
4k
x
4
+ ω
6k
x
6
+ ω
k
(x
1
+ ω
2k
x
3
+ ω
4k
x
5
+ ω
6k
x
7
).
The Fast Fourier Transform 519
x
3
x
3
X
3
x
2
x
2
X
2
x
1
x
1
X
1
x
0
x
0
X
0
−1
−1
i
−1
−i
FIGURE C.3: A butterfly diagram for a four-element FFT
Now, let z = ω
2
= e
−2πi/4
. Then
X
k
= (z
0
x
0
+ z
k
x
2
+ z
2k
x
4
+ z
3k
x
6
) + ω
k
(z
0
x
1
+ z
k
x
3
+ z
2k
x
5
+ z
3k
x
7
) (C.1)
If we examine at the brackets in this expression, we note that the first bracket is the kth
term of the DFT of (x
0
, x
2
, x
4
, x
6
), and the second bracket is the kth term of the DFT of
(x
1
, x
3
, x
5
, x
7
). So we can write:
X
k
= DFT(x
0
, x
2
, x
4
, x
6
)
k
+ ω
k
DFT(x
1
, x
3
, x
5
, x
7
)
k
.
To make the argument easier to follow, let us write
(Y
0
, Y
1
, Y
2
, Y
3
) = DFT(x
0
, x
2
, x
4
, x
6
)
(Y
0
, Y
1
, Y
2
, Y
3
) = DFT(x
1
, x
3
, x
5
, x
7
)
Thus, we have
X
k
= Y
k
+ ω
k
Y
k
.
There is a slight problem here: the DFT of a four-element vector only has four terms, so
that k here only takes values 0 to 3, and we need values 0 to 7. However, if we look back
at Equation C.1, we can see that if k takes values 4 to 7, the powers of z j ust cycle around
again, since z
4
= 1. Thus, for these values of k we have:
X
k
= Y
k−4
+ ω
k
Y
k−4
.
This means that the indices for X
k
can take all values between 0 and 7, but the indices of
Y
k
and Y
k
only take on values 0 to 3.
We can check this from first principles. Recall that in MATLAB and Octave, the
fft
function, to obtain a correct result, must be applied to a column vector.
Let us first create an eight-element vector, and obtain its Fourier transform:
520 A Computational Introduction to Digital Image Processing, Second Edition
MATLAB/Octave
>> x = 2:9
x =
2 3 4 5 6 7 8 9
>> fx=fft(x’)
fx =
44.0000
-4.0000 + 9.6569i
-4.0000 + 4.0000i
-4.0000 + 1.6569i
-4.0000
-4.0000 - 1.6569i
-4.0000 - 4.0000i
-4.0000 - 9.6569i
Now we shall split up th e vector into even and odd parts, and put their Fourier transforms
together using the above formula:
MATLAB/Octave
>> even = [2 4 6 8]; odd = [3 5 7 9];
>> feven = fft(even’);
>> fodd = fft(odd’);
>> X = zeros(8,1);
>> omega = exp(-2
*
pi
*
sqrt(-1)/8);
>> for i = 0:3,X(i+1) = feven(i+1)+omega^i
*
fodd(i+1);end
>> for i = 4:7,X(i+1) = feven(i-3)+omega^i
*
fodd(i-3);end
>> X
X =
44.0000
-4.0000 + 9.6569i
-4.0000 + 4.0000i
-4.0000 + 1.6569i
-4.0000
-4.0000 - 1.6569i
-4.0000 - 4.0000i
-4.0000 - 9.6569i
and this result agrees with the Fourier transform obtained from above. Note that in the
for lo ops we used indices i + 1 and i − 3. This is because the theory starts indices at 0,
but MATLAB starts indices at 1.
In Python it is equally straightforward:
The Fast Fourier Transform 521
Python
In : from numpy.fft import fft
In : x = np.arange(2,10)
In : fx = fft(x)
In : print fx
[ 44.+0.j -4.+9.65685425j -4.+4.j -4.+1.65685425j
-4.+0.j -4.-1.65685425j -4.-4.j -4.-9.65685425j]
This agrees—as it should!—with the computations above. Now, for even and odd subarrays:
Python
In : evenx = x[::2]
In : oddx = x[1::2]
In : feven =fft(evenx)
In : fodd = fft(oddx)
In : omega = np.exp(-2.0
*
np.pi
*
1j/8)
In : X1 = feven + omega
**
np.arange(4)
*
fodd
In : X2 = feven + omega
**
np.arange(4,8)
*
fodd
In : np.set
_
printoptions(precision=4)
In : print np.hstack([X1,X2])
[ 44. +0.0000e+00j -4. +9.6569e+00j -4. +4.0000e+00j -4. +1.6569e+00j
-4. -1.0658e-14j -4. -1.6569e+00j -4. -4.0000e+00j -4. -9.6569e+00j]
Note that because of Python’s array indexing starting at zero, the computation of X1 and
X2 is very straightforward.
As with the four-element transform, we can express the eight-element transform by
using a butterfly diagram. Such a diagram, treating the four-element FFT as a “black box,”
is shown in Figure C.4. Note that as in Figure C.3 the order of the original elements is
changed.
If we now replace the black box FFTs from Figure C.4 with the four-element butterfly
diagram of Figure C.3 we obtain a “complete” butterfly diagram for eight elements, which is
given in Figure C.5. To show the structure of the diagram, we have left out the multiplication
factors, which are simply inherited from their respective diagrams.
We have noted that the input values in our butterfly diagrams are not given in their
correct order. The ordering we require can be obtained by binary bit reversal. Suppose we
list the input elements x
i
in order but replace the indices with their binary expansions:
x
0
x
1
x
2
x
3
x
4
x
5
x
6
x
7
= x
000
x
001
x
010
x
011
x
100
x
101
x
110
x
111
Now we replace each index with the reversal of its bits, and go back to decimal:
x
000
x
100
x
010
x
110
x
001
x
101
x
011
x
111
= x
0
x
4
x
2
x
6
x
1
x
5
x
3
x
7
and now we have the new order for input into the FFT.
The particular form of the FFT we have developed here is known as the “decimation in
time, 2 radix” FFT. We can describe its general workings as follows:
1. Re-order the initial 2
n
vector elements by binary bit reversal
2. Butterfly the elements two at a time, using scaling factors 1 and −1
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.138.134.229