Obsah

Komprese obrazu

Motivace: snaha o zmenšení velikosti souborů např. pro přenos po síti, archivaci apod.

Základní přístupy ke kompresi

Nejprve je potřeba zvolit v jaké oblasti chceme komprimovat:

Základní kompresní algoritmy

JPEG

JPEG

  1. Obrázek je převeden do barevného modelu YCbCr (kódování RGB, kde Y je komponenta luminace a Cb s Cr jsou modrý a červený chrominanční komponent
  2. Jelikož oko vnímá více jas než barvy, Cb a Cr můžeme podvzorkovat = snížit přesnost informací o barvě (Chroma Subsampling)
  3. Celý obrázek je rozdělen do bloků o velikosti 8 × 8 pixelů. A pro každou ze složek (Y, Cb a Cr) se provede Diskrétní cosinová transformace (DCT). DCT je dvourozměrnou obdobou Fourierovy transformace. Blok 8 × 8 se tak vyjádří jako složení signálů o různé frekvenci.
  4. Nad bloky se provede kvantizace. Lidský zrak je citlivý k relativně malé změně v jasu nebo v barvě na poměrně velké ploše (nízké frekvence). V rozlišování konkrétní síly rychle se měnícího jasu (vysokofrekvenční změny) je však mnohem horší. To nám umožňuje informace o takovýchto změnách vynechat. Výsledek DCT se vydělí kvantizační maticí (tabulkou) a zaokrouhlí. Hodnoty v kvantizační tabulce, kterými se budou násobit hodnoty vysokofrekvenčních změn, jsou takové, aby po vydělení původní hodnoty hodnotou z tabulky a zaokrouhlení vyšla nula nebo malé číslo.
  5. Data bloků se dále v zig-zag pořadí komprimují bezeztrátově nejprve pomocí Run-length encoding (RLE) a pak Huffmanovým kódováním nebo pomocí Aritmetického kódování.

Dekódování probíhá inverzně (problém kostičkování).

JPEG komprese dosahuje kompresních poměrů od 10:1–20:1 (high) až po 60:1 – 100:1 (low).

GIF

Graphics Interchange Format

Používá Lempel–Ziv–Welch algoritmus:

  1. Inicializuj slovník na všechny řetězce dlouhé jeden znak.
  2. Najdi nejdelší možný řetězec ve slovníku, který odpovídá aktuálnímu vstupu.
  3. Zakóduj řetězec indexem ze slovníku.
  4. Přidej řetězec + následující znak ze vstupu do slovníku.
  5. Běž na krok 2.

Typický kompresní poměr je 4:1–10:1.

PNG

Portable Network Graphics

PNG používá dvoustupňovou bezeztrátovou kompresi:

  1. Před samotnou kompresí se snaží objevit běžné vzory (např. barevné pruhy, gradienty). Tento krok se nazývá filtering.
  2. Komprese – PNG ke kompresi používá metodu DEFLATE, což je kombinace algoritmu LZ77 a Huffmanova kódování.

Kompresní poměr typicky o 10–30 % lepší než GIF.