## CS/ECE 545 Homework 4

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

Prove the convolution theorem for the DFT. Eq. 4.6-24. What to hand in
Hand in to class