Analýza a zpracování obrazu, počítačové vidění a robotika
Obsah
- 1 Rozsah látky
- 2 Matematický model obrazu
- 3 2D Fourierova transformace a konvoluce
- 4 Vzorkování a kvantování obrazu
- 5 Změna kontrastu a jasu
- 6 Odstranění šumu
- 7 Detekce hran
- 8 Inverzní a Wienerův filtr
- 9 Určení vzájemné polohy snímků, problém korespondence bodu a objektu, odstranění geometrických zkreslení snímků
- 10 Detekce hranic objektů, detekce oblastí
- 11 Příznaky pro popis a rozpoznávání 2D objektů, momentové invarianty
- 12 Wavelety a jejich použití
- 13 Statistická teorie rozpoznávání (Pattern Recognition)
- 14 klasifikace s učením (Bayessův, lineární a k-NN klasifikátor)
- 15 klasifikace bez učení (hierarchické a iterační shlukování)
- 16 Počítačové vidění
- 17 Úvod do počítačové robotiky, plánování cesty mobilního robota
- 18 Předměty
- 19 Materiály
Rozsah látky[editovat | editovat zdroj]
Seznam oficiálních státnicových otázek:
- Matematický model obrazu, 2D Fourierova transformace a konvoluce, vzorkování a kvantování obrazu, změna kontrastu a jasu, odstranění šumu, detekce hran, inverzní a Wienerův filtr, určení vzájemné polohy snímků, problém korespondence bodu a objektu, odstranění geometrických zkreslení snímků, detekce hranic objektů, detekce oblastí, příznaky pro popis a rozpoznávání 2D objektů, momentové invarianty, wavelety a jejich použití, statistická teorie rozpoznávání, klasifikace s učením (Bayessův, lineární, SVM a k-NN klasifikátor), klasifikace bez učení (hierarchické a iterační shlukování), počítačové vidění, úvod do počítačové robotiky, plánování cesty mobilního robota.
Matematický model obrazu[editovat | editovat zdroj]
Obrazová funkcia (spojitá), 2D:
$ f:U \subset \mathbb{R}^2 \rightarrow \mathbb{R}^n $
$ f:[x,y] \rightarrow [a_1,a_2, ..., a_n] $
(poloha bodu v rovine -> atributy obrazu (farba, priehladnost, ... - $ \mathbb{R}^4 $ pre [R,G,B,$ \alpha $]))
Digiálny rastrový obraz:
$ I: <0..m-1> \times <0..n-1> \ \rightarrow \mathbb{R}^n $
Digitalizácia pomocou filtru d:
$ I_f(i,j)= \int\!\!\!\!\int_{R^2} f(x,y)d(x-i,y-j) \mathrm{d}x \mathrm{d}y $
d vyjadruje snímaciu charakteristiku digitalizačného zariadenia (fotočidlo, CCD prvok, ...)
2D Fourierova transformace a konvoluce[editovat | editovat zdroj]
Spojité verze[editovat | editovat zdroj]
- Dopředná Fourierova transformace: $ F(u,v) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x,y) e^{-2 \pi i ( ux + vy )} dxdy $
- Zpětná Fourierova transformace: $ f(x,y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} F(u,v) e^{2 \pi i ( ux + vy )} dudv $
- Konvoluce: $ (f * g)(x,y) = (g * f)(x,y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(a,b) g( x - a, y - b ) dadb $Vlastnosti:
- komutativní $ f*g = g*f $
- asociativní $ f*(g*h) = (f*g)*h $
- distributivní: $ f*(g+h) = f*g+f*h $
- asociativita při násobení skalárem: $ a(f*g) = (af)*g=f*(ag) $
- Existence jednotky: $ f*\delta = \delta * f = f $ ($ \delta $ je diracova delta fce)
Vlastnosti[editovat | editovat zdroj]
- Convolution theorem: $ \mathcal{F}\{f * g\} = \mathcal{F}\{f\}\cdot \mathcal{F}\{g\} $
- Linearita: $ \mathcal{F}\{ a \cdot f + b \cdot g \} = a \cdot \mathcal{F}\{f\} + b \cdot \mathcal{F}\{g\} $
- Shift theorem: $ \mathcal{F}\{ f( x-x_0, y-y_0 ) \}( u,v ) = e^{-2 \pi i ( ux_0 + vy_0 )} F(u,v) $
- Rotace: $ \mathcal{F}\{ Rot(f) \} = Rot(\mathcal{F}\{ f \}) $
Diskrétní verze[editovat | editovat zdroj]
- Dopředná Fourierova transformace: $ F_{n,m} = \frac{1}{\sqrt{MN}} \sum_{k=0}^{N-1} \sum_{l=0}^{M-1} f_{k,l} e^{-2 \pi i ( \frac{km}{M} + \frac{ln}{N} )} $
- Zpětná Fourierova transformace: $ f_{k,l} = \frac{1}{\sqrt{MN}} \sum_{m=0}^{N-1} \sum_{n=0}^{M-1} F_{n,m} e^{2 \pi i ( \frac{km}{M} + \frac{ln}{N} )} $
- Konvoluce: $ (f * g)[m,n] = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} f(i,j) g( m - i, n - j ) $.
- Okrajový jev: valid (výsledek je menší), same(výsledek stejný), full(dokud konvoluční jádro zasahuje). Ošetření okrajového jevu: zero padding, zrcadlové prodloužení, periodické prodloužení
Vzorkování a kvantování obrazu[editovat | editovat zdroj]
Matematický model vzorkování, Shannon theorem[editovat | editovat zdroj]
$ f(x,y) \cdot s(x,y) = d(x,y) $, kde $ f $ je původní funkce, $ s $ je vzorkovací fce (pole delta funkcí) a $ d $ je navzorkovaný obraz.
- $ F(u,v) * S(u,v) = D(u,v) $
- $ s(x,y) = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} \delta( x - i\Delta x, y - j\Delta y ) $
- $ S(u,v) = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} \delta( u - i\frac{1}{\Delta x}, v - j\frac{1}{\Delta y} ) $
Fourierův obraz navzorkované funkce ($ D(u,v) $) je tvořen do mřížky poskládanými spektry původní funkce s roztečemi $ \frac{1}{\Delta x} $ a $ \frac{1}{\Delta y} $. Dokážeme zrekonstruovat původní funkci pouze pokud se nám jednotlivá spektra neslijí a to platí jen pokud je původní funkce frekvenčně omezená a vzorkujeme s dostatečnou frekvencí:
- $ \Delta x \leq \frac{1}{2W_u} $ a $ \Delta y \leq \frac{1}{2W_v} $, kde $ W_u $ a $ W_v $ jsou maximální frekvence v základních směrech.
Potřebujeme dvakrát vyšší frekvenci než je maximální přítomná frekvence v původní fci.
Negativní projevy podvzorkování[editovat | editovat zdroj]
- aliasing (stráta vysoko frekvenčnej informacie - hrany, detaily)
- Moiré efekt - falešné nízké frekvence
Kvantování[editovat | editovat zdroj]
- Diskretizace oboru hodnot signálu - vždy ztrátové.
- Často se kvantizér navrhuje tak aby využíval vlastnosti lidského oka - např. nerozlišitelným jasovým ůrovním se přiřazuje stejná hodnota
Změna kontrastu a jasu[editovat | editovat zdroj]
Založeno na úpravě histogramu
- ekvalizace histogramu - Máme histogram, kde každá intenzita má nějakou pst $ p(i) $, z toho lze udělat $ cdf(x) = \int\limits{0}{x} p(t) dt $. Chceme cdf, která je skoro přímka.
- převodní funkce pro jasové úrovně (LUT - lookup table)
- nelineární transformace intenzit $ ampl = log(ampl+1) $, člověk může lépe vidět
- gamma korekce - kompenzace toho, že CRT zobrazuje $ output = c input^{gamma} $, korekce je inverzní
Odstranění šumu[editovat | editovat zdroj]
Šum sa vyčísluje ako logaritmus pomeru signalu k šumu v decibeloch [dB] (Signal-to-Noise Ratio). Čím viac decibelov tým lepší odstup signálu od šumu -> kvalitnejší obraz.
$ \mathrm{SNR}=10log\frac{D(f)}{D(n)}\mathrm{[dB]} $
f - signál, n - šum
Modely šumu:
- Aditivní náhodný šum $ g = f + n $
- Gaussovský bílý šum
- Impulsní šum (sůl a pepř)
Noise reduction: (nedám za to ruku do ohňa)
- bílý šum -> Priemerovanie v čase (prosté/vážené)
- impulsní šum -> Mediánový filter (pre pixel vyberáme intenzitu medianu v okolí), iné nelineárne filtre,
- low-pass filter (napr. Gauss) - zbaví vysokofrekvenčného šumu (rovnako ako aj každej inej vysokofrekvenčnej informácie - hrany). Ve freq oblasti vynásobím filtrem odstraňujím vysoké freq = v obrazové oblasti konvoluce.
- Rotujúce okno - pokus o odstranenie vysokofrekvenčného šumu a zachovania hran zaroveň. Može vytvárať artefakty. Hodnotu pixelu nahradím EX z okénka, kde je nejmenší var X (=patrně tam nebudou hrany).
- Priemerovanie podél hran
Nelineárlní filtry:
- Medián - pixel nahradíme mediánem okolí, dobré na pepř a sůl. Lze aplikovat iterativně, několikrát. Není triviální rozšířit do barvy.
Odstranění šumu a zachování hran jde proti sobě
Detekce hran[editovat | editovat zdroj]
Lidské vnímání je založeno na detekci hran (edge detection), tedy změnou jasu hrany vidíme objekty. Toho se taktéž ve velké míře používá v segmentačních technikách pro zpracování obrazu. Mnoho metod segmentace právě vychází z detekce hran pro odlišení objektů v obraze. Hranu v obraze je charakterizovat gradientem, tedy velikostí a směrem. Existuje také mnoho filtrů pracující s detekcí hran v obraze a hrany hrají také klíčovou roli pro příznaky a posléze klasifikace podle vektorů příznaků. Mezi geometrické příznaky patří např. pravoúhlost, podlouhlost, kruhovost či vzdálenost pixelů od okraje, tedy hrany. Vektor příznaků, označme jej např. vc =(x1, x2,...,xn), kde xi je daný příznak. Tyto příznaky pak slouží jako vstupy (např. pro perceptron), a pomocí nich se klasifikuje výstup (třída).
Unsharp masking: původní obrázek - alfa * rozostřený orbázek - zvýrazní hranu, šlo již analogově.
Hrany jsou veliké změny v derivaci a proto je tím detekujeme.
Metody:
- podle 1. derivace: Roberts, Prewitt, Sobel, Canny
- podle 2. derivace: Laplacián (Marr-Hildreth) - hledáme zero crossings, protože může být nula i na homogeních plochách.
Inverzní a Wienerův filtr[editovat | editovat zdroj]
Předpokládáme, že známe funkci, která poškodila obraz.
Ideální případ - bez šumu:
- $ g(x,y) = (f * h)(x,y) $, kde h je funkce poškození, prostorově neměnná (stejná pro celý obraz).
Obvyklé fce poškození h:
- motion blur - 1D čtverec
- out of focus - cylinder
- atmosférická turbulence - gaussian
Z Convolution theoremu dostaneme:
- $ G = F \cdot H $
- $ F = G \cdot \frac{1}{H} $
V praxi je však běžně přítomen i šum, který dekonvoluci stěžuje:
- $ g(x,y) = (f * h)(x,y) + n(x,y) $, kde n je aditivní šum, nezávislý na obrazové fci.
- $ G = F \cdot H + N $
- $ F = G \cdot \frac{1}{H} - \frac{N}{H} $
Z posledního výrazu je vidět, že šum bude nejvíce ovlivňovat výsledek na frekvencích, kde bude H téměř nulové.
Wikipedia: předzpracování obrazu
Wienerův filtr[editovat | editovat zdroj]
Wienerův filtr se snaží vypořádat se šumem a najít nejlepší opravu obrazu z hlediska nejmenších čtverců (matematicky správné, ale neideální pro člověka)
$ H_W( u, v ) = \frac{H^*(u,v)}{|H(u,v)|^2 + \frac{S_{nn}( u,v )}{S_{ff}(u,v)}} $
Určení vzájemné polohy snímků, problém korespondence bodu a objektu, odstranění geometrických zkreslení snímků[editovat | editovat zdroj]
Problém registrace obrázků (image registration) -- postup:
- Výběr kontrolních bodů
- rohy, čáry, významné body, uzavřené plochy
- Hledané vlastnosti:
- Významné a detekovatelné
- Rozložené na obraze
- Vyskytují se ve všech obrazech
- Odolné k degradaci
- Nalezení korespondence kontrolních bodů
- area-based - porovnávají se celé obrázky (obrazová funkce)
- Obrázková korelace, rozdíly obrázků, fázová korelace (ve frekvenční oblasti, shift hteorem)
- Zrychlení: Pyramidální reprezsentace - postupuje se od nejhrubšího k nejjemnějšímu
- feature-based - porovnávají se jenom malé kousky (invarianty popsaná okolí kontrolních bodů) nebo vztahy mezi nimi (clustery s parametry)
- Kombinatorické porovnávání - porovnávání grafů, parameter clustering(různé transformace možných bodů mají parametry a hledám shluk parametrů pro všechny transformace)
- Hledání ve feature space: dva body si odpovídají, pokud mají minimální vzdálenost ve feature space. Chceme dobré featury, robustní k šumu, diskriminantní, invariantní
- hybridní - kombinace
- area-based - porovnávají se celé obrázky (obrazová funkce)
- Volba transformační funkce - Funkce může být jednoduchá nebo složití, afinní transformace, různé splajny, trojúhelníková síť, polynomy, wen:Thin plate spline
- Odhad transformace
- Převzorkování podle transformace - dopředná nebo zpětná transformace + interpolace
- Vyhodnocení přesnosti: např. vzdálenost features,
Detekce hranic objektů, detekce oblastí[editovat | editovat zdroj]
Segmentace: rozdělení obrazu do segmentů, $ S: I \to R $, I obrázek, $ R={0,1,2..n} $
Šum je všude, nezapomínat.
Hranicové metody[editovat | editovat zdroj]
wen:Outline of object recognition Segmentace a detekce geometrických primitiv
Wikipedia Detekce hran. Hrana separuje dva objekty,
- Roberts
- Sobel
- Wateshed - °Hodnoty pixelů se interpretují jako výšky, do každého lokálního minima umístím zdroj vody a pstupně přidávám vodu. Pokud se setkají dva různé zdroje vody, je to hranice. Tato technika může způsobit přesegmentaci. Mayerův algoritmus
- Canny - Gauss (elim šumu), detekce gradientů, edge thinning, hystereze
- Sledování hranice - Použito, pokud je např. známa barva objektu. Jde se po řádcích a pokud se narazí na hledanou barvy, prochází se okolní pixely v daném pořadí (od zhora proti směru hod ručiček), dokud se nevrátí zpět na původní místo
- Hough transformace - Každý pixel má nekonečně přímek, které jím procházejí - které přímky mají nejvíce pixelů. používá se akumulátor v polárním rpostoru.
- Active countours - snake. Optimalizuje uzavřenou křivku, aby odpovídala objektu. Snaží se minimalizovat energii
Region based metody[editovat | editovat zdroj]
Region je množina souvislých podobných pixelů. Místo hran hledáme homogení oblasti. Každá oblast musí být spojitá a nesmí se překrývat. Používají se v případě hodně zašumněného obrazu, kde hranové metody selhávají.
[Kapitola 6], wen:Image_segmentation
- Prahování - globální/lokální metoda, velmi jednoduchá. Pokud pixel> prah, patří do regionu, jinak nepatří. Případně více mžonách regionů. Automatická, založená na histogramu. Adaptivní prahování-obrázek rozdělen na oblasti a pro každou zvlášť.
- K-means clistering algorithm - Zvol počet K. Zvol počáteční střed K clusterů. Pro každý pixel najdi nejbližší střed clusteru a přiřaď ho k němu. Přepočítej středy. Opakuj, dokud se středy mění.
- Region growing - Teoreticky nejjednodušší. Podobný záplavovému vyplňování, máme semínka a pokud je pixel v okolí "dost podobný", přidá se. Na začátku každý pixel region a pokud hranice mezi regiony slabá, slijí se.
- [Splitting & Merging] - Je predikát Q, který je true, pokud je jeho parametr (plocha obrázku) pravděpodobně region segmentace. Obrázek se rekurzivně dělí na kvadrany, dokud je Q false. Poté se vždy vybere jeden region a najdou se všichni jeho sousedi, kteří jsou podobní a slijí se. Pozor, nemusí už být čtvercové.
Příznaky pro popis a rozpoznávání 2D objektů, momentové invarianty[editovat | editovat zdroj]
Příznak - bod v prostoru příznaků, pro porovnání 2 příznaků potřebujeme metriku (typicky euklidovská).
2D objekt - Oblast pixelů, binární (buď pixel je součástí objektu nebo není), konečný, nezakrtý. Okraj - pixel, objektu, který má za 4/8 souseda pozadí, jednoduchá nekřížící se křivka/více křivek.
Rozpoznávání objektů: přiřazení do 1
Detekce[editovat | editovat zdroj]
Jakým způsobem rozeznám objekt, jehož příznaky budu počítat?
- Prahování: nejjednodušší způsob, používá se, objekt se např. speciálně zkontrastuje.
- edge-linking - najdeme v obrázku hranice a snažíme se je spojit (občas může kus hranice chybět)
- region-growing
Příznaky[editovat | editovat zdroj]
Hledané vlastnosti příznaků:
- invariance na deformace, např. otáčení
- diskriminalita - schopnost odlišitr různé objekty
- robustnost vůči šumu
- nezávislost na ostatních příznacích, efektivní výpočet
Hlavní kategorie:
- vizuální příznaky - moc se nepoužívají, nelze z nich rekonstruovat objekt
- kompaktnost: $ \frac{4\pi P}{O^2} $P plocha, O obvod
- konvexita: plocha objektu/plocha konvexní obálky
- Kompletní příznaky (kompletní = lze z nich rekonstruovat objekt)
- chain kód
- polygonální aproximace
- tvarový vektor - vezmu těžiště objektu, nakreslím kolem něj kružnici a výsledný vektor jsou čísla, ve kterých se objekt protíná v úhlových intervalech. Není vhodný na nekonvexní objekty. První položka je maximum, invariantní na otočení a posunutí.
- tvarová matice - podobné tvarovému vektoru, více soustředných kružnic, zasahuje objekt do kruhu
- Příznaky transormačních koeficientů
- Fourierovy deskriptory - vezmu hranici objektu a interpretuji ji jako komplexní čísla, na ně FT, z výsledných koeficientů vyhodím Z_0, čímž se dostanu invariantnost proti posunutí. Invariantnost proti rotaci lze získat absolutní hodnotou a škálování dělením |z1|: $ c_i = \frac{|z_i|}{|z_1|} $ (z0 už bylo vyhozeno)
Momentové invarianty[editovat | editovat zdroj]
Moment je průmět fce do prostoru polynomů, mám prostor polynomiálních fcí a koeficienty jsou momenty.
Obrazová fce $ f(x,y) $, omezená na $ \Omega \subset R x R $.
Obecný moment s polynomem $ P_{pq} $: $ M_{pq} = \int\int P_{pq}(x,y)f(x,y) dx dy $
- Geometrický moment: $ m_{pq}(x,y) = \int\int x^p y^q f(x,y) dx dy $
- Centrální moment: $ \mu_{pq}(x,y) = \int\int (x-x_t)^p (y-y_t)^q f(x,y) dx dy $ - odečítá těžiště a je invariantní k poloze
Funkce momentů jsou invariantní k některým degradacím: rotace, pohyb, škálování, afiní transformace, konvoluce...
Wavelety a jejich použití[editovat | editovat zdroj]
http://users.rowan.edu/~polikar/WAVELETS/WTtutorial.html
http://pagesperso-orange.fr/polyvalens/clemens/wavelets/wavelets.html
http://cnx.org/content/m11140/latest/
Statistická teorie rozpoznávání (Pattern Recognition)[editovat | editovat zdroj]
wen:Statistical classification, Hlaváč - VZTAH MEZI STATISTICKÝM A STRUKTURNÍM ROZPOZNÁVÁNÍM]
Co to je: Přiřazení objektu do 1 předdefikované třídy.
Rozpoznávání:
- Syntaktické (např. vzroce, je to +- gramatika, vzor je popsán svou strukturou a zjišťuje se, jestli slovo patří do jazyka)
- Statistické - vzor je popsán 2-D vektorem příznaků
2 Typy:
Klasifikace s učením[editovat | editovat zdroj]
Známe počet tříd. Tvorba pravidla:
- jaké příznaky použijeme
- vybereme třénovací množinu
- spočítáme na ní příznaky
- na základě toho vytvoříme klasifikační pravidlo - tohle je ta netriviální a zajímavá část
Vlastnosti Training Set:
- Obsahovat typické prvky každé třídy variabilitu mezi třídami
- Dost veliká a spolehlivá (klasifikovat odborníci, ale občas stejně chyby + sporné případy). Klasfifikátory často předpokládají, že v TS jsou chyby.
Sestavení klasifikátoru: definovat pokrytí příznakového prostoru. Formálně je každá třída charaketrizovaná fcí $ g_i(x) $, kde $ x $ je příznak vektorů. Klasifikace je nalezení $ \displaystyle\max_{i} g_i(x) $. Tedy přiřaď pokud je hodnota mpro daný vektor maximální.
Pozor na přetrénovaní klasifikátoru! Klasifikační pravidlo pak může sice naprosto splňovat TS, ale na zbytku selhat.
Jak hodnotit klasifikátory? Můžeme použít klasifikátor na TS, ale protože ten jsme použili na tvorku pravidla, tak to je dost optimistické. Případně můžeme míst menší oklasifikovanou množinu, která není součstí TS a porovnat její klasifikaci s tím, co řekli doborníci.
Jak zlepšit výkon:
- jiné příznaky
- více příznaků (pozor, na wen:Curse of dimensionality)
- větší/lepší TS
- jiný klasifikátor
- kombinace různých klasifikátorů
klasifikace s učením (Bayessův, lineární a k-NN klasifikátor)[editovat | editovat zdroj]
k-NN klasifikátor[editovat | editovat zdroj]
wen:K-nearest neighbors algorithm. Objekt postupně prochází body z TS podle vzdálenosti a patří do první třídy, která má k nejbližších bodů. Pro k=1 je to Nearest Neighbour klasifikátor (Voroniho diagram), pouze jeden bod = velmi citlié na šum. $ g(x) = 1/ dist(x,ω) $
K měření vzdálenosti lze použít různé metriky, euklidovskou, hammingovu.
Lineární klasifikátor[editovat | editovat zdroj]
Výhody: jednoduchý, výpočetně nenáročný, nezávislý na datech. Klasifikuje do dvou tříd.
Lineární klasifikátor je nadrovina $ g(x) = w^T \cdot x + w_0 = 0 $, $ w_0 $ je práh, $ w $ je váhový vektor(resp. norm. vektor nadroviny). Příklad - přímka ve 2D $ g(x) = ax+by+c = 0 $. Hranice rozděluje prostor na 2 části, na 1 straně $ g(x)>0 $ a na druhé $ g(x)<0 $.
wen:Perceptron alg. Předpokládá lineární separabilitu tříd. Máme ztrátovou funkci $ J(w) = \sum \delta_i w^T \cdot x $, která přes všechny špatně zařazené uzly spočítá chybu. delat je tam, aby to bylo vždy v plusu, šla by použít absolutní hodnota. Nyní iteračně chceme získat hodnoty w, $ w(t+1) = w(t) + \alpha \frac{\partial J(w)}{\partial w} $, derivace J podle w je $ \sum \delta_i x $, takže iterujeme přes $ w(t+1) = w(t) + \alpha \sum \delta_i x $
SVM (Support Vector Machines) - lineární separabilita není určena jednoznačně. Snažím se, aby mezera byla co největší. Různé optimalizace na šířku a špatné umístění.
Bayessův klasifikátor[editovat | editovat zdroj]
Předpoklad: přízkany jsou náhodné veličiny.
$ P(\omega_i | x) = \frac{P(x | \omega_i) P(\omega_i)}{P(x)} $. $ P(x) = \sum_i P(x | \omega_i) P(\omega_i) $.
$ P(\omega_i | x) $ říká, že když máme x, s jakou pstí je v třídě omega_i. X patri do omega_i, kde je tato pst. maximální. Protože se to přímo špatně počítá, používáme bayessův vzorec.
Jak odhadneme $ P(\omega_i) $?
- Case studies (OCR, atd).
- Z četnosti v training set
- V nejhorším případě řekneme, že jsou stejně veliké.
Jak odhadneme $ P(x | \omega_i) $? Parametrický odhad, pokud víme, jakou pdf to má (obvykle normání rozdělení, např. výška člověka, IQ..). Pokud nic nevím, nějaký neparametrický odhad. Zda jsou vzroky z normální pdf můžeme otestovat např. wcs:Test dobré shody.
Protože máme obvykle více, než 1 příznak, používá se d-dimenzionální gausovka. Místo stand. odchylky matice kovariancí. Pokud mají 2 gausovky stejnou maticki kovariancí, rozděluje je římka.
Aplikace: družicové snímky v různých frekv, velká data.
klasifikace bez učení (hierarchické a iterační shlukování)[editovat | editovat zdroj]
v podstatě shluková analýza. Nevím, jaké třídy, kolik a jestli vůbec existují.
Shluk - libovolná podmnožina
Shlukování - rozdělení do disj. podmnožin.
Definice vzdálenost důležitá a mění tvar shluků.
Porovnávání dvou shlukování: $ J = \sum_{j=1}^{N} \sum_{x \in C_{i}} | x - \bar{x}_{i}|^2 $ - Lze porovnávat pouze při stejném množství shluků, degenerovaný případ, kde každý bod je shluk.
Iterační[editovat | editovat zdroj]
Typicky je počet shluků zadán.
N-mean[editovat | editovat zdroj]
Vytvoř N počátečních středů clusterů. Opakuj: každý bod přiřaď k nejbližšímu středu clusteru. Přepočítej středy clusterů. Pokud se změnily, opakuj. Problémy: závislé na počátečním odhadu, neminimalizuje J.
Úprava - pomocí k-means najdi počáteční odhad a pak zkus přesunovat body, jestli to snižuje J.
Hierarchické[editovat | editovat zdroj]
Obvykle neznáme počet clusterů. Buď shora dolů (divisive) nebo zdola nahoru (agglomeratiec).
Agglomerative: na začátku každý bod vlastní cluster. Nalezni dva nejbližší/nejpodobnější clustery a spoj je. Opakuj, dokud není splněna nějaká podmínka. Meotdy se liší způsobem, jakým počítají podobnost (např. nebližší/nejvzdálenější body clusterů) a ukončovací podmínkoiu. Není vždy zcela jasné, co je cluster..
Počítačové vidění[editovat | editovat zdroj]
Úvod do počítačové robotiky, plánování cesty mobilního robota[editovat | editovat zdroj]
Voroniho diagram - plánování cesty co nejdále od překážek
Hlaváč - Path planning in Robotics Hlaváč Motion planning methods
Předměty[editovat | editovat zdroj]
- Digitální zpracování obrazu
- Speciální funkce a transformace ve zpracování obrazu
- Rozpoznávání vzorů
- Úvod do mobilní robotiky
- Počítačové vidění a inteligentní robotika
Materiály[editovat | editovat zdroj]
- Slajdy: Flusser J., Zitová B. [1], Hlaváč V. [2], Štanclová J. [3]
- Flusser J., Zitová B., Image registration methods: a survey, AVČR [4]
- Gonzales R. C., Woods R. E., Digital Image Processing [5]
- Slajdy k předmětu "Zobrazovací systémy v lékařství" z ČVUT [6]