Rozsah látky

Seznam 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. $x=x_1,y=y_1$

  2. $dx=1;dy=\frac{y_2-y_1}{x_2,x_1}$ (předpokládáme |y_2 - y_1| < |x2-x1|)

  3. while (x<=x_2) $x_{n+1}=x_n+dx,y_{n+1}=y_n+dy$; 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 $\frac{1}{8}$ 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 - $E^{\prime }=E-\frac{dy}{dx}<=M=\frac{1}{2}$

  • Kružnice - $F(M)=M_x^2+M_y^2-R^2>0$

  • Elipsa - kreslí se po čtvrtinách, pozor, od chvíle, kdy dy=dx se posouvá v každém kroku y a ne x!!!

    • $F(M)=b^2{M}_x^2+a^2{M}_y^2-a^2{b}^2>0$

• 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

$ I(i,j) = \int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} f(x,y) h(x-i, y-j), dx dy

$ Většinou se stačí omezit na obdélníkový filtr jednotkového čtverce

$ I(i,j) = \int\limits_{i}^{i+1}\int\limits_{j}^{j+1} f(x,y), dx dy

$

Integrál lze buď spočítat analyticky nebo odhadnout numericky z několika vzorků:

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

$

• 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

• $Y{C}_b{C}_r$ - používán při kódování JPEG

  • $Y=0.3\ast R+0.6\ast G+0.1\ast B$

  • $C_b=0.56\ast (B-Y)$

  • $C_r=0.71\ast (R-Y)$

• 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 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-$N^2$) 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: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲A, \alpha_A]

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲B, \alpha_B]

. 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲R\alpha, G\alph…

, při zpětném převodu se barvy jen vydělí alfa kanálem. Dva pixely se slučují jako

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲F_A R_A + F_B R…

.

Další operace:

• darken(A, $\rho$)

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲R\rho, G\rho, B…

• fade(A, $\delta$)

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲R\delta, G\delt…

• opaque(A, $\omega$)

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲R, G, , \alpha\…

Geometrické deformace rastrových obrázků

Slajdy: Deformace rastrových obrázků a 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 $f(x,y)->R^n$ 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: $I_f(i,j)=\int \int f(x,y)d(x-i,y-j)dxdy$. Fce d je způsob, jak třeba pixelové čidlo v kameře snímá světlo, které na něj dopadá.

Zrekonstruovaný obraz: $f^r(x,y)=\sum _{i=0}^{m-1}\sum _{j=0}^{n-1}{I}_f(i,j).r(i-x,j-y)$. Chceme, aby se $f^r$ co nejvíce podobala původní $f$.

Geometrická transformace je fce $g:R^2->R^2$, která vytvoří novou obraz. fci $f^{\prime }$, pro kterou platí $f(x,y)=f^{\prime }(g(x,y))$, resp. $f^{\prime }(x,y)=f(g^{-}1(x,y))$.

Transformace s interpolací (zpětná): předpokládá, že vzorky jsou brány dirac. impulsem, pro každý pixel v cíli transformuje pomocí $g^{-}1$ 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 $g^{-}1$).

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 $X=A{x}_a+B{x}_b+C{x}_c;x_a,x_b,x_c>0;x_a+x_b+x_c=1$ (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 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 $g$ a obrazovou fci $f$. Obrazová fce v čase $t$ je snadná $f_t(x,y)=(1-t)\ast f_0(x,y)+t\ast f_1(g(x,y))$, u deformační máme pouze okrajové podmínky

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 10: g_0(x,y)=\̲[̲x,y]

a $g_1=g(x,y)$.

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

Kódování rastrových obrázku a 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 $S=x_1,x_2,...x_n$

• pst. výskytu symbolu $x_i$ je $p_i$

• kód symbolu $x_i$ má délku $d_i$

• zpráva (kódovaný řetězec) $X=x_{i_1},x_{i_2},...x_{i_k}$

• entropie (informační hodnota) symbolu $x_i$ je $E_i=-{\log }_2{p}_i$ bitů

• průměrná entropie symbolu je $AE=\sum _{i=1}^n{p}_i{E}_i$ bitů

• entropie zprávy je $E(X)=\sum _{j=0}^k{p}_{i_j}{E}_{i_j}=-\sum _{j=0}^k{p}_{i_j}lo{g}_2{p}_{i_j}$ bitů

• délka zprávy $L(X)=\sum _{j=1}^k{d}_{i_j}$ bitů

• redundance zprávy $R(X)=L(X)-E(X)$ bitů

• Výběrová střední kvadratická odchylka $RM{S}^2=\frac{1}{NM}\sum \sum (u_{i,j}-u_{i,j}^{\prime }{)}^2$ (původním obrazem vs rekonstrukce)

• Peak Signal to Noise ratio $PSNR=10lo{g}_{10}\frac{P^2}{RM{S}^2}dB$, kde P^2 je interval hodnot originálu, např 255^2

Skalární a vektorové kvantování

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 $t_i$ a rekonstrukční hodnoty $r_i$. Pokud $tmezi<t_i,t_{i+1})$, tak se použije rekonstrukční hodnota $r_i$

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

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: E=E\̲[̲(u-u')^2] = \in…

  .

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

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 $\overline{u_k^{\prime }}=u_{k-1}^{\prime }$ (chyba je tudíž $e_k=u_k-u_{k-1}^{\prime }$)

• 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

Slajdy, 20+ a 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

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

Jak funguje JPEG 2000

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%20compensation, wen:Video%20compression

Standardy JPEG a MPEG

MPEG-1; MPEG-2;

MPEG-3; MPEG-4;

Chroma subsampling

Macroblock

Pelikán - JPEG1

- Pelikán MPEG

JPEG

• DCT bloky 8x8

• kvantování - fyziologicky optimalizované tabulky

• kódování - huffman/artimetický kodek

DCT - před transformací posun z $\mathrm{0..}{2}^p-1$ do $-2^{p-1}..2^{p-1}-1$

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:%20Státnice%20Informatika%20Mgr.