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=x1,y=y1x=x_1, y=y_1

    2. dx=1;dy=y2y1x2,x1dx=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) xn+1=xn+dx,yn+1=yn+dyx_{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 18\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=Edydx<=M=12E'=E-\frac{dy}{dx}<=M=\frac{1}{2}

    • Kružnice - F(M)=Mx2+My2R2>0F(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)=b2Mx2+a2My2a2b2>0 F(M)=b^2M_x^2+a^2M_y^2-a^2b^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

  • YCbCrYC_bC_r - používán při kódování JPEG

    • Y=0.3R+0.6G+0.1BY = 0.3*R + 0.6*G + 0.1*B

    • Cb=0.56(BY)C_b = 0.56*(B-Y)

    • Cr=0.71(RY)C_r = 0.71*(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-N2N^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)>Rnf(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: If(i,j)=f(x,y)d(xi,yj)dxdyI_f(i,j) = \int\int f(x,y) d(x-i, y-j) dx dy. Fce d je způsob, jak třeba pixelové čidlo v kameře snímá světlo, které na něj dopadá.

Zrekonstruovaný obraz: fr(x,y)=i=0m1j=0n1If(i,j).r(ix,jy)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). Chceme, aby se frf^r co nejvíce podobala původní ff.

Geometrická transformace je fce g:R2>R2g: R^2 -> R^2, která vytvoří novou obraz. fci ff', pro kterou platí f(x,y)=f(g(x,y))f(x,y) = f'(g(x,y)), resp. f(x,y)=f(g1(x,y))f'(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í g1g^-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 g1g^-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=Axa+Bxb+Cxc;xa,xb,xc>0;xa+xb+xc=1X = 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 gg a obrazovou fci ff. Obrazová fce v čase tt je snadná ft(x,y)=(1t)f0(x,y)+tf1(g(x,y))f_t(x,y) = (1-t)*f_0(x,y) + t * 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 g1=g(x,y)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=x1,x2,...xnS = {x_1, x_2,...x_n}

  • pst. výskytu symbolu xix_i je pip_i

  • kód symbolu xix_i má délku did_i

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

  • entropie (informační hodnota) symbolu xix_i je Ei=log2piE_i=- \log_2 p_i bitů

  • průměrná entropie symbolu je AE=i=1npiEiAE = \sum\limits_{i=1}^{n} p_i E_i bitů

  • entropie zprávy je E(X)=j=0kpijEij=j=0kpijlog2pijE(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} bitů

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

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

  • Výběrová střední kvadratická odchylka RMS2=1NM(ui,jui,j)2RMS^2 = \frac{1}{NM} \sum \sum (u_{i,j} - u'_{i,j})^2 (původním obrazem vs rekonstrukce)

  • Peak Signal to Noise ratio PSNR=10log10P2RMS2dBPSNR = 10 log_{10} \frac{P^2}{RMS^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 tit_i a rekonstrukční hodnoty rir_i. Pokud tmezi<ti,ti+1)t mezi <t_i, t_{i+1}), tak se použije rekonstrukční hodnota rir_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 uk=uk1\overline{u'_k} = u'_{k-1} (chyba je tudíž ek=ukuk1e_k = u_k - u'_{k-1})

  • 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 0..2p10..2^p - 1 do 2p1..2p11-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

{{Stub}} Category:%20Státnice%20Informatika%20Mgr.