# Appendix 3

## Porous III-V Semiconductors by I. Tiginyanu, S. Langa, H. Föll and V. Ursachi

Last Updated on
2009-10-08

#### Two Dimensional Fast Fourier Transformation

2D Fourier transforms simply involve a number of one dimensional Fourier transforms. More precisely, a 2D transform is achieved by first transforming each row, i.e. replacing each row with its 1D Fourier transform. This first step yields an intermediary 'picture' in which the horizontal axis is frequency f and the vertical axis is space y. The second step is to apply 1D Fourier transform individually to the vertical line of the intermediate image. This new image will be the 2D Fourier transformation of the initial image.

A schematic representation how the 2D Fourier transform is performed is presented in Figure 9.1. From the figure it is obvious that a 2D Fourier transform from an image with n'n pixels consists of 2n one dimensional transforms. The formulas used for 2D Fourier transform (see Eqs. 68 and 69) follow directly from the definition of the Fourier transform of a continuous variable or the discrete Fourier transform of a discrete system.

In the most general situation a 2D Fourier transform takes a complex array. But, the most common application is for image processing where each value in the array represents one pixel, therefore the real value is the pixel value and the imaginary value is 0.

(68)

(69)

where f(x,y) is the initial pixel array of the image; F(u,v) is the direct Fourier transform of the image; N, M are the width and height of the image respectively. The Eqs. 68 and 69 are usually called 2D Discrete direct and indirect Fourier Transforms.

Figure 9.1: The schematic principle of 2D Fourier Transform (FT). 1D FT is taken first from the rows of the initial picture, thus an intermediate function g(u,y) is obtained. Then, the resulting 2D FT spectrum F(u,v) is obtained by taking once again the 1D FT from the of the intermediate function g(u,y).

Also, although the spatial image is a set of integers, its transform is complex (i.e., consisting of a real and an imaginary part) and non-integer. To display the transform as a frequency image, an output form must be selected from among real R, imaginary I, module (R2+I2)e(-1/2), or phase. The values are then normalized and truncated to integers for display.

As with the one dimensional Fourier transform the preferred method for computing is the so-called Fast Fourier Transform (FFT) which saves a huge amount of computation time. The number of operation used for FT is proportional to N^2 whereas for FFT is proportional to n x ln(n). In order to perform a 2D FFT instead of the much slower 2D FT the image must be transformed so that the width and height are integer-powers of 2. This can be achieved in one of the two ways, scaling the image up to the nearest integer-power of 2 or zero pad to the nearest integer-power of 2.

Fourier filtering and reconstruction is a well known technique extensively used by High Resolution Transmission Electron Microscope (HRTEM) specialists. The main steps involved in filtering HRTEM pictures are the following:

• Fourier transform is taken from a region of HRTEM image. The result will be a diffraction pattern (DP) of that region, which is nothing else but the initial image in the reciprocal space, i.e. the frequency domain.
• The DP is filtered by removing the irrelevant frequencies.
• Finally, the inverse Fourier transformation is taken from the filtered DP in order to obtain the filtered HRTEM image in real space.

This technique allows to do microscopy on the computer, i.e. the image becomes the specimen. Analyzing the computer generated DP's is the same as analyzing TEM difractograms, i.e. analyzing them it is possible to find a lot of useful information about the crystal, e.g., it is possible to find if the crystal is single crystalline, poly crystalline, amorphous etc.