傅里叶变换频域乘法代替空域卷积

傅里叶变换使得空域信号与频域信号实现相互转换，而在空域中运算复杂度很高的卷积运算在频域中仅为乘法，本文记录相关内容。

概述

按照通俗的语言来说,频域是时域整体的表达,频域上信号的一个点,对应的是整个时域信号该对应频率的信息,因此,在频域中的乘法,自然就对应了时域整段所有不同频率信号乘法的叠加,这就是卷积了.

• 傅里叶变换

空域卷积与频域乘法

连续信号

• 设两时域信号f(t), g(t) , 对于卷积有:

• 那么其傅氏变换为:

• 调整顺序

• 证明了空域卷积结果的傅里叶变换为两时域信号傅里叶变换结果的乘积

• 同理可以得到

离散信号

为原始图像）。

• 表示为

• 定义傅里叶变换长度为 N, W_{N}=e^{-j \frac{2 \pi}{N}}
• 对 g 做离散傅里叶变换，并适当变换

• 得到相同结论

快速计算空域卷积

卷积结果的傅里叶变换为信号傅里叶变换乘积 这一结论为空域卷积快速计算提供了可能。

• 对于二维数据，假设数据 f 与卷积核 h 的尺寸非别为 N\times N, M\times M，那么直接卷积的运算复杂度为 O(N2M2)
• 假设傅里叶变换后得到频域数据尺寸 P\times P, 乘法运算复杂度为 O(P^2)，一般 P 与 max(N,M) 具有相同的数量级，因此复杂度为 O(max(N, M)^2)，可以大大减少运算量

计算过程

• 为了计算信号f 与 h的卷积 g
• 计算f 与 h的傅里叶变换，得到：

• 相乘得到 g 的傅里叶变换：

• 反变换 G 得到 g：

参考资料

• https://www.zhihu.com/question/340004682
• https://blog.csdn.net/sw3300255/article/details/83717772/
• https://zhuanlan.zhihu.com/p/176935055
• https://blog.csdn.net/callinglove/article/details/80857827