• Use the 1D FFT code included in a sample program "e186//programs/myfft.c" in your own code for 2D Fourier transform of an N by N image. As discussed in class, all you need to do is to run 2N 1D transforms: first you transform each of the N columns of the image array and put the transformed columns back in the same order to form a new array, then you transform each of the N rows of this new array and put them back in the same order. The resultant N by N 2D array is the spectrum of your image. (You could also do the row transforms first and then the column transforms. The order is not important.) Remember DFT is a complex t ransform. You could use the image as the real part of the complex array and always use zeros for the imaginary part. Or, better, you can use the method (discussed in class and also in the handout on Fourier transform) to transform 2 real vectors at the same time and separate their spectra after the transform. You can save half of the operation during the column (or row) transform, after which the method can no longer be applied as the data is no longer real. (But I have an algorithm which can take this advantage all the way in the forward and inverse transforms so that computation will be reduced to half. If you are serious to know, I can provide the paper.)

  In order to visualize the spectrum to see how the energy is distributed in the frequency domain, convert the spectrum in the complex array into a real image. To do this, you first find the magnitude of each frequency component (with both real and imaginary parts), then normalize these values so that they range from 0 to 255. As most of the energy is contained in the DC component and low frequency components, you will most likely see a bright spot at the center of the spectrum (if centralized). To see better how the rest of the total energy is distributed, you can scale their magnitude nonlinearly by, say, y=pow(x, 0.3). Then save the spectrum as an image. Submit the image and its spectrum as images 1 and 2.

• Frequency domain Filtering can be achieved by multiplying the complex spectrum by a "zonal mask", such as an ideal filter mask or a Butterworth mask. Whether the filter is low-pass or high-pass can be determined by, for example, whether the spectrum is centralized or not. This way the same zonal mask can be used for both low-pass and high-pass filters. Filter the image using the following filters:

  (i) an ideal low-pass filter (ILPF).
  (ii) an ideal high-pass filter (IHPF).
  (iii) a Butterworth low-pass filter (BLPF).
  (iv) a Butterworth high-pass filters (BHPF).
  Try a few different orders for Butterworth filter to see the effect. Also try different cut-off frequencies to see the filtering effect. When considering the cut-off frequency, always keep in mind that most of the energy is concentrated a round the DC component. In other words, the radius of the filter (representing cut-off frequency) can be small for low-pass filtering (as most low frequency components are kept), and it should be large to cover enough energy for high-pass filtering (as the DC and some low frequency components are filtered out).

• Inverse transform the filtered spectrum back to spatial domain. You can use the same 1DFT code except now you need to set the switch "inverse" to 1. Submit the 4 images filtered differently as images 3, 4, 5, and 6. Comment on the differences between the high-pass and low-pass filters, and between the ideal and Butterworth filters (you should be able to observe the ringing effect). Note that you may need to do some post-processing (such as linear stretching) for the output images to look right.

Use the 1D fast DCT function contained in a sample program "/e186/programs/myfdct.c" in your own DCT 2D filtering program. Similar to the 2D DFT, here you transform the columns and then the rows to get the 2D spectrum. Print the spectrum as an image (after nonlinear scaling and normalization) to have a visual display of the spectrum. Submit this frequency spectral 2D array as image 5.

Then both high-pass and low-pass filter the image. Different from the Fourier spectrum, now the lowest frequency component, the DC component, is at the upper-left corner and the highest sequency component is at the lower-right corner of the 2D array of the spectrum. You should design your filters accordingly. To avoid the ringing effects, use any of the smooth filters discussed in class (Gaussian, Butterworth, or Hamming filter). Then inverse transform the filtered spectrum back to the spatial domain and submit the two filtered images as images 6 and 7.

Now do the same for sequency filtering. Use the provided 1D fast WHT function "/e186/programs/mywht.c" in your program. Save the sequency spectrum as an image (after rescaling and normalization) and submit it as image 8.

Then both high-pass and low-pass filter the sequency spectrum of the image in the same way as 2D DCT filtering (you can use exactly the same code). Then inverse transform the filtered spectrum back to the spatial domain. Note that the inverse transform is identical to the forward transform (How nice!). Submit the two filtered as images 9 and 10.