EP05_04 — 🔴 Implémentation de la TFD 2D à partir de la définition

5.13.4 EP05_04 🔴 Implémentation de la TFD 2D à partir de la définition

Un laboratoire de recherche en astronomie computationnelle a reçu, d’une mission ancienne, un petit capteur expérimental dont les données brutes ne peuvent pas être traitées par les bibliothèques modernes de FFT — l’environnement de validation est isolé et ne permet que des opérations arithmétiques de base. L’équipe doit réimplémenter la Transformée de Fourier Discrète 2D à partir de la définition mathématique elle-même, cellule par cellule, pour ensuite comparer bit à bit avec np.fft.fft2 dans un autre environnement.

C’est l’exercice le plus conceptuel de la liste : il n’y a pas de raccourcis. Vous allez implémenter la double sommation de la Équation 5.1 directement, en mettant en évidence pourquoi la FFT existe — et le coût computationnel qu’elle évite.

5.13.4.1 📋 Directives d’implémentation

Dimensions : Lire les entiers \(M\) (lignes) et \(N\) (colonnes) de l’image \(f(x,y)\).
Données : Lire les valeurs entières de \(f(x,y)\), ligne par ligne.
TFD 2D : Pour chaque paire de fréquences \((u,v)\) avec \(u=0,\ldots,M-1\) et \(v=0,\ldots,N-1\), calculer \[ F(u,v) = \sum_{x=0}^{M-1}\sum_{y=0}^{N-1} f(x,y)\, e^{-j2\pi\left(\frac{ux}{M}+\frac{vy}{N}\right)} \] en utilisant l’identité d’Euler \(e^{-j\theta} = \cos(\theta) - j\sin(\theta)\) pour séparer les parties réelle et imaginaire — n’utilisez aucune fonction de FFT prête à l’emploi.
Magnitude : Calculer \(|F(u,v)| = \sqrt{\text{Re}(F)^2 + \text{Im}(F)^2}\) et arrondir à l’entier le plus proche.
Sortie : Afficher la matrice des magnitudes arrondies, \(M \times N\), dans le même ordre (sans fftshift — la composante DC reste en \((0,0)\)).

5.13.4.2 📌 Contraintes computationnelles

Interdiction d’utiliser des bibliothèques de FFT : l’implémentation doit calculer les double sommations explicitement (boucles imbriquées), même si c’est plus lent.
Sans fftshift : la sortie conserve la convention brute de la TFD, avec la composante DC en \(F(0,0)\) (coin supérieur gauche).
Arrondi : la magnitude finale doit être arrondie à l’entier le plus proche ; dans les cas de test, il n’y a pas d’ambiguïté .5.
Précision : de petites erreurs de virgule flottante (de l’ordre de \(10^{-6}\)) avant l’arrondi sont attendues et n’affectent pas le résultat entier final.

5.13.4.3 🧠 Fondement théorique

Élément	Signification
\(F(0,0)\)	Composante DC — somme de tous les pixels, \(F(0,0) = \sum f(x,y)\)
Partie réelle \(\text{Re}(F)\)	Projection du signal sur les cosinus
Partie imaginaire \(\text{Im}(F)\)	Projection du signal sur les sinus
Complexité de cette implémentation	\(\mathcal{O}((MN)^2)\) — c’est pourquoi la FFT, avec \(\mathcal{O}(MN\log(MN))\), est indispensable pour les images réelles

5.13.4.4 📦 Spécification d’entrée et de sortie (VPL)

Entrée :

Ligne 1 : Entier \(M\).
Ligne 2 : Entier \(N\).
Lignes suivantes : Éléments entiers de \(f(x,y)\), \(M\) lignes.

Sortie :

Matrice des magnitudes \(|F(u,v)|\) arrondies, \(M \times N\), séparées par des espaces.

5.13.4.5 📌 Exemples

Entrée	Sortie	Remarque
2 2 1 2 3 4	10 2 4 0	\(F(0,0)=1+2+3+4=10\) (DC = somme totale). \(F(0,1)=(1-2)+(3-4)=-2 \to \|F\|=2\). \(F(1,0)=(1+2)-(3+4)=-4\to\|F\|=4\). \(F(1,1)=(1-2)-(3-4)=0\).

🎮 Simulateur EP05_04 : DFT 2D — Définition directe ΣΣ f(x,y) e^-j2π(…)

Cliquez sur les cellules de f(x,y) pour modifier les valeurs (incrément +1 ; Maj + clic décrément -1) et voyez |F(u,v)| recalculé en direct.

f(x,y) — Domaine spatial

|F(u,v)| — Magnitude (sans décalage)

–

Figure 5.35: Simulateur EP05_04: DFT 2D manuel

%%writefile EP05_04.cpp
// your solution

Overwriting EP05_04.cpp

TestSuite("EP05_04.cpp").run()

✔️ EP05_04.cases existe déjà dans casos/
📋 5 cas chargé(s) depuis casos/EP05_04.cases

🔍 Test de C++ : EP05_04.cpp
⚠️ EP05_04.cpp : fichier vide (moins de 3 lignes). Tests ignorés.