Matematica e Informatica: Alessandro Russo affronta in questo articolo il fascinoso mondo delle JPEG. Scoprirete tutto (o quasi tutto) a proposito della compressione degli oggetti multimediali e, in particolare, delle immagini.

 

JPEG: Matematica in azione

di Alessandro Russo

 

Indice

 

0. Introduzione

Il World Wide Web è ormai un luogo multimediale. Sul web possiamo trovare immagini, musica, filmati eccetera. Uno dei concetti chiave per comprendere come tutto questo sia possibile è quello di compressione. Infatti, gli oggetti multimediali sul web non avrebbero senso se non fossero compressi perché sarebbero di gran lunga troppo grandi per essere scaricati oppure anche inviati per posta elettronica come si fa normalmente.
In questo breve articolo cercherò di spiegare come funziona la compressione degli oggetti multimediali. In particolare mi occuperò della compressione di immagini e dei concetti matematici che ne costituiscono la base.

1. Gli oggetti digitali

Digitalizzare un oggetto significa trasformarlo in una sequenza finita di numeri in modo che sia poi possibile ricostruire l'oggetto originario (o magari una sua approssimazione). Il nome deriva da digit che in inglese significa cifra.

Un testo scritto si può facilmente digitalizzare definendo una tabella che assegna un numero ad ogni lettera dell'alfabeto e ai segni di interpunzione, e poi trasformando il testo in una sequenza di numeri seguendo la tabella. È chiaro che partendo dalla sequenza di numeri e dalla tabella di conversione possiamo ricostruire il testo esattamente uguale all'originale. La "tabella di conversione" più comune è quella dei codici ASCII, introdotta all'inizio degli anni sessanta, che stabilisce una corrispondenza precisa tra i caratteri dell'alfabeto americano (quindi senza lettere accentate) e numeri.

Attualmente ogni segno dell'alfabeto (lettere, numeri, segni di interpunzione) è rappresentato come elemento in una tabella di 256 possibili posizioni. La scelta di 256 è legata al fatto che 256=28, cioé ogni numero da 0 a 255 può essere rappresentato da una sequenza di 8 entità binarie, ovvero a due stati (acceso-spento, 1-0, ecc.) La quantità di informazione necessaria per rappresentare un carattere si chiama byte. byte e carattere sono spesso usati come sinonimi, anche se ciò è leggermente improprio.

La tabella di conversione che si usa per gli alfabeti dell'Europa Occidentale (compreso quello italiano) che prevede le lettere "modificate" con accenti, dieresi, umlaut eccetera si chiama iso-latin-8859-1. Per avere un'idea delle problematiche connesse con la codifica dei segni alfabetici si può leggere l'articolo A Brief History of Character Codes di Steven J. Searle. Su internet si trovano numerosissimi documenti dedicati alla codifica dei caratteri.

Per i nostri scopi, possiamo quindi supporre senza entrare nei dettagli che esista una tabella di corrispondenza che comprende tutti i caratteri di stampa di uso più comune nella lingua italiana.

Per vedere come questo funziona nella pratica, qui trovate una digitalizzazione dell'Orlando Furioso che occupa 1.488.599 byte, che corrispondono ai caratteri tipografici dell'opera. Per trasformare questo file in testo leggibile dagli umani dobbiamo conoscere la tabella in cui è stato codificato; in questo caso, è la iso-latin-8859-1. Se quindi aprite il file per esempio nel vostro browser, bisogna che il browser sia informato della codifica usata; molto spesso in mancanza di informazioni si suppone che la codifica sia proprio questa. C'è quindi una buona possibilità che vi troviate davanti il capolavoro dell'Ariosto con tutti gli accenti al posto giusto, anche se non è detto. Naturalmente, sarebbe possibile inserire nel file stesso l'informazione per il browser o più in generale per l'applicazione che lo deve aprire. Per esempio, questa pagina web che usa i caratteri accentati ha all'inizio la riga

charset=iso-8859-1
che appunto dice al browser che la leggerà la codifica da utilizzare.

È interessante ricordare che la Microsoft, nelle sue mire monopolistiche, ha anche tentato di imporre una sua codifica dei caratteri, ovviamente incompatibile con tutte le codifiche standard: si veda questo articolo per una spiegazione completa.

 

2. La compressione

256 posizioni per identificare i segni dell'alfabeto italiano (e anche di qualunqe alfabeto latino) sono un po' troppe; abbiamo infatti 26 lettere minuscole, 26 maiuscole, 10 segni per i numeri, le lettere modificate (accentate, ecc.) e una decina di segni di interpunzione. Il totale fa circa 100, che noi codifichiamo usando 256 posizioni. Pertanto circa il 60% dello spazio è sprecato. Esistono dei programmi capaci di compattare i files tenendo conto delle spazio sprecato (e anche di eventuali ripetizioni di segni). Vediamo cosa succede usando tre dei compressori di testo più diffusi: zip, gzip e bzip2.

# zip -v orlando-furioso.txt.zip orlando-furioso.txt
total bytes=1488599, compressed=604051 -> 59% savings

# gzip -v orlando-furioso.txt
orlando-furioso.txt:     59.4% -- replaced with orlando-furioso.txt.gz

# bzip2 -v orlando-furioso.txt
orlando-furioso.txt:  69.60% saved, 1488599 in, 452588 out.
I primi due compresori, zip e gzip, hanno sostanzialmente sfruttato la ridondanza della tabella di conversione e hanno risparmiato piu' o meno la percentuale prevista di spazio; bzip2 invece fa un'analisi più fine del testo (infatti impiega circa il doppio del tempo) e riesce a comprimere di più. In generale, c'è un tradeoff tra compressione e tempo impiegato.

La compressione in questo caso si dice lossless, ovvero senza perdita di informazione: infatti posso sempre riscostruire esattamente il file orginario.

 

3. Le immagini

Vediamo invece adesso cosa succede quando viene digitalizzata un'immagine; per fissare le idee, esaminiamo come si arriva ad una foto digitale.

Oggi le macchine fotografiche digitali sono diventate molto popolari. Si scatta una foto, la si trasferisce sul computer e poi la si guarda sullo schermo (o la si stampa). La "pellicola" di una macchina fotografica digitale non è una superficie sensibile che viene impressionata dalla luce ma un rettangolo diviso in tanti piccolissimi quadratini (pixel) il cui numero (i cosiddetti "megapixel") è diventato uno dei parametri commerciali più importanti per le macchine fotografiche digitali.

Al momento dello scatto della foto, la macchina digitale "colora" ciascuno di questi pixel assegnandogli un numero tra 0 e 16.777.215. Da dove sbuca fuori questo numero? La spiegazione completa sarebbe un pó complicata. Per i nostri scopi, possiamo pensare che ogni colore viene rappresentato mescolando una certa intensità di rosso (R=red), verde (G=green) e blu (B=blue) e ciascuna di queste intensità viene graduata da 0 a 255.

Quindi scrivendo in fila tre numeri ciascuno dei quali può andare da 0 a 255 abbiamo la rappresentazione di qualunque colore. È facile vedere che le combinazioni possibili sono 2563 = 16.777.216, ovvero 3 byte per pixel.

Vediamo quanto spazio occupa l'oggetto che abbiamo descritto. Supponiamo che il numero di pixel sia 600×600 = 360.000, un numero molto basso per gli standard attuali. Allora l'immagine occupa 360.000×3 = 1.080.000 byte, cioé circa un megabyte.

C'è sicuramente qualcosa che non va: infatti le fotografie che si trovano comunemente su internet sono molto molto più piccole come grandezza anche se hanno una risoluzione molto maggiore. Si potrebbe pensare di ricorrere ai programmi per la compressione dei dati descritti predentemente, ma qui non c'è spreco di spazio e non ci possiamo aspettare che tra i byte ci siano delle sequenze ripetute da cui trarre vantaggio.

Verifichiamolo.

Il formato che abbiamo descritto prima si chiama bmp (Windows Bitmap Format) e semplicemente elenca pixel per pixel le tre componenti RGB del colore. Il file bacche.bmp misura 600×600 pixel e raffigura l'immagine seguente:

La sua dimensione è di 1.080.054 byte (1.080.000 byte che avevamo previsto più qualche byte per annotare larghezza, altezza e formato del colore).

Attenzione: molto probabilmente il vostro browser non riuscirà a visualizzare direttamente bacche.bmp. La ragione è che questo formato è talmente inefficiente e poco utilizzato che non vale la pena di supportarlo da parte di un browser.

Proviamo a comprimere il file:


# zip -v bacche.bmp.zip bacche.bmp
total bytes=1080054, compressed=1012106 -> 6% savings

# gzip -v bacche.bmp
bacche.bmp:       6.3% -- replaced with bacche.bmp.gz

# bzip2 -v bacche.bmp
bacche.bmp:  1.264:1,  6.331 bits/byte, 20.86% saved, 1080054 in, 854744 out.
Questa volta il guadagno è molto inferiore a prima, e le dimensioni ottenute sono di gran lunga molto più grandi di quelle che si incontrano normalmente su internet. Più di 800.000 byte per un'immagine 600×600 è veramente troppo.

Per ridurre le dimensioni del file dell'immagine bisogna usare una tecnica di compressione completamente diversa, per così dire fatta su misura per le immagini di tipo fotografico. Cominciamo subito col dire che, a differenza del caso precedente, qui la compressione è lossy, cioé non potremo ricostruire il file iniziale. Però quello che perderemo sono i dettagli pressoché invisibili all'occhio umano.

 

 

4. La DCT (Discrete Cosine Transform)

Lo strumento fondamentale che viene utilizzato per la compressione di immagini e di oggetti multimediali in genere (musica, film) è la Trasformata di Fourier Discreta. I dati (nel nostro caso le intensità RGB di colore) vengono trasformati in altri dati che rappresentano lo stesso oggetto ma visto in un altro modo, cioé come somma di dettagli via via sempre più fini; i dettagli cosí fini da risultare invisibili all'occhio umano vengolo eliminati, e poi si applica la trasformazione inversa che ci riporta alle intensità di colore. I dati che vengono effettivamente memorizzati sono solo i dettagli conservati.

Prima di vedere come si applica questo procedimento alle immagini, vediamolo su un caso più semplice. Prendiamo 16 valori e rappresentiamoli nel formato originale (in blu) e nel formato trasformato (in rosso). Le proprietà fondamentali della DCT sono tre:

  • la DCT trasforma lo spazio fisico (cioé i dati che abbiamo) nello spazio delle frequenze (cioé i dettagli)
  • la DCT è invertibile, cioé possiamo passare dalla descrizione nello spazio fisico alla descrizione nello spazio delle frequenze in modo intercambiabile;
  • la DCT è lineare, cioé se spezziamo i dati nello spazio fisico, calcoliamo la DCT delle singole componenti e poi rimettiamo insieme i pezzi abbiamo lo stesso risultato che avremmo ottenuto calcolando la DCT sui dati non spezzati.
I curiosi possono trovare qui la formula matematica della DCT. Come vedete, usa solo le 4 operazioni e la funzione coseno che tutti conoscete.

Nelle figure che seguono, ho sempre rappresentato a sinistra in blu i dati nello spazio fisico e a destra in rosso i corrispondenti valori nello spazio delle frequenze.

Il modo migliore per comprendere come funziona la DCT è in un certo senso guardarla alla rovescia, cioé prendere dei dati semplici nello spazio delle frequenze e vedere a che cosa corrispondono nello spazio fisico. Vediamo cosa succede se "eccitiamo" solo la frequenza 1:

Si vede che se "eccitiamo" solo la frequenza 1 allora nello spazio fisico tutti i valori sono uguali: è è il dettaglio piú grosso di tutti, quello che coinvolge i valori in tutti i punti nello spazio fisico allo stesso modo. La frequenza 1 è stata eccitata al valore 1; se la raddoppiamo, raddoppiano anche i valori corrispondenti nello spazio fisico (linearità della DCT):

ma la struttura non cambia: la frequenza 1 corrisponde a un valore costante nel dominio fisico. Eccitiamo adesso solo la frequenza 2 mettendola al valore 1. Ecco il risultato:

Nello spazio fisico c'è un "dettaglio" più fine del precedente; infatti c'è una oscillazione intera. Eccitiamo adesso la frequenza 5.

Come si vede, abbiamo delle oscillazioni più strette che corrispondono a maggiori dettagli nello spazio fisico. Per verificare la linearità, eccitiamo contemporaneamente la frequenza 1 al valore 2 e la frequenza 5 al valore 1. La figura che otteniamo è proprio la somma delle due figure precedenti (attenti ai valori della scala!).

Facciamo qualche altro esempio:

L'ultimo esempio ha una distribuzione di valori a caso nello spazio fisico a cui corrispondono un po' tutte le frequenze nello spazio trasformato.

Torniamo adesso alle immagini. La compressione dello standard JPEG è adatta a immagini della vita reale di tipo fotografico, che sono caratterizzate da alte frequenze piccole. In altre parole, se trasformiamo una immagine fotografica con la DCT, nella maggior parte dei casi le frequenze più alte saranno trascurabili. Se le eliminiamo completamente, l'immagine (all'occhio umano) sembrerà immutata. La prossimo figura illustra un "tipica" situazione di questo genere.

La distribuzione nello spazio fisico è tipica di una fotografia di un oggetto reale. Vediamo che nello spazio delle frequenze il valore delle frequenze più alte è quasi zero:


(...)
12.   -0.1579
13.   -0.0525
14.   -0.0771
15.   -0.0234
16.   -0.0234
Se noi mettiamo a zero il valore delle ultime 4 frequenze e trasformiamo all'indietro i dati così ottenuti nello spazio fisico otteniamo una figura molto simile alla precedente:

Viceversa, se abbiamo un'immagine con un dei bordi molto netti (tipo i cartoni animati), tutte le freqenze verranno eccitate e quindi non possiamo tagliare quelle alte senza modificare radicalmente l'immagine.

Ecco cosa succede se mettiamo a zero la frequenza più alta:

5. La compressione JPEG

Vediamo adesso cosa succede a una vera immagine. La differenza maggiore con il nostro modellino è che un'immagine è bidimensionale; pertanto bisogna usare una DCT bidimensionale, ma questo non è un grosso problema: è semplicemente il prodotto di tante DCT monodimensionali.
  1. Vengono separate le componenti RGB dell'immagine. La procedura descritta qui sotto viene ripetuta 3 volte, una per ogni componente del colore;
  2. l'immagine viene suudivisa in quadratini 8×8;
  3. a ciascuno dei quadratini viene applicata la DCT bidimensionale, ottenendo così 8×8=64 valori di frequenza nello spazio trasformato;
  4. le frequenze più alte vengono troncate;
  5. si memorizzano solo le frequenze rimaste.
Questo è il principio di funzionamento della compressione delle immagini. In realtà la situazione reale è un po' più complessa, nel senso che:
  • non solo le frequenze più alte vengono eliminate, ma quelle intermedie vengono quantizzate, ovvero arrotondate a dei valori prefissati. Questo aumenta ulteriormente la compressione;
  • i dati nello spazio delle frequenze prima di essere memorizzati subiscono una ulteriore compressione lossless (cioé con un compressore tipo quelli che funzionano bene per i files di testo).
JPEG significa "Joint Photographic Experts Group"; infatti questa procedura è fatta apposta per le immagini di tipo fotografico.

I parametri di compressione JPEG non sono fissati nello standard, nel senso che le soglie a cui quantizzare e tagliare sono di responsabilità dell'applicazione; viceversa, in ogni file JPEG è contenuta la tabella che permette di risalire ai dati nello spazio fisico, quindi possiamo essere certi che lo stesso file verrà visualizzato sempre nello stesso modo da qualunque applicazione.

I programmi che permettono la compressione JPEG hanno di solito un parametro, che può essere scelto dall'utente, che determina la qualità della compressione. Più il file finale è piccolo, e peggiore è la qualità dell'immagine risultante.

Per comprendere meglio il meccanismo della compressione JPEG, osserviamolo in azione. Cominciamo col comprimere sempre di più la figura bacche.bmp. Dato che la compressione viene fatta separatamente sui quadratini 8×8, dopo un po' questi struttura soggiacente dovrebbe venire fuori, perché nulla garantisce che ci sia corrispondenza tra un quadratino e l'altro.

Vediamo.

La prima figura rappresenta l'imamgine ottenuta utilizzando la compressione "di default" di un popolare programma grafico di Unix (xv).

Come si vede, l'immagine è sostanzialmente indistinguibile dall'originale, ma la sua dimensione è ora 69.454 byte: un guadagno del 93%!!!!! La prossima immagine è stata compressa ulteriormente ("qualità 10% secondo xv"); adesso si nota chiaramente la struttura 8×8. In compenso, la dimensione è precipitata a 17.311 byte.

Nella prossima immagine è riportato un particolare ingrandito dove si vede chiaramente la struttura soggiacente 8×8:

Per quanto detto prima, il formato JPEG dovrebbe essere particolarmente inefficiente quando ha a che fare con immagini dai bordi netti come i fumetti o i cartoni animati. Verifichiamolo. L'immagine seguente è un pezzettino ingrandito del mio terminale:

Proviamo a salvarlo in JPEG, usando la qualità di default di xv. Ecco il risultato:

Come si vede, i colori si sono offuscati e sono stati generati dei pixel spuri che prima non c'erano. Questo succede perché le alte frequenze che sono state tagliate nella compressione JPEG non erano piccole!

Per questo tipo di immagini si usa il formato GIF, che è l'equivalente dei programmi di tipo zip di prima. Non c'è perdita nella compressione e ovviamente è piuttosto inefficiente per le immagini di tipo fotografico; infatti il file bacche.gif occupa 248.921 byte. Sempre meglio comunque dei compressori "general puprpose" zip, gzip o bzip2.

Per un approfondimento, raccomando la lettura delle FAQ (Frequently Asked Questions) su questi argomenti, reperibili qui. Raccomando in particolare la lettura delle jpeg-faq e delle compression-faq.

 

6. Musica e film

Per la musica e i video, lo strumento di base è sempre la DCT. Naturalmente, i dettagli dell'implementazione, che già sono abbastanza complicati per le immagini, diventano estremamente intricati per un oggetto complesso come un video, dove bisogna comprimere contemporaneamente immagini in movimento e musica. Lo standard DVD è forse la maggiore conquista tecnologica degli ultimi anni in questa direzione.

 

7. Il futuro

La tecnologia alla base della multimedialità è piuttosto vecchia; lo standard JPEG è della fine degli anni 80, preistoria per la computer science. C'è un nuovo formato, JPEG2000, che usa strumenti più sofisticati (wavelet) per operare la compressione, ma le specifiche non sono state ancora completate. Inoltre, la compressione video ha ancora spazi notevoli di miglioramento all'interno dello standard attuale, e i DVD hanno appena cominciato a diffondersi. Io credo che non vedremo niente di radicalmente nuovo sul Web in questa direzione per un po' di anni, ma naturalmente posso sbagliarmi.


Copyright (C) 2002 Alessandro Russo
Updated: $Date: 2002/07/12 18:20:00 $ $Author: russo $