Review II: done

Formeln bei quadr. Ähnlichkeit mit MathML gesetzt, Bib OK

Acronyme, Absätze, Wordanführungszeichen done.

@ Prof. Kosch: Überschriften für "Demo Systeme" LOD2 finden done.

Review von Prof. Kosch eingearbeitet.

Unbekannte Character gecheckt.

Bei Formeln Block Typ entfernt.

Ähnlichkeitsabfragen Farbe

1

Histogramm Darstellung (Farbe)

• Eine Liste aus Farbprozentsatz-Paaren:
  • Beschreibt die Farbe und ihre prozentuales Vorkommen in einem Bild
    
  

Auto PC

Auto PDA_Phone

Auto PC

Auto PDA_Phone

Quantifizierung: Farbe

• Indizierte Farben
  • Ein jpg-Bild mit 256-Farb-Komponenten in jedem RGB302 Kanal
  • 256 x 256 x 256 Farbe gesamt n Gruppen, z.B., in 256 Gruppen, dadurch Reduzierung auf 256x256, d.h. jede Gruppe nimmt 265 Farben zum Zählen
  • In jeder Gruppe berechnen wir wieviele Pixel in diese Gruppe fallen, das ergibt z.B. 145.
  • Quantifizierung bedeutet hier auch die Kodierung der Zellwerte mit einer festen Anzahl von Bits.

Ähnlichkeitsmetriken

Minkowski Ähnlichkeit

Distanz L1 : r = 1

Distanz L2 : r = 2

Auto PC

Auto PDA_Phone

Quadratische Ähnlichkeit

Schnittmengen Ähnlichkeit (Swain et Ballard 1991)

Auto PC

Auto PDA_Phone

Einschränkung

• Ähnlichkeitsmetriken basierend auf Histogrammen ignorieren Ähnlichkeit zwischen Farben
  • Beispiel
    • Zwei Farbbehälter
      • Behälter-1 Farbbereich: 1 - 10
      • Behälter-2 Farbbereich: 11 - 20
    • Drei Farbpixel
      • Pixel 1 ist Farbe 10 -> Behälter-1
      • Pixel 2 ist Farbe 11 -> Behälter-2
      • Pixel 3 ist Farbe 20 -> Behälter-2
  • Pixel 2 ist ähnlicher zu Pixel 3 als zu Pixel 1 -> unvernünftig !
• Ignoriere räumliche Beziehungen zwischen Pixels

Auto PC

Auto PDA_Phone

2

Histogramm Darstellung (Farbe)

Farbverteilungen können durch Histogramme dargestellt werden.

Auto PC

Auto PDA_Phone

Auto PC

Auto PDA_Phone

Auto

Die Farbhistogramme werden erzeugt, indem diskrete Farbabschnitte gebildet werden und die Anzahl der Pixel gezählt wird, die in die jeweiligen Farbabschnitte fallen. Die Werte der Achsen sind hier der Farbwert und die prozentuelle Übereinstimmung.

Quantifizierung: Farbe

Quantifizieren (="Zählbarmachung") ist ein wissenschaftliches Verfahren zur Umformung. Eigenschaften eines Gegenstands oder die Beschaffenheit eines Sachverhaltes werden so umformuliert, dass sie in messbaren Größen erfasst werden können. Dieses Verfahren wird auch bei Farben angewendet.
Das Format Joint Photographic Experts Group (JPEG29) ist das gebräuchliche Format für die Darstellung von Fotos und anderen Halbtonbildern, die mehr als 256 Farben benötigen.
In einem jpg-Bild gibt es 256-Farb-Komponenten in jedem RGB302 Kanal (RGB302 = Rot, Grün, Blau). Daher gibt es insgesamt 256 x 256 x 256 Farben, da die Kanäle kombiniert werden. Um die Größe des Histogramms verwaltbarer zu machen werden diese Farben in n Farbbehälter aufgeteilt. Wenn n z.B. den Wert 256 hat, gibt es 256 Gruppen. Diese Gruppen nehmen je 256 Farben zum Zählen und dadurch reduziert sich die Anzahl der Farbbehälter auf 256 x 256.

In jeder Gruppe wird dann berechnet, wie viele Pixel in diese Gruppe fallen. Danach werden die Zellwerte durch eine Anzahl von festen Bits codiert - womit die Quantifizierung abgeschlossen ist.

Ähnlichkeitsmetriken

Mehrere Ähnlichkeitsmetriken sind in der Anwendung. Am häufigsten wird die Minkowski Ähnlichkeit benutzt:

Minowski Ähnlichkeit

Auto PC

Auto PDA_Phone

Auto

hq und ht sind die Signaturvektoren des Abfrage- bzw. des Zielbildes. In der Formel werden dann die einzelnen Werte der beiden Vektoren subtrahiert. Das absolute Ergebnis dieser Substraktion wird dann hoch den Faktor r gerechnet. Nachdem die Abstände der Vektoren so aufsummiert wurden, wird das Ergebnis hoch dem Kehrwert von r, als 1/r gerechnet.
Ist r = 1, bekommt man als Ergebnis die Manhattan Distanz, auch City Block Distanz genannt, wählt man r = 2 erhält man für d die Euklidische Distanz. Geht r gegen unendlich erhält man die größtmögliche Distanz zwischen den Vektoren.

Quadratische Ähnlichkeit

Die Quadratische Ähnlichkeit ermittelt auch die einzelnen Abweichungen zwischen Abfrage- und Zielbild.

ist eine N x N Matrix wobei aij der Ähnlichkeitskoeffizient zwischen den Dimensionen i und j ist.

Schnittmengen Ähnlichkeit

Die Schnittmengen Ähnlichkeit hat eine etwas andere Berechnung:

Auto PC

Auto PDA_Phone

Auto

Bei dieser Metrik werden irrelevante Elemente aus den Signaturvektoren herausgefiltert. hq und ht sind hier wieder die Signaturvektoren des Abfrage- bzw. des Zielbildes. Es wird jeweils der kleinere Wert im Vektor ausgewählt und aufsummiert. Dann wird das Ergebnis durch die Summe der Werte des Zielbildes dividiert und man erhält d. Sie wird typischerweise für eine Objekt (Teil eines Bildes)-Bild Abfrage benutzt.

Einschränkung

Ähnlichkeitsmetriken basierend auf Histogrammen ignorieren Ähnlichkeit zwischen Farben:
Die Zuteilung von Farben in Gruppen hat jedoch auch ihre Grenzen. Hat man beispielsweise zwei Farbbehälter in denen die Farben 1-10 bzw. 11-20 zugeteilt werden, werden die ähnlichen Pixel mit Farbe 10 und 11 je in einen der Farbbehälter gegeben, und das obwohl sie einander mehr ähneln als z.B. die Farbe 11 der Farbe 20.

Auto PC

Auto PDA_Phone

Auto

Farbhistogramme sind zwar eine geeignete Darstellung für Farbverhältnisse, dennoch können sie alleine nicht als Ähnlichkeitsmerkmal herangezogen werden. Die obigen zwei Bilder ergeben laut Farbhistogramm eine 100% Ähnlichkeit, jedoch ist die Verteilung der Farben grundverschieden. Daher ist es wichtig, auch die räumliche Beziehung bzw. Struktur zu beschreiben. Eine Möglichkeit ist die Zuhilfenahme eines Strukturelements, wie z.B. der MPEG31-7 Color Structure Desciptor realisiert.

Populäre Content-based Retrieval Systeme

1

Auto

• Hermitage Museum Homepage (QBIC)
  • http://hermitagemuseum.org/
  • http://hermitagemuseum.org/fcgi-bin/db2www/qbicColor.mac/qbic?selLang=English
• Medien Portal: WebSEEk
• Video Suchmaschine: VideoQ ViQ04

QBIC (IBM's Query By Image Content) Eigenschaften und Eigenschaften

• Farbe: QBIC berechnet die durchschnittlichen Munsell (Miyahara, et.al., 1988) Koordinaten für jedes Objekt und Bild, und ein k Element Farbhistogramm (k ist typischerweise 64 oder 256).
• Textur: QBIC's Textur Eigenschaften beruhen auf modifizierten Versionen von vorgeschlagen Granularitäts-, Kontrasts- und Gerichtetheits- Eigenschaften (H. Tamura, et.al., 1978). Die Granularität misst die Abstufung der Textur (Kiesel vs. Felsblöcke), der Kontrast beschreibt die Klarheit der Muster und die Gerichtetheit beschreibt, ob das Bild eine begünstigte Richtung hat oder isotrop ist (Gras versus glattes Objekt).
• Form: QBIC verwendet einige unterschiedliche Mengen von Formeigenschaften. Eine beruht auf einer Kombination von Fläche, Kreisförmigkeit, Exzentrizität und einer Menge von algebraischen Moment-Invarianten. Eine zweite ist der sich drehenden Winkel oder Tangenten-Vektoren um den Umkreis eines Objekts, berechnet von einer glatten Spline passend zum Umkreis. Das Ergebnis ist eine Liste von 64 Werten von drehenden Winkeln.

WebSeek

• WebSEEK: (John R. Smith und Shih-Fu Chang 1997)
  • Sammelt und kategorisiert Bilder/Videos im Web (600K Bilder, 10K Videos)

Auto PC

Auto PDA_Phone

Auto PC

Auto PDA_Phone

VideoQ

VideoQ: Video Suchmaschine

• Automatische Bewegungs-Analyse, Bereichssegmentierung und Verfolgung
• Räumlich-zeitliche Suche von multiplen Video Objekten
• Testen mit einer Video Sammlung (3.000 Video Clips) (30.000 Video Objekte)
• Demo

Auto PC

Auto PDA_Phone

2

Auto

QBIC (IBM's Query By Image Content) ist eine Bildsuchmaschine. Das System kommt beispielsweise auf der Homepage des Hermitage Museum Petersburg zum Einsatz (http://www.hermitagemuseum.org). Die virtuelle Galerie gibt dem Besucher der Website die Möglichkeit, Gemälde des Museums durch Farbanteile oder Layout zu suchen (http://www.hermitagemuseum.org/fcgi-bin/db2www/qbicSearch.mac/qbic?selLang=English).
Die Suche wird entweder mittels globaler Farbverteilung oder anhand eines grob skizzierten Beispiellayouts durch Kreis, Oval und Rechteck durchgeführt. Das Suchergebnis kann mit Ausschnitt angezoomt werden oder auch in unterschiedlichen Auflösungen dargestellt werden. Das Relevance Feedback gibt die Möglichkeit ähnliche Bilder zur selben Kategorie anzuzeigen.

WebSEEk, entwickelt an der New Yorker Columbia-Universität, ist ein nach Sachgebieten geordnetes Bildverzeichnis mit Bildern und Videos. Es kann nach Stichworten oder via Text gesucht werden, wobei das Suchergebnis auf Video, Farbfoto, Schwarzweißbilder oder Graphiken eingeschränkt werden kann.
WebSEEK sendet einen Webagent aus, der die Internetseiten nach Grafiken und Videos durchsucht. Aus deren Namen versucht es Informationen zum dargestellten Inhalt zu extrahieren. Anschließend überprüft WebSEEK welche Farben in einem Bild wo vorkommen. Daraus lassen sich Rückschlüsse auf die Art des Bildes wie Grafik, Foto, Schwarzweiß- oder Graubilder ziehen. Anhand dieser Informationen werden die Bilder in Klassen eingeordnet. Die Suche erfolgt demnach nicht nach einem Suchbegriff, sondern durch Navigation durch die Klassenhierarchie. Informationen aus Videosequenzen extrahiert das Programm aus Einzelbildern. Insgesamt hat WebSEEK mehr als 660 000 Internet-Bilder auf diese Weise indiziert.

VideoQ ViQ04, eine Video Suchmaschine wurde auch auf der Columbia Universität entwickelt. Individuelle Videos werden automatisch in seperate Shots segmentiert. Gegenwärtig werden über 2000 Shots in der großen Digital-Video Datenbank gespeichert. Jeder Shot wird komprimiert und in drei Schichten gespeichert, um unterschiedliche Bandbreiten zu unterstützen (30 - 7,5 Bilder/Sekunde). VideoQ ist unter http://www.ctr.columbia.edu/videoq erreichbar.

QBIC (IBM's Query By Image Content) Eigenschaften

QBIC wurde 1995 vom IBM Almaden Research Center entwickelt. Es ermöglicht die Suche mittels Beispielbildern, interaktiv gezeichneten Formen und unterschiedlichen Farb- und Texturmustern. Es ist in die Multimedia Extenders der IBMDB2 integriert.

Bei der Eigenschaftsextraktion der Farbe wird ein Farbhistogramm definiert. Dazu wird der Farbraum festgelegt: Berechnung der durchschnittlichen Munsell (Miyahara, et.al., 1988) Koordinaten für jedes Objekt und Bild. Danach folgt die Berechnung der Farbhistogramme: Das k Element Farbhistogramm (k ist typischerweise 64 oder 256) gibt den Prozentsatz der k Farben pro Pixel in jedem Bild an.

Die Textureigenschaften beruhen auf Granularität, Kontrast und Gerichtetheit (H. Tamura, et.al., 1987). Bei der Granularität wird die Abstufung der Textur, also die Grössenordnung gemessen (Kiesel vs. Felsblöcke). Beim Kontrast wird zwischen Lebendigkeit und Unruhe der Textur unterschieden (unifarben vs. gemustert). Bei der Gerichtetheit wird das Vorhandensein von Richtungen beschrieben (Gras - begünstigte Richtung vs. glattes Objekt - isotrop).

Bei den Formeigenschaften werden unterschiedliche Formen verwendet. Eine beruht auf einer Kombination von Fläche (Anzahl der Pixel im Formenkörper), Kreisförmigkeit (Kreisfläche/Umfang²), Exzentrizität und eine Menge von algebraischen Moment-Invarianten. Eine zweite ist der sich drehenden Winkel oder die Tangenten-Vektoren um den Umkreis eines Objekts, berechnet von einer glatten Spline passend zum Umkreis. Das Ergebnis ist eine Liste von 64 Werten von drehenden Winkeln.

WebSeek

Auto PC

Auto PDA_Phone

Auto

In WebSeek sammeln selbständige Web-agents oder "spiders" Bilder und Videos aus dem Internet. Die "spiders" durchlaufen das Web indem sie Hyperlinks zwischen Dokumenten folgen. Sie spüren so Bilder und Videos auf, überarbeiten sie und fügen die neue Information dem Katalog hinzu. Dieser Sammelprozess wird durch drei Module ermöglicht:

• Der Traversal Spider durchsucht das WWW23 nach Bildern, Videos oder Hyperlinks.
• Der Hyperlink Parser extrahiert die URIs der Bilder und Videos.
• Der Inhaltsextraktor erhält dann die Bilder und Videos, extrahiert aus ihnen die Eigenschaften und generiert Icons.

Auto PC

Auto PDA_Phone

Auto

Die Graphik beschreibt die Funktionsweise des Inhaltsextraktors.
Das Bild bzw. Video wird vom Hyperlinkparser zur Verfügung gestellt. Der Extraktor, auch Content-Spider genannt, erkennt das richtige Format (jpg, gif oder Video). Danach kann eine Formatkonvertierung in drei Schritten erfolgen:
Bei der Extrahierung visueller Eigenschaften, die für eine inhaltsbasierte Suche notwendig sind, wird ein Farbhistogramm erstellt. Außerdem wird auch eine Tabelle generiert, welche die extrahierten Farbregionen und die Eigenschaften und Attribute für jedes Bild und Video speichert.
Dann wird ein Icon bzw. Motion Icon generiert, das kompakt die visuelle Information repräsentiert. Das Icon kann dann für Browsing oder Darstellung der Abfrageresultate verwendet werden.
Attribute wie Breite, Höhe, Anzahl der Frames, Datentyp (Photo, Graphik oder Video) werden in der Attributsextraktion gewonnen.

VideoQ

Die Segmentierung in Video Shots, die Bewegungsanalyse mit Hilfe des sechs Parameter Affine Modell und die Verfolgung erfolgt automatisch.

Das VideoQ System will allen Benutzern ermöglichen, nach Videos mittels visueller Merkmale und räumlich-zeitlichen Beziehungen zu suchen.

Die Videosuchmaschine kann unter http://www.ctr.columbia.edu/videoq mit 3.000 Video Clips, aus denen 30.000 Video Objekte extrahiert wurden getestet werden. Um ein Video zu finden, kann man dies entweder durch textuelle oder visuelle Suche tun oder auch mittels dem Video Navigator durch die nach Kategorien strukturierten Clips browsen.

Auto PC

Auto PDA_Phone

Auto

VideoQ ist ein webbasiertes Videosuchsystem, bei dem der Benutzer mittels animierter Entwürfe Abfragen an das System stellen kann. Ein animierter Entwurf wird als eine Skizze definiert, in welcher der Benutzer Bewegungen in jedem Teil der Szene festsetzen kann. Diese Skizzen sind eine Sammlung von Objekten, die verschiedene Eigenschaften haben: Bewegung, räumlich-zeitliche Ordnung, Form und auch Farbe und Textur. Der Abfrageserver enthält eine Eigenschaftsdatenbank, welche die individuellen Merkmale der Videos speichert. Die Video Shot Datenbank enthält komprimierte MPEG31-Streams. Wenn der Benutzer seine Anfrage an das System übermittelt, sendet der Client sie über das Netzwerk zum Abfrageserver. Dort werden die Daten mit den Objekten in der Datenbank abgeglichen. Dann wird für jedes in der Abfrage spezifizierte Objekt eine Liste von Video-Shot Kandidaten generiert. Die Kandidaten werden dann zu einer Liste gruppiert und es werden Schlüsselbilder von der Video-Shot Datenbank extrahiert. Die übereinstimmenden Objekte werden in den Schlüsselbildern markiert. Der Benutzer kann interaktiv die Ergebnisse über das Netzwerk betrachten, indem er einfach ins Schlüsselbild klickt. So wird der VideoShot in Realtime aus der Datenbank "geschnitten" und steht dem Benutzer zur Verfügung.

Die gesamte Video Datenbank wird off-line verarbeitet. Die individuellen Videos werden in separate Shots zerlegt. Dann, innerhalb jedes Shots, werden Video Objekte quer durch Frames aufgespürt. Als Eigenschaften werden aber auch Schlüsselwörter herangezogen.

Bibliographie

2

Auto

Lu99

QBI04

Kos03

WES04

ViQ04