Annotazione Automatica di materiale multimediale Enver Sangineto, Dipartimento di Informatica [email protected] Annotazione automatica Estrarre automaticamente informazione “semantica” da immagini, video o audio e rappresentarla in forma: testuale o simbolica (“machine understandable”) Si usano spesso tecniche di machine learning p. 2 Annotazione automatica [2] E’ una fase di pre-processing, precedente al retrieval vero e proprio, che avviene con metodi più “tradizionali” avvalendosi dell’informazione estratta off-line E’ simile alla “information extraction” nel caso dei testi, in cui da un documento si ricava informazione rappresentata poi in maniera machine understandable p. 3 Annotazione di documenti digitali: OCR e Document Analysis Un caso particolare di immagine è la digitalizzazione di un documento di testo Tecniche di Document Analysis permettono di analizzare la struttura del documento al fine di individuare le parti contenenti testo Il testo può essere riconosciuto attraverso Optical Character Recognition (OCR) p. 4 Annotazione di immagini (generiche) L’ideale sarebbe poter disporre di un sistema che riconosca i principali oggetti presenti in un’immagine e li descriva tramite una lista di keywords p. 5 Annotazione di immagini [2] E’ difficile stabilire a priori quali sono gli oggetti importanti in una data immagine Un tale sistema non sarebbe in grado di estrarre significati più complessi (e.g. “Rabin e Arafat si stringono la mano”…) Tuttavia una lista degli oggetti (e.g., in primo piano) sarebbe già un grosso passo in avanti p. 6 Esempio Annotazione 1: ci sono 3 esseri umani Annotazione 2: ci sono 3 esseri umani, Arafat, Clinton e Rabin p. 7 Problemi principali nel riconoscimento di oggetti La maggior parte dei problemi che un sistema di object recognition deve affrontare sono riconducibili a due problemi base: Variabilità delle apparenze con cui l’immagine di un oggetto può presentarsi sul piano di vista La segmentazione della scena, ovvero l’individuazione di quelle sotto-parti dell’immagine che rappresentano l’oggetto cercato p. 8 Variabilità [1]: cambiamento del punto di vista p. 9 Michelangelo 1475-1564 Variabilità [2]: cambiamento delle condizioni di illuminazione p. 10 Variabilità [3]: oggetti deformabili Xu, Beihong 1943 p. 11 Variabilità [4]: variazione intra-classe p. 12 Segmentazione [1]: Occlusioni p. 13 Magritte, 1957 Segmentazione [2]: separazione dallo sfondo p. 14 Klimt, 1913 Categorizzazione tramite apprendimento automatico Suppongo di disporre, in fase di training, di un insieme T = {(I1, y1), …, (IN, yN)}, dove Ij è un’immagine e yj un’etichetta che indica l’oggetto in essa contenuto: yj {o1, …, om} p. 15 Categorizzazione tramite apprendimento automatico [2] Utilizzo T off-line per addestrare un classificatore statistico C (e.g., una rete neurale, una SVM, …) On-line, uso C per classificare un’immagine nuova I, non appartenente a T: C(I) {o1, …, om} p. 16 Categorizzazione tramite apprendimento automatico [3] Esistono molti approcci all’object recognition che utilizzano tecniche di apprendimento automatico Essi si scontrano con i problemi di segmentazione e variabilità visti prima p. 17 Idea: image categorization come text categorization Un approccio nuovo si avvale di un’analogia con i documenti testuali: documenti <-> immagini concetti <-> classi di oggetti keywords <-> (valori “prototipi” di) feature spazio vettoriale <-> spazio della frequenza delle feature prototipe p. 18 Proprietà di invarianza delle feature Maggiore è l’invarianza delle feature a cambiamenti di apparenza, minore la variabilità da rappresentare nel training set Invarianze desiderabili: Cambiamenti di punti di vista (rotazioni, traslazioni, scalamenti) Cambiamenti di illuminazione p. 19 Features per immagini non segmentate Le feature globali sono inefficaci se l’oggetto cercato non è separato dal background L’orientazione corrente è utilizzare feature locali che in genere dipendono sia dalla forma che dalla texture dell’oggetto p. 20 Esempi di feature: Istogrammi basati sui pixel di edge • SIFT, D. Lowe, Int. Journal of Computer Vision, 2004 • Shape context Belongie, Malik, Puzicha, NIPS 2000 p. 21 Scale Invariant Feature Transform (SIFT) [Lowe] L’estrazione delle SIFT da un’immagine è composta da due fasi: Individuazione di punti “stabili” a cambiamenti di scala Descrizione delle zone circostanti tali punti con il descrittore SIFT [Lowe ] David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, Int. J. Comput. Vision, 60 (2), pp 91-110, 2004. p. 22 Selezione di punti stabili a cambiamenti di scala Differenze di scala vengono simulate costruendo una “piramide” di DoG I punti stabili sono scelti cercando punti di massimo/minimo nella piramide p. 23 Descrittore SIFT Il descrittore è ottenuto concatenando il valore dei 4*4 istogrammi da 8 orientazioni l’uno Normalizzando rispetto al modulo si ottiene un descrittore invariante per trasformazioni affini della luce nell’area descritta p. 24 Bags of Words Estraggo le feature da vari punti dell’immagine, scegliendo: I punti più salienti (tipo SIFT…), oppure Dei punti a caso… Conto la frequenza dei valori delle feature estratte e classifico l’immagine in base alla frequenza trovata Tecnica simile alla rappresentazione di un documento in uno spazio vettoriale p. 25 Object Bag of ‘words’ p. 26 immagine presa da: Tutorial CVPR 07 Problema: dimensionalità del “vocabolario” delle feature Una feature f(), a differenza delle keyword, ha codominio in Rk, e non in un insieme discreto, finito e numericamente limitato come un vocabolario di un linguaggio p. 27 Esempio: dimensionalità delle SIFT Un descrittore SIFT è composto da 4*4 istogrammi da 8 orientazioni (128 elementi) I valori del “bin” di ogni istogramma sono normalizzati in [0, 255] In totale 256128 possibili valori… p. 28 Prototipi di feature: le “keywords” discrete che mancavano Suddivido i valori che può assumere una feature in “tipi” diversi Ogni tipo è rappresentato da un prototipo, detto “word” per analogia al caso testuale In sostanza, creando i tipi di feature, creo un vocabolario di valori discreti p. 29 Esempio Supponiamo che lo spazio delle feature sia RGB (uno spazio semplice, di sole 3 dimensioni) Posso pensare di partizionare tale spazio associando ad alcune zone l’etichetta “rosso” o “giallo”, ecc. Una volta definiti opportunamente i confini della zona rossa, il centro di tale zona può essere usato come coordinate prototipe (r,g,b) del colore “rosso” p. 30 Vector Quantization Si tratta di un processo di vector quantization con cui creo un dizionario (codebook o codeword dictionary) per discretizzare i possibili valori del feature space p. 31 Es: estraggo le feature da un’img di training p. 32 immagine presa da: Tutorial CVPR 07 Estraggo le feature da tutte le img di training … p. 33 immagine presa da: Tutorial CVPR 07 Rappresentazione nel feature space dei valori estratti dal training set … p. 34 immagine presa da: Tutorial CVPR 07 Costruisco il Codeword dictionary tramite clustering … w2 w1 w3 Vector quantization p. 35 immagine presa da: Tutorial CVPR 07 Rappresentazione di un’immagine nello spazio delle frequenze Supponiamo che il dizionario è composto da n valori possibili {w1, …, wn} Ogni wi è un’etichetta associata con un valore prototipo xi del feature space p. 36 Rappresentazione di un’immagine nello spazio delle frequenze [2] Da una generica immagine I estraggo un insieme di feature locali: z1 = fk(Iq), z2 = fh(Ip), … Associo ogni zi con la “parola” wj più simile, e.g., scegliendo j in modo da minimizzare: Dist(zi, xj) I è quindi rappresentata da (c1, …, cn)T, dove: cj= # { wj : Esiste zi associata con xj } p. 37 frequency Rappresentazione dell’immagine ….. w1 w2 w3 w4 … p. 38 immagine presa da: Tutorial CVPR 07 Effetti dell’uso del dizionario Ho ridotto il numero dei possibili valori che una feature può assumere da |Rk| a n (n << |Rk| ) Nello spazio delle frequenze (Rn) posso applicare tecniche di classificazione simili a quelle usate, ad ese., nel text categorization Il risultato è un procedimento di classificazione statistica delle immagini che mi permette, data una nuova immagine in input, di stabilire quali oggetti (o1, …, om) essa rappresenta p. 39 Bags of Words: riassunto 1. 2. 3. Scelta delle feature per rappresentare le img e costruzione dello spazio delle feature F Attraverso un training set di img e tecniche di clustering, costruisco il dizionario delle feature scegliendo i prototipi di feature più comuni (“words”) Utilizzando il dizionario rappresento il training set di img nello spazio delle frequenze (S) delle words p. 40 Bags of Words: riassunto [2] 4. 5. 6. Utilizzo tecniche di classificazione in S per costruire un classificatore statistico C On-line, associo le feature prototipe ad una nuova img (I) e ne conto la frequenza Posso quindi rappresentare I in S e utilizzare C per classificarla p. 41 Annotazioni di video Un video è una sequenza di immagini (frame), per cui potrei applicare tecniche di image classification (e.g., ai soli key frame) Tuttavia si rileva normalmente più efficace studiare approcci ad hoc per tipi di video differenti (film, news, video sportivi, pubblicità, …) p. 42 Nei video sono spesso già presenti alcune informazioni testuali “Content independent-Metadata”: titolo, autore, produttore, data.. Sottotitoli e trascrizioni degli autori p. 43 Esempio: annotazione di video sportivi Annotare può significare riconoscere azioni di gioco importanti (nel calcio, nel tennis, …) e indicizzare i punti esatti in cui avvengono p. 44 Esempio: annotazione di film Riconoscere gli attori (face recognition) Riconoscere il tipo di scena (allegra, triste, drammatica, suspance, …) da alcune sue caratteristiche come l’intensità luminosa o della colonna sonora, … … p. 45 Annotazioni audio E’ anzitutto necessario distinguere (classificare…) le parti del file audio che contengono una parte parlata da altri suoni o musiche Tecniche di speech recognition possono quindi essere utilizzate per trasformare il parlato in testo p. 46 Annotazioni audio [2] La qualità del riconoscimento può essere elevata per sistemi speaker-dependent Qualità accettabili ai fini del retrieval anche per sistemi speaker-independent p. 47 Alcuni riferimenti Forsyth, Ponce, Computer Vision, a Modern Approach 2003, Duda, Hart, Stork, Pattern Classification (II edition) 2001, Bishop, Pattern Recognition and Machine Learning, 2006 Fergus, Fei-Fei, Perona, Zisserman, Learning Object Categories from Google’s Image Search, ICCV 05 p. 48 Domande… p. 49