Programujeme JPEG: Huffmanovo kódování kvantovaných DCT složek

Obsah

1. Huffmanovo kódování kvantovaných DCT složek
2. Princip kódování DC koeficientů
3. DC složky a diferenční kategorie
4. Zápis diferenčních kategorií pomocí Huffmanova kódu
5. AC složky a jejich kategorie
6. Odkazy na další informační zdroje
7. Obsah dalšího pokračování tohoto seriálu

1. Huffmanovo kódování kvantovaných DCT složek

Posledním krokem před zápisem obrazových dat do souborů typu JFIF/JPEG je Huffmanovo či aritmetické kódování. V dalším textu se zaměříme pouze na popis Huffmanova kódování. Aritmetické kódování se příliš často nepoužívá, protože je pomalejší, implementačně náročnější a také je zatíženo několika patenty (http://en.wi­kipedia.org/wi­ki/Arithmetic_co­ding#US_paten­ts_on_arithme­tic_coding). Ukazuje se, že snížení velikosti souboru o cca 5% – 10% v případě aritmetického kódování výrobci oželí a raději se soustředí na kvalitně provedené Huffmanovo kódování s možnou optimalizací kódovacích tabulek a se zárukou, že vytvořené soubory bude možné bez problémů prohlížet či editovat v mnoha dalších aplikacích.

Huffmanovo kódování obecně funguje na principu zápisu symbolů vstupní abecedy, které se vyskytují s větší frekvencí, s využitím malého množství bitů na výstupu a naopak: symboly vstupní abecedy s malou frekvencí výskytu se mohou na výstup zapsat větším počtem bitů (na podobném principu je postavena i Morseovka, ovšem s tím rozdílem, že se v jejím případě nejedná o kód prefixový). Symbolem může být cokoliv. Typicky se jedná o znaky (třeba ASCII), v případě JPEGu jde o čísla takzvaných kategorií, ale může se například jednat i o sekvence bytů, třeba dvojici či trojici znaků. Dokonce se může jednat i o samostatná slova, což je použito při velmi účinné komprimaci známých HLP souborů firmy Microsoft. Správně vytvořený Huffmanův kód je kódem s minimální délkou (ve smyslu Shannova teorému) a také se jedná o takzvaný prefixový kód, který se vyznačuje tím, že je jednoznačně dekódovatelný.

Huffmanův kód se vytváří pomocí konstrukce binárního stromu s koncovými uzly, které odpovídají symbolům původní abecedy. Hrany stromu jsou ohodnoceny symboly 0 a 1 a všechny uzly (včetně koncových) jsou ohodnoceny pravděpodobností výskytu příslušných symbolů ve vstupní sekvenci. Pravděpodobnost vnitřního uzlu se rovná součtu pravděpodobnosti jeho poduzlů; z toho plyne, že kořen má pravděpodobnost nastavenou na jedničku. Výsledný binární strom je možné zapsat pouze sekvencemi symbolů 0 a 1, které jsou přiřazeny jednotlivým hranám. Z principu „pravidelné“ konstrukce binárního stromu také plyne fakt, že Huffmanův kód je kódem prefixovým.

Při čtení minule uvedeného popisu DCT a kvantizace jste možná měli pocit, že se v JPEG komprimaci používá hrubá síla a složité vysokoúrovňové operace typu výpočet kosinu či dělení se zaokrouhlením. Samotné kódování DC i AC koeficientů pomocí Huffmanova kódování naproti tomu spíše připomíná jemnou práci s jednotlivými bity s důrazem i na malé detaily (například použití RLC po Huffmanově kódování AC složek nebo použití čtyř rozdílných kódových tabulek). Není divu, protože Huffmanovo nebo aritmetické kódování představuje kritické místo celé metody JPEG komprimace. Špatný návrh by vlastně zhatil předchozí úsilí (převod RGB na YC_bC_r, DCT i kvantizaci), protože tyto tři kroky se provádí právě proto, aby výsledkem byla sekvence bitů snadno zpracovatelná právě Huffmanovým či aritmetickým kódováním.

2. Princip kódování DC koeficientů

Nejprve si řekněme, jakým způsobem jsou kódovány DC (tj. stejnosměrné) koeficienty. V předchozí části tohoto seriálu jsme si řekli, že stejnosměrné koeficienty jsou před vlastním Huffmanovým kódováním upraveny velmi jednoduchým prediktorem: vypočte se rozdíl mezi aktuální hodnotou DC koeficientu a hodnotou DC koeficientu z předchozího bloku. Přitom platí, že u prvního bloku 8×8 pixelů umístěného v levém horním rohu obrázku, se DC koeficient předchozího bloku definitoricky nastavuje na nulu (tento blok totiž nemá žádného předchozího souseda).

Výpočet rozdílu DC koeficientů vychází z teorie tvrdící, že sousední bloky 8×8 pixelů mají u reálných obrázků s velkou pravděpodobností stejné či alespoň podobné průměrné barevné hodnoty. Proto jsou shodné či blízké i jejich stejnosměrné složky a jejich rozdílem tedy většinou získáme poměrně malou číselnou hodnotu. To však platí pouze statisticky, ve skutečnosti musíme být připraveni zakódovat i velké rozdíly mezi DC složkami. Vzhledem k tomu, že pravděpodobnost velké změny mezi sousedními DC složkami (a tím i velkého číselného rozdílu mezi nimi) je poměrně malá, je zvoleno odstupňované kódování rozdílů mezi složkami, které je popsáno v následující kapitole.

3. DC složky a diferenční kategorie

Pro vstupní data o bitové hloubce 8 bitů na každou barvovou složku platí, že dynamický rozsah DCT koeficientů je 11 bitů. Prediktor, který byl pro stejnosměrné složky zaveden (tj. výpočet rozdílů stejnosměrných složek sousedních bloků 8×8 pixelů), sice statisticky tento počet bitů snižuje, v nejhorším možném případě však naopak jeden bit přidává. Sčítání a odčítání má tento charakter při všech operacích, to je ostatně hlavní důvod pro existenci sčítaček a odčítaček s přenosem (carry). Z předchozího textu vyplývá, že rozdílovou DC složku musíme umět v JPEGu zaznamenat až do šířky dvanácti bitů, což představuje rozsah hodnot rozdílových složek DC koeficientů –2048..2047 (ve skutečnosti je rozsah symetrický –2047..2047, onu poslední hodnotu nebudeme brát v úvahu, což bude patrné z následující tabulky).

V případě, že vstupní obrázek obsahuje 12 bitů na barvovou složku (rentgenové či ultrazvukové snímky, výstupy z některých typů CCD čipů), dostaneme pro DC složky vzniklé po DCT transformaci celkem šestnáct kategorií, tyto obrázky jsou však spíše vzácností nežli pravidlem a v praxi se s nimi často nesetkáte. V dalším textu se budeme zabývat pouze situací při zpracování obrázků s osmi bity na barvovou složku. V JPEGu jsou rozdílové hodnoty DC koeficientů rozděleny do dvanácti kategorií tak, jak to ukazuje následující tabulka (tato tabulka se do souboru JFIF/JPEG neukládá, musí však být použita v kodérech i dekodérech):

Ve výše uvedené tabulce můžeme vidět, jakým způsobem se v každé diferenční kategorii vytváří pravidelným způsobem rozsahy hodnot. Pokud například máme zakódovat hodnotu 42, můžeme v této tabulce jednoduše dohledat, že se bude jednat o kategorii číslo 6. Jak konkrétně kódování hodnot uložených v jednotlivých kategoriích vypadá? Nejprve se podívejme, kolik bitů potřebujeme pro zápis kladných i záporných hodnot v každé kategorii. Za příklad si vezměme například zmiňovanou kategorii číslo 6. Celkový počet hodnot DC složek, které mohou být v této kategorii zapsány, je:

abs(-63-(-32))+1+abs(63–32)+1=abs(-31)+abs(31)+2=64 = 2⁶

Hodnoty v šesté kategorii jsou tedy uloženy na šesti bitech. Podobné vztahy platí i pro další diferenční kategorie DC složek (i AC složek): číslo kategorie nám přímo udává počet bitů nutných pro uložení rozdílové hodnoty dané DC složky. Vlastní bitový zápis čísla kategorie do souboru je již záležitostí Huffmanova kódování, které bude popsáno v následující kapitole.

4. Zápis diferenčních kategorií pomocí Huffmanova kódu

Před hodnotu rozdílové DC složky (počet bitů se liší podle kategorie, viz předchozí kapitolu) je nutné zapsat i číslo kategorie, aby dekodér věděl, kolik bitů má přečíst. Číslo kategorie se do souboru nezapisuje přímo, ale je použito Huffmanovo kódování, které často používaná čísla kategorií ukládá na menším počtu bitů než nepoužitá či méně často používaná čísla kategorií. V souborech typu JFIF/JPEG mohou být zapsány až čtyři Huffmanovy kódovací tabulky, které jsou uvozeny značkou DHT s číselným identifikátorem nula nebo jedna (o značkách si povíme příště). Tyto tabulky mají následující význam:

Vidíme, že každá kódovací tabulka je použita pro kódování jiných typů kvantovaných DCT složek. Pro stejnosměrné (DC) složky je použita jiná tabulka, než pro složky střídavé (AC). Barvonosné signály C_b a C_r používají jinou dvojici tabulek, než světlonosný signál Y. Význam čtyř obecně rozdílných tabulek vychází z praxe, protože každá složka AC/DC :-) a každý barvový signál má jiné rozložení hodnot a hodí se pro něj i jiná kódová tabulka.

Kódové tabulky si může každý komprimační program vytvořit vlastní, většinou se však používají tabulky definované konsorciem JPEG. Je to škoda, protože zejména v obrázcích s malým rozlišením nejsou všechny kategorie přítomny a příslušné kódovací tabulky by mohly být mnohem menší než ty normované. V dalším textu si uvedeme podobu standardních tabulek pro DC složky, jedná se tedy o tabulky DHT Class=0 (ID=0 či ID=1).

Jak se s těmito tabulkami pracuje? Podle velikosti ukládané hodnoty získáme z první tabulky (uvedené v předchozí kapitole) číslo příslušné kategorie; přesně to jsme provedli pro naši hodnotu 42. Posléze se ve druhé tabulce získá bitový vzorek (kódové slovo, codeword) příslušné kategorie, který se zapíše do výstupního bitového proudu. Například pro kategorii 6 by se zapsal buď bitový vzorek 1110 nebo 111110 podle toho, zda se provádí kódování luminančních hodnot (světlostí) či hodnot chrominančních (barvonosné signály C_b, C_r). V případě zápisu luminanční hodnoty 42 tedy získáváme tento bitový vzorek:

1100 101010

Z příkladu můžeme vidět, že za bitový vzorek reprezentující zakódované číslo kategorie (1100) se doplní znaménko a velikost vypočtené diference (000000₂=-63₁₀, 011111₂=-32₁₀, 100000₂=32₁₀, 101010₂=42₁₀, atd.), ovšem pouze n-dolních bitů (počet těchto bitů přímo odpovídá dané kategorii, to jsme si již také řekli). Žádné další bity se již nezapisují, protože rozsah hodnot je známý už ze zakódovaného čísla kategorie. Speciálním případem je kategorie 0, za kterou se již žádné „hodnotové“ bity nepřipojují – v této kategorii se nachází pouze jedna hodnota, u které se nemusí rozlišovat znaménko (jde o nulu).

Všimněte si konstrukce předchozí tabulky – její tvůrci evidentně počítali s tím, že diferenční složky barvonosných signálů budou mít nízké hodnoty, proto jsou také „vyplýtvány“ hned tři dvoubitové prefixy: 00, 01 a 10. U luminance tato jistota nebyla tak velká, proto se použil pouze jeden dvoubitový prefix a pět tříbitových prefixů. Výskyt vysokých hodnot diference DC složek je málo pravděpodobný, proto si tvůrci mohli dovolit i velmi dlouhá kódová slova. Ze druhé tabulky je také patrné, proč mluvíme o Huffmanově kódu: ten je vytvářen pomocí bitových prefixů naprosto stejným způsobem (i když se většinou pomocí něho přímo kódují symboly, znaky či jejich sekvence a zde se jedná o čísla kategorií).

Také stojí za uvedení, že se v tabulce nevyskytují sekvence samých bitových jedniček (vždy je přítomna alespoň jedna nula na konci sekvence). Je to z toho důvodu, že tvůrci JPEG celý formát navrhli tak, aby se v případě chyby vzniklé například při přenosu mohl dekodér co nejdříve zasynchronizovat na speciálních značkách. Ty vždy začínají bytem s hodnotou 0×ff, za kterým následuje kód značky. Pokud se přímo při zápisu jednotlivých pixelů (tj. čísel kategorií s hodnotami) vyskytne dlouhá sekvence bitových jedniček, může to znamenat, že se do souboru zapíše právě byte s hodnotou 0×ff, za kterým musí následovat „vložený“ byte s hodnotou 0×00. Aby byla pravděpodobnost tohoto stavu co nejmenší (zbytečně se zvyšuje velikost souboru o „vkládané“ byty), tak se v tabulkách nikde nevyskytují pouze sekvence samých jedniček. To sice problém vkládaných bytů zcela neodstraní, ale alespoň se snižuje pravděpodobnost jejich výskytu.

Při optimalizaci JPEGu se Huffmanův kód tvoří dynamicky podle charakteru zpracovávaných dat, většinou se však používají pevně nastavené kódové tabulky (neoptimalizovaný JPEG). Má to tu výhodu, že se vlastní tabulky (které jsou poměrně rozsáhlé) nemusí počítat, což je zejména paměťově, ale i výpočetně náročné – musí se vytvořit tabulka četností jednotlivých kategorií a z této tabulky sestrojit binární strom, který se posléze převede do prefixového kódu. Standardní tabulky mohou být naproti tomu uloženy například v paměti ROM a vlastní kódování je mnohem méně náročné na paměť (nehledě na to, že se obrázek prochází pouze jedenkrát). Uvádí se, že při použití optimalizovaných Huffmanových kódovacích tabulek se délka souboru u obrázků s větším rozlišením sníží o cca 5%-10%, u malých obrázků to však může být i 50% (vlastní kódovací tabulky je také nutné do souboru uložit, to se více projeví u malých obrázků).

5. AC složky a jejich kategorie

I střídavé složky (AC) jsou rozděleny do několika kategorií. Vzhledem k tomu, že AC složky nejsou ukládány v diferenční podobě, tj. není použit prediktor, je pro ně definováno pouze deset kategorií (resp. za jedenáctou kategorii můžeme považovat nulové hodnoty, ty se však většinou zapisují pomocí RLC):

Tyto hodnoty se však nezapisují do výstupního souboru přímo, ale provádí se navíc jednoduchá podoba RLC kódování. Je tomu tak z toho důvodu, že mnoho AC koeficientů má po provedení kvantizace DCT koeficientů nulovou hodnotu a tak musí existovat způsob efektivního zápisu několika za sebou jdoucích nul. Nenulové AC koeficienty se vyjádří dvojicí R|S, kde R je takzvaný „0-run“ (sled), což je vlastně čtyřbitový čítač nulových hodnot, udávající, kolik těchto hodnot je v souboru za sebou zapsáno (podobný způsob je použit u grafického formátu PCX, tam se však jednalo o přímé kódování barev). S udává „size“ (velikost) první nenulové AC složky (samotná velikost je zapsána na čtyřech bitech), která následuje po složkách nulových.

Kromě toho existuje ještě speciální bitová hodnota EOB (End Of Block), která má podobu sekvence bitů 1010. Touto hodnotou je celý blok 8×8 hodnot ukončen s tím, že všechny zbylé AC složky mají hodnotu nulovou. V reálných obrázcích se opravdu EOB často používá, protože cik-cak sken, který jsme si popsali minule, ponechává AC složky s vysokými frekvencemi až na konci sekvence a právě tyto složky mají po kvantizaci většinou nulovou hodnotu. V praxi se tedy například může stát, že se do souboru zakóduje diferenční hodnota DC složky, potom následuje např. deset nenulových hodnot AC složek a značka EOB, která automaticky nastaví zbylých 53 AC složek na nulu, aniž by se musely tyto nuly zapisovat do souboru a prodlužovat tak jeho délku.

6. Odkazy na další informační zdroje

1. From ASCII coding to Huffman coding:
   http://www.cs­.duke.edu/csed/po­op/huff/info/
2. Wikipedia: Huffman coding:
   http://en.wiki­pedia.org/wiki/Huf­fman_coding
3. Wikipedia: Huffmanovo kódování:
   http://cs.wiki­pedia.org/wiki/Huf­fmanovo_k%C3%B3do­v%C3%A1n%C3%AD
4. Calvin Hass: JPEG Huffman Coding Tutorial:
   http://www.im­pulseadventure­.com/photo/jpeg-huffman-coding.html
5. Calvin Hass: JPEGsnoop – JPEG File Decoding Utility:
   http://www.im­pulseadventure­.com/photo/jpeg-snoop.html
6. comp.compression Frequently Asked Questions (part 1/3):
   http://www.faq­s.org/faqs/com­pression-faq/part1/
7. comp.compression Frequently Asked Questions (part 2/3):
   http://www.faq­s.org/faqs/com­pression-faq/part2/
8. comp.compression Frequently Asked Questions (part 3/3):
   http://www.faq­s.org/faqs/com­pression-faq/part3/

7. Obsah dalšího pokračování tohoto seriálu

V následující části tohoto seriálu si popíšeme strukturu souboru JFIF/JPEG, včetně významu nejdůležitějších značek (markers), které se v těchto souborech mohou nacházet.