EP05_04 — 🔴 Implementazione della DFT 2D a partire dalla definizione

5.13.4 EP05_04 🔴 Implementazione della DFT 2D a partire dalla definizione

Un laboratorio di ricerca in astronomia computazionale ha ricevuto, da una missione remota, un piccolo sensore sperimentale i cui dati grezzi non possono essere elaborati tramite librerie moderne di FFT — l’ambiente di validazione è isolato e consente solo operazioni aritmetiche di base. Il team deve reimplementare la Trasformata di Fourier Discreta 2D a partire dalla definizione matematica stessa, cella per cella, per poi confrontare bit per bit con np.fft.fft2 in un altro ambiente.

Questo è l’esercizio più concettuale della lista: non ci sono scorciatoie. Dovrai implementare direttamente la doppia sommatoria della Equazione 5.1, evidenziando perché la FFT esiste — e il costo computazionale che essa evita.

5.13.4.1 📋 Linee guida per l’implementazione

Dimensioni: Leggere i numeri interi \(M\) (righe) e \(N\) (colonne) dell’immagine \(f(x,y)\).
Dati: Leggere i valori interi di \(f(x,y)\), riga per riga.
DFT 2D: Per ogni coppia di frequenze \((u,v)\) con \(u=0,\ldots,M-1\) e \(v=0,\ldots,N-1\), calcolare \[ 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)} \] usando l’identità di Eulero \(e^{-j\theta} = \cos(\theta) - j\sin(\theta)\) per separare la parte reale e quella immaginaria — non utilizzare alcuna funzione FFT predefinita.
Magnitudine: Calcolare \(|F(u,v)| = \sqrt{\text{Re}(F)^2 + \text{Im}(F)^2}\) e arrotondare all’intero più vicino.
Output: Visualizzare la matrice delle magnitudini arrotondate, \(M \times N\), nello stesso ordine (senza fftshift — il componente DC rimane in \((0,0)\)).

5.13.4.2 📌 Vincoli computazionali

Vietato l’uso di librerie FFT: l’implementazione deve calcolare esplicitamente le doppie sommatorie (cicli annidati), anche se più lenta.
Senza fftshift: l’output mantiene la convenzione grezza della DFT, con il componente DC in \(F(0,0)\) (angolo superiore sinistro).
Arrotondamento: la magnitudine finale deve essere arrotondata all’intero più vicino; nei casi di test non vi è ambiguità .5.
Precisione: piccoli errori di virgola mobile (ordine di \(10^{-6}\)) prima dell’arrotondamento sono previsti e non influenzano il risultato intero finale.

5.13.4.3 🧠 Fondamenti teorici

Elemento	Significato
\(F(0,0)\)	Componente DC — somma di tutti i pixel, \(F(0,0) = \sum f(x,y)\)
Parte reale \(\text{Re}(F)\)	Proiezione del segnale sui coseni
Parte immaginaria \(\text{Im}(F)\)	Proiezione del segnale sui seni
Complessità di questa implementazione	\(\mathcal{O}((MN)^2)\) — ecco perché la FFT, con \(\mathcal{O}(MN\log(MN))\), è indispensabile nelle immagini reali

5.13.4.4 📦 Specifica di input e output (VPL)

Input:

Riga 1: intero \(M\).
Riga 2: intero \(N\).
Righe successive: elementi interi di \(f(x,y)\), \(M\) righe.

Output:

Matrice delle magnitudini \(|F(u,v)|\) arrotondate, \(M \times N\), separate da spazio.

5.13.4.5 📌 Esempi

Input	Output	Osservazione
2 2 1 2 3 4	10 2 4 0	\(F(0,0)=1+2+3+4=10\) (DC = somma 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\).

🎮 Simulatore EP05_04: DFT 2D — Definizione Diretta ΣΣ f(x,y) e^-j2π(…)

Clicca sulle celle di f(x,y) per modificarne i valori (incrementa +1; Shift + clic decrementa -1) e osserva |F(u,v)| ricalcolato in tempo reale.

f(x,y) — Dominio Spaziale

|F(u,v)| — Magnitudine (Senza Shift)

–

Figura 5.35: Simulatore EP05_04: DFT 2D manuale

%%writefile EP05_04.py
# Codice Python

Overwriting EP05_04.py

TestSuite("EP05_04.py").run()

✔️ EP05_04.cases esiste già in casos/
📋 5 caso/i caricato/i da casos/EP05_04.cases

🔍 Test di Python: EP05_04.py
⚠️ EP05_04.py: file vuoto (meno di 3 righe). Test saltati.