Seminar CBIR

Evaluierungsmethoden für die Bildsuche

1. Wozu Evaluation?

• Welche CBIR-Algorithmen sind gut?
• Welche CBIR-Algorithmen sind in speziellen Anwendungsgebieten gut?
• Kann man herausfinden, warum?
  Mit diesem Wissen könnte man die Algorithmen verbessern.

Evaluationsergebnisse können bei der Beantwortung dieser Fragen helfen.

• Elephantenbilder ===(Algorithmus)===> Ergebnis ===(Evaluationssystem)===> „gut“
• Bilder von Bergen ===(Algorithmus)===> Ergebnis ===(Evaluationssystem)===> „schlecht“

Wichtig:

• Meßbarkeit

  Am einfachsten wäre eine einzige Zahl als Ergebnis, zum Beispiel 0 für „maximal schlecht“ und 1 für „maximal gut“. Ein Graph (oder gar eine Liste von Bildern) sind schwerer zu interpretieren. In einem Graphen kann jedoch mehr Information enthalten sein.

• Vergleichbarkeit

  Welcher Algorithmus/Welches CBIR-System ist besser? Mit welchen Parametern sollte das CBIR-System benutzt werden? Falls ein Vergleich durch den Computer möglich ist, können Algorithmen verwendet werden, die „lernfähig“ sind (und zum Beispiel die optimalen Parameter selbst herausfinden).

Liste von Bildern als Evaluierungsmethode

„Early reports of the performance of CBIR systems were often restricted simply to printing the results of one or more example queries (e.g. Flickner et al. (1995)).
…
It is neither an objective performance measure, nor a means of comparing different systems.“ (aus *a)

Demo

Vorteile

• Weit verbreitet, praktisch überall (bei allen Systemen) anwendbar
• Ergebnisse für jeden sichtbar
• Praxisnah (je nach Anwendung)

Nachteile

• „Gute“ Ergebnisse können auch von weniger guten CBIR-Systemen erreicht werden.
• Nicht meßbar.
• Nicht (objektiv) vergleichbar mit anderen Ergebnissen.

2.1. Bilddatenbanken

Anforderungen an eine Bilddatenbank

• Bilder für jeden frei benutzbar.
• Möglichst eine Datenbank, die häufig für die Evaluation von CBIR-Systemen benutzt wird, damit Vergleiche einfacher möglich sind. Die Wahl der Datenbank beeinflußt (zumindest bisher) überall stark die Bewertungsergebnisse.

Verfügbare Bilddatenbanken (siehe *b)

• „WANG database“: Hier verwendet. Je 100 Bilder aus 10 Kategorien. Auf http://wang.ist.psu.edu/ bekommt man die Bilder.
• „UW database“ 1109 Bilder, keine Unterteilung in Klassen, Anmerkungen zu den Bildern
• „ZuBuD“ Häuser (5 Bilder von jedem der 201 Häuser, dazu 115 Anfragebilder)
• „CalTech database“ Bilder enthalten bestimmte Objekte (Motorräder, Flugzeuge, Gesichter) oder nicht. Graubilder.
• …

2.2. „Ground truth“

Wann sind Bilder ähnlich/unterschiedlich?

Welche Definition von „Ähnlichkeit“ soll man verwenden?

• 1. Wenn sie (optisch) ähnlich aussehen?
• 2. Wenn ihr Inhalt ähnlich ist?
• 3. Wenn sie unter dieselbe (abstrakte) Kategorie fallen?
• 3*. Extremfall: Bilder unterscheiden zu können, die Menschen nicht unterscheiden können.

• @1. Als Suchmaschine: „Wählen Sie Bilder, die ähnlich aussehen.“
• @2. Zum Beispiel: Beide Bilder zeigen einen Elephanten. Auf beiden Bildern ist dieselbe Person zu sehen
• @3. Bilder eines defekten technischen Verschleißteiles (Ziel: automatische Erkennung von Defekten) Bilder (z.B. der Haut) eines Menschen mit einer bestimmten Krankheit
• @3*. Die Probleme aus (3*) besser, schneller oder effizienter zu lösen als Menschen. (z.B. Erkennung des Defekts bei einem Verschleißteils innerhalb von Millisekunden)

Semantische   Lücke

Bei der Wahl der „Definition“ sollte man den Anwendungsbereich berücksichtigen.

Sowohl die Wahl der Datenbank als auch die „Ground truth“-Werte hängen von der Definition ab.

Woher bekommt man die Werte für die Ähnlichkeiten („ground truth“)?

• 1. Schon der Datenbank enthalten, wenn diese z.B. in Kategorien unterteilt ist.
• 2. Unterteilung in Gruppen durch Experten (z.B. in der Medizin)
  Hierbei ist auch eine zeitliche Verschiebung möglich (z.B. „Menschen, die innerhalb von 6 Monaten an XYZ erkrankt sind.“; „Verschleißteile, die bald defekt waren.“; „Kirche mit Baustil XYZ“; „Wald aus XYZbäumen “)
• 3. Simulation der Benutzer (siehe *a)
  Beispiel: Es wird angenommen, daß sich durch das Hinzufügen von etwas Rauschen zu einem Originalbild ein Bild entsteht, das (für einen Benutzer) ähnlich zum Originalbild ist.
  Es ist jedoch sehr schwierig, das Verhalten der Benutzer zu simulieren.
• 4. Direktes Fragen der Benutzer
  • Aufwendig bei großen (Bild-)Datenbanken
  • Es gibt Techniken, um den Aufwand zu verringern
  • subjektiv
  • Auswahl der Benutzer wichtig - jeder Benutzer bewertet anders
• 5. Schlüsselwörter zu jedem Bild
  Ähnlich wie 4, jedoch
  • Weniger aufwendig als 4 (lineare Zeit)
  • Schlüsselwörtern können unterschiedlich gewichtet werden
  • Probleme mit falsch geschriebenen Schlüsselwörtern
  • Probleme mit unterschiedlichen Schlüsselwörtern, die das gleiche bezeichnen (z.B. Wald-Baum-Nadelwald-Nadelbaum-Fichte)
  • Einige Probleme können reduziert werden, wenn eine vorgegebene Menge an Schlüsselwörtern benutzt wird.

• @1. (a) Die WANG-Datenbank ist in 10 Kategorien zu je 100 Bildern unterteilt.
• @4. (b) Zu 42 Anfragebildern der WANG-Datenban k ist eine Liste relevanter Bilder erstellt worden.
• @4. (c) Zu 17 Anfragebildern der WANG-Datenbank ist noch eine Liste relevanter Bilder erstellt worden.

(a), (b) und (c) sind schon drei Verschiedene Werte für die „ground truth“!

Verwendet werden soll (c).

2.3. Evaluationsmethoden/Bewertungsfunktionen

Beispiele (siehe *a, *b, *c, *d)

P(x): Precision nach x Bildern, R(x): Recall nach x Bildern

• precision/recall vs. number of images retrieved
• precision vs. recall (PR-graph, precision(recall)): "Retrieval effectiveness" (Beispiel)
• - detections vs. false alarms: "Receiver operating characteristic"
  - detections vs. fallout: "Relative operating characteristic"
• - P(number of relevant images) = P(N_R)
  - P(R=P): "the precision where recall and precision are equal" (*b)
  - „R-value“
• P(1), P(10), P(20), P(30), P(50)
• Mean Average Precision
• Recall at precision 0.5
• R(100)
• Rank first relevant
• Rank~: "normalized average rank"
• ANMRR: "Average Normalized Modified Retrieval Rank" (*c)
• PR-area (*b)

Es können noch unterschiedliche Gewichte berücksichtigt werden.

Einschub: Standard?

Quasistandard (direkt)

Nicht so gut…

Es gibt Benchmarkinitiativen wie z.B. Benchathlon, die sich aber bisher wohl nicht durchsetzen konnten.

Gründe

• Wie immer bei Standards: Ein Standard wird erst dann verwendet, wenn er sich durchgesetzt hat. Und durchgesetzt hat er sich dann, wenn er oft verwendet wird…
• Technik noch relativ neu (im Gegensatz zu Textsuche)
• Unterschiedliche Anwendungsgebiete (Ein Algorithmus der optimiert ist für die Erkennung/Unterscheidung von Bildern eines bestimmten Gebietes wird möglicherweise schlecht bewertet, wenn er mit einer allgemeinen Bilddatenbank getestet wird)
• Unterschiedliche Ansichten über Ähnlichkeit.
• Ergebnisse nicht einfach manipulierbar. (Erhöht oder senkt das die Verwendung/Akzeptanz eines Standards?)

Vergleich

• Schon oben angesprochen: Graphen oder einzelne Werte?

  In einem PR-Graphen ist mehr Information enthalten als in PR-area, P(R=P), … (man kann diese Werte aus dem Graphen berechnen).
  Spielen diese zusätzlichen Informationen eine (wesentliche) Rolle für die Bewertung eines CBIR-Systems?

  Falls man die Möglichkeit hat, die Graphen direkt zu vergleichen, kann man dort bestimmte Schwächen und Stärken eines Systems erkennen.

  Ich denke, daß für die Gesamtbewertung eines Systems diese zusätzlichen Informationen keine entscheidende Rolle spielen.
  Bei Graphen gibt es außerdem noch spezielle Probleme (Durchschnitt mehrerer Graphen; Graphen nicht direkt objektiv vergleichbar)
• 
  In (*b) wird angenommen, daß es nicht entscheidend ist, welcher Wert benutzt wird, da sie alle stark korreliert sind.

  Wie dort P(1) zu verwenden scheint mir jedoch nicht optimal (Nachteile der „error rate“).
  Rank~ (bzw. NARANK), PR-area oder P(R=P) halte ich für besser geeignet.

3. Anleitung zur Benutzung der Algorithmen

Siehe „Inhalt.txt“.

• (*a) "Performance Evaluation in Content-Based Image Retrieval: Overview and Proposals" 1999 (H. Müller, W. Müller, D. McG. Squire, T. Pun)
• (*b) "Classifiction Error Rate for Quantitative Evaluation of Content-based Image Retrieval Systems" (T. Deselaers, D. Keysers, H. Ney)
• (*c) "A Performance Evaluation Protocol for Content-Based Image Retrieval Algorithms/Systems" (Liu Wenyin, Zhong Su, Stan Li, Yan-Feng Sun, Hongjiang Zhang)
• (*d) "IMAGE RETRIEVAL EVALUATION" CBAIVL-98 (John R. Smith)

Copyright © 2004 Hendrik Tessendorf