Convoluzione 2D veloce per DSP

Question

Desidero implementare alcuni algoritmi di elaborazione delle immagini che devono essere eseguiti su un beagleboard. Questi algoritmi usano ampiamente le convoluzioni. Sto cercando di trovare una buona implementazione C per la convoluzione 2D (probabilmente usando la trasformazione di Fourier veloce). Voglio anche che l'algoritmo sia in grado di funzionare sul DSP di beagleboard, perché ho sentito che il DSP è ottimizzato per questo tipo di operazioni (con le sue istruzioni di accumulo multiplo).

Non ho esperienza nel campo, quindi penso che non sarebbe una buona idea implementare la convoluzione da solo (probabilmente non lo farò come qualcuno che capisca tutta la matematica che c'è dietro). Credo che esistano da qualche parte una buona implementazione di convoluzione per DSP, ma non sono riuscito a trovarla?

Qualcuno potrebbe aiutare?

MODIFICA: Risulta che il kernel è piuttosto piccolo. Le sue dimensioni sono 2X2 o 3X3. Quindi penso che non sto cercando un'implementazione basata su FFT. Stavo cercando la convoluzione sul web per vedere la sua definizione in modo da poterla implementare in modo diretto (non so davvero cosa sia la convoluzione). Tutto quello che ho trovato è qualcosa con integrali moltiplicati e non ho idea di come farlo con le matrici. Qualcuno potrebbe darmi un pezzo di codice (o pseudo codice) per il caso del kernel 2X2?

Answer 1

Quali sono le dimensioni dell'immagine e del kernel? Se il kernel è di grandi dimensioni, è possibile utilizzare la convoluzione basata su FFT, altrimenti per i kernel piccoli è sufficiente utilizzare la convoluzione diretta.

Il DSP potrebbe non essere il modo migliore per farlo anche se - solo perché ha un'istruzione MAC non significa che sarà più efficiente. La CPU ARM sulla scheda Beagle ha NEON SIMD? Se è così allora quella potrebbe essere la strada da percorrere (e anche più divertente).

Per un piccolo kernel, si può fare convoluzione diretta in questo modo:

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

È possibile modificare questo per sostenere anche i valori di K - ci vuole solo un po 'di attenzione con i/limiti superiori inferiori sul due anelli interni.

Answer 2

So che potrebbe essere fuori tema ma a causa della somiglianza tra C e JavaScript credo che potrebbe essere ancora utile. PS .: Ispirato alla risposta @Paul R.

Due dimensioni 2D algoritmo di convoluzione in JavaScript utilizzando matrici

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

È possibile controllare il post completo al http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with-arrays-in-javascript/