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ů Xi ∈ Rn (v našem případě to jsou vektorizované obrázky obličejů). PCA předpokládá, že vzorky mají nulový součet, tj. že  ∑iXi=1...k=0, kde 0∈ Rn je nulový vektor. Je tedy třeba před použitím PCA od všech vzorků odečíst jejich průměr  ∑iXi=1...k/k.

Cílem PCA je nalézt m < n vektorů Yj ∈ Rn takových, že reprezentace vzorků Xi lineární kombinací Yj má ve smyslu nejmenších čtverců minimální reziduum.  Tedy, aproximujeme každé Xi lineární kombinací Yj (Zi je aproximace Xi)

Zi = ∑j wij Yj,            i = 1, ... , k; j = 1, ... , m

tak, že reziduum
g(Yj, wij) = ∑i || Xi - Zi ||2

je minimální. Každý vzorek Xi je tedy reprezentován pouze m čísly wij, j = 1, ... ,m.

Vektory Yj  řešící tento problém jsou rovné vlastním vektorům matice S = XXT 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á Xi. Vlastním vektorům Yj se v případě, že vstupy Xi jsou obrázky obličejů, říká eigenfaces (z anglického eigenvectors). Můžeme je dát do matice Y o rozměru n×m.

Když máme eigenfaces Yj, koeficienty lineární kombinace se najdou jako wij = YjT Xi, což v maticové formě lze psát jako W=YTX.

Odvození zde uvedené teorie lze najít v [1].

Výpočetní trik

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

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

Su = λu

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 = v = λ(Xv)
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í

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

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

  3. Vykreslete vlastní vektory (eigenfaces) jako obrázky (mají stejné rozměry jako původní obrázky).

    ...

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


  5. Vykreslete rekonstrukci vybraného obličeje s použitím narůstajícího počtu vlastních vektorů.

                                      

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

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