Cで2D畳み込みを速く実装する方法

Question

私は視覚アルゴリズムを実装しようとしています。これには、9x9ラプラシアンガウスフィルタを使用したプレフィルタリングステージが含まれています。高速なフィルタ実装について簡単に説明しているドキュメントを参照できますか？私は、最も効率的なフィルタリングのためにFFTを使うべきだと思います。ここで

Answer 1

FFTを使用してもよろしいですか？これは高価になるアレイ全体の変換になります。すでに9x9コンボリューションフィルタを使用している場合、FFTは必要ありません。

一般的に、Cで最も畳み込みを行う最も簡単な方法は、ポインターを配列上に移動し、各ポイントで畳み込み値を合計し、データを新しい配列に書き込むループを設定することです。このループは、あなたの好きな方法（コンパイラのベクトル化、MPIライブラリ、OpenMPなど）を使って並列化することができます。境界について

：

• あなたは値が境界外で0であることを前提とした場合、ポイントのあなたの2次元配列に0の4要素の境界線を追加します。これは高価な境界を扱う `if`ステートメントの必要性を避けるでしょう。
• データが境界でラップする場合（つまり周期的な場合）、モジュロを使用するか、グリッドの反対側をコピーする4要素境界を追加します（abcdefg - > fgabcdefgabの2点）。 **注：これは、FFT **を含む任意の種類のフーリエ変換で暗黙のうちに仮定しているものです。そうでない場合は、FFTを実行する前にそれを考慮する必要があります。

9点のカーネルの最大境界の重なりがメイングリッドの外側の4点であるため、4点があります。従って、2n + 1×2n + 1カーネルにはn個の境界点が必要であった。

このコンボルーションが本当に高速で、かつ/またはグリッドが大きい場合は、プロセッサのキャッシュに保持できる小さな部分に分割して、より高速に計算することを検討してください。これはまた、実行したいGPUオフロード（このタイプの浮動小数点計算には理想的です）にも適用されます。

Answer 2

は理論リンク http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf

されており、ここで私は過去に使用したかなり良いFFTライブラリであるFFTWへのリンク、（必ずそれが適切である作るためにライセンスをチェックしてください）http://www.fftw.org/

です

あなたがしているのは、画像とカーネル（9x9マトリックス）をFFTするだけです。一緒に乗算してから、逆変換します。

しかし、9x9の行列では、実際の座標（画像のピクセルと行列の上にダブルループを置くだけ）で行う方がよい場合があります。両方の方法をお試しください！

Answer 3

実際には、画像全体を保持するのに十分な大きさのFFTサイズを使用する必要はありません。あなたは2d fftsを重ねてたくさん重ねることができます。 「高速コンボリューション」「重複保存」「重複加算」を検索できます。

ただし、9x9カーネルの場合。あなたはスピードをあげて多くの利点を見ないかもしれません。