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.
Fyzická x Logická -- fyzická komprese probíhá na úrovni bitů, bez ohledu na informační obsah. Logická probíhá na úrovni informačního obsahu, což je člověku velmi blízké -- např. tvorba zkratek.
Ztrátová (nelze např. použít u textových dokumentů, ale u obrazu ano) x Bezztrátová

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.
Může dosahovat velkých kompresních poměrů, ale za cenu ztráty informace.
Podle toho, jakou informaci chceme ztrátově omezovat:

  • Informace o barvách
  • Informace o tvarech
  • Kombinace předchozích dvou

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.
Např. 65 65 65 66 65 65 => 03 65 01 66 02 65
Může být použita i ztrátová komprese => 06 65
Podle směru kódovacího toku: Horizontálně, Vertikálně, Úhlopříčně

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.