FFTs in Graphics and Vision
600.660
Assignment 1

Due: Sunday (02/22/15)
You can download the code stub from here.
1. Implement the 1D FFT: Implement the O(n logn) algorithm for computing the forward and inverse Fourier transforms. To help you on your way, a starting code stub is provided for you in FFT1D.cpp. You will need to implement the methods ForwardFFT and InverseFFT which compute the forward and inverse Fourier transforms.

To run the code, you need to specify the input 1D array name:

`% FFT1D --in in.array`

The code will then test to see that:

• Running the Forward and Inverse transforms gives you back the original array.
• The computed coefficients satisfy the conjugacy relations.
• The computed coefficients are the same as those returned by the FFTW algorithm.
Notes:
• The code in Complex.h and Complex.inl provides a template class for complex numbers. It may be helpful to familiarize yourself with the class as most of the simply arithmetic operations you will want to perform have already been implemented.
• The FFT transforms that you implement should be un-normalized. First of all, it makes implementing the transforms a bit faster. Second, it ensures that the computed coefficients should be the same as those computed by the FFTW.
• Keep in mind that since you are working with real-valued data, the FourierKey1D class will only store half of the coefficients. Making a call to FourierKey1D::size( ) will tell you exactly how many coefficients there are. Do not confuse this with FourierKey1D::resolution( ) which returns the resolution of the array from which the coefficients are computed.
• Finally, you will actually need some input arrays to work with. Some example arrays are provided for you. These are: bike.array, bunny.array, car.array, cow.array, plane.array, and rose.array. If you are working under windows, a visualization tool called CircularArrayViewer.exe is provided in the Executables.zip archive.

2. Image Processing: For this part of the assignment, you will need to implement the following image processing filters discussed in class:
• Gaussian blurring
• Boundary detection using gradient magnitudes
• Boundary detection using the Laplacian
• Gaussian sharpening
A code base for this project is provided in ImageProcessing.cpp. The code reads in the names of the input and output files and parses the command line arguments specifying which of the image processing methods are to be run. Your job is to implement the missing code in main. To run the code, you will have to specify the input and output file-names for the images (24-bit bmp and jpeg extensions are supported):
`% ImageProcessing --in in.[bmp/jpeg/jpg] --out out.[bmp/jpeg/jpg]`
and the types of image processing operations you would like performed:
• `--smooth <standard deviation>`: Smooth the image using a Gaussian with the specified standard deviation.
• `--gradient`: Compute the boundary of the image by computing the magnitude of the gradient. To do this, you will have to you the FFT to separately compute the partial derivatives with respect to x and y, and then set the value of a pixel in the output image equal to the size of the gradient at that point.
• `--cLaplacian`: Compute the boundary of the image by computing the image Laplacian.
• `--dLaplacian <standard deviation>`: Compute the boundary of the image by computing the discrete image Laplacian. To do this you will have to compuate a smoothed version of the image using the specified standard deviation, and then subtract off the original pixel values from the smoothed ones.
• `--sharpen <standard deviation>`: Sharpen the image using a Gaussian sharpening filter. This is, in effect, the process of undoing a Gaussian smoothing with a fixed standard deviation.
Notes:
• Keep in mind that in addition to the scaling factor that's provided to account for the lack of normalization in the Fourier transform, you will also have to perform the appropriate scaling to account for the correlation.
• Because the data is real-valued, the FourierKey2D class only stores half of the information. Specifically, there are resolution( )xsize( ) entries in the key.
• Keep in mind that if the initial image is of size nxn then the Fourier coefficients are themselves periodic, modulo n. This means that the k-th Fourier coefficient is the same as the (k+n)-th Fourier coefficient. This is important to remember in two steps:
• When specifying the values of the Gaussian, make sure that for an index k>n/2, you set the value of the Gaussian array to the value of the Gaussian at k-n.
• When computing the derivative, you want to minimize the contribution of high-frequency components, so for a Fourier coefficient at index k>n/2, make sure to treat that as the Fourier coefficient corresponding to the function exp(i (k-n) x), not exp(i k x).