Ähnlichkeitsanfragen unter Verwendung von Bildmerkmalen und Text

Abstract

Informationen sind nicht nur in reiner Textform, sondern zunehmend auch in multimedialen Formaten verfügbar. So bestehen im Internet HTML-Dokumente oft aus Texten und Bildern. Um den Informationsbedarf der Benutzer Rechnung zu tragen, gewinnt die Bildsuche zunehmend an Bedeutung. Im allgemeinen werden heute zwei Verfahren zur Bildsuche eingesetzt. Zum einen kann man die Bilder mit Schlagworten annotieren und unter Anwendung von Text-Retrieval-Verfahren suchen. In manchen Anwendungsfeldern (z.B. bei Bildagenturen) existieren solche Annotationen, die den Inhalt eines Bildes in Schlagworten relativ genau beschreiben. Falls die zu durchsuchenden Bilder Bestandteile von Dokumenten sind, können die Annotationen auch aus der Umgebung der Bilder gewonnen werden: Informationen, wie beispielsweise überschriften, Bildunterschriften oder benachbarte Textpassagen geben Aufschluss über den Inhalt und Kontext des Bildes. Beim zweiten Ansatz extrahiert man (visuelle) Merkmale, wie z.B. Farbe oder Textur, aus den Bildern und sucht aufgrund dieser Merkmale nach ähnlichen Bildern zu einer Vorlage. Bei dieser inhaltsbasierten Bildähnlichkeitssuche verwendet man zum Teil hochdimensionale Merkmalsvektoren mit mehreren hundert Dimensionen. Wenn man beispielsweise ein Farbhistogramm als Merkmal verwendet, sind zwei Bilder (farblich) ähnlich, falls sie ähnliche Vektoren aufweisen. Die Vektoren aller Bilder bezüglich eines Merkmales befinden sich im gleichen Vektorraum, den man kurz Merkmalsraum nennt. Eine k-Nächste-Nachbar-Suche in diesem Merkmalsraum liefert die k ähnlichsten Bilder zu einem oder mehreren gegebenen Bildern, den Referenzbildern. Von der Kombination der inhaltsbasierten Suche mit der Textsuche versprechen wir uns bessere Suchresultate. Dieser Beitrag beschreibt ein Modell und Techniken zur Auswertung kombinierter Anfragen mit Bild- und Textbestandteil. Zur effizienten Auswertung kommen dabei drei Indexstrukturen parallel zum Einsatz: Invertierte Listen (via SQL) und Signaturen für die Textbestandteile und das VA-File für die Suche in den hochdimensionalen Merkmalsräumen. Im folgenden stellen wir unser Modell solcher kombinierter Anfragen dar. Anschliessend beschreiben wir effiziente Verfahren zur Bildsuche und zur Textsuche. Diese Verfahren sind dann die Grundlage des kombinierten Algorithmus zur Auswertung solcher Anfragen, den wir danach darstellen werden.