用于 DSP 的快速 2D 卷积

Question

我想实现一些图像处理算法，这些算法旨在在 beagleboard 上运行。这些算法广泛使用卷积。我正在尝试为 2D 卷积找到一个好的 C 实现（可能使用快速傅立叶变换）。我还希望该算法能够在 beagleboard 的 DSP 上运行，因为我听说 DSP 针对此类操作进行了优化（通过其乘法累加指令）。

我没有该领域的背景，所以我认为自己实现卷积不是一个好主意（我可能不会像理解其背后所有数学的人那样做得好）。我相信某个地方有一个很好的 DSP C 卷积实现，但我找不到它？

有人可以帮忙吗？

编辑：结果内核非常小。其尺寸为 2X2 或 3X3。所以我想我并不是在寻找基于 FFT 的实现。我在网上搜索卷积以查看其定义，以便我可以以直接的方式实现它（我真的不知道卷积是什么）。我发现的只是乘积分的东西，我不知道如何用矩阵来做。有人能给我一段 2X2 内核案例的代码（或伪代码）吗？

Answer 1

图像和内核的尺寸是多少？如果内核很大，那么您可以使用基于 FFT 的卷积，否则对于小内核，只需使用直接卷积。

不过，DSP 可能不是实现此目的的最佳方法 - 仅仅因为它具有 MAC 指令并不意味着它会更高效。 Beagle Board 上的 ARM CPU 有 NEON SIMD 吗？如果是这样，那么这可能是正确的选择（而且也更有趣）。

对于小内核，您可以像这样进行直接卷积：

// 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 的偶数值 - 只需要注意两个内部循环的上限/下限。

Answer 2

我知道这可能偏离主题，但由于 C 和 JavaScript 之间的相似性，我相信它仍然会有所帮助。 PS.：受到@Paul R 回答的启发。

JavaScript 中使用数组的二维 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 -卷积算法与数组-in-javascript/