Datenbanksysteme für neue Anwendungen
Das Seminar 1912 "Multimedia-Datenbanken"

Multimedia-Datenbanken

Vorwort

Datenstrukturen und Algorithmen für Multimedia-Daten basieren teilweise auf speziellen mathematischen Formalismen. So enthalten einige der hier genannten Papiere relativ komplizierte Formeln. Sinn dieses Seminars soll es sein, ein grundlegendes Verständnis für die Speicherung und das Wiederauffinden von Multimedia-Daten zu entwickeln. Seien Sie also nicht beunruhigt, wenn Sie die eine oder andere Formel nicht ganz verstehen. In den von Ihnen anzufertigenden Ausarbeitungen und Vorträgen sollen Sie die Grundideen hinter den verschiedenen Verfahren beschreiben und keine genaue mathematische Analyse betreiben.

Compression Techniques

Multimedia-Daten haben im Gegensatz zu Standard-Daten ein sehr großes Datenvolumen. Um die Anzahl der notwendigen Festplattenzugriffe sowie das Übertragungsvolumen von der Datenbank zur Anwendung zu verringern, werden die Daten komprimiert.
In [Wal91] wird ein Verfahren zur Datenreduktion von Bilddaten (JPEG) beschrieben. Dabei handelt sich sich um ein verlustbehaftetes Kompressionverfahren, d.h. die Kompression führt zu einer Veränderung der Originaldaten. Eine Möglichkeit zur Kompression von Videodaten ist Thema von [Gal91].

Indexing of Complex Data

Aufgrund der Mehrdimensionalität von Multimedia-Daten können die Indexstrukturen von klassischen Datenbanksystemen (z.B. B-Bäume) nicht für Multimedia-Daten verwendet werden. Bei diesem Thema sollen zwei Ansätze diskutiert werden, mit denen es möglich ist, mehrdimensionale Daten zu indizieren. [Uhl91] beschreibt die grundsätzliche Idee von Indexstrukturen in metrischen Räumen. Eine Umsetzung dieser Idee findet sich in [CPZ97].
Im Gegensatz dazu behandeln [LJF94] und [BKK96] Indexstrukturen für hoch-dimensionale Vektorräume.
Ziel dieses Themas soll es nicht sein, alle Papiere im Detail darzustellen, sondern vielmehr einen Überblick über die Konzepte, ihre Stärken und Schwächen zu geben.

Text Retrieval 1

Um Anfragen auf kompletten Dokumenten zu ermöglichen, ist es erforderlich, effizient prüfen zu können, ob ein gespeicherter Text ein gegebenes Wort enthält. Ein solcher Algorithmus wird in [BM77] vorgestellt. Ein weiteres Problem ist die große Datenmenge, die beim Speichern vollständiger Dokumente zu verarbeiten ist. Wie auch andere Multimedia-Daten werden Texte komprimiert in der Datenbank gespeichert. Im Gegensatz zu Bildern oder Videos, dürfen hierbei verwendete Verfahren die ursprünglichen Daten nicht verändern. Ein entsprechender Algorithmus ist Inhalt von [ZL77]. In [NT00] werden die beiden Konzepte zusammengeführt und gezeigt, wie man erkennen kann, ob ein komprimierter Text ein Wort enthält - ohne diesen vorher vollständig dekomprimiert zu haben.

Text Retrieval 2

Dieses Thema behandelt Indexstrukturen für Textdokumente. In [DDL+90] wird versucht, in Dokumenten eine semantische Struktur zu erkennen. Dokumente und Queries werden auf Vektoren abgebildet, um eine Anfrage möglichst schnell beantworten zu können.
Eine Datenstruktur, mit der eine Suche mit Hilfe von Schlüsselwörtern beschleunigt werden kann, wird in [MZ96] beschrieben.

Content Based Image Retrieval 1

In früheren Bilddatenbanken wurden Bilder zusammen mit Schlüsselwörtern abgelegt, die vom Benutzer der Datenbank von Hand eingetragen werden mußten. Durch die Zunahme der Verwendung digitaler Bilder, mußten Möglichkeiten entwickelt werden, Bilder automatisch zu erkennen. Der Benutzer gibt dazu ein Referenzbild als Anfrage an, und das Datenbanksystem ermittelt alle in der Datenbank gespeicherten Bilder, die zum gegebenen Bild eine genügende Ähnlichkeit aufweisen.
Eine Möglichkeit, solche Ähnlichkeiten von Bildern festzustellen, ist zu prüfen, ob die beiden zu vergleichenden Bilder eine ähnliche Farbverteilung aufweisen. Indexstrukturen, die mit Hilfe von Histogrammen gebildet werden, sind Gegenstand von [SO95] Eine andere Möglichkeit, welche in [GR95] genutzt wird, ist die Suche nach räumlichen Ähnlichkeiten zwischen zwei Bildern.

Content Based Image Retrieval 2

In [Jag91] wird eine Organisation einer Datenbank vorgestellt, die das Wiederauffinden von Bildern ermöglicht, die ähnliche Formen zu einem gegebenen Bild haben. [FBF+94] behandelt QBIC, ein von IBM entwickeltes System zum Suchen nach Bildern (und Videos) in Datenbanken.

Music Retrieval 1

Wie bei Bildern besteht bei Audio-Daten das Problem automatisch eine Ähnlichkeitserkennung durchführen zu lassen. Dabei sollten Störungen (Rauschen etc.) weitestgehend korrekt behandelt werden. In [LS01] wird eine Funktion beschrieben, mittels derer Ähnlichkeiten zwischen zwei Musikstücken festgestellt werden können. In [WBH+99] wird ein System vorgestellt, in dem Musikdateien relativ stark reduziert werden, um Ähnlichkeiten zwischen diesen festzustellen. Auch [RH03] beschreibt ein System zum Auffinden von Audio-Dateien innerhalb einer Datenbank.

Music Retrieval 2

Ein System von Auffinden von Liedern, die durch den Benutzer ,,angesummt`` werden, ist in [NKYK99] und [KNS+00] beschrieben. Die Berechnung eines Hash-Wertes für eine gegebene Audio-Datei ist Gegenstand von [HKO01]. Mit Hilfe dieses Wertes kann ein entsprechendes Lied innerhalb der Datenbank gefunden werden.

Video Retrieval

VideoQ [CCM+97] ist ein System, um Videodateien finden zu können. Dazu werden aus den gegebenen Video-Daten Eigenschaften extrahiert, die zur Suche verwendet werden. In [AC97] werden aus Videos "repräsentative Frames" extrahiert, aus denen sogenannte r-Frame-Descriptoren berechnet werden. Diese werden zur weiteren Suche verwendet.

Literatur

AC97
Edoardo Ardizzone and Marco La Cascia.
Automatic video database indexing and retrieval.
Multimedia Tools Appl., 4(1):29-56, 1997.
BKK96
Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel.
The x-tree: An index structure for high-dimensional data.
In T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, and Nandlal L. Sarda, editors, VLDB, pages 28-39. Morgan Kaufmann, 1996.
BM77
Robert S. Boyer and J. Strother Moore.
A fast string searching algorithm.
Commun. ACM, 20(10):762-772, 1977.
CCM+97
Shih-Fu Chang, William Chen, Horace J. Meng, Hari Sundaram, and Di Zhong.
Videoq: An automated content based video search system using visual cues.
In ACM Multimedia, pages 313-324, 1997.
CPZ97
Paolo Ciaccia, Marco Patella, and Pavel Zezula.
M-tree: An efficient access method for similarity search in metric spaces.
In Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, and Manfred A. Jeusfeld, editors, VLDB, pages 426-435. Morgan Kaufmann, 1997.
DDL+90
Scott C. Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas, and Richard A. Harshman.
Indexing by latent semantic analysis.
JASIS, 41(6):391-407, 1990.
FBF+94
Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, and William Equitz.
Efficient and effective querying by image content.
J. Intell. Inf. Syst., 3(3/4):231-262, 1994.
Gal91
Didier Le Gall.
Mpeg: A video compression standard for multimedia applications.
Commun. ACM, 34(4):46-58, 1991.
GR95
Venkat N. Gudivada and Vijay V. Raghavan.
Design and evaluation of algorithms for image retrieval by spatial similarity.
ACM Trans. Inf. Syst., 13(2):115-144, 1995.
HKO01
J. Haitsma, T. Kalker, and J. Oostveen.
Robust audio hashing for content identification.
In Proceedings of the Content Based Multimedia Indexing,pages 19-21, 2001.
Jag91
H. V. Jagadish.
A retrieval technique for similar shapes.
In James Clifford and Roger King, editors, SIGMOD Conference, pages 208-217. ACM Press, 1991.
KNS+00
Naoko Kosugi, Yuichi Nishihara, Tetsuo Sakata, Masashi Yamamuro, and Kazuhiko Kushima.
A practical query-by-humming system for a large music database.
In ACM Multimedia, pages 333-342, 2000.
LJF94
King-Ip Lin, H. V. Jagadish, and Christos Faloutsos.
The tv-tree: An index structure for high-dimensional data.
VLDB J., 3(4):517-542, 1994.
LS01
B. Logan and A. Salomon.
A music similarity function based on signal analysis,
In Proceedings of the IEEE International Conference on Multimedia and Expo, pages 745-748, 2001.
MZ96
Alistair Moffat and Justin Zobel.
Self-indexing inverted files for fast text retrieval.
ACM Transactions on Information Systems, 14(4):349-379, 1996.
NKYK99
S. Kon'ya N. Kosugi, Y. Nishimura, M. Yamamuro, and K. Kushima.
Music retrieval by humming.
In PACRIM'99, pages 404-407, August 1999.
NT00
G. Navarro and J. Tarhio.
Boyer-Moore string matching over ziv-lempel compressed text.
In R. Giancarlo and D. Sankoff, editors, Proceedings of the11th Annual Symposium on Combinatorial Pattern Matching, number 1848, pages 166-180, Montréal, Canada, 2000. Springer-Verlag, Berlin.
RH03
Seung-Min Rho and Een-Jun Hwang.
Fmf(fast melody finder): A web-based music retrieval system.
In Uffe Kock Wiil, editor, CMMR, volume 2771 of Lecture Notes in Computer Science, pages 179-192. Springer, 2003.
SO95
Markus A. Stricker and Markus Orengo.
Similarity of color images.
In Storage and Retrieval for Image and Video Databases (SPIE), pages 381-392, 1995.
Uhl91
Jeffrey K. Uhlmann.
Satisfying general proximity/similarity queries with metric trees.
Inf. Process. Lett., 40(4):175-179, 1991.
Wal91
Gregory K. Wallace.
The jpeg still picture compression standard.
Commun. ACM, 34(4):30-44, 1991.
WBH+99
M. Welsh, N. Borisov, J. Hill, R. von Behren, and A. Woo.
Querying large collections of music for similarity,
Technical Report 1096,
U.C. Berkeley Computer Science Division, 1999.
ZL77
Jacob Ziv and Abraham Lempel.
A universal algorithm for sequential data compression.
IEEE Transactions on Information Theory, 23(3):337-343, 1977.



[ Seminar 1912 | Lehrgebiet | Fachbereich Informatik | FernUniversität in Hagen ]


last update: 2006-03-01, Thomas Behr