EP05_04 — 🔴 Implementing the 2D DFT from the Definition

5.21.4 EP05_04 🔴 Implementing the 2D DFT from the Definition

A research laboratory in computational astronomy received, from an old mission, a small experimental sensor whose raw data cannot be processed by modern FFT libraries — the validation environment is isolated and only allows basic arithmetic operations. The team needs to reimplement the 2D Discrete Fourier Transform from the mathematical definition itself, cell by cell, to later compare bit by bit with np.fft.fft2 in another environment.

This is the most conceptual exercise on the list: there are no shortcuts. You will implement the double summation from Equation 5.1 directly, demonstrating why the FFT exists — and the computational cost it avoids.

5.21.4.1 📋 Implementation Guidelines

Dimensions: Read the integers \(M\) (rows) and \(N\) (columns) of the image \(f(x,y)\).
Data: Read the integer values of \(f(x,y)\), row by row.
2D DFT: For each frequency pair \((u,v)\) with \(u=0,\ldots,M-1\) and \(v=0,\ldots,N-1\), compute \[ 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)} \] using Euler’s identity \(e^{-j\theta} = \cos(\theta) - j\sin(\theta)\) to separate the real and imaginary parts — do not use any ready-made FFT function.
Magnitude: Compute \(|F(u,v)| = \sqrt{\text{Re}(F)^2 + \text{Im}(F)^2}\) and round to the nearest integer.
Output: Display the matrix of rounded magnitudes, \(M \times N\), in the same order (without fftshift — the DC remains at \((0,0)\)).

5.21.4.2 📌 Computational Constraints

Using FFT libraries is prohibited: the implementation must compute the double summations explicitly (nested loops), even if slower.
No fftshift: the output maintains the raw DFT convention, with the DC component at \(F(0,0)\) (upper-left corner).
Rounding: the final magnitude must be rounded to the nearest integer; in the test cases there is no .5 ambiguity.
Precision: small floating-point errors (on the order of \(10^{-6}\)) before rounding are expected and do not affect the final integer result.

5.21.4.3 🧠 Theoretical Foundation

Element	Meaning
\(F(0,0)\)	DC component — sum of all pixels, \(F(0,0) = \sum f(x,y)\)
Real part \(\text{Re}(F)\)	Projection of the signal onto cosines
Imaginary part \(\text{Im}(F)\)	Projection of the signal onto sines
Complexity of this implementation	\(\mathcal{O}((MN)^2)\) — this is why the FFT, with \(\mathcal{O}(MN\log(MN))\), is indispensable for real images

5.21.4.4 📦 Input and Output Specification (VPL)

Input:

Line 1: Integer \(M\).
Line 2: Integer \(N\).
Following lines: Integer elements of \(f(x,y)\), \(M\) lines.

Output:

Matrix of rounded magnitudes \(|F(u,v)|\), \(M \times N\), separated by spaces.

5.21.4.5 📌 Examples

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

🎮 Simulator EP05_04: 2D DFT — Direct Definition ΣΣ f(x,y) e^-j2π(…)

Click on the f(x,y) cells to change the values (click increments +1; Shift + click decrements -1) and watch |F(u,v)| recalculated live.

f(x,y) — Spatial Domain

|F(u,v)| — Magnitude (No Shift)

–

Figure 5.35: EP05_04 Simulator: Manual 2D DFT

%%writefile EP05_04.py
# Python code

Overwriting EP05_04.py

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

✔️ EP05_04.cases already exists in casos/
📋 5 case(s) loaded from casos/EP05_04.cases

🔍 Testing Python: EP05_04.py
⚠️ EP05_04.py: Empty file (fewer than 3 lines). Tests skipped.