CPR Model for Summarazing Video
M. Fayzullin, V.S. Subrahmanian
University of Maryland
{fms,vs} @cs.umd.edu
A. Picariello
Università di Napoli
[email protected]
Gattamorta Mirko
Meneghello Andrea
Vergari Gino
M.L. Sapino
Università di Torino
[email protected]
Premessa (1)

Creare un sommario di un video


Un sommario video è una rappresentazione compatta di
una sequenza video ed è utile per diverse applicazioni
video. Per esempio, fornisce una rapida panoramica del
contenuto del video, permettendo un accesso veloce ai vari
shots.
Ci sono due forme di sommario video:


1. una sequenza di anteprime, concatenazione di un
numero limitato di segmenti video
2. un insieme di key-frames, una raccolta di frames scelti
adeguatamente.
Premessa (2)

Cosa abbiamo già a disposizione:




Video databases che supportano API video
Tecniche di sommario basate sul key-frame
Selezione a manuale dei frames interessanti
Lo stato dell’arte

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
Premessa (3)

Costruire un indice:
1. Che usi delle regole per specificare quali sono gli
oggetti, eventi o frames “interessanti” (F.I.) per quel
contesto.
2. Possieda una funzione obbiettivo che dati i F.I.
combini assieme questi tre parametri:



Continuity
Priority
Repetition
Sommario
1. Introduzione
2. Modello formale
3. Algoritmi
1. Benchmark
2. Conclusioni
CAPITOLO 1
Introduzione
Introduzione

Reperire le parti più interessanti di un video

Es: partita di calcio


Goal, falli gravi, azioni spettacolari…
Non considerare azioni ripetitive, passaggi,
sostituzioni…
Scenari di applicazione (1)

A cosa serve un CPR model per sintetizzare
un video?





Per automatizzare il processo di sintesi
Permette alle aziende di “contabilizzare” e vendere clip di video.
Gli utenti possono selezionare le parti che ritengono più
interessanti e acquistare in seguito l’intero video
Molte società fanno uso di seminari audio e video interni
disponibili on line.
Device requirement



Cellulari, PDA sia per rete GSM che UMTS che supportino la
ricezione di video o brevi clip.
Decoder digitali
Personal Computer connessi a internet
Scenari di applicazione (2)
CPR Model
Sommario
Goal
Azioni
Accounting
Video store
Video: cosa analizzare (1)

Video:



Es: 15 fps, 1 hour = 60 x 60 x15 = 54.000 frames
Impossibile confrontarli tutti per decidere i F.I.
Utilizziamo il keyframe: Significa letteralmente fotogramma chiave e indica il
fotogramma di riferimento nella codifica di una clip. In sostanza un key frame non contiene
alcuna informazione sui frames adiacenti.Molti compressori usano il keyframe per
risparmiare spazio nella compressione, che in questo modo deve tenere conto solo delle
differenze tra due keyframes.
Key
frame
Video: cosa analizzare (2)

Basta il keyframe ?

Il keyframe ci dice solo i frame da
considerare, quelli che contengono
più informazione. Ma noi abbiamo
anche bisogno di regole per
determinare quelli interessanti (F.I.)
Bisogna che selezioniamo solo alcune scene, le più significative per il
contesto che si sta analizzando (Es: i goal per una partita di calcio)
Es. Se abbiamo in media un keyframe ogni 300 frame con l’esempio precedente 54000/300=180
che implica che il numero di scene da confrontare è comunque elevato.
Vedremo nel capitolo 2 come queste regole si possano esprimere usando un linguaggio logico.
La funzione obbiettivo

La funzione obbiettivo, che discuteremo nel
capitolo 2, servirà:
1.
una volta che abbiamo raccolto tutte le scene che
rispettano le nostre regole,
2.
per decidere quali inserire effettivamente nel sommario
Proprietà e criteri di selezione (1)

Continuity
(del sommario): Il sommario deve essere continuo e non
presentare “salti”.

Es rigore: oltre al goal deve esserci frame dell’istante prima del tiro e quello
immediatamente successivo.
Rincorsa
Tiro
Parata
Goal
Festeggiamenti
Ogni frames qui sta ad indicare un istante del video
Proprietà e criteri di selezione (2)

Priority
(dei frames): per ogni applicazione di sommario
certi oggetti o eventi sono più importanti di altri

Es. di contesto: video di calcio

Es. di evento: il goal è più importante di un semplice passaggio a centro campo

Es. di oggetto: Il portiere se ha di fronte l’attaccante che si appresta a tirare è più
importante del portiere che rimette da fondo campo.
Evento più
importante
Proprietà e criteri di selezione (3)

Repetitions
(del sommario): anche se un evento è prioritario ma
4 rigori calciati da
ricorre molte volte nel video, questo diventa meno prioritario nel sommario
altrettanti giocatori
finale

Es: i calci di rigore, l’evento è ripetuto molte volte quindi ne utilizzo alcuni per
rappresentare il sommario e gli altri perdono di priorità
Scelgo ad esempio il primo
come più prioritario
Riassumendo
Selezioniamo da un video, in modo totalmente
automatico tutti i keyframes.
2. Eseguiamo un’analisi con regole per determinare i
frames interessanti per il contesto.
3. Tramite una funzione obbiettivo decidiamo
quali inserire nel sommario finale.
1.
CAPITOLO 2
Modello Formale
Modellazione del sommario
v=
1
2
1
k-summary
Goal 21’ del 1°T
Rigore 8’ del 2°T
…
Assist 44’ del 2°T
3
len
...
...
…
K
Sommario S al più di k frame o di
blocchi di frame continui:
S  {1, ..., len } con S  k
v
S deve contenere solo frame “interessanti”:
f ∈S ⇔insum(f ) = true
Ma quando un frame è interessante?
 Quando contiene oggetti o azioni che ci interessano!
Selezione dei frame (1)
I frame sono analizzati e individuati per contenuti da API del DB multimediale
chiamate video-call:
findframe(v,X) individua i frame che contengo l’azione o l’oggetto X
findobj(v,f)
individua gli oggetti contenuti nel frame f
findact(v,f)
individua le azioni contenute nel frame f



findframe(v,BALL)
V=
findobj(v,f’)
...
findact(v,f’’)
...
Selezione dei frame (2)
Per istanziare frame, oggetti ed azioni “interessanti” usiamo predicati che
associano ad una variabile X l’output della video-call invocata
X ∈ findframe(v," Rivaldo")
X=
I predicati a loro volta possono essere uniti in and logico formando vincoli
più stringenti sulle variabili libere:
X  findact v,f 
 X  findact v,f '
X = “celebrazione”
Si associa alla variabile una o più azioni (e oggetti) presenti in entrambi i frame
Video Condition (Vc)
Il motore che mette in esecuzione i predicati sono le regole di sommario (V )
insum(X) : predicato unario (detto anche testa della regola) che restituisce
true o false se si è o non si è associato ad X uno o più frame
corpo della regola
Vc
insum X   X  findframe v,"esplulsione"
frame X da restituire
funzione video-call che cerca una
o più espulsioni nel video v
k-summary
insum X  " goal" findact v , X 
" capitano " findobj v , X 
insumY  " celebrazio ne" findact v , Y 
insum Z  " passaggio a" findact v , Z 
" Totti " findobj v , Z 
" Totti"  findobj v , X 
 insum X 
Frame contenente un’azione di
goal in cui partecipa il capitano
Frame con celebrazione del goal
Frame contenente un passaggio
in cui è coinvolto il giocatore Totti
solo se quest’ultimo è presente in
un frame già considerato
interessante [ insum(X) ]
I frame restituiti sono inseriti nell’insieme dei frame reputati interessanti: Der (V ).
X
{f1,f2,f3,f4,f7}
Y
{f1,f5,f6,f9}
Z
{f1,f2}
La scelta dei migliori frame costituirà il k-summary
S  DerV
Es:S = {f1,f6,f9}
Continuità


Rendere più attrattivo il sommario
Aumentare l’informazione comunicata
VS

Introduciamo tra le regole di sommario anche la seguente
insumY   near  X ,Y , i   insum X 
Si restituiscono tutti i F.I. Y
nell’intervallo [X-i,X+i] dove X è
il frame centrale dell’azione
Priorità & non-Ripetizione

Migliorare la qualità del sommario
Si attribuiscono ai frames canditati per il k-summary delle priorità singole
e di gruppo (frame set)
pri( f1 ) = 0.6
pri( {f1,f2} ) = score[0,1]
Usando la funzione pri possiamo imporre score bassi per frame set contenenti
frames simili.
Similarità valutata attraverso funzioni di distanza (color histograms)
applicate ai frames o al loro contenuto: oggetti ed azioni.
f1
f2
Fare vedere nel sommario più azioni di presunto fallo in area è poco interessante
CAPITOLO 3
Algoritmi
CPR ottimo - sommario ottimale (1)
1. Dato il dominio delle regole V otteniamo N frames interessanti
che vanno a formare l’insieme Der(V)
Der V   N
2. Il sommario ottimo S  DerV  deve avere al massimo k
frames con k ≤ N
3. Quindi calcolo tutti i possibili sommari di lunghezza k partendo
dall’insieme Der(V)
N!
k! N  k !
possibili sommari
4. Tramite la funzione eval() calcoliamo il migliore
…
CPR ottimo - sommario ottimale (2)
…
5.
6.
Risultato migliore in termini di Continuità, Priorità, non-Ripetizione
Pesi α, β, γ sono decisi dall’utente in base alle sue esigenze
= α·C(S) + β·P(S) – γ·R(S)
scegliendo il k-summary S tale che eval(S) > eval(S’ )  S'  Der V 
calcoliamo eval(S)
Riconducibile alla computazione di un knapsack problem
Come ottenere sommari video

Permettono di dare un peso alle tre specifiche del
modello CPR (continuità, priorità, ripetitività )
• SEA (Summary Extension Algorithm)
• CPR dynamic
• CPR genetic programming
Definiamo il dominio delle regole V
Per ogni regola Vc  peso Wi
normalizzato tra [0, 1]
Corpo della regola
0.7
Insum(Y)




Calcoliamo Pi nel caso
della regola …
Frame Coverage Pair
(FCP) è (f,p)
0.3
Insum(X)
Frame i
Pi
2/3
(0.67)
Sommario Video
Indica il grado di soddisfazione in
forma normalizzata [0,1] della video
condizione (Vc)
FCP
FCP
FCP
V
Sommario video - esempio
In questo caso avremo il
 ValidSummaryExtension
Regola 1
0.3
0.7
1 Avendo calcolato per ogni
FCP il valore del grado di
soddisfacibilità per la regola i
Regola 2
0.3
2 Viene scelto FCP che massimizza le
condizioni fra tutti gli FCP della regola i e
viene moltiplicato per il peso della regola
0.7
0.7
1.0
0.3
3 Tra tutti i FCP max delle rispettive regole
vengono presi quello che ha il valore
massimo
0.3
Si osservi che il procedimento deve
avvenire iterativamente per tutte le
regole in V e per tutti i frames che
soddisfano V anche parzialmente
0.3
CPR Dynamic - (Alcuni cenni)
Procedure CPRdyn(V,k)
• Basato sulla programmazione dinamica metodo iterativo
Sia
Vcurrent variabile che descrive la migliore soluzione fino al corrente istante
V
è un sommario video con specifico contenuto
k
è la lunghezza del sommario desiderato
1. Verifica ad ogni passo di iterazione se rimpiazzare un frame
contenuto in Vcurrent con un nuovo frame considerandolo un
buon sommario
•
Un sommario è considerato solo se ha esattamente k frame
•
La funzione di valutazione dei frames Eval() è monotona
CPR Genetic - (Alcuni cenni)
Procedure CPRGen(V,k,N, α)
• Usa un approccio basato sulla programmazione genetica nel
calcolare un Sommario video
1. Operatore EVAL() valuta la bontà del membro della popolazione(insieme dei frame)
2. Operatore MUTATION() : elimina i membri dalla popolazione del punto 1
3.
 1 presenza del frame i nel sommario 

0
assenza


 frame fi  var binaria 
1. Crea un sommario con numero casuali di frame e imposta il
valore secondo la funzione Eval()
2. Applico operatore Mutation() ad un numero casuale di
membri della popolazione del sommario.
3. Condizione di stop quando la variazione della funzione
eval() della popolazione ≤ valore di soglia α stabilito
4. Itero il procedimento per N volte
Analisi Complessità
Glossario
N
numero iterazioni
K
lunghezza sommario
In ultimo
CPR ottimo ha
complessità Exp
in Lenv
Lenv lunghezza video
a
numero max di letterali (atomi)
appartenenti al dominio delle regole V
Spazio
Tempo
CPR Dynamic
O (num frame)
O ( exp(k) )
CPR Genetic
O ((Len v)² / K)
O ((Len v)² / K²) * N²)
SEA
O (a)
Len v *card(V)*card(K)ª
Benchmark (1)

Per valutare la bontà di ogni algoritmo si sono
utilizzati:

50 video di calcio



Hardware:



1 Pentium 3 @ 800 MHz
128 MB di SDRAM
Risultato:



@ 30fps 640x480,
Durata 90 ÷ 120 minuti (circa 16200 frames)
40 blocchi per ogni video
Si sono creati sommari di 2,4,6 minuti
Valutazione:

200 studenti (tutti tifosi)
Benchmark (2)
Quale algoritmo dà i risultati migliori ?
User preference (%)
Summary Quality Comparison
80
70
60
50
40
30
20
10
0
Sea
CPRgen
CPRdyn
2
4
Summary duration (minutes)
6
Benchmark (3)
Quanto impiegano gli algoritmi a creare il sommario ?
Time(msec)
Algorithm's Performance
2450
2400
2350
2300
2250
2200
2150
2100
2050
SEA
CPRgen
CPRdyn
4
11
16
24
28
37
42
49
Number of frames
58
64
67
75
Conclusioni


Come si può vedere dai grafici il SEA è l’algoritmo che
offre i migliori risultati sia in termini di qualità del
sommario prodotto sia in termini di tempo impiegato.
Il CPR è il primo modello per creare sommari di video
basato sulla semantica.
Bibliografia







[1] The CPR Model For Summarizing Video: M. Fayzullin,
V.S.Subrahmanian,A. Picariello, M.L. Sapino
[2] Searching Multimedia Databases Searching: P.Ciaccia
[3] Image Databases: P.Ciaccia
[4] Multimedia Databases Indexing: P.Ciaccia
[5] Progettazione, implementazione e sperimentazione di un ambiente
per la video summarization:D'Onofrio Salvatore
[6] Action description (and eventual recognition):
http://www.cfar.umd.edu/
[7] The First ACM International Workshop on Multimedia Databases
(MMDB 2003) at ACM CIKM 2003: Shu-Ching Chen, Mei-Ling Shyu
THE END