EP05_04 — 🔴 Implementando a DFT 2D a Partir da Definição

5.13.4 EP05_04 🔴 Implementando a DFT 2D a Partir da Definição

Um laboratório de pesquisa em astronomia computacional recebeu, de uma missão antiga, um pequeno sensor experimental cujos dados brutos não podem ser processados por bibliotecas modernas de FFT — o ambiente de validação é isolado e só permite operações aritméticas básicas. A equipe precisa reimplementar a Transformada de Fourier Discreta 2D a partir da própria definição matemática, célula por célula, para depois comparar bit a bit com np.fft.fft2 em outro ambiente.

Este é o exercício mais conceitual da lista: não há atalhos. Você vai implementar o duplo somatório da Equação 5.1 diretamente, evidenciando por que a FFT existe — e o custo computacional que ela evita.

5.13.4.1 📋 Diretrizes de Implementação

Dimensões: Ler os inteiros \(M\) (linhas) e \(N\) (colunas) da imagem \(f(x,y)\).
Dados: Ler os valores inteiros de \(f(x,y)\), linha a linha.
DFT 2D: Para cada par de frequências \((u,v)\) com \(u=0,\ldots,M-1\) e \(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 a identidade de Euler \(e^{-j\theta} = \cos(\theta) - j\sin(\theta)\) para separar parte real e imaginária — não utilize nenhuma função de FFT pronta.
Magnitude: Calcular \(|F(u,v)| = \sqrt{\text{Re}(F)^2 + \text{Im}(F)^2}\) e arredondar para o inteiro mais próximo.
Saída: Exibir a matriz de magnitudes arredondadas, \(M \times N\), na mesma ordem (sem fftshift — o DC permanece em \((0,0)\)).

5.13.4.2 📌 Restrições Computacionais

Proibido usar bibliotecas de FFT: a implementação deve calcular os somatórios duplos explicitamente (laços aninhados), mesmo que mais lenta.
Sem fftshift: a saída mantém a convenção crua da DFT, com o componente DC em \(F(0,0)\) (canto superior esquerdo).
Arredondamento: a magnitude final deve ser arredondada para o inteiro mais próximo; nos casos de teste não há ambiguidade .5.
Precisão: pequenos erros de ponto flutuante (ordem de \(10^{-6}\)) antes do arredondamento são esperados e não afetam o resultado inteiro final.

5.13.4.3 🧠 Fundamentação Teórica

Elemento	Significado
\(F(0,0)\)	Componente DC — soma de todos os pixels, \(F(0,0) = \sum f(x,y)\)
Parte real \(\text{Re}(F)\)	Projeção do sinal sobre cossenos
Parte imaginária \(\text{Im}(F)\)	Projeção do sinal sobre senos
Complexidade desta implementação	\(\mathcal{O}((MN)^2)\) — por isso a FFT, com \(\mathcal{O}(MN\log(MN))\), é indispensável em imagens reais

5.13.4.4 📦 Especificação de Entrada e Saída (VPL)

Entrada:

Linha 1: Inteiro \(M\).
Linha 2: Inteiro \(N\).
Linhas seguintes: Elementos inteiros de \(f(x,y)\), \(M\) linhas.

Saída:

Matriz de magnitudes \(|F(u,v)|\) arredondadas, \(M \times N\), separadas por espaço.

5.13.4.5 📌 Exemplos

Entrada	Saída	Observação
2 2 1 2 3 4	10 2 4 0	\(F(0,0)=1+2+3+4=10\) (DC = soma 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 — Definição Direta ΣΣ f(x,y) e^-j2π(…)

Clique nas células de f(x,y) para alterar os valores (incrementa +1; Shift + clique decrementa -1) e veja |F(u,v)| recalculado ao vivo.

f(x,y) — Domínio Espacial

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

–

Figura 5.35: Simulador EP05_04: DFT 2D manual

%%writefile EP05_04.py
# Código Python

Writing EP05_04.py

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

✔️ EP05_04.cases já existe em casos/
📋 5 caso(s) carregado(s) de casos/EP05_04.cases

🔍 Testando Python: EP05_04.py
⚠️ EP05_04.py: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.