FFT for multi-dimensional input is usually obtained by applying FFT on each dimension. FFT algorithm has an asymptotic complexity of O (N log N ). 2D FFT is especially important in the areas of image processing. Here we propose a new technique which can directly be applied on 2D image without using 1D FFT on rows and columns. It extends the concept of FFT to two dimensions. This too has an asymptotic complexity of O(N log N ).
Keywords : Fourier Transform, DFT, FFT, 2D-FFT.