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 つのレベルの共役があります。真ん中の 2 つは互いに元に戻し、スキップできます。

スケーリング係数

fft がユニタリであるためには、規範を維持する必要があります。 多くの ライブラリとツールはこれを無視し、逆変換で元に戻す順変換で sqrt(N) スケール ファクターを発生させます。

于 2013-06-28T12:56:12.700 に答える
0

はい。2 次元行列の変換は、単純にすべての行の個々の変換と、すべての行が変換された後、すべての列の個々の変換の組み合わせです。

ただし、FFT には多くのパフォーマンスの問題があります。特に、配列の列を変換すると、キャッシュのスラッシングの問題が発生する可能性があります。また、個々の変換を実行することは、それをサポートするマシンで SIMD 並列処理を使用するよりも効率的ではありません。したがって、通常は、1 次元の FFT から 2 次元の FFT を作成するよりも、パフォーマンスの詳細を念頭に置いて 2 次元の実装を作成する方が適切です。

于 2013-06-27T17:48:33.947 に答える
0

私が書いた Java でのこのソリューションを見てください。複雑なクラスは投稿しませんが、かなり標準的なもので、実数成分の double と虚数成分の double を保持するだけで、複素数に対する多数の数学演算があります。

方向パラメータには、順方向に -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 に答える