1 Neřízená klasifikace obrazu Základní pojmy * Nevyužívá trénovaných dat, nevyžaduje a priori informaci o vlastnostech hledaných tříd * Základním předpokladem, ze kterého vychází, je to, že pixely, které patří do jedné třídy, jsou ve vícerozměrném prostoru přirozeně blízko sebe a naopak pixely odlišných skupin, které představují povrchy lišící se svým spektrálním chováním, jsou dobře separované. * Výsledkem první fáze neřízené klasifikace jsou tzv. třídy spektrální. Až jejich interpretací a postupným spojováním vznikají třídy informační. Příznakový prostor Vztah mezi počtem shluků, spektrálními a informačními třídami Algoritmy neřízené klasifikace * K vymezení odlišných skupin (shluků) v multispektrálním příznakovém prostoru lze potom využít vícerozměrné statistické metody. * K nejpoužívanější skupině algoritmů patří postupy založené na shlukové analýze. * Algoritmy založené na shlukování využívají iteračního počtu, existují i algoritmy označované jako ,,jednoprůchodové" * Neřízené algoritmy klasifikace mají i některé postupy založené na využití neuronových sítí. Metody shlukové analýzy hierarchické aglomerativní nehierarchické rozkladové optimalizační ... 2 Hierarchické metody rozkladové naopak postupně dělí vstupní soubor do 2, 3, 4, ... skupin. Aglomerativní hierarchické shlukování jednotky se postupně spojují do shluků Nehierarchické metody shlukové analýzy * Nehierarchické metody lze charakterizovat jako optimalizační. * Hledají takový rozklad množiny objektů, který je optimální podle vhodně zvoleného kritéria optimality * Mohou být založeny na předem daném (přibližném) počtu shluků a jejich postupném ,,zlepšování" převodem vybraných jednotek mezi shluky, na eventuelním spojování či rozdělování shluků. * Výpočty využívají iteračního počtu. Obecný postup shlukování 1. Definování (přibližného) počtu výsledných shluků 2. Určení počáteční polohy centroidu pro každý shluk 3. Postupné přiřazení všech pixelů k tomu shluku, k němuž mají v příznakovém prostoru nejblíže 4. Výpočet nové polohy centroidu pro každý shluk na základě přiřazených pixelů 5. Opakování kroku 3 a 4 do té doby, dokud se poloha shluku či počet pixelů zařazených do shluku výrazně nemění 6. Přiřazení konkrétního významu každému tzv. stabilnímu shluku 7. Vytváření informačních tříd spojováním (agregací) tříd spektrálních Definování počáteční polohy shluků 1. úvodní středy shluků jsou rozmístěny pravidelně po diagonále příznakového prostoru. Definování počáteční polohy shluků 2. při určité znalosti spektrálního chování tříd lze úvodní polohu definovat pomocí tzv. zakládacího souboru (seed file) ­ řádky tvoří průměrový vektor pro jednotlivé shluky pásmo 1 2 3 4 1. shluk 5 3 5 9 2. shluk 40 45 44 20 3. shluk 57 60 47 49 Použití určitého klasifikátoru a přiřazení pixelů k jednotlivým shlukům 3 Výpočet nových centroidů a přerozdělení pixelů ve shlucích Iterační postup shlukování Algoritmy shlukové analýzy * metoda K ­ průměrů (K-means) * ISODATA (Iterative Self-Organising Data Analysis Technique Algoritmy předpokládají, že dopředu známe (alespoň přibližně) počet shluků, do kterého si přejeme rozdělit vstupní soubor. Výpočet začne s k náhodnými shluky. Jednotky se poté postupně přesouvají mezi jednotlivými shluky a to tak, aby: 1. minimalizovaly variabilitu mezi jednotkami uvnitř jednoho shluku 2. maximalizovaly variabilitu mezi jednotlivými shluky Algoritmus K-means 1. Na počátku je zadán požadovaný počet shluků a pokud je k dispozici, také úvodní poloha jejich středů. 2. Úvodní polohu centroidů lze definovat jejich rovnoměrným rozmístěním ve vícerozměrném prostoru. 3. Každý klasifikovaný pixel je přiřazen do shluku, k jehož průměrovému vektoru má v analyzovaném prostoru nejblíže. 4. Jsou vypočteny nové polohy centroidů (nové průměrové vektory každého shluku). 5. Poté se celý výpočet opakuje dalšími iteracemi a to do té doby, než je dosaženo zadaného počtu iterací ­ méně vhodný výsledek. 6. Celý výpočet by měl být ukončen při splnění jednoho z ,,kritérií konvergence", v okamžiku, kdy: A. již nedochází k významnému počtu změn v zařazení jednotlivých klasifikovaných pixelů. B. průměrový vektor významně nemění polohu v prostoru Postupná změna polohy průměrového vektoru v příznakovém prostoru Algoritmus ISODATA 1. Na počátku je definován počet požadovaných shluků a počet iterací. 2. Není-li k dispozici zakládací soubor středů shluků, tyto jsou umístěny rovnoměrně v analyzovaném prostoru. 3. Vlastní zařazování pixelů do jednotlivých shluků probíhá také v jednotlivých iteracích, přičemž se řídí následujícími parametry: * Shluk, který se stane heterogenním - měřeno hodnotou násobku směrodatné odchylky, zadanou na počátku výpočtu je rozdělen na dva nové shluky. * Shluky, které jsou svými středy v analyzovaném vícerozměrném prostoru blíže, než je předem zadaná hodnota, jsou spojeny v jeden shluk. * Shluky, které obsahují méně pixelů, než je předem zadaná hodnota, jsou zrušeny a jejich pixely zařazeny ke shlukům okolním 4 Algoritmus ISODATA * V důsledku uvedeného spojování a rozdělování jednotlivých shluků v každé iteraci není výsledný počet stabilních shluků často shodný s počtem požadovaným. * Tento požadovaný konečný počet shluků je často zadáván určitým rozsahem minimálního a maximálního počtu. * Parametry, řídící spojování a rozdělování shluků, lze v průběhu výpočtu (mezi jednotlivými iteracemi) interaktivně měnit. Jednoprůchodové algoritmy (Single pass) * V případě klasifikace dvou pásem vytváří ,,dvourozměrný" histogram povrch s množstvím lokálních maxim (,,vrcholy") a minim (,,údolí"). * Jednotlivé vrcholy na tomto povrchu představují přibližně středy jednotlivých shluků, údolnice pak představují místa, kudy vede hranice mezi jednotlivými shluky. * Postup neumožňuje zadat požadovaný počet výsledných shluků a výpočet na rozdíl od předcházejících způsobů není iterační. * Metody pracují s histogramy klasifikovaných pásem obrazu. RGB Clustering ­ shlukování v RGB prostoru * Jednoduchá metoda neřízené klasifikace tří pásem, která představují složky RGB systému AMOEBA Algoritmus pracuje také s parametrem vzájemné polohy pixelů. Je definován způsob posuzování sousedství (4 či 8 pixelů). Posuzovaný pixel tvoří se svými sousedními pixely jeden shluk: * pokud nabývá podobné DN hodnoty * pokud je osamocen v homogenní ploše pixelů AMOEBA Maximální možná proměnlivost pixelů v daném shluku je definována hodnotami rozptylu či směrodatné odchylky. Pixely určité třídy postupně vytvářejí víceméně souvislé části obrazu. Pokud pixely tvořící jednu třídu (shluk) obklopují dosud nezařazený obrazový prvek a jeho zařazením do dané třídy by nedošlo k překročení jeho předem definovaného rozptylu hodnot, je tento obrazový prvek zařazen do daného shluku. Tento postup tedy funguje jako speciální filtrace obrazu. Dává dobré výsledky u snímků s rozsáhlými homogenními plochami a malou variabilitou DN hodnot Hybridní klasifikace I. * Využívá výhod obou postupů klasifikace * Neřízená klasifikace slouží k nalezení homogenních ploch. * Tyto spektrálně homogenní plochy mohou sloužit přímo jako plochy trénovací * Mohou však také pouze vymezovat míst ve zpracovávaném obraze, na kterých je následně provedeno trénování pro řízenou klasifikaci. * Výsledné třídy mají povahu tříd spektrálních a jsou agregovány do výsledných kategorií druhů povrchů 5 Hybridní klasifikace II. * Využívá ,,unsuppervised training areas" * Jsou zvoleny části obrazu, které se na rozdíl od ,,suppervised" trénovacích ploch vyznačují co největší heterogenitou. * Cílem je postihnout co nejvíce spektrálních tříd. Ty jsou dále podrobeny shlukování a statistické analýze. * Podobné shluky jsou spojeny a je jim přiřazen geografický význam * Následně je klasifikována celá scéna metodou řízené klasifikace Úprava výsledků neřízené klasifikace Shlukováním vytvořené spektrální třídy jsou agregovány do informačních tříd, které odpovídají klasifikačnímu systému výsledné tématické mapy. Pokud jedna spektrální třída obsahuje pixely více než jedné třídy informační je nutné proces shlukování opakovat: * s větším počtem shluků * s modifikovanými parametry spojování či rozdělování shluků (ISODATA) * s jinými vstupními pásmy ­ například s pásmy transformovanými metodou PCA Hodnocení výsledků klasifikace Klasifikace není ukončena, dokud není zhodnocena její přesnost. Pro chyby v klasifikaci obrazu platí následující: * chybně klasifikované pixely se ve výsledném obrazu nevyskytují náhodně, ale mají určité prostorové uspořádání * chybně klasifikované pixely jsou více méně asociovány pouze s určitými třídami * chybně klasifikované pixely se většinou nevyskytují izolovaně, ale v určitých skupinách * chybně klasifikované pixely jsou svým výskytem vázány na typické části klasifikovaných ploch Klasifikační chybová matice 90,850,000,000,000,009,1510605holá p. 0,0086,790,000,000,0013,216664ttp 0,000,0092,720,000,007,288933pole 0,000,000,0089,440,0010,5610892les 0,000,000,000,0088,5511,4512231voda 543210počet pixelůkódtřída Průměrná přesnost = 89,67 % * Počty mimo hlavní diagonálu představují chyby v klasifikaci. * Průměrná přesnost = suma na hlavní diagonále / počet posuzovaných pixelů Hodnocení výsledků klasifikace s využitím testovacích dat * chyby z opomenutí (vynechání) -ve sloupcích mimo hlavní diagonálu * chyby z nesprávného zařazení - v řádcích matice mimo hlavní diagonálu * přesnost z hlediska uživatele ­ představuje pro každou třídu počet správně klasifikovaných pixelů (hodnota na hlavní diagonále) dělený celkovým počtem pixelů, které do této kategorie byly zařazeny (suma v řádce). * přesnost z hlediska zpracovatele - poměr mezi počtem správně klasifikovaných pixelů (tedy opět hodnota na hlavní diagonále) a počtem pixelů použitých pro testování dané třídy (suma ve sloupci). Hodnocení výsledků klasifikace s využitím testovacích dat Průměrná přesnost: (480 + 52 + 313 + 126 + 342) / 1432 = 92 % CHU - chyba z opomenutí CHZ - chyba z nesprávného zařazení PU - přesnost z hlediska uživatele PZ - přesnost z hlediska zpracovatele 6 Hodnocení výsledků klasifikace - Kappa koeficient: * Porovnává klasifikaci provedenou podle určitého rozhodovacího pravidla s klasifikací vzniklou čistě náhodným procesem zařazování pixelů do jednotlivých tříd. * Jeho výpočet je založen na předpokladu, že i při čistě náhodném procesu zařazování pixelů zpracovávaného obrazu do jednotlivých tříd bude určité procento těchto pixelů zařazeno správně. * Potom hodnotu koeficientu Kappa lze zjednodušeně vyjádřit následujícím způsobem: = - PP PO PO1 kde PP - přesnost pozorovaná (určená z chybové matice) PO - přesnost dosažitelná čistě náhodným zařazením pixelů do jednotlivých tříd Úprava výsledků klasifikace Hlavní metodou post-klasifikačních úprav bodových klasifikátorů jsou nízkofrekvenční filtrace. * Postklasifikační shlazení výsledků ­ modální filtrace * Sieve filter ­ odstranění ploch určité velikosti Vektorizace a generalizace tvarů Modální filtrace ,,SIEVE" filtr (síto) FILE Database File Name DBIC Database Input Channel List DBOC Database Output Channel List STHRESH Polygon Size Threshold KEEPVALU Values not to be filtered CONNECT Connectedness of Lines (4 or 8)