DCT (Discrete Cosine Transform): convertendo pixels em frequências

DCT (Discrete Cosine Transform): convertendo pixels em frequências

Olá leitor, seja muito bem vindo de volta a mais uma etapa da nossa jornada aqui no Portal da Micilini 😊

Este é o nono artigo da nossa série de ~25, e é, sem exagero, o coração absoluto de tudo o que estamos construindo. Se a série inteira fosse um filme, este artigo seria o clímax.

Deixa eu te situar rapidinho onde estamos:

Agora que temos os blocos 8×8 em mãos, chegou a hora de fazer a mágica de verdade: pegar aqueles 64 pixels de um bloco e transformá-los em 64 frequências.

Eu prometi no fim do artigo 8 que este seria o mais denso e fascinante da série. Então pega um café bem forte ☕, respira fundo, e vamos com calma, porque quando a ficha cair, você nunca mais vai olhar pra um JPEG do mesmo jeito.

O problema: por que transformar pixels em frequências?

Vamos começar com a pergunta óbvia: por que raios a gente ia querer transformar pixels em frequências? O pixel já não é a coisa mais fundamental da imagem?

A resposta é que o pixel é ótimo pra mostrar a imagem, mas é péssimo pra comprimir a imagem.

Pensa comigo. Um bloco 8×8 tem 64 pixels. Cada pixel é meio "independente" do outro, você não consegue olhar pra um pixel e dizer "esse aqui é redundante, pode jogar fora", uma vez que todos parecem igualmente importantes.

Mas e se existisse uma forma de reorganizar esses 64 valores de um jeito onde uns poucos valores concentram quase toda a informação importante, e o resto vira quase-zero?

Aí sim a compressão fica fácil: você guarda os poucos valores importantes com precisão, e joga fora (ou guarda com pouca precisão) os que são quase-zero. E o olho humano quase não percebe a diferença.

É exatamente isso que a DCT faz. Ela não joga nada fora (ela é 100% reversível).

Ela só reorganiza a energia do bloco de um jeito que deixa a compressão trivial no passo seguinte.

Guarda essa frase, porque ela é a alma deste artigo:

A DCT não comprime nada. Ela reorganiza a informação pra que a quantização (próximo artigo) possa comprimir com o mínimo de perda visível.

O que é "frequência" numa imagem?

A palavra "frequência" normalmente nos faz pensar em som. Um som grave é uma onda de baixa frequência (varia devagar), um som agudo é uma onda de alta frequência (varia rápido).

Numa imagem, o conceito é o mesmo, só que no espaço em vez do tempo. A gente chama isso de frequência espacial:

Uma analogia que ajuda: imagina que você está passando a mão numa superfície de olhos fechados.

E aqui está a sacada que faz tudo funcionar: o olho humano é muito mais sensível às baixas frequências do que às altas.

Se você borrar levemente a textura de um cabelo (alta frequência), quase ninguém percebe. Mas se você borrar o contorno geral de um rosto (baixa frequência), todo mundo percebe na hora.

A DCT nos dá exatamente a ferramenta pra separar essas duas coisas.

Depois que separamos, a quantização vai poder ser generosa com as baixas frequências (guarda com precisão) e agressiva com as altas (joga a maior parte fora).

E é aí que mora a compressão do JPEG 🤗

A grande sacada: todo bloco é uma soma de ondas de cosseno

Agora vem a ideia central, e ela é linda.

A DCT parte de uma afirmação matemática que parece maluca na primeira vez que você ouve (ou lê):

Qualquer bloco de 8×8 pixels, não importa o quão complexo, pode ser escrito como uma soma de 64 padrões fixos de cosseno, cada um multiplicado por um peso.

Ou seja, existem 64 "padrões base" (chamados de basis functions), que são sempre os mesmos pra qualquer imagem do mundo. A única coisa que muda de bloco pra bloco é o peso de cada padrão.

Pensa numa analogia musical. Um acorde complexo de piano pode parecer um som único e indivisível.

Mas na verdade ele é a soma de várias notas puras tocadas juntas, cada uma com um volume (peso) diferente.

Se você souber quais notas e com que volume, você reconstrói o acorde perfeitamente.

A DCT faz isso com imagem. Os 64 "padrões de cosseno" são as "notas puras". Os 64 coeficientes que a DCT calcula são os "volumes" de cada nota.

Junte tudo de volta e você tem o bloco original, pixel por pixel 🤓

Visualizando as 64 funções base

Vamos imaginar essa grade de 64 padrões. Ela é uma matriz 8×8 de "mini-imagens", cada uma 8×8:

freq horizontal  →  0   1   2   3   4   5   6   7
                          ┌───┬───┬───┬───┬───┬───┬───┬───┐
freq vertical  0          │ ▓ │▐ ▌│▐▐▌│...│   │   │   │   │
    ↓                     ├───┼───┼───┼───┼───┼───┼───┼───┤
               1          │▀▀▀│   │   │   │   │   │   │   │
                          ├───┼───┼───┼───┼───┼───┼───┼───┤
               2          │   │   │   │   │   │   │   │   │
                          ├───┼───┼───┼───┼───┼───┼───┼───┤
              ...         │   │   │   │   │   │   │   │▞▞│
                          └───┴───┴───┴───┴───┴───┴───┴───┘

O que você precisa entender dessa grade:

Então, quando a DCT processa um bloco, ela responde a pergunta: "quanto de cada um desses 64 padrões eu preciso somar pra reconstruir esse bloco exato?"

A resposta é uma nova matriz 8×8 de coeficientes (os pesos).

E aqui está o pulo do gato: pra imagens reais (que são majoritariamente suaves), os pesos dos padrões de baixa frequência (canto superior esquerdo) são grandes, e os pesos dos padrões de alta frequência (canto inferior direito) são quase zero.

Foi essa reorganização que a gente estava buscando desde o começo 😉

A matemática da DCT-II

Dito isso, chegou a hora de aprendermos uma nova formula matemática!

Você não precisa fugir dela, porque ela é mais amigável do que parece. A versão que os CODECs usam é a famosa DCT-II bidimensional:

F(u,v) = (1/4) · C(u) · C(v) · Σ Σ  f(x,y) · cos[(2x+1)·u·π / 16] · cos[(2y+1)·v·π / 16]
                                x y

onde:
  f(x,y)  = valor do pixel na posição (x,y) do bloco  (já com level shift)
  F(u,v)  = coeficiente da frequência (u,v)
  x, y    = variam de 0 a 7  (posição do pixel)
  u, v    = variam de 0 a 7  (frequência)
  C(k)    = 1/√2  se k = 0
          = 1     caso contrário

Vamos destrinchar cada pedaço com calma:

O somatório duplo Σ Σ: é usado para calcular UM coeficiente F(u,v), você varre todos os 64 pixels do bloco e vai somando as contribuições. Faz isso 64 vezes (uma pra cada (u,v)) e tem a matriz completa de coeficientes.

Os dois cossenos: um cuida da direção horizontal (x e u), o outro da vertical (y e v). É a "pergunta" que mede o quanto aquele padrão de frequência específico aparece no bloco. Se o bloco combina bem com aquele padrão, a soma dá um número grande. Se não combina, dá perto de zero.

O C(u)·C(v): são fatores de normalização. Aquele 1/√2 no DC existe só pra deixar a transformada matematicamente "ortonormal" (o que garante que a inversa reconstrói o bloco exato). Não precisa perder o sono com o porquê — é um ajuste de escala.

O 1/4: mais normalização. Pra um bloco 8×8, esse fator é 2/N = 2/8 = 1/4 (aplicado uma vez pra cada dimensão: (1/√(2/N))... enfim, no fim das contas dá 1/4).

E o level shift? 🤨

Antes de aplicar a DCT, o JPEG subtrai 128 de cada pixel. Os pixels vêm no range 0..255, e depois do shift ficam em -128..127, centralizados no zero. Por quê?

Porque assim o coeficiente DC passa a representar o desvio em relação ao cinza médio (128), e não o brilho absoluto.

Isso mantém os números menores e centrados, o que ajuda tanto na precisão numérica quanto na codificação lá na frente. Na hora de decodificar, a gente soma 128 de volta.

DC e AC: o significado dos coeficientes

Se a sua ideia é trabalhar com CODECs daqui em diante, DC e AC serão dois nomes que vão te acompanhar nesta jornada.

Coeficiente DC (posição 0,0 — canto superior esquerdo): é o coeficiente de frequência zero. Ele representa o valor médio de todo o bloco. Se o bloco é um pedaço de céu azul claro, o DC carrega esse "azul claro médio". É de longe o coeficiente mais importante e mais energético do bloco.

O nome "DC" vem da eletrônica: Direct Current (corrente contínua), aquela que não varia. DC é a parte do bloco que "não varia".

Coeficientes AC (todos os outros 63): representam as variações em torno dessa média — os detalhes, as bordas, as texturas. O nome vem de Alternating Current (corrente alternada), a que varia.

Quanto mais pra baixo e pra direita na matriz, mais alta a frequência daquele coeficiente AC, e (pra imagens reais) menor tende a ser seu valor.

Energy compaction: por que isso comprime de verdade

"Energy compaction" (compactação de energia) é o nome técnico da propriedade mágica da DCT, e é o motivo dela existir nos CODECs.

A ideia: depois da DCT, a energia do bloco (a soma dos quadrados dos coeficientes) fica concentrada em pouquíssimos coeficientes, quase todos no canto superior esquerdo.

Isso não é papo teórico. No fim do artigo você vai rodar um programa que prova isso com números reais.

Só pra adiantar o que você vai ver: no bloco de exemplo clássico do JPEG, 86% de toda a energia fica só no coeficiente DC, e 97% fica no quadrante 4×4 de baixas frequências.

Os outros 48 coeficientes de alta frequência dividem entre si os 3% restantes.

Pega a implicação disso: se 97% da informação está em 16 coeficientes, dá pra ser bem "descuidado" com os outros 48 sem estragar a imagem.

É essa margem que a quantização vai explorar pra comprimir no próximo artigo.

Implementação 1: a DCT "naive" (didática)

Agora que já sabemos grande parte da teoria, vamos direto pro código, onde vamos implementar a DCT 🤗

A primeira implementação que iremos fazer neste momento é chamada de naive (ingênua).

Ela nada mais é do que a tradução literal da fórmula, letra por letra. E diga-se de passagem: ela é lenta, porém é cristalina a ponto de você ler o código e ver a fórmula acontecendo.

A gente vai usar ela pra entender e validar uma versão rápida. 

Um detalhe de produção logo de cara: os cossenos da fórmula dependem só da posição e da frequência, nunca do conteúdo do bloco.

Então seria um desperdício absurdo chamar cos() dentro do loop pra cada pixel de cada bloco. Em vez disso, a gente pré-calcula todos os cossenos uma vez numa tabela e depois só faz multiplicação.

Isso é o que separa uma DCT de brinquedo de uma DCT séria.  

Dito isso, eu recomendo você criar uma pasta chamada codec-dct-test, e dentro dela um arquivo chamado main.c, com o seguinte código:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// ============================================================
// CONSTANTES
// ============================================================

#define BLOCK_SIZE 8
#define PI 3.14159265358979323846

// ============================================================
// ESTRUTURAS (reaproveitadas do artigo 8)
// ============================================================

typedef struct {
    double valores[BLOCK_SIZE][BLOCK_SIZE];
} Bloco8x8;

// ============================================================
// TABELAS PRÉ-CALCULADAS DA DCT
// ============================================================
//
// A DCT usa cossenos que dependem SÓ da posição e da frequência,
// nunca do conteúdo do bloco. Então calculamos todos os cossenos
// UMA vez, no início do programa, e reusamos em todos os blocos.
//
//   tabela_cos[freq][pos] = cos( (2*pos + 1) * freq * PI / 16 )
//
// Isso é o que separa uma DCT "de brinquedo" (que chama cos()
// milhões de vezes) de uma DCT real (que só faz multiplicações).

double tabela_cos[BLOCK_SIZE][BLOCK_SIZE];
double alpha[BLOCK_SIZE];

void inicializar_tabelas_dct(void) {
    for (int freq = 0; freq < BLOCK_SIZE; freq++) {
        // alpha[0] = 1/raiz(2) normaliza o coeficiente DC;
        // as demais frequências usam alpha = 1
        alpha[freq] = (freq == 0) ? (1.0 / sqrt(2.0)) : 1.0;

        for (int pos = 0; pos < BLOCK_SIZE; pos++) {
            tabela_cos[freq][pos] =
                cos((2.0 * pos + 1.0) * freq * PI / (2.0 * BLOCK_SIZE));
        }
    }
}

// ============================================================
// IMPLEMENTAÇÃO 1 — DCT NAIVE 2D (DIDÁTICA)
// ============================================================
//
// Tradução direta da fórmula matemática. Para cada um dos 64
// coeficientes de saída, varremos os 64 pixels de entrada.
// São 64 x 64 = 4096 multiplicações por bloco.
//
// É lenta, mas é a que mostra EXATAMENTE o que a fórmula faz.
// Usamos ela só pra entender e pra validar a versão rápida.
//
// Repare no "- 128.0": esse é o LEVEL SHIFT do JPEG. Os pixels
// vêm no range 0..255, e antes da DCT centralizamos em torno de
// zero (range -128..127). Isso faz o coeficiente DC representar
// o desvio em relação ao cinza médio, e mantém os números menores.

void dct_naive(Bloco8x8 *entrada, Bloco8x8 *saida) {
    for (int fr = 0; fr < BLOCK_SIZE; fr++) {          // freq vertical
        for (int fc = 0; fc < BLOCK_SIZE; fc++) {      // freq horizontal
            double soma = 0.0;
            for (int lin = 0; lin < BLOCK_SIZE; lin++) {
                for (int col = 0; col < BLOCK_SIZE; col++) {
                    double pixel = entrada->valores[lin][col] - 128.0;
                    soma += pixel
                          * tabela_cos[fr][lin]
                          * tabela_cos[fc][col];
                }
            }
            saida->valores[fr][fc] = 0.25 * alpha[fr] * alpha[fc] * soma;
        }
    }
}

// A INVERSA naive: reconstrói os pixels a partir dos coeficientes.
void idct_naive(Bloco8x8 *entrada, Bloco8x8 *saida) {
    for (int lin = 0; lin < BLOCK_SIZE; lin++) {
        for (int col = 0; col < BLOCK_SIZE; col++) {
            double soma = 0.0;
            for (int fr = 0; fr < BLOCK_SIZE; fr++) {
                for (int fc = 0; fc < BLOCK_SIZE; fc++) {
                    soma += alpha[fr] * alpha[fc]
                          * entrada->valores[fr][fc]
                          * tabela_cos[fr][lin]
                          * tabela_cos[fc][col];
                }
            }
            saida->valores[lin][col] = 0.25 * soma + 128.0;  // desfaz o level shift
        }
    }
}

// ============================================================
// IMPLEMENTAÇÃO 2 — DCT SEPARÁVEL 2D (PRODUÇÃO)
// ============================================================
//
// A sacada: a DCT 2D é SEPARÁVEL. Em vez de varrer 64 pixels
// pra cada coeficiente, fazemos:
//   1. Uma DCT 1D em cada LINHA  (8 DCTs de 8 pontos)
//   2. Uma DCT 1D em cada COLUNA do resultado (mais 8 DCTs)
//
// Custo: 8 linhas x 64 + 8 colunas x 64 = 1024 multiplicações.
// Contra 4096 da naive. 4x mais rápido, resultado IDÊNTICO.
// É essa a versão que o nosso CODEC vai usar de verdade.

// DCT 1D de um vetor de 8 amostras.
void dct_1d(double entrada[BLOCK_SIZE], double saida[BLOCK_SIZE]) {
    for (int freq = 0; freq < BLOCK_SIZE; freq++) {
        double soma = 0.0;
        for (int pos = 0; pos < BLOCK_SIZE; pos++)
            soma += entrada[pos] * tabela_cos[freq][pos];
        saida[freq] = 0.5 * alpha[freq] * soma;
    }
}

// IDCT 1D de um vetor de 8 coeficientes.
void idct_1d(double entrada[BLOCK_SIZE], double saida[BLOCK_SIZE]) {
    for (int pos = 0; pos < BLOCK_SIZE; pos++) {
        double soma = 0.0;
        for (int freq = 0; freq < BLOCK_SIZE; freq++)
            soma += alpha[freq] * entrada[freq] * tabela_cos[freq][pos];
        saida[pos] = 0.5 * soma;
    }
}

void dct_separavel(Bloco8x8 *entrada, Bloco8x8 *saida) {
    double temp[BLOCK_SIZE][BLOCK_SIZE];

    // Passo 1: level shift + DCT 1D em cada linha
    for (int lin = 0; lin < BLOCK_SIZE; lin++) {
        double linha_in[BLOCK_SIZE], linha_out[BLOCK_SIZE];
        for (int col = 0; col < BLOCK_SIZE; col++)
            linha_in[col] = entrada->valores[lin][col] - 128.0;
        dct_1d(linha_in, linha_out);
        for (int col = 0; col < BLOCK_SIZE; col++)
            temp[lin][col] = linha_out[col];
    }

    // Passo 2: DCT 1D em cada coluna do resultado
    for (int col = 0; col < BLOCK_SIZE; col++) {
        double col_in[BLOCK_SIZE], col_out[BLOCK_SIZE];
        for (int lin = 0; lin < BLOCK_SIZE; lin++)
            col_in[lin] = temp[lin][col];
        dct_1d(col_in, col_out);
        for (int lin = 0; lin < BLOCK_SIZE; lin++)
            saida->valores[lin][col] = col_out[lin];
    }
}

void idct_separavel(Bloco8x8 *entrada, Bloco8x8 *saida) {
    double temp[BLOCK_SIZE][BLOCK_SIZE];

    // Passo 1: IDCT 1D em cada coluna
    for (int col = 0; col < BLOCK_SIZE; col++) {
        double col_in[BLOCK_SIZE], col_out[BLOCK_SIZE];
        for (int lin = 0; lin < BLOCK_SIZE; lin++)
            col_in[lin] = entrada->valores[lin][col];
        idct_1d(col_in, col_out);
        for (int lin = 0; lin < BLOCK_SIZE; lin++)
            temp[lin][col] = col_out[lin];
    }

    // Passo 2: IDCT 1D em cada linha + desfaz o level shift
    for (int lin = 0; lin < BLOCK_SIZE; lin++) {
        double linha_in[BLOCK_SIZE], linha_out[BLOCK_SIZE];
        for (int col = 0; col < BLOCK_SIZE; col++)
            linha_in[col] = temp[lin][col];
        idct_1d(linha_in, linha_out);
        for (int col = 0; col < BLOCK_SIZE; col++)
            saida->valores[lin][col] = linha_out[col] + 128.0;
    }
}

// ============================================================
// UTILITÁRIOS DE IMPRESSÃO E ANÁLISE
// ============================================================

void imprimir_bloco(const char *titulo, Bloco8x8 *b, const char *fmt) {
    printf("%s\n", titulo);
    for (int lin = 0; lin < BLOCK_SIZE; lin++) {
        printf("  ");
        for (int col = 0; col < BLOCK_SIZE; col++)
            printf(fmt, b->valores[lin][col]);
        printf("\n");
    }
    printf("\n");
}

// Quanto da energia total está no coeficiente DC (canto sup. esq.)?
double energia_no_dc(Bloco8x8 *F) {
    double dc = F->valores[0][0] * F->valores[0][0];
    double total = 0.0;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++)
            total += F->valores[r][c] * F->valores[r][c];
    return 100.0 * dc / total;
}

// Quanto da energia está no quadrante 4x4 de baixas frequências?
double energia_baixas_freq(Bloco8x8 *F) {
    double baixas = 0.0, total = 0.0;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++) {
            double e = F->valores[r][c] * F->valores[r][c];
            total += e;
            if (r < 4 && c < 4) baixas += e;
        }
    return 100.0 * baixas / total;
}

// ============================================================
// MAIN — Demonstração completa da DCT
// ============================================================

int main() {
    inicializar_tabelas_dct();

    printf("=== DCT 8x8: convertendo pixels em frequencias ===\n\n");

    // ---------- Bloco 1: exemplo clássico do JPEG ----------
    Bloco8x8 bloco = {{
        {52, 55, 61, 66, 70, 61, 64, 73},
        {63, 59, 55, 90,109, 85, 69, 72},
        {62, 59, 68,113,144,104, 66, 73},
        {63, 58, 71,122,154,106, 70, 69},
        {67, 61, 68,104,126, 88, 68, 70},
        {79, 65, 60, 70, 77, 68, 58, 75},
        {85, 71, 64, 59, 55, 61, 65, 83},
        {87, 79, 69, 68, 65, 76, 78, 94}
    }};

    imprimir_bloco("Bloco de pixels original (canal Y, valores 0-255):",
                   &bloco, "%5.0f ");

    // ---------- Aplicar as duas DCTs ----------
    Bloco8x8 coef_naive, coef_sep;
    dct_naive(&bloco, &coef_naive);
    dct_separavel(&bloco, &coef_sep);

    imprimir_bloco("Coeficientes DCT (canto sup. esq. = DC):",
                   &coef_sep, "%8.2f");

    // ---------- Provar que naive == separavel ----------
    double max_diff = 0.0;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++) {
            double d = fabs(coef_naive.valores[r][c] - coef_sep.valores[r][c]);
            if (d > max_diff) max_diff = d;
        }
    printf("Naive vs Separavel: diferenca maxima = %.12f ", max_diff);
    printf("%s\n", (max_diff < 1e-9) ? "(IDENTICAS)" : "(ERRO!)");
    printf("  -> Naive: 4096 multiplicacoes/bloco\n");
    printf("  -> Separavel: 1024 multiplicacoes/bloco (4x menos)\n\n");

    // ---------- Roundtrip lossless ----------
    Bloco8x8 reconstruido;
    idct_separavel(&coef_sep, &reconstruido);

    double max_err = 0.0;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++) {
            double d = fabs(reconstruido.valores[r][c] - bloco.valores[r][c]);
            if (d > max_err) max_err = d;
        }
    printf("Roundtrip DCT -> IDCT: erro maximo = %.12f ", max_err);
    printf("%s\n\n", (max_err < 1e-6) ? "(LOSSLESS)" : "(perdas!)");

    // ---------- Energy compaction ----------
    printf("Energy compaction do bloco:\n");
    printf("  DC sozinho:        %6.2f%% da energia\n", energia_no_dc(&coef_sep));
    printf("  Quadrante 4x4 low: %6.2f%% da energia\n\n", energia_baixas_freq(&coef_sep));

    // ---------- Comparação: bloco suave x bloco xadrez ----------
    Bloco8x8 suave, coef_suave;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++)
            suave.valores[r][c] = 100.0 + 3.0 * r + 2.0 * c;  // gradiente suave
    dct_separavel(&suave, &coef_suave);

    Bloco8x8 xadrez, coef_xadrez;
    for (int r = 0; r < BLOCK_SIZE; r++)
        for (int c = 0; c < BLOCK_SIZE; c++)
            xadrez.valores[r][c] = ((r + c) % 2) ? 200.0 : 50.0;  // alta freq
    dct_separavel(&xadrez, &coef_xadrez);

    printf("Bloco SUAVE  -> baixas freq (4x4) concentram %.2f%% da energia\n",
           energia_baixas_freq(&coef_suave));
    printf("Bloco XADREZ -> baixas freq (4x4) concentram apenas %.2f%%\n",
           energia_baixas_freq(&coef_xadrez));
    printf("  (no xadrez, a energia vai toda pro canto inferior direito:\n");
    printf("   coeficiente de frequencia maxima [7][7] = %.1f)\n\n",
           coef_xadrez.valores[7][7]);

    printf("=> A DCT nao jogou nenhum dado fora (e reversivel).\n");
    printf("   Ela so REORGANIZOU a energia pro canto superior esquerdo.\n");
    printf("   Quem vai jogar dado fora e a QUANTIZACAO (artigo 10)!\n");

    return 0;
}

Para compilar e rodar esse projeto, basta usar os comandos abaixo:

cd ~/codec-dct-test
gcc main.c -o dct -lm
./dct

Dito isso, vamos entender o funcionamento desse código parte por parte 🙃

inicializar_tabelas_dct(): pré-calcula todos os cossenos e os fatores alpha uma única vez. Depois disso, nenhuma função da DCT chama cos() de novo, só multiplicação. Essa é a diferença entre didático e usável.

dct_naive(): a tradução literal da fórmula. Quatro loops aninhados: os dois de fora escolhem qual coeficiente (fr, fc) estamos calculando, os dois de dentro varrem os 64 pixels somando as contribuições.

Repare no - 128.0, que é o level shift, e no 0.25 * alpha[fr] * alpha[fc], que é a normalização. Se você comparar linha a linha com a fórmula lá de cima, é a mesma coisa.

dct_separavel(): a versão de produção. Explora o fato de que a DCT 2D pode ser feita como duas passadas de DCT 1D: primeiro em cada linha, depois em cada coluna.

O truque matemático é que o 0.25 da versão 2D se fatora em 0.5 (primeira passada) × 0.5 (segunda passada), e os alpha se aplicam naturalmente em cada passada. Resultado: exatamente os mesmos coeficientes, com 4× menos multiplicações.

idct_separavel(): o caminho de volta. Mesma lógica, na ordem inversa (colunas primeiro, depois linhas), e no fim soma 128 de volta pra desfazer o level shift. É essa função que o decoder do nosso CODEC vai usar pra reconstruir a imagem.

energia_no_dc() e energia_baixas_freq(): medem quanto da energia total do bloco está concentrada onde. É a prova numérica do energy compaction.

Os resultados: vendo a mágica acontecer

Ao rodar o projeto do DCT, você vai ver exatamente isto:

=== DCT 8x8: convertendo pixels em frequencias ===

Bloco de pixels original (canal Y, valores 0-255):
     52    55    61    66    70    61    64    73
     63    59    55    90   109    85    69    72
     62    59    68   113   144   104    66    73
     63    58    71   122   154   106    70    69
     67    61    68   104   126    88    68    70
     79    65    60    70    77    68    58    75
     85    71    64    59    55    61    65    83
     87    79    69    68    65    76    78    94

Coeficientes DCT (canto sup. esq. = DC):
   -415.38  -30.19  -61.20   27.24   56.12  -20.10   -2.39    0.46
      4.47  -21.86  -60.76   10.25   13.15   -7.09   -8.54    4.88
    -46.83    7.37   77.13  -24.56  -28.91    9.93    5.42   -5.65
    -48.53   12.07   34.10  -14.76  -10.24    6.30    1.83    1.95
     12.12   -6.55  -13.20   -3.95   -1.88    1.75   -2.79    3.14
     -7.73    2.91    2.38   -5.94   -2.38    0.94    4.30    1.85
     -1.03    0.18    0.42   -2.42   -0.88   -3.02    4.12   -0.66
     -0.17    0.14   -1.07   -4.19   -1.17   -0.10    0.50    1.68

Naive vs Separavel: diferenca maxima = 0.000000000000 (IDENTICAS)
  -> Naive: 4096 multiplicacoes/bloco
  -> Separavel: 1024 multiplicacoes/bloco (4x menos)

Roundtrip DCT -> IDCT: erro maximo = 0.000000000000 (LOSSLESS)

Energy compaction do bloco:
  DC sozinho:         86.04% da energia
  Quadrante 4x4 low:  97.19% da energia

Bloco SUAVE  -> baixas freq (4x4) concentram 99.96% da energia
Bloco XADREZ -> baixas freq (4x4) concentram apenas 0.76%
  (no xadrez, a energia vai toda pro canto inferior direito:
   coeficiente de frequencia maxima [7][7] = -492.6)

=> A DCT nao jogou nenhum dado fora (e reversivel).
   Ela so REORGANIZOU a energia pro canto superior esquerdo.
   Quem vai jogar dado fora e a QUANTIZACAO (artigo 10)!

Vamos ler esses números com atenção, porque cada linha conta uma história diferente...

A matriz de coeficientes: olha o coeficiente DC no canto superior esquerdo: -415.38. É de longe o maior em módulo, agora olha o canto inferior direito: valores como 1.68, -0.66, 0.46. Minúsculos. Ou seja, a energia despencou do canto superior esquerdo pro inferior direito, exatamente como prometido.  

💡 Curiosidade: esse bloco de exemplo (52, 55, 61...) é o mesmo bloco usado no artigo clássico do JPEG na Wikipedia. Se você jogar esses coeficientes em qualquer implementação de referência da DCT no mundo, vai bater esse -415.38 no DC. É basicamente o "Hello, World" da DCT 😊

Naive vs Separável: diferença = 0: as duas implementações produzem coeficientes idênticos até a última casa decimal. Isso prova que a otimização separável não é uma aproximação: é matematicamente a mesma transformada, só que 4× mais barata.

Roundtrip lossless: erro = 0: aplicamos DCT e depois IDCT, e voltamos ao bloco original sem perder nada. Isso confirma que a DCT sozinha não perde informação. Ela é uma via de mão dupla perfeita.

Energy compaction: 86% no DC, 97% no 4×4: a prova numérica de tudo. Com 97% da informação em 16 dos 64 coeficientes, temos uma margem gigantesca pra comprimir os outros 48.

Suave (99,96%) vs Xadrez (0,76%): Um bloco suave joga quase toda a energia nas baixas frequências (ótimo pra comprimir). Já o xadrez de alta frequência faz o oposto: joga tudo pro canto inferior direito (aquele -492.6 na posição [7][7], a frequência máxima).

É por isso que texturas complexas comprimem pior que céus lisos, elas têm energia nas altas frequências, que a DCT não consegue "empacotar" no canto.  

A DCT sozinha NÃO comprime

Preciso bater nessa tecla porque é o mal-entendido número um de quem tá aprendendo CODECs.

Olhando os números acima, alguém poderia perguntar: "peraí, mas se a DCT é reversível e não perde nada, ela também não ganha nada, certo? Continuam sendo 64 números."

Exatamente. E isso está 100% correto.

A DCT transforma 64 pixels em 64 coeficientes. Mesma quantidade de números. Se você guardasse os 64 coeficientes com precisão total, o arquivo até ficaria maior (porque coeficientes são números fracionários, ocupam mais que um unsigned char).

Então onde está a compressão? Ela vem de dois passos que ainda estão por vir:

Ou seja: a DCT é a preparação do terreno. Ela reorganiza a energia de um jeito que faz a quantização poder ser agressiva onde o olho não liga, e conservadora onde o olho é exigente.

Sem a DCT, a quantização não teria como saber "o que é detalhe fino" e "o que é a estrutura importante" do bloco.

É um trabalho em equipe. A DCT separa, a quantização joga fora, o RLE+Huffman empacota.

E a DCT ultra-rápida que a libjpeg usa?

Você deve estar pensando: "a separável é 4× mais rápida que a naive, mas será que dá pra ir além?"

Dá, e muito. Existe uma família de algoritmos chamados fast DCT que exploram simetrias trigonométricas pra derrubar o número de multiplicações drasticamente.

Os mais famosos são o AAN (Arai-Agui-Nakajima) e o Loeffler-Ligtenberg-Moschytz.

Pra você ter noção da escala:

O algoritmo de Loeffler faz uma DCT 1D de 8 pontos com apenas 11 multiplicações (o mínimo teórico é 11, provado matematicamente). Aplicando nas 8 linhas + 8 colunas, dá aquelas ~176 por bloco.

O preço é que o código fica bem mais obscuro: vira uma sequência de somas e multiplicações "mágicas" que não parecem em nada com a fórmula original.

Além disso, os algoritmos fast normalmente produzem coeficientes com uma escala diferente, e essa escala precisa ser "absorvida" dentro da tabela de quantização.

E é aí que está a beleza da coisa: como o próximo passo (quantização) já vai dividir cada coeficiente por um valor mesmo, dá pra embutir o fator de escala do fast DCT de graça dentro da tabela de quantização.

A libjpeg faz exatamente isso no modo JDCT_IFAST.

Pro nosso CODEC, vamos manter a DCT separável por enquanto ela é rápida o bastante, é fácil de validar, e o código é legível.

Quando chegarmos na fase de otimização, a gente troca por um Loeffler e dobra a escala na quantização. Fica anotado esse gancho pro futuro 😉

Resumo: o coração está batendo

Recapitulando o artigo mais importante da série até aqui:

No próximo artigo, vamos pegar essa matriz de coeficientes e finalmente fazer a compressão com perdas acontecer: a quantização.

É lá que a gente decide, coeficiente por coeficiente, quanto de precisão vale a pena guardar. É o passo onde o "qualidade 90%" e o "qualidade 20%" do JPEG nascem.

Prepara o café de novo, porque agora que a DCT reorganizou a energia, a quantização vai ensinar o nosso CODEC a jogar fora exatamente o que o olho não vê. É onde a compressão de verdade começa 🚀

Até o artigo 10!