Rozsah látky

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

Obrazová funkcia (spojitá), 2D:

<math>f:U \subset \mathbb{R}^2 \rightarrow \mathbb{R}^n</math>

<math>f:[x,y] \rightarrow [a_1,a_2, ..., a_n]</math>

(poloha bodu v rovine -> atributy obrazu (farba, priehladnost, ... - <math>\mathbb{R}^4</math> pre [R,G,B,<math>\alpha</math>]))

Digiálny rastrový obraz:

<math>I: <0..m-1> \times <0..n-1> \ \rightarrow \mathbb{R}^n</math>

Digitalizácia pomocou filtru d:

<math>I_f(i,j)= \int\!\!\!\!\int_{R^2} f(x,y)d(x-i,y-j) \mathrm{d}x \mathrm{d}y</math>

d vyjadruje snímaciu charakteristiku digitalizačného zariadenia (fotočidlo, CCD prvok, ...)

2D Fourierova transformace a konvoluce

Spojité verze

  • Dopředná Fourierova transformace: <math>F(u,v) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x,y) e^{-2 \pi i ( ux + vy )} dxdy</math>

  • Zpětná Fourierova transformace: <math>f(x,y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} F(u,v) e^{2 \pi i ( ux + vy )} dudv</math>

  • Konvoluce: <math>(f * g)(x,y) = (g * f)(x,y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(a,b) g( x - a, y - b ) dadb</math>Vlastnosti:

    • komutativní <math>f*g = g*f</math>

    • asociativní <math>f*(g*h) = (f*g)*h</math>

    • distributivní: <math>f*(g+h) = f*g+f*h</math>

    • asociativita při násobení skalárem: <math>a(f*g) = (af)*g=f*(ag)</math>

    • Existence jednotky: <math>f*\delta = \delta * f = f</math> (<math>\delta</math> je diracova delta fce)

Vlastnosti

  • Convolution theorem: <math> \mathcal{F}\{f * g\} = \mathcal{F}\{f\}\cdot \mathcal{F}\{g\}</math>

  • Linearita: <math> \mathcal{F}\{ a \cdot f + b \cdot g \} = a \cdot \mathcal{F}\{f\} + b \cdot \mathcal{F}\{g\}</math>

  • Shift theorem: <math> \mathcal{F}\{ f( x-x_0, y-y_0 ) \}( u,v ) = e^{-2 \pi i ( ux_0 + vy_0 )} F(u,v)</math>

  • Rotace: <math> \mathcal{F}\{ Rot(f) \} = Rot(\mathcal{F}\{ f \}) </math>

Diskrétní verze

  • Dopředná Fourierova transformace: <math>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} )}</math>

  • Zpětná Fourierova transformace: <math>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} )}</math>

  • Konvoluce: <math>(f * g)[m,n] = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} f(i,j) g( m - i, n - j )</math>.

    • 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

Matematický model vzorkování, Shannon theorem

<math>f(x,y) \cdot s(x,y) = d(x,y)</math>, kde <math>f</math> je původní funkce, <math>s</math> je vzorkovací fce (pole delta funkcí) a <math>d</math> je navzorkovaný obraz.

  • <math>F(u,v) * S(u,v) = D(u,v)</math>

  • <math>s(x,y) = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} \delta( x - i\Delta x, y - j\Delta y )</math>

  • <math>S(u,v) = \sum_{i=-\infty}^{\infty} \sum_{j=-\infty}^{\infty} \delta( u - i\frac{1}{\Delta x}, v - j\frac{1}{\Delta y} )</math>

Fourierův obraz navzorkované funkce (<math>D(u,v)</math>) je tvořen do mřížky poskládanými spektry původní funkce s roztečemi <math>\frac{1}{\Delta x}</math> a <math>\frac{1}{\Delta y}</math>. 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í:

<math>\Delta x \leq \frac{1}{2W_u}</math> a <math>\Delta y \leq \frac{1}{2W_v}</math>, kde <math>W_u</math> a <math>W_v</math> 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í

  • aliasing (stráta vysoko frekvenčnej informacie - hrany, detaily)

  • Moiré efekt - falešné nízké frekvence

Kvantování

  • 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

Založeno na úpravě histogramu

  • ekvalizace histogramu - Máme histogram, kde každá intenzita má nějakou pst <math>p(i)</math>, z toho lze udělat <math>cdf(x) = \int\limits{0}{x} p(t) dt</math>. Chceme cdf, která je skoro přímka.

  • převodní funkce pro jasové úrovně (LUT - lookup table)

  • nelineární transformace intenzit <math>ampl = log(ampl+1)</math>, člověk může lépe vidět

  • gamma korekce - kompenzace toho, že CRT zobrazuje <math>output = c input^{gamma}</math>, korekce je inverzní

Odstranění šumu

Š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.

<math>\mathrm{SNR}=10log\frac{D(f)}{D(n)}\mathrm{[dB]}</math>

f - signál, n - šum

Modely šumu:

  • Aditivní náhodný šum <math>g = f + n</math>

  • 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

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.

Hledání hran

Inverzní a Wienerův filtr

Předpokládáme, že známe funkci, která poškodila obraz.

Ideální případ - bez šumu:

<math>g(x,y) = (f * h)(x,y)</math>, 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:

<math>G = F \cdot H</math>

<math>F = G \cdot \frac{1}{H}</math>

V praxi je však běžně přítomen i šum, který dekonvoluci stěžuje:

<math>g(x,y) = (f * h)(x,y) + n(x,y)</math>, kde n je aditivní šum, nezávislý na obrazové fci.

<math>G = F \cdot H + N</math>

<math>F = G \cdot \frac{1}{H} - \frac{N}{H}</math>

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

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)

<math>H_W( u, v ) = \frac{H^*(u,v)}{|H(u,v)|^2 + \frac{S_{nn}( u,v )}{S_{ff}(u,v)}} </math>

Wikipedia Wienerův filtr

Určení vzájemné polohy snímků, problém korespondence bodu a objektu, odstranění geometrických zkreslení snímků

Problém registrace obrázků (image registration) -- postup:

  1. 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

  2. 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

  3. 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

  4. Odhad transformace

  5. Převzorkování podle transformace - dopředná nebo zpětná transformace + interpolace

  6. Vyhodnocení přesnosti: např. vzdálenost features,

Detekce hranic objektů, detekce oblastí

Slajdy segmentace obrazu

Segmentace: rozdělení obrazu do segmentů, <math>S: I \to R</math>, I obrázek, <math>R={0,1,2..n}</math>

Šum je všude, nezapomínat.

Hranicové metody

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

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í.

http://pernerscontacts.upce.cz/15_2009/Silar.pdf 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.

  • http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/MARBLE/medium/segment/split.htm 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

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

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

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: <math>\frac{4\pi P}{O^2}</math>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|: <math>c_i = \frac{|z_i|}{|z_1|}</math> (z0 už bylo vyhozeno)

Momentové invarianty

Moment je průmět fce do prostoru polynomů, mám prostor polynomiálních fcí a koeficienty jsou momenty.

Obrazová fce <math>f(x,y)</math>, omezená na <math>\Omega \subset R x R</math>.

Obecný moment s polynomem <math>P_{pq}</math>: <math>M_{pq} = \int\int P_{pq}(x,y)f(x,y) dx dy</math>

  • Geometrický moment: <math>m_{pq}(x,y) = \int\int x^p y^q f(x,y) dx dy</math>

  • Centrální moment: <math>\mu_{pq}(x,y) = \int\int (x-x_t)^p (y-y_t)^q f(x,y) dx dy</math> - 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...

Wikipedie

Wavelety a jejich použití

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)

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

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í <math>g_i(x)</math>, kde <math>x</math> je příznak vektorů. Klasifikace je nalezení <math>\displaystyle\max_{i} g_i(x)</math>. 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)

k-NN klasifikátor

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. <math>g(x) = 1/ dist(x,ω)</math>

K měření vzdálenosti lze použít různé metriky, euklidovskou, hammingovu.

Lineární klasifikátor

LINEÁRNÍ KLASIFIKÁTORY

Výhody: jednoduchý, výpočetně nenáročný, nezávislý na datech. Klasifikuje do dvou tříd.

Lineární klasifikátor je nadrovina <math>g(x) = w^T \cdot x + w_0 = 0</math>, <math>w_0</math> je práh, <math>w</math> je váhový vektor(resp. norm. vektor nadroviny). Příklad - přímka ve 2D <math>g(x) = ax+by+c = 0</math>. Hranice rozděluje prostor na 2 části, na 1 straně <math>g(x)>0</math> a na druhé <math>g(x)<0</math>.

wen:Perceptron alg. Předpokládá lineární separabilitu tříd. Máme ztrátovou funkci <math>J(w) = \sum \delta_i w^T \cdot x</math>, 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, <math>w(t+1) = w(t) + \alpha \frac{\partial J(w)}{\partial w}</math>, derivace J podle w je <math>\sum \delta_i x</math>, takže iterujeme přes <math>w(t+1) = w(t) + \alpha \sum \delta_i x</math>

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

Předpoklad: přízkany jsou náhodné veličiny.

<math>P(\omega_i | x) = \frac{P(x | \omega_i) P(\omega_i)}{P(x)}</math>. <math>P(x) = \sum_i P(x | \omega_i) P(\omega_i)</math>.

<math>P(\omega_i | x)</math> ří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 <math>P(\omega_i)</math>?

  • Case studies (OCR, atd).

  • Z četnosti v training set

  • V nejhorším případě řekneme, že jsou stejně veliké.

Jak odhadneme <math>P(x | \omega_i)</math>? 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í)

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í: <math>J = \sum_{j=1}^{N} \sum_{x \in C_{i}} | x - \bar{x}_{i}|^2</math> - Lze porovnávat pouze při stejném množství shluků, degenerovaný případ, kde každý bod je shluk.

Iterační

Typicky je počet shluků zadán.

N-mean

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é

wen:Hierarchical clustering

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í

Wikipedia

Úvod do počítačové robotiky, plánování cesty mobilního robota

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

Materiály

{{Stub}} Category: Státnice Informatika Mgr.