Читать книгу Rethinking Prototyping - Группа авторов - Страница 118

The idea of the procedure called Fourier Analysis (named after Jean Baptiste Joseph Fourier, 1768-1830) is that any signal (of any dimension) can be decomposed into a series of sine waves of different frequencies, magnitudes and phase angles. Fig. 3 shows the Fourier transform of a one-dimensional signal. The brightness values of one line of pixels (a) are fed into a one-dimensional matrix (b, x-axis=index, y-axis=value) from which the Fourier transform is calculated. The first eight component waves (d, wavelength 1/1, 1/2, 1/3, 1/4 …) are added up to form the inverse transform (c) being a low pass filtered approximation of the original curve. Fourier transform makes a translation from the time domain (or in the case of two-dimensional images spatial domain) into the frequency domain. The signals can be sound, heart pulses, stock market prices or raster images, where the intensities of each row and each column is computed.

Fig. 3 Fourier analysis of a one-dimensional signal: original image, one line of pixels (a), corresponding section (b), reconstructed approximation or inverse transform (c) by overlaying the first eight individual frequencies (d)

The short introduction above is meant to give the reader who is unfamiliar with Fourier analysis some necessary basic knowledge. The mathematics involved are not described in further detail here. One is referred to specialist literature amply available. Implementations are also available with linear algebra libraries for most programming languages. Using the Java linear algebra library Parallel Colt (Wendykier and Nagy 2010), the Fast Fourier Transformation (FFT) of all the four matrices are calculated, resulting in four matrices of complex numbers. Fig. 4 shows one sample input image and the corresponding FFT-matrix of its luminosity channel. Following usual conventions, the values are shifted by half of the matrix’s dimension, so that the value of column 0 / row 0 appears in the center of the image. The grey level G of each pixel is calculated as

Where M is the magnitude, R the real part and I the imaginary part. Other possible quantities to be visualized are just the real part, just the imaginary part or the phase angles A, which are calculated as

Because these values contain negative values as well, either the absolute value should be taken or the values have to be normalized to range from -1 (black) to 1 (white), 0 being a medium grey (128).

Fig. 4 Sample image Afrormosia (left) and the corresponding FFT (right) with filter boundary (red)

The real part of the Fourier transformation of a 4 x 4 matrix stores the following values:

The imaginary part of the same matrix stores the following values:

These symbolic representations show that the top-left (0,0) values of each quadrant only appear once in the real part and are all zero in the imaginary part. All the other values symmetrically appear twice (colour index in Formula 5). In the imaginary part, the second appearance of these values is multiplied with -1. The library makes use of this redundancy by offering another version of the Fourier transformation. It returns a matrix of not complex but only double numbers, the two parts being interwoven into each other. This can be of great value because of the smaller memory needs. For the study presented here however, the author decided to neglect this because on one hand, the application of filters (high-pass, low-pass, band-pass, etc.) is more comfortable on the complex number matrix. On the other hand, the interwoven method requires the matrix to be square with 2n (n ϵ ℕ) rows and columns.