Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
METODY ROZPOZNÁNÍ OBJEKTŮ V OBRAZU CÍLE LABORTATORNÍ ÚLOHY 1. Seznámení se s metodami rozpoznání objektů v obraze 2. Vyzkoušení detekce objektů na snímcích z kamery a MRI snímku
ÚKOL 1. Seznamte se s metodami rozpoznávání objektů v obraze viz níže. 2. Seznamte se s funkceme knihovny AForge (C#) a Matlabu pro segmentaci a klasifikaci objetků. Ukázky zdrojových kódů naleznete v uloha.zip. 3. Napište program, který ve MRI snímku mozku snímek.jpg rozliší šedou hmotu mozkovou a bílou hmotu mozkovou a mozkomíšní mok 4. Vytvořte program, který rozezná jednotlivé kostky v obraze soubor kostky.png 5. Získejte obraz s kamery a online rozeznejte objekty
TEORETICKÝ ZÁKLAD Detekce různých objektů či tvarů ve snímku je velmi důležitým prvkem veškerých operací zahrnujících práci s obrazem. Uplatňuje se nejen ve zpracování lékařských obrazových dat (hledání struktur v tomografech), ale i v bezpečnosti (např. kontrola zda vše je na svém místě), a v osobním sektoru u fotoaparátů a kamer (detekce obličeje, úsměvu…). Samozřejmě existuje ještě více využití.
SEGMENTACE Jelikož hledání objektů patří mezi analýzu obrazu, je většinou nutné si obraz nejprve nějak předzpracovat, než se s ním bude dále manipulovat. K tomu je vhodná metoda segmentace, jejímž hlavním úkolem je rozdělit obraz do takových částí, které mají úzkou souvislost s oblastmi reálného světa zachyceného na obraze, nebo mají společné vlastnosti. Mezi takové patří např. barva, tvar nebo textura. Výsledkem segmentace je soubor vzájemně se nepřekrývajících oblastí. Podle výsledku dělíme segmentaci na kompletní (oblasti odpovídají objektům) a neúplnou (oblasti odpovídají jen určitým vlastnostem – jas, barva, textura). Výhodou je výrazné snížení objemu dat. Problémem pak může být nejednoznačnost obrazu nebo šum. Mezi nejstarší a nejjednodušší metody segmentace patří tzv. tresholding (prahování), který se stejně tak řadí mezi cenově nenáročné a z hlediska výpočtu i mezi rychlé, ale využívá se spíše v jednodušších případech (např. předměty na bílém pozadí). Mnoho objektů nebo oblastí obrazu je charakterizováno konstantní odrazivostí či pohltivostí svého povrchu. V takovém případě můžeme využít hodnoty jasu k oddělení objektů od pozadí. V ideálním případě je výstupem
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
prahování kompletní segmentace na oblasti. U obrazu, který obsahuje různě jasné úseky (nehomogenní), nelze určit jednotný práh. Lze však použít adaptivní prahování.
Obr 1.: Šedý obraz a jeho histogram
Důležitou roli při metodě tresholdingu hrajou histogramy. Pokud máme obraz v odstínech šedi, tak nám vznikne histogram intenzity. Na ose x máme stupně intenzity (0-255) a na ose y počet pixelů odpovídajících danému stupni šedi. Předpokládejme, že máme histogram šedého obrázku, na kterém jsou tmavé objekty a světlé pozadí (obr1), tak že na histogramu je jasně odlišitelná barevná skupina. V případě obr1 to je bílá, která odpovídá pozadí. Pokud potřebujeme oddělit objekty od pozadí, musíme si zvolit práh, který nám rozdělí obraz na barvu pozadí a na barvu objektů. Potom každý bod, který má menší hodnotu než tento práh, je nazýván bod objektu a zbylé body jsou body pozadí. Pokud máme stanovený práh, pak platí (
)
(
)
(
)
{
kde T představuje práh. Všechny body, které po segmentaci mají hodnotu 1 a představují objekty. Body s hodnotou 0 jsou pixely pozadí. Pomocí prahování se otestují všechny pixely (i, j) obrazu f. Hodnotu prahu můžeme určit pokusně (od oka z histogramu) nebo za pomoci některých automatických metod určování prahu. Výsledkem je binární obraz. Málokdy se dá pracovat pouze s jedním prahem, kvůli změnám jasu objektu i pozadí zaviněnými nerovnoměrností osvětlení. V této situaci může pomoci prahování s proměnným prahem, kdy hodnota prahu je určována podle lokálních vlastností obrazu. Obraz se musí rozdělit do několika podobrazů a u těch následně postupovat jako při běžném prahování. Každý podobraz prahujeme lokálním prahem, pokud v některém z těchto podobrazů nelze určit lokální práh, použijeme práh získaný interpolací sousedních prahů. Modifikací tresholdingu s globálním prahem je prahování s více prahy, pro které platí
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
(
)
( (
) )
(
)
{ A jsou podmnožiny jasových úrovní. Výsledkem není binární obraz, ale obraz s velmi omezeným počtem jasových úrovní. Jestliže potřebujeme z obrazu segmentovat oblasti s danou množinou jasu, tak platí vztah ( (
)
)
{
A představuje množinu jasu. Toho je možné využít například pro segmentaci mikroskopických snímků krevních buněk, v nichž se cytoplazma jeví v určitém intervalu úrovní jasu, zatímco pozadí je světlejší a jádro naopak tmavší. Další možností jak segmentovat obraz je za použití regionálních metod (region-based). Tyto metody pomáhají najít takové body, které mají podobnou nějakou vlastnost. Za společnou vlastnost můžeme považovat např. jas, barva, textura. Principem je, že stavění segmentu postupuje zdola nahoru, od jednoho pixelu po celý segment. Nejprve jsou nějakým algoritmem v obraze rozmístěny iniciální pixely, obvykle rovnoměrně nebo náhodně, segment pak vzniká iterativním rozrůstáním se okolí iniciálního pixelu. Tato metoda nemusí dávat stejné výsledky jako metody založené na detekci hran nebo na kombinaci metod. Na druhou stranu jsou tyto metody schopny segmentovat i takový obraz, který obsahuje značné množství šumu. Regionální metody: -
spojování oblastí štěpení oblastí štěpení a spojování watershed shluková analýza (Mean-shift,K-means)
Segmentace narůstáním oblastí zahrnuje spojování i štěpení oblastí. Základní myšlenkou je rozčlenit obraz do maximálních souvislých oblastí tak, aby z hlediska zvoleného parametru byly homogenní. Uplatňuje se tu opět kritérium homogenity, kterým může být textura, barva nebo jasové vlastnosti. Tyto metody slouží k přímé konstrukci oblastí a výrazně se uplatňují v obrazech se šumem. Spojování oblastí, jak už název napovídá, slouží ke konstrukci oblasti spojováním malých homogenních oblastí. Postup: 1. Definování počátečního rozdělení obrazu do velkého množství malých oblastí 2. Definování kriteria spojování dvou sousedních oblastí 3. Spojení sousedních oblastí, které vyhovují vybranému kritériu. Pokud již nelze spojit žádné dvě oblasti, aniž by bylo porušeno kritérium – > konec spojování
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
Příklad: Pokud rozdíl jasů dvou sousedních oblastí je menší než 5, pak tyto oblasti spoj.
Touto metodou se dá dosáhnout různých výsledků pro různé definice počátečních oblastí, kritéria, počátky spojování, pořadí předkládaných oblastí nebo pro různé postupy spojování. Štěpení oblastí je principiálně opačný přístup k segmentaci než jejich spojování. Na začátku se vezme celý obraz a ten se dělí tak dlouho, dokud podoblasti neodpovídají kritériu. Postupy štěpení oblastí pracují se stejnými kritérii jako postupy spojování oblastí. Stejně jako u spojování oblastí i při této metodě se dosahuje různých výsledků. Štěpení a spojování využívá pyramidální reprezentaci obrazu, kde je štěpení a spojování realizováno v rámci čtvercových oblastí pyramidální datové struktury. Pokud je oblast v dané úrovni pyramidy nehomogenní, je rozštěpena na čtyři podoblasti. Jsou-li čtyři oblasti navzájem homogenní a je-li možné je vy vyšší úrovni pyramidy spojit, jsou spojeny.
Obr2.: Spojování a štěpení, zleva: originál, štěpení, štěpení a spojování
Při segmentaci pomocí metody watershed (rozvodí, povodí, vodní předěl) se vychází z geografie. Obraz je chápán jako terén nebo topografický reliéf, kde jas vstupního obrázku určuje výšku terénu – černá je nejníže, bílá nejvýše. Princip je založen na postupném zaplavování terénu vodou nebo stoupání hladiny. Výsledkem je obraz rozdělený do jednotlivých povodí (regionů) oddělených hrázemi, všechny body daného povodí jsou označeny stejným unikátním indexem. Pro obrazy obsahující šum vytváří tato metoda příliš mnoho oblastí. Lze je eliminovat vhodnou předpřípravou obrázku, nebo ¨zaplavovat¨ obrázek od určité prahové výšky. Obecný algoritmus (metoda zaplavování): 1. Najít lokální minima obrazu 2. „Zaplňování vodou“ z těchto lokálních minim a. v místech, kde by se voda z různých dvou zdrojů mohla slít, vytvořit hráze 3. Ukončit zaplavování ve chvíli dosažení maxima
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
Obr.3.: Watershed segmentace
Shluková analýza (cluster analysis) je vícerozměrná statistická metoda, která se používá ke klasifikaci objektů. Slouží k třídění jednotek do skupin (shluků) tak, aby si jednotky náležící do stejné skupiny byly podobnější než objekty ze skupin různých. Shlukovou analýzu je možné provádět jak na množině objektů, z nichž každý musí být popsán prostřednictvím stejného souboru znaků, které má smysl v dané množině sledovat, tak na množině znaků, které jsou charakterizovány prostřednictvím určitého souboru objektů, nositelů těchto znaků. Pokud uvažujeme, že každý pixel (nebo část obrazu) je reprezentován vektorem vlastností x=[x1, x2, …, xn], což může být pozice, vlastnosti okolí, barevné komponenty pixelů, atd., je nutné vybrat takové vlastnosti, které mají pixely z jedné oblasti podobné a z různých oblastí rozdílné (měli by v N-rozměrném prostoru vznikat shluky)
Obr.4.: Shluková analýza Úlohou segmentace je automaticky určit polohu shluků (někdy i jejich počet) a přiřadit jednotlivým vzorkům nejbližší shluk – metoda učení bez učitele, iterativní postup. Shluková analýza vychází z podobnosti, resp. vzdálenosti vzorků. Její kvantitativní vyjádření je jedním ze základních problémů shlukové analýzy. Vzdálenost dvou objektů r a s (charakterizovanými N vlastnostmi) je možné určit např.:
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
(
)
√∑|
|
k= 1 vzdálenost v městských (Manhattan) k= 2 Euklidovská vzdálenost
( blocích
)
|
|
Čebyševova vzdálenost
Detekce hran (edge detection) patří mezi metody založené na hranici (boundary-based). Vychází ze skutečnosti, že hranice oblastí obrazu jsou tvořeny hranami, které můžeme najít použitím některého z hranových operátorů (Cannyho hranový detektor, Sobelův filtr). Protože výstupem gradientního operátoru je obraz, kde jsou sice hrany zdůrazněny, ale může obsahovat další artefakty odpovídající lokálním nehomogenitám v obraze, je třeba, aby obraz prošel dalšími úpravami, které spojují hrany do řetězů lépe odpovídajících průběhu hranic. K odstranění artefaktů vzniklých lokálními malými rozdíly obvykle postačuje prahování. Vzhledem ke svým vlastnostem mohou detektory hran vytvářet přerušované hranice i falešné hranice, obraz hranic je tedy třeba dále zpracovat. Hrany se v obraze často vyskytují v místech, kde dochází k náhlé změně jasu. Metody pro identifikaci těchto nespojitostí spočívají v nalezení lokálních maxim v případě první derivace signálu nebo v nalezení průchodu nulou v případě druhé derivace signálu. V počítačovém zpracování se využívá konvoluce obrazu s maskou, která aproximuje první nebo druhou derivaci.
Obr.5.: Detekce hran
Jak už bylo zmíněno, pro nalezení hran můžeme použít hranové detektory. V praxi existují tři kategorie hranových detektorů, které se odlišují svým algoritmem. 1. Hledání maxim prvních derivací
Úlohy pro praktickou výuku zpracování obrazových dat podpořeno z FRVŠ č. 724/2011
2. Hledání průchodů druhých derivací nulou 3. Lokální aproximací obrazové funkce parametrickým modelem, např. polynomem dvou proměnných Pokud chceme využít aproximaci první derivace diferencí, můžeme použít např. tyto operátory:
Robertsův operátor o využívá okolí 2x2 body o Nevýhoda: velká citlivost na šum, protože okolí použité pro aproximaci je malé. operátor Prewittové o gradient je odhadován v okolí 3x3 body pro osm směrů o vyber se ten směr, který má největší modul gradientu Sobelův operátor o jako operátor Prewittové, dává však větší důraz centrální buňce o často se používá pro detekci vodorovných a svislých hran Cannyho hranový detektor o využívá konvoluce Gaussiánu s obrazem a následné derivace ve směru gradientu o pro určení významných hran se výstup detektoru prahuje o používá se prahování hysterzí – souvislost hran
Detekce hran pomocí metod využívajících průchodu druhé derivace nulou, zejména pak Cannyho hranový detektor, vykazují velmi dobré výsledky zvláště při automatickém nastavení prahu. Cannyho hranový detektor vykazuje i nejmenší citlivost na šum při prahování nastaveným na 0. Naopak, metody využívající pro detekci hran pouze první derivaci obrazové funkce, některé hrany nenaleznou vůbec. Při prahování nastaveném na 0 se projeví jejich velká citlivost na šum. Další z boundary-based metod je sledování hranice (boundary tracking). Tento postup aplikovatelný na obrazy obsahující především informaci o hranicích, například na výsledky použití gradientních filtrů (gradientní obraz). Cílem metod je v gradientním obraze právě jen skutečné hrany a vyloučit artefakty. Slouží k určení vnitřních a vnějších hranic obrazu. Sledování hranice může selhávat u příliš zašumělých obrazů nebo u příliš komplikovaných tvarů segmentu.
ROZPOZNÁNÍ OBJEKTŮ Segmentace nám rozdělí obrázek na jednotlivé oblasti zájmu. U těchto oblastí nejdříve definujeme charakteristiky, které reprezentují daný objekt. Charakteristiky závisí na typu objektu, který rozpoznáváme. Například rozpoznáváme-li banány od jablek, budeme jako charakteristiku volit kulatost objektu (podlouhlost) a případně barvu. Základní charakteristiky:
barva, může být průměrná nebo jenom středu objektu. V barevných obrázcích můžeme jako barvu použít hodnotu jednotlivých RGB složek. Nebo použít jiný barevný systém (HSV, Lab) a používat například jen jednu barevnou složku například. Obecně nelze s kon konvexnost konkávnost – parametr , který udává, jak je objekt konvexní nebo konkávní tvar objektu – kulatost, excentricita momentové příznaky Plnost objektu – poměr obsahu konvexní obálky k obsahu objektu
Na základě charakteristik pak klasifikuje objekty do tříd viz výše kluster analýza.