[Traitement du signal] Convolution en passant par la FFT

Slt a tous J'ai besoin de confirmation et d'aide...

Je veux convoluer une image en passant par Fourier.
En effet le théoreme de la convolution nous dit que

F(t)*G(t)=FFT(F(t))xFFT(G(t))
F(t)x G(t) =FFT(F(t))*FFT(G(t))


Primo : est ce que je dit vrai?
Secondo :pour mon Noyau de convolution .... la fft me donnera un tableau de valeur avec une dimension differente que la FFT de mon image.

Que doit je faire.

Est ce que je "colle" mon noyaux (dans le dommaine temporel )dans une imgage de meme taille que l'image a traiter en le centrant.Ou est ce que je centre la FFT dans un tableau de meme taille que la FFT de l'image a convoluer.?

Je doute la dessus.

Je sais que l'on peut faire un zoom avec la FFT...

Il suffit de coller la FFT de l'image dans un tableau noir de taille 2n plus grande pour un zoom de 2n x 100% plus grand. Je suis surement incomprehensible .... Dslé.

Lorsque l'on fait la FFT inverse : Miracle nous avons une image plus grande contenant le zooming executé.


Voila j'ai besoin de soutient merci d'avance.

Eh oui, le traitement du signal, c'est compliqué, et là, c'est qu'une infime partie !

Une FFT est faite pour un signal périodique. On ne prend qu'une seule tranche, mais en fait tout se passe comme s'il y en avait une infinité côte à côte.
Si tu veux convoluer 2 images, en fait une image et un filtre 3*3 par exemple, ça va être difficile d'appliquer la formule directement. Il faut en fait ajouter des 0 et faire que ton filtre ait la même taille que ton image, ou appliquer le filtre sur une imagette extraite de l'image. Mais là, il y a le problème de la périodicité qui intervient.
Si on prend l'image complète et un filtre de même taille, en faitles "bords" de l'image filtrée qui existent quand on fait la convolution directement se retrouvent additionnés à la valeur filtrée de l'image de l'autre côté.
Donc ce qu'on fait, c'est qu'on fait une FFT sur une imagette avec des 0 ajoutés autour et sur un filtre de même taille. Il y a autant de zéros que la dimension du filtre - 1, donc pour un filtre 3*3 sur une imagette 4*4, on ferait une transformée sur une imagette 6*6.
Ensuite, on "replace" cette imagette 6*6 dans l'image de départ avec les bords qu'on additionne aux autres imagettes résultat.

Pour ce qui est du suréchantillonage, il suffit de rajouter des 0 derrière les valeurs de la transformée et de faire une IFFT de dimension double. Mais si on ne sait pas ce qu'est le résultat d'une FFT, ça va être chaud de savoir comment le faire réellement, déjà certains qui connaissent la théorie ont du mal avec l'application...

Code:

---

1 2 3 4

fft f(t) ->F(w) f(f)*f(t)=ifft(F(w)xF(w))

---

Ceci est vrai qq soit la dimension, mais uniquement pour un signal continu.

Mais je présume que tu veux faire ça sur une image discrète.
Au lieu d'une convolution, tu obtiens une convolution cyclique, c'est à dire que les fréquences supérieurs à 2PI reviennent sur 0, les fréquences < 0 revinennent sur 2PI. Si tu peux négliger ce phénomène alors ça peut marcher.

Sinon il faux "pader" le signal, le compléter avec des zéros, pour diminuer l'aliasing. Par exemple en doublant sa taille avec des zéros.
Donc la FFT et l'IFFT sont plus lentes à calculer. O(NlogN) -> O(2Nlog2N).
En tenant compte que le signal contient pour moitié des zéros, on peut (difficilement) obtimiser l'algo et obtenir du O(2Nlog(2N-1)): pas terrible quand on connait la progression du logarithme.
De mème pour un signal 2D, mais on quadruple la surface.

Je comprends pas ton problème de "coller et centrer" l'image. Il faut pas oublier que le signal est périodique en fréquence.

Il faudra que tu convertisses les pixels en floats -> perte de temps.
Une convolution directe avec des instructions multimédia SIMD est peut-être plus rapide.

Je sais pas pourquoi tu veux convoluer ton image, peut-être existe t-il des méthodes plus appropriées à ton problème:
-filtre
-motion estimation

PS: Miles tu m'as doublé

MErci a vous deux pour vos reponses.

Enfait pour ce qui est du noyaux je le met dans une image de taille egale a l'image a traité avec des 0 autour.


Sinon pourquoi Utiliser la FFT,j"ai deja trop lutter sur la convolution et je sature j'ai envi d'essayer la FFT et la mutliplier avec le masque de convolution.
C'est aussi parcque j'ai entendu parler plusieur de la loi.
Je veux la mettre en execution c'est la curiosité.....

Merci en tous cas de toutes ces explications expertes.

Je vous tiens au courant.

Miles à écrit :

Citation:

---

"Pour ce qui est du suréchantillonage, il suffit de rajouter des 0 derrière les valeurs de la transformée"

---

En général je préfère faire le lien avec une fonction continue entre le dernier point observé de la FFT et le 1er point de la FFT afin d'éviter les "sauts" qui sont toujours peu recommandable pour le calcul de la IFFT

Citation:

---

Envoyé par j.p.mignot

En général je préfère faire le lien avec une fonction continue entre le dernier point observé de la FFT et le 1er point de la FFT afin d'éviter les "sauts" qui sont toujours peu recommandable pour le calcul de la IFFT

---

J'approuve, mais pour simplifier...

Citation:

---

Envoyé par parp1

MErci a vous deux pour vos reponses.

Enfait pour ce qui est du noyaux je le met dans une image de taille egale a l'image a traité avec des 0 autour.

---

Maintenant, tu sais qu'il faut aussi ajouter des "0" autour de ton image. Mais je ne te conseille pas trop de faire la convolution sur la totalité de l'image d'un coup, c'est pas rentable si on fait le calcul de complexité et d'occupation mémoire.

Salut a tous et encore merci de votre interet.

J'uitlise la FFT,Je fais une FFT sur une image elle me retourne un tableau a deux dimension avec une d'entre elle -1.Losrque je fais la IFFT je retrouve grossierement les valeur et je pers une ligne de pixels? Est ce que vous avez une idéee de cela?


Autre chose:

Pour la convolution je fais bien le produit mais le resultat n'est pas bon.
Quel sorte de valeur doitje utilisé ldans le tableau? Des UInt8,Int8 ..... parce que j'obtiens des valeurs trés faible est parfois négative.Donc pour la retranscrire dans l'image....un niveau de gris négatif....ca doit posé probleme.


Merci a plus tard.

Des flottants, au moins. Ca ça, tu perds de la précision.
Ensuite, pour ta ligne qui disparait, c'est un problème dans la bibliothèque que tu utilises.
N'oublies pas que la FFT d'une image 2D est en fait une image de nombres complexes, donc tu tre poses des questions inutiles.