本文最后更新于：2024年5月7日 下午
傅里叶变换使得空域信号与频域信号实现相互转换，而在空域中运算复杂度很高的卷积运算在频域中仅为乘法，本文记录相关内容。
概述
按照通俗的语言来说,频域是时域整体的表达,频域上信号的一个点,对应的是整个时域信号该对应频率的信息,因此,在频域中的乘法,自然就对应了时域整段所有不同频率信号乘法的叠加,这就是卷积了.
空域卷积与频域乘法
连续信号卷积
- 设两时域信号$f(t), g(t)$ , 对于卷积有:
$$
f(t) * g(t)=\int_{-\infty}^{\infty} f(\tau) * g(t-\tau) d \tau
$$
- 那么其傅氏变换为:
- 调整顺序
-
反向计算也可以得到相同结果
-
证明了空域卷积结果的傅里叶变换为两时域信号傅里叶变换结果的乘积
$$
f * g \longleftrightarrow F \cdot G
$$
- 同理可以得到
$$
f \cdot g \longleftrightarrow F * G
$$
连续信号互相关
- 两时域信号$f(t), g(t)$ , 对于互相关有:
$$
f(t) \otimes g(t)=\int_{-\infty}^{\infty} f(\tau) * g(t+\tau) d \tau
$$
- 按照同样方法推导其在频域的样子：
$$
\begin{array}{c}
F[f(t) \otimes g(t)]&=&\int_{-\infty}{\infty}\left[\int_{-\infty}{\infty} f(\tau) g(t+\tau) d \tau\right] e^{-j w t} d t \
&=&\int_{-\infty}^{\infty} f(\tau)\left[\int_{-\infty}^{\infty} g(t+\tau) e^{-j w t} d t\right] d \tau \
&=& \int_{-\infty}^{\infty} f(\tau) e^{j u \tau} d \tau\left[\int_{-\infty}^{\infty} g(t+\tau) e^{-j w(t+\tau)} d(t+\tau)\right] \
&=&F^[f(\tau)] F[g(t-\tau)] \
&=&F^(w) G(w)
\end{array}
$$
离散信号
假设有一个函数$g$，表示空域离散信号$f$ 与 $h$的卷积（可以看作 $h$ 是滤波器，$f$为原始图像）。
$$
g=f * h
$$
- 表示为
$$
g(n)= \sum_{m=-\infty}^{+\infty} f(m)h(n-m)
$$
- 定义傅里叶变换长度为 $N$, $ W_{N}=e^{-j \frac{2 \pi}{N}} $
- 对 $g$ 做离散傅里叶变换，并适当变换
- 得到相同结论
快速计算空域卷积
卷积结果的傅里叶变换为信号傅里叶变换乘积 这一结论为空域卷积快速计算提供了可能。
-
对于二维数据，假设数据 $f$ 与卷积核 $h$ 的尺寸分别为 $N\times N, M\times M (N>M)$，那么直接卷积的运算复杂度为 $O(N ^ 2 M ^ 2)$
-
假设通过傅里叶变换计算卷积
- 需要将卷积核 pad 到和 $f$ 一样大，数据均为 $N\times N$
- 后得到频域数据尺寸 $N\times N$, 时间复杂度为$O(N^2log(N))$
- 乘法运算复杂度为 $O(N^2)$
- 因此复杂度为 $O(N^2logN)$
-
因此若 $logN < M^2$ 时会极大地减少运算量，也就是说当卷积核和数据尺寸接近时，使用频域计算卷积可以大幅加速。
计算过程
- 为了计算信号$f$ 与 $h$的卷积 $g$
- 计算$f$ 与 $h$的傅里叶变换，得到：
$$
F=DFT[f(n)],H=DFT[h(n)]
$$
- 相乘得到 $g$ 的傅里叶变换：
$$
G=F \times H
$$
- 反变换 $G$ 得到 $g$：
$$
g=IDFT(G)
$$
参考资料
文章链接：
https://www.zywvvd.com/notes/study/math/fourier-transform/fourier-conv/fourier-conv/
“觉得不错的话，给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付