1
$\begingroup$

I have a binary 2D image that consists of 95% black pixels with a few white pixels scattered about, and I want to convolve it with a 2D gaussian kernel. I'm hoping to exploit its sparsity to improve the efficiency of the blurring.

For simplicity, lets consider my signal to be 1-dimensional. Since the signal is just a superposition of a relatively small number of shifted Kronecker deltas, is there a shortcut for computing it's discrete Fourier transform?

(Apologies in advance for asking a probably obvious question, I'm a lowly computer scientist, not a math major :-) ).

  • 3
    This question would fit nicely at [dsp.stackexchange.com](http://dsp.stackexchange.com/)2012-01-16

1 Answers 1

1

I think the answer here depends on several things:

How long is you array in total and what is the variance of the Gaussian? If the array is not too large, convolution by fft may be slower than direct computation. However, if the Gaussian is very narrow then an overlap-add procedure may be fast.

But since the performance of the fft in practice is difficult to estimate (if you use fftw) I think that you should just try what approach works fastest...