Capitolo 1

Capitolo 1

1.1

Introduzione

La comunicazione multimediale è un campo in continua evoluzione, le cui applicazioni includono tra le altre video conferenze, video telefonate, broadcasting digitale, web browsing e sistemi di controllo ed assistenza remoti. I personal computer e le workstation sono diventati un’importante piattaforma per l’intrattenimento, la pubblicità, l’educazione e la ricerca. Queste applicazioni multimediali interattive rappresentano l’obiettivo di nuovi terminali wireless e wired.

Il progresso in questo campo è supportato dalla disponibilità di canali di trasmissione digitali e dalla possibilità di immagazzinare dati in modo efficiente. Con le nuove tecnologie di comunicazione è oggi possibile superare i limiti di banda di decine di Kbits/s sia per comunicazioni wired che wireless. Per esempio la tecnologia xDSL (Digital Subscriber Line) permette all’utente residenziale un flusso di dati dalle centinaia di Kbps fino a qualche Mbps servendosi della comune linea telefonica. Per le comunicazioni wireless i cellulari di 3rd generazione permettono un flusso di dati di centinaia di Kbps che diventa di parecchi Mbps per le WLAN (Wireless Local Area Network) o i sistemi bluetooth. Comunque la crescita repentina di varietà e quantità di dati multimediali porta alla necessità di un’efficiente compressione degli stessi. La tabella 1.1 mostra la quantità di dati necessari per differenti segnali per applicazioni multimediali non compresse. La trasmissione e la memorizzazione di due ore di un filmato audiovisivo di buona qualità richiedono più di 300 Mbps di banda e all’incirca 290 Gbytes di memoria. Diventa quindi necessario codificare il segnale per poter soddisfare la richiesta da parte degli utenti (contenuti multimediali di alta qualità, che però siano accessibili in tempi brevi e a un costo ragionevole) colmando il divario che si viene a creare tra tale domanda e la limitata capacità di trasmettere informazioni e di memorizzare dati.

Tabella 1.1Bit-rate richiesto per segnali non compressi

Text Speech [1] Music Photo Video

1 page ASCII 16 Kbits 8 KHz, 8 bits 64 Kbits/s 44.1 KHz 16 bits 2 channels 1.4 Mbits/s 1024x768 pixels 24 bits/pixel 18 Mbits/photo 800x600 pixels 30 Hz 24 bits/pixel 330 Mbits/s

Un sistema di comunicazione multimediale conta tipicamente quattro fasi. Inizialmente un codificatore elimina la ridondanza nel segnale in ingresso e le informazioni compresse vengono segmentate in pacchetti di lunghezza fissa o variabile (source coding). Il segnale di uscita di uno o più codificatori (ad esempio quelli che trattano l’audio e il video) vengono combinati nel canale di codifica dove si aggiungono informazioni inerenti alla segmentazione ed atti a migliorare la robustezza dei dati agli errori introdotti nel canale (channel coding). Dopo un’appropriata modulazione, l’informazione viene inviata sul canale di trasmissione. Il decoder demodula il segnale così ricevuto identifica e corregge eventuali errori di trasmissione e separa il segnale sorgente. A questo punto il decoder riproduce il segnale nel modo più fedele possibile. Mentre tecnologie efficienti per la trattazione di dati, voce, file audio o di testo sono pienamente disponibili oggigiorno (permettendo la larga diffusione di cellulari, lettori di musica MP3, GPS per nominarne alcuni) la trattazione di informazioni video rappresenta una sfida ancora aperta a causa degli alti bit-rate e dell’elevata quantità di dati da mantenere. Lo standard H.264/MPEG-4 Advanced Video Codec (H.264/AVC), recentemente definito da un team congiunto dell’ITU-T e ISO/IEC è stato pensato per raggiungere un’elevata efficienza di compressione sui precedenti standard di compressione video (H.263, MPEG-4) e network friendly video streaming.

Il codec soddisfa applicazioni di conversazione (videotelefonia bi-direzionale e in tempo reale,videoconferenze) e non (memorizzazione, broadcasting, streaming) per un largo range di bit-rates sia per trasmissioni wireless che via cavo.

1.2

la codifica video e il suo ruolo nelle applicazioni

multimediali

1.2.1

Standard internazionali

Per permettere un efficace scambio di informazioni sia con dei dispositivi sui quali sono memorizzati dati (e.g. Compact Disk, Digital Video Disk) che attraverso sistemi di comunicazione, e per permettere una produzione su larga scala di sistemi e dispositivi VLSI si è assistito in questi anni ad un’elevata attività di standardizzazione (vedi [6]). Fin dai primi anni del 1980 l’ISO/IEC e l’ITU-T hanno proposto molti standard di codifica a seconda dei campi di applicazioni su cui si andava ad operare. ITU-T (precedentemente CCITT) ha proposto H.120, H.261 e poi H.263, H.263+ e H.263++ che hanno come obiettivo soprattutto applicazioni a medio-basso bit-rate nell’ordine di decine o poche centinaia di Kbps. ISO/IEC ha proposto JPEG (Joint Photographic Experts Group) per immagini statiche e MPEG (Moving Pictures Experts Group versioni 1, 2 e 4) per applicazioni audiovideo come televisione ad alta definizione e broadcasting. Lo schema di base dei codificatori ISO/IEC e ITU-T viene descritto nel paragrafo 1.2.2. In questo capitolo viene poi introdotto lo standard H264 advanced video codec (AVC), recentemente definito da un Joint Video Team (JVT) dell’ITU-T e ISO/IEC,studiando le sue prestazioni e facendo una stima della complessità.

1.2.2

Principi di compressione di immagini

La rappresentazione di immagini, in accordo al contenuto informativo, è realizzata attraverso degli schemi di codifica. Grazie alle informazioni ridondanti e irrilevanti presenti nel segnale video è possibile ottenere una riduzione del bit-rate. Qualunque informazione che può essere estratta usando le dipendenze statistiche tra gli elementi nelle immagini è ridondante e può essere rimossa. Ogni informazione che si trova sotto una certa soglia non è rilevante per chi riceve e può non essere trasmessa. Sono le

proprietà visive. Il primo passo per operare una compressione sia essa di un immagine statica o in movimento è sfruttare il fatto che la percezione umana sia maggiormente influenzata dalle caratteristiche di luminanza della scena piuttosto che dalle caratteristiche di crominanza. Come conseguenza la tipica rappresentazione RGB (Red Green Blue) di un immagine è convertita in una rappresentazione di tipo Y (luminanza) U V (due componenti di crominanza) e si opera anche un sottocampionamento sui pixel: cioè per 4 campioni di luminanza si prendono solo 2 campioni di crominanza (4:2:0 o 4:1:1). L’ intensità della luminanza e della crominanza sono entrambe codificate tipicamente su 8 bit.

1.2.2.1 codifica di immagini statiche

Lo schema di base per un codificatore di immagini statiche consiste nel suddividere l’immagine in blocchi di dimensione fissata, fino all’H.263 e all’MPEG-4 tipicamente 8x8 o 16x16. Come viene mostrato in figura 1.1, ogni blocco viene trasformato in uno spazio frequenziale, quantizzato e infine trasmesso dopo essere stato codificato con stringhe di bit di lunghezza variabile. Questo schema di compressione viene chiamato “intra-frame” dato che la codifica viene ottenuta senza alcun riferimento ad altri frame ma sfruttando solo le dipendenze spaziali all’interno del freme in esame. Tale frame viene indicato come “I-frame”.

DCT

Quantization

Entropy

Coder

Video

In

Figura 1.1: schema di base di un encoder per immagini statiche

La trasformata che viene comunemente usata è la DCT (discrete cosine trasform), essa offre infatti un buon compromesso tra l’efficienza di codifica e il costo di implementazione. La DCT trasforma i dati di un blocco dell’immagine nello stesso numero di coefficienti dove ogni coefficiente è assegnato a un’immagine di base con un certo contenuto frequenziale. I coefficienti con indice alto sono assegnati a frequenze alte. La DCT ha le seguenti proprietà: (i) i coefficienti sono strettamente correlati, (ii) la

maggior parte dell’informazione risiede nelle componenti a bassa frequenza. La sensibilità dell’ occhio umano è più bassa per le alte frequenze spaziali e quindi possiamo quantizzare i coefficienti con indice alto in modo meno fine. Inoltre se l’ampiezza è inferiore alla soglia più bassa del quantizzatore i coefficienti possono essere messi a 0. Vale la pena di osservare che per tipiche sequenze video più del 90% dei coefficienti sono 0 (vedi [6]) e i pochi coefficienti con valore non nullo sono posizionati a basse frequenze, in questo modo per ogni blocco 8x8 di 8 righe con 8 elementi ciascuna ci sono dalle 5 alle 6 righe piene di zeri. Per la trasmissione la matrice bidimensionale dei coefficienti viene riordinata in un flusso monodimensionale seguendo un percorso a zig-zag partendo dalle frequenze più basse vedi figura 1.2. Un codificatore RLC (run length coder) permette un’efficace rappresentazione della lunga catena di 0 che si hanno nello stream. L’RLC rappresenta infatti i coefficienti attraverso una coppia di simboli (valore e salto) dove salto indica il numero di zeri consecutivi e valore indica quanto vale il coefficiente non nullo. Infine si usa un VLC (variable length coder). Questo metodo viene anche chiamato codifica entropica ed è basato sulla diversa probabilità dei dati nel flusso e riduce ulteriormente il bit-rate.

Figura 1.2: scansione a zig-zag della matrice dei coefficienti

I dati codificati sono poi multiplexati con informazioni di servizio e poi trasmessi. Come mostrato in figura 1.3 il ricevitore compie con ordine inverso le azioni descritte in precedenza.

IDCT

Inverse

Quantization

Video

Entropy

Decoder

Figura 1.3: schema di base di un decodificatore per immagini statiche

1.2.2.2 codifica di immagini in movimento

Lo schema della codifica di tipo intra proposto in 1.2.2.1 (e.g può essere utilizzato anche per codificare sequenze video. La codifica intra è infatti utilizzata per tutte le applicazioni che richiedono un accesso rapido a ogni singolo frame. Operando però in questo modo non si riesce a sfruttare la correlazione temporale che è presente tra i vari frame. La ridondanza temporale può essere eliminata da una codifica che adotta un approccio di tipo predittivo che prende il nome di codifica “inter”. L’immagine così codificata viene denominata P (Predetta). L’approccio più semplice è quello che si basa sulla cosiddetta codifica differenziale, cioè codifico e trasmetto la differenza pixel-pixel tra il frame corrente e quello immediatamente precedente. La predizione può esser migliorata se si tiene di conto il moto degli oggetti. La stima del moto viene implementata in modo tale che, considerando il moto degli oggetti nell’immagine, ad ogni blocco sia associato quello che meglio gli è correlato nei frames precedenti. L’ offset tra i blocchi determina dei vettori di moto ,”motion vectors” (MV) che sono usati per predire il frame corrente dalla compensazione del moto del precedente frame codificato e trasmesso. Per un approccio predittivo abbiamo bisogno di una memoria dove mantenere i frame. Si può raggiungere un’elevata efficienza combinando i due schemi,l’intra e l’inter. Lo schema di base è mostrato in figura 1.4 e prende il nome di coder ibrido, su di esso si basano gli standard principali dell’ ITU-T e dell’ ISO/IEC: in questo caso la differenza pixel-pixel viene portata nel dominio trasformato e poi trasmessa. Per fare in modo di avere la stessa predizione sia in trasmissione che in ricezione il decoder deve essere compreso nell’ encoder. Si nota infatti che nella struttura in trasmissione è presente un anello di feedback, esso permette di eliminare le divergenze tra decoder e encoder.

DCT

_Quantization

Entropy

Coder

Inverse

Quantization

IDCT

Motion estimation

& compensation

Video

In

In uscita dall’encoder, il cui schema è mostrato in Figura 1.4, si ottengono stringhe di bits di lunghezza variabile si ha anche un bit-rate variabile che dipende dalle caratteristiche del segnale in ingresso. Per trasmettere con un bit-rate costante si ha quindi bisogno di un buffer FIFO (first-in first-out) in uscita. Il rate del segnale video deve essere aggiustato al rate costante del canale e questo si ottiene con un controllo della quantizzazione da parte del buffer in uscita: se esso è quasi pieno la quantizzazione diviene più severa altrimenti, se quasi vuoto ho una quantizzazione più blanda. In figura 1.5 viene rappresentata una tipica sequenza video codificata secondo gli schemi H.26x e MPEG. Il primo frame viene codificato in modo non differenziale, e gli viene dato il nome di intra-frame (I). Poi viene applicato un algoritmo predittivo sia prendendo come riferimento i soli frame precedenti , ottengo i cosiddetti P-frame, sia prendendo a riferimento anche i frame successivi effettuando una predizione bi-direzionale, i cosiddetti B-frame. Vale la pena notare che un elevato numero di B-frame comporta un aumento della latenza del sistema.

Figura 1.5: esempio di predizioni I, P e B di una sequenza video

Per concludere è importante indicare che gli standard ISO/IEC e ITU-T non definiscono esplicitamente l’architettura dell’ encoder ma piuttosto la sintassi che deve avere un bit-stream codificato e il metodo di codifica.

In pratica è auspicabile che il decoder e l’encoder includano i task funzionali descritti in questo capitolo, comunque, soprattutto per quanto riguarda l’encoder, si possono apportare delle modifiche nell’ architettura per raggiungere un accettabile compromesso tra prestazioni algoritmiche e costo di implementazione. Per quanto riguarda l’architettura del decoder essa dipende da quella dai profili dell’ encoder supportati per la decodifica .

1.2.3

Misure di distorsione

Le prestazioni di un algoritmo di compressione sono di solito espresse in termini di qualità visiva raggiunta con un fissato bit-rate. L’ispezione visiva è il modo naturale per giudicare la qualità di un immagine. Quindi per comparare diverse implementazioni algoritmiche è richiesto l’analisi di un numero di persone statisticamente rappresentativo dell’intera popolazione, ed è per questo che necessitiamo di un criterio di valutazione oggettivo per poter compiere veloci misure di distorsione. La percezione della distorsione di un’ immagine è una quantità non facile da misurare dato che il sistema di percezione visivo umano è complesso e non ancora completamente studiato. I modelli usati per la valutazione della distorsione sono: Mean Squared Error (MSE),

Sum of Absolute Differences (SAD) oppure Peak Signal to Noise Ratio (PSNR). Essi sono definiti come:

¦ ¦

¦ ¦

Dove A e B sono due vettori (un’immagine o parte di essa ) di dimensione MxN. MSE e PSNR sono più accurati della SAD e quindi sono utilizzati per determinare le prestazioni di qualità di un algoritmo di compressione. La SAD viene utilizzata come funzione di costo per stabilire l’errore che si commette nella codifica di un’ immagine essendo più facile calcolarla.

1.3

Storia degli standard precedenti

H.120: Sviluppato dall’ITU-T e approvato nel 1984 rappresenta il primo vero

esempio di standard, ormai quasi del tutto non più in uso oggigiorno. Lo schema di base è quello di un encoder ibrido con il quale si implementa una codifica differenziale, quantizzazione e di lunghezza variabile. L’uso della codifica differenziale migliora l’efficienza di conversione rispetto alla codifica di tipo intra per le immagini in movimento codificando solo la differenza col frame precedente. L’idea di base consiste nell’indicare quale parti dell’immagine posso ripetere e inviare nuovi dati per le parti che sono cambiate. Nel 1988 una seconda versione dell’H.120 aggiunse una compensazione del moto. I bit-rate con cui si operava erano fino a 2048 Kbps.

compensazione di moto ibrida e un modello di codifica in dominio trasformato utilizzato ancora oggi.

JPEG: Sviluppato congiuntamente dall’ISO/IEC e dall’ITU-T e approvato nel 1992

è uno standard di successo per quanto riguarda la trattazione di immagini statiche. Viene anche usato all’interno dell’H.261 per effettuare la codifica intra e quindi segue lo schema di Figura 1.1.

MPEG-1: Approvato nel 1993 è un codec che offre una qualità di una videocassetta

VHS o al massimo di 1.5 Mbits/s. Utilizza la struttura di base dell’ H.261 e aggiunge una predizione bi-direzionale (i cosiddetti B-frame) e un’accuratezza di metà pixel nella compensazione del moto. Grazie a queste innovazioni MPEG-1 fornisce una qualità visiva superiore dell’H.261 per bit-rate maggiori di 1 Mbits/s.

MPEG-2: Completato nel 1994 da uno sforzo congiunto dell’ITU-T e ISO/IEC è

stato pensato per applicazioni con bit-rate da 4 a 30 Mbits/s e offre una qualità visiva superiore rispetto agli standard precedenti. Le principali innovazioni introdotte sono rappresentate da un’efficiente gestione di immagini analizzate in modo interallacciato.

H.263: Approvato dall’ITU.T nel 1996 è un codec progettato per gestire

applicazioni a bassi e bassissimi bit-rate. E’ ancora oggi usato per videoconferenze e video telefonate. Pensato originariamente per applicazioni da 10 a 30 Kbps il range di applicazione è stato allargato da 10 a 2048 Kbps. Le innovazioni rispetto ai codici precedenti risiedono nella possibilità di utilizzare nella compensazione di moto blocchi a dimensione variabile (16x16 e 8x8) e sovrapporli, una codifica entropica di lunghezza variabile su tre livelli, un predittore mediano per i vettori di moto e un’intestazione del segnale di informazione più efficiente. E’ stato poi rimpiazzato nel 1998 dall’H.263+ e nel 2000 dall’ H.263++ . Lo schema di codifica è lo stesso dell’ H.263 in più ho dei tools opzionali che migliorano l’efficienza di codifica, la robustezza all’ errore e la scalabilità anche se comportano un aumento della complessità. Le nuove versioni estendono i bit-rate di applicazione e la possibilità di supportare ogni formato progressivo (non interallacciato) e frame-rate. In particolare H.263+ è stato il primo

standard che offriva dei tools per il recupero di errori nelle trasmissioni wireless e a pacchetto.

MPEG-4: Approvato nel 1999 può essere considerato il primo standard che unisce

dei tools per la codifica di dati ,audio e video. L’MPEG-4 introduce il concetto di “oggetti” per descrivere e campionare una scena audiovisiva permettendo di combinare vari algoritmi per elaborare dati audio, video grafica 3D, immagini.

Praticamente, MPEG-4 copre tutti i bit-rate (da poche centinaia di bit per audio sintetizzato fino a centinaia di Mbits/s per scene multimediali complesse), i formati delle immagini i frame-rate comprendendo sia sequenze video che cono realizzate in modo interallacciato o progressivo.

1.4

Descrizione dello standard H.264/AVC

L’H.264/AVC rappresenta il più recente progetto di standardizzazione video sviluppato congiuntamente dall’ITU-T Video Codec Export Group (VCEG) e dall’ISO/IEC Moving Picture Export Group (MPEG), che nel dicembre 2001 hanno formato il Joint Video Team (JVT).Lo standard ha avuto l’approvazione formale a marzo 2003. Le trasmissioni di contenuti multimediali attraverso cable modem, xDSL, o UMTS, l’aumento di servizi e la crescente popolarità della TV ad alta definizione stanno creando una crescente necessità di alte efficienze di codifica per poter trasmettere ad elevata qualità utilizzando le limitate capacità di trasmissione esistenti.

Il progetto dell’H.264/AVC comprende sia un Video Coding Layer (VCL), che rappresenta efficientemente il contenuto video, sia un Network Adatation Network (NAL) che struttura la rappresentazione del VLC e inserisce dei bit di intestazione in modo appropriato per la trasmissione (per approfondimenti [5,7]).

sistemi di trasmissione a pacchetto e non. Il formato delle unità NAL nei due casi è identico eccetto per il fatto che ogni unità NAL in sistemi di comunicazione non a pacchetto può essere preceduta da un prefisso di inizio codice. Rispetto agli standard di codifica precedenti la suddivisione in gruppi di blocchi (slices) è più flessibile dato che ogni slice può essere decodificata in modo indipendente dalle altre. L’H.264/AVC prevede la trasmissione e la ricezione di slice in un ordine qualunque; questo migliora il ritardo tra la fine di un immagine ricostruita e la seguente e determina un guadagno soprattutto nelle applicazioni in tempo reale.

1.4.2

Video Coding Layer

Il progetto del VCL , come negli standard precedenti, segue un approccio di tipo ibrido strutturato a blocchi. Per sfruttare le dipendenze statistiche di tipo temporale viene implementato un algoritmo di tipo predittivo e utilizzando un dominio trasformato è possibile utilizzare le dipendenze statistiche di tipo spaziale. Non è un singolo elemento di codifica che rende questo standard migliore nell’efficienza di compressione ma piuttosto una seria di piccoli miglioramenti, che portano assieme ad un notevole guadagno.

Nella figura 1.6 si riporta uno schema di base di un VCL per un macroblocco 16x16.

L’immagine viene suddivisa in blocchi. La prima immagine di una sequenza o di un punto di essa con accesso casuale tipicamente è codificato in modo “intra” usando solo le informazioni presenti nell’ immagine stessa. Ogni campione in un blocco di un intra-frame è predetto utilizzando campioni spaziali dei vicini blocchi che sono già stati codificati. Il processo di codifica sceglie come e quali campioni usare per la predizione di tipo intra.

Figura 1.6: struttura di base di un VCL per H.264/AVC per un macroblocco

Per tutte le immagini della sequenza che restano si usa un approccio di codifica di tipo “inter”. La predizione inter sfrutta i frame codificati in precedenza (compensazione del moto). Il processo di codifica per la predizione inter consiste nello scegliere dati riguardanti il moto, comprendenti l’immagine di riferimento e uno spiazzamento, che viene applicato a tutti i campioni del blocco. I dati riguardanti il moto sono poi trasmessi come informazioni addizionali e sono usate dal decoder e dall’ encoder per fornire il segnale di predizione inter.

Ciò che resta come residuo della predizione, sia essa intra o inter, (in pratica dato dalla differenza tra l’immagine originale e quella predetta) viene trasformato e i coefficienti ottenuti vengono poi scalati e quantizzati. Tali coefficienti sono poi codificati in modo entropico e trasmessi con le informazioni addizionali.

1.4.3

Suddivisione dell’immagine in macroblocchi

Ogni immagine viene suddivisa in macroblocchi di dimensione fissata; ogni macroblocco copre un’area rettangolare di 16x16 campioni della componente di luminosità e 8x8 campioni di ognuna delle due componenti di crominanza. I campioni di luminosità e crominanza di un macroblocco sono predetti sia temporalmente che spazialmente e il residuo della predizione risultante viene poi trasmesso.

I macroblocchi sono organizzati in quelle che vengono dette “slices” cioè una parte dell’immagine data che può essere codificata in modo indipendente. L’ ordine di trasmissione dei macroblocchi è determinato dalla cosiddetta “macroblock allocation map” e non è detto che sia in ordine raster. H.264/AVC supporta cinque diversi tipi di codifiche di slice. La più semplice è quella di tipo intra (I-slice) dove i macroblocchi sono codificati senza fare riferimento alle altre immagini della sequenza, tale riferimento viene invece effettuato per la codifica di tipo predittiva e bi-predittiva (rispettivamente indicate come P-slice e B-slice). Le rimanenti due tipologie di codifiche di slice sono la “switching P” (SP-slice) e la “switching I” (SI-slice) che sono specifiche per applicazioni in cui ci si sposta in continuazione tra bit-stream codificati a diversi bit-rate.

Per fornire metodi efficienti per il recupero degli errori l’H.264/AVC prevede un particolare modo di assegnare i macroblocchi alle slices ottenuto col cosiddetto FMO (Flexible Macroblock Ordering). I macroblocchi vicini vengono trasmessi su slices diverse in modo tale che se anche nella trasmissione viene perduta un’intera slice sono comunque in grado di ricostruire l’immagine, altrimenti se perdessi le informazioni relative a tutti i macroblocchi in una precisa zona dell’immagine non sarebbe possibile ricostruire tale zona in modo efficiente.

1.4.4

Predizione di un intra-frame

Ogni macroblocco può essere codificato in uno dei modi descritti in precedenza a seconda della slice in cui è inserito. Sono supportate due classi di codifica intra denominate come INTRA-4x4 e INTRA-16x16. Differentemente dai codificatori precedenti, nei quali la predizione era effettuata nel dominio trasformato la predizione nell’H.264/AVC è sempre condotta nel dominio spaziale facendo riferimento ai campioni vicini dei blocchi già codificati.

Quando si sceglie il modo INTRA-4x4 ogni blocco 4x4 che si riferisce alla luminanza utilizza uno dei nove modi di codifica. Infatti oltre alla predizione DC sono previsti altri otto modi. Utilizzando invece il modo INTRA-16x16, che è molto efficiente per aree in cui ho minore variazioni, si effettua una predizione uniforme per i componenti di luminanza. Sono supportati quattro modi di predizione. I campioni di crominanza dei macroblocchi sono sempre trattati come descritto nel caso INTRA-16x16. Non è permessa la predizione tra i bordi delle slices dato che esse devono mantenersi tra loro indipendenti.

1.4.5

Compensazione e stima del moto

In aggiunta ai tipi di codifica per i macroblocchi intra sono specificate altri tipi di codifica e di compensazione del moto . Ogni macroblocco di tipo P può essere suddiviso in blocchi più piccoli: 16x16 16x16), 16x8 16x8), 8x16 (inter-8x16), 8x8 (inter-8x8), nel caso in cui si scelga il modo inter-8x8 viene trasmesso nella codifica anche un elemento addizionale di sintassi che indica come il corrispondente sotto-macroblocco è stato codificato, cioè se per effettuare la predizione nella compensazione di moto si usano blocchi 8x4, 4x8 o 4x4. Questo standard di codifica offre una maggiore flessibilità per la gestione della dimensione e forme dei blocchi. Gli standard di codifica precedenti erano basati soprattutto su blocchi trasformati 8x8 mentre l’H.264/AVC principalmente si basa sui blocchi 4x4. In Figura 1.7 si riportano le partizioni in blocchi.

Il segnale di predizione per ogni blocco MxN codificato in modo predittivo è ottenuto selezionando un’area sull’immagine di riferimento, essa viene specificata attraverso un vettore di moto. Per un macroblocco 16x16 quindi posso essere trasmessi fino a 16 vettori di moto. La sintassi dell’H.264/JVT supporta un’accuratezza per la compensazione del moto di un quarto di pixel. Nei casi in cui il vettore di moto punta alla posizione di un campione intero il segnale che rappresenta la predizione è composto dal campione stesso nell’immagine di riferimento; negli altri casi il segnale si ottiene operando una media sui campioni interi e sui sottocampioni. Nel caso in cui si scelga una risoluzione di un quarto di pixel si adoperano nella media i campioni sulle posizioni con accuratezza intera e mezza utilizzando poi un filtro mono-dimensionale FIR a 6 coefficienti.

I valori di predizione per le componenti di crominanza sono ottenute da interpolazione bi-lineare.

Nell’H.264/AVC i vettori di moto possono anche puntare fuori dall’area dell’immagine, in questo caso i bordi vengono allargati ripetendo i pixel più esterni prima dell’interpolazione. Le componenti dei vettori di moto sono codificate usando una predizione sui mediani o direzionale dai blocchi vicini.

Attraverso i confini delle slices non si effettuano predizioni sulle componenti dei vettori di moto.

L’ H.264/AVC supporta una predizione per la compensazione di moto che si basa su più di una immagine, cioè per riferimento si può usare più di un’immagine codificata in precedenza. Questo concetto viene esplicato in figura 1.8.

Quattro frame codificati in precedenza frame corrente

Figura 1.8: compensazione di moto su più frame.

Congiuntamente al vettore di moto si trasmettono anche dei parametri (delta) riguardanti il frame di riferimento.

Il decoder e l’encoder devono memorizzare i frames precedenti di riferimento usati nella predizione di tipo inter in un buffer. Il decoder replica il buffer dell’ encoder in accordo al modo in cui si memorizzano i frames precedenti e alle operazioni di controllo per la gestione della memoria. A meno che la dimensione del buffer sia unitaria deve essere segnalato anche l’indice al quale è locata l’immagine di riferimento. L’indice di riferimento viene trasmesso per ogni blocco riguardante la luminanza 16x16, 16x8, 8x16 e 8x8.

In aggiunta ai modi di trasmissione dei macroblocchi trattati una slice P può essere trasmessa nel cosiddetto modo SKIP. Per questo modo non si trasmettono i segnali di errore della predizione né i vettori di moto né l’indice dell’immagine di riferimento. Il segnale ricostruito è comunque trattato in modo simile a quello usato nella predizione di un macroblocco 16x16 che usa come immagine di riferimento quella con indice nullo nel buffer. In generale i vettori di moto usati nel modo SKIP sono gli stessi di quelli usati nella predizione di un blocco 16x16; talvolta invece sotto particolari condizioni il vettore di moto viene settato a 0.

di memoria che serve per assicurare il corretto funzionamento del decoder. La rimozione di questa costrizione ha portato anche alla riduzione dei ritardi aggiuntivi che si avevano nel caso di predizione bi-direzionale.

1.5

Metodologia di valutazione di complessità e

prestazioni

Come si mostra in Figura 1.9, il flusso di progetto di sistemi multimediali complessi, come video codecs, tipicamente è composto di due fasi: una di sviluppo algoritmico seguita da un processo di implementazione del sistema. La prima fase riguarda le prestazioni algoritmiche ( Peak Signal to Noise Ratio –PSNR-, bit-rate e come effettivamente viene percepita l’immagine). Le specifiche algoritmiche sono determinate da una descrizione in formato cartaceo e da un modello software di verifica (spesso in C).

Di solito il modello software non è ottimizzato per una realizzazione di costo effettivo dal momento che il suo fine è sopratutto una verifica algoritmica funzionale e che la piattaforma che verrà poi utilizzata non è ancora nota. Inoltre, per standard multimediali come ITU-T e ISO/IEC video codecs, i modelli software di verifica sono scritti con diversi stili di codice dal momento che sono il prodotto di più team e sono molto complessi (quasi 100000 linee di codice).

La seconda fase del flusso di progetto riguarda la reale realizzazione del sistema partendo dalle specifiche di progetto e dal software utilizzato. Soltanto adesso, a questo stadio avanzato, è nota la vera complessità di implementazione dell’ algoritmo, che determinerà il costo del prodotto finale all’utente e che quindi determinerà se avrà oppure no successo e una larga diffusione.

Se le specifiche iniziali di costo non sono state raggiunte, le informazioni che sono state ricavate devono essere utilizzate per ripercorrere il flusso di disegno con modifiche a livello algoritmico e di implementazione. Si genera così un loop che termina solo quando la complessità soddisfa le richieste dell’utente.

Time Algorithm development

reference software code

Implementation electronic equipments

Complexity Cost of the service

Step 1 ( AVC status)

Analyze & Predict

focus on performance Conventional flow Aim of this work

Step 2

Optimize

Figura 1.9: co-valutazione di prestazioni algoritmiche e di complessità per un effettivo costo di un sistema

Per colmare il gap tra lo sviluppo algoritmico delle nuove applicazioni multimediali e la realizzazione del costo effettivo, proponiamo di esplorare le prestazioni mettendole in relazione con lo spazio del costo di implementazione già alla fase di progetto algoritmica. Il vantaggio che si trae da questo approccio di co-valutazione è duplice: (i) fornire le prestazioni e il costo algoritmico dei nuovi sistemi multimediali presentando un raffronto con la tecnologia corrente (indicato dalla freccia”analyse & predict”in fig. 1.9); (ii) avere dei feedback sulla realizzazione di colli di bottiglia e mettere in luce le proprietà del sistema permettendo una riduzione di complessità già alla fase algoritmica (indicato dalla freccia “optimize” in fig. 1). In questo modo possiamo risparmiare parte del tempo che era necessario per compiere il processo iterativo che si aveva nel flusso di disegno convenzionale. Per una trattazione più completa si rimanda a [6].

1.6

Analisi tool-by-tool del codice JM2.1

Il data base che verrà utilizzato in questa trattazione è disponibile al sito

http://bs.hhi.de/~wiegand/JVT.html dove troviamo le varie versioni del codice che sono state sviluppate in questi anni. Come si può ben osservare il codice, in linguaggio C++, è in continua evoluzione; infatti periodicamente compaiono sul sito sopra citato nuove versioni.

I software a cui faremo riferimenti sono: JM2.1 (di cui è stato fatto in [4] uno studio approfondito) e i recenti JM6.1d e AHM20.

Riporteremo di seguito i risultati di un analisi del codice JM2.1, svolto in [6], che saranno utili per la trattazione che svolgeremo nel prossimo capitolo.

In [6] è stata effettuato uno studio sulla versione JM2.1 riguardante il confronto tra le prestazioni e la complessità del codice. Le prestazioni sono state espresse in termini di rapporto segnale/rumore (PSNR) e bit-rate, come funzioni di costo per la valutazione della complessità sono stati presi in esame la frequenza di accesso ai dati (il numero di trasferimenti per secondo) e il picco di utilizzo della memoria (il massimo spazio di memoria che viene allocato dal codice). Le conclusioni a cui si è giunti in [4] indicano che la versione JM2.1 riesce a migliorare l’efficienza di compressione (fino a un 50% comparato ai precedenti standard ISO/IEC e ITU-T) mantenendo una buona qualità su un’ampia gamma di frequenze. Queste nuove funzionalità sono comunque legate ad un aumento del costo di implementazione. In [6] si compara il codice JM2.1 con l’MPEG-4, i risultati che si riportano fanno riferimento a codici sorgenti non ottimizzati, quindi un’ottimizzazione a livello algoritmico e architetturale porterebbe a una diminuzione del valore assoluto della complessità. Comunque in termini relativi si osserva per l’encoder un aumento di complessità di più di un ordine di grandezza tra MPEG-4 e il JM2.1 (considerando le specifiche non ottimizzate) e di un fattore 2 per il decoder. Il rapporto tra la complessità dell’encoder e quella del decoder varia tra 10 per le configurazioni di base e cresce fino a 2 ordini di grandezza per configurazioni più complesse. Come primo passo per ottenere un’efficace implementazione viene effettuata un’analisi tool-by-tool per sfruttare le dipendenze tra i tools e trovare un valido bilanciamento tra le prestazioni e la complessità. Per quanto riguarda l’encoder, il collo di bottiglia più importante si ha combinando più frames di riferimento con un’area di ricerca molto grande. Questi tools hanno un impatto limitato sull’ aumento

dell’efficienza di compressione soprattutto a medi e bassi bit-rate ma molto elevato per la complessità (fino a un fattore 60). Utilizzando Hadamard si ottiene sia un aumento di complessità che di bit-rate mentre si ha un guadagno in termini di PSNR. L’uso della risoluzione a 1/8 di pixel deve essere evitata a bassi bit-rate (si verifica solo un aumento di complessità senza avere guadagni) ma si rivela importante per applicazioni ad alto bit-rate. Le tecniche RD-Lagrangiane aumentano l’efficienza di compressione ma la complessità raddoppia quando la configurazione del codec è tale da comprendere molti modi di codifica e svariata decisioni sulla stima del moto. Adottare l’uso di blocchi a dimensione variabile migliora sia il bit-rate che il PSNR. Mentre la complessità aumenta linearmente con il numero dei modi usati, la maggior parte del guadagno si raggiunge già con i primi 4 modi. Il CABAC (codificatore entropico) fornisce un miglioramento in termini di bit-rate fino al 16% portando però ad un aumento dell’uso della memoria e di calcolo fino al 30% comparato col codificatore UVLC. Sono anche mostrati i risultati per l’uso dei B-frames e del filtro di deblock. Per quanto concerne il decoder, i tools che maggiormente comportano un peggioramento della velocità di decodifica e della frequenza di accesso in memoria sono l’utilizzo dei B-frames e di 1/8 di risoluzione. Un minore aumento di complessità è dovuto all’utilizzo del CABAC, di Hadamard, del filtro di deblock e della ottimizzazione ottenuta con RD-Lagrange. L’adozione di più frame di riferimento comporta un aumento lineare della memoria usata. I risultati delle simulazioni mostrati in [6] provano che, sommando i tools, la complessità continua a crescere mentre l’efficienza di compressione satura. Quindi un uso appropriato dei tools porta alle stesse prestazioni ma ad una notevole riduzione di complessità (di un fattore 6,5 per l’encoder e di un fattore 1,5 per il decoder).

1.7

Descrizione della stima del moto Full Search

La stima del moto è un elemento chiave in ogni sistema di compressione video dato che essa sfrutta la correlazione temporale tra i frames e quella spaziale all’interno del frame in esame per ridurre la ridondanza nell’ immagine da codificare [6]. La stima del moto è diventata anche un’operazione importante nella pre e post-processazione di

Un metodo per effettuare la stima del moto è quello che assume il nome di Full Search (FS) [1,2]: come si mostra in Figura 1.10, l’immagine in esame viene divisa in blocchi NxN non sovrapposti (tipicamente 16x16) che prendono il nome di blocchi correnti, per ciascuno di essi si ricerca in modo esaustivo su un’area di ricerca che presenta uno spiazzamento verticale e orizzontale pari a p il blocco (blocco candidato) che meglio approssima quello in esame.

m p a N n p Candidate Block Search Area N Current Block j i Frame i-1 Frame i Current Block Search Area Candidate Block b Frame i-1 Frame i

Figura 1.10: algoritmo di Full search

L’algoritmo che determina il blocco candidato consiste nella valutazione di una funzione di costo, di solito rappresentata dalla SAD (Sum of Absolute Differences). Se

a(i,j) e b(i,j) sono i pixel rispettivamente del blocco corrente e del blocco candidato e m

e n sono le coordinate dei vettori di moto (MV) la SAD viene definita come:

¦ ¦

con pdm,ndp1

La stima della distorsione viene fatta su tutte le 4˜p2 possibili posizioni che assumono i blocchi candidati all’interno della finestra di ricerca che ha una dimensione di _{(2 1)}2

  N

p pixels. Il blocco che presenta il valore minimo della SAD (SADmin)

viene selezionato per effettuare la predizione. Il corrispondente vettore di moto è dato da:

) ,

(MV MV mn _SAD

MV _{x y} con SADmin min

_>

_@

n)

(m, (1.5).

Questo approccio esaustivo permette di raggiungere prestazioni ottime in termini di PSNR per un dato fattore di compressione ma porta anche un aumento notevole della complessità computazionale e della banda necessaria per la gestione dei dati con una dipendenza quadratica rispetto alla dimensione dell’area di ricerca. Per esempio, a 30 Hz per un formato CIF (352x288 pixels) con i valori tipici di

p=16 e N=16, a livello di pixel sono richieste più di 3 u 109 operazioni al secondo (i.e su dati a 8 bits). L’aumento di complessità computazionale e i più frequenti accessi in memoria portano inevitabilmente a un aumento di consumo. Questo approccio non risulta quindi ideale per applicazioni in cui si trattano dispositivi alimentati a batteria per i quali il consumo di potenza è uno dei requisiti fondamentali: i cellulari di terza generazione, le macchine fotografiche con sensori CMOS, terminali di sorveglianza wireless e sistemi di tecnologia per assistere persone anziane o disabili. Anche per circuiti integrati la riduzione della potenza dissipata è un obiettivo fondamentale per evitare l’uso di costosi package per dissipare il calore.