M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Vorlesung 6
Biologisch motivierte Methoden der Objekterkennung II
Martin Giese
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Übersicht
KategorisierungGrundbegriffe der InformationstheorieErkennung basierend auf gelernten Objektteilen
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Erkennung vs. Kategorisierung
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Erkennung vs. Kategorisierung
Andy
Elke
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Erkennung vs. Kategorisierung
männlich
weiblich
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Edelman (1999)
S. Edelman
Objektansichten eingebettet in abstrakten RaumVariationen entlangverschiedenerDimensionen (Ansicht, Beleuchtung, …)
Chorus of Prototypes
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Edelman (1999)
Chorus of PrototypesModule, die verschiedene Ansichten desselben Objektes erkennenGruppe (“Chorus”) solcher Module, tragen zur Repräsen-tation von Objekten bei.Aktivierungen definieren niederig-dimensionalen Repräsentationsraum
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Chorus of PrototypesObjektspezifische Module feuern verschieden stark, jenach Ähnlichkeit mit BildAktivitätsvektor enkodiert dasObjekt
“Chorus of prototypes”
Edelman (1999)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Kategorisierung mit HMAX Modell
Riesenhuber (2001)
Pool von “ansichtgetunten”Neuronen, die nicht bestimmten Objekten zugeordnet sindAuslesen abhängig von Aufgabe (Kategorisierung, Identifikation, …)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Kategorisierung mit HMAX Modell
Zuordnung zu verschiedenen subarealen des inferotemporalen Kortex (Area IT) (anterior vs. posterior)Neurone im Prä-frontalkortex (PFC)steuern Auslesen abhängig von AufgabePrädiktion: Aktivität derPFC-Neurone sollte Kategorien enkodieren
Riesenhuber & Poggio (2003)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Kategorisierung bei Affen
Generierung von kontinuierlicher Klasse von Objekten (Tieren) durch 3D-MorphingAffe mit verschiedenen Kategoriegrenzen trainiert
3D Morphs
Freedman et al. (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Kategorisierung bei Affen
Morphingraum mit 2 oder 3 Kategorien
Freedman et al. (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Kategorisierung bei AffenNeuronenantwort im Präfrontalkortex
Neuronenantwort reflektiert gelernte KategoriegrenzeGilt für alle Linien zwischen MorphpaarenNach Umtrainieren auf andere Kategoriegrenze “lernt” ein Teil der Neurone um”
Freedman et al. (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
II. Grundbegriffe der Informationstheorie
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Grundbegriffe der InformationstheorieGeg.: Diskrete Zufallsvariable X mit X ∈ {x1, …, xN }, mit P(X = xn) = P(xn).
Def.: Der durch das Ereignis {X = xn} übertragene Informationsgehalt ist definiert als:
→ Idee: Seltene Ereignisse übertragen viel Information.
Def.: Der mittlere Informationsgehalt (Entropie), der durch die Variable X übertragen wird ist definiert als:
))(/1(log)(log)(log:)( 222 nnnn xPxPxXPxH =−==−=
[ ]0)(log)()}(log{:)(1
22 ≥−=−= ∑=
N
nnn xPxPXPEXH
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Grundbegriffe der InformationstheorieFür das Paar von Zufallsvariablen (X, Y) ist die gemeinsame oder Verbundentropie
Beachten: Falls die Variablen X und Y unabhängig sind, gilt wegen P(X, Y) = P(X) • P(Y):
Falls X und Y abhängig sind gilt wegen P(X, Y) = P(X|Y) • P(Y) = P(Y|X) • P(X):
mit der bedingten Entropie
∑∑= =
−=M
m
N
nmnmn yxPyxPYXH
1 12 ),(log),(),(
)()(),( YHXHYXH +=
)|()()|()(),( YXHYHXYHXHYXH +=+=
)|(log)()|( 2 nm
N M
n xyPxPXYH ∑ ∑−=1 1n m= =
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Grundbegriffe der InformationstheorieBew.:
[ ]
∑ ∑
∑ ∑
∑ ∑
∑∑
∑∑
= =
= =
= =
= =
= =
−
−
=+−
=−
=−
=
N
n
M
mnmnn
N
n
M
mnmnmn
M
n
M
mnnmnmn
M
m
N
nnnmnnm
M
m
N
nmnmn
xyPxPxP
xyPxyPxP
xPxyPxyPxP
xPxyPxPxyP
yxPyxP
YXH
1 12
1 12
1 122
1 12
1 12
)|()(log)(
)|(log)|()(
)(log)|(log)|()(
)()|(log)()|(
),(log),(
),(
H(Y|X)
H(X) 1
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Grundbegriffe der InformationstheorieMan kann zeigen mit “=“ genau dann wenn X und Y unabhängig. (z.B. Papoulis, 1991)
Graphische Illustration:
Def.: Die Transinformation (mutual information) der Variablen X und Y ist definiert als
)|()()|()(),()()(),(
XYHYHYXHXHYXHYHXHYXI
−=−=−+=
)()(),( YHXHYXH +≤
H(Y)
H(Y)H(X,Y)
H(X|Y) H(Y|X)
I(X,Y)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Grundbegriffe der Informationstheorie
Anwendung auf Informationskanal:a. Perfekter Kanal: X und Y vollständig
abhängig, d.h. P(X,Y)=P(X)=P(Y) ⇒H(X,Y) = H(X) = H(Y) = I(X,Y)
b. Vollständig gestörter Kanal: X und Y unabhängig, d.h. P(X,Y)=P(X) P(Y) ⇒H(X,Y) = H(X) + H(Y) ⇒ I(X,Y) = 0
c. Teilweise gestörter Kanal:H(X,Y) < H(X) + H(Y) ⇒ I(X,Y) > 0
H(X)
H(Y)
H(X)
H(Y)H(X)
H(Y)I(X,Y)
XY
I(X,Y)
H(Y)
H(Y)
H(X|Y)
H(Y|X)
Sender
Empfänger
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
III. Erkennung basierend auf gelernten Objektteilen
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Objektdetektionssystem
Heisele (2002)
Merkmalsextraktion
Merkmalsvektor (x1, x2 ,…, xn)
Klassifikator
Pixelmuster
Klassifikations-Ergebnis:“Objekt da” / “nicht da”
Positive Beispiele
Off-line Training
Negative Beispiele
Suche über verschiedenePositionen und Skalen
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Fehler beim Testen
Trainingsbeispiele
Trainieren des Klassifikators
False Positive
Heisele (2002)
Gelabelter Trainingsdatensatz korrekt
Empfindlichkeit
Klassifi-kation
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Receiver Operating Characteristics (ROC)
Problem:Zahl der korrekten Klassifika-tionen / False Alarms hängt von Empfindlichkeit (Schwelle) abErgebnisse verschiedener Klas-sifikatoren nicht vergleichbar
Lösung: ROCKorrekte Klass. und False Alarms gegeneinander auftragenSchwelle variierenFläche zwischen ROC und Diagonale bestimmt Qualität
Pkorrekt
PFA
Zufallsergebnis des Klassifikators
Pkorrekt
PFA
Zufallsergebnis des Klassifikators
1
1
1
1
Schwelle
Schlechter Klassifikator
Guter Klassifikator
Schwelle
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
FussgängerdetektionEinzelne Klassifikatoren trainiert mit Komponenten (Arme, Beine, …)Kombination der Klassifikatoren mit einem weiteren Klassifikator (SVM)
Mohan (2001)
Systemarchitektur
Teilbasierte Erkennung
Positionsbe-schänkungen für Teile
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Teilbasierte ErkennungErgebnisse
Verschiedene Kombina-tionsregeln für die Teil-klassifikatoren– UND (“voting”)– Kombinationsklassi-
fikator (“adaptive”)Besseres Ergebnisse mit teilbasiertem Verfahren als mit Klassifikator für die gesamte Figur
Mohan (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Vorteile teilbasierter MethodenRotation ausserhalb der Bildebene
Rotationen:
Rotation in derBildebene
• Rotationsinvariante Merkmale• Alignment
• Teilbasierte Klassifizierung• Training auf rotierten Gesichtern
Heisele (2002)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Vorteile teilbasierter Methoden
EinfachesTemplate
Teil-Templates
Heisele (2002)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
GesichtsfragmenteVorteile teilbasierter Methoden
Ullman et al. (2002)
Anwendung auf Bilder von Gesichtern und AutosDefinition von Bild-Fragmentendurch Fenster der Grösse p x qVerschiedene AuflösungenInformation eines Fragmentes Füber Gesicht der Klasse C: I(F, C)Maximaler Informationsbeitrag für Fragmente mittlerer Grösse (11 % der Objektgrösse)Selektion der infor-mativsten Fragmente
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Ullmanet al. (2002)
Beispiele:
Beitrag eines Fragmentes F zur Erken-nung eines bestimmten Gesichtes Cgegeben durch Likelihood-Ratio:
Klassifikation des Gesichtes C durchMAX-Pooling der Ausgangssignale der Fragmente Fik (I-tes Fragment des Typs k) über verschiedene Positionen:
Wesentlich bessere Ergebisse als globalen Templates (97 % korrekt; 2.1 % falscher Alarm)Mittlere Fragmentgrösse liefert beste Klassifizierungsergebnisse
Lernen optimaler Fragmente
)|()|()(
CFPCFPFR =
θ>∑ )(max)(log2 lk ik li FFR
33%optimal4%Fragmentgr.
(% G. Fläche)
0%0%30.4%False Alarms
39%95.6%97%Detektion
Gesichter ausserhalb der Klasse C
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Teilbasierte Detektion
Heisele et al. (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Lernen von KomponentenRechtreckige Startregion
Expansion in eine von 4 Richtungen
Heisele (2002)
Extraktion neuer Komponent aus Bildern
Trainieren eines SVM Klassifikators
Auswahl der besten Komponenten anhand des Klassifikationsfehlers
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Lernen von KomponentenErgebnisse:
Bilder: 58 x 58 Pixel
Grosse Zahl ~ 10.000negativer Trainingsbeispiele
Synthetische zusätzliche positive Beispiele aus 3D Gesichtsmodell; ges. ~2700
14 Regionen
Startgrösse 5x5
Endgrösse: Rechtecke mit ca. 15…22 Pixeln Seiten-länge
Heisele (2002)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Lernen von KomponentenFace Detection: Component-based vs. Global Approach
(5,000 faces 25, 000 non-faces)
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2
FP / inspected window
Corr
ect 14 learned components
whole face
Ergebnisse:
Teilbasierte Methode wesentlich besser
Heisele et al (2001)
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Heisele (2002)
Leistungsvergleich False Positives
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
Wichtige Punkte
Kategorisierung -- IdentifikationChorus of PrototypesInformation und TransinformationReceiver Operating CharacteristicsKomponentenbasierte Detektion
M. Giese: Lernmethoden in Computer Grafik und Multimedia16 November 2003
LiteraturEdelman, S. (1999). Representation and Recognition in Vision. MIT Press,
Cambridge, MA. Freedman DJ, Riesenhuber M, Poggio T, Miller EK (2001) Categorical representation
of visual stimuli in the primate prefrontal cortex.Science 293, 312-316.
Heisele B, Serre T, Pontil M, Vetter T, Poggio T (2001) Categorization by Learning and Combining Object Parts. In: Advances in Neural Information Processing Systems (NIPS'01), Vancouver, Canada.
Mildenberger O (1992) Informationstheorie und Codierung. Vieweg-Verlag, Braunschweig.
Mohan A (2000) Object detection in images by components. AI Memo # 1664, CBCL Paper #178. Massachusetts Institute of Technology, Cambridge, MA.
Papoulis A (1991) Probability, Random Variables, and Stochastic Processes.McGraw-Hill, Signapore.
Ullman S, Vidal-Naquet M, Sali E (2002) Visual features of intermediate complexity and their use in classification. Nature Neuroscience 5, 682-687.