EP05_04 — 🔴 Implementando la DFT 2D a partir de la definición

5.13.4 EP05_04 🔴 Implementando la DFT 2D a partir de la definición

Un laboratorio de investigación en astronomía computacional recibió, de una misión antigua, un pequeño sensor experimental cuyos datos brutos no pueden ser procesados por bibliotecas modernas de FFT — el entorno de validación está aislado y solo permite operaciones aritméticas básicas. El equipo necesita reimplementar la Transformada de Fourier Discreta 2D a partir de la propia definición matemática, célula por célula, para después comparar bit a bit con np.fft.fft2 en otro entorno.

Este es el ejercicio más conceptual de la lista: no hay atajos. Vas a implementar el doble sumatorio de la Ecuación 5.1 directamente, evidenciando por qué existe la FFT — y el costo computacional que evita.

5.13.4.1 📋 Directrices de implementación

Dimensiones: Leer los enteros \(M\) (filas) y \(N\) (columnas) de la imagen \(f(x,y)\).
Datos: Leer los valores enteros de \(f(x,y)\), fila a fila.
DFT 2D: Para cada par de frecuencias \((u,v)\) con \(u=0,\ldots,M-1\) y \(v=0,\ldots,N-1\), calcular \[ 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 la identidad de Euler \(e^{-j\theta} = \cos(\theta) - j\sin(\theta)\) para separar parte real e imaginaria — no se debe utilizar ninguna función de FFT predefinida.
Magnitud: Calcular \(|F(u,v)| = \sqrt{\text{Re}(F)^2 + \text{Im}(F)^2}\) y redondear al entero más cercano.
Salida: Mostrar la matriz de magnitudes redondeadas, \(M \times N\), en el mismo orden (sin fftshift — el DC permanece en \((0,0)\)).

5.13.4.2 📌 Restricciones computacionales

Prohibido usar bibliotecas de FFT: la implementación debe calcular los sumatorios dobles explícitamente (bucles anidados), aunque sea más lenta.
Sin fftshift: la salida mantiene la convención cruda de la DFT, con el componente DC en \(F(0,0)\) (esquina superior izquierda).
Redondeo: la magnitud final debe redondearse al entero más cercano; en los casos de prueba no hay ambigüedad .5.
Precisión: pequeños errores de punto flotante (del orden de \(10^{-6}\)) antes del redondeo son esperados y no afectan al resultado entero final.

5.13.4.3 🧠 Fundamentación teórica

Elemento	Significado
\(F(0,0)\)	Componente DC — suma de todos los píxeles, \(F(0,0) = \sum f(x,y)\)
Parte real \(\text{Re}(F)\)	Proyección de la señal sobre cosenos
Parte imaginaria \(\text{Im}(F)\)	Proyección de la señal sobre senos
Complejidad de esta implementación	\(\mathcal{O}((MN)^2)\) — por eso la FFT, con \(\mathcal{O}(MN\log(MN))\), resulta indispensable en imágenes reales

5.13.4.4 📦 Especificación de entrada y salida (VPL)

Entrada:

Línea 1: Entero \(M\).
Línea 2: Entero \(N\).
Líneas siguientes: Elementos enteros de \(f(x,y)\), \(M\) líneas.

Salida:

Matriz de magnitudes \(|F(u,v)|\) redondeadas, \(M \times N\), separadas por espacios.

5.13.4.5 📌 Ejemplos

Entrada	Salida	Observación
2 2 1 2 3 4	10 2 4 0	\(F(0,0)=1+2+3+4=10\) (DC = suma total). \(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\).

🎮 Simulador EP05_04: DFT 2D — Definición Directa ΣΣ f(x,y) e^-j2π(…)

Haz clic en las celdas de f(x,y) para cambiar los valores (incrementa +1; Shift + clic decrementa -1) y observa |F(u,v)| recalculado en vivo.

f(x,y) — Dominio Espacial

|F(u,v)| — Magnitud (Sin Shift)

–

Figura 5.35: Simulador EP05_04: DFT 2D manual

%%writefile EP05_04.cpp
// your solution

Overwriting EP05_04.cpp

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

✔️ EP05_04.cases ya existe en casos/
📋 5 caso(s) cargado(s) de casos/EP05_04.cases

🔍 Probando C++: EP05_04.cpp
⚠️ EP05_04.cpp: archivo vacío (menos de 3 líneas). Pruebas omitidas.