Lineare Unterraumtechniken zur automatischen

Transcrição

Bachelorarbeit
Lineare Unterraumtechniken zur
automatischen Gesichtserkennung
Andreas Pawelko
Oktober 2012
Korrigierte Version
Gutachter:
Prof. Dr.-Ing. Gernot A. Fink
Dipl.-Inf. Leonard Rothacker
Technische Universität Dortmund
Fakultät für Informatik
Mustererkennung in Eingebetteten Systemen (LS-12)
http://ls12-www.cs.tu-dortmund.de
Inhaltsverzeichnis
1 Einleitung
1.1
1
Verfahren zur Gesichtserkennung . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.1
Merkmalsbasierte Verfahren . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Holistische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.3
Vergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2 Grundlagen
2.1
2.2
2.3
2.4
9
Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1
Transformationsmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2
Eigenwertproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3
Lösung des Eigenwertproblems . . . . . . . . . . . . . . . . . . . . . 11
Stochastik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1
Korrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2
Mischverteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Optimierung
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1
Vektorquantisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2
EM-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3
Lagrange-Multiplikator . . . . . . . . . . . . . . . . . . . . . . . . . 20
Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Verfahren
3.1
3.2
3.3
9
23
Allgemeines Gesichtserkennungssystem . . . . . . . . . . . . . . . . . . . . . 23
3.1.1
Unterraumkonzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2
Klassifikator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.3
Distanzmetriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Hauptkomponentenanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1
Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2
Eigenfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3
Projektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Lineare Diskriminanzanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 32
i
ii
INHALTSVERZEICHNIS
3.4
3.5
3.3.1
Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2
Direkte Fisherfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.3
Indirekte Fisherfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.4
PCA+LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Hauptkomponentenmischung . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.1
Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.2
Optimierungsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3
Gewichte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.4
Modellparameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.5
Merkmalsvektoren zur Klassifikation . . . . . . . . . . . . . . . . . . 41
4 Versuche
4.1
45
FERET-Programm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1
Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.2
FERET-Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.3
Datenbank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2
Normalisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3
Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4
Standard-Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.5
4.6
4.4.1
Durchführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.2
Evaluierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Parameteroptimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5.1
Bildgröße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5.2
Dimensionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5.3
Distanzmetriken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5.4
Kombination bester Parameter . . . . . . . . . . . . . . . . . . . . . 64
5 Abschluß
67
Abbildungsverzeichnis
69
Literaturverzeichnis
76
Kapitel 1
Einleitung
Seit Jahrzehnten beschäftigt sich die Wissenschaft mit Gesichtserkennung. Besonders im
Bereich der Computervision, der Neurowissenschaft und der Psychologie werden durch
intensive Forschung heute noch bedeutende Fortschritte erzielt. Diese führen dazu, dass
die maschinelle Gesichtserkennung zunehmend an Beliebtheit gewinnt und immer mehr
Anwendung findet.
Die Gesichtserkennung zählt zu den biometrischen Verfahren und bietet in diesem
Bereich eine Reihe wichtiger Vorteile gegenüber anderen Techniken. Im Unterschied zur
Überprüfung des Fingerabdrucks oder der Iriserkennung ist die Gesichtserkennung eine
passive und nicht intrusive Identifizierungstechnik. Ihre Anwendung kann nämlich bereits
aus der Ferne stattfinden, ohne dass die betroffene Person einem Gerät direkt ausgesetzt
wird und sie sich dadurch unwohl oder bloßgestellt fühlt. Ein anderer Grund der Popularität der Gesichtserkennung ist, dass ihre Anwendung genau der Art und Weise entspricht,
wie sich Menschen selbst im Alltag untereinander identifizieren - und zwar visuell. Zudem
ist für die Gesichtserkennung kein großer technischer Aufwand notwendig, denn es reicht
bereits eine einfache Kamera aus, statt teurer Scanner oder Spezialgeräte.
Aus diesen Gründen besitzt die Gesichtserkennung heute ein weitreichendes Spektrum
von Anwendungsgebieten. Einige davon sind:
• Einfache und schnelle Autorisierung und Authentifizierung (statt PIN-Codes, Karten
usw.).
• In der Kameraüberwachung von Straßen, Bahnhöfen, Zügen und Büssen zur Reduzierung von Gewalt und Vandalismus oder zum Aufspühren vermisster Personen.
• Bei der Überwachung von Anlagen und Gebäuden zum Durchsetzen von Hausverboten oder Finden von Dieben (z.B. wird in einigen Fußballstadien Gesichtserkennung
verwendet, um bekannten Hooligans den Eintritt zu verweigern (vgl. [wSt12])).
• In der Forensik zum Aufspühren von Verbrechern aus Polizei-Datenbanken.
1
2
KAPITEL 1. EINLEITUNG
• Unterstützung der Kriminalitätsbekämpfung im Bereich des Terrorismus und Drogenschmuggels (z.B. Identifizierung verdächtiger Personen am Flughafen).
• Als Designkomponente für intelligente und ubiquitäre Systeme (Intelligentes Haus,
Multimedia-Anwendungen usw.).
Im Bereich der Gesichtserkennung wird viel geforscht, denn es ist eine große Herausfor-
derung ein leistungsstarkes und zuverlässiges Gesichtserkennungssystem zu entwerfen. Der
Grund dafür ist, dass das Gesicht kein invariantes Identifizierungsmerkmal darstellt. So
kann sich ein menschliches Gesicht bereits innerhalb kürzester Zeit - von einem Tag auf den
anderen - ändern. Eine solche Veränderung wichtiger Gesichtscharakteristiken kann dazu
führen, dass ein gleiches Gesicht nicht mehr richtig erkannt wird. Beispiele für solche Fälle
sind Gesichtsaccessoires (Brille, Bart usw.), variierende Beleuchtungsstärken, wechselnde
Gesichtausdrücke oder Gesichtsdrehungen.
Unter den Gesichtserkennungstechniken gehören Unterraumverfahren zu den vielversprechendsten, wie es sich in unabhängigen Tests herausstellte. Bei Unterraumverfahren
werden Gesichtsbilder als Vektoren in einen algebraischen Raum projiziert und dort anhand ihrer Abstände zueinander klassifiziert. Kommerzielle Gesichtserkennungssysteme,
die in der Praxis Anwendung finden, sind hoch-komplex und bestehen aus mehreren Einzelkomponenten. Obwohl Details zur genauen Struktur dieser Systeme vertraulich behandelt
werden, ist allgemein bekannt, dass sie meißt eine Unterraumkomponente zur Dimensionsreduktion und zum Bestimmen wichtiger Gesichtsmerkmale enthalten. Solche Systeme
übersteigen die menschliche Erkennungsfähigkeit von Gesichtern und kommen auch an die
Identifizierungsleistungen anderer biometrischer Verfahren, wie der Fingerabdrucküberprüfung oder der Iriserkennung, heran.
Im Rahmen dieser Arbeit werden drei Unterraumverfahren vorgestellt. Die ersten beiden sind die Hauptkomponentenanalyse und die lineare Diskriminanzanalyse. Beide zählen zu Meilensteinen in der Gesichtserkennung. Bei dem dritten Verfahren handelt es sich
um die Hauptkomponentenmischung. Dieses Verfahren wurde ursprünglich für die Fehlerverdeckung in Videoübertragungen entwickelt. Es wurde zwar von den Autoren in der
Gesichtserkennung erprobt, jedoch ist in der Literatur kein umfangreicher Vergleich dieses
Ansatzes zu finden (insbesondere nicht auf der FERET-Datenbank). Wir werden diese
drei Verfahren genauer analysieren, um die optimalen Arbeitsbedingungen für jedes dieser
Verfahren herauszufinden und anschließend eine Schlußfolgerung darüber zu ziehen, für
welchen Bereich der Gesichtserkennung sich das jeweilige Verfahren besonders eignet.
1.1
Verfahren zur Gesichtserkennung
Zunächst soll eine Übersicht über allgemeine Verfahren zur Gesichtserkennung gegeben
werden. Gesichtserkennungsverfahren werden grundsätzlich in drei Kategorien eingeteilt,
1.1. VERFAHREN ZUR GESICHTSERKENNUNG
3
je nach dem mit welcher Art von Bildern sie arbeiten: Techniken, die auf Intensitätsbildern
operieren, Methoden für Video-Gesichtserkennung und Verfahren, die besondere Bilder
(z.B. Infrarot-Bilder) verwenden (vgl. [JA09]).
In dieser Arbeit werden Verfahren zur Gesichtserkennung auf Intensitätsbildern betrachtet. Diese Verfahren lassen sich in zwei Grundbereiche einteilen. Zum einen gibt es
die merkmalsbasierten Verfahren, bei denen lokale Merkmale von Gesichtern gemessen
und verglichen werden. Zum anderen existieren holistische Techniken, die statt einzelner
Bereiche das gesamte Bild zur Gesichtserkennung heranziehen.
1.1.1
Merkmalsbasierte Verfahren
Merkmalsbasierte Verfahren gelten als die ersten
Ansätze zur automatischen Gesichtserkennung. Sie
arbeiten in zwei Schritten. Im ersten Schritt werden aus Bildern markante Merkmale (Mund, Augen,
Nase usw.) - meißt manuell - extrahiert. Die geometrische Lagen und Beziehungen dieser Merkmale
werden gemessen und in einem Merkmalsvektor zusammengefasst. Durch die kompakte Repräsentation in einem Merkmalsvektor wird die Problemgröße
reduziert. Im zweiten Schritt erfolgt dann mit Hilfe
von Pattern-Matching-Methoden ein Vergleich der
Merkmalsvektoren verschiedener Bilder.
Der erste Ansatz (in [Kan73], 1973) bestand darin, mit Methoden der Bildbearbeitung einen Merk- Abbildung 1.1: 35 manuell idenmalsvektor zu erstellen, der insgesamt 16 Anga- tifizierte
ben zu Distanzen, Flächen und Winkeln eines Ge-
Gesichtsmerkmale
(aus
[IJCY96]).
sichts enthielt. Um dann zu klassifizieren, wurde ein
Pattern-Matching mit der euklidischen Distanz durchgeführt. Für 20 Personen mit jeweils
2 Bildern, führte das Verfahren zu Erkennungsraten von bis zu 75%. Eine Erweiterung dieses Ansatzes ([BP93], 1993) auf einen Merkmalsvektor mit 35 geometrischen Parametern
erreichte eine Erkennungsrate von 90% für 47 Personen mit jeweils 4 Bildern. Ein solcher
Merkmalsvektor aus 35 Parametern ist in Abbildung 1.1 veranschaulicht. Man erkennt,
dass geometrische Beziehungen von Gesichtsmerkmalen gespeichert werden. Verbesserungen solcher Ansätze, die auf Merkmalsvektoren arbeiten, können beispielsweise mit dem
Gebrauch von dynamischen Templates (s. [YCH89]) oder Hough-Transformationen (s.
[mn85]) erreicht werden.
Einen anderen Bereich merkmalsbasierter Gesichterkennungsverfahren stellen Methoden dar, die auf Profilen von Gesichtern operieren ([LL99]). Dabei werden Informationen
4
zu Gesichtsprofilen in einen Vektor geschrieben, der dann nach einem Distanzmaß mit
anderen Profil-Vektoren verglichen wird. Auf einer Datenbank von 112 Personen wurden
Erkennungsraten von 96% berichtet.
Eine weitere, sehr bekannte Methode ist der Elastic Bunch Graph Matching (EBGM)
Algorithmus (s. [WFKvdM97]). Dabei werden auf jedem Bild charakteristische Punkte
(wie Mund, Augen, Nase) ausgewählt. Anschließend extrahiert man Gabor Jets aus jedem
dieser Punkte. Aus den gewonennen Gabor Jets wird dann ein sogenannter Gesichtsgraph
generiert. Ein Gesichtsgraph besteht aus den charakterisitschen Punkten als Knoten, die
mit ihren Gabor Jets beschriftet werden, und eine Kante wird zwischen diesen Punkte erstellt und mit der Distanz der Punkte zueinander gewichtet. Die Darstellung eines Gesichts
als Graph dient als eine kompaktere Repräsentation der Reduzierung der Problemgröße.
Um dann mit dem EMBG-Verfahren ein unbekanntes Gesichtsbild zu klassifizieren, wird
der Gesichtsgraph zu diesem Bild erstellt und mit den bereits erstellten Gesichtsgraphen
der Trainingsbilder verglichen. Der Ähnlichkeitsgrad zwischen zwei Graphen ist dann der
Indikator für die Zuordnung. Der EBGM-Algorithmus war in den FERET-Tests insgesamt
eines des besten Verfahren in der Kategorie der Gesichtsidentifikation (vgl. [PMRR00]),
jedoch lag der Implementierung ein holistisches Verfahren zum Aufspühren der charakteristischen Punkte zugrunde.
1.1.2
Holistische Verfahren
In diesem Abschnitt werden holistische Methoden zur Gesichtserkennung vorgestellt. Grundsätzlich wird dieser Bereich in statistische Verfahren, zu denen unter anderem lineare Unterraumtechniken gehören, und Verfahren der Künstlichen Intelligenz (KI) unterteilt.
Statistische Verfahren
Eine naheliegende statistische Methode zur Gesichtserkennung besteht darin, für die
Klassifikation eines Bildes Korrelationen zwischen den Pixelwerten des Bildes mit den Pixelwerten von Bildern aus der Datenbank direkt zu vergleichen, um so die Ähnlichkeit
der Bilder zu ermitteln ([Bar81]). Solche Ansätze haben sich als sehr intolerant gegenüber
Änderungen von Außenbedingungen im Bild (z.B. variierende Lichtstärke, Bildrotationen,
Bildhintergrund) herausgestellt. Außerdem ergeben sich direkte Nachteile aus der hohen
Dimensionalität der Bilder. Um diesen sogenannten ”Fluch der Dimensionalität” (vgl.
[Alp10], S. 170) zu umgehen, wurden zahlreiche Unterraumverfahren entwickelt. Bei Unterraumverfahren wird vor der eigentlichen Gesichtserkennung eine Dimensionsreduktion
durchgeführt, bei der unwichtige Bildinformationen entfernt werden.
5
Aufbauend auf den Arbeiten von Sirovich und Kirby ([SK87]), die mit Hilfe der Hauptkomponentenanalyse (PCA) ein Verfahren zur Bildkomprimierung entwickelt hatten, haben Turk und Pentland in [TP91b] und [TP91a] im Jahr 1991 die Eigenfaces-Methode
vorgestellt, die in Kapitel 3 dieser Arbeit ausführlicher eingeführt wird. Auf ihrer eigenen
Gesichtsdatenbank von 2500 variierenden Bildern zu 16 Personen berichteten sie Erkennungsraten zwischen 64% und 96%.
Ein anderes lineares Unterraumverfahren ist die Independent Components Analysis
(ICA) ([Com94], 1994). Während die Basisvektoren der PCA von paarweisen Zusammenhängen zwischen jeweils zwei Pixeln der Bilder abhängen, werden bei der Bestimmung der
ICA-Komponenten, Beziehungen höherer Ordnung zwischen Pixeln betrachtet. Die ICA
wurde erstmals von Bartlett et al. in der Gesichtserkennung eingesetzt ([BMS02], 2002)
und es wurden mit der ICA bessere Ergebnisse berichtet als mit der PCA. Jedoch ist trotz
vieler durchgeführter Vergleiche zwischen der ICA und der PCA nicht eindeutig, welches
Verfahren generell als besser einzustufen ist (vgl. ([DGG05]).
Einen weiteren Unterraum-Ansatz hatten Belhumeur et al. ([BHK97]) im Jahr 1997. Es
wurde argumentiert, dass bei Datenbanken, die mehrere Bilder zu einer Person enthalten,
durch die Wahl der Basisvektoren des Unterraums bei der PCA Informationen behalten werden, die nicht zur Unterscheidung von Gesichtern geeignet sind (wie z.B. Lichteinflüße oder Gesichtsausdrücke). Deswegen haben die Autoren die Fisherfaces-Methode
vorgeschlagen, die mit der linearen Diskriminanzanalyse (LDA) eine Trennung von Bildern verschiedener Personen durchführt. Kurze Zeit später wurde die LDA auf Bilder im
PCA-Unterraum angewendet. Dieser Ansatz entspricht dem PCA+LDA-Verfahren, das
in Kapitel 3.3.4 vorgestellt wird. Auf einer Datenbank von 330 verschiedenen Bildern zu
5 Personen wurden bessere Erkennungsraten erreicht als mit dem Eigenfaces-Verfahren.
Jedoch haben Experimente von [MK01] ergeben, dass bei kleinen Trainingsets PCA besser als LDA sein kann. Außerdem kann die PCA für Datenbanken, die wenige Bilder pro
Person enthalten, höhere Erkennungsraten als die LDA liefern. Jeweils drei Basisvektoren
des PCA-, ICA- sowie LDA-Unterraums sind in Abbildung 1.2 visualisiert. Zu erkennen
sind die unterschiedlichen Annahmen, die der Wahl der Basen jedes Verfahrens zugrunde
liegen.
Mit der Argumentation, dass in einem Unterraum sich die Projektionen von verschiedenen Individuen überlappen können und so eine korrekte Klassifikation nicht möglich
wäre, schlugen Pentland et al. in [MNP96] ein probabilistisches Verfahren vor, das zwei
Klassen von Differenzbildern als arithmetische Differenz zwischen den Pixelwerten zweier
Bilder definiert. Es werden intrapersonelle Bilder (Differenzbilder zwischen Bildern der
selben Person) und extrapersonelle Bilder (Differenzbilder zwischen Bildern verschiedener
Personen) berechnet. Mit Hilfe der Regel von Bayes werden Differenzbilder in Klassen eingeordnet, sodass ein binäres Klassifikationsproblem entsteht, das man anschließend mit
6
PCA
ICA
LDA
Abbildung 1.2: Komponenten der PCA, ICA und einer PCA-basierten LDA (aus [DGG05]).
a-posteriori Wahrscheinlichkeiten löst. In den FERET-Tests war dieses Verfahren eines
der besten Verfahren (vgl. [PMRR00]).
Bis heute wurden vielerlei Verbesserungen der ursprünglichen PCA- und LDA-Ansätze
(s. [JA09]) entwickelt. Eine davon ist beispielsweise die MPC (nach [TC02a]). Es ist eine
lineare Erweiterung der PCA, die mehrere PCA-Unterräume in einem Modell kombiniert
und dadurch eine genauere Repräsentation von Bildern anstrebt. Die MPC wird in dieser
Arbeit vorgestellt.
Neben den linearen Unterraumtechniken gibt es zahlreiche nicht-lineare Verfahren. Bei
diesen Ansätzen wird argumentiert, dass lineare Verfahren nur ”oberflächliche” Strukturen betrachten und nicht-lineare Zusammenhänge, die insbesondere bei Bildern mit
variierenden Lichteinflüßen, Gesichtsausdrücken und Aufnahmewinkeln vorhanden sein
sollen, außer Acht lassen. Ein Beispiel eines nicht-linearen Unterraumverfahrens ist das
Laplacianfaces-Verfahren ([HYH+ 05]). Eines der Probleme nicht-linearer Unterraumverfahren besteht darin herauszufinden, auf welcher Mannigfaltigkeit die nicht-linearen Eigenschaften der Bilder liegen (vgl. z.B. [HYH+ 05]).
KI-Verfahren
KI-Verfahren orientieren sich an Methoden der künstlichen Intelligenz. Die wichtigsten
Konzepte stellen dabei künstliche neuronale Netze dar. Diese sind eine Nachbildung von
Nervenvernetzungen des Gehirns und sind Modelle zur vereinfachten Informationsverar-
7
beitung. Ein künstliches neuronales Netz besteht aus mehreren Knoten, die zusammen
eine Struktur für automatisches Lernen bilden.
Einer der ersten Ansätze verwendete ein auto-assoziatives neuronales Netzwerk, um 50
extrahierte Hauptkomponenten einer PCA auf 5 Dimensionen zu reduzieren. Anschließend
wurde mit einem mehrschichtigen Perzeptron klassifiziert ([DY93], 1993). Die Erkennungsraten waren zwar zufriedenstellend, jedoch lag den Experimenten eine Datenbank von nur
20 Personen zugrunde, die alle unter gleichen Bedingungen fotographiert wurden.
In [LGTB97] wurde ein hybrides neuronales Netzwerk eingesetzt, das eine selbstorganisierende Karte (SOM) zur Dimensionsreduktion und ein konvolutionelles neuronales
Netzwerk zum Kompensieren von Rotationen und Skalierungen des Bildes verwendet. Auf
einer Datenbank von 400 Bildern von insgesamt 40 Personen hatte dieses Verfahren laut
den Autoren bessere Ergebnisse als das Eigenfaces-Verfahren.
Li und Yin ([LY05], 2005) zerlegten ein Bild mit einer Wavelet-Transformation in drei
Bildebenen. Auf die drei so entstandenen Bilder wurde die Fisherfaces-Methode angewendet. Anschließend vereinte man die einzelnen Klassifikationsergebnisse mit einem RBF
neuronalen Netzwerk. Laut ihren Experimenten auf einer Datenbank von 40 Personen
wurde so eine Verbesserung des reinen Fisherfaces-Verfahrens erreicht.
Gute Erkennungsraten von 98% auf Frontalbildern der FERET-Datenbank erzielten
Zhang et al. ([ZHL+ 05], 2004). Bei ihrem Ansatz wird eine Ählichkeitsfunktion trainiert,
die zu zwei Bildern die Wahrscheinlichkeit angibt, dass es sich um die selbe Person handelt. Von Gesichtsregionen werden Local Binary Pattern (LBP) Histogramme gewonnen,
aus denen dann Gesichtsmerkmale ausgesucht werden. Chi-quadratische Distanzen zwischen den LBP-Histogrammen stellen dabei Merkmale zum Unterscheiden von Gesichtern
dar. Anschließend werden mit dem AdaBoost-Lernalgorithmus die besten LBP-Merkmale
ausgewählt und die Ähnlichkeitsfunktion als Kombination der schwachen LBP-Merkmale
trainiert.
Außerdem können mit dem Support Vector Machine (SVM) Klassifikator gute Erkennungsraten erreicht werden, wie z.B. in [LWQ05]. Dabei werden Trainingsbilder als
Klassen in einen hoch-dimensionalen Raum projiziert und mit Hyperebenen in diesem
Raum werden dann unterschiedliche Klassen bestmöglich voneinander getrennt.
Hidden Markov Modelle (HMM) können ebenfalls in der Gesichterkennung eingesetzt
werden. In [SH94] wurde mit einem eindimensionalen HMM und später mit einem pseudo
zweidimensionalen HMM experementiert. Es konnten Erkennungsraten von bis zu 87%
bzw. 95% auf der ORL-Datenbank erzielt werden. Außerdem erreichte man mit eingebetteten HMM-Gesichtsmodellen ([NI99]) Erkennungsleistungen von bis zu 98% auf der
gleichen Datenbank.
8
1.1.3
Vergleich
Nun sollen Vor- und Nachteile merkmalsbasierter und holistischer Verfahren nach [JA09]
einander gegenübergestellt werden.
• Merkmalsbasierte Verfahren sind im Vergleich zu holistischen Verfahren relativ robust gegenüber variierenden Lichteinflüßen, Bilddrehungen oder Bildgrößen, da nur
die Verhältnisse zwischen Gesichtsmerkmalen betrachtet werden.
• Bei merkmalsbasierten Verfahren werden Bilder relativ kompakt als Merkmalsvektoren repräsentiert, was einen geringen Aufwand zum Vergleichen der Vektoren zur
Folge hat. Holistische Verfahren hingegen sind meißt mit einem relativ hohen Rechenaufwand verbunden.
• Es ist schwierig und aufwändig die relevanten Gesichtsmerkmale für einen Merkmalsvektor eines merkmalsbasierten Verfahrens automatisch zu lokalisieren. Diese
Merkmale müssen so gewählt werden, dass mit ihrer Hilfe eine gute Unterscheidbarkeit von Gesichtern möglich ist. Bei den meißten oben vorgestellten Verfahren
wurden die Merkmale manuell erfasst. Im Unterschied dazu arbeiten holistische Verfahren meißt vollautomatisch.
• Bei holistischen Verfahren werden Bilder als Ganzes betrachtet, statt auf ihre wichtigsten Merkmale reduziert. Dadurch wird die meißte Bildinformation behalten.
Kapitel 2
Grundlagen
Um Hintergründe und Zusammenhänge linearer Unterraumverfahren nachvollziehen zu
können, müssen zunächst einige grundlegende Aspekte in linearer Algebra, multivariater
Stochastik sowie mathematischer Optimierung verstanden werden.
Bei Unterraumverfahren wird in der Trainingsphase ein Unterraum bestimmt, in den
für die spätere Zuordnung eines Gesichtsbildes zu einer Person das Bild hineinprojiziert
wird. Die Projektion erfolgt über Transformationsmatrizen. Diese definieren den Unterraum und werden aus Eigenvektoren gebildet. Transformationsmatrizen und Eigenvektoren werden in Kapitel 2.1 beschrieben.
Eigenvektoren zur Bildung einer Transformationsmatrix werden aus einer sogenannten
Streuungsmatrix (s. Kapitel 2.2.1) extrahiert, die für eine Punktmenge in einem mehrdimensionalen Raum angibt, in Richtung welcher Dimension die größte Streuung der Punkte
vorliegt. Dabei wird angenommen, dass die Dimension mit der größten Streuung die beste
Unterscheidbarkeit der Punkte ermöglicht.
Darüberhinaus werden für das Verfahren der Hauptkomponentenmischung (MPC) zusätzlich noch Kentnisse über Mischverteilungen von Zufallsvariablen benötigt (Kapitel
2.2.2). Dazu werden in Kapitel 2.3.1 und 2.3.2 zwei unterschiedliche Möglichkeiten zum
Erstellen von Mischverteilungsmodellen aus mehreren Normalverteilungen vorgestellt. Bei
der MPC handelt es sich nämlich um einen EM-Algorithmus, der mit einer Kombination mehrerer PCA-Unterräume eine Art ”Misch-Unterraum” modelliert. Außerdem wird
für die Entwicklung des MPC-Modells die Methode des Lagrange-Multiplikators benötigt.
Diese erlaubt es Nebenbedingungen in Form von Funktionen in Optimierungsprobleme
einzubinden (s. Kapitel 2.3.3).
2.1
Algebra
In diesem Unterkapitel werden Transformationsmatrizen, Basisvektoren und Projektionen
von Vektoren in Unterräume behandelt. Dazu wird außerdem die Bedeutung und die
9
10
KAPITEL 2. GRUNDLAGEN
Berechnung von Eigenwerten und Eigenvektoren erläutert, die bei unseren Verfahren für
die Bildung von Unterräumen essenziell sind.
2.1.1
Transformationsmatrix
Bei jedem unserer Unterraumverfahren wird eine Transformationsmatrix verwendet, um
Vektoren in den Unterraum zu projizieren. Weiterhin definiert die Transformationsmatrix
den Unterraum und seine Dimensionalität.
Eine Basisrepräsentation eines Vektorraums besteht aus einer Menge sogenannter Basisvektoren. Sie spannen den Vektorraum auf und definieren seine Elemente, die Vektoren
(vgl. [Beu03], S. 54ff).
Soll nun ein Basiswechsel eines Vektors durchgeführt werden, d.h. ein Vektor soll von
einem Vektorraum in einen anderen transformiert werden, dann wird eine Transformationsmatrix benötigt. Eine Transformationsmatrix

a
 11
 ..
T = .

···
..
.

a1n

.. 
. 
am1 · · · amn
(2.1)

bildet einen Vektor von einem n-dimensionalen Vektorraum in einen m-dimensionalen
Vektorraum ab. Der resultierende Vektor wird Projektion genannt und seine Koeffizienten
sind Linearkombinationen der Zeilenvektoren von T mit Vektor v (vgl. [Beu03]). Mathematisch gesehen definiert die Transformationsmatrix T eine lineare Abbildung, weshalb
T auch Abbildungsmatrix genannt wird. Die Abbildung entspricht einer Matrixmultiplikation (vgl. [KM03], S. 52ff):
T · v = v0.
(2.2)
Dabei bestimmt die Anzahl der Zeilenvektoren der Transformationsmatrix T die Dimensionalität des abgebildeten Vektors v 0 .
2.1.2
Eigenwertproblem
Eigenvektoren sind für unsere Zwecke Komponenten von Transformationsmatrizen. Im Folgenden zeigen wir, wie aus Eigenvektoren Transformationsmatrizen entstehen können und
ein mehrdimensionaler Raum mit Hilfe von Eigenvektoren in seine einzelnen Dimensionen zerlegt werden kann, um dann mit ausgewählten Dimensionen Unterräume für unsere
Verfahren zu definieren.
Als Eigenwertproblem wird die Aufgabe der Berechnung von Eigenvektoren und Eigenwerten zu einer Matrix bezeichnet. Eigenvektoren einer Matrix T haben die Eigenschaft,
dass sich durch die Transformation mit T ihre Richtung nicht ändert, sondern nur eine Skalierung ihrer Länge stattfindet. Der Skalierungsfaktor eines Eigenvektors nach der
Transformation mit seiner Matrix T heißt Eigenwert zum Eigenvektor von T . Seien v ein
2.1. ALGEBRA
11
Eigenvektor von Transformationsmatrix T und λ der dazugehörige Eigenwert von v, dann
gilt folgender mathematischer Zusammenhang (vgl. [Jä00], S. 197f):
T ·v =λ·v
und v 6= 0.
(2.3)
Der Skalierungsfaktor λ ist für sein Eigenvektor-Matrix-Paar immer konstant, unabhängig
von der vorherigen Skalierung seines Eigenvektors.
Es kann gezeigt werden, dass zu einer symmetrischen und quadratischen n × n-Matrix
höchstens n Eigenvektoren gefunden werden können, die insbesondere orthogonal zueinander sind (vgl. [DHS01], S. 609f). Wegen der Orthogonalität stellen sie voneinander unabhängige Dimensionen dar und bilden zusammen als Basisvektoren eine Basis für einen
Vektorraum. Da jeder orthogonale Eigenvektor eine unabhängige Dimension darstellt, besteht der Vorteil der Eigenvektordarstellung eines Raums darin, durch das Weglassen von
Eigenvektoren einzelne Dimensionen zu entfernen und auf diese Weise eine lineare Dimensionsreduktion zu vollziehen.
2.1.3
Lösung des Eigenwertproblems
Dieser Abschnitt widmet sich der Berechnung von Eigenwerten und Eigenvektoren. Angefangen mit einer anschaulichen Berechnung mit Hilfe des charakteristischen Polynoms,
schließen wir mit einem praktischen Verfahren, dem QR-Verfahren, ab, welches derzeit
auch z.B. in Matlab Verwendung findet und für unsere spätere Berechnung von Eigenwerten und Eigenvektoren gebraucht wird (vgl. [QS06], S. 158ff).
Eine exakte Berechnung von Eigenwerten und Eigenvektoren findet grundsätzlich über
das charakteristische Polynom statt. Dazu geht man laut [KM03] wie folgt vor: Im ersten
Schritt berechnet man die Eigenwerte. Nach Formel 2.3 gilt für Matrix T , Eigenwert λ
und Eigenvektor v mit Einheitsmatrix E:
T · v = λ · E · v ⇐⇒
(2.4)
T · v − λ · E · v = 0 ⇐⇒
(2.5)
(T − λ · E) · v = 0.
(2.6)
Da v 6= 0 gilt, ist die Gleichung dann lösbar, wenn det(T − λ · E) 6= 0. Schreibt man die
Determinante aus, dann erhält man das charakteristische Polynom. Die Nullstellen dieses
Polynoms sind gerade die gesuchten Eigenwerte. Im zweiten Schritt können die gefundenen
Eigenwerte in Formel 2.3 eingesetzt werden, wodurch man ein lineares Gleichungssystem
erhält. Anschließend kann mit dem Gauß-Verfahren das lineare Gleichungssystem für jeden
Eigenwert gelöst werden, um die Eigenvektoren zu erhalten.
Die Berechnung von Eigenwerten als Nullstellen das charakteristischen Polynom funktioniert zwar für kleine Matrizen, für Matrizen, deren charakteristisches Polynom Grad 5
12
oder höher hat, ist die Berechnung der Eigenwerte jedoch problematisch, da kein allgemeines Verfahren zur Berechnung von Nullstellen solcher Polynome existiert (nach [KM03],
S. 126f). Deswegen werden dann numerische Approximationsverfahren angewendet.
Ein bekanntes Näherungsverfahren ist zum Beispiel das QR-Verfahren. Das Verfahren
basiert darauf, dass zwei ähnliche Matrizen die selben Eigenwerte besitzen. Zwei gleichdimensional quadratische Matrizen A und B sind ähnlich, wenn eine invertierbare Matrix
T existiert, mit der gilt (vgl. [QS06], S. 158ff):
T −1 AT = B.
(2.7)
Ist dann λ ein Eigenwert von A und v 6= 0 der zugehörige Eigenvektor, so folgt aus
Gleichung 2.3 unmittelbar, dass λ auch Eigenwert von B ist, denn
T −1 Av = λT −1 v ⇐⇒
(2.8)
BT −1 v = λT −1 v.
(2.9)
Der Eigenvektor zum gefundenen Eigenwert λ ist dann T −1 v.
Ausgehend von diesen Überlegungen ist das Vorgehen des QR-Verfahrens zum Bestimmen aller Eigenwerte einer Matrix A, die Matrix A schrittweise zu einer ähnlichen, aber
diagonalen, Matrix B zu überführen. Dazu werden iterativ QR-Zerlegungen von der aktuellen Matrix A berechnet. Die QR-Zerlegung ist dabei die Umformung einer Matrix A
in das Produkt zweier Matrizen Q und R, sodass
A = QR
(2.10)
gilt. Dies wird solange wiederholt, bis eine Diagonalmatrix B entstanden ist, aus der dann
die Eigenwerte von A als Diagonaleinträge abgelesen werden können (vgl. [QS06], S. 158ff).
2.2
Stochastik
Dieser Abschnitt stellt den Bezug zur stochastischen Schätzung von Parametern her. Für
jedes in dieser Arbeit vorgestellte Unterraumverfahren wird eine Streuungsmatrix verwendet, um Einsichten in die Verteilung von Daten zu gewinnen und entsprechend den
Unterraum zu wählen.
Außerdem ist es für das spätere Verständnis der MPC wichtig zu verstehen, wie Mischverteilungen mit Hilfe von Normalverteilungen modelliert werden können. Die MPC greift
nämlich diese Idee auf.
2.2.1
Korrelation
Wir stellen die Streuungsmatrix vor. Mit ihr kann eine Punktmenge (repräsentiert durch
Zufallsvariablen) in einem mehrdimensionalen Raum charakterisiert werden und entspre-
2.2. STOCHASTIK
13
chend der Eigenschaften der Punktwolke wird bei unseren Verfahren ein passender Unterraum in Form von Eigenvektoren gewählt. Die Eigenvektoren werden aus der Streuungsmatrix gewonnen. Sie repräsentieren dann Dimensionen des Ausgangsraums, während ihre
Eigenwerte die Stärke der Streuung der Punkte in der entsprechenden Dimension angeben.
Die Kovarianz ist ein Maß der multivariaten Statistik, um anzugeben, ob ein linearer
Zusammenhang zwischen zwei Zufallsvariablen besteht, das heißt eine Korrelation zwischen ihnen vorliegt. Für zwei Zufallsvariablen X und Y mit Realisierungen Xi bzw. Yi
kann die Kovarianz mit folgender mathematischer Formel geschätzt werden (nach [Kir10],
S. 45ff):
Cov(X, Y ) =
n
1 X
(Xi − X̄)(Yi − Ȳ ).
n − 1 i=1
(2.11)
Dabei sind X̄ und Ȳ die entsprechenden Schätzungen der Erwartungswerte der Zufallsvariablen und n die Anzahl der Elemente.
Wie an der Formel erkennbar ist, wertet die Kovarianz zwei Zufallsvariablen bezüglich
einander aus, indem die gemeinsame Streuung der Stichprobendaten berechnet wird. Die
Kovarianz ist also ein Streuungsmaß, welches Aussagen zur linearen Beziehung zwischen
zwei Zufallsvariablen macht (vgl. [Kir10]):
• Ist Cov(X, Y ) > 0, dann kann auf eine positive Korrelation geschloßen werden. Dies
bedeutet, große X-Werte gehen mit großen Y -Werten einher und kleine X-Werte
implizieren kleine Y -Werte.
• Ist Cov(X, Y ) < 0, dann liegt eine negative Korrelation vor: Aus kleinen X-Werten
kann auf große Y -Werte geschloßen werden und umgekehrt.
• Ist Cov(X, Y ) ≈ 0, dann existiert kein linearer Zusammenhang zwischen den beiden
Zufallsvariablen, das heißt sie sind unkorreliert.
Abbildung 2.1 zeigt eine positive Korrelation (links) und eine Unkorreliertheit (rechts)
zwischen zwei Zufallsvariablen, die in der Abbildung als Achsen dargestellt sind. Würde
man beispielsweise für die zwei Zufallsvariablen in der linken Abbildung die Kovarianz
schätzen, würde man einen Kovarianzwert größer Null erhalten. Demnach besteht zwischen
X und Y also ein linearer Zusammenhang in Form einer positiven Korrelation. Für die
Zufallsvariablen gilt dann prinzipiell, dass der X-Wert wächst, wenn der Y -Wert fällt und
umgekehrt.
Die Kovarianz findet lineare Beziehungen zwischen zwei Zufallsvariablen. Nun hat man
in Problemstellungen jedoch meißt mit mehr als zwei Zufallsvariablen zu tun, die alle nach
ihren Abhängigkeiten untereinander analysiert werden sollen. Folglich muss für jede Kombination der Zufallsvariablen die Kovarianz berechnet werden. Diese Kombinationen werden in einer Kovarianzmatrix dargestellt, indem systematisch alle möglichen Kovarianzen
14
Abbildung 2.1: Beispiel für eine positiv korrelierte Punktwolke (links) und eine unkorrelierte
Punktwolke (rechts) für zwei Zufallsvariablen X und Y (nach [Fin03], S. 140).
zwischen den Zufallsvariablen gebildet werden. Eine solche Kovarianzmatrix sieht für zwei
Zufallsvariablen X und Y wie folgt aus (nach [DHS01], S. 617f):

K=
Cov(X, X)
Cov(X, Y )
Cov(Y , X)
Cov(Y , Y )

.
(2.12)
Sind die Einträge der Kovarianzmatrix, wie in Formel 2.12, Schätzungen der tatsächlichen
Kovarianz, dann wird die Kovarianzmatrix als Streuungsmatrix bezeichnet (vgl. [Fin03],
S. 141f.). Sie ist eine Schätzung der Kovarianzmatrix. Die Streuungsmatrix ist stets quadratisch und die Einträge an der Hauptdiagonalen sind die Schätzungen der Varianzen für
die einzelnen Zufallsvariablen. Die Schätzung der Varianz von Zufallsvariable X entspricht
Cov(X, X). An Formel 2.11 ist erkennbar, dass Cov(X, Y ) = Cov(Y , X) gilt. Aus diesem
Grund ist die Streuungsmatrix immer symmetrisch und erfüllt damit wichtige Voraussetzungen für die Berechnung von Eigenwerten und Eigenvektoren (siehe Kapitel 2.1.2).
2.2.2
Mischverteilung
Aus mehreren Normalverteilungen kann ein Mischverteilungsmodell angegeben werden.
Analog dazu erschafft das MPC-Verfahren aus mehreren Unterräumen eine Mischung von
Unterräumen. Aus diesem Grund werden zunächst Grundlagen von Mischverteilungen erklärt.
Eine Wahrscheinlichkeitsverteilung einer Zufallsvariablen gibt an, wie wahrscheinlich
es ist, dass eine Realisierung der Zufallsvariable eintritt. Es ist aus Kompaktheitsgründen
praktisch eine Verteilung als Funktion anzugeben. Ist eine Zufallsvariable normalverteilt,
dann kann ihre Verteilung als Gaußsche Normalverteilung dargestellt werden. Hierbei
handelt es sich um eine Dichtefunktion, die zu jeder Realisierung einer Zufallsvariablen
angibt, mit welcher Häufigkeit sie eintreten kann.
2.2. STOCHASTIK
15
Abbildung 2.2: Beispiel für zwei Normalverteilungen N1 und N2 (nach [Fin12], S.
141).
Für eine mehrdimensionale Zufallsvariable kann die Normalverteilung als Funktion
angegeben werden (vgl. [Fin03], S. 46f):
1
1
T
−1
e− 2 (x−µ) K (x−µ) .
N (x|µ, K) = p
|2πK|
(2.13)
Dabei müssen sowohl Mittelvektor µ als auch Kovarianzmatrix K bekannt sein, um die
Normalverteilung angeben zu können. In der Formel bezeichnet |2πK| die Determinante
der Matrix 2πK, K −1 ist die Inverse zur Matrix K und K T die Transponierte zu K.
Da Normalverteilungen nur ein Häufungsgebiet (siehe zum Beispiel Abbildung 2.2),
und zwar um den Mittelvektor herum, gleichzeitig aufweisen, können Verteilungen, die
mehrere Häufungsgebiete besitzen, nicht gut mit einer einzelnen Normalverteilung repräsentiert werden. Allerdings kann mit einer linearen Kombination aus mehreren Normalverteilungen die Verteilung einer Zufallsvariablen mit mehreren Häufungsgebieten approximiert werden. Die so entstehende Mischverteilung ist umso genauer, je mehr Normalverteilungen kombiniert werden. Nach [Fin03] ist die Mischverteilung aus K Normalverteilungen
dann gebildet durch
p(x) ≈
K
X
ci N (x|µi , Ki ).
(2.14)
i=1
Zum Bilden eines solchen Mischverteilungsmodells müssen die Mittelvektoren µi , die Kovarianzmatrizen Ki der Normalverteilungen und die Mischungsgewichte ci , die als Summe
1 ergeben müssen, als Parameter vorliegen.
In Abbildung 2.3 ist ein Beispiel für eine Mischverteilung mit zwei Häufungsgebieten
dargestellt. So könnte eine Mischverteilung aussehen, die aus den zwei Normalverteilungen
von Abbildung 2.2 geschätzt wurde.
16
Abbildung 2.3: Beispiel für eine Mischverteilung (nach [Fin12], S. 168).
2.3
Optimierung
Methoden aus dem Gebiet der mathematischen Optimierung werden wir benötigen, um
eine optimale Parameterschätzung für einen Unterraum durchzuführen. Dieses Kapitel
trägt hauptsächlich zum Verständnis der MPC-Methode bei, denn diese basiert auf den
Ideen dieses Kapitels.
2.3.1
Vektorquantisierung
Parameter für Mischverteilungsmodelle, die wir in Kapitel 2.2.2 eingeführt haben, können
mit Verfahren der Vektorquantisierung geschätzt werden. Wir erklären das Vorgehen und
beschreiben ein Vektorquantisierungsverfahren, den Lloyd-Algorithmus, dessen Ergebnisse
als Parameter für ein einfaches Mischverteilungsmodell verwendet werden können.
Die Vektorquantisierung ist ein allgemeiner Begriff für Verfahren, die vor allem der
Kompression von Datenvektoren dienen. Ziel ist es, zu einer Menge von Vektoren, die
einen großen Wertebereich haben, eine kleine Menge von repräsentativen Vektoren zu
bestimmen, auf welche alle Vektoren abgebildet werden können. Auf diese Weise werden
für spätere Zwecke nur noch die Repräsentanten benötigt und nicht die Vielzahl aller
möglichen Ausprägungen der Vektoren. Die Menge der Repräsentanten wird dabei als
Codebuch bezeichnet ([Fin03], S. 53ff).
Ein Beispiel für das Ergebnis einer durchgeführten Vektorquantisierung ist als VoronoiDiagramm in Abbildung 2.4 zu sehen. Es sind vierzehn Repräsentanten bestimmt worden
(schwarze Punkte in der Abbildung). Die Vektoren, die auf einen Repräsentanten abgebil-
2.3. OPTIMIERUNG
17
Abbildung 2.4: Beispiel für eine Vektorquantisierung. Die Repräsentanten sind als schwarze Punkte dargestellt und die Partitionen der jeweiligen Repräsentanten sind durch die Linien abgegrenzt (nach [Fin12], S. 138).
det werden, sind durch die Fläche (auch Partition oder Zelle genannt) um den jeweiligen
Repräsentanten gegeben.
Während der Vorteil der Vektorquantisierung darin besteht, nur das Codebuch und
nicht alle Vektoren speichern zu müssen, liegt der Nachteil darin, dass mit kleinerem Codebuch ebenso die Ungenauigkeit zunimmt. Die Ungenauigkeit der Quantisierung wird
als globaler Quantisierungsfehler bezeichnet. Dieser berechnet sich als statistischer Erwartungswert der Quantisierungsfehler aller bekannten Vektoren x zur Zufallsvariable X (vgl.
[Fin03], S. 53ff):
¯(Q) = ε{d(X, Q(X))}
(2.15)
Hierbei bezeichnet Q(X) die Quantisierung von X. Die Distanz zwischen X und Q(X) ist
durch eine Funktion d(X, Q(X)) gegeben.
Das Optimalitätskriterium für die Vektorquantisierung ist es nun für eine gegebene
Codebuchgröße die Repräsentanten so zu bestimmen, dass der globale Quantisierungsfehler
¯(Q) minimiert wird. Die Vektorquantisierung beachtet dabei zwei Grundbedingungen:
1. Die Nächster-Nachbar-Bedingung: Bei gegebenem Codebuch sind für die Repräsentanten die Partitionen, die darüber entscheiden, ob ein Vektor auf den jeweiligen
Repräsentanten abgebildet wird, so zu wählen, dass alle Vektoren in der jeweiligen
Partition minimalen Abstand zum Repräsentanten dieser Partition haben.
18
2. Die Zentroid-Bedingung: Bei gegebenen Partitionen sind die optimalen Repräsentanten gerade die Zentroiden dieser Partitionen. Zentroiden sind diejenigen Vektoren,
die minimalen Abstand zu allen anderen Vektoren in ihrer Partition haben.
Ein einfacher Algorithmus zur Vektorquantisierung ist der Lloyd-Algorithmus. Bei die-
sem Verfahren werden nach den zwei oben genannten Bedingungen das Codebuch und die
Partitionen abwechselnd aktualisiert. Dabei wird bei jedem Iterationsschritt der Quantisierungsfehler minimiert und der Algorithmus terminiert, sobald keine Verbesserung des
Quantisierungsfehlers mehr stattfindet. Das Codebuch und dessen Größe müssen initial
festgelegt werden, was auf heuristische oder zufällige Art zu erfolgen hat. Bei der Durchführung des Lloyd-Algorithmus (z.B. mit der euklidischen Distanz) für eine gegebene Menge
von Vektoren kann eine Iteration wie folgt aussehen (vgl. [Fin03], S. 58f):
• Ordne jeden Vektor nach der Nächster-Nachbar-Bedingung seinem Repräsentanten
im Codebuch zu.
• Berechne die Repräsentanten nach der Zentroid-Bedingung neu anhand der Partitionen, die durch die ihnen zugeordneten Vektoren gegeben sind.
Ein Problem des Lloyd-Algorithmus ist, dass nicht immer garantiert das globale Optimum gefunden wird. Das Verfahren kann nämlich bereits bei einem lokalen Optimum
konvergieren.
Das Ergebnis eines Vektorquantisierers kann dazu verwendet werden, um Parameter
eines Mischverteilungsmodells zu schätzen. Liefert ein Vektorquantisierer ein Codebuch
der Größe N mit N Partitionen, so kann jede Partition als Normalverteilung betrachtet
werden, die - wie in Kapitel 2.2.2 erwähnt - zusammen zu einer Mischverteilung kombiniert werden können. Die Parameter für eine Normalverteilung i = 1..N können wie folgt
geschätzt werden (vgl. [Fin03], S. 62f)
• Der Mittelvektor µi entspricht dem Zentroiden der i-ten Partition, das heißt dem
i-ten Codebucheintrag.
• Die Kovarianzmatrix Ki kann aus den Vektoren, die zur i-ten Partition gehören,
geschätzt werden.
• Das Mischungsgewicht ci für die Kombination der Normalverteilungen ist dabei die
a-priori-Wahrscheinlichkeit der i-ten Partition (dezimaler Prozentualanteil der Partitionsvektoren aus allen Vektoren)
2.3.2
EM-Algorithmus
Schätzt man ein Mischverteilungsmodell mit Ergebnissen des Lloyd-Algorithmus, dann fließen in jede Berechnung einer Normalverteilung nur Vektoren aus der jeweiligen Partition
2.3. OPTIMIERUNG
19
mit ein, obwohl eine Normalverteilung laut Definition Dichtewerte für jeden Vektor liefern
muss, auch wenn diese Werte beliebig klein sein können. Dies ist bei dem als nächstes vorgestellten Verfahren zur Schätzung von Mischverteilungsmodellen, dem EM-Algorithmus,
anders. Bei dieser Methode geschieht keine strikte Zuordnung von Vektoren zu Normalverteilungen, sondern es erfolgt eine sogenannte ”weiche Vektorquantisierung” (vgl. [Fin03],
S. 63ff). Dabei wird jedem Vektor für jede Normalverteilung eine Wahrscheinlichkeit vergeben. Bei der MPC wird ebenfalls eine solche Vektorquantisierung mit einem EM-Verfahren
durchgeführt.
Wir betrachten den Expectation-Maximization-Algorithmus, kurz EM-Algorithmus,
als Verfahren zur Schätzung von Mischverteilungsparametern. Es handelt sich um eine
Maximum-Likelihood-Methode, bei der iterativ eine zu maximierende Likelihood-Funktion
verbessert wird. Das Verfahren terminiert, sobald keine bedeutende Verbesserung des Likelihoods mehr stattfindet, also bis das Verfahren konvergiert.
Wir erinnern uns an die Definition einer Mischverteilung aus Kapitel 2.2.2. Ausgehend
von N Normalverteilungen, werden für ein Mischverteilungsmodell die Parameter für jede
Normalverteilung benötigt. Wir fassen diese Parameter im Parametersatz Θ zusammen.
Mit Hilfe der Likelihood-Funktion werden die Parameter der Mischverteilung geschätzt.
Wir führen die Likelihood-Funktion ein und vereinfachen diese durch Anwendung des Logarithmus. Wir können dies problemlos tun, da die Anwendung einer monotonen Funktion
auf eine andere Funktion nicht das Ergebnis des Maximierungsproblems verändert. Wir
erhalten somit die Log-Likelihood-Funktion (vgl. [Fin03], S. 63ff):
L(Θ|w) =
X
ln(p(x|Θ)).
(2.16)
x∈w
Sie ist abhängig vom Parametersatz Θ bei gegebener Stichprobe w. Es handelt sich bei
dieser Berechnung um die Summe der Dichtewerte des Mischverteilungsmodells zum Parametersatz Θ.
Nach der Initialisierung arbeitet der EM-Algorithmus in zwei Schritten pro Iteration.
Im Expectation-Schritt werden bekannten Datenvektoren der Stichprobe Wahrscheinlichkeiten für die Zugehörigkeit zu jeder Normalverteilung zugeordnet. Und im MaximizationSchritt erfolgt dann die Neuberechnung der Parameter mit dem Ziel, die Log-LikehoodFunktion zu maximieren.
In Kapitel 2.3.1 haben wir beschrieben, wie eine einfache Schätzung von Parametern
für ein Mischverteilungsmodell nach einer Vektorquantisierung erfolgen kann. Auf genau
diese Weise kann der Ausgangsparametersatz Θ0 des EM-Algorithmus initialisiert werden.
Danach können die zwei EM-Schritte abwechselnd ausgeführt werden.
Im ersten Schritt (Expectation-Schritt) wird die a-posteriori Wahrscheinlichkeit für die
Neuzuordnung jedes Vektors x ∈ w zu jedem Repräsentanten wi des Codebuchs für den
20
aktuellen Parametersatz Θm berechnet. Diese berechnet sich in [Fin03] als Prozentualanteil
der Dichtewerte folgendermaßen:
m
cm · N (x|µm
i , Ki )
P (wi |x, Θm ) = P i m
m
m .
j cj · N (x|µi , Ki )
(2.17)
Nun können im zweiten Schritt (Maximization-Schritt) die Parameter des Modells anhand
der soeben aktualisierten a-posteriori-Wahrscheinlichkeiten neu geschätzt werden. Für jede
Normalverteilung i ist die Neuschätzung der Parameter dann wie folgt (vgl. [Fin03], S.
63ff):
P
ci =
µi =
P (wi |x)
,
|w|
x∈w
P
x∈w P (wi |x) · x
P
,
x∈w
P
Ki =
x∈w
P (wi |x)
P (wi |x)(x − µi )(x − µi )T
P
.
x∈w P (wi |x)
(2.18)
(2.19)
(2.20)
Zuletzt kann das Konvergenzkriterium kontrolliert werden, das heißt die Log-LikelihoodFunktion wird berechnet und es wird überprüft, ob diese einen bedeutend optimaleren
Wert liefert als die zuvor berechnete Funktion. Ist dies nicht der Fall, terminiert der
EM-Algorithmus mit dem aktuellen Parametersatz Θm , welcher das endgültige Mischverteilungsmodell definiert.
2.3.3
Lagrange-Multiplikator
Die Methode des Lagrange-Multiplikators werden wir bei dem MPC-Verfahren brauchen,
um das Optimum einer Funktion mit Nebenbedingungen berechnen zu können.
Soll eine Extremstelle (Maximum oder Minimum) einer Funktion bestimmt werden,
dann ist es einfach diese Funktion nach ihren Veränderlichen abzuleiten und die Ableitung
gleich Null zu setzen, um das gesuchte Extremum zu erhalten. Ist jedoch die zu optimierende Funktion durch Nebenbedingungen eingeschränkt, dann ist dies nicht direkt möglich.
Zum Lösen von Optimierungsproblemen mit Nebenbedingungen wird daher die Methode
des Lagrange-Multiplikators verwendet. Hierbei wird für jede Nebenbedingung, die die
Funktion einhalten muss, eine skalare Variable eingeführt, die als Lagrange-Multiplikator
bezeichnet wird. Indem nun jede solche Variable als Koeffizient einer Linearkombination
eingesetzt wird, reduziert man das Optimierungsproblem mit Nebenbedingungen auf ein
Problem ohne Nebenbedingungen.
Will man zum Beispiel von einer Funktion f (x) die Extrema berechnen und gleichzeitig
eine Nebenbedingung in Form einer Funktion g einhalten, sodass g(x) = 0 gelten soll,
2.4. ZUSAMMENFASSUNG
21
dann definiert man zunächst die Lagrange-Funktion, die diese Nebenbedingung mit der
zu optimierenden Funktion kombiniert (vgl. [DHS01], S. 610):
L(x, λ) = f (x) + λ · g(x)
Diese Funktion ist nicht mehr durch separate Nebenbedingungen eingeschränkt, sodass
ihre Extrema leicht berechnet werden können.
2.4
Zusammenfassung
Es wurden wichtige mathematische Grundlagen für das Verständnis der nächsten Kapitel
gelegt.
Mit Hilfe linearer Abbildungen in Form von Transformationsmatrizen werden Vektoren, die bei den hier vorgestellten Techniken Gesichtern entsprechen werden, in lineare
Unterräume projiziert. Für unsere Zwecke wird eine Transformationsmatrix aus mehreren
Vektoren gebildet, die zusammen als Basen einen Unterraum aufspannen. Solche Vektoren
werden Eigenvektoren zu einem Eigenwertproblem sein, das z.B. mit dem QR-Algorithmus
gelöst werden kann.
Um lineare Abhängigkeiten zwischen Vektoren einer Menge in einem mehrdimensionalen Raum zu beschreiben, verwendet man eine Streuungsmatrix. Diese zeigt Korrelationen
zwischen mehreren Zufallsvariablen, die als Dimensionen angesehen werden können, an.
Streuungsmatrizen werden bei jedem in dieser Arbeit eingeführten Unterraumverfahren
berechnet, um aus den Streuungsinformationen gegebener Vektoren einen geeigneten Unterraum zu bestimmen.
Darüberhinaus wurde dargestellt, wie die Verteilung einer Datenmenge, die mehrere
Häufungsgebiete aufweist, mit einer Kombination von Normalverteilungen zu einer Mischverteilung genauer modelliert werden kann als mit einer einzelnen Normalverteilung. Zum
Erstellen eines solchen Mischverteilungsmodells wurden zwei Möglichkeiten erläutert, zum
Einen mit Ergebnissen eines Verfahrens zur Vektorquantisierung (z.B. Lloyd-Algorithmus)
und zum Anderen mit einem EM-Algorithmus. Letzteres ist dabei vorteilhafter, weil nicht
nur lokale, sondern auch globale Informationen betrachtet werden. Diese Erkenntnisse
werden bei der Hauptkomponentenmischung aufgegriffen mit dem Ziel, eine optimalere
Repräsentation von Vektoren durch ein EM-Vorgehen zu erreichen. Dabei wird es erforderlich sein, eine Optimierungsfunktion mit Einschränkung zu definieren. Diese Nebenbedingung muss erst mit der Funktion verknüft werden, bevor das Optimum berechnet werden
kann. Das Verbinden von Nebenbedingungen mit einer Funktion leistet der LagrangeMultiplikator.
22
Kapitel 3
Verfahren
In diesem Kapitel wird die allgemeine Struktur eines Gesichtserkennungssystems vorgestellt. Darauf folgt eine Einführung in das Grundkonzept von Unterraumverfahren. Dies
beeinhaltet auch die Beschreibung des Nächste-Nachbarn-Klassifikators und einiger verwendbarer Distanzmaße. Anschließend werden die drei Unterraumverfahren Hauptkomponentenanalyse (PCA), Lineare Diskriminanzanalyse (LDA) und Hauptkomponentenmischung (MPC) im Kontext der Gesichtserkennung detailliert beschrieben.
3.1
Allgemeines Gesichtserkennungssystem
Abbildung 3.1: Grundaufbau eines Gesichtserkennungssystems.
Das grundlegende Schema eines Gesichtserkennungssystems ist in Abbildung 3.1 dargestellt. Unter der Annahme, dass eine aus bekannten Gesichtsbildern bestehende Datenbank
bereits erstellt wurde, die als Referenz für wiederzuerkennende Gesichter dient, besteht das
grundlegende Schema eines Gesichtserkennungssystems aus drei Komponenten: der Aufnahme des Gesichtsbilds, der Normalisierung des Bilds sowie dessen Klassifizierung.
Der erste Schritt liegt darin, ein Gesichtsbild zu beschaffen, das aus der Datenbank
wiedererkannt werden soll. Das Bild kann zum Beispiel eine Foto- oder Videoaufnahme
sein.
Da das aufgenommene Bild neben dem Gesicht auch andere Dinge enthalten kann und
Bilder nicht immer unter optimalen Bedingungen aufgenommen werden, muss das Bild
normalisiert werden. Dies beinhaltet unter anderem das Lokalisieren der Gesichtsposition
im gesamten Bild, das Ausschneiden und das anschließende Skalieren sowie ein eventuelles
23
24
KAPITEL 3. VERFAHREN
Rotieren des Gesichts. Die konkrete Prozedur zur Normalisierung der Bilder bei unseren
Experimenten wird in Kapitel 4.2 erklärt.
Im dritten und letzten Schritt erfolgt die Klassifizierung des normalisierten Bildes.
Hierbei entscheidet der Klassifikator, welcher Person in der Datenbank dieses Gesichtsbild
zuzuordnen ist oder, ob es sich um eine unbekannte Person handelt.
Abbildung 3.2: Einige Gesichtsbilder der verwendeten Trainingsmenge (aus [FER12]).
Bevor ein Gesichtserkennungssystem tatsächlich in Betrieb genommen werden kann,
muss in der sogenannten Trainingsphase das Verfahren initialisiert werden. Diesem Training liegt eine Datenbank von bekannten Gesichtern zugrunde, aus denen ein Verfahren
Informationen extrahiert, die für das spätere Erkennen unbekannter Gesichter hilfreich
sein könnten. Ein Einblick in einige Gesichtsbilder der Datenbank, die bei unseren Experimenten verwendet wird, gibt Abbildung 3.2. Nach dem Training werden unbekannte
Personen dann aus der Datenbank identifiziert. Das Identifizieren wird im experimentellen
Zusammenhang auch als Testphase und die unbekannten Bilder als Testbilder bezeichnet.
3.1.1
Unterraumkonzept
Im Zusammenhang mit Unterraumverfahren wird ein Gesichtsbild als Vektor betrachtet.
Bei einem Gesichtsbild handelt es sich um eine Pixelmatrix, die zu jeder Position im
Bild einen Pixelwert angibt. Um nun ein Bild als Vektor darzustellen, wird jede Zeile der
Pixelmatrix hintereinander zu einem Vektor hinzugefügt. Hatte das ursprüngliche Bild
m × n Pixel, dann besteht der entsprechende Bildvektor aus m · n Einträgen. Mit der
Projektion eines Bildes ist also immer die Projektion eines Bildvektors gemeint.
Die Idee von Unterraumverfahren zur Gesichtserkennung ist es, einen geeigneten Unterraum zu bestimmen, in dem die Klassifikation stattfinden kann. Die Bestimmung des
Unterraums findet vorab, noch vor der eigentlichen Gesichtserkennungsprozedur, im sogenannten Training statt. Dabei werden Informationen aus der Datenbank von gegebenen,
bekannten Gesichtern genutzt, um einen möglichst optimalen Unterraum zu berechnen.
Optimal bedeutet, dass der Unterraum so aufgebaut ist, dass nach der Projektion in diesen
3.1. ALLGEMEINES GESICHTSERKENNUNGSSYSTEM
25
Raum möglichst viele Informationen zur Unterscheidung von Gesichtern erhalten bleiben
und möglichst viel der nebensächlichen Information verloren geht. Ist der Unterraum einmal bestimmt, kann der tatsächliche Prozess der Gesichtserkennung stattfinden. Dazu wird
das Bild in den Unterraum projiziert und anschließend vom Klassifikator der jeweiligen
Person zugeordnet.
Die Vorteile von Unterraumverfahren sind:
• Der Unterraum wird so bestimmt, dass die Klassifikation begünstigt wird.
• Nach der Projektion in den Unterraum sind die Gesichtsbilder durch kompakte Vektoren repräsentiert. Das führt zu einem geringeren Rechenaufwand bei der Klassifikation.
• Es wird ein geringerer Speicherplatzbedarf benötigt, da die Bilder der Datenbank
nicht in ihren Ursprungsbildgrößen gespeichert werden müssen, sondern nur ihre
Projektionen.
Die Nachteile hingegen sind:
• Durch die Dimensionsreduktion bei der Projektion in einen Unterraum gehen Bildinformationen verloren, die nicht fehlerlos wiederhergestellt werden können.
• Die Berechnung des Unterraums benötigt zusätzlichen Rechenaufwand, der je nach
Verfahren sehr hoch sein kann. Jedoch kann diese Berechnung problemlos vor der
Inbetriebnahme des Gesichtserkennungssystems stattfinden und zum Beispiel bei
Stehzeiten des Systems wiederholt werden.
3.1.2
Klassifikator
Bei unterraumbasierten Gesichtserkennungsverfahren kann ein Bild aus m×n Pixel als ein
mn-dimensionaler Vektor oder als ein Punkt in einem mn-dimensionalen Raum aufgefasst
werden. Ein solcher Vektor enthält dann alle Informationen eines Gesichtsbildes und wird
Gesichtsvektor genannt. Bei unseren Verfahren wird jeder Vektor eines Gesichtsbildes in
einen Unterraum projiziert, sodass Projektionen entstehen, die zu den jeweiligen Gesichtern gehören. Um eine unbekannte Person zu identifizieren, wird ihr Gesichtsvektor in
den Unterraum projiziert und mit dem Nächste-Nachbarn-Klassifikator einer der bekannten Projektionen zugeordnet. Der Nächste-Nachbarn-Klassifikator ordnet einem Vektor
einen anderen Vektor zu, der den geringsten Abstand zu ihm hat. Mit der Annahme, dass
ein kleiner Abstand zweier Projektionen auf zwei ähnliche Bilder schließen lässt, werden
bei den später vorgestellten Unterraumverfahren nach diesem Schema Gesichter Personen
zugeordnen.
26
3.1.3
Distanzmetriken
Distanzmaße verden verwendet, um den Abstand zwischen zwei Vektoren - in unserem Fall
also den Unterschied zwischen zwei Gesichtsbildern - zu berechnen. Im Folgenden werden
einige Distanzmaße vorgestellt, die sich in der Gesichtserkennung etabliert haben und oft
in Verbindung mit Unterraumverfahren verwendet werden.
Seien u und v zwei P -dimensionale Vektoren, für die die Distanz zueinander berechnet
werden soll, dann sind die Distanzfunktionen wie folgt definiert (vgl. [ML09]):
1. L2-Norm (euklidische Distanz):
v
uP
uX
DL2 (u, v) = t (ui − vi )2
(3.1)
i=1
Die L2-Norm ist ein weitverbreitetes Abstandsmaß. Dabei wird die Wurzel der quadrierten
Differenzen betrachtet. Fasst man zwei Vektoren als Punkte im mehrdimensionalen Raum
auf, dann entspricht die euklidische Distanz der Länge der direkten Verbindung zwischen
den beiden Punkten.
2. L1-Norm (Manhattan-Distanz):
DL1 (u, v) =
P
X
|ui − vi |
(3.2)
i=1
Bei der L1-Norm wird die Distanz zweier Vektoren als Summe der absoluten Differenzen
der Komponenten berechnet. Das entspricht einer blockweisen Verbindung in Richtung
der Koordinatenachsen.
3. Kosinusdistanz:
P
ui vi
uv
= 1 − qP i=1qP
DKosinus (u, v) = 1 −
P
P
|u||v|
2
2
i=1 ui
i=1 vi
P
(3.3)
Die Kosinusdistanz ist von dem Kosinus-Ähnlichkeitsmaß abgeleitet, welches den Kosinus
des Winkel zwischen zwei Vektoren berechnet. Dieses ist ein Indikator dafür, wie ähnlich
sich die beiden Richtungen der beiden Vektoren sind. Damit nun die Kosinusdistanzfunktion für zwei Vektoren, die in die gleiche Richtung zeigen, einen minimalen Distanzwert
ausgibt, wird das Ergebnis der Kosinusähnlichkeitsfunktion durch Subtraktion von eins
normiert (vgl. z.B. [WYB02]).
Für die folgenden Distanzmaße werden die Vektoren u und v in den MahalanobisRaum projiziert. Im Mahalanobis-Raum besitzt jede Dimension eine Varianz von Eins (vgl.
[ML09]). Dadurch wird jede Dimension beim Messen der Distanz gleichwertig behandelt.
Um einen Vektor in den Mahalanobis-Raum zu transformieren, wird zu jeder Dimension
ihre Varianz benötigt. Diese ist bei unseren Verfahren durch die Eigenwerte bekannt.
√
Die Varianz von Dimension i bezeichnen wir also mit λi . Die Transformation jedes
Vektoreintrags ui und vi ist damit mi =
√ui
λi
sowie ni =
√vi .
λi
Nachdem Vektoren u
3.2. HAUPTKOMPONENTENANALYSE
27
und v auf diese Weise zu Vektoren m und n transformiert wurden, können die oberen
Distanzfunktion angewendet werden.
4. Mahalanobis-L2
v
uP
uX
DM ahL2 (m, n) = t (mi − ni )2
(3.4)
i=1
5. Mahalanobis-L1
DM ahL1 (m, n) =
P
X
|mi − ni |
(3.5)
mn
|m||n|
(3.6)
i=1
6. Mahalanobis-Kosinus
DM ahKosinus (m, n) =
Die letzten drei Distanzmaße sind jeweils Kombinationen des Mahalanobis-Raums mit der
L2-Norm, der L1-Norm oder der Kosinusdistanz.
Diese sechs Distanzmaße werden für den Nächste-Nachbarn-Klassifikator zur Berechnung der Abstände zwischen Projektionen benötigt. In den Experimenten in Kapitel 4
werden die sechs vorgestellten Distanzmaße analysiert.
3.2
Hauptkomponentenanalyse
Das erste Verfahren zur Gesichtserkennung, welches in diesem Kapitel vorgestellt wird,
ist das Eigenfaces-Verfahren nach [TP91b]. Es basiert auf der Hauptkomponentenanalyse
(Principal Component Analysis, PCA) und gilt als erstes wirklich erfolgereiches Gesichtserkennungsverfahren. Die Idee der Gesichtserkennung mit der PCA ist es, einen Unterraum
zu bestimmen, bei dem nach der Projektion die meißte Information des Gesichtsvektors
erhalten bleibt. Anschließend wird der Abstand des projizierten Gesichts zu bekannten,
bereits projizierten Gesichtern verglichen.
3.2.1
Prinzip
Generell wird die PCA mit dem Ziel der Dekorrelation von Daten und der Dimensionsreduktion verwendet (vgl. [Fin03], S. 141ff). Dazu wird zu den Daten die Streuungsmatrix
gebildet, wodurch Korrelationen zwischen den Dimensionen der Daten bekannt werden
(vgl. Kapitel 2.2.1). Dann werden Eigenvektoren der Streuungsmatrix berechnet, die einen
Vektorraum bilden, bei dem im Vergleich zum ursprünglichen Raum die projizierten Daten
so verteilt sind, dass ihre Streuungsmatrix in Diagonalform vorliegt. Die Diagonalmatrix
enthält für jede Dimension Angaben zur Varianz der Daten (vgl. Kapitel 2.1.3).
In Abbildung 3.3 ist die Dekorrelation der Punktwolke von Abbildung 2.1 (links) aus
Kapitel 2.2.1 dargestellt. Erkennbar ist eine Translation des Koordinatensystems zum
Zentrum der Punktwolke und eine anschließende Rotation des Koordinatensystem. Das
28
Abbildung 3.3: Beispiel einer durch die PCA dekorrelierten Punktwolke im zweidimensionalen
Raum mit Achsen X und Y .
Ergebnis ist eine Ausrichtung der Koordinatenachsen in Richtung der Streuung. Der Dimensionsreduktionsschritt bei der PCA wird durchgeführt, indem Achsen zur geringsten
Streuung der Daten entfernt werden. Mit so einer Dimensionsreduktion wird ein minimaler
Informationsverlust der Daten erreicht.
Die Idee der PCA wird bei dem Eigenfaces-Verfahren aufgegriffen. Zunächst werden
die bekannten Gesichtsbilder, die Trainingsbilder, als Gesichtsvektoren repräsentiert (vgl.
Kapitel 3.1.2). Durch anschließende Berechnung der Streuungsmatrix zu den Vektoren wird
ihre Streuung bekannt, sodass die aus der Streuungsmatrix berechneten Eigenvektoren
und Eigenwerte nun Informationen über die Gesichtsbilder enthalten, genauer über die
Verteilung der Pixel und über die Variationen in jedem Bildbereich. Insbesondere verläuft
der Eigenvektor zum größten Eigenwert in Richtung der größten Varianz der Bildern. Die
grundlegende Annahme des Verfahrens ist es, dass die Dimension mit der größten Varianz
- also der Eigenvektor mit dem größten Eigenwert - am charakteristischsten für Gesichter
ist und daher am meißten Information zur Unterscheidung von Gesichtern enthält (vgl.
[TP91a]).
Diese Annahme wird bei der Wahl des Unterraums ausgenutzt. Eigenfaces werden nach
ihrer Berechnung absteigend nach ihren Eigenwerten geordnet. Die ersten P Eigenfaces zu
den größten Eigenwerten spannen einen P -dimensionalen Vektorraum auf, der Eigenraum
oder auch Gesichtsraum genannt wird (vgl. [TP91a]). In diesem Unterraum wird jedes
29
Gesichtsbild als Linearkombination der Eigenfaces dargestellt. Indem zur Dimensionsreduktion Eigenvektoren zu den kleinsten Eigenwerten entfernt werden, erreicht man einen
im Durchschnitt minimalen Rekonstruktionsfehler der Gesichter. Als Rekonstruktionsfehler eines Vektors wird der euklidische Abstand zwischen dem ursprünglichen Vektor und
seiner Rückprojektion aus einem Unterraum bezeichnet. Mit einer Dimensionsreduktion,
bei der Achsen mit den geringsten Varianzanteilen entfernt werden, wird der Projektionsfehler der Daten minimiert.
Die Initialisierungsschritte des PCA-Verfahrens können wie folgt zusammengefasst werden:
• Erstellen einer Datenbank von bekannten Gesichtern (Trainingsbilder).
• Berechnung der Eigenfaces und Bildung des P -dimensionalen Gesichtsraums aus den
ersten P Eigenfaces.
• Projektion jedes Bildes aus der Gesichtsdatenbank in den Gesichtsraum.
Zum Klassifizieren eines unbekannten Gesichts müssen nur noch zwei Schritte ausgeführt werden:
• Projektion des unbekannten Gesichtsbilds in den Gesichtsraum.
• Klassifikation der Projektion mit dem Nächste-Nachbarn-Klassifikator.
Abbildung 3.4: Veranschaulichung der Klassifikation eines unbekannten Gesichts aus einer Datenbank von drei Personen in einem zweidimensionalen Gesichtsraums (nach [TP91b]). Die Projektionen der bekannten Gesichter (P1, P2 und P3) sind als schwarze Punkte und die Projektion
des unbekannten Gesichts als blauer Stern abgebildet. Der Unterraum wird von zwei Eigenfaces
u1 und u2 aufgespannt.
Zur Verdeutlichung des Eigenface-Verfahrens dient Abbildung 3.4. Dargestellt ist ein
Gesichtsraum, in den drei Gesichter von bekannten Personen projiziert wurden. Soll nun
30
ein unbekanntes Gesicht klassifiziert werden, wird es ebenfalls in den Gesichtsraum abgebildet. Anschließend kann anhand der Distanz dieser Projektion zu anderen Projektionen
entschieden werden, welcher Person das unbekannte Gesichtsbild zuzuordnen ist. In der
Abbildung würde der Klassifikator das unbekannte Gesicht Person P2 zuweisen, da die
Projektion des unbekannten Gesichts die kleinste Distanz zur Projektion von P2 hat.
3.2.2
Eigenfaces
In diesem Abschnitt wird die Berechnung der Eigenfaces nach [TP91a] erklärt.
Sei die Trainingsmenge gegeben durch x1 , ..., xN . Jeder der N Gesichtsvektoren besitzt
D Dimensionen. Der durchschnittliche Gesichtsvektor zur Trainingsmenge ist:
m=
N
1 X
xi .
N i=1
(3.7)
Das wird verwendet, um die Trainingsbilder im Koordinatensystem zu zentrieren (Translationsschritt). Matrix A enthält die zentrierten Bilder als Spaltenvektoren. Die Zentrierung
jedes Trainingsvektors xi erfolgt durch:
ai = xi − m
, für alle i = 1..N .
(3.8)
Das Durchschnittsgesicht zu der Trainingsmenge, die bei den späteren Experimenten verwendet wird, ist in Abbildung 3.5 dargestellt. Zu erkennen ist eine partielle Unschärfe
des Gesichts. Das liegt daran, dass das Durchschnittsgesicht aus verschiedenen Gesichtern
besteht. Besonders am Mundbereich des Durchschnittsgesichts ist zu erkennen, dass die
Trainingsbilder unterschiedliche Gesichtausdrücke haben.
Als Nächstes kann die Streuungsmatrix berechnet werden:
C=
N
1 X
ai aTi = AAT .
N i=1
(3.9)
Bei einer Bildauflösung von 150 × 130 Pixel, ist C eine
19500 × 19500-Matrix (D × D). Das bedeutet, aus C können potenziell D Eigenvektoren gewonnen werden, was bei Abbildung 3.5: Das durchgroßem D aufwändig sein kann. Ist jedoch die Anzahl der
Trainingsvektoren, die in die Berechnung von C einfließen,
schnittliche Gesicht zur verwendeten Trainingsmenge.
kleiner als die Dimension der Vektoren, falls also N < D gilt, dann können nach [TP91a]
aus C nur N − 1 Eigenvektoren berechnet werden, deren Eigenwert größer Null ist. Aus
diesem Grund ist es nicht erforderlich C direkt zu berechnen.
Stattdessen werden die Eigenvektoren zur Matrix
C 0 = AT A
(3.10)
31
berechnet. Es besteht nämlich zwischen Eigenvektoren ui von C und Eigenvektoren vi von
C 0 für i = 1..N folgender Zusammenhang (siehe dazu auch Definition des Eigenwertproblems in Kapitel 2.1.2):
T
T
C 0 vi = λi vi ⇐⇒ A |A{z
A} vi = Aλi vi ⇐⇒ AA
| {z } Avi = λi Avi .
=C 0
(3.11)
=C
An der letzten Gleichung ist erkennbar, dass die Eigenvektoren von C dem Produkt Avi
entsprechen, also ist für alle i = 1..N
ui = Avi .
(3.12)
Auf diese Weise können indirekt N Eigenvektoren ui zu den größten Eigenwerten von C
berechnet werden, von denen höchstens N − 1 einen Eigenwert von ungleich Null besitzen.
Diese Eigenvektoren sind die Eigenfaces des Gesichtsraums.
3.2.3
Projektion
In Kapitel 3.2.2 wurde erklärt, wie Eigenfaces für den Unterraum berechnet werden. Dieses
Kapitel setzt sich mit der Projektion von Gesichtern mit Hilfe von Eigenfaces auseinander.
Soll der Gesichtsraum P Dimensionen haben, dann sortiert man die berechneten Eigenfaces ui absteigend nach ihren Eigenwerten und behält die P ersten. Aus diesen P Eigenfaces wird jetzt eine Transformationsmatrix U definiert, mit der jedes D-dimensionale
Bild in den Gesichtsraum projiziert werden kann. Die Transformationsmatrix U ist eine
P × D-Matrix, die die Vektoren ui als Zeilen enthält. Um dann ein Gesicht als Vektor x
in den Unterraum zu projizieren, wird es durch Subtraktion des Durchschnittvektors m
zentriert und dann durch Transformation mit U (vgl. Kapitel 2.1.1) in den Gesichtsraum
projiziert:
z = U (x − m).
(3.13)
Fünf Eigenfaces zu den größten Eigenwerten sind in Abbildung 3.6 visualisiert. Sie beschreiben die größten Variationen innerhalb der Trainingsbilder. Beispielsweise trägt das
zweite Eigenface (v. links) zur Rekonstruktion von hellen Bildern bei, das dritte Eigenface charakterisiert lächelnde Personen und das vierte sowie fünfte Eigenface beschreiben
Gesichtsbehaarungen. Im Unterschied dazu charakterisieren die unwichtigsten Eigenfaces
nur unwesentliche Details der Trainingsbilder. Fünf der Eigenfaces zu den kleinsten Eigenwerten sind in Abbildung 3.7 abgebildet.
Ist ein unbekanntes Gesicht als Vektor in den Unterraum projiziert worden, dann ordnet der Nächste-Nachbarn-Klassifikator es einer Person aus der Datenbank zu (vgl. Kapitel
3.1.2). Die Person, dessen Gesichtsprojektion den geringsten Abstand zur Projektion des
gesuchten Gesichts hat, ist der gesuchten Person am ähnlichsten und folglich auch unter
allen bekannten Personen am wahrscheinlichsten die gesuchte Person.
32
Abbildung 3.6: Die wichtigsten fünf Eigenfaces eines Gesichtsraums.
Abbildung 3.7: Die unwichtigsten fünf Eigenfaces eines Gesichtsraums.
Außerdem kann eine Rückweisung von Bildern realisiert werden, auf denen kein Gesicht abgebildet ist. Dazu wird der Rekonstruktionsfehler des Bildes betrachtet, ist dieser
zu groß (es muss zuvor eine Grenze definiert werden), dann konnte das Bild nicht gut mit
Eigenfaces repräsentiert werden. In so einem Fall handelt es sich bei dem Bild wahrscheinlich um kein Gesicht und das Verfahren kann entsprechend reagieren.
3.3
Lineare Diskriminanzanalyse
Das zweite Gesichtserkennungsverfahren, das wir im Rahmen dieser Arbeit kennenlernen,
ist die lineare Diskriminanzanalyse (Linear Discriminant Analysis, LDA). Die LDA ist als
Fishers Diskriminanzanalyse auf R. A. Fisher zurückzuführen und wird deshalb im Kontext
der Gesichtserkennung oft auch als Fisherfaces-Technik bezeichnet (vgl. [BHK97]).
3.3.1
Prinzip
Die LDA ist ein klassenbasiertes Verfahren, bei dem mehrere Gesichter einer Person als
Klasse aufgefasst werden. Ziel der LDA ist es Diskriminanzkomponenten zu finden, die es
am besten erlauben zwischen verschiedenen Klassen zu unterscheiden. Wie in Abbildung
3.8 erkennbar, ist die Grundidee des Verfahrens, den Unterraum so zu wählen, dass bei
der Projektion der Bilder die Streuung zwischen den Klassen (Interklassenstreuung) maximiert und gleichzeitig die Streuung innerhalb jeder Klasse (Intraklassenstreuung) minimiert wird. Dadurch wird im Unterraum die Unterscheidbarkeit der projizierten Gesichter
verschiedener Personen erleichtert.
Bei der LDA wird eine Eigenwertaufgabe formuliert mit dem Ziel, einen Unterraum
zu bestimmen, der die beiden oben genannten Eigenschaften erfüllt. Die Lösung der Eigenwertaufgabe liefert dann Eigenvektoren, die den gewünschten Unterraum aufspannen.
3.3. LINEARE DISKRIMINANZANALYSE
33
Abbildung 3.8: Trennung von Klassen bei der LDA. Dargestellt ist ein Unterraum aus zwei
Eigenvektoren u1 und u2 . Es sind jeweils drei Projektionen (Punkte) von unterschiedlichen Gesichtsbildern zu zwei Personen P1 und P2 vorhanden.
Im Zusammenhang mit Gesichtserkennung werden Eigenvektoren der LDA (mit Bezug zu
den Eigenfaces) oft auch als Fisherfaces bezeichnet (vgl. z.B. [BHK97]).
3.3.2
Direkte Fisherfaces
Im Folgenden erklären wir, wie man bei der Berechnung von Fisherfaces vorgehen kann,
um eine Minimierung der Interklassenstreuung sowie eine Maximierung der Intraklassenstreuung der Trainingsbilder im Unterraum zu erreichen. Wir orientieren uns am Vorgehen
nach [Fin03] (S. 147ff), [Fin12] (S. 51f), [Bev01], [DHS01] (S. 117ff) sowie nach der Originalliteratur zu Fisherfaces in [EC96].
Für die LDA ist eine annotierte Trainingsmenge erforderlich, in der jedes Gesichtsbild
einer Klasse zugeordnet ist. Sei jedes Gesichtsbild als ein D-dimensionaler Vektor gegeben
und die Trainingsmenge in K Klassen aufgeteilt. Die gesamte Trainingsmenge x1 , ..., xN
ist dann eine Vereinigung aus K Teilmengen, also
Ω=
K
[
Ωi .
(3.14)
i=1
Das Durchschnittsgesicht jeder Klasse i ist
mi =
1 X
x
|Ωi | x∈Ω
(3.15)
i
und das Durchschnittsgesicht der gesamten Trainingsmenge ist
m=
1 X
x.
N x∈Ω
(3.16)
34
Für jede Klasse i kann ihre a-priori Wahrscheinlichkeit bestimmt werden mit:
pi =
|Ωi |
.
|Ω|
(3.17)
Die a-priori Wahrscheinlichkeiten braucht man für eine unterschiedliche Gewichtung der
Streuungswerte jeder Klasse. Um die Streuung innerhalb jedes Klassengebiets zu beschreiben, wird die Intraklassenstreuungsmatrix (within-class-scatter) SW berechnet (vgl.
[BHK97]):
SW =
K X
X
(x − mi )(x − mi )T .
(3.18)
i=1 x∈Ωi
Dies ist die Summe der Streuungen innerhalb jeder Klasse. Streuungsangaben zwischen
den Klassengebieten beschreibt man mit der Interklassenstreuungsmatrix (between-classscatter) SB , wie in [BHK97] als gewichtete Streuungsmatrix der Durchschnittsvektoren
jeder Klasse:
SB =
K
X
pi (mi − m)(mi − m)T .
(3.19)
i=1
Das Ziel ist eine minimale Intraklassenstreuung und eine maximale Interklassenstreuung. Damit beide Eigenschaften für den Unterraum gelten muss also die Funktion
J(U ) =
|U T SB U |
|U T SW U |
(3.20)
maximiert werden. Eigenvektormatrix U , die diese Funktion maximiert, kann durch Lö−1
SB bestimmt werden (vgl. [DHS01], S. 117ff).
sung des Eigenwertproblems für Matrix SW
Die gesuchten Fisherfaces sind dann Spaltenvektoren von Matrix U und die entsprechenden Eigenwerte die Einträge an der Hauptdiagonalen der Diagonalmatrix Λ zum Problem:
−1
SW
SB U = U Λ.
(3.21)
Um dieses Eigenwertproblem zu lösen, muss SW invertiert werden. Bei einer Anzahl von N
Trainingsvektoren mit jeweils Dimension D ist SW singulär und somit nicht invertierbar,
falls N ≤ D gilt (vgl. [DHS01], 117ff). Da in der Gesichtserkennung die Anzahl der Trainingsvektoren fast immer geringer ist als die Anzahl der Pixel, ist es im Allgemeinen nicht
möglich SW zu invertieren und das Eigenwertproblem aus Gleichung 3.21 direkt zu lösen.
Allerdings gibt es eine Alternativlösung, die ohne eine Matrixinvertierung auskommt und
die gleichen Eigenvektoren liefert.
3.3.3
Indirekte Fisherfaces
In diesem Abschnitt wird beschrieben, wie die Matrixinvertierung bei dem Eigenwertproblem aus Gleichung 3.21 umgangen werden kann. Durchgeführt wird ein zweistufiges
Vorgehen (vgl. [Fin03], S. 147ff).
3.3. LINEARE DISKRIMINANZANALYSE
35
Im ersten Schritt wird Matrix SW auf Einheitsform gebracht, damit sie durch weitere
Transformationen nicht verändert wird. Dazu berechnet man aus dem Eigenwertproblem
SW V = V Λ
(3.22)
Eigenvektormatrix V und Eigenwertematrix Λ von SW .
1
Aus der Eigenwertematrix Λ wird dann Matrix Λ− 2 wie folgt berechnet:

− 21
λ1
− 12
Λ



=



0
−1
0
..
.
λ2 2
..
.
0
0

···
0 

0 

.
.. 

. 
···
..
.
−1
· · · λD 2
(3.23)

1
Transformiert man nun die Trainingsdaten mit Λ− 2 V T , erhält man als neue Intraklassenstreuungsmatrix:
1
1
S̃W = Λ− 2 V T SW V Λ− 2 = E.
(3.24)
Matrix S̃W ist also eine Einheitsmatrix. Das bedeutet, die Klassengebiete weisen eine
Streuung von Eins auf und S̃W wird die durch weitere (orthogonale) Transformationen
der Daten nicht beeinflußt.
Durch die erste Transformation der Daten zur Normierung der Intraklassenstreuung
(s. Gleichung 3.24) hat sich die Interklassenstreuungsmatrix SB geändert und ist jetzt:
1
1
S̃B = Λ− 2 V T SB V Λ− 2 .
(3.25)
Das Lösen des Eigenwertproblems für S̃B liefert die Eigenvektormatrix V . Die Transformation mit V ist der zweite Schritt des Verfahrens. Beide Transformationen können in
1
einer Transformationsmatrix U = V T Λ− 2 V T zusammengefasst werden. Diese enthält die
gesuchten Fisherfaces als Spaltenvektoren.
3.3.4
PCA+LDA
Das LDA-Verfahren ist in der Praxis nicht immer direkt umsetzbar, da mehrere große
Matrizen berechnet werden müssen. Das ist nicht besonders effizient und die Arbeit von
[ZCK98] hat außerdem ergeben, dass die Durchführung der LDA auf einer Datenmenge,
die mit der PCA dekorreliert wurde, zu besseren Ergebnissen führt als die reine LDA. Bei
so einem Vorgehen werden zuerst die Eigenfaces aus der PCA für die ursprünglichen Bilder
berechnet und anschließend werden die Fisherfaces zu der mit den Eigenfaces projizierten Datenmenge berechnet. Zur Klassifikation kombiniert man dann beide Transformationen. Dieses hybride Verfahren aus PCA und LDA wird oft als PCA+LDA bezeichnet
(vgl. z.B. [ZCP99]). Die Funktionsweise der PCA+LDA ist in Abbildung 3.9 schematisiert. Ein Bild wird erst mit der PCA und danach mit der LDA transformiert, bevor es
36
Abbildung 3.9: Schema des PCA+LDA-Vorgehens.
abschließend klassifiziert wird. Die Klassifikation projizierter Bilder wird dabei mit dem
Nächste-Nachbarn-Klassifikation durchgeführt, wie in Kapitel 3.1.2 beschrieben. Bei den
Experimente in Kapitel 4 wird eine Implementierung der PCA+LDA-Methode verwendet.
In Abbildung 3.10 sind fünf Fisherfaces zu den größten Eigenwerten eines durchgeführten PCA+LDA-Verfahrens zu sehen. Fisherfaces der PCA+LDA erlauben eine bessere
Unterscheidung zwischen Gesichtsbildern verschiedener Personen als die Fisherfaces der
reinen LDA, da sie eine auf Gesichter spezialisierte Verallgemeinerung der LDA-Fisherfaces
sind (die Darstellung der reinen LDA-Fisherfaces ähnelt Gesichtern kaum) (vgl. [ZCP99]).
Außerdem sind in Abbildung 3.10 aufgrund der Vollständigkeit fünf Fisherfaces zu den
kleinsten Eigenwerten der PCA+LDA abgebildet. Im Allgemeinen können keine Aussagen
darüber gemacht, welchen Bereich des Bildes ein Fisherface repräsentiert.
Abbildung 3.10: Die wichtigsten fünf Fisherfaces bei einer PCA+LDA.
Abbildung 3.11: Die unwichtigsten fünf Fisherfaces bei einer PCA+LDA.
3.4
Hauptkomponentenmischung
Die Hauptkomponentenmischung (Mixture of Principal Components, MPC) ist das dritte
in dieser Arbeit betrachtete Verfahren. Es wurde ursprünglich in [TC02b] mit dem Zweck
der Fehlerverdeckung in Videoübertragungen vorgestellt. Daraufhin erprobten die Autoren
die MPC in [TC02a] als Verfahren zur Gesichtserkennung und berichteten auf der PIEDatenbank bessere Erkennungsraten mit der MPC als mit der PCA.
3.4. HAUPTKOMPONENTENMISCHUNG
3.4.1
37
Modell
Die MPC ist eine lineare Erweiterung der PCA, die mehrere PCA-Unterräume in einem
Modell kombiniert. In Kapitel 2.2.2 wurde erklärt, dass Daten, die sich auf mehrere Häufungsgebiete verteilen, mit einer Mischverteilung besser modelliert werden können als mit
einer einzelnen Normalverteilung. Analog zu der Erstellung eines Mischverteilungsmodells
durch eine Kombination mehrerer Normalverteilungen, ist die Idee der MPC, mehrere
PCA-Unterräume in einem Modell zu vereinen. Dadurch sollen Gesichtsvariationen genauer repräsentiert werden können. Statt sich wie bei der einfachen PCA für eine Reihenfolge
von wichtigsten Hauptkomponenten zu entscheiden, werden bei der MPC zu verschiedenen
Gesichtseigenschaften jeweils Hauptkomponenten bestimmt, die für eine optimalere Repräsentation von Gesichtsbildern kombiniert werden. Ziel dabei ist es, den durchschnittlichen
Rekonstruktionsfehler (s. Kapitel 3.2.1) der Gesichtsbilder zu minimieren.
Durchschnittsgesicht
Eigenvektoren
M1
M2
M3
M4
Abbildung 3.12: Parameter zu vier Mischungskomponenten eines fertigen MPC-Modells. Abgebildet sind Mittelvektoren und Eigenvektoren zu Mischungskomponenten M 1, ..., M 4.
Abbildung 3.12 verdeutlicht, wie einzelne Mischungskomponenten verschiedene Eigenschaften von Gesichtern speichern. Zu jeder der vier Mischungskomponenten ist jeweils der
Mittelvektor und vier Eigenvektoren dargestellt. Zu erkennen ist, dass Mischungskomponente M 1 sich auf eher dunkelhäutige und M 2 auf Brillen tragende Personen spezialisiert
haben, während M 3 Personen mit Bart und M 4 lächelnde Personen repräsentieren.
Die MPC ist ein EM-Algorithmus und führt eine ”weiche Vektorquantisierung” durch
(vgl. Kapitel 2.3.2). Dadurch fließt jeder Unterraum des MPC-Modells in die Repräsenta-
38
tion eines Gesichts mit ein. So wie beim Schätzen von Mischverteilungen mit einem Vektorquantisierungsalgorithmus (”harte Vektorquantisierung”) und einem EM-Algorithmus,
der EM-Algorithmus zu einem genaueren Modell führt, hofft man bei der MPC ebenso
durch ein EM-Vorgehen bessere Resultate zu erzielen.
Das MPC-Modell besteht aus mehreren Mischungskomponenten. Jede Mischungskomponente spannt einen PCA-Unterraum auf, der jeweils durch eine Eigenvektormatrix und
einen Mittelvektor definiert ist. Da die MPC mehrere PCA-Unterräume kombiniert, würde
ein MPC-Modell bestehend aus einer Mischungskomponente einer gewöhnlichen PCA entsprechen. Beim Training wird zu jedem Trainingsvektor für jede Mischungskomponente ein
Gewicht berechnet, das angibt, wie stark eine Mischungskomponente zur Rekonstruktion
dieses Vektors beiträgt.
Abbildung 3.13: Schema für das Training eines MPC-Modells (nach [TC02b]).
Im Expectation-Schritt des iterativen EM-Algorithmus werden die Gewichte und der
Rekonstruktionsfehler berechnet. Im Maximization-Schritt wird dann der Rekonstruktionsfehler durch Neuberechnung der Mittelvektoren und Eigenvektoren zu jeder Mischungskomponente minimiert. Das Vorgehen zum Bestimmen der Parameter (Training) für das
MPC-Modell ist in Abbildung 3.13 dargestellt. Zu Beginn werden die Modellparameter
(z.B. zufällig oder mit Ergebnissen eines Vektorquantisierungsverfahrens) initialisiert.
Anschließend folgen iterativ die EM-Schritte:
• Berechnung der neuen Gewichte für jeden Vektor zu jeder Mischungskomponente.
39
• Berechnung der neuen Mittelwertvektoren zu jeder Mischungskomponente.
• Berechnung der neuen Eigenvektoren zu jeder Mischungskomponente.
Diese drei Schritte werden wiederholt, bis keine wesentliche Änderung der Modellparameter (Mittelvektoren und Eigenvektoren jeder Komponente) mehr festgestellt wird, d.h. bis
keine Reduzierung des Rekonstruktionsfehlers mehr erzielt wird. Die Parameter der MPC
sind die Eigenvektoren und die Mittelvektoren zu jeder Komponente. Die Gewichte sind
kein Teil des eigentlichen Modells, sie dienen nur als Hilfe zur Berechnung der tatsächlichen
Modellparameter.
3.4.2
Optimierungsproblem
In diesem Abschnitt wird das Optimierungskriterium der MPC definiert. Mit dem Ziel
dieses Kriterium zu optimieren werden in den darauf folgenden Abschnitten die Modellparameter der MPC berechnet.
Seien die Trainingsbilder x1 , ..., xN D-dimensionale Bildvektoren. Das MPC-Modell
soll aus M Mischungskomponenten mit jeweils P Eigenvektoren bestehen. Zu Komponente
j wird der Mittelvektor mit mj und die Eigenvektormatrix, die Eigenvektoren uj1 , ..., ujP
als Spalten enthält, mit Uj bezeichnet. Des Weiteren bezeichnet man das Gewicht zum
Vektor xi für Komponente j als wij .
Die Rekonstruktion eines Vektors xi zu Mischungskomponente j ist:
x̂ij = mj +
P h
X
i
(xi − mj )T ujk ujk .
(3.26)
k=1
Dies entspricht der Projektion des Vektors xi mit dem j-ten Komponentenraum und der
anschließenden Rückprojektion. Der dabei entstehende Informationsverlust wird Rekonstruktionsfehler zu Komponente j genannt. Dieser Fehler ist die euklidische Distanz des
Originalvektors xi zu seiner Rückprojektion x̂ij . Die Distanz von Vektor xi zur Summe
seiner gewichteten Rekonstruktionen aus jeder Mischungskomponente ist dann:
M
X
= xi − X̂i wi .
xi −
w
x̂
ij
ij
j=1
(3.27)
Die Rekonstruktionsmatrix X̂i enthält als Spaltenvektoren die Rekonstruktionen xi1 , ..., xiM
zu den Mischungskomponenten. Im Gewichtsvektor wi sind Gewichte wi1 , ..., wiM die Einträge. Das Ziel der MPC ist es, den durchschnittlichen Rekonstruktionsfehler für die gesamte Trainingsmenge zu minimieren. Dies lässt sich als Optimierungsproblem wie folgt
formulieren:

  
N M
P h


i
X
X
X
1
 
min =
wij mj +
(xi − mj )T ujk ujk .
xi −
mj ,ujk

 N i=1 j=1
k=1

 |
{z
} =x̂ij
(3.28)
40
Mit Hilfe dieses Optimierungsproblems werden in Kapitel 3.4.4 die Modellparameter
der MPC bestimmt.
3.4.3
Gewichte
In diesem Abschnitt wird die Berechnung der Gewichte erläutert, die für das MPC-Training
benötigt werden.
Für jeden Vektor xi muss der Gewichtsvektor so bestimmt werden, dass der Rekonstruktionsfehler (s. Formel 3.27) für xi minimiert wird. Dies lässt sich als Optimierungsproblem formulieren:
min = xi − X̂i wi .
(3.29)
wi
Für jeden Vektor xi müssen sich seine Gewichte zu Eins summieren. Diese Nebenbedingung
wird mathematisch formuliert:
M
X
wij = 1
j=1
(3.30)
⇐⇒
wiT 1 − 1 = 0.
Dabei ist 1 ein M -dimensionaler Spaltenvektor mit Einsen als Einträgen. Diese Nebenbedingung integriert man nun mit Hilfe des Lagrange-Multiplikators (vgl. Kapitel 2.3.3)
in das Optimierungsproblem 3.29 und erhält (die Wurzel der euklidischen Norm konnte
entfernt werden, da dadurch das Optimierungsergebnis nicht beeinflußt wird):
min =
wi ,λ
xi − X̂i wi
T xi − X̂i wi + λ wiT 1 − 1
.
(3.31)
Um das Minimum dieser Optimierungsfunktion zu bestimmen, wird die Funktion nach
ihren Veränderlichen wi und λ abgeleitet und die Ableitung gleich Null gesetzt. Dadurch
entsteht das folgende lineare Gleichungssystem:
2X̂iT X̂i wi − 2X̂iT xi + λ1 = 0
1T wi = 1.
(3.32)
Dieses ist offensichtlich äquivalent zur Matrixschreibweise:

2X̂iT X̂i 1

1T
0

wi

λ


2X̂iT xi
=
1

.
(3.33)
Das lineare Gleichungssystem kann beispielsweise mit dem Gauß-Verfahren gelöst werden.
Die Lösungen sind die gesuchten optimalen Gewichte, die für die gegebenen Parameter
zum minimalsten Rekonstruktionsfehler führen.
3.4.4
41
Modellparameter
Jede Mischungskomponente der MPC ist definiert durch Eigenvektoren und einen Mittelvektor. In diesem Abschnitt wird die Berechnung dieser Parameter beschrieben.
Die Optimierungsfunktion für die MPC wurde bereits in Gleichung 3.28 formuliert.
Aus dem Nullsetzen der Ableitungen dieser Funktion folgt, dass der Mittelvektor zur
Mischungskomponente r sich ergibt durch (vgl. [TC02b]):
mr = PN
1
2
i=1 wir


N
X

wir xi −
i=1
M
X

wij x̂ij 
(3.34)
j=1,j6=r
Dies entspricht dem normierten, gewichteten Durchschnitt der Trainingsvektoren, von denen zuvor jeweils ihre gewichtete Summe der Rekonstruktionen subtrahiert wurde.
Zur Berechnung der Eigenvektoren von Mischungskomponente r wird das Optimierungsproblem in Gleichung 3.28 zum Eigenwertproblem
Cr Ur = ΛUr
(3.35)
umgeformt, sodass Matrix Cr gegeben ist durch (vgl. [TC02b]):

h
wir (xi − mr ) xTi + xi (xi − mr )T
i




h
i

 − PM w w (x − m ) mT + m (x − m )T
ij
ir
i
r
j
i
r
j=1
j
N 

1 X

Cr =
ih
i
N i=1 

PP h T
T
T
 − PM
k=1 ujk (xi − mj ) (xi − mr ) ujk + ujk (xi − mr )
j=1,j6=r wij wir




2 (x − m ) (x − m )T
−wir
i
r
i
r
(3.36)
Die Lösung des Eigenwertproblems für Cr liefert Eigenvektormatrix Ur mit Eigenvektoren
ur1 , ..., urD als Spaltenvektoren. Die P Eigenvektoren zu den größten Eigenwerten sind
dann die gesuchten Eigenvektoren für Mischungskomponente r.
3.4.5
Merkmalsvektoren zur Klassifikation
Ist das MPC-Modell erstellt, kann mit der Klassifizierung unbekannter Gesichter begonnen
werden.
Zunächst soll verdeutlicht werden, dass die Entwickler der MPC ihr Verfahren auf
eine etwas andere Weise zur Gesichtserkennung eingesetzt haben als wir es tun werden.
Sie trainierten ein MPC-Modell pro Person (vgl. [TC02a]). Dadurch sollten variierende
Ansichten, Blickwinkel und Beleuchtungsstärken von Gesichtern einer Person in einem
Modell besser repräsentiert werden. Zur Klassifikation eines unbekannten Gesichts wurden







.







42
dann die Rekonstruktionsfehler jedes MPC-Modells betrachtet. Die Person zum MPCModell, für das das unbekannte Gesicht den geringsten Rekonstruktionsfehler aufweiste,
war dann die unbekannte Person.
Für ihre Versuche verwendeten die Autoren der MPC eine Trainingsmenge von fünf
Personen mit jeweils 286 Bildern, unseren Experimenten in Kapitel 4 liegt jedoch eine
Trainingsmenge von 501 Personen (mit einer geringen Anzahl von Bildern pro Person)
zugrunde. Es wäre rechnerisch sehr aufwändig 501 MPC-Modelle zu erstellen und zu speichern, die außerdem auch nur wenige Bilder für ihr Training zur Verfügung hätten. Aus
diesem Grund trainieren wir ein einziges Modell für die gesamte Trainingsmenge und führen ebenso eine alternative Klassifikation unbekannter Gesichter durch. Im Folgenden wird
beschrieben, wie mit Hilfe eines fertigen MPC-Modells Merkmalsvektoren gebildet werden,
an denen klassifiziert wird.
Ein unbekanntes Gesicht wird als Vektor y in jede Mischungskomponente j projiziert,
indem y erst mit Mittelvektor mj zentriert und anschließend mit Eigenvektormatrix Uj
transformiert wird. Dadurch erhält man M Projektionsvektoren z1 , ..., zM :
zj = UjT (y − mj ) .
(3.37)
Das Projizieren der Gesichter in jeden Unterraum ist in Abbildung 3.14 illustriert. Dargestellt sind zwei Unterräume, die jeweils drei Projektionen enthalten. Die Koeffizienten
der Projektionen sind für jede Mischungskomponente verschieden, da jeder Unterraum auf
unterschiedliche Eigenschaften von Gesichtern trainiert ist.
Zum Schluß werden die Projektionen der Unterräume kombiniert, sodass ein einzelner
Merkmalsvektor z ensteht:
z=
M
X
zj .
(3.38)
j=1
Nach diesem Schema wird auch jeder Trainingsvektor als Merkmalsvektor repräsentiert,
sodass jetzt mit dem Nächste-Nachbarn-Klassifikator das unbekannte Gesicht einem der
Trainingsvektoren zugeordnet werden kann (vgl. Kapitel 3.1.2).
Die Idee die Projektionen miteinander zu kombinieren wird durch Abbildung 3.14 begründet. Die Grundannahme ist, dass zwei ähnliche Gesichter auch ähnliche Projektionen
haben, wodurch wiederrum ihre Kombinationen ähnlich sind und durch die geringe Distanz
der Kombinationen zueinander sie mit dem Nächste-Nachbarn-Klassifikator als Gesichter
einer Person identifiziert werden. In der Abbildung sind die Projektionen a1 und a2 einer
Person mit Gesichtsvektor a in den beiden Unterräumen zu sehen. Wird ein Gesichtsvektor b, der an gleichen Pixelpositionen ähnliche Werte besitzt wie Vektor a, in die beiden
Unterräume projiziert, dann werden die Koeffizienten seiner beiden Projektionen ähnlich
zu den beiden Projektionen von a sein. Folglich ist die Distanz zwischen den Kombinationen der jeweiligen Projektionen gering und die beiden können als Gesichter einer Person
aufgefasst werden. Wird hingegen ein Gesichtsvektor c projiziert und die Kombination
43
Abbildung 3.14: Projektion von Gesichtern bei einem aus zwei Mischungskomponenten bestehenden MPC-Modell. Die erste Mischungskomponente hat Mittelvektor m1 und Eigenvektoren
u11 und u12 , die zweite Komponente hat Mittelvektor m2 und Eigenvektoren u21 und u22 . Dargestellt sind jeweils Projektionen dreier Gesichtsvektoren a, b und c in die beiden Unterräume (nach
[TC02b]).
seiner Projektionen weist einen großen Abstand zu der Kombination für Gesicht a oder b
auf, dann handelt es sich bei Gesicht c wahrscheinlich um nicht die gleiche Person wie bei
Gesicht a oder b.
Da die verschiedenen Unterräume unterschiedliche Vektorräume sind, kann der AdditionsAnsatz nicht mathematisch begründet werden. Aus diesem Grund wurden anstelle einer
Addition der Projektionen einige andere Möglichkeiten zur Bildung von Merkmalsvektoren
untersucht. Eine davon war beispielsweise die Konkatenation der Projektionen zu einem
einzelnen Vektor, der so unveränderte Informationen jeder Mischungskomponente enthielt.
Dieser lange Merkmalsvektor wurde dann mit dem Nächste-Nachbarn-Klassifikator einer
Person zugeordnet. Ein anderer Versuch lag darin, jedes Gesicht mit allen Gesichtern
der Mischungskomponente zu klassifizieren, die das Gesicht mit geringstem Rekonstruktionsfehler repräsentieren konnte. Jedoch war unter allen Versuchen die Kombination der
Projektionen zu einem einzelnen Merkmalsvektor (vgl. Formel 3.38) am erfolgreichsten.
44
Dennoch werden Ergebnisse alternativer Möglichkeiten zur Bildung von Merkmalsvektoren
in Kapitel 4.4 angegeben und diskutiert.
3.5
Zusammenfassung
Ein Gesichtserkennungssystem hat im Allgemeinen drei Komponenten: Eine Datenbank
von Gesichtsbildern, eine Komponente zur Normalisierung von Bildern und einen Klassifikator (vgl. Kapitel 3.1). Die ersten beiden Komponenten werden in Kapitel 4 beschrieben.
Die Identifizierung von Personen führt der Nächste-Nachbarn-Klassifikator durch (vgl.
Kapitel 3.1.2). Dabei wird ein Vektor demjenigen Vektor zugewiesen, der die geringste Distanz zu ihm aufweist. Zur Messung von Distanzen können zahlreiche Distanzfunktionen
verwendet werden, von denen einige grundlegende in Kapitel 3.1.3 eingeführt wurden.
Das PCA-basierte Vorgehen wird als Eigenfaces-Technik bezeichnet (vgl. Kapitel 3.2).
Eigenfaces sind die charakteristischsten Eigenvektoren zur Streuungsmatrix der Trainingsbilder und verlaufen folglich in Richtung der größten Varianz der Daten. Eigenfaces spannen als Basisvektoren einen Unterraum auf. Gesichtsbilder werden als Vektoren in den
Unterraum projiziert und mit dem Nächste-Nachbarn-Klassifikator Personen zugeordnet.
Bei der Fisherfaces-Methode (Kapitel 3.3) wird mit der LDA durch Kenntnis von
Klassenzugehörigkeiten der Trainingsbilder ein Unterraum bestimmt, in dem projizierte
Gesichtsbilder eine maximale Streuung zwischen Klassen und eine minimale Streuung
innerhalb von Klassen aufweisen. Es wird eine schärfere Klassentrennung und dadurch eine
leichtere Klassifikationsaufgabe erreicht. Das Verfahren kann verbessert werden, indem die
Trainingsbilder zuerst in den PCA-Unterraum projiziert werden und dann die LDA auf
diese Projektionen angewendet wird (vgl. Kapitel 3.3.4).
Die MPC ist ein PCA-basiertes EM-Verfahren (vgl. Kapitel 3.4). In einem Modell
werden mehrere Unterräume kombiniert, die jeweils für verschiedene Gesichtseigenschaften zuständig sind. Dadurch können Gesichtsbilder genauer - das heißt mit geringerem
Rekonstruktionsfehler - repräsentiert werden.
Kapitel 4
Versuche
Nachdem die Hauptkomponentenanalyse (PCA), die lineare Diskriminanzanalyse (LDA)
und die Hauptkomponentenmischung (MPC) in Kapitel 3 beschrieben wurden, werden die
drei Verfahren auf ihre Erkennungsleistung von Gesichtsbildern der FERET-Datenbank
untersucht. Die FERET-Datenbank wird in Kapitel 4.1 vorgestellt und das FERETProtokoll zum Durchführen standardisierter Tests wird erläutert.
Da Bilder der FERET-Datenbank unter verschiedenen Bedingungen aufgenommen
wurden, muss eine Normalisierung der Bilder durchgeführt werden. Die Normalisierungsprozedur ist für jedes der drei Verfahren identisch und wird detailliert in Kapitel 4.2 erklärt.
Im Anschluß erfolgt eine kurze Vorstellungen der verwendeten Programmiersprache zur
Implementierung der Verfahren.
Schließlich werden die FERET-Tests unter standardisierten Bedingungen (soweit dies
möglich ist) in Kapitel 4.4 durchgeführt und evaluiert, sodass Aussagen darüber gemacht
werden können, ob signifikante Unterschiede zwischen den Erkennungsleistungen der getesteten Verfahren existieren. Aussagen zur Signifikanz werden dabei mit Hilfe von Konfidenzintervallen geführt. Um dann die drei Verfahren weiter zu vergleichen, werden Parameter
(Bildgröße, Anzahl der Dimensionen und Distanzfunktion) in Kapitel 4.5 variiert. Mit den
so gefundenen, für das jeweilige Verfahren besten Parametern wird zum Schluß überprüft,
ob die Erkennungsleistung der Verfahren durch Kombination dieser Parameter gesteigert
werden kann.
4.1
FERET-Programm
Das Face Recognition Technology (FERET) Programm wurde im September 1993 vom
Army Research Laboratory (ARL) eingeleitet, um den Stand der Technik in der Gesichtserkennung zu messen und eine unabhängige Methode zum Testen und Auswerten
von Gesichtserkennungsalgorithmen zu entwickeln. Dadurch sollte die Entwicklung von
Gesichtserkennungsverfahren unterstützt werden, die für Sicherheit sorgen, Kriminalität
45
46
KAPITEL 4. VERSUCHE
reduzieren und intelligente Systeme fördern würden (vgl. [PMRR00]). Zu diesem Zweck
wurde die FERET-Gesichtsdatenbank erstellt und ein standardisiertes Auswertungsprotokoll definiert. Das Prokoll legt fest, mit welchen Bildern der Test eines Verfahrens gemacht
wird und wie die Ausgabe und Leistung bewertet werden soll (vgl. [PWHR98]).
4.1.1
Motivation
Bevor FERET als Auswertungsprotokoll und unabhängige Datenbank zur Verfügung stand,
gab es keine einheitlichen Methoden zum Bewerten von Gesichtserkennungsalgorithmen.
Die meißten Wissenschaftler erstellten eigene kleine Datenbanken, die aus nur einigen
Dutzend Individuen bestanden und auf das Verfahren angepasst waren (vgl. [PRD96]).
Als Folge davon konnten verschiedene Verfahren nicht richtig miteinander verglichen werden und viele Forscher berichteten in ihren Arbeiten Erkennungsraten von über 95%.
Heute können Wissenschaftler die Leistung eines Gesichtserkennungsalgorithmus mit dem
FERET-Protokoll bewerten und dadurch erfahren, in welchen Bereichen der Gesichtserkennung ihre Verfahren verbessert werden sollten.
Heute zählt die FERET-Datenbank zu den umfangreichsten allgemein vorhandenen
Gesichtsdatenbanken. Sie gilt als der De-facto-Standard zum Testen und Auswerten von
Gesichtserkennungsverfahren. Dadurch, dass mit ihr verschiedene Verfahren verglichen
werden können, hat die Datenbank dazu beigetragen, den wissenschaftlichen Stand in der
Gesichtserkennung voranzutreiben und Bereiche aufzudecken, in denen weiter geforscht
werden muss.
4.1.2
FERET-Tests
Aus den durchgeführten FERET-Tests haben sich die heutigen Standard-Tests entwickelt,
die zur Beurteilung von Algorithmen verwendet werden. Die Tests waren so ausgerichtet, dass man Aussagen über die Leistung von Gesichtserkennungsverfahren mit großen
Datenbanken, Personenveränderungen über längere Zeiträume, Bildskalierungen, Posenänderungen, verschiedenen Beleuchtungsstärken und Hintergründen zu arbeiten treffen
konnte. Teilgenommen haben verschiedene Universitäten und Firmen, die in der Gesichtserkennung forschten. Die Rechendauer eines Algorithmus wurde bei der Auswertung nicht
bewertet, sondern nur die Erkennungsleistung. Die Ergebnisse der FERET-Tests sind ausführlich in [PRD96] protokolliert.
Die Resultate eines Algorithmus wurden in sogenannten CMS-Kurven (cummulative
match score curves) angegeben. Eine CMS-Kurve stellt die Erkennungsleistung eines Verfahrens für Rang k (gewöhnlich für k = 1..50) dar. Ein Gesicht ist unter Rang k erfolgreich
identifiziert, wenn sich unter den ersten k Ausgabekandidaten des Verfahrens die korrekte
Person zu diesem Gesicht befindet. Die Idee von CMS-Kurven ist es nicht anzugeben, wie
eindeutig ein Verfahren eine Person identifizieren kann, sondern die Sicherheit des Verfah-
4.1. FERET-PROGRAMM
47
rens dafür zu messen, dass die gesuchte Person unter den ersten k Ausgabekandidaten ist.
Gibt das Verfahren dann die k ersten Personen aus, kann in der Praxis z.B. ein Mensch die
gesuchte Person aus den wenigen k Personen manuell identifizieren. Dabei wird vorausgesetzt, dass jede Testperson dem Verfahren bekannt ist (geschloßenes Universum) (vgl.
[PRD96]).
Im Laufe des FERET-Programm von 1994 bis 1997 wurden drei großangelegte Tests
durchgeführt. Gemessen wurden vollautomatische Algorithmen, die Gesichter in Bildern
selbstständig lokalisieren, normalisieren und identifizieren konnten. Als Gallerie werden
Bilder der Personen, die dem Algorithmus bekannt sind, und Bilder unbekannter Person als Testbilder bezeichnet. Trainingsbilder werden zur Initialisierung des Algorithmus
verwendet. Diese sind Bilder von Personen aus der Gallerie.
Der erste Test war der August-1994 Test. Ziel des Tests war es, eine Messbasis zu
erschaffen, an der sich Gesichtserkennungs-Algorithmen erstmals orientieren konnten. Es
wurden drei Teiltests durchgeführt. Der Erste bestand aus einer großen Gallerie und testete
die allgemeine Identifizierungsleistung der Algorithmen. Der Zweite war der Falsch-AlarmTest. Diesem Test lag ein offenes Universum zugrunde und es wurde gemessen, wie gut
ein Verfahren Gesichter ablehnt, die sich nicht in der Gallerie befinden. Im dritten Test
überprüfte man die Leistung der Verfahren rotierte Gesichter zu erkennen. Dabei waren
die Kopfposition der Test-Personen bis zu 90 ◦ seitlich gedreht (vgl. [PWHR98]).
Der zweite große FERET-Test fand im März 1995 statt und basierte auf den Ergebnissen und Schlußfolgerungen des ersten Tests. Er bestand aus einer größeren Gallerie.
Der Schwerpunkt des Tests lag in der Erkennungsfähigkeit von Duplikatbildern. Ein Duplikatbild einer Person ist eine Gesichtsaufnahme, die zu einem anderen Zeitpunkt (bis
zu mehreren Jahren) gemacht wurde. Der Test ergab trotz steigenden Schwierigkeitsgrads
im Vergleich zum August-1994-Test keine sinkenden Erkennungsleistungen der Verfahren. Daraus konnte geschlußfolgert werden, dass die Verfahren besser geworden sind (vgl.
[PWHR98]).
Der September-1996 Test war der dritte FERET-Test. Er sollte den damals aktuellen
Stand der Technik verbessern und Richtungen für zukünftige Forschung vorgeben. Für
diesen FERET-Test wurden die vier Testsets entwickelt, die in der FERET-Datenbank
dokumentiert sind und in Kapitel 4.1.3 beschrieben werden. Der Test hat gezeigt, dass das
beste Verfahren von der jeweiligen Testkategorie abhängt, denn kein getestetes Verfahren
konnte in allen Kategorien die besten Ergebnisse erzielen (vgl. [MP98]).
4.1.3
Datenbank
Für die Auswertung von Algorithmen wird eine gemeinsame Datenbank mit einer ausreichenden Anzahl von Bildern benötigt. Die FERET-Datenbank wurde ständig erweitert
48
KAPITEL 4. VERSUCHE
und an den technischen Stand von Gesichtserkennungsverfahren angepasst. Heute beinhaltet die FERET-Datenbank über 11338 Bilder von 994 verschiedenen Personen.
Für jede Person sind unterschiedliche Foto-Aufnahmen vorhanden. Ein Beispielsatz der
Fotos einer Person ist in Abbildung 4.1 zu sehen. Es sind mehrere Frontalansichten mit verschiedenen Gesichtsausdrücken, Beleuchtungsstärken und Altererungen der Personen, die
für einige Fotos auch gebeten wurden eine Brille aufzusetzen oder ihre Frisur zu verändern,
abgebildet. Außerdem konnten durch variierende Kameraabstände und Kamerapositionen
die Gesichter auf den Bildern in unterschiedlichen Skalierungen und Ansichtswinkeln aufgenommen werden.
Abbildung 4.1: Ein Beispielsatz einer Person in der FERET-Datenbank (aus [FER12]).
Die FERET-Dokumentation definiert vier Standard-Testsets, auf denen Algorithmen
mit der FERET-Datenbank ausgewertet werden sollen. Die Testsets mit ansteigendem
Schwierigkeitsgrad (nach [PMRR00]) sind:
FAFB: Das ist das vermeintlich leichteste Testset, denn es besteht aus Personen, die ihren Gesichtsausdruck oder ihr Erscheinungsbild (durch Brille o.ä.) modifizieren. Es
beeinhaltet 1195 Testbilder.
FAFC: Dieses Testset besteht aus 194 Bildern, die im Vergleich zur Gallerie andere Beleuchtungsstärken aufweisen.
DUP1: Das Testset beeinhaltet 722 Bilder. Die Aufnahme jedes Bildes liegt innerhalb eines
Zeitraums von einer Minute und 1031 Tagen nach der entsprechenden Aufnahme des
Gallerie-Bildes.
4.2. NORMALISIERUNG
49
DUP2: Dieses Testset hat sich als schwierigstes erwiesen. Es ist eine Teilmenge von dem
DUP1-Testset und besteht aus 234 Bildern, deren Aufnahme mindestens 18 Monate
nach der entsprechenden Gallerie-Aufnahme stattgefunden hat.
Die Standard-Gallerie besteht aus 1196 Personen, für die jeweils ein Frontalbild vorhanden
ist. Ein Standard-Trainingsset ist nicht von FERET vorgegeben. Für 3368 Bilder stellt
FERET die Augen- und Mundkoordinaten zur Verfügung, um Gesichtserkennungssysteme
zu unterstützen, die keine Gesichtslokalisierungskomponente besitzen. Bei den FERETTests war dies bei einigen Verfahren der Fall.
4.2
Normalisierung
Die FERET-Datenbank, der unsere Experimente zugrunde liegen, enthält Bilder, die erst
normalisiert werden müssen, bevor ein Unterraumverfahren darauf trainiert wird.
Bilder der FERET-Datenbank wurden unter verschiedenen Bedingungen aufgenommen. Dadurch soll eine reale Umgebung simuliert werden, in der Foto- und Videoaufnahmen nicht optimal auf die Gesichtserkennung angepasst sind. Fast immer ist der Hintergrund mit abgebildet oder die Größe des Gesicht auf dem Bild variiert. Um die Erkennungsrate zu verbessern, werden durch Normalisierung Informationen im Bild entfernt,
die nicht relevant oder charakteristisch für Gesichter sind. Unter anderem werden Hintergründe entfernt und Gesichter lokalisiert und auf eine einheitliche Größe skaliert.
Zur Normalisierung der Bilder für die Experimente wird die Normalisierungsprozedur
von der Colorado State University (CSU) verwendet (s. [CSU12b]). Diese Normalisierung ist eine verbesserte und stabilere Version der originalen FERET-Normalisierung. Die
CSU-Normalisierung besteht aus fünf Schritten und konvertiert ein FERET-Bild in ein
normalisiertes Bild wie folgt (vgl. [GBDB04]):
1. Integer zu Float umwandeln: Die 256 Grauwerte des Bildes werden als Gleitkommazahlen repräsentiert.
2. Geometrische Normalisierung: Anhang der Augenkoordinaten (für FERET-Bilder
vorhanden) wird das Gesicht im Bild auf eine einheitliche Position verschoben und
skaliert.
3. Maskierung: Eine elliptische Maske wird erstellt, die nur das Gesicht ausschneidet
(der Hintergrund wird abgedeckt).
4. Histogrammausgleich auf die Pixel des Gesichtsbereichs, um den gesamten Wertebereich der Pixel auszunutzen.
5. Pixelnormalisierung: Pixelwerte werden so skaliert, dass der Durchschnitt null und
die Standardabweichung eins ist.
50
KAPITEL 4. VERSUCHE
Abbildung 4.2: Beispiel für ein Original-Bild der FERET-Datenbank (links) und das entsprechende normalisierte Bild (rechts) (aus [FER12]).
Nach der Normalisierung liegt das Bild in 150 × 130 Pixel vor. In Abbildung 4.2 ist
das Ergebnis der Normalisierungsprozedur (rechtes Bild) zu sehen. Diese Prozedur wird
auf jedes Bild der FERET-Datenbank angewendet.
4.3
Implementierung
Für die Experimente werden die drei Verfahren PCA, LDA und MPC in Matlab implementiert. Matlab ist eine Programmiersprache, die primär auf die Lösung mathematischer
Probleme mit Hilfe von Matrizen ausgelegt ist. Die Sprache ist auf Matrixberechnungen
spezialisiert und da bei Unterraumverfahren die meißten Rechenschritte algebraisch durchführbar sind, eignet sich Matlab gut zur einfachen und effizienten Implementierung solcher
Verfahren. Die Implementierung jedes Verfahrens erfolgt separat voneinander, um einen
unabhängigen Vergleich der Verfahren zu ermöglichen.
4.4
Standard-Test
Das FERET-Protokoll definiert vier standardisierte Testsets, mit denen die Erkennungsleistung von Gesichtserkennungsalgorithmen gemessen wird. In diesem Abschnitt werden die
Verfahren aus Kapitel 3 unter FERET-Bedingungen getestet, die es erlauben einen möglichst direkten Vergleich zur Literatur herzustellen und die Verfahren auch miteinander zu
vergleichen. Der Vergleich wird mit Hilfe von Konfidenzintervallen geführt.
4.4. STANDARD-TEST
4.4.1
51
Durchführung
Parameter
Gallerie
Trainingsset
Testsets
PCA
LDA
MPC
1196 Bilder (1196 Personen)
501 Bilder (428 Personen)
FAFB (1195 Bilder), FAFC (194), DUP1 (722), DUP2 (234)
Bildgröße
150 × 130 px
45 × 39 px
Dimension
40% = 200
10 · 20 = 200
Distanz
Euklidisch
Tabelle 4.1: Parameterübersicht für den Standard-Test mit der FERET-Datenbank.
Eine Übersicht zu den Parametern des Tests befindet sich in Tabelle 4.1. Verwendet
werden die vier Standard-Testsets FAFB, FAFC, DUP1 und DUP2 sowie die StandardGallerie von 1196 Personen nach dem FERET-Protokoll (in Kapitel 4.1 ausführlich beschrieben). Die Gallerie enthält ein Bild pro Person. Verfahren nutzen die Gallerie, um
nach ihrem Training Personen zu identifizieren, die sich nicht in der Trainingsmenge befanden. FERET schreibt kein festes Trainingsset vor. Aus diesem Grund sind in der Literatur
unterschiedliche, beinahe willkürliche Trainingssets zu finden. Um diese Arbeit trotzdem
mit einigen anderen Arbeiten vergleichen zu können, wird das Trainingsset verwendet, das
im CSU Face Identification Evaluation System ([CSU12b]) definiert ist. Es besteht aus
501 Bildern von insgesamt 428 Personen.
PCA und LDA werden auf eine Bildgröße von 150×130 Pixel angewendet. Die Autoren
der MPC testeten ihr Verfahren auf der PIE-Datenbank (vgl. [TC02a]), die nach [SBB02]
Bilder der Größe 640×486 Pixel enthält. Diese Bildgröße wäre für ein Gesichtserkennungssystem nicht vorstellbar und die Autoren der MPC erwähnen in ihrer Arbeit nicht, welche
Skalierung sie vorgenommen haben. Wir entscheiden uns für Bilder der Größe 45 × 39, da
größere Bilder zu Speicherproblemen und sehr langen Rechenzeiten führten.
Bei dem Dimensionsreduktionsschritt werden - wie von FERET empfohlen und in den
meißten Arbeiten eingehalten - 40% von den 501 Dimensionen für den Unterraum behalten. Um einen möglichst gleichwertigen Vergleich mit der PCA und LDA zu ermöglichen,
wird die MPC für 10 Mischungskomponenten mit jeweils 20 Eigenvektoren trainiert. Dies
entspricht einer Gesamtanzahl von 10 · 20 = 200 Dimensionen im MPC-Modell. Mit der
gleichen Begründung vergleichen die Autoren der MPC in [TC02a] ihr Verfahren mit der
PCA.
Für die Klassifikation der Projektionen mit dem Nächste-Nachbarn-Klassifikator wird
die euklidische Distanz (L2-Norm) verwendet. Diese ist weitverbreiteter Standard, der in
den meißten Arbeiten als primäres Distanzmaß benutzt wird (s. z.B. [DGG05], [BSDG01]).
52
KAPITEL 4. VERSUCHE
4.4.2
Evaluierung
Nach [CSU12a]
Unsere
FAFB
FAFC
DUP1
DUP2
Durchschnitt
PCA
74,31%
4,64%
33,80%
14,10%
31,71%
LDA
61,17%
19,07%
37,95%
13,68%
32,97%
PCA
73,47%
4,64%
34,35%
14,96%
31,85%
LDA
69,29%
24,74%
23,27%
12,82%
32,53%
MPC
51,97%
9,28%
52,22%
51,71%
41,30%
Tabelle 4.2: Erkennungsraten für Rang 1 für PCA und LDA nach [CSU12a] sowie unsere Erkennungsraten für PCA, LDA und MPC für die FERET-Testsets unter standardisierten Bedingungen.
In Tabelle 4.2 sind die Ergebnisse unserer Tests (untere Tabellenhälfte) dargestellt.
Diese werden in der Tabelle den Ergebnissen von [CSU12a] (obere Tabellenhälfte) gegenübergestellt, die unter gleichen Bedingungen und gleichen Parametern durchgeführt
wurden, wie unsere Tests. Die etwas unterschiedlichen Erkennungsraten sind Folge unterschiedlicher Details in der Implementierung der Verfahren.
Konfidenzintervall
Nach [CSU12a]
Unsere
PCA
[29,83; 33,59]
LDA
[31,07; 34,87]
PCA
[29,96; 33,74]
LDA
[30,63; 34,43]
MPC
[39,31; 43,29]
Tabelle 4.3: Kofidenzintervalle zu den Ergebnissen in Tabelle 4.2.
Da es sich bei der Messungen einer Erkennungsrate an einer Stichprobe nur um eine Schätzung der tatsächlichen Erkennungsrate handelt, muss ein Toleranzbereich für
die Erkennungsrate angegeben werden, der eine statistische Schwankung repräsentiert.
Dies ist mit Konfidenzintervallen möglich. Für Aussagen zur Signifikanz werden Konfidenzintervalle einer 95%-igen Sicherheit berechnet (vgl. [PL95]). Überschneiden sich die
Konfidenzintervalle zweier Erkennungsraten nicht, ist das ein Hinweis darauf, dass ein
signifikanter Unterschied zwischen den Erkennungsraten besteht (vgl. [BSDG01]). Eine
Überschneidung der Konfidenzintervalle hingegen deutet auf keinen signifikanten Unterschied hin. Basierend auf diesen beiden Aussagen werden im Folgenden Vermutungen zu
signifikanten Unterschieden zwischen Erkennungsraten geführt.
4.4. STANDARD-TEST
53
Die Konfidenzintervalle zu den durchschnittlichen Erkennungsraten aus Tabelle 4.2
sind in Tabelle 4.3 angegeben. Es wird die durchschnittliche Erkennungsrate über alle vier
Testsets betrachtet, da festgestellt werden soll, welches Verfahren insgesamt und nicht für
einzelne Kategorien besser ist als die anderen Verfahren.
Aus Tabelle 4.3 kann man folgern, dass zwischen den Erkennungsraten für Rang 1
der PCA von [CSU12a] und unserer Implementierung der PCA kein bedeutender Unterschied besteht. Dies gilt ebenso für die LDA. Unterschiedliche Erkennungsraten zwischen
unserer LDA und der LDA von [CSU12a] sind möglicherweise ein Resultat abweichender Implementierungen. Weiterhin stellt man fest, dass nach [CSU12a] die PCA nicht
eindeutig schlechter ist als die LDA. Die gleiche Schlußfolgerung kann auch über unsere
Implemetierungen der PCA und LDA getroffen werden. Die weitere Betrachtung der Konfidenzintervalle ergibt, dass die MPC signifikant höhere Erkennungsraten hat als die PCA
und LDA. Zu dieser Einsicht gelangten die Autoren der MPC bei ihren Vergleichen des
Verfahrens mit der PCA ebenfalls (vgl. [TC02a]).
Abbildung 4.3: CMS-Kurve für PCA bis Rang 50.
In jedem der FERET-Tests war es nicht Ziel die Verfahren nur nach ihrer direkten
Identifizierungsleistung von Gesichtern zu untersuchen. Vielmehr sollten Erkennungsraten der Verfahren für die k-Nächsten-Nachbarn, also für Rang k (meißt mit k = 1..50),
angegeben werden (vgl. z.B. [PRD96]). Für diesen Zweck verwendete man CMS-Kurven
54
KAPITEL 4. VERSUCHE
Abbildung 4.4: CMS-Kurve für LDA bis Rang 50.
(s. Kapitel 4.1.2). In dieser Arbeit sollen ebenso die Erkennungsraten der untersuchten
Verfahren als CMS-Kurven dargestellt werden.
Die Erkennungsraten der PCA für Rang 1 bis Rang 50 für die vier FERET-Testsets
sind als CMS-Kurve in Abbildung 4.3 dargestellt. Zur Durchführung eines Vergleiches ist
die CMS-Kurve der LDA in Abbildung 4.4 und die CMS-Kurve der MPC in Abbildung
4.4 visualisiert. Die PCA-Kurve ist mit den CMS-Kurven nach [CSU12a] für alle vier Testsets bis auf geringe Schwankungen identisch. Die LDA-Kurve (Abbildung 4.4) ist für das
Testset DUP2 ähnlich der LDA-Kurve nach [CSU12a]. Für die restlichen Testsets schwanken die Verläufe zwar insgesamt zwischen etwa 5% und 15% (für zwei der drei Testsets
sind die Erkennungsraten unserer LDA besser), insgesamt jedoch können beide Implementierungen der LDA als gleichwertig angesehen werden. Der Grund der unterschiedlichen
Kurvenverläufe liegt wahrscheinlich in der Implementierung.
Betrachtet man die CMS-Kurve der MPC, dann fällt auf, dass diese bereits ab einem
Rang von 2 die Kurven der PCA und LDA in allen Testkategorien überragt. Die MPCKurve erreicht bereits bei Rang 6 für alle vier Testsets eine Erkennungsrate von beinahe
100%. Sogar für das Testset FAFC, bei dem die MPC für Rang 1 weniger als 10% der
Bilder korrekt erkennt (vgl. Tabelle 4.2), sind es bereits für Rang 2 fast 100%. Dieser
Wert übertrifft die Erkennungsrate des besten Algorithmus der FERET-Tests, der in der
4.4. STANDARD-TEST
55
Abbildung 4.5: CMS-Kurve für MPC bis Rang 50.
Kategorie FAFC getestet wurde (vgl. [PMRR00]). Auch für die Kategorien DUP1 und
DUP2 ist die MPC ab Rang 2 bedeutend besser als die besten Verfahren der FERETTests. Für das FAFB-Testset erreichen die Algorithmen der FERET-Tests ebenso wie die
MPC Erkennungsraten von fast 100% für Rang 2. Diese Ergebnisse erreicht das MPCVerfahren durch die genaue Repräsentation der Bilder durch mehrere Unterräume.
FAFB
FAFC
DUP1
DUP2
Durchschnitt
Addition
51,97%
9,28%
52,22%
51,71%
41,30%
Konkatenation
61,92%
1,55%
25,90%
9,83%
24,80%
min. Rekonstr.fehler
44,35%
0,00%
16,34%
8,12%
17,20%
Tabelle 4.4: Erkennungsraten der MPC unter Rang 1 für alternative Möglichkeiten zur Bildung
von Merkmalsvektoren zur Klassifikation.
In Kapitel 3.4.5 wurde erläutert, dass bei der MPC die einzelnen Projektionen in die
Unterräume addiert werden, um einen Merkmalsvektor für die Klassifikation zu bilden. Am
Ende des Kapitels erklärte man, dass alternative Methoden zur Bildung der Merkmalsvektoren untersucht wurden, die Addition jedoch die besten Erkennungsraten ergab. Neben
56
KAPITEL 4. VERSUCHE
der Addition wurden drei Alternativen getestet: Die Konkatenation der Projektionen und
der Vergleich der Projektion in der Mischungskomponente zum kleinsten Rekonstruktionsfehler des Bildes (eine ausführliche Erklärung der Alternativen ist am Ende von Kapitel
3.4.5 zu finden). In Tabelle 4.4 sind die Erkennungsraten der Alternativen aufgeführt. Das
Konfidenzintervall zur Konkatenation ist: [23, 05; 26, 55]. Dieses überschneidet sich nicht
mit dem Konfidenzintervall für die Addition (vgl. Tabelle 4.3), was darauf schließen lässt,
dass die Addition der Merkmalsvektoren eine signifikant höhere Erkennungsrate ergibt als
die beiden Alternativen. Aufbauend auf dieser Erkenntnis werden die Folgeexperimente
zur MPC mit der Addition der Projektionen durchgeführt.
4.5
Parameteroptimierung
Die Tests im vorherigen Kapitel wurden unter standardisierten Bedingungen durchgeführt.
Die Ergebnisse der Tests dienen nun als Vergleichsbasis für weitere Experimente. In diesem
Kapitel wird versucht die Erkennungsleistung der Verfahren zu optimieren, indem Parameter systematisch verändert werden. Es werden jeweils Bildgröße, Anzahl der Dimensionen
und Distanzmaße abwechselnd und unabhängig voneinander varriert.
4.5.1
Bildgröße
Zuerst wird die Bildgröße variiert, um zu entscheiden, welche Bedeutung ihr zufällt. Dabei
bleiben alle restlichen Parameter fest, wie in Kapitel 4.4 angegeben. Zum Verkleinern der
Bilder wird die Matlab-Funktion imresize() verwendet. Die verschiedenen Skalierungsergebnisse eines Beispielbildes sind in Abbildung 4.6 dargestellt.
Abbildung 4.6: Beispiel für Bildskalierungen eines normalisierten FERET-Bildes (von 100% oben
links bis 5% unten rechts) (aus [FER12]).
In Tabelle 4.5 sind die Resultate der PCA für unterschiedliche Bildskalierungen angegeben. Bis zu einer Bildskalierung auf 10% der Originalgröße ist eine streng monotone
Steigerung der durchschnittlichen Erkennungsrate bei kleiner werdenden Bildern festzu-
4.5. PARAMETEROPTIMIERUNG
57
PCA
Skal.
Pixel
FAFB
FAFC
DUP1
DUP2
Durchschnitt
100%
(150 × 130)
73,47%
4,64%
34,35%
14,96%
31,85%
90%
(135 × 117)
73,56%
4,64%
34,49%
15,39%
32,02%
80%
(120 × 104)
73,72%
4,64%
34,49%
15,39%
32,06%
70%
(105 × 91)
73,81%
4,64%
34,63%
15,81%
32,22%
60%
(90 × 78)
73,89%
4,64%
34,77%
15,81%
32,28%
50%
(75 × 65)
74,14%
4,64%
34,90%
15,81%
32,37%
40%
(60 × 52)
74,48%
4,64%
35,04%
16,24%
32,60%
30%
(45 × 39)
74,48%
4,64%
35,32%
16,67%
32,78%
20%
(30 × 26)
75,06%
5,16%
35,73%
16,67%
33,16%
10%
(15 × 13)
75,65%
4,12%
32,69%
15,39%
31,96%
5%
(8 × 7)
66,86%
2,06%
23,41%
8,55%
25,22%
Tabelle 4.5: Erkennungsraten der PCA für Rang 1 unter verschiedenen Bildskalierungen zwischen
100% und 5%.
stellen. Es wird mit Hilfe von Konfidenzintervallen untersucht, ob eine signifikante Steigerung der Erkennungsrate erzielt werden kann. Die höchste Erkennungsrate wird bei einer
Bildskalierung von 20% erreicht. Das Konfidenzintervall dazu ist: [31, 25; 35, 07]. Da sich
das Konfidenzintervall mit dem Intervall der PCA aus Tabelle 4.3 überschneidet, kann
keine signifikante Steigerung der Erkennungsrate durch Veränderung der Bildgröße geschlußfolgert werden. Daraus folgt offensichtlich auch, dass eine Verkleinerung der Bilder
auf bis zu 10% ihrer Originalgröße keine bedeutende Verschlechterung der Erkennungsrate
nach sich zieht. Bei einer Skalierung von 5% sinkt die Erkennungsrate aufgrund geringen
Informationsgehalts in den Bildern (insgesamt nur 56 Pixel in einem Bild).
Bei dem Experiment mit der LDA (Tabelle 4.6) beobachten wir einen ähnlichen Zusammenhang, wie bei der PCA (Erkennungsrate steigt bis zu einem gewissen Punkt bei
sinkender Bildgröße). Jedoch ergibt die Berechnung des Konfidenzintervalls für die durchschnittliche Erkennungsrate bei einer 10%-tigen Skalierung ([41,95; 45,97]), dass im Vergleich zur Standard-Bildgröße (vgl. Konfidenzintervall in Tabelle 4.3) eine signifikante
Steigerung der Erkennungsrate vorliegt. Durch Verkleinerung der Bildgröße kann bei der
LDA die Erkennungsrate also signifikant erhöht werden. Das ist womöglich damit zu erklären, dass bei kleineren Bildern die LDA eine schärfere Klassentrennung durchführen
kann.
Da bei der MPC Bildgrößen über 45 × 39 Pixel (entspricht einer Skalierung von 30%)
kritisch werden und jedes MPC-Training langwierig ist, verzichten wir bei der MPC auf
diesen Test und nehmen an, dass sich die Bildgröße bei diesem Verfahren analog zu den
58
KAPITEL 4. VERSUCHE
LDA
Skal.
Pixel
FAFB
FAFC
DUP1
DUP2
Durchschnitt
100%
(150 × 130)
69,29%
24,74%
23,27%
12,82%
32,53%
90%
(135 × 117)
70,21%
24,74%
24,52%
14,52%
33,50%
80%
(120 × 104)
70,29%
24,23%
25,21%
15,39%
33,78%
70%
(105 × 91)
70,63%
24,74%
25,90%
16,67%
34,49%
60%
(90 × 78)
70,71%
24,74%
26,18%
17,09%
34,68%
50%
(75 × 65)
71,13%
23,71%
27,29%
17,52%
34,91%
40%
(60 × 52)
71,88%
25,77%
28,95%
18,38%
36,24%
30%
(45 × 39)
72,47%
25,77%
31,72%
20,51%
37,62%
20%
(30 × 26)
74,31%
29,90%
39,20%
22,65%
41,51%
10%
(15 × 13)
78,33%
23,20%
46,95%
27,35%
43,96%
5%
(8 × 7)
61,84%
10,31%
34,90%
13,68%
30,18%
Tabelle 4.6: Erkennungsraten der LDA für Rang 1 unter verschiedenen Bildskalierungen zwischen
100% und 5%.
Ergebnissen der PCA verhält, das heißt bei Bildskalierungen von 30% die Erkennungsrate
nicht geringer wird.
Insgesamt konnte für die FERET-Datenbank ein linearer Zusammenhang zwischen Erkennungsrate und Bildgröße festgestellt werden. Bis zu einer bestimmten Bildgröße steigt
die Rate und fällt, sobald die Bildverkleinerung zu groß ist. Letzteres ist damit zu erklären,
dass bei sehr kleinen Bildern ein zu geringer Informationsgehalt vorliegt und eine Unterscheidung der Bilder kaum noch möglich ist. Man kann also zum Sparen von Speicherplatz
und Rechenzeit die Bildgröße bedenkenlos auf mindestens die Hälfte reduzieren ohne mit
gravierenden Verlusten in Erkennungsleistung zu rechnen. Diese Erkenntnis ist konsistent
zu den Ergebnissen der Experimente in [ZCK98].
4.5.2
Dimensionen
Nun wird mit der Anzahl der Dimensionen des Unterraums experimentiert. Die restlichen
Parameter bleiben auf den Werten von Kapitel 4.4. Lediglich die Bildgröße wird auf 75 ×
65 Pixel reduziert, denn dadurch ist keine statistisch bedeutende Verschlechterung der
Erkennungsrate zu erwarten, wie in Abschnitt 4.5.1 festgestellt wurde.
In Tabelle 4.7 sind Erkennungsraten der PCA für unterschiedliche Dimensionsgrößen
des Unterraums aufgelistet. Dazu ist angegeben, wieviel Energie der jeweilige Unterraum
enthält. Als Energie wird der Varianzanteil des Unterraums an der Gesamtvarianz der
Bilder bezeichnet (vgl. z.B. [WYB02]). Energie kann also als Informationsgehalt der projizierten Bilder im Unterraum aufgefasst werden. Generel sinkt die Erkennungsrate mit
59
PCA
Dim.
Energie
FAFB
FAFC
DUP1
DUP2
Durchschnitt
500
100%
75,40%
4,64%
35,87%
16,24%
33,04%
450
99,82%
75,31%
4,64%
35,46%
16,24%
32,91%
400
99,53%
75,23%
4,64%
35,46%
16,24%
32,89%
350
99,11%
75,06%
4,64%
35,60%
16,24%
32,88%
300
98,51%
74,90%
4,64%
35,32%
16,24%
32,77%
250
97,64%
74,73%
4,64%
35,18%
16,24%
32,70%
200
96,35%
74,14%
4,64%
34,90%
15,81%
32,37%
150
94,34%
73,56%
4,64%
34,76%
16,24%
32,30%
100
90,88%
71,97%
4,12%
34,07%
15,81%
31,49%
50
83,48%
68,70%
3,61%
31,30%
13,25%
29,21%
25
74,22%
61,67%
1,55%
26,04%
10,68%
24,99%
5
44,56%
25,11%
0,00%
3,88%
2,14%
7,78%
Tabelle 4.7: Erkennungsraten der PCA für Rang 1 für verschiedene Dimensionen des Unterraums.
sinkender Dimensionszahl (konsistent zu [BHK97]). Das Konfidenzintervall für die Dimensionsanzahl zur höchsten durchschnittlichen Erkennungsrate (500 Dimensionen) ist
[31, 14; 34, 94], das Konfidenzintervall zu 100 Dimensionen ist [29, 61; 33, 37] und das für
50 Dimensionen ist [27, 37; 31, 05]. Aus den Intervallen kann geschloßen werden, dass kein
eindeutiger Unterschied zwischen den Erkennungsleistungen bei 500 und 100 Dimensionen
besteht. Erst bei 50 Dimensionen sinkt die Erkennungsrate signifikant. Bei nur noch 100
Dimensionen sind über 90% der Bildinformationen im Unterraum gespeichert und bei 200
Dimensionen über 96%. Die Empfehlung von FERET 40% der Dimensionen (in unserem
Fall sind es gerade die 200 Dimensionen) für den Unterraum zu verwenden kann nachfolzogen werden, weil dies ein zufriedenstellender Kompromiss zwischen Dimensionsgröße
und Informationsgehalt der Projektionen scheint. Ist die Zahl der Hauptkomponenten zu
gering, sind hohe Fehlerraten zu verzeichnen (ab 25 Dimensionen). Dies haben auch die
Versuche von [WYB02] ergeben.
Die LDA-Ergebnisse zum Experiment mit unterschiedlicher Dimensionsanzahl des Unterraums sind in Tabelle 4.8 angegeben. Bei der LDA können nur weniger von Null verschiedene Eigenvektoren zustande kommen als verschiedene Klassen vorhanden sind (vgl.
Kapitel 3.3 und z.B. [DGG05]). Aus diesem Grund kann in 100 Dimensionen noch 100%
der Energie erfasst werden. Selbst bei 50 Eigenvektoren ist im Vergleich zur maximalen
Dimensionsgröße keine eindeutige Veränderung der Erkennungsrate festzustellen (beide
Werte im Bereich von 34%). Diese Ergebnisse sind zu denen der PCA ähnlich, jedoch
60
KAPITEL 4. VERSUCHE
LDA
Dim.
Energie
FAFB
FAFC
DUP1
DUP2
Durchschnitt
500
..
.
100%
..
.
71,13%
..
.
23,71%
..
.
27,29%
..
.
17,52%
..
.
34,91%
..
.
100
100%
71,13%
23,71%
27,29%
17,52%
34,91%
50
95,50%
70,04%
20,10%
29,64%
17,52%
34,33%
25
74,22%
62,09%
12,89%
27,70%
11,97%
28,66%
5
44,56%
24,85%
1,03%
5,82%
1,71%
8,35%
Tabelle 4.8: Erkennungsraten der LDA für Rang 1 für verschiedene Dimensionen des Unterraums.
enthalten wenige Fisherfaces mehr Informationen als die gleiche Anzahl von Eigenfaces
(z.B. speichern 50 Fisherfaces über 95%, 50 Eigenfaces aber nur 83,48% Energie).
MPC
Dim.
200
100
10
M
P
FAFB
FAFC
DUP1
DUP2
Durchschnitt
5
40
51,97%
0,52%
53,05%
51,71%
39,31%
10
20
51,97%
9,28%
52,23%
51,71%
41,30%
5
20
55,56%
1,55%
53,46%
51,71%
40,57%
2
5
46,03%
46,71%
50,42%
47,86%
47,76%
5
2
47,20%
8,76%
51,25%
50,43%
39,41%
Tabelle 4.9: Erkennungsraten der MPC für Rang 1 für verschiedene Kombinationen von Mischungskomponenten M und Eigenvektoren P pro Mischungskomponente.
In Tabelle 4.9 sind Resultate zur Variierung der MPC-Parameter dargestellt. Es wurden verschiedene Kombinationen von Mischungskomponenten und ihren Eigenvektoren
untersucht. Das Konfidenzintervall für die niedrigste durchschnittliche Erkennungsrate (5
Mischungskomponenten mit je 40 Eigenvektoren) ist [37, 33; 41, 29] und das zur höchsten
Erkennungsrate (2 Mischungskomponenten mit je 5 Eigenvektoren) ist [45, 74; 49, 78]. Daraus folgt, dass eine signifikante Steigerung der Erkennungsrate durch einen Unterraum,
der insgesamt nur 10 Dimensionen enthält, erreicht werden konnte. Außerdem ist die Kombination von Mischungskomponenten entscheidend. So ist die Erkennungsrate für 5 Mischungskomponenten und je 2 Eigenvektoren signifikant schlechter als die Erkennungsrate
für 2 Mischungskomponenten mit je 5 Eigenvektoren. Als Ursache dafür vermuten wir, dass
Bilder der FERET-Datenbank gut durch zwei Unterräume repräsentiert werden können.
Genaue Aussagen erfordern jedoch weitere Untersuchungen.
PCA
61
FAFB
FAFC
DUP1
DUP2
Durchschnitt
normal
74,14%
4,64%
34,90%
15,81%
32,37%
ohne 1en 3
72,39%
20,62%
35,04%
17,52%
36,40%
Tabelle 4.10: Ergebnisse der PCA für 200 Eigenfaces, aber ohne die wichtigsten drei Eigenfaces.
LDA
FAFB
FAFC
DUP1
DUP2
Durchschnitt
normal
71,13%
23,71%
27,29%
17,52%
34,91%
ohne 1en 3
65,27%
20,62%
22,85%
14,10%
30,71%
Tabelle 4.11: Ergebnisse der LDA für 200 Fisherfaces, aber ohne die wichtigsten drei Fisherfaces.
MPC
FAFB
FAFC
DUP1
DUP2
Durchschnitt
normal
51,97%
9,28%
52,22%
51,71%
41,30%
ohne 1en 1/M
51,80%
10,31%
52,22%
51,71%
41,51%
ohne 1en 3/M
49,21%
8,25%
52,22%
51,71%
40,35%
Tabelle 4.12: Ergebnisse der MPC für 10 Mischungskomponenten mit je 20 Eigenvektoren, wobei
jeweils der erste Eigenvektor bzw. die ersten 3 Eigenvektoren jeder Mischungskomponente entfernt
wurden.
Konfidenzintervall
PCA
LDA
MPC
normal
[30,48; 34,26]
ohne 1en 3
[34,45; 38,35]
normal
[32,98; 36,84]
ohne 1en 3
[28,84; 32,58]
normal
[39,31; 43,29]
ohne 1en 1/M
[39,52; 43,50]
ohne 1en 3/M
[38,36; 42,34]
Tabelle 4.13: Kofidenzintervalle zu den durchschnittlichen Erkennungsraten aus Tabelle 4.10,
Tabelle 4.11 sowie Tabelle 4.12.
62
KAPITEL 4. VERSUCHE
Ein weiterer Untersuchungsaspekt liegt in der Bedeutung der ersten Eigenvektoren
eines Verfahrens. Es kann nämlich bei der PCA vorkommen, dass die ersten Eigenfaces
(also die mit den größten Eigenwerten) Bildinformationen speichern, die für das Unterscheiden von Gesichtern keine Rolle spielen. Beispielsweise kann es sein, dass ein Eigenface
die Varianz in den Beleuchtungsstärken oder in den unterschiedlichen Gesichtsausdrücken
aufnimmt. Aus diesem Grund wird ein weiteres PCA-Experiment durchgeführt, bei dem
die wichtigsten drei Eigenfaces entfernt werden. Das Resultat ist in Tabelle 4.10 dargestellt. Es ist offensichtlich ein signifikanter Anstieg der Erkennungsleistung der PCA für
das FAFC-Testset feststellbar. Dieses Testset untersucht die Leistung der Verfahren, Gesichter unter verschiedenen Lichtbedingungen zu identifizieren (vgl. Kapitel 4.1.3). Die
signifikante Steigerung der Leistung durch das Entfernen der ersten drei Eigenfaces (vgl.
Konfidenzintervalle in Tabelle 4.13) unterstützt die Vermutung, dass die ersten Eigenfaces Gesichter anhand der Beleuchtung unterscheiden. Diese Erkenntnis ist konsistent zu
[BHK97] und [WYB02].
Das gleiche Experiment mit der LDA (Tabelle 4.11) zeigt, dass die ersten Fisherfaces
im Gegensatz zu den Eigenfaces tatsächlich relevante Informationen (statt Lichtstärken
o.Ä.) speichern. Das ist daran zu erkennen, dass die Erkennungsrate ohne die ersten drei
Fisherfaces für jedes Testset sinkt. Die Betrachtung der Konfidenzintervalle in Tabelle 4.13
ergibt, dass die durchschnittliche Erkennungsrate der LDA ohne die ersten drei Fisherfaces
im Vergleich zur Erkennungsrate mit den drei ersten Fisherfaces signifikant abnimmt. Das
haben auch die Versuche in [BHK97] ergeben.
Da bei der MPC in der Theorie sich jede Mischungskomponente auf bestimmte Gesichtseigenschaften spezialisiert und deshalb auch nur eine Mischungskomponente für die
Varianz in der Beleuchtung zuständig ist, kann durch das Entfernen des ersten Eigenvektors bzw. der ersten drei Eigenvektoren aus jeder Mischungskomponente keine bedeutende
Steigerung der Erkennungsleistung erwartet werden (vgl. Tabelle 4.12 und die entsprechenden Konfidenzintervalle in Tabelle 4.13).
4.5.3
Distanzmetriken
Als Letztes wird die Erkennungsleistung jedes Verfahrens für sechs verschiedene Distanzmaße untersucht. Diese sind die euklidische Distanz (L2-Norm), die Manhattandistanz
(L1-Norm), die Kosinus-Distanz sowie die Kombination jeder dieser Distanzmaße mit dem
Mahalanobis-Raum (vgl. Kapitel 3.1.3).
Die Erkennungsraten der PCA für die sechs Distanzmaße sind in Tabelle 4.14 dargestellt. Zu erkennen ist, dass die L1-Norm besser als die L2-Norm und die Kosinusdistanz ist
und die Projektion in den Mahalanobis-Raum für jedes Distanzmaß mit einer verbesserten
Erkennungsrate einhergeht. Der Grund dafür ist die gleichwertige Gewichtung jedes Eigenfaces. Das ist vor allem an der Steigerung der Raten für das FAFC-Testset zu erklären.
63
PCA
FAFB
FAFC
DUP1
DUP2
Durchschnitt
L2/euklid.
74,14%
4,64%
34,90%
15,81%
32,37%
L1/manhat.
81,09%
29,90%
39,34%
18,38%
42,18%
Cos
72,13%
7,22%
35,32%
14,96%
32,41%
MahL2
79,33%
43,81%
34,76%
17,52%
43,86%
MahL1
78,00%
44,33%
34,90%
18,80%
44,01%
MahCos
85,10%
60,82%
46,12%
21,79%
53,46%
Tabelle 4.14: Erkennungsraten der PCA für unterschiedliche Distanzmaße.
Bilder in diesem Testset variieren in der Beleuchtungsstärke und durch die Normierung jeder Dimension auf eine Varianz von Eins fällt die hohe Streuung in der Beleuchtungsstärke
nicht mehr so stark ins Gewicht und eine Unterscheidung der Gesichter mit geeigneteren
Dimensionen kann besser stattfinden. Die Mahalanobis-Kosinus-Distanz ist für die PCA
am besten geeignet. Mit ihr kann für drei von vier Testkategorien eine signifikante Steigerung der Erkennungsrate erzielt werden. Dies ist konsistent zu den Erkenntnissen in
[WYB02], [MP01] und [ML09]. Der Grund für die Verbesserung der Erkennungsleistung
der PCA durch Verwendung der Mahalanobis-Kosinus-Distanz ist, dass die Kosinusdistanz
den Winkel zwischen zwei Vektoren betrachtet und je gleicher die Richtung zweier Vektoren ist, desto kleiner ist ihre Kosinusdistanz. Folglich ist für zwei ähnliche Projektionen
(d.h. Vektoren mit ähnlicher Richtung) die Kosinusdistanz gering (vgl. Kapitel 3.1.3).
LDA
FAFB
FAFC
DUP1
DUP2
Durchschnitt
L2/euklid.
71,13%
23,71%
27,29%
17,52%
34,91%
L1/manhat.
72,38%
26,80%
25,62%
14,96%
34,94%
Cos
71,21%
21,65%
30,06%
17,09%
35,00%
MahL2
68,03%
24,74%
18,42%
11,97%
30,79%
MahL1
67,70%
26,29%
18,01%
12,82%
31,21%
MahCos
70,21%
28,35%
22,99%
12,39%
33,49%
Tabelle 4.15: Erkennungsraten der LDA für unterschiedliche Distanzmaße.
Bei der LDA führt die Projektion der Vektoren in den Mahalanobis-Raum zu keiner
Steigerung der Erkennungsrate (vgl. Tabelle 4.15). Zwischen L2, L1 und der Kosinusdistanz
liegt kein eindeutiger Unterschied für die LDA vor, denn das Konfidenzintervall für L2 ist
[32,98; 36,84] und für die Kosinusdistanz [33,07; 36,93] (die Intervalle überschneiden sich).
64
KAPITEL 4. VERSUCHE
MPC
FAFB
FAFC
DUP1
DUP2
Durchschnitt
L2/euklid.
51,97%
9,28%
52,22%
51,71%
41,30%
L1/manhat.
51,72%
4,12%
52,63%
51,71%
40,05%
Cos
51,72%
24,23%
50,83%
49,57%
44,09%
MahL2
52,89%
13,92%
52,08%
51,28%
42,54%
MahL1
51,97%
9,79%
52,08%
51,28%
41,28%
MahCos
51,72%
35,57%
49,17%
45,73%
45,55%
Tabelle 4.16: Erkennungsraten der MPC für unterschiedliche Distanzmaße.
Für die MPC kann die durchschnittliche Erkennungsrate ihres Standard-Distanzmaßes
(L2) (Konfidenzintervall: [39,31; 43,29]) durch die Mahalanobis-Kosinus-Distanz (Konfidenzintervall: [43,53; 47,57]) signifikant übertroffen werden. Das liegt daran, dass dieses
Maß eine bessere Erkennung im FAFC-Testset erlaubt (mit der Begründung, wie bei der
PCA).
4.5.4
Kombination bester Parameter
Nun soll die Erkennungsrate jedes Verfahrens gesteigert werden, indem die jeweils besten
Parameter verwendet werden.
Dazu wird die PCA auf Bildern der Größe 30 × 26 trainiert, 500 Eigenfaces (ohne die
ersten drei) werden für den Unterraum verwendet und es wird die Mahalanobis-KosinusDistanz zum Testen benutzt. Bei der LDA sind es Bilder mit 15 × 13 Pixel, 100 Dimensionen für den Unterraum und die Kosinusdistanz als Distanzsmaß. Für die MPC wird die
Bildgröße von 45 × 39 Pixel, 2 Mischungskomponenten mit jeweils 5 Eigenvektoren und
die Mahalanobis-Kosinus-Distanz verwendet. Die Gallerie, das Trainingsset sowie die vier
Testsets bleiben für alle Verfahren identisch, wie in Kapitel 4.4 beschrieben.
Die Ergebnisse des Tests für jedes Verfahren sind in Tabelle 4.17 den Ergebnissen des
Standard-Tests gegenübergestellt. In der Tabelle sind außerdem die entsprechenden Konfidenzintervalle angegeben, mit denen überprüft werden soll, ob eine signifikante Verbesserung der Erkennungsleistung eines Verfahrens erreicht werden konnte. Die Betrachtung
der Konfidenzintervalle lässt den Schluß zu, dass mit den jeweils besten Parametern die
durchschnittlichen Erkennungsleistungen der PCA und LDA signifikant verbessert werden
konnten. Die Leistung der MPC hingegen ist durch die Kombination ihrer besten Parameter signifikant gesunken. Der Grund dafür ist wahrscheinlich, dass die MPC in ihrem
Training auf bestimmte Parameter eingestellt wurde (vgl. Kapitel 3.4) und das Verfahren
deshalb durch spätere Parameterveränderungen nicht verbessert werden kann. Die Kombination der Parameter für die LDA hat dazu geführt, dass die Erkennungsrate der MPC
4.6. ZUSAMMENFASSUNG
Vorher
Nachher
65
FAFB
FAFC
DUP1
DUP2
Durchschnitt
Konfidenzintervall
PCA
73,47%
4,64%
34,35%
14,96%
31,85%
[29,96; 33,74]
LDA
69,29%
24,74%
23,27%
12,82%
32,53%
[30,63; 34,43]
MPC
51,97%
9,28%
52,22%
51,71%
41,30%
[39,31; 43,29]
PCA
63,51%
59,79%
19,11%
11,11%
38,38%
[36,41; 40,35]
LDA
78,58%
20,62%
48,34%
23,93%
42,87%
[40,87; 44,87]
MPC
39,92%
24,23%
37,40%
29,06%
32,65%
[30,75; 34,55]
Tabelle 4.17: Erkennungsraten der PCA, LDA und MPC für standardisierte Parameter nach
Kapitel 4.4 (obere Tabellenhälfte) und für die in diesem Abschnitt bestimmten besten Parameter
(untere Tabellenhälfte). Außerdem sind die Konfidenzintervalle zu den durchschnittlichen Erkennungsraten angegeben.
nicht mehr eindeutig besser ist. Zudem ist die LDA nach der Kombination signifikant besser als die entsprechende PCA. Dies war für die Ausgangsparameterbelegungen nicht der
Fall.
4.6
Zusammenfassung
Drei lineare Unterraumverfahren (PCA, LDA, MPC) wurden in diesem Kapitel getestet.
Die Tests wurden an der FERET-Datenbank durchgeführt und Bilder wurden mit dem
Verfahren nach [CSU12b] normalisiert.
Bei der ersten Testdurchführung (Kapitel 4.4) hat man sich an dem FERET-Protokoll
orientiert und Parameter wurden so gewählt, dass ein möglichst direkter Vergleich zur
Literatur geführt werden konnte. Die Ergebnisse des Tests können zusammengetragen
werden:
1. Als Durchschnitt über die vier FERET-Testsets besteht zwischen den Erkennungsraten der PCA und der LDA für Rang 1 kein eindeutiger Unterschied. Allerdings ist
für den DUP1-Test die PCA signifikant besser als die LDA und die LDA ist für den
FAFC-Test signifikant besser als die PCA.
2. Zwischen den durchschnittlichen Erkennungsraten unserer PCA und LDA und der
PCA und LDA nach [CSU12a] besteht jeweils kein bedeutender Unterschied.
3. Die Erkennungsrate der MPC als Durchschnitt über die vier Testkategorien ist signifikant höher als die der PCA und der LDA.
4. Die MPC erreicht für Rang 2 in allen Testkategorien eine höhere Erkennungsrate
als PCA und LDA. Für Rang 2 ist die Erkennungsrate der MPC in jeder Testkate-
66
KAPITEL 4. VERSUCHE
gorie genauso gut oder besser als die Erkennungsraten der besten Algorithmen der
FERET-Tests.
5. Für Rang 6 erreicht das MPC-Verfahren Erkennungsraten von fast 100%.
Um die Erkennungsleistungen der Verfahren zu steigern, wurde versucht die jeweils
besten Parameter jedes Verfahrens zu kombinieren. Untersucht wurden unterschiedliche
Bildgrößen, Dimensionsanzahlen im Unterraum sowie sechs verschiedene Distanzmaße. Die
Experimente ergaben folgende Resultate:
6. Generell steigt sowohl für PCA als auch für LDA mit der Verkleinerung der Bilder die Erkennungsrate. Für die PCA kann die Erkennungsleistung insgesamt nicht
signifikant gesteigert werden, für die LDA schon.
7. Für PCA und LDA sinkt die Erkennungsleistung bei kleiner werdender Dimensionalität des Unterraums. Bei beiden Verfahren kann die Anzahl der Dimensionen auf
1
5
der Maximalanzahl reduziert werden ohne eine eindeutig sinkende Erkennungsrate
zu erwarten.
8. Die signifikant höchste Erkennungsrate erzielt die MPC bei einer Konstellation von
2 Mischungskomponenten mit je 5 Eigenvektoren. Andere getestete Konstellationen
ergaben keine eindeutigen Unterschiede in Erkennungsleistung.
9. Die wichtigsten Eigenvektoren der PCA speichern Bildinformationen, die nicht relevant zur Identifizierung von Gesichtern sind. Entsprechend kann bei der PCA in
speziellen Fällen (z.B. FAFC-Kategorie) durch Entfernen der ersten Eigenvektoren
die Erkennungsrate signifikant gesteigert werden. Dies ist für die LDA und die MPC
nicht der Fall.
10. Für die PCA erzielt die Mahalanobis-Kosinus-Distanz im Vergleich zu anderen getesten Distanzmaßen die signifikant besten Erkennungsraten.
11. Bei der MPC wurde mit der Mahalanobis-Kosinus-Distanz eine im Vergleich zur
euklidischen Distanz signifikant höhere Erkennungsrate erreicht.
12. Ein eindeutiger Anstieg der Erkennungsrate durch Variierung von Distanzmaßen
konnte bei der LDA nicht erreicht werden. Jedoch führte die Kosinusdistanz zu den
höchsten Raten.
Unter Ausnutzung dieser Erkenntnisse konnten die PCA und LDA für ihre jeweils
optimalen Parameter signifikant in ihrer Erkennungsleistung verbessert werden. Außerdem wurden für Rang 1 die Erkennungsraten der MPC erreicht. Der Versuch das MPCVerfahren zu optimieren hatte insgesamt keinen Erfolg.
Kapitel 5
Abschluß
Im Verlauf dieser Arbeit wurden drei lineare Unterraumverfahren zur Gesichtserkennung
untersucht. Bevor ein Unterraumverfahren zur Identifikation von Gesichtern eingesetzt
werden kann, wird es initialisiert. Dazu berechnet das Verfahren automatisch anhand von
Bildern einer Gesichtsdatenbank einen Unterraum, in dem die Klassifizierung unbekannter
Gesichtsbilder durchgeführt wird. Für diesen Zweck werden Bilder in den berechneten Unterraum projiziert. Durch die Projektion wird das anfängliche Problem ein möglicherweise
großes Bild mit einer hohen Anzahl von Pixeln mit allen anderen Bildern der Datenbank zu
vergleichen derart reduziert, dass nur noch die kompakten Projektionen der entsprechenden Bilder miteinander verglichen werden müssen. Einen solchen Vergleich führt prinzipiell
der Nächste-Nachbarn-Klassifikator durch.
Die drei vorgestellten Unterraumverfahren waren die Hauptkomponentenanalyse (PCA),
die lineare Diskriminanzanalyse (LDA) und die Hauptkomponentenmischung (MPC). Die
PCA und die LDA sind zwei bekannte Verfahren, die oft als Basis für den Vergleich von
Gesichtserkennungsverfahren dienen. Beide Verfahren haben nach ihrer Entwicklung an
den FERET-Tests teilgenommen und zählten dort zu den besseren Verfahren. Geringer
Rechenaufwand sowohl zur Initialisierung der Verfahren als auch zum Identifizieren unbekannter Gesichter macht die PCA und LDA zu effizienten und schnellen Verfahren,
die auch in Echtzeit-Anwendung zum Einsatz kommen können. Mit dem MPC-Modell
können Gesichter genauer repräsentiert werden als mit der gewöhnlichen PCA. Soll aus
einer Datenbank beispielsweise die Identität eines unbekannten Gesichts auf sechs Personen eingeschränkt werden, dann trifft die MPC in so einem Fall selbst unter schlechten
Lichtverhältnissen oder großen Altersunterschieden der Personen mit nahezu 100%-iger
Sicherheit die korrekte Entscheidung.
Gesichtserkennung ist eine große Herausforderung. Seit Jahrzehnten versucht Forschung und Wissenschaft erfolgreiche und effiziente Gesichtserkennungsverfahren zu entwickeln. Eine besondere Schwierigkeit stellt dabei das Gesicht selbst dar, denn es ist kein invariantes Identifizierungsmerkmal des Menschen. Lichteinflüße, Mimik und Alterung kön67
68
KAPITEL 5. ABSCHLUß
nen die Leistung eines Gesichtserkennungsverfahrens drastisch beeinflußen. Trotz dieser
Hindernisse wird weiterhin versucht neue Gesichtserkennungsverfahren zu entwickeln und
alte zu verbessern.
Zum Fortschritt im Bereich der Gesichtserkennung hat die FERET-Datenbank beigetragen. Durch ihren großen Umfang sowie ihrer einfachen Erhältlichkeit können Verfahren
zur Gesichtserkennung einfach und ausgiebig getestet werden. In Kooperation mit FERET stellt außerdem die Colorado State University (CSU) ein System zum Auswerten
von Gesichtserkennungsalgorithmen an der FERET-Datenbank zur Verfüngung. Zahlreiche Veröffentlichungen sind der Beweis für den Erfolg der FERET-Datenbank und des
CSU-Systems. Bis heute wird die FERET-Datenbank weiter erweitert und auf neue Problembereiche der Gesichtserkennung angepasst, sodass auch in Zukunft die Entwicklung
von Gesichtserkennungsverfahren weiter voran getrieben werden kann. Neue FERET-Tests
sind die Basis für den weiteren Erfolg im Bereich der Gesichtserkennung.
Das Ziel der Arbeit drei Unterraumverfahren miteinander zu vergleichen wurde erreicht. Unseres Wissens nach durften wir als erste Arbeit (abgesehen von der Originalarbeit) eine Implementierung der MPC vornehmen und mit dem Verfahren an der FERETDatenbank experimentieren. Die Experimente betrachten wir als Erfolg, da mit der MPC
ein Verfahren gefunden werden konnte, das bereits ab Rang 6 eine sehr hohe Erkennungsrate aufweist.
Zukünftige Arbeiten könnten sich auf weitere Experimente mit der MPC konzentrieren. Mit der genauen Repräsentation von Bildern ist es durchaus vorstellbar das MPCVerfahren beispielsweise zur Bildkomprimierung zu verwenden. Bei unseren Experimenten
mit der MPC sind wir außerdem auf einige Probleme gestoßen, die weiterer Untersuchung
bedürfen. So gibt es keine automatische und analytische Methode, um zu entscheiden, wie
die Anzahl von Mischungskomponenten und Eigenvektoren zu wählen ist. Ein weiteres
Problem stellt die lange Rechenzeit des Verfahrens zur Initialisierung dar. Abhängig von
Bildgröße und Anzahl der Mischungskomponenten des Modells dauerte eine Initialisierung
bis zu mehreren Tagen. Wir sind der Überzeugung, dass durch weitere Forschung die Geschwindigkeit des Verfahrens stark optimiert werden kann. Darüberhinaus könnte weiter
untersucht werden, ob das Verfahren für Rang 1 verbessert werden kann.
Abbildungsverzeichnis
1.1
35 manuell identifizierte Gesichtsmerkmale . . . . . . . . . . . . . . . . . . .
3
1.2
Komponenten der PCA, ICA und LDA . . . . . . . . . . . . . . . . . . . . .
6
2.1
Beispiel für eine korrelierte und eine unkorrelierte Punktwolke . . . . . . . . 14
2.2
Beispiel für zwei Normalverteilungen . . . . . . . . . . . . . . . . . . . . . . 15
2.3
Beispiel einer Mischverteilung . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4
Beispiel für eine Vektorquantisierung . . . . . . . . . . . . . . . . . . . . . . 17
3.1
Grundaufbau eines Gesichtserkennungssystems . . . . . . . . . . . . . . . . 23
3.2
Beispielbilder aus der FERET-Datenbank . . . . . . . . . . . . . . . . . . . 24
3.3
Beispiel einer dekorrelierten Punktwolke . . . . . . . . . . . . . . . . . . . . 28
3.4
Klassifikation im Gesichtsraum . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5
Das durchschnittliche Gesicht der Trainingsmenge . . . . . . . . . . . . . . 30
3.6
Die wichtigsten fünf Eigenfaces . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.7
Die unwichtigsten fünf Eigenfaces . . . . . . . . . . . . . . . . . . . . . . . . 32
3.8
Trennung von Klassen bei der LDA . . . . . . . . . . . . . . . . . . . . . . . 33
3.9
Schema des PCA+LDA-Vorgehens . . . . . . . . . . . . . . . . . . . . . . . 36
3.10 Die wichtigsten fünf Fisherfaces . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.11 Die unwichtigsten fünf Fisherfaces . . . . . . . . . . . . . . . . . . . . . . . 36
3.12 Parameter eines MPC-Modells . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.13 Schema des MPC-Trainings . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.14 Projektionen im MPC-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1
Beispielsatz einer Person der FERET-Datenbank . . . . . . . . . . . . . . . 48
4.2
Beispiel eines normalisierten Bildes . . . . . . . . . . . . . . . . . . . . . . . 50
4.3
CMS-Kurve der PCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4
CMS-Kurve der LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5
CMS-Kurve der MPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6
Beispiel für Bildskalierungen
. . . . . . . . . . . . . . . . . . . . . . . . . . 56
69
70
ABBILDUNGSVERZEICHNIS
Literaturverzeichnis
[Alp10]
Alpaydin, E. (Herausgeber): Introduction to Machine Learning. The MIT
Press, Cambridge, Massachusetts, Zweite Auflage, 2010.
[Bar81]
Baron, Robert J.: Mechanisms of Human Facial Recognition. International Journal of Man-Machine Studies, Seiten 137–178, 1981.
[Beu03]
Beutelspacher, A.: Lineare Algebra, Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen. Vieweg+Teubner, Sechste
Auflage, 2003.
[Bev01]
Beveridge, J.R.: The Geometry of LDA and PCA Classifiers Illustrated
with 3D Examples. Technischer Bericht, Colorado State University, 2001.
[BHK97]
Belhumeur, P.N., J.P. Hespanha und D.J. Kriegman: Eigenfaces vs.
Fisherfaces: recognition using class specific linear projection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):711–720, Juli
1997.
[BMS02]
Bartlett, Marian Stewart, Javier R. Movellan und Terrence J.
Sejnowski: Face recognition by independent component analysis. IEEE
Transactions on Neural Networks, Seiten 1450–1464, 2002.
[BP93]
Brunelli, R. und T. Poggio: Face recognition: features versus templates. IEEE Transactions on Pattern Analysis and Machine Intelligence,
15(10):1042–1052, Oktober 1993.
[BSDG01]
Beveridge, J.R., K. She, B.A. Draper und G.H. Givens: A nonparametric statistical comparison of principal component and linear discriminant subspaces for face recognition. In: Proceedings of the 2001 IEEE
Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2001, Band 1, Seiten 535–542, 2001.
[Com94]
Comon, Pierre: Independent component analysis, a new concept? Signal
Process., 36(3):287–314, April 1994.
71
72
[CSU12a]
LITERATURVERZEICHNIS
CSU Baseline Results on the Feret Database (Website), Oktober 2012.
http://www.cs.colostate.edu/evalfacerec/algorithms/version5/
CSUBaselineResultsV5/index.html.
[CSU12b]
Evaluation of Face Recognition Algorithms (Colorado State University)
Website, Oktober 2012. http://www.cs.colostate.edu/evalfacerec/data.php.
[DGG05]
Delac, Kresimir, Mislav Grgic und Sonja Grgic: Independent comparative study of PCA, ICA, and LDA on the FERET data set. International
Journal of Imaging Systems and Technology, 15(5):252–260, 2005.
[DHS01]
Duda, R.O., P.E. Hart und D.G. Stork: Pattern classification. Pattern
Classification and Scene Analysis: Pattern Classification. Wiley, 2001.
[DY93]
Demers, David und Garrison Cottrell Y: Non-Linear Dimensionality
Reduction. In: Advances in Neural Information Processing Systems 5, Seiten
580–587. Morgan Kaufmann, 1993.
[EC96]
Etemad, K. und R. Chellappa: Face recognition using discriminant eigenvectors. In: 1996 IEEE International Conference on Acoustics, Speech,
and Signal Processing, 1996. ICASSP-96. Conference Proceedings, Band 4,
Seiten 2148–2151, Mai 1996.
[FER12]
Face Recognition Technology (FERET) Website, Oktober 2012. FERETDatabase, http://www.nist.gov/itl/iad/ig/feret.cfm.
[Fin03]
Fink, G.A.: Mustererkennung Mit Markov-Modellen: Theorie - Praxis Anwendungsgebiete. Leitfäden Der Informatik. Teubner, 2003.
[Fin12]
Fink, G.A.: Skriptum zur Vorlesung “Mustererkennung”, Technische Universität Dortmund. 2012.
[GBDB04]
Givens, GeofH., J.Ross Beveridge, BruceA. Draper und David
Bolme: Using a Generalized Linear Mixed Model to Study the Configuration
Space of a PCA+LDA Human Face Recognition Algorithm. In: Articulated
Motion and Deformable Objects, Band 3179 der Reihe Lecture Notes in
Computer Science, Seiten 1–11. Springer Berlin Heidelberg, 2004.
[HYH+ 05]
He, X., S. Yan, Y. Hu, P. Niyogi und H.J. Zhang: Face recognition
using laplacianfaces. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 27(3):328–340, 2005.
[IJCY96]
I. J. Cox, J. Ghosn und P. N. Yianilos: Feature-based face recognition
using mixture-distance. In: Proceedings of IEEE Conference on Computer
Vision and Pattern Recognition, Seiten 209–216, 1996.
73
[Jä00]
Jänich, K.: Lineare Algebra. Springer, Achte Auflage, 2000.
[JA09]
Jafri, Rabia und Hamid R. Arabnia: A Survey of Face Recognition
Techniques. Journal of Information Processing Systems, 5(2):41–68, Juni
2009.
[Kan73]
Kanade, Takeo: Picture Processing System by Computer Complex and
Recognition of Human Faces. In: doctoral dissertation, Kyoto University.
November 1973.
[Kir10]
Kirillova, E.: Skript zur Vorlesung “Statistik, Wahrscheinlichkeitsrechnung und Mathematische Logik”, Technische Universität Dortmund. 2010.
[KM03]
Kowalsky, H.-J. und G.O. Michler: Lineare Algebra. Walter de gruyter,
12. Auflage, 2003.
[LGTB97]
Lawrence, S., C.L. Giles, Ah Chung Tsoi und A.D. Back: Face recognition: a convolutional neural-network approach. IEEE Transactions on
Neural Networks, 8(1):98 –113, Januar 1997.
[LL99]
Liposcak, Zdravko und Sven Loncaric: A Scale-Space Approach to
Face Recognition from Profiles. In: Proceedings of the 8th International
Conference on Computer Analysis of Images and Patterns, CAIP ’99, Seiten
243–250, London, UK, 1999. Springer-Verlag.
[LWQ05]
Li, Huaqing, Shaoyu Wang und Feihu Qi: Automatic Face Recognition
by Support Vector Machines. In: Combinatorial Image Analysis, Band 3322
der Reihe Lecture Notes in Computer Science, Seiten 716–725. Springer
Berlin Heidelberg, 2005.
[LY05]
Li, Bicheng und Hujun Yin: Face recognition using RBF neural networks
and wavelet transform. In: Proceedings of the Second international conference on Advances in neural networks - Volume Part II, ISNN’05, Seiten
105–111, Berlin, Heidelberg, 2005. Springer-Verlag.
[MK01]
Martínez, Aleix M. und Avinash C. Kak: PCA versus LDA. IEEE
Trans. Pattern Anal. Mach. Intell., 23(2):228–233, Februar 2001.
[ML09]
Miller, Philip und Jamie Lyle: The Effect of Distance Measures on
the Recognition Rates of PCA and LDA Based Facial Recognition. Digitial
Image Processing, 2009.
[mn85]
nixon mark: Eye Spacing Measurement for Facial Recognition. In: Proc.
SPIE Applications of Digital Image Processing, Band 575, Seiten 279–283,
1985.
74
[MNP96]
Moghaddam, B., C. Nastar und A. Pentland: A Bayesian Similarity
Measure for Direct Image Matching. In: Proceedings of the 13th International Conference on Pattern Recognition - Volume 2, ICPR ’96, Seiten
350–358, Washington, DC, USA, 1996.
[MP98]
Moon, H. und P.J. Phillips: The FERET verification testing protocol
for face recognition algorithms. In: Third IEEE International Conference
on Automatic Face and Gesture Recognition, Seiten 48–53, April 1998.
[MP01]
Moon, Hyeonjoon und P Jonathon Phillips: Computational and performance aspects of PCA-based face-recognition algorithms. Perception,
30:303–321, 2001.
[NI99]
Nefian, Ara V. und Monson H. Hayes III: Face Recognition Using An
Embedded HMM. In: IEEE Conference on Audio and Video-based Biometric
Person Authentication, Seiten 19–24, 1999.
[PL95]
Paulus, Erwin und Michael Lehning: Die Evaluierung von Spracherkennungssystemen in Deutschland. Technischer Bericht, Universitäts- und
Landesbibliothek, Saarbrücken, 1995.
[PMRR00]
Phillips, P.J., Hyeonjoon Moon, S.A. Rizvi und P.J. Rauss: The FERET evaluation methodology for face-recognition algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(10):1090–1104,
Oktober 2000.
[PRD96]
Phillips, P. Jonathon, Patrick J. Rauss und Sandor Z. Der: FERET (Face Recognition Technology) Recognition Algorithm Development
and Test Results. Army Research Laboratory, Oktober 1996.
[PWHR98]
Phillips, P.Jonathon, Harry Wechsler, Jeffery Huang und Patrick J. Rauss: The FERET database and evaluation procedure for facerecognition algorithms. Image and Vision Computing, 16(5):295 – 306, 1998.
[QS06]
Quadteroni, A. und F. Saleri: Wissenschaftliches Rechnen mit Matlab.
Springer, 2006.
[SBB02]
Sim, Terence, Simon Baker und Maan Bsat: The CMU Pose, Illumination, and Expression (PIE) Database. In: Proceedings of the IEEE
International Conference on Automatic Face and Gesture Recognition, Mai
2002.
[SH94]
Samaria, F.S. und A.C. Harter: Parameterisation of a stochastic model
for human face identification. In: Proceedings of the Second IEEE Workshop
on Applications of Computer Vision, Seiten 138–142, Dezember 1994.
[SK87]
75
Sirovich, L. und M. Kirby: Low-dimensional procedure for the characterization of human faces. Journal of the Optical Society of America A,
4(3):519–524, März 1987.
[TC02a]
Turaga, D.S. und Tsuhan Chen: Face recognition using mixtures of
principal components. In: International Conference on Image Processing,
Band 2, Seiten II–101 – II–104, Dezember 2002.
[TC02b]
Turaga, D.S. und Tsuhan Chen: Model-based error concealment for wireless video. IEEE Transactions on Circuits and Systems for Video Technology, 12(6):483–495, Juni 2002.
[TP91a]
Turk, M. und A. Pentland: Eigenfaces for recognition. J. Cognitive
Neuroscience, 3(1):71–86, Januar 1991.
[TP91b]
Turk, M.A. und A.P. Pentland: Face recognition using eigenfaces. In:
IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR ’91, Seiten 586–591, Juni 1991.
[WFKvdM97] Wiskott, L., J.-M. Fellous, N. Kruger und C. von der Malsburg:
Face recognition by elastic bunch graph matching. In: International Conference on Image Processing, Band 1, Seiten 129–132, Oktober 1997.
[wSt12]
Hörzu Wissen Website, Oktober 2012.
http://www.hoerzu.de/wissen-
service/wissen/datenschuetzer-warnen.
[WYB02]
W. Yambor, B. Draper und R. Beveridge: Analyzing PCA-based Face
Recognition Algorithms: Eigenvector Selection and Distance Measures. Empirical Evaluation Methods in Computer Vision, Colorado State University,
2002.
[YCH89]
Yuille, A.L., D.S. Cohen und P.W. Hallinan: Feature extraction from
faces using deformable templates. In: IEEE Computer Society Conference
on Computer Vision and Pattern Recognition, Proceedings CVPR ’89, Seiten 104–109, Juni 1989.
[ZCK98]
Zhao, W., R. Chellappa und A. Krishnaswamy: Discriminant analysis
of principal components for face recognition. In: Third IEEE International
Conference on Automatic Face and Gesture Recognition, Seiten 336–341,
April 1998.
[ZCP99]
Zhao, W., R. Chellappa und P. Phillips: Subspace Linear Discriminant Analysis for Face Recognition, Computer Vision Laboratory, Center
for Automation Research, University of Maryland, April 1999.
76
[ZHL+ 05]
Zhang, Guangcheng, Xiangsheng Huang, Stan Li, Yangsheng
Wang und Xihong Wu: Boosting Local Binary Pattern (LBP)-Based Face
Recognition. In: Advances in Biometric Person Authentication, Seiten 179–
186. 2005.

Lineare Unterraumtechniken zur automatischen

Transcrição

Documentos relacionados

Wer wird LDA-Titelmädchen 2007? - E-Paper - Lahn

Kennen Sie schon die neue o2c

Abell 1689 (Hubble Space Telescope): Galaxienhaufen

Grupo Musica Disco Nº Obs: O-Zone Dragostea din tei P3 7

Portugal - Sammelverkehre, Teil- und Komplettladungen

Original Canon Toner-Kartusche schwarz (8489A002, EP-27)

EFFAcLAR SCHÄUMENDES REINIGUNGSGEL - shop

MPC Praxis Teil 3

o2c. objects to see

TAUCHEN - Preisliste