TITLE for suggested student project:
"Efficient FFT Algorithms for multi-dimensional real-valued data"

John Daugman

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:

What savings in multi-dimensional FFT algorithms are possible as a result of these simplifications? How may these observations be exploited in new MPEG compression schemes for video sequences?

Go to John Daugman's home page.