2D FFT ``Image Compression''

This demo is a Java port of one of the HPFA (High Performance Fortran Applications) kernels. As explained in the description of the original code:

The Fast Fourier Transform (FFT) is the most widely known example of the Spectral method for computational problems. In all such methods, one performs a linear transformation of the stated problem into another physical domain where it is hoped will be more tractable. In Fourier transformations, the mapping is from the time-domain to the frequency-domain. The FFT is widely used in the field of image processing, where one commonly describe an image in terms of intensity values in a two-dimensional matrix. The codes contained here performs a two-dimensional FFT over an example matrix in the following manner:

1. Set up the input 2-D matrix.
2. Perform FFT across the leading dimension of the matrix.
3. Transpose the matrix, using an F90/HPF intrinsic function.
4. Perform FFT again, across the leading dimension.

In our case ``transpose'' is a new operation in the class library, on a par with the ``shift'' operation used in nearest neighbour updates. As explained above, sequential FFTs are performed on all columns of the image data in parallel, then on all rows of the image in parallel. The transpose operation sits between these two phases.

After selecting the set of processors click on the ``FFT'' button. In the demo the image data is a photograph of a wolf. One of several image files (of different resolution) can be selected. In order of increasing size, the options presently are

  wolf_4.pgm
  wolf_2.pgm
  wolf.pgm

The mask width defines the size of a square centered in the Fourier space representation of the picture. You can choose to delete modes inside or outside this boundary. On clicking the ``Begin'' button, the original image is displayed then the FFT is performed. The result of the Fourier transform is also displayed as an image, mapping Fourier components into pixels. According to the masking selection, some of the components will be deleted. Finally the FFT is reversed, and the modified (``uncompressed'') version of the original image is displayed.

Once again the processor ``owning'' a particular pixel or Fourier component is coded through the colour of the cells.

Figure 4: Screens of the ``FFT'' demo.