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)
FFT
instead of rawDFT
? $\endgroup$FFTW
inC
. $\endgroup$