Convolución 2D rápida para DSP

Question

Quiero implementar algunos algoritmos de procesamiento de imágenes que están destinados a ejecutarse en un beagleboard. Estos algoritmos usan circunvoluciones extensivamente. Estoy tratando de encontrar una buena implementación C para la convolución 2D (probablemente usando la Transformada Rápida de Fourier). También quiero que el algoritmo pueda ejecutarse en el DSP de beagleboard, porque he oído que el DSP está optimizado para este tipo de operaciones (con su instrucción de acumulación múltiple).

No tengo experiencia en el campo, así que no sería una buena idea implementar la convolución yo mismo (probablemente no lo haga tan bien como alguien que entienda todas las matemáticas que hay detrás). Creo que existe una buena implementación de convolución C para DSP en algún lado, pero no pude encontrarla.

¿Alguien podría ayudar?

EDITAR: Resulta que el kernel es bastante pequeño. Sus dimensiones son 2X2 o 3X3. Así que supongo que no estoy buscando una implementación basada en FFT. Estaba buscando la convolución en la web para ver su definición, así que puedo implementarla de una manera directa (realmente no sé qué es la convolución). Todo lo que he encontrado es algo con integrales multiplicadas y no tengo ni idea de cómo hacerlo con matrices. ¿Alguien podría darme una pieza de código (o pseudo código) para el caso del kernel 2X2?

Answer 1

¿Cuáles son las dimensiones de la imagen y el kernel? Si el kernel es grande, entonces puede usar la convolución basada en FFT; de lo contrario, para núcleos pequeños solo use convolución directa.

Sin embargo, el DSP podría no ser la mejor manera de hacerlo: solo porque tiene una instrucción MAC no significa que será más eficiente. ¿La CPU ARM en la placa Beagle tiene NEON SIMD? Si es así, ese podría ser el camino a seguir (y más divertido también).

Para un pequeño núcleo, puede hacer convolución directa como esto:

// 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 
    } 
} 

Puede modificar esto para soportar incluso los valores de K - Solo se necesita un poco de cuidado con los límites superior/inferior en los dos bucles internos.

Answer 2

Sé que podría estar fuera de tema, pero debido a la similitud entre C y JavaScript creo que todavía podría ser útil. PD .: Inspirado por @Paul R respuesta.

dos dimensiones algoritmo de convolución 2D en JavaScript utilizando matrices

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; 
} 

Puede comprobar el blog completo en http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with-arrays-in-javascript/