Быстрая 2D свертка для DSP

Question

Я хочу реализовать некоторые алгоритмы обработки изображений, предназначенные для работы на beagleboard .Эти алгоритмы широко используют свертки.Я пытаюсь найти хорошую реализацию C для двумерной свертки (возможно, используя быстрое преобразование Фурье).Я также хочу, чтобы алгоритм мог работать на DSP beagleboard, потому что я слышал, что DSP оптимизирован для таких операций (с его командой умножения-накопления).

У меня нет опыта вполе, так что я думаю, что это не будет хорошей идеей, чтобы реализовать свертку самостоятельно (я, вероятно, не буду делать это так же хорошо, как тот, кто понимает всю математику за ней).Я полагаю, что где-то существует хорошая сверточная реализация C для DSP, но я не смог ее найти?

Может ли кто-нибудь помочь?

РЕДАКТИРОВАТЬ: Оказалось, что ядро ​​довольномаленький.Его размеры 2X2 или 3X3.Так что, думаю, я не ищу реализацию на основе FFT.Я искал свертку в сети, чтобы увидеть ее определение, чтобы я мог реализовать ее прямым способом (я действительно не знаю, что такое свертка).Все, что я нашел, это что-то с умноженными интегралами, и я понятия не имею, как это сделать с матрицами.Может ли кто-нибудь дать мне кусок кода (или псевдокод) для случая ядра 2X2?

Answer 1

Каковы размеры изображения и ядра?Если ядро ​​большое, вы можете использовать FFT-свертку, в противном случае для маленьких ядер просто используйте прямую свертку.

Хотя DSP может быть не лучшим способом сделать это - просто потому, что у него есть инструкция MAC,не означает, что это будет более эффективным.Есть ли у процессора ARM на плате Beagle 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 с использованием массивов

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 / двумерный алгоритм свертки с массивами в-JavaScript /