# Catalogue of Artificial Intelligence Techniques

## 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(Nlog(N))$ and two-dimensional transforms is $O({N}_{}^{2}log(N))$ 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.

### Comments:

No comments.