Analýza a zpracování obrazu, počítačové vidění a robotika

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:

$ 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

Spojité verze

• 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

• 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

• 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

Matematický model vzorkování, Shannon theorem

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

• 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 $ 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

Š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

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:

$ g(x,y) = (f * h)(x,y) $, kde h je funkce poškození, prostorově neměnná (stejná pro celý obraz).

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

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)}} $

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)
     • 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
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ů, $ S: I \to R $, I obrázek, $ R={0,1,2..n} $

Šum je všude, nezapomínat.

Hranicové metody

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ů

• Prahování - globá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 - Podobný záplavovému vyplňování, máme semínka a pokud je pixel v okolí "dost podobný", přidá 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 a poté spojuje, dokud Q true.

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: $ \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

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

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/

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

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. [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]