web analytics

Lepton è ora open source, ecco come funziona

dropbox logo
In breve: Dropbox sul suo Tech Blog ha annunciato che il tool per l’image compression Lepton è ora open source. Vi spieghiamo passo passo come funziona la codifica dell’immagine.
Dropbox ha da qualche giorno annunciato di aver reso open source (con licenza Apache) Lepton, il suo tool per la compressione delle immagini JPEG senza perdita di qualità.
Lepton consente di raggiungere un riduzione delle dimensioni dei file del 22% per le immagini JPEG esistenti grazie ad un meccanismo molto complesso. Lepton è in grado di conservare il file originale con una precisione bit per bit. E’ possibile comprimere un immagine JPEG ad una velocità pari a 5 Megabytes/s e di decomprimere la medesima immagine a 15 MB/s.
lepton-compression rate
Un grafico del rate di compressione dell’algoritmo Lepton al lavoro su 10k immagini su un Intel Xeon E5 2560 v2 @2.6GHz
Lepton è già in uso presso Dropbox e ha già ridotto ben 16 miliardi di immagini riuscendo a far risparmiare all’azienda diversi petabyte di spazio.

Come funziona JPEG…

Il formato JPEG codifica un’immagine dividendola in una serie di blocchi da 8×8 pixel, ad esempio l’immagine seguente verrebbe codificata come 4 blocchi JPEG.
 jpg imagejpg image blocchi

Gli elementi di ciascun blocco sono shiftati da interi senza segno a interi con segno. Ogni blocco 8×8 può essere visto come un segnale discreto a 64 punti. Tale segnale è dato in input alla trasformata FDCT (discrete cosine transform), della quale ometto la definizione matematica.

L’output della FDCT è un insieme di 64 coefficienti (DCT coefficient) che rappresentano le ampiezze dei segnali base in cui il segnale originale è stato scomposto.
dct image
Uno dei 64 coefficienti del blocco, che assume il nome di DC, rappresenta la luminosità dell’intero blocco 8×8 mentre gli altri 63 coefficienti , detti AC, descrivono tutte le rimanenti caratteristiche dell’immagine.

Sotto potete vedere un’animazione della lettera A che diventa man mano più chiara all’aumentare dei coefficienti AC. L’animazione inizia con il solo DC e aggiunge ogni AC istante per istante.

dct transform.

E come opera Lepton

Lepton per codificare i 63 coefficienti AC inizialmente rappresenta i numeri diversi da zero e successivamente scrive i restanti muovendosi nel blocco sotto rappresentato a zig-zag.

lepton block

I numeri non sono codificati in binario ma viene usata una codifica detta VP8 che è molto più efficiente in questo contesto.

Per codificare un solo coefficiente AC Lepton lo scrive in binario usando la codifica “Unary“, con questo metodo, ad esempio, tre sarebbe 1110 mentre 5 sarebbe 111110, lo zero finale serve per indicare di smettere di contare. Zero è semplicemente 0.

Il coefficiente DC occupa molto spazio (circa l’8%) pertanto va compresso bene. Molti algoritmi lo posizionano prima dei coefficienti AC mentre Lepton lo posiziona come ultimo elemento del blocco. In questo modo, conoscendo molte informazioni dell’immagine grazie ai coefficienti AC già salvati è possibile predire il coefficiente DC, cosi facendo l’algoritmo sottrae dal vero DC il risultato della predizione e va a immagazzinare solo il delta nel blocco:

                                                            DC-DCpredetto = delta.

Chiaramentem grazie al delta, è possibile tornare indietro e riottenere il coefficiente DC originale.

Tutto questo processo permette di salvare un numero significativamente minore di simboli, diminuendo lo spazio occupato dalle immagini.

Trovate maggiori dettagli su Lepton nel post con l’annuncio ufficiale del rilascio mentre il codice sorgente è disponibile su GitHub qui.