# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

## Fourier Transform

Keywords: frequency domain, linear systems theory

### Categories: Pattern Recognition and Image Processing

Author(s): Fritz Seytter

A method that transforms a (spatial or temporal) signal into the frequency domain by exploiting the fact that a signal can be represented as the sum (or integral) of a (usually infinite) series of weighted sinusoidal functions. The Fourier transform is useful for analysing and understanding the influence of linear operations on temporal or spatial signals. A good qualitative understanding about how a certain operation influences the signal in the frequency domain often helps to estimate limitations or possibilities that are otherwise not so easily recognised. This is most important for low-level vision applications. Fourier transforms are the most important tool for linear systems theory. The Fourier transform is quite tedious computationally: i.e., the computational complexity of most one-dimensional transforms is $O\left(Nlog\left(N\right)\right)$ and two-dimensional transforms is $O\left({N}_{}^{2}log\left(N\right)\right)$ where typically $N>250$ . Hence, it is usually impractical to implement the transform in software, although multi-processor systems are now being used. Alternatives include use of special-purpose hardware or optical techniques.

### References:

• Gaskill, J.D., Linear systems, Fourier transforms, and optics , Wiley, New York and Chichester , 1978.