Lepton è ora open source, ecco come funziona

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 è già in uso presso Dropbox e ha già ridotto ben 16 miliardi di immagini riuscendo a far risparmiare all’azienda diversi petabyte di spazio.

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.

 

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.

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.

.

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.

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.