Kompresný štandard JPEG
- História vzniku
- Úvod
- Štyri spôsoby činnosti (módy)
- Sekvenčný JPEG kóder
- TRANSFORMÁCIA FARIEB
- PODVZORKOVANIE
- DCT (Diskrétna kosínusová transformácia)
- KVANTIZÁCIA
- ENTROPICKÉ KÓDOVANIE
- DEKÓDER JPEG
- Výhody a nevýhody formátu JPEG
- Vývojové trendy
- Použitá literatúra
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.
- sekvenčné DCT kódovanie, pri ktorom je každý prvok obrázku zakódovaný v jednom prechode zľava doprava, z hora nadol
- progresívne (postupné) DCT kódovanie, pri ktorom je obrázok zakódovaný v rámci niekoľko prechodov cez originál, ktorého cieľom je poskytnúť rýchlo aspoň hrubý náčrt
obrázku, pokiaľ je celkový čas prenosu dlhý
- bezstratové kódovanie, v prípade, že chceme zachovať verný obraz originálu
- hierarchické kódovanie, pokiaľ chceme získať obrázok s rôznym rozlíšením
Sekvenčný JPEG kóder
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.
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
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:
Pre bloky 8x8 bodov, môžeme zostaviť 64 základných funkcií DCT.
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).
 |
 |
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.
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.
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
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.
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é.
)window.location='http://www.jpeg.org/JPEG2000.htm'){kind=link}
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
)window.location='http://www.jpeg.org/'){kind=link}