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

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Obsah

Rozsah látky[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

Kreslicí a ořezávací algoritmy v rovině[editovat | editovat zdroj]

Kreslení[editovat | editovat zdroj]

Kreslení čar[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Alias[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Barevné vidění[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

  • 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ů[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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ů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Přenáší se pouze některé pixely a zbylé se dopočítají.

Hierarchické a progresivní metody[editovat | editovat zdroj]

Slajdy JPEG.1

Progresivní kódování[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Jak funguje JPEG 2000

Pelikan Wavelet Lifting

Kódování koeficientů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

wen:Motion compensation, wen:Video compression

Standardy JPEG a MPEG[editovat | editovat zdroj]

MPEG-1; MPEG-2; MPEG-3; MPEG-4;

Chroma subsampling

Macroblock

Pelikán - JPEG1 - Pelikán MPEG

JPEG[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

Materiály[editovat | editovat zdroj]