Refinando o N.148i antes do julgamento

Refinando o N.148i antes do julgamento

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

Este é o décimo oitavo artigo da nossa série, e ele nasceu de uma inquietação. 🤔

No artigo passado, a gente fechou o ciclo: o N.148i comprime e descomprime imagens de verdade. O plano original era partir direto pro benchmark contra JPEG, PNG e WebP. Mas aí eu parei pra pensar numa coisa:

Faz sentido colocar o nosso codec no ringue sabendo que ele tem fraquezas que dá pra corrigir? 🥊

Não faz. Seria como entrar numa corrida com o pneu murcho de propósito. Então, antes do julgamento, vamos fazer uma passagem de refinamento e corrigir três coisas que ficaram pendentes:

E já adianto: o terceiro item é o mais pesado da lista, e sozinho vai derrubar o tamanho dos nossos arquivos em cerca de 25%. 😱

Pega um café bem reforçado ☕, porque tem bastante coisa boa aqui. Bora! 🚀

Refinamento 1: upsampling bilinear 

Vamos começar pelo mais leve.

Lembra do que a gente fez no decoder? Como os canais Cb e Cr estão pela metade (por causa do 4:2:0), na volta a gente precisavamos esticar eles de novo. E a forma que usamos foi a mais simples possível: o vizinho mais próximo.

Na prática, cada valor de cor era simplesmente copiado pelos 4 pixels do seu grupo 2×2:

Chroma (2x2):        Esticado com vizinho mais próximo (4x4):
┌────┬────┐          ┌────┬────┬────┬────┐
│ 10 │ 90 │          │ 10 │ 10 │ 90 │ 90 │
├────┼────┤    →     ├────┼────┼────┼────┤
│ 20 │ 80 │          │ 10 │ 10 │ 90 │ 90 │
└────┴────┘          ├────┼────┼────┼────┤
                     │ 20 │ 20 │ 80 │ 80 │
                     ├────┼────┼────┼────┤
                     │ 20 │ 20 │ 80 │ 80 │
                     └────┴────┴────┴────┘

Isso funciona, mas repara no problema: entre o 10 e o 90 existe um degrau brusco. A cor pula de um valor pro outro sem transição nenhuma, criando pequenos "quadradinhos" de cor. 🧱 

A interpolação bilinear resolve isso calculando valores intermediários. Em vez de copiar o vizinho, ela faz uma média ponderada dos quatro vizinhos mais próximos, dando mais peso pros que estão mais perto:

Esticado com bilinear (4x4):
┌────┬────┬────┬────┐
│ 10 │ 30 │ 70 │ 90 │   ← transição suave!
├────┼────┼────┼────┤
│ 12 │ 32 │ 68 │ 88 │
├────┼────┼────┼────┤
│ 18 │ 38 │ 62 │ 82 │
├────┼────┼────┼────┤
│ 20 │ 40 │ 60 │ 80 │
└────┴────┴────┴────┘

Muito mais natural, né? 😍 E a cor da imagem fica visivelmente mais suave nas bordas.

O detalhe do meio-pixel

Aqui tem uma sutileza que quase todo mundo erra na primeira vez, e vale a pena entender.

Quando a gente mapeia um pixel da imagem grande pra uma coordenada na imagem pequena, a conta ingênua seria cx = px / 2.

Porém, analisando mais de perto, isso está ligeiramente errado, e desloca a imagem meio pixel pro lado.

O motivo: um pixel não é um ponto, é um quadradinho com área. O "centro" do pixel px fica na posição px + 0.5.

E quando você reduz pela metade, esse centro vai parar em (px + 0.5) / 2. Pra voltar pra "coordenada de pixel" na imagem pequena, subtrai 0,5 de novo:

cx = (px + 0.5) * escala - 0.5

Sem esse ajuste, a camada de cor fica desalinhada da camada de brilho, e a imagem ganha uma leve franja colorida nas bordas. Com ele, os dois grids ficam certinhos um sobre o outro.

Chegou a hora do código

A função de amostragem bilinear fica assim:

// Bilinear sampling of a chroma plane at a fractional position.
// Instead of grabbing the nearest sample, we blend the four
// neighbours according to how close each one is.
static double sample_bilinear(Plane *p, double x, double y) {
    int x0 = (int) floor(x);
    int y0 = (int) floor(y);
    double fx = x - x0;                 // how far between x0 and x0+1
    double fy = y - y0;

    double top    = plane_sample(p, x0,     y0)     * (1.0 - fx)
                  + plane_sample(p, x0 + 1, y0)     * fx;
    double bottom = plane_sample(p, x0,     y0 + 1) * (1.0 - fx)
                  + plane_sample(p, x0 + 1, y0 + 1) * fx;

    return top * (1.0 - fy) + bottom * fy;
}

A lógica é: primeiro interpola horizontalmente na linha de cima (top), depois na linha de baixo (bottom), e por fim interpola verticalmente entre as duas. Daí o nome "bi-linear", ou seja, duas interpolações lineares. 🧮

Repara que ela usa o nosso velho plane_sample(), que já limita as coordenadas às bordas. Então mesmo quando a conta pede o pixel -1 ou um além do limite, tudo funciona sem estourar memória.

E no merge_channels(), a gente passa a escolher entre os dois modos:  

if (smooth) {
    // Map the pixel centre into chroma coordinates.
    // The -0.5 / +0.5 keeps the two grids properly aligned.
    double cx = (px + 0.5) * scale_x - 0.5;
    double cy = (py + 0.5) * scale_y - 0.5;
    blue_diff = sample_bilinear(cb, cx, cy) - 128.0;
    red_diff  = sample_bilinear(cr, cx, cy) - 128.0;
} else {
    int cx = (int)(px * scale_x);
    int cy = (int)(py * scale_y);
    blue_diff = plane_sample(cb, cx, cy) - 128.0;
    red_diff  = plane_sample(cr, cx, cy) - 128.0;
}

E aqui está a beleza desse refinamento: agora estamos comparando na mesma imagem, com a mesma qualidade:

Upsampling  │ Tamanho  │  PSNR
────────────┼──────────┼──────────
nearest     │ 2290 B   │ 33,79 dB
bilinear    │ 2290 B   │ 34,70 dB   ← +0,91 dB de graça! 🎁

Exatamente o mesmo tamanho de arquivo, e quase 1 dB a mais de qualidade. 🤯

Por que de graça? Porque o upsampling acontece só no decoder. O arquivo não muda nada, onde os bytes são idênticos. A gente só ficou mais esperto na hora de reconstruir.

É o tipo de melhoria mais bonita que existe: custo zero, ganho real. 💎

Refinamento 2: liberando os módulos 4:4:4 e 4:2:2

Lembra do artigo 3, quando estudamos os modos de chroma subsampling? A gente aprendeu os três, mas na prática o nosso codec só usava o 4:2:0.

Relembrando rapidinho o que cada um faz com os canais de cor:

Agora vamos deixar os três disponíveis de verdade, onde a mudança principal é generalizar a função que encolhe os canais. Antes ela era fixa em 2×2; agora ela recebe o "passo" em cada direção:

void chroma_dimensions(int mode, int width, int height, int *cw, int *ch) {
    switch (mode) {
        case CHROMA_MODE_422:                 // half width, full height
            *cw = (width + 1) / 2;  *ch = height;            break;
        case CHROMA_MODE_420:                 // half width, half height
            *cw = (width + 1) / 2;  *ch = (height + 1) / 2;  break;
        default:                              // 4:4:4 - no shrinking
            *cw = width;            *ch = height;            break;
    }
}

// Averages the chroma samples that share one output sample.
// step_x / step_y say how many pixels are grouped in each direction.
static void downsample_plane(unsigned char *full, int w, int h,
                             Plane *out, int step_x, int step_y) {
    for (int y = 0; y < out->height; y++) {
        for (int x = 0; x < out->width; x++) {
            int sum = 0, count = 0;
            for (int dy = 0; dy < step_y; dy++) {
                for (int dx = 0; dx < step_x; dx++) {
                    int sx = x * step_x + dx;
                    int sy = y * step_y + dy;
                    if (sx >= w) sx = w - 1;      // clamp on odd sizes
                    if (sy >= h) sy = h - 1;
                    sum += full[(long) sy * w + sx];
                    count++;
                }
            }
            out->data[(long) y * out->width + x] =
                (unsigned char)((sum + count / 2) / count);   // rounded average
        }
    }
}

Repara como ficou genérico: com step_x=2, step_y=2 temos 4:2:0; com step_x=2, step_y=1 temos 4:2:2; e com ambos em 1, temos 4:4:4. Uma função só, três modos.

E o melhor: o decoder não precisou de nenhuma mudança especial. Como o merge_channels() calcula a escala olhando o tamanho real dos planos (cb->width / w), ele se adapta sozinho a qualquer modo.

Isso é sinal de que a arquitetura estava bem desenhada. 😎

Rodando os três modos na mesma imagem, teremos:

Chroma  │ Tamanho  │  PSNR    │ Observação
────────┼──────────┼──────────┼───────────────────────
4:4:4   │ 3257 B   │ 36,71 dB │ melhor qualidade
4:2:2   │ 2656 B   │ 35,74 dB │ meio-termo
4:2:0   │ 2290 B   │ 34,70 dB │ menor arquivo

Olha o trade-off clássico aparecendo com números reais! Do 4:4:4 pro 4:2:0, o arquivo encolhe 30% e o PSNR cai 2 dB.

E aqui vale uma reflexão importante: os 2 dB de diferença não são tão visíveis quanto os números sugerem.

Como a gente descobriu no artigo 15 (quando olhamos os canais separados), o olho humano é muito ruim pra perceber detalhe de cor. Por isso o 4:2:0 é o padrão de fato na indústria, a economia compensa demais a perda.

Mas agora você tem a escolha. Pra uma foto de paisagem, 4:2:0 é perfeito. Pra uma imagem com texto colorido ou bordas de cor muito nítidas (tipo um screenshot), o 4:4:4 pode valer a pena.

Refinamento 3: tabelas de Huffman sob medida

Chegamos ao item mais pesado, e o que mais impacta o tamanho do arquivo.

Desde o artigo 13, a gente vem usando as tabelas padrão do JPEG (as do Anexo K). Elas foram criadas nos anos 80, com base nas estatísticas médias de um conjunto de imagens de teste.

Repara na palavra: médias. 🤨

Essas tabelas são um compromisso pensado pra funcionar razoavelmente bem em qualquer imagem. Mas a sua imagem não é a média. Se você comprime uma foto de um céu azul, os símbolos que aparecem são bem diferentes dos de uma foto cheia de textura.

Lembra do princípio do Huffman (artigo 6)? Símbolos frequentes devem ter códigos curtos. Se a tabela genérica dá um código de 8 bits pra um símbolo que aparece o tempo todo na sua imagem, você está desperdiçando bits em cada ocorrência.

A solução é fazer o que os encoders profissionais fazem: construir uma tabela sob medida pra cada imagem.

E para isso, podemos usar uma das grandes estratégias que visam codificar em duas passadas! 🔄

Mas tem um problema de galinha e ovo aqui: pra construir a tabela ótima, você precisa saber as frequências de cada símbolo.

E pra saber as frequências... você precisa processar a imagem inteira. 🐔🥚

A solução é fazer duas passadas:

Sim, isso dobra o tempo de codificação. É o preço a pagar, e todo encoder que usa tabelas otimizadas paga (o libjpeg chama isso de modo "optimize"). 💰

O perigo das duas passadas: Aqui mora uma armadilha traiçoeira, em que diz que as duas passadas precisam produzir exatamente os mesmos símbolos, se elas discordarem em um único bloco, a tabela vai estar errada e o arquivo sai corrompido.

E é fácil discordarem por descuido, bastando apenas você mexer numa das passadas e esquecer da outra.

A minha solução foi extrair a lógica pra um lugar só: uma função tokenize_block() que transforma um bloco na sua lista de símbolos.

As duas passadas chamam essa mesma função. Uma conta os símbolos, a outra escreve, mas a lista vem da mesma fonte:  

// Both passes need exactly the same symbols: pass 1 only counts
// them, pass 2 writes them. Doing the work in ONE place means the
// two passes can never disagree.

typedef struct {
    int symbol;      // the Huffman symbol
    int extra_bits;  // how many amplitude bits follow
    int extra_value; // the amplitude itself
    int is_dc;       // which table this symbol belongs to
} Token;

static int tokenize_block(double block[8][8], const int quant[8][8],
                          int *dc_prev, Token *tokens) {
    /* ... DCT, quantização, zig-zag e RLE, gerando a lista ... */
}

Esse padrão (extrair a parte comum pra impossibilitar a divergência) é o mesmo raciocínio que usamos no artigo 17 quando criamos o tables.c.

E é uma das lições de engenharia mais valiosas da série. 🧠 

Agora a parte matematicamente interessante. Como construir a melhor tabela possível a partir das frequências?

O algoritmo clássico de Huffman (artigo 6) monta uma árvore juntando sempre os dois nós menos frequentes.

Mas o JPEG usa uma variação esperta: em vez de montar a árvore com ponteiros, ele calcula apenas o comprimento do código de cada símbolo, que é tudo que a gente precisa pra montar uma tabela canônica. 🎯

E tem duas complicações práticas que o JPEG resolve:

Complicação 1 — o limite de 16 bits. 📏

O nosso formato guarda o comprimento dos códigos em 16 posições. Mas o algoritmo de Huffman puro pode gerar códigos de 20, 25 bits, se a distribuição for muito desequilibrada.

A solução é um algoritmo de "achatamento" (Anexo K.3 da especificação) que redistribui os códigos longos demais, encurtando eles à força e alongando outros de compensação.

Isso custa uma perdinha mínima de compressão, mas mantém tudo dentro do limite:

// Squeezes any code longer than 16 bits down into 16 (JPEG Annex K.3).
// It costs a tiny bit of compression but keeps the format simple.
static void limit_to_16_bits(int bits[33]) {
    for (int i = 32; i > 16; i--) {
        while (bits[i] > 0) {
            int j = i - 2;
            while (bits[j] == 0) j--;

            bits[i]     -= 2;              // take two long codes...
            bits[i - 1] += 1;              // ...turn one into a shorter one
            bits[j + 1] += 2;              // ...and split a shorter pair
            bits[j]     -= 1;
        }
    }
    /* ... */
}

Complicação 2 — o símbolo reservado. 🎭

Tem um detalhe curioso: o algoritmo adiciona um símbolo fantasma com frequência 1, que depois é descartado. Por quê?

Porque isso garante que nenhum símbolo real receba um código formado só por bits 1 (tipo 1111111111111111).

Alguns decodificadores usam esse padrão como marcador especial, e ter um símbolo real com esse código causaria confusão.

É uma proteção elegante: o símbolo fantasma "ocupa" a pior posição e some. 👻

O código completo fica no módulo novo huffman.c:

#define RESERVED 256

static void compute_code_sizes(const long freq_in[256], int code_size[257]) {
    long freq[257];
    int  others[257];

    for (int i = 0; i < 256; i++) freq[i] = freq_in[i];
    freq[RESERVED] = 1;                    // the reserved symbol

    for (int i = 0; i <= 256; i++) { code_size[i] = 0; others[i] = -1; }

    for (;;) {
        // Find the two least frequent symbols still in play.
        // On a tie we take the HIGHEST index, exactly like the spec.
        int v1 = -1, v2 = -1;
        long min1 = 0, min2 = 0;

        for (int i = 0; i <= 256; i++) {
            if (freq[i] == 0) continue;
            if (v1 < 0 || freq[i] <= min1) { v2 = v1; min2 = min1; v1 = i; min1 = freq[i]; }
            else if (v2 < 0 || freq[i] <= min2) { v2 = i; min2 = freq[i]; }
        }

        if (v2 < 0) break;                 // only one symbol left: done

        // Merge v2 into v1
        freq[v1] += freq[v2];
        freq[v2]  = 0;

        // Everyone in v1's chain gets one bit longer
        code_size[v1]++;
        while (others[v1] != -1) { v1 = others[v1]; code_size[v1]++; }

        others[v1] = v2;                   // link the two chains

        code_size[v2]++;
        while (others[v2] != -1) { v2 = others[v2]; code_size[v2]++; }
    }
}

Aquele array others é o truque que substitui a árvore: ele encadeia os símbolos que já foram agrupados, pra que quando um grupo cresça, todos os membros dele ganhem um bit a mais.

É a árvore de Huffman disfarçada de lista ligada...

Guardando as tabelas no arquivo 💾

Tem uma consequência óbvia de usar tabelas customizadas: o decoder não tem como adivinhar elas. Se cada imagem tem a sua tabela, ela precisa viajar junto com o arquivo.

Então o nosso formato evolui de novo... Bem-vindo à versão 3! 🎉

Campo        │ Tamanho  │ Exemplo
─────────────┼──────────┼──────────────
Assinatura   │ 5 bytes  │ "N148I"
Versão       │ 1 byte   │ 3          👈 subiu!
Largura      │ 4 bytes  │ 320
Altura       │ 4 bytes  │ 240
Qualidade    │ 1 byte   │ 50
Chroma       │ 1 byte   │ 2 (= 4:2:0)
Otimizado    │ 1 byte   │ 1          👈 NOVO!
Tam. dados   │ 4 bytes  │ 2145
─────────────┴──────────┴──────────────
Total: 21 bytes, seguidos das tabelas (se otimizado = 1)

Aquele campo optimized diz ao decoder: "as tabelas vêm logo depois do cabeçalho" ou "use as tabelas padrão". Assim o formato continua suportando os dois modos. 🔀

E o formato de cada tabela é o mesmo do JPEG, bem econômico:

// Each table is stored as: 16 bytes of BITS, then the symbol list.
// The symbol count is the sum of BITS, so it needs no extra field.
int write_huffman_tables(FILE *f, HuffSpec specs[4]) {
    for (int t = 0; t < 4; t++) {
        for (int l = 1; l <= 16; l++) write_u8(f, (uint8_t) specs[t].bits[l]);
        fwrite(specs[t].values, 1, specs[t].value_count, f);
    }
    return 1;
}

Repara na economia: a gente não precisa guardar a quantidade de símbolos, porque ela é a soma dos 16 valores de BITS. E não precisa guardar os códigos em si, porque eles são reconstruídos canonicamente.

Quanto custam as tabelas? 🤔

Essa é a pergunta certa a se fazer. Se as tabelas ocupam espaço no arquivo, será que compensa?

Na nossa imagem de teste, as quatro tabelas juntas ocuparam 124 bytes. E a economia foi de 758 bytes, ou seja, compensou com folga. 💰

Mas atenção a uma nuance honesta: em imagens muito pequenas, pode não compensar. Se você comprimir um ícone de 16×16 pixels, os 124 bytes de tabela podem ser maiores que a economia.

É por isso que encoders profissionais deixam isso como uma opção (o nosso OPTIMIZE), e não como comportamento obrigatório.

E aqui está o impacto, com as duas configurações na mesma imagem:

Tabelas     │ Tamanho  │  PSNR    │ Economia
────────────┼──────────┼──────────┼──────────
padrão      │ 3048 B   │ 33,79 dB │    —
customizada │ 2290 B   │ 33,79 dB │  -24,9% 🎉

Um quarto do arquivo evaporou, e a qualidade é EXATAMENTE a mesma. 🤯

E isso faz todo sentido, se você pensar: a codificação de entropia é lossless. A gente não jogou nenhum dado fora, só passou a representar os mesmos dados de forma mais eficiente.

É compressão pura, sem custo nenhum de qualidade. 💎

Juntando tudo: o resultado final

Agora vamos rodar com as três melhorias ligadas e ver onde chegamos:

=== N.148i encoder ===
Input:    ../images/example.ppm  (320 x 240)
Quality:  50
Chroma:   4:2:0
Huffman:  optimized for this image

Y plane:      320 x 240
Cb/Cr planes: 160 x 120

Encoded 1800 blocks
Huffman tables: 124 bytes stored in the file
Entropy data:   2145 bytes
Wrote ../output/image.n148i

=== N.148i decoder ===
Header:  v3, 320 x 240, quality 50, chroma 4:2:0, custom tables
Decoded 1800 blocks, consumed 2145 of 2145 bytes
Upsampling: bilinear
Wrote ../output/decoded.ppm

=== Results ===
Original PPM:   230415 bytes
N148i file:       2290 bytes
Compression:  100.6:1
PSNR:         34.70 dB

Comparando com onde a gente estava no fim do artigo 17, nos tínhamos o seguinte:

             │  Artigo 17  │  Artigo 18  │ Diferença
─────────────┼─────────────┼─────────────┼───────────
Tamanho      │   3047 B    │   2290 B    │  -24,8% 📉
Compressão   │   75,6:1    │  100,6:1    │  +33%   📈
PSNR         │  33,79 dB   │  34,70 dB   │  +0,91  📈

Isso representa um arquivo 25% menor E qualidade melhor, ao mesmo tempo.

🎉 Passamos da marca simbólica dos 100:1 de compressão.

E repara: o consumed 2145 of 2145 bytes continua batendo perfeitamente, mesmo com as tabelas customizadas. O ciclo completo segue íntegro. ✅  

Uma espiadinha no que vem por aí 👀

Eu não resisti e fiz um teste rápido comparando com o JPEG na mesma imagem, mesma qualidade e mesmo 4:2:0:

JPEG (tabelas padrão):      3688 bytes   PSNR 34,66 dB
JPEG (tabelas otimizadas):  2584 bytes   PSNR 34,66 dB
N.148i (otimizado):         2290 bytes   PSNR 34,70 dB

Interessante, né? 😏 Mas eu preciso ser honesto e colocar duas ressalvas importantes antes que você saia comemorando:

Ou seja: é um resultado animador, mas não é um benchmark. É justamente por isso que o próximo artigo existe. 😄

Repositório no GitHub

E sim, você pode acompanhar a evolução desse CODEC de imagens em um repositório no GitHub, commit por commit 👋

Segue o link abaixo do commit desse artigo, onde implementamos o upsampling bilinear, os modos 4:4:4 e 4:2:2, e as tabelas de Huffman customizadas:

Resumo

Recapitulando os três refinamentos:

O N.148i está afiado. 🔪

Corrigimos as três fraquezas conhecidas, e o codec ficou menor e melhor ao mesmo tempo, que é a combinação mais difícil de conseguir em compressão.

Agora sim ele está pronto pro ringue. No próximo artigo, chega a hora do julgamento: vamos colocar o N.148i frente a frente com JPEG, PNG e WebP, medindo tamanho e qualidade com PSNR, SSIM e VMAF (lembra do artigo extra sobre eles? Finalmente vamos usar os três!).

Vai ser um artigo de resultados honestos, inclusive sobre onde a gente apanha.

Até a próxima! 👋