image-processing - FFT が畳み込みに関連する計算を高速化するのはなぜですか?

Question

私は、fft を使用することで、より高速な畳み込みに到達できると彼らが言う多くの文献を見ています。結果からfftを取得してからifftする必要があることは知っていますが、fftを使用すると畳み込みが高速になる理由が本当にわかりませんか?

Answer 1

FFT は、十分な大きさのフィルターの畳み込みを高速化します。これは、畳み込みでは各出力サンプルに対して N 回の乗算 (および N-1) の加算が必要であり、逆に、N サンプルのブロックに対して (2)N^2 演算が必要なためです。

ゼロを追加して FFT 処理のブロック サイズを 2 倍にしなければならないことを考慮すると、各ブロックは FFT を実行するために (2)*(2N)*log(2N) 演算、乗算するために 2N 演算、そして再び 4N*log(2N) を必要とします。逆 FFT を実行するための操作では、8Nlog2N <= 2N^2 のブレーク イーブン ポイントがあります。

基本的な理由は次のとおりです。

1) 離散時間領域信号は、周波数の和として表すことができます。
2) 時間領域での畳み込み (O(N^2)) は、周波数領域での周波数の乗算 (O(N)) に等しい 3) 変換は可逆
4) 信号を時間領域から周波数領域に変換する方法が存在するN^2 未満の演算 (「高速フーリエ変換」の最初の F です)。

単純な FT は O(N^2) で、各周波数領域要素 F(i) = シグマ f(i) * exp(i*pi/N) です。

ただし、FFT は、exp(i*pi/N) に特定の対称性があるという観察に基づいており、計算を奇数/偶数ベクトルに分割できます。偶数ベクトルは O(N) を犠牲にして計算できますが、奇数ベクトルは半分のサイズの完全な FT を必要とします。これは N=2 になるまで繰り返すことができるため、全体的な複雑さは (比例して) Nlog(N) になります。