~~UNDERCONSTRUCTION~~ ====== Segmentace ===== 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: \\ \\ | Vstupní obrázek | Částečná anotace vytvořená manuálně| Počítačem odhadnutá segmentace | |- | {{courses:a4m33mpv:cviceni:5_segmentace:6_2_s.png?250|Vstupní obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:annotated_img1.png?250|Částečně anotovaný obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:segmented_img1.png?250|Automaticky nalezená segmentace}} | |- | {{courses:a4m33mpv:cviceni:5_segmentace:testimg1.png?250|Vstupní obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:testimg1_annot.png?250|Částečně anotovaný obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:testimg1_segment.png?250|Automaticky nalezená segmentace}} | |- | {{courses:a4m33mpv:cviceni:5_segmentace:testimg3.png?250|Vstupní obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:testimg3_annot.png?250|Částečně anotovaný obrázek}} | {{courses:a4m33mpv:cviceni:5_segmentace:testimg3_segment.png?250|Automaticky nalezená segmentace}} | \\ 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. ====== Statistický model obrázku ====== 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 [H\times W] označíme písmenem T = \{(i,j) \mid i=1,\ldots,H, j=1,\ldots,W\}, tj. každý prvek t\in T určuje souřadnice jednoho pixelu. Každý pixel t\in T dále popíšeme vektorem {x_t\in\Re^3 a binárním číslem y_t\in\{1,2\}. Vektor x_t=(r_t,g_t,b_t) bude obsahovat RGB složky barvy pixelu t , které lze z obrázku přímo získat (pozorovat). Číslo y_t určuje, ke které ze dvou oblastí pixel t náleží, např. si můžeme zvolit, že y_t=1 je pixel objektu a y_t=2 je pixel pozadí. Vektoru x_t budeme říkat vektor barev nebo také barva pixelu t . Číslu y_t skrytý stav pixelu t , protože jeho hodnotu nelze z obrázku přímo získat. Označme písmenem n=H\cdot W počet pixelů v obrázku. Dále si písmenem {\bf x}=(x\in\Re^3\mid t\in T) označíme uspořádanou n-tici všech vektorů barev a písmenem {\bf y}=(y_t\in\{1,2\} \mid t\in T) 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 {\bf x} a skryté stavy {\bf y} jsou realizací nějakého náhodného procesu se sdruženou hustotou pravděpodobnosti p({\bf x}, {\bf y}) . Předpokládejme, že hustota pravděpodobnosti p({\bf x},{\bf y}) je známá. Potom jeden ze způsobu, jak vstupní obrazek segmentovat je nalezt maximálně pravděpodobmou konfiguraci skrytých stavů {\bf y} při zadaných barvách {\bf x} , tj. vyřešit následující maximalizační úlohu \\ \\ \hat{{\bf y}} = \displaystyle{\rm argmax}\limits_{{\bf y}\in Y} p({\bf y}\mid {\bf x}) \\ \\ kde Y=\{1,2\}^n 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 p({\bf x},{\bf y}) není v obecném netriviálním případě možné. Např. pro reprezentaci p({\bf y}\mid {\bf x}) v paměti počítače bychom potřebovali 2^{W\cdot H}} realných čísel. Stejně tak řešení MAP problému je výpočetně nezvládnutelné. Z tohoto důvodu je nutné náš model p({\bf x},{\bf y}) zjednodušit přijetím dodatečných předpokladů. ====== 1. Modelování barev pomocí směsi gaussovských rozdělení ====== Náš statistický model se podstatně zjednoduší pokud přijmeme následující dodatečné předpoklady: - Při zafixovné hodnotě skytého stavu y_t je barva pixelu x_t statisticky nezávislá na hodnotách všech ostatních náhodných proměnných v obrázku, tj. platí p(x_t \mid {\bf y}, {\bf x}_{\neq t}) = p(x_t \mid y_t) , kde {\bf x}_{\neq t} = \{ x_{t'} \mid t'\in T\setminus \{t\}\} je množina barev ve všech pixelech až na pixel t . Z toho předpokladu také vyplývá, že p({\bf x}\mid {\bf y}) = \prod_{t\in T} p(x_t \mid y_t) . - Předpokládejme, že hustota pravděpodobnosti p(x_t\mid y_t) je směs gaussovských rozdělení, tj. p(x_t \mid y_t) = \sum_{k=1}^K p(x_t\mid k,y_t) p(k\mid y_t) kde p(x_t\mid k,y_t)= N(x_t; \mu_{k,y_t}, \sigma_{k,y_t}) je [[http://en.wikipedia.org/wiki/Multivariate_normal_distribution|gaussovské rozdělení]] určené vektorem středních hodnot \mu_{k,y_t}\in\Re^3 a kovarianční maticí \sigma_{k,y_t} \in \Re_{+}^{3 \times 3}. Současně předpokládáme, že p(x_t\mid y_t) je nezávislá na pozici pixelu t\in T. Tímto předpokladem jsme ke každému pixelu t implicitně zavedli další náhodný stav k_t , který určuje které z K gaussovských rozdělení generovalo barvu x_t. Písmenem {\bf k} = (k_t \mid t\in T) označme uspořádanou n-tici všech těchto pomocných stavů k_t . - Hodnoty skrytých stavů jsou na sobě nezávislé , tj. platí p({\bf y}) = \prod_{t\in T} p(y_t) . Dále předpokládejme, že hodnota pravděpodobnosti p(y_t) je nezávislá na pozici pixelu. Navíc pro jednoduchost budeme předpokládat, že oba dva skryté stavy jsou stejně pravděpodobné, tj. p(y_t=1) = p(y_t=2) = 0.5. S použitím předpokladům 1. až 3. se statistický model obrázku zjednoduší na tvar// // \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} kde \theta = (\mu_{k,y},\sigma_{k,y}, p(k|y), k=\{1,\ldots,K\}, y\in\{1,2 \}) jsou parametry. Kolik reálných čísel potřebujeme k reprezentaci parametrů \theta v paměti počítače ? Pro takto definovaný model vede MAP odhad skrytých stavů na výpočet:\\ \\ \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} kde \\ \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 \hat{{\bf y}}=(\hat{y}_1,\ldots,\hat{y}_t) získáme řešením n jednoduchých maximalizačních úloh \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} . Protože jednotlivé členy součtu (1) mohou být velmi malá čísla, naivní implementace výpočtu hodnot q_t(y_t) často vede k numerickým chybám. Problém lze obejít výpočetním trikem, který využívá toho, že \log ( \sum_{i=1}^N b_i ) lze spočítat z logaritmů sčítanců \log b_i, i=1,\ldots,N . Tento trik je implementován ve funkci logsumexp, kerou budete mít k dispozici. ===== Odhad parametrů gaussovské směsi pomocí k-means algoritmu ===== Dosud jsme předpokládali, že parametry \theta 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 \tilde{{\bf y}} = (\hat{y}_t \mid t\in \tilde{T}) pro podmnožinu pixelů \tilde{T}\subset T. Dvojici (\tilde{{\bf y}},\tilde{T}) 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 \tilde{T}_1 = \{ t \mid \tilde{y}_t = 1, t\in\tilde{T}\} množinu pixelů označených jako oblast 1 a písmenem \tilde{T}_2 = \{ t \mid \tilde{y}_t = 2, t\in\tilde{T}\} množinu pixelů označených jako oblast 2. Na základě množin \tilde{T}_1 a \tilde{T}_2 odhadneme (naučíme) parametry gaussovské směsi pro první a druhou oblast. **Algoritmus 1** * **Vstup**: Částečná anotace vstupního obrázku (\tilde{{\bf y}},\tilde{T}); počet shluků K . * **Výstup**: Parametry gaussovské směsi \theta pro oblast 1 a 2 . - Použijte algoritmus k-means s běžnou euklodovskou metrikou [[..:3_indexace:start#vektorova_kvantizace_-_k-means|(viz. cvičení 3)]] k roztřídění barev \{ x_t \mid t\in\tilde{T_1}\} do K shluků. Výstupem shlukování budou čísla ( \tilde{k}_t \in \{1,\ldots,K\} \mid t\in\tilde{T}_1), která udávají příslušnost jednotlivých pixelů z množiny \tilde{T_1} k jednomu z K shluků. - Vektor středních hodnot \mu_{k,1} spočtěte jako výběrový průměr bodů \{x_t \mid \tilde{k}_t = k, t\in \tilde{T}_1\} patřících k-tému shluku. Pro výpočet středních hodnot použijte funkci mean . - Kovarianční matici \sigma_{k,1} spočtěte jako výběrovou kovarianční matici bodů \{x_t \mid \tilde{k}_t = k, t\in \tilde{T}_1\} patřících k-tému shluku. Pro výpočet kovariančních matic použijte funkci cov . - Pravděpodobnost p(k\mid y=1) spočtěte jako poměr barev patřící do k-tého shluku ku počtu všem pixelů označených jako oblast 1, tj. p(k\mid y=1) = \frac{A}{B} kde A = |\{ t\in \tilde{T}_1 \mid \tilde{k}_t = k \}| a B= {|\tilde{T}_1| } . - Kroky 1. až 4. zopakuje pro směs oblasti 2, tj. ve vzorcích zaměňte (\tilde{T}_1,\mu_{k,1},\sigma_{k,1},p(k\mid y= 1)) za (\tilde{T}_2,\mu_{k,2},\sigma_{k,2},p(k\mid y= 2)) . S nastavením počtu shluků K můžete experimentovat. Jako rozumná hodnota se jeví K=5 . ===== Zadání úlohy 1 ===== 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: - Pomocí Algoritmu 1 odhadněte parametry směsi gaussovských rozdělení pro pixely označené značkou 1 a 2. - Odhadněte skryté stavy neanotovaných pixelů pomocí vztahu (2). Nezapomeňte pro výpočet hodnot q_t(y_t) použít funkci logsumexp. ====== 2. Pottsův model ====== 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 p({\bf y}) . Kokrétně použijeme tzv. Pottsův model, který předpokládá, že skrytý stav v pixelu t je přímo ovlivněn jen množinou sousedících pixelů N_t , tj. platí p(y_t \mid \{y_{t'} \mid t'\in T \setminus\{t\}\}) = p(y_t \mid \{y_t \mid t\in N_t\}). V našem případě zvolíme N_t = \{ t'\in T \mid \|t-t'\| \leq 1, t' \neq t \} , 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 E = \{ (t,t')\in T^2 \mid t'\in N_t \} , která obsahuje dvojice navzájem sousedících pixelů. Pottsův model lze pak definovat vztahem \\ \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} kde \\ \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} \\ Kladné číslo \lambda>0 je jediným parametrem Pottsova modelu. Číslo Z je normalizační konstanta, která je zvolena tak, aby \sum_{{\bf y}\in Y} p({\bf y};\lambda) = 1. Snadno je vidět, že pravděpodobnost p({\bf y}; \lambda) bude maximální pokud segmentace {\bf y} bude tvořena jen jednou oblastí (nejkompaktnější segmentace). Naopak p({\bf y}; \lambda) bude nejmenší, pokud všechny sousedící pixely budou mít jiný skrytý stav (nejméně kompaktní segmentace). Použijeme-li pro popis barvy gaussovskou směs jako v předchozím odstavci a jako apriorní pravděpodobnost Pottsův model, pak dostane následující statistický model obrázku: p({\bf x},{\bf y}; \theta,\lambda ) = \displaystyle \sum_{{\bf k}\in K^n} p({\bf x}, {\bf k} \mid {\bf y}; \theta)\; p({\bf y};\lambda) = \displaystyle \sum_{{\bf k}\in K^n} \left ( \prod\limits_{t\in T} N(x_t; \mu_{k_t,y_t}, \sigma_{k_t,y_t}) \; p(k_t \mid y_t) \right ) \; \left ( \frac{1}{Z} \exp \big ( \sum_{(t,t')\in E} g(y_t,y_{t'})\big ) \right ) \;.\\ MAP odhad pro takto definovaný model vede na řešení následující maximalizační úlohy, tzv. max-sum problém:\\ \setcounter{equation}{5} \begin{array}{rcl} % \begin{array} \hat{{\bf y}} & = & \displaystyle {\rm argmax}_{{\bf y}\in Y} \log p({\bf x}, {\bf y}; \theta, \lambda) \\ &= &\displaystyle {\rm argmax}_{{\bf y}\in Y} \Bigg ( \sum_{t\in T} q_t(y_t) + \sum_{(t,t')\in E} g(y_t,y_{t'}) \Bigg) \qquad \end{array} \qquad \end{equation} kde q_t(y_t) jsou funkce dané vzorcem (1) a g(y,y') vzorcem (4). U výsledné segmentace bychom chtěli zaručit, aby skryté stavy v manuálně označených pixelech \tilde{T} odpovídaly zadaným hodnotám \tilde{y} . Toho dosáhneme modifikací hodnot unárních funkcí q_t(y_t) právě v těchto pixelex: \\ \setcounter{equation}{5} \begin{equation} \begin{array}{rcl} q_t(1) & = & {\rm Konst} \; , \qquad t\in\tilde{T}_1 \\ q_t(2) & = & {\rm Konst} \; , \qquad t\in\tilde{T}_2 \\ \end{array} \qquad \qquad \end{equation} kde {\rm Konst} je nějaké velké číslo, např. použijte {\rm Konst}=10000 . Rozmyslete jaké nejnižší číslo bude vždy fungovat ? K vyřešení MAP problému (5) použijte funkci emaxflow_mex, která má následující volací konvenci: >> help emaxflow_mex Synopsis: x = emaxflow_mex(E,Q,G) Description: This functions finds a global minimum of the energy function F(x) = sum Q(x(t),t) + sum G(x(E(1,e),x(E(2,e)),e) t=1:nV e=1:nE where all G(:,:,e) must be submodular functions. Input: E [2 x nE] int32 -- edges of the graph (0-based index) Q [2 x nV] int32 -- univariate functions G [2 x 2 x nE] int32 -- pairwise functions Output: x [nV x 1] int32 - optimal solution (0-based) Všiměte si, že: * emaxflow_mex řeší minimalizační úlohu zatímco my potřebujeme maximalizovat. Maximalizaci převedeme na minimalizaci tak, že vynásobíme funkce q_t(y_t) a g(y_t,y_{t'}) číslem -1 . * emaxflow_mex vyžaduje na vstupu hodnoty funkcí q_t(x_t) a g(y_t,y_{t'}) reprezentované typem int32. Proto nezapomeňte hodnoty správně přetypovat, tj. v Matlabu použijte a = int32(b). * Indexy uzlů v definici hran jsou číslovány od nuly. Podobně složky vektoru řešení, tj. nalezené skryté stavy, jsou číslovány od nuly. Pro odhad parametrů \theta gaussovských směsí, které modelují barvu pixelů, můžeme použít Algoritmus 1. Parametr \lambda , který je jediným parametrem Pottsova modelu, nebudeme odhadovat z dat, ale naladíme ho ručně. V testech se ukázalo, že pro většinu obrázků dává \lambda = 10 rozumné výsledky. ===== Zadání úlohy 2 ===== Implementujte funkci, která na vstupu dostane RGB obrázek, jeho částečnou anotací a parametr \lambda . 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 = graphcut_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 následujcí výpočet: - Pomocí Algoritmu 1 odhadněte parametry směsi gaussovských rozdělení pro pixely označené značkou 1 a 2. - Spočtě unární (datové) členy q_t(y_t) dané vzorcem (1), přičemž pro jejich výpočet opět použijte funkci sumlogexp. Modifikujte odpovídající členy q_t(y_t) podle vztahu (6). - Vytvořte množinu hran E, která spojující každý pixel s jeho 4-okolím. Např. pro obrázek velikosti 3x3 bude v Matlaboveské notaci E = [ 0 1 2 3 4 5 0 3 6 1 4 7 ; 3 4 5 6 7 8 1 4 7 2 5 8 ]. - Vypočtěte binární člen g(y,y') podle vzorce (4). - Vyřešte max-sum problém (5) pomocí funkce emaxflow_mex a vraťte získaný výsledek jako odhadnutou segmentaci. Nezapomeňte zajistit aby výstupní segmentace byla stejného formatu jako vstupní obrázek a její hodnoty byly jen 1 a 2. Např. použijte outL = reshape(S+1,H,W) kde S je výsledek emaxflow_mex. ====== 3. GrabCut algoritmus ====== V předcházejících odstavcích jsme si zavedli statistický model obrázku, kterým byla združená pravděpodobnost p({\bf x},{\bf y}) = \sum_{{\bf k\in K^n}} p({\bf x},{\bf k}, {\bf y}) popisující vztah mezi barvami {\bf x} , skrytými stavy {\bf y} a pomocnými stavy {\bf k} . 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 \\ 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 kde 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ů ({\bf k}, {\bf y}, \theta ), která maximalizuje kritérium F({\bf k},{\bf y},\theta) , 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 F({\bf k},{\bf y},\theta) podle všech neznámých současně je složitá. Naopak maximalizaci jen podle jedné z neznámých ({\bf k},{\bf y},\theta) lze řešit efektivně. Přesně toho využívá algoritmus GrabCut, který funguje následovně: **Algoritmus 2** * **Vstup: ** Barvy vstupního obázku {\bf x}; částečná anotace (\tilde{\bf y},\tilde{T}) ; počet shluků K ; parametr Pottsova modelu \lambda * **Výstup: ** Odhadnutá segmentace \hat{\bf y}}. - Inicializuj parametry \hat{\theta} pomocí Algoritmu 1. - Zafixuj \hat{\theta} a maximalizuj F({\bf k},{\bf y},\theta) podle ({\bf k},{\bf y}), tj. vyřeš (\hat{{\bf k}},\hat{{\bf y}}) = \displaystyle {\rm argmax}_{{\bf k},{\bf y}} F({\bf k},{\bf y},\hat{\theta}) . Řešení získáme ve třech krocích: - Spočteme hodnoty k'_t(y) = {\rm argmax}_{k=1,\ldots,K} d_t(k,y,\hat{\theta}) pro všechny t\in T, y\in\{1,2\} - Pomocí funkce emaxflow_mex vyřešíme \hat{{\bf y}} = {\rm argmax}_{{\bf y}\in Y} \big (\sum_{t\in T} d_t(k'_t(y_t), y_t,\hat{\theta}) + \sum_{(t,t')\in E} g(y_t,y_{t'}) \big ). - Nastavíme \hat{k}_t = k'_t(\hat{y}_t) pro všechny t\in T. - Pokud se získaná segmentace \hat{\bf y} neliší od segmentace z předchozím kroku ve více než M pixelech (rozumná hodnota je M = 10), pak vrať segmentaci \hat{\bf y}. Jinak jdi na krok 4. - Zafixuj (\hat{{\bf k}},\hat{{\bf y}}) a maximalizuj F({\bf k},{\bf y},\theta) podle \hat{\theta} , tj. vyřeš \hat{\theta} = \displaystyle {\rm argmax}_{\theta} F(\hat{{\bf k}},\hat{{\bf y}}, \theta) . Řešení získáme ve třech krocích: - Vektory sředních hodnot \mu_{k,y},\; k=1,\ldots,K, y=\{1,2\} spočteme jako výběrové průměry bodů \{x_t \mid \hat{k}_t = k, \hat{y}_t = y, t\in T \} . - Kovarianční matice \sigma_{k,y}\; k=1,\ldots,K, y=\{1,2\} spočteme jako výběrové kovarianční matice bodů \{x_t \mid \hat{k}_t = k, \hat{y}_t = y, t\in \tilde{T}_1\} . - Pravděpodobnosti směsi spočtěte podle vzorce p(k\mid y) = \frac{A}{B}, kde A je počet prvků (kardinalita) množiny \{ t\in T \mid \hat{k}_t = k, \hat{y}_t = y\} a B je počet prvků množiny \{ t \in T \mid \hat{y}_t = y \} . - Pokračuj krokem 2. ===== Zadání úlohy 3 ===== Implementujte funkci, která na vstupu dostane vstupní RGB obrázek, jeho částečnou anotaci a parametr \lambda . 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. ====== Balíček funkcí ====== Při řešení úloh použijte balíček funkcí {{:courses:a4m33mpv:cviceni:5_segmentace:student_package_12may2010.zip|student_package_12may2010.zip }} (nově přidány mex funkce pro Win64), který obsahuje tyto soubory: * image_segmentation.m ... interaktivní nástroj, který umožňuje anotovat obrázky a volá funkce gmm_segmentation, graphcut_segmentation a gabcut_segmentation jejichž výsledky vizualizuje. Tuto funkci použijte pro ladění vašich metod. * emaxflow_mex.(mexglx,mexa64,mexw32) ... MEX implementace MAX-SUM solveru kompilovaná pro Linux, Linux64 a Windows. * emaxflow_mex.m ... help k emaxflow_mex.XXXX. * logsumexp.m ... funkce pro výpočet logaritmu součtu z velmi malých čísel. * gmm_segmentation.m, graphcut_segmentation.m, gabcut_segmentation.m ... templaty funkcí, které máte implementovat a odevzdat. * testimg1.png, testimg2.png, testimg3.png ... testovací obrázky. ====== Co odevzdat ====== * Povinná část (5+5 bodů): Vyřešte úlohu 1 a 2 a do odevzdávacího systému nahrajte soubory gmm_segmentation.m a graphcut_segmentation.m spolu se všemi kódy, které ke své činnosti vyžadují. * Bonusová úloha (3 body): Vyřešte úlohu 3 a do odevzdávacího systému nahrajte soubor grabcut_segmentation.m spolu se všemi kódy, které ke své činnosti vyžadují. Termín odevzdání 16.5.2010 23:59. ===== Kontrola výsledků ===== Pro kontrolu správnosti odevzdaných funkcí jsme použili skript a funkci MATLABu publish. Nakopírujte si {{courses:a4m33mpv:cviceni:5_segmentace:segment_test.zip|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 [[http://cmp.felk.cvut.cz/~perdom1/mpv/10_segment/test.html|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. ====== Reference ====== [[http://docs.gimp.org/en/gimp-tool-foreground-select.html|Nástroj Foreground Select (Výběr popředí)]] v [[http://www.gimp.org/|Gimpu]] [[http://livedocs.adobe.com/en_US/Photoshop/10.0/help.html?content=WSfd1234e1c4b69f30ea53e41001031ab64-76c4.html|Background eraser]] nebo [[http://livedocs.adobe.com/en_US/Photoshop/10.0/help.html?content=WSFD9BA8C5-31BA-4fec-81F3-CF04EE5295FC.html|Quick selection tool]] jsou podobné nástroje [[http://www.adobe.com/products/photoshop/compare//|Adobe Photoshop]] [[http://sourceforge.net/projects/opencvlibrary/|Implementace pro vaše programy je od verze 2.1. i v OpenCV]] [[http://research.microsoft.com/pubs/67890/siggraph04-grabcut.pdf|“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts]]