1 - Studienarbeit - Entwurf und Umsetzung von kombinierten Anfragen für die Ähnlichkeitssuche auf...

1

- Studienarbeit -- Studienarbeit -

Entwurf und Umsetzung von kombinierten Entwurf und Umsetzung von kombinierten Anfragen für die Ähnlichkeitssuche auf Anfragen für die Ähnlichkeitssuche auf

digitalen Bilder auf der Basis von digitalen Bilder auf der Basis von Regionen und FeaturesRegionen und Features

Bearbeiter:Bearbeiter: Ralph SpickermannRalph SpickermannBetreuer:Betreuer: Holger MeyerHolger Meyer

Temenushka IgnatovaTemenushka IgnatovaStand:Stand: 25.04.200625.04.2006

2

GliederungGliederung

1.1. Grundlagen/AufgabenstellungGrundlagen/Aufgabenstellung2.2. Regionenbasierte RepräsentationenRegionenbasierte Repräsentationen3.3. Konzeptuelles DatenmodellKonzeptuelles Datenmodell4.4. Prototypische ImplementierungPrototypische Implementierung5.5. Aktueller StandAktueller Stand

3

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

Nutzung von Bildern für die verschiedensten Nutzung von Bildern für die verschiedensten ZweckeZweckeOrganisation in Bilddatenbanken immer wichtigerOrganisation in Bilddatenbanken immer wichtigerBeispiele: ClipArt-Sammlungen, Museen, Beispiele: ClipArt-Sammlungen, Museen, eNoteHistoryeNoteHistoryAber:Aber:

sesensorische Lückensorische Lückesemantische Lückesemantische Lücke

4

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

Anfrage nach Bildinhalten nötig, um semantische Anfrage nach Bildinhalten nötig, um semantische Lücke zu schließenLücke zu schließenNutzung von Features zur Bildbeschreibung (Farbe, Nutzung von Features zur Bildbeschreibung (Farbe, Form, Textur, ..)Form, Textur, ..)Erweiterung zum regionenbasierten System durch Erweiterung zum regionenbasierten System durch Extraktion von markanten Bildteilen Extraktion von markanten Bildteilen Festlegen von räumlichen Beziehungen (Abstand, Festlegen von räumlichen Beziehungen (Abstand, Hierarchie, Überlappung, ..)Hierarchie, Überlappung, ..)

5

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

6

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

7

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

AufgabeAufgabe::Untersuchung der Möglichkeiten, Regionen und Untersuchung der Möglichkeiten, Regionen und Features in einer Anfrage zu verbindenFeatures in einer Anfrage zu verbindenRecherche bestehender Darstellungen und SystemeRecherche bestehender Darstellungen und Systeme

Anfrage = zu einer gegebenen Vorgabe passende Anfrage = zu einer gegebenen Vorgabe passende Bilder aus einer Bildsammlung findenBilder aus einer Bildsammlung findenDazu Definition von Ähnlichkeit notwendigDazu Definition von Ähnlichkeit notwendig

8

1. Grundlagen/Aufgabenstellung1. Grundlagen/Aufgabenstellung

Ähnlichkeit ist ein Maß für die Distanz zweier Ähnlichkeit ist ein Maß für die Distanz zweier Features in einem FeatureraumFeatures in einem FeatureraumOft basierend auf einer MetrikOft basierend auf einer MetrikBeispiele für Distanzfunktionen:Beispiele für Distanzfunktionen:

Diskrete MetrikDiskrete MetrikLLpp-Distanz-Distanz

Bottleneck-DistanzBottleneck-DistanzEarth Mover's Distance (EMD)Earth Mover's Distance (EMD)

9

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

2.1. 2D-String2.1. 2D-StringEffiziente Darstellung räumlicher BeziehungenEffiziente Darstellung räumlicher BeziehungenSegmentierung von Bildern, anschließend Segmentierung von Bildern, anschließend Anordnung der Regionen in x- und y-RichtungAnordnung der Regionen in x- und y-RichtungEffiziente Suche auf so entstandenem Effiziente Suche auf so entstandenem zweidimensionalen String möglichzweidimensionalen String möglich

10

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

Stringdarstellung:Stringdarstellung:(u,v) = (C<A<D<B, D<C<A=B)(u,v) = (C<A<D<B, D<C<A=B)

11

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

Matching von 2D-Strings:Matching von 2D-Strings:Exaktes Matching:Exaktes Matching:

Gleiche ObjekteGleiche ObjekteGleiche Beziehungen zwischen den ObjektenGleiche Beziehungen zwischen den Objekten

Angenähertes Matching:Angenähertes Matching:Nicht zwangsweise Übereinstimmung der Nicht zwangsweise Übereinstimmung der Teilstrings nötigTeilstrings nötigÄhnlichkeit zwischen Strings wird berechnetÄhnlichkeit zwischen Strings wird berechnet

12

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

2.2. Attributierter Relationaler Graph (ARG)2.2. Attributierter Relationaler Graph (ARG)Basiert auf Grundlagen der GraphentheorieBasiert auf Grundlagen der GraphentheorieGraph G = (V,E,A) mitGraph G = (V,E,A) mit

V = Knotenmenge, entspricht den RegionenV = Knotenmenge, entspricht den RegionenE = Kantenmenge, entspricht Beziehungen E = Kantenmenge, entspricht Beziehungen zwischen Regionenzwischen RegionenA = Attributmenge mit Attributen, welche sowohl A = Attributmenge mit Attributen, welche sowohl Knoten als auch Kanten zugeordnet sein könnenKnoten als auch Kanten zugeordnet sein können

13

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

14

2. Regionenbasierte Repräsentationen2. Regionenbasierte Repräsentationen

Matching von ARGs:Matching von ARGs:Exaktes Matching:Exaktes Matching:

Basiert auf GraphenisomorphismusBasiert auf Graphenisomorphismusbijektive Abbildung von einem Graphen G1 zu bijektive Abbildung von einem Graphen G1 zu einem Graphen G2einem Graphen G2

Angenähertes Matching:Angenähertes Matching:Nutzung eines Fehlermodells Nutzung eines Fehlermodells Gesucht sind minimale Kosten für Änderungs-Gesucht sind minimale Kosten für Änderungs-operationen, damit ein Graph in den anderen operationen, damit ein Graph in den anderen überführt wirdüberführt wird

15

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

Ziel:Ziel: Erstellung eines Frameworks, welches Anfragen Erstellung eines Frameworks, welches Anfragen nach Features sowie nach Regionen miteinander nach Features sowie nach Regionen miteinander verbindetverbindet

Dazu Abbildung der grundlegenden Komponenten Dazu Abbildung der grundlegenden Komponenten auf abstrakte Klassenauf abstrakte KlassenKomponenten: Feature, Region, Relation, BildKomponenten: Feature, Region, Relation, Bild

16

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

17

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

Versuch der Anwendung des Frameworks auf Versuch der Anwendung des Frameworks auf bestehende Repräsentationenbestehende Repräsentationen

2D-String2D-String

ARGARG

18

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

Abbildung auf ARG:Abbildung auf ARG:Vom Konzept der ziemlich nah am FrameworkVom Konzept der ziemlich nah am FrameworkKnoten = RegionKnoten = RegionKante = RelationKante = RelationAttribut = FeatureAttribut = Feature

19

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

20

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

Abbildung auf 2D-String:Abbildung auf 2D-String:Region = RegionRegion = RegionAbbildung der räumlichen Anordnung auf Feature Abbildung der räumlichen Anordnung auf Feature mit RangX und RangYmit RangX und RangYBeziehungen wie north-of, south-of, .. werden als Beziehungen wie north-of, south-of, .. werden als Relation modelliert, welche die Ränge vergleichtRelation modelliert, welche die Ränge vergleicht

21

3. Konzeptuelles Datenmodell3. Konzeptuelles Datenmodell

22

4. Prototypische Implementierung4. Prototypische Implementierung

Anwendung des Frameworks anhand eines Anwendung des Frameworks anhand eines BeispielesBeispielesNutzung einer geeigneten BildsammlungNutzung einer geeigneten BildsammlungExtraktion von Regionen und FeaturesExtraktion von Regionen und FeaturesFeatures: dominante Farbe, Regionenzentrum, Features: dominante Farbe, Regionenzentrum, umschließendes Rechteckumschließendes RechteckBeziehungen: Himmelsrichtungen, Abstand, Beziehungen: Himmelsrichtungen, Abstand, Überlappung, EnthaltenseinÜberlappung, Enthaltensein

23

4. Prototypische Implementierung4. Prototypische Implementierung

24

5. Aktueller Stand5. Aktueller Stand

Theoretischer Teil so gut wie fertigTheoretischer Teil so gut wie fertigKonzeptueller Teil so gut wie fertig, muss noch Konzeptueller Teil so gut wie fertig, muss noch geschrieben werdengeschrieben werdenMomentan ImplementierungMomentan Implementierung

In JavaIn JavaSuche nach geeigneter BildsammlungSuche nach geeigneter BildsammlungSchreiben der Klassen und MethodenSchreiben der Klassen und MethodenImplementierung in DB2 Implementierung in DB2

25

- THE END -- THE END -Vielen Dank!Vielen Dank!