Principal Component Analysis (PCA)

Principal component analysis (PCA) je technika redukce dimenze příznakového prostoru. Také se o ní mluví jako o metodě extrakce příznaků. V dnešním cvičení použijeme PCA k redukci dimenze příznakového prostoru obrázků obličejů.

Vstupem do našeho algoritmu jsou obrázky obličejů o rozměrech 300×250 pixelů. Dále se ale na obrázky budeme raději dívat jako na sloupcový vektor délky n = 75000 (= 300 * 250). Délka vektoru reprezentujícího obrázek, n, určuje dimenzi příznakového prostoru. Cílem PCA je nalézt takovou reprezentaci, ve které bude obrázek vyjádřen vektorem délky m << n (odtud "redukce dimenze příznakového prostoru").

V tomto nízkodimenzionálním prostoru budeme klasifikovat nové obrázky pomocí metody nejbližšího souseda.

Nezbytné teoretické minimum

Mějme k vzorků X_i ∈ Rⁿ (v našem případě to jsou vektorizované obrázky obličejů). Cílem PCA je nalézt m < n vektorů Y_j ∈ Rⁿ takových, že reprezentace vzorků X_i lineární kombinací Y_j má ve smyslu nejmenších čtverců minimální reziduum. Tedy, aproximujeme každé X_i lineární kombinací Y_j (Z_i je aproximace X_i)

Z_i = ∑_j w_ij Y_j, i = 1, ... , k; j = 1, ... , m
tak, že reziduum

g(Y_j, w_ij) = ∑_i || X_i - Z_i ||²

je minimální. Každý vzorek X_i je tedy reprezentován (s minimální chybou) pouze m čísly w_ij, j = 1, ... ,m.

Vektory Y_j řešící tento problém jsou rovné vlastním vektorům matice S = XX^T odpovídajícím m největším vlastním číslům. Matice X má rozměry n×k a její i-tý sloupec odpovídá X_i. Koeficienty w_ij lineární kombinace se najdou jako w_ij = X_i^T Y_j. Podrobnější odvození těchto vztahů lze najít v [1].

Vlastním vektorům Y_j se v případě, že vstupy X_i jsou obrázky obličejů, říká eigenfaces (z anglického eigenvectors).

Výpočetní trik

V případě obrázků bývá matice S příliš velká (v našem případě asi 45 GB) na to, abychom s ní mohli pracovat. Je tedy nutné použít následující výpočetní "trik" [3, 5].

V původní úloze hledáme vlastní vektory matice S = XX^T (n×n):

Su = λu

Namísto matice S vytvoříme mnohem menší (k×k) matici T = X^TX. Pro její vlastní vektory platí

Tv = (X^TX)v = λv
X(X^TX)v = Xλv = λ(Xv)
S(Xv) = λ(Xv)

Pokud nám tedy stačí m ≤ k vlastních vektorů matice S, stačí spočítat vlastní vektory mnohem menší matice T a z nich pronásobením maticí X dostáváme požadované vlastní vektory matice S.

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.

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).

...
Všimněte si prvního vlastního vektoru. Víte, čemu odpovídá?
Vykreslete si kumulativni součet seřazených normovaných (sčítají do jedničky) vlastních čísel (vynechejte první vlastní číslo).
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ů.
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, 29.12.2006