Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Walter Balzano » 12.Video


Indicizzazione e recupero del Video

  • Introduzione
  • Approcci di Indicizzazione e Recupero basati su shot
  • Scoperta di shot; segmentazione
  • Indicizzazione e recupero del video
  • Video: rappresentazione ed astrazione

Introduzione

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:

  • metadati: informazioni strutturate memorizzate in RDBMS tradizional;i
  • testo: sottotitoli o trascrizioni dei dialoghi trattati con tecniche di IR standard per l’indicizzazione e la ricerca;
  • audio: segmentazione in parlato e non parlato; tecniche di speech recognition per ricavare il testo su cui poi applicare tecniche di IR;
  • contenuto:
    • metodo 1 (singolo fotogramma): il video viene considerato come una serie di immagini indipendenti su cui è possibile applicare tecniche per immagini. Questo approccio comporta evidenti svantaggi:
      • perdita di informazioni temporali;
      • la mole di dati da elaborare è molto grande;
    • metodo 2 (gruppi di fotogrammi): i frame vengono suddivisi in gruppi (shots) e l’indicizzazione è basata sui frame rappresentativi di ogni shot.

Indicizzazione e ricerca basata sugli shot

Shot: gruppo di frame contigui che hanno uno o più delle seguenti caratteristiche:

  • frame fanno parte della stessa scena;
  • frame non sono interrotti da uno “stacco” della telecamera;
  • frame contengono lo stesso evento / azione.

Esempi:

  • In un video di un telegiornale, ogni notizia rappresenta uno shot diverso.
  • In un film, una serie di immagini con gli stessi protagonisti presenti nello stesso ambiente è uno shot

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.

Passaggio shot

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:

SD_i=\Sigma \arrowvert H_i (j) - H_{i+1} (j)\arrowvert

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.

Shot e transizioni (segue)

Esempio di dissolvenza incrociata.

Esempio di dissolvenza incrociata.


Segmentazione a due soglie

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.

Cambio SHOT: doppia soglia.

Cambio SHOT: doppia soglia.


Utilizzo degli shot

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:

  • non vengono considerate correttamente le differenze di lunghezza tra i vari shot;
  • non è “catturato” completamente il contenuto di uno shot.

N r-frame al secondo.
Svantaggi:

  • gestisco la lunghezza ma non il contenuto;
  • potrebbero anche essere sovrabbondanti nel caso di uno shot molto uniforme.

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.

Individuazione degli r-frame

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:

  • si considera come r-frame il primo frame dello shot (o del sotto-shot);
  • si calcola un frame “medio” facendo la media dei colori di tutti frame dello shot pixel per pixel;
  • si calcola la media di tutti gli istogrammi dei frame dello shot e scelgo come r-frame il frame il cui istogramma è più vicino all’istogramma medio.
Individuazione dei r-frame.

Individuazione dei r-frame.

Individuazione dei r-frame.

Individuazione dei r-frame.


Tecniche basate sulle informazioni di movimento

Le tecniche basate sulle informazioni di movimento memorizzano, per ogni frame , le informazioni derivanti dai “motion vectors“:

  • direzione prevalente di movimento;
  • uniformità del movimento;
  • panning;
  • zoom.

Ogni shot viene indicizzato attraverso i motion vectors che lo caratterizzano.

Definizione del Motion Vector.

Definizione del Motion Vector.

Motion Vectors.

Motion Vectors.


Tecniche basate sul riconoscimento degli oggetti

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.

Riconoscimento per segmentazione.

Riconoscimento per segmentazione.


Rappresentazione video

I Video sono assai ricchi dal punto di vista informativo e contengono una dimensione temporale.

Sono richiesti metodi di rappresentazione compatta.

  • Video browsing (scorrere un video ricercando una porzione di interesse): una rappresentazione compatta velocizzerebbe di molto tali operazioni su video di una certa lunghezza;
  • presentazione dei risultati di una ricerca: un sistema di ricerca ritorna video o shot a seguito di una query dell’utente. Una rappresentazione compatta occupa una limitata porzione di schermo;
  • limitazione dei requisiti sulla banda di trasmissione: un utente potrebbe consultare la rappresentazione compatta che occupa molti meno byte dell’originale.

Classificazione dei video

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:

  • un r-frame;
  • la profondità (indica la durata temporale);
  • i pixel presenti sui bordi orizzontali e verticali danno una idea del movimento all’interno dello shot.

Una MICON può fornire informazioni aggiuntive tagliando il “cubo” orizzontalmente o verticalmente.

Classificazione dei video per argomenti.

Classificazione dei video per argomenti.

MICON
Fonte: MICON – tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.

MICON Fonte: MICON - tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc.,© 1999 by Artech House, Inc.


Browser video gerarchico

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.

Struttura di video gerarchico.

Struttura di video gerarchico.

Esempio di video gerarchico.

Esempio di video gerarchico.


Altre tecniche di rappresentazione compatta

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:

  • V: vertici. Ciascun Vertice rappresenta un cluster di Shot simili;
  • E: archi. Una coppia di Vertici i e j sono connessi da un arco se esiste uno shot in un cluster i che precede uno shot in un cluster j.
STG: un esempio.

STG: un esempio.


Tecniche e strutture dati per la ricerca efficiente di similarità nei dati multimediali

Le feature, una volta estratte, vengono rappresentate attraverso vettori multidimensionali:

  • zero crossing rate;
  • silence ratio;
  • istogrammi di colore;
  • … ecc.

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.

Tipi di query e di vettori

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).

Riduzione dello spazio di ricerca tramite filtraggio

In alcune applicazioni è possibile utilizzare alcuni criteri per focalizzare la ricerca solo in alcune “zone” dello spazio multidimensionale:

  • filtraggio per classificazione;
  • filtraggio per disuguaglianza triangolare;
  • filtraggio per istogrammi di colore;
  • filtraggio basato sul colore medio.

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).

Filtraggio per attributi.

Filtraggio per attributi.

Filtraggio per triangolazione.

Filtraggio per triangolazione.


Filtraggio per istogrammi di colore

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:

  • ridurre il numero dei bin (diminuendo l’accuratezza in quanto colori diversi vengono considerati uguali);
  • effettuare il calcolo della distanza solo per un sottoinsieme delle immagini presenti nel database.

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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion