Быстрая двумерная свертка для DSP

Question

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

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

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

EDIT: Оказывается, ядро ​​довольно мало. Его размеры - 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 ответ.

Два измерения 2D свертка алгоритм в 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/two-dimensional-convolution-algorithm-with-arrays-in-javascript/