4.1.1 Jednoduché prahovanie

Prahovacie metódy predpokladajú, že objekty v obraze sa dajú odlíšiť od pozadia na základe jasovej hodnoty jednotlivých obrazových bodov. Najprv sa zvolí prah T. Podľa tejto prahovej hodnoty sa rozdelia obrazové body na body objektu a body pozadia. Táto metóda sa nazýva globálne prahovanie. Prahovaný obraz g(x,y) získame z pôvodného obrazu f(x,y) pomocou vzťahu:

                                                                                       (1)

Poloprahovanie je podobné globálnemu prahovaniu, len jasové hodnoty, ktoré presahujú prah T sa nemenia.

                                                                                (2)

Ak namiesto prahovej hodnoty máme interval, tak sa to nazýva spektrálne prahovanie.

                                                                                  (3)

kde I je interval jasových hodnôt.
Ak máme viac objektov s rôznymi jasovymi hodnotami môžeme použiť na segmentáciu multispektrálne prahovanie

                                                                                                (4)

kde I₁, .. I_n  sú disjunktné intervaly jasových hodnôt. a₁, .. a_n sú rôzne jasové úrovne.

Jednoduché prahovanie.

Otázkou ostáva, ako zvoliť prahovú hodnotu T ? Máme na to viac možností:

• Ak histogram obrazovej funkcie je bimodálny, to znamená, že predmety v obraze majú výrazne odlišnú hodnotu jasu od pozadia. Lokálne minimum medzi dvoma špičkami histogramu je vhodné použiť ako prahovú hodnotu.

 
Obr. 4.1  Bimodálny histogram.

• Na základe apriórnej informácie o obraze, ako napr. percentuálny podiel objektu a pozadia.
• Optimálny prah. Modelovať histogram, ako súčet dvoch normálnych rozdelení hustot obrazovej funkcie.

4.1.2Adaptívne prahovanie

V praxi sa môže stať, že obraz ktorý dostaneme na vstup obsahuje objekty, ktoré sú zle osvetlené, alebo vrhajú tieň. Tieto dôvody môžu byť príčinou, že jednoduché prahovacie metódy zlyhajú. Riešením situácie je adaptívne prahovanie. Rozdiel medzi adaptívnym a jednoduchým prahovaním je, že v prvom prípade prahová hodnota sa vypočítava zvlášť pre každý bod obrazu.
Poznáme dve základné techniky na výpočet prahovej hodnoty:

• Chow a Kanenho metóda: Obraz rozdelíme na množinu menších častí. Skúmaním histogramu pre každú obrazovú časť zistíme príslušný optimálny prah. Prahovú hodnotu pre konkrétny bod vypočítame interpoláciou prahových hodnôt podobrazov. Nevýhodou tejto metódy je zložitý, časovo náročný výpočet, preto nie je vhodný pre real-time aplikácie.
• Lokálne prahovanie: pre každý bod si zvolíme malé okolie, pomocou ktorého vypočítame prahovú hodnotu. Na výpočet prahovej hodnoty máme viac možností:
1. priemer jasových hodnôt v okolí
2. medián jasových hodnôt v okolí
3. stredná hodnota minimálnej a maximálnej jasovej hodnoty v okolí

Adaptívne prahovanie - Lokálne prahovanie.

Okolie musíme zvoliť tak, aby obsahovalo dostatočný počet bodov objektu i pozadia. Výsledok môžeme vylepšiť, ak za prahovú hodnotu zvolíme

                                                                                                                              (5)

kde F(o) označuje zvolenú funkciu, C je kladná konštanta najčastejšie z rozsahu 5 až 10. Takýmto spôsobom eliminujeme veľké homogénne oblasti, ktoré zapĺňajú celú masku.

4.2 Techniky založené na hranách 

V kapitole 2.6 sme sa oboznámili s metódami na detekciu hrán. V ideálnom prípade, tieto metódy nám vrátia hranicu medzi objektom a pozadím. V praxi je to veľmi zriedkavé. Naše výpočty ruší šum, zlé osvetlenie objektu. Preto hranica je nesúvislá a množina hrán obsahuje aj nepodstatné hrany. Preto sa vyvinuli algoritmy, ktoré sa snažia z množiny hrán vytvoriť súvislú hranicu objektov.

4.2.1 Lokálna analýza – spájanie hrán

 Vstup pre tieto algoritmy môže byť prahovaný obraz hrán, ktorý získame z obrazu hrán prahovaním. To znamená, že slabé hrany sú z obrazu hrán vynechané. Táto metóda skúma okolie každého bodu v obraze hrán. Okolie bodu je definované maticou veľkosti 3x3 alebo 5x5. Všetky susediace body, ktoré spĺňajú nasledujúce podmienky sú spojené a vytvárajú tak hranicu.

• Veľkosť odozvy gradientového operátora pre bod (x,y) sa málo líši od veľkosti odozvy pre bod (x1,y1). Kde bod (x1,y1) patrí do okolia bodu (x,y).

                                                                                       (6)

T je prahová hodnota.

• Smer gradientu pre bod (x,y) sa málo líši od smeru gradientu pre bod (x1,y1)

                                                                                                (7)

kde A je prahová hodnota daná v uhloch. Pritom si treba uvedomiť, že smer gradientu je kolmý na smer hrany.

 
Prahovanie obrazu hrán s veľkosťou masky 5x5.
Parametre: Prah pre obraz hrán.
Konštanty: prah pre hrany T=10, pre uhly A=10. 

4.2.2 Sledovanie hranice

Predpokladajme, že vstupný obraz je binárny, alebo že oblasti boli identifikované farbením (7.1.1). Potom vnútornú hranicu oblasti môžeme získať pomocou nasledujúceho algoritmu:

1)      Prechádzajme obraz po riadkoch, až kým nenarazíme na obrazový element, ktorý nepatrí pozadiu. Tento bod označíme P, je to prvý bod hranice.
Nech premenná Smer uchováva smer od posledného bodu do aktuálneho bodu.

a)      Pre 4-susednosť:  Smer:=3

b)     Pre 8-susednosť: smer:=7.

2)      Nasledujúci hraničný bod je ten, ktorý je nájdený ako prvý pri prehľadávaní okolia bodu, pričom prehľadávanie začneme v smere

a)      Pre 4-susednosť
(smer + 3) mod 4

b)     Pre 8-susednosť:
(smer + 7) mod 8   pre párny smer 
(smer + 6) mod 8   pre nepárny smer

            Nasledujúca hodnota premennej smer je určená na základe obr. 4.2.

3)      Ak P_n = P₁ a P_n-1 = P₀ potom krok (4)
Inak opakuj krok (2)

4)      Opakujeme kroky (1) až (3) dovtedy, kým neprejdeme celý obraz.

 
Obr. 4.2 Poradie susedov pri sledovaní hranice.
a)      pre 4-susednosť.
b)     pre 8-susednosť.

Tento algoritmus nájde hranice všetkých oblastí v obraze, ale nenájde diery v oblastiach. Diery môžeme najsť jednoduchou úpravou predchádzajúceho algoritmu.

Simulácia alg. sledovania hranice.

4.3 Techniky založené na oblastiach 

V predošlej kapitole sme hľadali hranice regiónov. Teraz budeme hľadať samotné regióny na základe určitých vlastností.
Definujme kritérium homogenity P, ako logický predikát na množine bodov, ktorý je pravdivý, ak maximálny jasový rozpty
l bodov je menší ako prahová hodnota T. Nech R je množina bodov, potom pre P platí

                                                                         (8) 

4.3.1Selekcia podľa farby – Narastanie oblasti spájaním bodov do oblasti

Myšlienka metódy je spájanie bodov do oblasti. Na začiatku musíme zvoliť základné body, ktoré budú vytvárať jadrá jednotlivých oblastí. Pre každý základný bod budeme testovať jeho susedov, či spolu spĺňajú kritérium homogenity. Ak áno, potom ich spojíme do jednej oblasti. Výsledok závisí na voľbe základných bodov a na voľbe T pre kritérium homogenity.   

Selekcia podľa farby.
 Parameter - prahová hodnota.

4.3.2Spájanie oblastí

Nech R je región obsahujúci celý obraz. Cieľom je rozdeliť R na n podregiónov R1,..,Rn s vlastnosťami:

a)      

b)       Ri je spojitý región, pre každé i=1,..,n. Región je spojitý, ak pre každú dvojicu bodov z regiónu existuje cesta spájajúca tieto body, patriaca celá do regiónu.

c)      

d)      

e)      

Obraz najprv rozdelíme na menšie disjunktné časti veľkosti 2x2, 4x4 alebo 8x8. Susedné oblasti, ktoré spolu spĺňajú kritérium homogenity spojíme do jednej oblasti. Výsledkom tohto postupu je rozdelenie spĺňajúce podmienky a) – e).

Spájanie oblastí na základe kritéria homogenity.

Na spájanie oblastí môžeme použiť aj ďalšie heuristiky:

• dve susedné oblasti Ri, Rj spojíme, ak dostatočne veľká časť ich vzájomnej hranice je zložená z nevýznamných hrán. Či je časť vzájomnej hranice dostatočne veľká sa určuje podľa celkovej dĺžky kratšej uzavretej hranice.

                                                                                                             (9)

kde W je počet slabých hrán spoločnej hranice, l_i, l_{j sú dĺžky} hranice oblastí Ri, Rj, T je prahová hodnota.

• Dve susedné oblasti Ri, Rj spojíme do jednej oblasti, ak dostatočne veľká časť ich vzájomnej hranice je zložená z nevýznamných hrán.

                                                                                                                           (10)

kde W je počet slabých hrán vzájomnej hranice, l je počet spoločných hrán, T je príslušná prahová hodnota.

• Dve susedné oblasti Ri, Rj spojíme, ak počet nevýznamných hrán ich vzájomnej hranice presahuje prahovú hodnotu T.

                                                                                                                           (11)

Hrana medzi dvoma bodmi obrazu je nevýznamná hrana, ak rozdiel v jasových hodnotách je dostatočne malý.

                                                                                                                    (12)

kde A, B sú susedné body.

4.3.3 Rozdeľovanie oblasti

Rozdeľovanie oblasti je principiálne opačný prístup k segmentácií ako spájanie oblastí. Obraz tvorí jeden región, ktorý zvyčajne nespĺňa podmienky a) – e). Preto ho rozdelíme na menšie časti, až kým podmienky nebudú splnené.

Rozdeľovanie oblasti na základe kritéria homogenity.

4.3.4 Rozdeľovanie a spájanie oblastí

Metóda rozdeľovania a spájania oblastí zachováva dobré vlastnosti predošlých techník. Pri tejto metóde využívame pyramídovú dátovú štruktúru. Ak je oblasť v danej úrovne pyramídy nehomogénna, tak sa rozdelí na štyri podoblasti, na elementy nižšej úrovne. Výsledkom rozdeľovania bude kvadrantový strom, v ktorom každý list reprezentuje homogénnu oblasť. V druhej časti algoritmu spojíme dve susedné oblasti, ak spolu spĺňajú kritérium homogenity. Výpočet ukončíme, keď už nemáme čo spojiť, teda regióny spĺňajú podmienky a) – e).  

Kvadrantový strom.

Poznámka: Pri implementácií týchto algoritmov výsledok závisí aj od toho, kde sme začali spájanie. Napríklad výsledok spájania začínajúceho v ľavom hornom rohu sa môže líšiť od výsledku spájania začínajúceho v pravom dolnom rohu.

Rozdelovanie a spájanie oblastí na základe kritéria homogenity.

4.4 Porovnávanie so vzorom

Ďalším prístupom k segmentácií je vyhľadávanie známych objektov v obraze. Táto metóda sa môže použiť aj na detekciu pohybu objektu v obraze. V praxi je obvykle časť obrazu oproti vzoru nejako porušená, napríklad zašumená. Preto nemôžeme hľadať absolútnu zhodu so vzorom, ale len čiastočnú. Používajú sa rôzne kritéria zhody. Sú to funkcie, ktoré nám vracajú hodnotu z intervalu (0,1>. Hodnota 1 znamená úplnú zhodu.

Nech f je obrazová funkcia, h je hľadaný vzor a (u,v) umiestnenie vzoru v obraze. Nasledujúce funkcie sú vhodné pre kritérium zhody:

                                                                            (13)

                                                                                (14)

                                                                               (15)

kde V je množina obrazových elementov vzoru.