V článku sú opísané teoretické základy morfologickej vnútrosnímkovej segmentácie obrazov. Uvedený algoritmus vnútrosnímkovej segmentácie obrazu segmentuje vstupný obraz hierarchicky v niekoľkých úrovniach. Tento algoritmus bol implementovaný do programu, ktorý tak simuluje segmentáciu statických šedotónových obrazov. Na reprezentáciu dosiahnutých výsledkov bol použitý šedotónový obraz Lena veľkosti 256×256 obrazových prvkov (op).

1. Úvod

V oblasti kódovania obrazov pre veľmi malé bitové rýchlosti (pod 64 kb/s) sa často používajú metódy kompresie obrazov druhej generácie [1], [2]. Tie eliminujú redundantnú informáciu vo vnútri snímok alebo medzi snímkami a sú založené na nekonvenčných prístupoch ako napr. regiónovo alebo objektovo orientované metódy, tzn. metódy orientované na štrukturálne vyššiu obrazovú úroveň – na objekty alebo segmenty [3].

Segmentácia je jednou zo základných operácií v metódach kompresie obrazov [5]. Úlohou segmentácie je rozdeliť spracovaný obraz na menšie časti tzv. segmenty, ktoré majú silnú koreláciu. Cieľom segmentácie je jednotlivé segmenty od seba navzájom oddeliť a oddeliť ich aj od pozadia, ktoré je pre ďalšie spracovanie obrazu väčšinou nepodstatné. Neexistuje jedná univerzálna metóda segmentácie, ktorá by bola vhodná na ľubovoľné typy obrazov. Preto je množstvo segmentačných metód, ktoré sú vhodné len na určite typy obrazov. V literatúre nájdeme veľké množstvo segmentačných metód a ich rôzne rozdelenie [6], [7]. Objektovo orientované metódy kódovania prebiehajú v troch základných krokoch spracovania:

1. segmentácia,
2. kódovanie obrysov,
3. kódovanie textúry.

Segmentácia rozdelí vstupný obraz na jednotlivé segmenty obrazu, ktoré predstavujú sémanticky jednotnú časť obrazu. Pri kódovaní obrysov sa kódujú kontúry týchto segmentov a pomocou kódovania textúry sa kóduje šedotónová alebo farebná informácia z vnútra segmentov. Segment je teda reprezentovaný dvoma komponentmi: obrysmi a textúrou. Článok rozpracováva vnútrosnímkovú segmentáciu obrazu s využitím morfologických operácií, na základe ktorej boli vypracované programové prostriedky na simuláciu tejto vnútrosnímkovej segmentácie reálnych šedotónových obrazov.

2. Metódy vnútrosnímkovej segmentácie obrazu

Segmentácia je jedným zo základných krokov v procese objektovo orientovaného kódovania dynamických, ale aj statických obrazov. Jej úlohou je rozdeliť obraz na množinu homogénnych a spojitých segmentov. Základné požiadavky kladené na segmentáciu sú [4]:

• extrahovať z vizuálneho hľadiska najdôležitejšie časti obrazu,
• koherentnosť v čase,
• vyhnúť sa náhodným zmenám obrysov,
• vyriešenie zmien tvarov segmentov v čase.

Posledné tri požiadavky sa týkajú segmentácie dynamických obrazov. Tieto požiadavky najlepšie spĺňa časovo – rekurzívna segmentácia, ktorá môže prebiehať v dvoch módoch: vnútrosnímková segmentácia a medzisnímková segmentácia.

Vnútrosnímková segmentácia obrazu je dvojrozmerný proces, ktorý segmentuje dynamický obraz vo vnútrosnímkovom móde alebo segmentuje statický obraz. Existuje viacero techník vnútrosnímkovej segmentácie napr. jednoduchá detekcia hrán alebo metóda “split and merge”. Z hľadiska štrukturálne vyššieho chápania obrazu je vhodná morfologická segmentácia, ktorá využíva morfologické operátory. Matematická morfológia umožňuje geometrickú reprezentáciu obrazov a geometrický prístup k ich spracovaniu. Známe sú rôzne techniky vnútrosnímkovej morfologickej segmentácie [3].

Nami vypracované programové prostriedky na simuláciu vnútrosnímkovej segmentácie obrazu sú založené na hierarchickej viacúrovňovej technike nazývanej “top-down”. Je to technika atraktívna hlavne z hľadiska progresívneho kódovania a prenosu obrazov. Algoritmus začína segmentovať obraz na segmenty obsahujúce čo možno najglobálnejšiu informáciu. Na prvých úrovniach segmentácie dostávame len veľmi hrubú aproximáciu originálneho obrazu a počet segmentov je malý . Postupne, v ďalších úrovniach hierarchie, sa segmentácia zjemňuje, berúc do úvahy jemnejšie detaily v obraze. Počet segmentov sa so zvyšujúcou sa úrovňou segmentácie zväčšuje. So zväčšovaním kvality segmentácie a väčším počtom segmentov sa však zmenšuje kompresný pomer kódovania. Počet segmentačných úrovní môže byť rôzny, najtypickejším počtom sú však 4 úrovne. Štruktúra jednej z úrovní vnútrosnímkovej hierarchickej viacúrovňovej morfologickej segmentácie obrazu má nasledujúci tvar [3], [4]:

• modelovanie,
• zjednodušovanie,
• rozpoznávanie segmentov,
• značkovanie jadier segmentov.

2.1 Modelovanie

Za predpokladu, že poznáme segmentáciu z predchádzajúcej úrovne, úlohou aktuálnej úrovne je zlepšiť túto segmentáciu tým, že zavedie do už segmentovaného obrazu ďalšie segmenty, ktoré opisujú menšie detaily v obraze, než predstavujú segmenty z predchádzajúcich úrovní. Aby sa získala informácia o týchto nových segmentoch, je potrebné každý aktuálny segment zakódovať. Tento krok je v podstate estimáciou kvality segmentovaného obrazu. V ideálnom prípade [3] by sa mal používať reálny kódovací algoritmus, tzn. kódovanie obrysov a kódovanie textúry. Väčšinou však postačuje iba kódovanie textúry. Môžu byť použité rôzne metódy kódovania textúry. Z dôvodov jednoduchosti a rýchlosti spracovania naše programové prostriedky používajú na simuláciu segmentácie kódovanie textúry založené na kódovaní segmentu jednou konštantnou úrovňou jasu, ktorá je pre ten-ktorý segment uložená vo vzorkovnici a vypočítaná počas predchádzajúcej úrovne segmentácie. Touto konštantnou úrovňou šedej sa teda modeluje celý segment. Spôsoby výpočtu tejto úrovne jasu sú uvedené v ďalšej časti článku.

Vstupným obrazom v kroku modelovania je segmentačný obraz, ktorý obsahuje informáciu o rozdelení obrazu v predchádzajúcich úrovniach segmentácie. Výstupným obrazom procesu modelovania je aktuálne zakódovaný obraz na základe aktuálnej segmentácie. Výstupný obraz modelovania na prvej úrovni segmentácie je obraz, ktorý celý tvorí jeden segment, tzn. celý obraz je vyplnený konštantnou úrovňou jasu s hodnotou 128. Po modelovaní sa vypočíta rozdiel originálneho (Obr.1a) a modelovaného obrazu. Výstupom je chybový obraz (Obr.1b), v ktorom sa koncentruje informácia rozdelenia na oblasti obrazu, ktoré sú aktuálnym segmentovaním len slabo reprezentované. Znamená to, že čím má chybový obraz v určitej oblasti obrazu vyšší jas, tým slabšie/nedokonalejšie je táto oblasť segmentovaná. Chybový obraz takto nesie informáciu o častiach obrazu, ktoré je potrebné v ďalších úrovniach jemnejšie segmentovať, aby sa dosiahlo ich presnejšieho zakódovania.

(a)

(b)
Obr. 1. a) originálny 8 bitový obraz LENA s rozmermi 256×256 op; b) chybový obraz vytvorený rozdielom modelovaného obrazu na prvej úrovni a originálneho obrazu (čím väčší jas má op na určitej súradnici, tým väčšia je chyba segmentácie na danej súradnici).

2.2 Zjednodušovanie

Úlohou kroku zjednodušovania je zjednodušiť vstupný chybový obraz tak, aby bol na danej úrovni hierarchie ľahšie segmentovateľný. Zjednodušovanie rozhoduje o type a množstve informácie, ktoré bude na danej úrovni v obraze ponechané alebo odstránené a tiež rozhoduje o odstraňovaní prípadného šumu zo vstupného obrazu. Z hľadiska potreby pracovať s geometrickými atribútmi obrazu sú na účel zjednodušovania mimoriadne vhodné morfologické filtre, ktoré sú schopné pracovať s takými vizuálne dôležitými kritériami zjednodušovania obrazu, ako sú veľkosť alebo kontrast [10], [11]. Podľa kontrastného kritéria sa zo vstupného obrazu odstránia oblasti s menším kontrastom, ako je určený limit a podľa veľkostného kritéria sú potom segmentované len oblasti s veľkosťou väčšou ako je daný limit [3]. Vstupným obrazom pre krok zjednodušovania je chybový obraz a výstupom je zjednodušený chybový obraz (Obr.2a).

(a)

(b)

(c)
Obr. 2. a) Zjednodušený chybový obraz prvej úrovne segmentácie filtrovaný morfologickým rekonštrukčným otváraním-zatváraním s filtračným oknom 21×21 op; b) jadrá segmentov na prvej úrovni segmentácie (čierne objekty v obraze predstavujú jadrá a biele oblasti obrazu predstavujú oblasti neurčitosti); c) jadrá segmentov na prvej úrovni segmentácie po filtrácii morfologickým rekonštrukčným otváraním-zatváraním s filtračným oknom 3×3 op.

(a)

(b)

(c)
Obr.3. a) Jadrá segmentov druhej úrovne segmentácie, ktoré vznikli zjednotením jadier segmentov vzniknutých na prvej úrovni segmentácie a jadier segmentov získaných na aktuálnej úrovni segmentácie; b) jadrá segmentov druhej úrovne segmentácie po filtrovaní morfologickým rekonštrukčným otváraním-zatváraním s filtračným okienkom 3×3 op; c) označkované jadrá segmentov druhej úrovne segmentácie.

2.3 Rozpoznávanie segmentov

Po zjednodušení chybového obrazu výstupný obraz obsahuje informáciu o oblastiach, ktoré budú na danej úrovni segmentované. Je teda potrebné detegovať tieto oblasti. Jedným zo spôsobov detekcie objektov je vytvorenie morfologického gradientu zjednodušeného chybového obrazu a tento gradient potom prahovať. Po prahovaní sa získa binárny obraz, kde binárna 0 označuje obrazový prvok patriaci k tzv. jadrám segmentov.

Jadrá segmentov sú spojité objekty v binárnom obraze s hodnotou binárnej 0, ktoré pozostávajú z obrazových prvkov (op), o ktorých možno jednoznačne povedať, že patria k niektorému zo segmentov. Tieto jadrá potom tvoria základ budúcich segmentov. Binárna 1 obrazového prvku v binárnom obraze označuje obrazové prvky, o ktorých nemožno jednoznačne povedať, že patria k určitému jednému segmentu. Tieto op tak vytvárajú oblasť neurčitosti (Obr.2b). Každá úroveň segmentácie však potrebuje aj informáciu o už vytvorených segmentoch v predošlých úrovniach segmentácie. Ako druhý zdroj informácií o rozpoznávaní segmentov využíva aktuálnu segmentáciu vytvorenú na predošlej úrovni.

Z aktuálnej segmentácie – segmentačného obrazu alebo modelovaného obrazu – sa vytvorí morfologický gradient a ten sa prahuje. Tým získame jadrá už vytvorených segmentov a oblasti neurčitosti, ktoré spolu vytvárajú druhý binárny obraz (Obr.2c). Za predpokladu, že binárna 0 označuje jadrá segmentov a binárna 1 označuje oblasť neurčitosti, obraz zjednotených jadier získame bodovým maximom, t.j. pre každý op sa zisťuje logický súčet dvoch op – jedného z obrazu aktuálnych jadier a druhého z obrazu nových jadier (Obr.3a). Prahovanie v procese rozpoznávania segmentov môže mať pevný prah pre celý obraz bez ohľadu na informačný obsah tej-ktorej oblasti alebo adaptívny prah, ktorý mení svoju hodnotu pre každý op v závislosti od informačného obsahu gradientného obrazu [4].

Zjednotením dvoch binárnych obrazov sme získali jeden s jadrami segmentov a oblasťou neurčitosti. Jadrá segmentov sú spojité objekty tohto binárneho obrazu, ktoré tvoria základ budúcich segmentov vytvorených na danej úrovni segmentácie. Jadrá segmentov sú obklopené oblasťou neurčitosti, ktorej op zatiaľ nie sú priradené k žiadnemu segmentu. Jadrá segmentov určujú iba počet, približné umiestnenie a približný tvar budúcich segmentov aktuálnej úrovni segmentácie. Presné obrysy segmentov zatiaľ nie sú určené. Keďže zjednotením jadier z dvoch rôznych zdrojov môžu vzniknúť jadrá segmentov predstavujúcich objekty, ktoré boli už predtým krokom zjednodušovania chybového obrazu z neho odstránené, je potrebné binárny obraz zjednotených jadier prefiltrovať tak, aby v obraze ostali len jadrá s veľkosťou väčšou než je daný limit [4].

Filtráciu binárneho obrazu možno previesť rovnakým filtrom, aký bol použitý pre zjednodušovanie, napr. rekonštrukčné otváranie -zatváranie s veľkosťou n_k , pre ktorú platí , že n_k < n, kde n je veľkosť filtra použitého pre zjednodušovanie chybového obrazu. Napr. v 4] sa uvádza hodnota n_k = n/2. Výsledkom filtrácie bude zjednodušený obraz jadier a oblasti neurčitosti (Obr.3b). Aby bolo možné v ďalšom kroku selektívne pracovať s jednotlivými segmentami, je potrebné ich rozlíšiť. Každý segment (jadro segmentu) dostane svoju vlastnú značku jednotnú pre celý segment. Značkovanie jadier segmentov (labeling) je úlohou nasledujúceho kroku.

2.4 Značkovanie jadier segmentov

Vlastné rozlíšenie segmentov, t.j. rozpoznávanie segmentov, prebieha značkovaním jadier segmentov. Každý op patriaci k určitému jadru segmentu dostane zodpovedajúcu značku pridelenú pre daný segment (Obr.3c). Ďalej sú uvedené dva spôsoby značkovania jadier segmentov.

Rýchla metóda

Vstupný obraz z hľadiska procesu značkovania je binárny obraz jadier a oblasti neurčitosti. Výstupom bude obraz obsahujúci značkované jadrá a oblasť neurčitosti. Rýchla metóda vykoná túto transformáciu pomocou dvoch prebehnutí obrazu bod po bode a riadok po riadku. Uvažujme, že skúmame obraz bod po bode, zľava doprava a riadok po riadku, zhora nadol, pričom uvažujeme pre každý obrazový prvok (okrem tých, ktoré sú okrajové) 8 susedných obrazových prvkov: 3 v predchádzajúcom riadku, 3 v nasledujúcom riadku a 2 susedné prvky v aktuálnom riadku. Počas prvého prezerania obrazu skúmame pre každý op z hľadiska postupu prezerania obrazu predchádzajúce op: 1 z aktuálneho riadku a 3 susedné z predchádzajúceho riadku. Ak tieto op existujú, prvým prezeraním už boli navštívené a ak patrili k niektorému jadru, už majú svoju značku.

Algoritmus rýchlej metódy pre všetky obrazové prvky obrazu :

{
 -ak aktuálny op má hodnotu binárna 0 (je z jadra):
 {
  - ak všetky 4 vedľajšie predchádzajúce op majú hodnotu binárna 1, tak aktuálnemu op priradíme novú značku,
  - ak práve jeden zo susedných predchádzajúcich op má značku (nemá hodnotu binárna 1), tak aktuálnemu op priradíme práve túto značku,
  - ak zo susedných predchádzajúcich op majú značku viaceré, tak priradíme aktuálnemu op jednu zo značiek niektorého susedného predchádzajúceho op, a ak aspoň dve zo značiek susedných predchádzajúcich op sú rôzne, postavíme medzi nimi ekvivalencie.
 }
}

Výsledkom tejto prvej transformácie obrazu sú prvotne označkované jadrá a ekvivalencie. Prvotne označkované jadrá však nemusia byť označkované správne – jedno jadro môže mať viacero značiek. Tento nedostatok odstraňuje druhá transformácia pomocou ekvivalencií, t.j. tie určujú, ktoré rôzne značky patria do rovnakého jadra. Druhá transformácia preznačkuje všetky op jadier podľa stanovených ekvivalencií tak, že z ekvivalentných značiek sa vyberie jedna, reprezentujúca ďalej dané jadro a tá sa priradí všetkým op majúcim značku ekvivalentnú s vybranou značkou.

Pomalá metóda

Pomalá metóda značkovania jadier je založená na tom, že v prvom prezeraní obrazu s neoznačkovanými jadrami každý op patriaci jadru bude mať uvedeným spôsobom pridelenú značku (Obr.4a), čím vznikne prvotné značkovanie jadier, ktoré však má rovnaký nedostatok, ako v prípade rýchlej metódy. Rozdiel medzi oboma metódami je v odstraňovaní viacerých rôznych značiek jedného jadra, čiže v nejednoznačnosti značkovania. Preznačkovanie sa v tejto metóde robí opakovanou operáciou lokálneho maxima (alebo minima) aplikovanou na prvotne označkovaný obraz. Pre každý označkovaný op sa zisťuje maximálna značka v jeho jednotkovom okolí a táto sa potom priradí aktuálnemu obrazovému prvku z jadra (Obr.4b). Táto operácia sa opakuje, až kým v hodnotách značiek op nastanú zmeny vplyvom aplikácie lokálneho maxima.

Algoritmus pomalej metódy pre všetky obrazové prvky obrazu :

{
pre všetky op z aktuálneho riadku, ktoré nemajú hodnotu binárna 1:
 - ak op v predchádzajúcom riadku v rovnakom stĺpci, v akom je aktuálny prvok, má značku, tak sa táto značka priradí aktuálnemu op,
 - ak op z aktuálneho riadku v predchádzajúcom stĺpci má značku, táto sa priradí aktuálnemu op,
 - ak op z aktuálneho riadku v nasledujúcom stĺpci má značku, táto sa priradí aktuálnemu op,
 - ak aktuálny op má hodnotu binárna 0, priradí sa mu nová značka.
}

Uvedený algoritmus zabezpečí prvotné značkovanie jadier a následná aplikácia lokálneho maxima zabezpečí správne značkovanie všetkých jadier segmentov (Obr.4c). Počet prehliadaní obrazu však dopredu nie je známy a môže byť značne veľký, čo spôsobuje, že tento algoritmus značkovania je pomalší ako algoritmus rýchlej metódy.

(a)

(b)

(c)
Obr.4. a) Označkované jadrá segmentov na prvej úrovni segmentácie. Na značkovanie bola použitá pomalá metóda. Každé jadro segmentu je rozlíšiteľné svojou pridelenou značkou t.j. jasovou hodnotou; b) segmentácia obrazu na prvej úrovni segmentácie. Každý segment je vyplnený konštantnou úrovňou jasu, t.j. zodpovedajúcou značke segmentu (deliace čiary v obraze sú čiary s maximálnou jasovou hodnotou – biele čiary); c) segmentácia obrazu na prvej úrovni segmentácie bez deliacich čiar (každý op patrí k niektorému z existujúcich segmentov).

3. Výpočet vzorkovnice

Každá úroveň segmentácie pri modelovaní segmentovaného obrazu používa vzorkovnicu, podľa ktorej pri modelovaní priradzuje reálne jasové hodnoty op podľa toho, ku ktorému zo segmentov patria. Vzorkovnicu je možné získať práve po získaní označkovaných jadier. Vzorkovnica je j-rozmerný vektor, ktorého index zároveň označuje hodnotu značky a k-tý prvok vektora, kde k≤j sa rovná reálnej jasovej hodnote op, ktoré pri modelovaní majú značku k. Vzorkovnica je informácia, ktorá sa prenáša medzi dvoma úrovňami segmentácie.

Jednoduchý spôsob výpočtu vzorkovnice

Princíp jednoduchého výpočtu spočíva v tom, že pre vzorkovnicu sa pre danú značku vyberie jedna reálna jasová hodnota z originálneho obrazu a to z tých op, ktoré sú na rovnakej horizontálnej aj vertikálnej pozícii, ako niektorý vybraný op jadra segmentu, ktorý má danú značku. Výber zodpovedajúceho op z jadra môže byť rôzny, napr. môže to byť posledný op z daného jadra z hľadiska prehľadávania obrazu zľava doprava a zhora nadol.

Priemerový výpočet vzorkovnice

Priemerový výpočet vzorkovnice možno vykonať až potom, keď je známa celková segmentácia obrazu na danej úrovni. Reálna jasová hodnota, ktorá sa priradí k-tému op vektora vzorkovnice je určená priemerom jasových hodnôt všetkých op patriacich k segmentu so značkou k.

4. Watershed metódy

Po označkovaní jadier je už známy počet segmentov, ich približná pozícia v obraze a približný tvar, ale stále nie sú známe presné obrysy týchto segmentov. Obrysy sa nachádzajú niekde v oblasti neurčitosti. Určenie presnej segmentácie a obrysov segmentov je úlohou kroku rozhodovanie. Morfologickým nástrojom rozhodovacieho procesu je transformácia watershed [8], [9].

4.1. Základné definície

Uvažujme šedotónový statický obraz I, ktorého op nadobúdajú diskrétne hodnoty z intervalu (0, N), kde N je ľubovoľné kladné číslo (napr. N = 255). Takýto obraz možno považovať za dvojrozmernú funkciu alebo topografický reliéf.

Definícia 1.: Nech G označuje diskretizačnú mriežku, na ktorej je definovaný obraz I. Potom cesta P dĺžky d medzi dvoma obrazovými prvkami p a q obrazu je (d+1)-tica obrazových prvkov (p₀, p₁,…, p_k-1, p_d), takých, že : p₀ = p, p_d = q, A pre všetky i = (1, d) sú (p_i-1, p_i) z mriežky G.

Definícia 2.: Minimum M obrazu I vo výške h je spojitý objekt obrazu, ktorého obrazové prvky majú hodnotu h a z tohto minima nie je možné urobiť cestu k nižšiemu obrazovému prvku v obraze (ak existuje) bez toho, aby body cesty nemali väčšiu výšku ako h.

Definícia 3.: Geodézická vzdialenosť medzi dvoma obrazovými prvkami p a q je dĺžka najkratšej cesty P s koncovými bodmi p a q.

Definícia 4.: Majme binárnu dvojrozmernú množinu X (obraz). Prvky množiny X predstavujúce pozadie majú hodnotu binárnej 1. Uvažujme v množine X spojité objekty Z_i s hodnotou binárnej 0. Potom zóna vplyvu objektu Z_i v rámci množiny X je definovaná ako podmnožina obrazových prvkov množiny X, ktoré majú geodézickú vzdialenosť k objektu Zi menšiu ako geodézickú vzdialenosť ku ktorémukoľvek inému objektu Z_k. Zónu vplyvu objektu Zi v rámci množiny-obrazu X označíme: ZI (obraz = X , objekt = Z_i).

4.2. Algoritmus SKIZ

Obrazové prvky, ktoré majú v obraze X rovnakú geodézickú vzdialenosť k viacerým objektom Zi, nazývame body deliacich čiar zón vplyvu. Deliace čiary vytvárajú skelet zón vplyvu a oddeľujú ich od seba. Algoritmus pre binárne obrazy , ktorý zisťuje zóny vplyvu a skelet zón vplyvu sa nazýva SKIZ (SKeleton by Influence Zone). Predpokladajme obraz X, ktorého op patriace objektom Zi sú označkované niektorou z transformácií uvedených vyššie. Každý op objektu Zi má teda vlastnú značku pre každý objekt. Body nepatriace objektom (pozadie v obraze X) dostanú hodnotu VAL, ktorá sa nerovná ani jednej zo značiek.

Paralelné opakovanie nasledujúcej transformácie, až kým nenastane konvergencia:

{
 - pre všetky op obrazu X:
 {
  -ak má op hodnotu VAL:
  {
   - ak aktuálny op nemá vo svojom jednotkovom okolí žiaden značkovaný op, potom aktuálny op si ponechá hodnotu VAL,
   - ak aktuálny op má vo svojom jednotkovom okolí len jeden typ značky, táto značka sa priradí aktuálnemu op,
   - ak aktuálny op má vo svojom jednotkovom okolí viac typov značiek, aktuálny op si ponechá hodnotu VAL.
  }
 }
}

Po tejto transformácii bude obraz X obsahovať zóny vplyvu, ktorých podmnožinou budú objekty Z_i. Každá zóna vplyvu je spojitá časť obrazu s konštantnou hodnotou op zodpovedajúcou značke príslušného objektu Zi. Obraz X bude ďalej obsahovať op s hodnotou VAL, ktoré tvoria deliace čiary zón vplyvu . Algoritmus SKIZ v podstate segmentuje binárny obraz a je stavebným prvkom pre algoritmus watershed, ktorý segmentuje šedotónový obraz.

4.3. Transformácia watershed

Úlohou transformácie watershed je určiť zóny vplyvu jadier segmentov v šedotónovom obraze s ohľadom na topografický reliéf morfologického gradientu originálneho obrazu. Najprv je potrebné vytvoriť morfologický gradient originálneho obrazu, ktorý možno považovať za topografický reliéf. Transformácia watershed je založená na simulácii postupného zaplavovania kvapalinou tohto morfologického gradientu ako topografického reliéfu.

Nech g(I) je šedotónový obraz vytvorený morfologickým gradientom obrazu I, h_min a h_max je minimálna resp. maximálna jasová hodnota, ktorú nadobúda obraz g(I) na svojom definičnom obore. T_h(g(I)) je binárny obraz vytvorený prahovaním obrazu g(I) s prahom h. Z_i pre i = (0,…,s) sú označkované jadrá segmentov s počtom s získané v predošlých krokoch aktuálnej úrovne segmentácie a C(Z_i) je zóna vplyvu jadra Z_i. Uvažujme, že obraz g(I) zaplavujeme postupne po jednotlivých hladinách h kvapalinou vytekajúcou z jadier Z_i, pričom h = (h_min, h_max). Nech Z je zjednotením všetkých jadier Z_i, označme C_h(Z) ako zjednotenie všetkých zón vplyvu jadier v rámci prahovaného obrazu T_h(g(I)), potom môžeme písať:

čo je inicializačný krok algoritmu watershed a pre h = (h_min, h_max):

Topografická interpretácia: Algoritmus watershed založený na simulácii zaplavovania simuluje zaplavovanie gradientu originálneho obrazu kvapalinou vychádzajúcou z označkovaných jadier segmentov. Na každej hladine h simuluje algoritmus SKIZ roztečenie kvapaliny v rámci prahovaného obrazu T_h(g(I)). Ak dôjde vplyvom roztečenia k dotyku kvapalín vytekajúcich z dvoch rôznych jadier, a teda majúcich rôzne značky, v mieste dotyku sa postaví hrádza, tzn. deliaca čiara zón vplyvu jednotlivých jadier. Po dosiahnutí hladiny hmax budú nezaplavené už iba hrádze (deliace čiary) oddeľujúce jednotlivé segmenty.

Po transformácii watershed ako výstupný obraz dostaneme segmentačný obraz so segmentami, ktorých jasová hodnota zodpovedá hodnote značky jadra segmentu a s deliacimi čiarami, oddeľujúcimi od seba jednotlivé segmenty (Obr.5a). Aby sme získali skutočnú segmentáciu, je potrebné tieto deliace čiary z obrazu odstrániť. Odstránenie deliacich čiar je možné previesť priradením obrazovému prvku deliacej čiary značku niektorého vedľajšieho op patriaceho niektorému zo segmentov (Obr.5b).

(a)

(b)
Obr.5. Segmentácia obrazu druhou úrovňou segmentácie a) s deliacimi čiarami; b) bez deliacich čiar.

5. Simulácia a dosiahnuté výsledky

Vytvorený program na simuláciu vnútrosnímkovej segmentácie obrazov bol vypracovaný na základe vyššie uvedených metód. Pre krok modelovania bol odskúšaný jednoduchý aj priemerový výpočet vzorkovnice. Z dôvodu lepších výsledkov pomeru signál/šum (S/Š) používa finálna verzia programu na výpočet vzorkovnice iba priemerovú metódu. Pre krok zjednodušovanie chybového obrazu bol použitý morfologický filter: rekonštrukčné otváranie-zatváranie a to z dôvodu, že odfiltruje zo vstupného obrazu detaily, ktoré sú veľkosťou menšie ako filtračné okno.

Ďalej umožňuje riadiť množstvo odfiltrovanej informácie vhodnou voľbou parametra filtra, ktorý určuje veľkosť filtračného okna a neporušuje informačný obsah oblastí obrazu, ktoré sú veľkosťou väčšie, ako veľkosť filtračného okna. Krok rozpoznávania segmentov používa pevný prah pre gradient chybového obrazu aj pre gradient segmentácie z predchádzajúcej úrovne segmentácie. Po zjednotení jadier segmentov sa obraz jadier filtruje morfologickým rekonštrukčným otváraním-zatváraním s filtračným oknom 3×3 obrazových prvkov. Značkovanie získaných jadier je prevedené pomalou metódou. Rozhodovací proces o presnom umiestnení obrysov segmentov je založený na algoritme watershed simulujúcom zaplavovanie gradientu originálneho obrazu.

Maximálny počet segmentačných úrovní je 4, ale segmentáciu obrazu možno ukončiť po každej úrovni segmentácie. Všetky úrovne segmentácie používajú pre zjednodušovanie veľkostné kritérium prostredníctvom morfologického rekonštrukčného otvárania – zatvárania s veľkosťou filtračného okna, ktoré je na každej úrovni zadávané užívateľom. So zväčšujúcim sa počtom úrovní segmentácie je možné zadávať iba veľkosti filtračného okna menšie, ako mali okna na predchádzajúcich úrovniach (čo zodpovedá progresívnemu zlepšovaniu segmentácie z úrovne na úroveň). Čas výpočtu krokov zjednodušovanie, značkovanie jadier a rozhodovanie je relatívne veľký a závisí od veľkosti filtračného okna. Počet segmentov, na ktoré program segmentuje vstupný obraz, je maximálne 256.

V ďalšom sú uvedené niektoré dosiahnuté výsledky segmentácie reálnych obrazov pomocou vypracovaného programu na simuláciu vnútrosnímkovej segmentácie. Segmentácie boli prevedené na 8 šedotónových obrazoch, v článku uvádzame na ukážku iba výsledky dosiahnuté na šedotónovom obraze LENA s rozmermi 256×256 op a s 8 bitmi na op. Stredná kvadratická chyba segmentovaného obrazu je určená vzťahom :

kde N₁ a N₂ sú vertikálny a horizontálny rozmer obrazu a e(n₁,n₂) je rozdiel originálneho op a op z modelovaného obrazu. Potom pre pomer signál-šum v decibeloch platí , kde označuje strednú kvadratickú hodnotu vstupného originálneho obrazu.

Dosiahnuté výsledky

1.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : jednoduchý
Úroveň 1	Úroveň 2
Filtračné okno : 21×21	Filtračné okno: 7×7
Počet segmentov : 31	Počet segmentov : 86
S/Š : 14,01 dB	S/Š: 16,14 dB

2.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : priemerový
Úroveň 1	Úroveň 2
Filtračné okno: 21×21	Filtračné okno: 7×7
Počet segmentov : 31	Počet segmentov : 63
S/Š: 17,94 dB	S/Š: 19,42 dB

3. a 4.Segmentácia

Počet úrovní : 1
Výpočet vzorkovnice : jednoduchý	priemerový
Filtračné okno: 7×7	Filtračné okno: 7×7
Počet segmentov : 75	Počet segmentov : 75
S/Š: 15,87 dB	S/Š: 19,77 dB

5.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : priemerový
Úroveň 1	Úroveň 2
Filtračné okno: 17×17	Filtračné okno: 5×5
Počet segmentov : 36	Počet segmentov : 92
S/Š: 17,99 dB	S/Š: 19,87 dB

6.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : priemerový
Úroveň 1	Úroveň 2
Filtračné okno: 21×21	Filtračné okno: 5×5
Počet segmentov : 31	Počet segmentov : 87
S/Š: 17,95 dB	S/Š: 19,85 dB

7.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : priemerový
Úroveň 1	Úroveň 2
Filtračné okno: 11×11	Filtračné okno: 3×3
Počet segmentov : 55	Počet segmentov : 87
S/Š: 19,47 dB	S/Š: 19,58 dB

8.Segmentácia

Počet úrovní : 2
Výpočet vzorkovnice : priemerový
Úroveň 1	Úroveň 2
Filtračné okno: 15×15	Filtračné okno: 3×3
Počet segmentov : 48	Počet segmentov : 83
S/Š: 19,07 dB	S/Š: 19,54 dB

V 1. a 2. segmentácií sa porovnávali dva spôsoby výpočtu vzorkovnice a to jednoduchý a priemerový, pričom veľkosť filtračného okna sa nezmenila. Vidno, že s priemerovým spôsobom jej výpočtu sa na oboch úrovniach segmentácie dosiahol lepší pomer S/Š pri 2. segmentácii. Pri druhej úrovni 2.segmentácie je S/Š o 3,28 dB lepší ako pri 1.segmentácii, aj počet výsledných segmentov je v tomto prípade o 23 menší, čo znamená rýchlejší spôsob spracovania.

Výsledky 3. a 4. segmentácie poukazujú na dosiahnuté hodnoty S/Š iba pri jednej úrovni segmentácie, ak sa znova porovnával jednoduchý a priemerový spôsob výpočtu vzorkovnice, avšak pri menšej veľkosti filtračného okna (7×7) ako v prvých dvoch segmentáciách. Pre priemerový spôsob výpočtu vzorkovnice je S/Š o 3,9 dB lepší, ako pri jednoduchom spôsobe jej výpočtu a rovnakých podmienkach.
V ďalšom sme už používali iba priemerový spôsob výpočtu vzorkovnice a segmentáciu sme previedli na dvoch úrovniach, pričom druhá úroveň musí mať menšiu veľkosť filtračného okna ako prvá úroveň, ako už bolo vyššie uvedené.

V 5. a 6. segmentácií sa porovnával vplyv zmeny veľkosti filtračného okna len v prvej úrovni segmentácie, v druhej úrovni zostala veľkosť filtračného okna rovnaká. Pri zmene veľkosti okna zo 17×17 na 21×21 op sa znížila hodnota výsledného S/Š na druhej úrovni segmentácie iba o 0,02 dB (podobne je to aj pri S/Š v prvej úrovni). Počet segmentov sa znížil o 5, čo zodpovedá zväčšenie filtračného okna.

Pri 7. a 8. segmentácii sa dosiahli podobné výsledky, ako pri 5. a 6. segmentácii, len sme tiež zväčšovali veľkosť filtračného okna v prvej úrovni segmentácie z 11x11na 15×15 a v druhej úrovni segmentácie sme zmenšili veľkosť okna na 3×3 oproti 5. a 6. segmentácii. Hľadali sme primeranú veľkosť filtračných okien, pri ktorej by sme dosiahli maximálnu hodnotu S/Š.

Z porovnania výsledkov štyroch vnútrosnímkových segmentácii 5. až 8. pre konkrétny 8 bitový šedotónový obraz Lena veľkosti 256×256 op vyplýva, že najvyššiu hodnotu S/Š = 19,87 dB sme dosiahli pri druhej úrovni segmentácie s veľkosťami filtračných okien 17×17 na prvej úrovni a 5×5 na druhej úrovni segmentácie. Dá sa konštatovať, že hodnota S/Š sa zväčšuje aj pri postupnom zmenšovaní filtračného okna, čo zodpovedá teoretickým vlastnostiam hierarchického segmentačného algoritmu. Na Obr.6 je zobrazený konečný výsledok vnútrosnímkovej segmentácie pri použití priemerového výpočtu vzorkovnice (a) a pri jej jednoduchom výpočte (b).

(a)

(b)
Obr.6. Konečný obraz LENA modelovaný na základe a) 6.segmentácie s priemerovým modelovaním (priemerový výpočet vzorkovnice); b) 1.segmentácie s jednoduchým modelovaním (jednoduchý výpočet vzorkovnice).

Literatúra

1. Salembier,P.- Gu,C.- Pardas,M.- Kunt,M.: Very low bit rate video coding using mophological segmentation and contour/texture motion compensation. IEEE 12th Int. Conf. on Patt. Recog. , Jerusalem, Israel, Oct. 1994.
2. Wang,D.- Labit, C, Ronsin,J.: Segmentation-Based Motion-Compensated Video Coding Using Morphological Filters. IEEE Trans. on Circuits and Systems for Video Technology, vol.7, no.3, 1997.
3. Salembier,P.- Torres,L. – Meyer,F. – Gu,C.: Region-based video coding using mathematical morphology. Proceedings of the IEEE, vol. 83, no. 6, pp. 843 – 857, 1995.
4. Salembier, P.: Morphological multiscale segmentation for image coding. EURASIP Signal Processing, vol. 38, no. 3, p. 359 – 386, Sept.1994.
5. Mihalík,J. – Gladišová,I.: Implementácia metód segmentácie obrazov. In: Electrical Engineering and Informatics 5; Proceedings of the Faculty of Electrical Engineering and Informatics of the Technical University of Košice, p. 964-968, 2014.
6. Hoover,A. – Baptiste,G.J.: An experimental comparison of range image segmentation algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no.7, 1996.
7. Gladišová,I. – Mihalík,J.: Aplikácia vybraných morfologických transformácii na spracovanie obrazu. In: Electrical Engineering and Informatics 4; Proc. of the Faculty of Electrical Engineering and Informatics of the Technical University of Košice, p. 541 – 546, 2013.
8. Vincent, L. – Soille, P.: Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583 – 598, June 1991.
9. Gladišová,I. – Mihalík,J.: Segmentácia obrazov metódou watershed. In: Electrical Engineering and Informatics 5 : Proceedings of the Faculty of Electrical Engineering and Informatics of the Technical University of Košice, 2014, p. 959-963.
10. Maragos, P.-Schafer, R.W.: Morphological filters – Part I : Their set-theoretic analysis and relations to linear shift-invariant filters. Part II : Their relations to median, order-statistic, and stack filters. IEEE Transactions on Acoustics, Speech and Signal Processing, vol.35, no. 8. pp. 1153 – 1184, Aug. 1987; ibid. vol.37, p.597, Apr. 1989.
11. Chien, S.Y., Ma,S.Y., Chen, L.G.: Efficient Moving Object Segmentation Algorithm Using Background Registration Technique. IEEE Trans. on Circuits and Systems for Video Technology, vol.12, no.7, 2002.

---

Spoluautormi článku sú Ján Mihalík a Jaroslav Petráš, Katedra elektroniky a multimediálnych telekomunikácií, Fakulta elektrotechniky a informatiky, Technická univerzita Košice