Discussion :

[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 réduire 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-même, c'est l'implémentation, et là, il faut commencer par regarder de près 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 passées ?

Tu ne penses quand même 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

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
22
23
24
25
26
27
28
29
30
31
32
33
 
function [Y]=FFT_1D(M)
 
  [lig,col]=size(M);
  Y=zeros(1,col);
 
  if col==1 then
    Y=M;
  else
 
    x=modulo(col,2)
 
    for i=0:col/2-1
      Pair(1,i+1)=M(1,2*i+1)
      Impair(1,i+1)=M(1,2*i+2)
    end
 
    if x==1
      Pair(1,col/2+1)=M(1,col)
    end
 
    A=FFT_1D(Pair)
    B=FFT_1D(Impair)
 
    for k=0:col-1
      e=exp(-2*%i*%pi*k/col)
      t=modulo(k,col/2)+1
      Y(1,k+1)=A(1,t)+e*B(1,t)
    end 
 
  end
 
endfunction

ca fai des heures que j'essai de faire que ca marche pour des matrices impaire mais pas moyen dc si qqun a une idée 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 transformée de Fourier 2D pour une image ?

Tu comptes implémenter tout ça dans quel langage ? (car il existe par exemple des bibliothèques existante permettant de réaliser des transformées 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 après.

[romainromain]

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

[millie]

Scilab a également des bibliothèques 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

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
clear;
 
////////////////////////////
// Partie 1: TFD rapide  ///
////////////////////////////
 
 
//Fonction permettant de realiser le decoupage
// d'un vecteur X de taille pair en deux vecteurs
// Le premier aura les valeurs des indices impair
// Le second aura les valeurs des indices pair
function [X0, X1] = decouper(X);
 dimensionX = length(X);
 for k=0:dimensionX/2-1;
   X0(k+1) = X(2*k+1);
   X1(k+1) = X(2*k+2);
 end;
endfunction;
 
//Tests de la fonction
[dec1, dec2] = decouper([1,2,4,5]');
 
 
//Transformee Fourier Discrete Rapide
// Precondition: X de dimension 2^q 
function T= TFDrapide(X)
 dimensionX = length(X);
 if (dimensionX==1) then
    //cas d'arret 
    T(1) = X(1);
  else
    //cas general
    [X0, X1] = decouper(X);
    TFDX0 = TFDrapide(X0);
    TFDX1 = TFDrapide(X1);
    for k=0:dimensionX/2-1;
      T(k+1) = TFDX0(k+1) + exp(-2* %i * %pi * k/ dimensionX) * TFDX1(k+1);
      T(k+1+dimensionX/2) = TFDX0(k+1) - exp(-2* %i * %pi * k/ dimensionX) * TFDX1(k+1);
    end;
  end;
endfunction;
 
 
 
///////////////////////////////////
// Partie 2: TFD rapide inverse  //
///////////////////////////////////
 
 
//Transformee Fourier Discrete Inverse Rapide
function T = TFDrapideInverse(X)
 dimensionX = length(X);
 T = TFDrapide(X);
 for k=0:dimensionX-1;
   T(k+1) = conj(T(k+1)) / dimensionX;
 end;
endfunction;
 
 
 
//////////////////////////////////
// Partie 3: Module de spectre  //
//////////////////////////////////
 
 
//Calcul le module du spectre d'un vecteur X
//  qui sera allonge a une taille 256
//Precondition: taille de X inferieur a 256
function S = modspectre(X)
  dimensionX = length(X);
  for k=1:256;
    S(k) = X(max(int((k /256) * dimensionX),1));
  end;
  S = TFD(S);
  for k=1:256;
    S(k) = abs(S(k));
  end;
endfunction;
 
 
/////////////////////////////
// FONCTION POUR LES TESTS //
/////////////////////////////
 
//version moins optimise du calcul de la TFD
// par simple application de la definition de la TFD
function T = TFD(X);
  dimensionX = length(X); 
 for k=0:dimensionX-1;
   somme=0;
   for n=0:dimensionX-1;
     somme = somme + X(n+1)* exp(-2*%i*%pi*k*n/dimensionX);
   end;
   T(k+1) = somme;
 end;
endfunction;
 
 
//version moins optimise du calcul de la TFD inverse
// par simple application de la definition de la TFD inverse
function T = TFDinverse(X);
 dimensionX = length(X);
 for k=0:dimensionX-1;
   somme=0;
   for n=0:dimensionX-1;
     somme = somme + X(n+1)* exp(2*%i*%pi*k*n/dimensionX);
   end;
   T(k+1) = somme / dimensionX;
 end;
endfunction;
 
 
//fonction utilise pour tester la fonction modspectre
function X = creerSin()
 
 for k=1:2048;
   X(k) = sin(k/5);
 end;
 
endfunction;
 
 
 
////////////
// TESTS ///
////////////
 
//version rapide
timer();
 s3 =  TFDrapide(creerSin());
//version peu optimise
disp(timer());
 
timer();
S3 = TFD(creerSin());
disp(timer());
 
//version de scilab
 
 sc = fft( [45,14,14,15,14,15,16,17]',-1);
 
//version rapide
 //s4 = TFDrapideInverse([45,14,14,15,14,15,16,17]');
//version moins optimise
 //s4 = TFDinverse([45,14,14,15,14,15,16,17]');
 
//test de modspectre
 spectre = modspectre(creerSin());

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 dépend 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 légérement plus noir (car le noir autour s'est "diffusé" sur l'image).

Si ça tombe pile poil la bonne taille. Il y aura quand même des problèmes au bord car il manque des informations de toute manière pour appliquer le produit de convolution (au bord). Avec la transformée de Fourier, on considère en fait que l'image est "dupliquée" (en haut, à droite à gauche et en bas), ce qui fait que l'on peut appliquer le produit de convolution, mais que le résultat sera légérement faussé.

Exemple de contour qui devient légérement noir (c'est un flou gaussien) car on a completé :

Mais de toute façon, le produit de convolution est correctement défini 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.
merci

[lili81]

Salut;
j'ai un problème avec les descripteurs de Fourier que j'ai appliqués sur une image contour, j'ai calculé un certain nombre de coefficients mais mon problème et que je n'arrive pas à récupérer mon contour à partir de ces coefficients, j'ai appliqué la forme complexe en considérant les coordonnées 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 coordonnées dans l'image alors comment exploiter ces a(n) et b(n) ( avec deux parties imaginaire et réelle) pour trouver (x,y), merci d'avance.