与真实空间卷积相比，FFT卷积有何缺点? [英] What are the downsides of convolution by FFT compared to realspace convolution?

问题描述

因此，我知道通过FFT进行卷积比在实际空间中进行卷积具有更低的计算复杂度.但是FFT卷积的缺点是什么?

So I am aware that a convolution by FFT has a lower computational complexity than a convolution in real space. But what are the downsides of an FFT convolution?

内核大小是否总是必须与图像大小匹配，或者是否有函数可以做到这一点?例如在pythons numpy和scipy软件包中?那抗锯齿效果又如何呢?

Does the kernel size always have to match the image size, or are there functions that take care of this, for example in pythons numpy and scipy packages? And what about anti-aliasing effects?

推荐答案

FFT卷积基于卷积定理，该状态给出给定两个函数f和g，如果Fd()和Fi()表示直接和逆傅立叶变换，以及*和.卷积和乘法，则:

FFT convolutions are based on the convolution theorem, which states that givem two functions f and g, if Fd() and Fi() denote the direct and inverse Fourier transform, and * and . convolution and multiplication, then:

f*g = Fi(Fd(d).Fd(g))

要将其应用于信号f和内核g，需要注意以下事项:

To apply this to a signal f and a kernel g, there are some things you need to take care of:

• f和g的大小必须相同，才能进行乘法运算，因此您需要对内核进行零填充.
• 在执行DFT(即FFT的功能)时，所得到的函数的频域表示是周期性的.这意味着，默认情况下，进行卷积时，内核会环绕边缘.如果您要这样做，那么一切都很好.但是，如果没有，则必须添加额外的零填充内核大小来避免这种情况.
• 大多数(全部?)FFT软件包在大小上没有任何主要因素的情况下(在性能方面)仅能很好地工作.通常将信号和内核大小四舍五入到下一个2的幂，这可能会导致(非常)显着的加速.

• f and g have to be of the same size for the multiplication step to be possible, so you need to zero-pad the kernel.
• When doing a DFT, which is what FFT does, the resulting frequency domain representation of the function is periodic. This means that, by default, your kernel wraps around the edge when doing the convolution. If you want this, then all is great. But if not, you have to add an extra zero-padding the size of the kernel to avoid it.
• Most (all?) FFT packages only work well (performance-wise) with sizes that do not have any large prime factors. Rounding the signal and kernel size up to the next power of two is a common practice that may result in a (very) significant speed-up.

如果信号大小和内核大小分别为f_l和g_l，则在时域中进行直接卷积需要g_l * (f_l - g_l + 1)乘法和(g_l - 1) * (f_l - g_l + 1)加法.

If your signal and kernel sizes are f_l and g_l, doing a straightforward convolution in time domain requires g_l * (f_l - g_l + 1) multiplications and (g_l - 1) * (f_l - g_l + 1) additions.

对于FFT方法，您必须执行3个大小至少为f_l + g_l的FFT，以及f_l + g_l乘法.

For the FFT approach, you have to do 3 FFTs of size at least f_l + g_l, as well as f_l + g_l multiplications.

对于f和g的大尺寸，FFT的n*log(n)复杂度显然是优越的.对于小型内核，直接方法可能会更快.

For large sizes of both f and g, the FFT is clearly superior with its n*log(n) complexity. For small kernels, the direct approach may be faster.

scipy.signal都具有 convolve 和 fftconvolve 方法给你玩.并且fftconvolve为您透明地处理上述所有填充.

scipy.signal has both convolve and fftconvolve methods for you to play around. And fftconvolve handles all the padding described above transparently for you.

这篇关于与真实空间卷积相比，FFT卷积有何缺点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！