Python 实现图象快速傅里叶变换以及离散余弦变换

图象的正交变换在数字图象的处理与分析中起着很重要的作用，被广泛利用于图象增强、去噪、压缩编码等众多领域。

1. 傅里叶变换试验原理文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

对一幅图象进行 离散傅里叶变换 （DFT），可以得到图象信号的傅里叶频谱。二维 DFT 的变换及逆变换公式如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

DFT 虽然解决了频域离散化的问题，但运算量太大。从公式中可以看到，有两个嵌套的乞降符号，显然直接计算的繁杂度为 \\(O(n^2)\\) 。为了加快傅里叶变换的运算速度，后人提出 快速傅里叶变换 （FFT），即蝶形算法，将计算 DFT 的繁杂度降低到了 \\(O(n\\log n)\\) 。文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

FFT 应用傅里叶变换的数学性质，采取分治的思想，将一个 \\(N\\) 点的 FFT，变为两个 \\(N/2\\) 点的 FFT。以一维 FFT 为例，可以表示如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

其中， \\(G(k)\\) 是 \\(x(k)\\) 的偶数点的 \\(N/2\\) 点的 FFT， \\(H(k)\\) 是 \\(x(k)\\) 的奇数点的 \\(N/2\\) 点的 FFT。文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

这样，通过将原问题不断分解为两个一半范围的子问题，然后计算相应的蝶形运算单元，终究得以完成整个 FFT。文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

算法步骤文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

本次试验中，一维 FFT 采取递归实现，且仅支撑长度为 2 的整数幂的情况。文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

算法步骤如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

1. 检查图象的尺寸，如果不是 2 的整数幂则直接退出。
2. 对图象的灰度值进行归一化。
3. 对图象的每一一行执行一维 FFT，并保留为中间结果。
4. 对上一步结果中的每一一列执行一维 FFT，返回变换结果。
5. 将零频份量移到频谱中心，并求绝对值进行可视化。
6. 对中心化后的结果进行对数变换，以改善视觉效果。

主要代码一维 FFT文章源自微观生活（93wg.com）微观生活-https://93wg.com/11807.html

def fft(x): n = len(x) if n == 2: return [x[0] + x[1], x[0] - x[1]] G = fft(x[::2]) H = fft(x[1::2]) W = np.exp(-2j * np.pi * np.arange(n//2) / n) WH = W * H X = np.concatenate([G + WH, G - WH]) return X

二维 FFT

def fft2(img): h, w = img.shape if ((h-1) & h) or ((w-1) & w): print(&

一维离散余弦变换与离散傅里叶变换拥有类似性，对离散傅里叶变换进行下式的修改：

式中

由上式可见， \\(\\sum\\limits_{x=0}^{2M-1}f_e(x)e^{\\frac{-j2ux\\pi}{2M}}\\) 是 \\(2M\\) 个点的傅里叶变换，因而在做离散余弦变换时，可将其拓展为 \\(2M\\) 个点，然后对其做离散傅里叶变换，取傅里叶变换的实部就是所要的离散余弦变换。

算法步骤

基于上述原理，二维 DCT 的实现重用了上文中的一维 FFT 函数，并依据公式做了一些修改。

算法步骤如下：

1. 检查图象的尺寸，如果不是 2 的整数幂则直接退出。
2. 对图象的灰度值进行归一化。
3. 对图象的每一一行进行延拓，执行一维 FFT 后取实部，乘以公式中的系数，并保留为中间结果。
4. 对上一步结果中的每一一列进行延拓，执行一维 FFT 后取实部，乘以公式中的系数，返回变换结果。
5. 对结果求绝对值，并进行对数变换，以改善视觉效果。