Regionální segmentace a shlukování

Regionální segmentace a shlukování Po íta ové vid ní

Ilona Kalová Skupina po íta ového vid ní Ústav automatizace a m icí techniky Fakulta elektrotechniky a komunika ních technologií Vysoké u ení technické v Brn

Regionální segmentace a shlukování – p ednáška

Tematické rozd lení p ednášky: 1. 2. 3. 4. 5. 6. 7.

Segmentace – úvod. Metody orientované na regiony. Znalostní metody. Hybridní metody. Segmentace – barevná hloubka obrazu. Segmentace textur. Vypl ování oblastí, indexace oblastí.

Segmentace - úvod



Segmenta ní metody

Segmentace prahováním - prosté - s více prahy - áste né / poloprahování - adaptivní / lokální prahování Metody vycházející z detekce hran (edge-based) - prahování obrazu hran - sledování hranice - heuristické sledování hranice - ur ování hranice s využitím znalosti o její poloze - aktivní kontury - level-set - houghova transformace

Hybridní metody - neuronové sít - morfologické operace - amplitudová projekce - … Znalostní metody (knowledge-based) - srovnáním se vzorem Metody orientované na regiony (region-based) - spojování oblastí - št pení oblastí - št pení a spojování - watershed - shluková analýza (Mean-shift, K-means)

Metody orientované na regiony



Metody orientované na regiony Snaha o roz len ní obrázku do maximálních souvislých homogenních oblastí (z hlediska zvoleného parametru)

• kritérium homogenity – jasové vlastnosti, textura, barva, model obrazu, …

Nemusí dávat stejné výsledky jako metody založené na detekci hran; kombinace metod Vhodné pro obrazy se šumem, kde se hranice ur ují obtížn Metody: - spojování oblastí - št pení oblastí - št pení a spojování - watershed - shluková analýza (Mean-shift,K-means)

Spojování oblastí Nar stání oblastí spojováním malých homogenních oblastí Pro oblasti požadujeme spln ní t chto podmínek: 1. H(Ri) = TRUE pro i = 1, 2, … I 2. H(Ri U Rj) = FALSE pro i,j 1, 2, … I; i j; Ri sousedí s Rj kde I …po et oblastí, Ri … jednotlivé oblasti H(Ri) … dvouhodnotové vyjád ení kritéria homogenity

oblasti musí být (1) homogenní a (2) maximální

Algoritmus: 1. Definuj po áte ní rozd lení obrazu do velkého množství malých oblastí (nejlépe jen bod). 2. Definuj kriterium spojování dvou sousedních oblastí. 3. Spojuj sousední oblasti vyhovující kritériu. Pokud již nelze spojit žádné dv oblasti bez porušení kritéria, skon i.

R zné výsledky pro r zné: - definice po áte ních oblastí - kritéria - po átky spojování - po adí p edkládaných oblastí

P íklad: Kritérium: Pokud rozdíl st edních jas dvou sousedních oblastí je menší než 5, tak tyto oblasti spoj.

Št pení oblastí, Št pení a spojování Št pení oblastí

• principieln opa ný p ístup než spojování • na za átku je jediná oblast (celý obraz) a ten se pak d lí dokud podoblasti nespl ují kritérium • št pení a spojování mohou dávat r zné výsledky

Št pení a spojování

• využívá pyramidální reprezentaci obrazu – št pení a spojování je realizováno v rámci tvercových oblastí pyramidální datové struktury • je-li oblast v dané úrovni pyramidy nehomogenní -> oblast je rozd lena na ty i podoblasti • jsou-li oblasti navzájem homogenní -> dojde ke spojení do jedné

originál

št pení

št pení a spojování

Watershed watershed = rozvodí, povodí i vodní p ed l

• segmenta ní metoda vycházející z geografie - obraz je chápán jako terén nebo topografický reliéf – jas vstupního obrázku ur uje výšku terénu ( erná nejníže, bílá nejvýše) • princip je založen na postupném zaplavování terénu vodou – stoupání hladiny • výsledkem je obraz rozd lený do region - jednotlivých povodí odd lených hrázemi, všechny body daného povodí jsou ozna eny stejným unikátním indexem • varianta s uživatelskou inicializací • pro obrazy obsahující šum vytvá í p íliš mnoho oblastí. Lze eliminovat: - vhodnou p edp ípravou obrázku - povolením hráze až ur ité prahové výšky - regiony pat ící do stejné oblasti lze pozd ji spojit jinými metodami

Algoritmus: 1. Nalezni nejnižší body (lokální minima obrazu). 2. Za ni zapl ovat povodí vodou z t chto po áte ních bod – hladina stoupá. - v místech, kde by se voda ze dvou r zných povodí mohla slít, vytvo hráze 3. Ve chvíli dosažení nejvyššího bodu terénu (maxima obrazu) skon i.

p evzato z http://cmm.ensmp.fr/~beucher/wtshed.html

Shluková analýza Shluková analýza = obecná statistická klasifika ní metoda Zpracování obrazu -> shlukování pixel podobných vlastností

• každý pixel nebo ást obrazu je reprezentována vektorem vlastností x = [x1, x2, …, xN], což mohou být nap . barevné komponenty pixelu/ , vlastnosti okolí, pozice atd. (nutná je normalizace jednotlivých vlastností) • je nutné vybrat takové vlastnosti, které mají pixely z jedné oblasti podobné a z r zných oblastí rozdílné = m ly by v N-rozm rném prostoru vznikat shluky

• úlohou segmentace je automaticky ur it polohu shluk (n kdy i jejich po et) a p i adit jednotlivým vzork m nejbližší shluk • metoda u ení bez u itele, iterativní postup • shluková analýza vychází z podobnosti, resp. vzdálenosti vzork . Její kvantitativní vyjád ení je jedním ze základních problém shlukové analýzy. Vzdálenost dvou objekt r a s (charakterizovanými N vlastnostmi) je možné ur it nap .: d (r , s )

N k

k

xri

xsi

í 1

k = 1 vzdálenost v m stských blocích (Manhattan) k = 2 Euklidovská vzdálenost

d (r , s) max xri

xsi

ebyševova vzdálenost

Mean-shift Mean-shift segmentace shlukuje body obrazu na základ podobnosti jejich vzhledu a blízkosti jejich pozic pomocí konvergence do lokálních maxim spojeného sou adnicového a intenzitního prostoru Nap .: xi = [x, y, f(x,y)], xi = [x, y, r(x,y), g(x,y), b(x,y)] Algoritmus: Vstup: množina vzork (bod v N-rozm rném prostoru) 1. Definuj velikost a tvar okna 2. Pro všechny vzorky: a) Vypo ti lokální maximum hustoty vzork uvnit okna kolem aktuálního vzorku (mean pozice) b) Posu (shift) pozici vzorku do maxima c) Opakuj dokud se m ní pozice maxima d) Zapamatuj si poslední pozici 3. Shlukujeme ty vzorky, které dokonvergovaly do stejného maxima (s ur itou tolerancí). Oblasti, z které vzorky konvergují do stejného bodu, íkáme basin of attraction.

Mean-shift obloha

tráva silnice

jas

x

originální obrázek segmenty barvou centra shluku obrázek index

y

K-means K-means algoritmus iterativn hledá hodnoty vektor j (st edy shluk ) tak, že minimalizuje st ední odchylku mezi zadanou množinou dat a vektory, které mají k t mto dat m nejmenší euklidovskou vzdálenost a rozd luje je do p edem daného po tu shluk (t íd) K: C1, C2,…Ck. Algoritmus: Vstup: množina dat x1, x2, … xl a íslo K udávající po et shluk , tedy vektor 1. Inicializace vektor informace)

j:

j,

j = 1, … k

bu na náhodn zvolené hodnoty nebo s využitím n jaké vhodné heuristiky (nap . apriorní

2. Iterativní opakování krok dokud se alespo jeden vektor xi klasifikuje do jiné t ídy než byl klasifikován v p edcházejícím kroku: a) Klasifikace: Všechna data xi se klasifikují do t íd ur ených vektory j podle minima euklidovské vzdálenosti. Tedy vzor xi je p i azen do t ídy yi, podle: yi arg min xi u j j

b) P epo ítání vektor j : Vypo ítají se nové hodnoty vektor j jako st ední hodnota dat xi, které byly klasifikovány do t ídy ur ené p íslušným vektorem j. Tedy nová hodnota j se ur í jako: 1 l xi , j kde lj je po et vzor xi klasifikovaných v p edchozím l j i 1, yi j kroku do t ídy ur ené vektorem j

Voroného diagram

Shluková analýza

P .: Lokalizace SPZ – ve snímcích po p edzpracování (hranové filtry, zten ování,…) se SPZ hledá jako skupina svislých ar (ur ité délky, s podobnými sou adnicemi,..)

Znalostní metody



Znalostní metody Pat í sem všechny metody využívající d íve získané znalosti o objektech Vyhledávání známých objekt nebo jen nap . vzor , textury, model , geometrických útvar atd. v obrazu pomocí srovnání se vzorem = tamplate matching

• nikdy nem žeme o ekávat absolutní shodu – šum, zkreslení atd. => hledáme jen maximum vhodného kritéria • a to pro všechny možné transformace obrazu (nato ení, zm na m ítka, zkreslení,…) • vhodné i pro stereoskopické snímky nebo sledování relativního pohybu – z jednoho snímku se vyjme p edloha a v ostatních se pátrá po stejném objektu

Metody: • srovnání region , ale možné i srovnávat pouze kontury • hledání shody ástí obrazu jen s jednotlivými ástmi vzoru • srovnávání model objekt (modely definovány vlastnostmi jako nap . st ední jas, velikost, momenty nebo jiné radiometrické i fotometrické p íznaky) • srovnání graf vytvo ených podle vlastností sledovaných objekt P íklady míry souhlasu (hodnotícího kritéria): C1 (u, v )

1 max f (i u , j v ) h(i, j )

C2 (u , v)

1 f (i u, j v) h(i, j )

f … zpracovávaný obraz h … hledaný vzor F, H … Fourierovy obrazy V … množina všech obrazových element vzoru

(i , j ) V

1 f (i u, j v) h(i, j )

C3 (u , v)

2

(i , j ) V

C4 … F • H a následná zp tná transformace

Srovnání se vzorem – vzájemná korelace

vzájemná korelace se vzorem v základní pozici

sou et korelací od ty pozic + práh

vzor + rotace originální snímek

ode tené pozadí + ekvalizace + prahování

výsledek s ozna enými indexy

Active Appearance Models (AAM) AAM využívá statisticky vytvo ený model objekt z manuáln segmentovaných trénovacích dat. Parametry získaného modelu je možné p izp sobit jakémukoliv novému obrazu a ov it tak p ítomnost objektu v obraze • model je generován jako kombinace modelu variací tvaru objektu a modelu variací textury (intenzity pixel ) • k vytvo ení modelu je t eba trénovací sada anotovaných obraz , kde jsou vždy ozna eny odpovídající si hrani ní body (landmark points) • v pr b hu trénovaní je zaznamenán vzájemný vztah mezi zm nou polohy hrani ních bod a zm nou intenzity pixel v dané množin vzor • vytvo ení modelu pomocí statistické metody zpracování dat - PCA (Principal Component Analysis) analýza • tímto zp sobem natrénovaný model umož uje velice rychlé porovnání modelu s objekty v novém obraze

Výhody • rychlé porovnání / prohledávání obrazu • rychlá adaptace modelu na nový obraz

Nevýhody • nutná rozsáhlá a reprezentativní galerie trénovacích vzor • náro ná ru ní anotace vzor • metoda vyžaduje pom rn p esnou po áte ní inicializaci (odhad polohy objektu v testovaném obraze)

Active Appearance Models (AAM)

anotované snímky ruky s 56 hrani ními body

nezarovnané anotace ze 40 snímk

Anotace snímk : 1. Zvolit významné body objektu 2. Najít a ozna it tyto body na všech snímcích 3. Zarovnat všechny obrázky - translace, rotace, m ítko (nap . Procrustes analysis, tangenciální projekce) 4. Ur it variace polohy všech bod a variance intenzit 5. Korela ní matice bod – body se pohybují závisle (nap . PCA - principal component analysis)

zarovnané anotace se zvýrazn ným „st edním tvarem“

nazna ení vzájemného pohybu bod

nezávislá PCA analýza pro každý hrani ní bod

Active Appearance Models (AAM)

segmentace záp stních k stek:

segmentace obli eje: inicializace

model tvaru

model intenzit

po první iteraci

kombinovaný model

po druhé iteraci

prohledávání

convergence

p evzato z: http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=403

Hybridní metody



Hybridní metody Metody primárn ur ené k jiným ú el m Kombinace r zných p ístup Úprava obrazu p ed nebo po nasazení jiné segmenta ní techniky Neuronové sít • obecn nástroj pro klasifikaci, simulaci, zpracování informací atd. • paralelní distribuovaný systém jednoduchých výkonných prvk uspo ádán ú eln tak, aby byl schopen požadovaného zpracování informací

Morfologické operace • vhodné p edevším jako úprava/zjednodušení binárního obrazu (nap . po prahování), nap .: - spojení blízkých segment , vypln ní d r atd. (dilatace nebo uzav ení) - rozložení složitého objektu na n kolik jednodušších (eroze) - náhrada složitého objektu jeho skeletem; zten ování - odstran ní objekt dle velikosti

Amplitudová projekce • technika, kterou je možné použít pro separovaní obrazových dat

Segmentace na základ pohybu

Neuronové sít Snaží se zjednodušit problém, kdy tradi ní segmenta ní techniky založené na strukturních vlastnostech obrazu asto vyžadují odborné znalosti a zkušenosti, které musí zadávat uživatel – trénování neuronových sítí probíhá principem u ení z p íklad • NN jsou rozsáhlé paralelní sít obsahující jednoduché výpo etní elementy (neurony), které simulují schopnost živých organism u it se. Každý neuron je schopen provád t pouze jednoduché výpo ty • u ení se d je adaptací vah na propojích mezi jednotlivými neurony (znalosti se ukládají do vazeb)

Významné rysy NN:

• u ení se z p íklad a zobec ování znalostí • potla ení šumu • odolnost v i defekt m a poruchám ve vstupních datech

Použití:

• klasifikace – pomocí trénovacích obraz jsou nastaveny váhy v síti. Sí je pak schopna segmentovat neznámé obrazy nebo klasifikovat segmentované obrazy do t íd • shlukování • deforma ní modely

Dva p ístupy:

- hledáme charakteristické vlastnosti vstupních dat (obvykle p íznakové vektory) a klasifikujeme je do t íd bez jakékoliv další interpretace - u ení bez u itele (podobné shlukové analýze) - trénování s u itelem vyžaduje ru n segmentovaná trénovací data. Vstupem u ícího algoritmu jsou nejen p íznakové vektory, ale i funkce, která každému vstupnímu vektoru p i azuje ur itý segment obrazu.

Neuronové sít – Kohonenova mapa Samoorganizující se sí = u ení bez u itele, princip podobný shlukování

• využívá se sout žní strategie u ení = neurony ve výstupní vrstv spolu sout ží o to, který bude aktivní (do které t ídy bude vstup za azen) • sí je dvouvrstvá, každý neuron výstupní vrstvy je spojen se všemi neurony vstupní vrstvy • po et vstup je dán po tem m ených vlastností pixelu nebo oblastí (jas, pozice, vlastnosti okolí atd.) • po et výstup ur uje po et o ekávaných shluk – segment obrazu (problém s jejich vhodným ur ením) Proces u ení: 1. inicializace vah (nap . náhodn nebo rovnom rn ), p ípadn parametru u ení (t), velikosti okolí (t) 2. p edložení vzoru x(t) = [x0(t), x1 (t), … xn(t)] a. výpo et vzdálenosti vzoru pro všechny výstupní neurony, nap . euklidovskánvzdálenost: 2 dj

xi (t ) wij (t )

í 0

b. výb r nejbližšího (nejpodobn jšího) neuronu = vít zný neuron dj* = min(dj) c. úprava vah nejpodobn jšího neuronu (p ípadn i okolních), ostatní váhy z stávají stejné wij (t 1) wij (t ) (t ) xi (t ) wij (t ) d. je možné upravit i další parametry – parametr u ení i velikost okolí 3. krok 2. opakujeme pro všechny vzory nebo do dosažení pot ebné p esnosti Proces segmentace: 1. pro celý obrázek a. p edložení nového vzoru x(t) b. výpo et vzdáleností a ur ení nejbližšího neuronu = p i azení indexu daného vít zného segmentu

Amplitudová projekce není p ímo segmenta ní technikou, spíše “lokaliza ní”

obrazové segmenty mohou být n kdy vhodn separovatelné vytvo ením projekce ve sm ru ádk a sloupc = X Y vertikální a horizontální projekce V ( y)

f ( x, y ),

x 1

H ( x)

f ( x, y )

y 1

Segmentace – barevná hloubka obrazu



Segmentace – barevná hloubka obrazu Binární

• výhodou je snadn jší vyhodnocení • nevýhodou je nižší p esnost, ztráta podstatných informací

Šedotónový

• nej ast ji 256 úrovní jasu • náro n jší a delší výpo ty; dosahuje se vyšší p esnosti • asto se pracuje s kombinací binární+šedotónový – šedotónový se p evede na binární, kde se „hrub “ nalezne tvar a v p vodním obrazu se provede up esn ní

Barevný

• nej ast ji 3 složky ve 256 úrovních jasu • ada možností pro další zp esn ní • kvalitn jší segmentace hlavn pokud máme apriorní znalosti o barv objektu • Možné postupy: • p evést na šedotónový obraz • vybrat pouze nejvýznamn jší barevnou složku a s ní pracovat (šedotónový obraz) • rozd lit na jednotlivé složky a každou složku zpracovávat zvláš • komplexní ešení ve všech složkách • p evést na jiný výhodn jší barevný model (RGB, HSV, YCbCr, …), kde vyniknou požadované informace

Barevná segmentace – p íklad segmentace barvy k že

RGB

HSV

YCbCr

Barevná segmentace – p íklad segmentace barvy k že

databáze obraz k že

histogram výskytu pixel

CbCr

histogram aproximovaný gaussovou k ivkou

p íklady – originální snímek (vlevo), detekovaná k že (uprost ed), naprahovaný obraz (vpravo)

Transformace barev – omezení barevného prostoru Barevný

šedotónový

z hlediska dalšího zpracování obrazu

• m žeme každé složce barevného obrazu p i adit stejnou váhu Iz

0, 33R 0, 33G 0, 33B

• m žeme pracovat pouze s jednou dominantní složkou • p evod do jiného barevného modelu

z hlediska vnímání obrazu lov kem

• využívá se r zné citlivosti oka na r zné složky Io

Io

0,299 R

0,587G

0,114 B

Iz

Transformace barev – omezení barevného prostoru Šedotónový

binární

z hlediska dalšího zpracování obrazu

• prahování – zvolení vhodného prahu vzhledem ke snímané scén • prahování aplikujeme bu na plochy nebo hrany – bu p ímo na p vodní obraz nebo na nahranovaný (hranové filtry)


• využívá se schopnosti oka skládat barvy – pr m rovat => rozptylování a) náhodné rozptýlení Algoritmus: Cyklus p es všechny sou adnice obrazu x,y: Pokud Cin > random(0:255), tak Cout = 1, jinak Cout = 0

Transformace barev – omezení barevného prostoru Šedotónový

binární


• využívá se schopnosti oka skládat barvy – pr m rovat => rozptylování

b.2) zachování velikosti obrazu • místo p vodního pixelu vložíme jen odpovídající hodnotu masky Algoritmus: Cyklus p es všechny sou adnice obrazu x,y: Pokud Cin > M[(X mod XmaskSize),(Y mod YmaskSize)], tak Cout = 1, jinak Cout = 0

b) pravidelné (maticové) rozptýlení • p edem vytvo ené vzory erných a bílých bod , které budou zastupovat jednotlivé odstíny v originálním obrazu b.1) zv tšení obrazu • místo p vodního pixelu vložíme celou vybranou masku P .: Cin = (0-50> 0 0 0 0

(50-100> (100-150> (150-200> (200-256) 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 M display

c) distribuce zaokrouhlovací chyby • algoritmus Floyd-Steinberg, Burkes, Stucki

0 12 3 15 8 4 11 7 2 14 1 13 10 6 9 5

M tisk

1 5 9 2 8 12 13 6 4 15 14 10 0 11 7 3

Segmentace textur



Segmentace textur Textura • opakující se struktura (tonální variace) • nefigurativní • má vlastní a nevlastní složku (nevlastní – nerovnost povrchu, osv tlení) • má výrazné statistické vlastnosti • m že se vyskytovat ve více úrovních rozlišení

Segmentace textur Prahování • tón a kontrast textury (z histigramu ) – statistika 1. ádu => nepostihuje prostorovou strukturu

Metody vycházející z detekce hran • prostorové vlastnosti textur – hustota hran, sm r hran • kombinace s jinými metodami (nap . znalostní – porovnání obraz hran) • u jednoduchých textur nap . typu šrafování m že být využita houghova transformace

Metody orientované na regiony • spojování oblastí – definice kriteria homogenity z vlastností textury • shluková analýza – textura popsána vektorem jejich vlastností

Znalostní metody • vzorek textury, se kterým je prohledáván (korelován) obraz

Hybridní metody • neuronové sít – textura popsána vektorem jejich vlastností

Segmentace textur Popis vlastností textury: • • • • • • • • • • • •

tón a kontrast textury (z histigramu ) – statistika 1. ádu, nepostihuje prostorovou strukturu velikost primitiva a periodicita - autokorela ní funkce energie spektra – charakteristické frekvence a sm rovost spektra energie ve fourierov roviny waveletová analýza gáborova analýza – obraz je filtrován bankou filtr , které jsou popsány Gáborovou funkcí spektrum vzoru – aplikace morfologických operací pro m ení zrnitosti textury histogram kookurence (jak asto se v textu e vyskytuje stejná konfigurace pixel vzdálených o vektor (p,q) nebo ur ené polom rem r) lokální momenty obrazové funkce histogram LBP (local binary pattern) – pro každý bod obrazu je pomocí prahování a váhování bod v jeho okolí vytvo en LBP kód, texturním p íznakem je pak histogram LBP kód všech bod haarovy p íznaky – extrahují informace o lokální frekvenci, jednoduchá šablona, mnoho kombinací haralickovy texturní p íznaky – energie, entropie, kontrast, homogenita, korelace, … …

primitiva LBP

p íklady haarových p íznak

p íklady jader vygenerovaných pomocí gáborovské funkce

energie spektra

p evzato z: http://www.fit.vutbr.cz/study/courses/IKR/public/prednasky/04_obrazove_priznaky/IKR4.pdf

Segmentace textur P íklad: metod a k-means

• p íznakový vektor zkonstruován z gradientu - vektory jsou dvojdimenzionální, jednotlivé složky jsou obrazové derivace ve sm ru ádk a sloupc • dv textury = dva shluky

P íklad: LBP p íznaky

p evzato z: http://cmp.felk.cvut.cz/cmp/courses/DZO/Lab05/lab05.html

• texturním p íznakem není hodnota LBP jednotlivých pixel , ale histogram hodnot lokálního okolí • segmentace – porovnáním histogram textur

p evzato z: http://www.fit.vutbr.cz/study/courses/IKR/public/prednasky/04_obrazove_priznaky/IKR4.pdf

Vypl ování oblastí, indexace oblastí



Vypl ování oblastí Definice oblasti souvisí s popisem její hranice a) geometricky ur ená hranice • posloupnost bod definující mnohoúhelník • Metody: - ádkové vypl ování b) hranice nakreslená v rastru • hranice není jasn definována, všechny informace o oblasti se získávají pouze z obrazu (z obrazové = rastrové pam ti)

- hrani ní vypl ování = bod je vnit ní, pokud má jinou barvu než hranice - záplavové vypl ování (lavinové, p ebarvování) = bod je vnit ní, pokud má stejnou barvu jako semínko - m kké vypl ování = bod je vnit ní, pokud má výrazn jinou barvu než hranice (hranice byla vyhlazena a má nestejnou barvu)

• Metody: - semínkové vypl ování

- jednoduché / ádkové - rekurzivní / se zásobníkem

- indexace oblastí - barvení

Vypl ování geometricky ur ené hranice ádkové vypl ování • každým ádkem je vedená pomyslná ára a jsou hledány její pr se íky s hranicí oblasti • nalezené pr se íky se se adí podle sou adnic x – dvojice pr se ík ur uje úse ky ležící uvnit oblasti

• problémy s vrcholy a vodorovnými hranicemi, proto vhodn jší modifikace algoritmu

Vypl ování geometricky ur ené hranice 1a.

1b.

2a.

2b.+c.

3.

1c.

Algoritmus: 1. Pro všechny hrani ní úse ky ov : a. je-li vodorovná, tak ji vynechej b. uprav orientaci shora dol c. zkra hranice zdola o jeden pixel d. ur i mezní sou adnice celé hranice ymax a ymin 2. Pro všechna y od ymin do ymax prove : a. nalezni pr se íky hrani ních úse ek s ádkem y b. uspo ádej všechny pr se íky podle sou adnice x c. vykresli úseky mezi lichými a sudými pr se íky 3. Vykresli hranici oblasti

Vypl ování hranice nakreslené v rastru Semínkové vypl ování • základem je semínko – libovolný vnit ní bod (ur í uživatel nebo dané znalostmi o oblasti) • od semínka se postupn rozši uje prohledávání obrazové pam ti a nalezeným vnit ním bod m je p i azena nová barva • 4-spojitá X 8-spojitá oblast • 4-spojitá X 8-spojitá hranice

a) Jednoduché semínkové vypl ování • rekurzivní algoritmus – ší ení semínka do všech stran • => prakticky nepoužitelné – každý pixel je testován n kolikrát, mnohonásobné zano ení rekurze - možné ešit pomocí zásobníku

Algoritmus – rekurze, ty okolí: Seminko(x,y) Je-li bod [x,y] vnit ní, pak: 1. obarvi bod [x,y] požadovanou barvou 2. prove Seminko(x+1,y) 3. prove Seminko(x-1,y) 4. prove Seminko(x,y+1) 5. prove Seminko(x,y-1)

Vypl ování hranice nakreslené v rastru b) ádkové semínkové vypl ování • vyhledávání sousedních bod je provád no v jednom ádku pixel (úsek), pouze bezprost edn nad ním a pod ním má smysl hledat nová semínka Algoritmus - zásobník: 1. Vlož první semínko do zásobníku 2. Dokud není zásobník prázdný, opakuj: a. vyjmi semínko se sou adnicemi [x,y] ze zásobníku b. nalezni hranici xL a xR na ádku y v nejbližším okolí bodu [x,y] c. nakresli úse ku [xL,y],[y,xR] d. na vyšší úse ce [xL,y-1], [xR,y-1] hledej souvislé nevypln né vnit ní úseky a pro každý z nich vlož do zásobníku sou adnici jednoho vnit ního bodu e. na nižší úse ce [xL,y+1], [xR,y+1] hledej souvislé nevypln né vnit ní úseky a pro každý z nich vlož do zásobníku sou adnici jednoho vnit ního bodu

Indexace oblastí - barvení Obvyklá metoda - 1 až N barev • každou samostatnou souvislou oblast opat íme neopakujícím se p irozeným íslem – pozadí má íslo 0, oblastem jsou p i azena ísla postupn od jedni ky. Nejv tší identifika ní íslo oblasti tedy udává po et oblastí v obraze.

Jiná možnost - 4 barvy • použijeme menší po et identifika ních ísel - pouze zajistíme, aby žádné dv sousední oblasti nem ly stejné identifika ní íslo. Teoreticky sta í ty i barvy (resp. ísla). Pro identifikaci oblastí je pak t eba mít pro každou oblast uloženou informaci o poloze n kterého jejího bodu. Algoritmus – 1 až N barev: 1. procházíme obraz po ádcích a každému nenulovému obrazovému elementu p i adíme hodnotu podle hodnoty všech jeho již obarvených soused - jsou-li všechny nulové, p i adíme bodu dosud nep id lenou barvu - pokud je jeden nenulový, nebo je více nenulových, ale se stejnou barvou, p i adíme bodu tuto jeho/jejich barvu - pokud je více nenulových s r znou barvou, p i adíme bodu jednu z t chto barev a zaznamenáme barvy do tzv. tabulky ekvivalence barev (došlo k tzv. kolizi barev)

sledované pixely pro 4-okolí a pro 8-okolí

kolize barev (4-okolí) p íklady objekt , kdy dojde ke kolizi

Indexace oblastí - barvení Algoritmus – 1 až N barev: 2. projdeme znovu celý obraz po ádcích a p ebarvíme obrazové body kolizních barev podle tabulky ekvivalence barev P .: kolize barev 7 a 9 = všechny pixely s barvou 9 p ebarvíme na 7 (po et oblastí bude od zjišt ného ísla po prvním pr chodu o jednu nižší). Chceme-li aby žádná barva nebyla vynechána (barva 9), musíme zbytek oblastí p e íslovat (p ebarvit).

Barvení: - p vodní obraz - naprahovaný obraz - první pr chod - druhý pr chod

Zdroje - literatura Segmentace: Hlavá , V., Šonka, M.: Po íta ové vid ní, Grada Praha, 1992, ISBN 80-85424-67-3. http://www.fit.vutbr.cz/~spanel/segmentace/ Watershed: http://cmm.ensmp.fr/~beucher/wtshed.html http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/KIM1/Seminars/Watershed/index.htm Beucher S.: Image Segmentation and Mathematical Morphology. Center of Mathematical Morphology home page, 2000. Shluková analýza, Mean-shift: Kelbel, J., Šilhán, D. Shlukova analyza http://staff.utia.cas.cz/nagy/skola/Projekty/Classification/ShlukovaAnalyza.pdf Doubek, P. Mean-Shift segmentace http://cmp.felk.cvut.cz/cmp/courses/ZS1/Cviceni/cv4/meanshift.pdf Active Appearance Models: Cootes, T.F., Edwards, G.J., Taylor, Ch.J. Active Appearance Models, IEEE Translation on Pattern Analysis and Machine Intelligence, vol. 23, no. 6, june 2001 Stegmann, M.B. Active Appearance Models http://www2.imm.dtu.dk/~aam/ Neuronové sít : Rayes-Aldasoro, C.C. Image Segmentation with Kohonen Neural Network Self-Organising Maps. http://www.cs.jhu.edu/~cis/cista/446/papers/SegmentationWithSOM.pdf Dinggang, S., Horace, H.S. A Hopfield neural network for adaptive image segmentation: An active surface paradigm. http://bric.unc.edu/ideagroup/Publications/articles/PRL97.pdf Textura: Šára, R. Analýza textury http://cmp.felk.cvut.cz/cmp/courses/dzo/resources/lecture_texture_sara.pdf Láník, A., Zuza ák, J. Extrakce obrazových p íznak . http://www.fit.vutbr.cz/study/courses/IKR/public/prednasky/04_obrazove_priznaky/IKR4.pdf Vypl ování oblastí: Žára, J., Beneš, B., Felkel, P.: Moderní po íta ová grafika, Computer Press Praha, 1998, ISBN 80-7226-049-9 Vypl ování oblastí – p ednáška Po íta ová grafika 2006, PV-KID-UPCE http://school.lynn.cz/grafika/prednasky/PG_2006_P04_Vyplnovani_4s.pdf

Regionální segmentace a shlukování

Recommend Documents