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?
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).
obr.2. Ukázka jednoho vstupního obrázku.
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:
pro pixely pozadí (tj. pro c vyhovující 1 <= c < ki
nebo ki+w
<= c <=Wimg ):
P(xi(r,c)
| ki) = N(b, σ)
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
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:
E-step:
V E-kroku, pro odhadnutá
F, b, σ vyčíslujeme koeficienty α(k,i) :
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.
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í
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)
] ,
( Vztah
b si
zkuste odvodit. Položte derivaci rovnice (1) dle b rovnu 0 a vyjádřete b.)
Úkoly
Nastudujte EM algoritmus.
Zkuste si odvodit vztah v M-kroku pro odhad parametru b (barva pozadí).
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.
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).
obr.4. Očekávaný výsledek 4. bodu: odhadnutá/nejpravděpodobnější pozice
tváře v prvním obrázku.
Nápověda
V E-kroku, během výpočtu
α(k,i)
doporučujeme sečíst nejdříve exponenty všech gaussiánů, které se
vyskytují v součinech. Dále před vydělením samotného zlomku je vhodné
vynásobit čitatel i jmenovatel dostatečně
velkým číslem (tj. přičíst k exponentům dostatečně velké číslo), abyste
předešli zaokrouhlovacím chybám funkce exp.
Chytřejší a doporučené řešení zmíněného problému napovídá Lukáš Cerman: "Uvedený problém lze vyřešit numericky stabilnějším výpočtem -- stačí invertovat podíl, posčítat části a invertovat zpátky
(viz. obr, nebo pdf).
Exponenciály v dílčích součtech se tak výrazně zmenší, protože stačí odečíst jejich exponenty."
Ti, kteří nedůvěřují vlastní implementaci výpočtu koeficientů
α(k,i) ,
mohou pro urychlení použít funkci
getalpha.m od studentů Rusz,Horniak.
Soutěž o bonus:
Výsledky rekonstrukce tváře včetně zdrojových kódů můžete posílat již během týdne
emailem cvičícím. Prvních 5 správných řešení získávají bonus významné váhy (tzv. EM bonus).
Poznámka I: Případné nejasnosti v zadání konzultujte
(např. emailem) s cvičícími.