Why use a gaussian low pass filter, when we can convolve with gaussian kernel

Question

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)

Answer 1

In practice gaussian low-pass filters are written using F.I.R. or I.I.R. filters, first the filter runs left then right on each horizontal line, then the filter runs up then down on each vertical line. It's much cheaper than doing FFTs and IFFTs.

Your two operations are not performing the same operation. The effects of the filtering around the edges will be very different. You are doing a circular convolution. For the Discrete Fourier Transform the convolution theorem says that the multiplication of fourier transforms is equivalent to convolving the image infinitely repeated/tiled in the plane. So around the left edge, for example you are blurring together some components from the right side of the picture. (For example try performing your operations on a picture that is black on the left half and white on the right half.)

Your "low pass" filter is padding the image and the kernel to try to reduce some of the edge effects. It's more expensive, but it is closer to what you would get if you did a "real" convolution of a gaussian with your image.

In your application the circular convolution effect of blurring in data from the other side of the image may be okay, but in many application it is unacceptable.

As to the reason that the FFT of an $N\times N$ image is 10 times faster than the FFT of a $2N \times 2N$ image. A 2d FFT is done by taking 1d FFTs of each horizontal line, then 1d FFTs of each vertical line. So in the $N \times N$ case you are doing $2N$ 1-d FFTs, each of which take $O(N \log N)$ for a total of $O(2N^2 \log N)$. In the $2 N \times 2 N$ case you are doing $4N$ 1-d FFTs each of which take $O(2N \log 2N)$ for a total of (a little more than) $O(8N^2 \log N)$. Add in cache effects for the larger image and 10x slower seems quite reasonable.