**Discrete Fourier Transform (DFT)**
**Fast Fourier Transform (FFT)**

In this lab, we will see some of the applications of DFT and FFT. We learned in class about the 1-D and 2-D discrete Fourier Transforms. In our textbook, the 1-D Discrete Fourier Transform (DFT) is denoted by F(u) as:

In the first equations i = 0, 1,..., N-1 represent the number of samples of the continuous function and in the second equation those corresponds to their corresponding Discrete Fourier Transform.

Any x, x_{i}, can be computed using i*del (x), where del(x)
is the width of the grid on x direction. Any value of u, u_{i},
can be computed using u_{0}+i*del(u), where del(u) is defined as:
del(u) = 1/[N.del(x)].

The 2-D DFT is defined as:

The 2-D IDFT is defined as:

Similar to the 1-D case, any x or y can be computed using the initial value and the number of grids that that point is away from the origin. Thus,

x_{i} = i*del (x) and y_{j} = j*del (y).

Where del(u) = 1/[N.del(x)] and del(v) = 1/[N.del(y)].

MATLAB has some build in functions to do the 1-D and 2-D DFT. However, if the grid size is a power of 2, the calculation is done in a faster scheme called Fast Fourier Transform. By default, MATLAB attempts to solve the problem using FFT, however, in the case that the grid size is not a power of, then it uses DFT.

**Please note that there is a minor difference between the way MATLAB
uses the constant in front of the transform and the way the textbook uses
it. In the text 1/N and 1/MN appears in front of the DFT, i.e., F(u)
and F(u,v), while in MATLAB these are appearing in front of f(x)
or f(x,y). So to get the answers to be the same as what you get
in the textbook, you can divide the resulting transform by N or NM depending
on the dimension or in the inverse case multiply the result by N or MN
depending on the dimension.**

That being said, let's solve some examples.

Suppose we have a 1-D function defined as:

f =

1 1
0 0

Note that to make the number of points a power of two, I have added
the zeros.

**>> F = fft(f)**

F =

2.0000
1.0000 - 1.0000i 0
1.0000 + 1.0000i

As you can see some answers have both the real and the imaginary parts.

Can you confirm these answers by hand calculation?

F(0) = f(0).exp[-j2*pi*(0)(0)/4] + f(1).exp[-j2*pi*(0)(1)/4]
+ f(2).exp[-j2*pi*(0)(2)/4] + f(3).exp[-j2*pi*(0)(3)/4]

F(1) = f(0).exp[-j2*pi*(1)(0)/4] + f(1).exp[-j2*pi*(1)(1)/4]
+ f(2).exp[-j2*pi*(1)(2)/4] + f(3).exp[-j2*pi*(1)(3)/4]

F(2) = f(0).exp[-j2*pi*(2)(0)/4] + f(1).exp[-j2*pi*(2)(1)/4]
+ f(2).exp[-j2*pi*(2)(2)/4] + f(3).exp[-j2*pi*(2)(3)/4]

F(3) = f(0).exp[-j2*pi*(3)(0)/4] + f(1).exp[-j2*pi*(3)(1)/4]
+ f(2).exp[-j2*pi*(3)(2)/4] + f(3).exp[-j2*pi*(3)(3)/4]

As you perhaps noticed, in order to be consistent with the MATLAB calculations, I did not use the (1/N). The difference is that constant, if you would use it. We also could use F = fft(f)/4 to get the answer from MATALB to be consistent with that of the book.

Now let's try a 2-D case. Suppose we have the following 2-D array: Suppose we have the following data:

2 4

4 2

>> f = [2 4

4 2]

f =

2
4

4
2

**>> F = fft2(f)**

F =

12
0

0
-4

Can you confirm these answers by hand calculation?

The Inverse Fourier Transform of F should result
into what we began with.
**>> FI = Ifft2(F)**

FI =

2
4

4
2

Using a similar procedure, we can transfer an image.

**>> T = imread('text.tif');**
**>> FT = fft2(T);**
**>> FT = real(FT);**
**>> imshow(FT);**

**>> IT = ifft2(FT);**
**>> IT = real(IT);**
**>> imshow(IT);**

Do you get the same image back?

One of the application of Fourier Transform is to locate features in
an image. For instance occurrences of a letter in a text. The
MATLAB Image Processing Toolbox has an example in which the letter **a
**has been extracted from a sample text. The procedure for extracting
that a letter is explained below. Before you try this please copy
two image file e.jpg and n.jpg to your directory. Here is how:

cp ~rt/3531_s01/codes/e.jpg . (You need the .).

cp ~rt/3531_s01/codes/n.jpg .

These two images are the images of letters "n" and "e" with the same size as they appeared in the text.jpg image file. The idea (if it works) is to find where the location of "e" or "n" is in the image shown below.

The correlation of the image e.jpg and text.jpg can be computed by:

1) Rotate image e.jpg by 180 degree.

2) Suppose image e.jpg is m-by-n size and text.jpg is p-by-q.
Then, the convolution of the two will be at least of size (m+p-1)-by-(n+q-1)
size. Thus, we zero pad both images to these sizes. It is better
to round the size up to a number that is power of 2, to make use of FFT.
For your information, text.jpg is a 256-by-256 image, e.jpg is a 9-by-11
image, and n.jpg is an 11-by-11 image. So the next power of 2 is 512.

3) Compute the 2-D DFT of both images.

4) Multiply the two resulting DFTs together (.*) to get the convolution.

5) Use IFFT to compute the inverse of the resulting matrix.

6) Cut the extra zeros, use the maximum of mxn or pxq dimension.

7) To view the resulting matrix, you need to take the real part.

8) Display the result.

This should generate the image with bright dot points representing the
location of occurrences of e in the text.jpg image.