COnvolution and FFT

Started by Pravesh 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. �����������������������������������������������������������������������