La tessera esatta

Bentornati in bottega. Nell'episodio scorso abbiamo visto il mosaicista veloce, quello che coglie la forma e rinuncia alla grana. Oggi entriamo nella stanza accanto, dove lavora il suo collega pignolo. Qui ogni tessera va esattamente dove l'originale ha un pixel, con esattamente quel colore. Nessuna approssimazione.

Ma il collega pignolo è anche furbo. Non posa le tessere una per una: si accorge degli schemi che si ripetono, delle zone simili, dei colori che tornano sempre uguali. E li sfrutta.

È la compressione senza perdita di WebP. Il chunk si chiama VP8L, ma quella L non deve ingannare: con VP8 non ha nulla in comune. È un algoritmo progettato da zero in Google da un gruppo guidato da Jyrki Alakuijala, e la sua specifica oggi è parte della RFC 9649.

A differenza della versione con perdita, qui non si cambia spazio colore e non si sottocampiona nulla. Ogni pixel resta un pixel con quattro componenti da otto bit: alfa, rosso, verde e blu. Se l'immagine non ha trasparenza, l'alfa vale semplicemente il massimo ovunque e costa quasi niente.

Il segreto di VP8L è che, prima di comprimere, applica all'immagine fino a quattro trasformazioni. Nessuna perde informazione: tutte sono perfettamente reversibili. Il loro unico scopo è rendere i dati più prevedibili, cioè più comprimibili.

La prima idea la conoscete già dall'episodio scorso: indovinare un pixel dai vicini e trasmettere solo la differenza. Ma qui la si fa pixel per pixel, ed esattamente.

L'immagine viene divisa in riquadri, e per ogni riquadro l'encoder sceglie uno tra quattordici modi di predire: il pixel a sinistra, quello sopra, quello in diagonale, varie medie tra questi, e una modalità che sceglie in modo adattivo il vicino più somigliante. Le scelte di tutti i riquadri vengono salvate in una piccola immagine a parte, una sorta di mappa del disegno preparatorio.

Dopo la predizione, una zona di colore uniforme diventa una distesa di zeri. Un gradiente regolare diventa una distesa di valori piccoli e ripetuti. Ed è esattamente quello che vogliono i compressori.

Nelle immagini naturali i tre canali non sono indipendenti. Se un pixel è più chiaro del vicino, di solito lo è in rosso, in verde e in blu insieme.

La trasformazione del colore sfrutta questo legame: usa il verde per predire una parte del rosso e del blu, e verde e rosso insieme per predire una parte del blu. Anche qui i coefficienti possono cambiare da riquadro a riquadro, e anche qui finiscono in una piccola immagine di servizio.

La terza è la più semplice di tutte: sottrarre il valore del verde dal rosso e dal blu. Sembra banale, ma in moltissime immagini basta questo per ridurre molto la varietà dei valori. È un trucco che costa niente e che l'encoder usa quasi sempre.

E se l'immagine usa pochi colori? Un'icona, un grafico, un'interfaccia, uno screenshot di un terminale. Allora conviene la trasformazione di indicizzazione dei colori: si costruisce una tavolozza fino a duecentocinquantasei colori, e ogni pixel diventa un indice nella tavolozza.

C'è di più. Se i colori sono al massimo sedici, più pixel vengono impacchettati in un solo valore: due, quattro o addirittura otto pixel per volta, a seconda di quanti bit servono per l'indice. Un'immagine in bianco e nero diventa un bit per pixel prima ancora di cominciare a comprimere.

È questo il motivo per cui WebP senza perdita fa così bene con la grafica e con gli screenshot, molto meglio del suo collega con perdita, e spesso meglio di un PNG ben ottimizzato.

Dopo le trasformazioni, i dati vengono compressi con tre strumenti combinati.

Il primo è la copia all'indietro, la stessa famiglia di idee di LZ77 che trovate dentro gzip e zip. Invece di scrivere una sequenza di pixel, si scrive: "ripeti i prossimi trenta pixel copiandoli da quelli che stanno a una certa distanza indietro". In un'immagine le ripetizioni più utili spesso non sono quelle subito a sinistra, ma quelle nella riga sopra. Per questo VP8L ha centoventi codici speciali per le distanze corte in due dimensioni: "il pixel due righe sopra e uno a destra" costa pochissimi bit.

Il secondo strumento è la cache dei colori. Encoder e decoder tengono una piccola tabella con i colori usati di recente, indicizzata da un hash del colore. Se il prossimo pixel ha un colore già nella cache, basta scrivere la sua posizione nella tabella. La dimensione della cache si sceglie per ogni immagine, da due fino a duemila e quarantotto posizioni.

Il terzo strumento sono i codici di Huffman, o codici a prefisso: i simboli frequenti ricevono codici brevi, quelli rari codici lunghi. VP8L ne usa cinque per gruppo: uno per il verde, che condivide l'alfabeto con le lunghezze delle copie e con gli indici della cache, uno per il rosso, uno per il blu, uno per l'alfa e uno per le distanze.

E qui il collega pignolo mostra tutta la sua furbizia. Una zona di cielo e una zona di testo hanno statistiche completamente diverse: usare gli stessi codici per entrambe sarebbe uno spreco.

Così VP8L permette di avere più gruppi di codici, e una ulteriore immagine di servizio, chiamata immagine dell'entropia, dice quale gruppo usare in ogni riquadro. Pensatela così: il mosaicista ha più cassetti di tessere, e una mappa che dice da quale cassetto pescare in ogni zona del pannello.

Ricapitolando: un VP8L contiene le trasformazioni con le loro piccole immagini di servizio, la scelta della cache, i gruppi di codici con la mappa che li assegna, e infine i dati veri e propri. Tutto calcolato dall'encoder, che più lavora più trova combinazioni efficienti.

Questo spiega perché la compressione senza perdita è lenta da produrre e veloce da leggere. Il decoder segue istruzioni: trasformazione per trasformazione, codice per codice. L'encoder invece deve cercare: quale predittore per ogni riquadro, quanta cache, quante tavolozze, quali copie.

Negli strumenti di libwebp questo sforzo si regola con un livello da zero a nove. A zero l'encoder fa il minimo e produce file più grandi in un attimo; a nove prova di tutto e impiega anche dieci o venti volte tanto. Per immagini che vengono compresse una volta e scaricate milioni di volte, come le icone di un sito, conviene il livello alto.

Esiste una via di mezzo, chiamata near-lossless, quasi senza perdita. Prima della compressione, l'encoder modifica leggermente i valori dei pixel nelle zone dove l'occhio non nota la differenza, arrotondandoli in modo da creare più ripetizioni. Poi comprime senza perdita il risultato.

Il risultato non è più identico all'originale, ma resta molto più fedele della compressione con perdita classica, e non ha il sottocampionamento del colore né l'effetto a quadretti. Per screenshot e grafica con qualche sfumatura è spesso il compromesso migliore.

Un'ultima cosa che sorprende molti. Di default, in un'immagine con trasparenza, l'encoder si sente libero di cambiare il colore dei pixel completamente trasparenti, perché tanto non si vedono, e così comprime meglio.

Quasi sempre va benissimo. Ma se usate l'immagine come texture, o se un programma successivo modifica l'alfa, quei colori nascosti riemergono. Per questi casi c'è un'opzione chiamata exact che obbliga l'encoder a conservarli.

Ricapitolando: VP8L lavora su pixel interi, applica fino a quattro trasformazioni reversibili, predizione, colore incrociato, sottrazione del verde e tavolozza, e poi comprime con copie all'indietro, cache dei colori e codici di Huffman che cambiano da zona a zona.

Tenete a mente quei codici di Huffman e quelle tabelle: nell'ultimo episodio della stagione scopriremo che proprio lì, nel 2023, si nascondeva una crepa molto seria.

Intanto, nel prossimo episodio, entriamo nel laboratorio del vetro: la trasparenza, e il modo in cui WebP la abbina perfino alla compressione con perdita. Ci sentiamo lì.