EM algoritmus pro Nicka Cartera

Proslulý detektiv Nick Carter se během řešení záhadného zločinu, zmizení psa hraběnky Thunové, ocitl v úzkých. Dá se říci, že bezradně tápe. Jediná stopa, kterou se mu podařilo získat, je pouze několik velmi nekvalitních, téměř zcela nečitelných, snímků pravděpodobného zloducha.

Ano, nyní Nick Carter hluboce lituje, že během studií tolik zanedbával přednášky a semináře předmětu 33RPZ. Ale už je pozdě. Sám není schopen jediné dostupné indicie zužitkovat. Naštěstí se od komisaře Ledviny doslechl o Vás, talentovaných studentech a obrací se s prosbou o pomoc.

Pomůžete Nickovi odhalit tvář zákeřného bídáka a zabránit tak jeho dalším zločinům?

Nick Carter
obr.1. Nick Carter studující EM algoritmus.

Popis dostupných indicií

Jak jsme již zmínili, jediná stopa Nick Cartera je m nečitelných snímků o rozměru Himg x Wimg pixelů (obr. 2). Nick Carter dále ví, že na každém snímku je zachycena tvář padoucha. Nick Carter tuší, že tvář padoucha má rozměr pouze Himg x w pixelů (výška je tedy stejná, jen je tvář o něco užší). Na každém snímku je hledaná tvář pravděpodobně v jiném místě (předpokládáme, že se mění pouze její horizontální pozice k). Barva b ostatních pixelů (tj. pixelů tvořící pozadí) je konstantní. Snímky jsou navíc silně zašuměny (gaussovským šumem).

Nick Carter
obr.2. Ukázka jednoho vstupního obrázku.



Nick Carter
obr.3. Model obrázku. Tvář padoucha na pozici k.

Stochastický model

Vstupní data tvoří množína m obrázků {X1, X2, ... , Xm} o rozměrech Himg × Wimg, kde Xi značí jeden (i-tý) obrázek.  Každý obrázek má tedy n = Himg * Wimg pixelů. V každém obrázku Xi je na ki-té pozici obrázek padouchovy tváře F o rozměru Himg x w, (viz. obr.3). Přesněji, na každém obrázku Xi začíná obrázek obličeje na sloupci ki. Ostatní pixely mají konstantní hodnotu b.

Poloha tváře na obrázcích není předem známá, tj. hodnoty ki jsou neznámé, jedná se o skryté parametry.

Hodnota každého pixelu xi(r,c) v i-tém obrázku na pozici (r,c) je zatížena gaussovským šumem N(0,σ). Pravděpodobnost naměření hodnoty xi(r,c), za předpokladu, že tvář je na ki-té pozici, můžeme tedy zapsat jako:
  1. pro pixely pozadí (tj. pro c vyhovující 1 <= c < ki nebo ki+w <= c <=Wimg ):

    P(xi(r,c) | ki) = N(b, σ)
  2. pro pixely tváře (tj. pro c vyhovující ki <= c < ki+w ):

    P(xi(r,c) | ki) = N(F(r,c-ki+1), σ) .
Pravděpodobnost naměření obrázku Xi, za předpokladu, že tvář padoucha je na ki-té pozici, lze zapsat jako součin přes všechny pixely

P( Xi | ki ) = Πr Πc P( xi(r,c) | ki) .


Pravděpodobnost naměření všech m obrázků P( {X1,...,Xm} ) můžeme vyjádřit jako

P( {X1,...,Xm} ) = Πi P( Xi) = Πi Σk P( Xi , k) = Πi Σk P(k) P( Xi | k) .

Zlogaritmováním získáme věrohodnost L = log P( {X1,...,Xm} ) .

Nick Carter správně usoudil, že pro nejvěrohodnější odhad padouchovy tváře F se nabízí použít EM algoritmus, kde skrytými parametry jsou pozice tváře ki , i=1,..,m v obrázcích.

Formulace EM

EM algoritmus použijeme jako ML-odhad parametrů F, b, σ

(F, b, σ) = argmax P({X1,...,Xm}|F, b, σ).

Skrytými parametry jsou pozice tváře ki v obrázcích.

V EM algoritmu opakovaně střídáme dva kroky, E-krok a M-krok:
  1. E-step:
    V E-kroku, pro odhadnutá F, b, σ vyčíslujeme koeficienty α(k,i) :

    α(k,i) = P(k) * P(Xi | k) / Σk [ P(k) * P(Xi | k) ] ,


    kde k = 1,...,Wimg-w+1, i = 1,...,m. Koeficienty α(k,i) představují odhady pravděpodobnosti P(ki|Xi) . Jinými slovy odhadujeme, jaká je pravděpodobnost, že na i-tém obrázku je tvář na pozici ki a to pro všechny obrázky a všechny možné pozice.

  2. M-step:
    V M-kroku pro daná α(k,i) odhadujeme (maximalizací dolní meze věrohodnosti) parametry P(k), F, b, σ.  Pravděpodobnost P(k) se počítá jako aritmetický průměr α(k,i) přes index i

    P(k) = Σi α(k,i) / m ,

    kde k = 1, ..., Wimg - w + 1 a sčítání je přes i = 1, ..., m. Parametry F, b, σ hledáme maximalizací

    (F, b, σ) = argmax Σi Σk α(k,i) * log P(Xi | k, F, b, σ) ,         (1)

    k = 1, ..., Wimg - w + 1 a sčítání je přes i = 1, ..., m. Vztahy pro F, b, σ získáme položením derivace předešlé rovnice dle F, b, σ rovné nule. Tímto způsobem lze odvodit, že

    F = [ Σi Σk α(k,i) * Xi (:, k:k+w-1) ] / m

    b = [ Σi Σk α(k,i) * S(k,i) ] / [ m * (n-Himg*w) ] ,

    σ2 = [ Σi Σk α(k,i) * ( A(k,i) + B(k,i) ) ] / (m*n) ,
    kde
    S( k,i) = Σr Σc Xi( r,c) , r=1,..., Himg , c=[1:k-1, k+w:Wimg]
    A(k,i) = Σr Σc [ Xi ( r,k+c-1) - F(r,c) ]2 , r=1,...,Himg , c=1,...,w
    B( k,i) = Σr Σc [ Xi( r,c) - b ]2 , r=1,..., Himg , c=[1:k-1, k+w:Wimg]

    ( Vztah b si zkuste odvodit. Položte derivaci rovnice (1) dle b rovnu 0 a vyjádřete b.)

Úkoly

  1. Nastudujte EM algoritmus.
  2. Zkuste si odvodit vztah v M-kroku pro odhad parametru b (barva pozadí).
  3. Použijte EM-algoritmus pro nejvěrohodnější odhad padouchovy tváře F. V každém kroku vykreslujte odhad padouchovy tváře F a věrohodnost odhadu. Vstupní obrázky jsou ke stažení zde: image_data.mat. Soubor obsahuje 500 obrázků o rozměru 45x60pixelů. Předpokládaná šířka padouchovy tváře w je 36 pixelů. Odhad zkuste postupně pro m = 10,100,500.
  4. Do prvních deseti vstupních obrázků vykreslete nalezenou polohu tváře v obrázku, tj. označte počáteční sloupec tváře ki = argmax ki P( ki | Xi).
  5. pozice tváře
    obr.4. Očekávaný výsledek 4. bodu: odhadnutá/nejpravděpodobnější pozice tváře v prvním obrázku.

Nápověda


Soutěž o bonus:



Poznámka I: Případné nejasnosti v zadání konzultujte (např. emailem) s cvičícími.

Doporučená literatura

[1] Expectation-maximization algorithm (Wikipedia).
[2] Podklady pro cvičení (2005)
[3] Schlesinger, Hlaváč. Deset přednášek z teorie statistického s strukturního rozpoznávání.


Created by Martin Urban, last update 14.12.2007