Ähnlichkeitssuche in der "Lost Art Internet Database"
©2003
Bachelorarbeit
49 Seiten
Zusammenfassung
Inhaltsangabe:Einleitung:
Das Ziel dieses Praktikums ist es, unter Berücksichtigung der Phasen der Softwareentwicklung, eine Webanwendung zur effizienten Recherche in der Lost Art Internet Datenbank zu entwerfen und einzelne Module zu implementieren. Die Webanwendung soll den vollständigen Rechercheprozess, angefangen von der Vorverarbeitung der Daten bis hin zur Repräsentation der Ergebnisse unterstützen. Auch für bereits existierende Abbildungen muss die Möglichkeit bestehen diverse Feature (z.B. Farbe oder Textur) zu extrahierten und diese in einer Datenbank abzulegen. Der Nutzer soll die Möglichkeit bekommen die Ähnlichkeitssuche, die Suche nach Objekten und die textbasierte Suche einzeln oder in Kombination einzusetzen.
Das heißt das System muss in der Lage sein auch komplexe Nutzeranfragen zu bearbeiten, die aus mehreren Anfragetermen zusammengesetzt sind. Aufgrund dieser Anforderungen ist ein wesentlicher Bestandteil der Arbeit die Vorverarbeitung der Daten und die dazu gehörende Entwicklung von Programmmodulen zur Bildsegmentierung, Verschlagwortung, Featureextraktion und Bestimmung der Lagebeziehungen.
Da vollautomatische Objekterkennungssysteme, die z.B. mit dem Split and Merge Algorithmus arbeiten, nicht immer die gewünschten Ergebnisse liefern und das manuelle Nachzeichnen von Objektkanten ungenau und sehr zeitintensiv ist, soll ein semiautomatisches Segmentierungstool entwickelt werden, das den Benutzer bei dieser Aufgabe unterstützt. Ein weiterer wichtiger Aspekt ist die Entwicklung eines Recherchesystems mit den entsprechenden Schnittstellen zur Integration der Programmkomponenten. Am Ende des Rechercheprozesses sollen dem Nutzer die Abbildungen, die eine Ähnlichkeit von beispielsweise 90 Prozent aufweisen, in entsprechender Reihenfolge präsentiert werden.
Um in das Lost Art Projekt integriert werden zukönnen muss das zu entwickelnde System als Webanwendung z.B. mit Hilfe von Servlets, JSP, Applets, PHP oder CGI implementieren werden. Der Systemaufbau soll dabei mit Hilfe von Modulen erfolgen und somit flexibel erweiterbar sein. Weiterhin muss das existierende Datenbankschema an die neuen Anforderungen angepasst oder weiterentwickelt werden. Bei der Umsetzung von Datenbankoperationen ist zu berücksichtigen, dass die Datenbanksoftware Oracle 8i zum Einsatz kommt.
Im zweiten Kapitel dieser Studienarbeit werden bereits existierende Bild-Retrievalsysteme vorgestellt und ihre Suchkriterien verglichen, wobei besonders die Wahl der […]
Das Ziel dieses Praktikums ist es, unter Berücksichtigung der Phasen der Softwareentwicklung, eine Webanwendung zur effizienten Recherche in der Lost Art Internet Datenbank zu entwerfen und einzelne Module zu implementieren. Die Webanwendung soll den vollständigen Rechercheprozess, angefangen von der Vorverarbeitung der Daten bis hin zur Repräsentation der Ergebnisse unterstützen. Auch für bereits existierende Abbildungen muss die Möglichkeit bestehen diverse Feature (z.B. Farbe oder Textur) zu extrahierten und diese in einer Datenbank abzulegen. Der Nutzer soll die Möglichkeit bekommen die Ähnlichkeitssuche, die Suche nach Objekten und die textbasierte Suche einzeln oder in Kombination einzusetzen.
Das heißt das System muss in der Lage sein auch komplexe Nutzeranfragen zu bearbeiten, die aus mehreren Anfragetermen zusammengesetzt sind. Aufgrund dieser Anforderungen ist ein wesentlicher Bestandteil der Arbeit die Vorverarbeitung der Daten und die dazu gehörende Entwicklung von Programmmodulen zur Bildsegmentierung, Verschlagwortung, Featureextraktion und Bestimmung der Lagebeziehungen.
Da vollautomatische Objekterkennungssysteme, die z.B. mit dem Split and Merge Algorithmus arbeiten, nicht immer die gewünschten Ergebnisse liefern und das manuelle Nachzeichnen von Objektkanten ungenau und sehr zeitintensiv ist, soll ein semiautomatisches Segmentierungstool entwickelt werden, das den Benutzer bei dieser Aufgabe unterstützt. Ein weiterer wichtiger Aspekt ist die Entwicklung eines Recherchesystems mit den entsprechenden Schnittstellen zur Integration der Programmkomponenten. Am Ende des Rechercheprozesses sollen dem Nutzer die Abbildungen, die eine Ähnlichkeit von beispielsweise 90 Prozent aufweisen, in entsprechender Reihenfolge präsentiert werden.
Um in das Lost Art Projekt integriert werden zukönnen muss das zu entwickelnde System als Webanwendung z.B. mit Hilfe von Servlets, JSP, Applets, PHP oder CGI implementieren werden. Der Systemaufbau soll dabei mit Hilfe von Modulen erfolgen und somit flexibel erweiterbar sein. Weiterhin muss das existierende Datenbankschema an die neuen Anforderungen angepasst oder weiterentwickelt werden. Bei der Umsetzung von Datenbankoperationen ist zu berücksichtigen, dass die Datenbanksoftware Oracle 8i zum Einsatz kommt.
Im zweiten Kapitel dieser Studienarbeit werden bereits existierende Bild-Retrievalsysteme vorgestellt und ihre Suchkriterien verglichen, wobei besonders die Wahl der […]
Leseprobe
Inhaltsverzeichnis
ID 7786
Urban, Christian: Ähnlichkeitssuche in der "Lost Art Internet Database"
Hamburg: Diplomica GmbH, 2004
Zugl.: Otto-von-Guericke-Universität Magdeburg, Universität, BA-Thesis / Bachelor, 2003
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2004
Printed in Germany
I
Inhaltsverzeichnis
Abkürzungsverzeichnis III
Abbildungsverzeichnis IV
Tabellenverzeichnis V
1 Einleitung und Motivation
1
1.1 Zielstellung der Arbeit
2
1.2 Gliederung der Arbeit
3
2 Verwandte
Arbeiten
4
2.1 CHARIOT - ETH Zürich
4
2.2 MARS - University of California, Irvine
5
2.3 Blobworld - University of California, Berkley
5
2.4 QBIC - IBM
6
2.5 Viper - University of Geneva
6
2.6 Image Rover - Boston University
7
2.7 Oracle Visual Information Retrieval Cartridge
8
2.8 Zusammenfassung
8
3 Grundlagen
10
3.1 Segmentierung von Abbildungen
10
3.2 Ähnlichkeitssuche
11
4 Entwurf eines Retrievalsystems für Lostart
14
4.1 Datenbankentwurf
15
4.2 Entwurf des Vorverarbeitungssystems
17
4.3 Entwurf des Retrievalsystems
19
4.3.1 Textbasierte Suche
19
4.3.2 Ähnlichkeitssuche
19
4.3.3 Iconisierte Suche
20
II
5 Implementierung
21
5.1 Implementierung der Datenbank
21
5.2 Auswahl der Programmiersprachen
22
5.3 Implementierung des Vorverarbeitungssystems
24
5.4 Implementierung des Retrievalsystems
26
6 Zusammenfassung und Ausblick
30
Literaturverzeichnis 32
Anhang
A
ER-Modell
36
B Beschreibung der Entities und Attribute
37
C
Aktivitätsdiagramm
Modul
Vorverarbeitung
38
D Aktivitätsdiagramm Modul Retrieval und Ergebnisdarstellung
39
E
Klassendiagramm
Vorverarbeitungssystem
40
F Komponentendiagramm Retrieval und Ergebnisdarstellung
41
III
Abkürzungsverzeichnis
CBIR
Content-Based Image Retrieval
CGI
Common Gateway Interface
DB Datenbank
DFT
Diskrete Fourier Transformation
ER-Modell Entity-Relationship
Modell
HDD
Hard Disk Drive
HTML
Hypertext Markup Language
ID Identifier
JDK
Java Development Kit
JSP
Java Server Pages
MRML
Multimedia Retrieval Markup Language
NN-Suche Nächste-Nachbar-Suche
OOP Objektorientierte
Programmierung
PHP(3/4)
PHP Hypertext Preprocessor (Version 3 oder 4)
SQL
Structured Query Language
VA-File
Vector Approximation File
IV
Abbildungsverzeichnis
Abbildung 1: Beispielabbildungen mit ähnlichen Features
1
Abbildung 2
:
Untergliederung eines Bildes beim CHARIOT
System
[ETHZ01]
4
Abbildung 3
:
Bild und Blobworldpräsentation des Bildes
6
Abbildung 4: Client- Server Kommunikation mit MRML [UoGe03]
7
Abbildung 5: Anfragebild a) und Ergebnisse b) & c)
im CHARIOT-System [ETHZ01]
8
Abbildung 6: unpräzise Segmentierung durch regionenbasierte
Verfahren
[UoCB00]
9
Abbildung 7: Ähnlichkeits- Retrieval
[Schm01]
12
Abbildung 8: Grobarchitektur des Retrievalsystems für Lostart
14
Abbildung 9: Ausschnitt aus dem ER- Schema
15
Abbildung 10
:
Aktivitätsdiagramm des Lagebeziehungstools
20
Abbildung 11: Benutzeroberfläche des Java Applets
24
Abbildung 12: Kommunikation zwischen Applet und Servlet
25
Abbildung 13: Segmentierung eines Objektes
25
Abbildung 14: Menü zur Verschlagwortung eines Objektes
26
Abbildung 15: Suchmaske des Retrievalsystems
27
Abbildung 16: Oberfläche des Lagebeziehungstools
27
Abbildung 17: Abfrage für die Featurewichtungen bei der
Ähnlichkeitssuche
29
Abbildung 18: Ergebnispräsentation der Ähnlichkeitssuche
29
V
Tabellenverzeichnis
Tabelle 1: Retrievaleigenschaften verschiedener CBIR-Systeme
9
Tabelle 2: Datentypen der Attribute
16
Tabelle 3: Lagebeziehungen der Segmente
18
Tabelle 4: Gegenüberstellung verschiedener Implementierungssprachen
23
1 Einleitung
1
1 Einleitung und Motivation
Mit der immer weiteren Verbreitung kommerzieller und nicht kommerzieller
Bilddatenbanken gewinnt das Problem der effizienten Recherche in derartigen
Datenbeständen mehr und mehr an Bedeutung. Ein Beispiel dafür ist die
Internetdatenbank Lost Art Internet Database, in der Informationen und tausende von
Abbildungen verlorener Kulturgüter gespeichert sind. Das Lostart Portal bietet die
Möglichkeit, diese Kulturgüter, die infolge des zweiten Weltkrieges bzw. des
Nationalsozialismus verbracht, verlagert oder insbesondere jüdischen Eigentümern
verfolgungsbedingt entzogen wurden oder für die eine solche Verlustgeschichte nicht
ausgeschlossen werden kann, zu recherchieren.
Ziel dieses Praktikums ist es, die in der Lost Art Internet Database existierenden
Abbildungen, mit in den Rechercheprozess einzubeziehen und dadurch weitere
Recherchemöglichkeiten anzubieten. Zur Umsetzung dieses Zieles eignen sich
verschiedene Methoden. Weit verbreitet und bereits im Lostart Projekt umgesetzt ist die
Suche nach Bildern nur mit Hilfe textueller Informationen (z.B. Titel, Künstler,
Herkunft, etc.). Das textbasierte Bildretrieval ist einfach zu implementieren, denn es
kann auf bestehende Techniken wie z.B. die Suche über Schlüsselwörter (Information
Retrieval) zurückgegriffen werden. Als Nachteil muss man allerdings anführen, dass die
manuelle Beschreibung der Bilder sehr aufwändig und durch mögliche Tippfehler
fehleranfällig ist. Hinzu kommt die Subjektivität der Beschreibungen von Abbildungen,
denn der Bildinhalt kann von verschiedenen Personen auf unterschiedliche Weise
interpretiert werden.
Eine weitere Recherchemöglichkeit bietet die inhaltsbasierte Suche (content-based
image retrieval (CBIR)), wozu die Suche nach enthaltenden Objekten, deren
Lagebeziehungen oder ähnlichen Abbildungen gehört [ABHo98]. Um
Ähnlichkeitsanfragen bearbeiten zu können, müssen aus den Bilddaten spezielle
Bildeigenschaften (Features) wie z.B. Farbe, Textur oder Struktur extrahiert werden
[Schm01]. Bereits die Auswahl der Features hat Auswirkungen auf die Ergebnisse.
Betrachten wir zum Beispiel die in Abbildung 1 dargestellten grünen Bilder, die in der
Bildmitte einen roten Kreis bzw. ein rotes Dreieck enthalten.
Abbildung 1: Beispielabbildungen mit ähnlichen Features
1 Einleitung
2
Werden hier die Features globale und lokale Farbe gewählt, so sind sich die
Abbildungen sehr ähnlich. Eine Ähnlichkeitssuche würde egal welche Abbildung man
zur Suche benutzt, die andere als Ergebnis liefern.
Fällt die Wahl jedoch auf die Struktur als Feature, so zeigt sich der Unterschied der
Bilder. Eine Ähnlichkeitssuche würde in diesem Fall keine Ähnlichkeit zwischen den
Bildern ermitteln. Obwohl dieses Beispiel nur einen Ausschnitt möglicher Probleme
offen legt, hat das inhaltsbasierte Bildretrieval dennoch ein großes Potenzial, um den
Rechercheprozess entscheidend zu verbessern. Weitere Vorteile sind zum Beispiel der
Wegfall der Subjektivität einzelner Nutzer und die Abnahme der manuellen Mehrarbeit.
1.1 Zielstellung der Arbeit
Das Ziel dieses Praktikums ist es, unter Berücksichtigung der Phasen der
Softwareentwicklung, eine Webanwendung zur effizienten Recherche in der Lost Art
Internet Datenbank zu entwerfen und einzelne Module zu implementieren. Die
Webanwendung soll den vollständigen Rechercheprozess, angefangen von der
Vorverarbeitung der Daten bis hin zur Repräsentation der Ergebnisse unterstützen.
Auch für bereits existierende Abbildungen muss die Möglichkeit bestehen diverse
Feature (z.B. Farbe oder Textur) zu extrahierten und diese in einer Datenbank
abzulegen. Der Nutzer soll die Möglichkeit bekommen die Ähnlichkeitssuche, die
Suche nach Objekten und die textbasierte Suche einzeln oder in Kombination
einzusetzen. Das heißt das System muss in der Lage sein auch komplexe
Nutzeranfragen zu bearbeiten, die aus mehreren Anfragetermen zusammengesetzt sind.
Aufgrund dieser Anforderungen ist ein wesentlicher Bestandteil der Arbeit die
Vorverarbeitung der Daten und die dazu gehörende Entwicklung von
Programmmodulen zur Bildsegmentierung, Verschlagwortung, Featureextraktion und
Bestimmung der Lagebeziehungen.
Da vollautomatische Objekterkennungssysteme, die z.B. mit dem Split and Merge
Algorithmus arbeiten, nicht immer die gewünschten Ergebnisse liefern [Schm01] und
das manuelle Nachzeichnen von Objektkanten ungenau und sehr zeitintensiv ist, soll ein
semiautomatisches Segmentierungstool entwickelt werden, das den Benutzer bei dieser
Aufgabe unterstützt. Ein weiterer wichtiger Aspekt ist die Entwicklung eines
Recherchesystems mit den entsprechenden Schnittstellen zur Integration der
Programmkomponenten. Am Ende des Rechercheprozesses sollen dem Nutzer die
Abbildungen, die eine Ähnlichkeit von beispielsweise 90 Prozent aufweisen, in
entsprechender Reihenfolge präsentiert werden.
1 Einleitung
3
Um in das Lost Art Projekt integriert werden zukönnen muss das zu entwickelnde
System als Webanwendung z.B. mit Hilfe von Servlets, JSP, Applets, PHP oder CGI
implementieren werden. Der Systemaufbau soll dabei mit Hilfe von Modulen erfolgen
und somit flexibel erweiterbar sein. Weiterhin muss das existierende Datenbankschema
an die neuen Anforderungen angepasst oder weiterentwickelt werden. Bei der
Umsetzung von Datenbankoperationen ist zu berücksichtigen, dass die
Datenbanksoftware Oracle 8i zum Einsatz kommt.
1.2 Gliederung der Arbeit
Im zweiten Kapitel dieser Studienarbeit werden bereits existierende Bild-
Retrievalsysteme vorgestellt und ihre Suchkriterien verglichen, wobei besonders die
Wahl der eingesetzten Features eine entscheidende Rolle spielt. Die bei der
Implementierung der Webanwendung und Programmmodule eingesetzten Techniken
der Bildsegmentierung und Ähnlichkeitssuche werden im Kapitel Grundlagen näher
erläutert. Der Schwerpunkt wird dabei auf den im Vorverarbeitungsmodul eingesetzten
Live Wire Algorithmus und die Ermittlung der Distanz zweier Abbildungen gelegt. Das
vierte Kapitel beschreibt die Entwicklung der Datenbank vom konzeptionellen bis hin
zum logischen Entwurf, außerdem wird der Entwurf der einzelnen Programmteile, des
Vorverarbeitungssystems und des Retrievalsystems dargestellt. Die Implementierungen
des Segmentierungstools, des Retrievalsystems und der Datenbank werden im fünften
Kapitel beschrieben. Dazu steht im Abschnitt 5.2 die Auswahl der eingesetzten Skript-
und Programmiersprachen im Mittelpunkt. Abschließend erfolgt eine
Zusammenfassung der Arbeit mit einem kurzen Ausblick auf mögliche Veränderungen
und Erweiterungen.
Die in der Entwurfsphase entstandenen Modelle, Tabellen und Diagramme sind im
Anhang zu finden.
2 Verwandte Arbeiten
4
2 Verwandte Arbeiten
In diesem Kapitel werden die bereits existierenden Bildretrievalsysteme CHARIOT,
MARS/IRS, Blobworld, QBIC, Viper, Image Rover und das Oracle Visual Information
Retrieval Cartridge vorgestellt und miteinander verglichen. Sie wurden ausgewählt, weil
sie stellvertretend für alle Systeme die verschiedenen Ansätze des Bildretrievals
abdecken. Es wird aufgezeigt, welche Kriterien die einzelnen Systeme bei der
inhaltsbasierten Suche verwenden, wie diese umgesetzt wurden und wie sich die
Systeme unterscheiden, die Schwerpunkte liegen dabei auf der Ähnlichkeitssuche, der
Anfrageverfeinerung und auf der Wahl der Feature.
2.1 CHARIOT - ETH Zürich
Das CHARIOT System ist ein inhaltsbasiertes Suchsystem für große Bilddatenbanken.
Es unterstützt die Ähnlichkeitssuche von Abbildungen mit Hilfe so genannter
Featurevektoren, die jeweils eine spezifische Bildeigenschaft repräsentieren. Beim
CHARIOT System werden ausschließlich Farbmomente, Farbhistogramme und
Texturmomente benutzt, um den Inhalt eines Bildes zu beschreiben [ETHZ01].
Zusätzlich wird das Bild in sich überlappende Teilregionen untergliedert (Abbildung 2),
welche dann mit den Basisfeaturevektoren verknüpft werden. Dieses Verfahren hat
Feature die zwischen 9 und 320 Dimensionen variieren zur Folge.
Abbildung 2: Untergliederung eines Bildes beim CHARIOT System [ETHZ01]
Um die Probleme des hochdimensionalen Raumes zu umgehen, erfolgt die
Ähnlichkeitssuche beim CHARIOT System über die Nächste-Nachbar Suche mit Hilfe
eines so genannten Vector Approximation Files (VA). Dabei wird ein Index aufgebaut,
dessen Werte sich den realen Merkmalen annähren und somit die Suche beschleunigen
[BMSW01]. Der Retrievalvorgang läuft in zwei Schritten ab, zuerst werden die
Nachbarn im VA-File ermittelt und danach die eigentlichen Distanzen mit Hilfe der
Originalfeature bestimmt.
IMAGE
2 Verwandte Arbeiten
5
Um die Suchergebnisse noch weiter zu verbessern, wurde ein Feedback-Mechanismus
in das System integriert. Dieser ist äquivalent zum MARS Projekt und erlaubt eine
Bewertung der Ergebnisse in den 5 Stufen: highly relevant, relevant, neutral, non-
relevant und highly non-televant [ETHZ01].
2.2 MARS - University of California, Irvine
MARS steht für ,Multimedia Analysis and Retrieval System' und setzt sich aus
verschiedenen Teilprojekten (Indexing, Retrieval, Management, etc.) zusammen
[UoCI01]. Teil des MARS Konzepts ist ein ,Image Retrieval System' (MARS/IRS)
welches die Ähnlichkeitssuche unterstützt.
Die Suche basiert wie beim CHARIOT System auf der Untergliederung der
Abbildungen sowie deren Farb- und Texturvektoren. Abbildungen werden dabei aber
nicht gleichmäßig (CHARIOT) sondern in Bereiche gleicher Textur und Farbe
untergliedert. Im MARS/IRS spielen zusätzlich auch die Struktur und Schlüsselwörter
wie Künstlername, verwendetes Material oder Erstellungsdatum eine Rolle [HuMR96].
Bei einer Ähnlichkeitsanfrage kann der Nutzer selbst entscheiden, welche Features mit
in den Rechercheprozess einbezogen werden sollen und welche nicht. Mit Hilfe eines
Relevanz Feedback-Mechanismus sollen auch hier neue Anfragen aus den Resultaten
der ersten Suche generiert werden können, um so bessere Ergebnisse zu erlangen.
2.3 Blobworld - University of California, Berkeley
Das Blobworld Projekt verfolgt eine etwas andere Strategie als CHARIOT oder
MARS/IRS. Ziel der inhaltsbasierten Suche ist hier die Segmentierung einer Abbildung
in Objektregionen, welche dann als Suchparameter eingesetzt werden [UoCB00].
Die Segmentierung eines Bildes verläuft dabei in drei Schritten [CBGM00]:
· Extraktion der Farb-, Textur- und Positionsfeatures für jedes Pixel,
· Gruppierung der Pixel zu Regionen anhand ihrer Feature und
· Beschreibung der Farbverteilung und Textur jeder Region.
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2003
- ISBN (eBook)
- 9783832477868
- ISBN (Paperback)
- 9783838677866
- DOI
- 10.3239/9783832477868
- Dateigröße
- 616 KB
- Sprache
- Deutsch
- Institution / Hochschule
- Otto-von-Guericke-Universität Magdeburg – Informatik
- Erscheinungsdatum
- 2004 (März)
- Note
- 1,7
- Schlagworte
- segmentierung softwareentwicklung java bildretrieval datenbank
