Discussion :

[LukeS]

Bonjour,

je dois utiliser une transformée de fourier en C sur une image. J'ai déjà regardé d'autres articles sur le forum et je n'ai pas tout compris.
J'ai notamment lu les discussion suivantes : probleme avec la FFT [Résolu] et fft, numerical recipie.

Je ne comprend pas le fonctionnement de cette fonction : Ou doivent être les données d'entrées ? ou sont les données de sortie ? Quels paramètres il faut modifier ? ...

Merci d'avance pour les explications.

Luke

[diogene]

Ton problème est de faire une DFT à 2 dimension et visiblement, tu t'orientes vers la solution d'utiliser des DFT 1D.
Pour faire cette opération, il faut
1- faire la DFT sur chaque ligne du tableau pour toutes les lignes du tableau
2- faire la DFT sur chaque colonne du tableau pour toutes les colonnes du tableau
et faire ces opérations dans l'ordre 1-2 ou 2-1

Il faut donc disposer d'une DFT 1D correspondant à la taille d'une ligne N et d'une DFT 1D correspondant à la taille d'une colonne M.

Il faut alors se pencher sur l'organisation des données et sur ce que cela implique. Par exemple, le tableau 2D peut être rangé dans un grand tableau la première ligne puis la seconde etc. (Ceci correspond au rangement dans un tableau 2D du C Tab[N][M])
L'étape 1 correspond à faire la DFT (sur M points) de la première ligne Tab[0] puis de la seconde Tab[1] etc. jusqu'à la dernière Tab[N-1]. Il faut donc disposer d'une DFT 1D sur M points, les M points étant consécutifs en mémoire.
L'étape 2 traite des colonnes et les points ne sont plus consécutifs en mémoire (Pour la première colonne, les points sont Tab[0][0] puis Tab[1][0]) et les points dune colonne sont espacés de N points en mémoire.

Il faut donc disposer d'une fonction de DFT pouvant traiter un nombre P de points espacés de Q points en mémoire dans un tableau (1D) et il faudra adapter la fonction utilisée en ce sens, la plupart des fonctions (dont celle que vous évoquez) ne traitant que le cas où P=2^n et Q=1 (et réalise le calcul sur place)

Il faut également se poser la question de ce qu'est un point des données : les données de départ et les données d'arrivée sont fondamentalement des points complexes : où se trouve la partie imaginaire d'un point par rapport à la position de sa partie réelle ? juste derrière en mémoire ou dans un autre tableau ? L'algorithme utilisé doit tenir compte de cette contrainte.

[LukeS]

Merci pour toutes ces réponses.

les données de départ et les données d'arrivée sont fondamentalement des points complexes

Je ne comprends pas bien. Les données de départ ne sont pas complexe si ? ou alors elles sont complexes mais avec une partie imaginaire nulle ? Dans ce cas a-t-on vraiment besoin de cette partie imaginaire nulle ?

Si j'ai bien compris il faut que les données soient rangées dans un tableau à une dimension ligne par ligne et partie imaginaire a la suite de chaque partie réelle ?

Par contre, il m'a semblé voir qu'il fallait que la taille de chaque dimension soit une puissance de 2, ou je me trompe ?


edit : j'ai compris certaines choses, je pense, entre temps.

[diogene]

Je ne comprends pas bien. Les données de départ ne sont pas complexe si ? ou alors elles sont complexes mais avec une partie imaginaire nulle ? Dans ce cas a-t-on vraiment besoin de cette partie imaginaire nulle ?

Fondamentalement, les données de départ et d'arrivée sont complexes. Si les données de départ sont purement réelles, cela veut dire effectivement que les parties imaginaires sont nulles. Dans ce cas les données d'arrivée donneront des valeurs complexes avec en général des parties imaginaires non nulles.
Il existe des formes d'algorithme de calcul de la DFT qui s'appliquent spécifiquement à des données de départ réelles.
On peut également utiliser un algorithme de calcul plus général en ajoutant au tableau des données réelles des données imaginaires de départ nulles.

Si j'ai bien compris il faut que les données soient rangées dans un tableau à une dimension ligne par ligne et partie imaginaire a la suite de chaque partie réelle ?

Il n'y a pas d'obligation dans ce domaine excepté que les algos de calculs utilisés soient adaptés à l'organisation des données.

Par contre, il m'a semblé voir qu'il fallait que la taille de chaque dimension soit une puissance de 2, ou je me trompe ?

Cela dépend de l'algo utilisé. C'est vrai que la plupart de ceux qu'on trouve ça et là travaille avec un nombre de points qui doit être une puissance de 2.

[LukeS]

Cela dépend de l'algo utilisé. C'est vrai que la plupart de ceux qu'on trouve ça et là travaille avec un nombre de points qui doit être une puissance de 2.

Dans ces codes en questions, qu'est-ce qui impose cette condition ? Comment faire si le nombre de point n'est pas une puissance de deux ?

[diogene]

Dans ces codes en questions, qu'est-ce qui impose cette condition ?

Le fait qu'il soit "rapide". L'algorithme utilisé pour accélérer le calcul dépend du nombre de points.

Comment faire si le nombre de point n'est pas une puissance de deux ?

Chercher un algo rapide utilisable avec le nombre de points qu'on a. En dehors de l'algo de FFT applicable pour un nombre de points égal à une puissance de 2, il y a beaucoup d'autres possibilités, même pour le cas où ce nombre est premier, mais qui sont plus spécifiques, plus compliquées et moins courantes que l'algo FFT. Le problème se complique singulièrement si le nombre de points peut varier d'une fois sur l'autre.

D'aucuns envisagent de compléter les N données par des points supplémentaires mis à 0 pour atteindre un nombre total de points M qui est une puissance de 2 (zéro filling).
Il faut bien prendre conscience que le calcul ainsi effectué est différent du calcul initial et la validité de cette procédure dépend de comment on va interpréter le résultat obtenu et ce qu'on va en faire ensuite.
En effet, on cherchait la DFT sur N points soit

Vk=0..N-1 = Sommei=0..N-1(vi*Wik) avec W = e-2PIj/N

et on a ainsi calculé celle sur M points :

Vk=0..M-1 = Sommei=0..N-1(vi*Wik) avec W = e-2PIj/M

ce qui n'est pas la même chose.