Efficient analysis in multimedia databases [Elektronische Ressource] / von Peter Kunath

Peter Kunath

Sujets

• Informatik

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2006
• Nombre de lectures: 10
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

Efficient Analysis in
Multimedia Databases
Dissertation im Fach Informatik
an der Fakult¨at fur¨ Mathematik, Informatik und Statistik
der Ludwig-Maximilians-Universit¨at Mun¨ chen
von
Peter Kunath
Tag der Einreichung: 24.11.2006
Tag der mu¨ndlichen Pru¨fung: 19.12.2006
Berichterstatter:
Prof. Dr. Hans-Peter Kriegel, Ludwig-Maximilians-Universit¨at Mun¨ chen
Prof. Dr. Bernhard Seeger, Philipps-Universit¨at MarburgiiAcknowledgement
While I can not name all the people who have supported and encouraged me
during the past years, I want to thank those that notably helped me with
the development of this thesis.
First of all, like to express my warmest thanks to my supervisor, Prof.
Dr. Hans-Peter Kriegel who initiated and supported this work. I learned a
lot from his long standing experience and organizational background. Then
I want to thank Prof. Dr. Bernhard Seeger for the interest in my work. He
was kindly willing to act as second referee for this work.
Without the inspiring, productive and supportive working environment
of the database research team this work would never have been possible.
Therefore I express my gratitude to my colleagues, in particular to Matthias
Renz, Dr. Peer Kr¨oger, Alexey Pryakhin, Dr. Matthias Schubert, Stefan
Brecheisen, Johannes Aßfalg, and Dr. Martin Pfeifle. I also want to thank
Prof. Dr. ChristianB¨ohm,ChristianMahrt,KarstenBorgwardt,andArthur
Zimek for many inspiring discussions. Thank you for the constructive and
productive team work. Special thanks to Elke ”Elki” Achtert, the power
woman in our research team.
Furthermore,IwanttothankOtmarHilligesforfruitfulmultidisciplinary
discussions about similarity of multimedia objects and musical genres.
I also appreciate the substantial help of the students whose study thesis
ordiplomathesisIsupervised. ThisincludesRolphKreis, MarkusDolic, Ilja
Vishnevski, Tim Schmidt, Georg Straub, OlegGalimovand Michael Gruber.
They helped me in many ways including implementation, data processing,
iiiiv
and testing.
I am very grateful for the background support of Susanne Grienberger,
who managed much of the administrative work. She also gave me invaluable
hints for improving on my English. Furthermore, I want to express spe-
cial thanks to Franz Krojer, who helped to master all technical issues. He
promptly provided tools that helped to accelerate my work.
Finally I like to thank my family and friends, who constantly supported
me during the development of this thesis. My parents who always supported
my career and encouraged me to find my way. Frank Riffel, with whom
I developed DeliTracker which sparked my interest in Multimedia content.
Florian Vorberger, who is the co-programmer of DeliPlayer and who also
implemented the MUSCLE approach. Thanks to Dr. Karen Richter for
proof-reading the intro & outro part of my thesis.Abstract
The rapid progress of digital technology has led to a situation where com-
puters have become ubiquitous tools. Now we can find them in almost every
environment, be it industrial or even private. With ever increasing perfor-
mance computers assumed more and more vital tasks in engineering, climate
and environmental research, medicine and the content industry. Previously,
these tasks could only be accomplished by spending enormous amounts of
time and money. By using digital sensor devices, like earth observation
satellites, genome sequencers or video cameras, the amount and complexity
of data with a spatial or temporal relation has gown enormously. This has
led to new challenges for the data analysis and requires the use of modern
multimedia databases.
Thisthesisaimsatdevelopingefficienttechniquesfortheanalysisofcom-
plex multimedia objects such as CAD data, time series and videos. It is
assumed that the data is modeled by commonly used representations. For
example CAD data is represented as a set of voxels, audio and video data is
represented as multi-represented, multi-dimensional time series.
The main part of this thesis focuses on finding efficient methods for col-
lision queries of complex spatial objects. One way to speed up those queries
is to employ a cost-based decompositioning, which uses interval groups to
approximate a spatial object. For example, this technique can be used for
the Digital Mock-Up (DMU) process, which helps engineers to ensure short
product cycles. This thesis defines and discusses a new similarity measure
for time series called threshold-similarity. Two time series are considered
similar if they expose a similar behavior regarding the transgression of a
vvi
given threshold value. Another part of the thesis is concerned with the ef-
ficient calculation of reverse k-nearest neighbor (RkNN) queries in general
metricspacesusingconservativeandprogressiveapproximations. Theaimof
such RkNN queries is to determine the impact of single objects on the whole
database. At the end, the thesis deals with video retrieval and hierarchical
genre classification of music using multiple representations. The practical
relevance of the discussed genre classification approach is highlighted with a
prototype tool that helps the user to organize large music collections.
Both the efficiency and the effectiveness of the presented techniques are
thoroughly analyzed. The benefits over traditional approaches are shown by
evaluating the new methods on real-world test datasets.Zusammenfassung
Aufgrund der rasanten Entwicklung von digitalen Technologien ist der Com-
puter, sowohl im privaten als auch im industriellen Umfeld, als zentrales
Hilfsmittel heute allgegenwar¨ tig. Mit zunehmender Leistungsfahig¨ keit ha-
ben Computer wichtige Aufgaben im Maschinenbau, in der Umwelt- und
Klimaforschung, in der Medizin oder in der Medienbranche ubernommen,¨
die vorher nur unter Aufbietung enormer zeitlicher und finanzieller Ressour-
cen bewaltigt werden konnten. Durch den Einsatz von digitalen Erfassungs-¨
geratenwiez.B.Erdbeobachtungssatelliten,GensequenzierernoderVideoka-¨
meraswachsendieDatenmitr¨aumlichemundzeitlichemBezuginMengeund
Komplexitatdrastischan,waszuneuenHerausforderungenbeiderenAnaly-¨
sefuhrtunddenEinsatzmodernerMultimedia-Datenbanksystemenotwendig¨
macht.
Das Ziel dieser Doktorarbeit ist es, effiziente Verfahren fur¨ die Analyse
von komplexen Multimedia-Objekten, wie z.B. CAD-Daten, Zeitreihen und
Audio- bzw. Videodaten, zu entwickeln. Ausgegangen wird dabei von der
Modellierung der Daten in gel¨aufigen Darstellungsformen. So werden z.B.
CAD-Daten als Mengen von Voxeln, Audio- bzw. Videodaten als multire-
prasentierte, mehrdimensionale Zeitreihen aufgefaßt.¨
ImEinzelnenbeschaftig¨ tsichdieArbeitmitdereffizientenBeantwortung
von Kollisionsanfragen auf komplexen raumlic¨ hen Objekten. Die komplexen
Objekte werden dabei mittels einer kostenbasierten Zerlegung in einen ein-
fachen Grundtyp zerlegt, mit dessen Hilfe die Anfragebearbeitung erheblich
beschleunigt werden kann. Dies ist z.B. beim digitalen Zusammenbau (Di-
gital Mock-up) von Interesse, wodurch Ingenieure die Anforderungen immer
viiviii
kurzer¨ werdender Produktzyklen meistern konnen.¨ Des weiteren wird die
¨Threshold-Similarity als neues Ahnlichkeitsmaß auf Zeitreihen eingefuhrt.¨
Dabei werden zwei Zeitreihen als ahnlich angesehen, wenn sie ein ahnliches¨ ¨
¨Verhalten bezuglic¨ h der Uberschreitungen eines vorgegebenen Grenzwertes
aufweisen.EinweitererAbschnittbeschaftigtsichmitdereffizientenBerech-¨
nung von Reversen-k-Nachste-Nachbar-Anfragen (RkNN-Anfragen) in me-¨
trischen R¨aumen mittels konservativer und progressiver Approximationen.
Ziel von RkNN-Anfragen ist es, den Einfluß des Anfrageobjekts auf die ge-
samte Datenbank zu bestimmen. Schließlich befaßt sich die Arbeit mit der
Video-Suche sowiederhierarchischenGenre-Klassifikation vonMusikstuc¨ ken
basierend auf multiplen Reprasentationen. Die Praxisrelevanz des Genre-¨
Klassifikationsverfahrens wird in einer realen Anwendung demonstriert.
Die Effizienz und Effektivitat der vorgestellten Techniken wird ausgie-¨
big untersucht und die Vorteile gegenub¨ er herk¨ommlichen Verfahren mittels
Real-Datenbanken experimentell nachgewiesen.Contents
Acknowledgement iv
Abstract vi
Zusammenfassung viii
I Preliminaries 1
1 Introduction 3
1.1 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Purpose of the Thesis 13
2.1 Analysis of Spatial Data . . . . . . . . . . . . . . . . . . . . . 13
2.2 Modeling Spatial Data . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Multi-Step Query Processing . . . . . . . . . . . . . . . 15
2.2.2 Digital Mock-up . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Modeling Spatial Objects . . . . . . . . . . . . . . . . 18
2.2.4 Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . 19
2.2.5 Voxel-Sets and Voxel-Sequences . . . . . . . . . . . . . 20
2.2.6 Decomposition Algorithm . . . . . . . . . . . . . . . . 23
2.2.7 Compression Techniques . . . . . . . . . . . . . . . . . 23
2.2.8 Relational Spatial Indexing . . . . . . . . . . . . . . . 26
2.2.9 Test Datasets . . . . . . . . . . . . . . . . . . . . . . . 28
ixx CONTENTS
2.3 Analysis of Temporal Dat