DFT与FFT

如果要对一个连续信号进行计算机处理，那么就必须经过离散化处理。这样对连续信号进行的傅里叶变换的积分过程就会自然地蜕变为求和过程。

一维情况

DFT:

$$X(m) = \sum^{N-1}_{n=0}x(n)e^{-i\frac{2\pi mn}{N}},m=0,1,2,…,N-1$$

IDFT:

$$x(n) = \sum^{N-1}_{m=0}X(m)e^{i\frac{2\pi mn}{N}},n=0,1,2,…,N-1$$

二维情况

$$F(u,v) =\frac{1}{MN}\sum^{M-1}_{x=0} \sum^{N-1}_{y=0}f(x,y)e^{-i 2\pi (\frac{ux}{M} + \frac{vy}{N})} \\ u=0,1,2,…,M-1,v=0,1,2,…,N-1$$

反变换为

$$f(x, y) = \sum^{M-1}_{u=0}\sum^{N-1}_{v = 0}F(u,v)e^{i2\pi(\frac{ux}{M} + \frac{vy}{N})}\\ x=0,1,2,…,M-1,y=0,1,2,…,N-1$$

其中M,N为图像的长宽，$F(u,v)$为频域

FFT 快速傅里叶变换

快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种算法

$$X(m) = \sum^{N-1}_{n=0}x(n)e^{-i\frac{2\pi mn}{N}},m=0,1,2,…,N-1$$

设 $e^{\frac{-i2\pi}{N}} = W$，$e^{\frac{i2\pi}{N}} = W^{-1}$，称其为旋转因子。

那么可以将上式改写

$$X(m) = \sum^{N-1}_{n=0}x(n)W^{mn}$$

如果将其展开，我们可以得到下列的计算方式

这种计算方式时间复杂度过高！
接下来对$W$进行分析：

$$W^{mn} = e^{\frac{-i2\pi mn}{N}} = \cos(\frac{2\pi mn}{N}) - i\sin(\frac{2\pi mn}{N})$$

$$W^{(m + lN)(n + hN)} = e^{\frac{-i2\pi (m + lN)(n + hN)}{N}} \\= \cos(\frac{2\pi (m + lN)(n + hN)}{N}) - i\sin(\frac{2\pi (m + lN)(n + hN)}{N})\\=\cos(\frac{2\pi mn}{N} + 2\pi ln + 2\pi hm + 2\pi lhN) - i\sin(\frac{2\pi mn}{N} + 2\pi ln + 2\pi hm + 2\pi lhN)\\ = W^{mn}$$

即$W^{mn}$是以$N$为周期的。进而获得以下特性：

• 对称性 $(W^{nk}_{N})^* = W^{-nk}_{N} =W^{(N-n)k}_{N}$
• 周期性 $W^{(n + N)k}_{N} = W^{nk}_{N}$
• 可约性 $W^{mnK}_{mN} = W^{nK}_{N}$

可见，离散傅里叶变换中的乘法运算有许多重复内容。1965年库利－图基提出把原始的N点序列依次分解成一系列短序列，然后，求出这些短序列的离散傅里叶变换，以此来减少乘法运算。

根据分解的特点一般有两类：一类是按时间分解，一类是按频率分解

时间分解

设 $N = 2^L$， 将$x(n)$按照n分为奇偶两组
那么有

$$x_1(r) = x(2r)\\x_2(r) = x(2r + 1)$$

那么原始变化可以写成

$$X(m) = \sum^{N-1}_{n=0}x(n)W^{mn}\\ =\sum^{N-1}_{n=0(偶数)}x(n)W^{mn} + \sum^{N-1}_{n=0(奇数)}x(n)W^{mn}$$

带入，可得

$$X(m) =\sum^{N/2-1}_{r=0}x(2r)W_N^{2rm} + \sum^{N/2-1}_{r=0}x(2r+1)W_N^{(2r+1)m}\\ =\sum^{N/2-1}_{r=0}x_1(r)W_{N/2}^{rm} + W_N^{m}\sum^{N/2-1}_{r=0}x_2(r)W_{N/2}^{rm}\\ =X_1(m) + W_N^{m}X_2(m)$$