Tecniche per l’esecuzione Tecniche per l’esecuzione efficiente di efficiente di interrogazioni sul interrogazioni sul contenuto in collezioni contenuto in collezioni MPEG-7MPEG-7

Tecniche per l’esecuzione Tecniche per l’esecuzione

efficiente di efficiente di

interrogazioni sul interrogazioni sul

contenuto in collezioni contenuto in collezioni

MPEG-7 MPEG-7

Università degli Studi di Modena e Reggio Emilia Università degli Studi di Modena e Reggio Emilia

Facoltà di Ingegneria – Sede di Modena Facoltà di Ingegneria – Sede di Modena

Corso di Laurea Specialistica in Ingegneria Informatica -

Corso di Laurea Specialistica in Ingegneria Informatica - NODNOD

Relatore:

Relatore:

Prof. Paolo Tiberio Prof. Paolo Tiberio

Correlatori:

Correlatori:

Dott. Federica Mandreoli Dott. Federica Mandreoli Ing. Riccardo Martoglia Ing. Riccardo Martoglia

Anno accademico 2004-2005 Anno accademico 2004-2005

Alessandro Tonelli Alessandro Tonelli

Ambito di Ambito di

ricerca:

ricerca:

Progetto europeo DELOS (A Network of Excellence Progetto europeo DELOS (A Network of Excellence

on Digital Libraries) on Digital Libraries)

Sviluppo di tecnologie su digital libraries Sviluppo di tecnologie su digital libraries

Obiettivo Obiettivo

Ambito di indagine Ambito di indagine

della tesi:

della tesi:

Sviluppo di tecniche che permettano di interrogare Sviluppo di tecniche che permettano di interrogare

dati video utilizzando misure di similarità dati video utilizzando misure di similarità

Interrogazioni sul contenuto in collezioni MPEG-7 Interrogazioni sul contenuto in collezioni MPEG-7

Obiettivo Obiettivo

Problematiche affrontate Problematiche affrontate

 Analisi stato dell’arte Analisi stato dell’arte

 Ricerche di similarità Ricerche di similarità

 Modifiche al sistema XSiter Modifiche al sistema XSiter

MPEG-7 MPEG-7

MPEG-7 è uno standard ISO/IEC formalmente MPEG-7 è uno standard ISO/IEC formalmente chiamato “Multimedia Content Description chiamato “Multimedia Content Description Interface”, che fornisce un insieme di specifiche Interface”, che fornisce un insieme di specifiche e strumenti per la descrizione, attraverso e strumenti per la descrizione, attraverso metadati

metadati , di contenuti di tipo multimediale. , di contenuti di tipo multimediale.

Esso descrive le informazioni multimediali Esso descrive le informazioni multimediali attraverso una rappresentazione testuale attraverso una rappresentazione testuale ( ( XML XML ) che facilita l’identificazione, il filtraggio, ) che facilita l’identificazione, il filtraggio, la ricerca, il reperimento e la gestione dei dati la ricerca, il reperimento e la gestione dei dati multimediali, siano essi file audio, filmati o multimediali, siano essi file audio, filmati o

immagini.

immagini.

MMDBMS MMDBMS

Un MultiMedia DataBase Management Un MultiMedia DataBase Management System fornisce un ambiente adatto per System fornisce un ambiente adatto per

utilizzare e gestire dati multimediali.

utilizzare e gestire dati multimediali.

Deve:

•

fornire mezzi per l’indicizzazione ed il recupero efficiente delle informazioni

•

supportare modelli concettuali dei dati multimediali

•

gestire l’ottimizzazione delle query e il

processing delle stesse.

Soluzioni database XML Soluzioni database XML

native

native estensioni estensioni

Querying di dati MPEG-7 Querying di dati MPEG-7

feature- feature- based based querying querying semantic semantic

querying querying

si riferisce alle tecniche che si si riferisce alle tecniche che si

concentrano sulle

concentrano sulle

caratteristiche audiovisive di caratteristiche audiovisive di basso livello (colore, forma, basso livello (colore, forma,

ecc.) ecc.)

si riferisce all’interrogazione si riferisce all’interrogazione basata su semantiche di livello basata su semantiche di livello più alto che sono più vicine più alto che sono più vicine alle interpretazioni dell’utente alle interpretazioni dell’utente ed ai contesti d’uso.

ed ai contesti d’uso.

- -

- -

Processing di Processing di

query…

query…

Problematiche affrontate Problematiche affrontate

 Analisi stato dell’arte Analisi stato dell’arte

 Ricerche di similarità Ricerche di similarità

 Modifiche al sistema XSiter Modifiche al sistema XSiter

Ricerca di similarità Ricerca di similarità

estrarre da ciascun oggetto N caratteristiche numeriche e mappare gli oggetti in punti di uno spazio vettoriale N-dimensionale

usare una distanza opportuna su tale spazio e cercare oggetti

“vicini” usando un indice multi-dimensionale (“spaziale”) (bassa distanza = alta similarità)

 Definizione della “similarità” tra due oggetti qualsiasi

 Supporto per interrogazioni che richiedono oggetti “simili”

riguarda l’efficacia

riguarda efficacia ed

efficienza

Alberi metrici Alberi metrici

Gli alberi metrici considerano soltanto le Gli alberi metrici considerano soltanto le

distanze relative

distanze relative degli oggetti (piuttosto che degli oggetti (piuttosto che le loro posizioni assolute in uno spazio le loro posizioni assolute in uno spazio multidimensionale) per organizzare e multidimensionale) per organizzare e partizionare lo spazio di ricerca e richiedono partizionare lo spazio di ricerca e richiedono

solo che la

solo che la funzione funzione usata per misurare la usata per misurare la distanza (dissimilarità) fra gli oggetti sia una distanza (dissimilarità) fra gli oggetti sia una

metrica

metrica di modo che si possa applicare la di modo che si possa applicare la proprietà della

proprietà della disuguaglianza triangolare disuguaglianza triangolare e e possa essere usata restringere lo spazio di possa essere usata restringere lo spazio di

ricerca.

ricerca.

M-tree M-tree



Rappresenta un albero bilanciato e dinamico Rappresenta un albero bilanciato e dinamico



Memorizza tutti gli oggetti nelle foglie dell’albero Memorizza tutti gli oggetti nelle foglie dell’albero



I suoi nodi interni contengono i cosiddetti routing object I suoi nodi interni contengono i cosiddetti routing object

O_r (valore del) routing object

ptr(T(O_r)) puntatore alla radice of T(O_r)

r(O_r) covering radius of O_r

d(O_r, P(O_r)) distanza di O_r dai suoi genitori

O_j (valore del) DB object

oid(O_j) identificatore dell'oggetto

d(O_j, P(O_j)) distanza di O_j dai suoi genitori

routing object O routing object Or r

DB object O DB object Oj j



range query range query (tutti i punti aventi una distanza dalla (tutti i punti aventi una distanza dalla query minore di una soglia)

query minore di una soglia)



k k nearest neighbor query nearest neighbor query (i (i k k punti più vicini alla punti più vicini alla query)

query)

Interrogazioni di Interrogazioni di

similarità similarità

r(N)

O_N

Q



O

d(Q,O_N)

d(O,Q

d(O,Q ) ) ≤ ≤  

A D

C B

d d

(Q,N) minima (Q,N) minima

Problematiche affrontate Problematiche affrontate

 Analisi stato dell’arte Analisi stato dell’arte

 Ricerche di similarità Ricerche di similarità

 Modifiche al sistema XSiter Modifiche al sistema XSiter

Architettura di XSiter Architettura di XSiter

Offline Process

Query Engine

Doc Filter

Range Filter

Query Processor

For Each Document Scan Range

Results

Query Value Constraints

Document Qualifying Nodes Input

Documents

Input Query

Filtered Documents

Set

Doc Signature

Doc Content Based Indexes

“...”

Query Engine di XSiter

Query Engine di XSiter

ContentInde x

InvertedInde x

SimilarityIn dex

Modifiche alla struttura Modifiche alla struttura

degli indici degli indici

query query esatte

esatte query query

approssimate approssimate

ContentInde

xes

Interrogazioni Interrogazioni

Setting considerato:

Setting considerato:

Digital library multimediale contenente Digital library multimediale contenente

video di

video di Formula 1 e i loro Formula 1 e i loro metadati metadati MPEG-7

MPEG-7

“Recupera tutti i video clip annotati “Recupera tutti i video clip annotati come

come camera carscamera cars””

“Recupera tutti i video clip “Recupera tutti i video clip riguardanti

riguardanti Ferrari Ferrari camera carscamera cars”” Exact value match

Exact value matchSimilarity matchSimilarity match

Data tree Data tree video

video image1 image1

scalable scalable

color

color dominant dominant color color

image2 image2 colore

colore formaforma

scalable scalable

color color

colore colore

dominant dominant

color color Twig query

Twig query video video

Interrogazione di Interrogazione di

similarità similarità

“Recupera tutti i video clip relativi a “Recupera tutti i video clip relativi a camera cars

camera cars con auto di colore con auto di colore rosso

rosso””

Conclusioni:

Conclusioni:

Col lavoro di tesi si è avuta la possibilità di studiare concetti Col lavoro di tesi si è avuta la possibilità di studiare concetti legati ai sistemi database multimediali e alla sottomissione legati ai sistemi database multimediali e alla sottomissione ed elaborazione di interrogazioni sugli stessi con ed elaborazione di interrogazioni sugli stessi con particolare attenzione alla ricerca di similarità. Si è quindi particolare attenzione alla ricerca di similarità. Si è quindi proceduto ad estendere un software di notevoli dimensioni proceduto ad estendere un software di notevoli dimensioni (XSiter) con funzionalità di similarità attraverso una (XSiter) con funzionalità di similarità attraverso una minuziosa opera di reingegnerizzazione approfondendo tra minuziosa opera di reingegnerizzazione approfondendo tra l’altro il linguaggio di programmazione Java, la libreria XXL l’altro il linguaggio di programmazione Java, la libreria XXL e gli standard XML e MPEG-7

e gli standard XML e MPEG-7

Sviluppi futuri:

Sviluppi futuri:

• Miglioramento strategie di inserimento e Miglioramento strategie di inserimento e politiche di split

politiche di split

• Utilizzo di altre funzioni di distanza Utilizzo di altre funzioni di distanza approssimata

approssimata

• Risoluzione di interrogazioni più complesse Risoluzione di interrogazioni più complesse

• Estensioni nel sottosistema GUI di XSiter Estensioni nel sottosistema GUI di XSiter

• Ulteriori prove sperimentali Ulteriori prove sperimentali