問題タブ [convolution]

さまざまな長さの多くのファイルをブロック指向のメディア (固定サイズ、たとえば 1024 バイト) に保存しています。ファイルを読み戻すと、各ブロックが欠落しているか、正しい (ビット エラーなどがない) かのいずれかになります。欠落しているブロックはランダムであり、欠落しているブロックに順序があるとは限りません。欠落しているブロックの数が何らかのしきい値を下回っている限り、ファイル全体を再構築できるようにしたいと考えています。これはおそらくエンコード方式によって異なります。

私が見た文献のほとんどは、データ ストリーム内の一連のビット エラーを扱っているため、当てはまらないようです。

簡単な方法は、一度に N ブロックを取得し、N ブロックの XOR を含むブロックを格納することです。N ブロックの 1 つが欠落しているが、チェック ブロックが欠落していない場合、欠落しているブロックを再構築できます。

この問題に適した誤り訂正方式はありますか? 文献やコードへのリンクを歓迎します。

離散信号を離散フィルタで畳み込みたいと思います。シグナルとフィルターは、F# の float のシーケンスです。

その方法を理解できる唯一の方法は、ネストされた 2 つの for ループと、結果を格納する可変配列を使用することですが、あまり機能的ではありません。

機能しないようにする方法は次のとおりです。

画像操作ルーチンのライブラリを Java から C に移植していますが、結果を比較すると非常に小さな違いがいくつかあります。これらの違いがさまざまな言語の float 値の処理にあるというのは合理的ですか、それともまだやるべきことがあるのですか?

ルーチンは 3 x 3 カーネルを使用した畳み込みで、ピクセルの線形配列、幅、深さで表されるビットマップで操作されます。私の質問に答えるためにこのコードを正確に理解する必要はありません。

Java コード;

クランプはバンドの値を [0..255] の範囲に制限し、Color.red は (ピクセル & 0x00FF0000) >> 16 と同等です。

C コードは次のようになります。

たとえば、 xOffsets がカーネル要素の xOffset を提供するのとは少し異なります。

重要な点は、私の結果はせいぜい 1 ビットであるということです。以下はピクセル値です。

これは私のコードの問題だと思いますか、それとも言語の違いだと思いますか?

敬具、

ガブ

私はいくつかの基本的な画像フィルタリングアルゴリズムの複雑さを評価しようとしています。この理論を検証できるかどうか疑問に思いました。

Inverseのような基本的なピクセルごとのフィルターの場合、操作の数は入力のサイズ（ピクセル単位）に比例して増加します。

S=画像の辺の長さM=＃ピクセル入力とします

逆はO（M）またはO（S ^ 2）の次数です。

一方、畳み込みフィルターには、各フィルターの次のピクセル値を確立する際に畳み込む近傍のサイズを決定するパラメーターRがあります。

R=畳み込みフィルターの半径とします

畳み込みの次数はO（M *（（R + R * 2）^ 2）= O（M *（4R ^ 2）= O（MR ^ 2）

または、N =畳み込みフィルターのサイズ（近隣）をピクセル単位で指定する必要がありますか？

O（M *（N））= O（MN）

最終的に、畳み込みフィルターは、ピクセル数と近傍のピクセル数の積に線形依存します。

これが文書化されている論文へのリンクがあれば、それは大いにありがたいです。

敬具、

ギャビン

Python で 2 つの関数の畳み込みを実装する必要がありますが、SciPy/Numpy には 2 つの配列の畳み込み専用の関数があるようです。

畳み込みの正規積分表現を使用してこれを実装しようとする前に、これらの操作を実行する既に利用可能なモジュールを誰かが知っているかどうかを尋ねたいと思います。

それができない場合、SciPy が提供するいくつかの種類の統合のうち、これに最も適しているのはどれですか?

ありがとう！

これは「プログラミング」の問題ではありません。しかし、それはこのコミュニティで広く知られ、理解されていることだと確信しています。

画像 x と、はるかに小さい画像 y があり、それらの FFT を乗算して 2 つを畳み込む必要があります。しかし、それらは同じサイズではないため、周波数領域の乗算を行う方法がわかりません。

x (次元 4096 x 4096 の整数行列) の (2 次元) FFT を取得すると、周波数領域表現 X (複素数の行列であり、次元は 2048 x 2048 だと思います) が得られます。 ）。

同様に、(次元 64 x 64 の整数行列である y の 2 次元 FFT を取得します。これにより、周波数領域表現 Y (複素数の行列でもあり、次元は 32 であると思います) が得られます。 ×32）。

Numerical Recipes で fourn 関数を使用しているため、入力行列 x と y を 1 次元配列に折りたたむ必要があり、これが離散フーリエ変換 X と Y に置き換えられます。画像の二次元問題、私は一次元配列で作業しています。

まったく同じ次元の x と y の 2 つの画像を畳み込みたいとします。それはすべて非常に簡単です：

しかし、X と Y の長さが異なる場合、どのように乗算を行うのでしょうか?

1 つの可能性は、x と同じ次元になるように y をパディングすることです。しかし、これは恐ろしく非効率的です。別の可能性は、Y をパディングして X と同じ次元にすることです。しかし、これが周波数空間で何を意味するのかわかりません。

この質問の別の言い方は次のとおりです。FFT を使用して非常に異なる次元の 2 つの画像を畳み込みたい場合、それらのスペクトル (周波数領域表現) の乗算を行うことができます。その乗算を行うにはどうすればよいですか?

ありがとう、

〜マイケル。

多くの画像の各行に畳み込みフィルターを適用する必要があります。クラシックは1024x1024ピクセルの360画像です。私の使用例では、720画像560x600ピクセルです。

問題は、私のコードが記事で宣伝されているものよりもはるかに遅いことです。

素朴な畳み込みを実装しましたが、2分30秒かかります。次に、fftwを使用してFFTに切り替えました。複合体2複合体を使用し、各変換で2つの行をフィルタリングしました。今は20代くらいです。

問題は、記事が約10代を宣伝し、古典的な状態ではさらに少ないということです。ですから、畳み込みを計算するより速い方法があるかどうか、ここの専門家に尋ねたいと思います。

数値レシピは、dftで行われるソートを回避し、それに応じて周波数領域フィルター関数を適応させることを提案しています。しかし、これを行う方法のコード例はありません。

たぶん私はデータをコピーするのに時間を失うでしょう。実数2の実数変換を使用すると、データを複合値にコピーする必要はありません。しかし、とにかく0で埋める必要があります。

編集：進捗状況のフィードバックとこの問題の解決に関する詳細については、以下の私自身の回答を参照してください。

質問（正確な再定式化）：

離散非周期関数（512から2048の値）に非常に高速な畳み込みを適用するためのアルゴリズムまたはコードを探しています。どうやら、離散時間フーリエ変換が進むべき道です。ただし、データのコピーと複雑な変換は避け、バタフライの並べ替えは避けたいと思います。

私の質問が実際にはプログラミングの質問ではないことはわかっていますが、プログラミングの必要性から出てきました。斜めモーションブラーの畳み込み行列を知っている人はいますか。3x3、4x4、または 5x5 はすべて適切です。

ありがとう、

3D 畳み込みを実装するソース コードを探しています。理想的には、C++ コードまたは CUDA コードが必要です。誰かが私に素晴らしくて速い実装を教えてくれれば幸いです:-)

乾杯

Pythonを使用して畳み込みのパフォーマンスを向上させたいと考えており、パフォーマンスを向上させる最善の方法についての洞察を望んでいました。

私は現在、以下のスニペットのようなコードを使用して、scipy を使用して畳み込みを実行しています。

グレースケール (0 ～ 255 の整数値) を使用して画像データを処理していますが、現在、畳み込みあたり約 4 分の 1 秒を取得しています。私の考えは、次のいずれかを行うことでした。

できればいくつかの最適化を行って、corepy を使用してください。icc と iml で numpy を再コンパイルします。python-cuda を使用します。

誰かがこれらのアプローチのいずれかを経験したことがあるかどうか（どのような種類のゲインが典型的であるか、そしてそれが時間の価値があるかどうか）、またはNumpyで畳み込みを実行するためのより良いライブラリを誰かが知っているかどうか疑問に思っていました.

ありがとう！

編集：

Numpy を使用して C で python ループを書き直すことにより、約 10 倍高速化します。