Das Internet bietet eine enorme Anzahl an Bildern. Bildsuchmaschinen stehen vor der Herausforderung Bilder e ektiv und e zient zu erschlie en. Die klassischen Arten der Bildsuche, die stichwort- und die inhaltsbasierte Bildsuche, haben Nachteile. Ein Retrieval-Modell, welches die Vorteile beider Sucharten integriert und die Nachteile ausschlie t, ist die auf einem visuellen Worterbuch basierende Bildsuche. Ein visuelles Worterbuch ist dabei eine Menge von Stichwortzu-visueller-Beschreibung Beziehungen. Wir prasentieren ein Verfahren zur automatischen Erstellung eines visuellen Worterbuchs aus einer Trainingsmenge von annotierten Bildern. Dabei werden verschiedene Modelle von visuellen Beschreibungen untersucht und anschlie end evaluiert. Wir zeigen, dass eine kompakte visuelle Beschreibung existiert, die verglichen mit multiple-Instanzen visuellen Beschreibungen bessere Retrieval-Ergebnisse liefert und gleichzeitig die Anfragezeit drastisch senkt. image search, visual dictionary, visual words, visual phrases Das heutige World Wide Web stellt einen gro en und standig wachsenden Datenbestand von Bildern dar und bildet somit eine gute Basis fur die Suche nach gewunschten Bildern. Es gibt zwei klassische Arten der Bildsuche: die stichwortbasierte und die inhaltsbasierte Bildsuche. Die stichwortbasierte Bildsuche basiert auf Annotationen und Metadaten der Bilder. Die Anfrageformulierung erfolgt textuell, somit schnell und unkompliziert. Bei der Verarbeitung der Anfrage sucht das System nach Bildern, die, grob gesagt, die Stichworter aus der Anfrage beinhalten. Einen Nachteil hat diese Suchart jedoch: der Erfolg der Suche hangt von der Qualitat der Annotationen und Metadaten der Bilder ab. Je nachdem, ob Bilder manuell vom Benutzer oder automatisch mit Hilfe eines Algorithmus annotiert wurden, wei-
sen diese unterschiedliche Schwachen auf, z.B. die Subjektivitat des Beschreibenden, abstrakte Formulierungen oder falsche Stichwortzuordnungen, sowie Unvollstandigkeit der Beschreibung. Aufgrund dieses Nachteils versucht man heutzutage, fern von den Annotationen, auf das Bild selbst einzugehen und somit den Inhalt des Bildes zu erschlie en. Die inhaltsbasierte Bildsuche basiert demnach auf visuellen Eigenschaften des Bildes, z.B. bzgl. der Farbe, der Textur, Form usw. Eine Anfrage wird mittels einem Beispielbild gestellt, das Retrieval-System sucht dann nach Bildern, die dem Anfragebild ahnlich sind, bezogen auf den, dem System zugrundeliegenden Deskriptor und das A hnlichkeitsma . Der Nachteil dieser Suchart betri t die Anfrageformulierung mittels dem Anfragebild - ein Anfragebild liegt dem Benutzer in der Regel nicht vor, dieses wird schlie lich gesucht. Gewunscht ist daher ein Retrieval-System, welches die Vorteile beider Sucharten integriert, d.h. eine textuelle Anfrageformulierung mit einer inhaltsbasierten Bildsuche kombiniert. Eine Losung ist das Modell des visuellen Worterbuchs als eine Menge von Stichwort-zu-visueller-Beschreibung Beziehungen. Bei der Bildsuche auf der Basis des visuellen Worterbuchs wird nun eine Anfrage textuell gestellt, dann die Stichworter aus der Anfrage in dem visuellen Worterbuch nachgeschlagen und deren U bersetzung, d.h. eine visuelle Beschreibung des Stichwortes, fur die anschlie ende inhaltsbasierte Bildsuche verwendet. Die Entwicklung eines Verfahrens zur automatischen Erstellung eines visuellen Worterbuchs ist Gegenstand dieses Papers. Wir geben zunachst einen U berblick uber verwandte Arbeiten, beschreiben dann das entwickelte Verfahren, evaluieren visuelle Beschreibungen und schlie en mit einer Schlussfolgerung und einem Ausblick. 2.
In der Literatur existieren zwei weitverbreitete De
nitionen des Begri s visuelles Worterbuch. Die erste De nition
beschreibt das Konzept der Zuordnungen von Stichwort zu
visueller Beschreibung, die zweite betri t die Quantisierung
des Deskriptor-Raums in Partitionen, sogenannte visuelle
Worter. Jeder Deskriptor wird dann mit seinem zugehorigen
visuellen Wort reprasentiert. Alle Partitionen bilden das
visuelle Worterbuch. Oft werden beide Konzepte kombiniert
[
In diesem Kapitel prasentieren wir das entwickelte Verfahren zur automatischen Erstellung eines visuellen Worterbuchs aus einer Trainingsmenge von annotierten Bildern. Das Verfahren basiert auf der Idee, die Trainingsbilder einmal bzgl. der A hnlichkeit ihrer Annotationen und einmal bzgl. ihrer visuellen A hnlichkeit zu gruppieren, dann die Trainingsbilder, die bzgl. der beiden Aspekte zueinander ahnlich sind, d.h. bzgl. beider Aspekte zusammen gruppiert wurden, aufzusuchen und aus diesen schlie lich Korrelationen zwischen Stichwortern und visuellen Bildmerkmalen abzuleiten. 3.1
Das visuelle Worterbuch kann man sich wie ein herkommliches Worterbuch vorstellen, welches aus einer Menge von Eintragen besteht. In dem visuellen Worterbuch sollen Objekte und visuelle Zusammenhange, wie z.B. Tiere, Gegenstande, Gebaude, Logos, Symbole, etc. verwaltet werden. Jeder Eintrag ist ein Paar aus einem Stichwort, der das Objekt benennt und einer dazugehorigen visuellen Beschreibung des Objektes. Stichworter sollen in der Grundform vorliegen wir sprechen dann von Termen -, und es soll die Polysemie der Terme unterstutzt werden. Eine visuelle Beschreibung stellt eine Einheit dar, die fur die inhaltsbasierte Bildsuche verwendet wird. Diese soll nur die fur dieses Objekt relevanten visuellen Charakteristika erfassen, die allen Perspektiven und Erscheinungsformen des Objektes gemeinsam sind. Zudem soll diese aus E zienzgrunden kompakt, sowie zu der Reprasentation der Bilder kompatibel sein. 3.2
Das konzeptuelle Modell des Verfahrens ist in Abbildung 1 dargestellt. Grundlage zum Erlernen des visuellen Worterbuchs bildet die Trainingsmenge von annotierten Bildern, die beliebig und ohne zusatzliche Vorbearbeitung gewahlt werden kann. Ausgehend von dieser werden zunachst einmal zwei Ziele verfolgt: die Gruppierung von ahnlichen Bildern auf der Basis der semantischen A hnlichkeit ihrer Annotationen und die Gruppierung von ahnlichen Bildern bezuglich ihrer visuellen A hnlichkeit. Dazu werden die Annotationen sowie die Bilder unabhangig voneinander in eine interne Reprasentation uberfuhrt und auf der Basis eines de nierten A hnlichkeitsma es gruppiert. Aus den beiden Gruppierungen wird dann das visuelle Worterbuch erstellt. Dazu wird zunachst einmal das Vokabular fur das visuelle Worterbuch bestimmt. Fur jeden Term des Vokabulars werden Trainingsbilder ermittelt, die diesen Term in der Annotation enthalten und bzgl. der A hnlichkeit von Annotationen und der visuelTrainingsmenge
Annotierte
Bilder Annotationen Repräsentation & Ähnlichkeitsmaß
Bilder Repräsentation & Ähnlichkeitsmaß Gruppierung
Gruppierung s h c esd rebu lngu tröW lte n rs lle E eu s i v
Wahl des Vokabulars Abgleich der Gruppierungen
Visuelle
Beschreibung Visuelles Wörterbuch
Te....r..m Visuelle Be....s..chreibung Abbildung 1: Das konzeptuelle Modell des Verfahrens len Bildmerkmale ahnlich sind. Es ndet also ein Abgleich der Gruppierungen statt. Aus den ermittelten Trainingsbildern eines Terms wird schlie lich die visuelle Beschreibung des Terms gelernt und zusammen mit dem Term als ein Eintrag in dem visuellen Worterbuch abgespeichert. Wir erhalten das visuelle Worterbuch aus Stichwort-zu-visuellerBeschreibung Eintragen. 3.3
Fur einen semantischen Vergleich mussen Annotationen und Bilder in eine interne Darstellung uberfuhrt werden.
Wir bereiten auf und bereinigen zuerst die Annotationen, erstellen dann einen Index mit dem Indexvokabular und leiten daraus fur jede Annotation einen Annotationsvektor gema der tf-idf Gewichtung. Als A hnlichkeitsma wahlen wir das Kosinusma .
Als Grundlage fur die Reprasentation von Bildern
wahlen wir Scale Invariant Feature Transform (SIFT)[
Fur die Bestimmung der A hnlichkeit zweier Bilder verwenden wir ein A hnlichkeitsma , das auf dem Histogrammschnitt hs zweier Histogramme basiert: hs(nHistiX ; nHistjX ) = k X min(nHistiX [l]; nHistjX [l]) (3) l=1 wobei nHistX die normalisierte Version des absoluten Histogramms aHistX darstellt. Die A hnlichkeit zweier Bilder bi und bj ergibt sich dann mit: ahnlichkeit(bi; bj) = (1
) hs(nHistiV W ; nHistjV W ) (4)
+
hs(nHistiV P ; nHistjV P )
Fur den Wert des Gewichts orientieren wir uns an dem
Paper [
Fur die Gruppierung der Annotationen wenden wir den
in [
Die Gruppierung von ahnlichen Bildern bedeutet, Bilder, die dasselbe Objekt beinhalten, in eine Gruppe zu fassen. Da wir von nicht vorbearbeiteten Trainingsbildern ausgehen, liegen diese Bilder also in der Regel etwas "verschmutzt\ vor, d.h. sie beinhalten neben dem Hauptobjekt ggf. noch andere irrelevante Objekte oder einen Hintergrund. Dadurch kann es leicht zu dem Problem kommen, dass zwei Bilder, die wir intuitiv nicht gruppiert hatten, weil diese unterschiedliche Hauptobjekte haben, trotzdem einen hoheren A hnlichkeitswert haben, als zwei Bilder, die dem menschlichen Emp nden nach ahnlich sind. Bei der Wahl eines Gruppierungsverfahrens mussen wir diese Problematik einbeziehen. Clusteringverfahren, die die Trainingsbilder in Partitionen zerlegen, sind nicht geeignet, es konnte namlich passieren, dass Bilder aufgrund fur uns falsch erscheinenden Gemeinsamkeiten, wie dem Hintergrund, zusammengefasst und dann bzgl. des relevanten Objektes nicht mehr gruppiert werden. Am besten ware, man hatte visuelle Beschreibungen von den, in der Trainingsmenge enthaltenen Objekten und wurde diese als Clusterzentren nehmen, um die Trainingsbilder anhand dieser Clusterzentren uberlappend zu gruppieren. Die visuellen Beschreibungen sind aber genau das was wir suchen. Hatten wir solche Beschreibungen, dann ware die Gruppierung hier uber ussig. Man kann trotzdem versuchen solche visuellen Beschreibungen zu simulieren, indem man das was den Trainingsbildern gemeinsam ist, extrahiert. Sind zwei Bilder bzgl. einem Objekt ahnlich und teilen damit die Charakteristika des Objektes, dann mussen die gemeinsamen Charakteristika auch in der kompakten Bilddarstellung der visuellen Worter und der visuellen Phrasen verankert sein, namlich als Durchschnitt der visuellen Worter und visuellen Phrasen Histogramme der beteiligten Bilder. Der Durchschnitt ds zweier Bilder bi, bj ist wie folgt de niert: ds(bi; bj) = dsV W (bi; bj); dsV P (bi; bj)
dsX (bi; bj) = (m(1); :::; m(k)) m(l) = min(aHistiX [l]; aHistjX [l]) mit und (5) wobei bei X = V W ist k = 1000 und X = V P ist k = 500:500. Fur die Gruppierung der Trainingsbilder berechnen wir die Durchschnitte der ahnlichsten Bilder, betrachten diese als Pseudo-Objekte und damit als Centroide, und clustern die Trainingsbilder gema einem Schwellwert uberlappend an diese Durchschnitte. Wir erhalten eine Menge von Gruppen visuell ahnlicher Bilder Glvisuell j 1 l ng . 3.5
Als nachstes mussen wir klaren, welche Stichworter in das visuelle Worterbuch aufgenommen werden. Als Stichworter kommen naturlich nur Terme aus dem Indexvokabular in Frage. Die U bernahme aller Terme als Stichworter ist jedoch nicht sinnvoll, denn nicht alle Terme bzw. die den Termen zugrundeliegenden Worter beschreiben Objekte oder beinhalten einen visuellen Aspekt. Wir betrachten daher die Gruppen, die wir durch das Clustering von Annotationen erhalten haben. Wir nehmen an, dass innerhalb einer Annotationsgruppe die Terme, die in den meisten Annotationen vorkommen, etwas mit dem visuellen Inhalt der zugehorigen Bilder zu tun haben mussen. Fur jede Annotationsgruppe werden daher diese hochfrequenten Terme bestimmt. Dazu wird zunachst der Term mit der hochsten Annotationshaugkeit ermittelt und dann noch weitere, deren Annotationshau gkeit gro er ist als 0:7 mal die maximale Hau gkeit. Die Vereinigung der so erhaltenen Terme bildet dann das Vokabular des visuellen Worterbuchs, also im Grunde die Eintrage. Um die Forderung nach der Unterstutzung der Polysemie von Termen zu realisieren, werden die betro enen Terme mehrmals, nur mit unterschiedlichem Kontext, in dem visuellen Worterbuch aufgefuhrt. Der jeweilige Kontext eines Terms ergibt sich aus der Gruppe, genauer aus den anderen Termen der Gruppe, zu der der Term gehort. Als Kontext wird der Centroid der Gruppe verwendet. Wir erhalten somit eine Seite des visuellen Worterbuchs, namlich eine Menge von Eintragen, die jeweils ein Objekt reprasentieren und aus einem Term und seinem Kontextvektor bestehen. 3.6
Fur jeden Eintrag des visuellen Worterbuchs muss nun eine Menge von Trainingsbildern bestimmt werden, aus der die visuelle Beschreibung des Terms gelernt werden soll. Das bedeutet, es mussen die Bilder bestimmt werden, die sowohl bzgl. des Terms als auch visuell bzgl. des beinhaltenden Objekts ahnlich sind. Dazu werden Bilder, die diesen Term in der Annotation enthalten, aus der Annotationsgruppe des Terms genommen und es wird daraus eine Gruppe Geintrag gebildet. Diese Gruppe wird dann mit jeder Gruppe Glvisuell visuell ahnlicher Bilder abgeglichen. Beim Abgleich wird der Mengendurchschnitt jeweils zweier Gruppen gebildet, indem die Bilder ubernommen werden, die in der Gruppe Geintrag und in der Gruppe Glvisuell vorkommen. Der resultierende Mengendurchschnitt zweier Gruppen muss mindestens zwei Bilder beinhalten, sonst konnen keine gemeinsamen Charakteristika gelernt werden. Als Resultat des Abgleichs erhalten wir wiederum, ggf. uberlappende, Gruppen von Bildern. Die Bilder innerhalb einer solchen Gruppe sind nun visuell als auch bzgl. des Terms und seinem Kontext ahnlich. Jeder Eintrag des visuellen Worterbuchs besteht nun aus einem Term, seinem Kontextvektor und der Menge der Bildgruppen aus welcher eine visuelle Beschreibung im nachsten Schritt hergeleitet wird. 3.7
Als nachstes muss die rechte Seite des visuellen Worterbuchs, die Seite der visuellen Beschreibungen, bestimmt werden. Wir betrachten einen Eintrag, also einen Term, des visuellen Worterbuchs und die ihm zugehorige, im letzten Abschnitt bestimmte Menge von Bildgruppen. Es gibt mehrere Moglichkeiten aus der Menge der Bildgruppen eine visuelle Beschreibung abzuleiten. Im Folgenden stellen wir einige Arten von visuellen Beschreibungen in der Reihenfolge der eigenen Entwicklung und Untersuchung vor. 3.7.1
Die erste und einfachste Methode eine visuelle Beschreibung anzugeben ist, die Bildgruppen zu vereinigen und die so erhaltene Menge an Trainingsbildern als Reprasentation des Terms zu verwenden. Bei der Bildsuche zu diesem Term nden dann mehrere inhaltsbasierte Bildsuchen statt, indem jedes dieser Trainingsbilder als Anfragebild verwendet wird. Bei dieser multiple-Instanzen visuellen Beschreibung erhalten wir jedoch zunachst fur jedes Anfragebild ein Ranking von Bildern als Ergebnis. Es stellt sich also die Frage, wie das Endergebnis aus den Ergebnissen der einzelnen Anfragen berechnet werden soll. Fur die Angabe des Endergebnisses werden drei Strategien untersucht.
Bei der ersten Strategie wird das beste Resultat als Endergebnis ausgegeben. Dazu wird die Gute der einzelnen Ergebnisse mittels einem Qualitatsma berechnet. Eine solche Berechnung erfordert allerdings zu wissen, welche Bilder des Ergebnisrankings fur den Anfrageterm relevant und welche irrelevant sind. Dafur mussten die Bilder in der Bilddatenbank kategorisiert oder mit Termen versehen sein. Von diesem Fall kann man in der Realitat jedoch nicht ausgehen. Diese Strategie ist auf einer Bilddatenbank also praktisch nicht anwendbar, lediglich auf einer vorbereiteten Testmenge. Aus Grunden des Performance Vergleichs wird diese trotzdem aufgefuhrt und untersucht. (AlleBilder-BesterScore)
Jedes Bild aus der Bilddatenbank hat fur jedes Anfragebild der visuellen Beschreibung, also in jedem der einzelnen Ergebnisse, eine Rankingposition und einen A hnlichkeitswert zum Anfragebild. Bei der zweiten Strategie wird fur jedes Bild aus der Bilddatenbank der maximale A hnlichkeitswert aus seinen A hnlichkeitswerten zu allen Anfragebildern ausgewahlt, die Bilder dann entsprechend ihrem maximalen A hnlichkeitswert sortiert und als Endergebnis ausgegeben (AlleBilder-MaxAhnlichkeit ).
Eine dritte Losung zur Bestimmung des Endergebnisses ist, fur jedes Bild aus der Bilddatenbank das arithmetische Mittel ihrer Rankingpositionen aus den einzelnen RankingErgebnissen zu berechnen, dann die Bilder bezuglich diesem arithmetischen Mittel aufsteigend zu sortieren und dieses Ranking als Endergebnis auszugeben. (AlleBilder-DurchschnittsRank ) 3.7.2
Bei der letzten visuellen Beschreibung werden nicht wirklich Charakteristika des Objektes gelernt, diese stellt also keine visuelle Beschreibung in unserem gewunschten Sinne dar. Wir gehen davon aus, dass die A hnlichkeit zweier ahnlicher Bilder auf einer gemeinsamen Teilmenge der visuellen Worter und visuellen Phrasen basiert. Wir extrahieren daher die Gemeinsamkeiten zweier ahnlicher Bilder, indem wir den Durchschnitt ihrer Histogramme gema der Formel 5 bilden. Fur jede Bildgruppe aus der Menge der Bildgruppen werden paarweise Durchschnitte der Trainingsbilder aus der Bildgruppe berechnet. Die visuelle Beschreibung besteht dann aus allen gebildeten Durchschnitten, d.h. jeder Durchschnitt dient bei der inhaltsbasierten Bildsuche als ein Anfragebild und es nden mehrere Anfragen statt.
Wie bei der ersten visuellen Beschreibung, erhalten wir auch hier eine Menge von einzelnen Ergebnissen und mussen diese zu einem Endergebnis berechnen. Wir wenden dazu die drei beschriebenen Strategien an (Durchschnitte-BesterScore, Durchschnitte-MaxAhnlichkeit, Durchschnitte-DurchschnittsRank ). 3.7.3
Die bisher vorgestellten visuellen Beschreibungen sind problematisch: sie bestehen aus mehreren Anfrageinstanzen und weisen daher eine zeitaufwandige Anfrageverarbeitung auf. Eine kompakte Darstellung der visuellen Beschreibung, d.h. eine Darstellung, die aus nur einer Anfrageinstanz besteht, ware von Vorteil. Eine einfache Losung wiederum ist, das beste Trainingsbild aus den Trainingsbildern eines Eintrags als visuelle Beschreibung zu wahlen. Um das beste Trainingsbild zu bestimmen, vereinigen wir die Bildgruppen und stellen mit jedem Bild aus der Vereinigung eine Anfrage an die ganze Trainingsmenge. Mit einem Qualitatsma wird jedes Anfrageergebnis bewertet und das Anfragebild mit der besten Gute, d.h. mit dem hochsten Score des Ergebnisses fur die visuelle Beschreibung ubernommen (BestesBild ). Das gewahlte Trainingsbild kann jedoch ein lokales Optimum darstellen und in der Suche auf der Bilddatenbank versagen. Weiterhin zeigt sich auch hier das Problem, dass keine Charakteristika von Objekten aus den ahnlichen Trainingsbildern gelernt werden. 3.7.4
Um eine kompakte Darstellung der visuellen Beschreibung zu erhalten, die die gemeinsamen Charakteristika des Objektes ausdruckt, kommen wir auf das Konzept der Durchschnitte zuruck. Wie in der zweiten visuellen Beschreibung beschrieben, bilden wir zunachst Durchschnitte der paarweisen Trainingsbilder pro jede Bildgruppe. Wir nehmen an, dass visuelle Worter und visuelle Phrasen, die in den meisten Durchschnitten auftreten, fur das Objekt relevanter sind, als die, die seltener vorkommen. Wir erstellen daher eine visuelle Beschreibung aus zwei Histogrammen, der visuellen Worter und der visuellen Phrasen, und zahlen fur jedes visuelle Wort und jede visuelle Phrase, in wievielen Durchschnitten es vorkommt. Diese absolute Durchschnitts-Frequenz bildet dann den Wert des jeweiligen visuellen Wortes oder der visuellen Phrase in den Histogrammen (DurchschnitteKompaktAnzahl ). 3.7.5
Um die Wichtigkeit jedes visuellen Wortes und jeder visuellen Phrase innerhalb eines Durchschnitts zu betonen, wird anstatt der Anzahl der Durchschnitte eine Summe der Durchschnitte gebildet. Genaugenommen werden wieder zwei Histogramme der visuellen Worter und visuellen Phrasen erstellt und jedes Bin des Histogramms ist die Summe der entsprechenden Bins der Histogramme aller Durchschnitte. (DurchschnitteKompakt-Summe) 3.7.6
Der nachsten visuellen Beschreibung liegt die folgende Frage zugrunde: gibt es visuelle Phrasen, die fur ein Objekt spezi sch sind, d.h. ist der Anteil der Bilder zu einem Term und einer visuellen Phrase an allen Bildern, die diese visuelle Phrase beinhalten, besonders hoch? Wir berechnen fur jede visuelle Phrase vp und dem zugrundeliegenden Term t des Eintrags das Gewicht: gV P (t; vp) := #B(t; vp) #B(vp) mit B(t; vp) stellt die Menge aller Trainingsbilder zu dem Term t, d.h. die Vereinigung der Bilder aus den Bildgruppen zu t, die die visuelle Phrase vp beinhalten, dar. Wir ubernehmen die zuvor de nierte visuelle Beschreibung DurchschnitteKompakt-Summe und gewichten den Hau gkeitswert jeder visuellen Phrase vp mit gV P (t; vp). (DurchschnitteKompaktGewichteteSumme) 3.7.7
Fur die folgende visuelle Beschreibung ubernehmen wir die Idee der tf-idf Gewichtung fur Dokumentvektoren. Mit Hilfe der inversen Dokumenthau gkeit eines Terms, hier inverse Bildhau gkeit eines visuellen Wortes oder einer visuellen Phrase, wollen wir die Hau gkeiten der visuellen Worter und visuellen Phrasen, die in sehr vielen Trainingsbildern vorkommen, schwacher, und die die seltener vorkommen, starker gewichten. Analog zum Text-Retrieval bilden wir also eine Summe aller Durchschnitte, wie in der visuellen Beschreibung DurchschnitteKompakt-Summe beschrieben, berechnen dann fur jedes visuelle Wort vw und jede visuelle Phrase vp das idf Gewicht: gIDF (vw) := log
#B #B(vw) (6) (7) wichten multipliziert: jedes Bin zu einem visuellem Wort vw mit gIDF (vw) und jedes Bin zu einer visuelle Phrase vp mit gIDF (vp). (DurchschnitteKompakt-TFIDF ) 3.7.8
Die Gewichte aus den beiden letzten visuellen Beschreibungen werden im Folgenden kombiniert. Wir erstellen wieder die Summe aller Durchschnitte und gewichten dann jeden Hau gkeitswert des jeweiligen visuellen Wortes vw mit gIDF (vw), und jeden Hau gkeitswert einer visuellen Phrase vp mit dem kombinierten Gewicht: gV P IDF (t; vp) := #B(t; vp) #B(vp) log
#B #B(vp) (8) (DurchschnitteKompakt-GewichtetesTFIDF ) 4. 4.1
Fur die Test- und Trainingsmenge werden Bilder und Annotationen zu 50 Objekten aus dem World Wide Web gesammelt. Fur jedes der 50 Terme werden jeweils 10 Trainingsbilder und ca. 30 Testbilder heruntergeladen. Als Objekte werden Tiere, Fruchte, Gegenstande, Gebaude und Symbole gewahlt. Fast alle Bilder liegen in einer Au osung von ca. 400 400 Pixel vor. 4.2
Die vorgestellten visuellen Beschreibungen werden hinsichtlich der Qualitat des Retrievals und der Anfragee zienz analysiert, um so aus den daraus gewonnenen Ergebnissen und Erkenntnissen die beste fur das visuelle Worterbuch auswahlen zu konnen. Dazu wird fur jede visuelle Beschreibung zuerst ein visuelles Worterbuch aus der Trainingsmenge gelernt und dieses dann in der Anwendung der Bildsuche eingelesen. Fur jeden Eintrag des visuellen Worterbuchs, also jeden Term (im jeweiligen Kontext), wird eine Anfrage auf der Testmenge durchgefuhrt, dabei die Anfragezeit gemessen und schlie lich aus dem erhaltenen Ranking-Ergebnis die Gute des Ergebnisses mit dem Ma Score, der im Folgenden erlautert wird, berechnet. Um die visuellen Beschreibungen letztlich miteinander vergleichen zu konnen, wird fur jede visuelle Beschreibung, also jedes Worterbuch, das arithmetische Mittel der Anfragezeiten und der Scores uber allen Eintragen gebildet. 4.3
In [
Als Testergebnis erhalten wir die zwei Diagramme in Abbildung 2. Das obere Diagramm stellt den durchschnittlichen Score und das untere die durchschnittliche Anfragezeit fur jede visuelle Beschreibung dar. Die besten durchschnittlichen Scores erreichen die visuellen Beschreibungen AlleBilder-BesterScore, Durchschnitte-BesterScore, die aus multiplen Instanzen und der Endergebnis-Strategie BesterScore bestehen. Dabei sieht man, dass die auf Durchschnitten basierende visuelle Beschreibung ein besseres RetrievalErgebnis liefert, die durchschnittliche Anfragezeit sich gleichzeitig aber verdoppelt. Wie bereits erwahnt ist diese Endergebnis-Strategie nur ein theoretisches Modell. Die zwei praktisch realisierbaren Endergebnis-Strategien verhalten sich je nach visueller Beschreibung unterschiedlich: MaxAhnlichkeit schneidet bei AlleBilder besser und bei Durchschnitte schlechter ab als DurchschnittsRank. Diese multipleInstanzen visuellen Beschreibungen mit den Strategien MaxAhnlichkeit und DurchschnittsRank werden jedoch von den eine-Instanz, auf Durchschnitten basierenden visuellen Beschreibungen bzgl. dem durchschnittlichen Score deutlich ubertro en. Von den besten multiple-Instanzen visuellen Beschreibung AlleBilder-MaxAhnlichkeit, Durchschnitte-DurchschnittsRank zu den besten eine-Instanz, DurchschnitteKompakt-GewichteteSumme und DurchschnitteKompakt-TFIDF haben wir einen Zuwachs des durchschnittlichen Scores von 0.07 und die Anfragezeit sinkt dabei drastisch um das 9bzw. 17-fache. Die eine-Instanz, auf Durchschnitten basierenden visuellen Beschreibungen weisen einen deutlich besseren, um ca. 0.12 hoheren, durchschnittlichen Score gegenuber BestesBild auf, sind untereinander mit Unterschieden von bis 0.02 aber relativ ahnlich. Die besten unter ihnen, DurchschnitteKompakt-GewichteteSumme und DurchschnitteKompakt-TFIDF liefern zudem den besten durchschnittlichen Score unter allen praktisch realisierbaren visuellen Beschreibungen. DurchschnitteKompakt-TFIDF maximiert den durchschnittlichen Score und minimiert gleichzeitig die Anfragezeit, ist daher am besten fur das visuelle Worterbuch geeignet.
Von den gestellten Anforderungen an das visuelle Worterbuch werden die Grundform der Terme mit dem StemmingSchritt in der Aufbereitungsphase und die Polysemie mit dem CBC Clustering, dem Kontextvektor und den damit verbundenen Mehreintragen eines Terms, realisiert. Mit der erwahnten besten visuellen Beschreibung ist das Erfassen der Charakteristika des Objektes mit dem Konzept der Durchschnitte, die Kompaktheit und E zienz mit der eineInstanz Darstellung und die Kompatibilitat zu der Bilddatenbank mit den Histogrammen der visuellen Worter und Phrasen erfullt. Zukunftig, um die Anfragezeiten der eineInstanz visuellen Beschreibungen von ca. 12 Sekunden weiter zu reduzieren, kann man geeignete e ziente Indexstrukturen und Algorithmen fur die Bildsuche untersuchen und einsetzen. Um die Qualitat des Retrievals weiter zu verbessern, konnte man versuchen auch Farbeigenschaften und ihre Relevanz fur Objekte miteinzubeziehen, d.h. diese fur die visuelle Beschreibung zu lernen und in der Bildsuche einzusetzen.
0,53 0,53 0,55 0,55 0,54 visuelle Beschreibung Abbildung 2: Durchschnittlicher Score und durchschnittliche Anfragezeit der visuellen Beschreibungen