Discussion :

[el toro diablo]

Bonjour je cherche un algorithme de convolution, j'explique : je veux appliquer un masque (de taille 3*3 ou 5*5) à un tableau bidimensionnel.

Connaissez vous un algo rapide pouvant faire ça.

J'avais entendu parler de l'algo de KARATSUBA de multiplications de matrice, quelqu'un l'a t'il adapté à la convolution ?

Ma matrice est creuse (i.e. c'est un tableau représentant une image, un tableau de 622*622 cases avec moins de 10000 points contenant une valeur non nulle) appliquer un masque à tout mon tableau serait une perte de temps. Une idée, une solution ?

[Kangourou]

Salut,

Une solution classique pour accelerer la convolution (mais peut-etre pas forcement la plus adaptee dans ce cas) est de passer par la transformee de Fourier :
en effet, la transfomee de fourier d'un produit de convolution est egale au produit des transformees de Fourier de chaque signal. Comme la FFT est rapide, ca permet de faire une convolution lineaire (il me semble...)
ca te donne :
conv(img, filtre) = ifft( fft(img) * fft(fil))

A+

[Ol']

Tu peux essayer de décomposer ta matrice de convolution en produit de convolution de deux vecteurs. Cela fait tomber la complexité de ton algo d'un degré.

Ensuite, tu utilises la distributivité du produit de convolution

J'espère que cela pourra t'aider

A+
Ol'

[victorracine]

salut
a mon avis
tu dois faire une convoluiton normale mais, il ne faut pas se tromper de sens:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
B=conv(A,K) K est ton masque
for(i sur les X de A)
for(j sur les Y de A){
   si A(i,j)<>0
   alors{
      for(ii sur les X de K)
      for(jj sur les Y de K){
        B(i-ii,j-jj)=B(i-ii,j-jj)+A(i,j)*K(ii,jj)
      }
   }
}
 
et pas 
 
for(i sur les X de A)
for(j sur les Y de A){
    for(ii sur les X de K)
    for(jj sur les Y de K){
      B(i-ii,j-jj)=B(i-ii,j-jj)+A(i,j)*K(ii,jj)
    }
}

je ne suis pas sur d'avoir eté clair... mais bon
bye
Vic

[el toro diablo]

j'ai bien compris, c'est la méthode basique d'une convolution, je voulais en fait surtout savoir si dans le cas de matrice (500*500 environs) creuses (uniquement 1500 points valides i.e. 1500 points de valeur non nulle), il existait d'autres méthodes plus rapides ! Sinon l'algo le plus rapide de multiplication de matrices est celui de KARATSUBA (cf + haut) est ce qu'il a été adapté pour des masques de convolution ? Est ce quelqu'un à un bout de code de cet algo que je pourrai adapter, car j'en ai entendu parler, mais je ne l'ai pas encore vu (comme le père noël ... désolé )


je viens de trouver une adresse :
http://gersoo.free.fr/docs/docs.html
Il ya l'algo de KARASUBA et bien d'autres choses

[fadoua_22]

puisque vous parlez du masque de convolution je demande juste de savoir comment on calcule le masque en 3*3 ou 5*5 et la je parle du coté purement théorique.

merci d avance pour votre réponse

cordialement
fadoua

[millie]

La convolution n'a aucun rapport avec la multiplication matricielle.

Si le masque de convolution est gros, comme l'a dit Kangourou, il faut passer dans le domaine de Fourier.

Tu peux regarder :
http://humbert-florent.developpez.co...ement/fourier/

http://humbert-florent.developpez.co.../introduction/

[Copros]

L'algorithme de Karatsuba est à l'origine destiné au produit de polynômes, d'après le principe du diviser pour mieux régner. En réalité cette méthode permet de réduire le nombre de multiplications au détriment du nombre d'additions / soustractions, dans la mesure où le coût de ces opérations est moindre.

En gros, l'idée est de ramener le produit de polynômes de degrés quelconques à une succession de produits de polynômes du premier degré, lesquels sont optimisés de la façon suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
{
  double p1[2] = { /* coeff. du 1er polynome */ };
  double p2[2] = { /* coeff. du 2nd polynome */ };
  double p3[3];  /* produit de p1 par p2 */
  double temp1, temp2, temp3;
 
  temp1 = p1[0] * p2[0];
  temp2 = (p1[0] + p1[1]) * (p2[0] + p2[1]);
  temp3 = p1[1] * p2[1];
 
  p3[0] = temp1;
  p3[1] = temp2 - temp3 - temp1;
  p3[2] = temp3;
}

La convolution 1D étant une opération similaire au produit de polynôme (en considérant un signal comme un polynôme dont les coefficients correspondent aux éléments du signal), on peut y employer cet algorithme. J'ai pu le vérifier en l'implémentant par moi-même, avant de l'étendre à des signaux 2D (il y a quelques temps déjà), donc si tu veux quelque détails je dois pouvoir t'aider.