4.5.2 Codifica di Huffmann

La proposta del JPEG specifica due metodi di codifica entropica: la codifica di Huffman (approccio Baseline) e la codifica aritmetica (Lempel-Zif-Welsh Algorithm (LZW)).

Sebbene la codifica aritmetica offra spesso migliori risultati, è poco usata poiché coperta da copyright IBM, AT&T e Mitsubishi.

L'algoritmo di Huffman è utilizzato per ottenere una rappresentazione più compatta de dati; esso utilizza frequenze statistiche con cui un simbolo compare in una sequenza.

I simboli che compaiono più frequentemente vengono rappresentati con sequenze di bit corte, quelli meno frequenti con sequenze più lunghe.

Le tabelle di codifica di Huffman, in cui viene associato ad ogni simbolo della sequenza un codice di Huffman, possono essere calcolate prima della fase di compressione, attraverso un'analisi statistica dei dati da rappresentare oppure si possono usare delle tabelle di default già stabilite a priori.

Lo standard JPEG non stabilisce a priori queste tabelle però mette a disposizione delle tabelle definite a priori che sono state stabilite attraverso l'analisi di immagini con caratteristiche frequenti. (tabelle 5 e 6).

La codifica avviene nel seguente modo: bisogna creare una sequenza di bit che deriva dalla codifica dei diversi simboli che ho ottenuto tramite la "Baseline Entropy Encoding" (paragrafo precedente), con la quale ho definito (Runlenght, Size) con Simbolo-1 e (Ampiezza) con Simbolo-2.

A tutte le occorrenze di Simbolo-1 viene associato un codice di Huffman che è distinto a seconda che Simbolo-1 codifichi un elemento AC o uno DC, infatti si usano due tabelle di Huffman separate per le due classi di elementi. Questo codice è formato da una sequenza di bit di lunghezza variabile a seconda della frequenza dell'elemento. A questa sequenza devo aggiungere la codifica del Simbolo-2, che avviene come segue: Simbolo-2 rappresenta un numero che verrà convertito in un numero binario di un numero di cifre pari a simbolo-1 se il coefficiente è di tipo DC, se invece il coefficiente è di tipo AC si usa un numero pari alla seconda componente della coppia di Simbolo-1, cioè Size.

Category

Code lenght

Code word

0

2

00

1

3

010

2

3

011

3

3

100

4

3

101

5

3

110

6

4

1110

7

5

11110

8

6

111110

9

7

1111110

10

8

11111110

11

9

111111110

Tabella 5 - Tabella per i coefficiente di luminanza DC

 

Category

Code lenght

Code word

0

2

00

1

2

01

2

2

10

3

3

110

4

4

1110

5

5

11110

6

6

111110

7

7

1111110

8

8

11111110

9

9

111111110

10

10

1111111110

11

11

11111111110

Tabella 6 - Tabella per i coefficiente di crominanza DC

 

Se Simbolo-2 è un numero positivo uso la rappresentazione binaria così ottenuta e la aggiungo alla sequenza di bit del Simbolo-1, nel caso in cui sia un numero negativo per ottenere la sequenza di bit che lo rappresenta devo procedere nel seguente modo: al numero negativo sottraggo 1; la rappresentazione positiva del numero così ottenuto la trasformo in binario; applico a questo numero binario il complemento a due; di questo numero complementato prendo a partire da destra un numero di cifre pari a Simbolo-1 ottengo in questo modo una rappresentazione in bit del numero negativo Simbolo-2.

Sulla sequenza di bit così ottenuta, che rappresenta la codifica di Huffman dei dati dell'immagine bisogna applicare un'ultima operazione detta "Byte Stuffing": si suddivide la sequenza di bit in byte, scandendo tutta la stringa byte per byte, ogni volta che si trova un byte che rappresenta il numero 0XFF in esadecimale, cioè 11111111 in binario, si inserisce nella sequenza il numero 0X00 cioè 00000000 subito dopo; se la stringa di bit non è divisibile per otto, si avrà un byte incompleto che dovrà essere completato con una sequenza di uno.