La grande quantità di informazione è sicuramente la proprietà più evidente di un flusso dati di tipologia video.
Il Video è ricco di informazioni in quanto è spesso corredato di sottotitoli, colonna sonora, frame, metadati.
Le principali metodologie impiegate sono basate su:
Shot: gruppo di frame contigui che hanno uno o più delle seguenti caratteristiche:
Esempi:
In molte applicazioni è necessario non soltanto individuare quale video contiene una determinata informazione, ma anche quale parte del video la contiene.
Scorrere un video alla ricerca di una particolare sequenza è una operazione che richiede molto tempo: sono necessarie tecniche di segmentazione dei video per l’identificazione automatica degli shot.
I frame consecutivi che sono ubicati prima e dopo un “cambio di camera” generalmente mostrano un elevato cambiamento quantitativo nel loro contenuto.
Per individuare gli shot occorre definire una misura quantitativa che catturi la differenza tra una coppia di frame: data una certa soglia, se la differenza tra un frame e il successivo supera tale valore, il punto viene considerato una interruzione tra shot diversi.
Per verificare eventuali passaggi tra shot occorre misurare la differenza tra 2 frame consecutivi.
Metodo 1: si calcola la somma, pixel per pixel, delle differenze tra i 2 frame consecutivi. Questo metodo non garantisce buoni risultati poiché la presenza di oggetti in movimento causa grandi differenze anche all’interno della stessa scena e porta a ottenere molte false interruzioni di shot.
Metodo 2: si calcola la differenza tra gli istogrammi di colore dei 2 frame consecutivi. Il metodo è basato sul fatto che il movimento di oggetti all’interno della stessa scena causa piccole variazioni nell’istogramma dell’immagine.
Se le metodologie adottate “scoprono” grosse variazioni allora probabilmente si tratta di un cambio di scena. In particolare definiamo la distanza tra frame:
In cui Hi(j) = valore del j-esimo bin dell’istogramma dell’i-esimo frame. Se SDi supera una soglia prefissata allora assumiamo che si sia verificato un cambio di shot.
Ovviamente, la scelta della soglia per l’individuazione degli shot è molto critica per l’ottenimento di risultati corretti: deve tollerare le variazioni presenti normalmente tra singoli frame ma individuare tutti i cambi di shot. Un buon compromesso consiste nel considerare un valore di soglia leggermente più grande della media di tutte le differenze tra un frame ed il successivo.
Quando tra una scena e l’altra di un video sono utilizzate le transizioni (dissolvenza incrociata, fade-in, fade-out, ecc…) la differenza frame per frame è sempre molto bassa; sarebbe necessario introdurre una soglia molto più bassa ma con il rischio di trovare molti cambiamenti di shot che non corrispondono a effettivi cambi di scena.
Un semplice metodo per la verifica del cambio SHOT consiste nell’introdurre due soglie diverse: una più alta Tb utilizzata per determinare i cambi di camera e una più bassa Ts per determinare i frame nei quali avviene una transizione graduale.
Confrontando un frame con il successivo, se la differenza è maggiore di Tb si introduce un cambio di shot, se la differenza è minore di Tb ma superiore a Ts il frame è dichiarato come un potenziale frame di transizione.
Fino a quando si hanno potenziali frame di transizione consecutivi, la loro distanza viene sommata e quando raggiunge la soglia Tb si genera un cambio di shot (se la sequenza di potenziali frame di transizione è interrotta da una differenza inferiore alla soglia Ts la somma riparte da zero).
In generale il compito di individuazione degli shot è molto più complesso in presenza di transizioni e le percentuali di riconoscimento corretto degli shot sono basse.
Dopo aver individuato gli shot, occorre rappresentarli ed indicizzarli in modo da essere efficacemente gestiti dalla fase di ricerca.
Per ogni shot si determinano uno o più frame rappresentativi (Representative Frame r-frame) che vengono usati per l’indicizzazione e la ricerca con tecniche simili a quelle viste per le immagini statiche (colore, forma o texture).
Quanti r-frame occorre utilizzare per ogni shot?
1 r-frame per ogni shot.
Svantaggi:
N r-frame al secondo.
Svantaggi:
Suddivisione in sotto-shot: mediante le stesse tecniche utilizzate per la determinazione degli shot, si introduce un nuovo livello e si genera un r-frame per ogni sotto-shot.
Se il video è abbastanza statico, ognuno dei frame di uno shot può essere scelto come r-frame.
Se ci sono movimenti di oggetti e/o della camera all’interno dello shot, la scelta dell’r-frame riveste una importanza fondamentale per ottenere buone performance di ricerca.
Metodi possibili:
Le tecniche basate sulle informazioni di movimento memorizzano, per ogni frame , le informazioni derivanti dai “motion vectors“:
Ogni shot viene indicizzato attraverso i motion vectors che lo caratterizzano.
Le tecniche di riconoscimento sono di difficile applicazione nel caso di immagini statiche.
Contrariamente a quanto può essere intuitivamente pensato, nel caso di dati video tali tecniche funzionano meglio in quanto il movimento degli oggetti tra frame successivi fornisce informazioni utili per segmentare il video e riconoscerne i singoli elementi.
Gli oggetti riconosciuti sono quindi utilizzati per l’indicizzazione degli shot e la successiva ricerca.
I Video sono assai ricchi dal punto di vista informativo e contengono una dimensione temporale.
Sono richiesti metodi di rappresentazione compatta.
Classificazione dei Video per Argomenti
La Classificazione dei video per argomenti consente una ricerca con maggiore focalizzazione sugli interessi informativi dell’utente (riduce lo spazio di ricerca)
Può essere utilizzata sia a livello di intero video che dei suoi singoli shot (e quindi realizzare una rappresentazione compatta del video stesso)
MICON (Motion Icon): rappresentazioni compatta degli shot (l’analogo delle miniature per immagini fisse).
Una MICON è caratterizzata da tre dimensioni:
Una MICON può fornire informazioni aggiuntive tagliando il “cubo” orizzontalmente o verticalmente.
Il browser video gerarchico è uno strumento che consente di ispezionare in maniera gerarchica i vari elementi di un video.
L’utente si muove sulla gerarchia alla ricerca delle informazioni che gli interessano.
Storyboard: collezione di r-frame che rappresentano le porzioni più importanti di un video
Mosaicatura: unione di frame diversi che nel loro insieme descrivono un elemento complesso (ad esempio un edificio)
Scene Transition Graph (STG): è una struttura a grafo che cattura in modo compatto sia il contenuto che il flusso temporale di un video (utilizza un concetto simile a quello degli ipertesti per la rappresentazione dei documenti).
Uno Scene Transition Graph (STG) consiste in una rappresentazione di un video mediante un grafo orientato G=(V,E) in cui:
Le feature, una volta estratte, vengono rappresentate attraverso vettori multidimensionali:
La similarità o la distanza sono calcolate come distanza tra i vettori che rappresentano le feature estratte.
Il calcolo della similarità è un’operazione computazionalmente dispendiosa.
Se la dimensionalità del vettore è grande, i tempi di ricerca per confrontare tutti i vettori dei dati memorizzati con la query diventano troppo lunghi.
Occorrono tecniche e strutture dati che permettano di organizzare i vettori multidimensionali e di effettuare le ricerche in modo veloce.
Lo scopo fondamentale di tali tecniche è di suddividere lo spazio multidimensionale in sottospazi in modo tale che solo alcuni di questi debbano essere considerati per rispondere ad una query.
Point query: una query utente è rappresentata da un vettore e la ricerca ha come obiettivo quello di trovare gli oggetti memorizzati nel database il cui vettore delle feature risulta identico a quello della query (exact match).
Range query: la query è rappresentata da un vettore e da un range di distanza. Tutti gli oggetti la cui distanza dalla query è inferiore o uguale a quella specificata sono ritrovati (in alcuni casi si possono dare range di distanze per ogni dimensione del vettore).
K-nearest neighbor: la query è rappresentata da un vettore e da un intero k: i k oggetti con le distanze più piccole dal vettore di query sono ritrovati.
Le tecniche e le strutture dati che vedremo potranno permettere una o più delle tipologie di query.
Oltre alla ricerca ed al calcolo della distanza si devono permettere inserimenti ed eliminazioni. Tali operazioni non risultano critiche poiché sono possibili off-line).
In alcune applicazioni è possibile utilizzare alcuni criteri per focalizzare la ricerca solo in alcune “zone” dello spazio multidimensionale:
Filtraggio tramite classificazione, attributi strutturati o parole chiave
Utilizza informazioni associate ai dati multimediali per ridurre lo spazio di ricerca.
Esempio: l’utente può essere interessato ad un intervallo di date di produzione o a prodotti di un autore/regista, ecc…)
Filtraggio per “disuguaglianza triangolare”
La distanza d tra due oggetti i e q non può essere inferiore alla differenza tra le loro distanze con un terzo oggetto k. Obiettivo fondamentale del filtraggio è la riduzione del numero dei confronti (tra la query q e gli N vettori di feature del database).
Un istogramma è composto da n bin e la distanza tra due istogrammi è calcolata sommando le differenze tra i valori dei bin corrispondenti.
Per ottenere una elevata velocità di ricerca si possono:
Le due strategie si possono combinare nel seguente modo:
Si utilizzano istogrammi con pochi bin per selezionare i possibili candidati tra tutte le immagini presenti nel database.
Di tale sottinsieme si calcola la differenza con la query utilizzando gli istogrammi completi.
1. Introduzione
2. Tipologia e formati dei dati MultiMediali. Il testo
3. Tipologia e formati dei dati MultiMediali. L'audio
4. Tipologia e formati dei dati MultiMediali. Grafica e video
5. Progetto di DB Multimediali
6. Indicizzazione e recupero dei documenti di testo
7. Indicizzazione e recupero dell'audio
8. Metodi di classificazione dell'audio
9. Colori
10. Indicizzazione e recupero delle immagini
11. Esempi reali di image retrieval
12. Video
13. Strutture dati efficienti per la ricerca della similarità - pa...
14. Strutture dati efficienti per la ricerca della similarità - pa...
15. Sistemi di supporto e misure di efficacia
17. Geographical Information System - parte prima
18. Geographical Information System -parte seconda
19. Geographical Information System - parte terza