Komprese

1. Komprese

Komprese je proces, při němž je vytvořen obraz původního souboru. Synonymem slova komprimace, zabalení.

Snaha o co nejlepší využití datových nosičů a snaha o co nejlepší využití přenosových kanálů.

• Při přenosu zkomprimovaného souboru má rušení závažné důsledky.
• Nerovnoměrné kódy.
  
• Prakticky se mohou kompresní algoritmy chovat heuristicky.
  

1.1. Vlastnosti komprese

Úspěšnost komprese může být dána:

• Kompresní poměr– podíl délky zkomprimovaného souboru k délce původního souboru. 
• Kompresní faktor – převrácená hodnota předchozího.
  
• Kompresní zisk – stonásobek přirozeného logaritmu z kompresního faktoru.

Bpc (Bits per character) či BPB (Bits Per Byte):

• Poměr počtu bitů ve zkomprimovaném souboru ku počtu symbolů (bytů) v původním souboru.

Kompresní algoritmy se testují na referenčních vzorcích daných např.
Canterbury Corpusem.

Podle poměru časové náročnosti komprese a dekomprese dělíme kompresní algoritmy na:

• symetrické,
• asymetrické.

• adaptivní,
  
• neadaptivní.
  

2. Bezeztrátová komprese

Při dekompresi je původní soubor zcela obnoven, žádná informace se neztrácí.

2.1. RLE

Run Length Encoding – kódování proudů.

• Proud – blok opakujících se symbolů ve vstupním souboru.
• Proudy se hledají procházením po řádcích, sloupcích, dlaždicích či cik-cak.
• 
  Použití např. u obrázků s malým počtem barev.

• První bit prvního bytu určuje, zda se jedná o záznam proudu opakujícího se bytu (1), či bloku neopakujících se bytů (0).
  
• Zbývajících sedm bitů prvního bytu určuje délku proudu opakujícího se následujícího bytu, nebo délku bloku následujících neopakujících se bytů.

• 65₁₀ 65₁₀ 65₁₀ 65₁₀ 65₁₀= 10000101₂ 01000001₂
  
• 72₁₀ 65₁₀= 00000010₂ 01001000₂ 01000001₂

2.2. PCX

Modifikace předchozího.

• Pro obrázky s paletou barev, kde jsou velké stejnobarevné plochy.
  

Typ bytu je určován podle hodnoty a závisí na tom, zda je nastaven na 1 určitý počet prvních bitů.

• Pokud ano, následující byte se opakuje.
• Pokud ne, v bytu je již kód barvy.
  

• Počítadlo nastaveno na C016 = 11000000₂.
  
• C1₁₆ CC₁₆ C5₁₆ FE₁₆ 18₁₆ AF₁₆ = 11000001₂ 11001100₂ 11000101₂ 11111110₂ 00010100₂ 10101111₂ = CC₁₆ FE₁₆ FE₁₆ FE₁₆ FE₁₆ FE₁₆ 18₁₆ AF₁₆
  

2.3. Cvičení k proudové kompresi

1. Původní soubor obsahuje řetězec znaků FFFFIIIIIIILIPPPPP. Dle ISO 8859-2 v desítkové soustavě (70 70 70 70 73 73 73 73 73 73 73 76 73 80 80 80 80 80)₁₀. Proveďte kompresu RLE.
2. Při kompresi PCX bylo počítadlo bytů nastavené např. na C0₁₆. Po kompresi jsme získali soubor: (C5 AB 45 CE ED C1 DE)₁₆. Proveďte dekompresi.

Tipy pro řešení

Podívejte se do předchozích studijních kapitol a dejte si pozor na to, zda máte dělat kompresi nebo dekompresi a o kterou metodu jde.

Návrh řešení

Návrh řešení si prohlédněte, až se pokusíte najít vlastní odpovědi.

 1. Proveďte kompresu RLE (70 70 70 70 73 73 73 73 73 73 73 76 73 80 80 80 80 80)₁₀.

 2. Proveďte dekompresi PCX při počítadlu C0₁₆: (C5 AB 45 CE ED C1 DE)₁₆.

2.4. LZ slovníkové komprese

Třída algoritmů pojmenovaná po tvůrcích původního z roku 1977.

• Lempel a Ziv.

Využívá se tzv. „posuvného okna“ rozděleného na prohledávané pole
a komprimované pole.
Jedna z prvních verzí se např. i dnes využívá u formátu PNG, další pak v ARJ, ZIP, RAR...

LZ77

Do výstupního souboru se zapisují trojice:

• Pozice kopírované sekvence z prohledávaného pole.
  
• Délka sekvence.
  
• Následující symbol.

Délka prohledávaného pole se pohybuje v kilobytech, délka komprimovaného pole spíše v B.

LZ78

Prohledávané pole nahrazeno dynamickým slovníkem opakujících se řetězců.

Ve zkomprimovaném souboru dvojice: 

• Ukazatel (většinou 12bitový) do slovníku již dříve nalezených řetězců.
  
• Bezprostředně následující symbol.
  

LZW

Modifikace navržená Welchem.

Nejprve se inicializuje slovník a není třeba posléze používat dvojice (stačí odkazy do slovníku). Slovník není součástí zkomprimovaného souboru. Využití např. u grafického formátu GIF.

2.5. Aritmetické kódování

J. J. Risanen v roce 1976.

Vstupní soubor je převeden na
číslo z intervalu <0;1).

Je třeba znát pravděpodobnost výskytu znaků ve vstupním souboru.

• Řadíme od nejmenší po největší.

Z pravděpodobností výskytu jednotlivých prvků se vytvoří na intervalu <0;1) podintervaly, které ho vyplní.

• Pole mez_d obsahuje dolní meze podintervalů.
  
• Pole mez_h obsahuje horní meze podintervalů.
  
• Součást vstupního i výstupního souboru (+ počet znaků).

Komprese

• Základní inicializace – h = 1; d = 0; s = 1.
  
• Cyklus postupně pro jednotlivé znaky:
  • h := d + s · mez_h(aktuálního symbolu)
  • d := d + s · mez_d(aktuálního symbolu)
  • s := h - d
  
• Po provedení cyklu pro poslední znak vybereme reprezentanta K z aktuálního intervalu (d; h).

Dekomprese

Označíme K jako K₁ a podle intervalu, do něhož patří, dekomprimujeme první znak

Další znaky dekomprimujeme postupně na základě obecného vzorce pro ítého
reprezentanta: (K_i-1 - mez_di-1) / s_i-1

2.6. Cvičení k aritmetické kompresi

1. Proveďte kompresi zprávy BAR aritmetickým kódováním, když víte, že pravděpodobnost výskytu znaků: A = 69 %, B = 13 %, R = 18 %.
2. Proveďte dekompresi aritmetickým kódováním, když víte, že pravděpodobnost výskytu znaků je: A = 69 %, B = 13 %, R = 18 %, reprezentant K = 0,06 a původní soubor obsahoval tři znaky.

Tipy pro řešení

Podívejte se do předchozí studijní kapitoly. Vyzkoušet si můžete výpočet dle vzorce, nebo přímé dělení intervalu.

Návrh řešení

Návrh řešení si prohlédněte, až se pokusíte najít vlastní odpovědi.

 1. Proveďte kompresi zprávy BAR aritmetickým kódováním, když víte, že pravděpodobnost výskytu znaků: A = 69 %, B = 13 %, R = 18 %.

 1. Proveďte dekompresi aritmetickým kódováním, když víte, že pravděpodobnost výskytu znaků: A = 69 %, B = 13 %, R = 18 %, K = 0,06 a zpráva měla 3 znaky.

2.7. Shrnutí

Zdroje

• JIROUŠEK, R. a kol. Principy digitální komunikace. Voznice: Leda, 2006. 309 s.
  ISBN 80-7335-084-X
• SNÁŠEL, V., DVORSKÝ, J. Algoritmická matematika I. Olomouc : Univerzita
  Palackého, 1999. 256 s. ISBN 80-244-0013-8
  

3. Typové příklady ke třetímu testu z bezeztrátové komprese

1. Podle algoritmu RLE dekomprimujte sekvenci hezadecimálně zapsaných bytů 8B 5A 88 4E 01 41 87 4C 03 20 5A 4E 89 41 84 4B 89 59 a spočtěte kompresní poměr.
2. Pomocí metody PCX zkomprimujte sekvenci bytů zapsaných v hexadecimální soustavě C4 33 33 33 54 7E 7E 7E 7E 7E 7E 7E C6 A2 4A 4A 4A 4A 4A A4 A4, když je počítadlo bytů nastaveno na C0₁₆ a zjistěte kompresní poměr.
3. Pravděpodobnost výskytu znaků je: K = 12 %, Č = 23 %, Í = 35 %, O = 30 %. Zkomprimujte zprávu KOČÍ pomocí aritmetického kódování.
4. Pravděpodobnost výskytu znaků je: B = 12 %, O = 30 %, K = 23 % a A = 35 %. Proveďte dekompresi, když víte, že zpráva před použitím aritmetického kódování měla 7 znaků a znáte reprezentanta K = 0,313.

Tipy pro řešení

Podívejte se do odpovídajících předchozích studijních kapitol a cvičení. Nezapomeňte na to, v jaké soustavě jsou byty zapsány.

Pokud se rozhodnete pro řešení v MS Excel, můžete s výhodou využít funkce KDYŽ(), CONCAT(), funkce pro převody mezi soustavami a dále si pomůžete správnou adresací.

Návrh řešení

Postup řešení tentokrát cíleně nenabízíme, abyste nebyli neustále zbytečně ovlivňováni. Pokud byste si zvoleným postupem nebyli jisti, samozřejmě kontaktujte vyučujícího (tutora). Po kliknutí zjistíte pro kontrolu alespoň výsledky, ale podívejte se na ně, až po pokusu o vlastní řešení.

4. Ztrátová komprese

Ztrátové kompresní algoritmy při kompresi vynechávají informace, které lze zanedbat a obnovený soubor po dekompresi neodpovídá zcela původnímu.

• Týká se především komprimování zvuku a obrazu.
  
• Ztrátu informace lze regulovat nastavením parametrů použitého kompresního algoritmu.

4.1. Východiska ke ztrátové kompresi

Akustický či obrazový signál se z analogové (spojité) formy převádí do digitální (diskrétní) podoby.

• Nejprve vzniká vzorkováním spojitý signál v diskrétním čase.
  
• Kvantováním vzniká diskrétní signál v diskrétním čase.
• Výsledkem je datový soubor.

Výhody digitálního uložení

• Lze se vyhnout zkreslení při přenosu využitím bezpečnostního kódování.
  
• Možnost vytváření identických kopií.
  
• Přizpůsobení pro přenos digitálními kanály.
  
• Možnost aplikace šifrovacích algoritmů.
  

4.2. Vlastnosti ztrátové komprese

• Kódování dat, které není jednoznačné.
  
• Omezuje redundanci a odstraňuje irelevanci.
  
• Její algoritmy jsou specifické pro různé druhy dat. 
  
• Je tedy třeba vědět, jak jsou data interpretována.

Míry ztrátovosti vyjadřují, k jakým ztrátám při kompresi dochází a udává se v dB.

• 
  MSE – Mean Square Error – Střední kvadratická chyba využívaná v dalších dvou vzorcích.
• 
  SNR – Signal-to-Noise Ratio – Poměr signálu k šumu.
• 
  PSNR – Peak Signal-to-Noise Ratio.

4.3. Prediktivní metody

Snaha o předpovědění následující hodnoty signálu na základě
hodnoty předcházející. Uložen je rozdíl mezi predikcí a skutečností.

• (A)DPCM – diferenční pulsní kódová modulace, v některé verzi může být i adaptivní. 
• Delta modulace – většina vzorků kódována jedním bitem. Nevýhodou možné přetížení sklonu a zrnitost.

Oboustranná predikce – vybere se každý i. vzorek a tyto vzorky jsou použity k predikci ostatních hodnot. 

Prostorová korelace – predikci každého dalšího pixelu mohou určovat okolní pixely.

4.4. Hierarchické metody

Soustavný rozklad obrazu, dokud se neskládá z triviálních prvků,
které lze kódovat jediným symbolem.

• Kvadrantový strom(quadtree)

4.5. Komprese zvuku

Vzorkové rozlišení

• Počet bitů.

Vzorkovací frekvence

• Počet vzorků za sekundu.

Vzorkovací stopy

• Počet kanálů

Lidské ucho:

• Je různě citlivé na různé frekvence.
  
• Vnímá vzájemný vliv současně znějících tónů tak, že při blízkých frekvencích musí mít druhý tón podstatně vyšší hlasitost (maskovací efekt).
  
• Nevnímá okamžitě po doznění hlasitého tónu tichý (zpoždění).
  

4.6. MP3

MPEG Audio Layer 3

• Vyvinula se z komprese videa MPEG.
  
• Patentovaná komprese.
  
• Obvyklý kompresní poměr 1:10.

• Mono – jeden audio kanál.
• Dva mono kanály – dva nezávislé audio kanály.
• Stereo – využívá korelaci pravého a levého kanálu.
• Joint-stereo – velmi nízké a velmi vysoké frekvence jsou kódovány jako mono kanál, zbylé jako dva.
  

• Pokud algoritmus nemůže část zvuku zakódovat v daném úseku na daný počet bitů, může využít případné volné bity z předchozích úseků.
  
• 32 až 320 kbit/s.

4.7. Komprese obrazu

Statický monochromatický obraz lze chápat jako funkci dvou proměnných, která přiřazuje jednotlivým bodům roviny hodnotu intenzity.
Digitální obraz je složen z obvykle čtvercových pixelů (pictures elements), kterým je přiřazena intenzita.

Podle Grassmana (1854) lidské oko vnímá odstín (hue – vlnovou délku), sytost (saturation – čistotu) a jas (brightness – intenzitu).

• Barvy v barevném digitálním obraze jsou analogicky reprezentovány jako trojice intenzity jednotlivých složek.

4.8. JPEG

Joint Photographic Experts Group

• Konsorcium, které tuto ztrátovou kompresní metodu standardizovalo.
  

JFIF – JPEG File Interchange Format

• Výměnný formát souborů, pro který se ale přesto vžil díky používané příponě .jpg.

Postup

Obrázek se převede do barevného schématu YC_BC_R
Každá barevná složka je následně kódována zvlášť (po rozdělení na čtverce 8 x 8 pixelů).

• Transformace
  
• Kvantování
  
• Entropický kodér
  

4.9. Shrnutí

Zdroje

• JIROUŠEK, R. a kol. Principy digitální komunikace. Voznice : Leda, 2006. 309 s.
  ISBN 80-7335-084-X
• TOMAN, M. MP3. Plzeň : ZČU, 2002. 52 s.