3.1 Komprimace dat
Data rastrového formátu nebo i vektorového formátu v přirozené podobě zabírají velké místo na paměťovém médiu. Proto vznikly různé komprimační techniky, jejichž jediným cílem je zmenšit objem dat, která jsou buď ukládána nebo přenášena (např. po počítačové nebo telekomunikační síti). |
Úvod |
Symetrické x Nesymetrické -- podle
souměrnosti času spotřebovaného na komprimaci a dekomprimaci. |
Typy komprimace |
Bezztrátová komprese Obrazy před komprimací a po dekomprimaci jsou naprosto stejné. Příklady: QUADTREE, RLE, LZW, Huffmanova |
Bezztrátová komprese |
Ztrátová komprimace
Obrazy před komprimací a po dekomprimaci nejsou naprosto
stejné, mohou se lišit.
Příklady: DCT, Fraktálová, Waveletová, Binarizace |
Ztrátová komprimace |
QUADTREE Obraz je rekurzivně dělen na čtverce, tak dlouho, dokud se nedostaneme k jednobarevným plochám. Můžeme se takto dostat až na úroveň jednotlivých pixelů. Quadtree se využívá obvykle pro obraz 1bitové barevné hloubky. |
QUADTREE |
RLE
Je účinná pro data, která obsahují opakující se prvky. Stejné znaky
(pixely stejné barvy) následující bezprostředně po sobě jsou
nahrazovány kombinací početnosti znaku a samotného znaku.U dat
s malým počtem opakování může dojít ke zvětšení velikosti. |
RLE |
LZW Jedná se o adaptivní slovníkovou metodu - je vytvářen slovník řetězců, které se již vyskytly. Data pro komprimaci jsou rozdělena do částí. Každá část se skládá z nejdelšího řetězce dosud obsaženého ve slovníku, ke kterému je připojen další znak. Takto vzniklý nový řetězec je vložen do slovníku a můžeme se na něj odkazovat pomocí indexu. Zakódovaný soubor obsahuje indexy řetězců, ze kterých se skládá původní zpráva. |
LZW |
Huffmanovo kódování Celý obrázek je podroben analýze četnosti. Odstínu barvy, který se v obrázku vyskytuje nejčastěji, je přiděleno nejkratší kódovací slovo. Druhému nejčastějšímu výskytu je přiřazeno druhé nejkratší kódovací slovo atd. Výsledkem je snížení velikosti místa potřebného k uložení grafiky. Huffmanovo kódování je používáno např. pro veškerá zařízení, která umí zasílat a přijímat fax. |
Huffmanova komprimace |
DCT Transformace DCT (Discrete Cosine Transformation) zavádí do obrazových dat redundanci, kterou lze efektivněji komprimovat. Komprimační poměr 20:1 až 30:1. Rozdělí obrázek na dílčí bloky 8x8 pixelů a vykoná jejich matematickou transformaci do frekvenční oblasti. Obrazové informace potom nejsou chápány jako 64 hodnot v matici 8x8 pixelů, ale jako proměnlivý signál, který je možno aproximovat pomocí 64 kosínových funkcí s příslušnými amplitudami. Funkcím vyšších frekvencí přidělíme nižší váhu a malé koeficienty (amplitudy) nahradíme nulami. Takto komprimované formáty často trpí Gibbsonovým jevem - zvlnění, které se objevuje okolo míst s vysokým kontrastem (v okolí hran). Obraz komprimovaný LZW (vlevo) a tentýž obraz komprimovaný DCT (vpravo) Takto je komprimován např. JPEG. |
Transformace DCT |
Fraktálová komprimace vychází z popisu chaosu přírody, který ovšem není zcela bez pravidel. Důležitým pojmem je soběpodobnost - např. máme-li dva kameny, liší se jen velikostí (obdobně větev). Záleží na dimenzi -- proměnlivost vůči změně velikosti. Fraktály: rodina matematických funkcí charakterizovaná sebepodobností a fraktálovou dimenzí. Fraktálová komprese je příkladem nesymetrické komprimace dat, pro komprimaci je potřeba daleko více času než pro dekomprimaci. Výhodou komprimace je výrazný kompresní poměr, i více než 1:100.
Např. tyto tři hvězdy na obrázku lze zapsat velmi jednoduše. Do souboru s fraktálovou komprimací se zapíše pouze ta nejmenší hvězda, její poloha v obraze, a pro další dvě hvězdy se zapíše jen poloha a poměr zvětšení resp. rotace vůči zapsané hvězdě.
Ukázka jiného fraktálu. |
Fraktálová komprimace |
Waveletová komprimace je nejmladší z technik. Je založena na principech diskrétní matematiky. Celý obraz se snaží popsat několika matematickými funkcemi, které jsou známy pod označením wavelet. Wavelety podobně jako fraktály nabízí vysokou míru komprimace a nesymetrický typ komprimace. Mezi známé zástupce formátů používající tuto komprimaci paří MrSID, ECW a JPEG 2000. |
Waveletová komprimace |
Binarizace je převod na bichromatický (dvoubarevný ) obraz. Je třeba určit práh mezi pozadím a objektem. K tomu lze použít histogram. Převod na úrovně šedé. K tomuto je možné využít známý vzorec vyjadřující vztah jednotlivých barevných složek modelu RGB a intenzity (I) vnímaného světla. I = 0,299*R + 0,587*G + 0,114*B Adaptivní vytváření 256 barevné palety je způsob, kdy se pro každý obraz zvlášť vytváří paleta. Vytváří se jen pro ty barvy, které se v obrazu skutečně vyskytují. Např. je-li obraz v truecolor a převádí se do palety, provede se analýza barev a vytvoří se paleta přesně na míru danému obrázku (paleta bude tvořit součást souboru obrázku). |
Komprimační metody založené na redukci barev |
Osobně jsem se nikdy nesetkal s tím, že by se vektorová obrazová data komprimovala jinak než jakákoliv jiná data. Obvykle se používají standardní komprimační metody jako např. ZIP, GZIP. Velmi dobře si lze představit komprimaci s využitím fraktálů a zřejmě i různých slovníků (Huffmanovo kódování). Praktickou zkušenost s těmito technikami v případě vektorové grafiky žádnou nemám. Kdybyste něco našli, tak dejte vědět, máte u mě panáka slivovice. |
Komprimace vektorových dat |
KONTROLNÍ OTÁZKA |
|
|
Ve kterém formátu (případně technologii) se využívá Hufmannovo kódování |
|
KONTROLNÍ OTÁZKA |
|
|
Popište princip fraktálové komprese obrazu |
|
KONTROLNÍ OTÁZKA |
|
|
Popište výhody a nevýhody fraktálové komprese obrazu. |
|