Vysoké učení technické v Brně

Fakulta informačních technologií

Ústav počítačové grafiky a multimédií

Obrazové segmentační techniky

Přehled existujících metod

Datum: 12.10.2005 Poslední změna: 19.1.2006

Ing. Michal Španěl Ing. Vítězslav Beran

Abstrakt

Klíčovým krokem většiny systémů pro zpracování obrazu je segmentace obrazu. Jejím úkolem je rozlišit jednotlivé objekty v obraze. Segmentovaný obraz je následně využíván pro rozpoznávání objektů, klasifikaci a jejich další zpracování. V průběhu let bylo publikováno mnoho rozličných segmentačních metod. Od jednoduchých algoritmů po velmi složité. Od obecných postupů po specializované algoritmy vyvíjené pro konkrétní úlohy. Hlavním cílem této dokumentace je předložit čtenáři pokud možno komplexní přehled existujících segmentačních technik.

Klíčová slova

Zpracování obrazu, segmentace obrazu, medicínská obrazová CT/MR data, rozšířená uživatelská realita.

Poděkování

Tato studijní dokumentace vznikla jako výstup grantu s názvem Využití obrazových segmentačních technik pro rekonstrukci 3D modelů objektů z obrazu, který v roce 2005 finančně podporoval Fond rozvoje vysokých škol. Děkujeme.

Obsah

Obsah. 3

1 Úvod. 4

2 Zpracování obrazu. 5

2.1 Základy zpracování obrazu. 5

2.2 Předzpracování obrazu pro segmentaci 7

3 Segmentace obrazu. 8

3.1 Definice segmentace. 8

3.2 Možné přístupy k segmentaci 8

3.3 Úskalí a problémy segmentace. 10

3.4 Segmentace medicínských obrazových dat 10

3.5 Segmentace v rozšířené realitě. 13

4 Segmentační techniky. 16

4.1 Detekce hran (edge-based metody) 16

4.2 Region-based techniky. 27

4.3 Statistické metody. 28

4.4 Hybridní metody. 38

4.5 Znalostní metody. 44

5 Závěr 47

Literatura. 48

1 Úvod

Zpracování obrazu je jedna z perspektivních oblastí počítačové grafiky. Díky rozvoji počítačových technologií a velkému rozmachu digitální techniky (fotoaparáty, kamerové systémy) nabývá zpracování obrazu na velkém významu. Své uplatnění nalézá v průmyslových aplikacích, bezpečnostních systémech, ale i v digitální fotografii.

Klíčovým krokem většiny systémů pro zpracování obrazu je segmentace obrazu. Jejím úkolem je rozlišit jednotlivé objekty v obraze. Výsledky segmentace jsou využívány například pro rozpoznávání a klasifikaci objektů. V průběhu let bylo publikováno mnoho rozličných segmentačních metod. Od jednoduchých algoritmů po velmi složité. Od obecných postupů po specializované algoritmy vyvíjené pro konkrétní úlohy zpracování obrazu.

Hlavním cílem této dokumentace je předložit čtenáři pokud možno komplexní přehled existujících segmentačních technik. Popisované metody však budeme zkoumat i z pohledu dvou velmi specifických oblastí zpracování obrazu. Obě se zabývají tvorbou modelů objektů z obrazových dat. V prvním případě se vytvořené modely používají pro zkvalitnění systémů virtuální a rozšířené reality. Ve druhém případě se jedná o tvorbu 3D modelů lidských tkání a kostí z medicínských obrazových CT/MR dat. Přestože se na první pohled jedná o zcela rozdílné problémy, mohou být některé segmentační algoritmy užitečné v obou případech.

V následující krátké kapitole se věnujeme základům zpracovaní obrazu. Dozvíte se co je to obraz a jak vzniká. Dále jsou v kapitole zmíněny některé techniky předzpracování obrazu často používané pro zkvalitnění následné segmentace. Může se jednat o odstranění šumu v obraze, potlačení vlivu nerovnoměrného osvětlení a další.

Třetí kapitolka rozvíjí problematiku segmentace obrazu, navrhuje jednoduchou klasifikaci segmentačních technik a poukazuje na některé problémy spojené se segmentací.

Vypracovaný přehled segmentačních metod tvoří kapitolu čtvrtou. Každý algoritmus či postup je krátce představen textem i příklady, jsou doplněny odkazy na další studijní prameny a jsou popsány základní vlastnosti metody a možnosti její aplikace.

První kapitola práce má název Úvod. Slouží k zasazení řešené problematiky do širšího kontextu a v podobě stručného obsahu jednotlivých kapitol definuje strukturu písemné práce.

2 Zpracování obrazu

Předmětem zpracování a případného rozpoznávání obrazu je obrazová informace o reálném světě, která do počítače vstupuje nejčastěji televizní či jinou kamerou. Cílem je porozumění obsahu obrazu. Postup zpracování a rozpoznávání obrazu reálného světa lze obvykle rozložit do několika základních kroků:

ˇ Snímaní a digitalizace obrazu

ˇ Předzpracování obrazu

ˇ Segmentace obrazu

ˇ Porozumění obsahu obrazu

Prvním krokem zpracování obrazu je snímání a digitalizace obrazu. Získaný obraz je v číselné formě uložen do počítače. Vstupní informací může být jas (z kamery, scanneru), nebo několik spektrálních složek (nejčastěji červená, zelená a modrá) při barevném snímání. Digitalizací se převádí vstupní analogový signál do diskrétního tvaru. Vstupní signál je popsán funkcí f(x,y) dvou proměnných - souřadnic v obraze. Funkční hodnota odpovídá např. jasu. Vstupní signál je vzorkován a kvantován. Výsledkem je matice čísel popisujících obraz - digitální obraz. Jednomu prvku matice se říká obrazový element, nebo-li pixel.

Druhým základním krokem je předzpracování obrazu. Cílem předzpracování je potlačit šum a

zkreslení vzniklé při digitalizaci a přenosu obrazu. Jindy se předzpracování snaží zvýraznit určité rysy obrazu podstatné pro další zpracování. Příkladem může být hledání hran.

Třetím a asi nejtěžším krokem postupu zpracování je segmentace, která dovolí v obraze rozlišit jednotlivé objekty. Za objekty lze považovat ty části obrazu, které nás z hlediska dalšího zpracování zajímají.

Kvalitní segmentace je klíčovým krokem pro porozumění obsahu obrazu a většinu vyšších metod zpracování obrazu. Typickými problémy jsou detekce a rozpoznávání objektů v obraze, tvorba modelů objektů v obraze a další.

2.1 Základy zpracování obrazu

Nejprve pár slov k literatuře. Literatury zabývající se zpracováním obrazu je bezpočet, zaleží jen na konkrétní oblasti vašeho zájmu. K podrobnějšímu studiu technik zpracování obrazu mohu doporučit česky psané knihy [Hlavac92, Jan97] věnované počítačovému vidění a zpracování obrazu. Ze zahraniční literatury můžete sáhnout po [Sonka98, Forsyth03, Russ98].

Výklad problematiky segmentace obrazu se opírá o některé základní pojmy, které je třeba vysvětlit. První pojem obraz už známe, podívejme se na některé další.

Konvoluce

Důležitou operací při lineárním přístupu ke zpracování obrazu je konvoluce. Konvoluce dvourozměrných spojitých funkcí f a h je definována integrálem

,

kde funkce se nazývá konvolučním jádrem.

Při práci s digitálním obrazem se používá tzv. diskrétní konvoluce, která je diskrétní dvojrozměrnou podobou předchozího vztahu,

.

V tomto případě je I(x,y) diskrétní obraz a h(x,y) jádro konvoluce.

Lineární filtrace

Část operací předzpracování obrazu se nazývá filtrace. Jedná se o metody využívající pro výpočet jasu bodu ve výstupním obraze jen lokálního okolí odpovídajícího bodu ve vstupním obraze. Na filtraci lze také pohlédnout jako na diskrétní konvoluci. Přičemž konvoluční jádro definuje použité lokální okolí. V mnoha praktických případech se využívá pravoúhlého okolí. Aby bylo použité okolí symetrické vůči jeho středovému elementu, volí se nejčastěji rozměry okolí z množiny lichých přirozených čísel.

Konvoluční lineární operace (lineární filtry) jsou použitelné pro vyhlazování i detekci hran (gradientní operace). Vyhlazování obrazu vede k potlačení vyšších frekvencí obrazové funkce. Žádaným výsledkem vyhlazování je potlačení náhodného šumu. Současně naneštěstí dochází k potlačení ostatních náhlých změn jasové funkce, nebo-li k rozmazání hran. Příkladem vyhlazování je například obyčejné průměrování. Každému bodu přiřazuje nový jas, který je průměrem původních jasů ve zvoleném okolí. V některých případech se zvyšuje váha středového bodu masky (konv. jádra) nebo jeho sousedů, aby se lépe aproximovaly vlastnosti šumu s Gaussovským rozložením. Příkladem často používaných průměrovacích filtrů jsou

, .

Výsledek průměrování obrazu filtrem s konvolučním jádrem velikosti 7 je patrný na následujícím obrázku.

Obrázek 1: Filtrace obrazu průměrovacím filtrem - konvolučním jádro velikosti 7.

Gradientní operace a s nimi těsně související ostření obrazu naopak vedou ke zdůraznění vyšších frekvencí. Současně jsou zvýrazněny ty obrazové elementy, ve kterých se jasová funkce náhle mění a má zde velký modul gradientu. Žádaným výsledkem je zvýraznění hran v obraze. Bohužel jsou zvýrazněny i šumové body. Z uvedeného srovnání vyhlazovacích a ostřících operací je patrná jejich protichůdnost. Řešení tohoto rozporu umožňují některé algoritmy, které oba postupy kombinují.

2.2 Předzpracování obrazu pro segmentaci

Segmentace je velmi složitý proces. Její náročnost souvisí nejen s charakterem a vlastnostmi objektů v obraze. Úspěšnou segmentaci do značné míry ovlivňují i vstupní data. Velký podíl šumu nebo nerovnoměrné rozložení jasu v obraze mohou segmentaci úplně znemožnit. V těchto případech můžeme vhodným předzpracováním vstupního obrazu vylepšit výsledky segmentačního algoritmu.

ˇ Filtrace a odstranění šumu

ˇ Adaptivní filtrace

ˇ Anizotropní filtry

ˇ Potlačení vlivu osvětlení a jiných nehomogenit

3 Segmentace obrazu

Obecná definice segmentace říká, že je to proces dělení obrazu do částí, které korespondují s konkrétními objekty v obraze. Jinými slovy, každému obrazovému pixelu je přiřazen index segmentu vyjadřující určitý objekt v obraze. Segmentace je jeden z nejdůležitějších kroků analýzy obrazu. Informaci o rozdělení obrazu do jednotlivých segmentů využívají vyšší algoritmy zpracování obrazu. Snaží se porozumět obsahu obrazu. Konkrétním úkolem může být detekce přítomnosti příslušného objektu nebo nalezení a klasifikace objektů v obraze. Precizní segmentace je důležitá i pro 3D modelování objektů.

3.1 Definice segmentace

Segmentace obrazu je jeho dělení na podobrazy tak, že podobrazy splňují následující kritéria:

1. ,

2. ,

3. Každý podobraz splňuje nějaké tvrzení, popř. množinu tvrzení, např:

ˇ všechny pixely v podobraze mají stejnou úroveň šedi,

ˇ všechny pixely v podobraze se neliší v úrovni šedi více než o předepsanou hodnotu,

ˇ standardní odchylka úrovni šedi všech pixelů poddobrazu je dostatečně malá, apod.

3.2 Možné přístupy k segmentaci

V průběhu let bylo publikováno mnoho segmentačních algoritmů. V této kapitole se pokusíme navrhnout jednu z možných klasifikací známých algoritmů. V první řadě se zaměříme na obecné segmentační techniky. K segmentaci je možné přistoupit několika základními způsoby. Podle přístupu dělíme segmentační algoritmy na

ˇ Metody vycházející z detekce hran (angl. edge-based) - Metody orientované na detekci významných hran v obraze. Lokální hrany jsou detekovány pomocí hranových detektorů na základě rozdílu hodnot okolních pixelů. Hranový detektor je algoritmus, který produkuje množinu hran (bodů, pixelů, nebo fragmentů) v obraze. Existuje mnoho hranových detektorů. Podrobněji budou popsány později.

ˇ Metody orientované na regiony v obraze (region-based) - principiálně jsou stejné jako edge-based metody. Pokud lze identifikovat hrany, měly by teoreticky ohraničovat regiony nalezené region-based segmentací. Kontury regionů však mohou být porušené, nemusí ohraničovat celý region. Ani v opačném případě není zaručeno, že hranice regionů nalezené edge-based metodou budou stejné jako ty nalezené region-based metodou. A v praxi také nejsou stejné.

ˇ Statistické metody - v tomto případě je základem segmentace statistická analýza obrazových dat, nejčastěji hodnot pixelů. Strukturní informace je obvykle zanedbávána.

ˇ Hybridní metody - některé segmentační techniky je těžké zařadit do jedné z předchozích tří kategorií, protože obsahují prvky každé z nich. Mluvíme tedy o tzv. hybridních metodách. Mezi hybridní řadíme také metody založené na matematické morfologii. Jedná se o skupinu metod, která pro segmentaci využívá matematických charakteristik obrazu, např. průběh gradientu.

ˇ Znalostní (knowledge-based) metody - Znalost vlastností segmentovaných objektů (tvar, barva, struktura, apod.) mohou segmentaci značně ulehčit. Metody patřící do této kategorie využívají atlas předloh či modelů segmentovaných objektů (v případě medicínských dat to může být atlas lidských tkání). Atlas je generován automaticky ze souboru trénovacích dat, nebo jsou do něj informace vloženy ručně, na základě lidské zkušenosti. V průběhu segmentace algoritmus hledá transformaci známých objektů, šablon v atlasu, na objekty nalezené v obraze. Tento proces se obvykle nazývá atlas-warping a nejčastěji využívá lineární transformace.

Pro klasifikaci segmentačních technik zavedeme několik pomocných kritérií. Prvním z nich je charakter zpracovávaných obrazových dat

ˇ 2D obrazové algoritmy - Klasické obrazové algoritmy zpracovávající dvourozměrná obrazová rastrová data.

ˇ 3D objemové algoritmy - Pracují s 3D rastrovými daty. Ponejvíce se jedná o medicínská CT/MR data.

ˇ Algoritmy nezávislé na typu dat, často se jedná o statistické metody.

Z hlediska složitosti a obtížnosti implementace, budeme segmentační techniky rozlišovat na

ˇ Základní - jednoduché metody, jejichž sílu však není třeba podceňovat. Mnohdy jsou lepší a efektivnější volbou než složité segmentační algoritmy.

ˇ Pokročilé metody - pro jejich pochopení je nutné mít dobré znalosti základů zpracování obrazu. Obvykle kladou větší nároky na implementaci.

ˇ Speciální - Úzce specializované segmentační techniky, které vyžadují podrobné znalosti dané problematiky a metod zpracování obrazu!

Vhodnost metod pro konkrétní typ segmentační úlohy budeme posuzovat samostatně. U každé metody by mělo být uvedeno jaký typ obrazových dat je schopna zpracovat, jaké jsou její vlastnosti vzhledem k různým typům šumu atd. Nejvíce nás budou zajímat medicínské aplikace a použitelnost metody pro segmentaci objektů v rozšířené realitě.

3.3 Úskalí a problémy segmentace

Proč je segmentace složitý problém? Prvním aspektem je samotný proces pořizování obrazové informace. Získaná data jsou obvykle deformovaná šumem, nebo nehomogenním osvětlením. Objekty mohou být velmi složité, jejich hranice se mohou překrývat atd. V takovém případě je rozlišení jednotlivých objektů obtížné i pro trénované lidské oko, natož pro počítačový algoritmus.

Zvláštní kapitolou jsou medicínská obrazová data. Přestože výběr zobrazovací metody (CT, MR, ultrazvuk, …) odpovídá požadovanému typu vyšetření, není zaručeno, že složitá anatomická struktura tkání bude dobře separovatelná. Hranice tkání nemusí být zřetelné vlivem šumu, nehomogenit a artefaktů vznikajících při pořizování dat.

3.4 Segmentace medicínských obrazových dat

Úspěchy moderní medicíny ukazují, jak lze technický pokrok využít v praxi. Pomocí medicínských zobrazovacích systémů, např. počítačové tomografie (angl. Computer Tomography - CT) nebo magnetické rezonance (Magnetic Resonance - MR), mohou lékaři vyšetřit pacienta zevnitř, bez jediného řezu skalpelem. Tato zařízení produkují obrazová data popisující strukturu a vlastnosti tkání ve zkoumané části lidského těla. Medicínská data ve formě obrazových řezů jsou často používána k diagnostickým účelům. Typickým příkladem je rentgenový snímek zlomeniny kosti.

Obrázek 2: Segmentace obrazu jednoduchým prahováním histogramu. Segmentovaný MR řez obsahuje tři různé oblasti (typy pixelů): kosti, měkké tkáně a světlé pozadí.

Medicínská CT/MR obrazová data

Na medicínská obrazová CT/MR data můžeme nahlížet tradiční cestou zpracování obrazu. Důležitým krokem takového zpracování je segmentace obrazu, v tomto případě segmentace jednotlivých typů tkání. Kvalitní segmentace hraje klíčovou roli v nových metodách zpracování medicínských dat, mezi které patří automatické rozpoznávání typů tkání, 3D modelování tkání či kostí a vizualizace.

Počítačová tomografie (CT)

Nejpoužívanější medicínské zobrazovací metody jsou právě počítačová tomografie a magnetická rezonance. Počítačová tomografie je moderní vylepšení tradičního rentgenového vyšetření. Rentgenové paprsky procházejí lidským tělem v různých úhlech. Každý obrazový pixel je pak rekonstruován z několika měření z různých úhlů. Nulová hodnota pixelu odpovídá hustotě vody. Ve stejném duchu, různé hodnoty intenzit odpovídají různým typům tkání v lidském těle. Počítačová tomografie poskytuje dobrou informaci o anatomické struktuře orgánů a měkkých tkání, ale je velmi citlivá na rozdíly v hustotě tkání.

Obrázek 3: Ukázkový CT a MR řez lidskou hlavou. Všimněte si prázdných/černých míst v MR řezu (vpravo). Pamatujte, kosti neovlivňují MR signál.

Magnetická rezonance (MR)

Základní rozdíl mezi CT a MR je fyzikální podstata měření. Magnetická rezonance produkuje informaci o chemické povaze tkání. Rozdílné intenzity odpovídají různé hustotě atomů vodíku. Teoretické základy metoda nalezla v nukleární fyzice. Základní výhodou magnetické rezonance je dobrá rozlišovací schopnost měkkých tkání. Kromě toho, kosti nijak nenarušují měřený signál (Obrázek 3). Z těchto důvodů se MR používá zejména pro vyšetření měkkých tkání, k odhalování patologických změn, např. zhoubných nádorů.

Medicínská CT/MR data jsou produkována jako série rovinných řezů skrze vyšetřovanou část pacientova těla. Z takové série obrazových řezů lze sestavit objemová 3D data a zpracovávat je specializovaným 3D segmentačním algoritmem.

Medicínské aplikace

Medicínská CT/MR data jsou používána především k diagnostickým účelům. V mnoha případech není klasický způsob vyšetření pomocí "šedotónových obrázků" dostatečný. Rozvoj zobrazovacích metod nám umožňuje zkoumat i jiné možnosti jejich zpracování. Nejčastěji se jedná o metody vizualizace CT/MR dat, 3D modelování tkání, plánování a simulaci operací, navigaci lékařů při zákrocích a mnoho dalších.

Transparentní zobrazení segmentovaných CT/MR dat je významné pro stanovení přesné lékařské diagnózy. Současný výzkum v této oblasti se soustřeďuje na množství metod tzv. volume renderingu (Obrázek 4) a techniky 3D modelování tkání.

Obrázek 4: Vizualizace CT dat pomocí volume renderingu. Obrázky jsou převzaty z článku [Bullit02] publikovaného na konferenci IEEE Transactions on Medical Imaging 2002.

Termín volume rendering označuje techniky zobrazení trojrozměrných dat. Data jsou tvořena 3D mřížkou, diskrétním objemem. Každý objemový element - voxel je popsán souřadnicemi, hodnotou a velikostí. Reálné velikosti voxelů závisí na rozlišení a nastavení použité metody vyšetření. Přínos trojrozměrného zobrazení dat oproti klasickým 2D řezům je zřejmý. Segmentované tkáně mohou být zkoumány z jakéhokoliv pohledu. Vyšetření je jednodušší a mnohem přesnější.

Obrázek 5: Geometrický model lidské lebky. Zleva: výsledek metody Marching Cubes, model po vyhlazení a redukci počtu polygonů. Obrázky dodány P. Krškem, který se intenzivně věnuje problematice tvorby 3D modelů tkání a jejich klinickým aplikacím na Ústavu počítačové grafiky a multimédií FIT VUT v Brně.

Diskrétní objemová a segmentovaná CT/MR data tvoří základ pro techniky geometrického 3D modelování tkání. Ze segmentovaných medicínských dat jsou vytvořeny trojrozměrné povrchové modely jako na Obr.. Výhoda povrchové reprezentace je stejná jako v případě volume renderingu. Lékař získá mnohem lepší představu o anatomii. Kromě toho mohou počítačové modely posloužit k tvorbě reálných modelů, které lékaři používají pro plánování složitých operací, přípravu umělých náhrad apod. Ke tvorbě povrchových modelů se často používá algoritmus zvaný Marching Cubes (Obrázek 5).

3.5 Segmentace v rozšířené realitě

Rozšířená realita je technologie, která se snaží odstranit nedostatky virtuální reality. Na rozdíl od virtuální reality, rozšířená realita nevytváří kolem uživatele umělé prostředí, ale pouze rozšiřuje pohled. Objekty vytvořené počítačem jsou vloženy do obrazu reálné scény, takže realističnost a autenticita pohledu na scénu zůstává. Jako příklad využítí uveďme zobrazení elektrického vedení ve zdech (Obrázek 6 vlevo), zobrázení plánované cesty při průchodu městem i s popisky památek a významných objektů (Obrázek 6 uprostřed) nebo v medicínských aplikacích, jak pro studijní účely tak pro zobrazování důležitýh informací přímo v reálné scéně.

Obrázek 6: Příklady rozšířené reality.

Další oblastí, kde použití rozšířené reality přináší kvalitnější interakci počítače se člověkem je uživatelské prostředí pro vzdálenou spolupráci. Jako příklad poslouží videokonferenční hovory, kdy je vzdálený uživatel zobrazen jako obrázek na obrazovce. S použitím rozšířené reality a náležitým vybavením (virtuální brýle a kamery) můžeme obraz vdáleného uživatele umístit kamkoli do scény našeho okolí. Uživatel pak vidí své reálné okolí a v něm obraz (video) vzdáleného uživatele. Dalším vylepšením příkladové aplikace je, když se pokusíme místo plochého obrazu vzdáleného uživatele zobrazovat jeho model. Jelikož k dispozici není přesný model uživatele, použijeme simulovaný model člověka, který upravíme podle tvaru siluety uživatele. Zobrazení modelu uživatele přináší oproti zobrazení pouze jeho obrazu lepší zdání komunikace s člověkem, než jenom s jeho obrazem. Struktura rozmístění kamer a příklad vodící značky je vidět na následujícím obrázku, kde kamera umístěná na hlavě uživatele zobrazuje obraz reálné scény do virtuálních brýlí a detekuje značku a kamera na stěně slouží k vytvoření modelu uživatele.

Obrázek 7: Struktura rozšířeného uživatelského rozhraní pro vzdálenou spolupráci.

V popsaném procesu umístění virtuálního objektu do reálné scény a vytvoření modelu uživatele je třeba nejdříve získat potřebné informace z obrazu. Má-li být do reálné scény umístěn virtuální objekt, nejjednodušší definice jeho polohy ve 3D prostoru je použití speciální značky (např. papírové kartičky se speciálním vodícím znakem). Ta pak je v obrazu detekována a ze znalosti jejího tvaru a perspektivního zkreslení se pak vypočítá poloha této značky v 3D prostoru. Vypočtená poloha a orientace značky pak slouží k přesému umístění virtuálního objektu, který nahradí detekovanou značku. Proces detekce značky a umístění modelu uživatele je naznačen na následujícím sledu obrázků.

Obrázek 8: Postup detekce vodících značek a umístění virtuálních objektů.

V procesu tvorby modelu uživatele je nutné oddělit uživatele od pozadí, provést analýzu jeho tvaru a vytvořit simulovaný reliéfní model člověka, na který se nakonec namapuje obraz uživatele. Proces je opět naznačen na obrázku.

Obrázek 9: Detekce uživatele v obraze, jeho separace od pozadí a tvorba reliéfního modelu.

Oba tyto postupy používají techniky pro zpracování obrazu, kde stěžejní částí je právě segmentace - segment s vodícím znakem a segment uživatele.

4 Segmentační techniky

V předchozí kapitole jsme existující segmentační techniky rozdělily do několika skupin. Pojďme se podívat na jejich typické zástupce, obrazové segmentační techniky.

4.1 Detekce hran (edge-based metody)

Detekce hran je jednou z nejdůležitějších oblastí nižší úrovně zpracování obrazu i přes to, že v reálných scénách je to složitý a dosud nevyřešený problém. Hranami rozumíme body obrazu, u kterých se hodnota jasu prudce mění. Hranu můžeme chápat jako vlastnost obrazového bodu započteného jako funkci obrazu v okolí tohoto bodu. Hrana je pak reprezentovaná velikostí a směrem.

Změny či přerušení v jasu obrazu jsou jedny z nejzákladnějších charakteristik obrazu, protože naznačují fyzické rozmístění objektů v obraze. Lokální změny jasu obrazu z jedné úrovně na jinou se nazývají jasové hrany a globální změny pak jasové hraniční segmenty.

Model ideální hrany může být skoková (angl. step) funkce. V reálných obrazech je změna jasu postupná, nikoli skoková, takže je vhodnější použít šikmou (ramp) funkci. Pokud se obě definované funkce objeví v obraze vedle sebe, vznikají ještě další dva typy hran: čára (line) a střecha (roof). Jednotlivé typy hran jsou znázorněny na následujícím obrázku.

Obrázek 10: Typy hran v obraze. Zleva: step, ramp, line a roof.

Proces detekce hran se dá rozdělit na tři fáze: filtrování, diferenciace a detekce. Šum vzniklý při vzorkování obrazu, kvantování, rozmazání či nevhodném nastavení kamery může být částečně odstraněn vhodným filtrem. Diferenciace pak zvýrazní oblasti v obraze, kde je změna intenzity jasu obrazu významná. Nakonec jsou detekovány a lokalizovány body, kde je změna intenzity nejvýznamnější.

Hranové detektory

Základní metody detekce hran se dají rozdělit do dvou hlavních skupin. Metody využívající první derivaci nebo druhou derivaci. Při použití první derivace je výsledný hranový gradient je porovnán s prahem, který určuje, jedná-li se o hrany či nikoli. U metod druhé derivace je výskyt hrany detekován, je-li prostorová změna v polaritě druhé derivace dostatečně významná.

Detekce pomocí první derivace

První derivaci diskrétního obrazu získáme jako rozdíl okolních pixelů obrazu. Slovo okolních nemusí přímo znamenat sousedních. V nejjednodušším případě vypočítáme derivaci pro řádky, resp. sloupce zvlášť. Bereme sousední pixely zleva doprava, resp. shora dolů. Výsledný gradient pak vypočteme jako:

nebo můžeme kvůli výpočetní složitosti hodnotu následovně aproximovat:

V některých případech vede tato aproximace k rapidnímu zhoršení výsledku. Orientaci gradientu v obraze vzhledem k řádkům určíme jako:

K výpočtu gradientu můžeme přistupovat jako ke konvolučnímu filtrování signálu (obrazu). Jednotlivé hranové detektory se pak liší jádrem konvolučního filtru. Jádro filtru udává, které body se pro výpočet gradientu použijí a jaké budou mít váhy. Vlastnosti filtru, jeho velikost a hodnoty významně ovlivňují výsledné vlastnosti hranového detektoru. Tzv. gradientní obraz získáme konvolucí mezi originálním obrazem a jádrem filtru. Impulsní charakteristiky významných filtrů jsou na následujícím obrázku.

Obrázek 11: Konvoluční jádra významných hranových detektorů.

Velikost jádra filtrů tohoto typu významně ovlivňuje jejich citlivost na šum. Proto existují některé uvedené filtry i s jádrem 5x5 nebo 7x7.

Další množinou hranových filtrů jsou detektory s váhovací funkcí Gaussovského tvaru. Argyle [Argyle71] (Rov. 1), resp. Macleod [Macleod70, Macleod72] (Rov. 2) navrhli filtry, které snižují váhy jednotlivých pixelů obrazu s jejich vzdáleností od středu. Níže jsou uvedeny definice filtrů pomocí Gaussovské funkce se střední odchylkou G(x,s) pro řádky, pro sloupce jsou vzorce podobné.

, resp. (Rov. 1)

(Rov. 2)

Výsledná odezva gradientních operátorů se pak získá složením řádkových a sloupcových operátorů pomocí konvoluce:

.

Další dobře známý příklad je operátor první derivace Gaussovské funkce.

Všechny uvedené operátory pro zvýraznění hran byly vyvynuty heuristicky. Analytický přístup zvolil Canny [Canny86]. Impulsní odezva Cannyho operátoru je nastavená tak, aby co nejlépe vyhovovala následujícím podmínkám:

ˇ Dobrá detekce - velikost poměru signál-šum je co největší, aby pravděpodobnost selhání výběru hrany byla co nejmenší.

ˇ Dobrá lokalizace - vybrané hranové body by měly být co nejblíže středu hrany.

ˇ Jedinečná odezva - měla by existovat jen jedinečná odezva na skutečnou hranu.

Analytická realizace není kvůli složitosti podmínek možná. Cannyho operátor je proto realizován různými způsoby, které se snaží co nejlépe vyhovět stanoveným podmínkám. Jednou z možností je využití operátoru první derivace Gaussovské funkce, adaptivním prahováním a techniky potlačení nemaximálních hodnot (non-maxima suppression).

Až doposud jsme počítali gradient ve dvou kolmých směrech. Dalším rozšířením může být výpočet gradientu ve více směrech s použitím konvoluce a šablon. Výsledný gradient je pak definován jako:

,

kde je

.

Úhel hrany je pak určen směrem největšího gradientu. Ukázky možných šablon a jejich tvaru pro jednotlivé směry jsou obrázku.

Obrázek 12: Šablony a jejich směry hranových detektorů.

Výsledný gradientní obraz se často dále zpracovává například morfologickými operátory pro ztenčení hran či jejich skeletonizaci. Nevýhodou uvedených operátorů je velká závislost na velikosti objektu v obraze a citlivost na šum.

Detekce pomocí druhé derivace

Při použití druhé derivace se používá detekce průchodu nulou. Je totiž mnohem jednodušší nalézt průchod nulou než extrém (viz. Obrázek 13).

Obrázek 13: Ukázka průchodu nulou u 1D funkce.

Laplacian je jedním z operátorů využívající druhou derivaci a má stejné vlastnosti ve všech směrech, díky čemuž je invariantní vůči rotaci:

.

Normalizovaná impulsová odezva Laplacianu se 4-okolím, 8-okolím a separabilní s 8-okolím je na následujícím obrázku.

Obrázek 14: Příklady normalizovaného Laplacianu.

Nevýhodou Laplaciánu je dvojitá odezva na některé hrany v obraze. Marr a Hildrith [Marr80] navrhli Laplacián Gaussovské funkce jako:

.

Tato funkce je aproximovatelná funkcí diferenciálu Gaussovské funkce:

.

Další nevýhodou metod druhé derivace detekující průchod nulou je příliš velké vyhlazení obrazu, ztráta ostrých rohů, a sklon vytvářet uzavřené smyčky hran. Tímto nejsou ani zdaleka vyčerpány možnosti filtrů a operátorů detekující či zvýrazňující hrany v obraze. Za ty další uveďmě například modelování tzv. facetů.

Následuje skupina hranových detektorů, které se snaží vytvořit parametrický model hrany z funkce obrazu. Tyto metody popisují hrany s větší přesností, avšak jsou výpočetně mnohem náročnější.

Houghovy transformace

Houghova trasformace byla vyvnuta k reprezentaci čar a rovinných křivek. Obrovskou výhodou této metody je její robustnost, kdy segmenatce není příliš citlivá na porušená data nebo šum. Jde o transformaci z Kartézského souřadnicového systému do polárního.

Parametrické vyjádření přímky je:

,

kde r je normalizovaná vzdálenost přímky od počátku a q je úhel vzheldem k ose x. Body obrazu jsou prezentovány křivkami v parametrickém prostoru. Jedná-li se o kolineární body (z jedné přímky), křivky v paramterickém prostoru se nejčastěji protínají právě v bodě reprezentující parametry hledané křivky (přímky).

Obrázek 15: Houghova transformace přímky.

Urychlení algoritmu můžeme dosáhnout použitím hodnoty q již v průběhu detekce hran.

Stejný princip se používá i pro hledání dalších křivek, které je možné popsat parametricky - křivky, elipsy, apod. Houghovy transformace se dá použít i na detekci tvarů, které nejde přímo popsat parametricky - Obecná Houghova tranformace.

Aktivní kontury

Aktivní kontury (snakes, active contours) je metoda postupného tvarování kontur až ke hraně objektu v obraze. Model aktivní kontury je řízená uzavřená kontura, která se deformuje vlivem tzv. vnitřních, obrazových a vnějších sil. Vnitřní síly kontrolují hladkost průběhu, obrazové síly směrují tvarování kontury směrem ke hraně objektu a vnější síly jsou výsledkem počátečního umístění kontury.

Mějme konturu reprezentovanou diskrétně:

.

Výsledná pozice aktivní kontury koresponduje s lokálním minimem energie kontury:

,

kde E_N je vnitřní energie kontury (ohyb, zlom), E_I reprezentuje energii obrazu a E_T energii omezení. Existuje mnoho navržených postupů měření výše uvedených energií [William92, Lam94, Ji99], např. tzv. nenasytný (greedy) algoritmus definuje vnitřní energii kontury jako energii spojitosti E_C a zakřivení E_K:

,

,

,

kde a(n) a b(n) kontrolují elastičnost a tuhost kontury, d je průměrný obvod kontury a v_n(j) reprezentuje osmi-okolí bodu v_n, j=1,2,...8.

Obrázek 16: Aktivní kontury - počáteční stav (vlevo), standardní postup (uprostřed) a modifikovaná verze algoritmu (vlevo).

Standardní algoritmus nedosahuje při složitějších konturách dostatečných kvalit, není schopen se přimknout k prudkým zlomům hranic objektu, vytváří falešné kontury či smyčky. Ji a Yan navrhl modifikovanou verzi, která některé tyto nedostatky odstraňuje.

Název	Aktivní kontury
Kategorie	Pokročílá detekce hran.
Vstupní data	Obrazová diskrétní data.
Výstupní data	Kontura objektu.
Cílové aplikace	Detekce hran objektů v obraze.
Výhody	ˇ Metoda je vhodná i pro složité a komplexní tvary. ˇ Umožňuje nastavení parametrů ovlivňujících výsledný tvar kontury.
Nevýhody	ˇ Nutná manuální inicializace.
Literatura	[William92, Lam94, Ji99]

Level-sets

Obdobný přístup jako aktivní kontury využívá tzv. Level-set segmentace představená pány Osherem a Sethianem [Sethian99]. Křivka je reprezentována tzv. nulovou hladinou - řezem v rovině xy (angl. zero level set) nějakou vícedimenzionální funkcí. Tato funkce se nazývá level set function a každému bodu roviny xy přiřazuje jeho výšku u nad nulovou hladinou (Obrázek 17). Povrch funkce se postupně adaptuje vzhledem k zadaným metrikám křivosti a obrazovým gradientům. Základní rozdíl level-set metody proti klasickým aktivním konturám je ten, že tvar křivky neměníme přímo, ale prostřednictvím level-set funkce.

Obrázek 17: Příklad Level-set funkce (vpravo) pro uzavřenou 2D křivku C.

Obecně lze říci, že Level-set segmentace je efektivnější pro komplexní objekty se složitými tvary. Obě techniky vyžadují manuální inicializaci, která přibližně odpovídá cílovému tvaru křivky.

Obrázek 18: Počáteční, průběžný a koncový stav segmentace testovacích obrázků elipsy metodou Level-set (převzato z [Leventon00]).

Název	Level-sets
Kategorie	Pokročílý edge-based algoritmus pracující ve 3D.
Vstupní data	Obrazová nebo objemová diskrétní data.
Výstupní data	Kontura případně povrchový model objektu.
Cílové aplikace	Tvorba geometrických povrchových modelů anatomických struktur v medicínských obrazových datech.
Výhody	ˇ Metoda je vhodná i pro složité a komplexní tvary. ˇ Umožňuje zavést podmínky křivostí a znalosti tvaru objektu.
Nevýhody	ˇ Nutná manuální inicializace.
Literatura	[Sethian99], [SethianWWW] [Droske01], [Leventon00] [Bankman00] str. 147-156

Isosurfaces

Pro rekonstrukci trojrozměrných povrchových modelů ze vstupních objemových diskrétních dat se často používá algoritmus Isosurface [Lorensen87]. Povrch/kontura modelu je definována propojením voxelů, jejichž intenzity jsou rovny zadané hodnotě (tzv. isovalue). Máme-li objemová data, geometrický polygonální povrch modelu získáme např. metodou Marching Cubes [Krsek01]. Naneštěstí jakýkoliv šum ve vstupních datech má za následek vznik nepříjemných artefaktů v modelovaném povrchu. Běžně se vyhlazují data pomocí trojrozměrných smoothing filtrů, nebo až výsledný povrchový model (např. surface-growing algoritmus).

Obrázek 19: Příklad segmentace povrchu mozku metodou Isosurfaces. Všimněte si rozdílných výsledků pro různé hodnoty isovalue. Obrázek byl převzat z článku [Vivodtzev03].

Název	Isosurfaces
Kategorie	Pokročilý edge-based algoritmus pracující ve 3D.
Vstupní data	Objemová diskrétní data.
Výstupní data	Povrchový geometrický polygonální model.
Cílové aplikace	ˇ Tvorba geometrických 3D povrchových modelů. ˇ Vizualizace 3D dat. (Medicínské aplikace, mechanika kapalin, ).
Výhody	ˇ Poměrně detailní povrchová reprezentace objektů.
Nevýhody	ˇ Vysoká výpočetní náročnost. ˇ Produkuje velký počet trojúhelníků. ˇ Vznik artefaktů ve výsledném povrchovém modelu.
Literatura	[Lorensen87], [Krsek01] a [Vivodtzev03]

4.2 Region-based techniky

Metody detekující přímo oblasti v obraze namísto hranic (hran) těchto oblastí jsou efektivnější pro zašumělý obraz. Je-li v obraze hodně šumu, hranové operátory obtížně detekují hrany. Hlavním segmentačním kritériem pro detekci oblastí v obraze je homogenita oblasti. Kritériem honogenity mohou být: úroveň šedi, barva, textura, tvar, model, apod.

Region growing

Metoda šíření oblasti je konceptuálně nejjednodušším postupem: sousední pixely s podobnou amlpitudou jsou seskupovány k sobě a vytváří segmentovanou oblast. V praxi jsou ovšem pravidla řídící seskupování poněkud složitější.

Při segmentaci jsou nejdříve vytvořeny atomické oblasti pomocí kvantizovaných hodnot pixelů. V následujícím kroku jsou odstraňovány slabé hrany mezi atomickými oblastmi, tj. oblasti jsou spojovány do větších celků, jsou-li splněna definovaná kritéria. Jednotlivé metody se mohou lišit pravidly pro počáteční rozdělení oblastí i kritérii pro jejich následné spojování. Výsledek spojování je též závislý na pořadí, v jakém jsou oblasti spojovány.

Heuristikou ovlivňující proces spojování [Brice70] může být např. síla společné hranice mezi sousedními oblastmi. Je-li hranice slabá, může být tzv. rozpuštěna a oblasti se spojí. Pro testování síly hrany se používá tzv. super-grid, který navíc obsahuje informace o rozdílu hodnot sousedních pixelů (s_i,j). Síla hrany je pak dána:

,

kde T₁ je práh určující, kdy se již jedná o silnou, resp. slabou hranu. Další pravidlo je založené na testování délky obvodů jednotlivých regionů (l_i, l_j) a jejich společné hranice (W, počet slabých hran společné hranice):

,

Posledním zde uvedeným kritériem je:

,

kde l je délka společné hrany.

Split and merge

Metoda dělení a spojování oblastí je založena na quad-tree prezentaci dat, kdy podobraz je rozdělen na čtyři kvadranty pokud jsou jeho měřené atributy nehomogení. Jsou-li některé sousední čtverce homogenní, jsou spojeny v jednu oblast.

Obrázek 20: Princip hierarchie segmnetace split-and-merge.

Nejjednodušším měřením uniformity je rozdíl mezi maximálním a minimálním pixelem v oblasti. Fukada [Fukada80] navrhl rozptyl oblasti jako měřenou veličinu, Chen a Pavlidis [Chen80] pak složitější měření.

4.3 Statistické metody

Prahování

Distribuce úrovní šedi v obraze může pomoci určit práh pro převod obrazu do binární reprezentace - objekt, pozadí. Histogram obsahuje informace o počtu pixelů v obraze s konkrétní hodnotou šedi. Analýzou takového histogramu získáme práh T, resp. množinu prahů T₁,T₂,...T_n pomocí kterých pak můžeme obraz rozdělit na poddoblasti:

, resp.

.

Získání prahu z histogramu ovšem není triviální úlohou. Histogramy reálných obrazů neobsahují ostré hrany a špičky, ale mohou mít několik vrcholů různé výšky a strmosti. K rozpoznání, jedná-li se o "dobrý" vrchol (ostrý a hluboký) můžeme použít poměr plochy vrcholu a plochy jeho obálky (viz. Obrázek 21).

Obrázek 21: Detekce vrcholu histogramu.

kde P a W jsou výška a šířka oblasti vrcholu, V_a a V_b jsou minima okolí vrcholu a N je počet pixelů vrcholu. Následující rovnice nám ohodnotí ostrost a výšku vrcholu (čím menší hodnota, tím lepší):

.

Výsledkem záklandího prahování je binární obraz, tzn. obsahuje pouze dva typy pixelů - je (1) a není (0) objekt. Pro další zpracování je mnohdy důležité najít takové 1-pixely, které jsou ve shlucích. O obecném shlukování pojednává jiná kapitola, zde uvedeme pouze speciální postup pro získání segmentů z binárního obrazu.

Nevýhodou histogramů je, že neobsahují prostorové informace o pixelech, takže obraz složený ze dvou obdélníků, bílého a černého, bude mít stejný histogram jako obraz složený s náhodně roztroušenými černými a bílými tečkami.

Existuje též modifikace nazývaná polo-prahování. Kdy hodnoty pixelů nejsou nahrazeny 0, resp. 1, ale hodnoty větší než je práh zustanou a ostatní se nastaví na 0.

Adaptivní prahování

Adaptivním prahování (též proměnné prahování) se liší od základnáho tím, že hodnota prahu se liší pro různé části obrazu, je funkcí lokálních parametrů obrazu. Obraz je nejdříve rozdělen do několika částí, pro každou část je nalezen práh (prahy jednotlivých oblastí mohou být interpolovány) a nakonec se provede prahování pro každou část s jejím konkrétním prahem.

Connected component labelling

Metoda zpracuje binární obraz tak, že pixely s hodnotou 1, které se vyskytují v propojeném shluku označí společným indexem. Výstupem je pak obraz, kde pixely mají hodnotu indexu segmentu ke kterému patří.

Amplitudová projekce

Obrazové segmenty mohou být někdy vhodně separovatelné vytvořením průměrné amplitudové projekce ve směru řádků a sloupců. Horizontální, resp. vertikální projekce je definována jako:

, resp.

.

Analýza výsledných projekcí může zlepšit detekci objektů ve scéně.

Shluková analýza (clustering)

Metoda shlukování pixelů podobných vlastností je přímo závislá na měření provedených pro každý pixel. Každý pixel je prezentován vektorem obsahujícím výsledky jednostlivých měření pro daný pixel. Měřením mohou být barevné komponenty pixelu, vlasnosti okolí pixelu jako jsou střední hodnota okolních pixelů, rozptyl, apod. Je nutné navrhnout taková měření, aby pixely z jednoho segmentu byly ohodnoceny podobně a z různých segmentů rozdílně. Jinými slovy, data by měly být v pevném shluku v N-rozměrném prostoru.

Mějme příklad, kdy provádíme pouze dvě měření (Obrázek 22). Úkolem segmentace je výpočet počtu shluků a přiřazení jednotlivých vektorů nejbližšímu shluku.

Obrázek 22: Příklad shlukování ve 2D prostoru.

Začneme pouze se dvěma shluky, každému přiřadíme vektory, které jsou shluku nejblíže a vypočteme, zda je nutné přidat další shluk. Pokud ano, vytvoříme nový shluk se středem v nejvzdálenějším vektoru a proces opakujeme. Nalezení kritéria pro přidání dalšího sluku ovšem není triviální.

Jednou z možností je použití faktoru kvality [Coleman79], který se počítá v každém kroku a řídí počet výsledných shluků (při dosažení maximální hodnoty faktoru proces končí). Faktor se počítá jako:

,

kde S_W, resp. S_B jsou roptýlené matice vypočteny následovně:

,

,

,

kde K je počet shluků, M_k je počet vektorů přiřazených k-tému shluku, u_k je střední hodnota shluku, S_k je množina vektorů přiřazených k-tému shluku, u₀ je střední hodnota všech vektorů a M' je počet pixelů určených pro shlukování.

Postup je podrobně popsán v práci Colemana a Andrewse [Coleman79].

Název	Shluková analýza
Kategorie	Základní statistická metoda segmentace.
Vstupní data	Obrazová i objemová diskrétní data.
Výstupní data	Segmentovaná diskrétní data.
Cílové aplikace	Jakákoliv shluková analýza dat.
Výhody	ˇ Jednoduchá snadno rozšiřitelná metoda. ˇ Mnoho modifikací a postupů.
Nevýhody	ˇ Problém stanovení cílového počtu shluků. ˇ Závislost výsledné segmentace na počátečním nastavení - výběru prvních shluků.
Literatura	[Coleman79], [Haralick69]

Kohonenovy mapy

Kohonenovy mapy [Novak98] jsou neuronové sítě typu SOM (Self-organizing Maps). Využívají soutěžní strategie učení (competitive learning). Principem tohoto modelu je, že výstupní neurony sítě spolu soutěží o to, který z nich bude aktivní. V určitém čase je tedy aktivní pouze jeden neuron. Důležitou vlastností těchto sítí je shlukovaní. Vstupy sítě jsou tříděny do skupin dle vítězného (aktivního) neuronu.

Každý neuron výstupní vrstvy je v kohonenově mapě propojen vazbou se všemi neurony vrstvy vstupní (Obrázek 23). Charakteristickou vlastností každé vazby je její váha w. Index vítězného neuronu pak odpovídá číslu segmentu v obraze. Vstupem sítě může být jas pixelu, případně další příznaky extrahované z obrazu.

Obrázek 23: Architektura 1D Kohonenovy mapy - SOM neuronové sítě (viz. [Wu01]).

Soutěžení výstupních neuronů spočívá ve výpočtu vzdálenosti vektoru vah každého neuronu od vstupního neuronu. Neuron s nejnižším výstupem je prohlášen za vítěze a právě jeho index c je pro nás podstatný. Vzdálenost obou vektorů lze spočítat jako Eukleidovskou vzdálenost, nebo jako pouhý rozdíl obou vektorů:

.

Učení sítě probíhá následujícím způsobem. Postupně procházíme celou tréninkovou množinu a při předložení jednoho tréninkového vzoru dochází ke kompetici neboli soutěži neuronů. Po vyhodnocení vítězného neuronu jsou pak upravovány váhy nejen tohoto neuronu, ale i neuronů v jeho okolí. Smyslem takového postupu je posunutí váhových vektorů neuronů v okolí vítěze směrem k aktuálnímu vstupu tak, aby tyto neurony ještě více vylepšily svou pozici vůči novému tréninkovému vzoru. Samotná adaptace vah se pak řídí podle vztahu:

kde c je index vítězného neuronu a jsou parametry učení. Reálný parametr určuje míru změny vah, na počátku učení je blízký jedné a postupně se zmenšuje. Velikost s okolí byla na počátku učení velká (srovnatelná s velikostí sítě) a postupně klesá až na hodnotu 0. Tento způsob učení je označován také jako učení bez učitele.

Jedním z problémů většiny clusterovacích algoritmů je počet shluků a tedy i počet výstupních neuronů. Úspěšnost těchto metod značně závisí na složitosti vstupu (počtu shluků ve vstupu) a zvoleném počtu shluků. Větší počet neuronů znamená lepší rozlišovací schopnosti, bohužel při nižším počtu shluků ve vstupním obraze jen obtížně nalezneme odpovídající správně segmentovaný obraz. Toto platí i pro opačný případ, kdy počet shluků ve vstupním obraze je vysoký, avšak síť se snaží třídit pixely do příliš malého počtu shluků. Řešením tohoto problému je upravit učící algoritmus sítě tak, aby byl schopen přidávat a případně odebírat neurony ve výstupní vrstvě dle potřeby [Wu00, Ma98].

Obrázek 24: Segmentace obrazu SOM sítí. Originální obraz (vlevo nahoře), segmentovaný obraz (vpravo nahoře) a segmentovaný rozmazaný obraz (dole). Pro rozmazání byl použit Gaussian s konvolučním jádrem o velikosti 17. Obrázky pocházejí z [Moreira96].

SOM neuronové sítě úzce souvisejí s K-means algoritmem. Otázkou zůstává jaký je mezi nimi vztah a jakou výhodou SOM sítě je adaptace nejen vítězného neuronu, ale i jeho okolí.

Název	Kohonenovy mapy (neuronové sítě typu SOM)
Kategorie	V základní variantě jednoduchá statistická metoda segmentace.
Vstupní data	Obrazová i objemová diskrétní data.
Výstupní data	Segmentovaná diskrétní data.
Cílové aplikace	Nejen segmentace obrazu, ale obecně jakákoliv shluková analýza dat.
Výhody	ˇ Jednoduchá snadno rozšiřitelná metoda.
Nevýhody	ˇ Pevný počet neuronů ve skryté vrstvě = pevný počet segmentů.
Literatura	[Novak98], [Wu01], [Moreira96] [Wu00], [Ma98]

Fuzzy Connectedness

Další segmentační metodu s fuzzy přístupem vyvinul Udupa [Udupa95]. Na rozdíl od pevné binární klasifikace zavádí pojem fuzzy podobnosti objektů v obraze. Podobnost se počítá jako váhovaná suma intenzit a obrazových derivací v okolí pixelu. Udupa se tím snaží zachytit nejen intenzitu pixelů obrazu, ale i charakter změn v intenzitě. Nicméně váhy okolních pixelů jsou předem dané, proto je výsledná segmentace citlivá na zvolené váhy a vlastnosti regionů v obraze.

Obrázek 25: Testovací obrázek (vlevo) - kontrast disku s pozadím roste zleva doprava, zašuměný a rozmazaný obraz (uprostřed) a segmentace fuzzy connectedness metodou popsanou v [Udupa02].

Pednekar a Kakadiaris [Pednekar02] původní metodu vylepšili o dynamický výpočet vah. Adaptivní váhy ve spojení se zavedenými energetickými funkcemi pro ohodnocení homogenity a gradientů obrazu zlepšují výsledky i robustnost metody, přičemž omezily nutnou interakci s uživatelem.

Obrázek 26: Příklad segmentace tepen MRA (Magnetic Resonance Angiography) snímku (vlevo). Uprostřed vidíte výsledek fuzzy connectedness segmentace cévního systému a vpravo segmentované tepny opět metodou [Udupa02]. Autor Udupa et al.

Název	Fuzzy Connectedness
Kategorie	Speciální statistická metoda segmentace.
Vstupní data	Zejména obrazová 2D diskrétní data.
Výstupní data	Segmentovaná diskrétní data.
Cílové aplikace	Aplikováno hlavně v medicíně. ˇ Segmentace mozku, cévního systému apod.
Výhody	ˇ Využití strukturní i texturní informace pro segmentaci. ˇ Klasifikace do segmentů pomocí fuzzy relací, nikoliv pevné přiřazení. ˇ Odolnost vůči pomalým změnám pozadí obrazu.
Nevýhody	ˇ Pokročilejší metody jsou zatím navrženy pouze pro segmentaci dvou objektů. ˇ Neumožňuje využít jakékoliv znalosti o tvaru segmentovaného objektu.
Literatura	[Udupa95], [Udupa02] a [Udupa03] [Pednekar02]

Markov Random Fields (MRF)

Markovská náhodná pole (angl. Markov Random Fields) [Marroquin03] nejsou přímo segmentační metodou, ale statistický model, jenž lze v segmentaci využít. MRF modelují prostorové vazby mezi sousedními a blízkými pixely obrazu. Typicky platí, že většina pixelů obrazu patří do stejného segmentu jako jeho sousedé. Jinými slovy, jakýkoliv objekt či segment o velikosti jednoho pixelu má velmi malou pravděpodobnost výskytu v obraze.

Markovská náhodná pole společně s Bayesovským modelem mohou být mimo jiné zapracována do shlukovacích segmentačních algoritmů (např. K-means). Výslednou segmentaci získáme maximalizací posteriorní pravděpodobnosti p(C|X) (pravděpodobnost, že vzorek X patří do segmentu C) pro všechny body obrazu.

Obrázek 27: Příklad segmentace obrazu bez MRF modelů (vpravo nahoře) a s využitím MRF (obrázek dole). Autor Shi X., Computer Engeneering Department, UCSC.

Nevýhodou spojenou s MRF modely je obtížná volba řídících parametrů, které ovlivňují sílu prostorových vazeb mezi pixely obrazu. Špatné nastavení parametrů může způsobit nadměrně hladké hranice mezi segmenty obrazu a tím pádem ztrátu důležitých detailů. Kromě toho metody založené na MRF jsou velmi výpočetně náročné.

Přes všechny uvedené nevýhody jsou statistické MRF modely velmi rozšířené. Používají se nejen k modelování struktury či textury segmentů obrazu, ale i pro modelování nehomogenit v obraze, nerovnoměrného osvětlení apod.

Název	Markov Random Fields
Kategorie	Pokročilá statistická metoda, kterou segmentační algoritmy využívají pro modelování prostorových vazeb např. pixelů uvnitř regionů obrazu.
Vstupní data	Zejména obrazová 2D diskrétní data.
Výstupní data	Model prostorových vazeb.
Cílové aplikace	ˇ Popis struktury a textury regionů obrazu pro segmentaci. ˇ Modelování nehomogenit v obraze, nerovnoměrného osvětlení atd.
Výhody	ˇ Využití texturní a strukturní informace pro segmentaci. ˇ MRF modely lze zakomponovat do existujících shlukovacích segmentačních metod.
Nevýhody	ˇ Obtížné nastavení řídících parametrů. ˇ Vysoká výpočetní náročnost.
Literatura	[LiWWW] [Bouman95], [Marroquin03]

4.4 Hybridní metody

V této kapitole se podrobněji podíváme na segmentační algoritmy, které nelze klasifikovat do jedné z předchozích kategorií. Tyto algoritmy využívají některé prvky všech předchozích typů algoritmů.

Watershed Transform

Watershed transformaci (watershed = rozvodí, povodí či vodní předěl) [Grau04] je možné zařadit mezi region-based segmentační přístupy. Tato morfologická metoda segmentace je postavena na myšlence pocházející z geografie. Obraz je chápán jako térén nebo topografický reliéf, který je postupně zaplavován vodou.

Obrázek 28: Počáteční obraz (vlevo) a čáry reprezentující hráze, nebo-li tzv. watershed lines. Zdroj [BeucherWWW].

Povodí (angl. catchmen basin) jsou z počátečních bodů (lokálních minim obrazu) zaplňována vodou. V místech, kde by se voda ze dvou různých povodí mohla slít jsou vytvořeny hráze (dams). Proces postupného zaplavování ja zastaven ve chvíli, kdy dosáhneme nejvyššího bodu terénu (maxima obrazu). Výsledkem je obraz rozdělený do regionů, jednotlivých povodí oddělených hrázemi. Vzniklé hráze jsou nazývány watershed lines, nebo jednodušeji watersheds.

Obrázek 29: Výsledek watersheds segmentace lidského mozku a jeho 3D rekonstrukce. Obrázky pocházejí z článku [Grau04].

Výraz watershed transform znamená označení všech pixelů obrazu tak, že všechny body daného povodí jsou označeny stejným unikátním indexem. Speciální index, odlišný od všech ostatních, je přiřazen všem bodům tvořícím hráze - watersheds. Příklad segmentace medicínských obrazových dat touto metodou je znázorněn na Obrázek 29.

Obrázek 30: Výsledek watershed transformace (vlevo nahoře) a postupné spojování vzniklých regionů metodou popsanou v článku [Haris98], odkud pocházejí i použité obrázky.

Metoda produkuje velký počet regionů. Výsledkem je nadměrná segmentace obrazu. Obvyklým řešením je proces spojování regionů, jenž následuje po transformaci. Regiony patřící do stejného segmentu či obrazové struktury jsou spojovány (např. [Haris98]).

Název	Watershed Transform
Kategorie	Pokročilý hybridní segmentační algoritmus pracující s 2D obrazovými daty. Metoda morfologické segmentace, která obraz chápe jako terén zaplavovaný vodou. Vznikající povodí tvoří regiony obrazu.
Vstupní data	Obrazová diskrétní data.
Výstupní data	Segmentovaný obraz (hodnota pixelu = index regionu).
Cílové aplikace	Jakákoliv segmentace obrazu. ˇ Metoda je hojně využívána v medicínských aplikacích zejména pro segmentaci mozku.
Výhody	ˇ Osvědčená a efektivní metoda segmentace.
Nevýhody	ˇ Je-li obraz zašuměný, produkuje watershed transformace velký počet regionů, které je nutné dále zpracovat.
Literatura	[Haris98], [Grau04] [BeucherWWW]

Neuronové sítě

Většina metod segmentace obrazu je založena na znalostech a zkušenosti, jak a podle čeho by měla probíhat. Opakem je segmentace obrazu neuronovými sítěmi, která není založena na podobných meta-pravidlech. Trénování neuronové sítě (dále jen NN - Neural Network) čistě orientované na data probíhá podle principu "učení příklady". Na druhé straně leží algoritmy analyzující data vzhledem k zadané množině pravidel a příznaků.

V zásadě existují dvě strategie trénování umělé NN. První přístup hledá charakteristické vlastnosti vstupních dat (obvykle příznakové vektory) a klasifikuje je do tříd bez jakékoliv další interpretace. Tento přístup nazýváme učení bez učitele a setkali jsme se s ním v podobě trénování SOM neuronových sítí v kapitole 4.3 o shlukové analýze obrazu a statistických metodách segmentace.

Druhý přístup, tzv. 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. V literatuře naleznete mnoho učících algoritmů s učitelem i bez učitele. Jejich kombinací vznikly např. GRBF (Generalized Radial Basis Functions) neuronové sítě [Vismüller00, Bankman00] spojující výhody obou přístupů.

Obrázek 31: Struktura neuronové sítě s radiální bázovou funkcí. Zdroj [Wismüller00].

Architektura GRBF sítě je třívrstvá (viz. Obrázek 31). Skládá se ze vstupní vrstvy, jedné skryté vrstvy a výstupní vrstvy. Propojení neuronů mezi vrstvami je úplné. Každý neuron skryté vrstvy je spojen se všemi neurony vstupní i výstupní vrstvy pomocí synaptických vah. Vstupní vrstva neuronů slouží pouze k přiložení klasifikovaného příznakového vektoru x na vstup sítě. Hodnoty přiloženého vektoru propaguje do skryté vrstvy, kde jsou použity neurony s radiální bázovou funkcí (RBF) [Novak98]. Vektor vah w_j neuronu ve skryté vrstvě lze interpretovat jako bod v n-rozměrném prostoru hodnot vstupního vektoru. Aktivační funkce skrytého neuronu je obdobná jako u dříve popisovaných soutěživých SOM sítí. Určí se vzdálenost (nejčastěji euklidovská) vektoru vah w_j neuronu od příznakového vstupního vektoru x:

.

Výsledná aktivační funkce RBF neuronu má charakter Gaussovy funkce, např.

,

kde ρ je směrodatná odchylka Gaussovy funkce - parametr skrytého neuronu. V některých případech se používá normalizovaný tvar aktivační funkce (viz. [Bankman00] str. 109). Kompetitivní chování skryté vrstvy je zřejmé. Neuron, jehož vektor vah je nejblíže vstupnímu příznakovému vektoru má nejvyšší hodnotu aktivační funkce.

Výstupy neuronů skryté vrstvy jsou lineárně propagovány do vrstvy výstupní. Vektor vah s_m výstupního neuronu slouží pro výpočet váhované sumy aktivačních funkcí skrytých neuronů:

.

Tato struktura výstupní vrstvy odpovídá velmi známé architektuře NN zvané perceptron [Novak98].

Trénování GRBF sítě probíhá ve třech fázích. První dvě probíhají automaticky bez učitele, třetí fáze obvykle s učitelem.

1. V první fázi jsou ustanoveny váhy w_j mezi vstupní a skrytou vrstvou. Pro tento účel se používají algoritmy shlukové analýzy (viz. Kapitola 4.3).

2. Jakmile jsou hodnoty vah w_j známé, můžeme určit parametry skrytých neuronů (směrodatné odhylky). Nejčastěji se používají jednoduchá heuristická pravidla.

3. V poslední fázi jsou určeny váhy mezi skrytou a výstupní vrstvou sítě. Nejvýhodnější je minimalizace celkové chyby neuronové sítě pomocí metody gradientního sestupu.

Detailní informace ohledně architektury a trénování GRBF neuronových sítí naleznete v již citované knize [Bankman00].

Obrázek 32: Výsledek plně automatické segmentace šedé a bílé kůry mozkové v MR řezu pomocí GRBF neuronové sítě. Obrázky zveřejněny v článku [Wismüller00].

Vlastnosti GRBF neuronových sítí jejich autoři ověřovali na automatické segmentaci šedé a bílé kůry mozkové v MR snímcích. Svoje výsledky hodnotí jako velmi povzbudivé, avšak stále jsou tu problémy, které je nutné řešit.

Název	GRBF neuronové sítě
Kategorie	Pokročilý hybridní segmentační algoritmus založený na neuronových sítích s radiální bázovou funkcí.
Vstupní data	Obrazová i objemová diskrétní data.
Výstupní data	Segmentovaná data.
Cílové aplikace	Jakákoliv segmentace obrazu. ˇ Metoda byla použita pro segmentaci šedé a bílé kůry mozkové v MR datech.
Výhody	ˇ Spojuje výhody dvou druhů algoritmů pro trénování neuronové sítě - s učitelem i bez učitele.
Nevýhody	ˇ Ručně anotovaná trénovací data. ˇ Nová metoda, některé problémy je třeba dořešit.
Literatura	[Wismüller00] a [Bankman00] str. 107-126 [Novak98]

4.5 Znalostní metody

Do této kategorie patří všechny metody, které využívají dříve získané znalosti objektů vyskytujících se v obraze. Takové znalosti jsou reprezentovány buď šablonami objektů, nebo modely objektů. Vytvořený model, nebo šablona je porovnáván s novým obrazem a hledají se případné shody.

Hlavní nevýhodou všech metod založených na znalostech je variabilita objektů. Přesná segmentace velmi složitých struktur je pak obtížná. Pokud je struktura objektů ve všech případech podobná, jsou naopak tyto metody velmi výhodné.

Active Appearance Models (AAM)

V posledních letech bylo dosaženo velmi dobrých výsledků v segmentaci medicínských i klasických obrazových dat pomocí tzv. Active Appearance Models [Cootes98] [Stegmann00]. Statistickou metodou zpracování dat, PCA (angl. Principal Component Analysis) analýzou, je 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.

Obrázek 33: Segmentace záprstních kostí pomocí AAM. Zleva: nezávislá analýza hraničních bodů, analýza změn v textuře kostí a vypočtený AMM model. Autor M.B. Stegmann [Stegmann00].

Mezi modelované vlastnosti patří tvar objektu a intenzity pixelů. Příprava trénovacích vzorů spočívá v manuálním zadávání hraničních bodů (angl. 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ů. Tímto způsobem natrénovaný model umožňuje velice rychlé porovnání modelu s objekty v novém obraze.

První nevýhodou segmentace pomocí AAM je samotné trénovaní. Musíme totiž sestavit reprezentativní množinu vzorů, což není jednoduché. Další problém je, že vzory v trénovací množině musíme ručně anotovat. V případě rozsáhlé množiny dat je taková anotace velmi časově náročná. Nepříjemnou vlastností AAM algoritmu je možnost selhání při porovnávání modelu s novým obrazem. Velmi důležitá je proto poměrně přesná inicializace, nebo-li odhad polohy objektu v testovaném obraze.

Název	Active Appearance Models
Kategorie	Speciální template-based segmentační algoritmus pracující s 2D obrazovými daty. Statistickou PCA analýzou dat je získán model segmentového objektu.
Vstupní data	ˇ Obrazová diskrétní data. ˇ Ručně anotovaná trénovací množina vzorů.
Výstupní data	Poloha detekovaného objektu v obraze.
Cílové aplikace	Segmentace objektů stejného charakteru. ˇ Metoda je široce využívána v medicínských aplikacích, ale i pro detekci lidského obličeje v obraze a rozpoznávání výrazu.
Výhody	Rychlá adaptace modelu na nový obraz.
Nevýhody	ˇ Nutná rozsáhlá a reprezentativní galerie trenovacích vzorů a jejich ruční anotace. ˇ Metoda vyžaduje poměrně přesnou počáteční inicializaci.
Literatura	[StegmannWWW], [CootesWWW] [Cootes98], [Stegmann00]

5 Závěr

Cílem tohoto dokumentu je shrnout a seznámit čtenáře se základními a pokročilými metodami obrazové segmetace, jejich klasifikaci a použití zejména při zpracování medicínských dat a v aplikacích rozšířené reality. Formou studijních materiálů seznamujeme čtenáře s obecnými postupy i s jejich modifikacemi a vlastnostmi a zákonitostmi procesu zpracování obrazu.

Rádi bychom tuto dokumentaci postupně doplňovali a rozšiřovali.

Literatura

[Argyle71] Argyle E.: Techniques for Edge Detection, Proc. IEEE, 59, 2, February 1971, 285-287.

[Bankman00] Bankman I. N.: Handbook of Medical Imaging: Processing and Analysis. Academic Press, San Diego, CA, USA, 2000.

[BeucherWWW] Beucher S.: Image Segmentation and Mathematical Morphology. Center of Mathematical Morphology home page, 2000.

URL: http://cmm.ensmp.fr/~beucher/wtshed.html

[Bouman95] Bouman C. A.: Markov Random Fields and Stochastic Image Models. Tutoriál Presented at IEEE International Konference on Image Processing 1995, October 1995.

[Brice70] Brice C. R., Fenema C. L.: Scene Analysis Using Regions. Artificial Intelligence, 1, 1970, 205-226.

[Bullit02] Bulit E., Aylward S. R.: Volume Rendering of Segmented Image Objects. In Proc. Of the IEEE Transactions on Medical Imaging. Vol. 21, No. 8, August 2002.

[Canny86] Canny J.: A Computational Approach to Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, PAMI-8, 6, November 1986, 679-698.

[Chen80] Chen P. C., Pavlidis T.: Image Segmentation as an Estimation Problem. Computer Graphics and Image Processing, 12, 2, February 1980, 153-172.

[Coleman79] Coleman G. B., Andrews H. C.: Image Segmentation by Clustering. Proc. IEEE, 67, 5, May 1979, 773-785.

[Cootes98] Cootes T. F., Edwards G. J., Taylor C.J.: Active Appearance Models. In Proceedings of European Conference on Computer Vision 1998, Vol. 2, pp. 484-498, Springer, 1998.

[CootesWWW] Cootes T. F.: Active Appearance Models. Division of Imaging Science and Biomedical Engineering, University of Manchester, UK, 2006.

URL: http://www.isbe.man.ac.uk/~bim/

[Droske01] Droske M., Meyer B., Rumpf M., Schaller K.: An Adaptive Level Set Method for Medical Image Segmentation. In Proc. of the Annual Symposium on Information Processing in Medical Imaging, Springer, Lecture Notes Computer Science, 2001.

[Forsyth03] Forsyth D. A., Ponce J.: Computer Vision: A Modern Approach. Prentice Hall, Pearson Education, Inc., USA, January 2003.

[Fukada80] Fukada Y.: Spatial Clustering Procedures for Region Analysis. Pattern Recognition, 12, 1980, 395-403.

[Grau04] Grau V. et al.: Improved Watershed Transform for Medical Image Segmentation Using Prior Information. IEEE Transactions on Medical Imaging, Vol. 23, No. 4, April 2004.

[Haralick69] Haralick R. M., Kelly G. L.: Pattern Recognition with Measurement Space and Spatial Clustering for Multiple Images. Proc. IEEE, 57, 4, April 1969, 654-665.

[Haris98] Haris K., Efstratiadis N., Maglaveras N., Katsaggelos A.K.: Hybrid Image Segmentation Using Watersheds and Fast Region Merging. IEEE Transactions on Image Processing, Vol. 7, No. 12, December 1998.

[Hlavac92] V. Hlaváč, M. Šonka: Počítačové vidění. Vydavatelství Grada, Praha, ČR, 1992.

[Jan97] J. Jan: Číslicová filtrace, analýza a restaurace signálů. Vysoké učení technické v Brně, ČR, 1997.

[Ji99] Ji L., Yan H.: Loop-Free Snakes for Image Segmentation. Proc. 1999 International Conference on Image Processing, 3, Kobe, Japan, 1999, 193-197.

[Krsek01] Kršek P.: Direct Creating of FEM Models from CT/MR Data for Biomechanice Applications. Edition PhD Thesis, Vutium, Brno, Czech Republic, 2001. ISBN 80-214-1796-X

[Lam94] Lam K.-H., Yan H.: Fast Greedy Algorithm for Active Contours. Electronic Letters, 30, 1, January 1994, 21-23.

[Leventon00] Leventon M.E. et al.: Level Set Based Segmentation with Intensity and Curvature Priors. In Proc. of IEEE workshop MMBIA 2000, IEEE, June 2000.

[LiWWW] Li S. Z.: Markov Random Field Modeling in Computer Vision. National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Science, 2001.

URL: http://www.nlpr.ia.ac.cn/users/szli/MRF_Book/MRF_Book.html

[Lorensen87] Lorenzem W., Cline H.: Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics 21:163-169, 1987.

[Ma98] Ma F. et al.: Probabilistic Segmentation of Volume Data for Visualization Using SOM-PNN Classifier. IEEE, 1998.

[Macleod70] Macleod I. D. G.: On Finding Structure in Pictures, in Picture Processing and Psychopictorics, B. S. Lipkin and A. Rosenfeld, Eds., Academic Press, New York, 1970.

[Macleod72] Macleod I. D. G.: Comments on Techniques for Edge Detection, Proc. IEEE, 60, 3, March 1972, 344.

[Marr80] Marr D., Hildrith E.: Theory of Edge Detection, Proc. Royal Society of London, B207, 1980, 187-217.

[Marroquin03] Marroquin J. L., Santana A., Botello S.: Hidden Markov Measure Field Models for Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Inteligence, Vol. 25, No. 11, November 2003.

[Moreira96] Moreira J., Costa L. F.: Neural-based Color Image Segmentation and Classification using Self-Organizing Maps. IX SIBGRAPI, pp. 47-54, 1996.

[Novak98] Novák M. a kol.: Umělé neuronové sítě, teorie aplikace. Praha: C. H. Beck, 1998.

[Pednekar02] Pednekar A., Kakadiaris I. A., Kurkure U.: Adaptive Fuzzy Connectedness-based Medical Image Segmentation. In Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing (ICVGIP‘02), Space Applications Centre (ISRO), Ahmedabad, India, December 2002.

[Pratt01] Pratt W. K.: Digital Image Processing: PIKS Inside, Third Edition. John Wiley and Sons, Inc., 2001.

[Russ98] Russ J. C.: The Image Processing Handbook, Third Edition. CRC Press, January 1998.

[Sethian99] Sethian J.A.: Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision and Materials Sciences. Cambridge University Press, 1996.

[SethianWWW] Sethian J.A.: Fast Marching Methods and Level-Set Methods. Dept. of Mathematics, University of California, Berkley, California, 1999.

URL: http://math.berkeley.edu/~sethian/level_set.html

[Sonka98] Sonka M., Hlavac V., Boyle R.: Image Processing, Analysis and Machine Vision. Brooks and Cole Publishing, 1998.

[Stegmann00] Stegmann M. B.: Active Appearance Models: Theory, Extensions and Cases. Master Thesis, 2^nd edition, IMM, Technical University of Denmark, Lyngby, September 2000.

[StegmannWWW] Stegmann M. B.: Active Appearance Models. Technical University of Denmark, Lyngby, 2004.

URL: http://math.berkeley.edu/~sethian/level_set.html

[Udupa02] Udupa J. K., Saha P. K., Lotufo R. A.: Relative Fuzzy Connectedness and Object Definition: Theory, Algorithms, and Applications in Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 11, November 2002.

[Udupa03] Udupa J. K., Saha P. K.: Fuzzy Connectedness and Image Segmentation. In Proc. Of the IEEE, Vol. 91, No. 10, October 2003.

[Udupa95] Udupa J. K., Samarasekera S.: Fuzzy Connectednes and Object Definition. In SPIE Proceedings Medical Imaging, Vol. 2431, pp. 2-10, SPIE, 1995.

[Vivodtzev03] Vivodtzev F. et al.: Hierarchical Isosurface Segmentation Based on Discrete Curvature. Joint EUROGRAPHICS - IEEE TCVG Symposium on Visualiation, The Eurographics Association, 2003.

[William92] Williams D. J., Shah M.: A Fast Algorithm for Active Contours and Curve Estimation. CVGIP: Image Understanding, 55, 1, 1992, 14-26.

[Wismüller00] Wismüller A., Vietze F. et al.: A Neural Network Approach to Adaptive Pattern Analysis - the Deformable Feature Map. European Symposium on Artificial Neural Networks, ESANN'2000, pp. 189-194, Bruges, Belgium, April 2000.

[Wu00] Wu Y., Liu Q., Huang T. S.: An adaptive self-organizing color segmentation algorithm with application to robust real-time human hand lokalization. University of Illinois at Urbana-Champaign, 2000.

[Wu01] Wu Y.: Segmentation: Clustering, Graph Cut and EM. ECE510 - Computer Vision Notes Series 5, 2001.