Komprese obrazu

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

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

• Prostorová – statické obrázky (RGB, YCbCr)
• Frekvenční – statické obrázky (FFT, DCT, DWT)
• Časová – video

• Ztrátová – využívají se znalosti o lidském oku, které nejvíce vnímá jasu než barvu.
• Bezstrátová – algoritmy pro kódovaní běžných dat (RLE, Huffman, deflate, LZ77).

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).

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.

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.