Ein Verfahren zur automatischen Erstellung eines visuellen Wörterbuchs für die Bildsuche Magdalena Rischka Institut für Informatik Heinrich-Heine-Universität Düsseldorf D-40225 Düsseldorf, Deutschland rischka@cs.uni-duesseldorf.de ZUSAMMENFASSUNG sen diese unterschiedliche Schwächen auf, z.B. die Subjek- Das Internet bietet eine enorme Anzahl an Bildern. Bild- tivität des Beschreibenden, abstrakte Formulierungen oder suchmaschinen stehen vor der Herausforderung Bilder effek- falsche Stichwortzuordnungen, sowie Unvollständigkeit der tiv und effizient zu erschließen. Die klassischen Arten der Beschreibung. Aufgrund dieses Nachteils versucht man heut- Bildsuche, die stichwort- und die inhaltsbasierte Bildsuche, zutage, fern von den Annotationen, auf das Bild selbst einzu- haben Nachteile. Ein Retrieval-Modell, welches die Vorteile gehen und somit den Inhalt des Bildes zu erschließen. Die in- beider Sucharten integriert und die Nachteile ausschließt, haltsbasierte Bildsuche basiert demnach auf visuellen Eigen- ist die auf einem visuellen Wörterbuch basierende Bildsuche. schaften des Bildes, z.B. bzgl. der Farbe, der Textur, Form Ein visuelles Wörterbuch ist dabei eine Menge von Stichwort- usw. Eine Anfrage wird mittels einem Beispielbild gestellt, zu-visueller-Beschreibung Beziehungen. Wir präsentieren ein das Retrieval-System sucht dann nach Bildern, die dem An- Verfahren zur automatischen Erstellung eines visuellen Wör- fragebild ähnlich sind, bezogen auf den, dem System zu- terbuchs aus einer Trainingsmenge von annotierten Bildern. grundeliegenden Deskriptor und das Ähnlichkeitsmaß. Der Dabei werden verschiedene Modelle von visuellen Beschrei- Nachteil dieser Suchart betrifft die Anfrageformulierung mit- bungen untersucht und anschließend evaluiert. Wir zeigen, tels dem Anfragebild - ein Anfragebild liegt dem Benutzer dass eine kompakte visuelle Beschreibung existiert, die ver- in der Regel nicht vor, dieses wird schließlich gesucht. Ge- glichen mit multiple-Instanzen visuellen Beschreibungen bes- wünscht ist daher ein Retrieval-System, welches die Vorteile sere Retrieval-Ergebnisse liefert und gleichzeitig die Anfra- beider Sucharten integriert, d.h. eine textuelle Anfragefor- gezeit drastisch senkt. mulierung mit einer inhaltsbasierten Bildsuche kombiniert. Eine Lösung ist das Modell des visuellen Wörterbuchs als eine Menge von Stichwort-zu-visueller-Beschreibung Bezieh- Schlüsselwörter ungen. Bei der Bildsuche auf der Basis des visuellen Wör- image search, visual dictionary, visual words, visual phrases terbuchs wird nun eine Anfrage textuell gestellt, dann die Stichwörter aus der Anfrage in dem visuellen Wörterbuch 1. EINLEITUNG nachgeschlagen und deren Übersetzung, d.h. eine visuelle Beschreibung des Stichwortes, für die anschließende inhalts- Das heutige World Wide Web stellt einen großen und stän- basierte Bildsuche verwendet. Die Entwicklung eines Ver- dig wachsenden Datenbestand von Bildern dar und bildet fahrens zur automatischen Erstellung eines visuellen Wör- somit eine gute Basis für die Suche nach gewünschten Bil- terbuchs ist Gegenstand dieses Papers. Wir geben zunächst dern. Es gibt zwei klassische Arten der Bildsuche: die stich- einen Überblick über verwandte Arbeiten, beschreiben dann wortbasierte und die inhaltsbasierte Bildsuche. Die stich- das entwickelte Verfahren, evaluieren visuelle Beschreibun- wortbasierte Bildsuche basiert auf Annotationen und Meta- gen und schließen mit einer Schlussfolgerung und einem Aus- daten der Bilder. Die Anfrageformulierung erfolgt textuell, blick. somit schnell und unkompliziert. Bei der Verarbeitung der Anfrage sucht das System nach Bildern, die, grob gesagt, die Stichwörter aus der Anfrage beinhalten. Einen Nachteil hat 2. VERWANDTE ARBEITEN diese Suchart jedoch: der Erfolg der Suche hängt von der In der Literatur existieren zwei weitverbreitete Definitio- Qualität der Annotationen und Metadaten der Bilder ab. nen des Begriffs visuelles Wörterbuch. Die erste Definition Je nachdem, ob Bilder manuell vom Benutzer oder auto- beschreibt das Konzept der Zuordnungen von Stichwort zu matisch mit Hilfe eines Algorithmus annotiert wurden, wei- visueller Beschreibung, die zweite betrifft die Quantisierung des Deskriptor-Raums in Partitionen, sogenannte visuelle Wörter. Jeder Deskriptor wird dann mit seinem zugehörigen visuellen Wort repräsentiert. Alle Partitionen bilden das vi- suelle Wörterbuch. Oft werden beide Konzepte kombiniert [1, 4]. [1] verwendet eine gut vorbereitete Trainingsmenge, SCD und HTD (MPEG-7 Standard) Deskriptoren und be- schreibt ein Stichwort mit einer konstanten Anzahl von vi- 23rd GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 31.05.2011 - 03.06.2011, Obergurgl, Austria. suellen Wörtern. [4] entwickelt ein visuelles Wörterbuch auf Copyright is held by the author/owner(s). der Grundlage von SIFT-Deskriptoren und daraus abgelei- 103 Trainingsmenge teten visuellen Wörtern und stellt jedes Stichwort mit einer Gaußschen Mischverteilung dar. Das Konzept der visuellen Annotierte Bilder Wörter wird mit der Idee der visuellen Phrase als ein Paar adjazenter visueller Wörter erweitert. Basierend auf SIFT Annotationen Bilder wird in [6] das Modell der visuellen Phrase untersucht und Repräsentation Repräsentation dabei die Verbesserung des Retrievals nachgewiesen. Wir & Ähnlichkeitsmaß & Ähnlichkeitsmaß verwenden den Begriff des visuellen Wörterbuchs um die erste Definition auszudrücken. Falls das Konzept der zwei- Gruppierung Gruppierung ten Definition und ihre Erweiterung gemeint ist, sprechen wir von visuellen Wörtern und visuellen Phrasen. Wahl des visuellen Wörterbuchs Vokabulars 3. DAS VERFAHREN ZUR ERSTELLUNG Erstellung des EINES VISUELLEN WÖRTERBUCHS Abgleich der Gruppierungen In diesem Kapitel präsentieren wir das entwickelte Ver- fahren zur automatischen Erstellung eines visuellen Wör- Visuelle Beschreibung terbuchs aus einer Trainingsmenge von annotierten Bildern. Das Verfahren basiert auf der Idee, die Trainingsbilder ein- mal bzgl. der Ähnlichkeit ihrer Annotationen und einmal Visuelles Wörterbuch bzgl. ihrer visuellen Ähnlichkeit zu gruppieren, dann die Term Visuelle Beschreibung Trainingsbilder, die bzgl. der beiden Aspekte zueinander ... ... ... ... ähnlich sind, d.h. bzgl. beider Aspekte zusammen gruppiert wurden, aufzusuchen und aus diesen schließlich Korrelatio- nen zwischen Stichwörtern und visuellen Bildmerkmalen ab- Abbildung 1: Das konzeptuelle Modell des Verfah- zuleiten. rens 3.1 Anforderungen an das visuelle Wörterbuch len Bildmerkmale ähnlich sind. Es findet also ein Abgleich der Gruppierungen statt. Aus den ermittelten Trainingsbil- Das visuelle Wörterbuch kann man sich wie ein herkömm- dern eines Terms wird schließlich die visuelle Beschreibung liches Wörterbuch vorstellen, welches aus einer Menge von des Terms gelernt und zusammen mit dem Term als ein Ein- Einträgen besteht. In dem visuellen Wörterbuch sollen Ob- trag in dem visuellen Wörterbuch abgespeichert. Wir er- jekte und visuelle Zusammenhänge, wie z.B. Tiere, Gegen- halten das visuelle Wörterbuch aus Stichwort-zu-visueller- stände, Gebäude, Logos, Symbole, etc. verwaltet werden. Je- Beschreibung Einträgen. der Eintrag ist ein Paar aus einem Stichwort, der das Objekt benennt und einer dazugehörigen visuellen Beschreibung des Objektes. Stichwörter sollen in der Grundform vorliegen - 3.3 Repräsentation und Ähnlichkeitsmaß wir sprechen dann von Termen -, und es soll die Polysemie von/ für Annotationen und Bilder der Terme unterstützt werden. Eine visuelle Beschreibung Für einen semantischen Vergleich müssen Annotationen stellt eine Einheit dar, die für die inhaltsbasierte Bildsuche und Bilder in eine interne Darstellung überführt werden. verwendet wird. Diese soll nur die für dieses Objekt relevan- Wir bereiten auf und bereinigen zuerst die Annotationen, ten visuellen Charakteristika erfassen, die allen Perspektiven erstellen dann einen Index mit dem Indexvokabular und lei- und Erscheinungsformen des Objektes gemeinsam sind. Zu- ten daraus für jede Annotation einen Annotationsvektor ge- dem soll diese aus Effizienzgründen kompakt, sowie zu der mäß der tf-idf Gewichtung. Als Ähnlichkeitsmaß wählen wir Repräsentation der Bilder kompatibel sein. das Kosinusmaß. Als Grundlage für die Repräsentation von Bildern wäh- 3.2 Das konzeptuelle Modell des Verfahrens len wir Scale Invariant Feature Transform (SIFT)[2], da es Das konzeptuelle Modell des Verfahrens ist in Abbildung 1 in der Literatur als eins der robustesten Features gilt. Ei- dargestellt. Grundlage zum Erlernen des visuellen Wörter- ne auf rohen SIFT-Features basierende Bilddarstellung ist buchs bildet die Trainingsmenge von annotierten Bildern, schwer zu handhaben und aus Gründen der Effizienz unge- die beliebig und ohne zusätzliche Vorbearbeitung gewählt eignet. Um alle Bilder einheitlich zu repräsentieren wenden werden kann. Ausgehend von dieser werden zunächst einmal wir daher die Technik der visuellen Wörter an. Mit dem zwei Ziele verfolgt: die Gruppierung von ähnlichen Bildern Clusteringalgorithmus K-Means basierend auf der Euklidi- auf der Basis der semantischen Ähnlichkeit ihrer Annotatio- schen Distanz wird der 128-dimensionale Deskriptor-Raum nen und die Gruppierung von ähnlichen Bildern bezüglich der SIFT-Keypoints in 1000 Partitionen, die visuellen Wör- ihrer visuellen Ähnlichkeit. Dazu werden die Annotationen ter, zerlegt. Jedem Deskriptor wird gemäß dem Nächsten- sowie die Bilder unabhängig voneinander in eine interne Re- Nachbar-Prinzip das entsprechende visuelle Wort zugeord- präsentation überführt und auf der Basis eines definierten net. Ein Bild wird schließlich mit einem Histogramm der Ähnlichkeitsmaßes gruppiert. Aus den beiden Gruppierun- visuellen Wörter dargestellt, indem das i-te Bin die Vor- gen wird dann das visuelle Wörterbuch erstellt. Dazu wird kommenshäufigkeit des i-ten visuellen Wortes in dem Bild zunächst einmal das Vokabular für das visuelle Wörterbuch misst. Weiterhin verwenden wir auch das Konzept der vi- bestimmt. Für jeden Term des Vokabulars werden Trainings- suellen Phrase für die Bilddarstellung. Eine visuelle Phrase bilder ermittelt, die diesen Term in der Annotation enthalten vpij ist ein nichtgeordnetes Paar (Menge) von zwei visuel- und bzgl. der Ähnlichkeit von Annotationen und der visuel- len Wörtern vwi , vwj . Für die Eigenschaft der räumlichen 104 Nähe übernehmen wir die in [5] definierte Bedingung. In ei- relevanten Objektes nicht mehr gruppiert werden. Am bes- nem Bild liegt eine visuelle Phrase vpij vor, falls in dem ten wäre, man hätte visuelle Beschreibungen von den, in der Bild zwei Keypoints kpa , kpb existieren und für diese fol- Trainingsmenge enthaltenen Objekten und würde diese als gendes gilt: das visuelle Wort von kpa ist vwi und von kpb Clusterzentren nehmen, um die Trainingsbilder anhand die- ist vwj und die Euklidische Distanz distanz zwischen den ser Clusterzentren überlappend zu gruppieren. Die visuellen (x, y) Positionen der Keypoints erfüllt die Bedingung: Beschreibungen sind aber genau das was wir suchen. Hät- ten wir solche Beschreibungen, dann wäre die Gruppierung distanz(kpa , kpb ) < sa · λ oder (1) hier überflüssig. Man kann trotzdem versuchen solche visu- distanz(kpa , kpb ) < sb · λ ellen Beschreibungen zu simulieren, indem man das was den wobei sa und sb die Skalierung der Keypoints und λ ein Trainingsbildern gemeinsam ist, extrahiert. Sind zwei Bilder Parameter ist, welcher das Auftreten der visuellen Wörter bzgl. einem Objekt ähnlich und teilen damit die Charakteris- Paare kontrolliert. Den experimentellen Ergebnissen aus [5] tika des Objektes, dann müssen die gemeinsamen Charakte- folgend setzen wir λ = 4. Analog zu visuellen Wörtern erstel- ristika auch in der kompakten Bilddarstellung der visuellen len wir auch für visuelle Phrasen ein Histogramm, welches Wörter und der visuellen Phrasen verankert sein, nämlich das Vorkommen der 500.500 visuellen Phrasen in einem Bild als Durchschnitt der visuellen Wörter und visuellen Phra- zählt. In [6] wurde gezeigt, dass Retrieval-Systeme, die auf sen Histogramme der beteiligten Bilder. Der Durchschnitt beiden Bilddarstellungen, der visuellen Wörter und der vi- ds zweier Bilder bi , bj ist wie folgt definiert: suellen Phrasen, basieren, die besten Ergebnisse liefern. Wir   ds(bi , bj ) = dsV W (bi , bj ), dsV P (bi , bj ) mit (5) folgen dieser Erkenntnis und repräsentieren jedes Trainings- bild mit zwei Histogrammen, der visuellen Wörter und der dsX (bi , bj ) = (m(1), ..., m(k)) und visuellen Phrasen:   m(l) = min(aHistX X i [l], aHistj [l]) b = aHistV W , aHistV P (2) wobei bei X = V W ist k = 1000 und X = V P ist k = Für die Bestimmung der Ähnlichkeit zweier Bilder ver- 500.500. Für die Gruppierung der Trainingsbilder berech- wenden wir ein Ähnlichkeitsmaß, das auf dem Histogramm- nen wir die Durchschnitte der ähnlichsten Bilder, betrach- schnitt hs zweier Histogramme basiert: ten diese als Pseudo-Objekte und damit als Centroide, und clustern die Trainingsbilder gemäß einem Schwellwert über- k X lappend an diese Durchschnitte. Wir erhalten eine Menge hs(nHistX X i , nHistj ) = min(nHistX X i [l], nHistj [l]) (3) von Gruppen visuell ähnlicher Bilder Gvisuell | 1 ≤ l ≤ n} . l l=1 X wobei nHist die normalisierte Version des absoluten Hi- 3.5 Wahl des visuellen Wörterbuch stogramms aHistX darstellt. Die Ähnlichkeit zweier Bilder Vokabulars bi und bj ergibt sich dann mit: Als nächstes müssen wir klären, welche Stichwörter in das visuelle Wörterbuch aufgenommen werden. Als Stichwörter ähnlichkeit(bi , bj ) = (1 − α) · hs(nHistVi W , nHistVj W ) (4) kommen natürlich nur Terme aus dem Indexvokabular in + α · hs(nHistVi P , nHistVj P ) Frage. Die Übernahme aller Terme als Stichwörter ist je- doch nicht sinnvoll, denn nicht alle Terme bzw. die den Ter- Für den Wert des Gewichts α orientieren wir uns an dem Pa- men zugrundeliegenden Wörter beschreiben Objekte oder per [6], in welchem der Einfluß unterschiedlicher Gewichts- beinhalten einen visuellen Aspekt. Wir betrachten daher die werte auf die Retrieval-Resultate untersucht wird. Es zeigt Gruppen, die wir durch das Clustering von Annotationen sich, dass das Optimum bei dem Wert α = 0.75 liegt. erhalten haben. Wir nehmen an, dass innerhalb einer Anno- 3.4 Gruppierung von Annotationen tationsgruppe die Terme, die in den meisten Annotationen vorkommen, etwas mit dem visuellen Inhalt der zugehörigen und von Bildern Bilder zu tun haben müssen. Für jede Annotationsgruppe Für die Gruppierung der Annotationen wenden wir den werden daher diese hochfrequenten Terme bestimmt. Dazu in [3] vorgeschlagenen Clusteringalgorithmus Clustering by wird zunächst der Term mit der höchsten Annotationshäu- Committee (CBC) an. figkeit ermittelt und dann noch weitere, deren Annotations- Die Gruppierung von ähnlichen Bildern bedeutet, Bilder, häufigkeit größer ist als 0.7 mal die maximale Häufigkeit. die dasselbe Objekt beinhalten, in eine Gruppe zu fassen. Die Vereinigung der so erhaltenen Terme bildet dann das Da wir von nicht vorbearbeiteten Trainingsbildern ausgehen, Vokabular des visuellen Wörterbuchs, also im Grunde die liegen diese Bilder also in der Regel etwas verschmutzt“ vor, Einträge. Um die Forderung nach der Unterstützung der ” d.h. sie beinhalten neben dem Hauptobjekt ggf. noch andere Polysemie von Termen zu realisieren, werden die betroffe- irrelevante Objekte oder einen Hintergrund. Dadurch kann nen Terme mehrmals, nur mit unterschiedlichem Kontext, es leicht zu dem Problem kommen, dass zwei Bilder, die wir in dem visuellen Wörterbuch aufgeführt. Der jeweilige Kon- intuitiv nicht gruppiert hätten, weil diese unterschiedliche text eines Terms ergibt sich aus der Gruppe, genauer aus Hauptobjekte haben, trotzdem einen höheren Ähnlichkeits- den anderen Termen der Gruppe, zu der der Term gehört. wert haben, als zwei Bilder, die dem menschlichen Empfin- Als Kontext wird der Centroid der Gruppe verwendet. Wir den nach ähnlich sind. Bei der Wahl eines Gruppierungsver- erhalten somit eine Seite des visuellen Wörterbuchs, näm- fahrens müssen wir diese Problematik einbeziehen. Cluster- lich eine Menge von Einträgen, die jeweils ein Objekt reprä- ingverfahren, die die Trainingsbilder in Partitionen zerlegen, sentieren und aus einem Term und seinem Kontextvektor sind nicht geeignet, es könnte nämlich passieren, dass Bil- bestehen. der aufgrund für uns falsch erscheinenden Gemeinsamkeiten, wie dem Hintergrund, zusammengefasst und dann bzgl. des 105 3.6 Abgleich der Gruppierungen bild der visuellen Beschreibung, also in jedem der einzelnen Für jeden Eintrag des visuellen Wörterbuchs muss nun Ergebnisse, eine Rankingposition und einen Ähnlichkeits- eine Menge von Trainingsbildern bestimmt werden, aus der wert zum Anfragebild. Bei der zweiten Strategie wird für je- die visuelle Beschreibung des Terms gelernt werden soll. Das des Bild aus der Bilddatenbank der maximale Ähnlichkeits- bedeutet, es müssen die Bilder bestimmt werden, die sowohl wert aus seinen Ähnlichkeitswerten zu allen Anfragebildern bzgl. des Terms als auch visuell bzgl. des beinhaltenden Ob- ausgewählt, die Bilder dann entsprechend ihrem maximalen jekts ähnlich sind. Dazu werden Bilder, die diesen Term in Ähnlichkeitswert sortiert und als Endergebnis ausgegeben der Annotation enthalten, aus der Annotationsgruppe des (AlleBilder-MaxÄhnlichkeit). Terms genommen und es wird daraus eine Gruppe Geintrag Eine dritte Lösung zur Bestimmung des Endergebnisses gebildet. Diese Gruppe wird dann mit jeder Gruppe Gvisuell l ist, für jedes Bild aus der Bilddatenbank das arithmetische visuell ähnlicher Bilder abgeglichen. Beim Abgleich wird der Mittel ihrer Rankingpositionen aus den einzelnen Ranking- Mengendurchschnitt jeweils zweier Gruppen gebildet, indem Ergebnissen zu berechnen, dann die Bilder bezüglich diesem die Bilder übernommen werden, die in der Gruppe Geintrag arithmetischen Mittel aufsteigend zu sortieren und dieses und in der Gruppe Gvisuell l vorkommen. Der resultierende Ranking als Endergebnis auszugeben. Mengendurchschnitt zweier Gruppen muss mindestens zwei (AlleBilder-DurchschnittsRank ) Bilder beinhalten, sonst können keine gemeinsamen Charak- teristika gelernt werden. Als Resultat des Abgleichs erhalten 3.7.2 Durchschnitte wir wiederum, ggf. überlappende, Gruppen von Bildern. Die Bei der letzten visuellen Beschreibung werden nicht wirk- Bilder innerhalb einer solchen Gruppe sind nun visuell als lich Charakteristika des Objektes gelernt, diese stellt also auch bzgl. des Terms und seinem Kontext ähnlich. Jeder Ein- keine visuelle Beschreibung in unserem gewünschten Sinne trag des visuellen Wörterbuchs besteht nun aus einem Term, dar. Wir gehen davon aus, dass die Ähnlichkeit zweier ähn- seinem Kontextvektor und der Menge der Bildgruppen aus licher Bilder auf einer gemeinsamen Teilmenge der visuel- welcher eine visuelle Beschreibung im nächsten Schritt her- len Wörter und visuellen Phrasen basiert. Wir extrahieren geleitet wird. daher die Gemeinsamkeiten zweier ähnlicher Bilder, indem wir den Durchschnitt ihrer Histogramme gemäß der Formel 3.7 Visuelle Beschreibungen 5 bilden. Für jede Bildgruppe aus der Menge der Bildgrup- Als nächstes muss die rechte Seite des visuellen Wörter- pen werden paarweise Durchschnitte der Trainingsbilder aus buchs, die Seite der visuellen Beschreibungen, bestimmt wer- der Bildgruppe berechnet. Die visuelle Beschreibung besteht den. Wir betrachten einen Eintrag, also einen Term, des vi- dann aus allen gebildeten Durchschnitten, d.h. jeder Durch- suellen Wörterbuchs und die ihm zugehörige, im letzten Ab- schnitt dient bei der inhaltsbasierten Bildsuche als ein An- schnitt bestimmte Menge von Bildgruppen. Es gibt mehrere fragebild und es finden mehrere Anfragen statt. Möglichkeiten aus der Menge der Bildgruppen eine visuel- Wie bei der ersten visuellen Beschreibung, erhalten wir le Beschreibung abzuleiten. Im Folgenden stellen wir einige auch hier eine Menge von einzelnen Ergebnissen und müssen Arten von visuellen Beschreibungen in der Reihenfolge der diese zu einem Endergebnis berechnen. Wir wenden dazu die eigenen Entwicklung und Untersuchung vor. drei beschriebenen Strategien an (Durchschnitte-BesterScore, Durchschnitte-MaxÄhnlichkeit, Durchschnitte-Durchschnitts- 3.7.1 Alle Bilder Rank ). Die erste und einfachste Methode eine visuelle Beschrei- bung anzugeben ist, die Bildgruppen zu vereinigen und die 3.7.3 Bestes Bild so erhaltene Menge an Trainingsbildern als Repräsentation Die bisher vorgestellten visuellen Beschreibungen sind pro- des Terms zu verwenden. Bei der Bildsuche zu diesem Term blematisch: sie bestehen aus mehreren Anfrageinstanzen und finden dann mehrere inhaltsbasierte Bildsuchen statt, indem weisen daher eine zeitaufwändige Anfrageverarbeitung auf. jedes dieser Trainingsbilder als Anfragebild verwendet wird. Eine kompakte Darstellung der visuellen Beschreibung, d.h. Bei dieser multiple-Instanzen visuellen Beschreibung erhal- eine Darstellung, die aus nur einer Anfrageinstanz besteht, ten wir jedoch zunächst für jedes Anfragebild ein Ranking wäre von Vorteil. Eine einfache Lösung wiederum ist, das von Bildern als Ergebnis. Es stellt sich also die Frage, wie beste Trainingsbild aus den Trainingsbildern eines Eintrags das Endergebnis aus den Ergebnissen der einzelnen Anfragen als visuelle Beschreibung zu wählen. Um das beste Trai- berechnet werden soll. Für die Angabe des Endergebnisses ningsbild zu bestimmen, vereinigen wir die Bildgruppen und werden drei Strategien untersucht. stellen mit jedem Bild aus der Vereinigung eine Anfrage an Bei der ersten Strategie wird das beste Resultat als End- die ganze Trainingsmenge. Mit einem Qualitätsmaß wird je- ergebnis ausgegeben. Dazu wird die Güte der einzelnen Er- des Anfrageergebnis bewertet und das Anfragebild mit der gebnisse mittels einem Qualitätsmaß berechnet. Eine sol- besten Güte, d.h. mit dem höchsten Score des Ergebnisses che Berechnung erfordert allerdings zu wissen, welche Bil- für die visuelle Beschreibung übernommen (BestesBild ). Das der des Ergebnisrankings für den Anfrageterm relevant und gewählte Trainingsbild kann jedoch ein lokales Optimum welche irrelevant sind. Dafür müssten die Bilder in der Bild- darstellen und in der Suche auf der Bilddatenbank versa- datenbank kategorisiert oder mit Termen versehen sein. Von gen. Weiterhin zeigt sich auch hier das Problem, dass keine diesem Fall kann man in der Realität jedoch nicht ausge- Charakteristika von Objekten aus den ähnlichen Trainings- hen. Diese Strategie ist auf einer Bilddatenbank also prak- bildern gelernt werden. tisch nicht anwendbar, lediglich auf einer vorbereiteten Test- menge. Aus Gründen des Performance Vergleichs wird diese 3.7.4 Durchschnitte kompakt - Anzahl trotzdem aufgeführt und untersucht. Um eine kompakte Darstellung der visuellen Beschreibung (AlleBilder-BesterScore) zu erhalten, die die gemeinsamen Charakteristika des Ob- Jedes Bild aus der Bilddatenbank hat für jedes Anfrage- jektes ausdrückt, kommen wir auf das Konzept der Durch- 106 schnitte zurück. Wie in der zweiten visuellen Beschreibung wichten multipliziert: jedes Bin zu einem visuellem Wort vw beschrieben, bilden wir zunächst Durchschnitte der paar- mit g IDF (vw) und jedes Bin zu einer visuelle Phrase vp mit weisen Trainingsbilder pro jede Bildgruppe. Wir nehmen an, g IDF (vp). (DurchschnitteKompakt-TFIDF ) dass visuelle Wörter und visuelle Phrasen, die in den meisten Durchschnitten auftreten, für das Objekt relevanter sind, als 3.7.8 Durchschnitte kompakt - Gewichtetes TFIDF die, die seltener vorkommen. Wir erstellen daher eine visuel- Die Gewichte aus den beiden letzten visuellen Beschrei- le Beschreibung aus zwei Histogrammen, der visuellen Wör- bungen werden im Folgenden kombiniert. Wir erstellen wie- ter und der visuellen Phrasen, und zählen für jedes visuelle der die Summe aller Durchschnitte und gewichten dann je- Wort und jede visuelle Phrase, in wievielen Durchschnitten den Häufigkeitswert des jeweiligen visuellen Wortes vw mit es vorkommt. Diese absolute Durchschnitts-Frequenz bildet g IDF (vw), und jeden Häufigkeitswert einer visuellen Phrase dann den Wert des jeweiligen visuellen Wortes oder der visu- vp mit dem kombinierten Gewicht: ellen Phrase in den Histogrammen (DurchschnitteKompakt- #B(t, vp) #B Anzahl ). g V P −IDF (t, vp) := · log (8) #B(vp) #B(vp) 3.7.5 Durchschnitte kompakt - Summe (DurchschnitteKompakt-GewichtetesTFIDF ) Um die Wichtigkeit jedes visuellen Wortes und jeder vi- suellen Phrase innerhalb eines Durchschnitts zu betonen, 4. EVALUATION wird anstatt der Anzahl der Durchschnitte eine Summe der Durchschnitte gebildet. Genaugenommen werden wieder zwei 4.1 Trainings- und Testmenge Histogramme der visuellen Wörter und visuellen Phrasen erstellt und jedes Bin des Histogramms ist die Summe der Für die Test- und Trainingsmenge werden Bilder und An- entsprechenden Bins der Histogramme aller Durchschnitte. notationen zu 50 Objekten aus dem World Wide Web gesam- (DurchschnitteKompakt-Summe) melt. Für jedes der 50 Terme werden jeweils 10 Trainings- bilder und ca. 30 Testbilder heruntergeladen. Als Objekte 3.7.6 Durchschnitte kompakt - Gewichtete Summe werden Tiere, Früchte, Gegenstände, Gebäude und Symbole Der nächsten visuellen Beschreibung liegt die folgende Fra- gewählt. Fast alle Bilder liegen in einer Auflösung von ca. ge zugrunde: gibt es visuelle Phrasen, die für ein Objekt 400×400 Pixel vor. spezifisch sind, d.h. ist der Anteil der Bilder zu einem Term 4.2 Testdurchführung und einer visuellen Phrase an allen Bildern, die diese visuelle Phrase beinhalten, besonders hoch? Wir berechnen für jede Die vorgestellten visuellen Beschreibungen werden hin- visuelle Phrase vp und dem zugrundeliegenden Term t des sichtlich der Qualität des Retrievals und der Anfrageeffizi- Eintrags das Gewicht: enz analysiert, um so aus den daraus gewonnenen Ergebnis- sen und Erkenntnissen die beste für das visuelle Wörterbuch #B(t, vp) auswählen zu können. Dazu wird für jede visuelle Beschrei- g V P (t, vp) := (6) #B(vp) bung zuerst ein visuelles Wörterbuch aus der Trainingsmen- ge gelernt und dieses dann in der Anwendung der Bildsuche mit B(t, vp) stellt die Menge aller Trainingsbilder zu dem eingelesen. Für jeden Eintrag des visuellen Wörterbuchs, al- Term t, d.h. die Vereinigung der Bilder aus den Bildgruppen so jeden Term (im jeweiligen Kontext), wird eine Anfrage auf zu t, die die visuelle Phrase vp beinhalten, dar. Wir überneh- der Testmenge durchgeführt, dabei die Anfragezeit gemes- men die zuvor definierte visuelle Beschreibung Durchschnitte- sen und schließlich aus dem erhaltenen Ranking-Ergebnis die Kompakt-Summe und gewichten den Häufigkeitswert jeder Güte des Ergebnisses mit dem Maß Score, der im Folgenden visuellen Phrase vp mit g V P (t, vp). (DurchschnitteKompakt- erläutert wird, berechnet. Um die visuellen Beschreibungen GewichteteSumme) letztlich miteinander vergleichen zu können, wird für jede 3.7.7 Durchschnitte kompakt - TFIDF visuelle Beschreibung, also jedes Wörterbuch, das arithme- tische Mittel der Anfragezeiten und der Scores über allen Für die folgende visuelle Beschreibung übernehmen wir Einträgen gebildet. die Idee der tf-idf Gewichtung für Dokumentvektoren. Mit Hilfe der inversen Dokumenthäufigkeit eines Terms, hier in- 4.3 Bewertungsmaß verse Bildhäufigkeit eines visuellen Wortes oder einer visu- In [6] wird für die Evaluation des Retrieval-Systems ein ellen Phrase, wollen wir die Häufigkeiten der visuellen Wör- Maß Score benutzt. Score bewertet die Top-20 zurückgege- ter und visuellen Phrasen, die in sehr vielen Trainingsbil- benen Bilder, indem jedes relevante Bild entsprechend des dern vorkommen, schwächer, und die die seltener vorkom- Intervalls, in dem seine Rankingposition liegt, gewichtet wird, men, stärker gewichten. Analog zum Text-Retrieval bilden die Gewichte aller relevanten Bilder summiert und schließ- wir also eine Summe aller Durchschnitte, wie in der visu- lich auf den Bereich [0, 1] normalisiert werden. Die Auto- ellen Beschreibung DurchschnitteKompakt-Summe beschrie- ren des Papers begründen, dass die meisten Benutzer nur ben, berechnen dann für jedes visuelle Wort vw und jede die ersten beiden Ergebnisseiten, mit jeweils 10 Bildern pro visuelle Phrase vp das idf Gewicht: Seite, betrachten und daher nur die Top-20 der zurückge- #B gebenen Bilder zu einer Anfrage die relevantesten für den g IDF (vw) := log (7) Benutzer sind. Wir stimmen mit der Argumentation über- #B(vw) ein und übernehmen dieses Maß für die Qualitätsbewertung wobei B ist die Menge aller Trainingsbilder und B(vw) die der visuellen Beschreibungen. Menge der Trainingsbilder, die das visuelle Wort vw bein- halten. Analog für vp. Die aus der Summe der Durchschnit- te entstandenen Histogramme werden dann mit diesen Ge- 107 4.4 Testergebnisse 0,70 0,60 0,59 0,57 Als Testergebnis erhalten wir die zwei Diagramme in Ab- 0,55 0,55 durchschnittlicher Score 0,53 0,54 0,53 bildung 2. Das obere Diagramm stellt den durchschnittli- 0,50 0,48 0,47 0,42 chen Score und das untere die durchschnittliche Anfrage- 0,40 0,36 0,38 zeit für jede visuelle Beschreibung dar. Die besten durch- 0,30 schnittlichen Scores erreichen die visuellen Beschreibungen 0,20 AlleBilder-BesterScore, Durchschnitte-BesterScore, die aus 0,10 multiplen Instanzen und der Endergebnis-Strategie Bester- 0,00 Score bestehen. Dabei sieht man, dass die auf Durchschnit- visuelle Beschreibung ten basierende visuelle Beschreibung ein besseres Retrieval- 250,0 Ergebnis liefert, die durchschnittliche Anfragezeit sich gleich- durchschnittliche Zeit (Sek) 200,0 191,4 191,4 191,4 zeitig aber verdoppelt. Wie bereits erwähnt ist diese End- ergebnis-Strategie nur ein theoretisches Modell. Die zwei 150,0 praktisch realisierbaren Endergebnis-Strategien verhalten 101,0 101,0 101,0 sich je nach visueller Beschreibung unterschiedlich: Max- 100,0 Ähnlichkeit schneidet bei AlleBilder besser und bei Durch- 50,0 schnitte schlechter ab als DurchschnittsRank. Diese multiple- 9,0 8,3 8,3 11,8 8,2 11,7 Instanzen visuellen Beschreibungen mit den Strategien Ma- 0,0 visuelle Beschreibung xÄhnlichkeit und DurchschnittsRank werden jedoch von den AlleBilder-BesterScore eine-Instanz, auf Durchschnitten basierenden visuellen Be- AlleBilder-MaxÄhnlichkeit AlleBilder-DurchschnittsRank schreibungen bzgl. dem durchschnittlichen Score deutlich Durchschnitte-BesterScore übertroffen. Von den besten multiple-Instanzen visuellen Be- Durchschnitte-MaxÄhnlichkeit Durchschnitte-DurchschnittsRank schreibung AlleBilder-MaxÄhnlichkeit, Durchschnitte-Durch- BestesBild schnittsRank zu den besten eine-Instanz, DurchschnitteKom- DurchschnitteKompakt-Anzahl DurchschnitteKompakt-Summe pakt-GewichteteSumme und DurchschnitteKompakt-TFIDF DurchschnitteKompakt-GewichteteSumme haben wir einen Zuwachs des durchschnittlichen Scores von DurchschnitteKompakt-TFIDF DurchschnitteKompakt-GewichtetesTFIDF 0.07 und die Anfragezeit sinkt dabei drastisch um das 9- bzw. 17-fache. Die eine-Instanz, auf Durchschnitten basie- renden visuellen Beschreibungen weisen einen deutlich bes- Abbildung 2: Durchschnittlicher Score und durch- seren, um ca. 0.12 höheren, durchschnittlichen Score gegen- schnittliche Anfragezeit der visuellen Beschreibun- über BestesBild auf, sind untereinander mit Unterschieden gen von bis 0.02 aber relativ ähnlich. Die besten unter ihnen, DurchschnitteKompakt-GewichteteSumme und Durchschnit- teKompakt-TFIDF liefern zudem den besten durchschnitt- 6. LITERATUR lichen Score unter allen praktisch realisierbaren visuellen [1] C. Hentschel, S. Stober, A. Nürnberger, and Beschreibungen. DurchschnitteKompakt-TFIDF maximiert M. Detyniecki. Adaptive multimedial retrieval: den durchschnittlichen Score und minimiert gleichzeitig die Retrieval, user, and semantics. chapter Automatic Anfragezeit, ist daher am besten für das visuelle Wörterbuch Image Annotation Using a Visual Dictionary Based on geeignet. Reliable Image Segmentation, pages 45–56. Springer-Verlag, Berlin, Heidelberg, 2008. 5. SCHLUSSFOLGERUNG UND [2] D. G. Lowe. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision, AUSBLICK 60:91–110, November 2004. Von den gestellten Anforderungen an das visuelle Wörter- [3] P. A. Pantel. Clustering by Committee. PhD thesis, buch werden die Grundform der Terme mit dem Stemming- University of Alberta, 2003. Schritt in der Aufbereitungsphase und die Polysemie mit [4] M. Wang, K. Yang, X.-S. Hua, and H.-J. Zhang. Visual dem CBC Clustering, dem Kontextvektor und den damit tag dictionary: interpreting tags with visual words. In verbundenen Mehreinträgen eines Terms, realisiert. Mit der Proceedings of the 1st workshop on Web-scale erwähnten besten visuellen Beschreibung ist das Erfassen multimedia corpus, WSMC ’09, pages 1–8, New York, der Charakteristika des Objektes mit dem Konzept der NY, USA, 2009. ACM. Durchschnitte, die Kompaktheit und Effizienz mit der eine- [5] S. Zhang, Q. Tian, G. Hua, Q. Huang, and S. Li. Instanz Darstellung und die Kompatibilität zu der Bildda- Descriptive visual words and visual phrases for image tenbank mit den Histogrammen der visuellen Wörter und applications. In Proceedings of the seventeen ACM Phrasen erfüllt. Zukünftig, um die Anfragezeiten der eine- international conference on Multimedia, MM ’09, pages Instanz visuellen Beschreibungen von ca. 12 Sekunden wei- 75–84, New York, NY, USA, 2009. ACM. ter zu reduzieren, kann man geeignete effiziente Indexstruk- [6] Q.-F. Zheng and W. Gao. Constructing visual phrases turen und Algorithmen für die Bildsuche untersuchen und for effective and efficient object-based image retrieval. einsetzen. Um die Qualität des Retrievals weiter zu verbes- ACM Trans. Multimedia Comput. Commun. Appl., sern, könnte man versuchen auch Farbeigenschaften und ih- 5:7:1–7:19, October 2008. re Relevanz für Objekte miteinzubeziehen, d.h. diese für die visuelle Beschreibung zu lernen und in der Bildsuche einzu- setzen. 108