DSPの高速2D畳み込み

Question

で実行することを目的とした画像処理アルゴリズムを実装したい ビーグルボード. 。これらのアルゴリズムは、畳み込みを広範囲に使用します。 2D畳み込みのための優れたC実装を見つけようとしています（おそらく高速フーリエ変換を使用しています）。また、DSPがこれらの種類の操作に最適化されていると聞いたことがあるため、アルゴリズムをビーグルボードのDSPで実行できるようにしたいと思います。

私はフィールドにバックグラウンドがないので、自分で畳み込みを実装することは良い考えではないと思います（おそらく、その背後にあるすべての数学を理解している人ほど良いことはないでしょう）。 DSPの優れたCコンボリューションの実装はどこかに存在すると思いますが、それを見つけることができませんでしたか？

誰かが助けることができますか？

編集： カーネルはかなり小さいことがわかりました。その寸法は2x2または3x3のいずれかです。ですから、FFTベースの実装を探していないと思います。私はその定義を見るためにウェブ上で畳み込みを探していたので、それを簡単な方法で実装できるようになりました（畳み込みとは何かがわかりません）。私が見つけたのは、乗算積分のあるものだけで、マトリックスでそれを行う方法がわかりません。誰かが2x2カーネルケースのコード（または擬似コード）を教えてもらえますか？

Answer 1

画像とカーネルの寸法は何ですか？カーネルが大きい場合は、FFTベースの畳み込みを使用できます。そうでなければ、小さなカーネルには直接畳み込みを使用するだけです。

DSPはこれを行うための最良の方法ではないかもしれません - Mac命令があるからといって、より効率的になるという意味ではありません。ビーグル委員会のアームCPUにはネオンシムドがいますか？もしそうなら、それは行く方法かもしれません（そしてもっと楽しいです）。

小さなカーネルの場合、このような直接的な畳み込みを行うことができます。

// in, out are m x n images (integer data)
// K is the kernel size (KxK) - currently needs to be an odd number, e.g. 3
// coeffs[K][K] is a 2D array of integer coefficients
// scale is a scaling factor to normalise the filter gain

for (i = K / 2; i < m - K / 2; ++i) // iterate through image
{
  for (j = K / 2; j < n - K / 2; ++j)
  {
    int sum = 0; // sum will be the sum of input data * coeff terms

    for (ii = - K / 2; ii <= K / 2; ++ii) // iterate over kernel
    {
      for (jj = - K / 2; jj <= K / 2; ++jj)
      {
        int data = in[i + ii][j +jj];
        int coeff = coeffs[ii + K / 2][jj + K / 2];

        sum += data * coeff;
      }
    }
    out[i][j] = sum / scale; // scale sum of convolution products and store in output
  }
}

これを変更して、kの値さえもサポートできます。2つの内側ループの上限/下限に少し注意してください。

Answer 2

私はそれが話題から外れているかもしれないことを知っていますが、CとJavaScriptの類似性のために、私はそれがまだ役立つと信じています。 PS。：@Paul R Answerに触発されました。

アレイを使用したJavaScriptの2つのディメンション2D畳み込みアルゴリズム

function newArray(size){
    var result = new Array(size);
    for (var i = 0; i < size; i++) {
        result[i] = new Array(size);
    }

    return result;
}

function convolveArrays(filter, image){
    var result = newArray(image.length - filter.length + 1);

    for (var i = 0; i < image.length; i++) {
        var imageRow = image[i];
        for (var j = 0; j <= imageRow.length; j++) {

            var sum = 0;
            for (var w = 0; w < filter.length; w++) {
                if(image.length - i < filter.length) break;

                var filterRow = filter[w];
                for (var z = 0; z < filter.length; z++) {
                    if(imageRow.length - j < filterRow.length) break;
                    sum += image[w + i][z + j] * filter[w][z];
                }
            }

            if(i < result.length && j < result.length)
                result[i][j] = sum;
        }   
    }

    return result;
}

でブログ投稿全体を確認できます http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional convolution-algorithm-with-arrays-in-javascript/