Multimedia Information Retrieval


Download 445 b.
Sana14.08.2018
Hajmi445 b.


Multimedia Information Retrieval

    • Enver Sangineto,
    • Dipartimento di Informatica
    • sangineto@di.uniroma1.it

Problema

  • Nel Web e nei DB “locali” esiste molta informazione non esclusivamente testuale:

    • audio (speech, musica…)
    • immagini,
    • video,
  • Come recuperare efficacemente materiale multimediale?



Esempi di applicazione

  • Web indexing:

    • Recupero di materiale multimediale dal Web,
    • Sistemi capaci di bloccare immagini pubblicitarie oppure illegali/indesiderate
  • Trademark e copyright

  • Accesso ai musei

  • DB commerciali



Esempi di applicazione [2]

  • Immagini satellitari (applicazioni militari, government, …)

  • Immagini mediche

  • Entertainment

  • Criminal investigation



Prima generazione di multimedia information retrieval systems

  • Off-line: il materiale multimediale viene associato con una descrizione testuale. Ese.:

    • Annotazione manuale (“content descriptive metadata”)
    • Il testo che in una pagina Web circonda l’img
  • On-line: utilizzo di tecniche di IR testuali basate sul “keyword match”





Limiti dell’approccio esclusivamente testuale

  • L’annotazione manuale di grossi DB multimediali è impensabile…

  • Non è facile descrivere verbalmente il contenuto percettivo di un’immagine, di un video o di un brano musicale…



Esempi

  • Cercare una canzone conoscendone solo il ritornello

  • Cercare una determinata azione in un video sportivo

  • Cercare dipinti che hanno un determinato dosaggio di colori



Esempi [2]

  • Google Image può restituire fino ad un 85% di documenti NON rilevanti anche per query semplici (e.g., oggetti specifici) [1]

  • [1] Fergus, Fei-Fei, Perona, Zisserman, Learning Object Categories from Google’s Image Search, ICCV 05



Soluzioni in fase di ricerca…

  • Sistemi “Content Based”:

    • Si basano sul contenuto percettivo dell’oggetto multimediale. Tipicamente:
      • utilizzano una query by example e
      • modellano direttamente la similitudine percettiva tra la query e gli oggetti del DB
  • Sistemi di annotazione automatica:

    • Fase di pre-processing (“information extraction”): viene estratta (in maniera automatica!) informazione da elementi non testuali e memorizzata sotto forma simbolica (e.g., testuale)
    • Il retrieval (on-line) avviene con tecniche “tradizionali”


Differenze rispetto all’IR Testuale…

  • Un problema comune a tutti i sistemi di Multimedia IR è il trattamento di informazione non simbolica

  • Un testo può essere visto come la combinazione di elementi simbolici atomici (le parole o token)

  • Un’immagine è una collezione di pixel e un suono un’onda sonora…



Cosa vedremo in queste tre lezioni…

  • Introduzione ai sistemi content based basati su caratteristiche percettive quali:

    • Colore, movimento, suono, forma…
  • Sistemi di annotazione automatica



Elementi tipici di un sistema di Content Based Multimedia IR

  • Dal punto di vista dell’utente:

    • La query è un oggetto multimediale (e.g., un’immagine, un disegno, un elemento audio, …)
    • L’output è una lista di elementi ordinati in base alla somiglianza percettiva con la query
    • Esistono strumenti opzionali di interazione per visualizzare collezioni di immagini o fornire feedback al sistema


Esempio: query by image example



Query by image example [2]



Query by image example (sketch) [3]



Elementi tipici di un sistema di Content Based Multimedia IR [2]

  • Dal punto di vista del sistema:

    • Rappresentazione dell’oggetto multimediale (e.g., spazio delle feature)
    • Modellazione del concetto di similitudine percettiva (e.g., attraverso appositi algoritmi di matching)
    • Utilizzo di strutture dati particolari che permettano un indexing efficiente dello spazio delle feature
    • Gestione dell’eventuale relevance feedback (non verrà trattato…)


Rappresentazione



Rappresentazione tramite Feature di un’immagine

  • Una feature è una rappresentazione, tramite un vettore di valori numerici, di tutta o parte dell’immagine

  • Se I' è una sottoparte dell’immagine I, allora una feature f è t.c.:

    • f(I') Rk,
    • f(I') = (v0, … vk-1)T,
    • k >= 1


In genere una feature è una caratteristica facilmente misurabile dell’immagine

  • In genere una feature è una caratteristica facilmente misurabile dell’immagine

  • L’immagine in esame viene quindi descritta usando i valori di un insieme di feature pre-scelte f1, …, fn



Feature globali e locali

  • I' = I: feature globale

  • I' I: feature locale

  • Feature locali:

    • È importante capire come selezionare le sottoparti di I (I‘1, I‘2, …) da rappresentare
    • Più robuste ad occlusioni, parti mancanti, separazione dal background


Esempio: feature locale

  • fi(I') I'

    • I


Alcuni semplici esempi di feature: istogrammi dell’intensità di grigio



Alcuni semplici esempi di feature: geometria facciale



Spazio delle Feature

  • Supponendo di utilizzare n features a valori in R, I può essere rappresentata tramite il vettore x(I) = (f1(I), …fn(I))T

  • x(I) è ottenuto concatenando il valore delle singole feature

  • x(I) è un punto in Rn, detto spazio delle feature



Spazio delle Feature [2]

  • In generale, se:

    • fi(I) Rk,
  • allora: x(I) = (f1(I) T … fn(I) T)T è un punto in Rn*k



Es.: Spazio delle Feature (R2)



Spazio delle Feature [3]

  • E’ un concetto simile ma non identico allo spazio vettoriale usato per rappresentare la frequenza dei termini nei documenti testuali

  • E’ la rappresentazione dei dati più usata nei vari sistemi content based (immagini, video, audio) ma non è l’unica!



Similitudine



Similitudine percettiva

  • Nel text retrieval, la similitudine tra due documenti può essere stimata in funzione dei termini in comune

  • Ad esempio, rappresentando la frequenza dei termini di un documento in un apposito spazio vettoriale, la distanza tra punti in tale spazio descrive la dissimilarità tra documenti

  • Lo spazio delle feature si comporta in maniera analoga…



Similitudine percettiva [2]

  • Nello spazio delle feature la differenza percettiva tra I1 e I2 è proporzionale ad una determinata misura di distanza (non necessariamente Euclidea): dist(x(I1),x(I2))

  • Data la query Q, l’output del sistema è una lista di immagini I1, I2, … ordinata minimizzando:

    • I1 = minI dist(x(Q),x(I)), …


Esempio (R2)



Similitudine percettiva [3]

  • Altri algoritmi di matching fanno uso di rappresentazioni più complesse o alternative allo spazio delle feature e sono tipicamente studiati ad hoc per il particolare sistema di MIR



Indexing



Tecniche di Indexing

  • Problema: come indicizzare efficientemente dei dati in uno spazio multidimensionale?

  • La maggior parte delle più comuni strutture dati per la ricerca efficiente si basano su un ordinamento totale dei valori rappresentati:

    • xi <= xj V xj <= xi (0 <= i,j <= N)
  • Ese.: nel caso delle keyword, l’ordine alfabetico stabilisce un ordinamento totale del vocabolario (e.g., negli inverted files)

  • In Rk ciò non è più vero



Il k-d Tree

  • E’ una generalizzazione dell’albero di ricerca binario in k dimensioni

  • Ad ogni livello dell’albero viene presa in considerazione ciclicamente una delle k feature



Il k-d Tree [2]

  • Supponiamo di voler indicizzare un insieme di punti multidimensionali:

  • P1, …, PN, Pi Rk, Pi =(xi1, …, xik)

  • Scelgo la prima dimensione (feature) e trovo il valore L1, mediano rispetto a x11, …, xN1



Il k-d Tree [3]

  • La radice dell’albero conterrà L1

  • Il sottoalbero sinistro (TL) conterrà i punti Pi t.c. xi1 <= L1

  • Il sottoalbero destro (TR) gli altri

  • A livello 1 scelgo la seconda feature e, separatamente per TL e TR, calcolo L2 e L3, scelti in modo tale che:



Il k-d Tree [4]

  • Dopo aver utilizzato la feature k-esima, ritorno ciclicamente a considerare la prima feature

  • I punti sono associati alle foglie





Image, video e audio retrieval



Retrieval by color: istogrammi di colore

  • Istogramma dei colori di una parte (eventualmente tutta) di immagine I':

    • Possibili rappresentazioni di un singolo pixel: RGB, HSV, CIE LAB, …
    • Divido ogni canale in k bin:
      • f(I') = (r0,…, rk-1, g0, …, gk-1, b0, …, bk-1)T,
      • ri = # { p in I’: divk(R(p)) = i },
      • gi = # { p in I’: divk(G(p)) = i },
      • bi = # { p in I’: divk(B(p)) = i }


Istogrammi di colore [2]

    • Oppure divido RGB in k3 bin:
      • f(I') = (z0,…, zh-1)T, h= k3
      • Se zi rappresenta i valori (i1, i2, i3), allora:
      • zi = # { p in I’: divk(R(p)) = i1 and divk(G(p)) = i2
      • and divk(B(p)) = i3 }


Istogrammi di colore [3]: esempio



Retrieval by texture



Approccio statistico

  • Tamura features: analizzano la distribuzione dell’intensità locale dell’img al fine di misurare caratteristiche percettive della texture quali:

    • Contrasto
    • Granularità
    • Direzionalità


Esempio



Approccio sintattico: grammatiche visive

  • Ese. di regola di produzione per la rappresentazione di texture (Rosenfeld):

  • Essa riassume le seguenti 4 regole:



Video retrieval



Componenti di un video

  • Frame: una singola immagine

  • Shot: Un sequenza di frame consecutivi ripresi da una singola telecamera

  • Scena: un insieme di shot consecutivi che rispettano le 3 unità aristoteliche di spazio, tempo e azione



Segmentazione di una videosequenza

  • Individuando gli “editing effects” (cuts, dissolvenze, ….) tra uno shot e l’altro è possibile suddividere (automaticamente) un video in shot

  • Molto più difficile è individuare le scene (concetto semantico)



Tipi di ricerca per i video

  • I video possono essere rappresentati con dei “key frame” rappresentativi di ogni shot

  • Un key frame è trattabile come una “still image”:

    • Si applicano le tecniche viste per le immagini (e.g., spazio delle feature, ricerca per colore, texture, forma, ecc.)


Tipi di ricerca per i video

  • Alternativamente, è possibile cercare in un video informazione relativa al movimento (e.g., una particolare traiettoria in un video sportivo, …)



Audio retrieval



Tipi di Query

  • Query by example: viene fornito/sintetizzato un file audio chiedendo di recuperare audio simili

  • Caso particolare, Query by humming:

    • l’utente accenna (vocalmente o anche fischiando…) la melodia da cercare


Rappresentazione e similitudine

  • Uno spazio delle feature può essere creato utilizzando, ad ese., istogrammi ricavati dalla rappresentazione spettrale del segnale

  • La similitudine percettiva in tal caso avviene calcolando la distanza tra punti multidimensionali come nel caso delle immagini

    • Distanze tipiche: Euclidea, Mahalanobis, distanze per istogrammi (Histogram Intersection, Kullback-Leibler divergence, Chi-quadro, ecc.)


Aspetti percettivi diversi possono essere combinati



Alcuni riferimenti

  • A. Del Bimbo, Visual Information Retrieval, Morgan Kaufmann Publishers, Inc. San Francisco, California", 1999

  • Forsyth, Ponce, Computer Vision, a Modern Approach 2003



Alcuni riferimenti [2]

  • Smeulders et al., Content-Based Image Retrieval at the End of Early Years, IEEE PAMI 2000

  • Long et al., Fundamentals of Content-based Image Retrieval, in: D. D. Feng, W. C. Siu, H. J. Zhang (Ed.),Multimedia Information Retrieval & Management-Technological Fundamentals and Applications, Springer-Verlag, New York(2003)

  • Foote et al., An Overview of Audio Information Retrieval, ACM Multimedia Systems, 1998

  • Hemant M. Kakde, Range Searching using Kd Tree, 2005



Domande…





Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2019
ma'muriyatiga murojaat qiling