Convolution 2D rapide pour DSP

Je souhaite implémenter des algorithmes de traitement d’images destinés à fonctionner sur un beagleboard . Ces algorithmes utilisent largement les convolutions. J’essaie de trouver une bonne implémentation en C pour la convolution 2D (probablement en utilisant la transformation de Fourier rapide). Je souhaite également que l’algorithme puisse s’exécuter sur le DSP du beagleboard, car j’ai entendu dire que le DSP est optimisé pour ce type d’opérations (avec son instruction multiply-accumulate).

Je n’ai pas d’expérience dans le domaine, alors je pense que ce ne sera pas une bonne idée de mettre en œuvre la convolution moi-même (je ne le ferai probablement pas aussi bien que quelqu’un qui comprend tout le calcul qui en découle). Je crois qu’une bonne implémentation de convolution C pour DSP existe quelque part mais je n’ai pas pu la trouver?

Quelqu’un pourrait aider?

EDIT: Il s’avère que le kernel est assez petit. Ses dimensions sont soit 2X2 ou 3X3. Donc, je suppose que je ne cherche pas une implémentation basée sur la FFT. Je cherchais une convolution sur le Web pour connaître sa définition afin de pouvoir la mettre en œuvre de manière simple (je ne sais pas vraiment ce que la convolution est). Tout ce que j’ai trouvé est quelque chose avec les intégrales multipliées et je ne sais pas comment le faire avec des masortingces. Est-ce que quelqu’un pourrait me donner un morceau de code (ou pseudo-code) pour le cas du kernel 2X2?

    Quelles sont les dimensions de l’image et du kernel? Si le kernel est volumineux, vous pouvez utiliser la convolution basée sur FFT. Sinon, pour les petits kernelx, utilisez simplement la convolution directe.

    Le DSP n’est peut-être pas la meilleure façon de le faire – le fait qu’il ait une instruction MAC ne signifie pas qu’elle sera plus efficace. Le processeur ARM de la carte Beagle est-il doté de NEON SIMD? Si c’est le cas, cela pourrait être la voie à suivre (et plus de plaisir aussi).

    Pour un petit kernel, vous pouvez faire une convolution directe comme ceci:

    // in, out are mxn images (integer data) // K is the kernel size (KxK) - currently needs to be an odd number, eg 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 } } 

    Vous pouvez modifier cela pour prendre en charge les valeurs K égales - cela prend juste un peu de soin avec les limites supérieure / inférieure des deux boucles internes.

    Je sais que cela peut être hors sujet, mais en raison de la similitude entre C et JavaScript, je pense que cela pourrait toujours être utile. PS .: Inspiré par la réponse de @Paul R.

    Algorithme de convolution 2D à deux dimensions en JavaScript à l’aide de tableaux

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

    Vous pouvez consulter l'article complet sur le blog à l' adresse http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with-arrays-in-javascript/