Tecniche semi-automatiche per l’annotazione semantica di...

Alma Mater StudiorumUniversita degli Studi di Bologna

Facolta di Ingegneria

Corso di Laurea in Ingegneria Informatica

Tesi di Laurea in Sistemi Informativi LS

Tecniche semi-automatiche per

l’annotazione semantica di dati

multimediali

Candidato: Relatore:

Elisa Rondini Chiar.mo Prof. Paolo Ciaccia

Correlatori:

Dott.ssa Ilaria Bartolini

Ing. Marco Patella

Anno Accademico 2004/2005 - Sessione II

.

.

“What the caterpillar calls the end,

The world calls a butterfly.”

- Lao Tze -

Indice

Introduzione 9

1 Organizzazione della tesi . . . . . . . . . . . . . . . . . . . . . 11

1 Introduzione ai sistemi di ricerca di immagini 13

1 Sistemi di ricerca basati sul contenuto . . . . . . . . . . . . . . 15

1.1 Architettura di un sistema CBIR . . . . . . . . . . . . 16

1.2 Sistemi region-based . . . . . . . . . . . . . . . . . . . 18

1.3 Caratterizzazione del contenuto di immagini . . . . . . 18

2 Cos’e l’etichettamento? . . . . . . . . . . . . . . . . . . . . . . 19

2.1 Etichettamento di immagini mediante keyword . . . . . 19

Etichettamento a singola keyword . . . . . . . . . . . . 21

Etichettamento a multipla keyword . . . . . . . . . . . 23

2.2 Le ontologie di dominio . . . . . . . . . . . . . . . . . . 23

3 Obiettivi per lo scenario di riferimento . . . . . . . . . . . . . 27

2 Stato dell’arte 29

1 Etichettamento semi-automatico mediante

Mixed-Media Graph . . . . . . . . . . . . . . . . . . . . . . . . 30

1.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 31


Multi-Modal Story-oriented video Summarization . . . . . . . 32

2.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Organizzazione mediante

Database Multi-Strutturali . . . . . . . . . . . . . . . . . . . . 35

3.1 Definizione di Database Multi-Strutturali . . . . . . . . 39

3.2 Definizione di Pairwise Disjoint Collection . . . . . . . 39

6 Indice

3.3 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Etichettamento basato su apprendimento

mediante istanza multipla . . . . . . . . . . . . . . . . . . . . 42

4.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 45

5 Etichettamento automatico basato

su selezione di feature . . . . . . . . . . . . . . . . . . . . . . . 46

5.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 48

6 Fusione di contesto, contenuto

ed ontologia semantica . . . . . . . . . . . . . . . . . . . . . . 49

6.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 51

7 Ricerca di similarita basata su connessioni di un grafo . . . . . 53

7.1 Valutazioni . . . . . . . . . . . . . . . . . . . . . . . . 56

3 Proposta per l’etichettamento

automatico di immagini 57

1 Scenario principale . . . . . . . . . . . . . . . . . . . . . . . . 58

2 Formalizzazione del modello . . . . . . . . . . . . . . . . . . . 59

3 Soluzione iniziale . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.1 Definizione formale dell’approccio . . . . . . . . . . . . 65

3.2 Costruzione del Mixed-Media Graph . . . . . . . . . . 66

3.3 Correlazione mediante Random Walk with Restart . . 67

3.4 L’algoritmo Cross-modal Correlation Discovery . . . . 69

3.5 Vantaggi e svantaggi . . . . . . . . . . . . . . . . . . . 70

4 Presentazione dell’approccio proposto . . . . . . . . . . . . . . 74

4.1 Costruzione della matrice di similarita

SimilarityTable . . . . . . . . . . . . . . . . . . . . . . 74

4.2 Fase di generazione delle etichette . . . . . . . . . . . . 79

4.3 Successivo raffinamento . . . . . . . . . . . . . . . . . . 85

4.4 Vantaggi apportati dall’approccio proposto . . . . . . . 93

4 Imagination 95

1 Applicazione di Windsurf al progetto Imagination . . . . . . . 96

2 Interfacciamento con il database MySql . . . . . . . . . . . . . 98

3 Integrazione di una molteplicita di tassonomie . . . . . . . . . 102

4 Architettura software . . . . . . . . . . . . . . . . . . . . . . . 105

Indice 7

4.1 Considerazioni relative al linguaggio . . . . . . . . . . . 105

4.2 Struttura di Imagination . . . . . . . . . . . . . . . . . 105

4.3 Struttura di Jont . . . . . . . . . . . . . . . . . . . . . 115

5 Interfaccia grafica di Imagination . . . . . . . . . . . . . . . . 118

6 Interfaccia grafica di Jont . . . . . . . . . . . . . . . . . . . . 131

7 Valutazioni sui parametri di Imagination . . . . . . . . . . . . 131

Bibliografia 145

Introduzione

Lo sviluppo raggiunto negli ultimi anni nell’ambito informatico e nelle tec-

nologie ad esso connesse ha reso sempre piu frequente l’uso dei computer e

di Internet al fine di conseguire i piu svariati obiettivi, siano essi di studio, di

lavoro o di semplice divertimento. Cio ha portato ad un notevole incremento

del materiale multimediale su cui ogni giorno facciamo affidamento sia esso

di tipo testuale, video o audio. Nasce, per questo motivo, la necessita di ge-

stire questa sempre crescente quantita di informazione in modo strutturato

al fine di rendere piu efficienti ed efficaci le ricerche che vengono compiute su

di essa.

Non e facile raggiungere questo scopo poiche, parallelamente alla crescita

della quantita di informazioni disponibili, e anche notevolmente aumenta-

to il numero di utenti che a tali contenuti vuole accedere. Di conseguenza

l’utente medio che si serve delle risorse disponibili in formato digitale e spes-

so inesperto riguardo alle tecniche atte a recuperarle. I sistemi di recupero

di immagini (le immagini sono, senza dubbio, il tipo di dato multimediale al

giorno d’oggi piu diffuso seconde solo ai dati puramente testuali) hanno avuto

per molto tempo come obiettivo quello di fornire un’interfaccia utente adatta

a guidarlo nel modo piu opportuno verso gli obiettivi che lui ha in mente,

spesso poco chiari e definiti anche nella mente dell’utente stesso, aiutandolo a

formulare una query, o interrogazione, in modo corretto e nascondendo pero,

all’utente stesso, un meccanismo di elaborazione veloce e efficace.

L’uso frequente di Internet ha sottolineato come sia necessario limitare al

massimo il numero dei false drop derivati da una ricerca: nessuno e, infat-

ti, interessato alla ricezione di risultati scorretti, soprattutto se per poterli

visualizzare e necessario sprecare parte della banda disponibile. Una tecnica

di retrieval ovvero di reperimento deve essere, dunque, efficace, efficiente e

10 Introduzione

presentare un’interfaccia utente possibilmente amichevole e semplice pur na-

scondendo un sistema potente.

Tra tutte le risorse disponibili, la piu significativa e probabilmente l’immagi-

ne: essa rappresenta dei contenuti a volte difficilmente esprimibili solo tramite

le parole e necessita di relativamente poco spazio rispetto a contenuti muti-

mediali quali video o audio.

Essendo, pero, peculiarita dell’uomo quella di capire il significato delle cose,

sorge la necessita di trovare un sistema di ricerca di immagini basato sul loro

contenuto semantico, o concettuale. Esistono diverse soluzioni tradizionali

che permettono, in maniera efficace, di reperire immagini dotate di determi-

nate caratteristiche di basso livello (low level feature) quali colore, tessitura e

forma, questo con la consapevolezza che non e sufficiente in quanto serve una

tecnica che consenta all’utente di cercare le immagini raffiguranti concetti o

oggetti dotati di una ben determinata semantica. Proprio in questo ambito

la ricerca diventa, pero, meno accurata se si usano sistemi tradizionali in

quanto non risulta immediato dedurre il significato di un’immagine a partire

dalle sue caratteristiche elementari.

Questo problema e noto con il nome di “gap semantico” . Tra le varie de-

finizioni attribuite a questo concetto vi e quella secondo cui esso denota la

differenza sussistente fra le caratteristiche di basso livello e la similarita fra

concetti di alto livello. In ogni caso esso denota la differenza che c’e fra cio

che il computer e un grado di comprendere da solo e cio che l’uomo e in gra-

do di astrarre avendo a disposizione le caratteristiche di basso livello, ossia i

concetti.

Non e semplice ridurre questo gap semantico, ma negli ultimi anni la ricerca

si e preoccupata molto a riguardo. Da tali sforzi e emersa l’importanza di

generare dei metadati opportuni che facciano da ponte fra le caratteristiche

di basso livello (low level feature) e il livello semantico o concettuale, os-

sia un metodo per annotare le immagini sfruttando dati che ne descrivano

il contenuto semantico. Questo viene fatto affinche un sistema di recupero

di immagini possa risultare molto piu familiare per l’utente che, in genere,

durante la propria attivita di ricerca, e molto piu abituato a pensare alle

immagini a livello di significati semantici ad esse associati piuttosto che a

caratteristiche tecniche associate alle stesse quali colore, tessitura, forma etc.

0.1 Organizzazione della tesi 11

Da queste considerazioni di base nasce e si sviluppa il presente lavoro di tesi

che si pone come obiettivo quello di esaminare quali sono le tecniche, per

gestire in modo semi-automatico e automatico l’annotazione di immagini,

introdotte negli ultimi anni.

L’idea e quella di partire dalla proposta che e stata studiata approfondi-

tamente durante l’attivita di tirocinio curriculare, i cui dettagli si possono

ritrovare in [30], al fine di valutare in maniera oggettiva i vantaggi e gli svan-

taggi connessi a quest’ultima. A partire da tale proposta, il presente lavoro

di tesi si ripromette di modellare un approccio innovativo di annotazione

semi-automatica di immagini composto da una molteplicita di algoritmi in

grado di fondere principalmente due tecniche di base con l’obiettivo di mi-

gliorare sia l’efficienza (intesa come velocita di generazione) sia l’efficacia

(intesa come qualita dei termini prodotti) nella generazione automatica delle

etichette.

1 Organizzazione della tesi

Il presente lavoro di tesi viene suddiviso nei seguenti capitoli:

• Capitolo 1

Viene fornita un’introduzione ai sistemi di image retrieval, presentando

il funzionamento generale dei sistemi di ricerca basati sul contenuto (si-

stemi CBIR), e viene valutata l’importanza di lavorare non solamente

con low level feature, ma anche con la semantica. Si presentano i ma-

cro approcci connessi all’etichettamento automatico di immagini e, al

termine, vengono descritti gli obiettivi che ci si prefigge di raggiungere

nel presente lavoro di tesi.

• Capitolo 2

In questo capitolo viene presentato lo stato dell’arte attuale relativo

ai processi di annotazione automatica e semi-automatica di immagini

mostrando i differenti approcci individuati mediante schede riassuntive

in grado di mappare i tratti salienti di ognuno di essi e facendo delle

valutazioni sul loro grado di bonta e/o applicabilita rispetto allo sce-

12 Introduzione

nario di riferimento e agli obiettivi che ci si e prefissati di raggiungere.

• Capitolo 3

Viene fornita la formalizzazione dello scenario di riferimento. Questo

capitolo si propone di parlare dell’approccio che si e scelto di segui-

re durante l’attivita di tirocinio curriculare presentando i vantaggi ed

esponendo le problematiche ad esso connesse. Al termine viene descrit-

to e formalizzato l’approccio di annotazione automatica di immagini

proposto, esponendone tutti i dettagli algoritmici e valutando i vantag-

gi da esso introdotti.

• Capitolo 4

Viene fornita una descrizione dettagliata del prototipo software Imagi-

nation (“IMage semAntics: ontoloGy mappiINg & Auto capTIONing”).

Si espone il modo in cui e stato possibile applicare il progetto Windsurf

al prototipo Imagination. Vengono forniti i dettagli relativi all’intera-

zione con il DBMS MySql. Viene presentato lo scenario multitassono-

mico di riferimento, descrivendo cos’e un’ontologia e dove quest’ultima

e stata applicata in ambito progettuale. Vengono descritte sia l’archi-

tettura software del sistema sia l’interfaccia grafica di quest’ultimo,

in particolare vengono introdotti anche esempi esplicativi del funzio-

namento del prototipo stesso e valutazioni sulla scelta dei valori dei

parametri utilizzando i risultati sperimentali raccolti.

• Conclusioni

Vengono riportate alcune valutazioni conclusive sia riguardo ai proble-

mi emersi durante lo sviluppo dell’applicazione, sia riguardo gli even-

tuali sviluppi futuri che si potrebbero apportare al sistema per miglio-

rare il processo di generazione automatica delle etichette e la successiva

annotazione di nuove immagini non ancora etichettate.

Capitolo 1

Introduzione ai sistemi di

ricerca di immagini

L’obiettivo principale di questo capitolo e quello di presentare i sistemi di

reperimento di immagini e di capire come e perche e stato necessario intro-

durre tecniche di annotazione automatica di immagini al fine di migliorare il

processo di recupero delle stesse nei sistemi globali di image retrieval. Con la

diffusione di database di immagini di crescenti dimensioni e sorta l’esigenza

di rappresentarne sintatticamente il contenuto per poterle poi confrontare

in fase di ricerca. Sono nati cosı i cosiddetti sistemi “Content Based Image

Retrieval” (CBIR).

I primi sistemi CBIR sono nati negli anni ’90 per far fronte alla necessita di

gestire un numero di immagini sempre crescente.

L’approccio tradizionale, sviluppato a partire dagli anni ’70, prevedeva infatti

una descrizione delle immagini basata sull’annotazione manuale di stringhe

di attributi (ad esempio l’autore, l’anno e il titolo di una fotografia), ed in

questo modo ci si riportava al caso degli algoritmi di ricerca basati sul testo

noti da tempo.

Tale metodo e entrato in crisi negli anni ’90 essendo in pratica inutilizzabile

per la gestione di dataset costituiti da milioni di oggetti: oltre a richiedere

all’operatore un carico di lavoro inaccettabile nella fase di popolazione del

database, si fornisce una descrizione delle immagini troppo soggettiva (tipi-

camente individui diversi potrebbero ad esempio scegliere attributi diversi)

e troppo spesso imprecisa a causa delle difficolta nel dare una descrizione

14 Introduzione ai sistemi di ricerca di immagini

verbale delle stesse.

Esistono diverse soluzioni tradizionali che permettono, in maniera efficace, di

reperire immagini dotate di determinate caratteristiche di basso livello (low

level feature) quali il colore e la tessitura, questo con la consapevolezza che

non e sufficiente in quanto serve una tecnica che consenta all’utente di cerca-

re le immagini raffiguranti concetti o oggetti dotati di una ben determinata

semantica. Proprio in questo ambito la ricerca diventa, pero, meno accurata

se si usano sistemi tradizionali in quanto non risulta immediato dedurre il

significato di un’immagine a partire dalle sue caratteristiche elementari.

Questo problema e noto con il nome di “gap semantico” . Tra le varie de-

finizioni attribuite a questo concetto vi e quella secondo cui esso denota la

differenza sussistente fra le caratteristiche di basso livello e la similarita fra

concetti di alto livello. In ogni caso esso denota la differenza che c’e fra cio

che il computer e un grado di comprendere da solo e cio che l’uomo e in grado

di astrarre da caratteristiche di basso livello, ossia i concetti.

Non e semplice ridurre questo gap semantico, ma negli ultimi anni la ricerca

si e preoccupata molto a riguardo. Da tali sforzi e emersa l’importanza di

generare dei metadati opportuni che facciano da ponte fra le caratteristiche

di basso livello e il livello semantico o concettuale, ossia un metodo per an-

notare le immagini sfruttando dati che ne descrivano il contenuto semantico.

Questo viene fatto affinche un sistema di recupero di immagini possa risulta-

re molto piu familiare per l’utente che, in genere, durante la propria attivita

di ricerca e molto piu abituato a pensare alle immagini a livello di significati

semantici ad esse associati, piuttosto che a caratteristiche tecniche associate

alle stesse quali colore, tessitura, forma etc.

Queste ed altre considerazioni hanno portato all’introduzione di una seconda

generazione di sistemi di ricerca di immagini che fosse adatta al nuovo sce-

nario presentato.

In questo capitolo si andranno a presentare le problematiche connesse al re-

perimento di contenuti multimediali all’interno di database di grosse dimen-

sioni, andando a soffermare l’attenzione sulle principali tendenze che si sono

evolute negli ultimi anni. Si offrira una descrizione per i sistemi di image re-

trieval ovvero per i sistemi di reperimento di immagini. Si parlera dell’impor-

tanza connessa alla possibilita di gestire un etichettamento semi-automatico

1.1 Sistemi di ricerca basati sul contenuto 15

o automatico di immagini, al fine di essere applicato ai sistemi di image re-

trieval, presentando gli obiettivi che si pensa potranno essere raggiunti con

il presente lavoro di tesi.

1 Sistemi di ricerca basati sul contenuto

Esistono ad oggi pochissimi prodotti commerciali che includono moduli per la

ricerca basati sul contenuto, cosı come pochi sono i pacchetti software utiliz-

zabili: uno dei piu sfruttati e senza dubbio QBIC (Query By Image Content),

sviluppato dall’ Almaden Research Center dell’IBM.

La maggior parte dei sistemi CBIR esistenti sono prototipi di ricerca svilup-

pati in laboratori ed universita; tra i tanti i piu noti sono Photobook, svilup-

pato al MIT Media Lab., VisualSEEk della Columbia University, NeTra della

UCSB, WALRUS sviluppato presso i Bell Laboratories, Blobworld dell’uni-

versita della California, SIMPLIcity della Stanford University e WINDSURF

sviluppato presso l’Universita di Bologna.

Il crescente interesse mostrato nei confronti dei sistemi per la gestione e il

reperimento di immagini e legato al sempre maggior numero di settori nei

quali vengono utilizzati, ad esempio in applicazioni Web ma anche nella me-

dicina, nel campo militare e nella prevenzione del crimine.

Come si puo notare, si tratta di settori applicativi molto diversi tra loro: le

immagini che devono essere gestite presentano, quindi, caratteristiche comu-

ni all’interno dello stesso settore applicativo, ma in generale completamente

diverse tra un settore e l’altro. Questo suggerisce come un approccio specia-

lizzato possa essere piu semplice da gestire rispetto ad un approccio generico:

infatti sfruttando la conoscenza del particolare dominio applicativo e possibi-

le scegliere il metodo piu opportuno in grado di caratterizzarne il contenuto

(cosı ad esempio puo risultare un inutile sforzo estrarre informazioni di forma

da fotografie rappresentanti paesaggi). Nella maggior parte dei casi tuttavia

si suppone di non conoscere a priori nessuna caratteristica comune alle imma-

gini che il sistema dovra processare per non perdere in generalita e sviluppare

sistemi di ricerca adatti a basi di dati eterogenee.


1.1 Architettura di un sistema CBIR

Un sistema di ricerca di immagini basato sul contenuto deve riuscire ad estrar-

re da ogni immagine, e in modo automatico, una qualche rappresentazione

semantica a basso livello del contenuto che sia comprensibile dal calcolatore

e possa, quindi, permettere i confronti in fase di interrogazione.

Come si puo notare in Figura 1.1 si possono distinguere due fasi distinte in

un sistema CBIR:

• La fase cosiddetta di popolazione del database (o di pre-processing), in

cui avviene l’estrazione automatica delle caratteristiche di basso livello

(low level feature) dell’immagine (ad esempio la distribuzione del colo-

re, informazioni di tessitura, di forma etc.). Tali informazioni vengono

poi memorizzate ed eventualmente indicizzate. Questa fase e di norma

abbastanza costosa in termini di tempo.

• La fase di interrogazione vera e propria (o fase di query processing), in

cui l’utente ad alto livello, tipicamente attraverso un’interfaccia grafica,

formula un’interrogazione alla collezione creata in precedenza mediante

esempi visivi (selezionando un’immagine oppure disegnando lui stesso

una forma di esempio se il sistema lo consente). L’immagine query sele-

zionata, in generale, deve essere a sua volta processata dal sistema per

estrarre feature analoghe a quelle memorizzate per il database. In que-

sto modo le caratteristiche estratte da ciascuna immagine della collezio-

ne sono comparate con quelle dell’immagine query secondo il modello

di similarita implementato dal sistema: il problema del confronto fra

immagini si riconduce, quindi, alla sola determinazione di una misura

di distanza fra le feature estratte. Questa seconda fase deve avere una

durata molto breve perche i risultati devono essere presentati all’utente

in tempo reale. Nei sistemi CBIR piu avanzati sono integrati meccani-

smi di interazione con l’utente detti di Relevance Feedback mediante i

quali l’utente puo, sulla base dei risultati ottenuti, riformulare la query

fornendo al sistema informazioni aggiuntive; ad esempio selezionando

le immagini, tra quelle presentate come risultato, che ritiene rilevanti.

I vari CBIR differiscono fra loro perche adottano soluzioni diverse relati-

vamente sia all’estrazione delle feature che alla valutazione della similarita,

1.1.1 Architettura di un sistema CBIR 17

Figura 1.1: Architettura di un Sistema Content-Based Image Retrieval.


oltre che alle modalita di indicizzazione dei dati utilizzate per aumentare

l’efficienza.

1.2 Sistemi region-based

Qualora le immagini in esame abbiano una struttura complessa e non omo-

genea considerare l’immagine come un unico oggetto atomico non porta a

risultati soddisfacenti: ad esempio se due immagini raffigurano lo stesso og-

getto, ma su sfondi diversi, le caratteristiche globali estratte probabilmente

saranno molto differenti, quando invece la semantica dell’immagine potrebbe

essere sostanzialmente la stessa.

Per superare questi limiti e stato introdotto l’approccio “region-based”. I

sistemi che implementano tale approccio suddividono l’immagine in regioni

omogenee in base alle feature utilizzate e descrivono poi ciascuna regione me-

diante feature locali quali colore, tessitura e forma. Viene definita una misura

di distanza per valutare la similarita fra le regioni, si confrontano le regioni

e solo in un secondo tempo, sulla base dei risultati parziali, si confrontano le

immagini nella loro totalita.

1.3 Caratterizzazione del contenuto di immagini

Le proprieta usate per la caratterizzazione delle immagini (o delle regioni

presenti) sono per lo piu percettive.

In particolare, quelle piu utilizzate come feature dai sistemi di ricerca di

immagini basati sul contenuto sono il colore e la tessitura. La scelta delle

caratteristiche da estrarre da un’immagine e sempre il risultato di un com-

promesso tra efficacia del risultato ed efficienza in termini di spazio su disco

e di tempo necessario per l’elaborazione. Combinando, infatti, tra loro le

caratteristiche principali si possono sia definire proprieta piu complesse, ad

esempio utilizzando le relazioni spaziali fra gli oggetti e attribuendo un signi-

ficato semantico ad alcune loro particolari combinazioni, sia aumentare anche

le informazioni da recuperare e memorizzare in fase di analisi dell’immagine.

1.2 Cos’e l’etichettamento? 19

2 Cos’e l’etichettamento?

Per avere un sistema di image retrieval efficiente e bene che le immagini

stesse, che fanno parte di un database, siano caratterizzate da un contenuto

semantico ovvero da delle etichette di termini che ne possano denotare il loro

contenuto. Non ci si vuole piu accontentare solamente di una caratterizza-

zione sintattica, basata su feature di basso livello, bensı si necessita di avere

una caratterizzazione contenutistica. Per questo motivo si vuole cercare di

studiare un metodo che consenta di etichettare le immagini mediante con-

tenuti semantici in un modo che sia il piu possibile automatico. Prima di

presentare lo stato dell’arte su cio che e stato fatto nel mondo nell’ambito

dell’etichettamento automatico, e opportuno chiarire tutti i dettagli che ci

consentono di capire cosa significa gestire una fase di etichettamento.

Supponiamo di lavorare in ambito locale e di avere a disposizione un da-

tabase di immagini. Mediante il processo di etichettamento si vuole fornire

una caratterizzazione ad ogni immagine, attribuendole uno o piu significati

semantici. Tali contenuti possono essere espressi mediante una molteplicita

di forme: concetti testuali, etichette semantiche, triple RDF (Resource De-

scription Framework) come descritto in [1] etc. Le triple RDF, a differenza

dei semplici concetti testuali o delle etichette semantiche che si esprimono

mediante parole, consentono l’etichettamento grazie alla possibilita di arti-

colare frasi piu complesse in cui i semplici termini possono essere correlati

mediante delle relazioni. Una tripla potrebbe essere rappresentata, ad esem-

pio, in questo modo: “pecora bruca erba” oppure “gattino beve latte” etc.

In questo scenario i termini “pecora”, “erba”, “gattino” e “latte” rappresen-

tano i concetti semantici mentre “bruca” e “beve” le relazioni connesse alle

azioni svolte. Il processo di annotazione consiste, dunque, nell’attribuire dei

significati semantici ad un’immagine.

2.1 Etichettamento di immagini mediante keyword

L’etichettamento di immagini mediante keyword non e un’idea innovativa

nell’ambito dei sistemi di image retrieval in quanto, gia da tempo, si usa

associare alle immagini delle parole chiave, o keyword, definite dall’utente al

fine di descrivere l’immagine stessa.


Il metodo delle keyword, fino a poco tempo fa utilizzato in maniera manuale

(il lavoro di annotazione viene svolto da persone che idealmente sfogliano le

immagini una per una ed associano ad esse una descrizione appropriata) e

per questo motivo particolarmente time consuming, puo diventare effettiva-

mente molto potente se implementato nella giusta maniera, ma fino ad ora

e stata data molta liberta all’utente nella scelta della modalita del tipo di

annotazione da dare ad un’immagine, cosa che ha manifestato una serie di

problemi quali:

• la soggettivita dell’annotazione e nella scelta delle keyword;

• la presenza di ambiguita nelle annotazioni dovuta all’uso di vocabolari

mal costruiti in dotazione a chi si occupa di annotare le immagini o

addirittura inesistenti.

Al fine di rendere il piu possibile automatico tale processo di annotazione so-

no state studiate varie tecniche. Tutte queste tecniche prevedono, comunque,

un intervento utente anche se in maniera piu limitata ad agevole. Globalmen-

te i metodi adottati per inferire gli aspetti semantici di un’immagine sono il

relevance feedback e l’apprendimento. Il primo consiste nello sfruttare i giu-

dizi dati di volta in volta dall’utente in merito ai risultati di una query al fine

di capire quali immagini siano effettivamente rilevanti e quali no, mentre il

secondo ha lo scopo di addestrare il sistema ad annotare da solo le immagini

partendo da un training set (relativamente ridotto rispetto all’intero data-

base di immagini a disposizione) di immagini campione gia annotate prima

dall’utente per via manuale.

In Figura 1.2 e rappresentato l’ambiente di lavoro di un sistema di recupero

di immagini dotato di un modulo di relevance feedback. L’interfaccia utente

e composta da tre moduli particolari: l’interfaccia per immettere la query

(query interface), l’image browser attraverso cui l’utente puo prendere visio-

ne delle immagini che costituiscono il risultato e l’interfaccia di feedback. Da

notare la freccia circolare che indica come il processo di feedback puo essere

eventualmente ripetuto piu e piu volte al fine di aggiornare, dopo ogni itera-

zione, il giudizio dato dall’utente alle immagini restituite dal sistema di volta

in volta. Ogni implementazione specifica di questa struttura puo proporre i

propri algoritmi per rendere concreti i vari moduli, l’obiettivo in questa sede

1.2.1 Etichettamento di immagini mediante keyword 21

e quello di fare comprendere solo il funzionamento di base del feedback di

rilevanza.

Figura 1.2: Sistema che gestisce il recupero di immagini e che possiede un

modulo di Relevance Feedback.

Etichettamento a singola keyword

A questo punto e opportuno indicare che l’etichettamento puo avvenire me-

diante singola etichetta o mediante etichettamento multiplo. I due approcci

sono molto differenti.

Nel caso dell’etichettamento singolo l’idea e che l’utente presenta al sistema

una nuova immagine query da etichettare, il sistema spesso puo condurre

un’analisi basata su contenuto ragionando a livello di similarita di vettori di


feature di basso livello (colore, tessitura, forma etc. dell’immagine) associati

alle immagini o alle singole regioni delle immagini e il sistema stesso genera

un set di immagini simili all’immagine query. Dopo aver fatto un ranking delle

migliori immagini restituite, (quelle piu simili all’immagine query stessa) si

va a vedere quali di queste sono etichettate e si puo andare ad etichettare la

nuova immagine magari con l’etichetta che compare piu di frequente fra tutte

le immagini restituite come risultato della query. In ogni caso, all’immagine

e associata una sola etichetta legata al contenuto semantico dell’oggetto piu

rilevante presente in essa.

Un esempio di quanto detto e presentato in Figura 1.3.

Figura 1.3: Esempio di etichettamento a singola keyword.

1.2.2 Le ontologie di dominio 23

Etichettamento a multipla keyword

Legame fra etichetta - regione di segmentazione

Nel caso dell’etichettamento multiplo abbiamo un maggior grado di preci-

sione perche, ad ogni immagine, possiamo associare un numero variabile di

etichette, tante quante sono le regioni costitutive dell’immagine stessa. Il

processo di generazione delle etichette dipende molto dalla specifica imple-

mentazione che viene presentata nei vari approcci proposti in letteratura; in

ogni caso, in questo frangente diventa importantissimo avere un buon siste-

ma che sia in grado di segmentare in maniera opportuna l’immagine nelle

sue regioni costitutive e avere a disposizione buoni algoritmi che valutino le

similarita dei vettori di feature associate alle varie regioni.

Un esempio di quanto detto e presentato in Figura 1.4.

Legame fra set di etichette - immagine

Sempre relativamente all’ etichettamento multiplo potremmo avere il caso in

cui, ad ogni immagine, possiamo associare un numero variabile di etichette

non dipendente dal numero di regioni in cui puo globalmente essere segmen-

tata l’immagine stessa, ma dipendente da tecniche di analisi di frequenza e

di probabilita con cui le stesse etichette vanno ad annotare immagini simili

all’immagine query.

Un’idea intuitiva di come dovrebbe operare un approccio di questo tipo e

illustrato in Figura 1.5.

2.2 Le ontologie di dominio

Prima di collocare le ontologie di dominio nel nostro scenario di riferimento e

opportuno chiarire cosa queste ultime rappresentano ed i motivi per cui sono

state introdotte.

Un’ontologia e una struttura che consente di memorizzare i concetti in mo-

do gerarchico esprimendo le relazioni reciproche fra gli stessi, le regole, gli

assiomi, ed i vincoli specifici di dominio. L’ontologia lessicale per eccellenza

e WordNet.


Figura 1.4: Esempio di etichettamento multiplo con una keyword associata

ad ogni regione.

1.2.2 Le ontologie di dominio 25

Figura 1.5: Esempio di etichettamento multiplo con keyword associate alle

immagini e non alle singole regioni delle immagini stesse.


WordNet, di cui si parla in [2] e [3], e una rete semantica realizzata presso

l’universita di Princeton da un gruppo di ricerca guidato da George Mil-

ler che si basa su teorie psicolinguistiche sull’organizzazione della memoria

lessicale. Nel sistema, consultabile online [4], nomi verbi aggettivi e avverbi

sono organizzati in un insieme di sinonimi ognuno dei quali rappresenta un

concetto lessicale di base. L’ontologia WordNet e suddivisa, infatti, in queste

quattro categorie sintattiche.

L’etichettamento di immagini attingendo a termini, che sono classificati ge-

rarchicamente all’interno di una struttura ad albero, conduce a notevoli bene-

fici se comparata alla fase descritta precedentemente di annotazione manuale.

L’uso di un’ontologia porta a diversi benefici sia in fase di annotazione sia in

fase di ricerca:

• la persona addetta all’annotazione non deve inventarsi dal nulla i con-

cetti utilizzati per l’annotazione stessa (se l’ontologia e stata ben co-

struita e sufficiente scorrerla dalla cima dell’albero fino eventualmente

alle foglie navigando attraverso i concetti che piu si addicono al con-

tenuto espresso dall’immagine ed associando ad essa il significato piu

opportuno);

• mediante un approccio ontologico si possono descrivere le relazioni

esistenti fra gli oggetti e quindi aumentare e migliorare la base di

conoscenza;

• ci si puo basare su un uso dei termini standardizzato, evitando descri-

zioni soggettive e l’uso di omonimi (che diminuiscono la precision rate)

e di sinonimi (che diminuiscono la recall rate), evitando in generale le

ambiguita;

• spesso l’utente, all’atto di una ricerca, non sa esattamente cosa deside-

ra e si trova a fare ricerche in un database di immagini senza sapere

esattamente quale sia il dominio applicativo e senza conoscere le key-

word da usare per effettuare la ricerca. La ricerca basata su keyword

prese da un thesaurus non controllato non offre molti strumenti d’aiuto

all’utente al fine di guidarlo verso risultati significativi in quanto non

lo aiuta in nessuno dei tre seguenti aspetti:

- estrapolare le sue vere intenzioni e interessi;

- formulare adeguatamente la query;

1.3 Obiettivi per lo scenario di riferimento 27

- presentare nel modo migliore i risultati della ricerca accompagnandoli

con un insieme di altri risultati che, pur non soddisfacendo la query ini-

ziale, possono essere interessanti per l’utente in quanto semanticamente

collegati al vero risultato della ricerca (reccomendation).

• l’uso di un’ontologia puo, dunque, favorire una ricerca di tipo view ba-

sed : con essa l’utente puo scorrere le gerarchie dell’ontologia, come si

naviga attraverso le cartelle di un sistema operativo, esplorandole sem-

pre piu in profondita e scegliendo i concetti di interesse semplicemente

tramite un click del mouse limitando cosı la possibilita di inserire query

con termini errati che possono portare a risultati vuoti.

• Semantic browsing : una volta focalizzato il campo di interesse e re-

stituita, ad esempio, un’immagine come risultato, il modello ontologico

permette facilmente di trovare delle relazioni fra l’immagine selezionata

ed altre immagini. Tali immagini fra loro legate presentano, infatti, nel-

la propria annotazione, dei concetti che puntano allo stesso nodo della

gerarchia ontologica che le mette in relazione, dunque, da un punto di

vista concettuale.

L’approccio di tipo ontologico presenta molteplici aspetti positivi, ma e bene

sottolineare che usarlo al meglio richiede tanto piu lavoro nel definire l’on-

tologia e nella fase di annotazione delle immagini, quanto piu dettagliata e

l’ontologia e il livello di dettaglio e di precisione voluti. La migliore soluzione

a livello attuale prevede, dunque, di potersi avvalere di un meccanismo di an-

notazione delle immagini semi-automatico o automatico sfruttando le idee di

base di un supporto ontologico a livello di tassonomia di concetti. La presen-

za di interventi umani, per quanto e necessario che sia limitata, e comunque

sempre rilevante anche in tali tecniche e puo effettivamente manifestarsi in

diversi modi: e previsto l’intervento umano nel processo di annotazione du-

rante la fase di apprendimento del sistema oppure durante l’intervento di

relevance feedback come descritto precedentemente.

3 Obiettivi per lo scenario di riferimento

Lo scenario di riferimento, su cui si vuole cercare di riflettere nella presente

attivita di tesi e quello che prevede la possibilita di etichettare in maniera


semi-automatica un’immagine mediante una molteplicita di termini che pro-

vengono da tassonomie multiple.

Assodato che l’utilizzo delle sole feature di basso livello non risultano suffi-

cienti per consentire di fornire una buona e rilevante caratterizzazione dell’im-

magine dal punto di vista dei contenuti, abbiamo deciso di collocarci in uno

scenario che, pur essendo locale, prevede di operare mediante concetti seman-

tici. Si suppone, inoltre, che i termini utilizzati per etichettare l’immagine in

esame non facciano parte di una sola, unica tassonomia bensı possano essere

presi da differenti tassonomie gerarchiche di concetti. In questo scenario e

possibile prevedere dei legami, delle connessioni fra i termini che apparten-

gono a diverse tassonomie anche se locali. L’idea e sempre quella di avere un

database di immagini ampiamente popolato e di sfruttare l’etichettamento di

un training set, set di immagini campione, al fine di gestire l’etichettamento

globale, in maniera semi-automatica, di una qualunque immagine non ancora

etichettata.

Ci si puo domandare perche si desidera operare con uno scenario multi-

tassonomico e la risposta riguarda la possibilita di lavorare, con esso, in

maniera molto piu strutturata e di consentire, mediante l’utilizzo di mol-

teplici tassonomie, di stabilire dei legami, delle connessioni semantiche fra

diverse ontologie che potrebbero essere fisicamente collocate su nodi (peer

semantici) diversi. Si cerca di rendere modulare la struttura a livello locale

in modo da facilitare il mapping a livello distribuito.

Capitolo 2

Stato dell’arte

Prima di scegliere una precisa strada d’azione, risulta opportuno, in ogni

caso, valutare lo stato dell’arte attuale relativo ai processi di annotazione au-

tomatica e semi-automatica di immagini, soffermandosi sulle proposte piu in-

teressanti ed andando ad indagare quali aspetti rendono queste ultime adatte

per i fini che ci stiamo prefiggendo e quali altri aspetti vanno, invece, scartati

poiche non rilevanti in base agli obiettivi presentati nello scenario di riferi-

mento. Si e deciso di concentrare la ricerca sugli studi piu recenti che si sono

evoluti nel corso degli ultimi anni cercando, dapprima, di comprendere le

idee che stanno alla base degli approcci proposti e provvedendo, poi, a fare

una valutazione conservativa sui vantaggi e gli svantaggi connessi alla loro

applicazione in relazione al nostro scenario di riferimento. Tutto cio con la

consapevolezza che le tecniche che verranno riassunte nei paragrafi succes-

sivi sono solamente alcune, quelle ritenute piu significative, delle tante che

sono state esaminate e che fanno parte dello stato dell’arte. Fra quelle che, in

qualche modo, risultano rilevanti e che sono riportate dettagliatamente nello

stato dell’arte di [30], ritroviamo delle tecniche che in questa sede, per ragio-

ni di completezza, abbiamo deciso semplicemente di citare suddividendole in

due grossi filoni.

Fra gli approcci che si concentrano principalmente sull’etichettamento auto-

matico mediante multipla keyword possiamo elencare quelli proposti in [14],

[15], [16], [17], [18], [19] e [20].

Fra gli approcci che discutono di annotazione automatica e di recupero di

immagini basati su ontologie di dominio possiamo elencare quelli proposti in

30 Stato dell’arte

[21], [22], [23], [24], [25], [26], [27] e [28].

Questi sono gli obiettivi che si propone di raggiungere il presente capitolo.


Mixed-Media Graph

La tecnica proposta da [5] riguarda la presentazione di un approccio che

consente di andare ad annotare in maniera automatica qualunque tipo di

dato multimediale (immagini, contenuti audio, video etc.) sfruttando una

rappresentazione a grafo per gestire le correlazioni fra gli attributi presen-

ti a seconda del differente contesto applicativo in esame. Il loro obiettivo e

quello di creare un metodo unificatore che sia indipendente dal dominio ap-

plicativo, che sia in grado di esprimere correlazioni fra vettori di feature e

che possibilmente possa essere applicato a corpose collezioni di oggetti sia

in relazione al training set delle immagini campione annotate sia per quanto

concerne i possibili tempi di risposta forniti dal sistema stesso. Gli autori si

concentrano sul processo di annotazione automatica delle immagini per mo-

strare l’efficienza e l’efficacia dell’approccio proposto. L’innovazione di questo

approccio riguarda la possibilita di gestire un etichettamento multiplo delle

immagini usando, a basso livello, i legami, le relazioni di similarita fra le

regioni costitutive delle immagini per definire a quali immagini gia etichet-

tate accedere al fine di recuperare i termini che, piu di frequente, ricorrono

nell’annotazione con lo scopo di annotare una nuova immagine. Il numero di

etichette rimane, in ogni caso, svincolato dal numero di regioni in cui l’im-

magine puo essere effettivamente segmentata.

Si va a lavorare sulle immagini andando a costruirsi staticamente dapprima

un grafo, “Mixed-Media Graph” (MMG), relativamente ad un training set

di immagini campione gia etichettate. Il grafo ha tanti livelli quanti sono

gli attributi esaminati; ad esempio, nel caso delle immagini, il grafo sarebbe

costituito da tre livelli: il livello dell’oggetto-immagine (come primo attribu-

to), il livello delle regioni che segmentano un’immagine, e conseguentemente

dei vettori di feature ad esse associate, (come secondo attributo) e il livello

dei termini (come terzo attributo). La gestione del processo di annotazio-

2.1.1 Valutazioni 31

ne automatica viene effettuata in questo modo: viene selezionata dall’utente

un’immagine query, vengono estratte runtime le feature da ogni regione che

viene estratta dall’immagine query stessa e si applica l’algoritmo “Random

Walk with Restart” (RWR) per andare a recuperare le k regioni piu simili a

quella esaminata. RWR, il cui algoritmo viene dettagliato in [5], e una tec-

nica che viene utilizzata per calcolare l’affinita di un nodo “B” per un nodo

“A”. Esso opera in questo modo: avendo a disposizione un random walker

(camminatore casuale) si parte dal nodo “A” e si sceglie randomicamente uno

fra tutti i cammini disponibili di volta in volta per arrivare al nodo “B” ma,

prima di fare una scelta, con probabilita c, il random walker ritorna indietro

e riparte dal nodo “A”. Accedendo per similarita di regione si recuperano le

immagini a cui tali regioni appartengono e, a questo punto, si vanno a cattu-

rare tutti i termini utilizzati per etichettare tali immagini. Si fa un ranking

delle etichette utilizzate piu di frequente e si decide di andare a prendere, fra

quelle, le prime k per etichettare la nuova immagine. L’algoritmo che con-

sente di scoprire le correlazioni a modalita incrociata si chiama “Cross-modal

Correlation Discovery” (CCD) ed opera a livello matriciale.

Per una descrizione approfondita dei dettagli algoritmici, corredati anche di

esemplificazioni a riguardo, si rimanda al Capitolo 3.

1.1 Valutazioni

La tecnica presentata potrebbe rivelarsi utile per i nostri scopi, connessi all’e-

tichettamento semi-automatico di immagini, poiche prevede di operare sia a

livello sintattico, utilizzando a basso livello i vettori di feature che caratteriz-

zano ogni regione dell’immagine, sia a livello semantico ovvero consentendo

di associare all’immagine degli attributi legati al significato semantico e con-

cettuale che emerge dall’immagine stessa.

Inoltre si va oltre il banale etichettamento mediante singola etichetta e si

procede ad associare ad un’immagine un set di etichette ovvero si opera

nel contesto di un multiplo etichettamento. Quest’ultimo consente, inoltre,

di connettere l’etichetta non ad una particolare regione dell’immagine bensı

all’immagine nella sua totalita in modo da poterla caratterizzare anche me-

diante contenuti “astratti” non ricavabili direttamente dalle specifiche regioni

in cui l’immagine stessa e segmentata.


Risulta particolarmente significativa anche l’idea di effettuare una ricerca per

similarita su un sistema che e stato precedentemente organizzato fornendogli

una struttura a grafo (MMG) in cui tutto e modulare ed in cui i vari livelli

possono essere navigati mediante semplici ricerche fra attributi diversi.

Un’ulteriore pregio della tecnica proposta e connessa alla sua estrema eteroge-

neita: l’approccio puo essere, infatti, utilizzato per l’annotazione automatica

di un qualunque tipo di dato multimediale, una volta che l’esperto del domi-

nio ha deciso quale funzione di similarita utilizzare a seconda dello specifico

tipo di dato multimediale sia esso di tipo audio, video etc.

Il problema e che, se si pone l’accento su quelli che sono gli obiettivi del

presente lavoro di tesi ci si accorge che, in realta, tale approccio non risol-

ve il problema di come evitare la soggettivita di quella che, anche durante

la fase di training set, potrebbe essere un’annotazione manuale poiche non

si contempla la possibilita di appartenenza dei termini semantici a nessuna

ontologia. I termini sono liberi, non ci sono legami fra di essi. Dal momento

che non si parla di tassonomia e ovvio che non viene preso in considerazione

neppure uno scenario multi-tassonomico in cui potrebbe essere prevista la

possibilita di organizzare i concetti in differenti tassonomie di concetti e che

rappresenta un po’ il cuore dei nostri studi.

Globalmente si potrebbe pensare di trarre spunto da tutto cio che concerne

l’etichettamento gestito in modo semi-automatico mediante MMG, con la

consapevolezza di dover ragionare su come risolvere le probelmatiche a livel-

lo ontologico a causa della carenza che emerge in tale direzione da questo

approccio.


Multi-Modal Story-oriented video Summa-

rization

La tecnica proposta da [6] e molto simile, dal punto di vista delle tecni-

che utilizzate, a quella proposta dagli stessi autori in [5]. Ancora una volta

questi ultimi tendono a proporre un framework che puo essere utilizzato in

qualunque dominio applicativo e che sfrutta la costruzione di un grafo. Per la

2.2 Etichettamento semi-automatico medianteMulti-Modal Story-oriented video Summarization 33

presentazione dell’approccio si concentrano in particolar modo sui contenuti

video.

La tecnica MMSS consente di lavorare con un framework molto generale che

si pone come obiettivo quello di scoprire le correlazioni fra le diverse modalita

di dato (e.g. frame/term/logo) che vengono estratte dai contenuti video. Le

correlazioni incrociate fra queste differenti modalita sono, poi, usate sia per

fornire dei sommari concettuali dei contenuti video proposti, sia per operare

a livello di reperimento dei contenuti video stessi. MMSS scopre, infatti, le

correlazioni incrociate fra i differenti modi di esprimere i contenuti ed e in

grado non solo di fornire buoni sommari dei video che vengono proposti, ma

anche di operare in ambito di un efficiente reperimento, o video retrieval,

degli stessi. Il data set utilizzato e un programma per news televisive. Ogni

programma per news viene spezzettato in un set di shot a ciascuno dei quali

e associato un frame ed un set di parole (in generale solo nomi o term) ca-

ratterizzanti. L’informazione riassuntiva viene espressa mediante i logo.

Ancora una volta l’idea e quella di costruire un grafo, chiamato GMMSS,

utilizzando i termini, i frame ed i logo, come quello che viene proposto in Fi-

gura 2.1, e di navigarlo in vari modi mediante la tecnica Random Walk with

Restart (RWR), di cui si forniscono i dettagli algoritmici in [5] e [6], al fine

di catturare le informazioni rilevanti a seconda della modalita di ricerca che

deve essere compiuta. Il grafo e costituto da tre tipi di nodi (logo li, frame

fi e term ti) e due tipi di archi (quelli tratteggiati ovvero i “same-logo edge”

e quelli continui ovvero i “term-occurence edge”).

Dal punto di vista del reperimento di sommari (story summarization) l’idea

e quella di presentare il logo e, partendo da cio, il sistema sara in grado di

catturare tutti i frame corrispondenti a quel nodo logo gestendo una naviga-

zione del grafo che sfrutta i nodi termine. Al completamento della ricerca, il

sistema restituira non solo i frame, ma anche i termini corretti connessi ad

una ricerca basata su logo (mediante un ranking dei valori restituiti dall’ap-

plicazione del RWR).

Durante il reperimento di video, all’interno di sistemi di video retrieval, data

una query costituita da un set di termini, l’obiettivo e quello di cercare di

recuperare tutti frame che sono piu rilevanti in relazione a quella query. In

altre parole si vuole fornire un ordinamento di tutti gli shot in accordo alla


vicinanza che questi ultimi hanno in relazione ai termini di query. In generale

MMSS pone al top della lista quelli che sono effettivamente gli shot rilevanti.

Figura 2.1: Grafo MMSS contenente tre tipi di nodi (logo li, frame fi e term

ti) e due tipi di archi (quelli tratteggiati ovvero i “same-logo edge” e quelli

continui ovvero i “term-occurence edge”).

2.1 Valutazioni

La tecnica presentata e interessante poiche, come quella proposta in [5], con-

sente di operare su diversi livelli cercando di gestire in modo automatico sia

l’etichettamento sia il recupero di contenuti (in questo caso video).

Il framework proposto risulta in tutto e per tutto ortogonale al tipo di dato

multimediale preso in esame. Si puo valutare, infatti, che in [5] l’approccio

a grafo MMG era stato applicato efficientemente alle immagini, mentre in

questo caso, ovvero in [6], ci si concentra sui contenuti video anche se con-

cretamente le cose non differiscono di molto.

L’idea e sempre quella di trovare le relazioni incrociate fra i vari livelli del

grafo che si costruisce, sia esso MMG, se si sta lavorando con delle immagini,

oppure MMSS, se si sta lavorando con dei video. L’efficienza si trova quan-

do il grafo staticamente costruito viene navigato mediante il Random Walk

with Restart al fine di trovare i contenuti significativi dal cui ordinamento

vengono estratti i dati che il sistema e effettivamente in grado di restituire.

Diciamo che MMSS ci consente di rafforzare l’approccio basato su Mixed-

2.3 Organizzazione medianteDatabase Multi-Strutturali 35

Media Graph che, in realta, e probabilmente quello che piu ci interessa in

quanto il tipo di dato multimediale su cui abbiamo deciso di concentrarci

sono proprio le immagini anche se, dal punto di vista della modalita di co-

struzione del framework stesso, i due approcci procedono in maniera del tutto

analoga.

3 Organizzazione mediante

Database Multi-Strutturali

La proposta presentata in [7] e [8] riguarda la costruzione di un modello con-

cettuale che puo essere applicato ad una molteplicita di contesti differenti.

Lo scopo e quello di arrivare a fare delle interrogazioni a livello semantico

che consentano di estrarre dei dati a partire da semplici concetti organizzati

gerarchicamente mediante l’uso di molteplici tassonomie. Intuitivamente, per

comprendere i fondamenti del modello, si puo riportare un esempio.

Supponiamo di avere un’ampia collezione di articoli di giornale. Questi pos-

sono essere classificati in un certo numero di “dimensioni”:

• temporale: si collocano temporalmente i giornali in base a giorno-mese-

anno, se quotidiani, oppure mese-anno, se mensili, oppure settimana-

mese-anno, se settimanali etc.

• tipologica: articoli che potrebbero provenire da quotidiani o da giornali

settimanali o mensili ed, in questi casi, si va ad indagare la tipologia

di giornali: settimanali di economia, musica, sport etc. oppure mensili

con notizie di semplice intrattenimento.

• geografica: gli articoli possono riguardare fatti accaduti negli USA op-

pure in Europa e, se all’interno dell’Europa, potrebbero provenire dalla

Francia o dalla Germania o dall’Italia etc.

• contenutistica: ci possono essere articoli che parlano di guerra o di ca-

tastrofi naturali o di politica etc. Ciascuno di questi contenuti potrebbe

contenere delle sotto gerarchie.

Queste ovviamente sono solo alcune delle dimensioni che potrebbero essere

indagate ed, in ogni caso, ognuna di esse puo essere valutata secondo dif-

ferenti gradi di granularita. Ad esempio, la dimensione temporale che, da


sola, potrebbe essere interpretata come una dimensione numerica e puntifor-

me, puo essere, al contrario, organizzata gerarchicamente a seconda di quale

rappresentazione si decide di fornire ad essa stessa. Si potrebbe lavorare a

livello di intervalli temporali, oppure si potrebbe pensare ad una struttura

della data che preveda di descrivere il tempo inteso come insieme di secoli, i

secoli come insiemi di decenni, i decenni come insiemi di anni, gli anni come

insiemi di mesi, i mesi come insiemi di giorni e cosı via. Si vede chiaramente

che le altre dimensioni elencate (tipologica, geografica e contenutistica) sono

gia strutturate gerarchicamente.

Su database ampiamente popolati, in questo caso da documenti, e a fronte

di caratterizzazioni cosı dettagliate e ovvio che si possono fare delle query

molto ampie come ad esempio queste di seguito proposte:

• Quali sono i dieci argomenti piu comuni di tutta la collezione?

• Quali contenuti specifici sono diventati accesi argomenti di discussio-

ne relativamente alla guerra? Questi sottoargomenti sono presentati in

maniera diversa a seconda dei diversi tipi di giornale venduti in Europa?

Analizzando le query che vengono formulate, si puo notare come queste ope-

rano in particolare in base alla logica fuzzy, ovvero l’idea e che non esiste

mai un’unica risposta sicuramente corretta o sicuramente errata, ma ci sono

molte risposte intermedie valide. Il risultato di una query viene ottenuto ap-

plicando una procedura di ottimizzazione.

La proposta presentata concerne la definizione di “Database Multi-Strutturali”

(MSDB). I MSDB comprendono sia i dati multimediali (nell’esempio prece-

dente, articoli di giornale) sia le tassonomie di concetti intese come le varie

dimensioni in cui i termini sono organizzati in maniera gerarchica (nell’e-

sempio precedente, si parla di dimensione temporale, tipologica, geografica e

contenutistica).

Le gerarchie di concetti vengono rappresentate mediante dei “reticoli” (rap-

presentazione di ordinamenti parziali attuata su un set di elementi) e, su

tali reticoli, vengono ammesse varie operazioni quali meet, ovvero interse-

zione, la cui rappresentazione e ∧, e join, ovvero unione, la cui rappre-

sentazione e ∨, come operazioni binarie che godono delle proprieta com-

mutativa e associativa. Per ogni elemento a e b vale la seguente proprieta

a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. Il reticolo induce, inoltre, un ordine parziale

2.3 Organizzazione medianteDatabase Multi-Strutturali 37

tale per cui a ≤ b se e solo se a ∧ b = a. Dato un reticolo L, si puo scrivere

che a ∈ L se si vuole indicare che a e un elemento di L. Un reticolo si dice

dimensionato inferiormente e superiormente se dispone di due elementi bot-

tom (⊥) e top (>) grazie ai quali, comunque scelto un qualunque elemento

a, se si applica l’operatore di meet fra l’elemento a e l’elemento bottom viene

restituito in uscita quest’ultimo (a∧⊥ = ⊥), mentre se si applica l’operatore

di join fra l’elemento a e l’elemento top viene restituito in uscita quest’ultimo

(a ∨ > = >). In pratica, tutti i reticoli sono dimensionati ed e per questo

che si utilizza #(A) per indicare la cardinalita di A. Ad esempio, se stia-

mo operando nella dimensione geografica e facciamo il join di tutte le citta

europee ovviamente otterremo il sovraconcetto piu generale Europa. Se, al

contrario, stiamo operando nella dimensione temporale e facciamo il meet di

due intervalli temporali questo equivale a catturare l’intersezione fra i due

intervalli stessi.

Ogni dato multimediale puo essere connesso a piu termini di un reticolo;

globalmente, infatti, quando un oggetto e associato ad un concetto in un

reticolo, esso puo dire di essere associato anche ad ogni altro concetto piu

generale rispetto a quello in esame: ad esempio, un articolo che parla della

Francia e anche un articolo che parla dell’Europa poiche la Francia e una

nazione geograficamente contenuta in Europa.

Piu si lavora a livello gerarchicamente basso all’interno di un reticolo e piu si

pensa che i termini siano disgiunti fra loro. In realta e vero che se ad esempio

andiamo ad indagare dal punto di vista contenutistico “sport” e “politica”

sono due aree completamente disgiunte, ma e anche vero che potrebbero esi-

stere degli articoli connessi ad entrambi tali concetti: potremmo avere un

articolo di giornale che parla di un governatore che pratica, a livello agoni-

stico, bodybuilding.

Si opera, inoltre, a livello di creazione successiva di reticoli andando a prende-

re il prodotto fra sottoinsiemi di reticoli, e quindi di gerarchie, differenti. Ad

esempio, “giornali francesi” deriva dal prodotto della dimensione tipologica

con la dimensione geografica. Questo esempio ci mostra come, lavorando a

livello di prodotto di dimensioni, spesso si vanno a caratterizzare in maniera

piu specifica delle collezioni di dati piuttosto di fornirne una visione piu glo-

bale.


Un’ultima idea caratterizzante il modello e quella che prevede la definizio-

ne di “Pairwise Disjoint Collection” (PDC): un modo di suddividere un set

di documenti in parti concettualmente non sovrapponibili in modo tale che

ogni parte, singolarmente presa, puo essere facilmente descritta utilizzando

gli elementi di una particolare multi-dimensione. Ad esempio, una PDC puo

contenere sia “sport” sia “politica” entrambi appartenenti alla dimensione

tipologica dal momento che, se si tenta di attuare l’operatore di meet fra

questi concetti, cio che viene restituito e l’elemento bottom, ovvero questi

concetti non condividono altri sottoconcetti piu specifici.

Questo modello e utilizzato non solo per strutturare sia gli oggetti sia i con-

cetti facenti parte del sistema, ma anche per consentire la formulazione di

query capaci di indagare e restituire cio che e ritenuto rilevante. La query

viene formulata come un problema di ottimizzazione in grado di mappare i

set di oggetti in schemi di tipo PDC utilizzando varie tipologie di operazioni.

Le principali operazioni studiate sono:

• DIVIDE: questa operazione mostra come un insieme di oggetti si di-

stribuiscono su un set di dimensioni. L’obiettivo di tale operazione e

quello di restituire una PDC in cui i documenti sono partizionati nella

maniera piu equa possibile rispetto al set di dimensioni. Lavoriamo a

livello di partizione.

• DIFFERENTIATE: questa operazione consente all’utente di confron-

tare due insiemi differenti di documenti rispetto a un certo set di

dimensioni fissate. Lavoriamo a livello di confronto.

• DISCOVER: questa operazione consente di estrapolare dei pattern si-

gnificativi dai dati. Da questo punto di vista si cerca, attraverso una

fase di mining di catturare dei comportamenti rilevanti che emergono

dai dati stessi. Lavoriamo a livello di scoperta di pattern.

Per utilizzare questi operatori sono stati proposti due tipologie di algoritmi:

la prima tipologia e in grado di operare in ambito mono-dimensionale pro-

ponendo degli algoritmi esatti, l’altra e in grado di agire in ambito multi-

dimensionale ed, in questo contesto, di operare mediante degli algoritmi

approssimati.

2.3.1 Definizione di Database Multi-Strutturali 39

3.1 Definizione di Database Multi-Strutturali

Un database multi-strutturale (“Multi-Structural Database” o MSDB) e una

tripla di elementi (X, D, R) dove X = {x1, x2, ..., xn} rappresenta l’insieme

universo degli oggetti (o dei documenti per come vengono trattati dall’ap-

proccio proposto), D = {D1, D2, ..., Dm} indica il numero di dimensioni ed

R indica a quale documento appartengono gli elementi di ogni dimensione. Il

singolo elemento xi sara utilizzato come un semplice identificatore con l’idea

che un identificatore puo indifferentemente essere utilizzato per identificare

dati e metadati. Ogni dimensione Di e un reticolo dimensionato di concetti

e si assume che tutti i nodi del reticolo, utilizzati in tutti i reticoli, siano

distinti. Un vocabolario e V = ∪iDi include tutti i nodi del reticolo. La re-

lazione di appartenenza R ⊆ XxV indica che un dato oggetto fa parte di un

elemento del reticolo.

In maniera del tutto analoga si possono definire dimensioni multiple per avere

la stessa struttura di dimensioni singole. Per un insieme non vuoto D′ ⊆ D la

multi-dimensione MD(D′) e definita come segue: se D′ e un singleton allora

la multi-dimensione e semplicemente la dimensione di un singolo elemento,

altrimenti se D′ = {D1, D2, ..., Dd} allora MD(D′) e ancora un reticolo i cui

elementi sono {l1, ..., ld)|li ∈ Li} dove (l11, ..., l1d)∨(l21, ..., l

2d) = (l11∨l21, ..., l

1d∨l2d)

e la stessa cosa vale per l’operatore di meet. La relazione di appartenenza R

e, di conseguenza, estesa al fine di contenere la coppia (x, (l1, ..., ld)), con

x ∈ X, se e solo se essa contiene (x, li) per tutti gli i.

3.2 Definizione di Pairwise Disjoint Collection

Le collezioni “Pairwise Disjoint Collection” (o PDC) rappresentano un mo-

do di partizionamento di un set di documenti in parti concettualmente non

sovrapponibili in modo che ogni parte puo essere facilmente descritta uti-

lizzando gli elementi di una particolare multi-dimensione. Formalmente per

ogni multi-dimensione MD(D′) e per ogni set di elementi S = {l1, ..., ld}della multi-dimensione si puo affermare che S e un PDC se li ∧ lj = ⊥ per

tutti gli i, j con i 6= j.

Un PDC, in contrasto a cio che in generale rappresenta un set di cluster, puo

essere comunicato facilmente ed in maniera concisa all’utente poiche di quel-


lo esiste gia uno schema. Ognuna delle operazioni analitiche, che sono state

descritte precedentemente, prende la multi-dimensione e altre informazioni e

restituisce un PDC su una ben definita multi-dimensione utilizzando le altre

informazioni per determinare quale PDC dovrebbe essere restituito.

Un PDC si dice completo per un sottoinsieme X ′ ⊆ X di oggetti se, per ogni

x ∈ X ′, esiste qualche elemento l nel PDC tale che (x, l) ∈ R, il che signifi-

ca che ogni documento concettualmente appartiene allo stesso elemento del

PDC. Quando si dice che un PDC e completo lo si intende completo su tutto

X.

3.3 Valutazioni

Cio che viene presentato da questi autori e la possibilita di creare un modello

concettuale assolutamente generale che puo essere applicato in ambiti diversi

e contesti specifici. Si suppone di avere a disposizione degli oggetti, dei dati

che, in uno degli innumerevoli esempi applicativi proposti, sono degli articoli

di giornale che in qualche modo vengono catalogati, classificati grazie alla

presenza di innumerevoli tassonomie di concetti. L’idea e che i singoli dati

sono qualificati utilizzando una molteplicita di strutture, i cosiddetti Data-

base Multi-Strutturali e che, grazie a questa idea di strutturazione, si ha la

possibilita di introdurre un insieme di operatori che ci consentono di lavora-

re sui dati stessi utilizzando degli algoritmi esatti se operiamo su una sola

dimensione oppure degli algoritmi approssimati se stiamo operando su piu

dimensioni contemporaneamente. L’obiettivo e quello di organizzare i dati,

di restituire in uscita quelli che risultano essere i piu rilevanti, secondo una

logica piuttosto fuzzy, in base alle query che l’utente finale formula.

Gli autori propongono un set di operatori, ma se ne potrebbero costruire mol-

ti altri ad hoc in base a come si ritiene opportuno procedere nell’analisi dei

dati stessi. In questo caso si decide di creare un set di operatori che operano

o partizionando i dati rispetto alle dimensioni di interesse, o confrontando i

dati che sono stati classificati secondo certe dimensioni specifiche, o cercando

di estrarre dei pattern ricorrenti dai dati stessi.

Se noi cerchiamo di fare delle valutazioni qualitative in relazione all’approc-

cio proposto, ci accorgiamo come tale modello puo essere applicato al nostro

scenario di riferimento per quanto concerne la possibilita di mappare tutti


i concetti in differenti tassonomie gerarchiche. Operando in questo modo, i

nostri dati sono le immagini, come tipo di dato multimediale in esame, e

tutti i termini che, da un punto di vista contenutistico servono per fornire

una caratterizzazione di alto livello per l’immagine stessa, sono organizzati

secondo delle tassonomie gerarchiche di concetti. E opportuno precisare che

stiamo lavorando a livello di tassonomie e non di “schemi”. Con gli schemi,

infatti, arriveremmo a stabilire delle relazioni gerarchiche fra concetti con

significati diversi e disconnessi; con le tassonomie organizziamo, al contrario,

in maniera gerarchica concetti che sono fra loro legati da delle relazioni di

contenimento di tipo “... is a... ” (... e un... ) o, a volte, ... part-of... (... e una

parte di... ) come si mostra in Figura 2.2.

L’approccio, di cui sono stati delineati i tratti essenziali, non presenta una

tecnica per l’etichettamento automatico di immagini, ma fornisce piuttosto

un modello di piu alto livello che potrebbe essere preso in considerazione nella

fase in cui si decidera di proporre una soluzione per lo scenario di riferimen-

to iniziale. Tutto cio con la consapevolezza che l’approccio presentato non

opera sulle feature di basso livello connesse all’immagine mentre, in realta,

sarebbe bene proporre una soluzione globale per l’etichettamento che tenesse

in considerazione entrambi i fattori, sintattici e semantici.

Figura 2.2: Differenza organizzativa fra uno “Schema” ed una “Tassonomia”.


4 Etichettamento basato su apprendimento

mediante istanza multipla

La proposta presentata in [9] riguarda l’applicazione di una tecnica che con-

sente di annotare automaticamente un’immagine. Un’immagine puo essere

segmentata in un set di regioni ed ogni regione puo avere associati diversi

contenuti e rappresentare diversi significati semantici. Un primo passo consi-

ste, dunque, nel segmentare l’immagine in regioni ed estrarre, da ogni regione,

un vettore di feature di basso livello connesse al colore, alla tessitura, alla

forma etc.

A questo punto viene applicato un modello statistico, a partire da un training

set di immagini campione gia annotate, che consente di collegare le regioni

con le keyword per arrivare ad annotare una nuova immagine, facente parte

del testing set, non ancora etichettata. L’idea e ancora una volta che l’eti-

chetta deve essere connessa all’immagine e non alla singola regione in cui

l’immagine stessa viene segmentata. Qui pero si opera in modo differente

rispetto a cio che viene proposto con l’approccio a grafi Mixed-Media Graph.

Per comprendere intuitivamente come l’approccio opera si pensi di avere una

situazione come quella proposta in Figura 2.3. La colonna di sinistra mostra

tre immagini rappresentanti una “tigre” mentre la colonna destra mostra

le regioni in cui le varie immagini sono state segmentate utilizzando “tagli

normalizzati”. Per trovare la corretta corrispondenza fra la regione di un’im-

magine e il termine “tigre” una macchina, che e in grado di apprendere, deve

essere capace di differenziare le regioni che effettivamente rappresentano una

“tigre” da tutte le altre regioni che presentano del rumore.

A questo punto si propone di apprendere la corrispondenza fra le regioni

dell’immagine e le keyword di annotazione attraverso la tecnica “Multiple-

Instance Learning” (MIL). La tecnica MIL, variazione di una forma di ap-

prendimento supervisionato, ha il compito di apprendere un concetto dati

dei contenitori (bag) positivi o negativi di istanze. Ogni contenitore puo con-

tenere una molteplicita di istanze, ma un contenitore e etichettato come

“positivo” anche se una sola delle istanze in esso contenute riguarda quel

concetto. Un contenitore, al contrario, e etichettato come “negativo” solo se

tutte le istanze in esso contenute sono etichettate come negative in relazione

2.4 Etichettamento basato su apprendimentomediante istanza multipla 43

Figura 2.3: Si mostrano tre immagini rappresentanti una “tigre” (colonna

sinistra) e le loro regioni (colonna destra). Un gran numero di regioni ir-

rilevanti e rumorose, come “erba”, “acqua” e “cespuglio” fanno parte del

training set insieme alla keyword “tigre”.

al concetto in esame.

Concretizzando il tutto, si puo dire che ogni regione rappresenta un’istanza e

che il set di regioni che segmentano l’immagine stessa costituiscono un bag.

Si attribuisce ad un’immagine un concetto se almeno una regione dell’imma-

gine ha, ad essa associato, quel particolare significato semantico. Ad esempio,

sempre facendo riferimento alla Figura 2.3, la prima immagine e etichettata

con la keyword “tigre” ed e segmentata in 10 regioni. Queste 10 regioni rap-

presentano un “positive bag” per la keyword “tigre” ed, in questo “positive

bag”, ci sono solamente 2 istanze positive poiche solo 2 regioni sono rilevanti

per la parola “tigre”. Da questo punto di vista, se un’immagine e etichetta-

ta con un concetto ci si aspetta che almeno una regione di quell’immagine

riguardi quel particolare concetto anche se la segmentazione potrebbe non

essere perfetta. Un modo per risolvere il problema MIL e quello di esaminare

le distribuzioni delle istanze in modo da cercare un’istanza che sia vicina a

tutte le istanze contenute nei “positive bag” e che contemporaneamente sia

lontana da tutte le istanze contenute nei “negative bag”. Si deve identificare

un punto in cui c’e effettivamente la piu alta “Diverse Density” di istanze


positive.

Dopo che una certa “regione rappresentativa dell’immagine” e stata selezio-

nata da MIL per essere associata ad una specifica keyword, il problema di

annotazione di un’immagine viene interpretato come un problema di clas-

sificazione che viene risolto attraverso l’utilizzo di un framework Bayesiano

che opera appoggiandosi al concetto di clustering. L’idea e questa: dati tut-

ti i vettori di feature di tutte le regioni in cui l’immagine del “testing set”

non ancora etichettata puo essere segmentata, ci si deve chiedere qual e la

probabilita che tale immagine appartenga alla classe del termine i-esimo spe-

cificato. Tutto cio supponendo che le immagini che fanno parte del “training

set” siano state etichettate con un insieme di termini variabile e che siano

costituite, a loro volta, da regioni a cui sono associate delle feature di basso

livello. Il processo di Multiple-Instance Learning e stato riassunto in Figura

2.4.

Figura 2.4: MIL consente di predire la regione rappresentativa di un’immagine

piu probabile, connessa ad uno specifico significato semantico, a partire dalle

immagini rilevanti e da quelle irrilevanti facenti parte del training set.


4.1 Valutazioni

Cercando di collocare questo approccio all’interno del nostro scenario di ri-

ferimento, ci rendiamo conto che e possibile utilizzare questa tecnica per la

gestione di una fase di etichettamento semi-automatico di immagini poiche

l’approccio prevede di operare sia a livello sintattico (utilizzando a basso li-

vello i vettori di feature che caratterizzano ogni regione dell’immagine) sia

a livello semantico, ovvero consentendo di associare all’immagine degli attri-

buti legati al significato concettuale che emerge dall’immagine stessa.

Inoltre, si va oltre il banale etichettamento mediante singola etichetta e si

procede ad associare ad un’immagine un set di etichette, ovvero si opera nel

contesto di un etichettamento multiplo. Quest’ultimo consente di connettere

l’etichetta non ad una particolare regione dell’immagine bensı all’immagine

nella sua totalita. Il problema e che, nella tecnica proposta, cio che risul-

ta cruciale e l’identificazione della regione rappresentativa dell’immagine. Se

quest’ultima non viene identificata in maniera corretta tutta l’intera fase di

annotazione non va a buon fine.

Un’ulteriore problematica e connessa alla possibilita di etichettare un’imma-

gine mediante dei concetti “astratti”. Questo aspetto nasce dal fatto che la

tecnica proposta riesce a lavorare meglio la dove le feature sono molto carat-

terizzanti, ad esempio, se si deve riconosce l’immagine di una “tigre” nella

savana, mentre non riesce ad annotare correttamente cio che e identificato da

feature piu piatte come ad esempio quelle che possono rappresentare l’imma-

gine che rappresenta una “folla di gente”. E vero anche che “folla di gente”

rappresenta un concetto abbastanza astratto.

Tutto si complica ulteriormente se si prende in considerazione il fatto che in

realta, tale approccio non risolve il problema di come evitare la soggettivita

nell’annotazione, poiche non si contempla la possibilita di appartenenza dei

termini semantici a nessuna ontologia. I termini sono liberi, non ci sono le-

gami fra di essi. Dal momento che non si parla di tassonomia e ovvio che

non viene preso in considerazione neppure uno scenario multi-tassonomico in

cui potrebbe essere prevista la possibilita di organizzare i concetti in diffe-

renti tassonomie di concetti e che rappresenta un po’ il cuore dei nostri studi.


5 Etichettamento automatico basato

su selezione di feature

La proposta presentata in [10] opera cercando di etichettare automaticamen-

te un set di immagini andando a lavorare sulle feature di basso livello, ovvero

proponendo degli algoritmi di selezione di feature a cui sono stati attribuiti

dei pesi.

L’idea e che se un utente fa una query su un database con l’intezione di farsi

restituire dal sistema in uscita tutte le immagini contenenti delle tigri, e suffi-

ciente che lui faccia una query con la keyword “tigre” al fine di ottenere come

risultato cio che desidera. In realta, ogni immagine puo essere segmentata in

tante regioni a ciascuna delle quale idealmente puo corrispondere uno o un

set di concetti. Per questo motivo si puo pensare di rendere il sistema molto

piu sofisticato se pensiamo, ad esempio, alla possibilita di farci restituire in

uscita da esso non tanto le immagini che contengono delle tigri quanto piu

le immagini che contengono “tigre”, ma che non contengono delle regioni di

segmentazione che si riferiscono a “ruscello”. Per far cio si deve operare sia

segmentando l’immagine nelle sue regioni significative, dette anche visual to-

ken, sia determinando le correlazioni fra le keyword e i visual token stessi.

Per gestire la segmentazione si utilizzano i “tagli normalizzati” che consen-

tono di suddividere un’immagine in varie regioni a ciascuna delle quali viene

fatto corrispondere un vettore di feature ovvero di caratteristiche di basso

livello quali colore, tessitura, forma etc.

A questo punto si deve capire come connettere le keyword alle varie regio-

ni di segmentazione. E possibile che una stessa regione sia condivisa da piu

immagini, di conseguenza si opera mediante una fase di clustering al fine di

raggruppare le regioni simili per generare un set finito di blob-token. La pre-

messa e che, se alcune regioni sono identiche, esse apparterranno allo stesso

cluster. Per questo motivo e necessario dapprima raggruppare, mediante una

fase di clustering, le regioni simili in modo da formare dei blob-token consi-

stenti, poi si deve analizzare il legame fra le etichette e i blob-token. Per la

creazione dei blob-token, lo stato dell’arte attuale prevede di utilizzare degli

algoritmi di clustering quali k-means che operano su vettori di feature ad alta

dimensionalita e che assegnano uguale peso a tutte le dimensioni. Proprio a

2.5 Etichettamento automatico basatosu selezione di feature 47

causa della dimensionalita, le matrici che lavorano sui dati diventano troppo

sparse e le misure di distanza fra i vettori di feature stessi perdono sempre

piu di significativita tanto che il risultato del clustering spesso viene falsifica-

to. Gli autori propongono, dunque, un meccanismo di selezione delle feature

in modo da attribuire alle stesse un peso. Ad esempio, per la keyword “pal-

la” la forma intesa come feature sara sicuramente molto piu rilevante della

feature colore o della feature tessitura, d’altro canto per la keyword “rosa”

risultera invece dominante la feature colore. L’idea e quella di assegnare run-

time ad ogni feature connessa ad ogni cluster di regioni un peso in accordo a

quanto quella feature risulta rilevante per quel particolare raggruppamento.

Per fare cio loro propongono di utilizzare un metodo che stima tale rilevanza

mediante l’analisi di istogrammi. Per determinare il legame fra le keyword e

i blob-token si applicano dei modelli statistici che stimano la corrisponden-

za fra ogni coppia di keyword e cluster di regioni, poi si va a costruire una

matrice WxB di probabilita dove W indica il numero totale di keyword e B

indica il numero totale di blob-token. Tale matrice sara riempita basandosi

su dei parametri di conteggio della frequenza con o senza l’attribuzione di

pesi, tecniche di Singular Value Decomposition e l’applicazione finale di un

algoritmo EM. A questo punto risulta banale determinare la corrispondenza

fra keyword e blob-token utilizzando la massimizzazione della probabilita o

dei pesi.

Un esempio di come si articola la corrispondenza fra gli oggetti di un’imma-

gine e le keyword ad essi associate viene presentato in Figura 2.5.

Per accrescere l’accuratezza dell’annotazione si puo cercare di trovare la cor-

rispondenza fra oggetti vicini nelle immagini considerando il contesto. Ad

esempio, due oggetti potrebbero rivelarsi pressoche indistinguibili utilizzan-

do come feature il colore (e.g., cielo e mare), ma un’indagine compiuta sugli

oggetti confinanti, oppure sul contesto, potrebbe aiutare a risolvere questa

ambiguita (e.g., se c’e un aereoplano molto probabilmente si stara parlando

di cielo). Globalmente, dunque, per gestire l’annotazione automatica si cal-

cola la distanza fra l’oggetto rappresentato da una determinata immagine e

tutti i centroidi dei vari cluster blob-token e si va a rappresentare l’oggetto

stesso con la keyword relazionata al blob-token piu vicino.


Figura 2.5: Corrispondenza fra gli oggetti di un’immagine e le loro keyword.

5.1 Valutazioni

Cercando di collocare questo approccio all’interno dello scenario di riferimen-

to, ci si rende conto che e possibile utilizzare questa tecnica per la gestione di

una fase di etichettamento semi-automatico di immagini poiche l’approccio

prevede di operare sia a livello sintattico (utilizzando a basso livello i vettori

di feature che caratterizzano ogni regione dell’immagine), sia a livello seman-

tico (consentendo di associare all’immagine degli attributi legati al significato

concettuale che emerge dall’immagine stessa).

Si opera, anche in questo caso, in un contesto di etichettamento multiplo

associando ad un’immagine una molteplicita di termini caratterizzanti.

Neppure con tale approccio, pero, si risolve il problema di come evitare la

soggettivita nell’annotazione, poiche non si contempla la possibilita di far

derivare i termini semantici da nessuna ontologia. I termini sono liberi, non

ci sono legami fra di essi. Dal momento che non si parla di tassonomia e

ovvio che non viene preso in considerazione neppure uno scenario multi-

tassonomico in cui potrebbe essere prevista la possibilita di organizzare i

concetti in differenti tassonomie di concetti e che rappresenta un po’ il cuore

dei nostri studi.

E vero che si opera a livello probabilistico, ma e anche vero che questa propo-

sta si pone come obiettivo quello di connettere gli oggetti (o meglio le regioni)

che caratterizzano un’immagine e le feature di basso livello, caratterizzanti le

singole regioni in cui l’immagine stessa viene segmentata, utilizzando come

2.6 Fusione di contesto, contenutoed ontologia semantica 49

strumento intermedio le keyword. In cio consiste la vera innovazione da cui

si potrebbe trarre spunto per automatizzare il processo di etichettamento.

6 Fusione di contesto, contenuto

ed ontologia semantica

Una proposta particolarmente interessante e quella presentata in [11].

Gli autori descrivono un framework probabilistico che utilizza i diagrammi di

influenza per fondere molteplici tipologie di metadati per gestire l’annotazio-

ne di fotografie. EXTENT fonde insieme informazioni connesse al contesto,

o context, (e.g., localita, tempo, parametri della macchina fotografica), al

contenuto, o content, dell’immagine (e.g., le feature visuali che emergono

dall’immagine stessa) e all’ontologia semantica in modo molto stretto. Si uti-

lizzano poi i vincoli causali per codificare sia i legami fra le variabili sia i

legami fra le variabili e le etichette semantiche.

Affinche gli utenti possano sia organizzare in maniera piu strutturata le im-

magini, sia ricercarle con piu facilita e necessario andare a caratterizzare

ogni immagine con delle etichette semantiche indicanti informazioni di tem-

po (quando), di persone (chi), di localita (dove), di punti di riferimento (cosa

si rappresenta) e di eventi (in generale, inferiti da tutte le informazioni pre-

cedenti). EXTENT fonde context, content e ontologia semantica insieme in

modo da generare delle etichette semantiche con cui le immagini possono

essere sia organizzate sia ricercate.

Identificare l’informazione connessa alla localita ed al tempo e banale in quan-

to ogni macchina fotografica fornisce l’informazione relativa all’istante in cui

la fotografia e stata scattata mentre l’informazione sulla localita puo essere

inferita utilizzando i dati trasmessi da un GPS. Il problema si ha nel cattura-

re le informazioni connesse a chi compare nella foto e a che cosa quest’ultima

rappresenta: e necessario, dunque, recuperare altre informazioni connesse al

context ed al content della foto. Le informazioni relative al contesto (con-

text), fornite dalla macchina fotografica possono essere suddivise in tempo

(time), localita (location), parametri della macchina (camera parameters) e

profilo utente (user profile). Le informazioni relative al contenuto (content)


riguardano le caratteristiche di basso livello che sono estratte dall’immagine

stessa e possono essere suddivise in due categorie: holistic perceptual feature

(e.g., forma, colore, tessitura etc. di un’ immagine) e local perceptual feature

(e.g., bordi e punti salienti delle regioni o degli oggetti che fanno parte di una

foto). Un’altra importante sorgente di informazione riguarda la relazione fra

le label semantiche, indicata col nome di semantic ontology.

Per capire il funzionamento, ad alto livello, dell’approccio proposto si riporta

di seguito un esempio. Supponiamo di avere due etichette come “outdoor” (in-

dica una foto scattata all’esterno) e “sunset” (indica una foto rappresentante

un tramonto). L’etichetta “outdoor” puo essere dedotta da alcune informa-

zioni di contesto quali, ad esempio, la lunghezza focale oppure le condizioni

di luce, mentre l’etichetta “sunset” puo essere dedotta da informazioni sul

tempo e sulla localita. Siamo in grado di dire che una foto rappresentante un

tramonto e di sicuro un esterno, ma non viceversa. Considerando, dunque,

le relazioni semantiche fra le etichette, EXTENT puo utilizzare le informa-

zioni di contesto in modo transitivo. A questo punto EXTENT mappa un

diagramma di influenza per attuare la fusione e l’inferenza semantica.

Le variabili che compaiono nel diagramma possono essere sia variabili deci-

sionali (decision variable) ovvero cause, sia variabili di probabilita (chance

variable) ovvero gli effetti. Dal punto di vista dell’annotazione di immagini

le decision variable sono il tempo, la localita, il profilo utente, i parametri

connessi alla macchina fotografica e le feature visuali, mentre le etichette

semantiche indotte sono le chance variable. Il diagramma di influenza ha il

compito di connettere i due tipi di variabili mediante degli archi pesati in base

alla forza esistente fra la causa e l’effetto stesso (“causal strength”). Riguardo

la costruzione del diagramma va ricordato che devono essere relazionati due

aspetti, ovvero la conoscenza del dominio ed i dati. In generale, pero, cercare

di apprendere dai dati un modello grafico probabilistico di questo tipo e un

problema NP-hard. Per il contesto in esame sono gia molte le relazioni esi-

stenti a livello di conoscenza di dominio, per questo motivo la sola relazione

causale che effettivamente deve essere appresa e quella che connette il conte-

sto/contenuto alle etichette semantiche. La Figura 2.6 mostra il diagramma

di influenza appreso per le due etichette semantiche di cui si e parlato so-

pra, ovvero “sunset” e “outdoor” vengono generate a partire dalle variabili


decisionali una volta definite le relazioni di causa ed effetto. Oltre agli archi

che mostrano le relazioni causali fra variabile-variabile ed etichetta-variabile,

il diagramma mette in evidenza come e possibile codificare la relazione fra

“sunset” e “outdoor” ovvero fra le etichette semantiche stesse.

Figura 2.6: Esempio di diagramma di influenza.

6.1 Valutazioni

Senza esserci addentrati nei formalismi legati alla presentazione dell’approc-

cio, ci siamo resi conto di quanto questa proposta possa essere vista come

innovativa poiche la sua idea di base parte dalla considerazione che non e

possibile ne etichettare in maniera efficiente, ne generare un buon sistema di

image retrieval, se non si fondono insieme varie “dimensioni” di indagine dei

dati, vale a dire quella del context, quella del content e quella del semantic


ontology.

Nel modello le dimensioni sono interpretate dalle variabili decisionali, ovvero

dalle informazioni che caratterizzano l’immagine a livello di contenuto e di

contesto. In realta queste dimensioni sono flat poiche sono viste come dati

che vengono in qualche modo recuperati dalla macchina fotografica o da in-

formazioni catturate mediante GPS.

Si potrebbe pero pensare, applicando questo approccio al nostro scenario

di riferimento, di utilizzare le dimensioni come strutture tassonomiche. Ad

esempio, l’informazione di contesto, connessa alla localita, potrebbe essere

vista come una tassonomia di concetti geografici oppure, quella legata al

tempo, potrebbe essere vista come una gerarchia di concetti temporali in

grado di mappare la data di riferimento e cosı via. Anche senza lavorare a

livello di diagramma di influenza, si potrebbe pensare di mappare delle “re-

lazioni” fra le varie dimensioni tassonomiche in modo da dare dei criteri per

capire come andare ad etichettare correttamente un’immagine. Un dato di

fatto e che, in generale, ogni immagine ha un soggetto dominante. Se stiamo

parlando di animali e difficile che in una stessa immagine siano rappresentati

contemporaneamente una mucca, un cavallo ed una tigre, per cui concettual-

mente si potrebbe stabilire che dalla tassonomia degli animali sia possibile

estrarre un solo concetto alla volta per andare ad annotare un’immagine, se

questa contiene gli animali in essa rappresentati.

A basso livello si potrebbe lavorare con similarita di feature, mentre ad alto

livello si potrebbe pensare di stabilire delle relazioni ad hoc per lavorare sulle

tassonomie in modo da attuare piu fasi di raffinamento successive in modo da

etichettare l’immagine in modo non ridondante o scorretto. Se un’immagine

dovesse essere etichettata con la keyword “tigre”, si dovrebbe essere in grado

di capire, inoltre, che non e possibile etichettare la stessa immagine con la

label “polo nord” poiche difficilmente una tigre potrebbe vivere al di fuori

della “savana”.

Queste ed altre considerazioni ci aiutano a capire che le idee proposte da

questo approccio non sono del tutto scorrette poiche ci potrebbero consen-

tire, variandole ed applicandole al nostro scenario, di operare sia a livello di

etichettamento multiplo utilizzando uno scenario multi-tassonomico sia con-

sentendo di integrare l’estrazione delle feature dalle immagini in modo da

2.7 Ricerca di similarita basata su connessioni di un grafo 53

avere linee guida nella fase di etichettamento successiva.

7 Ricerca di similarita basata su connessioni

di un grafo

La proposta presentata in [12] apparentemente sembra non fornirci degli

spunti utili per cio che concerne l’ambito dell’etichettamento automatico di

immagini. In realta essa presenta un insieme di algoritmi scalabili che posso-

no essere applicati a grafi estesi, ovvero costituiti da una grossa molteplicita

di vertici in ambito distribuito, con l’obiettivo di catturare le informazioni di

similarita nascoste in una struttura a link ipertestuali come quella del web.

Le similarita fra i vertici sono computate utilizzando delle funzioni quali, ad

esempio, SimRank, di cui si parla diffusamente in [13], ad altre sicuramente

piu innovative quali PSimRank, ovvero una variante della versione prece-

dente. I metodi sono presentati in un framework piu generale che raccoglie

algoritmi di similarita basandosi sul metodo “Monte Carlo”.

L’argomento che risulta sicuramente piu rilevante discutere, dopo aver ana-

lizzato l’articolo nella sua totalita, riguarda la presentazione di come viene

calcolata la similarita fra due nodi in un grafo utilizzando l’algoritmo PSim-

Rank come variante della versione Minimax SimRank.

L’algoritmo SimRank proposto da [13] in generale consente di calcolare la si-

milarita fra i nodi che costituiscono un grafo basandosi globalmente sull’idea

intuitiva che “due oggetti sono simili se sono referenziati da oggetti a loro

volta simili”. Il caso base prevede il confronto di un oggetto con se stesso

ed, in tal caso, il massimo punteggio (score) di similarita assegnato risulta

1. In generale lo score che viene computato e sempre un valore compreso fra

0 ed 1, dove 1 rappresenta il massimo grado di similarita e 0 rappresenta il

massimo grado di dissimilarita. Dati due oggetti a e b, la similarita fra i due

oggetti puo essere indicata con s(a, b) ∈ [0, 1].

Supponiamo di avere un grafo G costituito da un insieme di vertici e di pren-

dere in considerazione uno qualunque di tali vertici, ad esempio v. Si denota

con I(v) e con O(v), rispettivamente, il set di archi entranti (in-neighbors)

o uscenti (out-neighbors) dal nodo v. Individualmente gli archi entranti si


indicano con Ii(v) con 1 ≤ i ≤ |I(v)| mentre gli archi uscenti si indicano con

Oi(v) con 1 ≤ i ≤ |O(v)|.La versione originaria del SimRank, andando oltre i dettagli rappresentativi,

presenta alcuni problemi che possono essere evidenziati in maniera intuitiva

grazie ad un esempio. Supponiamo di avere a disposizione due portali web

molto popolari. Molti utenti si collegano a pagine simili contenute sui diversi

portali, ma queste pagine non sono indicate come simili utilizzando l’algorit-

mo SimRank. Un caso estremo puo essere rappresentato in Figura 2.7 in cui

sono rappresentati due differenti portali, ad esempio u e v che sono rappre-

sentati come nodi e che hanno lo stesso numero di archi entranti, supponiamo

k. Nonostante le k pagine possano avere una rappresentazione del tutto dis-

simile dal punto di vista dei link, l’idea e che si vorrebbe poter indicare u e

v come simili analizzando il numero di link entranti in tali nodi. Sfortuna-

tamente da questo punto di vista SimRank opera in maniera assolutamente

controintuitiva visto che la funzione di similarita siml(u, v) = c.(1/k) con-

verge a zero per valori crescenti di k che sono in realta gli archi entranti in

entrambi i nodi u e v.

Figura 2.7: Caso di fallimento di SimRank: le pagine u e v hanno k link

entranti comuni in esse, ma la similarita computata utilizzando SimRank

risulta, erroneamente, molto bassa (pari a 1/k).

A fronte di cio si definisce PSimRank come la funzione di distanza suppo-

sta (f-meeting distance) per far incontrare due camminatori casuali (random

walk) che non sono indipendenti, come accadeva per il SimRank, ma che so-

no accoppiati e di conseguenza, in ogni coppia, l’uno puo rintracciare l’altro

molto piu facilmente. La problematica emersa per il SimRank viene risolta

consentendo ai random walk di incontrarsi con una probabilita che e tanto

piu alta quanto piu ciascuno di loro e vicino all’altro: i due random walk,

2.7 Ricerca di similarita basata su connessioni di un grafo 55

posti uno sul vertice u′ ed uno sul vertice v′, procederanno verso lo stesso

vertice con una rapidita (anche in un unico step) che e connessa al fattore

probabilistico rappresentato dal coefficiente di Jaccard |I(u′)∩I(v′)||I(u′)∪I(v′)| che opera

in funzione di quelli che sono gli archi effettivamente entranti nei nodi u′ e

v′, ovvero I(u′) e I(v′).

Definizione di PSimRank

PSimRank e la funzione di distanza supposta (f-meeting distance) per far in-

contrare due camminatori casuali con f(t) = ct. Per ogni vertice u il random

walk Xu percorre l step uniformi ed indipendenti sul grafo partendo dal vertice

u. Per ogni coppia di vertici u, v e dato un istante temporale t si assume che i

random walk siano rispettivamente nella posizione iniziale Xu = u′ Xv = v′.

Da questo momento in poi si puo supporre che:

• con probabilita pari a |I(u′)∩I(v′)||I(u′)∪I(v′)| entrambi raggiungano lo stesso vertice

scelto uniformemente fra quelli di I(u′) ∩ I(v′);

• con probabilita pari a |I(u′)\I(v′)||I(u′)∪I(v′)| il random walk Xu si fermi in uno dei

vertici compresi in I(u′) \ I(v′) mentre il random walk Xv si fermi in

un vertice scelto indipendentemente fra quelli di I(v′);

• con probabilita pari a |I(v′)\I(u′)||I(u′)∪I(v′)| il random walk Xv si fermi in uno dei

vertici compresi in I(v′) \ I(u′) mentre il random walk Xu si fermi in

un vertice scelto indipendentemente fra quelli di I(u′).

Mediante PSimRank gli score possono essere calcolati mediante delle itera-

zioni che propagano le similarita su tutte le coppie degli archi entranti in un

nodo esattamente come accadeva per SimRank. Le iterazioni fatte con PSim-

Rank prevedono l’utilizzo di un algoritmo esatto quadratico organizzato in

vari passi.

Si denota con τu,v l’istante in cui i random walk Xu e Xv si incontrano per la

prima volta facendo iniziare il loro cammino dai vertici u e v. Ovviamente,

τu,v = ∞ se i camminatori non si incontrano mai. A questo punto gli score,

calcolati lungo un cammino di lunghezza l, possono essere espressi per defi-

nizione come psiml(u, v) = E(cτu,v). Risulta banale valutare che, se u = v,

allora psim0(u, v) = 1 altrimenti psim0(u, v) = 0 all’istante iniziale. Appli-

cando la legge della totale aspettativa a partire dal primo step di cammino


seguito da Xu e Xv e tenendo conto dello scorrere del tempo possono essere

mappate le seguenti iterazioni per il SimRank:

psiml+1(u, v) = 1, ifu = v;

psiml+1(u, v) = 0, ifI(u) = 0orI(v) = 0;

psiml+1(u, v) = C.[|I(u) ∩ I(v)||I(u) ∪ I(v)|

.1+

+|I(u) \ I(v)||I(u) ∪ I(v)|

.1

|I(u) \ I(v)|.|I(v)|∑

u′∈I(u)\I(v),v′∈I(v)

psiml(u′, v′)+

+|I(v) \ I(u)||I(u) ∪ I(v)|

.1

|I(v) \ I(u)|.|I(u)|∑

v′∈I(v)\I(u),u′∈I(u)

psiml(u′, v′)]

7.1 Valutazioni

Andando oltre quelli che, per i nostri fini, risultano dettagli non troppo utili

o significativi, abbiamo deciso di presentare anche questo approccio poiche

ci potrebbe essere d’aiuto in fase di etichettamento automatico per cercare

di valutare la similarita fra i concetti in un grafo di termini. Al di la di un

modello risolutivo per l’etichettamento automatico, e sembrata buona l’idea

di mettere a confronto differenti algoritmi di ricerca di similarita (SimRank

e PSimRank) poiche questi ci potrebbero servire per valutare quanto ogni

coppia di termini puo essere ritenuta simile sfruttando le indicazioni che

abbiamo a disposizione ovvero la presenza di un training set di immagini

campione gia etichettate in un certo modo utilizzando un insieme definito di

termini appartenenti ad esempio ad una molteplicita di tassonomie differenti.

Capitolo 3

Proposta per l’etichettamento

automatico di immagini

Dopo avere valutato attentamente la maggior parte delle proposte ad oggi

presentate per risolvere la problematica di etichettamento automatico di im-

magini, connessa alla possibilita di utilizzare uno scenario multi-tassonomico

da cui attingere per identificare i concetti semantici, e opportuno cercare di

fornire una formalizzazione del modello che rappresenta lo scenario di riferi-

mento per il presente lavoro di tesi.

Il presente lavoro di tesi si pone infatti, come obiettivo primario, quello di

valutare la strada scelta durante l’attivita di tirocinio curriculare, di cui e

fornita una descrizione dettagliata in [30], in modo da migliorare la qualita

globale dell’annotazione. La strada scelta e stata, infatti, in grado di presen-

tare una molteplicita di vantaggi, ma anche un insieme di problematiche che

potrebbero essere risolte applicando tecniche per un successivo raffinamento.

Nel presente capitolo si cerchera, dapprima, di fornire una formalizzazione

dello scenario di riferimento in cui si e deciso di operare, poi si descrivera

brevemente l’approccio che si e scelto di seguire durante l’attivita di tiro-

cinio curriculare, i cui dettagli sono proposti in [30], analizzando i vantaggi

e gli svantaggi da esso apportati. A questo punto verranno presentate le

caratteristiche relative alla proposta del nuovo approccio di etichettamento

automatico di immagini. Si fornira, infine, la formalizzazione degli algoritmi

creati e verranno analizzati e valutati i vantaggi da esso introdotti.

58Proposta per l’etichettamento


1 Scenario principale

Supponiamo di avere una situazione iniziale come quella presentata in Figu-

ra 3.1 e in Figura 3.2. Supponiamo di avere un database DB ampiamente

popolato contenente I1, ..., In immagini. Supponiamo che una parte di queste

immagini (e.g. circa 1/3 dell’intero database DB), quelle che costituiscono il

cosiddetto training set (TrS) di immagini campione, siano state etichettate

offline.

L’idea e che un utente esterno, che accede all’interfaccia di interrogazione,

puo selezionare una qualunque delle immagini non ancora etichettate, ovvero

quelle che costituiscono il cosiddetto testing set (TeS), e chiedere al sistema

di gestire una fase di etichettamento automatico dell’immagine stessa. Si

vuole cercare di automatizzare il piu possibile quello che un tempo era un

puro processo di annotazione manuale per cercare di far fronte al problema

della soggettivita dell’annotazione cercando di avere un sistema in grado di

generare etichette il piu possibile corrette in modo automatico.

Tutto cio avendo la consapevolezza di poter lavorare su due dimensioni ben

precise: quella delle feature f1, f2, ..., fh (h indica la dimensione del vettore

di feature, in genere una trentina di entry), ovvero delle caratteristiche di

basso livello che sono associate ad ogni singola regione dell’immagine (e.g.,

colore, tessitura, forma etc.), e quella delle etichette o keyword semantiche

K1, K2, ..., Kk che devono essere utilizzate per etichettare l’immagine stessa.

Supponiamo, infatti, che ogni immagine I1, ..., In possa essere segmentata

nelle sue regioni costitutive R1, ..., Rr. Va tenuto in considerazione che r e un

numero variabile da immagine ad immagine: non si puo definire, a priori, il

numero di regioni significative che possono essere estratte da ogni immagine

singolarmente considerata. Supponiamo, inoltre, di avere un certo numero

di tassonomie T1, ..., Tm, ovvero una molteplicita di organizzazioni gerarchi-

che di concetti, che costituiscono le nostre “dimensioni” di etichettamento.

Stiamo, infatti, operando in uno scenario multi-tassonomico. Ci si puo do-

mandare perche si desidera operare con uno scenario multi-tassonomico e la

risposta riguarda la possibilita di lavorare, con esso, in maniera molto piu

strutturata e di consentire, mediante l’utilizzo di molteplici tassonomie, di

stabilire dei legami, delle connessioni semantiche fra diverse ontologie che

3.2 Formalizzazione del modello 59

potrebbero essere fisicamente collocate su nodi (peer semantici) diversi. Si

cerca, conseguentemente, di rendere modulare la struttura a livello locale in

modo da facilitare il mapping a livello distribuito.

Utilizzando queste dimensioni e le relazioni ad esse connesse, vogliamo riu-

scire ad attribuire all’immagine delle etichette corrette che la possono ca-

ratterizzare semanticamente. Deve essere possibile gestire un etichettamento

multiplo, ovvero deve essere possibile attribuire ad ogni immagine, nella sua

globalita, un certo numero di etichette che possano caratterizzarla dal punto

di vista dei contenuti che essa stessa rappresenta. Le etichette semantiche

non sono, di conseguenza, connesse alle singole regioni bensı all’immagine

nel suo complesso.

In Figura 3.1 l’utente estrae un’immagine non ancora etichettata dal data-

base e si aspetta che il sistema fornisca delle caratterizzazioni semantiche

lavorando sulle feature di basso livello connesse alle singole regioni in cui

l’immagine stessa, rappresentante una tigre, puo essere segmentata.

In Figura 3.2 si comprende come vengono introdotte le molteplici tassonomie

per ricavare i concetti, le etichette che verranno utilizzate per l’annotazione

dell’immagine dal punto di vista semantico. Al termine delle fase di etichet-

temanto automatico si desidererebbe che l’immagine I1 fosse etichettata con

i termini “tigre”, “acqua”, “roccia” ed “erba”.

Siamo consapevoli del fatto che, lavorare con il solo contenuto semantico

o con le sole feature di basso livello non e sufficiente per fornire una buona

caratterizzazione delle immagini. Proprio per questo motivo e necessario inte-

grare il piu possibile i due approcci cercando di combinarli in modo efficiente

ed efficace per cercare di realizzare gli obiettivi che ci siamo prefissati.

2 Formalizzazione del modello

Supponiamo di avere un database ampiamente popolato che indicheremo

con DB. Le immagini, in esso contenute, possono essere rappresentate for-

malmente in questo modo:

Ii = ({R1, R2, ..., Rr}; {K1, K2, ..., Kk}) per i = 1, ..., n

Questo significa che ogni immagine singolarmente presa, contenuta nel DB,

puo essere rappresentata da un vettore di regioni, {R1, R2, ..., Rr}, e da un set



Figura 3.1: Come si opera a livello di feature connesse alle regioni in cui

un’immagine puo essere segmentata.


Figura 3.2: Come si opera a livello di etichette semantiche, derivanti da diver-

se dimensioni tassonomiche, al fine di caratterizzare un’immagine dal punto

di vista del contenuto.



di etichette, {K1, K2, ..., Kk}, in grado di caratterizzarla dal punto di vista

semantico. Il numero di regioni non puo essere definito a priori poiche non si

puo sapere esattamente in quante regioni un’immagine sara segmentata dal

sistema a runtime.

Ogni regione puo essere formalmente rappresentata in questo modo:

Rj = {f1, f2, ..., fh} per j = 1, ..., r

Ovvero ogni regione e caratterizzata da un vettore di feature ovvero di carat-

teristiche di basso livello quali colore, tessitura, forma etc. La dimensione del

vettore non puo essere definita a priori, ma dipende dal sistema che si occupa

dell’estrazione dalle immagini delle feature di basso livello che sono connesse

ad ogni regione in cui l’immagine puo essere segmentata. Ogni etichetta puo

essere formalmente rappresentata come segue:

Ky = (Tt; Ll) per y = 1, ..., k; t = 1, ...,m; l = 1, ..., #(Tt)

Questo indica che ogni keyword, per come viene rappresentata, viene in realta

indicata come una coppia indicante l’identificativo della tassonomia da cui

il termine e estratto e l’etichetta vera e propria che caratterizza il contenu-

to dell’immagine stessa dal punto di vista semantico. Supponiamo di avere

a disposizione m tassonomie di concetti e di prendere in considerazione un

concetto facente parte di questa tassonomia: l’l -esimo concetto sara compre-

so fra 1 e la cardinalita della tassonomia in esame (#(Tt)).

Definizione 1 (image retrieval)

In un sistema di reperimento di immagini, data un’immagine Iq appartenente

ad un DB di immagini ampiamente popolato, si vuole definire il concetto di

query fatta su un database di tale tipo in questo modo:

F := Q(Iq, DB)

Grazie a tale “Query Function” si vuole che il sistema sia in grado di restitui-

re, a fronte di un’immagine query Iq che viene presentata, tutte le supponiamo

z immagini piu simili all’immagine query sia sfruttando le feature di basso

livello (“query by feature”) sia lavorando a livello di etichette semantiche


(“query by keyword”) con le quali un’immagine deve essere stata precedente-

mente etichettata.

Definizione 2 (etichettamento automatico)

Data una qualunque immagine Iq non ancora etichettata, appartenente di

conseguenza al testing set di immagini del database DB, vogliamo definire una

funzione che consenta di etichettare automaticamente quest’ultima con key-

word semantiche appartenenti ad una molteplicita di tassonomie differenti.

Tale funzione, detta “Labeling Function”, puo essere scritta come segue:

{K1, K2, ..., Kk} := L(Ii, Tt) con i = 1, ..., n; t = 1, ...,m

Tale “Labeling Function”, presa in ingresso l’immagine da etichettare e le tas-

sonomie messe a disposizione dal sistema, fornisce in uscita un set di coppie

contenenti il termine di etichettamento e l’identificativo della tassonomia a

cui quel termine appartiene.

Si e cercato, in tal modo, di dare una formalizzazione a quelle che sono le

variabili ed i parametri di progetto su cui occorrera fare delle valutazioni

prima di decidere quale strada risolutiva scegliere alla luce di quelli che sono

gli approcci proposti nello stato dell’arte.

E necessario, a questo punto, cercare di scomporre lo scenario di riferimento

in tanti sotto-problemi. Indagando le singole parti e riferendoci a quello che

e stato proposto nello stato dell’arte, potremo capire e valutare in che modo

sia necessario procedere, in maniera del tutto innovativa, al fine di risolvere

le problematiche di cui si parlera qui di seguito.

Problema 1

Data un’immagine Iq (immagine query), estratta da un testing set TeS di

immagini non ancora etichettate e con l’ipotesi di avere a disposizione un

training set TrS di immagini campione gia etichettate dall’utente, si vuole

studiare una tecnica che consenta di gestire un etichettamento multiplo del-

l’immagine mediante un set di keyword {K1, K2, ..., Kk}.

Problema 2

Data un’immagine Iq (immagine query) non ancora etichettata, si vuole poter



attribuire ad essa un insieme di contenuti semantici utilizzando una molte-

plicita di tassonomie di concetti T1, ..., Tm dalle quali tali contenuti semantici

possono essere estratti.

Problema 3

Data un’immagine Iq (immagine query) che deve essere etichettata, si vuole

creare una tecnica che consenta di automatizzare il piu possibile il processo

di annotazione e che faccia uso sia delle feature di basso livello f1, f2, ..., fh,

associate ad ogni singola regione in cui l’immagine query puo essere seg-

mentata, sia di contenuti semantici lavorando a livello di scenario multi-

tassonomico come appartenenza delle singole keyword K1, K2, ..., Kk a diver-

se e svariate ontologie gerarchiche di contenuti.

3 Soluzione iniziale

E necessario presentare nel dettaglio l’approccio a cui si e deciso di far riferi-

mento durante l’attivita di tirocinio, di cui si puo trovare la documentazione

in [30], per le idee alquanto innovative da esso proposte. Esso tenta di appli-

care l’approccio a grafi proposto in [5], introdotto nello stato dell’arte e di cui

ci accingiamo a fornire una descrizione dettagliata utilizzando il formalismo

introdotto per modellare lo scenario di riferimento che si intende seguire.

L’innovazione di questo approccio riguarda la possibilita di gestire un etichet-

tamento multiplo delle immagini usando, a basso livello, i legami, le relazioni

di similarita fra le regioni costitutive delle immagini stesse per definire a

quali immagini gia etichettate accedere al fine di recuperare i termini che,

piu di frequente, ricorrono nell’annotazione con lo scopo di annotare una

nuova immagine. In fase di tirocinio si e deciso di scegliere proprio questo

approccio poiche ci e sembrata molto buona l’idea dell’etichettamento multi-

plo di un’immagine, ovvero la possibilita di attribuire all’immagine differenti

etichette che non siano solo strettamente connesse alle regioni in cui l’imma-

gine stessa viene segmentata, ma anche etichette piu “astratte” che emergono

dalla visione globale dell’immagine.

L’approccio a grafi ci e sembrato, inoltre, particolarmente efficiente. La co-

3.3.1 Definizione formale dell’approccio 65

struzione dinamica del grafo per un set corposo di immagini ha rivelato,

infatti, un alto livello di efficienza computazionale nella restituzione del ri-

sultato globale (etichette generate per annotare una nuova immagine). Ci

siamo resi conto, pero, che nonostante l’approccio sia abbastanza efficace,

esso avrebbe bisogno di una successiva fase di raffinamento che potrebbe

consentire di andare a migliorare la qualita globale delle etichette restituite.

Questo problema, insieme alla possibilita di rendere dinamicamente variabile

il numero di termini utilizzati per etichettare ogni immagine, ci ha consenti-

to di espandere il problema in modo consapevole introducendo un approccio

innovativo per la gestione dell’etichettamento automatico di immagini.

3.1 Definizione formale dell’approccio

Il problema di etichettare in maniera automatica un set di immagini puo

essere piu formalmente descritto come segue:

Problema 1

Dato un set S di immagini a colori ciascuna etichettata con un set di parole

e data una nuova immagine non ancora etichettata I, si vogliono trovare le t

migliori etichette (e.g., t=5) da assegnare a tale nuova immagine.

Problema 2

Dato un set S di n oggetti multimediali S=O1, O2, ..., On ciascuno con m at-

tributi multimediali, l’obiettivo e trovare un legame fra gli stessi.

Di seguito sono presentate un set di definizioni e di assunzioni utili:

Definizione 1

Un dominio Di di attributi di tipo i e la collezione di tutti i valori atomici

che l’attributo i puo assumere.

Definizione 2

I valori del dominio Di saranno chiamati con il nome di “token” del dominio

Di.



Assunzione 1

Per ogni dominio Di (i=1, ... ,m) viene fornita una funzione di similarita

si(∗, ∗) che e in grado di assegnare un punteggio ad ogni coppia di token di

dominio Di.

3.2 Costruzione del Mixed-Media Graph

Ogni immagine possiede degli attributi numerici (i vettori di feature connesse

alle regioni dell’immagine) e, solo alcune di esse, sono etichettate con una o

piu parole ricavate da un vocabolario. L’idea di base dell’approccio proposto e

quella di prendere tutte le immagini, di segmentarle in regioni (utilizzando un

qualunque algoritmo di segmentazione), di estrarre da ogni regione un vettore

di feature e di considerare che solo alcune delle immagini sono etichettate

con delle parole mentre la maggior parte delle stesse dovra essere etichettata

mediante questo approccio automatico. L’innovazione consiste nel mappare

tutti gli oggetti, cosı come i loro attributi, come nodi di un grafo; per dei

generici oggetti multimediali con m attributi si puo costruire un grafo a

(m+1) livelli fatto da m tipi di nodi differenti (uno per ogni attributo) e un

tipo di nodo strettamente connesso all’oggetto multimediale stesso.

Denotiamo con V(O) il vertice dell’oggetto O e denotiamo con V (ai) il vertice

il cui valore di attributo A = ai. A questo punto si tracciano tutti gli archi

che consentono il collegamento fra il nodo rappresentante l’oggetto e i vari

nodi corrispondenti ai suoi attributi.

Nel grafo Mixed-Media Graph (MMG) ci sono, dunque, due tipi di link:

• NN-links (nearest-neighbor links) fra i nodi che mappano vettori di

feature simili;

• OAV-links (object-attribute-value links) fra un nodo oggetto e tutti i

nodi che rappresentano i suoi valori di attributo.

C’e solo un punto critico da esaminare: per attributi di tipo numerico e vet-

toriale e necessario avere un modo per riflettere la similarita fra due vettori.

Si decide, di conseguenza, di aggiungere un arco fra due nodi attributo se e

solo se i due vettori di feature sono sufficientemente simili. Si deve decidere,

dunque, una soglia per valutare la similarita. Ci sono molti modi per fare

questo, ma gli autori hanno deciso di introdurre una soglia adattativa: per

3.3.3 Correlazione mediante Random Walk with Restart 67

ogni vettore di feature si vanno a scegliere i K-NN (K-nearest neighbors)

e, solo per quelli, si vanno a tracciare gli archi corrispondenti. Calcolare il

K-NN e facile dal momento che noi gia possediamo una funzione di similarita

si(∗, ∗) per ogni dominio Di.

A questo punto, per risolvere il problema dell’etichettamento automatico,

e necessario sviluppare un metodo per trovare buone parole da usare come

etichette di un’immagine. E necessario, dunque, stimare l’affinita che ogni

termine, delle immagini a cui si e acceduto per similarita di regione, ha con

la nuova immagine da etichettare.

Concretamente supponiamo di avere un set di immagini S = I = I1, I2, I3, I4

come quelle rappresentate in Figura 3.3. Il grafo corrispondente creato, se-

condo l’approccio sopra presentato, ha tre tipi di nodi differenti: uno per

gli oggetti immagine Ij (j=1,2,3,4), uno per le regioni Rj (j=1, ...,16) e uno

per i termini Lj (j=1, ..., 13). La Figura 3.4 mostra il corrispondente GMMG

ed, in esso, gli archi solidi rappresentano i Object-AttributeValue link, men-

tre gli archi tratteggiati rappresentano i Nearest-Neighbor link (nell’esempio

consideriamo k=1 nearest neighbor per evitare di sovraccaricare il grafo).

Relativamente all’esempio in esame, si dovra stimare la similarita di ogni

termine delle immagini recuperate mediante similarita di regione rispetto

all’immagine I4 non ancora etichettata.

3.3 Correlazione mediante Random Walk with Restart

Una volta che e stato mappato il tutto come un problema di grafi, si deve

trovare un metodo per assegnare importanza ai vertici di un grafo, cosı come

determinare quanto correlata e un’immagine non etichettata con un termine

o meglio con un set di termini con cui sono state etichettate altre immagini.

Gli autori propongono di utilizzare il metodo Random Walk with Restart

(RWR) con la consapevolezza che la scelta del metodo e, comunque, ortogo-

nale al framework da loro presentato.

Il metodo Random Walk with Restart opera come segue: per calcolare l’af-

finita, l’importanza di un nodo “B” per un nodo “A” si deve considerare

un random walker (camminatore casuale) che parte dal nodo “A” e sceglie

randomicamente uno fra tutti i cammini disponibili di volta in volta per arri-

vare al nodo “B” ma, prima di fare una scelta, con probabilita c, egli ritorna



Figura 3.3: Quattro immagini di cui le prime tre annotate e l’ultima da an-

notare; ad ogni immagine viene fatta corrispondere la sua segmentazione in

regioni.

Figura 3.4: Grafo MMG corrispondente creato in relazione alla situazione

esaminata.

3.3.4 L’algoritmo Cross-modal Correlation Discovery 69

indietro e riparte dal nodo “A”. Denotiamo con uA(B) la probabilita che il

random walker ha di trovarsi, partendo dal nodo “A”, in modo stabile sul

nodo “B”; uA(B) e l’importanza, l’affinita di “B” rispetto ad “A”.

Definizione 3

L’importanza del nodo B rispetto al nodo A e la probabilita di stato stabile

uA(B) di un random walk with restart come definito sopra.

Ad esempio, per risolvere il problema dell’etichettamento dell’immagine I4 di

Figura 3.4 si devono calcolare le probabilita di stato stabile uA(∗) per tutti

i nodi del grafo MMG valutando solo i nodi corrispondenti ai termini e, alla

fine, sara sufficiente riportare le migliori (e.g. 5) etichette che meglio saranno

in grado di descrivere l’immagine ancora da etichettare, ovvero I4 .

3.4 L’algoritmo Cross-modal Correlation Discovery

Per un problema generale l’algoritmo si sviluppa in varie fasi che prevedono

dapprima la costruzione del grafo MMG poi, quando l’utente si domanda

qual e l’importanza che il nodo “A” possiede in relazione al nodo “B”, si

calcola uA(B), ovvero la probabilita di trovarsi stabilmente su uno stato.

Il calcolo di uA(B) rappresenta una problematica importante e alquanto inte-

ressante. Gli autori di [5] propongono una notazione matriciale per compat-

tezza. Supponiamo che Oq sia l’oggetto query e di voler trovare i termini piu

adatti per etichettarlo. Si attiva un RWR dal nodo query q e si calcola il vet-

tore contenente le probabilita di stato stabile −→uq = (uq(1), uq(2), ..., uq(N))

dove N e il numero di nodi dell’MMG e E il numero di archi.

La stima del vettore −→uq puo essere efficientemente implementata grazie ad

una moltiplicazione matriciale. Supponiamo che A sia la matrice di adiacenza

del grafo MMG e che sia normalizzata per colonna. Supponiamo che −→vq sia

un vettore colonna con tutti gli N elementi a 0 eccetto l’elemento corrispon-

dente al nodo q il quale e settato a 1. Il vettore −→vq e il cosiddetto vettore di

restart.

A questo punto si puo formalizzare il concetto di “importanza” di un nodo

con la definizione che segue:



Definizione 4

Sia c la probabilita di attivare una fase di restart del random walk dal nodo q,

allora il vettore che mappa le probabilita di stato stabile (di dimensione Nx1)

uq e in grado di soddisfare la seguente equazione:

−→uq = (1− c)A−→uq + c−→vq

Si puo mostrare facilmente che:

−→uq = c(1/(I − (1− c)A))−→vq

dove I e la matrice identita di dimensione NxN.

Lo pseudocodice dell’algoritmo che consente di trovare le correlazioni a mo-

dalita incrociata e indicato di seguito.

Algoritmo Cross-modal Correlation Discovery (CCD)

Dato un grafo GMMG e un oggetto Oq dove alcuni attributi di Oq hanno dei

valori mancanti.

1. Sia −→vq = 0 per tutti i suoi N valori eccetto un unico ‘1’ per il q-esimo

valore.

2. Sia A la matrice di adiacenza del grafo aumentante creato nello step 1.

Normalizza la matrice A per colonna.

3. Inizializza −→uq = −→vq .

4. Finche (−→uq non ha raggiunto la convergenza)

(a) −→uq = (1− c)A−→uq + c−→vq .

3.5 Vantaggi e svantaggi

Molteplici sono i vantaggi connessi alla possibilita di utilizzare la tecnica

che sfrutta Mixed-Media Graph per l’etichettamento automatico di imma-

gini. Primo fra tutti la possibilita di generare una molteplicita di etichette.

Riflettendo si puo notare, infatti, come sia possibile annotare in modo auto-

matico le immagini (o qualunque tipo di dato multimediale) etichettandole

3.3.5 Vantaggi e svantaggi 71

con un set di parole significative in grado di descriverle. L’innovazione si ha

dal momento che l’etichetta non e attribuita alla regione, ovvero non c’e per

ogni regione una ed una sola etichetta che puo essere ad essa associata, ma

l’etichetta caratterizza l’immagine nella sua totalita. Si lavora, dunque, a li-

vello probabilistico accedendo, in base alla similarita di regione, alle immagini

gia etichettate e prendendo le supponiamo t etichette che compaiono piu di

frequente per etichettare la nuova immagine. Questa idea e assolutamente in-

novativa in quanto consente di poter annotare un’ immagine con dei concetti

in un certo qual modo “astratti”, ovvero concetti che non emergono in modo

immediato da una osservazione dettagliata delle singole regioni costitutive

dell’immagine stessa.

Ad esempio, se dovessimo etichettare in modo automatico una cartolina come

quella in Figura 3.5 vorremmo avere come etichette non solo “cielo”, “mare”,

“barca”, “grattacielo”, ma anche etichette come “CN Tower” e “Toronto”

capaci di esprimere concetti che non emergono in modo immediato dalle re-

gioni in cui l’immagine e segmentata, ma che sono concetti caratteristici, ad

esempio, di quello che e lo “skyline” di una citta famosa.

Un ulteriore esempio di quanto si vuole far comprendere e mostrato in Figu-

ra 3.6 dove noi vorremmo che l’immagine fosse etichettata non soltanto con

termini come “mucca”, “erba”, “cespuglio” e “terreno”, ma volemmo poter

gestire anche termini piu astratti connessi non soltanto alle regioni costitu-

tive dell’immagine bensı all’immagine nella sua totalita come ad esempio il

concetto di “pascolo”.

Durante lo studio affrontato nella fase di tirocinio ci si e resi conto della

presenza di una molteplicita di problematiche da risolvere per rendere piu

preciso ed efficace il processo di etichettamento.

Va detto, infatti, che l’emissione delle etichette si basa su una analisi finale di

frequenza delle stesse. Per ogni immagine del training set, che viene acceduta

mediante Random Walk with Restart lavorando sulle feature di basso livel-

lo connesse alle regioni, si catturano tutti i termini che la etichettano. Tali

etichette vengono raggruppate in una struttura dati in cui i termini compaio-

no senza ripetizioni e con accanto la frequenza. Al termine dell’applicazione

dell’algoritmo si procede ad effettuare un ordinamento (ranking) sulla base



Figura 3.5: Possibili etichette per l’immagine potrebbero essere: “cielo”, “ma-

re”, “barca”, “grattacielo”, ma anche concetti piu astratti come “CN Tower”

e “Toronto”.

Figura 3.6: Possibili etichette per l’immagine potrebbero essere: “mucca”,

“erba”, “terreno”, ma anche un concetto piu astratto come “pascolo”.

3.3.5 Vantaggi e svantaggi 73

delle frequenze e si decide di scegliere le prime supponiamo t etichette per

procedere all’annotazione automatica definitiva dell’immagine query Iq ap-

partenente al testing set di immagini che devono essere ancora etichettate.

Questo procedimento si rivela alquanto impreciso poiche una semplice analisi

sulle frequenze rischia di andare a falsificare quelle che sono le etichette real-

mente significative al fine dell’annotazione. Ad esempio, a volte si e verificato

il caso in cui, in maniera erronea, il sistema tentasse di andare ad etichettare

un’immagine rappresentante un “cavallo” con il termine “mucca”. Un altro

caso di manifestazione di questa problematica si ha con termini che compa-

iono frequentemente come “erba”: tale termine rischia di comparire, proprio

a causa della sua ubiqua presenza quasi in tutte le immagini, anche in quelle

che in realta non la rappresentano.

Un’altra problematica da affrontare e connessa alla possibilita di rendere fles-

sibile il numero di termini che devono andare ad etichettare un’immagine. Ci

sono immagini che, in realta, potrebbero necessitare meno di, supponiamo

t, termini di etichettamento. In tal caso purtroppo il sistema, che e stato

progettato per restituire esattamente t termini in modo automatico per ogni

immagine, si troverebbe a generare termini effettivamente non corretti ma che

verrebbero, comunque, proposti come potenziali per l’annotazione dell’imma-

gine. In questo caso si rivela fondamentale l’intervento utente che dovrebbe

consapevolmente intervenire nel processo di annotazione andando a cancel-

lare i termini non corretti restituiti. Ad esempio, se un’immagine contenesse

solamente un cavallo che corre in un prato, noi vorremmo che il sistema fosse

in grado di generare automaticamente solamente i termini “cavallo” ed “er-

ba”, ma se il sistema per come e stato costruito prevede la restituzione di

supponiamo 3 etichette allora il sistema restituira in uscita anche una terza

etichetta, insieme alle prime due, che sicuramente si rivelera inappropriata

per l’etichettamento dell’immagine in esame.

Entrambi i problemi di cui si e discusso sopra potrebbero essere attenua-

ti, o addirittura completamente risolti, prevedendo una successiva fase di

raffinamento delle etichette generate durante la prima fase di applicazione

dell’approccio a grafi Mixed-Media Graph. Tutto cio studiando nuovi algo-

ritmi in grado di fondere insieme tecniche differenti in modo opportuno per

i nostri scopi di annotazione automatica.



4 Presentazione dell’approccio proposto

In questa sezione ci si pone l’obiettivo di andare a descrivere tutti i detta-

gli riguardanti la tecnica che e stata pensata, insieme ai relativi algoritmi,

per risolvere in maniera efficiente ed efficace l’etichettamento automatico di

immagini in modo da superare tutte le problematiche che sono state pre-

cedentemente esposte. In definitiva, l’idea e quella di cercare di fondere i

principi costituenti due differenti approcci, quelli di cui sono state esposte

le idee di base in [5] ed in [12], in modo da generarne un terzo, del tutto

innovativo, in grado di intervenire piu che altro sull’efficacia delle etichette

generate durante una prima fase di etichettamento.

4.1 Costruzione della matrice di similarita

SimilarityTable

Il primo problema che deve essere risolto riguarda la possibilita di generare

un set di etichette, per i fini dell’etichettamento automatico di una nuova

immagine non ancora annotata, che in qualche modo siano correlate le une

con le altre.

Come abbiamo ampiamente discusso nella precedente sezione, sfruttando so-

lamente l’approccio a grafi si ha la possibilita di generare un set di etichette

che sono proprio quelle che il nostro sistema ha intenzione di restituire in usci-

ta. Queste ultime possono poi o essere sottoposte ad una successiva fase di

raffinamento da parte dell’utente esterno che puo intervenire nel processo di

annotazione eliminando dei termini che sono stati generati ma che non ritie-

ne corretti, o essere applicate come termini definitivi che il sistema utilizzera

ciecamente per etichettare l’immagine query Iq, senza porsi problemi relativi

alla loro correttezza formale. In questo modo potrebbe accadere abbastan-

za frequentemente che il sistema tenti di andare ad etichettare un’immagine

rappresentante un “cavallo” con i termini, a questo punto errati, “mucca” o

“cervo”.

Per far fronte a questo problema si e pensato di spostare il campo d’azio-

ne in modo da non considerare piu solamente la rilevanza di ogni etichetta

singolarmente presa (primo ordine), ma di valutare il grado di similarita che

puo essere associato ad ogni coppia di etichette (secondo ordine).

3.4.1 Costruzione della matrice di similaritaSimilarityTable 75

Partendo dal training set di immagini campione gia etichettate, si vuole

costruire un grafo bipartito (bipartite graph) costituito, da un lato, dalle im-

magini e dall’altro dalle etichette che annotano ciascuna singola immagine.

Il grafo di primo ordine che viene mappato si presenta approssimativamente

come quello che viene mostrato in Figura 3.7 e che e stato appositamente

inserito come esempio per cercare di dare un’idea piu precisa di qual e lo

scenario in cui ci si sta muovendo.

A partire da questo grafo G, l’idea e quella di costruire un nuovo grafo, G2,

che sia in grado di definire il grado di similarita di ogni coppia di immagini

partendo dal grado di similarita delle coppie di etichette che tali immagini

referenziano e cosı via in maniera del tutto ricorsiva. Si utilizzano le formule

che vengono proposte dall’algoritmo di ricerca di similarita fra coppie di nodi

in un grafo, ovvero l’algoritmo PSimRank. Un esempio del grafo G2 che con-

sente, grazie alla sua intrinseca struttura (archi entranti ed uscenti da ogni

nodo), di calcolare i valori di similarita fra due nodi appartenenti al grafo

stesso viene presentato in Figura 3.8.

Figura 3.7: Esempio di “Bipartite Graph”, costruito a partire dal training set,

composto dalle immagini e dai termini con cui queste ultime sono etichettate.



Come abbiamo gia illustrato all’interno dello stato dell’arte nel Capitolo 2,

l’algoritmo PSimRank, proposto da [12], in generale consente di calcolare la

similarita fra i nodi che costituiscono un grafo basandosi globalmente sul-

l’idea intuitiva che “due oggetti sono simili se sono referenziati da oggetti a

loro volta simili”. Riprendiamo ora le idee di base proposte da tale tecnica

per comprendere come poterla applicare alle nostre esigenze.

Il caso base prevede il confronto di un oggetto con se stesso ed, in tal caso,

il massimo punteggio (score) di similarita assegnato risulta 1. In generale lo

score che viene computato e sempre un valore compreso fra 0 ed 1 dove 1

rappresenta il massimo grado di similarita e 0 rappresenta il massimo grado

di dissimilarita. Dati, infatti, due oggetti a e b la similarita fra i due oggetti

puo essere indicata con s(a, b) ∈ [0, 1].

Supponiamo di avere un grafo costituito da un insieme di vertici e di pren-

dere in considerazione uno qualunque di tali vertici ad esempio v, si denota

con I(v) e con O(v) rispettivamente il set di archi entranti (in-neighbors) o

uscenti (out-neighbors) dal nodo v. Individualmente gli archi entranti si in-

dicano con Ii(v) con 1 ≤ i ≤ |I(v)| mentre gli archi uscenti si indicano con

Oi(v) con 1 ≤ i ≤ |O(v)|.Gli score, mediante PSimRank, possono essere calcolati mediante delle itera-

zioni che propagano le similarita su tutte le coppie degli archi entranti in un

nodo, esattamente come accadeva per SimRank proposto da [13]. Le iterazio-

ni fatte con PSimRank prevedono l’utilizzo di un algoritmo esatto quadratico

organizzato in vari passi i quali sono illustrati in Algoritmo 1.

3.4.1 Costruzione della matrice di similaritaSimilarityTable 77

Figura 3.8: Grafo di ordine due a partire dal quale si calcolano i valori di

similarita associati ad ogni coppia di etichette.



Algorithm 1 Formule di PSimRank per il calcolo della similarita fra i nodi

di un grafo.

1: if (u = v) then

2: psim0(u, v) = 1.

3: else

4: psim0(u, v) = 0.

5: end if

6: repeat

7: if (u = v) then

8: psiml+1(u, v) = 1.

9: else if (I(u) = 0oI(v) = 0) then

10: psiml+1(u, v) = 0.

11: else

12: psiml+1(u, v) = c.[ |I(u)∩I(v)||I(u)∪I(v)| .1+

13: + |I(u)\I(v)||I(u)∪I(v)| .

1|I(u)\I(v)|.|I(v)|

∑u′∈I(u)\I(v),v′∈I(v) psiml(u

′, v′)+

14: + |I(v)\I(u)||I(u)∪I(v)| .

1|I(v)\I(u)|.|I(u)|

∑v′∈I(v)\I(u),u′∈I(u) psiml(u

′, v′)].

15: end if

16: until (Non c’e convergenza)

PSimRank opera in maniera ricorsiva. Per dare un’intuizione di come esso

affronta ricorsivamente il calcolo delle similarita fra due nodi di un grafo sup-

poniamo di descrivere il procedimento con un esempio pratico. Supponiamo

di voler calcolare quanto sono simili due etichette ad esempio “tigre” e “giun-

gla”. All’iterazione k = 0 la similarita simk(tigre, giungla) = 0 poiche non

si possiede nessun’altra informazione che, in qualche modo, possa correlare i

due termini. All’iterazione k = 1 ci si chiede se esiste almeno un’immagine

che e etichettata con “tigre” e “giungla” contemporaneamente. Se sı, le due

etichette risultano correlate ed il loro grado di similarita puo essere calcolato

con le formule sopra indicate, ma in ogni caso il valore computato risulta

essere diverso da zero. All’iterazione k = 2 ci si chiede se, fra tutte le imma-

gini che sono etichettate con il termine “tigre” ce n’e almeno una che ha un

termine comune a tutte quelle che sono etichettate con il termine “giungla”.

Se sı, i termini “tigre” e “giungla” risultano correlati con un valore di simi-

larita computato che risultera rafforzato rispetto a quello calcolato al passo

3.4.2 Fase di generazione delle etichette 79

precedente (piu tendente a 1 che a 0). Il processo puo essere ripetuto fino a

n volte ovvero fino a quando non si verifica di aver raggiunto la convergenza

a livello di valori computati.

Una volta calcolati i valori di similarita fra tutte le possibili coppie di eti-

chette, impiegate per annotare le immagini del training set, questi vengono

inseriti in una matrice quadrata, che decidiamo di chiamare SimilarityTable,

la cui struttura generale e molto simile a quella della matrice riportata qui

di seguito nella Tabella 1.

E bene precisare che il calcolo degli score di similarita viene effettuato of-

fline. Per questo motivo, dato il training set, si va a riempire la matrice

SimilarityTable[j][j] prima di far partire l’effettivo processo di etichetta-

mento. Cio implica che questa prima fase non influenza la complessita com-

putazionale degli algoritmi che in seguito andremo a definire, poiche non

viene fatta a tempo di esecuzione bensı in una fase antecedente. Proprio per

questo motivo, la dimensione della matrice puo essere anche molto elevata

(dipende dal numero di etichette impiegate per l’annotazione del training

set) e, nonostante cio, non si va a toccare la complessita algoritmica finale.

Tabella 1

Orso T igre Scoiattolo Erba {...} Cielo

Orso 1 s1,2 s1,3 s1,4 s1,... s1,j

Tigre s2,1 1 s2,3 s2,4 s2,... s2,j

Scoiattolo s3,1 s3,2 1 s3,4 s3,... s3,j

Erba s4,1 s4,2 s4,3 1 s4,... s4,j

{...} s...,1 s...,2 s...,3 s...,4 1 s...,j

Cielo sj,1 sj,2 sj,3 sj,4 sj,... 1

4.2 Fase di generazione delle etichette

Durante questa fase si utilizzano e si offre una visione innovativa delle tecni-

che che in parte sono state indagate e sviluppate durante l’attivita di tiroci-

nio. Nel momento in cui il sistema entra in esecuzione si sfrutta la struttura a

grafo, Mixed-Media Graph (MMG), navigandolo in maniera casuale secondo

un algoritmo di tipo Random Walk with Restart (RWR).

Nell’attivita di tirocinio si e preferito utilizzare una tecnica che, invece di



andare a scegliere in modo randomico una fra le k regioni piu simili ad una

data regione, prevedeva di ciclare esattamente su tutte le k regioni simili ad

una regione data per cercare di velocizzare la convergenza algoritmica. In

questo contesto, al contrario, invece di gestire la generazione delle etichette

mediante una modalita “one shot”, ovvero in un solo passo, abbiamo deciso

di generare le etichette mediante un cammino casuale, che naviga liberamen-

te il grafo MMG costruito, andando ad esplorare sia regioni, sia etichette ed

andando a catturare la frequenza con cui tale RWR attraversa un dato nodo

etichetta. Ad ogni termine viene, infatti, associato un contatore il cui valore

viene incrementato di un’unita ogni volta che il RWR attraversa quella de-

terminata etichetta.

Dal punto di vista della convergenza algoritmica il sistema, data una nuova

immagine che deve essere etichettata, impiega un po’ piu tempo per la gene-

razione del set di etichette disponibili ma, in ogni caso, la precisione con cui

queste vengono generate e sicuramente superiore. Visto che il RWR procede

in modo casuale, e ovvio che se il processo di etichettamento viene ripetuto

una molteplicita di volte per annotare la stessa immagine ogni volta verranno

generate un set di etichette in parte uguali ed in parte differenti. Tutto cio

e dato dalla casualita della navigazione del RWR. E ovvio, pero, che piu fasi

di “RESTART” vengono previste, piu la precisione nella generazione del set

di etichetta aumenta.

L’algoritmo di generazione delle etichette e riportato in Algoritmo 2.

Strutture dati

L’algoritmo sfrutta la presenza di differenti tipologie di strutture dati, al-

cune permanenti ed altre temporanee. Quelle permanenti sono fondamentali

e devono essere salvate poiche serviranno nella parte di fusione successiva

delle due tecniche, che fino ad ora ci siamo apprestati a spiegare. Quelle

temporanee, al contrario, sono strutture che hanno il tempo di vita legato

all’esecuzione dell’algoritmo stesso.

Strutture permanenti

Ad ogni etichetta Li, che viene utilizzata per annotare il training set e che

viene navigata dal RWR poiche costituente un nodo di un grafo, e associato


un contatore counter(Li), inizializzato all’inizio a zero, il cui valore viene

incrementato di un’unita ogni volta che il RWR attraversa quella determina-

ta etichetta. Durante la fase di etichettamento di un’immagine non ancora

annotata, il RWR naviga il grafo n volte (con n abbastanza elevato per ga-

rantire maggiore precisione nella generazione delle etichette), ed ogni volta

che attraversa un nodo, sia esso un nodo regione o un nodo etichetta, viene

generato un valore di probabilita p ∈ [0, 1] il quale viene confrontato con un

valore di soglia C1. Se (p ≥ C1) il RWR riparte dall’immagine query (attua

la cosiddetta fase di “RESTART”). Durante la navigazione, pero, ogni volta

che il RWR capita su un nodo etichetta incrementa il valore del contatore as-

sociato ad essa di un’unita. L’idea e che, anche durante una sola navigazione,

il RWR potrebbe capitare piu volte sullo stesso nodo etichetta, poiche ogni

suo movimento e casuale, e di conseguenza il valore del contatore counter(Li)

potrebbe essere incrementato di piu unita anche durante un’unica navigazio-

ne. Noi siamo interessati a tenere traccia della frequenza di attraversamento

compiuta in tutte le, supponiamo n, navigazioni complessivamente.

Strutture temporanee

La struttura temporanea Z raccoglie tutte le regioni, piu simili ad una data

regione supponiamo Rk, che vengono accedute mediante una k-NN query e

tutte le etichette che annotano l’immagine a cui la regione Rk appartiene. Z

e un vettore di dimensione sempre variabile poiche una query k-NN raccoglie

sempre esattamente k elementi (i primi k termini del vettore), ma la variabi-

lita e data dal numero di etichette poiche non tutte le immagini del training

set sono annotate con lo stesso numero di termini. Tale struttura viene uti-

lizzata dal RWR per decidere dove muoversi in maniera casuale. Si sceglie,

infatti, in modo random un elemento del vettore e si decide di spostarsi su

di esso (sia quest’ultimo regione o etichetta).



Z =

R1

R2

...

...

Rk

L1

L2

...

...

Li

I dettagli dell’algoritmo sono riportati di seguito. Data in ingresso, infatti,

l’immagine query Iq che deve essere etichettata, l’algoritmo si articola nei

passi di risoluzione che vengono dettagliati in Algoritmo 2.

Per comprendere intuitivamente l’algoritmo vengono di seguito riportate tre

figure che tentano di mettere in luce un esempio di come opera il RWR su

un grafo MMG.

In Figura 3.9 si presenta la struttura di GMMG con tutti i suoi tre tipi di at-

tributi (immagini, regioni ed etichette) e connessioni (“object-attribute value

link” e “nearest-neighbor link”).

In Figura 3.10 ed in Figura 3.11 si mostrano due esempi di funzionamento

del RWR che naviga sul grafo GMMG. Gli step che vengono indicati non sono

quelli dell’algoritmo. Sono semplicemente stati inseriti per capire la sequen-

zialita di navigazione del grafo.


Algorithm 2 Generazione di etichette usando la tecnica Random Walk with

Restart e la struttura Mixed-Media Graph.

1: Inizializza la variabile n con un valore grande a piacere.

2: repeat

3: Decrementa la variabile n di un’unita.

4: Scegli a caso una delle regioni che segmentano l’immagine query (e.g.

Rk).

5: Genera un valore di probabilita p ∈ [0, 1].

6: if (p ≥ C1) then

7: ritorna allo Step (3).

8: end if

9: Applica una k-NN query e recupera le k regioni piu simili ad Rk.

10: Seleziona le i etichette {L1, ..., Li} dell’immagine (all’inizio Iq, poi

una qualunque scelta dal processo randomico) a cui la regione Rk

appartiene.

11: Riempi un vettore Z con le regioni e le etichette recuperate

rispettivamente negli Step (9) e (10).

12: Scegli a caso un elemento del vettore Z, che indichiamo con Z[z].

13: if (Z[z] e una regione (e.g. Rg)) then


15: else if (Z[z] e un’etichetta (e.g. Lg)) then

16: incrementa il valore di counter(Lg) di un’unita (inizializzandolo a 1

se non e ancora stato creato).

17: end if

18: Genera un valore di probabilita p ∈ [0, 1].

19: if (p ≥ C1) then


21: end if

22: Riempi un vettore E con gli identificativi di tutte le immagini che sono

etichettate con Lg.

23: Scegli a caso un elemento del vettore E, che indichiamo con E[e].

24: Scegli una regione a caso fra quelle che segmentano l’immagine E[e] e

ritorna allo Step (9).

25: until (n ≥ 0)



Figura 3.9: Esempio di struttura di un grafo Mixed-Media Graph.

Figura 3.10: Primo esempio di navigazione del Random Walk with Restart

sul grafo GMMG.

3.4.3 Successivo raffinamento 85

Figura 3.11: Secondo esempio di navigazione del Random Walk with Restart

sul grafo GMMG.

4.3 Successivo raffinamento

A questo punto ci troviamo in questa situazione:

• abbiamo costruito offline una matrice di secondo ordine contenente

le similarita fra tutte le coppie di concetti utilizzati per etichettare le

immagini del training set;

• facendo navigare il Random Walk with Restart sul grafo GMMG, abbia-

mo catturato un set di etichette, potenziali annotatori dell’immagine

query, con le loro frequenze di attraversamento.

La domanda che ci si pone ora e questa: come fare a raffinare l’iniziale proces-

so di etichettamento, dovuto a RWR, integrando la presenza di una matrice

contenente le similarita fra tutte le coppie di concetti usati per l’annotazione

del training set? Come integrare in definitiva le due tecniche di cui si e am-

piamente discusso fino ad ora?

L’approccio che si e deciso di seguire e quello riportato nel dettaglio all’inter-

no degli algoritmi Algoritmo 3 e Algoritmo 4. Per dare un’idea di come



le cose vengono organizzate procediamo di seguito a fornire una breve descri-

zione di come si e gestita l’integrazione. Prima, pero, definiamo il concetto

di “clique” e spieghiamo perche e stato introdotto.

Definizione di Clique

Nella teoria dei grafi, un clique ottenuto su un grafo non orientato G =

(V,E), costituito da un insieme di vertici (V) e da un insieme di archi (E),

e un sottoinsieme di vertici V’ ⊆ V tale che, per ogni coppia di vertici in

V’, deve esistere un arco in grado di connettere i due. Questo equivale a dire

che il sottografo indotto, ovvero V’, deve essere completo. La dimensione di

un clique viene identificata dal numero di vertici che il clique stesso contiene.

Il problema associato ai clique (clique problem) consiste nel determinare se

un generico grafo, fornito in ingresso, contiene un clique di almeno una data

dimensione, supponiamo k vertici. Nel momento in cui k o piu vertici ven-

gono individuati, risulta banale verificare se essi formano effettivamente un

clique o meno ed e per questo che si dice che il problema connesso alla de-

terminazione dei clique e in NP.

Il corrispondente problema di ottimizzazione (maximum clique problem) con-

siste nel determinare il clique massimo in un grafo. La NP-completezza di

questo problema deriva banalmente dalla NP-completezza del set dei pro-

blemi indipendenti ad esso associati poiche si puo individuare un clique di

almeno k elementi se e solo se c’e un set indipendente di almeno k vertici nel

grafo complementare. Questo e facile da vedere dal momento che, se un sot-

tografo e completo, il suo complementare non ha nessun arco di connessione.

Un esempio di rappresentazione di un grafo su cui e possibile individuare un

insieme di clique viene mostrato in Figura 3.12.


Figura 3.12: Esempio di un grafo di termini da cui possono essere estrat-

ti i clique. Le connessioni rosse mettono in evidenza il clique a frequenza

massima restituito.



Partendo da queste considerazioni di base si e deciso di procedere nel modo

che ci apprestiamo a descrivere.

Dapprima abbiamo preso tutte le etichette, restituite come risultato dal-

l’applicazione dell’Algoritmo 2, con tutte le loro frequenze, indicate con

counter(Lk), decidendo di tenere solamente quelle ritenute veramente “signi-

ficative” ovvero solamente le, supponiamo k, etichette con il piu alto valore

di frequenza ad esse associato. A questo punto, con tali etichette, abbiamo

deciso di costruire un grafo G(V, E) in cui i vertici V rappresentano i termi-

ni, mentre gli archi E indicano le connessioni fra i vari concetti in base al

valore di similarita che puo essere catturato dalla SimilarityTable, costruita

in modo offline durante la prima fase di elaborazione algoritmica.

Si e deciso, inoltre, di non mantenere tutte le connessioni ovvero, dati due

concetti generici (Lu, Lv), si e deciso di costruire l’arco di connessione fra i

due solamente se il corrispondete valore di similarita, SimilarityTable[u][v],

risulta superiore ad un ben definito valore di soglia C2. Questo perche vo-

gliamo pensare di eliminare a priori tutte le similarita che non sono ritenute

significative: probabilmente, infatti, se il valore di affinita fra due concetti e

troppo basso, non e corretto tenerlo in considerazione poiche questo rappre-

senta gia un primo indizio del fatto che i due termini non risultano poi cosı

correlati gli uni con gli altri.

Il grafo che si viene a costruire non e completo, ma l’obiettivo e quello di recu-

perare, da esso, tutti possibili clique applicando l’Algoritmo 4 che descrive-

remo successivamente. Una volta identificati tutti i possibili clique del grafo

calcoliamo, per ciascuno di essi, il valore della frequenza associata al clique,

rappresentato con la seguente formula FreqCliquei =∑

Lk∈Cliqueicounter(Lk)

dove i identifica l’i-esimo clique che stiamo prendendo in considerazione . La

frequenza complessiva di un clique si ottiene facendo, dunque, la sommatoria

di tutte le frequenze (counter(Lk)), associate ai concetti che fanno parte del

clique, recuperate durante l’applicazione dell’Algortimo 2.

L’Algoritmo 3 termina proponendo in uscita il clique, ovvero l’insieme di

etichette il cui valore di frequenza, ad esso globalmente associato, risulta il

massimo. Tale clique viene indicato con il nome di Cliquemax.


Va puntualizzato che in uscita non viene restituito il maximum clique, ovve-

ro il clique con il massimo numero di termini, bensı il clique con associato

il massimo valore di frequenza. Questo perche puo capitare che magari un

clique costituito, ad esempio, da tre soli concetti abbia, ad esso associato,

un valore di frequenza complessiva di molto maggiore rispetto ad un cilque

composto, ad esempio, da quattro concetti. Questo perche potenzialmente il

clique composto da tre concetti potrebbe essere dotato di un grado di preci-

sione maggiore essendo costituito dai termini che effettivamente potrebbero

rivelarsi piu adatti ad etichettare l’immagine. Vogliamo conseguentemente

dare a tutti i clique la possibilita di entrare in gioco per etichettare l’imma-

gine restituendo in uscita, pero, solamente quello che, al di la del numero

di concetti che esso stesso e in grado di aggregare, e realmente il candidato

migliore in base alla frequenza, catturata dall’applicazione del Random Walk

with Restart durante l’Algoritmo 2, associata ai singoli termini.

Algorithm 3 Raffinamento delle etichette generate, durante l’applicazione

dell’Algoritmo 2, usando la tecnica PSimRank.

1: Crea il vettore TERMS[k] contenente i k concetti con il piu alto valore

di frequenza, counter(Lk), ottenuti dall’Algoritmo 2.

2: Crea un grafo non orientato G(V, E) fatto da un insieme di vertici

e di archi, dove V corrisponde al vettore TERMS[k] e E contiene

tutte le coppie (Lu, Lv) aventi similarita maggiore di un data soglia

(SimilarityTable[u][v] ≥ C2).

3: Applica al grafo l’Algoritmo 4, in grado di individuare il clique

Cliquemax a frequenza massima (avendo che la frequenza di un clique

si calcola come FreqCliquei =∑

Lk∈Cliqueicounter(Lk)).

4: return Il vettore RESULT , contenente tutti i concetti Lj ∈ Cliquemax.

L’Algoritmo 4 si pone l’obiettivo di trovare tutti i clique presenti all’interno

del grafo operando con una tecnica a forza bruta.

Le strutture temporanee utilizzate sono tre, rispettivamente i vettori TEMP ,

TEMP1 e RESULT .

Ogni volta che un clique e scoperto esso viene aggiunto a RESULT che quin-

di, alla fine, arrivera a contenere tutti i clique del grafo.



L’algoritmo, facendo riferimento al grafo proposto in Figura 3.12, opera muo-

vendosi all’interno di una struttura simile a quella illustrata nella Tabella 2

ed in particolare, per ogni nodo del grafo, aggiunge a RESULT il nodo stesso

(clique di dimensione uno) e poi procede confrontando il nodo con ognuno

degli altri nodi del grafo con indice maggiore (il grafo e non orientato, quin-

di sarebbe superfluo confrontare il nodo con tutti gli altri), aggiungendo a

TEMP ogni coppia che risulti connessa all’interno del grafo stesso.

Una volta inizializzato il vettore TEMP , si procede in maniera analoga,

confrontando ogni clique di ordine (n), presente in TEMP , con i clique di

indice maggiore all’interno dello stesso vettore ed aggiungendo a TEMP1

ed a RESULT tutti i clique “compatibili” trovati, risultanti dall’unione dei

due clique confrontati e quindi di ordine (n+ 1). Due clique sono considerati

“compatibili” quando ognuno dei nodi presenti all’interno del primo clique e

connesso a tutti i nodi del secondo.

Quando tutti i clique di TEMP sono stati confrontati, il vettore stesso vie-

ne svuotato e, se TEMP1 contiene degli elementi, essi vengono spostati in

TEMP e la procedura e ripetuta per l’ordine (n + 1).

Tutto cio viene fatto per ogni singolo nodo del grafo iniziale.

Alla fine il vettore RESULT conterra tutti i clique trovati, insieme al loro

punteggio complessivo, ovvero alla somma di tutte le frequenze dei singoli

nodi componenti il clique.

Al chiamante verra, quindi, restituito il clique a punteggio massimo.

Il procedimento che e stato appena descritto viene esemplificato in Esempio

1 facendo riferimento al grafo in Figura 3.12. La descrizione formale viene,

invece, dettagliata in Algoritmo 4.

Esempio 1

Supponiamo che questi siano i k (e.g. k = 6) termini con piu alto valore di

frequenza restituiti dal Random Walk with Restart durante la prima fase di

generazione attribuita all’Algoritmo 2.

• (A) Grass

• (B) Bear

• (C) Ground

• (D) Rock


• (E) Water

• (F) Deer

Applicando l’Algoritmo 4 abbiamo la generazione di una struttura di que-

sto tipo contenente tutti i clique, ciascuno con associato il proprio valore di

frequenza complessiva (FreqCliquei).

Tabella 2

1 A (95) B (59) C (57) D (38) E (35) F (31)

2 A,B (154) B,C (116) C,E (92) D,E (73) E,F (66)

A,C (152) B,D (97) C,F (88)

A,E (130) B,E (94)

A,F (126)

3 A,B,C (211) B,C,E (151) C,E,F (123)

A,B,E (189) B,D,E (132)

A,C,E (187)

A,C,F (183)

A,E,F (161)

4 A,B,C,E (246)

A,C,E,F (218)

Applicando, infine, l’Algoritmo 3 otteniamo i dati che sono riportati sotto.

Il clique a massima frequenza estratto risulta:

Cliquemax = {“Grass” (A); “Bear” (B); “Ground” (C); “Water” (E)}la cui massima frequenza risulta FreqCliquemax = 95+59+57+35 = 246.



Algorithm 4 Individuazione del clique a massima frequenza contenuto nel

grafo G(V, E).

1: Crea il vettore TEMP .

2: Crea il vettore RESULT .

3: for (i = 0 to k) do

4: for (j = i + 1 to k) do

5: if (V [i] is similar V [j]) then

6: Aggiungi il clique (V [i], V [j]) ai vettori RESULT e TEMP .

7: end if

8: end for

9: Crea una variabile booleana cicla inizializzata a true.

10: repeat

11: Crea il vettore TEMP1.

12: for (j = 0 to k) do

13: for (l = j + 1 to k) do

14: if (Cliquej is similar Cliquel) then

15: Aggiungi il clique (Cliquej ∪ Cliquel) al vettore TEMP1.

16: end if

17: end for

18: end for

19: if (TEMP1 non e vuoto) then

20: Vuota il vettore TEMP .

21: for (ogni clique Cliquei in TEMP1) do

22: Aggiungi Cliquei a TEMP .

23: Aggiungi Cliquei a RESULT .

24: end for

25: else

26: Metti il flag cicla a false.

27: end if

28: until (cicla = true)

29: end for

30: return Cliquemax (quest’ultimo e uno dei clique facenti parte di

RESULT il cui score risulta il massimo).

3.4.4 Vantaggi apportati dall’approccio proposto 93

4.4 Vantaggi apportati dall’approccio proposto

Valutando conservativamente la bonta della tecnica che e stata ideata si puo

notare come siano stati raggiunti gli obiettivi che erano stati prefissati in

partenza.

In primo luogo abbiamo la possibilita di gestire l’etichettamento di una nuova

immagine mediante un set di etichette capaci di esprimere anche contenuti

astratti. Non e definito il legame fra un’etichetta e le regioni in cui l’immagine

puo essere segmentata. Le etichette sono vincolate in maniera forte all’imma-

gine nella sua totalita. Immagini, regioni di segmentazione ed etichette sono

correlate mediante la struttura modulare di un grafo, il Mixed-Media Graph,

il quale puo essere liberamente navigato tramite Random Walk with Restart.

In secondo luogo il numero di etichette generate non e staticamente defi-

nito, ma e variabile. La variabilita e data dalla possibilita di basarci sulla

determinazione di clique, all’interno di un grafo di concetti connessi fra loro

solamente se il valore di similarita (calcolato mediante la tecnica PSimRank)

associato ad ogni coppia di termini supera un ben definito valore di soglia,

per ciascuno dei quali si calcola il valore complessivo della frequenza ad essi

associata. Il sistema provvedera a restituire il clique a massima frequenza

andando ad etichettare l’immagine, non ancora annotata, con l’insieme di

termini facenti parte di tale clique. Rendiamo di conseguenza flessibile il nu-

mero di termini che devono andare ad etichettare un’immagine dal momento

che potrebbero esistere immagini che necessitano meno di, supponiamo t,

valori di etichettamento.

L’ultima considerazione riguarda l’intervento multitassonomico. Esso inter-

viene, secondo il nostro approccio, solo nella prima fase di etichettamento

del training set: ogni immagine che fa parte di quest’ultimo viene etichettata

con dei termini che provengono da diverse tassonomie. L’intervento multitas-

sonomico impedisce ad un utente di annotare le immagini con termini di sua

preferenza, vincolandolo in modo forte alla scelta di concetti facenti parte di

una struttura gerarchica organizzata.

Capitolo 4

Imagination

In questo capitolo ci apprestiamo a descrivere nel dettaglio le caratteristiche

del prototipo software , “Imagination”, che e stato realizzato per provare sia

gli algoritmi di etichettamento automatico di immagini, di cui si e parlato

approfonditamente nella presente tesi, sia le tecniche di “mapping” a livello

ontologico i cui dettagli sono presentati in [29].

Il nome “Imagination” rappresenta l’acronimo: “IMage semAntics: ontoloGy

mappiINg & Auto capTIONing”. Tale acronimo indica, in effetti, la doppia

valenza e il doppio utilizzo che si fa di esso. L’idea e quella di estrarre il con-

tenuto semantico, presente in un’immagine, operando su quest’ultima con la

finalita di gestire la sua annotazione, mediante concetti, in maniera automa-

tica e di valutare le relazioni fra i termini stessi che appartengono ad una

molteplicita di tassonomie differenti collocate non solo in un contesto locale,

ma anche in ambito distribuito.

Nel presente capitolo, di conseguenza, ci concentreremo dapprima sulla de-

scrizione di come e stato possibile gestire l’integrazione del sistema Windsurf

nel progetto Imagination, poi discuteremo di come ci si e potuti interfacciare

con il DBMS MySql. Parleremo poi del perche e stato necessario introdur-

re l’ontologia WordNet e del motivo che ci ha spinti, successivamente, a

progettare un nuovo editor di ontologie, Jont, al fine di rendere possibile

la costruzione di piu semplici strutture tassonomiche specifiche in grado di

adattarsi ai nostri domini di riferimento. Infine, presenteremo l’architettura

software dell’applicazione descrivendo cio che Imagination consente di fare

dal punto di vista dell’interazione dell’utente finale con l’interfaccia grafica di

96 Imagination

sistema ed analizzeremo le responsabilita associate a tutte le classi ed a tutti

i package che, da un punto di vista strutturale, rappresentano l’organizza-

zione complessiva del sistema. Al termine, valuteremo i risultati sperimentali

ottenuti in merito alla definizione, a regime, dei valori di soglia che vengono

utilizzati all’interno dei differenti algoritmi creati.

1 Applicazione di Windsurf al progetto Ima-

gination

Windsurf (Wavelet-based INDexing of imageS Using Region Fragmentation)

e un sistema Content-Based Image-Retrieval che si concentra sulla creazione

di algoritmi efficienti ed efficaci in grado di gestire la segmentazione delle

immagini in regioni. Esso e stato sviluppato presso l’Universita di Bologna

ed i dettagli relativi alla sua realizzazione sono presentati in [31], in [32] ed

in [33].

Questo sistema, come illustrato in Figura 4.1, utilizza la trasformata Wavelet

discreta per estrarre le feature di colore e tessitura da una qualunque imma-

gine presa in ingresso, poi applica un algoritmo di clustering per partizionare

l’immagine in regioni omogenee ed, infine, memorizza le caratteristiche delle

singole regioni con lo scopo di poterle confrontare.

Windsurf introduce un nuovo approccio per quanto riguarda l’estrazione del-

le feature: l’applicazione della trasformata di Wavelet produce, infatti, infor-

mazioni combinate su colore e tessitura che descrivono il contenuto dell’im-

magine, mentre nei presistenti sistemi le due tipologie di informazioni erano

sempre state mantenute separate. Le feature cosı estratte vengono successiva-

mente utilizzate per frammentare l’immagine in regioni, tramite l’algoritmo

di clustering k − means. Poiche questo algoritmo utilizza i coefficienti di

Wavelet per partizionare le immagini in regioni, non vengono mantenute le

informazioni spaziali ed i pixel sono raggruppati utilizzando solo le informa-

zioni relative a colore e tessitura. La similarita fra due immagini viene, infine,

calcolata attraverso una funzione di distanza che confronta le feature delle

singole regioni e combina poi i risultati a livello globale.

4.1 Applicazione di Windsurf al progetto Imagination 97

Figura 4.1: Fasi di elaborazione di un’immagine all’interno del sistema

Windsurf.

E necessario, a questo proposito, domandarsi in quale contesto il sistema

“Imagination” ha sfruttato le potenzialita di Windsurf. La risposta si ha

indagando l’ambito infrastrutturale: per gestire la segmentazione delle im-

magini in regioni si e scelto di utilizzare le librerie del motore Windsurf. E

importante capire infatti come, avendo a disposizione tali librerie, abbiamo

avuto la possibilita di mappare gia una prima parte del grafo GMMG ovvero

quella che gestisce il legame fra le immagini e le regioni costitutive delle stes-

se. In realta cio che abbiamo fatto e stato prendere Windsurf ed estrarre dal

sistema i metodi che effettivamente ci potevano essere utili per la gestione

della segmentazione delle immagini in regioni e per la successiva estrazione

dei vettori di feature da esse. Da Windsurf abbiamo estrapolato anche il

metodo che ci ha consentito di calcolare la similarita fra i vettori di feature

rappresentativi delle varie regioni. Con questo metodo abbiamo potuto ese-

guire le k-NN query andando a recuperare, data una regione, le k regioni piu

simili ad essa.

Da un punto di vista piu implementativo abbiamo deciso di non costruirci la

matrice di adiacenza proposta da [5] anche perche, nonostante la costruzione

in parte offline, essa sarebbe risultata prevalentemente sparsa (riempita con

molti 0 e pochi 1) e proprio per questo assai inefficiente per quanto riguarda

il nostro caso specifico in cui si opera con un dataset di 971 immagini e di

conseguenza circa 2000 regioni complessivamente. Ricordiamo che la matrice

di adiacenza dovrebbe, infatti, contenere tanti ingressi quanti sono i “nodi”

effettivi del grafo ovvero nodi immagine, regione e concetto. Siamo riusciti a

98 Imagination

lavorare, dunque, molto piu efficientemente sfruttando la struttura che im-

plicitamente Windsurf gia e stato in grado di fornirci, evitando di caricare

a tempo di esecuzione una matrice di dimensioni eccessive che sarebbe sta-

ta assolutamente non scalabile nel caso di database di immagini abbastanza

grandi da gestire.

Abbiamo, di conseguenza, deciso di effettuare una navigazione del grafo i cui

valori sono stati precedentemente caricati in un database, soluzione magari

piu lenta a convergere, ma che non esplode dal punto di vista della comples-

sita all’aumentare della grandezza del grafo. La probabilita C1 di effettuare

una fase di “RESTART” e fissa quindi, anche nel caso di un grafo arbitra-

riamente grande, il tempo di navigazione correlato al processo del Random

Walk with Restart rimane lo stesso.

2 Interfacciamento con il database MySql

Dal momento che si e deciso di sfruttare l’interazione con il database, per

memorizzare le immagini e le regioni connesse alle immagini stesse, e stato

creato un nuovo database, chiamato “mmg”, al cui interno sono state map-

pate un set di tabelle. Il DBMS utilizzato per la gestione complessiva delle

tabelle si cui si parlera e MySql, i cui dettagli si posso consultare online in

[34].

Le tabelle sono quelle elencate di seguito (in Figura 4.2 e proposto un dia-

gramma che evidenzia, inoltre, i collegamenti fra le stesse):

• Tabella IMAGES

Questa tabella ha la responsabilita di mappare per ogni immagine

(identificata univocamente dal suo “image id”) i termini (indicati

dal valore “term”) che la etichettano e il riferimento alla tassonomia

(“ontology”) a cui questi ultimi appartengono.

La primary key e costituita dalla tripla di valori (“image id”, “term”,

“ontology”).

• Tabella ID MATCH

Questa tabella memorizza il match fra l’identificativo numerico dell’im-

4.2 Interfacciamento con il database MySql 99

magine (“image id”) e il suo nome effettivo (“image name”).

La primary key e costituita dal solo termine “image id”.

• Tabella FEATURES

Questa tabella memorizza, per ogni regione di un’immagine, il vettore

contenente le sue feature ovvero le caratteristiche di basso livello ad

essa associate. La tabella contiene, infatti, l’identificativo univoco di

ogni regione(“id region”), il riferimento all’immagine a cui tale regio-

ne appartiene (“id image”) e il vettore delle feature di basso livello

associate alla regione dell’immagine stessa. Le feature sono diverse a

seconda della dimensione dell’immagine da cui vengono estratte per

questo e necessario tenere traccia di cio mediante il campo indicato

con “dimension”. I campi “center1”, ..., “center12” rappresenta-

no i centroidi per l’estrazione delle feature (questi valori sono stati presi

dalle librerie del motore Windsurf trasportandoli dai file, su cui erano

memorizzati, e salvandoli in MySql). Analogamente “covcoeff1”, ...,

“covcoeff24” sono dei coefficienti di covarianza utilizzati per l’estra-

zione delle feature dal motore Windsurf (anche questi valori sono stati

trasportati da file in tabelle MySql).

La primary key e costituita dal solo termine “id region”, dal momen-

to che tutte le immagini sono univocamente identificate.

• Tabella ONTOLOGIES

Prevedendo di lavorare con una molteplicita di ontologie non solo in

ambito distribuito, ma anche a livello locale e stato deciso di intro-

durre questa tabella in cui sono memorizzate tutte le ontologie create,

ciascuna con il proprio nome identificativo (“ontology”), con i concet-

ti in essa contenuti (“concept”) e la relazione di parentela progressiva

che lega fra loro i vari termini (“parent”). Per ogni concetto, apparte-

nente ad una definita tassonomia, si indica il termine da cui esso deriva,

vale a dire il suo termine genitore.

La primary key e rappresentata dalla coppia (“ontology”, “concept”)

al fine di identificare univocamente, per ogni ontologia, quali sono i ter-

100 Imagination

mini che essa e un grado di rappresentare.

• Tabella PSIMRANK

Questa tabella e stata introdotta per individuare, grazie all’utilizzo del-

l’algoritmo PSimRank, le similarita fra le varie coppie di concetti presi

in esame. Una volta definita l’ontologia che si sta indagando per valuta-

re la similarita fra i vari concetti (“ontology”), si prende ogni termine

(“termA”) e lo si confronta con ciascuno degli altri (“termB”) appar-

tenenti alla medesima tassonomia di concetti (“ontology”) e si calcola

il valore di similarita (“sim”) fra le coppie create utilizzando le formule

di cui tanto si e discusso nel capitolo precedente legate all’applicazione

dell’approccio PSimRank.

La primary key e costituita dalla tripla di valori (“termA”, “termB”,

“ontology”).

• Tabella SIMILARITY

Questa tabella e stata costruita al fine di salvare, per ogni regione

“id region”, le k regioni piu simili (e.g. k = 10) ad essa, indica-

te in “sim region”, riportando il corrispondente valore di similarita

(“sim”) calcolato utilizzando i metodi estratti da Windsurf.

Visto che il calcolo di tali valori e strettamente correlato al processo di

navigazione attuato dal Random Walk with Restart e che quest’ultimo

puo, durante il suo processo di attraversamento, toccare sia nodi regio-

ne sia nodi etichette e necessario indicare, in caso di un passaggio sui

nodi etichette, l’ontologia di appartenenza di queste ultime nel campo

“ontology”.

La primary key e costituita dalla tripla (“id region”, “sim region”,

“ontology”).

Si noti che tutte le frecce, che sono indicate in Figura 4.2, sono state inserite

per mettere in evidenza i vincoli di foreign key fra le varie tabelle.

4.2 Interfacciamento con il database MySql 101

Figura 4.2: Diagramma che mostra lo schema del database “mmg” evi-

denziando i vincoli di “primary key” e di “foreign key” presenti in

esso.

102 Imagination

3 Integrazione di una molteplicita di tasso-

nomie

L’ontologia rappresenta il tentativo di formulare uno schema concettuale

esaustivo e rigoroso nell’ambito di un dato dominio; si tratta generalmen-

te di una struttura dati gerarchica che contiene tutte le entita rilevanti, le

relazioni esistenti fra di esse, le regole, gli assiomi, ed i vincoli specifici del

dominio stesso. Un esempio di ontologia viene mostrato in Figura 4.3. In esso

viene messo in evidenza come i concetti, appartenenti a due diverse ontologie,

si possono correlare mediante la presenza di una molteplicita di relazioni.

L’ontologia per eccellenza e quella rappresentata da WordNet. WordNet,

per i cui dettagli si puo far riferimento a [2], a [3] ed a [4], e una rete se-

mantica realizzata presso l’universita di Princeton da un gruppo di ricerca

guidato da George Miller che si basa su teorie psicolinguistiche sull’organiz-

zazione della memoria lessicale. Nel sistema consultabile online nomi, verbi,

aggettivi e avverbi sono organizzati in un insieme di sinonimi ognuno dei

quali rappresenta un concetto lessicale di base. La principale differenza fra

WordNet e un dizionario standard e, infatti, la suddivisione dell’ontologia in

queste quattro categorie sintattiche di base.

Il vantaggio di questa suddivisione e che ogni categoria e organizzata seman-

ticamente in modo diverso; ad esempio, i nomi sono organizzati in memoria

all’interno di gerarchie specifiche, i verbi sono organizzati con una varieta

di relazioni concatenate, gli aggettivi e gli avverbi sono, invece, organizzati

come iperspazi n-dimensionali. Un unico principio organizzativo per tutte le

categorie sintattiche avrebbe mal rappresentato, infatti, la complessita della

conoscenza lessicale.

Ai fini dell’annotazione automatica di immagini ci siamo serviti dell’ontolo-

gia WordNet, dal punto di vista dei nomi e del significato ad essi connesso,

per consentire ad un utente di poter annotare il training set di immagini

campione accedendo ai termini facenti parte di tale ontologia. Ci siamo, in-

fatti, diffusamente soffermati sulla problematica connessa alla soggettivita

dell’annotazione nel senso che utenti diversi potrebbero scegliere di annotare

la stessa immagine con parole diverse, ma sinonime. E’ necessario utilizzare,

dunque, le parole provenienti da una ontologia di dominio per cercare di evi-

4.3 Integrazione di una molteplicita di tassonomie 103

Figura 4.3: Esempio di piu gerarchie di concetti connesse mediante un set di

differenti relazioni.

104 Imagination

tare questa problematica di fondo.

Ci siamo resi conto che, pero, WordNet e davvero un’ontologia molto ricca

ed estesa che rischia spesso e volentieri di non essere poi cosı appropriata se,

come nel nostro caso, l’obiettivo e quello di testare gli algoritmi per la gestio-

ne dell’etichettamento automatico di immagini lavorando su domini molto

piu ristretti e specifici riguardanti un certo ambito. Proprio per questo mo-

tivo si e pensato di creare un sistema, Jont di cui si fornira una descrizione

dettagliata nei paragrafi successivi, in grado di occuparsi dell’editing delle

ontologie. Un utente puo costruirsi la sua ontologia e decidere di andare ad

annotare le immagini, appartenenti al training set, con i termini appartenenti

ad essa. Per l’etichettamento e prevista la possibilita di annotare le immagi-

ni mediante una molteplicita di termini appartenenti a differenti tassonomie

gerarchiche di concetti. Un esempio di ontologie ad hoc, realizzate apposi-

tamente per rappresentare il nostro contesto di azione, sono molto simili a

quelle rappresentate in Figura 4.4.

Figura 4.4: Due esempi di ontologie ad hoc che, singolarmente, possono essere

utilizzate per l’etichettamento del training set.

4.4 Architettura software 105

4 Architettura software

Prima di andare a presentare l’interfaccia grafica delle due applicazioni Ima-

gination e Jont, andiamo a descrivere nel dettaglio l’architettura software

che e stata realizzata per applicare concretamente le tecniche illustrare nel

capitolo precedente. Tale descrizione avverra tenendo conto della suddivisio-

ne in vari package delle due applicazioni per meglio distinguere le diverse

funzionalita ed essere coerenti con la modularita delle stesse.

4.1 Considerazioni relative al linguaggio

L’applicazione e stata sviluppata utilizzando il Java framework su piattafor-

ma Macintosh OS X 10.4 (Tiger). La versione di Java utilizzata e la 1.5,

in quanto giudicata ormai sufficientemente matura ed implementata su tutte

le principali piattaforme (OS X, Linux, Windows).

La decisione del cambio di linguaggio, diverso dal C++ delle librerie Wind-

surf originali, e stata presa alla luce delle difficolta incontrate (e comunque

risolte) nel porting delle librerie C++ su piattaforma OS X, difficolta che

hanno portato a delle considerazioni sulla necessita di riscrivere o, comun-

que, adattare le librerie in caso di porting successivi su altre piattaforme. Nel

caso di Java il porting e invece a costo zero, ed anche l’interfacciamento con

il database MySql e reso molto piu facile che in C++ grazie alla disponibilita

del driver JDBC.

4.2 Struttura di Imagination

Il prototipo Imagination e stato organizzato in modo da mantenere un li-

vello di modularita strutturale. In esso possiamo identificare un insieme di

package in cui, ognuno di essi, riveste un set ben definito di responsabilita.

L’obiettivo e ora quello di andare a puntualizzare tali ruoli evidenziandone

le caratteristiche di base. La struttura complessiva dei package puo essere vi-

sualizzata nella sua interezza in Figura 4.5. In questo diagramma sono stati

riportati per completezza i legami fra le differenti classi e, di conseguenza,

fra i package corrispondenti.

106 Imagination

Figura 4.5: Architettura generale dell’applicazione Imagination dal punto di

vista dei package e delle classi in essi contenute.

4.4.2 Struttura di Imagination 107

Package jwindsurf

Contiene le librerie Windsurf, necessarie per ottenere la similarita fra le re-

gioni della collezione di immagini.

Nella prima versione dell’applicazione, in una politica generale di riutilizzo

del software scritto in precedenza, il package era solo un’interfaccia JNI verso

le librerie Windsurf originali scritte nel linguaggio C++. Solo una piccola

parte di tali librerie veniva, pero, effettivamente utilizzata, in particolare si

chiedeva di ricavare dall’intera collezione delle immagini una lista delle k re-

gioni piu simili alla regione data come query (ovvero k-NN query).

I primi test dell’applicazione hanno, pero, messo in evidenza tempi molto

lunghi per il calcolo di questa query k-NN, tempi che andavano ad influire

negativamente in maniera abbastanza evidente sui tempi di risposta dell’ap-

plicazione stessa nel suo complesso.

Il problema e stato individuato nell’utilizzo di file di testo per memorizzare

tutte le feature connesse alle regioni di tutte le immagini della collezione, file

evidentemente troppo grandi per permettere un rapido accesso ed un veloce

reperimento delle informazioni desiderate.

Per ovviare a questo problema, tutte le informazioni, contenute nei file di

testo, sono state trasferite nel database MySql (di cui si e ampiamente di-

scusso nei paragrafi precedenti), in modo da consentire un accesso molto piu

veloce e mirato alle feature, grazie anche all’utilizzo del linguaggio Sql per la

gestione delle interrogazioni fatte sul database “mmg” creato.

Le classi implementate per il trasferimento dei dati da file su database, ov-

vero Filler e Filler 1 , sono state mantenute, memorizzate all’interno del

package imagination.sql, in quanto potrebbero servire in futuro come me-

diatori per consentire la comunicazione fra un’altra eventuale applicazione,

che potrebbe essere utilizzata per l’estrazione delle feature dalle immagini

mediante tecniche diverse da quelle che vengono proposte da Windsurf, e la

nostra.

Una volta effettuata la conversione delle informazioni da file a database, il

package jwindsurf e stato radicalmente riscritto incorporando in esso una

parte delle librerie Windsurf e svincolandolo totalmente dall’uso del JNI,

garantendo cosı una totale portabilita dell’applicazione su qualsiasi piatta-

108 Imagination

forma con una Java Virtual Machine ed un database MySql (opensource).

L’interfacciamento con il database e garantito dal package imagination.sql,

distinto dal resto dell’applicazione per seguire una logica di massima modu-

larita e permettere il riutilizzo del software.

Per velocizzare ulteriormente l’accesso alle informazioni sulle immagini e sta-

to implementato un caching delle stesse, quindi all’avvio (se la memoria lo

permette) le feature statiche relative alle immagini vengono caricate in strut-

ture dinamiche per accelerare ancora di piu l’accesso ad esse grazie anche

all’utilizzo di tecniche di hashing per il reperimento delle regioni desiderate.

• Classe WUtility

Tale classe incorpora la maggior parte dei metodi relativi alle opera-

zioni tra matrici, usati dal metodo principale che calcola la distanza

di Bhattacharyya fra le feature connesse alle regioni in cui le immagini

possono essere segmentate.

• Classe Distance

Tale classe e un contenitore. A fronte di una k-NN query il risultato e

un vettore di istanze di questa classe. Tali istanze contengono la regio-

ne simile, l’immagine a cui essa appartiene e il valore di similarita di

questa con la regione query.

• Classe WArray

Tale classe contiene un insieme di strutture di supporto alla classifica-

zione ed indicizzazione dei dati della collezione.

• Classe WRegion

Tale classe contiene una singola regione e tutte le feature ad essa con-

nesse. E in grado di costruirsi a partire da un ResultSet e di restituire

la sua distanza con un’altra regione dello stesso tipo.

• Classe RegionCollection

Tale classe e una struttura che contiene all’interno tutte le regioni ed

implementa il metodo che consente di confrontare la regione, data come


input, con tutte le regioni, contenute all’interno della collezione (a pre-

scindere dalle immagini alle quali appartengono), secondo la distanza

di Bhattacharyya e restituendo le k regioni piu simili ad essa.

Package wordnetexplorer

In questo package si va ad indagare tutto cio che e connesso alla possibi-

lita di integrare la presenza dell’ontologia lessicale WordNet all’interno del

sistema per la gestione dell’etichettamento automatico di immagini. Benche

si abbia la consapevolezza che spesso WordNet risulta eccessivamente im-

mensa, come ontologia, rispetto ai nostri obiettivi e che, in realta, sarebbe

sufficiente creare delle tassonomie molto piu semplici ed ad hoc cablate per

i nostri scopi, e stato deciso di inserirla all’interno del sistema Imagination

primo per dare un’idea di generalita, secondo per testare, durante le prime

fasi, l’algoritmo di etichettamento automatico senza doverci eccessivamente

concentrare sull’origine ontologica dei concetti stessi.

• Classe Synset

Tale classe consente di rappresentare un concetto appartenente all’onto-

logia WordNet specificando, in particolare, anche il suo identificativo

numerico.

• Classe WnSql

Tale classe gestisce la connessione con il database “wn pro mysql”

implementando, in linguaggio Sql, le richieste di accesso a quest’ultimo

che provengono dalle altre classi.

Essa implementa i metodi necessari a cercare i lemmi nell’ontologia,

ad associarli alle loro descrizioni ed a costruire l’albero visualizzato nel

frame. Questa classe segue la logica di costruzione del pattern Single-

ton.

• Classe WordnetExplorer

Tale classe rappresenta l’interfaccia grafica di accesso all’ontologia Word-

Net permettendo di effettuare una ricerca per parole all’interno della

110 Imagination

stessa.

Package imagination.sql

Questo package garantisce l’accesso al database grazie alla classe singleton

MySqlConnector ed incorpora le classi Filler e Filler 1 che vengono

utilizzate per il trasferimento delle feature da file a database.

MySqlConnector e stato implementato secondo il pattern Singleton, quin-

di tutte le classi che all’interno dell’applicazione lavorano con esso si riferisco-

no alla stessa istanza, garantendo cosı lo sharing della connessione al database

ed una corretta apertura e chiusura della stessa rispettivamente all’avvio ed

al termine dell’applicazione. Questa classe offre tutti i metodi per accedere

al database dell’applicazione tranne quelli relativi a WordNet, contenuti in

un altro database e, quindi, in un’altra classe creata appositamente. I me-

todi sono di supporto a tutte le funzioni dell’applicazione, fra cui il caching

iniziale, l’etichettamento automatico ed il mapping ontologico.

• Classe MySqlConnector

Tale classe gestisce la connessione con il database “mmg” implemen-

tando, in linguaggio Sql, le richieste di accesso a quest’ultimo che pro-

vengono dalle altre classi.

• Classe SimComputer

Per ogni ontologia e per ogni immagine etichettata con i termini che

provengono da quest’ultima, questa classe implementa la procedura of-

fline che consente di ricavare le k regioni piu simili a ciascuna delle

regioni che appartengono all’immagine stessa.

• Classe Filler

Tale classe ha la responsabilita di prendere i dati, relativi a come opera

Windsurf dal punto di vista del recupero delle immagini, salvati su fi-

le e di inserirli all’interno del database “mmg” nella tabella id match.


• Classe Filler 1

Tale classe ha la responsabilita di prendere i dati, relativi a come ope-

ra Windsurf dal punto di vista della segmentazione delle immagini in

regioni e del corrispondente recupero delle feature di basso livello con-

nesse a queste ultime, salvati su file e di inserirli all’interno del database

“mmg” nella tabella features.

Package imagination.ontology

In questo package e inserita la classe base in grado di implementare l’al-

goritmo di mapping ontologico di cui parla dettagliatamente in [29].

• Classe OntologyWalker

Tale classe, dato un termine appartenente ad una ben definita ontolo-

gia di dominio, restituisce l’elenco dei k termini piu simili appartenenti

ad un’altra ontologia implementando l’algoritmo di mapping ontologico

descritto nel dettaglio in [29].

Package imagination.ontology.gui

Tale package ha la responsabilita di gestire la visualizzazione della strut-

tura gerarchica dell’ontologia, una volta che essa stessa e stata selezionata.

Nel paragrafo successivo andremo ad indagare nel dettaglio il modo in cui si

puo accedere a questa parte dell’interfaccia grafica andando a vedere in che

modo si puo gestire l’interazione con essa.

• Classe OntologyViewer

Tale classe consente di visualizzare la struttura di un’ontologia, met-

tendone in luce le sue caratteristiche dal punto di vista gerarchico, una

volta che essa e stata selezionata.

Package imagination.similarity

In questo package ci si concentra sulla presentazione di tutte le classi che

112 Imagination

sono state create per utilizzare l’algoritmo PSimRank ovvero per arrivare a

costruire, come fine ultimo, una tabella all’interno del database “mmg” che

consenta di definire la similarita, calcolata ricorsivamente una volta costruito

il bipartite graph fra le immagini e le etichette coinvolte, fra tutte le coppie

di concetti utilizzati per l’etichettamento del training set.

• Classe SetUtility

Tale classe offre la possibilita di computare le operazioni insiemistiche,

ovvero unione, intersezione e differenza, fra due insiemi. Essa viene

utilizzata nel calcolo dei coefficienti necessari all’applicazione dell’algo-

ritmo PSimRank.

• Classe ImageSimMatrix

Tale classe offre possibilita di gestire una matrice in cui vengono me-

morizzati i valori di similarita, calcolati mediante l’applicazione del-

l’algoritmo PSimRank, fra le coppie di immagini che costituiscono il

training set. Tali valori vengono aggiornati, ad ogni iterazione dell’al-

goritmo stesso, finche non si raggiunge la convergenza.

• Classe LabelSimMatrix

Tale classe offre possibilita di gestire una matrice in cui vengono me-

morizzati i valori di similarita, calcolati mediante l’applicazione dell’al-

goritmo PSimRank, fra le etichette che annotano il training set. Tali

valori vengono aggiornati ad ogni iterazione dell’algoritmo finche non

si raggiunge la convergenza.

• Classe MyComparator

Tale classe svolge il ruolo di comparatore fra due entita. Essa riveste un

ruolo di rilievo poiche e di aiuto nella gestione di ordinamenti di vettori.

• Classe PSimRank

Tale classe ha la responsabilita di implementare le formule ricorsive che

vengono utilizzate nell’applicazione dell’algoritmo PSimRank.


• Classe PSimRanker

Tale classe consente di calcolare, per ogni concetto appartenente ad

una certa ontologia, i valori di similarita con tutti gli altri termini ap-

partenenti ad essa utilizzando l’algoritmo PSimRank e sfruttando la

struttura di grafo bipartito fra immagini ed etichette in grado di anno-

tare le immagini stesse (per fare cio si utilizza il training set di immagini

campione gia etichettate).

• Classe RWR

Tale classe implementa l’Algoritmo 2, che e stato descritto nel detta-

glio nel capitolo precedente, ma senza imposizione di vincoli sul numero

di volte in cui l’algoritmo deve attuare la fase di “RESTART”.

• Classe RandomWalker

Tale classe utilizza RWR per portare a termine l’implementazione

dell’Algoritmo 2 imponendo il vincolo sul numero di volte in cui l’al-

goritmo deve attuare la fase di “RESTART”.

Package imagination.graph

In questo package ritroviamo tutte le classi che sono coinvolte nell’appli-

cazione dell’Algoritmo 4. In questa sezione ci si occupa di definire tutti i

metodi per poter lavorare con un clique e per poter rappresentare il grafo da

cui i clique stessi devono essere estratti.

• Classe Clique

Questa classe contiene tutti i metodi necessari per lavorare con un cli-

que rappresentandolo in tutta la sua interezza.

• Classe Graph

Tale classe e in grado di rappresentare il grafo di cui si parla negli al-

goritmi Algoritmo 3 e Algoritmo 4. Esso e composto da un insieme

di vertici, che rappresentano i termini con piu alto valore di frequenza

114 Imagination

restituiti dall’applicazione del Random Walk with Restart, e da un in-

sieme di archi in grado di definire il valore di similarita fra ogni coppia

di termini solo se tale valore, calcolato mediante l’applicazione dell’al-

goritmo PSimRank, e superiore ad un ben definito parametro di soglia,

vale a dire C2. A partire dalla struttura di questo grafo si vogliono iden-

tificare i clique in esso contenuti, con l’obiettivo di generare in uscita il

clique a massima frequenza di cui ampiamente si e discusso nel capitolo

precedente.

Package imagination.graph.drawing

In questo package ci si occupa della rappresentazione, dal punto di vista

grafico, di cio che viene generato mandando in esecuzione gli algoritmi Al-

goritmo 3 e Algoritmo 4. In questa sottosezione ci si concentra dunque

sulla creazione, dal punto di vista grafico, del grafo che consente di collegare

i concetti, estratti in prima battuta dall’applicazione dell’Algoritmo 2, e le

similarita fra di essi in modo da poter estrarre dal grafo stesso tutti i possibili

clique. Sempre graficamente si gestisce, inoltre, la visualizzazione del clique

a massima frequenza che viene restituito come risultato finale per l’utente.

• Classe CliqueDrawing

Questa classe e un’interfaccia grafica per la visualizzazione concreta di

cio che viene creato mandando in esecuzione gli algoritmi Algoritmo

3 e Algoritmo 4. Grazie a tale classe, infatti, viene resa possibile la

visualizzazione del grafo di concetti e similarita mettendo in luce il cli-

que a massima frequenza che, al termine, viene restituito.

Package imagination.gui

In questo ultimo package ritroviamo tutte le classi che sono coinvolte nella

creazione e nella gestione dell’interfaccia grafica principale del sistema Ima-

gination la quale verra spiegata nel dettaglio nel paragrafo successivo. Da

questa interfaccia tutto il sistema viene monitorato e gestito. Grazie ad essa

si offre all’utente il controllo di tutte le funzioni esaminate nelle descrizioni

4.4.3 Struttura di Jont 115

dei package precedenti.

• Classe SettingsFrame

Tale classe viene utilizzata da quella principale ImaginationFrame .

Essa consente di associare ad ogni parametro di soglia un ben definito

valore, prima di far eseguire l’applicazione stessa. Ad ogni parametro e

associato un valore di default di cui si parlera diffusamente in uno dei

paragrafi successivi.

• Classe JImagePanel

Tale classe viene utilizzata dalla classe principale ImaginationFrame

per gestire l’interfaccia grafica complessiva dell’applicazione.

• Classe ImaginationFrame

Tale classe rappresenta l’interfaccia grafica complessiva di gestione del-

l’applicazione. Da essa e possibile svolgere tutta una seria di operazioni

di base che possono consentire sia di applicare l’etichettamento auto-

matico di immagini sia di portare a compimento la fase di mapping

ontologico. La modalita di funzionamento di tale interfaccia verra de-

scritto nel dettaglio nei paragrafi successivi.

4.3 Struttura di Jont

Jont e un’applicazione “satellite”, rispetto a quella principale, che verra me-

glio descritta, dal punto di vista grafico, nel paragrafo successivo.

E stata introdotta per fornire velocemente piccole ontologie personalizzate

da usare negli esempi sia di etichettamento automatico di immagini sia di

mapping ontologico.

Essa permette di costruire l’albero di un’ontologia, partendo dai termini de-

finiti dall’utente, consentendo di connetterli sfruttando la relazione genitore-

figlio. Le operazioni, che possono essere svolte da questa applicazione, ri-

guardano la possibilita di aggiungere termini, eliminarli, spostarli nel piano

di lavoro ed aggiungere collegamenti fra ogni coppia di termini stessi. Tale

116 Imagination

applicazione si occupa, inoltre, dei controlli per evitare cicli, auto-link ed e

responsabile di fornire un’ontologia ben formata con un’unica radice. Il menu

di interazione con essa consente di mostrare le ontologie presenti nel databa-

se, salvare l’ontologia corrente, caricarne una gia esistente per modificarla o

eliminarla nel caso non sia piu rilevante per gli scopi proposti.

La struttura complessiva dei package puo essere visualizzata nella sua inte-

rezza in Figura 4.6. In questo diagramma sono stati riportati per completezza

i legami fra le differenti classi e, di conseguenza, fra i package corrispondenti.

Figura 4.6: Architettura generale dell’applicazione Jont dal punto di vista dei

package e delle classi in essi contenute.

Package jont

Questo package contiene le classi che consentono di accedere all’applicazione

di editing delle ontologie.

• Classe Main

Tale classe rappresenta semplicemente il punto di ingresso per accedere

all’applicazione principale contenuta nella classe MainFrame .

4.4.3 Struttura di Jont 117

Package jont.sql

Questo package contiene le classi che consentono di gestire l’accesso al da-

tabase. SqlConnector e stato implementato secondo il pattern Singleton,

quindi tutte le classi che all’interno dell’applicazione lavorano con esso si

riferiscono alla stessa istanza, garantendo cosı lo sharing della connessione

al database ed una corretta apertura e chiusura della stessa rispettivamente

all’avvio ed al termine dell’applicazione.

• Classe SqlConnector

Tale classe ha il compito di gestire l’accesso al database “mmg”, alla

tabella ontologies, nel quale viene fatto il salvataggio dell’ontologia

durante il suo processo di costruzione sfruttando la relazione genitore-

figlio. In linguaggio Sql tale classe implementa le richieste di accesso al

database che provengono dalle altre classi.

Package jont.gui

Questo package contiene, infine, tutte le classi in grado di gestire l’interfaccia

grafica dell’applicazione. Si disegna, di conseguenza, un’ontologia a partire

dai singoli concetti costitutivi della stessa che vengono introdotti dall’utente.

L’effetto finale e l’editing di una struttura ontologica gerarchica che viene

salvata all’interno del database “mmg”.

• Classe Concept

Questa classe ha il compito di rappresentare, anche da un punto di

vista grafico, l’idea del “concetto” che entra a fare parte di una certa

ontologia.

• Classe MainFrame

Questa classe si occupa dell’interfaccia grafica dell’applicazione. Grazie

ad essa si ha la possibilita di accedere alla differenti utility messe a

disposizione da essa. Essa permette di costruire l’albero di un’ontolo-

gia, partendo dai termini definiti dall’utente, consentendo di connetterli

118 Imagination

sfruttando la relazione genitore-figlio.

5 Interfaccia grafica di Imagination

Descriviamo ora l’interfaccia grafica del nostro sistema Imagination con l’o-

biettivo di comprendere meglio il funzionamento dell’etichettamento auto-

matico.

La Figura 4.7 mostra l’interfaccia grafica dell’applicazione. All’avvio vengo-

no caricate, dal database “mmg”, tutte le categorie delle immagini a di-

sposizione e, per ogni categoria, vengono caricate le immagini che ad essa

appartengono. Ogni volta che, con il mouse, si seleziona un’immagine ne vie-

ne visualizzata una sua miniatura. Nell’area di testo “Labels” sono indicate

le etichette effettive dell’immagine ovvero quelle che sono state associate in

modo definitivo a quest’ultima. In questo caso, come si puo notare, l’imma-

gine non e ancora stata etichettata e per questo motivo l’area di testo risulta

vuota.

Per attivare la fase di etichettamento ci sono due opzioni:

1. Fare click sul pulsante “Query” nel caso si voglia, in qualche modo,

monitorare la fase di etichettamento immagine per immagine.

2. Fare click sul pulsante “Auto caption!” nel caso in cui si vogliano

etichettare tutte le immagini del database avendo a disposizione un

training set di immagini gia etichettate sufficiente per gestire una buona

fase di etichettamento.

Ci concentriamo ora sul primo caso.

Supponiamo di aver selezionato, dunque, un’immagine non ancora etichetta-

ta e di aver fatto click sul tasto “Query”. Il sistema, utilizzando la tecnica

di cui abbiamo ampiamente discusso nel capitolo precedente, genera delle

potenziali etichette da attribuire all’immagine. Nell’esempio di Figura 4.7 il

sistema genera le etichette “bear”, “grass”, “ground” e “water” tutte corrette

rispetto a quella che e l’immagine che effettivamente sta per essere etichet-

tata. A questo punto l’utente puo fare click sul pulsante “Assign terms”

e, automaticamente, tutti i termini contenuti nell’area di testo contenente

4.5 Interfaccia grafica di Imagination 119

le “potenziali” etichette verranno assegnati in modo permanente all’area di

testo “Labels” e diventeranno etichette definitive per quell’immagine.

Si e deciso di riportare qui un set di esempi, quelli proposti nelle differenti

Figure 4.8, 4.9 e 4.10, che mostrano come il sistema e in grado di generare

buone etichette, in numero variabile a seconda delle immagini prese in esame,

sottoponendo immagini tutte differenti e direttamente alla prima applica-

zione dell’algoritmo. Concretamente, infatti, premendo piu volte il pulsante

“Query”, il sistema tende a generare un set di etichette per la maggior par-

te uguali con alcune varianti. Questo accade perche l’innovativo approccio di

annotazione proposto utilizza per prima cosa il Random Walk with Restart,

che segue cammini sempre casuali operando di conseguenza con un margine

di variabilita e, seconda cosa, nei due algoritmi che sono alla base della nostra

tecnica si utilizzano due valori di soglia (C1 e C2) che, in ogni caso, influen-

zano non solo il numero di termini che effettivamente vengono generati dal

sistema per la gestione dell’etichettamento automatico, ma anche il valore

assunto da tali termini a seconda della posizione che essi occupano nella lista

finale una volta che tutte le formule algoritmiche sono state applicate.

Graficamente si e deciso di mostrare anche il perche delle etichette generate

ovvero il clique a massima frequenza che e responsabile della generazione fi-

nale dei termini che il sistema e in grado di restituire.

Vengono infatti selezionati i, supponiamo x, termini a frequenza massima

che vengono catturati mediante il Random Walk with Restart, e tali concetti

vengono connessi fra loro solamente se il valore di similarita, computato me-

diante l’algoritmo PSimRank, supera un definito valore di soglia. A questo

punto il grafo presenta un insieme di nodi e di connessioni di colore azzurro.

Nel momento in cui si chiede al sistema di effettuare l’etichettamento auto-

matico di una nuova immagine si vuole fare in modo che il sistema stesso sia

in grado di definire quali sono i termini che, con maggiore probabilita, pos-

sono essere i potenziali annotatori per l’immagine oggetto di interrogazione.

Per fare cio si identificano tutti i clique all’interno del grafo di concetti e, per

ognuno di essi, si calcola lo “score”, ovvero si fa la sommatoria di tutte le

frequenze associate ai termini che costituiscono il clique in esame. Fra tutti i

clique si restituisce in uscita quello con il massimo valore di frequenza ad esso

associato che, dal punto di vista grafico, viene rappresentato con un insieme

120 Imagination

di nodi e di connessioni di colore rosso. Nel pannello di visualizzazione sono,

infine, presentati non piu solamente i termini che costituisco il clique a fre-

quenza massima, bensı anche lo score complessivo associato al clique stesso

restituito.

Tutti gli esempi che sono riportati di seguito mostrano non solamente le

etichette generate, ma anche il clique a massima frequenza prodotto grafica-

mente in uscita con il valore di score stesso.


Figura 4.7: Interfaccia grafica dell’applicazione. Primo esempio di ge-

nerazione automatica di etichette tutte corrette al fine dell’annotazione

automatica.

122 Imagination

Figura 4.8: Interfaccia grafica dell’applicazione. Secondo esempio di gene-

razione automatica di etichette tutte corrette al fine dell’annotazione au-

tomatica. Visualizzazione del clique a massima frequenza responsabile della

restituzione di tali termini.


Figura 4.9: Interfaccia grafica dell’applicazione. Terzo esempio di generazio-

ne automatica di etichette tutte corrette al fine dell’annotazione automatica.

Visualizzazione del clique a massima frequenza responsabile della restituzione

di tali termini.

124 Imagination

Figura 4.10: Interfaccia grafica dell’applicazione. Quarto esempio di gene-

razione automatica di etichette tutte corrette al fine dell’annotazione au-

tomatica. Visualizzazione del clique a massima frequenza responsabile della

restituzione di tali termini.


In Figura 4.11 viene riportato un esempio di errata generazione di un termi-

ne da parte del sistema. Dal momento che l’utente decide, in questo primo

caso, di monitorare l’etichettamento, egli stesso puo intervenire fornendo un

feedback di rilevanza nei confronti dei termini proposti. Egli puo, conseguen-

temente, selezionare il termine improprio generato e fare click sul pulsante

“Remove term” per rimuoverlo dalla lista di potenziali etichette. A questo

punto l’utente puo fare click sul pulsante “Assign terms” e, automatica-

mente, tutti i termini contenuti nell’area di testo contenente le “potenziali”

etichette verranno assegnati in modo permanente all’area di testo “Labels”

e diventeranno etichette definitive per quell’immagine.

Nel secondo caso invece, ovvero nel momento in cui l’utente decide si premere

il pulsante “Auto caption!”, si ha un etichettamento automatico di tutte

le immagini non ancora annotate senza nessun intervento di feedback lato

utente. Affinche l’etichettamento sia in grado di fornire delle buone etichette

complessivamente e opportuno partire da un training set di immagini gia

annotate sufficientemente corposo in modo da innalzare la probabilita di una

corretta generazione di termini.

A questo punto dobbiamo soffermarci su quali sono le utility a livello di

sistema che ci consentono di andare ad annotare manualmente le immagi-

ni, che costituiscono il training set, avendo al consapevolezza che i termini,

che vengono utilizzati per l’etichettamento, non possono essere scelti sog-

gettivamente, ma devono far parte di una o piu ontologie, ovvero strutture

gerarchiche, di concetti.

In Figura 4.12 si mostra semplicemente come, a fronte della pressione del ta-

sto “Show wordnet”, il sistema e in grado di caricare i termini classificati

secondo l’ontologia WordNet. L’interfaccia grafica e suddivisa infatti in due

pannelli, nel primo e rappresentata la parte dell’ontologia che stiamo attual-

mente esplorando, mentre il secondo, quello di destra, contiene la descrizione

del termine. L’utente deve inserire il nome approssimativo con cui vorrebbe

etichettare l’immagine, deve fare click sul pulsante “Search”, a questo punto

WordNet generera il sotto-albero a partire dalla parola inserita. L’utente

potra scegliere con quale livello di dettaglio etichettare l’immagine in base

alla gerarchia di parole restituite dall’ontologia stessa. Premendo il pulsante

“Reset tree” il sistema e in grado di ricaricare la struttura gerarchica inizia-

126 Imagination

Figura 4.11: Generazione di un sottoinsieme di etichette corrette. Rimo-

zione di quelle generate erroneamente e definitivo assegnamento di quelle

appropriate all’immagine.


le di WordNet. Una volta scelto il termine corretto, l’utente dovra premere

il tasto “Add term” per inserire il termine nell’area di testo in cui si trovano

tutti i potenziali termini candidati per l’etichettamento.

Vista la dimensione proibitiva dell’ontologia WordNet non e stato possibile

caricarla tutta in memoria, quindi l’albero e di tipo “dinamico”, ovvero ad

ogni esplorazione di un termine che non sia foglia, il sottoalbero relativo vie-

ne caricato dal database a tempo di esecuzione fino ad una profondita pari

a due livelli. Tutto cio non rallenta l’esplorazione dell’albero, quindi questa

soluzione e risultata molto soddisfacente in fase di realizzazione pratica.

In realta, come abbiamo gia spiegato nei paragrafi precedenti, ci siamo resi

conto che WordNet e davvero un’ontologia molto ricca ed estesa che rischia

spesso e volentieri di non essere poi cosı appropriata se, come nel nostro caso,

l’obiettivo e quello di testare gli algoritmi per la gestione dell’etichettamento

automatico di immagini lavorando su domini molto piu ristretti e specifici ri-

guardanti un certo ambito. Proprio per questo motivo si e pensato di andare

ad annotare le immagini con i termini appartenenti ad una molteplicita di

differenti tassonomie gerarchiche di concetti create ad hoc per i nostri scopi

e sicuramente molto meno ampie dell’ontologia lessicale WordNet.

Nella Figura 4.13 vengono mostrate due differenti esempi di ontologie una

composta dai termini italiani ed una composta dai termini inglesi. Come si

nota le due, pur memorizzando gli stessi termini da un punto di vista con-

cettuale presentano delle strutture gerarchiche completamente diverse. Con

ciascuna di queste ontologie si e andato ad etichettare un training set diver-

so di immagini. Questo e stato utile per andare a testare la fase di mapping

ontologico i cui dettagli sono riportati in [29]. La cosa che vogliamo puntualiz-

zare pero e che, per l’annotazione di uno dei due training set, per semplicita,

abbiamo utilizzato un’unica ontologia in grado di unire gli aspetti legati sia

al mondo naturale sia al mondo animale. Ovviamente questa e stata una

scelta semplicistica poiche, in realta, per ogni training set che era necessario

etichettare, si sarebbero potuti utilizzare i contenuti provenienti da una mol-

teplicita di ontologie proprio perche, per ipotesi, il nostro scenario di lavoro

e multitassonomico.

128 Imagination

Figura 4.12: Interfaccia di caricamento dell’ontologia WordNet.


Figura 4.13: Ontologie create ad hoc sia per la gestione dell’etichettamento

automatico, sia per il mapping ontolgico.

130 Imagination

Il menu “Ontology”, visibile in dettaglio in Figura 4.14, permette di mostra-

re le ontologie presenti nel database mediante la scelta “Show Ontologies”

e di scegliere quella da utilizzare per l’etichettamento o il mapping mediante

“Set Ontology”. Ogni volta che l’ontologia corrente viene cambiata, l’ap-

plicazione si aggiorna e mostra le etichette che le immagini hanno rispetto

all’ontologia correntemente selezionata. Mediante “Restore Training Set”

e possibile fare un ripristino del training set originario.

L’ultima parte che deve essere sviscerata, dal punto di vista dell’interfaccia

grafica, riguarda la finestra di dialogo “Settings” grazie alla quale e possi-

bile assegnare dei valori, variando quelli di default, ai parametri che devono

essere utilizzati all’interno dei vari algoritmi di cui abbiamo parlato nel ca-

pitolo precedente. Tale finestra e visibile in Figura 4.15 e i dettagli connessi

a tali parametri saranno esposti nei paragrafi successivi.

Figura 4.14: Dettaglio del menu Ontology dell’applicazione, che consente di

visualizzare le ontologie disponibili e di selezionare una di esse per poi usarla

per l’etichettamento/mapping.

Figura 4.15: Dettaglio del menu Settings dell’applicazione, che consente di

assegnare dei valori, variando quelli di default, ai parametri utilizzati dagli

algoritmi.

4.6 Interfaccia grafica di Jont 131

6 Interfaccia grafica di Jont

Jont e un’applicazione disgiunta rispetto a quella principale, che si presenta

graficamente come viene mostrato in Figura 4.16.

E stata introdotta per fornire velocemente piccole ontologie personalizzate da

usare negli esempi di etichettamento e di mapping. Essa permette di costruire

l’albero di un’ontologia, strutturata gerarchicamente, partendo dai termini

definiti dall’utente e legati dal rapporto di parentela genitore-figlio.

Nella toolbar sono evidenziati i comandi connessi alla creazione ed alla ge-

stione di una nuova ontologia. Grazie al comando “Add Concept” si puo

aggiungere un nuovo concetto mentre, grazie al comando “Remove Con-

cept”, si puo gestire la sua rimozione. Con “Link Concept” si possono

connettere i vari concetti gli uni con gli altri arrivando a costruire l’ontologia

e, dal punto di vista grafico, questi possono essere spostati sul piano grazie

al comando “Move Concept”. Dal menu File e possibile gestire il carica-

mento di un’ontologia che e stata precedentemente salvata grazie al comando

“Open Ontology” oppure e possibile salvare una nuova ontologia che e sta-

ta appena creata mediante l’istruzione “Save Ontology”. Si ha, inoltre,

la possibilita di vedere visualizzata la lista di tutte le ontologie disponibili

mediante “Show Ontologies” ed, infine, e possibile gestire la cancellazione

di quelle che si ritiene che non siano piu utili mediante il comando “Delete

Ontology”.

7 Valutazioni sui parametri di Imagination

L’ambiente Imagination, creato per offrire uno strumento di test per gli al-

goritmi proposti, permette il settaggio di tutte le principali variabili che re-

golano il funzionamento del mapping ontologico e dell’etichettamento auto-

matico. Attraverso una finestra, visibile in Figura 4.15, e possibile indicare

dei valori per ognuno dei parametri proposti, per poi eseguire gli algoritmi e

prendere visione del risultato.

I valori suggeriti al momento dell’apertura del programma sono derivati da

una fase preliminare di test (illustrata piu avanti) e rappresentano un trade-

off tra risultati ottenuti e tempo di esecuzione.

132 Imagination

Figura 4.16: Interfaccia grafica dell’applicazione Jont che gestisce l’editing

delle ontologie. In alto e visibile la toolbar dei comandi relativi alla modifi-

ca dell’ontologia, mentre il menu File consente di operare con le ontologie

presenti nel database.

4.7 Valutazioni sui parametri di Imagination 133

Andiamo ora ad esaminare le singole variabili, facendo riferimento alla Figu-

ra 4.15 e agli algoritmi presentati nel capitolo precedente:

• RWR Iterations

Variabile n dell’Algoritmo 2, indica il numero di iterazioni effettuate

dal Random Walk with Restart. Questo parametro e molto delicato in

quanto incide parecchio sul tempo di esecuzione, visto che la fase di

RWR rappresenta circa il 95% del tempo complessivo di un qualsiasi

etichettamento o mapping (come detto sopra la fase PSimRank e ese-

guita offline, quindi la sua durata e irrilevante). Se le iterazioni sono

troppe, quindi, l’utente e costretto ad attendere un tempo elevato in

attesa del risultato, cosa che dovrebbe assolutamente essere evitata, ma

se le iterazioni sono troppo poche si rischia di non avere convergenza

e, quindi, di non veder restituito un risultato corretto. La convergenza

si ha quando a fronte di piu esecuzioni successive della stessa query

(concetto per il mapping o immagine per l’etichettamento) i risultati

sono sempre gli stessi, assicurando cosı una risposta costante nel tempo.

• RWR Probability

Variabile C1 dell’Algoritmo 2, e la probabilita di restart del Random

Walk. Quando il cammino si trova in un nodo del grafo, genera un valo-

re casuale fra 0 e 1 e, se questo valore e maggiore di RWR Probability,

il cammino viene fatto ripartire dal nodo iniziale (o terminare nel caso

le iterazioni siano esaurite). Molti degli algoritmi studiati che fanno uso

di RWR sono concordi nello stabilire un valore ideale della variabile a

0.8, ed il nostro caso non fa eccezione.

• RWR k-NN

Variabile k dell’Algoritmo 2, rappresenta il numero di vicini da consi-

derare nell’applicazione della query k-Nearest Neighbours ad una regio-

ne dell’immagine considerata. Con un valore troppo grande si rischia

di prendere regioni troppo dissimili da quella di partenza e, quindi, di

aumentare il “rumore”, ovvero le etichette che non hanno relazione con

la query, mentre con un valore troppo piccolo si rischia di restringere

134 Imagination

troppo la ricerca e di non esplorare a sufficienza tutto il grafo MMG.

• Clique Candidates

Variabile k dell’Algoritmo 3, ovvero il numero di etichette restitui-

te dall’Algoritmo 2 per andare a formare il grafo su cui effettuare

la ricerca dei clique. Tale ricerca rappresenta un problema NP-Hard,

quindi il numero dei nodi del grafo va attentamente valutato per evitare

di avere tempi troppo lunghi, dal momento che l’incremento anche di

una sola unita potrebbe portare all’aumento esponenziale dell’attesa.

Ovviamente con un numero di nodi troppo piccolo si rischia di lasciar

fuori un candidato che potrebbe far parte del risultato finale.

• Clique Similarity Threshold

Variabile C2 dell’Algoritmo 3, e la soglia di similarita (PSimRank)

oltre la quale due concetti vengono considerati connessi all’interno del

grafo su cui effettuare la ricerca del clique. Con una soglia troppo bas-

sa tutti i termini risultano connessi e, quindi, il grafo costituirebbe un

unico clique (risultato ovviamente errato), mentre con un valore troppo

alto i clique potrebbero non superare i due elementi, o addirittura gli

unici clique potrebbero essere quelli rappresentati dai singoli nodi. An-

che relativamente a questo parametro e necessario attribuire un buon

valore di compromesso per far fronte ai due problemi estremi. Il valore

che abbiamo deciso di associare a tale variabile, dopo aver sottoposto

l’applicazione a innumerevoli prove, e 0.3.

Per decidere quali valori possono essere ritenuti ottimali al fine di essere

applicati ai vari algoritmi, abbiamo eseguito una serie di test automatici va-

riando, di volta in volta, i parametri d’ingresso al fine di ottenere un log dei

risultati, in cui si tiene traccia anche dei tempi di esecuzione connessi alla

computazione.

Per quanto riguarda l’etichettamento abbiamo supposto di annotare l’imma-

gine rappresentata in Figura 4.17. I termini che ci aspetteremmo di ottenere

dalla sua annotazione, supponendo di utilizzare l’ontologia Gaia, sono i quat-

tro termini “ground”, “bear”, “grass” e “water”. Senza riportare nel dettaglio


i nomi di tutti i termini di volta in volta generati dal sistema, si e deciso di

inserire, all’interno delle tabelle che seguono, il numero di termini corretti ed

il numero di termini errati rispetto alla configurazione ammessa.

Nella Tabella 3, riportata di seguito, variamo il numero di iterazioni del

Random Walk with Restart, mantenendo costante il numero di termini can-

didati a massima frequenza, che vengono estratti dall’applicazione del RWR,

che sono alla base della creazione del grafo da cui devono essere estratti i

clique.

Nella Tabella 4, al contrario, manteniamo fisse a 500 il numero di iterazioni

e variamo il numero di termini che costituiscono il grafo di concetti da cui

devono essere estratti i clique.

Figura 4.17: Immagine con la quale sono state raccolte le statistiche relative

all’etichettamento.

136 Imagination

Tabella 3

N◦ iter. RWR N◦ nodi grafo Termini corretti Termini errati Secondi

50 6 2 2 4

50 6 4 0 3

50 6 4 0 2

50 6 4 0 3

50 6 4 0 2

100 6 4 0 4

100 6 2 2 5

100 6 2 2 4

100 6 4 0 4

100 6 4 0 3

200 6 4 0 9

200 6 4 0 9

200 6 4 0 7

200 6 4 0 9

200 6 3 0 10

500 6 4 0 19

500 6 4 0 21

500 6 4 0 19

500 6 4 0 22

500 6 4 0 21

1000 6 4 0 41

1000 6 4 0 45

1000 6 4 0 40

1000 6 4 0 40

1000 6 4 0 40

5000 6 4 0 190

5000 6 4 0 194

5000 6 4 0 192

5000 6 4 0 200

5000 6 4 0 200


Tabella 4

N◦ iter. RWR N◦ nodi grafo Termini corretti Termini errati Secondi

500 3 3 0 19

500 3 3 0 20

500 3 3 0 17

500 3 3 0 20

500 3 3 0 20

500 4 3 0 21

500 4 3 0 18

500 4 3 0 19

500 4 3 0 17

500 4 3 0 21

500 8 4 0 20

500 8 4 0 20

500 8 3 2 19

500 8 4 0 20

500 8 4 0 19

500 10 3 1 21

500 10 4 0 23

500 10 4 0 20

500 10 3 2 20

500 10 4 0 21

Esaminando i dati raccolti si puo notare come, per un numero di iterazioni

superiore a 500, si abbiano 5 risultati corretti su 5 tentativi effettuati (mag-

gior numero di termini corretti senza termini errati), mentre per un numero

inferiore di tentativi si riscontrano alcuni risultati errati. Questo perche piu

il RWR ha la possibilita di iterare, piu riesce ad essere preciso nella scelta

dei termini che, in qualche modo, incontra nel suo cammino. Piu iterazioni

vengono fatte e piu si alza il valore della frequenza associata ai termini a cui

piu frequentemente il RWR accede. Il valore ideale per il numero di iterazioni

compiute dal RWR, quindi, e stato impostato a 500.

Per quanto riguarda, invece, il numero di termini candidati a massima fre-

quenza, che vengono estratti dall’applicazione del RWR e che sono alla base

138 Imagination

della creazione del grafo da cui devono essere estratti i clique, si puo osservare

che, per valori inferiori a 6, i termini sono corretti, ma ne vengono restituiti

meno di quelli globalmente corretti che in realta dovrebbero essere restituiti:

si produce un taglio sul numero di termini corretti che, in potenza, potreb-

bero essere generati. Per un numero maggiore di 6, invece, i clique risultano

composti anche da termini errati, ovvero si produce in uscita un eccesso di

etichette e, per questo, alcune di queste risultano non opportune per i fini

di etichettemento o mapping. In entrambi i casi le conseguenze incidono in

maniera errata sulle etichette effettivamente restituite. Si e deciso, di conse-

guenza, di impostare il valore ideale a 6.

Un’ultima considerazione deve essere effettuata relativamente alla convergen-

za dell’algoritmo PSimRank. Va tenuto in considerazione il fatto che, grazie

alle formule ricorsive che caratterizzano tale algoritmo, possiamo computare

la similarita fra ogni coppia di immagini che fanno parte del training set e,

partendo da queste e mediante un meccanismo di rinforzo progressivo, pos-

siamo calcolare la similarita fra ogni coppia di concetti connessi alle immagini

del training set stesso. PSimRank opera ricorsivamente ed e per questo che

e necessario domandarsi in quante iterazioni e fino a che cifra decimale e

possibile ottenere la convergenza dal punto di vista dei valori.

Nella Tabella 5, riportata di seguito ed i cui valori sono stati ottenuti in via

del tutto sperimentale, si puo notare come la convergenza di valori fino alla

nona cifra decimale viene ottenuta in circa 31 iterazioni dell’algoritmo ovvero

in un numero di iterazioni sufficientemente basso da consentirci di lavorare

con un livello di precisione particolarmente elevato.

Tabella 5

Cifre decimali Iterazioni

3 12

4 14

5 18

6 21

7 25

8 28

9 31


Da ultimo si vuole precisare che i valori, relativi ai dati sperimentali ottenuti,

sono stati calcolati su piattaforma Mac OS X 10.4.3 e JVM 1.5.0 05, con

processore PowerPC G4 1,67 Ghz dotato di 1 Gb di RAM.

Conclusioni

Giunti al termine del seguente lavoro di tesi possiamo concludere di esser-

ci fatti un’idea abbastanza approfondita di quello che e stato ed e lo stato

dell’arte circa il processo di annotazione semi-automatica e automatica di

immagini.

Partendo dall’attivita di tirocinio svolta e valutando le problematiche incon-

trate, abbiamo proposto una nuova tecnica per l’etichettamento automatico

di immagini in grado di superare i limiti delineati. Si e deciso di basare la

soluzione proposta sull’utilizzo del grafo Mixed-Media Graph, in grado di cor-

relare immagini, regioni ed etichette attraversato da un navigatore libero di

muoversi su di esso, ovvero il Random Walk with Restart. L’idea innovativa,

a questo punto, e consistita nel cercare di attuare una seconda fase di raffina-

mento delle etichette, generate durante la prima navigazione mediante RWR,

in modo da aumentare il grado di precisione complessivo dell’etichettamento

automatico. Per fare cio si e utilizzato l’approccio PSimRank il quale opera

con un livello di complessita di ordine due. Con PSimRank e stato possibile

computare offline la similarita fra tutte le coppie di concetti, utilizzati per

l’etichettamento del training set, una volta creata la struttura di un bipartite

graph, fatto dalle immagini e dalle etichette in grado di annotarle. Sfruttan-

do, infine, queste due tecniche si e deciso di creare un grafo di concetti con lo

scopo di identificare, in esso, i clique con score massimo in modo da recupera-

re l’insieme di termini qualitativamente piu adatti per annotare un’immagine

non ancora etichettata.

Dall’integrazione di queste due tecniche e nato un approccio innovativo che e

stato sicuramente in grado di aumentare l’efficacia complessiva delle etichette

142 Imagination

generate, dal punto di vista qualitativo, pur mantenendo invariata l’efficien-

za. Valutando conservativamente la bonta della tecnica che e stata ideata, si

puo notare come siano stati raggiunti gli obiettivi che ci si era prefissati.

In primo luogo, abbiamo la possibilita di gestire l’etichettamento di una nuo-

va immagine mediante un insieme di etichette capaci di esprimere anche

contenuti astratti. L’etichettamento multiplo inoltre ci consente di descrive-

re meglio i differenti significati semantici associati ai contenuti proposti dalle

immagini stesse. Non e definito, infatti, il legame fra un’etichetta e le regioni

in cui l’immagine puo essere segmentata. Le etichette sono vincolate in ma-

niera forte all’immagine nella sua totalita.

In secondo luogo, il numero di etichette generate non e statico, ma e varia-

bile poiche connesso alla possibilita di restituire un insieme di valori solo se

questi fanno parte di un clique di concetti correlati in modo forte sia dalla

frequenza di attraversamento sia dalla similarita. Rendiamo di conseguenza

flessibile il numero di termini che devono andare ad etichettare un’immagi-

ne dal momento che potrebbero esistere immagini che necessitano meno di,

supponiamo t, valori di etichettamento.

L’ultima considerazione riguarda l’intervento multitassonomico. Esso inter-

viene solo nella prima fase, ovvero durante l’etichettamento del training set :

ogni immagine, che fa parte di quest’ultimo, viene etichettata con dei ter-

mini che provengono da diverse tassonomie. L’intervento multitassonomico

impedisce ad un utente di annotare le immagini con termini di sua prefe-

renza, vincolandolo in modo molto forte alla scelta di concetti facenti parte

di una struttura gerarchica organizzata. Abbiamo infatti dato la possibilita

all’utente di attingere alla gerarchia di termini WordNet per gestire l’etichet-

tamento delle immagini in modo tale da non dover incorrere nel problema

della soggettivita dell’annotazione. E stato comunque reso possibile l’utilizzo

di una qualunque ontologia di dominio, non necessariamente WordNet che,

nell’essere cosı estesa, rischia spesso di non essere particolarmente adatta a

contesti piu semplici e specifici come quelli che sono stati riportati nei nostri

esempi.

A fronte di tutte queste considerazioni si e riusciti ad implementare un proto-

tipo software, chiamato Imagination, in grado di testare sia le problematiche


connesse all’etichettamento automatico di immagini, di cui si e discusso nel

presente lavoro di tesi, sia quelle legate al mapping ontologico in ambito di-

stribuito, i cui dettagli sono riportati in [29].

Ci sono varie cose su cui sara necessario riflettere in futuro. Primo fra tutti,

sara opportuno prevedere un modo per utilizzare la gerarchia WordNet, o

qualunque altra sia in quel momento utilizzata, al fine di gestire rilassamenti

semantici: se durante il processo di annotazione automatica venissero fornite

come scelte di etichette possibili per l’immagine di un orso le parole “bear” e

“asiatic black bear”, il sistema dovrebbe essere in grado di scendere e risalire

la gerarchia WordNet, o qualunque altra ontologia, andando ad etichettare

l’immagine con il termine piu specifico fra quelli proposti e appartenenti ad

uno stesso sotto-albero della gerarchia. In definitiva, sara necessario preve-

dere la possibilita di andare ad interrogare l’ontologia di dominio sia verso

l’alto, sia verso il basso una volta fornito un termine da valutare, andando

a fare il pruning di tutto cio che si trova sopra rispetto ad un termine piu

specifico che e stato restituito. L’interrogazione verso l’alto potrebbe essere

fatta sfruttando il concetto di rilassamento semantico, mentre la parte di

interrogazione del corrispondente albero sottostante potrebbe essere fatta in

modo integrale.

Un ulteriore sviluppo futuro riguarda la necessita di gestire una sorta di

aggregazione delle regioni. Le librerie del motore Windsurf, quelle di base,

lavorano a livello di similarita di colore e tessitura. Il problema e che, a livello

di grafo MMG, sarebbe piu opportuno lavorare con la similarita fra “forme”

prevedendo un eventuale intervento utente al fine di aggregare un set di re-

gioni che insieme potrebbero costituire la forma di un oggetto in grado di

possedere un significato semantico. A basso livello si continuerebbe a lavo-

rare con la similarita di colore, ma nella costruzione del grafo si potrebbe

lavorare a livello di macro-regioni derivanti da un’aggregazione delle regioni

di base mediante o un intervento utente che semplicemente potrebbe, con il

mouse, contornare un set di regioni, o un meccanismo automatico che in ma-

niera assolutamente casuale potrebbe tentare di aggregare un set di regioni

per costituire delle macro-regioni. Questo darebbe la possibilita di lavorare

con scale diverse di granularita a livello di feedback lato utente in un sistema

144 Imagination

ad apprendimento progressivo.

Bibliografia

[1] V. W. Soo, C. Y. Lee, C. C. Li, S. L. Chen e C. C. Chen.“Automated

Semantic Annotation and Retrieval Based on Sharable Ontology and

Case-based Learning Techniques”. IEEE Multimedia 2004.

[2] G. Miller.“WordNet: A Lexical Database for English”. Communications

ACM 1995.

[3] V. Guidetti.“Intelligent Information Integration Systems: Extending Le-

xicon Ontology”. Tesi di Laurea. Universita di Modena. Anno Accademico

2001-2002.

[4] WordNet: http://wordnet.princeton.edu/

[5] J. Y. Pan, H. J. Yang, C. Faloutsos, P. Duygulu. “Automatic Multimedia

Cross-modal Correlation Discovery”. KDD 2004.

[6] J. Y. Pan, H. J. Yang, C. Faloutsos. “MMSS: Multi-modal Story-oriented

Video Summarization”. ICDM 2004.

[7] R. Fagin, R. Guha, R. Kumar, J. Novak, D. Sivakumar, A. Tomkins.

“Multi-Structural Databases”. PODS 2005.

[8] R. Fagin, P. Kolaitis, R. Kumar, J. Novak, D. Sivakumar, A. Tomkins.

“Efficient Implementation of Large-Scale Multi-Structural Databases”.

VLDB 2005.

[9] C. Yang, M. Dong. “Region Based Image Annotation Through Multiple-

Instance Learning”. ACM 2005.

146 Bibliografia

[10] L. Wang, L. Khan, B. Thuraisingham. “A Framework for Automated

Image Annotation based on Feature Selection”. CVDB 2005.

[11] E. Y. Chang. “EXTENT: Fusing Context, Content, and Semantic

Ontology for Photo Annotation”. CVDB 2005.

[12] D. Fogaras, B. Racz. “Scaling Link-Based Similarity Search”. WWW

2005.

[13] G. Jeh, J. Widom. “SimRank: A Measure of Structural-Context

Similarity”. KDD 2002.

[14] R. Jin, J. Y. Chai e L. Si. “Effective Automatic Image Annotation Via

A Coherent Language Model and Active Learning”. ACM MM 2004.

[15] K. Goh, E. Y. Chang e W. Lai. “Multimodal Concept-Dependent Active

Learning for Image Retrieval”. ACM MM 2004.

[16] L. Wang, L. Liu e L. Khan. “Automatic Image Annotation and Retrieval

Using Subspace Clustering Algorithm”. MMDB 2004.

[17] W. Jin, R. Shi e T. S. Chua. “A Semi-Naıve Bayesian Method Incorpora-

ting Clustering with Pair-wise Constraints for Auto Image Annotation”.

ACM MM 2004.

[18] F. Kang, R. Jin e J. Y. Chai. “Regularizing Translation Models for Better

Automatic Image Annotation”. CIKM 2004.

[19] L. Zhang, Y. Hu, M. Li, W. Ma e H. Zhang. “Efficient Propagation for

Face Annotation in Family Albums”. ACM MM 2004.

[20] X. J. Wang, W. Y. Ma, G. R. Xue e X. Li. “Multi-Model Similarity

Propagation and its Application for Web Image Retrieval”. ACM MM

2004.

[21] E. HyvAonen, A. Styrman e S. Saarela. “Ontology-Based Image

Retrieval”. WWW 2003.

[22] C. Breen, L. Khan, A. Kumar e L. Wang. “Ontology-based image

classification using neural networks”. SPIE 2002.

Bibliografia 147

[23] S. Jiang, T. Huang e W. Gao. “An Ontology-based Approach to Retrieve

Digitized Art Images”. IEEE/WIC/ACM WI 2004.

[24] J. Fan, Y. Gao, H. Luo e G. Xu. “Automatic Image Annotation by Using

Concept-Sensitive Salient Objects for Image Content Representation”.

SIGIR 2004.

[25] V. Mezaris, I. Kompatsiaris e M. G. Strintzis. “Region-based Image Re-

trieval using an Object Ontology and Relevance Feedback”. EURASIP

JOURNAL ON APPLIED SIGNAL PROCESSING 2004.

[26] V. W. Soo, C. Y. Lee, C. C. Li, S. L. Chen e C. C. Chen. “Automa-

ted Semantic Annotation and Retrieval Based on Sharable Ontology and

Case-based Learning Techniques”. IEEE Multimedia 2004.

[27] B. Shevade e H. Sundaram. “Incentive based image annotation”. AME-

TR-02/2004.

[28] P. Appan, B. Shevade, H. Sundaram e D. Birchfield. “Interfaces For

Networked Media Exploration And Collaborative Annotation”. ACM IUI

2005.

[29] E. Ferranti. “Interrogazioni distribuite su collezioni eterogenee di dati

multimediali”. Tesi di Laurea Specialistica. Dipartimento di Elettroni-

ca Informatica e Sistemistica. Universita degli Studi di Bologna. Anno

Accademico 2004-2005.

[30] E. Rondini. “Studio di tecniche per l’utilizzo di ontologie in database

di immagini: 1) Modelli di annotazione semantica 2) Tecniche ai propa-

gazione automatica delle annotazioni”. Attivita di tirocinio curriculare.

Dipartimento di Elettronica Informatica e Sistemistica. Universita degli

Studi di Bologna. Anno Accademico 2004-2005.

[31] I. Bartolini. “Efficient and Effective Similarity Search in Multimedia

Databases”. Ph.D. Thesis. Dipartimento di Elettronica Informatica e

Sistemistica. Universita degli Studi di Bologna. Febbraio 2002.

[32] S. Ardizzoni, I. Bartolini and M. Patella. “Windsurf: Region-Based

Image Retrieval Using Wavelets”. IWOSS 1999.

148 Bibliografia

[33] I. Bartolini, M. Patella. “Correct and Efficient Evaluation of Region-

Based Image Search”. SEBD 2000.

[34] MySql: http://www.mysql.com/

Date post:	18-Feb-2019
Category:	Documents
Upload:	vukhue
View:	217 times
Download:	0 times

Tecniche semi-automatiche per l’annotazione semantica di...

Documents