2.4 Úspornost výrazu a komprese dat
Potřeba zjednodušení motivu v počítačové grafice je často dána limitovanou velikostí výsledného
souboru. Velký datový objem vede nejen k vyšším nárokům na čas zpracování a na hardware, ale
v případě webové grafiky dokáže dokonce zcela odradit od otevření nebo prohlédnutí. Snížení objemu
dat je možné nejen omezením detailů nebo rozlišení. Účinným nástrojem je také promyšlená komprese
dat a použití vhodného formátu pro jejich uložení.
Komprese dat (také komprimace dat)
je speciální postup při ukládání nebo transportu dat. Úkolem komprese dat je zmenšit datový tok
nebo zmenšit potřebu zdrojů při ukládání informací. Obecně se jedná o snahu zmenšit velikost
datových souborů, což je výhodné například pro jejich archivaci nebo při přenosu přes síť s omezenou
rychlostí (snížení doby nutné pro přenos). Komprese může být nutná při omezené datové propustnosti,
např. mobilní telefon komprimuje hovor pro přenos GSM sítí, apod.
Zvláštními postupy – kódováním, které je dané zvoleným kompresním algoritmem – se ze souboru
odstraňují redundantní (nadbytečné) informace, zvyšuje se entropie dat (pravděpodobnosti možných
stavů daného systému či soustavy). Komprese dat lze rozdělit do několika základních kategorií:
• ztrátová a bezeztrátová
• logická a fyzická
• symetrická a asymetrická
• adaptivní a neadaptivní
Ztrátová komprese – při kompresi jsou některé informace nenávratně ztraceny a nelze je zpět
rekonstruovat. Používá se tam, kde je možné ztrátu některých informací tolerovat a kde nevýhoda
určitého zkreslení je bohatě vyvážena velmi významným zmenšením souboru. Používá se pro
kompresi zvuku a obrazu (videa), při jejichž vnímání si člověk chybějících údajů nevšimne nebo si je
dokáže domyslet (do určité míry).
Tento způsob využívá například jeden z nejrozšířenějších formátů, formát JPEG. Při kompresi dat
formátu JPEG dochází k transformaci a redukci barev jednotlivých pixelů (bodů) tak, aby bylo možné
sestavit vzorky spojitých barevných signálů, se kterými pracuje tzv. diskrétní kosinová transformace.
Tyto změny barevných odstínů jsou, díky vyšší citlivosti oka na jasové rozdíly, téměř
nepostřehnutelné.
Úspěšné použití je ovšem podmíněno vhodnou volbou míry kvality komprese – k výraznější degradaci
kvality obrazu dochází při volbě vysoké míry komprese, projevující se tzv. čtverečkováním.
Na kvalitu obrázku má také vliv opakované ukládání snímku. Při opakovaném otevření a zpracování
snímku (například ve Photoshopu) je proto vhodnější volit bezeztrátový formát (PSD nebo TIFF),
s tím, že teprve konečný výsledek práce uložíme v případě potřeby jako JPEG.
Bezeztrátová komprese – obvykle není tak účinná jako ztrátová komprese dat. Velkou výhodou je, že
komprimovaný soubor lze opačným postupem rekonstruovat do původní podoby. To je nutná
podmínka při přenášení počítačových dat, výsledků měření, textu apod., kde by ztráta i jediného znaku
mohla znamenat nenávratné poškození souboru.
Jednou z možností je popsat vhodným způsobem opakující se sekvenci informací. Například namísto
popisu barvy jednotlivých bodů, z nichž se obraz v určitém místě skládá, formou „červený“,
„červený“, „červený“, „červený“, „červený“, „červený“, „modrý“, zvolíme zápis „6x červený, modrý“.
Opakující se sekvence mohou být dále uloženy do „slovníku“, čímž se délka zápisu opět zkrátí
použitím zástupných kódů. Na tomto principu je založena komprese LZW (kompresní algoritmus
32
vyvinutý Abrahamem Lempelem, Jacobem Zivem a Terry Welchem) používaná archivační programy
typu ZIP.
Logická a fyzická komprese – rozdíl mezi logickou a fyzickou komprimací spočívá v tom, zda
komprimační algoritmus při komprimaci přihlíží nebo nepřihlíží k logické informační hodnotě
komprimovaných dat.
Logická komprimace používá logické substituce (tj. sekvence znaků nahrazuje jinou, úspornější
řadou). Konkrétním příkladem jsou zkratková slova jako Čedok (nahrazující někdejší plný název
Československá dopravní kancelář) nebo Svazarm (Svaz pro spolupráci s armádou).
Fyzická komprese probíhá bez zřetele na logiku dat, se kterými se manipuluje. Vytváří se nová
sekvence znaků (bitů, bajtů atd.), jejíž vztah k původním datům lze rozpoznat výhradně s použitím
nekomprimačního algoritmu. Bez znalosti tohoto algoritmu je informační hodnota komprimovaných
dat nulová.
Symetrická a asymetrická komprese – toto rozdělení je založeno na porovnání množství práce, která
se podle algoritmu vykoná při kompresi a dekompresi dat. Pokud je doba (a tím většinou i počet
a druh operací) potřebná pro kompresi a dekompresi dat přibližně stejná jedná se o symetrickou
kompresi.
Některé algoritmy jsou však záměrně konstruovány jako asymetrické. Většina takových
komprimačních algoritmů provede větší množství operací při kompresi dat. Krátká doba
dekomprimace je výhodná například tam, kde soubor dat ukládáme na disk sice v komprimované
podobě, ale často s ním pracujeme.
Adaptivní a neadaptivní komprese – tyto algoritmy se rozlišují podle své schopnosti přizpůsobit se
charakteru dat, se kterými pracují.
Neadaptivní algoritmy jsou určeny výhradně pro komprimaci specifického druhu dat. Většinou
obsahují předdefinované slovníky nebo řetězce znaků, o kterých je známo, že jejich pravděpodobnost
výskytu v souborech dat je vysoká.
Adaptivní algoritmus je naproti tomu schopen dosáhnout určité nezávislosti na komprimovaných
datech. Takové algoritmy neobsahují žádné statické slovníky řetězců, ale budují si je pro každý
komprimovaný soubor dat znovu dynamicky v průběhu kódování.
Obecně lze říci, že adaptivní algoritmy platí za svou přizpůsobivost a větší šíři použití menší rychlostí
ve srovnání se specializovanými neadaptivními algoritmy. To však jistě nikoho nepřekvapí.
Kompresní algoritmy
Huffmanovo kódování
je algoritmus využívaný pro bezeztrátovou kompresi dat. Konvertuje znaky vstupního souboru do
bitových řetězců různé délky. Znaky, které se ve vstupním souboru vyskytují nejčastěji, jsou
konvertovány do bitových řetězců s nejkratší délkou (nejfrekventovanější znak tak může být
konvertován do jediného bitu), znaky, které se vyskytují velmi zřídka, jsou konvertovány do delších
řetězců (mohou být i delší než 8 bitů).
Nejjednodušší metoda komprese touto metodou probíhá ve dvou fázích:
a) První projde soubor a vytvoří statistiku četností každého znaku.
b) Ve druhé fázi se využije této statistiky pro vytvoření binárního stromu a k následné kompresi
vstupních dat.
33
Příklad:
Potřebujeme zkomprimovat soubor, který obsahuje pouze znaky: A, 8, K, 0, R.
Zjištěná pravděpodobnost výskytu těchto znaků je:
A – 50 %,
8 – 12,5 %
K – 6,25 %,
0 – 6,25 %,
R – 25 %.
Vytvoříme tzv. binární strom Huffmanova kódování, kde seřadíme jednotlivé znaky podle jejich
výskytu.
Obr. 37 Strom Huffmanova kódování
Dle stromu přiřadíme kódy jednotlivým znakům:
A: 0
8: 100
K: 1010
0: 1011
R: 11
Dekomprese naopak pomocí rekonstruovaného binárního stromu dekóduje řetězce proměnlivé délky.
Toto funguje bezproblémově pokud pravděpodobnosti výskytu znaků jsou mocninou 2. To se však
stane jen málokdy. Pokud jsou pravděpodobnosti jiné, pak se zaokrouhlují. Při tomto zaokrouhlování
musí být dodrženy dvě základní zásady: součet všech procentuálních hodnot musí dávat hodnotu
100% a v každém patře vytvářeného stromu může být maximálně určitý počet listů a uzlů. Tento počet
je dále omezen již vytvořenými patry stromu. Pokud se navíc stane že dva znaky mají stejnou
pravděpodobnost a nemohou být zaokrouhleny oba nahoru, pak se zkrátka jeden zvolí a jemu přiřazen
větší počet bitů než druhému.
Shanon-Fanovo kódování
je velmi podobné Huffmanovu. Rozdíl mezi oběma algoritmy spočívá v konstrukci binárního stromu.
Tvorba binárního stromu v Shanon-Fanově modifikaci je poněkud jednodušší. Lze ji shrnout do dvou
následujících kroků:
34
a) Rozděl soubor symbolů na dvě skupiny se stejnou nebo co nejpodobnější celkovou
pravděpodobností znaků obsažených v obou skupinách. První skupině se přiřadí binární
symbol nuly a druhé binární symbol jedničky.
b) Opakuj první krok na všechny dosud vytvořené skupiny, dokud každá nebude obsahovat
jediný znak.
Rozdíl mezi způsoby vytváření binárních stromů v Huffmanově a Shanon-Fanově variantě je v tom, že
Huffmanovo kódování vytváří strom od koncových listů směrem ke kořenu, zatímco Shanon-Fanova
metoda postupuje obráceně – od kořene k listům.
Příklad:
Mějme soubor se znaky s těmito pravděpodobnostmi výskytu:
A – 46%
8 – 22 %
R – 22 %
0–5%
K–5%
První skupina pak bude obsahovat pouze znak A (46%) a druhá ostatní znaky (54%). Binární strom
pak bude vypadat takto:
Obr. 38 Strom Shanon-Fanova kódování
Kódy jednotlivých znaků pak jsou následující:
A: 0
8: 100
0: 101
K: 110
R: 111
Shrnutí
Huffmanovo a Shannon-Fanovo kódování se v praxi nepoužívají samostatně, ale zpravidla
v kombinaci s nějakou slovníkovou metodou.
35
• Výhody:
velmi dobré kompresní poměry ve spojení se slovníkovou metodou
poměrně jednoduchý algoritmus dekomprese
• Nevýhody:
Huffmanovo a Shannon-Fanovo kódování je nejefektnější při hodnotách pravděpodobnosti
výskytů, jež jsou celočíselnou mocninou čísla 2.
relativně dlouhá doba komprese
36
Download

Pocitacova grafika