Search
~~UNDERCONSTRUCTION~~
V tomto cvičení se budeme zabývat segmentací barevných (RGB) obrazů do dvou tříd, tj. například budeme hledat oblast v obraze odpovídající nějakému objektu a jeho pozadí. Budou nás zájímat algoritmy, které tuto úlohu řeší poloautomaticky v tom smyslu, že uživatel dodá velice hrubou segmentaci a zbytek udělá počítač sám. Příklady takovéto segmentace jsou na následujícím obrázku:
V následujícím textu (konkrétně v sekcích číslovaných 1.,2. a 3.) si popíšeme tři metody pro segmentaci obrázeků. Budeme postuvat od nejjednoduší k nejsložitější. Povinně je třeba odevzdat pouze metody popsané v sekci 1. a 2. Odevzdání algoritmu GrabCut, který je popsán v sekci 3. je pouze dobrovolné, ale získáte za jeho odevzdání bonusové body a navíc jistě i dobrý pocit. Příklady segmentací uvedené výše jsou získané právě touto metodou, která je mimo jiné součástí programu PhotoShop.
Nejprve si zavedeme statistický model, kterým vstupní obrázek popíšeme. Obrázek je množina pixelů uspořádaných do pravidelné mřížky. Množinu pixelů v obrázku o velikosti <latex>[H\times W]</latex> označíme písmenem <latex>T = \{(i,j) \mid i=1,\ldots,H, j=1,\ldots,W\}</latex>, tj. každý prvek <latex>t\in T</latex> určuje souřadnice jednoho pixelu. Každý pixel <latex>t\in T</latex> dále popíšeme vektorem <latex>{x_t\in\Re^3</latex> a binárním číslem <latex>y_t\in\{1,2\}</latex>. Vektor <latex>x_t=(r_t,g_t,b_t)</latex> bude obsahovat RGB složky barvy pixelu <latex> t </latex>, které lze z obrázku přímo získat (pozorovat). Číslo <latex>y_t</latex> určuje, ke které ze dvou oblastí pixel <latex> t </latex> náleží, např. si můžeme zvolit, že <latex> y_t=1</latex> je pixel objektu a <latex>y_t=2</latex> je pixel pozadí. Vektoru <latex>x_t</latex> budeme říkat vektor barev nebo také barva pixelu <latex> t </latex>. Číslu <latex>y_t</latex> skrytý stav pixelu <latex> t </latex>, protože jeho hodnotu nelze z obrázku přímo získat. Označme písmenem <latex>n=H\cdot W</latex> počet pixelů v obrázku. Dále si písmenem <latex>{\bf x}=(x\in\Re^3\mid t\in T)</latex> označíme uspořádanou n-tici všech vektorů barev a písmenem <latex>{\bf y}=(y_t\in\{1,2\} \mid t\in T)</latex> uspořádanou n-tici všech skrytých stavů.
Ve statistickém přístupu, který k segmentaci obrázku použijeme, se předpokládá, že barvy <latex> {\bf x} </latex> a skryté stavy <latex> {\bf y} </latex> jsou realizací nějakého náhodného procesu se sdruženou hustotou pravděpodobnosti <latex> p({\bf x}, {\bf y}) </latex>. Předpokládejme, že hustota pravděpodobnosti <latex>p({\bf x},{\bf y})</latex> je známá. Potom jeden ze způsobu, jak vstupní obrazek segmentovat je nalezt maximálně pravděpodobmou konfiguraci skrytých stavů <latex> {\bf y} </latex> při zadaných barvách <latex> {\bf x} </latex>, tj. vyřešit následující maximalizační úlohu <latex>
\hat{{\bf y}} = \displaystyle{\rm argmax}\limits_{{\bf y}\in Y} p({\bf y}\mid {\bf x})
</latex> kde <latex>Y=\{1,2\}^n</latex> je množina všech možných konfigurací skrytých stavů, tj. množina všech možných segmentací. Této metodě odhadu skrytých parametrů se říká odhad podle maxima aposteriorní pravděpodobnosti (Maximum a posteriori estimation), ve zkratce MAP odhad.
Reprezentovat hustotu pravděpodobnosti <latex> p({\bf x},{\bf y}) </latex> není v obecném netriviálním případě možné. Např. pro reprezentaci <latex>p({\bf y}\mid {\bf x})</latex> v paměti počítače bychom potřebovali <latex>2^{W\cdot H}}</latex> realných čísel. Stejně tak řešení MAP problému je výpočetně nezvládnutelné. Z tohoto důvodu je nutné náš model <latex>p({\bf x},{\bf y})</latex> zjednodušit přijetím dodatečných předpokladů.
Náš statistický model se podstatně zjednoduší pokud přijmeme následující dodatečné předpoklady:
S použitím předpokladům 1. až 3. se statistický model obrázku zjednoduší na tvar
<latex>
\begin{array}{rcl} p({\bf x},{\bf y}; \theta ) & = & \displaystyle \sum_{{\bf k}\in K^n} p({\bf x}, {\bf k}, {\bf y}; \theta) \\ & = & \displaystyle \sum_{{\bf k}\in K^n} p({\bf x}, {\bf k} \mid {\bf y}; \theta)\; p({\bf y})\\ & = & \displaystyle \sum_{{\bf k}\in K^n} \prod\limits_{t\in T} N(x_t; \mu_{k_t,y_t}, \sigma_{k_t,y_t}) \; p(k_t \mid y_t) \; p(y_t) \\ & = & \displaystyle\frac{1}{2^n} \prod_{t\in T} \sum_{k=1}^K N(x_t; \mu_{k,y_t}, \sigma_{k,y_t}) \; p(k\mid y_t) \end{array}
</latex>
kde <latex> \theta = (\mu_{k,y},\sigma_{k,y}, p(k|y), k=\{1,\ldots,K\}, y\in\{1,2 \})</latex> jsou parametry. Kolik reálných čísel potřebujeme k reprezentaci parametrů <latex> \theta </latex> v paměti počítače ? Pro takto definovaný model vede MAP odhad skrytých stavů na výpočet:
<latex> \begin{array}{rcl}
\hat{{\bf y}} & = & \displaystyle {\rm argmax}_{{\bf y}\in Y} p({\bf y}\mid {\bf x} ; \theta) \\ &= &\displaystyle {\rm argmax}_{{\bf y}\in Y} \log p({\bf x},{\bf y}; \theta) \\ \displaystyle &= & \displaystyle {\rm argmax}_{{\bf y}\in Y} \sum_{t\in T} \log \left ( \sum_{k =1}^K N(x_t;\mu_{k,y_t}, \sigma_{k,y_t})\; p(k \mid y_t) \right )\\ \displaystyle &= & \displaystyle {\rm argmax}_{{\bf y}} \sum_{t\in T} q_t(y_t)
\end{array} </latex>
kde <latex> \setcounter{equation}{0}
\begin{equation} q_t(y) = \displaystyle \log \left ( \sum_{k=1}^K N(x; \mu_{k,y_t}, \sigma_{k,y_t})\; p(k\mid y_t) \right ) \qquad \end{equation}
A tudíž MAP odhad <latex> \hatbf_y=(\hat{y}_1,\ldots,\hat{y}_t)</latex> získáme řešením <latex> n </latex> jednoduchých maximalizačních úloh
<latex> \setcounter{equation}{1} \begin{equation} \hat{y}_t = {\rm argmax}\limits_{y\in \{1,2\}} q_t(y)\;, \qquad t\in T \qquad \qquad \end{equation} </latex>.
Protože jednotlivé členy součtu (1) mohou být velmi malá čísla, naivní implementace výpočtu hodnot <latex> q_t(y_t) </latex> často vede k numerickým chybám. Problém lze obejít výpočetním trikem, který využívá toho, že <latex> \log ( \sum_{i=1}^N b_i )</latex> lze spočítat z logaritmů sčítanců <latex> \log b_i, i=1,\ldots,N </latex>. Tento trik je implementován ve funkci logsumexp, kerou budete mít k dispozici.
Dosud jsme předpokládali, že parametry <latex>\theta</latex> známe. V praxi je však třeba tyto parametry ohadnout tak, aby statistický model odpovídal konkrétnímu segmentovanému obrázku. Pro odhad parametrů budeme potřebovat znát skryté stavy <latex> \tildebf_y = (\hat{y}_t \mid t\in \tilde{T})</latex> pro podmnožinu pixelů <latex> \tilde{T}\subset T</latex>. Dvojici <latex>(\tildebf_y,\tilde{T})</latex> získáme tak, že ve vstupním obrázku manuálně označíme část patřící oblasti 1 (objekt) a část patřící oblasti 2 (pozadí). Označme písmenem <latex>\tilde{T}_1 = \{ t \mid \tilde{y}_t = 1, t\in\tilde{T}\}</latex> množinu pixelů označených jako oblast 1 a písmenem <latex>\tilde{T}_2 = \{ t \mid \tilde{y}_t = 2, t\in\tilde{T}\}</latex> množinu pixelů označených jako oblast 2. Na základě množin <latex>\tilde{T}_1</latex> a <latex>\tilde{T}_2</latex> odhadneme (naučíme) parametry gaussovské směsi pro první a druhou oblast.
Algoritmus 1
S nastavením počtu shluků <latex> K </latex> můžete experimentovat. Jako rozumná hodnota se jeví <latex> K=5 </latex>.
Implementujte funkci, která na vstupu dostane RGB obrázek s jeho částečnou anotací a na výstupu vrací odhadnutou segmentaci ve všech pixelech. Jméno funkce a její vstupní a výstupní argumenty musí být následující:
Synopsis: outL = gmm_segmentation(I,inL) Input: I [H x W x 3 (uint8)] RGB image of size H x W pixels. inL [H x W (uint8)] Partial image annotation: 0 .. pixel not annotated 1 .. pixel assigned label 1 2 .. pixel assigned label 2 Output: outL [H x W] Complete image segmentation. Each pixel must be either 1 or 2.
V této funkci implementujte následujcí výpočet:
Doposud jsme předpokládáli, že skryté stavy jsou na sobě nezávislé. Ikdyž tento předpoklad podstatně zjednodušuje statistický model, očividně neplatí pro většinu obrázků. Přímým důsledkem je, že segmentace odhadnuté pomocí tohoto modelu můžou být silně nekompaktní, tj. složeny z velkého množství malých oblastí. Kompaktní segmentace vynutíme tak, že použijeme jiný model apriorní pravděpodobnosti <latex> p({\bf y}) </latex>. Kokrétně použijeme tzv. Pottsův model, který předpokládá, že skrytý stav v pixelu <latex> t </latex> je přímo ovlivněn jen množinou sousedících pixelů <latex> N_t </latex>, tj. platí <latex> p(y_t \mid \{y_{t'} \mid t'\in T \setminus\{t\}\}) = p(y_t \mid \{y_t \mid t\in N_t\})</latex>. V našem případě zvolíme <latex> N_t = \{ t'\in T \mid \|t-t'\| \leq 1, t' \neq t \} </latex> , tj. každý pixel (až na ty ležící na okraji obrázku) zavisí na čtyřech nejbližších pixelech. Dále zavedeme množinu <latex> E = \{ (t,t')\in T^2 \mid t'\in N_t \} </latex>, která obsahuje dvojice navzájem sousedících pixelů. Pottsův model lze pak definovat vztahem <latex> \setcounter{equation}{2} \begin{equation} \displaystyle p({\bf y}; \lambda) = \frac{1}{Z} \exp \left ( \sum_{(t,t')\in E} g(y_t,y_{t'})\right )\qquad \end{equation} </latex>
kde
<latex> \setcounter{equation}{3} \begin{equation} g(y_t,y_{t'}) = \left \{ \begin{array}{rcl} 0 & \mbox{pokud} & y_t=y_{t'} \\ -\lambda & \mbox{pokud} & y_t\neq y_{t' } \end{array} \right . \qquad \end{equation} </latex> Kladné číslo <latex>\lambda>0</latex> je jediným parametrem Pottsova modelu. Číslo <latex> Z </latex> je normalizační konstanta, která je zvolena tak, aby <latex>\sum_latex_setcounter_equation_5_begin_array_rcl_begin_array_hat_bf_y & = & \displaystyle {\rm argmax}_latex_._rozmyslete_jake_nejnizsi_cislo_bude_vzdy_fungovat p({\bf x},{\bf k}, {\bf y}) </latex> popisující vztah mezi barvami <latex> {\bf x} </latex>, skrytými stavy <latex> {\bf y} </latex> a pomocnými stavy <latex> {\bf k} </latex>. Parametry statistického modelu jsme určili z množiny manuálně anotovaných pixelů. K získání dobrého odhadu je často pořeba anotovat velké množství pixelů, což samozřejmě snižuje praktičnost metody. Jeden ze způsobů, jak tento problém obejít, nabízí algoritmus GrabCut, který je například součástí programu PhotoShop. Myšlenkou algoritmu GrabCut je iterativně odhadovat skryté stavy neanotovaných pixelů a takto odhadnuté skryté stavy použít k odhadu parametrů statistického modelu. Připomeňme, že v metodě popsané v přechozím odstavci jsme parametry odhadovali pouze z manuálně anotovaných pixelů.
Uvažujme stejný statistický model jako v předchozím odstavci, tj. směs gaussovských rozdělení jako model barvy a Pottsův model pro apriorní pravděpodobnost skrytých stavů. Pro takto definovaný model zaveďme funkci <latex>
F({\bf k},{\bf y},\theta) = \log p({\bf x},{\bf k}\mid {\bf y}; \theta) \; p({\bf y};\lambda) = \displaystyle \sum_{t\in T} d_t(k_t, y_t,\theta) + \sum_{(t,t')\in E} g(y_t,y_{t'}) - \log Z
d_t(k_t,y_t,\theta) = \log N(x_t;\mu_{k_t,y_t},\sigma_{k_t,y_t}) + \log p(k_t \mid y_t )
Metoda GrabCut hledá takovou konfiguraci skrytých stavů a parametrů <latex> ({\bf k}, {\bf y}, \theta )</latex>, která maximalizuje kritérium <latex> F({\bf k},{\bf y},\theta) </latex>, tj. řeší úlohu
(\hat{{\bf k}},\hat{{\bf y}},\hat{\theta}) = \displaystyle {\rm argmax}_{{\bf k}\in K^n, {\bf y}\in Y, \theta} F({\bf k},{\bf y},\theta)
Maximalizace funkce <latex>F({\bf k},{\bf y},\theta) </latex> podle všech neznámých současně je složitá. Naopak maximalizaci jen podle jedné z neznámých <latex>({\bf k},{\bf y},\theta) </latex> lze řešit efektivně. Přesně toho využívá algoritmus GrabCut, který funguje následovně:
Algoritmus 2
Implementujte funkci, která na vstupu dostane vstupní RGB obrázek, jeho částečnou anotaci a parametr <latex> \lambda </latex>. Na výstupu tato funkce vrací odhadnutou segmentaci ve všech pixelech. Jméno funkce a její vstupní a výstupní argumenty musí být následující:
Synopsis: outL = grabcut_segmentation(I,inL,Lambda) Input: I [H x W x 3 (uint8)] RGB image of size H x W pixels. inL [H x W (uint8)] Partial image annotation: 0 .. pixel not annotated 1 .. pixel assigned label 1 2 .. pixel assigned label 2 Lambda [1 x 1] Parametr of the Potts model. Output: outL [H x W] Complete image segmentation. Each pixel must be either 1 or 2.
V této funkci implementujte algoritmus 2.
Při řešení úloh použijte balíček funkcí student_package_12may2010.zip (nově přidány mex funkce pro Win64), který obsahuje tyto soubory:
Termín odevzdání 16.5.2010 23:59.
Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si segment_test.zip, rozbalte a přidejte k němu soubory, které vyžadujeme pro odevzdání. Výsledky si ověrte porovnáním s referenčním řešením. Výsledky se mohou lišit závisle na inicializaci parametrů a implementaci k-means, proto se každá funkce pouští vicekrát.
Nástroj Foreground Select (Výběr popředí) v Gimpu
Background eraser nebo Quick selection tool jsou podobné nástroje Adobe Photoshop
Implementace pro vaše programy je od verze 2.1. i v OpenCV
“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts