== Rozsah látky ==
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b52.htm 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.
[http://cmp.felk.cvut.cz/~hlavac/TeachPresCz/11DigZprObr/22EdgeDetectionCz.pdf 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é.
[https://cs.wikipedia.org/wiki/P%C5%99edzpracov%C3%A1n%C3%AD_obrazu 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>
[https://cs.wikipedia.org/wiki/Wiener%C5%AFv_filtr 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:
# 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
# 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í ==
[http://cgg.mff.cuni.cz/~vajicek/presentations/segment0409.pdf 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]]
[http://www.uamt.feec.vutbr.cz/vision/TEACHING/MPOV/05%20-%20Segmentace%20a%20detekce%20geometrickych%20primitiv.pdf Segmentace a detekce geometrických primitiv]
[https://cs.wikipedia.org/wiki/Detekce_hran Wikipedia Detekce hran]. Hrana separuje dva objekty,
* [https://en.wikipedia.org/wiki/Roberts_Cross Roberts]
* [https://en.wikipedia.org/wiki/Sobel_operator 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. [https://en.wikipedia.org/wiki/Watershed_segmentation#Meyer.27s_flooding_algorithm 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
* [https://en.wikipedia.org/wiki/Hough_transform 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.
* [https://en.wikipedia.org/wiki/Active_contour_model 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...
[https://en.wikipedia.org/wiki/Moment_invariant 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í, klasifikace s učením (Bayessův, lineární a k-NN klasifikátor), klasifikace bez učení (hierarchické a iterační shlukování) ==
== Počítačové vidění ==
[https://cs.wikipedia.org/wiki/Po%C4%8D%C3%ADta%C4%8Dov%C3%A9_vid%C4%9Bn%C3%AD 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
== Předměty ==
* [[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 ==
* Slajdy: Flusser J., Zitová B. [http://staff.utia.cas.cz/zitova/prednasky/], Hlaváč V. [http://cmp.felk.cvut.cz/~hlavac/HlavacTeachPresentCz.htm], Štanclová J. [http://www1.cuni.cz/~stancloj]
* Flusser J., Zitová B., Image registration methods: a survey, AVČR [http://library.utia.cas.cz/prace/20030125.pdf]
* Gonzales R. C., Woods R. E., Digital Image Processing [http://www.imageprocessingbook.com/index_dip2e.htm]
* Slajdy k předmětu "Zobrazovací systémy v lékařství" z ČVUT [http://cmp.felk.cvut.cz/cmp/courses/33DZOzima2005/slidy/index.html]
{{Stub}}
[[Category: Státnice Informatika Mgr.]]
