离散傅立叶变换及其反变换 - DFT & IDFT

来源于数字图像处理课

• 学了 DFT，顺手写下 Rust
• 顺便看了看 FFT

DFT 概述

原理和推导不说了，这里简单说明一下计算

对于一维情况：

数字图像是二维的，对于二维我们有

但是其实二维情况可以写成两次一维的 DFT，先对每一行做 DFT，再对每一列做 DFT。

同样的，对于逆变换也可以两次进行

一维 DFT 的直接计算时间复杂度为 。对于 的二维图像，直接计算的时间复杂度为 ；拆成行、列两次一维 DFT 后，时间复杂度为 。

FFT

对于长度为 （ 为非负整数）的序列，当 时，我们可以将其奇偶拆分

得到了两个子项，我们令

于是

将原长度为 的序列分为两长度为 的序列，分别将偶数下标序列 与奇数下标序列 按 重新编号，于是相当于对两个子数组做 DFT，因此具有递归性质

同时，由于 和 都是长度为 的 DFT，它们具有周期性：

这是因为对于整数 ，有

而且，旋转因子满足

于是，只需要计算两个长度为 的 DFT，就可以通过下面的蝶形运算得到全部 个结果：