Segmentace obrazu[5] obn´aˇs´ı rozdˇelen´ı obrazu na oblasti, kter´e silnˇe koreluj´ı s re´aln´ymi objekty ˇci oblastmi obsaˇzen´ymi v obraze. Nejˇcastˇeji se jako roz-hoduj´ıc´ı atribut pouˇz´ıv´a hodnota intenzity pro jednobarevn´e obrazy a jednot-liv´e komponenty barev (napˇr. kaˇzd´y z kan´al˚u RGB barevn´eho sch´ematu) pro v´ıcebarevn´e obrazy[8].
Neexistuje ˇz´adn´a ucelen´a teorie o segmentaci obrazu[8], n´asledkem ˇcehoˇz ne-vznikla pouze jedin´a univerz´aln´ı metoda pro tento probl´em. Existuje vˇetˇs´ı mnoˇzstv´ı metod, kter´e vznikly jako ˇreˇsen´ı urˇcit´eho probl´emu a postupnˇe z´ıskaly na popularitˇe. Protoˇze existuje velk´e mnoˇzstv´ı segmentaˇcn´ıch metod, je tˇreba nˇejak hodnotit jejich v´ysledky. Haralick a Shapiro[10] stanovili, ˇze segmenty by mˇely splˇnovat n´asleduj´ıc´ı vlastnosti
• Oblasti segment˚u by mˇely b´yt uniformn´ı a homogenn´ı
• Vnitˇrky segment˚u by nemˇely obsahovat mnoho mal´ych dˇer
• Hranice kaˇzd´eho segmentu by mˇely b´yt jednoduch´e, prostorovˇe pˇresn´e a pokud moˇzno nepˇr´ıliˇs ˇclenit´e
• Sousedn´ı segmenty by mˇely b´yt co nejv´ıce rozd´ıln´e (s ohledem na seg-mentaˇcn´ı atribut, podle kter´eho je oblast segmentu uniformn´ı)
Jeden ze zp˚usob˚u jak hodnotit segmentaˇcn´ı metody pˇredpokl´ad´a, ˇze spr´avn´a segmentace je zn´ama pˇredem. V´ysledky mˇeˇren´e metody jsou potom porovn´av´any s touto ”ground truth”. Tento postup je vˇsak velmi pracn´y[5] a nav´ıc pro vze-vrubn´e posouzen´ı metody, je tˇreba m´ıt objemnou datab´azi takov´ychto obraz˚u (nejzn´amˇejˇs´ı je nejsp´ıˇse The Berkeley Segmentation Dataset [11]).
Dalˇs´ım ze zp˚usob˚u je hodnocen´ı bez dohledu (unsupervised evaluation), kter´y je ovˇsem zpravidla testov´an na syntetick´ych datasetech a na vlastnosti ob-raz˚u zav´ad´ı restrikce, kter´e ˇcasto nemohou b´yt pouˇzit´e v aplikac´ıch z re´aln´eho svˇeta.[5]
(a) P˚uvodn´ı obraz
(b) Nejbliˇzˇs´ı soused (c) Biline´arn´ı int.
(d) Bell (e) Catmul-Rom
Obr. 8Porovn´an´ı interpolaˇcn´ıch metod
Moment´alnˇe vˇsak neexistuje ˇz´adn´y konsensus o tom, jak tyto metody hodnotit.
Pro praktick´e pouˇzit´ı se zpravidla zodpov´ıdaj´ı tˇri ot´azky[5]
1. Jak ˇcasto metoda selˇze (tzn. metoda ned´a rozumn´y v´ysledek) 2. Jak pˇresn´a metoda je
3. Do jak´e m´ıry je metoda reprodukovateln´a na ´uspˇeˇsn´ych pˇr´ıpadech
3.2.1 Zvaˇ zovan´ e metody
Jak jiˇz bylo zm´ınˇeno v´yˇse, existuje nepˇrebern´e mnoˇzstv´ı metod, kter´e dok´aˇz´ı obraz segmentovat. Prvn´ım zvaˇzovan´ym algoritmem byla, na z´akladˇe doporuˇcen´ı vedouc´ıho pr´ace, segmentace s vyuˇzit´ım hled´an´ı minim´aln´ıho ˇrezu (maxim´aln´ıho tok) grafu - GrabCut[12]. Tato metoda je inicializov´ana nalezen´ım bod˚u n´aleˇz´ıc´ıch pozad´ı a popˇred´ı, kter´e slouˇz´ı jako pevn´e omezen´ı (hard constraint); dodateˇcn´a flexibiln´ı omezen´ı (soft constraints) mohou b´yt zavedena, aby reflektovala in-formaci o oblastech nebo hranic´ıch objekt˚u. Vzhledem k tomu, ˇze tato metoda segmentuje obraz pouze na pozad´ı a popˇred´ı a ˇze poˇzadovan´y algoritmus by mˇel b´yt plnˇe automatick´y, byla nakonec segmentace s vyuˇzit´ım hled´an´ı mi-nim´aln´ıho ˇrezu grafu zam´ıtnuta.
Dalˇs´ım zvaˇzovan´ym algoritmem bylo velmi rozˇs´ıˇren´e shlukov´an´ı pomoc´ı k-means[5], kter´e lze popsat n´asledovnˇe
1. V obrazu je vybr´ano (v nejprimitivnˇejˇs´ı verzi n´ahodnˇe) k bod˚u - cen-troid˚u
2. Kaˇzd´y bod obrazu je pˇriˇrazen ke sv´emu nejbliˇzˇs´ımu stˇredu (nejbliˇzˇs´ımu ve smyslu zvolen´e metriky, ˇcasto pouˇz´ıvanou je euklidovsk´a vzd´alenost) 3. Pro kaˇzd´y takto vznikl´y shluk je pr˚umˇerov´an´ım vypoˇcten nov´y centroid
a shlukov´an´ı zaˇc´ına od 1. kroku
K-means iteruje dokud nedojde ke zmˇenˇe ˇz´adn´eho shluku (ide´aln´ı pˇr´ıpad) nebo dokud nen´ı pˇrekroˇcen poˇcet pˇredem dan´ych iterac´ı. ´Uskal´ım t´eto metody je volba parametru k, kter´y ud´av´a celkov´y poˇcet shluk˚u. Existuj´ı sice metody na automatick´e zjiˇstˇen´ık (napˇr´ıklad pomoc´ı detekce hran [13] nebo porovn´an´ım segment˚u pro r˚uzn´a k[14]), zav´adˇej´ı ovˇsem dalˇs´ı vrstvu komplexity do cel´eho algoritmu. Nav´ıc k-means velmi ˇcasto konverguj´ı k lok´aln´ımu optimu, ˇc´ımˇz doch´az´ı ke ztr´atˇe poˇctu segment˚u a nepˇresnostem v segmentaci.
Nakonec byl zvolen algoritmus zdol´av´an´ı kopc˚u (Hill-Climbing), kter´y dos´ahne segmentace hled´an´ım lok´aln´ıch maxim v trojrozmˇern´em histogramu[15].
3.2.2 Barevn´ y model HSV
Dobr´y barevn´y model pro segmentaci obrazu by mˇel splˇnovat vlastnost, ˇze vn´ıman´a rozd´ılnost barev odpov´ıd´a jejich euklidovsk´e vzd´alenosti v tomto modelu. HSV barevn´y model tuto vlastnost splˇnuje a nav´ıc velmi dobˇre od-pov´ıd´a lidsk´emu vn´ım´an´ı barev[15]. Barevn´y model HSV je podobnˇe jako RGB tˇr´ısloˇzkov´y - H (hue) je odst´ın barvy, S (satruation) sytost barvy a V (value) pˇredstavuje jas v porovn´an´ı s b´ılou barvou.
Obr. 9Barevn´y model HSV
Na Obr.9[15] je barevn´y HSV model zn´azornˇen´y - H jako hodnota na barevn´em kotouˇci, S urˇcuje pozici na kotouˇci od stˇredu a V je pozice barevn´eho kotouˇce na ose ˇcern´a-b´ıl´a.
RGB hodnoty se na HSV pˇrevedou podle n´asledn´ych vztah˚u[16]
R0 = R
255, G0 = G
255, B0 = B 255 Cmax = max{R0, G0, B0}
Cmin = min{R0, G0, B0} 4=Cmax−Cmin
H =
3.2.3 Algoritmus zdol´ av´ an´ı kopc˚ u (Hill-Climbing)
Vstupem zvolen´eho segmentaˇcn´ıho algortimu[15] je pole s RGB hodnotami pixel˚u zpracov´avan´eho obrazu, kde poˇrad´ı v poli odpov´ıd´a um´ıstˇen´ı pixelu v obraze (viz. Obr.10). V´ystupem je pole clusters stejn´e velikosti jako vstup, kter´e obsahuje rozˇrazen´ı pixel˚u do segment˚u -clusters(i) =j znamen´a, ˇzei-t´y pixel n´aleˇz´ıj-t´emu shluku.
0 1 2 3
4 5 6 7
8 9 10 11
Obr. 10 Zn´azornˇen´ı indexace pixel˚u (obr´azek o rozmˇerech 4x3)
RGB hodnoty jsou pˇrevedeny do HSV a upraveny tak, aby nejmenˇs´ı hodnota kaˇzd´e sloˇzky byla 0 a nejvˇetˇs´ı hodnota kaˇzd´e sloˇzky 1 (tedy nafitov´an´ı do inter-valu h0,1i) a pot´e je pomoc´ı Hill-Climbing algoritmu proveden´a segmentace.
Jednorozmˇern´y Hill-Climbing algoritmus pro H sloˇzku vypad´a n´asledovnˇe.
1. Vytvoˇren´ı jednorozmˇern´eho barevn´eho histogramu.
2. Zdol´av´an´ı kopce - zaˇc´ın´a se na libovoln´em nenulov´em binu (tj. datov´em intervalu) a podle n´asleduj´ıc´ıch pravidel, se hled´a vrchol (kopec), tj.
lok´aln´ı maximum v histogramu
(a) Porovn´an´ı poˇctu pixel˚u aktu´aln´ıho binu s jeho lev´ym a prav´ym sou-sedem. Je d˚uleˇzit´e si uvˇedomit, ˇze H sloˇzka je hodnota na barevn´em kotouˇci (Obr.6) a tedy lev´y krajn´ı bin soused´ı s prav´ym krajn´ım bi-nem.
(b) Pokud maj´ı sousedn´ı biny rozd´ıln´y poˇcet pixel˚u, dojde k pˇresunu vzh˚uru k binu s vˇetˇs´ım poˇctem pixel˚u.
(c) Pokud maj´ı sousedn´ı biny stejn´y poˇcet pixel˚u, dojde k posouv´an´ı na dalˇs´ı sousedy, dokud nejsou nalezeny biny s rozd´ıln´ym poˇctem pixel˚u. Pˇresun vzh˚uru je proveden na bin s vˇetˇs´ım poˇctem pixel˚u.
(d) Postup 2(a)-2(c) je opakov´an, dokud nedojde k nalezen´ı binu, z kter´eho jiˇz ˇz´adn´ym zp˚usobem nen´ı moˇzn´y pohyb vzh˚uru, tj. sousedn´ı biny obsahuj´ı menˇs´ı poˇcet pixel˚u. Tento bin je indentifikov´an jako peak (vrchol ˇci kopec), jedn´a se o lok´aln´ı maximum v histogramu 3. Je zvolen dalˇs´ı libovoln´y nenulov´y, avˇsak dosud nezpracovan´y, bin a je
zopakov´an krok ˇc´ıslo 2. Tento krok se opakuje, dokud nejsou zpracov´any vˇsechny biny histogramu.
4. Identifikovan´a lok´aln´ı maxima pˇredstavuj´ı poˇcet shluk˚u v obraze (pozn.
tato metoda by tedy mohla b´yt jednou z dalˇs´ıch moˇznost´ı automatizace segmentace pomoc´ı k-means shlukov´an´ı)
5. Jednotliv´e biny jsou pˇriˇrazeny k tomu lok´aln´ımu maximu, ke kter´emu se doˇslo v kroce 2; t´ımto je segmentace hotova.
Obr.11[15] zn´azorˇnuje pr˚ubˇeh algoritmu - (a) hled´an´ı vrchol˚u (peak˚u), (b) pˇriˇrazov´an´ı bin˚u k vrchol˚um.
Zobecnˇen´ı tohoto postupu do tˇr´ı rozmˇer˚u (tedy pro vˇsechny tˇri sloˇzky HSV) je pˇr´ımoˇcar´e. V 1. kroce je vytvoˇren trojrozmˇern´y histogram m´ısto jedno-rozmˇern´eho a ve 2. kroce se pouze liˇs´ı poˇcet sousedn´ıch bin˚u, se kter´ymi se porovn´av´a poˇcet jejich pixel˚u. Ve tˇrech rozmˇerech m´a obecnˇe kaˇzd´y bin m´ısto dvou dvacet ˇsest soused˚u (neplat´ı pro krajn´ı biny histogramu); d´ale je tˇreba si uvˇedomit, ˇze zat´ımco mezn´ı biny H komponenty spolu soused´ı, pro S a V sloˇzku toto neplat´ı. Nav´ıc je tˇreba zav´est n´asleduj´ıc´ı podm´ınku - pokud je hodnota S pˇr´ıliˇs mal´a (pˇribliˇznˇe 0.1), porovn´avaj´ı se pouze sousedn´ı biny ve smˇeru V sloˇzky. Kdyˇz jsou hodnoty S pˇr´ıliˇs mal´e, lidsk´e oko nedok´aˇze rozeznat zmˇenu barvy pˇri zmˇenˇe hodnoty V.
(a) (b) Obr. 11 Hill-Climbing algoritmus
Jedin´ymi parametry tohoto algoritmu je poˇcet jednotliv´ych bin˚u histogramu.
Pravidlem je, ˇze H sloˇzka je kvantizov´ana do v´ıce ´urovn´ı neˇz zbyl´e dvˇe sloˇzky tak, aby reflektovala r˚uznorodost barev. Doporuˇcen´y pomˇeru bin˚u H:S:V je 16:8:8[15], pˇri tomto rozloˇzen´ı ovˇsem doch´az´ı u vˇetˇs´ıch obrazu k ˇc´asteˇcn´emu pˇresegmentov´an´ı a zvolen byl proto nakonec pomˇer 15:7:7.
Pro kaˇzd´y bin histogramu je prozkoum´ano vˇsech jeho 26 soused˚u a kaˇzd´y pi-xel obrazu mus´ı b´yt pˇriˇrazen k jednomu z lok´aln´ıch maxim v histogramu (tzn.
k segmentu). Pˇri poˇctu bin˚u Ni a celkov´em poˇctu pixel˚u Np je tedy ˇcasov´a sloˇzitost Hill-climbing segmentaceO(26Ni+Np).