PHOTOBOOK

Vortrag im Rahmen des Mathematischen Seminars Studiengang Network Computing

TU Bergakademie Freiberg

Von André Säckel, Juli 2002 andre.saeckel@student.tu-freiberg.de

Betreuer: Dr. Oliver Ernst Referenzen:

• Content-Based Manupilation of Image Databases: A. Pentland, R.W. Picard, S. Scarloff

• Eigenface for Recognition: Matthew Turk & Alex Pentland • View-Based and Modular Eigenspaces for Face Recognition: A. Pentland, B.

Moghaddam, T. Starner • Zahlreiche Internetseiten verschiedener Hompages, die sich mit dem Thema

auseinander setzten In meinem Vortrag möchte ich Photobook vorstellen, welches mit einem dieser mathematischen Algorithmen, wie uns Thomas soeben erklärte, arbeitet. Die Bedeutung der automatischen Indexierung von Textdokumenten ist mit Zunahme der (Text)Information weltweit nicht nur jenen deutlich geworden, die sich zu Forschungszwecken mit diesem Thema befassen, sondern erschließt sich gerade denjenigen, die tagtäglich mit dem Retrieval von Texten konfrontiert werden. Neue Speichermedien und die zunehmende Neigung, Informationen multimedial, also durch Bild und Ton darzustellen, haben den Bedarf an effizienten Werkzeugen zur Verwaltung (Indexierung) und zum Retrieval gerade von Bilddokumenten erhöht.

1.1 Was sind Bilder?

Bilder, umgangssprachlich ausgedrückt, sind Fotografien, Gemälde oder Zeichnungen. In Bezug auf die hier angesprochene computerbasierte Indexierung, sie werden als 2-dimensionale Darstellungen auf einem Computerbildschirm umschrieben, wobei die kleinste Einheit, der auf dem Bildschirm angezeigte Pixel (Punkt) ist. Ein Bild entspricht demnach einer Matrix, die aus einer bestimmten Anzahl von Spalten und Zeilen von Pixeln besteht.

1.2 Worin unterscheiden oder ähneln sich Bilder?

Wesentliche Merkmale, die der Erstellung einer Klassifikation dienen können, werden im folgenden aufgezählt:

• Lichtquelle (Sonnenlicht vs. Blitzlicht) • Konturenschärfe (Aquarellgemälde- weiche Konturen vs. Konstruktionszeichnungen-

scharfe Konturen). • Schattierung (prozentualer Anteil des Schattens am Bild) • Dimension (2-dimensional bei Landkarten, 3-dimensional bei Personen o.ä.) • Vordergrund und Hintergrund (natürlicher Vordergrund z.B. Baum, künstlicher

Vordergrund z.B. Haus) • Art Unterteilung in Gruppen wie Portrait, Landschaftsbilder etc.

1.3 Wo wird die Verwaltung und das Retrieval von Bildern gebraucht?

Die wohl am häufigsten benötigten Bildarchive sind in die Archive von Zeitungs- und Zeitschriftenverlagen und Fernsehanstalten integriert. Zahlreiche Bildagenturen zeugen vom hohen Bedarf am (wiederholten) Einsatz für die unterschiedlichsten Zwecke. Es fallen aber nicht nur Fotografien und Gemälde unter den Bereich der Verwaltung, sondern auch geographische und technische Zeichnungen (Landkarten, Konstruktionspläne) und auch Piktogramme.

Im Folgenden sind einige typische Anwendungsfelder aufgelistet:

• Biomedizin (Röntgenbilder / CT-Aufnahmen) • Recht (Markenschutz) • Geographie (Landkarten) • Meteorologie / Weltraumforschung (Wetterkarten / Satellitenbilder) • Ingenieurwissenschaften (technische Zeichnungen) • Geologie (Landkarten) • Werbewirtschaft / Film- und Fotoindustrie (Fotografien) • Kunst(gewerbe) (Gemälde) • Polizei (Fotografien)

Bei der Suche nach Bildern gibt es zwei wesentlich unterschiedliche Zielsetzungen. Hierzu zwei Beispiele: 1. Während eines Banküberfalls zeichnet eine Videokamera das Verbrechen auf. Ein derart gewonnenes Foto wird nun einem Suchsystem übergeben. Das System wird nun im Datenbestand nach Bildern suchen, die beispielsweise hinsichtlich Kontur, Kontrast und anderer Merkmale weitgehendste Ähnlichkeit mit dem vorgegebenen Foto aufweisen. 2. Ein anderes Ziel steht im Vordergrund, wenn beispielsweise für eine Reportage ein zum Thema passendes Bild gesucht wird. Hier steht zu Beginn der Suche das Zielobjekt - also das entsprechende Bild - noch nicht fest. Bei dieser Art von Anwendung sind im Gegensatz zu den „1." genannten Fall eine gut strukturierte Klassifikation unverzichtbar.

1.4 Automatisch Indexieren

Grundsätzliche Probleme bei der Indexierung und dem Retrieval - natürlich nicht nur in Bezug auf Bilder - bestehen einerseits im zeitlichen Aufwand für die Analyse der Dokumente und andererseits in der Schwierigkeit, Regeln aufzustellen, die für alle Eventualitäten Gültigkeit besitzen. Hinzu kommt, daß die meisten Systeme nur von Experten zu bedienen sind, was erhebliche Nachteile in puncto Kosten und Verfügbarkeit mit sich bringt. Um Bilder automatisch zu indexieren bzw. zu klassifizieren, müssen Algorithmen entwickelt werden, welche Informationen aus Bildern herausziehen und diese Informationen einer Klassifikation zuordnen.

Softwarebeispiele: Projekt Anwendung Methodischer Ansatz Entwickler

CAFIIR Gesichtserkennung konturbasiert Narasimhalu, 1993

VIRAGE universell einsetzbar (theoretisch)

farb-, textur- und konturbasiert Virage Inc.

IRIS Klassifizierung, Indexierung, Verwaltung von Bildern (allg.)

farb-, textur- und konturbasiert

Hermes et al., 1995

ENIGMA Erkennung von medizinischen Bildern kantenbasiert

Gevers & Smeulders, 1992

FERET (Teil v. Photobook) Gesichtserkennung kontur- und

farbkontrastbasiert US Armee (MIT, USA)

2 MIT Photobook Photobook ist ein Projekt der Vision and Modeling Group des Media Laboratory am Massachuesetts Institute of Technology (MIT). Photobook ist ein interaktiver Browser, der es ermöglicht, Abfragen in Bilddatenbanken, die auf den Inhalten der Bilder aufbauen, durchzuführen. Dies erfolgt z.B. durch eine Sortierung nach Ähnlichkeit der vorhandenen Bilddateien anhand vorberechneter visueller Merkmale . Dieses System vergleicht Merkmale, die mit Bildern oder Bildinhalten verbunden sind, und nicht die Bilder selbst. Es geht also um eine Suche nach "Bildern, ähnlich wie dieses" oder nach gemeinsamen Merkmalen. Diese Merkmale stellen wiederum Parameterwerte verschiedener Konzepte oder Modelle dar, im allgemeinen Farbe, Textur und Form. Photobook arbeitet mit diesen Modellen, kann aber auch Merkmale jeglicher anderer Art abprüfen. Aus einer Bibliothek von Algorithmen wird jeweils ein zu diesem Modell passender gewählt und die betreffenden Merkmale damit verglichen. Unter Version 5 enthielt diese Bibliothek Euklidische, Divergenz-, Vektorraum-, Histogram-, Fourier-Spitzen- und Wavelet-Tree-Algorithmen; außerdem kann jede lineare Kombination dieser Formeln eingesetzt werden. Photobook arbeitet mit verschiedenen Grafikdateiformaten, (.raw, .ppm, .jpeg, .gif), wobei die Bilder unterschiedlichen Formatgrößen haben dürfen. Farbbilder werden bis 8-bit bearbeitet.

2.1 Umsetzung

Eine Photobookdatenbank liegt mit identischer Struktur als Kompositum auf einer Festplatte und zum Teil in Hashtabellen im Arbeitsspeicher. Ähnlich wie virtuelles RAM wechseln Teile der DB von Festplatte zu Arbeitsspeicher, bzw. zurück. Auf diese Weise werden Caching und nur zeitfristig benötigte Änderungen (=Sortierungen) umgesetzt. Manche Teile der DB werden nur auf Anfrage des Anwenders erstellt und nicht dauerhaft gesichert. Dies betrifft Ähnlichkeitswerte und vergrößerte Wiedergaben von Bilddateien Dies erfolgt mittels besonderer Tabellen, der active tables. Diese werden genauso wie alle anderen Tabellen auch behandelt und fallen unter das gleiche Protokoll, aber ihr Inhalt wird erst auf Abruf hin berechnet.

Die Trennung von Retrieval Engine und Indexierungsmodellen ermöglicht es, für bestimmte Zwecke besser geeignete Algorithmen zu implementieren, bzw. für manche Fragestellungen ungeeignete aus der Bearbeitung herauszunehmen. Vier Überlegungen, die den Anwender betreffen, wurden bei Entwicklung des Systems in den Mittelpunkt gestellt:

1. Anwender sollten weder auf Bedeutungstragende noch Wahrnehmungstragende Ettikettierungen eingeschränkt sein. Das System sollte sich der menschlichen Auffassung von "Ähnlichkeit" annähern.

2. Es sollte Anwendern möglich sein, einen Teil einer typischen, homogeneren Bildregion (z.B. Grasrasen) zu bezeichnen ("Dieses Eckchen ist Gras"), und diese Bezeichnung sollte auf visuell ähnliche Bereiche in diesem und anderen Bildern in der Datenbank angewandt werden.

3. Beliebig abgegrenzte, ggf. sogar überlappende Regionen, sollten frei bezeichnet werden können.

4. Das System für die Anmerkungen und Bezeichnungen sollte dem Anwender schnell visuelle Suchergebnisse vorlegen.

Es gibt drei Arten von Bildbeschreibungen bei Photobook: • Appeareance Photobook

Eine, die Suche auf Grundlage von Erscheinungen erlaubt. • Shape Photobook

Eine, die 2-D Formen verwendet • Texture Photobook

Eine Dritte, die das Suchen auf Grundlage von Strukturmerkmalen erlaubt. Diese Bildinhaltsbeschreibungen können miteinander und mit Text basierenden Beschreibungen kombiniert werden, um eine hochwertige Suchfähigkeit zu liefern. Die Datenbanken können schnell, interaktiv und effizient, unter UNIX bzw. Linux auf X-Windows Basis, durchsucht werden. 2.2 Die Bedienoberfläche : Sie besteht aus einer Arbeitsfläche, in der die Bilder angezeigt werden, und Buttons für die Steuerung. Um Bilder zu vergleichen, werden ein oder mehrere Bilder markiert und / oder Stichwörter in das Textfeld unter der Arbeitsfläche eingegeben. Die Suche kann entweder durch drücken der Return-Taste im Textfeld ausgelöst werden, oder man drückt mit der mittleren Maustaste auf die ausgewählten Bilder. Das Ergebnis wird nun so präsentiert, dass die Bilder angezeigt werden, die der Suchanfrage entsprechen. Geordnet werden sie nach der höchsten bis zur kleinsten Ähnlichkeit der Koeffizienten der Suchmenge (links nach rechts / oben nach unten jeweils abfallend). Beim starten des Programmes werden die Bilder in der Arbeitsfläche in der Reihenfolge präsentiert, wie sie in die Datenbank implementiert wurden. Wenn die Bilder nicht in die Arbeitsfläche hineinpassen, wird sie in Seiten unterteilt durch die man sich dann mit dem Scrollbalken durcharbeiten kann.

Optionsmenues :

• Datenbank – Auswahl der verschiedenen Datenbanken • Anzeigemodus – Festlegen wie jeder Datenbankeintrag auf der Arbeitsfläche

angezeigt wird z.B. Anzeige des normalen Bildes, Fourier Spektrum, oder verschiedene Verläufe, die die Schärfe, den Kontrast oder die Farbe wiedergeben

• Suchmetrik - Auswahl des Algorithmus, welcher die Ähnlichkeit bestimmen soll natürlich muss in der Datenbank festgelegt sein, welche Algorithmus unterstützt wird

3 Appeareance Photobook (Suche nach Erscheinungen)

Um ein genaues Ähnlichkeitsmaß in Bezug auf die Erscheinung von Objekten und Objektklassen zu erhalten, muss erst bestimmt werden, welche Eigenschaften die Bildobjekte am effektivsten beschreibt. Die gängigste, standardisierte lineare Methode um Informationen aus einer Bildermenge zu extrahieren ist die Karhunen-Loève Transformation (Hauptkomponentenanalyse). Diese Transformation benutzt die Eigenvektoren der Kovarianzmatrix von der Menge der Bildeigenschaften. Sie charakterisiert also alle Verschiedenheiten zwischen den Bildern des Objekts und der Erscheinung der Objekte. Im Prinzip werden nur wenige Eigenvektoren mit den größten Eigenwerten genommen, die den Hauptteil der Abweichung zwischen den Bildobjekten ausmachen

3.1 Gesichtserkennung (Face Recognition)

Hinter diesem Begriff versteckt sich ein System zur vollautomatisierten Entdeckung, Erkennung und Modellbasierten Kodierung von Gesichtern. Potentielle Anwendungsfelder werden in der Videotelephonie, Datanbankbildkompression und automatischen Gesichtserkennung gesehen. Das bestehende System setzt sich aus einer zweistufigen Objektfindungs- und Ausrichtungsphase, einer Kontrastnormalisierung und zuletzt einer Karhunen-Loève-basierten Merkmalsextraktionsstufe zusammen. Das Ergebnis dieser abschließenden eigenspace-Phase wird sowohl zur Erkennung als auch zum kodieren benutzt. Automatisch erzeugte, etwa 100 byte-große Dateien geben die Gesichter in guter Qualität wieder.

3.2 Gesichtserkennung mittels Template Matching

Thomas hat uns die Eigenface Recognition beschrieben. Ich möchte nun einen etwas verbesserten Algorithmus vorstellen, der den Eigenface nutzt, aber leicht erweitert wurde.

• Finde das Gesicht • Verbessere die Position und Größe • Verfeinere die Größe (x und y werden unabhängig behandelt) • lokale Verschiebungen pro Punkt werden durchgeführt

Thomas Analyse nimmt an, dass wir zentrierte Gesichter haben die in der gleichen Größe wie die Schulungsbilder & die Eigenbilder (eigenface) vorliegen. Bei Template Matching benötigen wir eine Methode um das Gesicht (bzw. Merkmale (feature)) in einer Szene zu lokalisieren & aufzuspüren. Wir wissen, dass sich Gesichter nicht radikal ändern, wenn man sie in einen Bildraum projiziert, während sich „Nicht-Gesichter“ ganz anders verhalten. Die Grundidee, die nun benutzt wird um Gesichter aus einer Szene zu entdecken ist es: An jeder Stelle im Bild die Distanz ε zwischen den lokalen Unterbild & dem Gesichtsraum (face space) auszurechnen. Diese Distanz vom Gesichtsraum wird als ein Maß der Gesichtigkeit (faceness) benutzt. Somit ist das Resultat der Berechnung der Distanz vom Gesichtsraum von jedem Punkt des Bildes eine „Gesichtskarte“ (face map) ( , )x yε = Unglücklicherweise ist die direkte Anwendung der Gleichung

2 || ||fε = Φ−Φ eher teuer (teuer im Sinne von Berechnungsaufwendig). Deshalb wurde eine simplere Methode zur Berechnung der Gesichtskarte entwickelt: Um die Gesichtskarte an jedem Pixel eines Bildes berechnen zu können, muss das Unterbild, (in diesem Pixel zentriert) Auf den Gesichtsraum zuprojiziert werden um dann die Projektion vom Original zu subtrahieren. Um das Unterbild Γ auf den Gesichtsraum zu projizieren, muss erst das Durchschnittsbild subtrahiert werden, was in

Φ = Γ −Ψ geschieht. Dabei ist fΦ die Projektion von Φ auf den Gesichtsraum, die Distance an einer gegebenen Stelle ist dann:

2 2|| ||fε = Φ −Φ [Gleichung 1]

( ) ( )Tf f= Φ −Φ Φ−Φ

( )T T Tf f f= Φ Φ−Φ Φ +Φ Φ −Φ

T Tf f= Φ Φ −Φ Φ

weil fΦ eine linear Kombination des Eigenfaces (1

k

f i ii

uω=

Φ =∑ ) & die Eigenfaces

orthonormal Vektoren sind folgt.

2

1

kTf f i

i

ω=

Φ Φ =∑ [Gleichung 2]

und

2 2

1( , ) ( , ) ( , ) ( , )

kT

ii

x y x y x y x yε ω=

= Φ Φ −∑ [Gleichung 3]

wobei ( , )x yε und ( , )i x yω skalare Funktionen der Bildmenge sind und ( , )x yΦ eine Vektorfunktion der Bildlage. Der 2. Teil der Gleichung 3 wird in der Praxis durch Korrelation mit den k Eigenfaces berechnet:

2

1( , )

k

ii

x yω=∑

1[ ( , ) ]²

kT

ii

x y u=

= Φ∑ [Gleichung 4]

1[( ( , ) ) ]²

kT

ii

x y u=

= Γ −Ψ∑

1[ ( , ) ]²

kT T

i ii

x y u u=

= Γ −Ψ∑

1[ ( , ) ]

k

i ii

x y u u=

= Γ ⊗ −Ψ⊗∑

wobei ⊗ der Korrelationsoperator ist. Der erste Ausdruck der Gleichung 3 wird zu: ( , ) ( , ) [ ( , ) ] [ ( , ) ]T Tx y x y x y x yΦ Φ = Γ −Ψ Γ −Ψ [Gleichung 5] ( , ) ( , ) 2 ( , )T T Tx y x y x y= Γ Γ − Ψ Γ +Ψ Ψ ( , ) ( , ) 2 ( , )T Tx y x y x y= Γ Γ − Γ ⊗Ψ +Ψ Ψ so dass:

2

1( , ) ( , ) ( , ) 2 ( , ) [ ( , ) ]

kT T

i ii

x y x y x y x y x y u uε=

= Γ Γ − Γ ⊗Ψ +Ψ Ψ + Γ ⊗ −Ψ⊗∑

Da das Durchschnittsgesicht Ψ und die Eigengesichter iu fest sind, können die Ausdrücke TΨ Ψ und iuΨ⊗ vornweg berechnet werden. Daher umfasst die Berechnung des

Gesichtsausschnittes nur k+1 Korrelationen über das Eigenface und die Errechnung des ersten Ausdrucks ( , ) ( , )T x y x yΓ Γ . Dies wird durch das quadrieren des Eingabebildes ( , )x yΓ und, an jeder Bildposition, durch das summieren der quadrierten Werte des lokale Unterbildes berechnet. Mit diesem abgewandelten Algorithmus ist es nun möglich Gesichter zu erkennen und nach einem Schablonen-Muster zu durchsuchen.

3.3 Template Matching mit Erweiterung durch die Beschreibung der Gesichtsmerkmale Augengesichtsstudien (Studien, bei denen die Augenstellungen von Personen beim erkennen anderer Testpersonen untersucht wurden) haben gezeigt, dass die Gesichtsmerkmale Augen, Nase und Mund wichtige Widererkennungsmerkmale sind. Deshalb wird eine zusätzliche Ebene der Beschreibung in Bezug auf die Eigeneyes, Eigennoses & Eigenmouths eingebunden. Dies geschieht durch eine gering aufgelöste Beschreibung des ganzen Kopfes erweitert durch zusätzliche hochaufgelöste Details bzgl. der wichtigsten Gesichtstsmerkmale.

Also wird bei diesem Programm die Augenpartie, die Nase oder der Mund von einer Person aus dem Testset als Maske verwendet. Diese Maske wird nun pixelweise über das Bild verschoben, in dem die Gesichtsmerkmale gefunden werden sollen. Bei jeder Position wird die euklidsche Norm zwischen dem Template und dem Ausschnitt aus dem jeweiligen Bild berechnet. Diejenige Position, bei der die Norm minimal ist, wird als die Augenpartie der neuen Person festgelegt. Ausgehend von dieser Position wird das Gesicht der neuen Position "ausgeschnitten". Wenn sich in diesem Ausschnitt beide Augen, Nase und Mund befinden, dann handelt es sich um eine korrekte Entdeckung, andernfalls wird das Gesicht nicht detektiert. Mit diesem Algorithmus wurden 290 von 300 Gesichtern aus dem Trainingsset der Manchester face database entdeckt. Dies entspricht einer Detektionsrate von 96,6%.

Bsp. für ein Trainingstemplate:

Die DFFS (different-from-feature-space) Merkmalsdetektor wurde für die Erkennung in einer großen DB mit 7562 Bildern benutzt. 128 repräsentative Personen wurde benutzt um einen Satz der Eigenmerkmale zu finden. Die ganze Datenbank wurde verarbeitet, indem man unabhängige Detektoren für jedes Merkmal benutzt (mit DFFS 10 Eigenvektoren). Treffer wurden erreicht, indem man unabhängig die globalen Minima für jede der 4 Distance-Maps ausgewählt wurden.

In diesem Bild werden typische Trefferquoten gezeigt. Die Treffer der Erkennung der Gesichtsmerkmale werden stabiler, wenn eine zusätzliche Beschränkung der Gesichtsgeometrie im Bezug auf die relative Merkmalslocation eingebunden wird. Experimente haben gezeigt, dass die Erkennungsrate von Mündern und Nase stark verbessert werden, indem man die Suche mittels der einfach zu erkennenden Merkmale (Augen) daran aufhängt. Mit der Fähigkeit Gesichtsmerkmale über einen weiten Bereich veläßlich zu erkennen, kann man automatisch eine modulare Präsentation generieren. Letztendlich erhält man, wenn wir die Verfahren (Eigenface + Eigenfeature) kombiniert nutzt, eine Verbesserung der Erkennungsrate auf 98 %. Die Eigenmerkmale haben die Möglichkeit, Nachteile der Standardeigenfaces auszugleichen. Eine reine Eigenface-Methode kann von starken Variationen im Inputbild in die Irre geführt werden. Im Bild wird ein Experiment gezeigt, bei dem die Inputbilder durch eine Hand, weisse Striche im Gesicht und einem vorgetäuschten Bart manipuliert wurden.

Die Eigenface Methode war nicht in der Lage, die richtigen Gesichter zu erkennen und anzuzeigen. Im Gegensatz dazu wurde mit der Eigenfeature-Methode eine vollständige Trefferquote erzielt.

Darstellung der einzelnen Erkennungsmethoden in einem Diagramm:

4 Zusammenfassung

Die automatische Indexierung von Bildern ist wesentlich komplexer als die automatische Indexierung von beispielsweise Volltexten. Hier fehlt dem „Indexierungs-Gegenstand" ein sprachliches Ordnungssystem. Die Beschreibung eines Bildes durch mehrere unterschiedliche Personen wird weitaus mehr Beschreibungsvarianten zur Folge haben, als die Beschreibung eines (wissenschaftlichen) Textes. Dementsprechend unterscheiden sich die spezifischen Problematiken wesentlich:

• bei Bildern gibt es keine alphabetische oder numerische Ordnung wie z.B. bei Textdokumenten oder numerischen Dokumenten, daher ist es schwierig, ein Bild eindeutig, also unverwechselbar (zu einem ganz ähnlichen Bild, wie z.B. bei den einzelnen Frames eines Videofilms) zu beschreiben. Eine solche beschreibende Sprache ist nämlich anwendungs- und wissensabhängig.

• Vorteil: die Mehrsprachigkeit fällt hier weg. Ein Dokument gleichen Inhalts in mehreren Sprachen zu finden, dürfte recht schwer sein, wenn das Retrievalsystem nicht alle entsprechenden Sprachen (und deren semantische Besonderheiten) beherrscht.

• Textdokumente werden meist thematisch zusammengehörend gruppiert. So wird eine Datenbank, zu biomedizinischen Themen ein festsstehendes Vokabular enthalten, anhand dessen Dokumente als thematisch ähnlich bzw. zusammengehörend identifiziert werden können. In einer Bilddatenbank (z.B. für die Zwecke einer Film-/Fotoagentur) wird eine solch thematische Abgrenzung schwerer zu definieren sein.

• Für die umfassende Indexierung von Bildern müssen Algorithmen gefunden werden, die alle möglichen Darstellungsvarianten eines Bildes (z.B. unterschiedliche Perspektiven) abbilden.