Un grafico del rate di compressione dell’algoritmo Lepton al lavoro su 10k immagini su un Intel Xeon E5 2560 v2 @2.6GHzCome funziona 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.
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.
