== Rozsah látky ==
Seznam [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b52.htm oficiálních] státnicových otázek:
: Výstupní grafická zařízení, plošné útvary - jejich reprezentace a množinové operace s nimi, kreslicí a ořezávací algoritmy v rovině, anti-aliasing, barevné vidění a barevné systémy, reprodukce barevné grafiky, rozptylování a půltónování, kompozice poloprůhledných obrázků, geometrické deformace rastrových obrázků, morphing, základní principy komprese rastrové 2D grafiky, skalární a vektorové kvantování, prediktivní komprese, transformační kompresní metody, hierarchické a progresivní metody, waveletové transformace a jejich celočíselné implementace, kódování koeficientů, komprese videosignálu, časová predikce - kompenzace pohybu, standardy JPEG a MPEG, snímání obrazu v digitální fotografii.
== Výstupní grafická zařízení ==
* podľa trvanlivosti zobrazenia
** zobrazovacie zariadenie (display, projector)
** tiskové zariadenia (tiskárna, plotter, osvitová jednotka)
* podle barevných schopností
** Č/B zobrazenie (2 barvy)
** monochromaticke zobrazení (256 odstínů šedi)
** Barevná paleta (pevná nebo nahrávaná: 16-1024)
** plná barevnost ("true-color" - maximální barevné využití zobrazovací technologie: 16.7 mil. i více)
* rastrový/vektorový výstup
** rastrový
*** jsou přímo adresovány jednotlivé pixely
*** data jsou závislá na rozlišení (a nelze je jednoduše škálovat)
** vektorový
*** zobrazují se přímo složitější objekty (čáry, křivky, písmo)
*** data nejsou závislá na rozlišení (lze je škálovat až v zobrazovacom zařízení)
* podla technologie výstupu:
** vektorový výstup (staré displeje, plotter, některé osvitové je dnotky)
** rastrový výstup (displje, tiskárny)
* podle komunikace:
** vektorové zařízení (urychlované video-adaptéry, plottery, PostScript)
** rastrové zařízení (bežné video-adaptéry, tiskárny v grafickém režimu)
== Plošné útvary - jejich reprezentace a množinové operace s nimi ==
== Kreslicí a ořezávací algoritmy v rovině ==
=== Kreslení ===
==== Kreslení čar ====
* Kreslení čáry - DDA algoritmus (celočíselní)
** vyhoda - snadná implementace
** nevýhody - nutno počítat s velkou přesností (real, fixed point), jedno dělení, v cyklu zaokrouhlování
input: x_1, x_2, y_1, y_2, color : integer
1. <math>x=x_1, y=y_1</math>
2. <math>dx=1; dy=\frac{y_2 - y_1}{x_2, x_1}</math> ''(předpokládáme |y_2 - y_1| < |x2-x1|)''
3. while (x<=x_2) <math>x_{n+1}=x_n+dx, y_{n+1}=y_n+dy</math>; PutPixel(x, round(y), color);
* Kreslení čáry - Bresenhamův algoritmus
** vyhody - rychlost, iba nasobenie a ščítaní, dá se implementovat bez if-ů
* Kreslení kružnica - Bresenhamův algoritmus
** kreslí se jen <math>\frac{1}{8}</math> kružnice (tj. while y>x) - zbytek se řeší symetrií
==== Odvození Bresenhamových algoritmů ====
* Rozkreslení pixelů, jejich polovin
* Určení základních vztahů pro dané tvary
** Úsečka - <math>E'=E-\frac{dy}{dx}<=M=\frac{1}{2}</math>
** Kružnice - <math>F(M)=M_x^2+M_y^2-R^2 > 0 </math>
** Elipsa - kreslí se po čtvrtinách, pozor, od chvíle, kdy dy=dx se posouvá v každém kroku y a ne x!!!
*** <math> F(M)=b^2M_x^2+a^2M_y^2-a^2b^2 > 0 </math>
* Odstranění zlomků, odvození inkrementů(resp. dekrementů)
==== Vyplňování n-úhelníka ====
* Seznam hran, dy, dxy (změna x při změně y o 1)
* Hrany orientované shora dolů, setříděné podle y, x, dxy
* Udržuje se seznam aktivních hran při vyplňování
* Zjednodušeně se vyplňují jen liché body
==== Vyplňování souvislé oblasti ====
Více druhů:
* Hraniční
* Stejné barvy (záplavové)
* 4-souvislé, 8-souvislé
Lépe využít frontu než zásobník - menší spotřeba paměti.
Řádkový algoritmus
==== Kreslení písma ====
Písmo zadáno dvěma různými způsoby:
* Vektorově
** Pomocí úseček, oblouků, kružnic,...
** Snadné neprofesionální škálování
** Při kreslení je nutno resterizovat
* Rastrově
** Zadáno v bitmapě
** Snadné vykreslení pomocí BitBlt
Při vykreslování vhodné využití vzoru Flyweight. (Vektorové písmeno se převede jen jednou pro danou velikost, nechá se uloženo v cache)
=== Ořezávání ===
Ořezávání úseček - Cohen-Sutherland:
* spočítá kódy pro koncové body úsečky (y>ymax, y<ymin, x>xmax, x<xmin)
* podle kódu:
** AND není nula -> mimo obraz,
** OR je nula -> oba uprostřed,
** jinak řezám podle kódů
ořezávání: Cyrus-Beck
* Okno je konvexní n-úhelník
* řežeme přímku P(t) = A +t * (B-A)
* každá hrana okna má normálu, která směřuje ven.
** tmin = 0; tmax=1
** dokud tmin < tmax, opakuj pro každou hraniční přímku
*** Pokud N dot (B-A) = 0, je úsečka rovnoběžná s hraniční přímkou, rozhodni na které straně
*** Jinak spočítat průsečík úsečky s přímkou a upravit tmin nebo tmax
Ling-Barsky
* efektivní úrava Cyrus-Beck pro obdélníkové okno
Ořezávání n-úhelníků:
* Pokud chceme jen hrany, stačí řezat jednotlivé úsečky
* Pokud chceme vybravovat, musíme oříznout speciálně
Proudové ořezávání (Sutherland-Hodgman):
* Ořezává podle jedné hranice obdélníkového okna, pro zbylé hranice se souřadnice otáčejí o 90 stupnu
* alg si pamatuje poslední 2 vrcholy (Last a Actual) a v závislosti na tom, na které straně hranice jsou vydává nové vrcholy n-úhelníka:
** L i A jsou uvnitř -> Output(A)
** L uvnitř, A venku -> Output(průsečík s hranicí)
** L i A venku -> nic
** L venku, A uvnitř -> Output(průsečík s hranicí), Output(A)
== Anti-aliasing ==
=== Alias ===
Alias vzniká při rekonstrukci vzorkovaného singálu. Jedná se o dodatečnou (nežádanou) nízkofrekvenční informaci, která vzniká ve dvou případech:
1. Pokud je původní funkce frekvenčně neomezená - neexistuje maximální frekvence. => při diskrétním zobrazení spojité funkce nikdy nedostaneme přesnou reprezentaci.
2. Pokud je původní funkce frekvenčně omezená, tj. pokud existuje v jejím Fourierovském spektru maximální frekvence fmax. Pokud se taková funkce vzorkuje s frekvencí menší než tzv. Nyquistův limit -> fnyq = 2*fmax, vzniká alias.
Typický příklad - vykreslování šachovnice.
=== Antialiasing ===
Problém aliasu se typicky řeší zvýšením prostorového rozlišení na úkor barevného - použitím více odstínů té samé barvy. Pixely i kreslené útvary jsou plošné objekty => pixely rozsvítím s intenzitou úměrnou jejich pokrytí.
Provádí se pomocí supersamplingu - převzorkováním na vyšší rozlišení a následným průměrováním hodnot. Nevýhodou je ztráta informace u vysokofrekvenčních částí - ostré hrany se rozmažou.
Vyhlazování pomocí integrace - obraz. fce f(x,y), vyhlazovací filtr h(x,y): Intenzita pixelu i,j je
<math>
I(i,j) = \int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} f(x,y) h(x-i, y-j)\, dx dy
</math>
Většinou se stačí omezit na obdélníkový filtr jednotkového čtverce
<math>
I(i,j) = \int\limits_{i}^{i+1}\int\limits_{j}^{j+1} f(x,y)\, dx dy
</math>
Integrál lze buď spočítat analyticky nebo odhadnout numericky z několika vzorků:
<math>
I(i,j) = \frac{\displaystyle \sum_{k} f(x_k,y_k) h (x_k,y_k)}{\displaystyle \sum_{k} h(x_k,y_k)}
</math>
. Poznámka: Tady by IMO mělo být h(x_k-i, y_k-j), ve slajdech je tohle.
* Pravidelné vzorkování - jen přenese problém o řád dál
* Stochastické vzorkování - problém se řeší umělým přidáním šumu
** Poison disc
** Jittering (roztřesení)
** N-věží
Adaptivní zjemňování: vzorkujeme podle důležistosti, nejprve několik vzorků a pokud je mezi nimi přiliš veliký rozdíl, zjemni vzrokování v dané podoblasti.
== Barevné vidění a barevné systémy, reprodukce barevné grafiky ==
=== Barevné vidění ===
oko - rohovka, duhovka, panenka, čočka, sklivec, sítnice. Žlutá skvrna
Tyčinky - intenzita světla - vnímání kontrastů, vidění za šera, v oku cca 120e6
Čípky - tři typy (r, g, b) - vnímání barev, soustředěny ve žluté skvrně, v oku cca 8e6
=== Barevné systémy ===
* RGB
* CMY(K) = 1 - RGB
* HSV (barvy na šestibokém jehlanu), HLS (barvy na dvou kuželech)
** převod není prosté zobrazení, používá se algoritmus. viz Pelikánovy slidy
* <math>YC_bC_r</math> - používán při kódování JPEG
** <math>Y = 0.3*R + 0.6*G + 0.1*B</math>
** <math>C_b = 0.56*(B-Y)</math>
** <math>C_r = 0.71*(R-Y)</math>
* různé barevné palety s různými počty barev
==== Konstrukce adaptované palety ====
Paleta se může adaptovat pro daný obrázek (např. v GIFu).
Metody:
* shora dolů
** množinu použitých barev dělím tak dlouho, dokud nedostanu požadovaný počet
* zdola nahoru
** sdružuji příbuzné barvy
* metoda shlukové analýzy
** využívá se histogram
* Heckbertova metoda
** opět histogram
** dělí se nejdelší vážená hrana kvádru v místě těžiště
=== Reprodukce barevné grafiky ===
Pokud někdo tušíte, co spadá pod tuhle otázku, prosím doplňte. Slajdy Pelikána [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/pg1-11-colorreproduction.pdf Zobrazování barev]
== Rozptylování a půltónování ==
Napodobení vjemu neexistujících barevných odstínů pro dané zařízení. Zvyšuji barevné rozlišení na úkor prostorového.
* Rozptylování
** zobrazuje se bez zvětšení rozlišení (1:1)
* Půltónování
** zobrazuje se se zvětšeným rastrovým rozlišením (1:N)
Typické příklady:
* černobílé tiskárny
* displaye s malou paletou barev
* obrázky s omezenou paletou
=== Půltónování ===
Jeden zdrojový pixel (rozsah hodnot 0-<math>N^2</math>) nakreslím jako čtverec NxN
* Inkrementální rastry
** odstín hodnoty k obsahuje právě k černých teček
** lze uložit do matice
* Pravidelný rastr
* Tečkový rastr
* Nutno předcházet pravidelnosti a aliasu - rastry se často otáčejí
=== Rozptylování ===
* Maticové rozptylování
** libovolná půltónovací matice
** nejčastěji matice pravidelného rastru
** několik sousedních pixelů sdílí jednu matici
** ztráta drobných detailů
** zvýraznění vedlejších odstínů
* Náhodné rozptylování
** pro lidské oko mnohem přirozenější
** černobílé obrázky příliš zašumělé - lepší výsledky u více výstupních odstínů
* Distribuce chyby
** zaokrouhlím hodnotu pixelu na nejbližší zobrazitelnou
** rozdíl distribuuji mezi sousední pixely
*** různé způsoby distribuce
*** je třeba pomocný buffer
** výhody
*** příjemné pro oko
*** dobrá kvalita
** nevýhody
*** nutnost kreslit po řádkách
*** nemožnost vrátit ze zpátky
*** pomalé
== Kompozice poloprůhledných obrázků ==
Slajdy: [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/pg1-08-alpha.pdf Kompozice rastrových obrázků]
Druhy kompozice:
* montáž
* prolínání
* syntéza
Alfa: procentuální pokrytí pixelu barvou (0-prhledné, 1-neprůhledné)
Skládání dvou pixelů: Mám pixel <math>[A, \alpha_A]</math> a <math>[B, \alpha_B]</math>. V realitě se mohou různě překrývat, ale mám pouze číslo alfa. Model pokrytí pixelu, kde je pixel pokryt barvou A s s rovnoměrně rozloženou pstí alfa_A. Nezáleží tak na skutečném tvaru a vyhovuje ve většině případů.
Překrývání dvou pixelů v realitě má 4 oblastí:
* Oblast bez A i bez B
* Oblast pouze s A
* Oblast pouze s B
* Oblast s A i B
V závislosti na způsobu překryvu je 12 možností, jak je zkombinovat
* Clear - nepoužijenic, F_A i F_B jsou 0
* A - pouze A, F_A=1, F_B=0
* B - pouze B, F_A=0, F_B=1
* A přes B, F_A=1, F_B=1-alpha_A
* B přes A, F_A=1-alpha_B, F_B=1
* A v B, F_A=alpha_B, F_B=0
* B v A, F_A=0, F_B=alpha_A
* A mimo B
* B mimo A
* A na povrchu B
* B na porvrchu A
* A xor B
F_A a F_B je kolik procent plochy, která by měla mít barvu A/B se má použít při směsi (ne poměr na vělikost pixelu, ale na plochu A/B pixelu).
Čtveřice RGBa se ukládají jako <math>[R\alpha, G\alpha, B\alpha, \alpha]</math>, při zpětném převodu se barvy jen vydělí alfa kanálem. Dva pixely se slučují jako <math>[F_A R_A + F_B R_B; F_A G_A + F_B G_B; F_A B_A + F_B B_B; F_A \alpha_A + F_B \alpha_B]</math>.
Další operace:
* darken(A, <math>\rho</math>) <math>[R\rho, G\rho, B\rho, \alpha]</math>
* fade(A, <math>\delta</math>) <math>[R\delta, G\delta, B\delta, \alpha\delta]</math>
* opaque(A, <math>\omega</math>) <math>[R, G, , \alpha\omega]</math>
== Geometrické deformace rastrových obrázků ==
Slajdy: [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-03-warping.pdf Deformace rastrových obrázků] a [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-04-warps.pdf Konkrétní metody deformace obrazu].
Účely deformace:
* mapování textur při 3D zobrazování, např. mapování na oblá tělesa
* oprava geom. zkreslení, např. letecké snímky
* speciální efekty
=== Geometrická transformace ===
Máme obrazovou funkci <math>f(x,y) -> R^n</math> mapující polohu v rovině na atributy (barva, průhlednost...). Obrazová fci typicky nemáme, máme pouze diskrétní rastrový obraz I digitalizovaný pomocí filtru d: <math>I_f(i,j) = \int\int f(x,y) d(x-i, y-j) dx dy</math>. Fce d je způsob, jak třeba pixelové čidlo v kameře snímá světlo, které na něj dopadá.
Zrekonstruovaný obraz: <math>f^r(x,y) = \sum\limits_{i=0}^{m-1}\sum\limits_{j=0}^{n-1} I_f(i,j) . r(i-x, j-y)</math>. Chceme, aby se <math>f^r</math> co nejvíce podobala původní <math>f</math>.
Geometrická transformace je fce <math>g: R^2 -> R^2</math>, která vytvoří novou obraz. fci <math>f'</math>, pro kterou platí <math>f(x,y) = f'(g(x,y))</math>, resp. <math>f'(x,y)=f(g^-1(x,y))</math>.
Transformace s interpolací (zpětná): předpokládá, že vzorky jsou brány dirac. impulsem, pro každý pixel v cíli transformuje pomocí <math>g^-1</math> do zdrojových souřadnic a tam interpoluje (bilin/bicub).
Transformace s filtrací (dopředná): odpovídá představě plošného pixelu, digitalizační filtr s nenulovou plochou. Zdrojové pixely se přenášejí do výsledného obrázku (není potřeba <math>g^-1</math>).
Vícekrokové transformace: místo jedné 2D transformace se použije více 1D transformací, transformují se pouze řádky/sloupce. Je to rychlejší, ale možnost ztráty přesnosti mezivýsledku.
=== Deformace ===
Zadávání deformační fce:
* explicitní analytická fce, např. mapování na kouli
* funkce zadávané po částech, typicky uživatelem, změny mají jen lokální charackter
Deformace v trojúhelníkové síti: Máme síť trojúhelníků a její vrcholy měníme -> topologie zůstává stejná. Barycentrické souřadnice bodu X v trojúhelníku <math>X = A x_a + B x_b + C x_c; x_a, x_b, x_c > 0; x_a + x_b +x_c = 1</math> (bod v trojúhelníku je A + alfa * (B-A) + beta * (C-A); alfa + beta = 1 a > 0). Algoritmus: procházím cílový obrázek řádkovým rozkladem, uvnitř každého trojůhelníku se souřadnice mění lineárně -> diferenční alg. Problémy: nespojitosti 1 řádu ( čára přes 2 trojůhelníky nezůstává čárou, nespojitá 1 derivace).
Aproximace vyšších řádů:
* kvadratická / kubická - spojité první nebo druhé derivace
* troj/čtyřpúhelníková topologie (je potřeba znát i okolní buňky)
* inverzní zobrazení obtížné
Feature-based warping:
* Lokální zadávání deformační fce - uživat. příjemné, není potřeba zadávat nepokryté oblasti
* Do zdroj. a cíl. obrázku se umisťují páry orientovaných úseček
* Pokud 1 šipka, afinní tranformace, pokud více, radiální tranformace
== Morphing ==
Slajdy [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-05-morphing.pdf Morphing]
Metamorfóza obrázku, transformace mezi dvěma obrázku (obrys pes->kočka), geom. deformace obrázku případně změna obrazové fce z jednoho na jiný obrázek.
Morphing je '''postupný''', máme počátek (čas t=0) a konec (čas t=1), ale je potřeba nějak interpolovat deformační fci <math>g</math> a obrazovou fci <math>f</math>. Obrazová fce v čase <math>t</math> je snadná <math>f_t(x,y) = (1-t)*f_0(x,y) + t * f_1(g(x,y))</math>, u deformační máme pouze okrajové podmínky <math>g_0(x,y)=[x,y]</math> a <math>g_1 = g(x,y)</math>.
Interpolace deformační fce jsou různé:
* deformace zadáné sítí - interpolují se jednotlivé body sítě
* deformace zadané soustavou šipek - lin. interpolace šipek
* deformace mnohoúhelníků v rovině - přechodová fce minimalizující vynaloženou práci
=== Metamorfóza mnohoúhelníků ===
Pokud mají mnohoúhelníky stejný počet vrcholů, lze použít lin. interpolaci vrcholů, případně lin. interpolaci úhlů vrcholů + délky hran.
Dále exituje model založený na minimalizaci deformační práce, založené na modelu drátu (natahovací/ohýbací práce).
== Základní principy komprese rastrové 2D grafiky ==
== Skalární a vektorové kvantování ==
== Prediktivní komprese ==
== Transformační kompresní metody ==
== Hierarchické a progresivní metody ==
== Waveletové transformace a jejich celočíselné implementace ==
[http://faculty.gvsu.edu/aboufade/web/wavelets/student_work/EF/how-works.html Jak funguje JPEG 2000]
== Kódování koeficientů ==
== Komprese videosignálu, časová predikce – kompenzace pohybu ==
== Standardy JPEG a MPEG ==
[http://en.wikipedia.org/wiki/MPEG-1 MPEG-1];
[http://en.wikipedia.org/wiki/MPEG-2 MPEG-2];
[http://en.wikipedia.org/wiki/MPEG-3 MPEG-3];
[http://en.wikipedia.org/wiki/MPEG-4 MPEG-4];
[http://en.wikipedia.org/wiki/Chroma_subsampling Chroma subsampling]
[http://en.wikipedia.org/wiki/Macroblock Macroblock]
== Snímání obrazu v digitální fotografii ==
== Materiály ==
* [[Počítačová grafika I]] – stránka předmětu
* [[Pokročilá 2D počítačová grafika]] – stránka předmětu
* [[Speciální funkce a transformace ve zpracování obrazu]] – stránka předmětu
{{Stub}}
[[Category: Státnice Informatika Mgr.]]
