使用FFT进行卷积相比于实空间卷积有哪些缺点？

Question

26

我知道使用FFT进行卷积比在实数空间中进行卷积具有更低的计算复杂度。但是FFT卷积有哪些缺点呢？

卷积核大小是否总是要与图像大小匹配，或者是否有一些函数可以处理这个问题，例如在Python的NumPy和SciPy软件包中？还有抗混叠效应方面的考虑吗？

- ABDreverhaven

4

请注意，频域卷积仅在核的大小超过一定阈值时才更加有效。对于相对较小的核，直接卷积更为高效。 - Paul R

2个回答

19

虽然快速卷积的“大O”复杂度优于直接形式卷积，但是存在一些缺点或注意事项。我曾经在一篇文章中对此进行过思考。

更好的“大O”复杂度并不总是更好的。对于小于某个大小的滤波器，直接形式卷积可能比使用FFT更快。确切的大小取决于所用平台和实现。交叉点通常在10-40系数范围内。
延迟。快速卷积本质上是一种块状算法。在转换之前排队处理数百或数千个样本可能对某些实时应用程序不可接受。
实现复杂度。直接形式在内存、代码空间以及作者/维护者的理论背景方面更简单。
在固定点DSP平台（而非通用CPU）上：固定点FFT的有限字长考虑使得大型固定点FFT几乎无用。在大小谱域的另一个极端，这些芯片具有专门设计用于执行直接形式FIR计算的MAC指令，增加了O（N ^ 2）直接形式比O（NlogN）更快的范围。这些因素往往会创建一个有限的“甜点”，在该点上固定点FFT对于快速卷积是有用的。

- Mark Borgerding

我对第四点非常感兴趣。您能否详细说明“固定点FFT的有限字长考虑使得大型固定点FFT几乎无用”是什么意思？ - Mattia Surricchio

在每个log2（N）的FFT阶段中，固定点和可以被缩小或风险饱和。任何一种方法都有失去信息的风险--分别是低或高幅度正弦波。一些库在阶段之间交替使用方法来规避损失。无论如何，信息丢失随着更多阶段（即更大的FFT）而增加。 - Mark Borgerding

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jaime · Accepted Answer

FFT卷积基于卷积定理，该定理指出，给定两个函数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方法，您需要对至少f_l + g_l进行3次FFT，以及f_l + g_l次乘法。

对于大型f和g，FFT的复杂度显然优于其n*log(n)计算。对于小内核，直接的方法可能更快。

scipy.signal为您提供了convolve和fftconvolve两种方法供您使用。并且fftconvolve会透明地为您处理上述所有填充。