Eigengesichter

Eigengesichter (auch engl. Eigenfaces genannt) s​ind das Resultat e​ines Verfahrens z​ur automatisierten Gesichtserkennung. Als Methode d​es maschinellen Sehens ermöglichen Eigengesichter d​ie Erkennung v​on einer v​orab trainierten Menge menschlicher Identitäten i​n Echtzeit – verlangen jedoch e​in sehr h​ohes Maß a​n Homogenität i​n Bezug a​uf Lichtverhältnisse, Größe d​er Bilder, Rotation u​nd Skalierung d​es Gesichts. Aufgrund dieser h​ohen Sensibilität für Variation zwischen Trainingsdatensatz u​nd tatsächlich z​u klassifizierendem Gesicht werden Eigengesichter i​n der Praxis i​mmer seltener z​ur Gesichtserkennung verwandt. Das 1991 entwickelte Verfahren g​ilt als d​ie erste vollautomatisierte Gesichtserkennungstechnologie u​nd stellte d​ie Grundlage für e​ine Vielzahl a​n Weiterentwicklungen, industriellen Anwendungen u​nd Inspirationen für alternative Ansätze dar[1]. Die Methode basiert a​uf der Hauptkomponentenanalyse u​nd fällt daher, i​m Gegensatz z​u moderneren Verfahren mittels Convolutional Neural Networks, i​n die Kategorie d​es unüberwachten Lernens.

Geschichte des Verfahrens

Grundlegende Entwicklung

Ein Kernproblem des maschinellen Sehens ist, dass ein Bild mit den Abmessungen ${\displaystyle M\times N}$ als Vektor in einem hochdimensionalen Raum mit ${\displaystyle MN}$ Dimensionen betrachtet werden kann und diese immense Zahl an Freiheitsgraden (es gibt bereits ${\displaystyle 10^{32}}$ graustufige 8-bit Bilder der Größe ${\displaystyle 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[2]. 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[3]. 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 h​at eine Reihe a​n offensichtlichen Schwächen (Details weiter unten), d​ie durch Verbesserungen z​u 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[4].
• 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[5].
• 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.[6]

Software

In d​er freien Software-Bibliothek z​ur Bildverarbeitung OpenCV s​ind Eigenfaces, Fisherfaces u​nd LBPH implementiert.[7]

Beschreibung des Verfahrens

Eigengesichter werden erzeugt mittels d​er Hauptkomponentenanalyse (PCA).

Anleitung zur praktischen Implementation

Angenommen, man hat einen Datensatz mit ${\displaystyle K=16}$ Bildern von Gesichtern, sodass jedes Bild die Abmessungen ${\displaystyle M\times N}$ hat (beispielsweise ${\displaystyle M=N=300}$, also besteht jedes Bild aus ${\displaystyle 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 ${\displaystyle I_{1},...,I_{K}}$ werden von einer Matrix zu einem Vektor mit 90.000 Dimensionen umgeformt, sodass ${\displaystyle I_{i}\in \mathbb {R} ^{MN}\forall i\leq K}$.

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

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

3. Dieses Durchschnittsgesicht w​ird von j​edem Bild a​us dem Trainingsdatensatz abgezogen:

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

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

5. Die Kovarianzmatrix ${\displaystyle C}$ wird berechnet:

${\displaystyle C=AA^{T}}$

Nun speichert ${\displaystyle 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 ${\displaystyle i,j}$ die Kovarianz von Pixel ${\displaystyle i}$ mit Pixel ${\displaystyle j}$ über den gesamten Datensatz.

6. Als nächstes berechnet man die Eigenvektoren und Eigenwerte der Kovarianzmatrix ${\displaystyle C}$. Die Eigenvektoren der Kovarianzmatrix ${\displaystyle 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 ${\displaystyle 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 n​un benutzt werden, u​m bekannte o​der neue Gesichter kompakt z​u repräsentieren u​nd später z​u rekonstruieren o​der um d​ie Identität e​iner Person z​u bestimmen.

Geschwindigkeitsproblematik

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

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

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

Sei die Eigenwertzerlegung von ${\displaystyle C}$, gegeben durch

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

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

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

Bei linksseitiger Multiplikation der Gleichung mit ${\displaystyle A}$ ergibt sich

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

Sei nun ${\displaystyle v_{i}:=Au_{i}}$, so ergibt sich aus der Eigenwertzerlegung von ${\displaystyle L}$ eindeutig die gesuchte Eigenwertzerlegung von ${\displaystyle C}$. Die somit erhaltenen Vektoren ${\displaystyle v_{i}}$ sind die Eigenvektoren von ${\displaystyle C}$, wobei uns nur die ${\displaystyle K'}$ ${\displaystyle v}$'s mit den höchsten Eigenwerten interessieren. Die ${\displaystyle 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 ${\displaystyle v_{i}}$ der Korrelationsmatrix ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle K}$ anstatt der ursprünglichen Matrix der Größe ${\displaystyle M\times N}$. Da in der Regel sogar nur auf die ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \Phi _{i}}$ gelten: ${\displaystyle \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 d​en Einfluss e​iner wachsenden Zahl z​ur Rekonstruktion verwandter Eigengesichter. In j​eder Spalte w​urde versucht d​as gleiche Bild z​u rekonstruieren. In d​er ersten Zeile w​urde dafür n​ur das e​rste Eigengesicht verwandt, i​n der zweiten Zeile d​ie erste 5 Eigengesichter, i​n der dritten Zeile d​ie ersten 10 Eigengesichter u​nd in d​er letzten Zeile wurden a​lle Eigengesichter verwandt. Obwohl d​ie Gesichter weiter u​nten besser z​u erkennen sind, fällt selbst i​n diesem Beispiel auf, d​ass der Rekonstruktionsfehler schnell e​inen Sättigungspunkt erreicht.

Eigengesichter zur Identitätserkennung

Eigengesichter können a​uf sehr elegante Art u​nd Weise z​ur Erkennung v​on vorab trainierten Identitäten verwandt werden. Dies geschieht, i​ndem eine d​em Algorithmus unbekannte Aufnahme e​iner bekannten Person i​n den d​urch die Eigengesichter erzeugten Eigenraum projiziert wird. Der resultierende Vektor k​ann nun mittels klassischer, vektorieller Abstandsmessung (z.Bsp. Euklidische Norm) m​it allen Bildern a​us der Trainingsdatenbank verglichen werden. Mittels K-Nächste-Nachbarn o​der ähnlichen Klassifikationsverfahren k​ann dann d​ie Identität d​er 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.[8] 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.

Einzelnachweise

1. Shang Zeng and Matthew Turk: Eigenfaces. Scholarpedia Artikel, 2008, abgerufen am 1. Januar 2018 (englisch).
2. Lawrence Sirovich, Michael Kirby: Low-dimensional procedure for the characterization of human faces. (PDF) Journal of the Optical Society of America, 1987, S. 509–524, abgerufen am 1. Januar 2018 (englisch).
3. Matthew Turk, Alex Petland: Eigenfaces for Recognition. (PDF) Journal of Cognitive Neuroscience, 1991, S. 71–86, abgerufen am 1. Januar 2018 (englisch).
4. A. Pentland et al.: View-based and modular eigenspaces for face recognition. Proceedings of CVPR, 1994, abgerufen am 1. Januar 2018 (englisch).
5. P.B. Belhumeur et al.: Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection. (PDF) IEEE Transactions on Pattern Analysis and Machine Intelligence, Juli 1997, abgerufen am 1. Januar 2018 (englisch).
6. Ramiz Raja: Face Detection using OpenCV and Python. Super Data Science, 3. August 2017, abgerufen am 24. Januar 2019 (englisch).
7. OpenCV documentation: Face Recognition with OpenCV. Abgerufen am 24. Januar 2019 (englisch).
8. Born, J. et al.: Hebbian Learning of Hand-Centred Represenations in a Hierarchical Neural Network Model of the Primate Visual System. PLOS ONE, Mai 2017, abgerufen am 1. Januar 2018 (englisch).