25

所以我知道 FFT 卷积的计算复杂度低于实际空间中的卷积。但是 FFT 卷积的缺点是什么？

内核大小是否总是必须与图像大小相匹配，或者是否有处理这个问题的函数，例如在 pythons numpy 和 scipy 包中？那么抗锯齿效果呢？

4

2 回答 2

31

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

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

要将其应用于信号f和内核g，您需要注意一些事项：

  • f并且g必须具有相同的大小才能使乘法步骤成为可能，因此您需要对内核进行零填充（或输入，如果内核比它长）。
  • 在进行 FFT 所做的 DFT 时，函数的结果频域表示是周期性的。这意味着，默认情况下，您的内核在进行卷积时会环绕边缘。如果你想要这个，那么一切都很好。但如果没有，您必须添加一个额外的内核大小的零填充以避免它。
  • 大多数（全部？）FFT 包只能在没有任何大素因数的尺寸下运行良好（性能方面）。将信号和内核大小四舍五入到二的下一个幂是一种常见的做法，可能会导致（非常）显着的加速。

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

对于 FFT 方法，您必须至少进行 3 个大小为 的 FFTf_l + g_l以及f_l + g_l乘法运算。

对于 和 的大尺寸f， FFT 的复杂性g显然更胜一筹。n*log(n)对于小内核，直接方法可能更快。

scipy.signalconvolve有两种fftconvolve方法供您玩耍。并fftconvolve为您透明地处理上述所有填充。

于 2013-08-22T15:56:10.753 回答
18

虽然快速卷积比直接形式卷积具有更好的“大 O”复杂度；有一些缺点或警告。在不久前写的一篇文章中，我对这个话题做了一些思考。

  1. 更好的“大 O”复杂性并不总是更好。对于小于特定大小的滤波器，直接形式卷积比使用 FFT 更快。确切的大小取决于所使用的平台和实现。交叉点通常在 10-40 的系数范围内。

  2. 潜伏。快速卷积本质上是一种分块算法。在转换之前一次排队数百或数千个样本对于某些实时应用程序可能是不可接受的。

  3. 实现复杂性。直接形式在内存、代码空间和编写者/维护者的理论背景方面更简单。

  4. 在定点 DSP 平台上（不是通用 CPU）：定点 FFT 的有限字长考虑使得大型定点 FFT 几乎无用。在尺寸范围的另一端，这些芯片具有专门的 MAC 指令，这些指令经过精心设计，可用于执行直接形式的 FIR 计算，从而增加 te O(N^2) 直接形式比 O(NlogN) 更快的范围。这些因素往往会创建一个有限的“最佳位置”，其中定点 FFT 对快速卷积很有用。

于 2013-08-23T15:44:31.623 回答