Discussion :

[mattthieu]

Bonjour a tous,

je voudrais calculer un produit de convolution entre 2 matrices 3d.

• Savez vous si scipy/numpy implementent directement des produits de convolutions?
• Sinon, je n'ai pas trouve de FFT en 3 dimension... Est ce qu'il en existe une? En fait il semblerait que numarray en ai une (voir ici) mais j'ai toujours lu qu'il ne fallait pas utiliser numarray. (s'il vous plait ne me dites pas de chainer des convolutions 1d c'est mathematiquement faux en general)

j'ai cherche un moment sur le net mais je n'ai rien trouve de concluant pour ces deux questions...

Merci d'avance!
a+
Mattthieu

[Matthieu Brucher]

Il me semble que oui. C'est à vérifier, mais normalement, c'est présent dans scipy.fftpack.
Il y a un module de FFT nd dans numpy.fft et dans scipy.fftpack.

Et la FFT est mathématiquement séparable (peut-être que tu fais allusion à la pratique ?)

[mattthieu]

Merci pour ta réponse!

J'ai effectivement trouvé la fonction fftn de numpy.fft qui semble faire ce que je veux.

A propos de la notion séparabilité, il faut qu'on se mette d'accord sur ce que ça veut dire. Pour moi c'est une fonction qui est séparable et pas la transformée de fourier (qui est une fonctionnelle). Voici quelques lignes, j'espère pas trop mathématiques, qui expliquent ce que je veux dire par "chainer des convolutions 1d est mathematiquement faux en general".

Hésitez pas à me dire que je me suis planté...

[Matthieu Brucher]

Ca, c'est utile si on fait la multiplication des FFTs. Si tu chaînes les FFT (tu fais la FFT sur le résultat de la précédente), tu ne passes pas du tout par le calcul que tu montres.
Un exemple simple. Une image n'est pas séparable en générale. Or, faire la FFT dans une dimension puis dans l'autre, ça fait la FFT 2D.
Si l'image est séparable et vaut un vecteur V1 * V2 (multiplication matricielle), alors la FFT de l'image vaut FFT(V1)*FFT(V2), mais là, tu ne fais que 2 FFT, tandis que tu en fais beaucoup plus si tu chaînes les FFTs (une par ligne puis une par colonne).
La FFT est un filtre séparable, il n'y a aucun problème

[mattthieu]

euh... je ne comprends pas vraiment ce que tu veux dire... Désolé de chercher la petite bête mais je voudrais pas passer à côté de quelquechose d'important (qui pourrait accellérer mes progs). Et puis cette discussion pourra surement aider quelqu'un.

Tout d'abord il faut rappeler qu'on parle de FFT dans cette discussion mais que pour l'aspect mathématique c'est plutot de transformée de fourier dont il faudrait parler. La FFT étant un implémentation rapide de la transformée de fourier.

Un exemple simple. Une image n'est pas séparable en générale. Or, faire la FFT dans une dimension puis dans l'autre, ça fait la FFT 2D.

Je suis d'accord: c'est la définition d'une intégrale en 2 dimensions. On intègre dans une dimension puis dans l'autre. C'est un processus très lent en général. Je n'aurais pas dû employer le terme de chainage dans mes posts précédents. Et de plus les FFT 1D d'origine des différents packages ne permettent pas de faire ce chainage., il faut utiliser les FFT 2D (ou plus) d'origine.

Si l'image est séparable et vaut un vecteur V1 * V2 (multiplication matricielle), alors la FFT de l'image vaut FFT(V1)*FFT(V2), mais là, tu ne fais que 2 FFT, tandis que tu en fais beaucoup plus si tu chaînes les FFTs (une par ligne puis une par colonne).

Là encore je suis d'accord ça correspond à ce que j'ai posté juste avant, non? C'est beaucoup plus rapide, d'où l'intérêt de se ramener à des images (ou des noyaux) séparables.

La FFT est un filtre séparable, il n'y a aucun problème

Par contre je ne suis pas d'accord. La FFT n'est pas une filtre, c'est un opérateur de fonction, donc on ne peut pas dire que la FFT est séparable. Ce lien explique (en anglais) ce qu'est un filtre séparable (qui correpond à ton exemple avec l'image sous la forme V1*V2).

Dis moi si tu penses que je me trompe...

Et merci de ton aide.

[Matthieu Brucher]

Tout d'abord il faut rappeler qu'on parle de FFT dans cette discussion mais que pour l'aspect mathématique c'est plutot de transformée de fourier dont il faudrait parler. La FFT étant un implémentation rapide de la transformée de fourier.

Je suis d'accord avec toi, mais bon, c'est chipoter pour pas grand chose, là...

Je suis d'accord: c'est la définition d'une intégrale en 2 dimensions. On intègre dans une dimension puis dans l'autre. C'est un processus très lent en général. Je n'aurais pas dû employer le terme de chainage dans mes posts précédents. Et de plus les FFT 1D d'origine des différents packages ne permettent pas de faire ce chainage., il faut utiliser les FFT 2D (ou plus) d'origine.

Et dans ce cas, il n'y a aucun problème pour faire une FFT dan sune dimension puis dans l'autre. D'ailleurs, c'est ce que font toutes les bibliothèques de FFT nD.

Là encore je suis d'accord ça correspond à ce que j'ai posté juste avant, non? C'est beaucoup plus rapide, d'où l'intérêt de se ramener à des images (ou des noyaux) séparables.

Oui, mais aucune image n'est séparable (ça paraît logique).

Par contre je ne suis pas d'accord. La FFT n'est pas une filtre, c'est un opérateur de fonction, donc on ne peut pas dire que la FFT est séparable. Ce lien explique (en anglais) ce qu'est un filtre séparable (qui correpond à ton exemple avec l'image sous la forme V1*V2).

C'est aussi un filtre. Tu peux voir ça comme un opérateur de fonction, mais c'est aussi un filtre linéaire. Bref, tu peux chaîner, faire un filtre avant l'autre, filtrer le filtre, ...

Ce que tu dois comprendre, c'est que tu peux chaîner les FFT, car c'est différent de ce que tu crois que ça fait.

[mattthieu]

Je suis d'accord avec toi, mais bon, c'est chipoter pour pas grand chose, là...

Je pense plutôt que ça peut aider certains à comprendre mieux...

C'est aussi un filtre. Tu peux voir ça comme un opérateur de fonction, mais c'est aussi un filtre linéaire. Bref, tu peux chaîner, faire un filtre avant l'autre, filtrer le filtre, ...

Toujours pas non . Un filtre prend un certain objet et renvoie un objet de la même nature. Le principe de la transformée de fourier est de prendre par exemple une fonction temporelle et de renvoyer une fonction fréquentielle. Les 2 ne sont pas homogènes. C'est un peu du pinaillage sur les mots mais c'est important que tout le monde comprenne bien.
En fait, la tranformée de fourier sert dans la plupart des opérations de filtrage des signaux (d'où la confusion). On filtre généralement S (un signal) par G (le noyau du filtre ou par abus de language le filtre) en faisant un produit de convolution entre les 2: conv(S,G). La TF permet de trouver le signal filtré avec la formule conv(S,G)=TF^{-1}((TF(S)*TF(G))). (On peut remplacer TF par FFT). Rigoureusement le filtre serait conv(.,G): la fonction qui à S associe conv(S,G) qui serait le filtre.
La notion ne séparabilité s'applique aux noyaux et non à la transformée de fourier (cf la pièce joint que j'ai mise avant).

M'enfin, mieux vaut arréter de digresser sur le vocabulaire ça ne nous amènera pas très loin...

Ce que tu dois comprendre, c'est que tu peux chaîner les FFT, car c'est différent de ce que tu crois que ça fait.

Bizarre comme phrase de conclusion. C'est plutôt moi qui sait ce que je pense, non? Et de plus il me semble que j'ai bien compris. Si jamais tu peux éclairer un peu plus ma lanterne n'hésite pas...

On a fait le tour de la question, non?
Merci encore!

A+

[Matthieu Brucher]

Toujours pas non . Un filtre prend un certain objet et renvoie un objet de la même nature. Le principe de la transformée de fourier est de prendre par exemple une fonction temporelle et de renvoyer une fonction fréquentielle. Les 2 ne sont pas homogènes. C'est un peu du pinaillage sur les mots mais c'est important que tout le monde comprenne bien.
En fait, la tranformée de fourier sert dans la plupart des opérations de filtrage des signaux (d'où la confusion). On filtre généralement S (un signal) par G (le noyau du filtre ou par abus de language le filtre) en faisant un produit de convolution entre les 2: conv(S,G). La TF permet de trouver le signal filtré avec la formule conv(S,G)=TF^{-1}((TF(S)*TF(G))). (On peut remplacer TF par FFT). Rigoureusement le filtre serait conv(.,G): la fonction qui à S associe conv(S,G) qui serait le filtre.
La notion ne séparabilité s'applique aux noyaux et non à la transformée de fourier (cf la pièce joint que j'ai mise avant).

Sincèrement, je pense avoir plus de recul à ce sujet que toi... Regarde à nouveau la formule.

Bizarre comme phrase de conclusion. C'est plutôt moi qui sait ce que je pense, non? Et de plus il me semble que j'ai bien compris. Si jamais tu peux éclairer un peu plus ma lanterne n'hésite pas...

Je sais très bien ce que je dis, je le maintiens.
Tu n'avais pas compris la différence entre séparabilité et chaînage, je ne sais toujours pas si tu l'as compris... Est-ce que tu es d'accord avec moi sur le fait qu'on peut chaîner les FFTs 1D pour faire une FFT 3D d'après ce que j'ai dit ?

[mattthieu]

Est-ce que tu es d'accord avec moi sur le fait qu'on peut chaîner les FFTs 1D pour faire une FFT 3D d'après ce que j'ai dit ?

Oui.

Mon but n'est pas d'enflammer la poudre et j'ai l'impression de me balader avec une chandelle dans un stock de munitions. Je demandais juste des explications. Je m'arrète la.

[Matthieu Brucher]

C'est le principal
Après, c'est une histoire d'interprétation, tu verras quand tu travailleras plus en TS que ce que j'ai dit est aussi valide