2D počítačová grafika, komprese obrazu a videa

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)

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'=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^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
• $ YC_bC_r $ - používán při kódování JPEG
  • $ Y = 0.3*R + 0.6*G + 0.1*B $
  • $ C_b = 0.56*(B-Y) $
  • $ 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-$ 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 $ [A, \alpha_A] $ a $ [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 $ [R\alpha, G\alpha, B\alpha, \alpha] $, při zpětném převodu se barvy jen vydělí alfa kanálem. Dva pixely se slučují jako $ [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] $.

Další operace:

• darken(A, $ \rho $) $ [R\rho, G\rho, B\rho, \alpha] $
• fade(A, $ \delta $) $ [R\delta, G\delta, B\delta, \alpha\delta] $
• opaque(A, $ \omega $) $ [R, G, , \alpha\omega] $

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) 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: $ 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 $ f^r $ co nejvíce podobala původní $ f $.

Geometrická transformace je fce $ g: R^2 -> R^2 $, která vytvoří novou obraz. fci $ f' $, pro kterou platí $ f(x,y) = f'(g(x,y)) $, resp. $ 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í $ 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)*f_0(x,y) + t * f_1(g(x,y)) $, u deformační máme pouze okrajové podmínky $ 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\limits_{i=1}^{n} p_i E_i $ bitů
• entropie zprávy je $ 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} $ bitů
• délka zprávy $ L(X) = \sum\limits_{j=1}^k d_{i_j} $ bitů
• redundance zprávy $ R(X)=L(X) - E(X) $ bitů

• Výběrová střední kvadratická odchylka $ RMS^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 = 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 $ t_i $ a rekonstrukční hodnoty $ r_i $. Pokud $ t mezi <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í $ E=E[(u-u')^2] = \int\limits{t_1}{t_{T+1}} [x - u'(x)]^2 p(x) dx $.

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} = u'_{k-1} $ (chyba je tudíž $ e_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 compensation, wen:Video compression

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..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ů

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