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
- 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