convoluzione veloce 2D per DSP

Question

Voglio implementare alcuni algoritmi di elaborazione delle immagini che sono destinati a funzionare su un BeagleBoard . Questi algoritmi utilizzano circonvoluzioni estesamente. Sto cercando di trovare una buona implementazione C per convoluzione 2D (probabilmente utilizzando il veloce di Fourier Transform). Voglio anche l'algoritmo per essere in grado di girare su DSP del BeagleBoard, perché ho sentito che il DSP è ottimizzato per questo tipo di operazioni (con la sua istruzione di moltiplicazione-addizione).

Non ho alcun background nel campo quindi credo che non sarà una buona idea per implementare la circonvoluzione me (probabilmente non lo farò buono come qualcuno che capisce tutta la matematica dietro di esso). Credo che una buona implementazione convoluzione C per DSP esiste da qualche parte, ma non è stato in grado trovarlo?

Potrebbe aiutare qualcuno?

EDIT: Si scopre che il kernel è piuttosto piccolo. Le sue dimensioni sono o 2X2 o 3X3. Quindi credo che non sto cercando un'implementazione basato su FFT. Ero alla ricerca di convoluzione sul web per vedere la sua definizione in modo da poter implementare in modo dritto in avanti (non so davvero che cosa è convoluzione). Tutto Ho trovato'VE è qualcosa con integrali moltiplicate 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 il kernel? Se il kernel è grande quindi è possibile utilizzare convoluzione FFT-based, altrimenti per i piccoli kernel basta usare convoluzione diretta.

Il DSP non potrebbe essere il modo migliore per fare questo anche se - solo perché ha un'istruzione MAC non significa che sarà più efficiente. La CPU ARM sulla scheda Beagle hanno NEON SIMD? Se è così allora che potrebbe essere la strada da percorrere (e 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 ai limiti superiori / inferiori sui due cicli interni

Answer 2

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

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 all'indirizzo http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with -arrays-in-javascript /