Complete by Class 6

**Discrete Fourier Transform**

Write a program which calculates the Discrete Fourier Transform of an image. The formaulæ for the DFT are given in Secton 4.5 of the text. Your program should write an image file with an image of the DFT, similar to Fig 4.24 in the text. It will be sufficient to produce the magnitude image.

As a reality check, also implement the inverse DFT. This is easy once you have written the forward DFT. Verify that you can transform an image, take the inverse transform, and get the original image back.

To make sure that your transform image is centered correctly, use the
trick of pre-multiplying the image by (-1)^{x+y}.
The simplest approach to the problem is to compute the transform along
one dimension at a time.

Test your program on the moon images.
There are two versions of the image: `moon1`

is a 256x256 image
and `moon2`

is a 64x64 version. Discrete Fourier Transforms can
be quite computationally intensive so you may find it more convenient to
use the second image.

You can find them here:

moon1.img,
moon1.tif,
moon1.gif

moon2.img,
moon2.tif,
moon2.gif

Hint: Here is how I wrote my version. It wasn't that hard taking it step by step.

- Write a complex and double precision image library. You don't have to do this, you may just use cimg.h and complex.c
- Verify that these work correctly.
- Write dft.c to take 3 inputs: input image name, output image name, and a 3rd filename that will hold the "reality check" image - the result of taking the idft of the dft. Use procedures dft() and idft() to compute the forward and inverse DFTs. In fact, they can call the same underlying procedure dft_both, which just has to know whether the kernel exponent is multiplied by -1 or +1 and the overall scale factor.
- In this initial version, have dft_both return whatever uit is given. (Should dft() idft(), and dft_both() take complex inputs?) Just make sure that this works correctly. It should!
- Now modify dft_both to compute the transform along one dimension only. Make sure this works, and that the reality check image matches the original image. Of course, the dft output won't be the real dft. Yet.
- Now extend dft_both to take transforms along both dimension. You just have to add (almost) identical code to transform along the second dimension. Make sure this works, and that the reality check image matches the original image. Now the dft output will be the real dft!
- Last, before the dft calls dft_both multiply by the checkerboard patter, and after the idft is called multiply by the same checkerboard pattern.
- Make sure this works and you're done!

**Convolution Theorem**

Hand in to class

- Your program, including enough comments so we can understnad what you have done,
- At least 2 examples of the DFT.
- Answer to the proof.

CS/ECE 545 Staff

Contents ©1997 - 2011 Norman Wittels and Michael A. Gennert