与realspace卷积相比,FFT卷积的缺点是什么？

Question

所以我知道FFT的卷积比现实空间中的卷积具有更低的计算复杂度.但是FFT卷积的缺点是什么？

内核大小是否始终必须与图像大小匹配,或者是否有用于处理此问题的函数,例如在pythons numpy和scipy包中？那么抗锯齿效果呢？

Answer 1

FFT卷积是基于卷积定理,其中指出givem两个函数f和g,如果Fd()与Fi()分别表示直接和逆傅立叶变换,*和.卷积和乘法,则:

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

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

f并且g必须具有相同的大小才能使乘法步骤成为可能,因此您需要对内核进行零填充.
当进行DFT时,这就是FFT所做的,所得到的函数的频域表示是周期性的.这意味着,默认情况下,在进行卷积时,内核会绕过边缘.如果你想要这个,那么一切都很棒.但如果没有,你必须添加额外的零填充内核大小以避免它.
大多数(全部？)FFT软件包只能在没有任何大质数因子的情况下很好地工作(性能方面).将信号和内核大小舍入到下一个2的幂是常见的做法,可能导致(非常)显着的加速.

如果您的信号和内核大小是,f_l并且g_l在时域中进行简单的卷积需要g_l * (f_l - g_l + 1)乘法和(g_l - 1) * (f_l - g_l + 1)加法.

对于FFT方法,您必须至少进行3次FFT大小f_l + g_l,以及f_l + g_l乘法.

对于大尺寸两个f和g的FFT是其明显优于n*log(n)复杂.对于小内核,直接方法可能更快.

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

Answer 2

虽然快速卷积比直接形式卷积具有更好的"大O"复杂度; 有一些缺点或警告.我之前写过一篇文章,我对这个主题做了一些思考.

更好的"大O"复杂性并不总是更好.对于小于特定大小的滤波器,直接形式卷积可能比使用FFT更快.确切的大小取决于所使用的平台和实现.交叉点通常在10-40系数范围内.
潜伏.快速卷积本质上是一种块状算法.在转换它们之前一次排队数百或数千个样本对于某些实时应用来说可能是不可接受的.
实施复杂性.直接形式在内存,代码空间和编写者/维护者的理论背景方面更简单.
在定点DSP平台(不是通用CPU)上:定点FFT的有限字大小考虑使得大的定点FFT几乎无用.在尺寸范围的另一端,这些芯片具有专门用于执行直接形式FIR计算的MAC指令,增加了te O(N ^ 2)直接形式比O(NlogN)更快的范围.这些因素倾向于创造一个有限的"最佳点",其中定点FFT对快速卷积很有用.