Namísto matice S vytvoříme
mnohem menší (
k×
k) matici
T
=
XTX. Pro její vlastní
vektory platí
Tv = (
XTX)
v = λ
v
X(
XTX)
v = Xλ
v = λ(X
v)
S(
Xv) = λ(
Xv)
Stačí tedy vypočítat vlastní vektory v mnohem menší matice
T a z nich dostat vlastní
vektory matice S jako u=Xv.
Poznámka. Vlastní vektory matice S=XXT jde také
spočítat pomocí úsporné formy SVD (Singular Value Decomposition) přímo
z matice X, což se v MATLABu napíše jako [Y S V]=svd(X,0). To ale
používat nebudeme, protože to déle trvá a chceme si procvičit
popsaný výpočetní trik. Hloubavější studenti se ale nad tím mohou zamyslet.
Shrnutí teorie
V tomto odstavci jsou slovně
popsány operace, které budete potřebovat při práci na úloze.
U každého tvrzení se
zastavte a promyslete si, jestli ho chápete a napište si ho ve
vektorovém zápisu! Prostoru
s redukovanou dimenzí, m,
budeme říkat obličejový prostor. Nezapomeňte, že před každou transformací do
obličejového prostoru je třeba odečíst průměrný obrázek a po transformaci z
obličejového prostoru ho opět přičíst.
Transformace obrázku do
obličejového prostoru - Skalární součin obrázku s každým
vlastním vektorem, výsledky uložené do vektoru délky
m.
Transformace z obličejového prostoru do obrázku -
Vynásobení vlastních vektorů jim odpovídajícími složkami vektoru z
obličejového prostoru, z toho celého suma.
Částečná rekonstrukce obrázku - Transformace do obličejového prostoru, transformace zpět s použitím jen několika prvních dimenzí obličejového prostoru.
Naučení nového obličeje
- Transformace obrázku do obličejového prostoru a zapamatování si
výsledného vektoru (který je mnohem kratší, než původní vektor).
Rozpoznání známého
obličeje -
Transformace daného obrázku do obličejového prostoru a nalezení
nejbližšího souseda (mezi naučenými obličeji). Pokud jsme
dostatečně blízko
(práh), vrať identitu nalezeného obličeje. Jinak vrať "neznámý obličej"
(Také je možné uložit si neznámý obličej jako "neznámý obličej #1".).
Vyhodnocení
"obličejovitosti"
obrázku
- Pokud si nejsme jistí, jestli je daný obrázek obličej, můžeme provést
následující: Transformace do obličejového prostoru následovaná
transformací zpět. Získaný obrázek obrázek porovnej s původním
(mean squared error) a pokud je chyba příliš velká, označ obrázek jako
"neobličej", jinak ho označ jako "obličej" (viz úkol s detekcí obličejů
v bonusové úloze).
Zadání
- Stáhněte si soubor data_33rpz_cv12.mat
s obrázky obličejů. Soubor obsahuje struktury trn_data
(trénovací data) a tst_data
(testovací data). Obě struktury mají položky images
a names
(jména lidí na obrázcích -- bude se hodit pro rozpoznávaní).
- Implementujte
algoritmus PCA s využitím výše popsaného "triku". Vstupem algoritmu
budou obrázky z trn_data.
Tip 1:
Vlastní čísla a vektory počítá v Matlabu funkce eig.
Tip 2:
Vlastní vektory si po jejich nalezení znormalizujte na jednotkovou
velikost.
- Vykreslete vlastní vektory
(eigenfaces) jako
obrázky (mají stejné rozměry jako původní obrázky).
...
- Vykreslete si kumulativni součet seřazených normovaných
(sčítají do jedničky) vlastních čísel.
Vždy záleží na
úloze, ale většinou se počet vlastních
vektorů, které se používají pro aproximaci vstupních vzorků, bere tak,
aby kumulativní součet jim odpovídajících vlastních čísel dával 65-90%
ze součtu všech vlastních čísel.
- Vykreslete rekonstrukci vybraného obličeje s
použitím narůstajícího
počtu vlastních vektorů.
- Vykreslete závislost chyby rekonstrukce na počtu m
vlastních vektorů. Chybou rekonstrukce zde míníme průměrnou hodnotu
čtverců rozdílů mezi původními a rekonstruovanými obličeji, to celé
počítané přes celou trénovací množinu.
- Pomocí metody nejbližšího souseda klasifikujte obrázky z tst_data.
Experimentujte s počtem použitých vlastních vektorů. Vypište chybu
klasifikace.
Bonusová úloha
Po absolvování kurzu 33RPZ máte na výběr z mnoha možností, co s
nalezenými eigenfaces podniknout. Můžete například...
- ... vyzkoušet jiný (snad i lepší) klasifikátor v ůloze
rozpoznávání,
- ... zkusit obličeje co nejlépe zarovnat a teprve pak na ně
pustit PCA (Použijte data,
kde je více prostoru okolo obličeje pro zarovnání a masky pro vyříznutí
obličejové
části. Také se můžete inspirovat stránkou [4].),
- ... vyzkoušet PCA na data s písmeny z minulých cvičení
(viz např. data z cvičení
na AdaBoost),
- ... porovnat PCA s Independent Component Analysis (ICA),
- ... napsat jednoduchý (i když pomalý) detektor obličejů
(viz odstavec Shrnutí teorie),
- ... použít PCA ke kompresi obrázku [2] ,
- ...
Vypracování libovolného z těchto rozšíření bude ohodnoceno bonusovým
bodem. Úlohy jsou záměrně formulovány ne moc konkrétně. Jejich
přesná formulace a navržení správných výstupů je součástí úkolu. Pokud
máte jiný nápad, jak tuto úlohu rozšířit, konzultujte svůj návrh
nejdříve se cvičícími (možno i emailem).
Doporučená literatura
[1]
Vysvětlení PCA
[2]
Text cvičení z
minulých
let
[3]
Eigenfaces
for recognition talk
[
4]
Zarovnání obličejů pro
přesnější PCA
[5] Turk, M. and Pentland, A. (1991). Eigenfaces for recognition. The
Journal of Cognitive Neuroscience, 3(1): 71-86.
Created by Jan Šochman. Last modification
10.1.2009