Introduction
Frequency domain operations on spatial or time data are often used as a means for accelerating calculations. For example, when filtering a signal, one can use convolution to perform the operation in the spatial domain or transform the signal to frequency domain and apply a window function to achieve the same effect. The problem with the first approach is that for large kernels, the convolution complexity approaches O(N2). When using a smart transform algorithm like the Radix-2 Fast Fourier Transform (FFT), the complexity is reduced to O(N∙lg2N). For a large N this can become a significant difference. Another reason for performing an operation in the frequency domain is that designing the filter may be easier and more intuitive (as a very simplistic example, a simple low-pass filter is merely a nulling of the high order frequency components of the signal). In this paper we will present the demonstration of a simple image enhancement program. This operation is performed in frequency domain by first applying 2D FFT to an image, then apply a low-pass filter and convert back to special domain by a 2D IFFT operation:

Full Article (PDF)

Source Code

Here is the source code for the project: (fft2d.tar)