JPEG pro mírně pokročilé. - Grafika.cz - vše o počítačové grafice

15. ledna 1998, 00.00 | Minule jsme si zlehka přiblížili, co znamená výraz ztrátová komprese. Trochu jsme opomněli další skutečnosti, které algoritmy pro kompresi obrazu používají. Podívejme se tedy na ně.

Minule jsme si zlehka přiblížili, co znamená výraz ztrátová komprese. Trochu jsme opomněli další skutečnosti, které algoritmy pro kompresi obrazu používají. Podívejme se na ně.

Redundantní informace je informace, kterou si pamatujeme vícekrát než je potřeba. Vezměme si malý příklad; představme si fotografii krajiny. Nahoře je čistá obloha bez mráčků. Je to velká plocha, na které se barva téměř nemění. Zakódujme tuto informaci takto: Tento pixel je skoro stejný jako ten vlevo jen se o něco liší, tento je tmavší. Slovem pixel označuji jednotlivé body v bitmapě, v mozaice bodů popisující obrázek.

Kdyby byly vedlejší pixely úplně jiné barvy, neušetřili bychom zhola nic. Jenže to se na reálných fotografiích nestává. Většina přechodů je plynulá a vysoce kontrastních hran je málo. Díky tomu jsme schopni ušetřit paměť. Abychom si pamatovali barvu jednoho bodu, potřebujeme jistý kus paměti - například 24 bitů. Pokud si řekneme: "Sousední pixely se liší nejvýš o osminu rozsahu v každé barvě", stačí nám ke schování informace méně než polovina místa.

Možná teď uvažujete takto: Pamatovat si jen rozdíly. To je rozumná myšlenka. Bezpochyby ji používají pro kompresi i ty algoritmy, které nejsou určeny ke kompresi obrazu. Proč je tedy nepoužijeme a vymýšlíme další formát souborů. Copak už jich není dost? Kdo se v nich má vyznat?

Pochopitelně uvažujete správně. Je tady ale jedna vlastnost, kterou běžný kompresní algoritmus nevyužije. Sousední body jsou podobné nejen ve směru horozontálním, tedy po řádcích, ale i ve směru vertikálním, tedy po sloupcích. Pokud programu nesdělím, že data co mu dávám, jsou obrázek, nemůže nikdy vědět, které dva pixely obrázku jsou pod sebou. Je to dáno typickým způsobem uložení obrázku v paměti.

Rozhodli jsme se, že využijeme podobnosti barev u vedlejších pixelů nahoře, dole i po stranách a uložíme jen rozdíly barev. Teď si povíme, jak je to ve skutečnosti uděláno.

Celý obrázek si rozstříháme na čtverečky velikosti osm krát osm pixelů. Toto opatření vůbec nesouvisí s úvahami, které jsme dělali doposud. Důvody jsou tři. Chceme, aby byl algoritmus byl jednoduchý. Když bude pracovat pokaždé se stejně velikou ploškou, podaří se nám ho napsat lépe. Nechceme, aby chyby způsobené při zaokrouhlování na tomto místě kazili vzhled obrázku na místě vzdáleném. Takto se chyby projevují jen v rámci čtverečku. Chceme používat experimentálně zjištěné koeficienty. Je tedy vhodné aby byly uloženy v pevně dané tabulce a nemusely se složitě počítat.

Na každé takto vzniklé plošce provedeme dvojrozměrnou diskrétní kosinovou transformaci. Její vnitřní funkce bude:

J(x,y,u,v) = f(x, y) / 4 * [ cos(x * Pi / 8 + Pi / 16) * u + cos(y * Pi / 8 + Pi / 16) * v ]

Funkce f(x,y) není nic jiného než hodnota barvy, která se nachází v plošce na souřadnicích x,y. Transformovanou funkci F(u, v) získáme tak, že funkci J posčítame přes celou plošku s hodnotami x,y od 0 do 8. Toto postupně provádíme pro hodnoty u, v ve stejných mezích. Ještě je třeba výsledek pro u = 0 a v = 0 podělit odmocninou ze 2. Nakonec dostaneme opět plošku o rozměrech 8x8 bodů.

Jak jsme si tím pomohli? Takto. Zatím jsme sice nic neušetřili, ale data teď mají zcela jiný význam. Bod o souřadnicích 0,0 je průměrná hodnota barvy na celé plošce. Ostatní body nesou informaci o tom, jak se odstín mění. Čím je vyšší index, tím zachycuje prudší změny.

Teď využijeme velké korelace barev sousedních bodů, jejich podobnosti či závislosti. Vysoké frekvence na typické fotografii nejsou příliš podstatné a mají malou amplitudu, tak je budeme uschovávat s menší přesností. K tomu použijeme experimentálně zjištěnou tabulku. Je nesymetrická podle úhlopříčky a obsahuje koeficienty určené podle dojmů lidí. Mnoha lidem byly ukazovány mnohé fotky zarušené různými frekvencemi a zjišťovalo se co má větší rušivý vliv.

Tabulka udává poměrné informace o tom, co je důležitější a co méně. Pro různé stupně komprese se potom ještě dále upraví, tak aby přímo značili počet zaznamenaných bitů. To je hodnota, kterou z vnějšku určujeme ztrátovost metody. Rozumné výsledky jsou stále ještě i při ušetření 80% původního množství dat.

Ještě se vraťme ke koeficientu (0,0), ten musíme zaznamenat s maximální přesností, jinak by došlo ke ztrátě barevného rozlišení. U jiných koeficientů narozdíl od tohoto přicházíme jen o strmost přechodů a ne o barevnou hloubku. Koeficient (0,0) je důležitější.

I zde ovšem chci ušetřit paměť. Vzpomenu si, že sousední pixely se moc neliší. Podobně ani průměrná barva sousedních plošek se nemusí moc lišit. Protože musíme být opatrnější, než v předchozím kroku, budeme volit místo ztrátové komprese kompresi bezeztrátovou. Případná chyba v tomto kroku by se promítla na příliš mnoho pixelů najednou a to je nežádoucí.

Barvu plošky budu odvozovat jedním ze sedmi způsobů od barev plošek nahoře a vlevo. Osmý způsob je nic nepredikovat a zapamatovat si barvu tak jak je. Potřebujeme ho minimálně pro pixel zcela vlevo nahoře. Tímto kódováním jsme schopni ušetřit až 66% paměti používané těmito "pixely".

To o čem jsme se doposud bavili stačilo pro černobílý obrázek. Pokud chceme zachytit barevný obrázek, musíme uschovat tři jeho barevné složky. Abychom opět šetřili místem, použijeme stejného triku jako se využívá v barevném televizním vysílání. Naše tři složky budou JAS, "modrost" a "červenost" (Y,cb,cr)

Y = 0.3 R + 0.59 G + 0.11 B

cb = -0.17 R - 0.33 G + 0.5 B + 128

cr = 0.5 R - 0.42 G - 0.08 B + 128

Koeficienty v těchto vzorcích jsou zaokrouhleny. Je to spíš ilustrace toho, co který pojem znamená.

Teď nám stačí uvědomit si, že lidské oko je mnohem citlivější na změnu jasu, než na změnu barvy. Budeme tedy jas zaznamenávat v plném rozlišení, jaké má vstupní obrázek a barvu jen v polovičním rozlišení v obou směrech. Tím jsme ušetřili 50% místa, za cenu nepříliš viditelných barevných změn na obrázku.

Posledním krokem je klasická slovníková komprese podobná algoritmu LZW používaného ve formátu GIF. Tato komprese už nevyužívá vlastností typických pro obrázek, proto se jí zabývat nebudeme. Tímto algoritmem se dá ušetřit řádově 50% místa.

Specifikace metody JPEG ještě zahrnuje bezeztrátovou formu komprese, která je založena na stejném principu jako bezeztrátové kódování bodů (0,0). Dále počítá s progresivním kódováním. Možnost poskytnout nejprve malé množství dat, které odpovídají obrázku v malém rozlišení či s velkými ztrátami. Je to vhodné při stahování obrázků po sítích jako je Internet.

Tímto jsem vyčerpal všechny podstatné principy, které jsou v algoritmu JPEG použity. Podrobnější informace potřebuje jen ten, kdo by měl použití tohoto grafického formátu naprogramovat, a ani to není zcela jisté. Pokud by se přeci někdo cítil ošizen, nemusí zoufat. Připravujeme článek JPEG v příkladech, ve kterém se tímto formátem budeme dále zabývat.

Literatura:

[i] Pelikán J. Počítačová grafika II,III

[ii] Klíma M., Berans M., Hozman J., Dvořák P. Zpracování obrazové informace Praha Vyd. ČVUT 1996.