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.

Convolution Theorem

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

CS/ECE 545 Staff
Contents ©1997 - 2011 Norman Wittels and Michael A. Gennert