Il compito di un codificatore MPEG è quello di determinare
i frames della sequenza video e di codificarli.
Questo simulatore mostra la sola determinazione dei frames ad uso didattico.
Sotto il nome di ‘‘Motion Estimation'' si indicano gli algoritmi
utilizzati dal codificatore per identificare
la correlazione fra le immagini. Tali algoritmi non fanno parte delle specifiche
MPEG, che si occupano
solo della decodifica.
Fondamentalmente, le tecniche di Motion Estimation ricadono in due principali
categorie. Nella ‘‘pel recursion'' i motion vector sono calcolati
mediante un procedimento recursivo, utilizzando gradienti di
intensità e informazioni sulla differenza fra le immagini. Questa
tecnica è utilizzata principalmente in
sistemi in cui i motion vector variano da pixel a pixel, e quindi non è applicabile
all'MPEG.
Nella ‘‘block matching'' i motion vector vengono determinati
dal calcolo di alcune misure di distorsione, con
l'obiettivo di scegliere il vettore che fornisca la distorsione minima.
Questa tecnica si applica a sistemi
in cui i motion vector sono associati a un blocco di pixel, come l'MPEG.
Richiami: compressione MPEG
Un video MPEG è essenzialmente una sequenza di tre tipi di frames:
I-Frames: "intra-coded"
Frames che possono essere ricostruiti
senza alcun riferimento agli altri frame.
P-Frames: "forward predicted"
Frames predetti in avanti a partire dall'ultimo frame di tipo I o P.
Non possono essere dunque ricostruiti senza i dati di un altro frame.
B-Frames: "forward&backward predicted"
Frames che sono sia predetti in avanti dall'ultimo I/P-Frame, sia predetti
in indietro dal prossimo I-P/Frame.
C'è quindi bisogno di 2 altri frame per poterli ricostruire.
Si considera in questa applet una sequenza standard del tipo:
I-B-P-B-I-B-P-B-I-B-P-B-I-B-P-P
Dato che i mosaici sono stati acquisiti con un tempo di scatto di circa 150ms
sono soddisfatti i requisiti:
- un I-Frame ogni circa 500ms
- due B-Frame fra due P/I Frames
In uscita al codificatore questi frame devono quindi essere riordinati per
poter essere elaborati dal decodificatore. Infatti i B-Frame richiedono per
la codifica anche informazioni di frames futuri. Cioè i frames predetti
in indietro devono anticipare il B-Frame relativo.
Predizione
Per capire cosa si intende per predizione si consideri
il seguente esempio.
Un I-Frame mostra un rettangolo su fondo bianco.
Un P-Frame successivo
corrisponde ad un immagine dello stesso rettangolo ma in posizione diversa.
Il compito del P-Frame è quello di trasmettere l'informazione per ricostruire
l'immagine a cui fa riferimento.
Per far ciò bisogna codificare il movimento
a cui è stato soggetto il rettangolo.
Predizione significa quindi estrazione di un vettore di moto
("Motion vector") che permette di ricostruire con buona fedeltà il
rettangolo nella nuova posizione.
Applet: determinazione dei frames
Ogni frame è composto da 128 x 96 pixel in verticale,
organizzati in macroblocchi da 16 x 16 pixel.
Si scompongono quindi i due fotogrammi in esame in macroblocchi.
Si procede poi valutando un blocco alla volta del primo fotogramma e per ogni
blocco:
- si determina l'errore col blocco corrispondente nel fotogramma di riferimento;
- se l'errore non supera la soglia si considera il blocco come non mosso e
il blocco viene codificato come vettore nullo;
- altrimenti si cercano eventuali vettori
di moto applicando l'algoritmo di Block Matching;
Dato che per la determinazione dei B-Frames bisogna avere le informazioni del
frame predetto in indietro, occorre prima ottenere la codifica dei P-Frames
o poi si determina quella dei B-Frames.
Errore fra blocchi L'errore fra i blocchi è un ottimo rilevatore
di cambiamenti e quindi di eventuali movimenti nell'immagine.
L'errore fra due blocchi viene valutato sulla sola componente
di luminanza dei blocchi perchè porta maggior informazioni sul movimento che
la crominanza.
In questa fase come errore è stato usato il M.A.D.
(Mean Absolute Distorsion).
Finestra di ricerca Nel calcolo dei frames per poter determinare i
vettori di moto tramite l'algoritmo di Block Matching bisogna usare l'area
di ricerca. Su questa per ogni suo possible regione di 16 x 16 pixels si effettua
il calcolo dell'errore col blocco di riferimento del frame in considerazione.
Quindi nella scelta delle dimensioni della finestra di ricerca si scelgono
i vincoli per la determinazione dell'area di ricerca di ogni blocco.
Ogni blocco ha infatti la sua area di ricerca che sarà quadrata o meno in base
a quanto è centrato il blocco nel fotogramma coi vincoli di finestra di ricerca
scelta.
Per maggiori informazioni pratiche sulla scelta della finestra vedere le Istruzioni.
Determinazione I-Frame
La determinazione dell'I-Frame consiste nella sola codifica Intra di ogni suo
blocco.
E quindi visivamente è qui rappresentato come il fotogramma di riferimento.
In una sequenza di frame solitamente deve esserci un I-Frame ogni 50ms.
Determinazione P-Frame Per la determinazione di un P-Frame si è proceduto in questo modo:
-si estrae un blocco alla volta dal fotogramma passato da cui si predige e
lo si identifica con le sue coordinate (colonna,riga);
-per ogni blocco si si procede come segue:
-si determina la componente di luminanza del blocco;
-si considera il fotogramma del frame attuale e se ne estrae la componente
di luminanza dell'area di ricerca;
-calcolo Z=MAD fra il blocco del frame e quello del frame passato;
-se Z è sotto la soglia trasmetto il vettore nullo, altrimenti
-determino il migliore vettore di moto nella finestra col proprio Matching
Value (M) usando l'algoritmo di Block Matching;
-se il vettore trovato è nullo lo trasmetto, altrimenti
-in base alla caratteristica Mc/NoMc in figura scelgo se codificare
il blocco come Intra o col vettore di moto trovato;
Per i P-Frame quindi l'errore utilizzato come parametro soglia nell'algoritmo
di Block Matching è il M.A.D.
Determinazione B-Frame Per la determinazione di un P-Frame si è proceduto in questo modo:
1) Determinazione del miglior macroblocco A a moto compensato in avanti:
-si estrae un blocco alla volta dal fotogramma passato da cui si predige in avanti
e lo si identifica con le sue coordinate (colonna,riga);
-per ogni blocco si si procede come segue:
-si determina la componente di luminanza del blocco;
-si considera il fotogramma del frame attuale
e se ne estrae la componente di luminanza dell'area di ricerca;
-si calcola Z_A=MAD fra il blocco passato e il blocco attuale;
-si calcola M0_A=MSE fra il blocco passato e il blocco attuale;
-se Z_A è sotto la soglia si sceglie per il macroblocco A il vettore
nullo e M_A=M0_A, altrimenti
-si determina il migliore vettore di moto VetMotoA nella finestra col proprio
Matching Value (M_A) usando l'algoritmo di Block Matching;
2) Determinazione del miglior macroblocco B a moto compensato in indietro:
-se eseguono le stesse operazioni del punto 1) per il fotogramma del frame
futuro e ottengo Z2, M_B,VetMotoB;
3) Determinazione del macroblocco C interpolato:
-VetMotoC=( (vx_A+vx_B)/2, (vy_A+vy_B)/2 )
-si estrae il Matching value che si a nell'area di ricerca di A nel pixel
individuato da VetMotoC;
-si estrae il Matching value che si a nell'area di ricerca di B nel pixel individuato
da VetMotoC;
-si fa la media dei due e si ottiene il Matching value M_C del macroblocco interpolato
C
4) Determinazione miglior macroblocco fra i candidati A,B,C
-si sceglie il macroblocco
con minor MSE: M_Finale = min(M_A, M_B, M_C)
-se M_A=M_B=M_C -> scelgo C (indecisione)
5) Scelta del macroblocco da utilizzare
- si deve scegliere se trasmettere il macroblocco trovato o quello Intra
-se M_Finale<M0_A e M_Finale<M0_B -> Trasmetto Macroblocco trovato
-se M_Finale=M0_A e M_Finale=M0_B -> Trasmetto Macroblocco trovato (indecisione)
-se M_Finale>M0_A o M_Finale>M0_B -> Trasmetto Macroblocco Intra
Per i B-Frame quindi l'errore utilizzato come parametro soglia nell'algoritmo
di Block Matching è l'M.S.E.
Block Matching
Un semplice algoritmo per effettuare la stima del moto tra frame è la
ricerca esaustiva (Full Search). Esso consiste nel calcolare la distorsione
in tutte le possibili
posizioni che un macroblocco può assumere all'interno della propria
area di ricerca. Lo
spostamento tra una posizione e la successiva è di un pixel.
La
ricerca esaustiva è un algoritmo solitamente oneroso per quanto
riguarda la complessità
computazionale. Tuttavia nel nostro caso non è particolarmente oneroso dato
che i singoli fotogrammi hanno una bassa risoluzione spaziale (128*96).
La Full Search ha una grande importanza dal punto di vista teorico:
garantisce
infatti di trovare la migliore predizione possibile all'interno di una data
finestra di ricerca.
Tuttavia si è notato che spesso la presenza di zone molto dettagliate lontane
dal centro dell'area di ricerca può portare alla scelta di un vettore di moto
che non individua un movimento effettivamente presente.
Per ovviare a questo si presenta qui un'alternativa all'algoritmo di Full Search.
Il seguente algoritmo di ricerca si basa sull'algoritmo Full Search del
Test Model 5.
L'encoder MPEG del Test Model 5 utilizza per la motion estimation una Full Search
parzialmente ottimizzata: la ricerca viene fatta con una traiettoria a spirale
a partire da una
posizione centrale della finestra di ricerca come mostra la figura seguente.
I numeri indicano l'ordine con cui si
valuta la distorsione nelle diverse posizioni della finestra di ricerca; la
spirale prosegue sino
a coprire tutte le possibili posizioni all'interno della finestra.
Per ogni posizione viene determinato il Matching Value e se tale valore è minore
a al minor valore fino a quell'istante trovato, si aggiorna il valore del minimo
Matching Value con quello appena determinato e si aggiornano anche le coordinate
del vettore di moto corrispondente a tale valore minimo.
Se inoltre il valore del Matching Value scende sotto la soglia (impostata tramite
l'interfaccia grafica, MSE per B-Frames e MAD per P-Frames) l'algoritmo di
Block Matching si arresta. Si evita così di effettuare un numero
di iterazioni eccessivo.
Infatti sperimentalmente si trova che il moto dei macroblocchi è nella
maggior parte dei casi di poca entità o nullo: quindi sono molto probabili
dei vettori di moto di ampiezza piccola o nulla e ci si arresterà in un punto
della spirale verosimilmente prossimo del centro e rispecchiante l'effettivo
movimento del blocco.
Così si procede fino all'esaurimento della finestra di ricerca e alla
fine viene ritornato il Matching Value minimo e il vettore di moto che lo determina
e che è il vettore di moto cercato.
Decremento Matching Value
Per evitare la scelta di un vettore
di moto che non individua un movimento effettivamente presente, nell'algoritmo
viene qui proposta una variante all'algoritmo precedente.
Questa variante è attivabile tramite l'interfaccia dell'applet ("Decremento Matching
Value") ed è stata proposta perchè si ritiene che in taluni casi essa renda
più solido
il confronto fra Matching Value.
Nel confronto fra Matching Value attuale e Matching
Value minimo che si effettua ad ogni nuova posizione, il Matching Value minimo
viene decrementato di una quantità proporzionale al percorso già effettuato.
Al primo giro di spirale il Matching Value minimo normalizzato viene decrementato
di 1 per i P-Frame e di 1 x 10 per i B-Frames.
Al secondo giro di 3 per i P-Frame
e di 3 x 10 per i B-Frames.
All'n-esimo giro di k per i P-Frame
e di k x 10 per i B-Frames, dove k viene incrementato di 2 ad ogni giro.
In caso di sequenze di immagini i cui fotogrammi presentano dettagli prossimi
all'oggetto in movimento si nota sperimentalmente una determinazione migliore
dei vettori di moto che effettivamente rispecchiano movimenti presenti nella
sequenza di immagini.
Determinazione del Matching Value
Nel simulatore vengono usate come funzioni di errore per la determinazione
del Matching Value dei blocchi dei P-Frame e dei B-Frame rispettivamente
il MAD e l'MSE.
Quindi si noterà nel log del simulatore che il valore di M (Matching Value)
dei blocchi sarà di un ordine di grandezza più grande in caso di B-Frames.
Ricostruzione dei frames P e B
Nella ricostruzione dei frames si procede seguendo l'ordine indicato dalla
sequenza in uscita al codificatore.
Sia per i P-Frames che per i B-Frames si è proceduto in questo modo:
- si considerano inizialmente i blocchi codificati come intra e li si inserisce
nell'immagine ricostruita;
- si considerano poi i blocchi contenenti vettori di moto non
nulli nel frame codificato:
- si estrae il blocco corrispondente dal frame di riferimento (I codificato
interamente, P ricostruito);
- lo si inserisce nell'immagine in ricostruzione;
- si considerano poi i blocchi codificati come vettori nulli:
- si estrae il blocco corrispondente dal frame di riferimento (I codificato
interamente, P ricostruito);
- lo si inserisce
nell'immagine in ricostruzione;
