Progettazione, implementazione e sperimentazione di un ambiente per la video summarization

INTRODUZIONE 
 6
video nella sua interezza. Fornisce un'impressione sull'intero contenuto del video o contiene solo 
i segmenti video più interessanti.  
 Le key-frames sono molto adatte al content-based video browsing, in cui  possono essere 
utilizzate per guidare un utente nell’individuazione di segmenti video specifici. Inoltre, le key-
frames sono efficaci anche nel rappresentare il contenuto visivo di una sequenza video a scopi di 
recupero: gli indici video possono essere costruiti basandosi su caratteristiche visive e le richieste 
possono essere dirette a key-frame utilizzando le tecniche di recupero di immagine [24]. Allo 
stesso modo come nel caso di sequenze di anteprime, le key-frames possono essere estratte anche 
in due modi diversi, per catturare le scene più importanti di un video, o per riassumere l'intero 
video in termini del suo contenuto visivo. Come illustrato nella figura 1.1, un video può essere 
estratto o manualmente o in maniera automatica.  
Application
Video
Video abstraction
HumanMachine
Comparison
Manual
abstraction
Automated
abstraction
Similar representative quality
Cognitio Machine criteria
 
Figura 1.1 Processo Manuale vs Processo Automatizzato  
 Se le key-frames e i segmenti video sono estratti manualmente, essi soddisferanno la 
conoscenza umana.  
INTRODUZIONE 
 7
 La capacità di ridurre il coinvolgimento umano nel processo di video summarization 
sviluppando strumenti di analisi e di trattamento video automatizzati è molto interessante. Si è di 
fronte ad una produzione di video in continua crescita e il numero sempre crescente dei servizi 
offerti ai clienti richiedono una manodopera enorme nella preparazione dei video per la loro 
distribuzione e collocazione sul mercato. I clienti spesso potrebbero desiderare di guardare 
piccoli clip del video per rendersi conto delle informazioni in esso contenute.  
 D'altra parte, se la video summarization deve essere eseguita dall’utente, per esempio, nei 
sistemi di memorizzazione contenenti data-processing [18], un'automazione completa di tali 
sistemi risulta essere cruciale. 
 Mentre l’esigenza di automatizzare la procedura di video summarization è forte, le 
possibilità per la sua realizzazione pratica sono molto limitate. La prima limitazione è relativa al 
fatto che è estremamente difficile sviluppare un sistema, che è capace di catturare 
automaticamente le caratteristiche principali di un video. Questo è principalmente dovuto al fatto 
che il processo di individuazione dei segmenti video da includere è molto soggettivo. Inoltre non 
si ha la possibilità di tracciare una mappa efficiente della conoscenza umana nel processo 
automatico, cosicché il processo manuale e il processo di video summarization automatizzato 
genererebbero risultati simili ma non uguali.  
 Oggetto di questo lavoro di tesi è la realizzazione di un ambiente interattivo per la 
realizzazione di sommari video. Particolare attenzione è stata dedicata all’implementazione di un 
algoritmo di ottimizzazione che permette di ottenere dei sommari video caratterizzati da 
determinate proprietà. Il sommario video prodotto è formato da un insieme di key-frames. Il 
INTRODUZIONE 
 8
ruolo di soggettività nel processo di video summarization è ridotto significativamente, e ciò può 
essere spiegato dal fatto che idealmente un sommario video contiene tutti gli elementi relativi del 
contenuto video (facce, oggetti, paesaggi, situazioni, ecc) e non una scelta soggettiva di questi 
elementi. Per la seconda limitazione, il sistema implementato non tenta di fornire un sommario 
che contenga esattamente gli stessi frame o segmenti ottenuti dal processo manuale. 
 Nell’organizzazione del lavoro proposto si individuano quattro sezioni principali. Nel 
capitolo 2 viene illustrato lo stato dell’arte dei sistemi di video summarization proponendo le 
varie tecniche utilizzate. Nel capitolo 3 verranno descritti i vari componenti dell'architettura e il 
modello formale per la video summarization in cui verrà introdotto il concetto di  “sommario 
ottimale” basato sulle proprietà di continuità, priorità e ripetitività. Successivamente nel capitolo 
4 verrà descritto l’algoritmo per la video summarization implementato. Nel capitolo 5 lo studio 
prosegue poi attraverso una fase di sperimentazione della soluzione proposta in modo da provare 
la qualità dei sommari prodotti. Infine verranno illustrate le possibili prospettive future. 
 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 9
CAPITOLO 2 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
2.1 STATO DELL’ARTE DEI SOMMARI VIDEO 
Data la veloce crescita della tecnologia audio-video, l’aumento della quantità di 
contenuto multimediale disponibile in rete è enorme. Gli utenti affrontano una nuova sfida:  
Come esaminare velocemente grandi quantità di contenuto multimediale 
La tecnica che permetterebbe una rapida panoramica del contenuto di oggetti 
multimediali è la sommarizzazione; cioè, una versione ridotta dell’originale ottenuta scegliendo 
in maniera ottimale i segmenti più significativi.  
Il contenuto multimediale sta diventando molto diffuso sia su reti Intranet aziendali che 
sulla rete Internet. Ad esempio, molte società fanno uso di seminari audio e video interni 
disponibili on line. Allo stesso modo, molte istituzioni accademiche rendono on line i video e i 
seminari delle varie  conferenze.  
 L'estrazione automatica di key-frames è stata studiata dai molti ricercatori [23-41]. Un 
primo tentativo fu di scegliere come key-frame il frame che appare dopo ciascuno shot rilevato 
[32]. Tuttavia, mentre ciò era sufficiente per shots stazionari, un key-frame non fornisce una 
rappresentazione accettabile del contenuto visivo nelle sequenze dinamiche. Quindi erano 
necessari dei metodi per estrarre key-frame da lunghe sequenza video. Uno dei primi approcci di 
estrazione sviluppato è presentato in [37], con tutti i dettagli in [40]. Le key-frames vengono 
estratte in modo consecutivo per ogni shot separatamente. La prima frame di uno shot è sempre 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 10
considerata come key-frame. Quindi viene applicato lo stesso metodo per la rilevazione degli 
estremi di uno shot. La differenza zFk
last(,) viene calcolata tra la frame corrente k di una 
sequenza e l'ultima key-frame estratta F
last  utilizzando gli istogrammi di colore. Se questa 
differenza supera una certa soglia T, la frame corrente è scelta come nuova key-frame. La 
procedura di estrazione è la seguente: 
 
StepF
StepkSifzFkTFk
last
lastlast
11
22
:
:[,](,)
=
∀∈>⇒=
                                                                 
dove S è il numero di frame all'interno di uno shot. La procedura di estrazione (1) è poi adattata 
utilizzando le informazioni sul movimento derivanti dalle operazioni della videocamera secondo 
un certo insieme di regole. Per una inquadratura con zoom, devono essere estratte almeno due 
frame, una all'inizio ed una alla fine dello zoom. La prima rappresenta una vista globale mentre 
l'altra una vista più dettagliata della scena. Nei casi di panoramica, il numero di frames da 
scegliere dipenderà dalla frequenza di variazione del contenuto visivo: idealmente, il contenuto 
visivo coperto da ogni key-frame dovrebbe avere una piccola sovrapposizione, oppure ciascuna 
frame dovrebbe coprire un diverso oggetto della scena. Di solito le frames che hanno meno del 
30% di sovrapposizione nel loro contenuto visivo sono scelte come key-frames. Un metodo di 
estrazione delle key-frames simile alla procedura (1) può essere trovato anche in [36], anche se 
non c’è l’utilizzo delle informazioni di movimento.  
 Nell'approccio presentato in [29], si calcola prima il valore della discontinuità tra la frame 
corrente k e le N frames precedenti. Questo viene fatto confrontando l'istogramma di colore della 
frame k con l'istogramma di colore medio delle N frames precedenti e cioè il valore:  
(1) 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 11
()zkkkNHi
N
Hike je
jk
kN
eYUVjk
kN
,{,..,}()()
,,
−−=−
=−
−
==−
−
∑∑∑1 1
11
                                                                
 Se il valore della discontinuità (2) supera la soglia T, la frame corrente k è considerata la 
nuova key-frame F
last , cioè: 
( )ifzkkkNTFk
last,{,..,}−−>⇒=1                                                                       
 Un possibile problema con i due metodi di estrazione precedenti è che la prima frame di 
uno shot è sempre scelta come key-frame, come pure quelle frame che si trovano in segmenti con 
un contenuto visivo variabile. Come discusso in [28], scegliendo una frame posta all'inizio o alla 
fine di uno shot, è  probabile che quella frame sia parte di un effetto di dissolvenza ai limiti dello 
shot, e ciò riduce fortemente la sua qualità rappresentativa. Lo stesso può essere detto per 
strutture che appartengono a segmenti di shot in cui vi siano movimenti della videocamera o 
oggetti zoomati. 
Una soluzione a questo problema può essere trovata in [26], dove prima si rappresenta 
una sequenza video come una curva in uno spazio high-dimensional e poi si semplifica la curva 
utilizzando l'algoritmo multidimensional curve splitting. Il risultato è, fondamentalmente, una 
curva linearizzata, caratterizzata da punti "significativi" collegati da rette. Un insieme di key-
frame di una sequenza è ottenuto infine raggruppando frames trovate nei punti significativi. Con 
una condizione di splitting che controlla la dimensionalità  del segmento, la curva può essere 
semplificata ricorsivamente a vari livelli di dettaglio, cioè con  varie densità dei punti 
significativi. Il livello di dettaglio finale dipende dalla soglia specificata, che valuta la distanza 
(2) 
(3) 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 12
fra la curva e la sua approssimazione lineare. Il problema principale di questo approccio è la 
difficoltà a valutare l'applicabilità delle key-frames ottenute, poiché non sono stati fatti studi 
completi per provare che la key-frame estratta dai punti significativi copre tutti gli eventi più 
importanti di un video. 
Un tipo diverso di approccio per l’estrazione di key-frame è proposto in [41], dove 
tutte le frame in uno shot video sono classificate come M gruppi, e il numero finale di gruppi è 
determinato da una soglia T. Una nuova frame è assegnata a un gruppo esistente, se è abbastanza 
simile alla frame centrale di quel gruppo. La somiglianza tra la frame corrente k e quella centrale 
di un gruppo è calcolata come l'intersezione degli istogrammi di colore a due dimensioni HS 
nello spazio di colore HSV (H colore, S saturazione, V valore). Se la somiglianza calcolata è 
inferiore alla soglia specificata T, un nuovo gruppo è formato intorno alla struttura corrente k. 
Inoltre, solo quei gruppi che sono più grandi della dimensione del gruppo medio in uno shot sono 
considerati come key-group e la frame più vicina a quella centrale di un key-group viene 
considerata come key-frame. 
 L'estrazione di key-frames in tutti gli approcci presentati è basata su una specifica di 
soglia. Le soglie utilizzate in [26], [37] e [41] sono euristiche, mentre gli algoritmi presentati in 
[29] lavorano con una soglia ottenuta utilizzando la tecnica di Otsu [42]. Adattando la soglia, si 
può regolare il numero totale di key-frame estratte. Tuttavia tale regolazione può essere eseguita 
solo senso globale, e ciò significa che più piccola sarà la soglia e maggiore sarà il numero 
frames, e viceversa. Il controllo esatto o almeno approssimato del numero totale di key-frame 
estratte non è possibile. Per prima cosa è difficile collegare il valore di soglia al numero di key-
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 13
frames estratte. In secondo luogo, lo stesso valore di soglia può portare ad un numero diverso di 
key-frames estratte per varie sequenze.  
 Una soluzione a questo problema è di rendere la soglia direttamente relativa alle 
prestazioni dell'estrazione. Un esempio è la specifica della soglia nella forma del massimo 
numero tollerabile di key-frames per una data sequenza. Un approccio che utilizza questo tipo di 
soglie è quello presentato in [33], in cui si devono specificare due soglie: una soglia r, che 
controlla quali frames saranno incluse nell'insieme e una soglia N data dal massimo numero 
tollerabile di key-frames in una sequenza. L'estrazione di key-frames è eseguita poi per mezzo di 
una procedura iterativa partitional-clustering. Nel primo passo di iterazione, una sequenza video 
è divisa in gruppi consecutivi della stessa lunghezza L. La differenza è calcolata tra la prima e 
l'ultima frame di ogni gruppo. Se la differenza supera la soglia r, tutte le frames di un gruppo 
sono considerate key-frames, altrimenti solo la prima e l'ultima frame del gruppo sono 
considerate come tali. Se il numero totale di frames estratte è minore o uguale del massimo 
numero tollerabile N, allora la procedura di estrazione si ferma, altrimenti una nuova sequenza 
viene costruita con tutte le frames estratte e viene ripetuta la stessa procedura di estrazione. Lo 
svantaggio più grande di questo metodo è la difficoltà della specifica della soglia r, poiché non è 
possibile collegare la qualità dell'insieme di key-frames ottenuto a qualsiasi valore specifico di r.  
 Un metodo alternativo e migliore viene proposto in [30]. Tale metodo non richiede 
nessun altro valore di soglia se non il massimo numero di key-frames permesse in un video. Ci 
sono due passi in questo approccio. Per prima cosa l'assegnazione di key-frame per ogni shot è 
effettuata basandosi sulla variazione del contenuto di uno shot e su quello dell'intera sequenza. 
La variazione del contenuto di una sequenza è definita come la somma di tutte le differenze 
CICLO DI SVILUPPO DI UN SISTEMA DI VIDEO SUMMARIZATION 
 14
frame-to-frame misurate nell'intera sequenza. L'assegnazione di key-frame è fatta in modo che la 
somma di tutte le key-frames assegnate lungo la sequenza è vicina al massimo numero N di key-
frames permesse per l'intera sequenza. Il numero N può essere adattato se si conosce a priori il 
tipo di problema da trattare. Il passo di assegnazione è seguito da una procedura threshold-free 
per distribuire in modo ottimale il numero assegnato di key-frames in ogni shot. La distribuzione 
ottimale di key-frames in ogni shot è eseguita nel secondo passo utilizzando un algoritmo 
numerico per ottimizzare la rappresentazione della distribuzione. Tuttavia, predefinire il numero 
assoluto di key-frames senza conoscere il contenuto del video può essere problematico in alcuni 
casi, ad esempio quando si assegnano due key-frames per una sequenza di mezzobusti di 30 
minuti, in cui alcune di loro possono essere considerate ridondanti. Inoltre, assegnando lo stesso 
numero di key-frames, per esempio, a due sequenze video della stessa lunghezza, non si 
garantisce lo stesso livello di astrazione visiva poiché il contenuto delle due sequenze può avere 
vari livelli di astrazione, e/o vari livelli di attività. 
 Se il numero totale di key-frames estratte è regolato da una soglia, le qualità dell'insieme 
risultante di key-frames e dell'insieme ottenuto per la stessa sequenza su conoscenza umana, non 
sono necessariamente paragonabili. Per esempio, se la soglia è troppo bassa, sono estratte troppe 
key-frames caratterizzate da un'alta ridondanza del loro contenuto visivo. Per un'alta soglia, 
l'insieme risultante di key-frames potrebbe essere troppo rado. Inoltre se la frequenza di 
cambiamento visual-content permette l’esistenza di un solo insieme ottimale di key-frames, 
trovare il valore della soglia che fornisce questo insieme di key-frames è un'attività 
estremamente complessa.