BETA La rivista ipertestuale tecnica
BETA
BETA La rivista ipertestuale tecnicaBarra BETA
Barra Sito Beta.it

BETA 2299.5 - Multimedia: La codifica digitale MPEG - Parte 1 | Parte 2 | Parte 3 | Parte 4 | Parte 5  -  Indici | Guida

Clicca qui!

La codifica digitale MPEG

Andrea Lubrano, Fabrizio Gargano, Luciano Giustini
BETA

Parte 3: Algoritmo di codifica

Ridondanze

All'interno di un segnale visivo statico si assiste spesso ad un insieme di ripetizioni delle informazioni, in quanto vi è una correlazione locale tra pixel, ovvero una vicinanza logica e/o cromatica tra pixel. Analogamente quando l'immagine è in movimento, molte zone vengono continuamente trasmesse anche quando queste rappresentano immagini statiche all'interno della scena, come per esempio oggetti all'interno di una stanza. Si assiste dunque a due tipi di ridondanza :
  • ridondanza spaziale, dovuta alla alta correlazione esistente tra pixel vicini tra loro.
  • ridondanza temporale, dovuta alla trasmissione di immagini contenenti un gran numero di "blocchi" privi di dinamicità.
Si cerca quindi di ridurre le correlazioni sopra esposte, attraverso l'implementazione di tecniche di compressione. In particolare, si definisce tecnica di tipo intra quella che sfrutta la correlazione spaziale all'interno di un'unica immagine, si definisce inter invece la tecnica che sfrutta la ridondanza d'informazione tra due immagini consecutive.

Luminanza e crominanza

Un'immagine grafica viene solitamente interpretata come un insieme di punti (pixel), e ad ognuno di essi viene associato un colore che viene espresso mediante tre componenti fondamentali : Rosso, Verde e Blu, brevemente indicate con la sigla RGB.
È stato tuttavia dimostrato, attraverso considerazioni statistiche, che queste ultime componenti presentano informazioni ridondanti, caratteristica  favorevole per una compressione efficiente; tale fatto induce ad effettuare una trasformazione delle componenti RGB, riportandole as un gruppo di componenti con basso grado di correlazione. Grazie ad un'opportuna matrice di conversione, è possibile disporre delle componenti YUV che presentano le caratteristiche ricercate.

La componente Y rappresenta l'immagine in versione a tonalità di grigi, e prende il nome di luminanza, mentre le altre due componenti vengono indicate con il nome di crominanze, e contengono l'informazione sul colore.
Gli aspetti interessanti di tali componenti sono, come già detto, la bassa correlazione esistente tra le diverse componenti, mentre la luminanza contiene la maggior parte di informazione dell'immagine, a differenza delle altre due componenti. Infatti l'occhio umano e' molto piu' sensibile ai contrasti piuttosto che alle sfumature di colore. Questo significa che la sola componente Y deve essere adeguatamente ed interamente trasmessa, mentre le altre due componenti possono essere maggiormente compresse (accettando anche la perdita d'informazione).

Nel caso di compressione MPEG si utilizza il "formato 4:2:0", che effettua un sottocampionamento di fattore 2 delle componenti di crominanza lungo entrambe le direzioni (verticale e orizzontale). Interessante è il confronto statistico tra la rappresentazione RGB e quella YUV. Nella prima si nota una distribuzione statistica nell'immagine sommariamente uniforme di tutte e tre le componenti. Nella seconda rappresentazione, si nota che il ruolo uniforme lo gioca solo la componente Y, mentre le due crominanze sono concentrate attorno ad un unico valore. Ciò prova ulteriormente che la rappresentazione YUV è molto più conveniente della rappresentazione RGB in prospettiva della ricerca di un efficiente metodo di compressione dell'informazione.

A questo punto l'immagine, per facilitare la trasmissione dei dati e la correzione dell'errore, viene suddivisa per passi in:

  • Slice (Striscia di Macroblocchi)

  • Ogni immagine viene suddivisa in un certo numero di strisce contigue di macroblocchi. La funzione delle slice è quella di fornire una protezione nei confronti degli errori di trasmissione: nel caso in cui parte dei dati all'interno di una immagine risultino errati, il decodificatore è in grado di ripartire correttamente dalla slice successiva, riuscendo a recuperare il resto dell'immagine. Le slice forniscono quindi il supporto per tutte le funzioni di sincronizzazione.
    Ogni slice può contenere un numero variabile di macroblocchi e può partire da un punto qualsiasi dell'immagine.
  • Macroblocco

  • Il macroblocco è l'unità fondamentale sulla quale MPEG basa tutte le scelte sulla compensazione del movimento e sulle tecniche di codifica.
    La dimensione del macroblocco è di 16 x 16 pixel
    Nel formato 4:2:2 un macroblocco è composto da un header e da 8 blocchi di 8 x 8 pixel organizzati nel seguente modo:

    la DCT (Trasformata Discreta del Coseno) viene effettuata sempre su blocchi 8 x 8, e, dato che le crominanze U e V sono sottocampionate di un fattore 2 lungo le righe, 4 blocchi sono associati al segnale di luminanza e 2 blocchi a ciascuna delle componenti U e V.
    La struttura interna dei macroblocchi è differente a seconda che il codificatore ritenga più conveniente eseguire una trasformazione DCT basata sul frame oppure sul field.
    La scelta sul tipo di DCT da effettuare è motivata dalla necessità di sfruttare nel miglior modo possibile la correlazione spaziale presente nel segnale, dando preferenza alla DCT di tipo field, ad esempio, nelle situazioni in cui la presenza di oggetti in movimento veloce rende molto differenti i due semiquadri.
    L'header del macroblocco contiene anche informazioni sui vettori di movimento e sul passo di quantizzazione
     

  • Blocco

  • Il blocco è la più piccola unità considerata da MPEG ed è quella su cui viene applicata direttamente la DCT. Esso consiste semplicemente in una matrice 8 x 8 pixel (valori associati ad ogni pixel). Durante la quantizzazione il blocco viene ordinato secondo la scansione a zig-zag.



 

Stadi di trasformazione: DCT

 Visto che, in genere, l'energia associata ai valori delle componenti Y,U e V di una immagine e' distribuita in una banda di frequenze abbastanza ridotta, ha senso applicare una trasformata ed aspettarsi di trovare informazioni spettrali in solo alcuni coefficienti.
Per ragioni di semplicita' si e' scelto di dividere l'immagine in blocchi di 8x8 punti ed applicare la DCT (Trasformata Discreta Coseno), che è un tipo di trasformata spesso utilizzata per la compressione di immagini. La trasformata DCT bidimensionale puo' essere ottenuta applicando la DCT monodimensionale alle colonne ed alle righe di ogni blocco. La sua espressione formale, in funzione del valore dei pixel del blocco  e dei coefficienti  nel dominio della frequenza, e' la seguente :

dove :

I coefficienti ottenuti, che sono in numero pari a quello dei punti del blocco, vengono organizzati in una matrice in modo che il valor medio, ovvero la componente continua, sia nell'angolo in alto a sinistra. I coefficienti delle componenti alternate (come mostrato nella figura seguente) vengono invece disposti in ordine decrescente, con i valori piu' alti vicino alla componente continua, ed in modo da avere un numero di riga/colonna che cresce in funzione del valore della frequenza verticale/orizzontale.


 
 

Stadi di trasformazione: Quantizzazione

La codifica a trasformate precedentemente analizzata, non comporta una perdita di informazione dell'immagine che si vuole trasmettere, quindi non porta a prima vista a dei benefici dal punto di vista della compressione dell'informazione associata. L'aver a disposizione, però, l'immagine dal punto di visto dello spettro di frequenza è molto significativo, in quanto è molto più facile individuare l'informazione che può essere eliminata. Il numero di coefficienti ottenuti per le varie componenti che hanno un valore nullo e' abbastanza elevato. Per aumentare tale numero, introducendo naturalmente della distorsione e rinunciando a parte della informazione originale, tali coefficienti vengono quantizzati.
Infatti tali quantizzatori sono caratterizzati anche da una soglia minima, al di sotto della quale il segnale viene considerato nullo (questi prendono il nome di quantizzatori uniformi con zona morta); tale fatto porta ad avere nelle sequenze codificate e quantizzate lunghe sequenze nulle, che possono essere codificate con un alto fattore di compressione .

Inoltre, data la caratteristica dell'occhio da un punto di vista sistemistico, è possibile riservare una codifica grossolana per le "alte frequenze", e più fine per frequenze ad alta probabilità di percezione.  Per esempio l'occhio umano e' piu sensibile a sfumature del colore nelle tonalità del verde e del giallo ed e' qundi proprio in quell'intervallo di frequenze che va adottato un passo di quantizzazione (arrotondamento dei valori dei coefficienti della matrice) minore.
Per semplicita' viene usato un metodo di quantizzazione uniforme, usando pero' un passo diverso a seconda della posizione del coefficiente della DCT ed a seconda del tipo di frame.

Nei blocchi dei frame di tipo I vengono quantizzate separatamente le componenti alternate e continua secondo le seguenti espressioni :

dove sono i coefficienti quantizzati,  sono i coefficienti della DCT,  e' il passo del quantizzatore,  e' un parametro di quantizzazione ed il segno + viene preso positivo per  positiva e negativo per  negativa.

La quantizzazione inversa si ottiene ponendo :

Mentre per i blocchi dei frame di tipo P e B il quantizzatore e' lo stesso per entrambi i tipi di componente e dato da :

ed il segno + viene preso positivo per  positiva e negativo per  negativa.

La quantizzazione inversa si ottiene da :

Nella figura possiamo vediamo una delle tre matrici dei coefficienti associate ai quadri Y, U e V

La quantizzazione e' la parte della codifica MPEG in cui si introduce l'errore maggiore dato che il cambiamento di scala di un coefficiente quantizzato comporta errori non recuperabili se il coefficiente in questione non e' multiplo del passo di quantizzazione. Questa condizione non e', ovviamente, in genere rispettata, ovvero è difficile avere un valore multiplo del passo di quantizzazione. Per il modo in cui viene fatta la quantizzazione, l'entita' dell'errore dipende dalla posizione spaziale del campione, l'errore massimo che si puo' commettere e' pari alla meta' del passo di quantizzazione.

Se la quantizzazione viene fatta in modo troppo "grosso'' le immagini ottenute appaiono segmentate e divise in grossi agglomerati, viceversa se viene fatta in maniera troppo "fine'' si utilizzano piu' bit del dovuto per trasmettere informazione sostanzialmente solo legata a rumore.
 

Codifica entropica

La fase di codifica entropica consiste nella compressione della rappresentazione dei coefficienti che sono stati calcolati con il processo di quantizzazione. In particolare nello standard MPEG viene utilizzato il metodo di Huffman per le parole ottenute scandendo a "zig-zag" la matrice dei coefficienti.
In questa maniera risulta molto probabile che la corrispondente parola termini con una lunga sequenza di zeri. Questo permette l'utilizzo del codice RLE (vedi di seguito), per trattare proprio queste sequenze di zeri.


 

Metodo di Huffman

  • In questo metodo si utilizzano delle informazioni di natura statistica (frequenza con cui si presentano determinate sottostringhe)
  • L'idea e' quella di codificare le sottostringhe piu' frequenti con "parole corte" e le sottostringhe meno frequenti con "parole lunghe"
Esempio:

Input: 11100011 01101110 10011000 01101110 01101110 11001011
 
Sottostringa Frequenza Codifica
01101110 35 11
10011000 25 10
01010100 20 01
11100011 12 001
00001000 5 0001
11001011 3 0000

Output compresso: 001 11 10 11 10 0000

RLE (Run Length Encoding)

È una tecnica di compressione molto semplice; l'idea di base consiste nel sostituire occorrenze consecutive di un dato simbolo con solo una copia di tale simbolo, seguito da un contatore che indica quante volte questo si ripete. Prendiamo in considerazione la sequenza BBBBBAAAAACCCCCCCC; l'applicazione bruta di tale algoritmo porterebbe alla seguente codifica: (B,5),(A,5),(C,8).
Si può ben capire come tale algoritmo sia caratterizzato da un alto coefficiente di compressione, in zone di immagini particolarmente omogenee. Questo algoritmo viene utilizzato sia nello standard delle immagini statiche JPEG, che nello standard delle immagine in movimento MPEG.

(segue)

Collegamento d'articolo
Parte 1 | Parte 2 | Parte 3 | Parte 4 | Parte 5

Parte 4 - Flusso Video


Andrea Lubrano, Fabrizio Gargano e Luciano Giustini hanno collaborato insieme per la stesura di una tesina sui codici di compressione MPEG per il corso di laurea in Ingegneria Informatica all'Università di Roma Tre, docente prof.ssa G. Murciano. La tesina è stata progettata in funzione della pubblicazione su Web ed è stata quindi prodotta fin da subito in formato HTML. Coloro i quali fossero interessati ad una versione stampabile e più ''leggera'' della stessa possono richiederla all'indirizzo info@beta.it. Per i lettori abbonati le due versioni sono disponibili all'indirizzo BETA http://subs.betamag.com

Copyright © 1999 Andrea Lubrano, Fabrizio Gargano, Luciano Giustini, tutti i diritti sono riservati. Questo Articolo di BETA, insieme alla Rivista, è distribuito secondo i termini e le condizioni della Licenza Pubblica Beta, come specificato nel file LPB.


BETA 2299.5: Sommario | Indice del Numero | Redazione | Liste/Forum | Informazioni | Licenza Pubbl. Beta | Mirror ufficiali | Abbonati a BETA | Internet ID | Guida | Cerca | Stampa


Beta.it (http://www.beta.it)email info@beta.it
Barra Sito Beta.it

indice sito | mappa | contattaci | newsletter | pubbl./ad info | abbonamento | informazioni | shopping

Copyright © 1994-1999 BETA, tutti i diritti sono riservati - http://www.beta.it

Sommario Abbonamenti a BETA Redazione Liste/Forum Informazioni Indice del Numero Mirror ufficiali Beta Home Page Beta Home Page english Beta News BETA Rivista Articoli BETA Beta Edit, pubblicazioni Beta Logo, premi Beta Lpb, Licenza Pubblica e Articoli Lpb Beta Navigatore Beta Online Beta Library Beta Info Gruppo Beta BETA La rivista ipertestuale tecnica Collegamento al sito Web