hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
mgr-szz:in-gra:7-gra [2014/10/27 09:07] 127.0.0.1 upraveno mimo DokuWiki |
mgr-szz:in-gra:7-gra [2020/04/12 16:56] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ===== Zadání ===== | ||
| - | Zpracování rastrového obrazu. Histogram, ekvalizace podle histogramu. Prahování, redukce úrovní jasu (barev). Konstrukce adaptivní barevné palety. Lineární a nelineární filtry. Detekce hran. Diskrétní transformace (Fourierova transformace, FFT). Geometrické transformace obrazu, filtrování, převzorkování. | ||
| - | ===== Rastrový obraz ===== | ||
| - | Rastrový obraz je matice n x m pixelů (1 bit -> černobílý, monochromatický). | ||
| - | * indexový mód - hodnota pixelu je ukazatel do tabulky - barevné palety (color palette), např. gray scale | ||
| - | * true color, static gray - pixel obsahuje přímo hodnotu intenzity | ||
| - | * direct color - pixel ukazuje do 3 palet (R, G, B) | ||
| - | |||
| - | ===== Histogram ===== | ||
| - | Histogram kvantifikuje množství a frekvenci barev obsažených v obraze, tj. hodnota histogramu H pro index i odpovídá počtu pixelů v obraze, které mají intenzitu i. (Šedotónní obraz má 1 histogram, barevný 3) | ||
| - | Bílý bod je nejsvětlejší bod v histogramu, černý bod je nejtmavší. | ||
| - | Poznámka: Při fotografování -> technicky dobrý obraz využívá celou škálu intenzit. | ||
| - | |||
| - | ===== Změny histogramu ===== | ||
| - | |||
| - | Zvýšení/snížení jasu, změny kontrastu - pomocí korekční křivky přímo na histogramu. | ||
| - | |||
| - | ==== Ekvalizace histogramu ==== | ||
| - | Je to vyrovnání, změna jasu. Cílem je najít mapovací funkci, která rozloží hodnoty histogramu rovnoměrně. Ideálně histogram obsahuje všechny hodnoty zastoupené stejnou četností d = (n * m)/max, kde max je maximální intenzita pixelů v obraze s rozlišením n x m. Lze provádět i lokálně (např. v astronomii). | ||
| - | |||
| - | === Ekvalizace v barevném prostoru === | ||
| - | Buď se provádí na každém barevném kanálu odděleně, nebo se obraz převede do jiného barevného prostoru, např. YIQ. Použití: fotografie proti světlu nebo v šeru. | ||
| - | |||
| - | ==== Prahování (Thresholding) ==== | ||
| - | Rozdělení jasové složky na 2 části a nahrazení jedinou hodnotou: | ||
| - | {{:mgr-szz:in-gra:threshold.png|}} | ||
| - | kde T je práh (nejčastěji je vhodné zvolit medián nebo 50 procent šedé). Prahováním se obraz (f) převede do binární reprezentace (g). | ||
| - | Ohraničené prahování: | ||
| - | i_n = | ||
| - | i pro 0 <= i < D | ||
| - | L pro D <= i < T | ||
| - | H pro T <= i < U | ||
| - | i pro U <= i <= max | ||
| - | |||
| - | Dělení: | ||
| - | * globální | ||
| - | * lokální | ||
| - | * dynamické/adaptivní | ||
| - | |||
| - | Jak najít vhodný práh automaticky? | ||
| - | * V bimodálním histogramu (2 lokální maxima): | ||
| - | {{:mgr-szz:in-gra:prah1.png|}} | ||
| - | * V unimodálním histogramu: | ||
| - | {{:mgr-szz:in-gra:prah2.png|}} | ||
| - | |||
| - | ==== Gama korekce ==== | ||
| - | CRT monitory -> nelineární časová odezva, ovlivňuje dithering | ||
| - | i' = i^(1/gamma), gamma = 2.5 +- 0.3 (závislá na typu obrazovky) | ||
| - | |||
| - | ===== Konstrukce adaptivní barevné palety ===== | ||
| - | Je vhodné vytvořit paletu, která odpovídá rozložení barevných odstínů v konkrétním obrazu. Paleta je uložena spolu s obrázkem. Např. GIF. | ||
| - | Postup: | ||
| - | Vytvoří se histogram, pak je potřebné nalézt tolik oblastí, kolik má mít paleta barev (typicky 256). Barevný prostor reprezentujeme pomocí RGB krychle (viz obrázek). Úkol: nalézt oblasti, které obklopují skupiny blízkých barev. | ||
| - | {{:mgr-szz:in-gra:rgb.gif|}} | ||
| - | Shrink&Split algoritmus (zmenši a rozděl): | ||
| - | - median cut - řez bodem, který má hodnotu mediánu | ||
| - | - konkrétní barvu stanovíme jako geometrický střed oblasti, aritmetický průmer, vážený průmer, nejčastější barva, ... | ||
| - | Pixely vstupního obrázku se pak musí převést na indexy položek v paletě: | ||
| - | - přímé přiřazení indexu do pixelu (podobné prahování) | ||
| - | - rozptylování | ||
| - | - distribuce chyby | ||
| - | Při použití binárního stromu (rekurzivní dělení RGB krychle) -> nejbližší barva s logaritmickou složitostí. | ||
| - | |||
| - | Přepsání položek barevného histogramu: | ||
| - | Hledání barvy je pouhé "vyzvednutí" indexu z histogramu. Lze požít dělení, které vyjadřuje citlivost lidského vnímání: cílem dělení jsou kvádry s délkami stran R, G, B v poměru 3,3 : 1,7 : 10. | ||
| - | Střední kvadratická odchylka (RMS error) - rozdíl mezi originálem a výsledkem. | ||
| - | |||
| - | ===== Lineární a nelineární filtry ===== | ||
| - | Šum je nová informace, která byla k původní přidána pořizovacím zařízením nebo během transportu (aditivní vs. multiplikativní). Druh šumu se určuje podle frekvenční charakteristiky po Fourierově transformace. Bílý šum má frekvenční spektrum dokonale vyrovnané - matematická abstrakce | ||
| - | Typy: | ||
| - | * Poissonův (photon-shot noise) | ||
| - | * Aditivní - g=f+n, kde f je originální funkce, n šum | ||
| - | * Impulsní - př. sůl a pepř | ||
| - | {{:mgr-szz:in-gra:saltandpeppernoise.jpg|}} | ||
| - | |||
| - | |||
| - | ==== Odstranění šumu (Filtrace) ==== | ||
| - | Za šum jsou považovány velké změny intenzit v sousedících pixelů. Potlačí se buď konvolucí (lineární) nebo lokální statiskitou okolí pixelu (nelineární). | ||
| - | |||
| - | === Nelineární filtry === | ||
| - | |||
| - | Lokální statistika okolí pixelu | ||
| - | {{:mgr-szz:in-gra:lin_filter.png|}} | ||
| - | |||
| - | == Medián filter == | ||
| - | Není konvolucí! Vhodné pro odstranění impulsního šumu, avšak narušuje tenké čáry. Okolí nemusí být čtvercové. | ||
| - | {{:mgr-szz:in-gra:med.png|}} | ||
| - | y(i) = med(x_i-k, ... x_i, ... x_i+k) | ||
| - | |||
| - | Jinak: | ||
| - | Pro všechny pixely [i, j] v obrazu A | ||
| - | 1. Načti body z intervalu [i-k, j-k][i+k, j+k] do pole M délky l = (2k+1)^2 | ||
| - | 2. Seřaď pole M | ||
| - | 3. Výstupní obraz B[i,j] = M[(l-1)/2] | ||
| - | |||
| - | == Max filter == | ||
| - | y(i) = x(n) | ||
| - | |||
| - | == Min filter == | ||
| - | y(i) = x(1) | ||
| - | |||
| - | == Alpha trimmed mean filter == | ||
| - | {{:mgr-szz:in-gra:alphafilter.png|}} | ||
| - | |||
| - | |||
| - | === Lineární filtry === | ||
| - | |||
| - | == Konvoluce == | ||
| - | {{:mgr-szz:in-gra:convolution0.png|}} | ||
| - | {{:mgr-szz:in-gra:convolution.png|}} | ||
| - | g, h - konvoluční jádro (okno, které se posouvá po obraze) | ||
| - | |||
| - | Vlastnosti konvoluce: | ||
| - | (f*g)(i) = (g*f)(i) | ||
| - | ( (f*g)*h )(i) = ( f*(g*h) )(i) | ||
| - | (kernel separability) g je separabilní, pokud platí g = g_row * g_col^T | ||
| - | Konvoluce s 2D jádrem O(n²), konvoluce s 2 1D jádrami O(n). | ||
| - | |||
| - | Konvoluční teorém: | ||
| - | F(f*g) = F(f).F(g) | ||
| - | F(f.g) = F(f)*F(g) | ||
| - | F - Fourierova transformace | ||
| - | f, g - obrázky | ||
| - | |||
| - | == Obyčejné průměrování == | ||
| - | {{:mgr-szz:in-gra:ones.png|}} | ||
| - | |||
| - | Filtrace pomocí obyčejného průměrování ve Fourierově doméně odpovídá násobení funkcí, která odstraní frekvence vyšší než určitá hodnota (odřezání vysokých frekvencí - low-pass filtering, potlačení s váhou). | ||
| - | * Ideal Low-Pass Filter: H(u,v) = | ||
| - | 1 pro √(u²+v²) ≤ D0, | ||
| - | 0 pro √(u²+v²) > D0, | ||
| - | jedná se o válec s poloměrem D0 a výškou 1. | ||
| - | |||
| - | Ostření obrazu ve frekvennční doméně -> high-pass filtering | ||
| - | * Ideal High Pass Filter: H(u,v) = | ||
| - | 0 pro √(u²+v²) < D0, | ||
| - | 1 pro √(u²+v²) >= D0 | ||
| - | |||
| - | == Gaussův filter == | ||
| - | {{:mgr-szz:in-gra:gauss.png|}} | ||
| - | |||
| - | ===== Detekce hran ===== | ||
| - | Hrana (edge) v diskrétním obraze je výrazná změna intenzit sousedních pixelů, vysokofrekvenční informace. Je určena gradientem (vektor ukazující směr největšího přírůstku funkce): | ||
| - | ∇f(x,y) = (∂f(x,y)/∂x, ∂f(x,y)/∂y), velikost: |∇f(x,y)| = √(∂f(x,y)/∂x)² + (∂f(x,y)/∂y)² | ||
| - | |||
| - | |||
| - | ==== Založené na první derivaci ==== | ||
| - | |||
| - | === Robertsův operátor === | ||
| - | Detekuje především hrany se sklonem 45°. Možno rozdělit na 2 složky detekující hrany v na sebe kolmých směrech. | ||
| - | {{:mgr-szz:in-gra:roberts.png|}} | ||
| - | |||
| - | Aproximuje velikost gradientu (první derivace): | ||
| - | {{:mgr-szz:in-gra:roberts2.png|}} | ||
| - | |||
| - | === Sobelův operátor === | ||
| - | Aproximuje velikost gradientu (první derivace): | ||
| - | {{:mgr-szz:in-gra:sobel2.png|}} | ||
| - | {{:mgr-szz:in-gra:sobel.png|}} | ||
| - | |||
| - | === Canny hranový detektor === | ||
| - | Požadavky: | ||
| - | * Minimální počet chyb (musí být detekovány všechny hrany, nesmí být detekována místa, která hranami nejsou) | ||
| - | * Přesnost (poloha hrany musí být určena co nejpřesněji) | ||
| - | * Jednoznačnost (odezva na jednu hranu musí být jedna, nesmí docházet ke zdvojení) | ||
| - | |||
| - | Stručný postup: | ||
| - | - Eliminace šumu (Gaussovým filtrem) | ||
| - | - Určení gradientu (první derivace) | ||
| - | - Nalezení lokálních maxim (thinning) | ||
| - | - Eliminace nevýznamných hran (thresholding) | ||
| - | |||
| - | {{:mgr-szz:in-gra:canny.png|}} | ||
| - | |||
| - | Neprodukuje spojité hrany. | ||
| - | |||
| - | === Rothwell hranový detektor === | ||
| - | Stejný jako Canny, jenom krok thinning je modifikován, aby hrany byly spojité. Topologický přístup. | ||
| - | |||
| - | |||
| - | ==== Založené na druhé derivaci ==== | ||
| - | |||
| - | Hrany se nacházejí v nulových bodech (zero crossings) druhé derivace, to jsou maxima první derivace. | ||
| - | |||
| - | === Laplaceův operátor (Δ) === | ||
| - | Aproximuje druhou derivaci funkce. | ||
| - | {{:mgr-szz:in-gra:laplace.png|}} | ||
| - | |||
| - | Nevýhody: | ||
| - | * detekuje nejen maxima, ale i minima | ||
| - | * citlivý na šum | ||
| - | * nedetekuje orientaci hrany | ||
| - | Výhody: | ||
| - | * produkuje spojité hrany | ||
| - | * invariantní k otáčení o násobky 45° | ||
| - | * orientačně nezávislý | ||
| - | |||
| - | == Laplacian of Gaussian (LoG) == | ||
| - | 5 x 5 LoG: | ||
| - | {{:mgr-szz:in-gra:log_mask.png|}} | ||
| - | |||
| - | "Mexican hut": | ||
| - | {{:mgr-szz:in-gra:log_mexican_hut.png|}} | ||
| - | |||
| - | == Difference of Gaussians (DoG) == | ||
| - | Aproximuje LoG. | ||
| - | {{:mgr-szz:in-gra:dog.png|}} | ||
| - | Ideální poměr: σ1/σ2 = 1.6 | ||
| - | |||
| - | |||
| - | ==== (Template based edge detection) ==== | ||
| - | |||
| - | === Lineární === | ||
| - | {{:mgr-szz:in-gra:template_lin.png|}} | ||
| - | |||
| - | === Nelineární === | ||
| - | == Goodness-Of-Fit Test Based Edge Detection == | ||
| - | {{:mgr-szz:in-gra:template_nelin.png|}} | ||
| - | |||
| - | ===== Diskrétní transformace ===== | ||
| - | |||
| - | ==== Fourierova transformace ==== | ||
| - | Slouží k převodu obrazu (z prostorové domény, I) do duálního prostoru (frekvenční domény, F) a zpět. Frekvenčná doména je obecně složením nekonečně mnoha sinusových signálů s různou amplitudou, které jsou různě fázově posunuté. | ||
| - | |||
| - | {{:mgr-szz:in-gra:ft1.png|}} | ||
| - | {{:mgr-szz:in-gra:ft2d.png|}} | ||
| - | k=0...N-1, n=0...N-1 | ||
| - | komplexní jednotka: i = √(-1) | ||
| - | Eulerova formule: e^(±i2πux) = cos(2πux) ± i sin(2πux) | ||
| - | Mějme bod o souřadnici u = Re(u) + i Im(u). Amplitudové spektrum funkce F(u) je |F(u)| = √(Re²(u) + Im²(u)), fázové spektrum φ(u) = atan(Re(u)/Im(u)). | ||
| - | {{:mgr-szz:in-gra:ft.png|}} | ||
| - | |||
| - | dualita: F ⇔ I | ||
| - | {{:mgr-szz:in-gra:ft2.png|}} | ||
| - | |||
| - | |||
| - | ==== FFT (Fast Fourier Transform) ==== | ||
| - | |||
| - | Důležité vlastnosti Fourierova transformace: | ||
| - | 1. Roztažení (stretch) funkce v prostorové doméně odpovídá opakování funkce (repetition) ve frekvenční doméně: | ||
| - | {{:mgr-szz:in-gra:ft3.png|}} | ||
| - | 2. Posun (shift) v prostorové doméně ovlivňuje jenom fázu: | ||
| - | {{:mgr-szz:in-gra:ft6.png|}} | ||
| - | |||
| - | {{:mgr-szz:in-gra:ft4.png|}} | ||
| - | {{:mgr-szz:in-gra:ft5.png|}} | ||
| - | |||
| - | Proveďme dělení dokud je možné, tj. dostaneme se k signálu délky jednoho bodu, který je stejný bod i ve frekvenční doméně: | ||
| - | {{:mgr-szz:in-gra:fft.png|}} | ||
| - | |||
| - | ====== Geometrické transformace obrazu ====== | ||
| - | Chceme transformovat vstupní obraz A na výstupní B. Geometrická transformace obrazu složeného z bodů [x,y] je funkce T(u,v) = [x(u,v), y(u,v)]. | ||
| - | * Dopředné mapování - procházíme pixely A, hledáme jejich umístění v obraze B (oblast) | ||
| - | * Zpětné mapování - procházíme pixely B, hledáme odpovídající oblasti v A | ||
| - | Separabilita: | ||
| - | Transformace je separabilní, pokud ji lze zapsat ve tvaru T(u,v) = F(u, G(v)). F a G jsou funkce jedné proměnné. Př. Fourierova transformace. | ||
| - | |||
| - | ===== Vzorkování (Sampling) ===== | ||
| - | |||
| - | Comb function (||| - shah): | ||
| - | {{:mgr-szz:in-gra:shah.png|}} | ||
| - | {{:mgr-szz:in-gra:shah2.png|}} | ||
| - | |||
| - | Vzorkování je proces převodu spojité funkce na diskrétní. | ||
| - | {{:mgr-szz:in-gra:sampling.png|}} | ||
| - | |||
| - | {{:mgr-szz:in-gra:sampling2.png|}} | ||
| - | == Nyquist-Shannon theorem == | ||
| - | Spojitou funkci je možné úplně zrekonstruovat pouze v případě, že signál je frekvenčně omezený (bandlimited) a vzorkovací frekvence je dvakrát větší než maximální frekvence signálu. | ||
| - | Při nesplnění těchto vlastností vzniká alias. | ||
| - | {{:mgr-szz:in-gra:sampling3.png|}} | ||
| - | |||
| - | ===== Rekonstrukce (Reconstruction) ===== | ||
| - | Inverzní proces ke vzorkování, konvoluce s low-pass filterem. Zrekonstuuje originální spojitý signál z diskrétních vzorků. | ||
| - | Rekonstrukční filtry: | ||
| - | * box - nejbližší soused | ||
| - | * tent - lineární interpolace | ||
| - | * kubický B-spline - kubická polynomiální interpolace | ||
| - | * Gaussian | ||
| - | * sinc | ||
| - | * Lanczos - omezený sinc | ||
| - | Plocha pod filtrem musí být jednotková, tj. ∫ h(t) dt = 1, kde h je rekonstrukční filter. | ||
| - | |||
| - | ===== Převzorkování (Resampling) ===== | ||
| - | {{:mgr-szz:in-gra:reconstruction.png|}} | ||
| - | |||
| - | ===== Lineární geometrické transformace ===== | ||
| - | |||
| - | == Posunutí (Translation) == | ||
| - | {{:mgr-szz:in-gra:translation.png|}} | ||
| - | == Otáčení (Rotation) == | ||
| - | {{:mgr-szz:in-gra:rotation.png|}} (clockwise) | ||
| - | == Změna měřítka (Scale) == | ||
| - | {{:mgr-szz:in-gra:scaling.png|}} | ||
| - | == Zkosení (Shear) == | ||
| - | {{:mgr-szz:in-gra:shear.png|}} | ||
| - | |||
| - | ===== Nelineární geometrické transformace ===== | ||
| - | |||
| - | == Warping == | ||
| - | viz otázku č. 13 | ||
| - | |||
| - | ====== Zdroj ====== | ||
| - | Žára, Beneš, Sochor, Felkel. Moderní počítačová grafika. Computer Press, Brno, 2004. ISBN: 80-251-0454-0 | ||
| - | David Svoboda : PA171 - Digital image filtering, slajdy. 2012. Fakulta informatiky, Masarykova Univerzita. Brno. | ||
