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