2

我是一个完整的信号处理新手，对于提出一个毫无头绪的问题，我提前道歉。

是否可以重用现有的 1D FFT 算法来计算 2D 逆 FFT 算法？

4

3 回答 3

3

是的。实际上，2D FFT 是按列然后按行（反之亦然）的 1-D FFT。这正是我过去所做的

线性代数

从线性代数意义上说；将 1D DFT 视为酉线性变换 F。方阵 X 的 2D FFT 很简单

F*X*F'

从 FFT 制作 IFFT

如果您没有 1D IFFT，则从 FFT 中制作一个：IFFT(x) == conj( FFT( conj( x ) ). 这源于它的统一性：

注意：对于从 1D FFT 组成的 2D IFFT，有 4 个共轭级别。中间两个相互撤消，可以跳过。

比例因子

fft 要统一，就应该保持规范。 许多 库和工具忽略了这一点，并在正向变换上产生了一个 sqrt(N) 比例因子，它们在逆向变换中撤消了这个比例因子。

于 2013-06-28T12:56:12.700 回答
0

看看我在 java 中写的这个解决方案。FFT 很棘手，但为了理解目的，我尽可能简单地写了这个。我不会发布复数类，但它非常标准 - 只为实部提供双精度，为虚部提供双精度 - 并且对复数有大量数学运算。

对于方向参数，传入 -1 表示正向，1 表示反向。在这个实现中，这就是所有的反比关系。当然，您知道要逆 2D - 您只需将 1D 逆应用于行，然后应用于列。（或相反亦然）。

//performs the FFT on a single dimension in the desired direction through recursion
    private static Complex[] RecursiveFFT(Complex[] input, double direction)
    {
        int length = input.length;
        int half_length = input.length / 2;
        Complex[] result = new Complex[length];

        if(length==1)
        {
            result[0] = input[0];
        }
        else
        {
            Complex[] sum = new Complex[half_length];
            Complex[] diff = new Complex[half_length];

            Complex temp = new Complex(0.0, direction*(2*Math.PI)/length).GetExponential();
            Complex c1 = new Complex(1,0);
            Complex c2 = new Complex(2,0);

            for(int index=0;index<half_length;index++)
            {
                sum[index] = input[index].Add(input[index+half_length]).Divide(c2);
                diff[index] = input[index].Subtract(input[index+half_length]).Multiply(c1).Divide(c2);
                c1 = c1.Multiply(temp);
            }

            Complex[] even = RecursiveFFT(sum,direction);
            Complex[] odd = RecursiveFFT(diff,direction);

            for(int index=0;index<half_length;index++)
            {
                result[index*2] = even[index];
                result[index*2 + 1] = odd[index];
            }
        }

        return result;
    }
于 2013-06-27T17:24:33.580 回答
0

是的。二维矩阵的变换只是所有行的单独变换的组合，并且在变换了所有行之后，所有列的单独变换。

但是，FFT 中存在许多性能问题。特别是，转换数组的列很可能会遇到缓存抖动问题。并且在支持它的机器上执行单个转换的效率低于使用 SIMD 并行性。因此，编写具有性能细节的二维实现通常比从一维 FFT 中组合二维 FFT 更好。

于 2013-06-27T17:48:33.947 回答