Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :-) ).

share|cite|improve this question
This question would fit nicely at – user6701 Jan 16 '12 at 15:22

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...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.