Sorry if this question is too simplistic, but I am new to image processing and after successfully writing two programs, a convolution program and a low pass filtering program, I noticed that for approximately the same output, the low pass filtering method takes 4 times the time!
Lets assume that the image is a square of side
N. When convolving we can use an arbitrarily small kernel (out to $3\sigma$ for example) and put a Gaussian in it, say of size
M=$3\sigma$. We then have to simply pad the image and the kernel into an
N+M-1 side square array and run DFT onit, multiply it and run IDFT.
But for low pass filtering we have to create a padded square array of width
2*N. There is one less DFT required, but the one DFT and the IDFT on the array with 4 times the elements will take a significantly longer amount of time because the padded array is huge (look at Gonzalez&Woods Fig.4.36 as an example)! Since the DFT of a Gaussian kernel is also a Gaussian, then why should we use a Gaussian low pass filtering at all when it takes nearly 4 times the time (look below)?
Source code: I have put the source code in github.
I am adding some timings in my program to show what I mean. The image was 233*233 pixels. My
CPU is clocked at 3.07GHz.
For a low pass filter, note that the FFTs and IFFTs are done on an array of size 466*466:
Gaussian low pass filter timing: Padding: 0.002564 (seconds) FFT: 0.018210 (seconds) Applying filter: 0.006686 (seconds) IFFT: 0.017254 (seconds) Time for final step: 0.000550 (seconds) Total: 0.047424 (seconds)
For a convolution of the same image with a kernel of size 9*9, note that the three FFTs and IFFTs are done on arrays of size 241*241:
Gaussian convolution timing: Making the kernel: 0.000077 (seconds) Pad both to same size: 0.001389 (seconds) Padded image FFT: 0.002699 (seconds) Padded kernel FFT: 0.001866 (seconds) Multiplying: 0.000384 (seconds) IFFT: 0.002241 (seconds) Crop from padded: 0.000574 (seconds) Total: 0.011149 (seconds)