I have an application where I do this:

DFT->Filter->IDFT on a range

For computational performance I'm zero-padding my FFT to a power of two, but when I take the IDFT I want to get out an interpolated image instead of the zero-padded image. A minor detail, is that the IDFT is performed over only a certain frequency window.

What can I do in the Fourier domain to stretch my signal so that the IDFT returns the image without the zeroes I padded it with?


To make it clear, you padded your image in what domain ?

  • Time domain >> No problem, IFFT and then truncate will bring you the original image. It's still intact.

  • Freq domain >> Padding in the Freq domain means image resizing. You cant get your original image with 100% anymore. If you really want the original size one, the only thing you can do is to resize it back with some resampling methods.

  • $\begingroup$ I padded it in the time domain, but I want an expanded image as the output. What do I need to do? $\endgroup$ – Mikhail Feb 12 '15 at 21:37
  • $\begingroup$ I got it. Your choices are below. $\endgroup$ – pakornosky Feb 13 '15 at 4:48
  • $\begingroup$ (1) Resize image instead of zero padding (before FFT) (2) Or resize it after truncation. (3) Resize in the freq domain, use zero padding in another domain will give you the interpolated image as the output. FFT length will not be power of 2 >> slower computation But you dont have to interpolate it again. So the last choice may be less computational costs and faster. $\endgroup$ – pakornosky Feb 13 '15 at 4:57
  • $\begingroup$ Yeah, so cutting the image is fine, but what can I do in the frequency domain? There must be something! $\endgroup$ – Mikhail Feb 13 '15 at 5:55
  • $\begingroup$ There is nothing @Mikhail. Zero padding is to make FFT/IFFT faster. Not to resize the image! If you want your interpolated image instead of zero-padded image, Just interpolate data before FFT (to power-of-2 size). No need to zero-padding anymore. $\endgroup$ – pakornosky Feb 13 '15 at 7:32

to interpolate in the image domain, you don't do any zero padding there. take your entire image, FFT it, and with the properly swapped quadrants, zero pad that in the 2D-frequency domain. the IFFT it back and you have more points for the same image.

  • $\begingroup$ So, I need to match power of 2s for the first FT, so the answer isn't particularly applicable to the question. $\endgroup$ – Mikhail May 7 '16 at 5:12
  • $\begingroup$ okay. i guess what MATLAB used to do, if N was not a power of 2, was to zero pad in the image domain (as you are) and then interpolate the FFT results using the Dirichlet kernel to reduce the number of frequency-domain points to the same as the number of your original time domain points. then those you zero-pad the properly swapped quadrants to a larger sized FFT. if that isn't a power of 2, then you got the same Dirichlet interpolation to do. scaling by an arbitrary amount with only power-of-2 FFTs is a pain. may as well interpolate direct $\endgroup$ – robert bristow-johnson May 7 '16 at 6:28

First of all, common FFT libraries (which software are you using?) have FFT implementations for a lot more lengths than powers of two -- the FFTW, which is by far the most widely used in general purpose computing (and is in use by things like Matlab, FFMPEG and so forth) for example supports any length that only has prime factors smaller than 13 or so; so unless you're doing an FFT of millions of points in each direction, you don't have to pad for performance reasons.

I assume you pad before transforming:

signal -> padding -> DFT -> Filtering -> IDFT -> ?

Now, you can just truncate your result, and will get the right thing -- the IDFT works cyclic, and thus you won't be throwing away information.

Also note that if "Filter" in your original description is a FIR filter, you are convolving your signal in frequency domain, just to transform it back --- just multiply it with the fourier transform of your Filter, and you'd have done the same in the original domain of your signal, as basic Fourier theory allows you to do.

  • $\begingroup$ I know you can crop the resulting image, but I would rather have my whole buffer filled with display-able data rather perform a second memory copy or use a weird stride. $\endgroup$ – Mikhail Jan 11 '15 at 22:03
  • $\begingroup$ I'm using cufft, you need to pad for performance reasons because the function call overhead is higher when switching between different kernels. (I even benchmarked it...) $\endgroup$ – Mikhail Jan 11 '15 at 22:04
  • $\begingroup$ 1. The cropped-away part of the image doesn't contain additional information. It's a cyclic reproduction of the kept part; throw it away. 2. How large is your image? At what rates do you need to do FFTs? What is your Filter? Basically, when you say that the overhead is killing your performance, that might indicate that doing stuff on your GPU might not really be worth the copy overhead. 3. Why do you need different FFT sizes for different kernels? That sounds wrong. $\endgroup$ – Marcus Müller Jan 11 '15 at 22:23
  • $\begingroup$ Just realized: You're just doing a kernel in the FFT domain? Hell, you can save yourself the DFT->kernel->IDFT for every single image. Just zero-pad your kernel once to the size of your images, and IDFT it, and multiply it pixel-by-pixel without any (I)DFT involved! Applying a kernel is discrete convolution in frequency domain, which is identical to multiplication in pixel domain! $\endgroup$ – Marcus Müller Jan 11 '15 at 22:25
  • $\begingroup$ I mean the CUDA kernels that cufft uses to actually do the FFT butterfly. There is overhead in switching between these (for example radix 2 to radix 3 layers), but if you have a good power of two size it will only use 2 kernels which results in a notable performance increase. My code demodulates specific frequencies in a 2D signal. I don't perform any filtering. $\endgroup$ – Mikhail Jan 11 '15 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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