image-processing - 为什么FFT会加速卷积中涉及的计算？

Question

我看到很多文献中他们说通过使用 fft 可以达到更快的卷积。我知道需要先得到fft，然后再从结果中得到ifft，但是我真的不明白为什么使用fft可以使卷积更快？

Answer 1

FFT 为足够大的滤波器加速卷积，因为卷积需要对每个输出样本进行 N 次乘法(和 N-1)次加法，而对 N 个样本块则需要 (2)N^2 次运算。

考虑到，必须通过添加零来使 FFT 处理的块大小加倍，每个块需要 (2)*(2N)*log(2N) 次运算来执行 FFT，2N 次运算来乘以 4N*log(2N)执行逆 FFT 的操作，有一个盈亏平衡点，其中 8Nlog2N <= 2N^2。

根本原因是:

1) 离散时域信号可以表示为频率之和。
2) 时域卷积 (O(N^2)) 等于频域中频率的乘积 (O(N))
3)变换是可逆的
4) 有一种方法可以在少于 N^2 的操作中将信号从时域转换为频域(这是“快速傅立叶变换”中的第一个 F)。

直接的 FT 是 O(N^2)，其中每个频域元素 F(i) = Sigma f(i) * exp(i*pi/N)。

然而，FFT 基于 exp(i*pi/N) 具有某些对称性的观察，允许将计算拆分为奇数/偶数向量。偶数向量​​可以以 O(N) 为代价来计算，而奇数向量需要一半大小的完整 FT。由于这可以重复直到 N=2，因此整体复杂度将是(与 Nlog(N) 成比例的)。