Třicet let s obrázky
JPEG (Joint Photographic Experts Group) je název výboru, který stojí za standardem pro kompresi obrazu ISO/IEC 10918–1 nebo též doporučením CCITT/ITU-T T.81. Tento standard z roku 1992 se běžně označuje zkratkou JPEG. Stejně tak se touto zkratkou označuje formát souboru, který takovýto kompresní formát zaobaluje. JPEG je formát primárně určený ke ztrátové kompresi obrazu. Standard však definuje také režim pro bezeztrátovou kompresi.
Pro ztrátovou kompresi podporuje JPEG sekvenční a progresivní přenos obrazových dat. Mimoto JPEG definuje hierarchický režim, kdy je obrázek uložen v několika různých rozlišeních. Ten může komprimován obrázek ztrátově i bezeztrátově. Standard definuje také formát JIF, do kterého je možné data komprimovaná metodou JPEG uložit. Ten se však sám o sobě nepoužívá. Namísto toho se používají s JIF kompatibilní souborové formáty JFIF a Exif, případně JFIF s vloženými segmenty Exif. Tyto soubory mají příponu jpeg nebo jpg.
Standard JPEG definuje čtyři kompresní postupy (procesy). Základní postup (baseline process), který musejí být schopny provést všechny aplikace pracující s formátem JPEG, umožňuje komprimovat 8bitová vstupní data (na každou složku). Pracuje s Huffmanovým kódování a ke kompresi umožňuje použít až dvě tabulky Huffmanových kódů pro koeficienty AC a dvě tabulky pro koeficienty DC.
Data jsou komprimována pouze sekvenčně. Tímto způsobem je možno zkomprimovat až čtyři složky (např. Y, Cb a Cr). Rozšířený postup (extended process) rozšiřuje možnosti základního také na 12bitová data. Umožňuje využít progresivní zpracování a až čtyři tabulky pro koeficienty AC a čtyři pro DC. Další je bezeztrátový postup, který se v praxi nepoužívá. Posledním je hierarchický postup, který se taktéž nepoužívá. Následující text se věnuje pouze základnímu postupu (baseline).
Obrázek výše popisuje zjednodušené schéma kodéru JPEG. Stejné schéma se aplikuje na každý obrazový kanál.
Zpracování obrazu
Vstupní obraz je zpracováván v barevném modelu YCbCr. Jednotlivé složky lze horizontálně i vertikálně podvzorkovat. Barvonosné (chromatické) složky Cb a Cr se typicky podvzorkovávají v jednou nebo obou směrech na polovinu (4:2:2 a 4:2:0). Tyto tři složky barevného modelu jsou dále zpracovávány odděleně.
Každá složka je rozsekána na bloky 8×8 vzorků. To je hlavní důvod vzniku tzv. blokového efektu (blokových artefaktů) u obrázků s vysokým stupněm komprese (obrázek výše). K blokovému efektu přispívá menší mírou také podvzorkování barvonosných složek. Blok 8×8 vzorků je základní datovou jednotkou formátu JPEG.
Pokud některá složka obrazu nemá rozměry přesně v násobcích bloků, bude při kompresi na velikost bloku rozšířena. Doporučený způsob rozšíření je duplikace nejbližšího řádku/sloupce. Na každém takovém bloku 8×8 je následně spočtena jeho diskrétní kosinová transformace (DCT).
Výsledkem je matice 64 koeficientů. Transformovaný blok má v levém horním rohu koeficient udávající posun vůči 0 neboli průměr bloku, tedy tzv. stejnosměrnou složku signálu. Odtud se nazývá koeficient DC (analogie ke stejnosměrnému proudu, anglicky Direct Current). Tento koeficient se dále kóduje odlišně proti zbytku transformace.
Zbylých 63 koeficientů se označuje jako koeficienty AC (analogicky ke střídavému proudu, Alternating Current). Udávají váhy, se kterými je v bloku přítomna odpovídající dvourozměrná kosinusoida. Právě popsaný postup je plně invertibilní, nedochází ke ztrátě dat. Nejvíce energie (nejvyšší amplitudy koeficientů) bývá soustředěno kolem nízkých frekvencí (okolí koeficientu DC). Vyšší frekvence se vyskytují především na hranách objektů.
Kvantování koeficientů
Následujícím krokem je kvantování koeficientů. K tomu musí kodér i dekodér obdržet tzv. kvantizační tabulku. To je tabulka s hodnotami, kterými má být při kompresi podělen korespondující koeficient DCT. Následně je každý koeficient zaokrouhlen na nejbližší celé číslo. Nejvyšší hodnoty jsou v kvantizačních tabulkách koncentrovány u vysokých frekvencí, kde je možné dopustit se větší ztráty dat.
| 16 | 11 | 10 | 16 | 124 | 140 | 151 | 161 |
| 12 | 12 | 14 | 19 | 126 | 158 | 160 | 155 |
| 14 | 13 | 16 | 24 | 140 | 157 | 169 | 156 |
| 14 | 17 | 22 | 29 | 151 | 187 | 180 | 162 |
| 18 | 22 | 37 | 56 | 168 | 109 | 103 | 177 |
| 24 | 35 | 55 | 64 | 181 | 104 | 113 | 192 |
| 49 | 64 | 78 | 87 | 103 | 121 | 120 | 101 |
| 72 | 92 | 95 | 98 | 112 | 100 | 103 | 199 |
Tabulka výše ukazuje příklad kvantizační tabulky pro 8bitovou jasovou složku Y.
Při dekompresi jsou těmito hodnotami koeficienty naopak násobeny. Protože byly hodnoty koeficientů zaokrouhleny na celá čísla, je rekonstruovaný koeficient kvantovaný do několika hladin. Kvantizační tabulka udává, jak velké ztráty dat se kompresor dopustí. Vyšší hodnoty znamenají hrubší kvantování, tedy větší ztrátu informace a tedy méně kvalitní dekomprimovaný obraz. Hodnoty v tabulce jsou tudíž vytvářeny s ohledem na cílovou kvalitu a lidský psychovizuální model. Pro jasovou složku Y a chromatické složky Cb a Cr se používá odlišná tabulka. Důvodem k tomu je větší citlivost lidského oka na jas Y.
Obrázek ukazuje význam koeficientů DCT v bloku 8×8 pixelů. V (a) je naznačena orientace funkce cosinus. Červeně jsou vybarveny vertikální hrany (světle jsou čistě vertikální), modře horizontální (světle čistě horizontální) a zeleně mřížka vytvořená kombinací vertikální a horizontální funkcí. V (b) je zobrazeno rozdělení frekvencí. Modře jsou vyznačeny nízké frekvence, červeně vysoké. Bázové funkce jsou zobrazeny v (c).
Kvantovací tabulky jsou parametrem metody JPEG, které udávají míru a kvalitu komprese. Uživatel samozřejmě pro nastavení míry komprese nemusí specifikovat 64 koeficientů každé kvantizační tabulky. Namísto toho je použitým programem spočtena každá z kvantizačních tabulek na základě jediného parametru q, který udává kvalitu obrazu neboli míru komprese. Jestliže je zvolena vhodná kvantovací tabulka, bude většina koeficientů DCT po kvantizaci nulová. Zbylé budou koncentrovány v levém horním rohu (nízké frekvence).
Linearizace
Matice kvantovaných koeficientů je dále linearizována tzv. zig-zag průchodem. Tento průchod prochází nejdříve koeficienty s nižšími frekvencemi. Ty mají typicky vyšší amplitudu a tudíž je u nich větší šance, že zůstanou i po kvantizaci nenulové. Naopak koeficienty ke konci průchodu budou s vyšší pravděpodobností nulové a není třeba je kódovat. Namísto toho se za poslední nenulový koeficient umístí symbol EOB (End Of Block).
Řada linearizovaných koeficientů je dále podrobena variantě RLE kódování nul. Mimo řetězec RLE stojí pouze koeficient DC, který je kódován diferenciálně (rozdílově) proti koeficientu DC z předchozího bloku. Tento rozdílný krok je proveden, protože průměrné hodnoty (koeficienty DC) sousedních bloků jsou velmi blízké.
Posledním krokem jejich komprese je Huffmanovo nebo aritmetické kódování. Obě kódování probíhají za pomoci dodaných tabulek. Aritmetické je cca o 5 až 10 % účinnější.
Huffmanovo kódování
Protože aritmetické kódování (QM kodér) se u JPEGu prakticky nepoužívá, budeme se věnovat pouze Huffmanovu kódování. Koeficienty DC se kódují za pomoci odlišných tabulek Huffmanových kódů než koeficienty AC. Sled koeficientů AC (zlinearizovaných průchodem zig-zag) obsahuje jen několik málo nenulových čísel. Mezery mezi nimi vyplňují sledy nul. Jak už bylo zmíněno výše, za posledním nenulovým koeficientem následuje dlouhý sled koncových nul, který je nahrazen symbolem EOB. Efektivní kódování těchto sledů nul je motivací k využití metody RLE.
Rozdílová hodnota koeficientu DC se kóduje podle tabulky níže. Ve skutečnosti není třeba takovou tabulku mít umístěnou v paměti. Kategorii lze pro danou hodnotu koeficientu jednoduše spočítat. Číslo kategorie se zakóduje kódem z použité tabulky Huffmanových kódů. Tento kód je následován stejným počtem bitů, jako je hodnota kategorie. Tyto další bity udávají pořadí hodnoty uvnitř sloupce rozsah zmíněné tabulky. Např. rozdílová hodnota koeficientu −2 bude zakódována Huffmanovým kódem kategorie 2, za kterým následuje binárně 01, tedy druhá hodnota ve sloupci rozsah.
První bit udává vlastně znaménko. Za kategorii 0 se již žádné další bity nepřipojují. Aby se předešlo konfliktu se synchronizačními značkami 0xff, netvoří žádný z použitých Huffmanových kódů pouze bity 1. Pokud by se bajt 0xff vyskytnul v zápise hodnoty za kódem kategorie, musí být následován vloženou hodnotou 0x00. Sestavení tabulky Huffmanových kódů je záležitostí kodéru. Často se však používají předpočítané tabulky, což má výhodu v menší výpočetní náročnosti komprese.
| Kategorie | Rozsah hodnot |
|---|---|
| 0 | 0 |
| 1 | −1, 1 |
| 2 | −3, −2, 2, 3 |
| 3 | −7 … −4, 4 … 7 |
| 4 | −15 … −8, 8 … 15 |
| 5 | −31 … −16, 16 … 31 |
| 6 | −63 … −32, 32 … 63 |
| 7 | −127 … −64, 64 … 127 |
| 8 | −255 … −128, 128 … 255 |
| 9 | −511 … −256, 256 … 511 |
| 10 | −1023 … −512, 512 … 1023 |
| 11 | −2047 … −1024, 1024 … 2047 |
Tabulka výše zobrazuje kategorie a rozsahy koeficientů DC.
Před kódováním každého nenulového koeficientu AC hledá kodér sled Z předcházejících nul. Pokud je nalezen sled délky více než 15 nul, je sled 15 nul zakódován symbolem ZRL. Dalším krokem je výpočet kategorie S pro amplitudu kódovaného nenulového koeficientu. Princip je stejný jako u kategorií koeficientů DC. Kategorie 0 není využita, protože koeficienty jsou již nenulové (nulové se kódují pomocí RLE).
Kategorie S a délka sledu Z se nyní použíjí jako indexy do tabulky Huffmanových kódů. Za kódem opět následují bity, které udávají pořadí ve sloupci rozsah (tedy upřesňují hodnotu koeficientu). Kód pro Z = 0 a S = 0 má význam EOB. Kód pro Z = 15 a S = 0 je ZRL, což lze chápat jako sled 15 nul, který je následován koeficientem s amplitudou 0, tedy celkem 16 nul.
Uložení do kontejneru
Standard JPEG (T.81) definuje základní kontejner JIF pro data komprimovaná metodou JPEG. JIF využívá uspořádání bajtů big endian. Soubory jsou rozděleny do segmentů, což je blok max. 65 535 B. Každý segment začíná značkou čili markerem, který identifikuje jeho obsah.
Marker je dvoubajtová hodnota, ve které první bajt má vždy hodnotu 0xff. Druhý bajt je vždy v rozsahu 0x01 až 0xfe. Hodnota 0x00 je vyhrazena pro použití skutečné hodnoty 0xff (255) uvnitř segmentu. Další hodnoty 0xff před začátkem markeru jsou ignorovány. Důležité markery jsou APP0 (hlavička JFIF), APP1 (Exif), SOF0 (začátek obrázku v základním režimu), SOS (začátek komprimovaných dat), RSTm (restartovací značky), DHT (definice Huffmanových tabulek) a DQT (definice kvantizačních tabulek).
Datový tok zkomprimovaný metodou JPEG je možné vkládat do různých kontejnerů (např. MJPEG, PDF, TIFF). Nejčastěji se vkládá do samostatného souborového formátu JFIF, který rozšiřuje JIF především o hlavičku a náhledy. Tyto soubory pak mají příponu jpeg nebo jpg. Další možností je použít formát Exif, který je taktéž rozšířením formátu JIF. Exif je značně složitější než JFIF – vkládá do formátu JIF formát TIFF, do kterého ukládá nejrůznější informace o snímku (např. výrobce, model fotoaparátu), náhled obrázku atd. Exif a JFIF nejsou kompatibilní, často se však používá hack, ve kterém se jako kontejner použije JFIF a za hlavičku se vloží ještě segment s daty Exif.
Přikládám ještě odkaz na svůj vlastní dekodér a kodér formátu JPEG. I s komentáři má cca 4 000 řádek kódu. Za reportování jakýchkoli chyb budu vděčný.
(Autorem obrázků je David Bařina.)
ČLÁNKY DO MAILU