Maîtrise d'informatique - Module 18
|
Vous ne pouvez aborder la deuxième séance de travaux pratiques que si le programme de TFR unidimensionnelle écrit lors de la première séance de travaux pratiques est exact. En effet, vous allez travailler à partir de ce programme. Si les tests de validation proposés à la fin de la première séance n'ont pas été concluants, veuillez cliquer sur le canot de sauvetage ci-dessous, afin de consulter la liste des erreurs les plus souvent commises. Si cela n'est pas suffisant, veuillez vous adresser à un enseignant.
Travaillez sur une copie tfr1D.c du fichier tfr.c écrit lors de la première séance de travaux pratiques.
1- Modifiez signal_discret de telle manière que le signal discret soit à valeurs complexes. Modifiez aussi la fonction init_spectre :
void init_spectre(float signal_discret[N][2],float spectre[N][2])
Dans la fonction main, on trouvera l'appel init_spectre(signal_discret,spectre) pour le calcul de la TFR et l'appel init_spectre(spectre,spectre) pour le calcul de la TFR inverse.
2- Modifiez la fonction init_w :
void init_w(float w[N/2][2],int sens)
Dans la fonction main, on trouvera l'appel init_w(w,1) pour le calcul de la TFR, l'appel init_w(w,-1) pour le calcul de la TFR inverse.
3- Modifiez la fonction tfr :
void tfr(float spectre[N][2],float w[N/2][2],int sens)
Dans la fonction main, on trouvera l'appel tfr(spectre,w,1) pour le calcul de la TFR et l'appel tfr(spectre,w,-1) pour le calcul de la TFR inverse.
4- Ecrivez une fonction affiche qui affiche les valeurs d'un tableau de complexes (partie réelle et partie imaginaire), ainsi que les modules de ces complexes :
void affiche(float s[N][2])
5- Modifiez la fonction main de telle façon que le programme contenu dans le fichier tfr1D.c :
Validez votre programme en utilisant les données de test de la première séance de travaux pratiques.
La transformation de Fourier bidimensionnelle d'une fonction complexe de deux variables réelles f(x,y) a été vue en cours : c'est une généralisation de la transformation de Fourier unidimensionnelle, dans laquelle l'intégrale simple devient une intégrale double :
(1)
Or, on peut réécrire l'égalité (1) sous la forme suivante :
(2)
Cette écriture peut être interprétée de la façon suivante : pour calculer la transformée de Fourier d'un signal bidimensionnel, on peut d'abord calculer la transformée de Fourier unidimensionnelle de chacune de ses lignes (c'est l'expression qui apparaît entre crochets dans (2)), puis calculer ensuite la transformée de Fourier unidimensionnelle de chacune des colonnes.
Quant à la transformation de Fourier inverse bidimensionnelle, elle s'obtient par généralisation de la transformation de Fourier inverse unidimensionnelle, par la formule :
(3)
Il a été également vu en cours la définition de la transformation de Fourier discrète (TFD) unidimensionnelle, ainsi que la formule de la transformation de Fourier discrète inverse (TFD-1) unidimensionnelle. La TFD bidimensionnelle associe au signal complexe discret bidimensionnel le spectre complexe discret bidimensionnel donné par :
(4)
L'égalité (4) peut être réécrite sous la forme suivante :
(5)
Dans cette écriture, on réalise d'abord la TFD unidimensionnelle des lignes (expression entre crochets), puis la TFD unidimensionnelle des colonnes. Quant à la TFD-1 bidimensionnelle, on peut vérifier qu'elle est donnée par :
(6)
Là encore, on peut réécrire (6) sous la forme suivante :
(7)
Dans cette écriture, on réalise d'abord la TFD-1 unidimensionnelle des lignes (expression entre crochets), puis la TFD-1 unidimensionnelle des colonnes.
Dans la suite de cette séance de travaux pratiques, vous allez programmer les algorithmes de la transformation de Fourier rapide (TFR) et de la transformation de Fourier rapide inverse (TFR-1) d'un signal bidimensionnel. Plutôt que de tout réécrire depuis le début, vous allez réutiliser le programme que vous avez déjà écrit, et vous vous servirez des définitions (5) et (7) de la TFD et de la TFD-1 bidimensionnelles. Pour éviter d'avoir à calculer tantôt la TFR des lignes, tantôt celle des colonnes, vous écrirez, un peu plus loin, la fonction de transposition d'une matrice à valeurs complexes, fonction qui permettra de transformer les lignes d'une matrice carrée en colonnes et vice versa.
Dans ce paragraphe, N désigne une constante (que vous fixerez à 256). Il vous est demandé d'écrire dans le fichier convert_tfr2D.c le source d'un programme de conversion : convert_tfr2D
Lisez l'ensemble du paragraphe 3.2. avant de commencer à programmer.
1- convert_tfr2D accepte trois paramètres :
Si sens vaut 1...
... c'est que fichier_in stocke un tableau du type : unsigned char tab[N][N]. Les NxN éléments de ce tableau représentent des entiers positifs (compris entre 0 et 255). fichier_in est un fichier binaire sans en-tête de NxN octets. Dans ce fichier, les NxN éléments du tableau ont été stockés séquentiellement, ligne par ligne (fichier au format "brut" .brt).
convert_tfr2D convertit ces entiers en complexes. Il produit un fichier fichier_out, binaire et sans en-tête, de NxNx2xsizeof(float)octets. Dans ce fichier, les complexes sont stockés séquentiellement. Chacun occupe 2xsizeof(float)octets consécutifs : les sizeof(float) premiers pour la partie réelle, les sizeof(float) autres pour la partie imaginaire (nulle).
Si sens vaut -1...
... c'est que fichier_in stocke un tableau du type : float tab[N][N][2]. Ce tableau représente un ensemble de NxN complexes. fichier_in est un fichier binaire sans en-tête de NxNx2xsizeof(float)octets.
Le programme convert_tfr2D écrit dans fichier_out les modules de ces complexes. Chaque module est représenté par une valeur de type unsigned char. Tout module supérieur à 255 est assimilé à 255. Le fichier fichier_out désigne donc un fichier de NxN octets (fichier au format "brut" .brt).
2- Dans convert_tfr2D.c, vous écrirez principalement les fonctions suivantes :
void ecrire_complexes(char* nom_fichier,float s[N][N][2])
void lire_complexes(char* nom_fichier,float s[N][N][2])
void ecrire_modules(char* nom_fichier,float s[N][N][2])
void lire_modules(char* nom_fichier,float s[N][N][2])
La fonction ecrire_complexes stocke dans le fichier nom_fichier les NxN complexes pointés par s. La taille du fichier sera de NxNx2xsizeof(float) octets. La fonction lire_complexes effectue l'opération inverse : initialisation de s à partir des données lues dans nom_fichier.
La fonction ecrire_modules stocke dans le fichier nom_fichier les modules des NxN complexes pointés par s. La taille du fichier sera de NxN octets. La fonction lire_modules effectue l'opération inverse : initialisation de s à partir des données lues dans nom_fichier, chaque complexe étant supposé réel positif. Pour le calcul des (valeurs approchées des) modules, ecrire_modules peut faire appel à une fonction modu_comp2 :
unsigned char modu_comp2(float c[2])
Si vous éprouvez des difficultés pour manipuler les fonctions de lecture/écriture dans des fichiers en langage C, cliquez sur le canot de sauvetage ci-dessous :
3- Avant de passer à la suite, il est prudent de valider ce programme de conversion ! Vous pouvez par exemple utiliser le code ci-après (où N doit cette fois être fixé à 2). A vous bien sûr d'écrire affiche2 (en retouchant légèrement la fonction affiche définie dans le paragraphe 2, point 4).
int main(void)
{
float s[N][N][2]={{{1.,-1.},{2.,-2.}},{{3.,-3.},{4.,-4.}}};
float t[N][N][2];
ecrire_complexes("ajeter1",s);
lire_complexes("ajeter1",t);
affiche2(t);
printf("\n");
ecrire_modules("ajeter2",t);
lire_modules("ajeter2",s);
affiche2(s);
exit(0);
}
Travaillez sur une copie tfr2D.c du fichier tfr1D.c et fixez N à 256 et P à 8.
1- Ecrivez une fonction transpose, qui transpose une matrice carrée de complexes :
void transpose(float s[N][N][2])
2- Supprimez la fonction affiche et remplacez-la par les fonctions ecrire_complexes et lire_complexes définies au paragraphe 3.2, point 2.
3- Modifiez la fonction main de telle façon que le programme contenu dans le fichier tfr2D.c accepte trois paramètres :
Si sens vaut 1, tfr2D.c :
Si sens vaut -1, tfr2D.c :
Dans le répertoire /home/mod18g0/TS/tests, vous trouverez les fichiers tp02test01.brt et tp02test02.brt, pour lesquels les constantes N et P ont été fixées respectivement aux valeurs 256 et 8. Effectuez une recopie de ces deux fichiers sur votre compte.
1- Lancez successivement les commandes suivantes :
convert_tfr2D tp02test01.brt tp02test01.comp 1
tfr2D tp02test01.comp tp02test02.comp 1
convert_tfr2D tp02test02.comp tp02test02_bis.brt -1
tfr2D tp02test02.comp tp02test03.comp -1
convert_tfr2D tp02test03.comp tp02test03.brt -1
2- Le fichier tp02test02_bis.brt contient donc l'image "brute" de la transformée de Fourier de tp02test01.brt, et doit être identique au fichier tp02test02.brt. Quant au fichier tp02test03.brt, il contient l'image "brute" de la transformée de Fourier inverse de tp02test02_bis.brt, c'est-à-dire que son contenu doit être le même que celui de tp02test01.brt. Comparez ces fichiers visuellement, à l'aide de Khoros.
Remarque :
La commande UNIX cmp permet de comparer deux fichiers quelconques : si cmp fichier1 fichier2 n'affiche aucun message, alors les fichiers fichier1 et fichier2 sont identiques. Cependant, si vous utilisez cette commande pour tester la validité de vos programmes tfr2D et convert_tfr2D, vous risquez de ne pas obtenir un résultat concluant, à cause d'une simple différence d'arrondi en un seul pixel ! Pour cette raison, il est préférable d'effectuer les comparaisons de fichiers de manière visuelle.
La prochaine séance de travaux pratiques débutera par l'intégration dans Cantata des opérateurs définis par tfr2D et convert_tfr2D.