Università degli Studi di Modena e Reggio Emilia
Facoltà di Ingegneria – Sede di Modena
Corso di Laurea Specialistica in Ingegneria Informatica - NOD
Tecniche per l’esecuzione
efficiente di interrogazioni sul
contenuto in collezioni MPEG-7
Alessandro Tonelli
Relatore:
Correlatori:
Prof. Paolo Tiberio
Dott. Federica Mandreoli
Ing. Riccardo Martoglia
Anno accademico 2004-2005
Ambito di ricerca:
Progetto europeo DELOS (A Network of
Excellence on Digital Libraries)
Obiettivo
Sviluppo di tecnologie su digital libraries
Ambito di indagine della tesi:
Interrogazioni sul contenuto in collezioni MPEG-7
Obiettivo
Sviluppo di tecniche che permettano di interrogare
dati video utilizzando misure di similarità
Problematiche affrontate

Analisi stato dell’arte

Ricerche di similarità

Modifiche al sistema XSiter
MPEG-7
MPEG-7 è uno standard ISO/IEC formalmente
chiamato “Multimedia Content Description Interface”,
che fornisce un insieme di specifiche e strumenti per la
descrizione, attraverso metadati, di contenuti di tipo
multimediale.
Esso descrive le informazioni multimediali attraverso
una rappresentazione testuale (XML) che facilita
l’identificazione, il filtraggio, la ricerca, il reperimento e
la gestione dei dati multimediali, siano essi file audio,
filmati o immagini.
MMDBMS
Un MultiMedia DataBase Management System
fornisce un ambiente adatto per 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
native
Native
database
solutions
Commercial
Open
source
Research
eXcelon XIS
GoXML DB
Infonyte-DB
Tamino
TEXTML
X-Hive/DB
estensioni
Database extensions
Unstructured storage
Structured storage
IBM DB2 XML Extender
Oracle XML DB/
Structured Mapping
Microsoft SQLXML
Oracle XML DB
dbXML
eXist
Xindice
ozone/XML
Lore
Natix
Monet XML
PDOM
TIMBER
Mapping
Shimura et al.
XML Cartridge
Querying di dati MPEG-7
-
-
feature-based
querying
si riferisce alle tecniche che si
concentrano sulle caratteristiche
audiovisive di basso livello
(colore, forma, ecc.)
semantic
querying
si riferisce all’interrogazione
basata su semantiche di livello
più alto che sono più vicine alle
interpretazioni dell’utente ed ai
contesti d’uso.
Processing di query…
Problematiche affrontate

Analisi stato dell’arte

Ricerche di similarità

Modifiche al sistema XSiter
Ricerca di similarità

Definizione della “similarità” tra due oggetti qualsiasi
riguarda l’efficacia
estrarre da ciascun oggetto N caratteristiche numeriche e mappare gli oggetti in
punti di uno spazio vettoriale N-dimensionale

Supporto per interrogazioni che richiedono oggetti “simili”
riguarda efficacia
ed efficienza
usare una distanza opportuna su tale spazio e cercare oggetti “vicini” usando
un indice multi-dimensionale (“spaziale”) (bassa distanza = alta similarità)
Alberi metrici
Gli alberi metrici considerano soltanto le distanze
relative degli oggetti (piuttosto che le loro posizioni
assolute in uno spazio multidimensionale) per
organizzare e partizionare lo spazio di ricerca e
richiedono solo che la funzione usata per misurare
la distanza (dissimilarità) fra gli oggetti sia una
metrica di modo che si possa applicare la proprietà
della disuguaglianza triangolare e possa essere usata
restringere lo spazio di ricerca.
M-tree



Rappresenta un albero bilanciato e dinamico
Memorizza tutti gli oggetti nelle foglie dell’albero
I suoi nodi interni contengono i cosiddetti routing object
routing object Or
Or
(valore del) routing object
ptr(T(Or))
puntatore alla radice of T(Or)
Oj
(valore del) DB object
r(Or)
covering radius of Or
oid(Oj)
identificatore dell'oggetto
d(Or, P(Or))
distanza di Or dai suoi
genitori
d(Oj, P(Oj))
distanza di Oj dai suoi
genitori
DB object Oj
Interrogazioni di similarità
range query (tutti i punti aventi una distanza dalla query
minore di una soglia)
 k nearest neighbor query (i k punti più vicini alla query)

D
BO
Q
ON
A
d(Q,ON)

r(N)
C
dmin(Q,N)
minima
d(O,Q)
≤
Problematiche affrontate

Analisi stato dell’arte

Ricerche di similarità

Modifiche al sistema XSiter
Architettura di XSiter
Query
Language
Query Specifier
Result Visualizer
GUI
Query Importer
Internal Query
Representation
Query Engine
Doc Importer
Internal Doc
Representation
Core System
Doc.xml
Datastore
Offline Process
Query Engine di XSiter
Input
Documents
Doc Filter
Filtered
Documents
Set
Input
Query
Range Filter
Scan Range
Results
Query Processor
Doc Signature
Query Value
Constraints
Document
Qualifying Nodes
“...”
Doc Content Based
Indexes
For Each Document
Query Engine
Modifiche alla struttura degli indici
ContentIndexes
ContentIndex
InvertedIndex
query esatte
SimilarityIndex
query approssimate
Interrogazioni
Setting considerato:
Digital library multimediale contenente video di
Formula 1 e i loro metadati MPEG-7
Exact
Similarity
valuematch
match
“Recupera
“Recupera
tutti itutti
video
i video
clip annotati
clip
riguardanti
comeFerrari
camera
camera
cars” cars”
Interrogazione di similarità
“Recupera tutti i video clip relativi a
camera cars con auto di colore
rosso”
video
image1
video
image2
colore
scalable
color
forma
dominant
color
Data tree
colore
scalable
color
dominant
color
Twig query
Conclusioni:
Col lavoro di tesi si è avuta la possibilità di studiare concetti legati ai sistemi
database multimediali e alla sottomissione ed elaborazione di interrogazioni
sugli stessi con particolare attenzione alla ricerca di similarità. Si è quindi
proceduto ad estendere un software di notevoli dimensioni (XSiter) con
funzionalità di similarità attraverso una minuziosa opera di reingegnerizzazione
approfondendo tra l’altro il linguaggio di programmazione Java, la libreria XXL
e gli standard XML e MPEG-7
Sviluppi futuri:
•Miglioramento strategie di inserimento e politiche di split
•Utilizzo di altre funzioni di distanza approssimata
•Risoluzione di interrogazioni più complesse
•Estensioni nel sottosistema GUI di XSiter
•Ulteriori prove sperimentali