FFTによる畳み込みの短所は、実空間畳み込みと比べて何ですか？

Question

私は、FFTによるコンボリューションは、実空間でのコンボリューションよりも計算の複雑さが低いことを認識しています。しかし、FFTコンボリューションの弱点は何ですか？

カーネルサイズは常にイメージサイズと一致する必要がありますか、これを処理する関数がありますか？たとえば、pythons numpyやscipyパッケージの場合は？アンチエイリアス効果はどうですか？

Answer 1

FFT畳み込みは述べconvolution theorem、に基づいているgivem二つの機能fとg、Fd()とFi()ダイレクトを表し、逆フーリエ変換すると、と*と.次いで畳み込み乗算、その：

f*g = Fi(Fd(d).Fd(g)) 

：

は信号fとカーネルgにこれを適用するには、あなたがの世話をする必要があるいくつかのものがあります

• fとgは、乗算ステップを可能にするために同じサイズでなければならないため、カーネルをゼロパッドする必要があります。
• FFTが行うDFTを実行するとき、関数の結果の周波数領域表現は周期的です。つまり、デフォルトでカーネルは畳み込みを行うときにエッジを囲むことを意味します。あなたがこれを望むなら、すべてが素晴らしいです。しかしそうでなければ、それを避けるためにカーネルのサイズに余分なゼロパディングを加えなければなりません。
• ほとんどの（すべて？）FFTパッケージは、大きなプライムファクタを持たないサイズでうまくいく（パフォーマンス上）。シグナルとカーネルサイズを2の次の累乗に丸めることは、（非常に）大幅なスピードアップを招く可能性のある一般的な方法です。時間領域での簡単なたたみ込みを行って

あなたのシグナルとカーネルサイズがある場合はf_lとg_lは、g_l * (f_l - g_l + 1)乗算と加算が必要(g_l - 1) * (f_l - g_l + 1)。

FFTの手法では、少なくともf_l + g_lのサイズとf_l + g_lの乗算の3つのFFTを実行する必要があります。

fとgの両方のサイズが大きい場合、FFTはその複雑さが明らかに優れています（n*log(n)）。小さなカーネルでは、直接的なアプローチがより高速になるかもしれません。

scipy.signalには、convolveとfftconvolveの両方の方法があります。そして、fftconvolveは、上記のすべてのパディングを透過的に処理します。

Answer 2

高速畳み込みは直接型畳み込みよりも "大きなO"複雑性が優れていますが、いくつかの欠点や注意点があります。私はan articleのこの話題についていくつか考えました。私はしばらく前に書きました。

1. "big O"の複雑さが改善されていると、必ずしも優れているとは限りません。ダイレクトフォームコンボリューションは、特定のサイズより小さいフィルタに対してFFTを使用するよりも高速になります。正確なサイズは、使用されるプラットフォームと実装によって異なります。交叉点は通常10〜40の係数範囲にある。

2. 遅延。高速畳み込みは本質的にブロックワイズアルゴリズムです。数百または数千のサンプルを変換する前に一度にキューイングすることは、リアルタイムアプリケーションによっては受け入れられない場合があります。

3. 実装の複雑さ。ダイレクトフォームは、メモリ、コードスペース、ライター/メンテナーの理論的背景の面でより簡単です。

4. 固定小数点DSPプラットフォーム（汎用CPUではなく）：固定小数点FFTの制限されたワードサイズを考慮すると、大きな固定小数点FFTはほとんど役に立たなくなります。サイズスペクトルのもう一方の端では、これらのチップは、直接形FIR計算を実行するために設計された特殊なMAC命令を持っており、te O（N^2）の直接形式がO（NlogN）より高速です。これらの要因は、固定小数点FFTが高速畳み込みに役立つ限定された「スイートスポット」を生成する傾向があります。