Frequency vs spatial domain filtering

Question

I applied a Gaussian low pass filter on an image using MATLAB for different standard deviations and recorded the time each method takes. I saw that implementing the filter in the frequency domain is much more efficient (faster). Does anyone has an explanation for this?

Answer 1

Assuming that you use imfilter, this function performs a convolution of the original image with the kernel (the gaussian filter image).

For going into the frequency domain and back, fast fourier transform (FFT) algorithms are used, and only an image multiplication is performed in the frequency domain.

imfilter will therefore take about N.M operations, being N and M the number of pixels in the image and kernel respectively.

Each of FFT or its inverse have complexity N log_2 N, and the multiplication has complexity N, for a total complexity of approximately N log_2 N, which is much faster than the convolution.