Do hlubin JPEG - Builder.cz - Informacni server o programovani

Navigace:  » Úvodní stránka  » Rubriky  » C/C++  

4. prosince 2002, 00.00 | Tento článek je určen
především lidem, kteří se nespokojí s informací, že JPEG je ztrátová
komprese a chtějí se dozvědet pokud možno srozumitelnou formou jak přesně tato
komprese funguje a jak lze jejich vlastností využít ve svůj prospěch.

JPEG v první řadě není přímo algoritmus, ale je to standard, který vyvinula Joint Photographic Expert Group – standard, a popisuje mechanizmus jak za pomocí konkrétní transformace (DCT) lze převést data z bitmapy t.j rastrového formátu do tzv.  frekvenčního formátu, který lze popsat matematickým vzorcem, jenž je docela snadno přenosný.

klasická bitmapa bmp	zkomprimovaný obraz
Pix1: R=250 | G=15 | B=0	R = 250 – 50*x
Pix2: R=200 | G=30 | B=0	G = 15 + 15*x
Pix3: R=150 | G=45 | B=0	B = 0 + 0*x
Pix4: R=100 | G=60 | B=0
Pix5: R=50 | G=75 | B=0

Všechny osoby a charaktery v této tabulce jsou zcela vymyšleny a neodpovídají skutečnosti... Je ale doufám zřejmé, co je podstatou ukládání dat za pomoci různých algoritmů, tj. že při bitmapových datech(vlevo) musíme na cílový počítač přenášet informace o hodnotě třeba kanálu R pro každý(!) bod v řádku, pomocí funkce(vpravo) přenášíme jen pár koeficientů této funkce(x je pozice konkrétního bodu)

  Pečlivému pozorovateli neunikne hned první nevýhoda JPEG formátu a to že obrázek jako takový se nedá rovnou zobrazit ale je nutné jej vypočítat! To jest přijatá data jsou víceméně pouze sada vzorečku, z nichž je nutno získat pozici a zastoupení RGB zložek pro každý pixel, aby to pak zobrazovací systém, pracující více méně jen s hodnoty RGB, dovedl zobrazit.

Jak to tedy vlastně funguje:
Teď musím zklamat nadšence čtoucí tento článek v jednom okně a zároveň připravenými psát dekoder pro JPEG v druhém. Protože JPEG standard je chráněn ISO a ITU Copyright–em není možné uveřejnit přesný popis. Ale pro pochopení se mi zdá zcela dostačující schéma, které kdysi popsal Tom Lane:

Krok 1 : Transformace obrázku do vhodného systému barev:

RGB      -->        HSL

smyslem této procedury je fakt, že lidské oko je schopno rozlišit velice přesně změny na ose L (lightness na obrázku vpravo) - v odstínu barvy, ale velice špatně vnímá změny na osách S a H(saturation a hue), které definují barvu jako takovou. Důsledkem takovéto transformace je skutečnost, že pak si můžeme dovolit velice silnou kompresi a ztráty dat na osách S a H aniž by si toho pozorovatel obrázku všiml. Také již při této transformaci barevných systémú vzniká jistá ztráta informací v důsledku zaokrouhlovaní. Rád bych ještě upozornil, že HSL model je zde uveden jen jako jeden z možných modelů,  které zohledňují os L t.j. světlost. Většinou se užívá označení YCbCr nebo YUV kde Y je tzv. luminance a zbývající dvě jsou „chrominance“ komponenty jenž popisují barvu.

Krok 2: Zjednodušení os H a S Zde dochází už ke zcela markantní ztrátě dat témeř 50% na osách S a H. Pro běžného uživatele je tenhle fakt nepozorovatelný ze stejného důvodu ovšem osa L musí zůstat bez zásahu.

Krok 3: Sloučení bodů do bloku 8x8 a vyjádření pomocí frekvenční funkce
Matice obrázku(raster)je rozdělena v tomto kroku na bloky o velikosti 8x8 pixelů. Každý 8x8 blok se pak převádí z tzv. údajů signálu (hodnot H,S,L) na frekvenční údaje DCT (Discrete Cosine Transform). Co obnáší tenhle krok: skutečné hodnoty jednotlivých políček v bloku se dají všeobecně popsat funkcí a posléze namísto reálných hodnot ukládat a přenášet jenom koeficienty této funkce.
Proč 8x8 : zde jsem se dopátral dvou vysvětlení (výběr ponechávám na čtenáři):
I -  technika JPEG je tzv. “memory based“ t.j. je velice vhodné a praktické když se pracuje s maticí o velikosti 64 komponent
II – samotná DCT transformace je založena na sumě celé řady t.j. všech částiček, což je při větším rozsahu  časově i hardwarově náročné. Přinejmenším bylo v období vzniku JPEG.

Krok 4: KOMPRESE!
Tak tady to je přátelé. Jelikož samotný převod reálných dat do frekvenční mapy není s přimhouřením oka vůbec ztrátový (jediné ztráty vznikají ze zaokrouhlování) je nutno nějakou tu ztrátu udělat, jinak by to přece nemohla být ztrátová komprese. :-)
Každý ze 64 získaných frekvenčních koeficientů z kroku 3 se vydělí příslušným kvantizačním koeficientem z tzv. kvantizační matice. Tohle je základní ZTRÁTOVÝ KROK protože koeficienty jsou poté přenášeny s menšími nároky na paměť. Koeficienty vycházející z DCT transformace jsou běžně v rozmezí od -1024 do 1023. Což odpovída zhruba 11 bitům paměti. Nejmenší koeficient kvantizační tabulky je kolem 10, takže největší přenášený koeficient by měl zabírat cca 8 bitů a ostatní přirozeně méně.

Krok 5: Další kódování
Následným krokem v cestě za nejmenší velikostí souboru je další kódování koeficientů pomocí VLC( Variable Length Coding). Používá se zde buď Huffmanovo nebo aritmetické kódování přičemž druhé je patentováno(rozuměj  placeno). Principem je přiřazení nejkratší délky slova nejčastěji se vyskytujícímu znaku. Naopak řídce se objevujíci znaky se kódují dlouhými slovy. Tenhle krok už je beze ztrát. A to je vše. Získané koeficienty se pak spolu s příslušnými hlavičkami, kvantizačními tabulkami uloží do souboru.

Pár vět na závěr: Síla - neboli intenzita komprese vzniká aplikováním nebo škálováním (scale) kvantizačních tabulek. Je samozřejmě možné používat specialní nebo taky vlastní kvantizační tabulky. Většina dnešního softwaru ovšem používá "klasické" uvedené v normě a při zadávání intenzity komprese jednoduše zvětšuje nebo zmenšuje koeficienty. Nejpodstatnější část komprese JPEG t.j. diskrétní kosinová transformace je už díky dnešnímu výkonnému HW překonaná resp. je čím dál tím víc vytlačována tzv. wavelet kompresí. Ale JPEG ovšem není nejlepší možný řešení komprimace grafiky - je to standard, potažmo dohoda ve smyslu "..já to udělám takhle a Ty pak budeš vědět jak to rozkódovat a poběží to na libovolném stroji." Nicméně v dohledu je nový standard JPEG 2000, který by už měl fungovat na principu waveletu, ale o tom snad až příště.

Zdroje:
www.faqs.org/faqs/compression-faq
Wallace, Gregory K " THe JPEG still Picture Compression standart"
www.volny.cz/mills1/digital/
Amaterske radio B/4 1996
www.ece.purdue.edu