# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  algo de la FFT

## romainromain

bonjour , voila je doi developpez un programme pour apliquer la fft sur une image.
Pour cela je doit faire une fonction qui permet de faire la fft 1d, mais je ne trouve pas d'algorythme et je ne c pas comment faire merci

----------


## mamelouk

salut,
tu as regard sur wikipedia ? http://fr.wikipedia.org/wiki/Transfo...Fourier_rapide

ca m'tonne que tu n'ai rien trouv sur google non plus...

----------


## j.p.mignot

j'uitilise la + part du temps l'algorithme de Cooley-Tukey qui est en n.log(n).
L'algorithme de Winograd [WFTA] permet de rduire sensiblement le nombre de multiplications par contre il necessite plus de mise en forme des data.

----------


## romainromain

merci mais en fait je dois faire l'algo moi meme.
en fait je dois prendre une image, effectuer une fft1d sur les lignes, puis sur les colonnes.
l'algo est un arbre: tf(M) = tf(paire) + tf(fourrier(impaire) mais cela est tres flou et je ne trouve rien dessus alor si quelqu'un voit merci

----------


## thewho

Bonjour,



> merci mais en fait je dois faire l'algo moi meme


Je ne pense pas qu tu doives faire a : l'algo de la FFT est bien connu.

Ce que tu dois faire toi-mme, c'est l'implmentation, et l, il faut commencer par regarder de prs ce que fait l'algo.

La balle est dans ton camp.

----------


## romainromain

merci c a que je veux dire mais la balle n'est pas trop dans mon camps car la fin du match est dans deux jours..........

----------


## mamelouk

> merci c a que je veux dire mais la balle n'est pas trop dans mon camps car la fin du match est dans deux jours..........


il est marrant ^^

----------


## thewho

Bonjour,



> merci c a que je veux dire mais la balle n'est pas trop dans mon camps car la fin du match est dans deux jours..........


Et  part a, les vacances se sont bien passes ?

Tu ne penses quand mme pas qu'on va faire le travail pour toi, rassure-moi ?

----------


## romainromain

voila g fini par reussir a faire un truc mais ca marche que pour des matrices de puissance de 2



```

```

ca fai des heures que j'essai de faire que ca marche pour des matrices impaire mais pas moyen dc si qqun a une ide merci...

----------


## millie

> bonjour , voila je doi developpez un programme pour apliquer la fft sur une image.
> Pour cela je doit faire une fonction qui permet de faire la fft 1d, mais je ne trouve pas d'algorythme et je ne c pas comment faire merci


Tu ne souhaites pas effectuer une transforme de Fourier 2D pour une image ? 

Tu comptes implmenter tout a dans quel langage ? (car il existe par exemple des bibliothques existante permettant de raliser des transformes de Fourier 1D et 2D. Par exemple en C/C++, il y a FFTW).

*EDIT :*



> merci mais en fait je dois faire l'algo moi meme


Zut, j'eusses vu aprs.

----------


## romainromain

merci
je programme en sous scilab mais je doit faire la fft 1d sinon c tro simple...

----------


## millie

Scilab a galement des bibliothques pour faire des FFT 1D.

Enfin, bref, voici un code source de moi que j'avais fait en scilab pour faire des FFT 1D. Il faut ventuellement remplir le signal pour qu'il atteigne une puissance de 2  :;):  



```

```

Il y a une partie avec la TFD pas rapide (c'tait juste pour les tests) et une partie qui faisait des calculs sur un spectre, donc  ne pas prendre en compte.

----------


## romainromain

merci ca marche

----------


## millie

Ca dpend tu comptes l'utiliser pour quoi.

Par exemple, en traitement d'image, si c'est pour appliquer un flou (qui provient d'un produit de convolution). Si tu remplis le tour avec du noir, il est possible que tu te retrouves avec des bords lgrement plus noir (car le noir autour s'est "diffus" sur l'image). 

Si a tombe pile poil la bonne taille. Il y aura quand mme des problmes au bord car il manque des informations de toute manire pour appliquer le produit de convolution (au bord). Avec la transforme de Fourier, on considre en fait que l'image est "duplique" (en haut,  droite  gauche et en bas), ce qui fait que l'on peut appliquer le produit de convolution, mais que le rsultat sera lgrement fauss.

Exemple de contour qui devient lgrement noir (c'est un flou gaussien) car on a complet :

Mais de toute faon, le produit de convolution est correctement dfini pour une image de taille "infinie" (ou une restriction de l'image d'origine).

----------


## romainromain

merrci ou c bon ca marche merci

----------


## lilya

bonjour millie!
j'ai essayer votre FFT 1D,ca donne de bon resultats,mais j'ai pa compris ou est le bit reverse???il n'apparait pas sur votre programme.parce que generalement chaque fft doit passer par un bit reverse .est ce que vous pouvez me donner quelques precisions. ::oops:: 
merci

----------


## lili81

Salut;
j'ai un problme avec les descripteurs de Fourier que j'ai appliqus sur une image contour, j'ai calcul un certain nombre de coefficients mais mon problme et que je n'arrive pas  rcuprer mon contour  partir de ces coefficients, j'ai appliqu la forme complexe en considrant les coordonnes du contour comme des nombres complexes, j'ai calcul les c(n) avec la somme des modules de a(n) et b(n), donc pour revenir  mon contour je dois travailler avec ces derniers, mais sachant que ces modules sont des nombres complexes et que mon but et d'avoir des coordonnes dans l'image alors comment exploiter ces a(n) et b(n) ( avec deux parties imaginaire et relle) pour trouver (x,y), merci d'avance.

----------

