10. Analýza rastrového obrazu (100%)

tags: `zpracovaniObrazu`, `PB130`,`PV131`

Segmentace obrazu, algoritmy značení komponent, popis objektů, klasifikace objektů
Výpočet mapy vzdáleností
Základy matematické morfologie
- dilatace a eroze
- otevření a uzavření
- hit-or-miss
- top-hat
- watershed

Analýza

Typické fáze analýzy

Předzpracovnání obrazu
- Potlačení šumu, odstranění nerovnoměrného osvitu, apod.
Segmentace obrazu
- Rozklad definičního oboru na oblasti odpovídající objektům
Popis objektů
- Určení atributů/vlastností objektů nutných pro rozpoznání
Klasifikace objektů
- Rozdělení objektů do tříd podle jejich atributů
Porozumění obrazu
- Porozumění smyslu objektů v obraze

Segmentace obrazu a algoritmy značení komponent

Dělení nebo separace obrazu na segmenty (regiony, spojené množiny) podobných vlastností (atributů)

Haralick and Shapiro „Oblasti by měly být jednotné a homogenní s ohledem na některé charakteristiky, jako je intenzita nebo textura. Interiéry regionů by měly být jednoduché a bez mnoha malých děr. Sousední oblasti by měly mít výrazně odlišné hodnoty s ohledem na charakteristiku v rámci které jsou jednotné. Hranice každého segmentu by měly být jednoduché, ne členité, a musí být prostorově přesné.“

Definice:

Sousedé daného pixelu
- 2D: Horizontální a vertikální sousedé, 4-sousedé, 8-sousedé,
- 3D: 6-sousedé, 18-sousedé, 26-sousedé,
Sousedství dvou pixelů
- 2D: 4-sousedství pixely, 8-sousedství pixely
- 3D: 6-sousedství pixely, 18-sousedství pixely, 26-sousedství pixely
Cesta mezi dvěma pixely
- Sekvence rozdílných pixelů
  $p_{0}, . . ., p_{n}$ takových že
  $p_{0}$ a
  $p_{n}$ jsou ony dva pixely a
  $p_{i}$ a
  $p_{i + 1}$ jsou sousedící pixely pro každé
  $0 \leq i \leq n - 1$
- $n$ je délka cesty
- 2D: 4-cesta, 8-cesta
- 3D: 6-cesta, 18-cesta, 26-cesta
Spojené pixely
- Uvažujme podmnožinu
  $S$ pixelů obrázku
- Dva pixely jsou spojeny v
  $S$ pokud mezi nimi existuje cesta složená pouze z pixelů podmnožiny
  $S$
Souvislá komponenta množiny
- Uvažujme podmnožinu
  $S$ pixelů obrázku
- Pro každý pixel v
  $S$ , množina s ním spojených pixelů v
  $S$ se nazývá souvislá komponenta
  $S$
Souvislá množina
- Uvažujme podmnožinu
  $S$ pixelů obrázku
- Pokud
  $S$ má pouze jednu souvislou komponentu, pak se
  $S$ nazývá souvislá množina
- Souvislá množina se také nazývá region, oblast nebo segment obrazu
Hranice oblasti
- Množina pixelů v regionu které mají alespň jednoho souseda mimo region

Prahování

Prahuje sa v Prahe často? … Badumtsss

Pixely jsou rozděleny na regiony podle jejich intenzity: pixely s intenzitou menší než zadaný práh patří do jiného regionu než pixely s intenzitou větší.

Globální prahování = prahování
- Práh je stejný pro všechny pixely obrazu (nezávisle na jejich pozici)
Lokální (adaptivní) prahování
- Práh závisí na pozici pixelu v obraze
Určení prahu
- Manuální - práh je nastaven uživatelem
- Automatcké - analýza histogramu intenzity

Dvouúrovňové prahování

Pokud je obrázek jednoduchý (předměty podobné intenzity na uniformním pozadí, např. zadaný text nebo buňky stejného typu), histogram obsahuje dva vrcholy s údolím mezi nimi. Hranice je převzata v údolí (na lokálním minimu mezi dvěma maximy).
Pro přesnější určení minima může být údolí proloženo parabolou.
Pokud histogram neobsahuje dvě maxima, může pomoci výpočet histogram pixelů, které mají velký Laplacián

Obrázky s unimodální distribucí

Pokud histogram obsahuje pouze jeden zřejmý vrchol, nazýváme takový obrázek obrazem s unimodální distribucí
Nejjednodušší metodou je vzít X% nejvíce/nejméně intenzivních pixelů jako objekt, zbytek jako pozadí (např. X=10 %)
Sofistikovanější metoda (Rosin)
- Nakresli úsečku od maxima k druhé straně histogramu
- Úsečka začíná na nejvetším sloupci a končí na prvním prázdném sloupci za posledním neprázdným sloupcem
- Práh je index
  $i$ který maximalizuje kolmou vzálenost mezi úsečkou a bodem
  $(i, h (i))$
- Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

Shlukování histogramu

Uvažujme dvě skupiny pixelů - popředí a pozadí
Každá skupina má svůj vlastní rozsah a distribuci
Rozsahy se obvykle překrývají
Místo minimálního překryvu nemusí být údolí
Cílem je minimalizovat chybu klasifikace pixelu pozadí jako pixel popředí a naopak
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

Algoritmus:

Zvol práh
$T$

Rozděl obraz do dvou shluků (před a po prahu
$T$ )

$μ_{B} (T)$ = průměr pixelů s hodnotou menší než práh T

$μ_{O} (T)$ = průměr pixelů s hodnotou větší než práh T

Vyhodnoť
$T = \frac{μ_{B} (T) + μ_{O} (T)}{2}$ a opakuj dokud algoritmus nezkonverguje

Shlukování histogramu (Otsu 1979)

Idea - Najdi práh který minimalizuje vážený rozptyl v rámci třídy
Stejné jako maximalizovat rozptyl v rámci třídy
Operuje přímo na šedotónovém histogramu (např. 256 hodnot) což je rychlé
Předpokládá uniformní nasvětlení a bimodální nebo multimodální distribuci histogramu
Lze modifikovat pro lokální použití

Algoritmus:

Pro každý práh
$T$ :

Rozděl pixely do dvou shluků a dle prahu
$T$

Najdi průměry
$μ_{B} (T)$ a
$μ_{O} (T)$ pro každý shluk

Najdi rozptyl
$δ_{b e t w e e n} (T)$

Najdi maximální rozpyl

Gradientní prahování (McAulay)

Idea - Mezi jakýmkoli objektem a pozadím je zřejmá hrana, intenzity na hranách jsou nejdůležitější.
Vyhodnocení: Vážený součet všech hodnot na obrázku, klást důraz na ty, které jsou v blízkosti silných hran.
$T = \sum_{m} f (m) \cdot \frac{| ▽ f (m) |}{\sum_{n} | ▽ f (n) |}$

Víceúrovňové prahování

Idea - Pokud obrázek obsahuje několik typů objektů na uniformním pozadí a každý typ objektu má specifický rozsah intenzity, (např. směs buněk více typů), histogram obsahuje několik vrcholů s údolími mezi nimi.
Je přijato několik prahů, jeden práh na každé údolí (na lokálním minimu mezi dvěma sousední maxima).
Pro přesnější určení minima může být údolí proloženo parabolou.

Prahování barevných obrázků

Prahování je provedeno na každý barevný kanál zvlášť (RGB).
Prahování se neprovádí podle intenzity, ale podle odstínu, sytosti nebo jiných charakteristik.
Uživatel (nebo počítač) vybere konkrétní rozsahy barev pro každý typ objektu.

Lokální (Adaptivní) prahování

Problém
- A) Nerovnoměrná intenzita pozadí
- B) Stejnoměrná intenzita pozadí, ale nerovnoměrná intenzita objektu, která netvoří jednotlivé píky v histogramu (píky se v histogramu překrývají a tvoří jeden širší vrchol)
Řešení:
1. Obrázek je rozdělen na pravidelné podoblasti (např. čtverce) a práh se nastavuje individuálně pro každý region pomocí analýzy histogramu vypočítaného z této konkrétní oblasti.
  - Nepříliš dobré výsledky na okrajích mezi oblastmi.
2. Stejné jako 1., ale jsou určeny prahové hodnoty pro jednotlivé pixely pomocí interpolace prahové hodnoty mezi regiony.
  - Dobré v případě A), ale ne v případě B).
3. Nejprve se provede globální prahování, aby se oddělilo pozadí objektů. Poté se pro každý objekt vypočítá histogram lokální intenzity a je stanovena prahová hodnota. Všechny objekty jsou přesegmentovány pomocí jednotlivých prahů
  - Dobré v případě B), ale problémy nastanou, když se dva typy objektů (různých intenzity) vzájemně dotýkají a je s nimi zacházeno jako s jednou oblastí po iniciálním globálním prahování.

Hysterezní prahování

Použijí se dva prahy, nízký a vysoký.
Pixely s hodnotou vyšší než je vysoký práh jsou označny jako objekt
Pixely s hodnotou vyšší než je nízký práh jsou označny jako objekt pouze pokud v obrázku vytvořeném prahováním nízkým prahem existuje cesta mezi tímto pixelem a libovolným pixelem, který je již jako objekt označen.
Ostatní pixely jsou označeny jako pozadí.
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

Metody založené na oblastech

Iterační metody založené na slučování a/nebo dělení oblastí na základě stupně podobnosti vlastností (atributů) oblasti.

Narůstání oblastí (Region growing)

Inicializace: Obraz je rozdělen do velkého počtu segmentů (oblastí).
Počáteční oblasti mohou být tvořeny dokonce jednotlivými pixely.
Iterace: Sousední oblasti jsou seskupeny, pokud jsou jejich vlastnosti (většinou intenzita) podobné.
Poznámky:
- Je dobré klást určitá omezení na proces slučování
- Omezení mohou být poměrně složitá

Štěpení a slučování (Split and Merge)

Vstup:
1. Původní obrázek (jedna oblast).
2. Jednotlivé pixely (mnoho oblastí).
3. Střední počet oblastí.
Iterace:
- Oblasti, které nejsou homogenní, jsou rozděleny do několika menších oblastí
- Sousední oblasti, které mají podobné vlastnosti, jsou sloučeny dohromady.

Podmínky pro rozdělení a sloučení mohou být poměrně složité.
Často se používá metoda Quad-Tree
- Nehomogenní oblasti se rozdělují na 4 stejné podoblasti (kvadranty)
- 4 sousední oblasti podobných vlastností se stejným rodičem se v rámci možností spojují dohromady.
- Následuje sloučení regionů na různých úrovních pyramidy nebo mající jiného rodiče.

Segmentace největší kontury (Largest Contour Segmentation - LCS)

Odfiltrování šumu (průměr nebo medián)

Velikost jádra závisí na typu a velikosti šumu

Určení lokálních maxim a minimální intenzity v obraze (
$G l o b a l M i n I$ )

Výpočet středů lokálních maxim, tj. redukce lokálních maxim na 1 pixel.

Pro každé lokální maximum:
4.1) Současný práh
$(C u r T) = ($ Maximální intenzita
$(L o c a l M a x I) + G l o b a l M i n I) / 2$
4.2) Počet iterací
$(I) = 0$
4.3) Provede se růst oblasti od středu lokálního maxima tak, aby byly zahrnuty všechny sousední pixely, jejichž intenzita
$\geq C u r T$ .
4.4)
$N$ = počet středů uvnitř tohoto regionu.
4.5)
$I = I + 1$
4.6) Pokud
$I = B i t D e p t h$ , dokončíme iteraci pro daný střed a přejdeme ke kroku 5.
4.7) Pokud
$N > 1$ ,
$C u r T = (C u r T +$ předchozí vyšší prahová hodnota
$) / 2$
4.8) Pokud
$N = 1$ ,
$C u r T = (C u r T +$ předchozí spodní prahová hodnota
$) / 2$
4.9) Přejdeme na krok 4.3

Pokud
$N > 1$ , Konečný práh
$(F i n T) = C u r T + 1$ Pokud
$N = 1$ , konečný práh
$(F i n T) = C u r T$

Ukázka:

Systematická chyba
- Objekt je často protáhlý směrem k sousednímu objektu (objektům)
- Hranice objektu je nepřesná
- Střed objektu je posunut směrem k sousednímu objektu (objektům)

Segmentace pomocí detekce hran

Určení hranic objektů ze snímku okrajové mapy
Konstrukce šedotónové mapy hran
- První derivace původního obrázku (např. Sobelův filtr)
- Druhá derivace původního obrázku (např. Laplaceův filtr)
Konstrukce binární mapy hran
- Vytvoření binárního obrázku (např. prahování)
  - 1 představuje hranové pixely
  - 0 představuje ostatní pixely
Problémy s šumem
- Před zvýrazněním hran (high-pass filtr) by měl být šum redukován vyhlazením (low-pas filtr)
Kombinace vícero směrů
- Často jsou detekovány hrany v několika směrech a výsledky jsou kombinovány (např. Sobelův filtr)
- Používají se různé techniky: maximum, součet (průměr), odmocnina ze součtu čtverců atd.
Post-processing šedotónové mapy hran
- Ztenčení hran na šířku 1 pixelu (např. Canny)
Konstrukce binární mapy hran
- Prahování nebo hysterezní prahování (dvojité prahování) šedotónové mapy hran pro získání pouze relevantních hran.

Problém - Hranice v prahované mapě hran nejsou souvislé!

Řešení 1 - Proložení křivkou (Curve fitting)
- Předpokladáme že objekty na obrázku jsou jednoduché, okrajová mapa neobsahuje větve.
- Iterativní přizpůsobení koncového bodu
- Proložení polygonem
- Proložení polynomem
- Bezierův polynom nebo spline
Řešení 2 - Heuristické spojování hrany
- Předpokladáme že objekty na obrázku nejsou příliš složité.
- Hraniční body jsou propojeny čarami pomocí určitého heuristického algoritmu
- Následně jsou vymazány vícenásobné spoje a větve a hraniční fragmenty spojeny tzv. „mosty“
Řešení 3 - Houghova transformace
- Předpokladáme že objekty na obrázku nejsou příliš složité.
- Hledáme známé tvary (např. čáry, kruhy, čtverce atd.)

Segmentace textur

Rozdělení obrazu do oblastí na základě charakteristik textury.
Metoda 1 (Rosenfeld et al.)
- Míra textury je definována a vypočítána pro všechny pixely (v určitém okolí daného pixelu).
- Textura je tedy převedena na amplitudu a poté je použita jedna z metod segmentace amplitudy
- Nevýhoda - hranice textur jsou rozmazané.
Metoda 2 (Thompson)
- Jsou detekovány přechody mezi oblastmi s různou texturou čímž se vytvoří okrajová mapa.
- Okrajová mapa je zpracována podobně jako segmentace pomocí detekce hran
- Nevýhoda - okraje nejsou souvislé.

Metody shlukování

Metody založené na analýze shluků.
U každého pixelu obrázku je vypočítán vektor
$x = [x_{1}, . . ., x_{N}]$
$N$ různých měření (vlastností) (obvykle
$N$ je asi 10).
Měří se různé uživatelsky definované charakteristiky.
Poté se provede shluková analýza v
$N$ -rozměrném prostoru, tj. ty pixely, které tvoří shluk v N-rozměrném prostoru, jsou segmentovány do jedné oblasti.
Výhoda - Snadné
Nevýhoda - Pomalé

Srovnávání se vzorem

Hledání šablony (vzoru) v obrázku výpočtem korelace mezi vzorem a hledanými daty obrázku.
Vyhodnoťí se kritérium shody pro každé umístění a otočení vzoru na obrázku.
Lokální maxima tohoto kritéria překračující přednastavený práh představují umístění vzoru v obraze.
Nevýhody:
- Velmi časově náročné, zvláště u velkých vzorů.
- Citlivé na geometrické zkreslení obrazu.

Popis objektů

Proč popisovat obrázky/objekty?

Popisovače – deskriptory

Popisovač je funkce, která pro daný obraz, oblast obrazu (často odpovídající nalezenému objektu), nebo hranici objektu vrátí popis vlastnosti nebo atributu
Popisem může být
- Číslo
- Vektor hodnot
- Řetězec
- Graf
- A další
Úrovně
- Globální deskriptory
  - Popis celého obrazu
- Lokální deskriptory
  - Extrakce zajímavých rysů z obrazu
  - Rohy, lokální struktury, apod.
  - Není nutná segmentace
- Deskriptory objektů
  - Nutná segmentace
  - Citlivé na okluzi, šum a vzorkování
  - Popis tvaru, textury, barvy, apod.

Obrázky nebo předměty je třeba popsat, aby bylo možné provést následnou klasifikační fázi.
Obvykle se počítají ty atributy, které jsou potřebné pro klasifikaci.
Alternativně lze popis použít pro vyhledávání podobných obrázků nebo předmětů ve velké sbírce.
Vyhledávání se provádí na základě podobnosti popisů (podpisů), které jsou stručné a indexované pro zvýšení rychlosti.
K jejich popisu není nutná žádná a předchozí znalost obrázků nebo předmětů.
Preferujeme deskriptory, které jsou invariantní vůči translaci, měřítku, rotaci a ideálně i zkreslení.
Existují také standardizované sady deskriptorů, např. MPEG-7

Analýza atributů

Analýza intenzity (střední a maximální intenzita, rozptyl intenzity atd.)
Analýza histogramu (centrální momenty, uniformita, entropie atd.)
Analýza frekvencí (Fourierova spektrální analýza)
Analýza barev
Analýza textury

Atributy objektů

Ohraničující obdélník (Bounding box)

Nejmenší ohraničující obdélník ve 2D (nebo ohraničující kvádr ve 3D) (
- ve 2D: obdélník o minimální ploše, který obsahuje daný objekt
- ve 3D: rovnoběžnostěn o minimálním objemu, který obsahuje daný objekt
Rozlišujeme
- Obrazově orientovaný ohraničující rámeček (orientovaný podél os obrázku)
- Objektově orientovaný ohraničovací rámeček (orientovaný podél hlavní osy objektu)
Lze spočítat
- Rozměry a velikost ohraničujícího rámečku (plochu nebo objem)
- Poměr velikosti rámečku k velikosti objektu

Průměr

Orientace ohraničovacího rámečku určuje také měření průměru
Maximální a minimální průměr lze intuitivně definovat jako nejdelší a nejkratší šířku ohraničovacího rámečku respektině.

Kruhovost

Parametr udávající (od 0 do 1) jak moc je daný objekt blízký ideálnímu kruhu
- $C i r c u l a r i t y (R) = 4 π \frac{A r e a (R)}{P e r i m e t e r^{2} (R)}$

Konvexní obal

Nejmenší polygon, který obsahuje všechny pixely regionu
$R$
Využití k výpočtu hustoty (poměr obsahu objektu k obsahu jeho konvexního obalu)

Moment setrvačnosti

Míra setrvačnosti tělesa při otáčivém pohybu
Na nalezený objekt, tj. množinu jeho pixelů R (ne nutně souvislého) se díváme jako na rozložení hmotnosti v objektu
Můžeme spočítat jeho těžiště (centroid) a tzv. centrální momenty z nichž lze spočítat natočení objektu

Feretův průměr

Umožňuje měření průměru v libovolném směru (pro libovolný úhel)
Je definován jako délka projekce objektu v daném směru
Rovná vzdálenosti mezi dvěma rovnoběžnými čarami (s daným sklonem), které jsou kolmé k hranicím objektu z opačných stran

Hranice

Obvykle reprezentována jako zakódovaný řetězec bodů
Je uložena pouze absolutní poloha prvního bodu a poté jsou uloženy pouze směry z jednoho bodu do druhého - Tzv. Freemanův kód (Freeman 1961)
Má své vlastní vlastnosti, které lze také vypočítat.
- Křivost - definována jako zlomek mezi počtem hraničních pixelů, kde hranice výrazně mění svůj směr, a celkovým počtem hraničních pixelů.
- Členité okraje s vysokým zakřivením (úzké výstupky, úzké zálivy atd.) jsou často následkem prahování.
  - Aby se tomuto efektu zabránilo, je užitečné použít morfologické transformace po prahování (např. otevření/zavření).
  - Pozor, po morfologickém zpracování se u objektů změní i další parametry (nejen hranice, ale i např. obvod)!

Souřadnice

Souřadnice rohu obrazově orientovaného ohraničujícího obdélníku (např. levý dolní roh ve 2D)
Souřadnice jednoho z hraničních bodů (např. nejspodnější levý hraniční bod ve 2D)
Geometrický střed objektu
- Průměr všech souřadnic pixelů/voxelů objektu, tj. součet všech souřadnic pixelů/voxelů objektu dělený počtem pixelů/voxelů objektu
Těžiště objektu (centroid)
- Vážený průměr všech souřadnic pixelů/voxelů objektu s váhami danými intenzitami, tj. součet všech souřadnic pixelů/voxelů objektu vynásobený jejich intenzitami dělený součet intenzit všech pixelů/voxelů objektu)

Prostorová orientace

Směr podlouhlého předmětu
- Směr delší strany minimálního ohraničujícího obdélníku
Lze rozlišit obrazově objektově orientovaný ohraničující obdelník
Lze vypočítat minimální poloměr a maximální poloměr (vzhledem ke středu objektu a hranici objektu), jejich úhly a také poměr těchto dvou délek a/nebo úhlů.
Orientaci lze spočítat z centrálních momentů druhého řádu
- Měření orientace pomocí momentů je obecně velmi přesné

Průměrná a maximální intenzita

Průměrná a maximální hodnota přes všechny intenzity pixelů/voxelů objektu
Lze vypočítat rozptyl intenzit jako směrodatnou odchylku těchto hodnot

Velikost (plocha nebo objem)

Počet pixelů/voxelů objektu vynásobený velikostí pixelů/voxelů
Vznikají artefakty způsobené hraniční pixelací

Podlouhlost (elongatedness/eccentricity)

Podlouhlost objektu lze spočítat přímo z centrálních momentů druhého řádu

Obvod nebo povrch

Počet hraničních pixelů/voxelů vynásobený konstantou (např. šířkou čtvercového pixelu ve 2D)
Generování hraničního řetězce (Freemanův kód) ve 2D a výpočet součtu
- Součet horizontálních/vertikálních kroků násobených konstantou (např. 1) plus součet diagonálních kroků násobených jinou konstantou (např.
  $\sqrt{2}$ )
Vznikají artefakty způsobené hraniční pixelací

Profily neboli projekce

Projekce počtu jedničkových pixelů podél dané osy
Je možné je použít pro analýzu struktury dokumentů
Často se provádí podél hlavní osy

Topologické vlastnosti

Mezi důležité vlastnosti objektů patří i jejich topologické vlastnosti, například počet souvislých komponent
$N_{C}$ nebo počet souvislých děr
$N_{H}$
Eulerovo číslo
$N_{E}$ udává rozdíl mezi počtem souvislých komponent a počtem jejich děr

Atributy textur

Nejsou vázány na výsledek segmentace (region
$R$ ), ale lze je použít i například před segmentací textur
Typicky kombinují informaci z lokálního okolí
- Například pomocí matice současného výskytu (co-occurrence matrix – Haralick 1973)
- Lokální binární vzory (local binary patterns – Ojala 1996)

Matice současného výskytu

Počítá jak časté jsou výskyty stejných hodnot v zadaném směru
$Δ x$ ,
$Δ y$
Před výpočtem se často provádí kvantizace kvůli snížení počtu úrovní

Haralickovy rysy

Nad maticí současného výskytu po normalizaci se počítají různé statistiky/charakteristiky
Např. různé momenty, míra korelace hodnot, apod.

Lokální binární vzory

Základní myšlenka spočívá v nahrazení pixelu na dané pozici 8-bitovým číslem, které udává výsledek porovnání dané hodnoty s hodnotami v osmi okolí
Deskriptor zobecněn i pro větší okolí
V praxi dosahuje často velmi dobrých výsledků (je invariantní k nerovnoměrnému osvětlení)
Byl rozšířen i na rotační nezávislost

Lokální detekce vlastností + popisy

Kromě globálních prvků (jako jsou Haralickovy) lze počítat i lokální prvky = zajímavé/dominantní body v obrázku.
To lze provést např. detekcí lokálních maxim a minim v pyramidě HPF napříč stupnicemi.
Každému zajímavému bodu jsou přiřazeny jeho souřadnice a další charakteristiky (např. síla, orientace atd.)
Nejedná ani o segmentaci (obrázek není rozdělen na oblasti), ani o detekci objektů (objekty nejsou extrahovány, pouze jejich rohy a další dominantní body, ale bez znalosti toho, které body patří ke kterému objektu)
Lokální extrakce rysů je však více než jen globální analýza obrazu a je dobrým kompromisem, pokud není třeba extrahovat objekty nebo je těžké je extrahovat.

Klasifikace objektů

Klasifikační krok se pokouší zařadit obrázek nebo objekty detekované během kroku segmentace do několika tříd.
Vlastnosti jednotlivých tříd musí být známy předem.
Počet tříd je také obvykle znám předem – je odvozen od specifikace problému.
Obrázky/objekty jsou obvykle klasifikovány podle jejich popisů, které jsou porovnávány s popisy jednotlivých tříd.

Přístupy ke klasifikačním krokům

Formální popis je konstruován (známý algoritmus).
- Pokud lze napsat formální popis, lze klasifikátor celkem snadno realizovat pomocí vhodného programovacího jazyka.
- Formální popis složitějších tříd je často psán přesně pomocí formálních gramatik (formálních jazyků), predikátové logiky nebo jiných matematických nástrojů.
Klasifikátor je trénován na sadě příkladů (učení pod dohledem).
- Počítač se krok za krokem učí, který vstup (který atributový vektor) odpovídá které třídě.
- Nejčastějším přístupem ke klasifikaci založeném na učení na sadě příkladů jsou neuronové sítě nebo přístup pomocí vektorových strojů.
Klasifikátor není vyškolen (učení bez dozoru).
- Klastrová analýza je typicky aplikována na body ve vícerozměrném prostoru, kde osy prostoru odpovídají měřeným atributům obrázku/objektu a každý bod představuje jeden obrázek/objekt. :::

Učení pod dohledem (Supervised Learning)

Lineární klasifikátory
- Body (atributové vektory) ve vícerozměrném prostoru atributů jsou rozděleny do shluků pouze pomocí nadrovin (hyperplane), žádné jiné hranice tříd nejsou povoleny.
Support Vector Machine (SVM)
- Cílem je najít takovou nadrovinu, která má největší okraje
- je povolen n-rozměrný prostor transformovat nelineárně, tak že konečná hranice není nadrovina
Klasifikátory k-nejbližších sousedů (k-NN)
- Neznámému vstupu je přiřazena stejná třída jako většině jeho nejbližších k sousedů (které patří do trénovací datové sady se známými třídami)

Učení bez dozoru (Unsupervised Learning)

Hierarchické shlukování (shlukování založené na konektivitě)
- Podobně rostoucím regionům
- Začne každým objektem/obrázekem patřím do jiné třídy
- Sloučí ty nejbližší
- Následně se iterativně uvolňuje kritérium blízkosti (nebo naopak, jako rozdělení regionů)
- Vytváří celou hierarchii klastrů:
K-Means (shlukování založené na centroidech)
- Shluky jsou reprezentovány centrálním vektorem, který nemusí být nutně součástí souboru dat
- Počet shluků pevně stanoven na
  $k$ , K-Means shlukování je optimalizační problém:
  - Nalezni
    $k$ středů shluků a přiřaď objekty nejbližšímu středu shluku tak, že součet čtverečních vzdáleností od středu shluku je minimalizován.
- Samotný optimalizační problém je NP-těžký, takže běžný přístup je hledat pouze přibližná řešení, typicky se používá následující iterativní algoritmus:
Shlukování založené na distribuci
- Předpokládá, že body ve shluku jsou rozmístěny podle určitého známého rozdělení, typicky Gaussova rozdělení
- Pomocí optimalizační procedury přizpůsobí známou distribuci datům tak, aby vytvořily shluky:

Měření kvality klasifikace

Je třeba Ground Truth (GT)

Získání Ground Truth (GT)

GT není známá, je určeno odborníky
- Obvykle pouze pro určitou část obrazových dat
- Velmi subjektivní, odhady se u komplikovaných nebo rozmazaných/zašuměných snímků mohou mezi odborníky výrazně lišit
- Za účelem snížení chyb v GT může být zapojeno několik odborníků a jejich GT sloučeny (většinové hlasování)
GT je známá, je určena z předchozích znalostí
- Získávají se objekty známých vlastností (standardizované testovací objekty, fantomy lidských orgánů v lékařském zobrazování atd.)
- GT lze snadno určit, protože máme k dispozici obraz i skutečný předmět, který jsme získali (můžeme se ho dotýkat, měřit ho, počítat jeho vlastnosti atd.)
GT je přesně a úplně známá pro velký soubor dat
- Vstupní objekty i jejich obrázky jsou simulovány, tj. používáme syntetické testovací objekty v paměti počítače (digitální fantomy)
- Můžeme generovat velké datové sady společně s GT, bez lidské práce!

Kontrola kvality Ground Truth (GT)

Výsledky segmentace
- GT = správná binární maska
- Kvalita (přesnost) algoritmu lze měřit na základě korelačních koeficientů (překrytí vypočítané a GT masky) např. Jaccardův index podobnosti nebo Diceův koeficient
Výsledky měření (pozice, délka, velikost/plocha/objem)
- GT = správná hodnota měření
- Chyba = rozdíl mezi naměřenou hodnotou a GT
- Přesnost lze měřit na základě rozložení chyb (histogram)
Výsledky klasifikace
- GT = správná třída pro každý pixel/voxel/objekt/obrázek
- Kvalita algoritmu lze měřit na základě poměrů TP/FP/TN/FN
Statistické výsledky
- GT = správná míra výskytu (v procentech) pro každou třídu
- Přesnost lze měřit na základě srovnání hodnot v procentech

Mapa vzdáleností

Každému bodu popředí přiřadíme jeho vzdálenost (v dané metrice) k nejbližšímu bodu pozadí
Význam popředí a pozadí lze zaměnit (vzdálenosti počítáme pro body pozadí) a případně kombinovat do jednoho obrazu pomocí různého znaménka

Algoritmus pro
$D_{4}$ a
$D_{8}$

Nutné pouze 2 průchody

Zleva doprava a shora dolů (dopředný)

Zprava doleva a zdola nahoru (zpětný)

Aktualizace vzdálenosti na základě již navštívených pixelů

Popsaný dvouprůchodový algoritmus lze použít pro každou regulární metriku
- Regulární  vzdálenost je možné propagovat inkrementálně
Euklidovská metrika není regulární

Využití

Oddělení dotýkajících se objektů
Výpočet morfologických operátorů
Výpočet geometrických reprezentací a měr (např. kostry, Voroného diagramy, osy souměrností, apod.)
Navigace robotů
Porovnávání vzorů

Časté metriky vzdálenosti

Euklidovská metrika
$D_{E}$
Šachovnicová metrika
$D_{8}$
Taxikářská metrika
$D_{4}$

Voroného diagramy

Každému objektu je přiřazena taková oblast definičního oboru, že všechny body v této oblasti mají menší vzdálenost k přiřazenému objektu než k jakémukoli jinému objektu
Lze spočítat aplikací algoritmu záplava (MM) na mapu vzdáleností
Dilatace s různými aproximacemi disku pomocí prahování mapy vzdáleností

Porovnávání vzorů

Vzory v obraze lze vyhledávat pomocí křížové-korelace (odpovídá konvoluci s překlopením vzoru
$P$ )
Normalizovaný součet vzdáleností (matching score) pixelů vzoru
$P$ od objektů v obraze

Matematická morfologie

Transformace
- Binární
- Šedotónové
Transformace fungují v lokálním sousedství každého pixelů (podobně jako konvoluce) definovaném tzv. strukturním prvkem.
Strukturní prvek může být čtvercový, křížový nebo jakýkoli jiný tvar s definovaným počátkem (referenční bod).
Referenční bod nemusí patřit do masky definované elementem

Dilatace

Nahradí centrální pixel maximem jeho sousedů.

Eroze

Nahradí centrální pixel minimem jeho sousedů.

Uzavření

Dilatace následovaná erozí.
Spojuje husté aglomerace lokálních maxim dohromady, vyplňuje malé dírky a vyhlazuje hranice.

Otevření

Eroze následovaná dilatací.
Odstraňuje jednotlivá lokální maxima, tenké čáry a rozděluje objekty spojené úzkou cestou.

Příklad: a. Originál b. Po 2 cyklech eroze c. Po 4 cyklech eroze d. Po 7 cylech eroze - separováno e. po 4 cyklech dilatace z obrázku d. f. po 7 cyklech dilatace (logika prevence spojení objektů) g. po 9 cyklech dilatace s omezením na vlastnosti původních okraju

Hit-or-miss

Skládá se ze dvou disjunktních množin se stejným počátkem
Vejde se první část SE do vyšetřované množiny na dané pozici a současně druhá část SE ji zcela mine? Pokud ano, tak ulož tuto pozici
HMT se často používá k nalezení (odstranění) konkrétní konfigurace pixelů
- Vytváření kostry (skeletonizing)
- Ztenčování (thinning)
- Scvrkávání
Příklady:

Bílý top-hat (WTH)

Definován jako rozdíl mezi původním obrázkem a jeho otevřením
Extrahuje světlé skvrny (lokální maxima) nezávisle na jejich intenzitě, bere v úvahu pouze tvar
Lze použít pro korekci nerovnoměrného osvětlení (tmavé pozadí)

Černý top-hat (BTH)

Definován jako rozdíl mezi uzavřením a původním obrázkem
Komplementární operátor k bílému top-hatu
Extrahuje tmavé skvrny (lokální minima) nezávisle na jejich intenzitě, bere v úvahu pouze tvar
Lze použít pro korekci nerovnoměrného osvětlení (světlé pozadí)

Příklad:

Watershed

Simulace zvyšování hladiny vody krok za krokem.
Šedotónový obraz je považován za topografický povrch s údolími a vodních předělů
spočítáme rozdělení pomocí stavby přehrad mezi údolími během procesu zaplavení.

Vyhlazení obrazu (obvykle Gaussův filtr), velikost jádra závisí na velikosti objektu a také na šumu.
Určení maximální intenzity (MaxI) a minimální intenzity (MinI) celého snímku.
Určení tzv. markerů, tedy zárodků budoucích objektů. Lze provést např. pomocí minimálního filtru.
Binární obrázek (BinImg) = prázdný obrázek (nuly)
Pro CurI = MinI až MaxI provedeme růst oblasti ze markerů (nebo již existujících oblastí BinImg), aby byly zahrnuty všechny pixely s intenzitou nižší nebo rovnou CurI. Regiony nesmí splývat!
BinImg nyní definuje území objektů. Počet objektů se rovná počtu markerů.

Obvykle se používá na gradient (Sobelův filtr) za účelem nalezení hranic objektů
Může fungovat bez markerů, v tomto případě jsou markery všechny lokální minima na obrázku (v sousedství 3x3)
Zaplavení lze provést v opačném směru pro invertované obrázky (anti-watershed)
Markery lze určit ručně nebo automaticky pomocí lepšího přístupu než minimální filtr, např. pomocí transformace vzdálenosti
- Obraz je prahován (dvouúrovňové prahování) a jsou určeny hranice
- Nalezne se nejkratší vzdálenost každého pixelu k nejbližšímu hraničnímu bodu.
- Ty pixely, které mají velkou vzdálenost k hranici (větší než předem definovaný práh) jsou brány jako markery.