2次元離散フーリエ変換の複雑さ

Question

2次元フーリエ変換に関する質問があります。私は現在、これの背後にある数学を理解している段階にあります。私はそれを知りません。私の知る限り、DFTの複雑さはO(N*N)です。私は次のアルゴリズムを見れば：

私はそれがどのように動作するか理解していません。我々は、変換された画像のすべてのピクセルについてこの計算を行うつもりですか？

例

1. 我々は2 * 2のイメージを持っています。我々はDFT F（x、y）をやろうとしている。この画像の各ピクセルに対して
3. 私は、新しいイメージを作成します、各画素はcorrosponding複素数値

の大きさであります

これは動作するのですか、何か不足していますか？今、私はそれを見ているので、複雑さがあります。O(N^4)

Answer 1

式は「ピクセル（u、v）でFの値を取得し、評価する（右辺の式）」を意味します。したがって、変換されたイメージ全体を取得するには、変換されたイメージのすべてのピクセルについて評価されます。

数式を使用してDFTを計算するには、すべての出力値の入力値ごとにO（1）計算を行う必要があります。 2D DFTの場合、入力ピクセル数はM * Nであり、入力ピクセルの数は（M * N）^ 2であるため、アルゴリズムは複雑さO（（M * N）^ 2）を持ちます。出力画素もM * Nである。

edit：2D行列DFTは、行と列を別々のステップで変換することによってO（NM^2 + MN^2）で計算できます。アルゴリズムはここにあります：http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html