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

■フーリエ解析（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 に対して計算量はほぼ N4に比例して膨大となります。 そこで、通常は１次元離散フーリエ変換の高速演算法である高速フーリエ変換（Fast Fourier Transform：FFT）を２重に用いた２次元FFTにより計算します。 次のアプレットは、画像データを２次元信号 f(x