Entropy coding

Una sorgente informatica può essere per sua natura di tipo discreto, come ne

caso di un documento scritto, o di tipo continuo, come nel caso di un segnale

analogico. In base a considerazioni di tipo statistico, la sorgente può essere ca-

ratterizzata da una grandezza, l'Entropia, che indica il tasso di indica il tasso

di informazione (in bit/s) intrinseco per i messaggi prodotti della sorgente. Lo

scopo della codica di sorgente è quello di individuare rappresentazioni alterna-

tive per le informazioni prodotte dalla sorgente, in modo da ridurre la quantità

di bit/s necessari alla trasmissione a valori quanto più possibile prossimi a quelli

indicati dall'Entropia, sfruttando le caratteristiche della sorgente e del processo

di codica.

La proposta del JPEG specica due metodi di codica entropica: la codica

di Human (approccio Baseline) e la codica aritmetica (Lempel-zif-Welsh

Algorithm LZW). Sebbene la codica aritmetica ora spesso migliori risultati,

è poco usata poiché coperta da copyright IBM, AT&T e Mitsubishi.

L'algoritmo Human è utilizzato per ottenere una rappresentazione più com-

patta dei dati; esso utilizza frequenze statistiche con cui un simbolo compare

in una sequenza. I simbolo che compaiono più frequentemente vengono rap-

presentati con sequenze di bit corte, quelli meno frequenti con sequenza più

lunghe.

Prima di eettuare la codica Human il vettore di 64 elementi viene sot-

toposto all'algoritmo Run-lenght Encoding, storicamente il primo algoritmo

di compressione inventato per le immagini. Più precisamente solo i 63 elementi

corrispondenti alle componenti AC vengono sottoposte a questo algoritmo.

Il primo elemento (DC) viene codicato con molta più precisione con un l'al-

goritmo DCPM. Questo sistema modica il coeciente DC dal valore assoluto

ad un valore relativo dipendente dal coeciente DC del blocco precedente. Ad

esempio, se i coecienti DC di due blocchi adiacenti sono 227 e 205, il secondo

diventerà -22. I blocchi adiacenti solitamente hanno un elevato grado di corre-

lazione, così la codica del coeciente DC come dierenza del DC precedente

tipicamente produce un piccolissimo numero. Il DPCM riduce così gli artefatti

(blocking artifacts) quando l'immagine viene ricostruita.

L'algoritmo Run-lenght Encoding codica i 63 elementi AC eliminando le

lunghe serie di zeri presenti all'interno del vettore come nell'esempio seguente:

V ettore

=

15

DC

, 0, −2, −1, −1, −1, 0, , 0, −1, 0, 0, 0, ..., 0

RLE

⇓

⇓

⇓

⇓

⇓

(1, −2), (0, −1), (0, −1), (0, −1), (2, −1), EOB

EOB (End of Block) è uno speciale codice che indica una lunga serie di zeri

che completano il vettore no in fondo, questo speciale codice è indicato nella

codica RLE dal simbolo (0, 0). Un altro codice speciale è il (15, 0) il quale

viene utilizzato quanto, tra due elementi diversi da zero presenti nel vettore, è

presente una serie di 16 zeri conseguitivi.

L'ultima codica entropica applicata ai dati è la classica codica a lunghezza

di codice variabile, Human. La codica consente trasformare dei simboli

in sequenza di bit grazie alle tabelle di codica Human. Per eettuare la

conversione, i dati creati dall'algoritmo RLE devono essere ordinati realizzando

2 simboli, Simbolo-1 e Simbolo-2. Questi 2 simboli solo composti come segue:

Coecienti DC:

Simbolo-1=⇒(Size)

Simbolo-2=⇒(Ampiezza)

Coecienti AC:

Simbolo-1=⇒(Runlenght, Size)

Simbolo-2=⇒(Ampiezza)

Con:

Ampiezza = valore del coeciente

Size = numero di bit per visualizzare il valore assoluto dell'Ampiezza

Runlenght = numero di zeri che precedono il coeciente

esempio:

Hp : coef f icente DC del blocco precedente = 12

15, 0, −2, −1, −1, −1, 0, , 0, −1, 0, 0, 0, ..., 0

DC

i

= DC

i

− DC

i−1

= 15 − 12 = 3 =⇒

simbolo−1



2

size



simbolo−2



3

ampiezza



AC

1

=⇒

simbolo−1



1

runlenght

, 2

size



simbolo−2



−2

ampiezza



AC

2

=⇒



0

runlenght

, 1

size

 

−1

ampiezza



AC

3

=⇒



0

runlenght

, 1

size

 

−1

ampiezza



AC

4

=⇒



0

runlenght

, 1

size

 

−1

ampiezza



AC

5

=⇒



2

runlenght

, 1

size

 

−1

ampiezza



EOB =⇒ (0, 0)

A tutte le occorrenza di Simbolo-1 viene associato un codice Human che

è distinto a seconda che Simbolo-1 codichi un elemento AC o DC, infatti si

usano due tabelle di Human separate per le due classi di elementi. Questo

codice è formato da una sequenza di bit di lunghezza variabile a seconda della

Figura 3.8: Tabelle Human per coecienti DC

frequenza dell'elemento. A questa sequenza si aggiunge la codica del Simbolo-2

che verrà convertito in un numero binario con un numero di cifre espresso dal

valore Size nel Simbolo-1. Le tabelle di Figura 3.8 sono utilizzate per codica-

re i coecienti DC di luminanza e di crominanza, più precisamente codicano

il Simbolo-1 dei coecienti DC. Il valore SIZE nel Simbolo-1 corrisponde al-

la colonna CATEGORY delle tabelle in gura, ad ogni SIZE corrisponde una

codica Human diversa (CODEWORD). Le tabelle di codica Human che

riguardano i coecienti AC sono riportati in appendice.

Il Simbolo-2, cioè l'Ampiezza, viene convertito rispettando una tabella pre-

disposta per la conversione Human relativa alle ampiezze. Figura 3.9. An-

che in questa tabella la colonna CATEGORY corrisponde al SIZE espresso nel

Simbolo-1, la colonna VALUES è il valore dell'Ampiezza contenuto in Simbolo-2

e l'ultima colonna indica la stringa di bit in cui Simbolo-2 deve essere convertito.

L'esempio precedente convertito con Human riguarda i valori di luminanza

e diventerà:

Figura 3.9: Tabella per la codica Human per la ampiezze di tutti i coecienti

Coe

simbolo-1 simbolo-2

DC

(2),(3)

011

11

AC

1

(1,2)(-2)

11011

01

AC

2

(0,1),(-1)

00

0

AC

3

(0,1),(-1)

00

0

AC

4

(0,1),(-1)

00

0

AC

5

(2,1),(-1)

11100

0

EOB

(0,0)

1010

In conclusione la matrice 8x8 di pixel sottoposta alla compressione JPEG è

diventata il seguente stream di bit:

011...11...11011...01...00...0...00...0...00...0...11100...0...1010

in cui i puntini verticali sono stati inseriti solamente per rendere più com-

prensibile la serie di bit.

Sulla stringa di bit così ottenuta, che rappresenta la codica di Human dei

dati dell'immagine, bisogna applicare un'ultima operazione detta Byte Stuf-

ng. Si suddivide la sequenza di bit in byte, scandendo tutta la stringa byte

per byte. Se la stringa di bit non è divisibile per otto si avrà un byte incompleto

che dovrà essere completato con una sequenza di uno.

Dal risultato nale di nota che i 512 bit dei 64 pixel della matrice 8x8 (64×8

bit per pixel = 512 bit), compressi sono diventati 31 bit e quindi possiamo

calcolare alcuni parametri:

R

compressione

=

512 bit_{31 bit}

≈ 17

bit pixel

=⇒

31 bit

64 pixel

= 0.48 bit/pixel

Tipicamente, la soglia di R

compressione

oltre la quale si iniziano a notare

visibilmente delle dierenze tra l'immagine originale e quella compressa e poi

decompressa si trova tra 10:1 e 20:1.

ESEMPIO COMPLETO:

Figura 3.10: Esempio completo di compressione JPEG

Nel documento Sviluppo di un sistema di compressione video Motion Jpeg su FPGA (pagine 37-43)