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. <math>x=x_1, y=y_1</math> 2. <math>dx=1; dy=\frac{y_2 - y_1}{x_2, x_1}</math> (předpokládáme |y_2 - y_1| < |x2-x1|)
3. while (x<=x_2) <math>x_{n+1}=x_n+dx, y_{n+1}=y_n+dy</math>; PutPixel(x, round(y), color);
Kreslení čáry - Bresenhamův algoritmus
vyhody - rychlost, iba nasobenie a ščítaní, dá se implementovat bez if-ů
Kreslení kružnica - Bresenhamův algoritmus
kreslí se jen <math>\frac{1}{8}</math> kružnice (tj. while y>x) - zbytek se řeší symetrií
Odvození Bresenhamových algoritmů
Rozkreslení pixelů, jejich polovin
Určení základních vztahů pro dané tvary
Úsečka - <math>E'=E-\frac{dy}{dx}<=M=\frac{1}{2}</math>
Kružnice - <math>F(M)=M_x^2+M_y^2-R^2 > 0 </math>
Elipsa - kreslí se po čtvrtinách, pozor, od chvíle, kdy dy=dx se posouvá v každém kroku y a ne x!!!
<math> F(M)=b^2M_x^2+a^2M_y^2-a^2b^2 > 0 </math>
Odstranění zlomků, odvození inkrementů(resp. dekrementů)
Vyplňování n-úhelníka
Seznam hran, dy, dxy (změna x při změně y o 1)
Hrany orientované shora dolů, setříděné podle y, x, dxy
Udržuje se seznam aktivních hran při vyplňování
Zjednodušeně se vyplňují jen liché body
Vyplňování souvislé oblasti
Více druhů:
Hraniční
Stejné barvy (záplavové)
4-souvislé, 8-souvislé
Lépe využít frontu než zásobník - menší spotřeba paměti.
Řádkový algoritmus
Kreslení písma
Písmo zadáno dvěma různými způsoby:
Vektorově
Pomocí úseček, oblouků, kružnic,...
Snadné neprofesionální škálování
Při kreslení je nutno resterizovat
Rastrově
Zadáno v bitmapě
Snadné vykreslení pomocí BitBlt
Při vykreslování vhodné využití vzoru Flyweight. (Vektorové písmeno se převede jen jednou pro danou velikost, nechá se uloženo v cache)
Ořezávání
Ořezávání úseček - Cohen-Sutherland:
spočítá kódy pro koncové body úsečky (y>ymax, y<ymin, x>xmax, x<xmin)
podle kódu:
AND není nula -> mimo obraz,
OR je nula -> oba uprostřed,
jinak řezám podle kódů
ořezávání: Cyrus-Beck
Okno je konvexní n-úhelník
řežeme přímku P(t) = A +t * (B-A)
každá hrana okna má normálu, která směřuje ven.
tmin = 0; tmax=1
dokud tmin < tmax, opakuj pro každou hraniční přímku
Pokud N dot (B-A) = 0, je úsečka rovnoběžná s hraniční přímkou, rozhodni na které straně
Jinak spočítat průsečík úsečky s přímkou a upravit tmin nebo tmax
Ling-Barsky
efektivní úrava Cyrus-Beck pro obdélníkové okno
Ořezávání n-úhelníků:
Pokud chceme jen hrany, stačí řezat jednotlivé úsečky
Pokud chceme vybravovat, musíme oříznout speciálně
Proudové ořezávání (Sutherland-Hodgman):
Ořezává podle jedné hranice obdélníkového okna, pro zbylé hranice se souřadnice otáčejí o 90 stupnu
alg si pamatuje poslední 2 vrcholy (Last a Actual) a v závislosti na tom, na které straně hranice jsou vydává nové vrcholy n-úhelníka:
L i A jsou uvnitř -> Output(A)
L uvnitř, A venku -> Output(průsečík s hranicí)
L i A venku -> nic
L venku, A uvnitř -> Output(průsečík s hranicí), Output(A)
Anti-aliasing
Alias
Alias vzniká při rekonstrukci vzorkovaného singálu. Jedná se o dodatečnou (nežádanou) nízkofrekvenční informaci, která vzniká ve dvou případech:
1. Pokud je původní funkce frekvenčně neomezená - neexistuje maximální frekvence. => při diskrétním zobrazení spojité funkce nikdy nedostaneme přesnou reprezentaci.
2. Pokud je původní funkce frekvenčně omezená, tj. pokud existuje v jejím Fourierovském spektru maximální frekvence fmax. Pokud se taková funkce vzorkuje s frekvencí menší než tzv. Nyquistův limit -> fnyq = 2*fmax, vzniká alias.
Typický příklad - vykreslování šachovnice.
Antialiasing
Problém aliasu se typicky řeší zvýšením prostorového rozlišení na úkor barevného - použitím více odstínů té samé barvy. Pixely i kreslené útvary jsou plošné objekty => pixely rozsvítím s intenzitou úměrnou jejich pokrytí.
Provádí se pomocí supersamplingu - převzorkováním na vyšší rozlišení a následným průměrováním hodnot. Nevýhodou je ztráta informace u vysokofrekvenčních částí - ostré hrany se rozmažou.
Vyhlazování pomocí integrace - obraz. fce f(x,y), vyhlazovací filtr h(x,y): Intenzita pixelu i,j je
<math> I(i,j) = \int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} f(x,y) h(x-i, y-j)\, dx dy
</math> Většinou se stačí omezit na obdélníkový filtr jednotkového čtverce
<math> I(i,j) = \int\limits_{i}^{i+1}\int\limits_{j}^{j+1} f(x,y)\, dx dy
</math>
Integrál lze buď spočítat analyticky nebo odhadnout numericky z několika vzorků:
<math> I(i,j) = \frac{\displaystyle \sum_{k} f(x_k,y_k) h (x_k,y_k)}{\displaystyle \sum_{k} h(x_k,y_k)}
</math> . Poznámka: Tady by IMO mělo být h(x_k-i, y_k-j), ve slajdech je tohle.
Pravidelné vzorkování - jen přenese problém o řád dál
Stochastické vzorkování - problém se řeší umělým přidáním šumu
Poison disc
Jittering (roztřesení)
N-věží
Adaptivní zjemňování: vzorkujeme podle důležistosti, nejprve několik vzorků a pokud je mezi nimi přiliš veliký rozdíl, zjemni vzrokování v dané podoblasti.
Barevné vidění a barevné systémy, reprodukce barevné grafiky
Barevné vidění
oko - rohovka, duhovka, panenka, čočka, sklivec, sítnice. Žlutá skvrna
Tyčinky - intenzita světla - vnímání kontrastů, vidění za šera, v oku cca 120e6
Čípky - tři typy (r, g, b) - vnímání barev, soustředěny ve žluté skvrně, v oku cca 8e6
Barevné systémy
RGB
CMY(K) = 1 - RGB
HSV (barvy na šestibokém jehlanu), HLS (barvy na dvou kuželech)
převod není prosté zobrazení, používá se algoritmus. viz Pelikánovy slidy
<math>YC_bC_r</math> - používán při kódování JPEG
<math>Y = 0.3*R + 0.6*G + 0.1*B</math>
<math>C_b = 0.56*(B-Y)</math>
<math>C_r = 0.71*(R-Y)</math>
různé barevné palety s různými počty barev
Konstrukce adaptované palety
Paleta se může adaptovat pro daný obrázek (např. v GIFu). Metody:
shora dolů
množinu použitých barev dělím tak dlouho, dokud nedostanu požadovaný počet
zdola nahoru
sdružuji příbuzné barvy
metoda shlukové analýzy
využívá se histogram
Heckbertova metoda
opět histogram
dělí se nejdelší vážená hrana kvádru v místě těžiště
Reprodukce barevné grafiky
Pokud někdo tušíte, co spadá pod tuhle otázku, prosím doplňte. Slajdy Pelikána Zobrazování barev
Rozptylování a půltónování
Napodobení vjemu neexistujících barevných odstínů pro dané zařízení. Zvyšuji barevné rozlišení na úkor prostorového.
Rozptylování
zobrazuje se bez zvětšení rozlišení (1:1)
Půltónování
zobrazuje se se zvětšeným rastrovým rozlišením (1:N)
Typické příklady:
černobílé tiskárny
displaye s malou paletou barev
obrázky s omezenou paletou
Půltónování
Jeden zdrojový pixel (rozsah hodnot 0-<math>N^2</math>) nakreslím jako čtverec NxN
Inkrementální rastry
odstín hodnoty k obsahuje právě k černých teček
lze uložit do matice
Pravidelný rastr
Tečkový rastr
Nutno předcházet pravidelnosti a aliasu - rastry se často otáčejí
Rozptylování
Maticové rozptylování
libovolná půltónovací matice
nejčastěji matice pravidelného rastru
několik sousedních pixelů sdílí jednu matici
ztráta drobných detailů
zvýraznění vedlejších odstínů
Náhodné rozptylování
pro lidské oko mnohem přirozenější
černobílé obrázky příliš zašumělé - lepší výsledky u více výstupních odstínů
Distribuce chyby
zaokrouhlím hodnotu pixelu na nejbližší zobrazitelnou
rozdíl distribuuji mezi sousední pixely
různé způsoby distribuce
je třeba pomocný buffer
výhody
příjemné pro oko
dobrá kvalita
nevýhody
nutnost kreslit po řádkách
nemožnost vrátit ze zpátky
pomalé
Kompozice poloprůhledných obrázků
Slajdy: Kompozice rastrových obrázků Druhy kompozice:
montáž
prolínání
syntéza
Alfa: procentuální pokrytí pixelu barvou (0-prhledné, 1-neprůhledné)
Skládání dvou pixelů: Mám pixel <math>[A, \alpha_A]</math> a <math>[B, \alpha_B]</math>. V realitě se mohou různě překrývat, ale mám pouze číslo alfa. Model pokrytí pixelu, kde je pixel pokryt barvou A s s rovnoměrně rozloženou pstí alfa_A. Nezáleží tak na skutečném tvaru a vyhovuje ve většině případů. Překrývání dvou pixelů v realitě má 4 oblastí:
Oblast bez A i bez B
Oblast pouze s A
Oblast pouze s B
Oblast s A i B
V závislosti na způsobu překryvu je 12 možností, jak je zkombinovat
Clear - nepoužijenic, F_A i F_B jsou 0
A - pouze A, F_A=1, F_B=0
B - pouze B, F_A=0, F_B=1
A přes B, F_A=1, F_B=1-alpha_A
B přes A, F_A=1-alpha_B, F_B=1
A v B, F_A=alpha_B, F_B=0
B v A, F_A=0, F_B=alpha_A
A mimo B
B mimo A
A na povrchu B
B na porvrchu A
A xor B
F_A a F_B je kolik procent plochy, která by měla mít barvu A/B se má použít při směsi (ne poměr na vělikost pixelu, ale na plochu A/B pixelu).
Čtveřice RGBa se ukládají jako <math>[R\alpha, G\alpha, B\alpha, \alpha]</math>, při zpětném převodu se barvy jen vydělí alfa kanálem. Dva pixely se slučují jako <math>[F_A R_A + F_B R_B; F_A G_A + F_B G_B; F_A B_A + F_B B_B; F_A \alpha_A + F_B \alpha_B]</math>.
Další operace:
darken(A, <math>\rho</math>) <math>[R\rho, G\rho, B\rho, \alpha]</math>
fade(A, <math>\delta</math>) <math>[R\delta, G\delta, B\delta, \alpha\delta]</math>
opaque(A, <math>\omega</math>) <math>[R, G, , \alpha\omega]</math>
Geometrické deformace rastrových obrázků
Slajdy: 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 <math>f(x,y) -> R^n</math> mapující polohu v rovině na atributy (barva, průhlednost...). Obrazová fci typicky nemáme, máme pouze diskrétní rastrový obraz I digitalizovaný pomocí filtru d: <math>I_f(i,j) = \int\int f(x,y) d(x-i, y-j) dx dy</math>. Fce d je způsob, jak třeba pixelové čidlo v kameře snímá světlo, které na něj dopadá.
Zrekonstruovaný obraz: <math>f^r(x,y) = \sum\limits_{i=0}^{m-1}\sum\limits_{j=0}^{n-1} I_f(i,j) . r(i-x, j-y)</math>. Chceme, aby se <math>f^r</math> co nejvíce podobala původní <math>f</math>.
Geometrická transformace je fce <math>g: R^2 -> R^2</math>, která vytvoří novou obraz. fci <math>f'</math>, pro kterou platí <math>f(x,y) = f'(g(x,y))</math>, resp. <math>f'(x,y)=f(g^-1(x,y))</math>.
Transformace s interpolací (zpětná): předpokládá, že vzorky jsou brány dirac. impulsem, pro každý pixel v cíli transformuje pomocí <math>g^-1</math> do zdrojových souřadnic a tam interpoluje (bilin/bicub).
Transformace s filtrací (dopředná): odpovídá představě plošného pixelu, digitalizační filtr s nenulovou plochou. Zdrojové pixely se přenášejí do výsledného obrázku (není potřeba <math>g^-1</math>).
Vícekrokové transformace: místo jedné 2D transformace se použije více 1D transformací, transformují se pouze řádky/sloupce. Je to rychlejší, ale možnost ztráty přesnosti mezivýsledku.
Deformace
Zadávání deformační fce:
explicitní analytická fce, např. mapování na kouli
funkce zadávané po částech, typicky uživatelem, změny mají jen lokální charackter
Deformace v trojúhelníkové síti: Máme síť trojúhelníků a její vrcholy měníme -> topologie zůstává stejná. Barycentrické souřadnice bodu X v trojúhelníku <math>X = A x_a + B x_b + C x_c; x_a, x_b, x_c > 0; x_a + x_b +x_c = 1</math> (bod v trojúhelníku je A + alfa * (B-A) + beta * (C-A); alfa + beta = 1 a > 0). Algoritmus: procházím cílový obrázek řádkovým rozkladem, uvnitř každého trojůhelníku se souřadnice mění lineárně -> diferenční alg. Problémy: nespojitosti 1 řádu ( čára přes 2 trojůhelníky nezůstává čárou, nespojitá 1 derivace).
Aproximace vyšších řádů:
kvadratická / kubická - spojité první nebo druhé derivace
troj/čtyřpúhelníková topologie (je potřeba znát i okolní buňky)
inverzní zobrazení obtížné
Feature-based warping:
Lokální zadávání deformační fce - uživat. příjemné, není potřeba zadávat nepokryté oblasti
Do zdroj. a cíl. obrázku se umisťují páry orientovaných úseček
Pokud 1 šipka, afinní tranformace, pokud více, radiální tranformace
Morphing
Slajdy Morphing
Metamorfóza obrázku, transformace mezi dvěma obrázku (obrys pes->kočka), geom. deformace obrázku případně změna obrazové fce z jednoho na jiný obrázek.
Morphing je postupný, máme počátek (čas t=0) a konec (čas t=1), ale je potřeba nějak interpolovat deformační fci <math>g</math> a obrazovou fci <math>f</math>. Obrazová fce v čase <math>t</math> je snadná <math>f_t(x,y) = (1-t)*f_0(x,y) + t * f_1(g(x,y))</math>, u deformační máme pouze okrajové podmínky <math>g_0(x,y)=[x,y]</math> a <math>g_1 = g(x,y)</math>.
Interpolace deformační fce jsou různé:
deformace zadáné sítí - interpolují se jednotlivé body sítě
deformace zadané soustavou šipek - lin. interpolace šipek
deformace mnohoúhelníků v rovině - přechodová fce minimalizující vynaloženou práci
Metamorfóza mnohoúhelníků
Pokud mají mnohoúhelníky stejný počet vrcholů, lze použít lin. interpolaci vrcholů, případně lin. interpolaci úhlů vrcholů + délky hran.
Dále exituje model založený na minimalizaci deformační práce, založené na modelu drátu (natahovací/ohýbací práce).
Základní principy komprese rastrové 2D grafiky
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 <math>S = {x_1, x_2,...x_n}</math>
pst. výskytu symbolu <math>x_i</math> je <math>p_i</math>
kód symbolu <math>x_i</math> má délku <math>d_i</math>
zpráva (kódovaný řetězec) <math>X = x_{i_1}, x_{i_2},...x_{i_k}</math>
entropie (informační hodnota) symbolu <math>x_i</math> je <math>E_i=- \log_2 p_i</math> bitů
průměrná entropie symbolu je <math>AE = \sum\limits_{i=1}^{n} p_i E_i</math> bitů
entropie zprávy je <math>E(X) = \sum\limits_{j=0}^{k} p_{i_j} E_{i_j} = - \sum\limits_{j=0}^{k} p_{i_j} log_2 p_{i_j}</math> bitů
délka zprávy <math>L(X) = \sum\limits_{j=1}^k d_{i_j}</math> bitů
redundance zprávy <math>R(X)=L(X) - E(X)</math> bitů
Výběrová střední kvadratická odchylka <math>RMS^2 = \frac{1}{NM} \sum \sum (u_{i,j} - u'_{i,j})^2</math> (původním obrazem vs rekonstrukce)
Peak Signal to Noise ratio <math>PSNR = 10 log_{10} \frac{P^2}{RMS^2} dB</math>, kde P^2 je interval hodnot originálu, např 255^2
Skalární a vektorové kvantování
Pulzní kódová modulace
Přenos analogového signálu digitálním kanálem, signál se vzorkuje v čase a kvatizuje a pak kóduje (moduluje)
Kvantování: vezmu spojitý signál a přiřadím mu přihrádku. Mám rozhodovací hodnoty <math>t_i</math> a rekonstrukční hodnoty <math>r_i</math>. Pokud <math>t mezi <t_i, t_{i+1})</math>, tak se použije rekonstrukční hodnota <math>r_i</math>
lineární kvantovač - používá se roznoměrné rozdělení (rekonstrukční hodnota uprostřed intervalu rozhodovacích hodnot)
Lloydův-Maxův kvantovač - minimalizuje střední kvadratickou chybu kvantování <math>E=E[(u-u')^2] = \int\limits{t_1}{t_{T+1}} [x - u'(x)]^2 p(x) dx</math>.
Vektorové kvantování: Kvantuje se celý vektor najednou podle určené kvantovací tabulky. Různé rozhodovací hodnoty pro různé koeficienty vektoru, např u JPEG je blok 8x8 s největší hodnotou vlevo nahoře, to se použije pro zig-zag.
Zónální kvantování: vektorové kvantování, přenáší se jen jistá část vektoru. Zbylé části se ignorují. Prahové kódování koeficientů: přenáší se pouze K koeficientů s nevětší amplitudou.
Prediktivní kvantování: kvantovač nekvantuje hodnotu, ale chybu. Chyba je spočítána jako hodnota signálu - predikce hodnoty signálu, která je spočítána z minulých hodnot.
Prediktivní komprese
Využívají závislost sousedních pixelů. V implementaci se používá predikční fce, která podle minulých hodnot co nejlépe odhadne současnoun hodnotu. Kóduje se pouze rozdíl mezi predikované hodnoty a skutečné hodnoty. Při úspěšné predikci má chyba menší amplitudu.
DPCM
Digital pulse-code modulation - kvantuje se chyba mezi predikovanou hodnotou a skutečnou hodnotou.
Kodér
Dekodér
Různé prediktory, nelineární, 2D/3D
Delta modulace
Kvantovač má pouze 2 výstupní hodnoty +q a -q
Prediktor je zpožďovací fce, která predikuje <math>\overline{u'_k} = u'_{k-1}</math> (chyba je tudíž <math>e_k = u_k - u'_{k-1}</math>)
vstupní fce nemusí být vzrokovaná, v takovém případě se používá integrátor
Převážně pro analogové signály, zvuk atd.
Může zrnit, v takovém případě třístavová kvantizační fce +q, 0, -q
Adaptivní predikční metody
Několik různých prediktorů pro různé směry, vybírá s max korelací
adaptivní kvantovač chyby, podle rozptylu predikční chyby
klasifikace oblastí podle lokálního okolí pixelu, např. rozdělit obraz do několika bloků 16x16
Transformační kompresní metody
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
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
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
JPEG
DCT bloky 8x8
kvantování - fyziologicky optimalizované tabulky
kódování - huffman/artimetický kodek
DCT - před transformací posun z <math>0..2^p - 1</math> do <math>-2^{p-1} .. 2^{p-1} -1</math>
Spočítané DCT koeficienty se kvantují, přesnost koeficientů závisí na jejich důležitosti pro vizuální vjem. Používají se lineární kvantovače, hodnota DCT koeficientu se vydělí hodnotou v kvantovací tabulce.
Kódování kvnatovaných koeficientů: F(0,0) je odlišný, používá se predikce z minulých bloků, přenáší se jen rozdíl. Zbylé koeficienty jsou zig-zag uspořádány, pak RLE a zakódovány pomocí VLI. Výsledek se zakóduje pomocí huffmana nebo artimentického kódéru.
Bezeztrátová varianta JPEG založena na prediktivním kodéru (DCT není vhodné). K dispozici 7 různých prediktorů 1D/2D. Chyby predikce reprezentovány pomocí VLI a huffman.
JPEG může mít až 255 složek, jednotlivé složky mohou mít různé rozlišení.
Progresivní režim: spektrání/postupná aproximace
Hierarchický režim: Postupně se přenáší obrázek ve stále lepším rozlišení. Pouze chyba je přenášena.
MPEG
Kompenzace pohybu, makrobloky 16x16
Různé vzrokovací schémata, barvevné složky se mohou přenášev v různé časové/prostorové kvalitě
Základ je DCT 8x8
Typy snímků:
I (intra), nezávisí na ostatních snímcích, v podstatně JPEg snímky
P (predicted), predikovaný, kompenzace pohybu z minulého I/P snímku
B (bidirectional predicted), kompenzace pohybu z minulého a budoucího I/P snímku
Délka mezi I snímky se nazývá Group Of Pictures, obvykle 15-18
Makroblok: Oblast 16x16, používá motion vectors k predikci pohybu. V závislosti na typou snímku může makroblok používat různé typy predikce:
Intra - nic, makroblok nezávisí na ostatních snímcích
forward - kompenzace z minulého I/P snímku
backward - kompenzace z budoucího I/P snímku
interpolated - použijí se dva motion vektory, jeden pro minulý a jeden pro budoucí snímek. Výsledek se zprůměruje.
Kvantování DCT koeficientů:
každý snímek může mít definovat dvě kvantovací tabulky, jedna pro Y a druhá pro chrome
možná adaptace na úrovni makrobloku pro přesnost AC koeficientů
Snímání obrazu v digitální fotografii
Materiály
Počítačová grafika I – stránka předmětu
Pokročilá 2D počítačová grafika – stránka předmětu
Speciální funkce a transformace ve zpracování obrazu – stránka předmětu
{{Stub}} Category: Státnice Informatika Mgr.