CONVOLって何だ？

『畳み込み（たたみこみ、英: convolution）とは関数 g を平行移動しながら関数 f に重ね足し合わせる二項演算である。畳み込み積分、合成積、重畳積分、あるいは英語に倣いコンボリューションとも呼ばれる。』by Wikipedia 用途は不明ではあるけど、とりあえず「関数gと関数fのグラフで、重なった面積」らしいです。

掛け算の筆算のことです。かける数一桁ごとに、かけられる数にかけて、最後にそれらを加算して答えだしますよね。あの計算のこと。 _123 x456 ----- __738 =(100*6+20*6+3*6) ...(a) _6150 =(100*50+20*50+3*50) ...(b) 49200 =(100*400+20*400+3*400) ...(c) ------ ????? = (a) + (b) + (c) A × B のコンボリューションを計算するには桁数の二乗の手間がかかります。ところが A × B = IFFT(FFT(A) と FFT(B) の各要素同士の乗算) という性質があるので、fft/ifft 使えば n*log2(n) の手間でできるのよ。 画像にぼかしフィルタかけたりするのは、まさしくこれ!!

お二人方ありがとうございました！！