# COnvolution and FFT

Started by August 2, 2005
```Hello,
I have a gaussian kernel of size [192,192] to be convoluted with an
image of size [512,512] for smoothing.
Using the FFT property that fft of a convolution is the product of the
fft of the individual terms (fft(f(t) * g(t))) = f(w)g(w), i could say
that

smoothedimage = fftinverse(fft(image) fft(kernel))

the problem i am encountering is this:
straightforward convolution is easy but very expensive in time. using
the fft property, i am not able to get the proper dimensions for the
image. because
image * kernel gives me image dimensions of [192,192] instead of
[512,512].
Please let me know where i am wrong.

Pravesh

```
```Pravesh wrote:
> Hello,
> I have a gaussian kernel of size [192,192] to be convoluted with an
> image of size [512,512] for smoothing.
> Using the FFT property that fft of a convolution is the product of the
> fft of the individual terms (fft(f(t) * g(t))) = f(w)g(w), i could say
> that
>
> smoothedimage = fftinverse(fft(image) fft(kernel))
>
> the problem i am encountering is this:
> straightforward convolution is easy but very expensive in time. using
> the fft property, i am not able to get the proper dimensions for the
> image. because
> image * kernel gives me image dimensions of [192,192] instead of
> [512,512].
> Please let me know where i am wrong.
>
> Pravesh
>
You need to pad out the Gaussian kernel to the same size as the image
before you take it's FFT.  Better yet just calculate the Gaussian filter
that you'll need in the frequency domain, since the Fourier transform of
a Gaussian is just a Gaussian.

The FFT thinks that it's periodic, so if you take your 512x512 image and
smooth it you'll smooth the right edge right into the left, and the top
edge right into the bottom.  I can think of a number of ways to deal
with this issue in the image space (mostly having to do with cleverly
truncated convolution) but I have no idea of how you could adroitly
implement this with the FFT.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
```
```Tim Wescott wrote:
> Pravesh wrote:
>
>> Hello,
>> I have a gaussian kernel of size [192,192] to be convoluted with an
>> image of size [512,512] for smoothing.
>> Using the FFT property that fft of a convolution is the product of the
>> fft of the individual terms (fft(f(t) * g(t))) = f(w)g(w), i could say
>> that
>>
>> smoothedimage = fftinverse(fft(image) fft(kernel))
>>
>> the problem i am encountering is this:
>> straightforward convolution is easy but very expensive in time. using
>> the fft property, i am not able to get the proper dimensions for the
>> image. because
>> image * kernel gives me image dimensions of [192,192] instead of
>> [512,512].
>> Please let me know where i am wrong.
>>
>> Pravesh
>>
> You need to pad out the Gaussian kernel to the same size as the image
> before you take it's FFT.  Better yet just calculate the Gaussian filter
> that you'll need in the frequency domain, since the Fourier transform of
> a Gaussian is just a Gaussian.
>
> The FFT thinks that it's periodic, so if you take your 512x512 image and
> smooth it you'll smooth the right edge right into the left, and the top
> edge right into the bottom.  I can think of a number of ways to deal
> with this issue in the image space (mostly having to do with cleverly
> truncated convolution) but I have no idea of how you could adroitly
> implement this with the FFT.

I've filtered images out to the edge with smaller kernels by using
modified kernels as the edge was approached. Yet another set is needed
for the corners. (Special corner treatment isn't needed with separable
kernels.) A scheme I came across while doping that out added a border to
the original that consisted of averages of nearby real data. The quality
didn't seem to be as good as what I described above.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```