minpic01.jpg

Dr. Aldo von Wangenheim

Cleveres Comeback

Bilder finden durch automatische Inhaltsanalyse

Die Nadel im Heuhaufen ist nichts gegen das Foto im Bildarchiv. Das Pixelpendant zur Volltextsuche ist schließlich noch nicht erfunden. Aber Forscher arbeiten daran: Software entsteht, die Bilder analysiert und eine Beschreibung des Inhalts erzeugt.

Bei den eigenen Fotoalben fangen die Probleme schon an. Wenn es überhaupt zum Einkleben kommt, sortiert man chronologisch. Später sind die Bilder nicht zu finden, deren Entstehungszeit unbekannt ist. In einem Vorort von Seattle stellt sich das Problem verschärft: Dort rafften die Mannen von Bill Gates´ Firma Corbis bisher eine Million Bilder zusammen und vermarkten sie.

Üblicherweise klassifiziert man Bilder bei der Ablage in Datenbanken mit einer Reihe vorgegebener Begriffe. Reichen die Begriffe nicht aus, um später eine Anfrage zu formulieren, dann ist Handarbeit angesagt. Um eine Statistik mit den beliebtesten Autofarben zu illustrieren, sucht eine Zeitschrift beispielsweise ein Bild mit Autos, von denen die meisten rot sind. Die grauen Haare des Bildarchivars könnten sich ob dieses Ansinnens dramatisch vermehren. Wo soll er suchen? Legionen von Fotos aus den Bereichen Autorennsport, Verkehr und Handel inspizieren?

Um der Bilderflut Herr zu werden, sollten wir also mehr Freiheit bei der Recherche haben. Niemand kann zum Zeitpunkt der Archivierung eines Bildes wissen, unter welchen Gesichtspunkten es später einmal wichtig wird. Deshalb besteht ein großer Bedarf an Verfahren, die Bilder in Multimedia-Datenbanken automatisch analysieren und eine detaillierte Beschreibung ihres Inhalts erstellen. Die Beschreibung wiederum läßt sich dann mit klassischen Techniken von der Volltextsuche bis zu ausgefeilten Verfahren des Information Retrieval nutzen.

Mit einer solchen Inhaltsanalyse von Bildern beschäftigt sich ein wachsender Forschungszweig namens CBIR (Content-Based Image Retrieval) [1]. Beispielsweise entwickelt das IBM-Forschungszentrum im kalifornischen Almadén das System QBIC (Query by Image Content). Bei der Arbeit mit diesem Programm gibt der Nutzer einige Bildaspekte wie Oberflächenstruktur (Textur), Farbe oder Form durch Beispiele an. QBIC erzeugt daraus eine Beschreibung, die es mit den automatisch erzeugten Beschreibungen von Bildern in der Datenbank vergleichen kann.

Schlüsseloperation

Zwei Gebiete der Informatik speisen die Forschungen zum Bild-Retrieval: Datenbanken und Bildverarbeitung. Herkömmliche Bilddatenbanken sind bei der Suche nach bestimmten Bildern jedoch ausschließlich auf den Begleittext angewiesen, der etwa in Form von Schlüsselwörtern mit den Bildern gespeichert ist. Diese Suche läßt sich etwas flexibler gestalten, wenn Begriffe mit UND- oder ODER-Operatoren verknüpft sind. Außerdem erlauben Synonymtabellen und Thesauri, auch nach solchen Begriffen zu suchen, die nicht in der Beschreibung der Bilder enthalten sind. So könnte eine Synonymtabelle etwa `Hintergrund: azur´ durch `Hintergrund: himmelblau´ bei der Suche ersetzen. Alle Merkmale, welche die Suche leiten, müssen jedoch dem System von vorneherein bekannt sein. Im Gegensatz zu IBMs QBIC-System ist es normalerweise nicht möglich, der Datenbank ein neues Bild zu zeigen und sie anschließend im Fundus nach Abbildungen suchen zu lassen, die in bestimmten Aspekten dem neuen Bild ähneln.

Den raffiniertesten Versuch, aus Bildtexten schlau zu werden, verfolgt eine Anwendung des Cyc-Systems [2] der texanischen Firma Cycorp. Cyc ist ein ebenso legendäres wie umstrittenes Langzeitprojekt der Künstlichen Intelligenz (KI). In dieser Anwendung faßt Cyc die Beschreibungen von Bildern nicht als bloße Zeichenketten auf, sondern verknüpft sie mit Wissen über unseren Alltag, das in Millionen Häppchen aufgeteilt sorgfältig geordnet bereitsteht. Bei einer Anfrage nach Menschen in Badehosen findet Cyc eine sommerliche Strandszene, auch wenn im Begleittext überhaupt nicht von Badehosen die Rede ist - der gesunde Binärverstand sagt, daß der Strand im Sommer von Badehosenträgern wimmelt. Bei der Suche nach unseren vorwiegend roten Autos dürfte allerdings auch Cyc aufgeschmissen sein.

Muttermalmerkmal

Das Bild-Retrieval profitiert nicht nur von der Forschung zu Datenbanken, sondern auch von der zur Bildverarbeitung. Die Analyse und Verarbeitung von Abbildungen geschah zunächst nach dem Prinzip der dynamischen Merkmalsanalyse (dynamic feature extraction): Ein System mit Zugriff auf eine Bilddatenbank verfügt über eine interne Beschreibung komplexer Merkmale und Objekte wie `Auto´ oder `Muttermal´. Verfahren zur Objekterkennung versuchen, auf einem Bild typische Merkmale zu erkennen. Eine Anfrage nach einem Bild, die mit Hilfe solcher Merkmale und Objekte formuliert ist, läßt sich so zur Laufzeit in einem aufwendigen Prozeß beantworten. Solche Systeme sind leider sehr auf ein Anwendungsgebiet fixiert, da sich etwa die Mittel zur Beschreibung eines Tumors in einer tomographischen Aufnahme sehr stark von denen zur Analyse technischer Erzeugnisse unterscheiden. Dieser Ansatz ist deshalb für universell einsetzbares kommerzielles Retrieval ungeeignet. Gegenwärtig setzt man die dynamische Merkmalsanalyse nur im Einzelfall ein: Die Universität Kaiserslautern entwickelt beispielsweise ein System für die Analyse der Aufnahmen von Kernspintomographen.

In jüngster Zeit versucht man nun, für das Bild-Retrieval Ansätze aus Datenbankforschung und Bildverarbeitung zu kombinieren: Schlüsselwörter und Beschreibungen ergänzen weiterhin die Bilder beim Abspeichern; zusätzlich sorgen jedoch einfache Bildverarbeitungsverfahren dafür, die Beschreibung des Inhalts beim Ablegen des Bildes weiter anzureichern. Die Verteilung von Farben, die Gestalt von Konturen oder die Struktur von Flächen können beispielsweise als automatisch analysierte Merkmale die Bildbeschreibung ergänzen. Das Ergebnis der Analyse ist nicht unbedingt ein Satz in natürlicher Sprache, und ebensowenig ist es oft sinnvoll, eine Anfrage mit Worten zu formulieren. Schließlich lassen sich viele Aspekte von Bildern nur unzureichend mit Begriffen beschreiben - ist das Kornfeld im Wind nun wellig, kurvig oder wogend? Ein kleines Beispielbild hilft, wenn Textur und Farbe dem Gesuchten ähneln.

Die Analyse eines Bildes kann beim Einfügen eines Bildes in eine Datenbank geschehen oder bei Bedarf, wenn das Bild ein Kandidat für die Beantwortung einer Suchanfrage ist. Die Entscheidung für eine dieser beiden Vorgehensweisen hängt auch davon ab, ob sich die Datensätze rasch ändern. Bilder in Datenbanken zeichnen sich durch eine relativ geringe Fluktuation aus. Was einmal drin ist, kommt nicht so rasch wieder raus - auch Updates sind selten. Daher lohnt es sich, wenn ein Retrieval-System bei Aufnahme eines neuen Bildes wichtige Merkmale wie Texturen, Farbverteilungen und Grenzen zwischen Bildelementen automatisch berechnet und zusammen mit den Bildern abspeichert, so daß diese Beschreibungen von vorneherein für Anfragen bereitstehen.

Bilderbergmann

Auch deutsche Forscher bemühen sich darum, das Bild im Archiv eher zur Mistgabel als zur Nadel im Heuhaufen werden zu lassen. Zum Beispiel haben KI-Wissenschaftler vom `Technologie-Zentrum Informatik´ an der Bremer Universität und IBM-Entwickler aus Böblingen und Almadén in den letzten drei Jahren das Programm ImageMiner entwickelt. Das System läuft auf einer IBM RS/6000-Plattform unter dem Betriebssystem AIX. Zur Zeit wird das Programm auf andere Plattformen portiert. IBM hat jüngst angekündigt, daß ImageMiner in Zukunft weltweit vermarktet wird.

Vor der Speicherung analysiert ImageMiner die Bilder und erzeugt eine inhaltliche Beschreibung des Bildes als ASCII-Text. Während dieser Analyse identifiziert ImageMiner Bildbereiche und ordnet ihnen Eigenschaften zu. Ein Bereich mag beispielsweise rot sein, eine wolkenähnliche Textur haben und durch eine Kontur begrenzt sein. Konturen findet das System durch einen Algorithmus, der die charakteristische Änderung von Helligkeit, Farbe oder Textur am Rande eines Objekts registriert. Wie detailliert Farbe und Textur beschrieben werden, stellt der Benutzer anhand eines Rasters vorher ein. Zum Schluß erzeugt das Analyseverfahren eine Beschreibung der Nachbarschaftsbeziehungen zwischen den während der Bildanalyse erkannten Merkmalen, beispielsweise daß eine kreisförmige hellgelbe Fläche an einen breiten, tiefblauen Bereich grenzt. Auch Überlappungen oder Einschließungen erkennt das System.

minpic05.jpg

Die Landschaft im Original ...

minpic02.jpg

minpic03.jpg

minpic04.jpg

... und nach der Analyse durch ImageMiner: Konturen, Texturen und Farben werden deutlich.

Die analysierten Informationen fügt ImageMiner anschließend zu einer Beschreibung des Bildes in Textform zusammen und legt sie zusammen mit dem Bild in der Datenbank ab. Einzelne Beschreibungen von Bildbereichen, die Begriffen wie `Baum´, `Himmel´ oder `Strand´ entsprechen, verwaltet ein Thesaurus, so daß Benutzer eine Anfrage mit vertrauten Begriffen formulieren können.

Minensuche

ImageMiner reduziert also das komplexe Problem, bestimmte Bilder zu finden, auf das einfachere Problem, einen bestimmten Text zu finden - nach der Analyse des Bildinhalts können bewährte Verfahren des Textretrievals zum Einsatz kommen, wenn eine Suchanfrage gestellt wird.

Eine solche Anfrage ist auf zweierlei Weise möglich. Entweder findet ImageMiner Bilder anhand von direkten Angaben zu Bildmerkmalen wie Farbe, Textur oder Kontur. Verschiedene Werkzeuge unterstützen die Eingabe und die Auswahl dieser Merkmale. Für ein Bild vom Meer kann man etwa nach einer Fläche fragen, die groß, blau und unten im Bild ist. Die Suche in den Bildbeschreibungen führt ImageMiner schließlich mit einer angepaßten Version des IBM SearchManager 6000 durch.

Alternativ darf man Begriffe aus dem Thesaurus für Anfragen verwenden: Nach `Wolken und Wald´ sucht man am besten direkt, ohne Farbe und Textur zu beschreiben. Eine Kombination beider Modi ist ebenfalls möglich. So darf man nach Bildern suchen, die oben blau sind und Wald enthalten. Der Thesaurus stellt ein Modell eines Teils der Realität dar; er definiert einfache und komplexe Objekte darin. Einfache Objekte sind direkt durch die Merkmale definiert, nach denen die Bildbereiche analysiert werden. So muß eine Wolke (als einfaches Objekt) weiß oder grau sein, eine wolkenähnliche Textur haben und eine Kontur aufweisen, die diese Farbe und Textur umschließt. Außerdem müssen sich die genannten Bereiche von Farbe und Textur überlappen. Komplexe Objekte werden analog definiert, dürfen aber in ihrer Beschreibung auch einfache Objekte enthalten, also nicht nur direkt analysierte Merkmale von Bildbereichen.

Komplexitätsfalle

Die Objekterkennung stellt sich intern als die Aufgabe dar, zu prüfen, ob ein Graph in einem anderen enthalten ist. Denn das Ergebnis der Analyse auf Farbe, Textur und Kontur liefert einen Graphen, dessen Knoten einheitliche Bildbereiche sind und dessen Kanten die Nachbarschaftsbeziehungen darstellen. Die Objektbeschreibungen wiederum sind analog auch als Graphen vorhanden, die gerade beschriebene Wolke etwa als drei Knoten mit entsprechenden Nachbarschaftskanten.

minpic06.jpg

Neue Freiheit beim Suchen: ImageMiner erlaubt komfortable Anfragen ...

minpic07.jpg

... und liefert passende Bilder aus dem Archiv im Handumdrehen.

Ein allgemeiner Algorithmus, der Graphen in der genannten Weise vergleicht, ist jedoch zu komplex, um in der Praxis berechenbar zu sein. Daher verwenden die Bremer Forscher einen `Graphgrammatik´-Ansatz, der mit Hilfe von Heuristiken (Faustregeln) des Anwendungsbereichs die Komplexität reduziert. Die Erkennung von Objekten wird damit von beiden Seiten vorangetrieben - die analysierten Daten des Bildes fügen sich auf der einen Seite zu komplexeren Strukturen, und auf der anderen Seite liefert das im System enthaltene Wissen über den Gegenstandsbereich Erwartungen, welche Objekte Kandidaten für die Erkennung sind.

Anwendungen gesucht

Die Betaversion von ImageMiner ist auf Landschaftsbilder und technische Zeichnungen spezialisiert. Die Entwickler suchen noch Kooperationspartner, um Versionen für andere Bereiche zu erstellen. Eine Anpassung an neue Gebiete soll problemlos möglich sein. Dazu erweitert man den Thesaurus um neue Beschreibungen von Objekten und Texturklassen. Eine Anpassung der Komponenten zur Farb- und Konturanalyse ist nach Angaben der Entwickler nicht nötig. Hier sind zumindest Zweifel angebracht, besonders was die Erkennung von Konturen angeht. Ob sich die Umrisse von geröntgten Lebern und geschniegelten Autos mit dem gleichen Verfahren erkennen lassen, muß erst die Praxis zeigen.

Wer ins Bilderfinden einsteigen will und einen WWW-Zugang sein eigen nennt, kann unter http://wwwqbic.almaden.ibm.com/ eine Testversion von QBIC downloaden, wahlweise für AIX, Linux, NT, Windows95 oder OS/2. Informationen zum ImageMiner gibt es unter http://www.tzi.uni-bremen.de/BV/ImageMiner. Eine Demoversion mit einigen Landschaftsbildern und Zeichnungen läßt sich direkt im Web ausprobieren. Das komplette Programm für AIX steht zum Download bereit.(ts)

Literatur
[1] Venkat N. Gudivada, Vijay V. Raghavan, Content-Based Image Retrieval Systems, IEEE Computer, September 1995, S. 18

[2] Thomas J. Schult, Transparente Trivialitäten, Cyc-Wissensbasis im WWW, c't 10/96, S. 118