lunedì 4 febbraio 2008

Un algoritmo di compressione video specifico per video-chiamate

Febbraio 2008: un algoritmo di compressione video specifico per video-chiamate.

Una video telefonata è simile ad un video: possiamo pensarla infatti costituita come i video da una serie consecutiva di immagini.
Questo potrebbe far pensare che i sistemi di compressione dei video - grazie ai quali possiamo scaricare film da internet in tempi decorosi riducendo ad una piccola frazione la dimensione originale del file che lo contiene - possano esser usati anche per le video chiamate, superando così il problema di banda stretta.
Tuttavia, a differenza del video dove tutte le immagini consecutive che lo costituiscono sono a disposizione "subito" e possono esser "impacchettate" considerando solo le variazioni tra un fotogramma e quello successivo, nella video-chiamata abbiamo a disposizione solo l'immagine corrente e quelle già trasmesse: quindi non possiamo sfruttare lo stesso sistema.
Ma qualcosa possiamo comunque fare!
Infatti in una video-chiamata l'immagine attuale sarà sicuramente collegata a quella precedente con qualche relazione: ad esempio se statica potrebbe essere quasi identica, mentre se dinamica (qualcosa si muove in una direzione) è probabile che il movimento non si esaurisca e ... così possiamo memorizzare il movimento per intuire la prossima immagine senza trasmettere nulla!!!!


New York City, febbraio 2008, 53rd Str a fianco del NY Hilton.
Sono seduto in terza fila su un autobus Academy in attesa della partenza: una ragazza seduta davanti a me chiacchiera con il suo cellulare in video-chiamata con un amico.
Le immagini visualizzate dal piccolo monitor a tratti perdono definizione, forse a causa della riduzione temporanea della qualità di trasmissione o della scarsa ampiezza di banda utilizzata.

La cosa che mi ha colpito è che l'immagine sullo schermo era quasi sempre la stessa (il viso dell'amico con uno sfondo indistinto monocolore); le pochissime differenze tra immagini successive erano dovute esclusivamente ai piccoli movimenti dell'interlocutore: quindi tutto sommato il totale di informazione rilevante per la trasmissione era minimo, eppure bastava a mandare in crisi l'apparato ricevente che reagiva alla mancanza di informazione con una pixellatura in definizione minore.
Doveva per forza esistere un modo più "razionale" nella scelta delle informazioni da trasmettere che permettesse di effettuare video-chiamate più fluide possibili, anche con ampiezza di banda ridotta, scartando "un rumore di fondo" costoso in termini di utilizzo di banda.

Ho provato allora a ragionare su come funzioni un sistema di compressione video e come potrebbe esser migliorato per un caso particolare come le video-chiamate.

Gli algoritmi di compressione delle immagini statiche (tipo gif) si basano sull’assunto che in una foto la maggioranza dei punti adiacenti abbiano un valore (colore) molto simile, cosicchè non sia necessario memorizzare il valore di tutti i punti (nel caso di un’immagine vga 640x480 dovremmo memorizzare un vettore di 307.200 valori) ma solo le ricorsività (del tipo il valore 0 - cioè bianco – per i prox 36 punti, il valore 23 per i prox 3 punti ecc) limitando notevolmente le dimensioni.

Nel caso di algoritmi con perdita di informazione tipo jpg possiamo addirittura stabilire le ricorsività non del singolo valore ma di un limitato campo di valori intorno a quello dato (due azzurri con intensità QUASI eguale saranno memorizzati come se si trattasse dello stesso azzurro).

Una video-chiamata in fondo non è altro che una serie ordinata di immagini successive: inviarle una dopo l'altra - anche se le singole fotografie sono compresse - richiede un'enorme scambio di dati tra il terminale che trasmette e quello che riceve le informazioni.
La sfida è ridurre la mole di informazioni da scambiare senza perdere definizione e funzionalità.

Come per le immagini, esistono diversi metodi di compressione video (quali MP4, MOV ecc.) che riducono le dimensioni di un file contenente un film completo permettendoci di scaricarlo da internet in un tempo ragionevole.
Il principio è simile a quello usato per le immagini, dove i pixel consecutivi con valori ricorsivi vengono raggruppati per risparmiare l'uso della memoria (colore nero per i prossimi 50 pixels): oltre a considerare la sequenza spaziale del vettore consideriamo la sequenza temporale dei diversi vettori.
Cioè mentre un'immagine vga 640 x 480 pixels viene memorizzata come un vettore lungo 307.200 posizioni,
un video costituito da 100 immagini vga successive viene memorizzato con una matrice 307.200 x 10.
Verranno quindi rilevati non solo i pixel consecutivi con stesso valore all'interno del vettore (riducendo cosi' la lunghezza del vettore necessario a memorizzare l'intera sequenza dei valori), ma anche i pixel con lo stesso valore che stanno sulla stessa colonna della matrice (cioè i punti in una determinata posizione dello schermo che in tempi successivi non cambiano colore/valore).
Se ad esempio il 150^ pixel del vettore della prima immagine ha valore "0" ed il 150^ pixel delle successive 20 immagini ha sempre valore  "0" allora possiamo codificare solo la seguente informazione:
 valore "0" nella posizione 150 per 20 immagini consecutive
Purtroppo la condizione essenziale per poter utilizzare questi algoritmi è che prima di procedere alla compressione siamo in grado di completare la matrice dei vettori, cioè abbiamo a disposizione tutte le immagini che compongono il video!
Questo non è il nostro caso: il ragazzo che conversa con la ragazza seduta davanti a me sull'autobus tra un istante potrebbe girare la telecamera del suo cellulare, ma il cellulare della mia vicina ADESSO non lo sa!

Ho immaginato di utilizzare il seguente "trucco":
poiché come abbiamo notato le immagini in una video-chiamata hanno la caratteristica di ripetersi con monotonia (per un tempo abbastanza lungo ci sarà sempre il viso dell'interlocutore), definiamo l'immagine al tempo 1 identica a quella al tempo 0.
Trasmetteremo solo l'informazione sui punti che cambiano colore! (cioè le differenze tra le immagini consecutive)
In pratica ci sarà lo stesso software su entrambi i cellulari: se il trasmittente non rileva nell'immagine corrente alcuna differenza rispetto all'immagine precedente NON TRASMETTE nulla, ed il ricevente continua a riproporre sul display la stessa immagine fino a che non riceverà istruzioni diverse!
Questo metodo permette di risparmiare notevolmente la quantità di informazione che è necessario trasmettere, ma può esser ancora migliorato in tre modi:

1) accettiamo una piccola perdita di informazione come nel caso dei JPG: pixel vicini (nella serie spaziale - vettore - come nella serie temporale - colonne della matrice) con colori molto simili vengono memorizzati come se avessero lo stesso colore

2) piccoli spostamenti al di sotto di una soglia stabilita non vengono rilevati

3) teniamo conto della dinamica del soggetto ripreso: questo forse è un aspetto che nessuno aveva ancora considerato!!!

Se il ragazzo dell'esempio ha iniziato a girarsi verso destra, è altamente probabile che continui il movimento nelle immagini successive (o meglio la probabilità che nell'immagine successiva prosegua il movimento è maggiore rispetto alla probabilità che si fermi).
Inseriamo questa "istruzione" nel software dei terminali (come abbiamo fatto per il primo "trucco") e cosi' in caso di movimento del soggetto ripreso sarà il cellulare stesso a calcolare quale dovrebbe essere l'immagine successiva "spostando" sullo schermo parte dell'immagine originale.
L'informazione verrà trasmessa solo se il trasmittente rileva pixels con valori diversi da quelli che ci si aspetta in base all'algoritmo (ad esempio se nel girarsi il ragazzo rallenta o accelera la velocità del movimento, o cambia l'illuminazione o altri accidenti)




In conclusione si tratta di creare un algoritmo che su ciascun telefonino crei l’immagine successiva prima che questa sia ripresa; al momento dell’acquisizione dell’immagine da parte della sorgente video saranno memorizzati solo i dati relativi alle variazioni e di conseguenza l’informazione da trasmettere si riduce drasticamente di dimensione.
Naturalmente l’ipotesi è che le immagini in tempi successivi presentino una correlazione significativa, cioè ci sia alta probabilità che il valore di P t+1 (x,y) sia molto simile a P t (x,y), e che si tenga conto degli spostamenti di gruppi di pixels dovuti alla dinamica del soggetto ripreso.
Tale processo è funzionale se tale relazione valga per almeno il 51% dei punti di un’immagine.
Nel caso della trasmissione di immagini diverse (ad es una serie di quadri o fotografie) non è utile; tuttavia nella stragrande maggioranza dei video esiste una correlazione temporale tra il fotogramma successivo e quello precedente, pertanto la condizione è verificata.

Aggiornamento 4/1/18
Scopro ora che un sistema simile è alla base di un bug appena rilevato nei processori dei pc e telefoni. Si chiama  “Esecuzione speculativa”: ecco la descrizione dall’articolo su la stampa:
“....
Tutte le falle hanno a che fare con la cosiddetta «esecuzione speculativa», una funzionalità con cui i processori, per velocizzare le operazioni, cercano di intuire quale strada tra due possibili è più probabile che venga presa, iniziando quindi a eseguire i calcoli prima di ricevere le istruzioni. 
...”

Elenco progetti.

2020  La frequenza dei numeri palindromi nelle diverse basi (numerazione binaria, terziaria,.. decimale, esadecimale)                 Espa...