■フーリエ解析（12）：　２次元高速フーリエ変換（FFT）
　　　　　　　　　　　　　　〜 画像データ処理の例 〜

　関数 f(x, y)の２次元離散フーリエ変換（DFT）、離散フーリエ逆変換（IDFT）は次式で定義されます。

F (k, l) = ��x=0M-1��y=0N-1 f (x, y)WM xk WN yl 　　f (x, y) = (1/(MN))��k=0M-1��l=0N-1 F (k, l)WM -xkWN -yl 　　ここで、 　　　WM = e-j2π/M, 　　　WN = e-j2π/N

　２次元の離散フーリエ変換、離散フーリエ逆変換ではデータ量 N に対して計算量はほぼ N⁴に比例して膨大となります。　そこで、通常は１次元離散フーリエ変換の高速演算法である高速フーリエ変換（Fast Fourier Transform：FFT）を２重に用いた２次元FFTにより計算します。

　次のアプレットは、画像データを２次元信号 f(x, y)と考えて、２次元のFFT および IFFTを行って結果を表示するものです。　演算時間の比較のため、通常のフーリエ変換（DFT、IDFT）、離散コサイン変換での計算もできます。

　２次元DFTの式：
　　F (k, l) = ��_x=0^M-1��_y=0^N-1 f (x, y)W_M ^xk W_N ^yl

について、右辺のｙに関する和を展開すると次のようになります。
　　F (k, l) = W_N ⁰��_x=0^M-1 f (x, 0)W_M ^xk + W_N ^l��_x=0^M-1 f (x, 1)W_M ^xk +

　　　　　　　…　+ W_N ^l(N-1)��_x=0^M-1 f (x, N-1)W_M ^xk

　　　　　　　= W_N ⁰F₀ + W_N ^lF₁ + … + W_N ^l(N-1)F_N-1

　　　ここで、　F_i = ��_x=0^M-1 f (x, i)W_M ^xk

　F_iは、第i列における１次元DFTであり、従って２次元DFTはｙ一定の各列における1次元FFTを実行して得られる行列の各行に対して１次元FFTを行うことで実現できることがわかります。
　N x Nピクセルの画像に対する２次元DFTの計算量はN⁴に比例しますが、これを２次元FFTで行うと計算量は 2N²log₂N に削減されます。

　下表はデータ量N と両者による計算量の比較です。

データ量 N による計算量の比較（概略）

データ量 N	計算量（２次元FFT／２次元DFT）
100	1/750
200	1/2,600
500	1/14,000
1000	1/50,000
2000	1/180,000
5000	1/1,000,000