Eigengesichter

Eigengesichter (auch engl. Eigenfaces genannt) sind das Resultat eines Verfahrens zur automatisierten Gesichtserkennung. Als Methode des maschinellen Sehens ermöglichen Eigengesichter die Erkennung von einer vorab trainierten Menge menschlicher Identitäten in Echtzeit – verlangen jedoch ein sehr hohes Maß an Homogenität in Bezug auf Lichtverhältnisse, Größe der Bilder, Rotation und Skalierung des Gesichts. Aufgrund dieser hohen Sensibilität für Variation zwischen Trainingsdatensatz und tatsächlich zu klassifizierendem Gesicht werden Eigengesichter in der Praxis immer seltener zur Gesichtserkennung verwandt. Das 1991 entwickelte Verfahren gilt als die erste vollautomatisierte Gesichtserkennungstechnologie und stellte die Grundlage für eine Vielzahl an Weiterentwicklungen, industriellen Anwendungen und Inspirationen für alternative Ansätze dar. Die Methode basiert auf der Hauptkomponentenanalyse und fällt daher, im Gegensatz zu moderneren Verfahren mittels Convolutional Neural Networks, in die Kategorie des unüberwachten Lernens.

Geschichte des Verfahrens

Grundlegende Entwicklung

Ein Kernproblem des maschinellen Sehens ist, dass ein Bild mit den Abmessungen $M\times N$ als Vektor in einem hochdimensionalen Raum mit $MN$ Dimensionen betrachtet werden kann und diese immense Zahl an Freiheitsgraden (es gibt bereits $10^{32}$ graustufige 8-bit Bilder der Größe $100\times 100$ Pixel) Objekterkennung rein statistisch zu einem sehr schwierigen Problem macht. Die Hauptkomponentenanalyse (PCA, engl. Principal Component Analysis) ist eine Methode, um einen kleinstmöglichen vektoriellen Unterraum zu finden, der die größtmögliche Menge an Varianz in den Daten repräsentiert und redundante Korrelationen eliminiert. Auf der Suche nach einer kompakteren Repräsentation von Bildern von Gesichtern, benutzten Sirovich und Kirby 1987 erstmals die Hauptkomponentenanalyse, um mithilfe der wichtigsten Hauptkomponenten als Basisvektoren eine geringer dimensionale Repräsentation zu erzeugen, deren Linearkombination die ursprünglichen Bilder effektiv rekonstruieren konnte. Dabei werden mittels PCA die Richtungen der größten Varianz extrahiert, indem die Eigenvektoren und Eigenwerte der Kovarianzmatrix von der Wahrscheinlichkeitsverteilung über den hochdimensionalen Raum an möglichen Gesichtsbildern berechnet wird (vereinfacht gesagt die charakteristischsten Features der jeweiligen Gesichter). Vier Jahre später hatten Turk und Pentland das Verfahren weiterentwickelt, sodass Gesichter annähernd in Echtzeit klassifiziert und kategorisiert werden konnten, was einen Durchbruch in der Gesichtserkennungstechnologie darstellte. Im Allgemeinen ist die Berechnung der Eigenvektoren der Korrelationsmatrix sehr zeitintensiv, da die Größe dieser quadratischen Matrix von der Bildqualität abhängt. Entscheidend für die Echtzeit-Berechnung war, dass Turk und Pentland eine Möglichkeit fanden die Eigenvektoren dieser hochdimensionalen Korrelationsmatrix zu berechnen, indem sie, die Eigenvektoren einer verwandten Matrix berechneten, deren Größe nur mit der Menge an Bildern in dem Datenset skaliert (Details im Abschnitt Beschreibung des Verfahrens).

Weiterentwicklungen

Das ursprüngliche Verfahren hat eine Reihe an offensichtlichen Schwächen (Details weiter unten), die durch Verbesserungen zu kompensiert gesucht wurden. Es werden exemplarisch genannt:

• Pentland et al. stellten 1994 mit View-Based Eigenfaces einen Ansatz vor, der separate Eigenräume für unterschiedliche mimische Ausdrücke von Gesichtern erstellt, damit die Gesichtserkennung nicht auf neutrale Ausdrücke beschränkt bleibt.
• In derselben Arbeit wurde ein modularer Eigenfeature Framework beschrieben, der unterschiedliche Eigenräume für bestimmte Komponenten des Gesichts berechnet und die resultierenden Eigennasen, Eigenaugen und weitere Features benutzt um eine „grobe“ Eigengesichtrepräsentation zu verfeinern.
• Um Klassifizierung von Gesichtern zu optimieren (anstatt maximal kompakte Repräsentationen zu erzeugen), können Fishergesichter (engl. Fisherfaces) anstatt von Eigengesichtern verwandt werden – basierend auf Linear Discriminant Analysis.
• Local Binary Patterns Histograms (LBPH). Eigenfaces und Fisherfaces sind stark abhängig von den Lichtverhältnissen. Dieser Nachteil wird mit Hilfe der LBPH-Gesichtserkennung überwunden.

Software

In der freien Software-Bibliothek zur Bildverarbeitung OpenCV sind Eigenfaces, Fisherfaces und LBPH implementiert.

Beschreibung des Verfahrens

Eigengesichter werden erzeugt mittels der Hauptkomponentenanalyse (PCA).

Anleitung zur praktischen Implementation

Angenommen, man hat einen Datensatz mit $K=16$ Bildern von Gesichtern, sodass jedes Bild die Abmessungen $M\times N$ hat (beispielsweise $M=N=300$, also besteht jedes Bild aus $90.000$ Pixeln). Damit die Methodik funktioniert, müssen die Bilder unter ähnlichen Lichtverhältnissen aufgenommen worden sein und dieselben Bestandteile (Auge, Nase, Mund etc.) an denselben Positionen liegen. Dann ist die Prozedur wie folgt:

1. Die einzelnen Bilder $I_{1},...,I_{K}$ werden von einer Matrix zu einem Vektor mit 90.000 Dimensionen umgeformt, sodass $I_{i}\in \mathbb {R} ^{MN}\forall i\leq K$.

2. Es wird ein Durchschnittsgesicht ${\bar {I}}$ aus dem gesamten Trainingsdatensatz berechnet:

${\bar {I}}={\frac {1}{K}}\sum _{i=1}^{K}I_{i}$.

3. Dieses Durchschnittsgesicht wird von jedem Bild aus dem Trainingsdatensatz abgezogen:

$\Phi _{i}=I_{i}-{\bar {I}}$.

4. Nun konkateniert man die Differenzgesichter $\Phi _{i}$ zu einer Matrix $A=[\Phi _{1}\Phi _{2}\cdots \Phi _{K}]\in \mathbb {R} ^{MN\times K}$.

5. Die Kovarianzmatrix $C$ wird berechnet:

$C=AA^{T}$

Nun speichert $C\in \mathbb {R} ^{MN\times MN}$ auf der Hauptdiagonalen die Varianzen der einzelnen Pixel über den gesamten Datensatz und abseits der Hauptdiagonalen an Position $i,j$ die Kovarianz von Pixel $i$ mit Pixel $j$ über den gesamten Datensatz.

6. Als nächstes berechnet man die Eigenvektoren und Eigenwerte der Kovarianzmatrix $C$. Die Eigenvektoren der Kovarianzmatrix $C$ haben die gleiche Dimensionalität wie die Originalbilder. Turk und Pentland nannten sie wegen ihres gesichtsähnlichen Aussehens Eigengesichter.

7. Die Eigenvektoren werden absteigend nach der absoluten Größe der Eigenwerte sortiert, sodass die ersten Eigenvektoren die meiste Varianz erfassen. Die Menge $k<K$ der berücksichtigten Eigengesichter wird nun recht willkürlich auf Basis eines Schwellenwertes für die kumulierte erklärte Varianz getroffen.

8. Die Eigengesichter können nun benutzt werden, um bekannte oder neue Gesichter kompakt zu repräsentieren und später zu rekonstruieren oder um die Identität einer Person zu bestimmen.

Geschwindigkeitsproblematik

Das Berechnen der Eigenvektoren aus $C$ ist in der Regel aus zwei Gründen nicht ohne Weiteres möglich. Erstens: Da $C\in \mathbb {R} ^{MN\times MN}$, erhält man schon bei Bildern der Größe $300\times 300$ Pixeln eine Kovarianzmatrix der Größe $90.000$ erzeugt, dessen Eigenvektoren sich nicht in zufriedenstellender Zeit berechnen lassen. Zweitens gilt im Allgemeinen, dass $\mathrm {rang} (C)=\mathrm {rang} (AA^{T})=\mathrm {rang} (A)\leq \min\{MN,K\}$. Weil nun im speziellen Fall der Berechnung von Eigengesichtern in der Regel $K<MN$ gilt, das Trainingsset also weniger Bilder als jedes Bild Pixel enthält, hat $C$ keinen vollen Rang und dementsprechend sind einige Eigenwerte gleich Null. In der Regel gibt es exakt $K-1$ tatsächliche Eigenvektoren. Statt diese nun mit extremen Rechenaufwand anhand von $C$ zu berechnen, benutzten Turk and Pentland einen Trick, der Echtzeit-Lokalisierung und Erkennung von Gesichtern ermöglicht: Man berechnet die $K-1$ Eigenvektoren einer neuen Matrix $L$, die wie folgt definiert ist:

$L:=A^{T}A\in \mathbb {R} ^{K\times K}$

Die Eigenvektoren von $L$ lassen sich in einem Bruchteil der Zeit berechnen, da $L$ viel kleinere Dimension als $C$ hat. Bei einem Trainingsset von $K=16$ Bildern der Größe $300\times 300$ hat $L$ nur noch die Größe $16\times 16$, anstatt der ursprünglichen Größe von $90.000\times 90.000$. Die Berechnung der Eigenvektoren von $C$ auf $L$ zu verlagern gilt aufgrund des Folgenden:

Sei die Eigenwertzerlegung von $C$, gegeben durch

$Cv_{i}=AA^{T}v_{i}=\lambda _{i}v_{i}$

gesucht. Weil $AA^{T}\in \mathbb {R} ^{MN\times MN}$ eine zu große Matrix ist, betrachten wir stattdessen die Eigenwertzerlegung von $L$:

$Lu_{i}=A^{T}Au_{i}=\lambda _{i}u_{i}$

Bei linksseitiger Multiplikation der Gleichung mit $A$ ergibt sich

$AA^{T}Au_{i}=\lambda _{i}Au_{i}$

Sei nun $v_{i}:=Au_{i}$, so ergibt sich aus der Eigenwertzerlegung von $L$ eindeutig die gesuchte Eigenwertzerlegung von $C$. Die somit erhaltenen Vektoren $v_{i}$ sind die Eigenvektoren von $C$, wobei uns nur die $K'$ $v$'s mit den höchsten Eigenwerten interessieren. Die $u$'s müssen orthonormal sein, d. h. sie müssen noch normalisiert werden.

Interpretation der Eigengesichter

Eigengesichter-Beispiele generiert von einer großen Datenbank

Die Eigengesichter sind die resultierenden Eigenvektoren $v_{i}$ der Korrelationsmatrix $C$. Eigengesichter sind generische Gesichter in dem Sinne, dass tatsächliche Gesichter durch Linearkombination der Eigengesichter rekonstruiert werden können. Bei einem hinreichend großen Datensatz könnte also jedes menschliche Gesicht durch eine Kombination von diesen standardisierten Gesichtern dargestellt werden. Anhand der rechterhand dargestellten Eigengesichter wird deutlich, dass verschiedene Eigengesichter verschiedene Eigenschaften (features) der Trainingsbilder encodieren. Während die oberen Eigengesichter Teile der Frisur widerspiegeln, repräsentiert das Gesicht unten links die Ausleuchtung des Hintergrunds und das Gesicht unten rechts die Richtung des Lichteinfalls.

Um die Eigengesichter zu visualisieren, müssen sie zunächst von Vektor- zu Matrixnotation umgewandelt werden. Es ist üblich, die Eigengesichter nach dem Absolutbetrag der zugehörigen Eigenwerte $\lambda _{i}$ zu ordnen, sodass die ersten Eigengesichter die Positionen größter Varianz darstellen und die Relevanz der folgenden Eigengesichter graduell abfällt. Mathematisch gesehen wird durch PCA das Koordinatensystem so rotiert, dass die Achsen des neuen Koordinatensystems (die Eigengesichter) in Richtung der größten Varianz der durch die Trainingsdaten gegebenen Mannigfaltigkeit liegt.

Kompression und Rekonstruktion von Gesichtern

Eigengesichter ermöglichen es, Bilder in sehr kompakter Form zu speichern, indem jedes Trainingsbild in den durch die Eigengesichter aufgespannten Eigenraum projiziert wird. Dies kann durch eine simple Multiplikation des Bildvektors mit der Eigengesichtermatrix erreicht werden und resultiert in einem Vektor der Länge $K$ anstatt der ursprünglichen Matrix der Größe $M\times N$. Da in der Regel sogar nur auf die $k<K$ wichtigsten Eigengesichter projiziert wird, ist die tatsächliche Repräsentation eines Bildes noch kompakter. Die tatsächlichen Trainingsbilder können nun durch eine Linearkombination der $k<K$ wichtigsten Eigengesichter rekonstruiert werden. Dabei verkleinert sich der Rekonstruktionsfehler je mehr Eigengesichter zur Rekonstruktion verwandt werden. Beispielsweise könnte für das erste Trainingsbild $\Phi _{i}$ gelten: $\Phi _{i}=0.15v_{1}+0.42v_{2}+...+0.2v_{k}$ (also 15 % des ersten Eigengesichts plus 42 % des zweiten und so weiter).

Die nebenstehende Grafik (folgt zeitnah) verdeutlicht den Einfluss einer wachsenden Zahl zur Rekonstruktion verwandter Eigengesichter. In jeder Spalte wurde versucht das gleiche Bild zu rekonstruieren. In der ersten Zeile wurde dafür nur das erste Eigengesicht verwandt, in der zweiten Zeile die erste 5 Eigengesichter, in der dritten Zeile die ersten 10 Eigengesichter und in der letzten Zeile wurden alle Eigengesichter verwandt. Obwohl die Gesichter weiter unten besser zu erkennen sind, fällt selbst in diesem Beispiel auf, dass der Rekonstruktionsfehler schnell einen Sättigungspunkt erreicht.

Eigengesichter zur Identitätserkennung

Eigengesichter können auf sehr elegante Art und Weise zur Erkennung von vorab trainierten Identitäten verwandt werden. Dies geschieht, indem eine dem Algorithmus unbekannte Aufnahme einer bekannten Person in den durch die Eigengesichter erzeugten Eigenraum projiziert wird. Der resultierende Vektor kann nun mittels klassischer, vektorieller Abstandsmessung (z.Bsp. Euklidische Norm) mit allen Bildern aus der Trainingsdatenbank verglichen werden. Mittels K-Nächste-Nachbarn oder ähnlichen Klassifikationsverfahren kann dann die Identität der unbekannten Aufnahme bestimmt werden.

Verallgemeinerung von Eigengesichtern zu Eigenbildern

Das Konzept von Eigengesichtern lässt sich problemlos verallgemeinern auf alle andere Arten von Bildern (Eigenbilder, englisch: eigenimages). Der Begriff Eigengesichter hat sich nur etabliert aufgrund der Tatsache, dass die erste mittels Eigenbilder untersuchte Anwendung die Erkennung von Gesichtern war. Beispielsweise können aus einer Menge an Bildern, die dasselbe Objekt aus verschiedenen Blickwinkeln, Distanzen und Lichtverhältnissen zeigt, die Eigenbilder extrahiert werden, um eine möglichst transformationsinvariante Objektrepräsentation zu erzeugen, die dann für top-down Objekterkennungsalgorithmen wie Template Matching oder Drahtgittermodelle benutzt werden kann. Ein anderes Beispiel wäre eine Sequenz an Bildern, die zeigt wie eine beobachtete, statische Szene sich aufgrund von Mikrosakkaden auf der Retina hin und her bewegt. Auch hier zeigen die Eigenbilder die besonders invarianten Bestandteile der Szene. Weitere Anwendungen von Eigenbildern sind im Lippenlesen, in Sprecherauthentifizierung, Bildgebenden Verfahren oder Handschrifterkennung.

Zusammenfassung

Pro

• Der Trainingsprozess ist vollautomatisch, unüberwacht und simpel zu implementieren.
• Sobald der Trainingsprozess abgeschlossen ist, kann Gesichtserkennung in Echtzeit erfolgen.
• Eigengesichter können mit großen Datenbanken an Trainingsbildern umgehen (scalability).
• Eigengesichter sind optimal (in Bezug auf Varianz) komprimierte Repräsentationen von hochdimensionalen Bildern von Gesichtern.

Kontra

• Hohe Sensibilität für Variation in Lichtverhältnissen, Rotation und Skalierung des Gesichts, Gesichtsausdruck, Verdeckungen und Größe des Bildes. Dementsprechend müssen die Bedingungen unter denen die Bilder aufgenommen werden, sehr präzise kontrolliert werden.
• In praktischen Anwendungen repräsentieren die ersten Eigengesichter in der Regel Variation in den Lichtverhältnissen und nicht Variation in den Gesichtern selbst. Um die Präzision des Algorithmus zu verbessern, werden oft die ersten 3 Eigengesichter ignoriert.