Capitolo 3

(1)

Capitolo 3

All’interno di questo capitolo effettueremo, dopo aver descritto l’ambiente di test, l’analisi di alcuni algoritmi per stima del moto video che sono stati proposti per apportare migliorie a quello di Full Search (FS). Successivamente affronteremo uno studio di un nuovo algoritmo proposto e effettueremo delle comparazioni tra questo e alcuni presenti in letteratura.

3.1 Ambiente di test

Il testbench proposto in questo capitolo consiste di 6 sequenze con un diversi gradi di dinamismo formati e bit-rate di riferimento. Le caratteristiche sono mostrate in Tabella 3.1. Mother&Daughter 30Hz QCIF (176x144 pixels) (MD) è una sequenza a mezzo busto tipica di applicazioni a bassi bit-rate (decine di Kbps). Foreman 30Hz QCIF (FOR1) presenta una complessità media ed è un buon test per applicazioni sempre a bassi bit-rate che sono comprese tra le decine di Kbps e poche centinaia di Kbps. La versione CIF (352x288 pixels) di Foreman (FOR2) rappresenta un test adatto per applicazioni a medi bit-rate. Stefan CIF (SF), che contempla movimenti più rapidi, permette di valutare applicazioni con bit-rate alti dell’ordine di poche migliaia. Mobile&Calendar (MC1) SIF (352x240), presentando diverse tipologie di moto di oggetti, rappresenta un buon test per applicazioni ad alti bit-rate, dell’ordine delle migliaia di Kbps. Prendiamo in esame anche la versione CCIR (720x480) di Mobile&Calendar (MC2) che ci permette un’analisi a bit-rate ancora maggiori tipici di applicazioni High Qualità (HQ) video, DVD, HDTV.

I test sono stati realizzati, diversamente che nel precedente capitolo, variando il fattore di quantizzazione (QP). Riassumiamo quanto detto finora in tabella 3.1 riportando anche i bit-rate per un fattore di quantizzazione di riferimento pari a 28, ottenuti utilizzando il coder H.264/AVC nella versione JM6.1d con stima del moto di tipo Full Search.

(2)

Tabella 3.1Caratteristiche delle sequenze di test Config. test Sequenze

video Formato (pixels) Frame/s (Hz) Bit-rate (Kbps) a QP = 28 MD Mother & Daughter QCIF (176x144) 30 50

FOR1 Foreman QCIF

(176x144) 30 150

FOR1 Foreman QCIF

(176x144) 30 150 SF Stefan CIF (352x288) 30 1250 MC1 Mobile & Calendar SIF (352x240) 30 2100 MC1 Mobile & Calendar SIF (352x240) 30 2100

Tutte le simulazioni di seguito riportate sono state effettuate in ambiente Windows XP con un processore Intel Pentium 4 a 2,4 GHz con 512 MB di memoria SDRAM DDR.

3.2 Algoritmi di stima del moto a bassa complessità

In letteratura sono stati proposti parecchi algoritmi di stima del moto nei quali si cercava un compromesso tra la complessità, stimata rispetto alla Full Search (descritta in dettaglio nel paragrafo 1.6), e la ricerca dei vettori di moto in grado di minimizzare l’errore di stima: Three-Step-Search, Four-Step-Search, 2D Log- Search, Cross-Search [6,10].

Questi algoritmi si basano sulla riduzione del numero di blocchi candidati presi in esame per ogni blocco corrente ma non tengono conto delle correlazioni statistiche dei

(3)

numero di posizioni attorno al centro di ricerca e fissato da un passo predefinito. Tale passo viene poi diminuito e la ricerca continua in modo iterativo attorno alla posizione di minima distorsione. La procedura ha termine quando il passo diviene unitario oppure è raggiunto un numero fissato di iterazioni. Invece di determinare il minimo globale su un’area di ricerca generalmente il processo identifica un minimo locale.

La classe degli algoritmi predittivi [1,10,11] invece sfrutta la correlazione spaziale e temporale che caratterizza il campo dello studio del moto nelle sequenze video prese dal mondo reale [18].

I vettori di moto (MV) di in dato blocco possono essere predetti da un set di iniziali MV candidati, selezionati a priori dai vicini spazio-temporali, in accordo a una certa legge, tipicamente la minimizzazione della SAD. Per ridurre ulteriormente la stima dell’errore si implementa un processo utilizzando i MV predetti come punto di partenza. Per applicazioni a bassi bit-rate (da decine fino a poche centinaia di Kbps) è possibile raggiungere la stessa efficienza di compressione dell’FS riducendo complessità computazionale di un ordine di grandezza. Comunque, più le applicazioni sono ad alti bit-rate e più peggiorano le prestazioni di compressione.

Vale la pena notare che gli approcci sopra proposti rompono la regolarità del flusso di dati che si ha nella FS. Questo fenomeno causa un riutilizzo poco efficiente dei dati, e una complessità nel caricamento degli stessi [13,14,15,16], questo aspetto verrà poi approfondito nel paragrafo 3.6. Quindi, il fattore di risparmio (complessità del circuito e consumo di potenza) che caratterizza le implementazioni VLSI di tecniche di stima di moto veloce [14,17], messo a confronto con le architetture sistoliche che tipicamente si usano per implementare la FS, è molto inferiore del fattore di risparmio (complessità computazionale) che si ottiene a un livello algoritmico vedi [6].

Per potere superare tale limite degli algoritmi di stima del moto a bassa complessità sopra citate, nelle prossime sezioni opereremo una ricerca di blocchi candidati ottimali che sfrutti le variazioni dei dati in ingresso per evitare calcoli non necessari e accessi alla memoria non rilevanti. In tal modo vedremo che otterremo prestazioni molto simili a quelle ottenute con l’FS raggiungendo una considerevole riduzione di potenza.

(4)

3.3 Stima del moto e ricerca adattiva

Nel paragrafo 1.7 abbiamo descritto l’algoritmo di Full Search, esso si basa su una ricerca esaustiva del migliore blocco candidato compiuta all’interno della finestra di ricerca. La FS comporta il raggiungimento di un ottimo livello di efficienza di compressione che però si deve pagare in termini di complessità di calcolo. L’algoritmo di FS offre comunque una struttura molto regolare che offre vantaggi nell’implementazione hardware permettendo un elevato riutilizzo dei dati, limitando così l’accesso alla memoria, questo aspetto sarà poi approfondito nel paragrafo 3.6.

Di seguito verranno proposti una serie di algoritmi in grado di offrire le stesse prestazioni della FS ma con un carico computazionale minore.

3.3.1 Approccio Window Follower

Possiamo osservare che l’attività di moto di una scena è direttamente collegata al valore dei MV. Nel caso di una elevata attività una finestra di ricerca di dimensioni allargate permette di prendere un MV che porti alla stima con un errore piccolo. Quando, invece, il moto presente in una scena è limitato non è necessario compiere una ricerca su un’area troppo allargata. Basandoci su queste considerazioni, e prendendo in considerazione la correlazione spazio-temporale dei campi di MV derivati da immagini prese dalla realtà, è possibile realizzare una finestra di ricerca la cui dimensione dipende, per tutti i blocchi di un frame, dal massimo spiazzamento nel campo dei MV del frame corrente o/e di quello precedente. In questo modo la finestra di ricerca segue il campo dei MV. Un approccio simile è stato seguito da Minocha e Shambang in [10], per il generico kth frame, l’algoritmo è:

Step 1. Dalla lista completa dei MV del precedente (k-1)th frame, calcolare il

massimo spiazzamento verticale e orizzontale chiamato D e definito come:

[ ]

t (t) d max D= (3.1) essendo

[

x y

]

t max MVt MVt d = , (3.2)

il massimo spiazzamento del vettore di moto MVt del generico tth blocco appartenente al frame.

(5)

Step 2. Calcolare i MV per tutti i blocchi del kth frame adottando una ricerca esaustiva con uno spiazzamento per l’area di ricerca pari a p=1+D. Per il primo frame poniamo p=pmax.

Come si afferma in [19], per sequenze con cambiamenti graduali di moto questo approccio permette un risparmio del 60% di consumo di potenza rispetto alla FS mantenendo prestazioni similari. Sorgono però problemi quando ci troviamo di fronte a cambiamenti di moto repentini o nel caso di analisi di frame in cui ci sono oggetti caratterizzati da diverse attività di moto, come ad esempio avviene nella sequenza Calendar&Mobile. L’incremento della finestra di ricerca nello step 2 non è sufficiente per seguire rapidi cambiamenti del moto. Inoltre l’algoritmo si comporta nello stesso modo per tutti i blocchi del frame e sfrutta solamente le correlazioni temporali dei MV ma non quelle spaziali che caratterizzano i video tratti dal mondo reale come è provato in letteratura [13,18,20,21].

3.3.2 Algoritmo JVT-C065

Riprendiamo adesso l’algoritmo trattato nel paragrafo 2.4.1. Si propone l’introduzione di una stima del moto con una area di ricerca adattiva (adaptive search area) JVT-C065.

La decisione sull’ampiezza dell’area di ricerca riveste un ruolo fondamentale nella stima di moto e permette la riduzione di complessità dell’ encoder. L’ algoritmo che viene proposto consta di più passi.

B C

A

E

(6)

Possiamo assumere che E sia un macroblocco sulla quale viene operata la stima del moto, e A,B,C siano dei blocchi 4x4 vicini come mostrato in Figura 3.1. Possiamo inoltre assumere che i motion vectors di A, B, C siano (MV_AX, MV_AY), (MV_BX,

MV_BY), (MV_CX, MV_CY), e il range di ricerca che viene inserito in ingresso sia

definito come imput_saerch_range. Un nuovo range di ricerca viene definito con i seguenti passi:

Step 1. Si verifica il numero di blocchi 4x4 vicini effettivamente presenti, se sono

almeno due vado al passo 2 altrimenti al 4.

Step 2. Dai motion vectors dei blocchi vicini determino la massima componente

orizzontale e verticale.

[

), ( _ )

]

_

max_MV E_i =max abs(MV_A_i),abs(MV_B_i absMV Ci per i = x,y (3.3)

nell’ equazione (3.3) se un blocco non è disponibile le componenti dei vettori sono settate a 0.

Step 3. Determinazione del range di ricerca locale (local_search_range).

[

_i i

]

i max k ,2xmax_MV E range

search

local_ _ = _ (3.4)

k_i è definito come: (input_search_range + 4)>>3 se alpha_i = 0. (3x input_search_range +8)>>4 se 0<alpha_i<2 (input_search_range +2)>>2 altrimenti

[

_i _i) ( _ i)

]

i abs(MV_A ) abs(MV_B abs MV C

alpha = + + (3.5)

Step 4. Viene determinato ora il nuovo search range che al massimo può essere pari

al valore posto in ingresso oppure assume il valore del range di ricerca locale determinato nello step 3.

(7)

[

i i

]

i input_search_range,local search range range

search

new_ _ =min _ _ (3.6)

oppure se il numero di blocchi disponibili è minore di due

i range search input range search new_ _ i = _ _ (3.7)

L’algoritmo proposto permette un risparmio in termini di tempo di codifica, in quanto determina, dove possibile, un range di ricerca più piccolo. La stima del moto diventa così meno pesante e può essere eseguita in tempi minori. Viene efficientemente sfruttata la dipendenza spaziale all’interno del frame ma non viene tenuto di conto della correlazione temporale che si ha tra frames successivi, questo porta a una compressione non del tutto efficiente soprattutto nelle applicazioni a bassi bit-rate dove l’attività di moto è comunque limitata e una predizione basata sullo sfruttamento della correlazione temporale tra frames sembra risultare ottimale.

3.3.3 Algoritmo Enhanced Window Follower per H.263

Questo algoritmo è stato proposto in[6] per la versione H.263/AVC utilizzando un solo frame di riferimento. Si cerca di superare i limiti dell’approccio proposto in [18] (i) adottando il valore della SADmin come misura dell’efficienza delle stima di moto; (ii) sfruttando nel campo dei vettori di moto sia le correlazioni spaziali che quelle temporali. Nel caso di codifica inter tra frame un alto valore della SADmin indica un elevato errore, per questo la SADmin di un certo blocco è confrontata con certe soglie per selezionare l’area di ricerca ottimale per i blocchi successivi. Per il generico kth frame l’algoritmo proposto è:

Step 1. Dalla lista completa dei MV del precedente (k-1)th frame calcolare il

massimo spiazzamento D come definito nell’equazione (3.1).

Step 2. Calcolare i MV per tutti i blocchi del kth frame adottando una ricerca

esaustiva con uno spiazzamento pt, per il generico tth blocco, dimensionati secondo le

(8)

i) SADmint-1 ≥ TH1 Æ F =1 e pt = pmax

ii) TH2 ≤ SADmint-1 < TH1 e F = 1 Æ pt = 1+max (D, dt-1)

TH2 ≤ SADmint-1 < TH1 e F = 0 Æ pt = 1+D

iii) SADmint-1 < TH2 e F = 1 Æ pt = max (D, dt-1)

SADmint-1 < TH2 e F = 0 Æ pt = D

Per il primo frame p=pmax.

SADmint-1 e dt-1 rappresentano rispettivamente la SADmin e il massimo

spiazzamento dei MV per il (t-1)th_{blocco del frame corrente.}

TH1=4096 e TH2=2048 sono le due soglie che sono state usate per valutare

l’efficienza della stima del moto. I loro valori derivano da simulazioni effettuate su sequenze con diversi gradi di dinamismo. Praticamente, quando si verifica un cambiamento di moto e l’attuale dimensione dell’area di ricerca non è sufficientemente larga, allora l’aumento dell’errore di predizione e della corrispondente SADmin è determinato dalla soglia TH1 che setta lo spiazzamento al massimo valore. Il valore

della seconda soglia TH2, invece, è utile nel caso cambi di moto graduali in cui non è

necessario un aumento dell’area di ricerca cercando così di evitare incrementi della dimensione dell’area non necessari.

F è un flag che viene settato a 0 all’inizio della valutazione di ogni frame. Durante la stima del moto se F=0 la dimensione dell’ampiezza dipende solamente dal campo dei MV del corrente (k-1)th frame attraverso la variabile D. Se F=1 la dimensione dell’area di ricerca dipende anche dal campo dei MV del kth frame attraverso la variabile dt-1.

Quindi, sono prese in esame sia la dipendenza temporale che quella spaziale. Vale la pena mettere in evidenza che F mantiene il suo valore quando sono applicate le regole di controllo ii) o iii) mentre può cambiare il suo valore all’inizio di ogni valutazione sul frame (reset) o quando si applica la regola di controllo i) (set).

Infine, come si vede in [6] l’equazione 1.3 (nel paragrafo 1.6) viene modificata attraverso una costante TH3 (=100) per dare maggiore priorità ai MV di coordinate

(9)

∑ ∑

− = − = − − = 1 0 1 0 3 ) , ( ) , ( ) 0 , 0 ( N i N j TH j i b j i a SAD (3.8).

Viene apportata questa modifica perché si raggiunge un miglioramento ulteriore nell’efficienza di compressione in quanto la codifica entropica (adottata negli standard ISO/IEC e ITU-T) è più efficiente quando le componenti dei MV sono prossime a 0. Tale modifica inoltre serve a ridurre la sensibilità della stima di moto alla fluttuazione dell’immagine dovuta al rumore presente in tutte la immagini statiche.

Rispetto all’algoritmo proposto in 3.3.2 viene adesso sfruttata sia la dipendenza temporale che quella spaziale. Tale algoritmo è stato pensato però per lo standard H.263 con blocchi 16x16 e un solo frame di riferimento, inoltre la predizione spaziale si basa solamente sul blocco precedente, mentre nell’algoritmo in 3.3.2 vengono presi in considerazione i MV di tre blocchi attorno al blocco corrente.

Nel prossimo paragrafo viene proposto, con riferimento allo standard H.264/AVC, un nuovo algoritmo che combina le tecniche proposte in 3.3.2 e 3.3.3 in quanto sfrutta sia le correlazioni temporali che si hanno tra frame, sia le correlazioni spaziali cercando però di rendere il processo di determinazione del range di ricerca più efficiente per tutti i bit-rate.

(10)

3.4 Algoritmo enhanced window follower

L’algoritmo trattato in 3.3.2, basato sullo standard H.264/AVC, esplica in modo efficiente la possibilità di sfruttare le corrispondenze spaziali per la determinazione di un range ottimale di ricerca. L’approccio che adotteremo per la definizione di un nuovo algoritmo si appoggia su una struttura di base simile a quella proposta in 3.3.2 alla quale verrà aggiunta la possibilità di sfruttare le corrispondenze temporali facendo riferimento al frame precedente. Di seguito si riporta una breve descrizione del codice C, che descrive il sistema, che andremo poi a modificare.

3.4.1 Struttura del codice sorgente

Il codice C che descrive l’H.264/AVC nella versione AHM20 conta più di 70000 linee e 122 file compresi quelli di libreria (59 file.h e 63 file.c) e presenta un file di configurazione (lencod.cfg) con 71 opzioni di codifica. Si può osservare come tale codice sia molto più complesso di quello che descrive gli standard precedenti, ad esempio per l’H.263 si contano circa 15000 linee di codice e 15 opzioni di codifica. Si riportano di seguito i passi principali del percorso di base che si segue nella codifica di un frame:

¾ Il processo ha inizio nel file “lencod.c”, dove si trova il main, con la funzione “Encode_one_frame”.

¾ Essa chiama la funzione “Encode_one_slice”, si osserva infatti che le slices (gruppi di macroblocchi appartenenti a uno stesso frame) devono essere codificate in modo indipendente tra loro.

¾ Al suo interno viene chiamata la funzione “Encode_one_macroblock” e adesso inizia il processo di codifica vero e proprio a livello di macroblocco ¾ Viene chiamata la funzione “Partition_motion_search” all’interno della

quale si determina il nuovo range di ricerca (“Determine_range”), e si effettua la stima vera e propria (“Block_motion_search”).

Effettueremo le modifiche sostanziali proprio in (“Determine_range”) aggiungendo la dipendenza dai MV del frame precedente sfruttando così le corrispondenze temporali. Abbiamo adottato un approccio di valutazione del range di ricerca condizionato da una

(11)

SAD minime, ovvero dell’errore di predizione, di tutti i blocchi appartenenti a ogni frame), in modo tale da operare con un algoritmo che scelga un range di ricerca con più parametri di giudizio, e in modo più severo se il valore della SADmax è elevato. Questo accade quando ci troviamo in una situazione con valore alto dell’errore. Per realizzare questo principio abbiamo avuto la necessità di studiare l’andamento della SAD per varie sequenze e per diversi fattori di quantizzazione.

3.4.2 Studio del comportamento della SAD al variare di QP

Abbiamo preso in esame la sequenza di Mother&Daugther (MD) formato CIF (176x144) per realizzare un’analisi a bassi bit-rate, e le sequenze Mobile&Calendar (MC1) formato SIF (352x240) e Stefan (SF) formato CIF (352x288) come esempio per applicazioni ad alti bit-rate. Nel codice C la SAD viene calcolata per ogni macroblocco 16x16 (corrisponde al valore assunto ogni volta da “min_mcost”).

Per ogni sequenza sono stati codificati 253 frames utilizzando vari fattori di quantizzazione (QP). Infatti le simulazioni sono state realizzate per valori di QP = 20, QP = 24, QP = 28, QP = 32, QP = 36.

Riporteremo di seguito l’andamento della SAD massima (maxsad), della SAD media (mediasad) e della SAD minima (minsad) per ogni frame, calcolate rispetto all’errore di predizione (SADmin),vedi paragrafo 1.6, di tutti i blocchi del frame.

Nel grafico in Figura 3.2 si osserva l’andamento della SAD per il test MD (utilizzando il coder JM6.1d con stima del moto Full Search. Si nota come in questa sequenza il valore delle SAD sia basso, anche la maxsad assume valori elevati solo per pochi frame; questo ci autorizza a pensare per applicazioni similari ad un algoritmo per determinare il range di ricerca non troppo severo, dato che comunque la sequenza, solo in pochi casi, comporta alti valori dell’errore di predizione (SADmin). Quindi anche con un’area di ricerca più piccola potrei raggiungere un’efficienza di codifica molto simile a quella che otterrei con un’area di ricerca più ampia.

(12)

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 1 24 47 70 93 116 139 162 185 208 231 frames codificati SA D minsad maxsad mediasad

Figura 3.2: andamento della SADmin per MD con QP =24.

Nel grafico in Figura 3.3 riportiamo l’andamento della SADmin per MC. Si nota come i valori assunti dalla SAD siano mediamente più alti rispetto a quelli registrati in Figura 3.2; inoltre la SAD massima (maxsad) indicativamente dal frame 140 assume valori molto alti. Questa situazione ci spinge a pensare alla necessità di un’area di ricerca più ampia e quindi a un algoritmo per la determinazione del range di ricerca più severo e che tenga di conto anche di più parametri rispetto al caso di MD.

Un comportamento similare lo ritroviamo per SF in Figura 3.4. Rispetto al caso di MC abbiamo valori della SAD massima (maxsad) addirittura più elevati. Possiamo estendere le stesse considerazioni fatte per MC anche in questo caso. Per questo genere di applicazioni si rende quindi necessaria una stima del moto più accurata effettuata su un’ampia area di ricerca.

(13)

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 1 23 45 67 89 111 133 155 177 199 221 243 frames codificati SA D minsad maxsad mediasad

Figura 3.3: andamento della SADmin per MC con QP =24.

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 1 24 47 70 93 116 139 162 185 208 231 frames codificati S AD minsad maxsad mediasad

(14)

Si sono riportati solamente i grafici relativi a un fattore di quantizzazione (QP) pari a 24 ma il comportamento per altri valori di QP è pressoché identico scalato però di una soglia che aumenta all’aumentare del QP. E’ logico aspettarsi tale comportamento: ad un aumento di QP corrisponde un peggioramento della qualità.

Possiamo concludere che per applicazioni a bassi bit-rate posso pensare di utilizzare un algoritmo per determinare il range di ricerca che si basi su parametri meno restrittivi: la scelta che effettueremo sarà quella di utilizzare anche la predizione temporale nelle applicazioni solamente quando l’errore di predizione dei macroblocchi (SADmin) sarà superiore a dei valori fissati, altrimenti opereremo basandoci solamente su dati relativi al frame corrente.

Le soglie vengono determinate in relazione all’andamento della SAD mostrato in Figura 3.2-3.4, in particolare da quella massima (maxsad). Se l’errore di predizione assume valori superiori a quelli della maxsad si pensa appunto alla necessità di utilizzare anche dati appartenenti al frame precedente e comunque operare in modo più restrittivo.

Nella Figura 3.5 e nella Figura 3.6 sono riportati i grafici nei quali osserviamo l’andamento delle SADmin, mediate sui 253 frame codificati, per i vari QP rispettivamente per MC e per SF.

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 1 2 3 4 5 casi di QP SA D minsad maxsad mediasad

(15)

Nei grafici indichiamo con (1 QP =20, (2 QP =24, (3 QP =28, (4 QP =32, (5 QP =36. 0 1000 2000 3000 4000 5000 6000 7000 8000 1 2 3 4 5 casi di QP SA D minsad maxsad mediasad

Figura 3.6: andamento della SAD al variare del QP per SF.

Si osserva dalla Figura 3.5 e dalla Figura 3.6 che l’andamento della SAD massima (maxsad) per le due sequenze è molto simile. Abbiamo scelto di interpolare questo andamento con una funzione di tipo lineare e l’equazione che lo descrive risulta essere:

alpha QP+ *

75 (3.9)

In cui alpha è un parametro che assume i valori 2500 e 1000. Tali valori sono stati definiti dall’osservazione dell’andamento della maxsad descritto nelle figure 3.1, 3.2 e 3.3.

Il valore più alto di alpha determina un livello oltre il quale si ritiene il valore della SADmin indicativo di un errore elevato. Quando invece il valore della SADmin è inferiore a quello determinato nell’espressione (3.9) utilizzando per alpha il valore più basso, ci troviamo in una condizione di segnale di errore abbastanza piccolo.

Durante la codifica di un blocco siamo così in grado di confrontare il valore della SADmin del blocco precedentemente codificato con delle soglie opportune, nell’algoritmo da noi implementato ne vengono utilizzate 3, esse permettono di

(16)

affrontare la determinazione del range attraverso approcci diversi. Le prime due soglie sono date dal valore dell’espressione (3.9) sostituendo i due valori di alpha, la terza assume il valore dell’espressione (3.10):

beta QP+ *

35 (3.10)

Il valore di questa espressione è stato ottenuto in modo empirico, basandosi sull’osservazione delle SAD massima, minima e media e effettuando verifiche di prestazioni del codice modificato dall’introduzione di questo algoritmo su più sequenze. Un valore della SADmin inferiore a quello assunto dall’espressione (3.10) è indice di un segnale di errore molto basso che ci spinge a operare in modo tale da determinare un’area di ricerca ridotta, possiamo così ottenere risparmi in termini di tempo necessario per la computazione senza perdere in prestazioni.

Il parametro beta assume valori conseguentemente al target bit-rate: -100 e 900 rispettivamente per applicazioni ad alto bit-rate e a basso bit-rate. Come vedremo anche nel paragrafo 3.4.3 è opportuno utilizzare un algoritmo meno restrittivo per applicazioni a bassi bit-rate; è difatti per tale motivo che l’espressione (3.10) assume valori più alti nel caso di bassi bit-rate. Tale concetto apparirà più chiaro nel seguente paragrafo.

(17)

3.4.3 Descrizione dell’algoritmo proposto

L’idea di base è quella di avvalersi di 3 soglie, come viene mostrato in Figura 3.7:

Figura 3.7:Suddivisione in zone del dominio di analisi per determinare il range di ricerca. Come viene mostrato in Figura 3.7 l’introduzione di 3 soglie divide il dominio di analisi in 4 zone:

¾ Zona 1: il valore della SADmin è elevato, stiamo operando quindi con condizioni di alto segnale di errore, utilizzeremo dunque per la predizione sia dati spaziali che temporali. Devo valutare in modo più severo l’area di ricerca, eventualmente allargandola di quanto risulta necessario. Setto il flag F =1, tale flag forza l’algoritmo ad operare nelle condizioni appena descritte. ¾ Zona 2 : La SADmin assume un valore intermedio, il comportamento

dell’algoritmo dipende dal valore di F, se pari ad 1 si comporta come descritto per la Zona 1, altrimenti per la predizione utilizzo solamente dati spaziali. F conserva il suo valore.

¾ Zona 3 : La SADmin assume valori bassi, questo ci permette di pensare un’analisi basata solo sui dati spaziali e di porre F =0.

75*QP+2500 75*QP+1000 35*QP+alpha ZONA1 ZONA2 ZONA3 ZONA4

(18)

H

¾ Zona 4 : La SADmin assume valori molto bassi che ci autorizzano non solo a trascurare i dati temporali, ma anche a utilizzare una stima che mi porti alla determinazione di un’area di ricerca ridotta. F viene forzato a 0.

La decisione sull’ampiezza dell’area di ricerca riveste un ruolo fondamentale nella stima di moto e permette la riduzione di complessità dell’encoder. L’ algoritmo che viene proposto consta di più passi e conserva una struttura similare a quella trattata in 3.2.2.

Figura 3.8: locazione dei blocchi di riferimento per la decisione dell’area di ricerca

Possiamo assumere che E sia un macroblocco sulla quale viene operata la stima del moto, e A,B,C siano dei blocchi 4x4 vicini, e H sia il macroblocco precedentemente codificato, come mostrato in Figura 3.8. Possiamo inoltre assumere che i motion vectors di A, B, C siano (MV_AX, MV_AY), (MV_BX, MV_BY), (MV_CX, MV_CY), il motion

vector che porta le informazioni di correlazione temporale viene indicato con mv_p, intesa come componente X o Y a seconda di quale componente sia calcolata. Il range di ricerca che viene inserito in ingresso sia definito come imput_search_range. Un nuovo range di ricerca viene definito con i seguenti passi:

Step 1. Si verifica il valore della SADmin del blocco H, che definisce la zona in cui

vado a operare.

Step 2. Si assegna a mv_p (a cui è legata la predizione temporale) il massimo MVi

del blocco occupante la medesima posizione nel frame precedente se mi trovo nella

B C

A

(19)

zona 1 oppure nella zona 2 con F =1. Altrimenti mv_p ha valore nullo (utilizziamo cioè una predizione solo spaziale).

Step 3. Dai motion vectors dei blocchi vicini si determina la massima componente

orizzontale e verticale.

[

), ( _ )

]

_

max_MV E_i =max abs(MV_A_i),abs(MV_B_i abs MV Ci per i = x,y (3.11)

nell’equazione (3.11) se un blocco non è disponibile le componenti dei vettori sono settate a input_range per il blocchetto A oppure assumono un valore pari a mv_p + K per i blocchetti B e C.

K assume i seguenti valori:

K =0 se il target bit-rate è basso K =4 se il target bit-rate è alto

Step 4. Determinazione del range di ricerca locale (small_range).

[

i i

]

i local_search_range, MV E range

small_ =max max_ _ se Zona =4 (3.12)

[

i i

]

i mv_P,2*max_MV_E,local search range range

small_ =max _ _ altrimenti (3.13)

local_search_range_i è definito come:

(input_search_range + 4)>>3 se alpha_i = 0 (3x input_search_range +8)>>4 se 0<alpha_i<2 (input_search_range +2)>>2 altrimenti per target bit-rate alti oppure

local_search_range_i è definito come:

0 se alpha_i = 0

1 se 0<alpha_i<2

2 altrimenti

(20)

[

_i _i) ( _ i)

]

i abs(MV_A ) abs(MV_B abs MV C

alpha = + + (3.14)

Step 5. Viene determinato ora il nuovo search range che al massimo può essere pari

al valore posto in ingresso oppure assume il valore del range di ricerca locale determinato nello step 4.

[

i i

]

i input_search_range,local search range range

search

new_ _ =min _ _ (3.15)

3.5 Confronto dell’ algoritmo proposto con la FS e

JVT-C065

Si presentano in questo paragrafo una serie di simulazioni effettuate su più sequenze utilizzando l’algoritmo proposto in 3.4.3, il JVT-C065 e l’algoritmo di FS. Le prime simulazioni che andremo ad analizzare sono relative alle sequenze di MD e FOR per studiare il comportamento del codice su applicazioni a basso bit-rate, con MC1 e SF invece analizzeremo il comportamento ad alti bit-rate.

In seguito riporteremo delle tabelle in cui si evidenzia il comportamento dei diversi algoritmi inserendo dei tools opzionali testati su sequenze a basso (MD) e alto (MC2) bit-rate.

Infine vedremo nel paragrafo 3.5.3 il comportamento degli algoritmi fissando tipici bit-rate per applicazioni che variano tra trasmissioni multimediali attribuibili a modem 56K fino a high qualità video (DVD, digital cinema, HDTV).

3.5.1 Risultati di simulazioni relative ai tre algoritmi

3.5.1.1 Considerazioni sulle prestazioni

(21)

come vedremo in questo paragrafo le prestazioni sono sostanzialmente identiche, mentre ho variazioni significative per i tempi di codifica. L’analisi viene effettuata al variare del fattore di quantizzazione (QP) che assume i seguenti valori:

1. QP = 20 2. QP = 24 3. QP = 28 4. QP = 32 5. QP = 36

La prima sequenza che prendiamo in esame è quella di Mother&Daughter QCIF (176x144) (MD). Di seguito riportiamo i grafici che descrivono l’andamento del PSNR (Figura 3.9) e del bit-rate (Figura 3.10) ottenuti utilizzando il coder JM6.1d con diverse stime del moto. Dall’osservazione dei grafici si nota che le prestazioni per i codici sono pressoché identiche. 0 20 40 60 80 100 120 140 160 180 1 2 3 4 5 casi di QP b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

(22)

25 27 29 31 33 35 37 39 41 43 45 1 2 3 4 5 casi di QP P S NR (dB) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.10: andamento del PSNR al variare di QP per MD

Adesso riportiamo i grafici relativi alla sequenza Foreman QCIF (176x144) (FOR). In Figura 3.11 riportiamo il grafico relativo al bit-rate e in Figura 3.12 quello relativo al PSNR. Come per MD possiamo formulare le stesse conclusioni: le prestazioni sono praticamente identiche. 0 50 100 150 200 250 300 350 400 450 500 1 2 3 4 5 casi di QP b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

(23)

25 27 29 31 33 35 37 39 41 43 1 2 3 4 5 casi di QP P S N R (dB) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.12: andamento del PSNR al variare di QP per FOR1

Adesso riportiamo i grafici relativi alla sequenza Mobile&Calendar SIF (352x240) (MC1). In Figura 3.13 riportiamo il grafico relativo al bit-rate e in Figura 3.14 quello relativo al PSNR. 0 1000 2000 3000 4000 5000 6000 1 2 3 4 5 casi di QP b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

(24)

25 27 29 31 33 35 37 39 41 43 1 2 3 4 5 casi di QP P S NR (dB) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.14: andamento del PSNR al variare di QP per MC1

Adesso riportiamo i grafici relativi alla sequenza Stefan CIF (352x288) (SF). In Figura 3.15 riportiamo il grafico relativo al bit-rate e in Figura 3.16 quello relativo al PSNR. 0 500 1000 1500 2000 2500 3000 3500 4000 1 2 3 4 5 casi di QP b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

(25)

25 27 29 31 33 35 37 39 41 43 1 2 3 4 5 casi di QP P S NR (dB) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.16: andamento del PSNR al variare di QP per SF

Come si vede nelle Figure 3.13-3.16 anche per MC1 e SF le prestazioni sono identiche

Concludendo dai grafici riportati sopra non si osserva una deviazione significativa dal comportamento della FS per l’algoritmo proposto e per il JVT-C065, Tutti gli algoritmi determinano quindi il raggiungimento di prestazioni molto simili.

Vale la pena notare che all’aumentare del QP ho una sensibile diminuzione del bit-rate ma, inevitabilmente, ad essa corrisponde un peggioramento della qualità visiva dell’immagine; infatti ad un aumento del fattore di quantizzazione corrisponde anche una diminuzione del PSNR.

3.5.1.2 Considerazione sui tempi di codifica

Affrontiamo adesso l’aspetto riguardante il tempo che si impiega nella codifica utilizzando i 3 algoritmi in esame.

(26)

40 45 50 55 60 65 70 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) _CODIFICA DIFFERENZIALE JVT-C065 ALGORITMO PROPOSTO

Figura 3.17: andamento del tempo di codifica al variare di QP per MD

Si osserva che l’andamento del tempo di codifica è quasi indipendente dal QP, tale comportamento si manifesta anche per le altre sequenze. Per le successive analisi fisseremo dunque QP =28 senza perdere di generalità. Riportiamo i tempi e i bit-rate degli algoritmi paragonati a quelli ottenuti utilizzando una codifica differenziale (per ogni blocco si sceglie come miglior predittore il blocco che occupa la stessa posizione nel frame precedente; di seguito viene effettuata la compensazione del moto) e una codifica di tipo intra (non viene effettuata né la stima né la compensazione del moto).

0 20 40 60 80 100 120 140 te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

(27)

0 50 100 150 200 250 300 350 400 450 500 b it-r at e FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.19: bit rate per MD (QP =28)

Dalla Figura 3.18 si osserva come la versione proposta sia più veloce di:

6,8 rispetto alla FS

1,9 rispetto alla JVT-065 assumendo come limite di tempo minimo per la codifica inter quello impiegato con la codifica differenziale.

La versione proposta è poi più veloce di:

3,4 rispetto alla FS 1,4 rispetto

alla JVT-065 assumendo come limite di tempo minimo per la codifica quello impiegato con la codifica di tipo intra.

Riportiamo adesso i dati riguardanti il tempo di codifica relativi alla sequenza Foreman QCIF (176x144) nella Figura 3.20, sono anche riportati i tempi relativi a una codifica differenziale e a una codifica di tipo intra. In Figura 3.21 sono invece riportati i corrispondenti bit-rate. Si osserva come il bit-rate nel caso di codifica intra sia molto maggiore di quello ottenuto con la codifica di tipo inter, nonostante il tempo di codifica

(28)

molto minore l’approccio intra ci porta ad una compressione poco efficiente. Un ragionamento analogo può essere fatto per la codifica differenziale.

0 20 40 60 80 100 120 140 te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.20: tempo di codifica per FOR1

0 100 200 300 400 500 600 700 bit-r ate ( K bps) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.21: bit-rate per FOR1 (QP =28)

(29)

1,5 rispetto alla JVT-C065 assumendo come limite di tempo minimo per la codifica inter quello impiegato con la codifica differenziale.

1,3 rispetto alla JVT-C065 assumendo come limite di tempo minimo per la codifica quello impiegato con la codifica di tipo intra.

Riportiamo adesso i dati riguardanti il tempo di codifica relativi alla sequenza Mobile&Calendar (MC1) SIF (352x240) nella Figura 3.22, sono anche riportati i tempi relativi a una codifica differenziale e a una codifica di tipo intra. In Figura 3.23 sono invece riportati i corrispondenti bit-rate.

0 50 100 150 200 250 300 350 400 450 te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

(30)

0 1000 2000 3000 4000 5000 6000 7000 b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.23: bit-rate per MC1 (QP =28)

Riportiamo adesso i dati riguardanti il tempo di codifica relativi alla sequenza Stefan (SF) CIF (352x288) nella Figura 3.24, sono anche riportati i tempi relativi a una codifica differenziale e a una codifica di tipo intra. In Figura 3.25 sono invece riportati i corrispondenti bit-rate.

(31)

0 50 100 150 200 250 300 350 400 450 500 te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.24: tempo di codifica per SF

0 500 1000 1500 2000 2500 3000 3500 4000 4500 b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.25: bit-rate per SF (QP =28)

1,14 rispetto alla JVT-C065

(32)

assumendo come limite di tempo minimo per la codifica inter quello impiegato con la codifica differenziale.

Riportiamo infine i dati riguardanti il tempo di codifica relativi alla sequenza Mobile&Calendar (MC2) CCIR (720x480) che ci porta una visione del comportamento degli algoritmi a bit-rate molto alti, per applicazioni tipo DVD. Nella Figura 3.26, sono anche riportati i tempi relativi a una codifica differenziale e a una codifica di tipo intra. Non abbiamo riportato l’analisi delle prestazioni al variare del QP per questa sequenza dato che ha un comportamento similare alla stesse versione in formato SIF. Si riporta comunque il bit-rate per QP =28 in Figura 3.27.

0 100 200 300 400 500 600 700 800 900 1000 te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

(33)

0 5000 10000 15000 20000 25000 b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO DIFFERENZIALE INTRA

Figura 3.27: bit rate per MC2 (QP =28)

(34)

3.5.1.3 Conclusioni

Dall’analisi svolta nel paragrafo 3.5.1.1 si vede come non ci siano differenze rilevanti nella prestazioni di compressione relativamente ai tre codici presi in esame. I tre codici però presentano dei tempi necessari per la codifica sostanzialmente diversi. In effetti ha maggiore senso, da un punto di vista fisico, confrontare i tempi depurati di quanto viene impiegato dalla codifica differenziale; in quanto confrontiamo codifiche tutte di tipo inter e nello studio presentato ci concentriamo sulla stima del moto senza però andare a modificare la struttura della codifica, quindi le operazioni che sono eseguite in una codifica differenziale vengono comunque effettuate qualunque sia l’approccio seguito in una codifica inter. Alla luce di questa riflessione l’algoritmo da noi proposto consente una computazione da un minimo di 3 fino a quasi 7 volte più veloce di quella che si ha utilizzando la FS. Anche rispetto all’algoritmo JVT-C065 otteniamo un guadagno da 1,06 fino a 1,9. Il risparmio di tempo è più sensibile a bassi bit-rate, il comportamento dell’algoritmo in questo caso tende infatti a sfruttare molto le correlazioni spaziali per poter ridurre il range di ricerca senza perdere in prestazioni. Otteniamo comunque un guadagno su tutta la banda disponibile in trasmissione.

3.5.2 Comportamento rispetto all’introduzione di tools

Prenderemo adesso in considerazione l’introduzione di alcuni tools opzionali che l’H.264/AVC offre e analizzeremo le prestazioni così ottenute e i relativi tempi di codifica. Per l’analisi ci concentreremo solo sul fattore di quantizzazione QP =28; prenderemo in esame Mother&Daughter QCIF (176x144) come esempio di applicazione a bassi bit-rate e Stefan CIF (352x288) e Mobile&Calendar SIF (352x240). Tali sequenze sono entrambe ad alti bit-rate.

Riportiamo la legenda dei tools utilizzati:

1. No tools 2. RD optimisation 3. CABAC 4. 5 frame 5. CABAC + 5 frame 6. 3 frame 7. CABAC + 3 frame

(35)

3.5.2.1 Analisi di Mother&Daughter QCIF

Nella figura 3.28 si riporta l’andamento del tempo di codifica dei tre algoritmi al variare dei tools utilizzati, in Figura 3.29-3.30 si riporta rispettivamente il bit-rate e il PSNR. 0 100 200 300 400 500 600 1 2 3 4 5 6 7 tools te m p o d i co d if ica ( sec) _FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.28: tempo di codifica per MD

Dal confronto della Figura 3.28 con la Figura 3.29 si vede come solo nel caso 3, corrispondente all’introduzione del CABAC, registro un miglioramento di prestazioni che giustifichi l’uso del tool. Negli altri casi infatti anche se ottengo dei miglioramenti nelle prestazioni questi sono troppo piccoli per giustificare il relativo aumento del tempo di codifica. Vale la pena notare che il CABAC agisce all’esterno della stima del moto e non comporta un aumento del tempo di codifica, è dunque un tool che è comunque opportuno utilizzare.

(36)

0 10 20 30 40 50 60 1 2 3 4 5 6 7 tools b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.29: bit-rate per MD

Si riportano in Figura 3.30 anche i relativi valori di PSNR che però sono molto vicini (in Figura abbiamo allargato molto l’intervallo di rappresentazione) proprio perché abbiamo operato con bit-rate variabile fissando il PSNR.

36,75 36,85 36,95 37,05 37,15 37,25 37,35 37,45 1 2 3 4 5 6 7 tools P S NR (dB) OUR JVT-C065 ALGORITMO PROPOSTO Figura 3.30: PSNR per MD

(37)

3.5.2.2 Analisi di Mobile&Calendar SIF

Nella figura 3.31 si riporta l’andamento del tempo di codifica dei tre algoritmi al variare dei tools utilizzati, in Figura 3.32-3.33 si riporta rispettivamente il bit-rate e il PSNR. 0 200 400 600 800 1000 1200 1400 1600 1800 1 2 3 4 5 6 7 tools te m p o d i co d if ica ( sec) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.31: tempo di codifica per MC1

Dalla comparazione tra la figura 3.31 e la figura 3.32 si può osservare come l’introduzione di alcuni tools porti effettivo guadagno in termini di riduzione del bit-rate. Ci sono però casi in cui ad un aumento del tempo di codifica non corrisponde un adeguato incremento di prestazione. Nel caso di introduzione di RD optimisation non si registra un aumento di prestazioni tale da giustificare l’aumento del tempo di codifica che si registra quindi come conclusione non è opportuno utilizzare i software in questa configurazione. L’uso del CABAC comporta solamente un miglioramento delle prestazioni senza appesantire la computazione, quindi l’utilizzo del CABAC è sicuramente utile. L’utilizzo di 5 frame di riferimento abbassa sensibilmente il bit-rate ma comporta un aumento di complessità, i calcoli infatti, soprattutto nel caso della FS sono proporzionali al numero di freme di riferimento utilizzati (vedi [9]). Conviene comunque utilizzare più frame di riferimento insieme al CABAC in modo da ottenere prestazioni ancora migliori (casi 5, 7 ). Nel caso 6 prendiamo in esame l’utilizzo di 3 frame di riferimento. Osserviamo così un guadagno più limitato ma anche un minore

(38)

aumento del tempo di codifica. L’utilizzo dei 3frame può rappresentare un valido compromesso tra prestazioni e tempo impiegato.

0 500 1000 1500 2000 2500 1 2 3 4 5 6 7 tools b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.32: bit-rate per MC1

33,1 33,15 33,2 33,25 33,3 33,35 33,4 33,45 1 2 3 4 5 6 7 tools P S NR (dB) FS JVT-C065 ALGORITMO PROPOSTO Figura 3.33: PSNR per MC1

(39)

3.5.2.3 Analisi con Stefan CIF

Nella figura 3.34 si riporta l’andamento del tempo di codifica dei tre algoritmi al variare dei tools utilizzati, in Figura 3.35-3.36 si riporta rispettivamente il bit-rate e il PSNR. 0 500 1000 1500 2000 2500 1 2 3 4 5 6 7 tools te m p o d i co d if ica ( sec) _FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.34:Tempo di codifica per SF

Dalla comparazione tra la Figura 3.34 e la Figura 3.35 si può osservare come l’introduzione di alcuni tools porti effettivo guadagno in termini di riduzione del bit-rate. Ci sono però casi in cui ad un aumento del tempo di codifica non corrisponde un adeguato incremento di prestazione. Nel caso di introduzione di RD optimisation non si registra un aumento di prestazioni tale da giustificare l’aumento del tempo di codifica che si registra quindi come conclusione non è opportuno utilizzare i software in questa configurazione. L’uso del CABAC comporta solamente un miglioramento delle prestazioni senza appesantire la computazione, quindi l’utilizzo del CABAC è sicuramente utile. L’utilizzo di 5 frame di riferimento abbassa sensibilmente il bit-rate ma comporta un aumento di complessità, i calcoli infatti, soprattutto nel caso della FS sono proporzionali al numero di freme di riferimento utilizzati (vedi[9]). Conviene comunque utilizzare più frame di riferimento insieme al CABAC in modo da ottenere prestazioni ancora migliori (casi 5, 7). Nel caso 6 prendiamo in esame l’utilizzo di 3 frame di riferimento. Osserviamo così un guadagno più limitato ma anche un minore

(40)

aumento del tempo di codifica. L’utilizzo dei 3 frame può rappresentare un valido compromesso tra prestazioni e tempo impiegato.

0 200 400 600 800 1000 1200 1400 1 2 3 4 5 6 7 tools b it-r at e (Kb p s) FS JVT-C065 ALGORITMO PROPOSTO

Figura 3.35: bit-rate per SF

35,05 35,1 35,15 35,2 35,25 35,3 35,35 35,4 35,45 1 2 3 4 5 6 7 tools P S NR (dB) FS JVT-C065 ALGORITMO PROPOSTO Figura 3.36: PSNR per SF

(41)

Dalle analisi svolte per le tre sequenze relativamente all’introduzione di tools opzionali si evince che tra quelli analizzati l’unico tool che comunque è sempre opportuno adottare è il CABAC che offre un guadagno in prestazioni senza appesantire la computazione. Per applicazioni a bassi bit-rate come MD l’introduzione di più frame di riferimento porta un guadagno troppo ridotto per giustificare l’incremento del tempo impiegato nella codifica. Al contrario per applicazioni ad alti bit-rate come MC1 e SF nonostante un incremento di tempo abbiamo un consistente miglioramento delle prestazioni; questo è maggiormente evidente per MC1, infatti intuitivamente il guadagno utilizzando più frame di riferimento si ottiene quando si presentano oggetti parzialmente nascosti e con moti di natura diversa, vedi[9]. Tale ragionamento sarà ripreso poi nel paragrafo 3.7 modificando l’algoritmo proposto per poter applicare l’uso di molteplici frames di riferimento solo quando è opportuno.

3.5.3 Esempi di codifica fissando il bit-rate

Riportiamo adesso alcuni esempi di codifiche fissando il bit-rate, tali esempi corrispondono a tipici casi di trasmissione dati multimediali con modem 56 Kb/s, con modem xDSL a 256 Kb/s o 512 Kb/s, oppure servendosi di linee più veloci che consentono bit-rate di 1500 Kb/s fino ad arrivare ad applicazioni DVD con un rate di 5000 Kb/s. Si nota come, al variare delle sequenze e a parità di bit-rate, sequenze diverse presentano diversi tempi di codifica e qualità (PSNR). Per ottenere i dati riportati abbiamo operato attivando il tool di rate control che permette di fissare il bit-rate utilizzando poi QP adeguati per la compressione.

Nella figura 3.37 si osserva il tempo di codifica per applicazioni con un bit-rate di 56 Kb/s, nella figura 3.38 viene riportato il PSNR che ci indica la qualità della trasmissione. Dalle Figure 3.37 e 3.38 si osserva come per ogni sequenza la qualità con cui trasmetto è pressoché identica ma il tempo impiegato nella codifica è minore quando utilizzo l’algoritmo proposto.

(42)

0 10 20 30 40 50 60 70 80 90 100 1 2 sequenze te m p o d i co d if ica ( sec) ALGORITMO PROPOSTO JVT-C065

Figura 3.37: tempo di codifica a 56 Kb/s

1. Mother&Daughter QCIF 2. Foreman QCIF 0 5 10 15 20 25 30 35 40 1 2 sequenze P S NR (dB) ALGORITMO PROPOSTO JVT-C065 Figura 3.38: PSNR a 56 Kb/s 1. Mother&Daughter QCIF 2. Foreman QCIF

Nella Figura 3.39 prendiamo in esame applicazioni che utilizzano 256 Kb/s. Valgono ancora le stesse affermazioni fatte per un bit-rate di 56 Kb/s, l’algoritmo proposto, a parità di prestazioni, impiega un tempo mInore per la codifica.

(43)

0 50 100 150 200 250 300 350 400 1 2 3 sequenze te m p o d i co d if ica ( sec) ALGORITMO PROPOSTO JVT-C065

Figura 3.39: tempo di codifica a 256 Kb/s

1. Mother&Daughter CIF 2. Foreman QCIF 3. Foreman CIF 0 5 10 15 20 25 30 35 40 45 1 2 3 sequenze P S NR (dB) ALGORITMO PROPOSTO JVT-C065 Figura 3.40: PSNR a 256 Kb/s 1. Mother&Daughter CIF 2. Foreman QCIF 3. Foreman CIF

Riportiamo adesso un esempio per bit-rate più alti dell’ ordine di 512 Kb/s. per alti bit-rate utilizzeremo nella codifica i tools di CABAC e faremo riferimento a 3 frame.

(44)

Nella Figura 3.41 riportiamo i dati relativi al tempo di codifica. Si osserva che anche in questo caso l’algoritmo proposto offre tempi minori. Nella Figura 3.42 invece si riporta il PSNR. 700 720 740 760 780 800 820 840 860 te m p o d i co d if ica ( sec) ALGORITMO PROPOSTO JVT-C065

Figura 3.41: tempo di codifica per 512 Kb/s per Foreman CIF

0 5 10 15 20 25 30 35 40 P S NR (dB) ALGORITMO PROPOSTO JVT-C065

Figura 3.42: PSNR per 512 Kb/s per Foreman CIF

Continuiamo la nostra analisi per applicazioni ad alti bit-rate, adotteremo adesso un bit-rate di 1500 Kb/s (1536 Kb/s). Utilizzeremo ancora i tools di CABAC e 3 frame di

(45)

riferimento. Nella Figura 3.43 riportiamo l’andamento del tempo di codifica. Nella Figura 3.44 riportiamo il PSNR. 0 100 200 300 400 500 600 700 800 1 2 sequenze te m p o d i co d if ica ( sec) ALGORITMO PROPOSTO JVT-C065

Figura 3.43: tempo di codifica a 1536 Kb/

1. Mother&Daughter QCIF 2. Foreman QCIF 31 32 33 34 35 36 37 38 1 2 sequenze P S NR (dB) ALGORITMO PROPOSTO JVT-C065 Figura 3.44: PSNR a 1536 Kb/s 1. Mother&Daughter QCIF 2. Foreman QCIF

(46)

Riportiamo infine i dati relativi alla sequenza Mobile&Calendar CCIR (720x480) che propone un bit-rate di 5000 Kb/s (5012 Kb/s) tipico di applicazioni DVD. Utilizzeremo ancora i tools di CABAC e 3 frame di riferimento. Nella Figura 3.45 riportiamo l’andamento del tempo di codifica. Nella Figura 3.46 riportiamo il PSNR.

1060 1070 1080 1090 1100 1110 1120 1130 1140 1150 te m p o d i co d if ica ( sec) ALGORITMO PROPOSTO JVT-C065

Figura 3.45: tempo di codifica per 5012 Kb/s per Mbile&Calendar CCIR

0 5 10 15 20 25 30 35 40 P S NR (dB) ALGORITMO PROPOSTO JVT-C065

(47)

Riassumendo dalle figure riportate si evince come, su un’ampia gamma di applicazioni multimediali, l’algoritmo proposto riesca a ridurre ulteriormente il tempo di codifica rispetto a quello ottenuto con l’algoritmo JVT-C065 offrendo identiche prestazioni.

(48)

3.6 Considerazioni sulla architettura hardware

Nel nuovo standard di codifica H.264/AVC si fa uso di una stima del moto basata su una finestra di ricerca di dimensioni variabili centrate sul vettore di moto predetto e non, come accadeva per l’H.263, su quello di coordinate (0,0). Questa stima offre migliori prestazioni rispetto a quella utilizzata nell’MPEG-4 e nell’H.263, infatti si riesce a coprire un’area di ricerca maggiore, ma comporta delle difficoltà di implementazione a livello hardware, come si osserva in [8]. Adottando un’area di ricerca centrata sempre su (0,0), cioè sulle coordinate corrispondenti al frame corrente, posso pensare ad un riutilizzo dei dati che sono caricati nella SRAM all’interno del chip limitando l’accesso alla RAM esterna. Tale concetto viene chiarito in Figura 3.47.

Figura 3.47: rispettivamente: frame corrente e frame di riferimento

Supponiamo di fissare un range di ricerca pari a 16, quindi otterremo un’area di ricerca di 48x48. Chiamiamo con C11 il primo blocco corrente in esame e con C12 il secondo. Il blocco corrispondente alle coordinate di C11 nel frame di riferimento sarà S11 che assieme ai blocchi intorno con indici 0-2 identificano l’area di ricerca. Quando dovremo caricare i dati relativi all’area di ricerca per il seguente blocco C12 se il range è centrato in (0,0), che ora corrispondono alle coordinate di C12, i dati appartenenti ai blocchi indicati in grassetto in Figura 3.48 non devono essere ricaricati perché già presenti dalla precedente computazione. Ottengo quindi un risparmio di 2/3 nel trasferimento dalla memoria esterna riutilizzando i dati in comune con quelli della precedente ricerca. Limitando l’accesso alla memoria esterna ottengo un guadagno intermini di risparmio di potenza dissipata. Se l’area è di volta in volta centrata sul MV preddittore, e non su un punto fissato, tale riutilizzo dei dati non è possibile. Per poter

C11 C12 S11 S12 S02 S22 S10 S21 S00 S01 S02 S03 S13 S23

(49)

seguire un approccio in hardware che consenta appunto un risparmio di potenza dobbiamo introdurre un semplice controllo a livello software che ci permetta di fissare, quando ritenuto opportuno, il centro dell’area di ricerca. Utilizziamo ancora come funzione di costo da analizzare l’errore di predizione dei singoli macroblocchi (SADmin) verificando se assume valore superiore a una soglia determinata empiricamente. Calcolo cioè il massimo valore che SADmin assume nel frame corrente, memorizzandolo nella variabile maxsad, confrontando fra loro di volta in volta i valori rilevati dell’errore di predizione dei singoli macroblocchi.

)) 3500 ) * 125 (( maxsad< QP + (3.16)

Se il valore delle SAD massima (maxsad) verifica la disequazione (3.16) adottiamo un’area di ricerca fissa attorno a (0,0), altrimenti il centro del search range viene determinato dal MV predetto. Con questo accorgimento adottiamo un’area di ricerca mobile solamente quando strettamente necessario.

3.6.1 Risultati di simulazione dell’algoritmo con search area

fissa

Riportiamo adesso i risultati di simulazioni compiute sull’algoritmo proposto attivando la possibilità di avere un’area di ricerca con centro fisso e sull’algoritmo proposto che opera sempre con un’area adattiva. Utilizzeremo sequenze che presentano vari bit-rate. Inizieremo da Mother&Daughter QCIF, poi riporteremo entrambe le versioni di Foreman QCIF e CIF, e per alti bit-rate analizzeremo Stefan CIF e Mobile&Calendar sia SIF che CCIR. Riporteremo solamente i grafici del tempo di codifica e del bit-rate dato che nell’analisi fissiamo il PSNR che quindi per i due algoritmi in esame è costante. L’analisi viene effettuata al variare del fattore di quantizzazione (QP) che assume i seguenti valori:

1. QP = 20 2. QP = 24 3. QP = 28 4. QP = 32 5. QP = 36

(50)

3.6.1.1 Analisi con Mother&Daughter

In figura 3.48 osserviamo come l’andamento del tempo di codifica sia molto vicino, e dalla Figura 3.49 si vede come anche le prestazioni in termini di bit-rate siano molto vicine. Come conclusione a bassi bit-rate non ho differenze sostanziali date dall’introduzione di un’area di ricerca con centro fisso.

35 40 45 50 55 60 65 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

Figura 3.48: tempo di codifica per MD

0 20 40 60 80 100 120 140 160 180 1 2 3 4 5 casi di QP b it-r at e (Kb p s) ADAPTIVA SEARCH AREA CENTER FIXED SAERCH AREA CENTER

(51)

3.6.1.2 Analisi con Foreman QCIF

In figura 3.50 osserviamo come l’andamento del tempo di codifica sia molto vicino addirittura di poco inferiore, e dalla Figura 3.51 si vede come anche le prestazioni in termini di bit-rate siano molto vicine. Come conclusione non ho differenze sostanziali date dall’introduzione di un’area di ricerca con centro fisso.

35 45 55 65 75 85 95 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

0 50 100 150 200 250 300 350 400 450 500 1 2 3 4 5 casi di QP b it-r at e (Kb p s) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

(52)

3.6.1.3 Analisi con Foreman CIF

In figura 3.52 osserviamo come l’andamento del tempo di codifica sia molto vicino. Dalla Figura 3.53 si vede però come le prestazioni in termini di bit-rate siano di poco peggiori di quelle ottenute utilizzando sempre un’area con centro mobile. Il peggioramento registrato è comunque dell’ordine del 3%.

250 260 270 280 290 300 310 320 330 340 350 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVA SEARCH AREA CENTER FIXED SEARCH AREA CENTER

(53)

3.6.1.4 Analisi con Stefan CIF

Dalla figura 3.54 si osserva un aumento del tempo di codifica medio del 5,5% e dalla figura 3.55 un aumento del bit-rate fino all’11 %. Questo peggioramento che si riscontra è dovuto a una maggiore complessità delle sequenza che ad esempio nei frame dal #175 al #195 e dal #230 fino all’ultimo frame considerato nella simulazione presenta dei MV maggiori del search range, anche se con una stima della SAD riusciamo a valutare tale situazione e torniamo all’utilizzo di un’area centrata sui MV predetti ho comunque un peggioramento in prestazioni.

250 260 270 280 290 300 310 320 330 340 350 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

(54)

0 500 1000 1500 2000 2500 3000 3500 4000 4500 1 2 3 4 5 casi di QP b it-r at e (Kb p s) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

Figura 3.55: bit-rate per SF

3.6.1.5 Analisi con Mobile&Calendar SIF

Dalla figura 3.56 si osserva come l’andamento del tempo di codifica sia molto simile, si registra un aumento massimo del tempo di codifica inferiore all’1%. Dalla Figura 3.57 si vede che l’andamento del bit-rate al variare di QP è molto simile. L’introduzione quindi di un’area di ricerca con centro fisso, che viene applicata quando è permesso da una stima della SADmin, non peggiora in modo rilevante le prestazioni e garantisce un risparmio di potenza dissipata dovuto al riuso dei dati già caricati.

150 160 170 180 190 200 210 220 230 240 250 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

(55)

0 1000 2000 3000 4000 5000 6000 1 2 3 4 5 casi di QP b it-r at e (Kb p s) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

3.6.1.6 Analisi con Mobile&Calendar CCIR

Per la versione CCIR di Mobile&Calendar si possono trarre le stesse considerazioni fatte per la versione SIF. In questo caso non si ottiene neppure un tempo di codifica costantemente maggiore come testimoniato in Figura 3.58. L’andamento del bit-rate è riportato in Figura 3.59. 400 420 440 460 480 500 520 540 560 580 600 1 2 3 4 5 casi di QP te m p o d i co d if ica ( sec) ADAPTIVE SEARCH AREA CENTER FIXED SEARCH AREA CENTER

(56)

Per quanto osservato nelle analisi sopra trattate l’utilizzo di un’area di ricerca con centro fisso, condizionata alla stima della SAD, permette di poter ridurre i l consumo di potenza, sfruttando il riutilizzo dei dati nella memoria interna, senza avere un peggioramento rilevante di prestazioni. Questo concetto può essere applicato a tutti i bit-rate, l’unico caso in cui si osserva un peggioramento rilevante è per Stefan data la particolare natura della sequenza come espresso in 3.6.1.4. L’introduzione di un controllo sulla SAD permette comunque di limitare molto la degradazione di prestazioni a cui si andrebbe incontro se si utilizzasse incondizionatamente un’area di ricerca con centro fisso.

(57)

3.7 Stima del moto multiframe

Nel nuovo standard H.264/AVC è permesso l’uso di più frames per la stima del moto. Prendendo in esame la Full Search l’aumento di complessità computazionale è direttamente proporzionale al numero di frames che si utilizzano, vedi [9]. La riduzione dei residui di predizione, cioè il segnale di errore, è legata soprattutto alla natura della sequenza e meno all’utilizzo di più frames di riferimento. Presenteremo in questo paragrafo un metodo per aumentare la velocità di computazione utilizzando più frames. Per ogni macroblocco analizzeremo le informazioni disponibili sulla SAD per decidere se utilizzare più frames di riferimento o se è sufficiente l’utilizzo di un solo frame.

Rispetto agli standard precedenti come MPEG-4 e H.263 l’efficienza di compressione del nuovo standard è raddoppiata, ciò è dovuto soprattutto alla parte predittiva, in particolare alla stima del moto. Il modello C di riferimento utilizza 7 tipi di dimensioni di blocchi ma sostanzialmente per la compensazione del moto, il calcolo della SAD e per determinare altre funzioni utilizza uno schema di base che si fonda sulla computazione svolta sui blocchetti 4x4 per poi riportare i risultati a blocchi di dimensioni maggiori. Infatti la dimensione variabile dei blocchi non porta a rilevanti aumenti di complessità di calcolo. L’introduzione però di molteplici frames di riferimento replica le operazioni svolte per ogni frame nel quale si effettua la ricerca; talvolta il guadagno in termini di prestazioni è notevole, talvolta otteniamo una mole di calcoli senza trarne alcun beneficio.

In [9] si afferma che per l’80% dei casi i MV ottimali per la predizione sono quelli appartenenti al frame precedente, è quindi necessario identificare una funzione di costo che ci indichi se dobbiamo usare oppure no più frames di riferimento.

L’idea di base è quella di confrontare la maxsad (valore massimo dell’errore di predizione dei singoli macroblocchi) del frame precedentemente codificato rispetto a quello in esame con delle soglie e utilizzare una predizione basata su più frames solo se ci accorgiamo di avere un segnale di errore troppo elevato.

Per la determinazione delle soglie diversamente da quanto fatto in 3.4.2 abbiamo adottato un’approssimazione lineare a tratti per i vari QP. Tale approssimazione è stata scelta perché maggiormente efficace per la scelta del numero di frame da utilizzare mentre non era necessaria per la definizione dell’algoritmo trattato. L’andamento della SAD massima al variare di QP è stato quindi così determinato: