How to choose the size of a Laplacian of Gaussian kernel for filtering images fast?

Question

I am filtering an image using a Laplacian of Gaussian (LoG) kernel. The kernel dimensions are the same as the image. The filter operation takes very long to complete. How can I speed this up while maintaining fidelity?

The LoG kernel is not separable like the Gaussian kernel. So I cannot speed it up by filtering the image with 2 vectors successively. The only other option is to resize the kernel to get rid of insignificant multipliers on the outside. Is there a rule of thumb when choosing the size of an LoG kernel (considering image size and standard deviation of LoG)?

I am using this picture (633x900):

Filtering this in matlab using Gaussian vs. LoG gives vastly different times with the same kernel size:

>> I = imread('PICTURE.jpg');

>> tic;imfilter(double(I), fspecial('gaussian', [633,900], 50)); toc
Elapsed time is 1.129423 seconds.

>> tic;imfilter(double(I), fspecial('log', [633,900], 50)); toc
Elapsed time is 253.447840 seconds.

I just started with image processing so please excuse me if I missed out on something glaringly obvious. Thanks!

Answer 1

you can approximate LoG with Difference of Gaussians. Apply 2 Gaussians (separable) with different sigmas. (for what I know with sigma ratio 1.1) and take the difference.

Answer 2

For many image processing applications, an exact Laplacian-of-Gaussian (LoG) operator is not required. So you could as well resort to faster approximate versions, such as the one on Fast Convolution with Laplacian-of-Gaussian Masks (IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987), using separability and factoring:

We present a technique for computing the convolution of an image with LoG (Laplacian-of-Gaussian) masks. It is well known that a LoG of variance a can be decomposed as a Gaussian mask and a LoG of variance $σ_1 < σ$. We take advantage of the specific spectral characteristics of these filters in our computation: the LoG is a bandpass filter; we can therefore fold the spectrum of the image (after low pass filtering) without loss of information, which is equivalent to reducing the resolution. We present a complete evaluation of the parameters involved, together with a complexity analysis that leads to the paradoxical result that the computation time decreases when σ increases. We illustrate the method on two images.

Related question:

• Concrete use of convolution algebraic properties

Answer 3

First question, if you are not constrained to use spatial filters, it would be vastly faster to do in the frequency domain.
To elaborate, transform both the image and the filter into the frequency domain by Fourier transform, then multiply their transformed versions together. Finally, transform the result back to spatial domain by doing inversed Fourier transform.