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) 成正比。