"Efficient FFT Algorithms for multi-dimensional real-valued data"

**ORIGINATOR**

John Daugman

**DETAILS OF PROJECT**

Existing Fast Fourier Transform algorithms
(such as the butterfly, Cooley-Tukey) in the general case handle
complex-valued data. When the data are purely real-valued, as with
acoustical signals or images, important simplifications are possible
because of Hermitian (conjugate) symmetry: The Fourier Transform of
real-valued only data has a real part which is even-symmetric and
an imaginary part which is odd-symmetric. These symmetries in the
Fourier domain are exploited in special versions of the FFT when
dealing with real-valued inputs, such as the DCT (Discrete Cosine
Transform) which is the standard for JPEG image compression.

When transforming higher-dimensional data, such as a video sequence digitized in three dimensions (two in space and one in time), the normal FFT has a complexity of order O(N^{3}log{N}) where N is the number of pixels (as opposed to a size dependence of O(N^{6}) without FFT). This project will seek to develop variants of the FFT for data in three dimensions (or more) which exploit the following simplifications to maximize the algorithms' computational efficiency:

- the input data are purely real-valued (equally imaginary),
rather than complex-valued;
- the input data are purely positive, as in the case of image
pixel values from a CCD (light being only positive);
- the input data are purely integers, as with sampled acoustical or image pixel values, rather than floating-point values.

Go to John Daugman's home page.