C# 中的图像 2D FFT

• 下载源代码 - 71.2 KB

引言

快速傅里叶变换 (FFT) 是一种高效的 算法，用于计算 离散傅里叶变换 (DFT) 及其逆变换。存在许多不同的 FFT 算法，涉及广泛的数学领域，从简单的 复数运算 到 群论 和 数论；本文概述了可用的技术及其一些通用属性，而具体的算法将在下面链接的附属文章中进行描述。

DFT 将一系列值分解为不同频率的分量。此操作在许多领域都很有用（有关变换的属性和应用，请参阅 离散傅里叶变换），但直接根据定义计算它通常太慢而无法实用。FFT 是一种更快地计算相同结果的方法：使用定义以最明显的方式计算 N 点的 DFT 需要 O(N ²) 次算术运算，而 FFT 仅用 O(N log N) 次运算即可计算相同的结果。速度上的差异可能非常显著，特别是对于 N 可能达到数千甚至数百万的长数据集——实际上，在这种情况下，计算时间可以减少几个 数量级，并且改进大约与 N/log(N) 成比例。这种巨大的改进使得许多基于 DFT 的算法变得实用；FFT 在各种应用中都非常重要，从 数字信号处理 和求解 偏微分方程 到快速 大整数乘法 的算法。

Cooley–Tukey 算法

迄今为止最常见的 FFT 是 Cooley–Tukey 算法。这是一个 分治算法，它 递归地 将任意 合数 N = N₁N₂ 的 DFT 分解为许多大小为 N₁ 和 N₂ 的较小 DFT，以及 O(N) 次与复数 单位根 相乘的操作，这些乘数传统上称为 扭曲因子。

这种方法（以及 FFT 的一般思想）由 J. W. Cooley 和 J. W. Tukey 于 1965 年发表的文章推广，但后来发现（Heideman & Burrus, 1984）这两位作者独立地重新发明了 卡尔·弗里德里希·高斯 大约在 1805 年已知的算法（随后以有限形式被多次重新发现）。

Cooley–Tukey 算法最著名的用法是在每一步将变换分成两个大小为 N / 2 的部分，因此仅限于二的幂次大小，但在一般情况下可以使用任何因子分解（高斯和 Cooley/Tukey 都知道这一点）。这些分别称为 **基数-2** 和 **混合基数** 情况（其他变体，如 分裂基数 FFT，也有自己的名称）。尽管基本思想是递归的，但大多数传统实现会重新组织算法以避免显式递归。此外，由于 Cooley–Tukey 算法将 DFT 分解为更小的 DFT，因此它可以与任何其他 DFT 算法任意组合，例如下面描述的算法。

使用代码

首先，我们将选定的图像读入一个二维整数数组；我们为此使用基于指针的图像读取。代码如下

private void ReadImage()
{
    int i, j;
    GreyImage = new int[Width, Height];  //[Row,Column]
    Bitmap image = Obj;
    BitmapData bitmapData1 = 
       image.LockBits(new Rectangle(0, 0, image.Width, image.Height),
       ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    unsafe
    {
        byte* imagePointer1 = (byte*)bitmapData1.Scan0;

        for (i = 0; i < bitmapData1.Height; i++)
        {
            for (j = 0; j < bitmapData1.Width; j++)
            {
                GreyImage[j, i] = (int)((imagePointer1[0] + 
                   imagePointer1[1] + imagePointer1[2]) / 3.0);
                //4 bytes per pixel
                imagePointer1 += 4;
            }//end for j
            //4 bytes per pixel
            imagePointer1 += bitmapData1.Stride - (bitmapData1.Width * 4);
        }//end for i
    }//end unsafe
    image.UnlockBits(bitmapData1);
    return;
}

图像的 FFT 将是一个复数数组；我们需要存储这个东西，所以我们为此定义一个复数结构。

struct COMPLEX
{
    public double real, imag;
    public COMPLEX(double x, double y)
    {
        real = x;
        imag = y;
    }
    public float Magnitude()
    {
        return ((float)Math.Sqrt(real * real + imag * imag));
    }
    public float Phase()
    {            
         return ((float)Math.Atan(imag / real));
    }
}

FFT 是使用傅里叶变换的可分离性实现的。我们先计算图像行上的 FFT，然后再计算列上的 FFT。

关注点

生成傅里叶图，对复数傅里叶系数数组执行频率移动，并通过动态范围压缩，生成傅里叶图。 

最初使用的 C++ 代码可在“此处”找到（感谢 Paul Bourke） 

http://local.wasp.uwa.edu.au/~pbourke/miscellaneous/dft/

 

历史

这是我关于 FFT 的第一篇文章，欢迎提出任何建议和修改。