Klasifikace obrazu metodami strojového učení • Neuronové sítě • Rozhodovací stromy Neuronové sítě • počítačová architektura, která se snaží napodobit procesy probíhající v nervové soustavě • je nezávislá na statistickém rozložení dat • je odolná proti chybám, má schopnost učit se (asociativní učení), dovede abstrahovat i generalizovat • dokáže odhadnout nelineární vztah mezi vstupními a požadovanými výstupními daty • umožňuje v procesu klasifikace kombinovat různé typy vstupních dat. Základní pojmy • neuron - výkonný prvek NS • synapse - spojeni neuronu • váhové koeficienty neuronů • adaptivní fáze - učící • aktivní fáze - vybavovací l A % i i i i B C Schematizované vrstva, B - uspořádání neuronové sítě A - vstupní skrytá vrstva, C - výstupní vrstva (multi-layer perceptron) NN pro klasifikaci multispektrálního snímku 1 vodní plochy 2 jehličnaté lesy uibauizov né plochy holi půda, stavby apc zemědélsk plochy 1 zemědébk plochy^ zemědělsk plochy 3 zemědélsk plochy 4 zamadálsk plochy 5 zemědělsk plochy 6 Příklad třívrstvé perceptronové sítě se 6 vstupními, 8 skiytými all výstupními uzly (MLP 6-8-11) s příkladem vstupu a výstupu při klasifikaci družicových snímků s vyznačenými aktivacemi zastavěné plochy Model neuronu x1w1 vszupy x2w2 AS) - —~ aktivační i + e funkce vystup kde xi- hodnota i-tého vstupu S(x^) = / W.X. wi - váha i-tého vstupu . Neuron provádí tři akce: • sumuje vstupy z jiných neuronů • provádí prahování • posílá výstup do jiných neuronů Model neuronu • Neurony v síti jsou propojeny tzv. váhovými koeficienty, které zesilují nebo zeslabují signál přicházející z předchozích neuronů. • Suma těchto vážených signálů určuje aktivaci neuronu, která ovlivňuje další výstup z neuronu. • Výstup z neuronu je funkcí této aktivace, kdy výstup je vypočten na základě logistické aktivační funkce - sigmoida. • Výstup z uzlu je realizován pouze překračuje-li určitou prahovou hodnotu. • Váhové koeficienty jsou na počátku náhodnými čísly Učící - adaptivní fáze • Učení - váhy na spojích mezi jednotlivými výkonnými prvky sítě se mění podle určitého tzv. učícího algoritmu. • Použije se trénovací soubor, ve kterém známe správné zarazení pixelů do jednotlivých klasifikačních tříd. • Učící algoritmus - predpis, podle kterého se předkládají síti vzory k učení a podle kterého se mění váhy jednotlivých spojení mezi neurony. • Učení se s učitelem - analogie řízené klasifikace Algoritmus zpětného šíření (Back propagation) • Učení se bez učitele - analogie shlukové analýzy (neřízené klasifikace) - samo-organizujíc í se sítě (Self-organizing) -Kohonenova síť • Ustálení - dosažení stabilního stavu sítě Algoritmus zpětného šíření (Back propagation) • signály nejprve vyšlou směrem dopředu • u výstupních neuronů se porovnají výstupy s požadovanými • zjištěné chyby se použijí ke změně nastavení vah v síti Výstup ze sítě má formu vektoru: Očekávaný výstup (z učící množiny): o = (0,0,0,1,0,0) Aktuální výstup: a = (0,1,0,0,0,0) Hodnocení úspěšnosti učení - chyba e: e=7Z(°j-aj) • Učení probíhá iteračním způsobem - cílem je dosáhnout nulové či minimální akceptovatelné chyby. • Adaptace sítě - úprava vah synapsí - probíhá po krocích. • Délka kroku se nazývá learning rate. • Velká délka kroku značí rychlejší, ale méně presné učení Přednosti neuronových sítí • nezávislost na statistickém rozdělení • schopnost generalizace • síť je tolerantní k šumu v učících datech Nedostatky neuronových sítí • problém návrhu architektury sítě (počet skrytých vrstev a počet neuronů v nich) • dlouhá doba učení • problém lokálního minima (oscilace) • nastavení úvodních (náhodných) vah synapsí 2 Klasifikace Rozhodovacími stromy (Decision Trees) Základní pojmy: • Název atributu - uzel • Aritmetický či logický výraz -větev stromu • Název třídy - list stromu TM3 <= 35 : | TM4 > 99 : polev (12.0) I TM4 <= 99 : I | TM5 > 58 : lesí (30.0/ 1.0) I I TM5 <= 58 : | | | TM6 <= 12 : lesí (2.0) | | | TM6 > 12 : lesj (8.0) TM3 > 35 : | TM6 <= 23 : voda (17.0) | TM6 > 23 : poleb (26.0) • Mohou ale i nemusí být založeny na binárním třídění, jsou neparametrické. • Umožňují testování sousedů - grafy sousednosti a topologických vazeb (meet, contain, overlap, ...) • Umožňují testování atributů různé povahy • Možnost klasifikace po vrstvách - hierarchické třídění („layered classification") • Problém objektivního hodnocení („ground truth") Klasifikace LAYERED CLASSIFIER Rozhodovacími stromy Water Soil, Rock Layered classification Soil ^^Rock Klasifikace po vrstvách či hierarchická klasifikace Vegetation o ^l\ , Crops Trees Grass | Corn Soybeans Non-Vegetation I\C?!-VV-0.'^Í ., ■ Rrst Layer Partitioning Second Layer Partitioning Third Layer Partitioning Kontextuální klasiflkátory • Zahrnují postupy hodnotící s polohu či prostorové uspořádání (strukturu) objektů v obraze. • K rozpoznávání a klasifikaci objektů používají prostorových příznaků - kontextu. • Kontext (pattern) je popisován v obraze jako celku. • Mohou pracovat i s jednotlivými obrazovými daty, většinou jsou však aplikovány na obraz rozdělený na objekty (např. segmentací) či na obrazová data již klasifikovaná (např. shlukovou analýzou). • Prostorové příznaky jsou hodnoceny topologickými vztahy Q- Základní topologické vazby • vzdálenost (určitý objekt se může nacházet pouze v určité vzdálenosti od jiného objektu) • směr (orientace - určitý objekt se může nacházet pouze v určitém směru od jiného objektu) •konektivita (spojení - dva objekty mohou anebo nemusí být spojeny jiným objektem) • dotyk (sousedství - dva objekty se mohou a nemusí dotýkat) • vnoření (obsazenost - jeden objekt se musí nebo naopak nesmí vyskytovat uvnitř jiného). -D -n D Základní topologické vazby • Mapová algebra jako nástroj k sestavování logických pravidel a topologických vztahů • Hlavní problém - kvantifikace vztahů, regionálně omezená platnost (příklad, lužního lesa) •Výhoda - možnosti uvažování i „ne rastrových" dat • Lze je považovat také za metodu úpravy výsledků klasifikace Tvrdé a měkké klasiflkátory, princip neurčitosti (fuzzy logic) • Umožňují hodnotit smíšené pixely. Pixel obsahuje na 51 % listnatý les a na 49 % jehličnatý les • Umožňují hodnotit sílu důkazu pro zařazení pixelu do dané třídy (maximální pravděpodobnost může být malá s ohledem na absolutní hodnoty). Pixel je z 26 % jehličnatý les, z 19 % listnatý, ale z 55 % nějaký jiný, neznámý (nenatrénovaný) povrch. • Umožňují použití GIS databáze pro vyhodnocování výsledků. Př.: Zastavěné plochy vs. vektorová databáze komunikací (do každého sídla vede cesta). 3 Měkké klasifikace - „neostrá vyhodnocení" „fuzzy" -neurčitý, nepevný, nedeterminovaný Fuzzy logic - skupina algoritmů a rozhodovacích pravidel, které nejsou pevné, v každém kroku jednoznačně definované, ale umožňuji pracovat s jistou mirou nejistoty. Nepřiřazuji jednoznačně pixel jedné třidě Pro každou třidu zjišťuji pravděpodobnost s jakou pixel této třidě náleži. Výstupem z těchto klasiíikátorů neni jedna tématická mapa, ale skupina rastrů, ve kterých hodnoty představuji pravděpodobnost s jakou pixel spadá do dané třidy. Funkce příslušnosti (membership function). 27 29 P - příslušnost k dané třídě, R - odrazivost Texturální klasifikátory • Určitou třídu povrchu nemusí charakterizovat homogenní množina pixelů ale naopak množina pixelů s typickou heterogenitou hodnot • Textura jako interpretační znak - plošná tónová proměnlivost skládající se se shodných opakujících se elementů • Statistické míry textury vycházejí z GLCM (Grey Level Cooccurrence Matrix) • Je to čtvercová matice, která vyjadřuje, jak často se určité kombinace DN hodnot pixelů v obraze vyskytují • Z GLCM lze vypočíst popisné charakteristiky textury. Těch potom můžeme využít např. jako vstupu do klasifikace v případech, kde selhává použití spektrálních příznaků. Výpočet GLCM • Textura je počítána ze vztahu několika pixelů - pro jednoduchost dvou. Definujeme tzv. Referenční pixel (REFERENCE) a sousední pixel (NEIGHBOUR). • N pixel je k R definován v určitém směru. Napf. N je vždy ojeden pixel vpravo ( na východ) do R. Tedy pracujeme s texturou určovanou v předem dohodnutém směru. • Těchto směrů může být 8. Prostorový vztah R a N pixelů lze vyjádřit zápisem (1,0) - tedy jeden pixel v ose x a žádný v ose y. Vztah R a N ve směru západním by byl zapsán (-1,0). Každý sousední pixel se stává referenčním atd. • Matice GLCM je počítána pro okno předem definované velikosti - stejně jako v případě filtrace obrazu. • Vztah mezi R a N je také definován vzdáleností mezi R a N (tzv. offset). V našem případě je 1, ale může být i více - pak je nutné zvětšit okno. Výpočet GLCM GLCM je čtvercová matice. Počet řádků (sloupců) je dán počtem hodnot, kterého mohou pixely analyzovaného obrazu nabývat. V našem případě bude rozměr matice 4, pixely v testovacím obrázku nabývají hodnot 0,1,2,3. 0 1 2 3 55 0 0 1 1 0 2 2 í 0 0 0 1 1 1 0 2 0 0 ■ 0 2 2 2 2 2 2 0 0 3 1 Hodnoty R pixelů jsou čteny v řádcích, hodnoty N pix elů ve sloupcích. Každý prvek GLCM matice nese informaci, kolikrát se daná kombinace hodnot v okně vyskytuje. Výpočet GLCM GLCM musí být symetrická. Pro definování textury je jedno, zdajde o směr (1,0) či (-1,0) Relaci (-1,0) dostaneme záměnou R a N pixelů (zaměníme řádky a sloupce - transponujeme matici) a obě GLCM matice sečteme. GLCM GLCM transponovaná GLCM symetrická 2 2 1 0 2 Ü Ü 0 4 2 1 0 0 2 Ü 0 2 2 Ü 0 2 4 Ü 0 0 U i 1 1 U i 0 1 U 6 1 0 Ü 0 1 Ü Ü 1 1 Ü Ü 1 2 4 Výpočet GLCM Prvky GLCM se vyjadřují v hodnotách pravděpodobnosti výskytu Je pravděpodobnost najít v originálním snímku kombinaci 2,2 větší jak kombinaci 2,3? Kombinace 2,2 se vyskytuje 6 krát z 24 možností - tedy pravděpodobnost výskytu je 6/24 tj. 1/4 tj. 0,25. Pravděpodobnost členu 2,3 je 0,042. Výpočtem pravděpodobnosti je matice normalizována 0,166 0,083 0,042 0 0,083 0,166 0 0 0,042 0 0,250 0,042 0 0 0,042 0,083 Vlastnosti GLCM • Na diagonále GLCM jsou prvky, které reprezentují dvojice pixelů, jejichž DN hodnotyjsou stejné (0-0, 1-1, 2-2,...). • Mají-li buňky matice na diagonále vysoké hodnoty, znamená to, že velké procento pixelů má stejnou hodnotu jako jejich sousedé - to svědčí o malém kontrastu analyzovaného snímku. • Paralelně s diagonálou se v GLCM nacházejí buňky, které nesou informaci o pravděpodobnosti výskytu kombinací pixelů, které se liší v horizontálním směru o hodnotu 1 (0-1,1-2, 2-3), dále potom kombinace pixelů, které se liší o hodnotu 2 (0-2,1-3,...). • Tedy čím dále od diagonály GLCM, tím je větší rozdíl v hodnotách R a N pixelu. Výpočet měr textury • Většina měr textury je váženým průměrem buněk GLCM. • Princip výpočtu míry textury je stejný jako v případě filtrace obrazu. Okno předem definované velikosti - čtvercové s lichým počtem řádků a sloupců se pohybuje po originálním obraze pixel po pixelu. • Pro každou pozici okna je vypočtena GLCM a určitá míra textury jako vážený průměr. Tato hodnota je přiřazena střednímu pixelu v rámci každé pozice okna. • Výsledkem je tedy TEXTURE IMAGE, ve kterém každý pixel nese hodnotu určité míry textury • Míry textury se třídí podle účelu použitých vah. Míry textury založené na kontrastu Používá se vah, které se vztahují ke vzdálenosti buněk od diagonály GLCM. Prvky na hlavní diagonále vypovídají o kombinacích stejných pixelů - tedy s nulovým kontrastem, rostoucí vzdáleností od diagonály roste kontrast - tedy zvětšují se váhy. N-l Kontrast = X-^ j 'v~ JI Vysvětlení: Je-li i a j stejné (na hlavní diagonále) váhaje 0. Liší-li se i a j o 1 váhaje 1, liší-li se o 2 váhaje 4 atd. Váhy exponenciálně rostou. Míry textury založené na pravidelnosti Vyjadřují, jak pravidelnejšou pixely v rámci okna uspořádány. Na obrázku je část snímku s pravidelným uspořádáním pixelů a nepravidelným - v obou případech se každý pixel liší o 1 oproti svému pravému sousedu - tedy kontrast snímků určený z GLCM je stejný. V případě těchto měr jsou váhy sestavovány na základě četnosti výskytu jednotlivých kombinací pixelů. 12 3 4 12 3 4 12 3 4 12 3 4 3 4 5 12 3 2 3 4 4 5 6 V případě měr pravidelnosti tvoří váhy přímo hodnoty prvků GLCM. Váhy, které budou zvyšovat svoji hodnotu s četnějším výskytem dané kombinace pixelů budou produkovat charakteristiku textury, která bude mít vyšší hodnoty se zvyšující se pravidelností uspořádání pixelů ve snímku. Míry textury založené na pravidelnosti Dávají vysoké hodnoty pro pravidelně uspořádané části obrazu ASM (Angular Second Moment) a Energy ASM = ^P1J2 Energy =