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

# COnvolution and FFT

Started by ●August 2, 2005

Posted by ●August 2, 2005

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

Posted by ●August 2, 2005

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