== 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 ==
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/pg1-19-imagecoding.pdf Kódování rastrových obrázku] a [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-09-still1g.pdf kompresní metody první generace]
Komprese snižuje množství dat:
* odtraňuje redundantní data
* odstraňuje informace nedůležité pro lidské oko
Schéma komprese: kodér obrazu (2D/3D) -> kanálový kodér (1D) -> kanálový dekodér -> dekodér obrazu
Důležité parametry komprese:
* kompresní poměr
* kvalita
* složitost implementace
* zpoždění
Další parametry:
* specifikovaná kvalita
* variabilita kompresního poměru
* citlivost k chybám přenosu
* progresivní kódování
* snadná HW implementace
Kanálové kódování/kódování entropie: LZW, RLE, Huffman, max 10:1 na obrázek
Komprese obrazu (kódování 2D/3D dat, fyziologie vidění):až 100:1 na obrázek
Typy kompresních algoritmů:
* Založené na datovém modelování, např. lin. predikce
* Bezeztrátové založené na průběhu fce, např. huffman
* Ztrátové založené na průběhu fce, např. delta modulace, wavelety
=== Komprese dat ===
* Máme kódovanou abecedu <math>S = {x_1, x_2,...x_n}</math>
* pst. výskytu symbolu <math>x_i</math> je <math>p_i</math>
* kód symbolu <math>x_i</math> má délku <math>d_i</math>
* zpráva (kódovaný řetězec) <math>X = x_{i_1}, x_{i_2},...x_{i_k}</math>
* entropie (informační hodnota) symbolu <math>x_i</math> je <math>E_i=- \log_2 p_i</math> bitů
* průměrná entropie '''symbolu''' je <math>AE = \sum\limits_{i=1}^{n} p_i E_i</math> bitů
* entropie zprávy je <math>E(X) = \sum\limits_{j=0}^{k} p_{i_j} E_{i_j} = - \sum\limits_{j=0}^{k} p_{i_j} log_2 p_{i_j}</math> bitů
* délka zprávy <math>L(X) = \sum\limits_{j=1}^k d_{i_j}</math> bitů
* redundance zprávy <math>R(X)=L(X) - E(X)</math> bitů
* Výběrová střední kvadratická odchylka <math>RMS^2 = \frac{1}{NM} \sum \sum (u_{i,j} - u'_{i,j})^2</math> (původním obrazem vs rekonstrukce)
* Peak Signal to Noise ratio <math>PSNR = 10 log_{10} \frac{P^2}{RMS^2} dB</math>, kde P^2 je interval hodnot originálu, např 255^2
== Skalární a vektorové kvantování ==
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-09-still1g.pdf Slajdy]
'''Pulzní kódová modulace'''
Přenos analogového signálu digitálním kanálem, signál se vzorkuje v čase a kvatizuje a pak kóduje (moduluje)
Kvantování: vezmu spojitý signál a přiřadím mu přihrádku. Mám rozhodovací hodnoty <math>t_i</math> a rekonstrukční hodnoty <math>r_i</math>. Pokud <math>t mezi <t_i, t_{i+1})</math>, tak se použije rekonstrukční hodnota <math>r_i</math>
* lineární kvantovač - používá se roznoměrné rozdělení (rekonstrukční hodnota uprostřed intervalu rozhodovacích hodnot)
* Lloydův-Maxův kvantovač - minimalizuje střední kvadratickou chybu kvantování <math>E=E[(u-u')^2] = \int\limits{t_1}{t_{T+1}} [x - u'(x)]^2 p(x) dx</math>.
Vektorové kvantování: Kvantuje se celý vektor najednou podle určené kvantovací tabulky. Různé rozhodovací hodnoty pro různé koeficienty vektoru, např u JPEG je blok 8x8 s největší hodnotou vlevo nahoře, to se použije pro zig-zag.
Zónální kvantování: vektorové kvantování, přenáší se jen jistá část vektoru. Zbylé části se ignorují.
Prahové kódování koeficientů: přenáší se pouze K koeficientů s nevětší amplitudou.
Prediktivní kvantování: kvantovač nekvantuje hodnotu, ale chybu. Chyba je spočítána jako hodnota signálu - predikce hodnoty signálu, která je spočítána z minulých hodnot.
== Prediktivní komprese ==
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-09-still1g.pdf Slajdy]
Využívají závislost sousedních pixelů. V implementaci se používá predikční fce, která podle minulých hodnot co nejlépe odhadne současnoun hodnotu. Kóduje se pouze rozdíl mezi predikované hodnoty a skutečné hodnoty. Při úspěšné predikci má chyba menší amplitudu.
=== DPCM ===
Digital pulse-code modulation - kvantuje se chyba mezi predikovanou hodnotou a skutečnou hodnotou.
* Kodér
* Dekodér
* Různé prediktory, nelineární, 2D/3D
=== Delta modulace ===
* Kvantovač má pouze 2 výstupní hodnoty +q a -q
* Prediktor je zpožďovací fce, která predikuje <math>\overline{u'_k} = u'_{k-1}</math> (chyba je tudíž <math>e_k = u_k - u'_{k-1}</math>)
* vstupní fce nemusí být vzrokovaná, v takovém případě se používá integrátor
* Převážně pro analogové signály, zvuk atd.
* Může zrnit, v takovém případě třístavová kvantizační fce +q, 0, -q
=== Adaptivní predikční metody ===
* Několik různých prediktorů pro různé směry, vybírá s max korelací
* adaptivní kvantovač chyby, podle rozptylu predikční chyby
* klasifikace oblastí podle lokálního okolí pixelu, např. rozdělit obraz do několika bloků 16x16
== Transformační kompresní metody ==
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-09-still1g.pdf Slajdy, 20+] a [http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-10-imagetransform.pdf slajdy transformačních fcí]
* řetězec: Transformace - kvantovač - kodér - dekodér - dekvantovač - inverzní transformace
* Snaží se pracovat s celým blokem (vektorem) obrazu najednou
* snaží se minimalizovat vzájemnou závislost jednotlivých složek vektoru
Transformační fce T:
* 1D - rozklad obrázku na jeden řádek
* 2D pracuje s celým blokem najednou
T by měla
* většinu informací o bloku soustředit do několika málo koeficientů
* zkreslení způsobené kvantováním a vynecháním koeficientů být co nejmenší
* koeficienty by měly být po transformaci co nejméně závislé
* rychlý výpočet T i T^-1
Kvantování může používat různé kvantovače pro různé koeficienty
'''1D lineární transformační metody''' používají lineární transformaci jako T
=== Praktické transformace ===
Mají suboptimální vlastnosti, ale jsou rychlejší, např. O(N logN) nebo O(N). Hledají koeficienty v nějaké ortonormální bázi (např. 1D cosinová báze), která má nejmenší chybu.
* Sinové transformace - Fourier, Sin, Cos
* po částech konstantní funkce, sčítání a odečítání, rychlé
* Wavelety
Kvantizace po transformacei
* Zónální kódování koeficientů - koeficienty mají různou potřebu přesnosti, přenáší se pouze určitá oblast (zóná)
* Prahové kódování koeficientů - přenáší se pouze K koeficientů s největší amplitudou. Zóna se pro každý blok liší -> je potřeba ji nějak zakódovat
=== Adaptivní transformační metody ===
Blok je předem analyzován a podle jeho charakeristik se používají různé
* transformační funkce
* kvantovače
* přenášené oblasti
=== Hybridní metody ===
Kombinuje transformační a hyrbidní metody, pro každý blok se použije transfomace a jednotlivé prvky se přenášejí prediktivně, případně se vynechají. Přenášené koeficienty je potřeba sjednotit do 1 proudy dat.
=== Interpolační metody ===
Přenáší se pouze některé pixely a zbylé se dopočítají.
== Hierarchické a progresivní metody ==
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-11-jpeg1.pdf Slajdy JPEG.1]
=== Progresivní kódování ===
Několik průchodů s postupným zlepšováním obrazu. Obraz je kódován v několika průchodech, postupně se zlepšuje jeho kvalita (vnhodné pro net, přenos lze zrušit). Je potřeba buffer pro celý obrázek.
Dvě metody:
* spektrální výběr - v každém průchodu se přenese jen několik koeficientů, od nejdůležitějších k méně důležitým. Každý koeficient se přenáší celý.
* postupná aproximace - přenášejí se všechny koeficinety, postupně se zpřesňují. Např. nejdříve se přenáší od most significant bit po least significant bit.
=== Hierarchické kódování ===
Je k dispozici několik různých rozlišení obrazu, které lze samostatně dekódovat
* Pyramidální kódování - Obraz je postupně přenášen v několika různých rozlišeních. Nižší rozlišení lze použít jako predikci pro vyšší rozlišení, kódují se pouze rozdíly. Jednotlivá rozlišení mohou být kódována různým způsobem.
* Mipmapy pro textury - textura o rozměru NxN je uložena ve čtverci 2N*2N, 1/4 paměti je použita pro nižší rozlišení
== Waveletové transformace a jejich celočíselné implementace ==
[http://faculty.gvsu.edu/aboufade/web/wavelets/student_work/EF/how-works.html Jak funguje JPEG 2000]
[http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-16-wavelets.pdf Pelikan Wavelet Lifting]
== Kódování koeficientů ==
Zónální a prahové kódování koeficientů.
Progresivní kódování:
* spektrální výběr - v každém průchodu se přenese jen několik koeficientů, od nejdůležitějších k méně důležitým. Každý koeficient se přenáší celý.
* postupná aproximace - přenášejí se všechny koeficinety, postupně se zpřesňují. Např. nejdříve se přenáší od most significant bit po least significant bit.
VLI - Variable length integer. Přenáším počet bitů přenášené hodnoty a její hodnotu dle:
* 1 bit -1, 1
* 2 bit -3..-2 2..3
* 3 bity -7..-4 4..7
* 4 bity -15..-8 8..15
== Komprese videosignálu, časová predikce – kompenzace pohybu ==
[[wen:Motion compensation]], [[wen:Video compression]]
== 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]
[http://http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-11-jpeg1.pdf Pelikán - JPEG1]
[http://http://cgg.mff.cuni.cz/~pepca/lectures/pdf/2d-13-mpeg.pdf - Pelikán MPEG]
=== JPEG ===
* DCT bloky 8x8
* kvantování - fyziologicky optimalizované tabulky
* kódování - huffman/artimetický kodek
DCT - před transformací posun z <math>0..2^p - 1</math> do <math>-2^{p-1} .. 2^{p-1} -1</math>
Spočítané DCT koeficienty se kvantují, přesnost koeficientů závisí na jejich důležitosti pro vizuální vjem. Používají se lineární kvantovače, hodnota DCT koeficientu se vydělí hodnotou v kvantovací tabulce.
Kódování kvnatovaných koeficientů: F(0,0) je odlišný, používá se predikce z minulých bloků, přenáší se jen rozdíl. Zbylé koeficienty jsou zig-zag uspořádány, pak RLE a zakódovány pomocí VLI. Výsledek se zakóduje pomocí huffmana nebo artimentického kódéru.
Bezeztrátová varianta JPEG založena na prediktivním kodéru (DCT není vhodné). K dispozici 7 různých prediktorů 1D/2D. Chyby predikce reprezentovány pomocí VLI a huffman.
JPEG může mít až 255 složek, jednotlivé složky mohou mít různé rozlišení.
Progresivní režim: spektrání/postupná aproximace
Hierarchický režim: Postupně se přenáší obrázek ve stále lepším rozlišení. Pouze chyba je přenášena.
=== MPEG ===
* Kompenzace pohybu, makrobloky 16x16
* Různé vzrokovací schémata, barvevné složky se mohou přenášev v různé časové/prostorové kvalitě
* Základ je DCT 8x8
Typy snímků:
* I (intra), nezávisí na ostatních snímcích, v podstatně JPEg snímky
* P (predicted), predikovaný, kompenzace pohybu z minulého I/P snímku
* B (bidirectional predicted), kompenzace pohybu z minulého a budoucího I/P snímku
Délka mezi I snímky se nazývá Group Of Pictures, obvykle 15-18
Makroblok: Oblast 16x16, používá motion vectors k predikci pohybu. V závislosti na typou snímku může makroblok používat různé typy predikce:
* Intra - nic, makroblok nezávisí na ostatních snímcích
* forward - kompenzace z minulého I/P snímku
* backward - kompenzace z budoucího I/P snímku
* interpolated - použijí se dva motion vektory, jeden pro minulý a jeden pro budoucí snímek. Výsledek se zprůměruje.
Kvantování DCT koeficientů:
* každý snímek může mít definovat dvě kvantovací tabulky, jedna pro Y a druhá pro chrome
* možná adaptace na úrovni makrobloku pro přesnost AC koeficientů
== 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.]]
