ČVUT - FEL - Semestrální práce - Algoritmy počítačové grafiky

Hlavní stránka » Osobní » ČVUT - FEL » Semestrální práce a referáty » Algoritmy počítačové grafiky

České vysoké učení technické v Praze

Fakulta elektrotechnická





Semestrální práce

Algoritmy počítačové grafiky



1996/1997 (zimní semestr) Marek Uher



Obsah:

  1. Zadání
  2. Zadavatel
  3. Vypracoval
  4. Teoretické řešení
    4.1 Historie vzniku
    4.2 Úvod do problematiky
    4.3 Principy JPEG
    4.4 Kompresní schéma JPEG
    4.5 Transformace předlohy
    4.6 Podvzorkování barevných komponent
    4.7 Diskrétní kosinová transformace
    4.8 Kvantizace DCT
    4.9 Kódování výsledných koeficientů
    4.10 Přiklad JPEG komprimace
    4.11 Problémy JPEG
  5. Praktické řešení
    5.1 Výukový program JPEG Analyser
    5.2 JPEG knihovna
    5.3 Informace k programům
  6. Ke stažení
  7. Odkazy
  8. Literatura



1. Zadání

  Prostudujte obrazový formát JPEG a vytvořte výukový program prezentující způsob zpracování a ukládaní obrázku. Vedlejším efektem Vaší práce bude dokumentovaná programátorská knihovna pro načítání a zápis obrázku ve formátu JPEG.



2. Zadavatel

  prof. Ing. Jiří Žára, CSc. / Ing. Martin Brachtl



3. Vypracoval

  Marek Uher, IV. ročník / studijní skupina 29.



4. Teoretické řešení



  4.1 Historie vzniku

  Zkratka JPEG znamená Joint Photographic Experts Group, což je komise pro standardy pod International Standard Organization (ISO).

  V roce 1982 vytvořila ISO skupinu PEG (Photographic Expert Group), která měla zkoumat metody pro přenos videa, nehybných předloh a textu pres ISDN (International Services Digital Network). Cílem PEG bylo vytvořit sadu průmyslových standardů pro přenos grafických dat a formátů předloh vhodných pro přenos v digitálních komunikačních sítích.

  V roce 1986 začala podskupina CCITT (International Telegraph and Telephone Consultative Committee) zkoumat metody komprese barevných a šedě odstupňovaných dat pro přenos faksimilií. Kompresní metody navržené pro barevný faksimilní systém byly velmi podobné těm, které zkoumala skupina PEG. Proto bylo následně rozhodnuto, že obě skupiny začnou pracovat dohromady a budou se snažit vyvinout společný standard.

  V roce 1987 byly skupiny ISO a CCITT spojeny do společné komise pod názvem JPEG.



  4.2 Úvod do problematiky

  Na rozdíl od všech ostatních kompresních metod není JPEG samostatný kompresní algoritmus. Může být brán jako sada kompresních metod, které mohou být přizpůsobovány daným požadavkům uživatele.

  JPEG je také jiný v tom, že je to už od základu ztrátová kompresní metoda. Do této doby používané kompresní metody (RLE, LZW, nebo standardy CCITT) jsou kompresní metody neztrátové. To znamená, že nedojde během komprese ke ztrátě jakýchkoliv dat. Předloha komprimovaná neztrátovou metodou zaručuje, že je naprosto identická s nekomprimovanou předlohou.

  Ztrátová schémata však během kódování odhazují nepotřebná data pryč. To je také důvod, proč ztrátová schémata dosahují mnohem lepších kompresních výsledků než schémata neztrátová. JPEG byl vytvořen tak, aby se ztrácely pouze informace, které může lidské oko vidět jen velmi obtížně. Malé změny barev není lehké lidským okem rozeznat tak, jako změny v intenzitě (tzn. rozdíl mezi světlým / tmavým). Proto ztrátové kódování JPEG zachází šetrněji s těmi částmi předlohy, které jsou v odstínech šedi. Naopak s barevnými částmi zachází lehkomyslněni.

  JPEG byl vytvořen hlavně kvůli komprimaci barevných, šedě odstínovaných, spojitě tónovaných předloh reálných předmětů: fotografií, video snímků nebo jakýchkoliv složitých grafických předloh znázorňujících reálný předmět. Animace, raytracing, line art, černobíle dokumenty a běžná vektorová grafika se pod JPEG nekomprimují tak dobře a taky se nepředpokládá, že by měly. Ačkoli se dnes JPEG používá ke kompresi pohyblivých video obrázků, není pro tyto aplikace vytvořen zatím žádný standard.

  Výsledný kompresní poměr závisí na obsahu předlohy. Běžná fotografická předloha může být komprimována v poměru 20:1 až 25:1 bez výrazné ujmy na kvalitě předlohy. Vyšší poměry mají za následek určitou kvalitativní ztrátu, ale stále můžeme výsledné zkomprimované předlohy považovat za velmi dobré. Kompresní poměr okolo 20:1 v mnoha případech nejen šetří místo na disku, ale rovněž zkracuje přenosový čas v datové síti a na telefonních linkách.



  4.3 Principy JPEG

  Specifikace JPEG definuje minimální úroveň standardu - základ JPEG. Tento standard vyžaduje, aby všechny aplikace pracující s JPEG podporovaly tento minimální základ. Standard JPEG používá pro dosažení komprimace kódovací schéma založené na Diskrétní Kosinové Transformaci (DCT). DCT je všeobecné jméno pro třídu matematických operací definovaných a publikovaných před několika lety. Algoritmy založené na DCT si od svého publikování již našly svou cestu do různých (nejen grafických) kompresních metod.

  DCT algoritmy nejsou ztrátové, ztrátový je až proces kvantizace. Proces kvantizace je ta část zpracování, kde se dosahuje vysokých kompresních poměrů při ztrátě jen velmi malého počtu dat. DCT algoritmy jsou navrženy výhradně pro předlohy se spojitým tónováním, kde je pouze minimální rozdíl mezi sousedními pixely. JPEG pracuje velmi dobře s předlohami, které mají hloubku nejméně čtyři nebo pět bitů na barevný kanál. Standard JPEG specifikuje osm bitů na každý vstupní vzorek. S daty o menší bitové hloubce se zachází tak, že se jejich hloubka zvětší na osm bitů na každý vzorek. Výsledek komprimace pomocí JPEG však není příznivý pro zdrojová data o hloubce s malým počtem bitů kvůli příliš velkým skokům mezi hodnotami sousedních pixelů. Z podobných důvodu se také nedosahuje dobrých výsledků při komprimaci barevně mapovaných zdrojových dat (zejména pak v tom případě, kdy byla předloha ditherována).



  4.4 Kompresní schéma JPEG

Obr. č. 1 - Kompresní schéma JPEG

  Kompresní schéma JPEG obsahuje následující kroky zpracování předlohy:

  1. Transformace předlohy do optimálního barevného prostoru
  2. Podvzorkování barevných komponent průměrováním sousedních skupin pixelů
  3. Zavedení DCT na blok pixelů, což má za následek odstranění redundantních dat předlohy
  4. Kvantizace každého bloku DCT koeficientu použitím váhových funkcí, které jsou speciálně uzpůsobeny potřebám lidského oka
  5. Kódování výsledných koeficientů (dat předlohy) použitím Huffmanova algoritmu nebo aritmetického binárního kódování, což má za následek odstranění redundance v koeficientech



  4.5 Transformace předlohy

  JPEG algoritmus je schopen kódovat předlohy, které používají jakýkoliv typ barevného modelu. Vlastní JPEG kóduje každou součást barevného modelu zvlášť a je tak proto zcela nezávislý na použitém barevném modelu. JPEG tak může pracovat v barevném modelu RGB, HSI nebo CMY. Nejlepších kompresních poměrů se ale dosahuje v případě jasového / chromatického barevného modelu, jako je například barevný model YUV a nebo YCbCr.

  Většina vizuálních informací, na které je lidské oko nejvíce citlivé, se vyskytuje na nízkých frekvencích šedě odstupňovaných jasových komponent (Y) barevného modelu YCbCr. Další dvě barevné komponenty (Cb a Cr) obsahují barevné informace o velmi vysoké frekvenci, na které je lidské oko méně citlivé. Většina těchto informací tak může být odstraněna.

  Oproti tomu barevné modely RGB, HSI a CMY mají rozptýleny užitečné vizuální informace o předloze rovnoměrně přes všechny tři barevné komponenty, což podstatně ztěžuje selektivní odstraňování informací. V takovém případě musí být všechny tři komponenty kódovány nejvyšší kvalitou, což má za následek menší kompresní poměr. Předlohy vytvořené odstíny šedi neobsahují žádné barevné prostředí, a proto nevyžadují jakoukoliv transformaci.

  Převod mezi barevným prostorem RGB a prostorem YCbCr je dán jednoduchým lineárním vztahem. Pro transformaci do barevného prostoru YCbCr platí vztah:

  Zpětný převod je určen následující transformací:

  Předchozí převod odpovídá digitálnímu zpracování, kdy je každá barevná složka zapsána v 8 bitech, tedy v rozsahu 0 - 255. Podle standardu CCIR-601 má být hodnota Y v intervalu 0.0 - 1.0 a hodnoty Cb, Cr v intervalu −0.5 - 0.5.

  Přibližně lze definovat hodnoty Cb a Cr jako:

Cb = 0.50198 (B - Y) + 128

Cr = 0.71606 (R - Y) + 128



  4.6 Podvzorkování barevných komponent

  Nejjednodušším způsobem, jak využít menší citlivosti lidského oka na určité barevné informace, je prostě použití menšího počtu pixelů v barevných kanálech. Například v předloze o velikosti 1000 x 1000 pixelů můžeme použít všech 1000 x 1000 jasových bodů, ale pouze 500×500 pixelů pro každou barevnou komponentu. V takové podobě každý barevný pixel zabírá stejnou plochu jako 2 x 2 bloku jasových pixelů. Ukládáme celkem šest pixelových hodnot pro každý blok 2 x 2 (4 jasové hodnoty, každá pro dva barevné kanály). Nepotřebujeme tedy dvanáct hodnot, pokud je každá komponenta reprezentovaná s plným rozlišením. Tato 50% úspora v datech nemá skoro žádný vliv na kvalitu většiny předloh. Tyto úspory nejsou možné u konvenčních barevných modelů jako je RGB, protože RGB v tomto modelu obsahuje pro každý barevný kanál nějaké jasové informace, a proto je jakýkoli zásah do nich ihned viditelný.

  Pokud jsou nekomprimovaná data dodávána v konvenčním formátu (stejné rozlišení pro všechny kanály), musí JPEG komprimátor zredukovat rozlišení barevných kanálů podvzorkováním nebo zprůměrováním skupiny pixelů. JPEG standard poskytuje několik různých možností pro vzorkovací poměry nebo relativní velikosti podvzorkovaných kanálů. Jasovému kanálu se většinou nechává plné rozlišení (vzorkování 1:1). Oba barevné kanály jsou běžně podvzorkovány 2:1 vodorovně a 1:1 nebo 2:1 svisle, což znamená, že barevný pixel zabírá stejnou plochu jako blok o velikosti 2 x 1 nebo 2 x 2 jasových pixelů. JPEG se odvolává na tyto podvzorkovací procesy jako na vzorkování 2h1v a 2h2v

  Další běžně užitými zápisy je vzorkování 4:2:2 pro 2h1v a vzorkování 4:2:0 pro 2h2v. Tento zápis je odvozen z televizních norem (barevná transformace a podvzorkování se používají už od těch dob, co byl vynalezen přenos barevného televizního signálu). Vzorkování 2h1v je velmi rozšířené, protože odpovídá TV standardu NTSC (National Television Standard Commitee). Poskytuje však menší kompresi, než vzorkování 2h2v bez jakéhokoliv viditelného zvýšení kvality.



  4.7 Diskrétní kosinová transformace

  Data předlohy jsou při zpracování rozdělena do bloku 8 x 8 pixelu (od tohoto okamžiku je každá barevná komponenta brána nezávisle, takže “pixel” znamená jedinou hodnotu, a to i v barevné předloze). Na každý z těchto 8 x 8 bloků je pak následně zavedena DCT. DCT konvertuje prostorovou reprezentaci do frekvenční mapy. Termín low-order (někdy též DC) znamená u tohoto kroku zpracování průměrnou hodnotu v bloku, zatímco termín higher-order (někdy též AC) představuje více radikálních změn, co se týká šířky a výšky bloku. Nejvyšší hodnota AC reprezentuje sílu kosinové vlny, která se mění z maxima na minimum na sousedních pixelech.

  Výpočet DCT je velmi složitý a v podstatě představuje nejnáročnější krok v JPEG kompresi. Účelem DCT je oddělení informaci o vysoké a nízké frekvenci obsažených v předloze. DCT ve svém výsledku odstraňuje data s vysokou frekvencí tak, aby současně data s nízkou frekvencí byla zachována. Vlastní krok DCT je neztrátový (mimo zaokrouhlovacích chyb).

  Dopředná diskrétní kosinová transformace (FDCT) se počítá podle vztahu:

  Kde C(u), C(v) je rovno druhé odmocnině ze dvou pro u,v=0, resp. 1 jinde. Zpětná (inverzní) diskrétní kosinová transformace (IDCT) se počítá podle vztahu:



  4.8 Kvantizace DCT

  K tomu, aby byla odstraněno přiměřené množství informací, vydělí DCT každou výstupní hodnotu kvantizačním koeficientem a výsledek zaokrouhlí na celé číslo. Čím větší je tento kvantizační koeficient, tím více dat se ztratí, protože aktuální DCT hodnota je reprezentovaná stále méně přesněji. Každá ze 64 pozic výstupního bloku má svůj vlastní kvantizační koeficient, higher-order členy jsou kvantizovány mnohem více, než low-order koeficienty (mají větší kvantizační koeficienty). Navíc jsou zaváděny oddělené kvantizační tabulky pro jasová a barevná data, kde barevná data jsou kvantizována více, než data jasová. To dovoluje JPEG využít rozdílnou citlivost na jas a na barvu.

  Kvantizace je také krok, který je řízen nastavením “kvality” většiny JPEG kompresorů. Kompresní procesor začíná s budováním tabulky, která přísluší střednímu nastavení kvality. Hodnotu každého tabulkového vstupu posléze zvyšuje nebo snižuje v nepřímé úměře k požadované kvalitě. Kompletní kvantizační tabulka, která se bude používat, je uložena do zkomprimovaného souboru. Dekompresor tak má k dispozici informaci, jak rekonstruovat příslušné DCT koeficienty.



  4.9 Kódování výsledných koeficientů

  Výsledné koeficienty v sobě obsahují velké množství redundantních dat. Neztrátově dokáže tuto redundanci odstranit Huffmanova komprese, což vede ke zmenšení JPEG dat. Namísto Huffmanova kódování se může také použít jiných volitelných rozšíření JPEG specifikace, např. aritmetického binárního kódováni, které dosahuje dokonce většího kompresního poměru. Po aplikaci Huffmanova kódování nebo aritmetického binárního kódováni je JPEG tok dat připraven k přenosu v komunikačních kanálech nebo k uložení do formátu souboru předlohy na disk. V současné době existují dva formáty souboru: JPEG FIF (File Interchange Format) a TIFF od verze 6.0.



  4.10 Přiklad JPEG komprimace

  Na následujících příkladech je ukázáno, jak JPEG komprese zachází s různými druhy obrazových předloh.

  Příklad č. 1 - spojitě tónovaná fotografie (portrét dívky)

     
Q = 100   Q = 75   Q = 45   Q = 15
13 876 B   3 249 B   2 229 B   1 462 B
       
  Q = 10   Q = 5   Q = 1  
  1 296 B   1 111 B   1 015 B  

  Příklad č. 2 - spojitě tónovaná fotografie (krajina)

     
Q = 100   Q = 75   Q = 45   Q = 15
19 051 B   5 104 B   3 358 B   1 873 B
       
  Q = 10   Q = 5   Q = 1  
  1 572 B   1 214 B   1 067 B  

  Příklad č. 3 - vektorová kresba (barevná)

     
Q = 100   Q = 75   Q = 45   Q = 15
10 229 B   3 831 B   2 955 B   2 042 B
       
  Q = 10   Q = 5   Q = 1  
  1 817 B   1 554 B   1 444 B  

  Příklad č. 4 - vektorová kresba (černobílá)

     
Q = 100   Q = 75   Q = 45   Q = 15
4 852 B   2 315 B   1 836 B   1 319 B
       
  Q = 10   Q = 5   Q = 1  
  1 200 B   1 037 B   971 B  



  4.11 Problémy JPEG

  JPEG není vždy tím ideálním řešením. Existuje několik případů, kdy není vhodné kompresi JPEG použít.

  Jak už bylo uvedeno, JPEG nesplňuje úplně všechny nároky kladené na kompresi dat. Například předlohy obsahující rozsáhlé oblasti jediné barvy nejsou komprimovány zcela dobře. Do takových předloh zavádí JPEG artefakty, které jsou viditelné proti jasnému pozadí. Takto zakódované předlohy potom vypadají mnohem hůře, než předlohy zakódované některou z klasických neztrátových metod. Předlohy, které mají rušnější kompozici obsahují po kompresi ještě horší artefakty, ale ty jsou mnohem méně zřetelné na složitějším pozadí předlohy.

  Metoda JPEG je docela pomalá, pokud je implementována pouze softwarově. Pokud požadujeme rychlejší dekompresi, je nejlepším řešením hardwarová implementace JPEG. Je možné samozřejmě také počkat na rychlejší softwarovou verzi, anebo si koupit rychlejší počítač.

  Nainstalovat JPEG do vlastního programu není až tak jednoduché. Už vůbec si nemůžete jenom tak sednout a napsat si za pár večerů svůj vlastní kodér / dekodér. Raději si opatřete již hotovou JPEG knihovnu, než abyste psali svou vlastní.

  JPEG dosud není podporován příliš mnoha formáty souborů. Formáty, které s JPEG pracují, jsou nové a očekává se, že budou velmi často revidovány



5. Praktické řešení



  5.1 Výukový program JPEG Analyser

  Program JPEG Analyser umožňuje sledovat jednotlivé kroky kompresní metody JPEG pomocí výpisu matic jednotlivých fází. Standardně dovoluje nastavovat koeficient kvality, který se používá při kvantizaci koeficientu po aplikování DCT. Neumožňuje však volit způsob vzorkování barevných kanálů Cb a Cr. Implementována je pouze metoda 2h2v (4:2:0). Jako vzorek pro aplikaci JPEG je určeno pole 8 x 8 pixelu. Toto pole je možné modifikovat pomocí jednoduchého kreslícího nástroje. Program v současné verzi pracuje pouze v odstínech šedi. Do budoucna lze případně program rozšířit o práci v RGB modelu v 24-bitové hloubce na pixel (true color).

Obr. č. 2 - Program JPEG analyzer v2.0 (screenshot)

  Hardwarové a softwarové nároky programu jsou následující:

  • Hardware:
    • PC/AT i386 nebo kompatibilní procesor (matematický koprocesor nutný)
    • 8 MB RAM
    • SVGA karta (min. 1MB VESA kompatibilní)
    • MS Mouse / Genius Mouse kompatibilní myš
    • 2 MB volného místa na HDD
  • Software:
    • Operační systém MS-DOS 5.0 a vyšší nebo DR-DOS 6.0 a vyšší



  5.2 JPEG knihovna

  Pro vývojáře je volně k dispozici programátorská knihovna v jazyce C pro načítání, ukládání a konverzi z / do JPEG, která podporuje celou řadu formátů obrazových předloh jako například Targa, BMP, GIF a další. Tato knihovna je distribuována pod licencí GNU a je přenositelná na řadu operačních systémů (Linux, UNIX, OpenVMS, MS DOS, DR DOS, OS/2, MS Windows, …). Součástí distribuce je dokumentace a skripty pro překlad pod nejznámějšími překladači programovacího jazyka C (Watcom, gcc, Borland, Symantec, Microsoft, …). Tuto knihovnu si můžete bezplatně stáhnout ze stránek Independent JPEG Group.



  5.3 Informace k programům

  Program JPEG analyzer již není dále vyvíjen ani udržován a podpora na něj se neposkytuje.

  Program byl vytvořen v překladači Borland C/C++ verze 3.1 v operačním systému MS-DOS 5.0.

  V případě, že se vyskytnou problémy s JPEG knihovnou, tak kontaktujte přímo Independent JPEG Group na adrese uvedené v dokumentaci dodávané společně s knihovnou.



6. Ke stažení

 
Binární verze Ano Ano1 Ano2 Ano2 Ano2 Ano2 Ano2
Zdrojové kódy Ano Ano  Ne3 Ne3 Ne3 Ne3 Ne3

  1 Program nepracuje v operačním systému MS Windows korektně - problematicky funguje ovladač myši a ovladač grafického adaptéru

  2 Program lze spouštět v některém z emulátorů operačního systému MS-DOS (DOSEMU, DOSBox, VMWare, Bochs, …)

  3 Zdrojové kódy jsou platformově zavislé na operačním systému MS-DOS



7. Odkazy

  Joint Photographic Experts Group
  Independent JPEG Group
  Wikipedia - JPEG
  Wikipedia - JPEG 2000
  Grafický formát JPEG



8. Literatura

  [Žára92] J. Žára, A. Limpouch, B. Beneš, T. Werner: Počítačová grafika - principy a algoritmy, Grada, Praha 1992

  [Sochor96] J. Sochor, J. Žára, B. Beneš: Algoritmy počítačové grafiky, Vydavatelství ČVUT, Praha 1996

  [Murray94] J. D. Murray, W. van Ryper: Encyclopedia of graphics file format, O’Reilly & Associates, California 1994

  [Hlaváč92] V. Hlaváč, M. Sonka: Počítačové vidění, Grada, Praha 1992

  [Bubeník94] F. Bubeník, M. Pultar: Matematické vzorce a metody, Vydavatelství ČVUT, Praha 1994

  [Herout92] P. Herout, V. Rudolf, P. Smrha: ABC programátora v jazyce C, Kopp, České Budějovice 1992

Poslední modifikace dokumentu: 17.01.1997



Tisk
Tisk