Kompresný štandard JPEG



História vzniku

V roku 1986 vznikla skupina expertov označená ako JPEG (Joint Photographics Experts Group), ktorá začala pracovať s cieľom vytvorenia prvého medzinárodného štandardu pre kompresiu a dekompresiu spojito tónovaného (viacúrovňového) statického obrazu.

Úvod

Na rozdiel od ostatných kompresných metód nieje JPEG samostatný kompresný algoritmus, ale môžeme ho považovať za súbor komprimačných techník, ktoré môžu byť prispôsobované daným požiadavkám užívateľa. Štandard JPEG predstavuje stratovú metódu kompresie dát, na rozdiel od populárnych kompresných algoritmov ako sú napr. RLE, LZW,...ktoré sú nestratové. Podstata kompresného algoritmu použítého v štandarde JPEG, spočíva vo využití transformačných vlastností DCT (diskrétnej kosínusovej transformácie) a kvantizácii získaných koeficientov .
Pri stratových kompresných algoritmoch sa určité, relatívne nepodstatné detaily strácajú preč. To je aj dôvodom prečo dosahujú lepších kompresných výsledkov ako nestratové algoritmy. JPEG bol vytvorený tak, aby sa strácali iba informácie, ktoré môže ľudské oko len veľmi tažko rozlíšiť. Malé zmeny farieb nieje ľahké ľudským okom rozoznať tak, ako zmeny v intenzite (svetlá, tmavá). Teda ľudské oko je viac citlivé na zmeny v intenzite ako na zmeny farieb. JPEG bol vytvorený hlavne kôli komprimácii farebných, šedo tieňovaných, spojito tónovaných predlôh reálnych predmetov, fotografií,... Pri kompresnom pomere 15:1 až 25:1 nedochádza k výraznej ujme na kvalite predlohy. V praxi však môžeme ísť s kompresiou vyššie, až pokiaľ nám vyhovuje výsledná kvalita komprimovaného obrazu, ktorý po kompresii vizuálne kontrolujeme.

Štandard JPEG popisuje 4 spôsoby činnosti (módy):

Sekvenčný JPEG kóder

Koder JPEG

Obr.1: Bloková schéma sekvenčného JPEG kódera

1.TRANSFORMÁCIA FARIEB

JPEG algoritmus je schopný kódovať predlohy používajúce akýkoľvek typ farebného prostredia. Kóduje každú súčasť farebného modelu zvlášť a je preto nezávislý na akomkoľvek farebnom modely ako RGB alebo CMY. Najlepších kompresných pomerov sa dosahuje v prípade jasového/chromatického farebného prostredia , ako YUV a YCbCr (definuje ich štandard CCIR č. 601). Y odpovedá jasovej zložke a Cb a Cr sú farbonosné zložky. Väčšina vizuálnych informácií na ktoré je ľudské oko najviac citlivé, sa vyskytuje v jasových komponentoch (Y) farebného prostredia YCbCr. Ďalšie dva farebné komponenty (Cb a Cr) obsahujú farebnú informáciu na ktoré je ľudské oko menej citlivé a väčšina týchto informácií môže byť odstránená ich podvzorkovaním. Oproti farebným modelom YUV a YCbCr majú RGB a CMY rozptýlené ich užitočné vizuálne informácie o predlohe rovnomerne cez všetky 3 farebné komponenty, čo podstatne sťažuje selektívne odstraňovanie informácií. Všetky tri komponenty musia byť kódované najvyššou kvalitou, čo má za následok menší kompresný pomer. Predlohy vytvorené odtieňmi šedi neobsahujú farebné prostredie a nevyžadujú akúkoľvek transformáciu.

2.PODVZORKOVANIE

Princíp spočíva v tom, že farebné komponenty tzv. podvzorkujeme . JPEG štandard poskytuje niekoľko rôznych možností pre vzorkovacie pomery alebo relatívnu veľkosť podvzorkovaných kanálov. Jasovému kanálu Y sa väčšinou necháva plná rozlíšiteľnosť (vzorkovanie 1:1). Oba farebné kanály Cb a Cr sa pre podvzorkovanie 2:1 vodorovne a 1:1 alebo 2:1 zvisle.

Konverzia RGB do YCbCr
YCbCr (256 hodnôt) môžeme priamo previezť z 8-bit RGB nasledovne:


   Y   =     0.299  R + 0.587  G + 0.114  B 

   Cb  =   - 0.1687 R - 0.3313 G + 0.5    B + 128 

   Cr  =     0.5    R - 0.4187 G - 0.0813 B + 128 

  

Príklad podvzorkovania bloku 4x4

YCbCr 4:2:2

Ak uvažujeme 8bit na jednu vzorku potom pri štandardnom farebnom modely RGB je potrebných 8x3=24bit/pixel. Po prevode do modelu YCbCr a následnom podvzorkovaní 4:2:2 je potrebných 16bit/pixel. Jedna vzorka Cb resp. Cr sa pri podvzorkovaní 4:2:2 získa priemerom dvoch susedných vzoriek z modelu YCbCr 4:4:4.

Takáto úspora nieje možná pri konvenčných farebných modeloch ako napr. RGB, pretože RGB v tomto modely obsahuje pre každý farebný kanál nejaké jasové informácie, a preto je akýkoľvek zásah do nich ihneď viditeľný.

3.DCT (Diskrétna kosínusová transformácia)

Na začiatku mala skupina JPEG niekoľko návrhov pre daný štandard. V januári 1988 padlo definitívne rozhodnutie , pričom za základ zvoleného štandardu sa zobrala diskrétna kosínusová transformácia (DCT). Výhodou DCT je, že pre typický obrázok so spojitými prechodmi farieb je väčšina vizuálne najdôležitejších informácií o obrázku koncentrovaná v malom počte kosínusových funkcií nízkych frekvencií. Ďalšou výhodou DCT je, že frekvenčné koeficienty sú reálne, z čoho vyplýva, že pre spätnú transformáciu sa využíva rovnakého postupu (t.j. aj rovnakých obvodov). Transformácia sa aplikuje na blok 8x8 pixelov. DCT vykoná matematickú transformáciu bloku 8x8 pixelov z priestoru súradníc x, y do frekvenčnej oblasti. Získame tak spektrálnu maticu rozmeru 8x8. Vo frekvenčnej oblasti môžeme jednoducho rozlíšiť ktoré časti informácie sú pre danú oblasť dominantné (hlavne nižšie frekvencie) a ktoré popisujú len jemné detaily (vyššie frekvencie) pozri obr.5.
Nasledujúce rovnice sú funkčnou definíciou doprednej diskrétnej kosínusovej transformácie FDCT (Forward Discrete Cosine Transform) a inverznej transformácie IDCT pre bloky údajov 8x8:

DCT vzorce

Pre bloky 8x8 bodov, môžeme zostaviť 64 základných funkcií DCT.

DCT base 8x8

Obr.2: 64 základných funkcií DCT pre blok 8x8

Predpoklad metódy DCT týkajúci sa nedôležitosti funkcií vyšších frekvencií neplatí v prípade, že sa v obraze vyskytujú ostré hrany. Potlačenie funkcií vyšších frekvencií sa vo výslednom obraze prejaví vlnením vychádzajúcim z miest pôvodných hrán (tzv. Gibbsov jav).

Original Gibbson_efekt
Obr.3: Prvý obrázok predstavuje originál obrázok. Druhý obrázok je po kompresii JPEG. Demonštrácia nevhodného použitia JPEG, obrázok obsahuje ostré hrany a preto miesta ostrých hrán sú zvlnené.

Tento jav vyplýva z vlastností DCT transformácie. Preto algoritmus JPEG nieje vhodný pre kompresiu grafiky obsahujúcej ostré hrany (rôzne nadpisy, geometrické útvary,...) tiež je nevhodný pre kompresiu čiernobielej a vektorovej grafiky.

4.KVANTIZÁCIA

Najdôležitejším krokom pre získanie vynikajúcich kompresných výsledkov s algoritmami JPEG je kvantizácia koeficientov po DCT. Všetky koeficienty po spektrálnej analýze sú vydelené koeficientmi kvantizačnej matice Q a zaokrúhlené na celé číslo podľa vzťahu:

Fq(u,v)=round(F(u,v)/Q(u,v))

Každá z 64 frekvencií má svoj vlastný kvantizačný koeficient. Čím je tento koeficient väčší tím viac informácie sa stratí. Naviac, sú zavádzané oddelené kvantizačné tabuľky pre jasové a farebné dáta, kde farebné dáta sú kvantované viac než jasové dáta. To dovoľuje JPEG využiť rozdielnu citlivosť oka na jas a farbu.

Kvantizacne tabulky

Obr.4: Doporučené kvantizačné tabuľky

Kvantizácia je tiež krok, ktorým je riadené nastavenie "kvality" resp. kompresného pomeru väčšiny JPEG kompresorov. Kompresor začína s kódovacou tabuľkou ktorá prislúcha strednému nastaveniu kvality. Hodnotu každého prvku kvantizačnej tabuľky potom zvyšujeme, alebo znižujeme v nepriamej úmere k požadovanej kvalite. Kompletná kvantizačná tabuľka, ktorá sa použije, je uložená do výstupného komprimovaného súboru. Dekompresor tak vie ako rekonštruovať príslušné DCT koeficienty.

Obr.5: Nasledujúci príklad ukazuje ako algoritmus JPEG spracuje blok obrazových dát veľkosti 8x8 pixelov (časť oka herečky). Pre názornosť je spracovávaný šedo tieňovaný obrázok a je použitá odporúčaná kvantizačná matica pre jasový signál.

Cameron
    Originál obrazové informácie                Matica koef. po DCT



   146 162 240 224  84  33  81  90   201.0  -5.3   5.4 -22.4  3.5  15.0  0.0  0.0

    92  84 150 146  62  27  83  94    43.8  -9.9  -2.0  25.4 -0.1 -12.8 -0.0 -4.3

    21   2  30  14   0  29 109 116    68.0  45.0 -17.6 -17.4  2.9   4.3  0.0 -0.0

    14   1  10   2  12  54 105 102   -36.0 -23.9  14.0   6.7 -3.6  -0.1 -0.1  4.8

    40  29  36  67  71  88 102 114    -6.3   0.1  -2.7  -0.0 -0.0  -0.0 -0.1  0.0

   138 131 123 143 123 128 122 136    -1.7   0.0  -4.2   0.1  6.0   0.1  0.0  0.1

   148 157 158 165 148 153 144 141     0.1   0.0   5.7   0.0  0.1   0.0 -0.0 -0.1

   160 152 156 164 155 142 139 141     5.5   6.9  -0.0   0.0  0.2   0.0  0.2  0.0



    Matica koef. DCT po kvantizácii           Rekonštruované obrazové údaje

 

    13   0   1  -1   0   0   0   0           135 193 237 206 124  66  70 100

     4  -1   0   1   0   0   0   0            85 116 135 108  60  39  66 103

     5   3  -1  -1   0   0   0   0            34  32  22   7   3  25  69 104

    -3  -1   1   0   0   0   0   0            30  11   0   0  16  53  85 103

     0   0   0   0   0   0   0   0            74  58  47  59  86 108 112 107

     0   0   0   0   0   0   0   0           127 124 125 135 146 147 136 123

     0   0   0   0   0   0   0   0           158 163 167 164 156 149 148 150

     0   0   0   0   0   0   0   0           166 174 174 159 138 134 151 171

porovnanie

5.ENTROPICKÉ KÓDOVANIE

entropicky_koder cik-cak

Po kvantizácii je koeficient DC a 63 koeficientov AC upravených pre entropické kódovanie. Pred samotným kódovaním je pole 8x8 koeficientov po DCT a kvantizácii preorganizované do postupnosti "cik-cak". Toto preorganizovanie spôsobí, že koeficienty zodpovedajúce najnižším frekvenciám sa dostávajú z ľavej hornej časti matice DCT na začiatok postupnosti "cik-cak". Ostatné, často nulové koeficienty odpovedajúce vyšším frekvenciám, vytvárajú v postupnosti "cik-cak" beh za sebou nasledujúcich núl. Ešte pripomeniem, že entropické kódovanie je bezstratové a slúži len na zníženie redundancie vstupných dát po kvantizácii. Entropické kódovanie potom prebieha v dvoch krokoch:
  -vytvorenie prechodnej postupnosti symbolov
  -zakódovanie kódom premenlivej dĺžky Huffmanovo, alebo aritmetické kódovanie

V postupnosti symbolov každý pár symbolov reprezentuje AC koeficient

         Symbol 1                  Symbol 2

      (dĺžka, počet)              (amplitúda)

  kde

  

dĺžka-je číslo určujúce počet za sebou idúcich AC koeficientov s nulovou hodnotou, ktoré predchádzajú nenulovému koeficientu AC. Hodnota parametru je v rozmedzí 0 až 15, čo si vyžaduje pre jeho reprezentáciu 4 bity.
počet-je číslo udávajúce počet bitov, pomocou ktorých je vyjadrená veľkosť koeficientu amplitúda. Počet bitov je v rozmedzí 0 až 10, takže na jeho reprezentáciu potrebujeme 4 bity.
amplitúda-udáva veľkosť nenulového koeficientu AC v rozmedzí od -1023 až po 1023, čo si vyžaduje 10 bitov na jeho reprezentáciu.

Príklad: Máme postupnosť AC koeficientov (0,0,0,0,0,0,476) a teda jej symbolická reprezentácia bude (6,9)(476) lebo dlžka=6 (nenulovému koeficientu predchádza 6 nulových) počet=9 (amplitúdu 476 môžeme vyjadriť pomocou 9 bitov 111011100 ) a amplitúda=476.

Pokiaľ by hodnota parametra dĺžka bola väčšia ako 15, potom je hodnota prvého symbolu (15,0) interpretovaná ako symbol rozšírenia s hodnotou dĺžka=16. Napríklad symboly (15,0)(15,0)(7,4)(12) budú reprezentované ako dĺžka=16+16+7, počet=4 a amplitúda=12. Za sebou môžu nasledovať maximálne tri takéto rozšírenia. Symbol (0,0) označuje koniec bloku (EOB) a slúži k ukončeniu každého bloku 8x8 bodov.

Symbolická reprezentácia DC koeficientov sa skladá s nasledovných symbolov:

            Symbol 1                          Symbol 2

            (počet)                          (amplitúda)

DC koeficienty sa kódujú diferenčne, pretože medzi DC koeficientmi susedných blokov 8x8 je silná korelácia. DIF=DCi-DCi-1 Rozsah je dvojnásobne väčší ako rozsah koefcientov AC a je to interval <-2048,2047>

Druhým krokom pri entropickom kódovaní je konverzia postupnosti symbolov do binárnej postupnosti. Jednotlivé symboly sú nahradené kódom premenlivej dĺžky. Štandard JPEG definuje dve metódy pre entropické kódovanie a to Huffmanovo a aritmetické kódovanie. Základný sekvenčný kóder/dekóder používa len Huffmanovo kódovanie. Huffmanovo kódovanie priraďuje najčastejšie sa vyskytujúcim symbolom najkratšie kódové slová. Tento kód je tiež prefixový a je teda je jednoznačne dekódovateľný. Každý symbol 1 (pre AC aj DC koeficienty) sa zakóduje pomocou kódu s premenlivov dĺžkou VLC (variable length code) podľa Huffmanovej tabuľky. Symbol 2 je zakódovaný pomocou kódu "celočíselnou hodnotou premenlivej dĺžky" VLI (variable length integer). VLC aj VLI sú kódy s premenlivou dĺžkou, ale VLI nie je Huffmanov kód. Huffmanove kódy musia byť špecifikované externe ako vstup do dekódera. Štandard JPEG uvádza príklady Huffmanových tabuliek, ale užívateľ môže v súlade so štandardom použiť svoje tabuľky. Kódy VLI sú naopak pevne dané v návrhu JPEG. Ako už bolo spomínané štandard JPEG umožňuje použiť aj aritmetické kódovanie, ktoré v porovnaní s Huffmanovým kódovaním dosahuje lepšie kompresné výsledky asi o 5 až 10%. Nevýhodou je, že tento algoritmus je veľmi náročný na aritmetické operácie.

DEKÓDER JPEG

Pri sekvenčnom JPEG dekódovaní je používaný opačný postup ako pri kódovaní. Na zakódované dáta sa použije entropický dekóder. Ten prevedie binárnu postupnosť na postupnosť symbolov pomocou kódovacích tabuliek. Potom sa symboly prevedú na postupnosť DCT koeficientov ktoré dekvantizujeme podľa vzťahu:

F(u,v)=Fq(u,v).Q(u,v)

Po dekvantizácii sa aplikuje (IDCT) inverzná diskrétna kosínusová transformácia, ktorá prevedie transformáciu s frekvenčnej oblasti do oblasti priestorových súradníc x y.

dekoder JPEG

Obr.6: Bloková schéma sekvenčného JPEG dekódera


Pogresívna komprimácia JPEG

Pri prenose rozsiahleho obrázku zloženého z veľkého množstva pixelov prostredníctvom siete, môže dekomprimácia trvať aj niekoľko minút. V takýchto aplikáciách ako je napr. WWW je vhodné čo najrýchlejšie zobraziť časť obrázku aspoň v hrubých rysoch a postupne pridávať detaily. Progresívny režim algoritmu JPEG zakóduje obrázok v postupných "vrstvách", ktoré sa postupne prekrývajú, od nízkofrekvenčného (rozmazaného) obrázku až po vysokofrekvenčný (ostrí) obrázok (spektrálny výber), alebo postupne od najvýznamnejších bitov po najmenej významné bity (postupná aproximácia), prípadne ich kombinácie.

Bezstratová komprimácia JPEG

Pri bezstratovom kódovaní sa dosahuje oveľa menší kompresný pomer, asi len 2:1. Využíva sa jednoduchá prediktívna metóda DPCM (Diferenciálna pulzne kódová modulácia), nezávislá od metódy DCT. Prediktor vytvára predikciu pomocou jedného predchádzajúceho prvku, alebo kombinuje dvoch, alebo troch susedov. Predikovaná hodnota je potom odpočítavaná od skutočnej hodnoty a rozdiel je potom kódovaný Huffmanovým alebo aritmetickým kódovaním.

Hierarchická komprimácia JPEG

Metóda hierarchickej komprimácie JPEG spočíva vo vytvorení súboru komprimovaných obrázkov začínajúcimi malými obrázkami s malým rozlíšením a končiacimi obrázkami s vysokým rozlíšením. Tento proces sa nazýva podvzorkovaním alebo pyramídovým kódovaním. Po každej fáze podvzorkovania je obrázok prispôsobený nasledujúcemu stupňu detailnejšieho rozlíšenia a je použitý pre predikciu hodnôt tejto úrovne.

Viac o týchto metódach napr. v [3]


Výhody a nevýhody formátu JPEG:

+ ukladá plnú farebnú informáciu (24 bit na pixel)
+ je vhodný na ukladanie fotografií so spojitým prechodom farieb
+ veľký kompresný pomer (väčší ako pri GIF,PNG)
+ nastaviteľná kvalita a teda aj kompresný pomer
+ JPEG predstavuje medzinárodne uznávaný štandard

- nieje vhodným pracovným formátom pretože k strate grafickej informácie (resp. zmene) dochádza pri každom uložení obrázka
- nevhodný pre kompresiu grafiky ktorá obsahuje ostré hrany
- na rozdiel od GIF neumožňuje používanie priehľadností


Vývojové trendy:

V oblasti kompresie obrazu sa stále viac do popredia predierajú algoritmy založené na tzv. vlnkovej transformácii (Wavelet Transformation). Disktrétna vlnková transformácia DWT dokáže reprezentovať obraz efektívnejšie než napríklad diskrétna kosínusová transformácia. DWT rozkladá obraz do tzv. bázových funkcií, ktoré sú obecne výhodnejšie pre reprezentáciu digitálnych signálov než sínusové alebo kosínusové funkcie. V tomto smere sa koncom roku 2000 pripravuje zverejnenie štandardu JPEG 2000. Diskrétnu kosínusovú transformáciu nahradí vlnková transformácia, ktorá umožňuje dosiahnuť vyššieho stupňa kompresie. Pribudnú aj ďalšie vylepšenia ako vodoznak, autorizácia, rôzne úrovne rozlíšenia, odolnosť proti poruchám pri prenose a iné.


Použitá literatúra:

[1] Wallace, G.K.: "The JPEG Still Picture Compression Standard", Communications of the ACM, 1991
[2] Murray, J.D., Van Ryper, W.: "Encyklopedie grafických formátů", Computer Press, 1995
[3] Čapek, J., Fabian, P.: "Komprimace dat principy a praxe", Computer Press, 2000
[4] Sestrienka, Ľ.: "Obrazová kompresia a štandard JPEG", Sdělovací technika č.8/1992
[5] Jiráček, M.: "Standard komprese JPEG", Sdělovací technika č.4/2000
[6] Sobota, B., Milán, J.: "Grafické formáty", Koop, 1996
[7] http://www.jpeg.org - domovská stránka skupiny JPEG


[hlavná strana]

Dušan SOVIČ