Discussion :

[jeje99]

Bonjour tout le monde,

Je suis actuellement étudiant, dans le cadre d'un projet (reconnaissance de forme) je dois implémenter une fft 2d pour traiter mes images. J'ai très vite trouvé un algorithme en C pour la fft. Le problème c'est que je n'en n'ai pas trouvé pour la ifft 2d.

Quelque pourrait - il m'aider ? On quelqu'un connait - il une adresse ou je pourrait trouver une librairie intégrant le type de fonction que je recherche ?

[ourk]

http://www.itwm.fraunhofer.de/mab/pr...up__fft2d.html

[Mac LAK]

J'ai mes vieux sources C de maîtrise info (TP FFT 1D/2D) qui traînent, si ça t'intéresse.

Sinon, le principe d'une FFT2D consiste, si ma mémoire est bonne, à faire des FFT1D sur chaque ligne, puis sur chaque colonne. Ca s'apparente à une convolution. Mais bon, j'ai pas touché à ça depuis 5 ans ! ;-)

[ronan99999]

Salut,
en effet comme la transformée de fourier est séparable tu peux la calculer comme ça:

Code :

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

1
2
3
 
 
FFT2D(I(x,y)) = FFT1D((FFT1D(I(x,y)) pour tout x)) pour tout y)

le tout en n²*log2(n), par contre si je mesouviens bien la FFT n'accepte qu'un signal du support égale à une puissance de deux, tu devras surement faire du pasting avant de transformer ton image.

[Mac LAK]

par contre si je mesouviens bien la FFT n'accepte qu'un signal du support égale à une puissance de deux

Il me semble que cette contrainte n'est vraie que pour l'algo dit "Papillon", non ?

[Kangourou]

salut

par contre si je mesouviens bien la FFT n'accepte qu'un signal du support égale à une puissance de deux

Il me semble que cette contrainte n'est vraie que pour l'algo dit "Papillon", non ?

il me semble que la FFT=papillon, sinon on fait une integration numerique classique et ca s'appelle DFT (Discrete Fourier Transform) tout simplement.

A+

[Mac LAK]

il me semble que la FFT=papillon, sinon on fait une integration numerique classique et ca s'appelle DFT (Discrete Fourier Transform) tout simplement.

Arf, oui, ça me rappelle quelque chose, cette distinction... Juste une lettre de différence, ça frise le mesquin... ;-)

[ceugniet]

il me semble que la FFT=papillon, sinon on fait une integration numerique classique et ca s'appelle DFT (Discrete Fourier Transform) tout simplement.

Arf, oui, ça me rappelle quelque chose, cette distinction... Juste une lettre de différence, ça frise le mesquin... ;-)

Pour ma part, je pense que le premier "F" de FFT (Fast Fourier Transform) fait référence à l'algorithme de factorisation. Supposons que l'on doive faire une Transformée de Fourier (forcément discrète) sur n éléments. L'application brute de la formule demande n*n multiplications et additions complexes.

Le génie de Cooley et Tuckey (je ne me souviens pas de l'orthographe exacte de leurs noms) a consisté à manipuler les calculs bruts lorsque n est factorisable : n = p * q

Ils ont montré que l'on pouvait s'en tirer en faisant p transformées de Fourier de longueur q, au prix de O(n) opérations. Et évidemment, ils ne se sont pas arrêtés en si bon chemin, en observant que si à son tour q était factorisable (q = r * s), ils ont vu que faire une transformée de Fourier de longueur q pouvait se faire en faisant r transformées de longueur s.... D'où l'approche générale : si n est une puissance de 2 (n=2**k), on évite k fois de faire des transformées de Fourier, jusqu'à devoir transformer des suites de longueur 1, c'est-à-dire qu'il n'y a plus rien à faire. Mais si n est un produit d'une puissance de 2 par une puissance de 3 (n=2**K * 3**L), on peut quand même mériter le "F" (fast) en appliquant K fois la séquence de calcul spécifique du facteur 2 et L fois la séquence spécifique du facteur 3.

Le terme "papillon" désigne l'opération élémentaire à faire lorsque l'on a un facteur 2. Je suppose que l'on utilise d'autres expressions lorsque le facteur est 3 ou 5. Mais ce n'est pas le "papillon" qui fait qu'une "FT" devient une FFT. La FFT, c'est la factorisation (par 2, par 3, par 5...). Comme la FFT est d'autant plus rapide que le facteur est petit, on est bien content lorsque n est une puissance de 2. Mais il y a des FFT qui traitent tous les produits de puissances de 2, 3 et 5 par exemple : tout dépend de l'ardeur au travail du programmeur, parce que "Ya du boulot ".

J'ignorais que DFT faisait référence à une intégration numérique complète sans la factorisation de Cooley Tuckey. Moi, j'aurais appelé ça "SFT" comme Slow Fourier Transform. Mais Bon !

En tous cas, rien n'empêche^de faire une FT pour n'iimporte quelle valeur de n, même si n est premier ; simplement, ça va plus vite si n se factorise et si l'algorithme choisi en profite.