DALIBOR BARTON K PO ÍTA OVÁ GRAFIKA Ilences.cz/domains/lences.cz/skola/subory/Skripta/GE09... ·...

VYSOKÉ U�ENÍ TECHNICKÉ V BRN� FAKULTA STAVEBNÍ

DALIBOR BARTON�K

PO�ÍTA�OVÁ GRAFIKA I MODUL M01

TEORIE GRAFICKÝCH FORMÁT�

STUDIJNÍ OPORY PRO STUDIJNÍ PROGRAMY S KOMBINOVANOU FORMOU STUDIA

© Ing. Dalibor Barton�k, CSc., 2005

Po�íta�ová grafika I – Modul 01 – Teorie grafických formát�

- 3 (120) -

OBSAH

1 Úvod 7 1.1 Cíle ........................................................................................................7 1.2 Požadované znalosti ..............................................................................7 1.3 Doba pot�ebná ke studiu .......................................................................8 1.4 Klí�ová slova.........................................................................................8 1.5 Metodický návod na práci s textem ......................................................8

2 Úvod do po�íta�ové grafiky .........................................................................9 2.1 Historie po�íta�ové grafiky...................................................................9 2.2 P�edm�t po�íta�ové grafiky ................................................................10 2.3 Shrnutí .................................................................................................11

3 Digitalizace obrazu .....................................................................................12 3.1 Vzorkování v ploše .............................................................................13 3.2 Kvantování v úrovních........................................................................14 3.3 Aliasing ...............................................................................................16 3.4 Shrnutí .................................................................................................19 3.5 Autotest ...............................................................................................19

4 Teorie barev ................................................................................................20 4.1 Chromatický diagram CIE ..................................................................23 4.2 Barevné modely ..................................................................................25

4.2.1 Model RGB...........................................................................26 4.2.2 Model CMY(K) ....................................................................27 4.2.3 Model HSV ...........................................................................28 4.2.4 Model HLS............................................................................29 4.2.5 Munsell�v model ..................................................................30 4.2.6 Modely pro televizní techniku a videotechniku....................30

4.3 Rozptylování barev .............................................................................31 4.3.1 Náhodné rozptýlení...............................................................31 4.3.2 Maticové rozptýlení ..............................................................32 4.3.3 Distribuce chyby ...................................................................33

4.4 Shrnutí .................................................................................................34 4.5 Autotest ...............................................................................................35

5 Uložení obrázku do souboru......................................................................36 5.1 Fyzické a logické formáty dat .............................................................36 5.2 Zp�sob uložení bod� obrazu do souboru ............................................38

5.2.1 P�ímé a nep�ímé uložení pixelu ............................................38 5.2.2 Barevné módy .......................................................................39

5.3 Obecná struktura bitmapových soubor� .............................................41 5.4 Organizace bitmapových dat...............................................................43

5.4.1 Souvislá data .........................................................................44 5.4.2 Pásy .......................................................................................44 5.4.3 Dlaždice ................................................................................45

5.4.4 Hierarchické dlaždice........................................................... 46 5.5 Výhody a nevýhody bitmapových formát� ........................................ 47 5.6 Shrnutí ................................................................................................ 48 5.7 Autotest............................................................................................... 49

6 Komprese dat ............................................................................................. 50 6.1 Základní pojmy................................................................................... 50 6.2 Pixelové zhuš�ování ........................................................................... 51 6.3 Komprese kvadrantovým stromem..................................................... 51 6.4 Proudové kódování (RLE).................................................................. 53

6.4.1 Proudové kódování na bitové úrovni ................................... 54 6.4.2 Proudové kódování na slabikové (bytové) úrovni................ 55 6.4.3 Proudové kódování na pixelové úrovni................................ 57 6.4.4 RLE komprese PackBits....................................................... 57 6.4.5 RLE komprese se t�emi slabikami ....................................... 58 6.4.6 Vertikální replika�ní pakety ................................................. 58

6.5 Slovníkové metody (LZW)................................................................. 59 6.6 Huffmanovo kódování........................................................................ 61 6.7 Predik�ní metody................................................................................ 65 6.8 Waveletová (vlnková) transformace................................................... 66 6.9 Komprese založená na redukci barev ................................................. 67 6.10 Vektorová kvantizace ......................................................................... 69 6.11 Diskrétní kosinová transformace........................................................ 70

6.11.1 Fourierova transformace obrazové funkce ........................... 70 6.11.2 Odvození diskrétní kosinové transformace .......................... 73 6.11.3 Využití DCT pro kompresi dat............................................. 74

6.12 Fraktální komprese ............................................................................. 75 6.12.1 Úvod do fraktální geometrie ................................................ 75 6.12.2 Princip fraktální komprese ................................................... 76 6.12.3 Algoritmus fraktální komprese............................................. 78

6.13 Shrnutí 80 6.14 Autotest 82

7 Vektorové formáty ..................................................................................... 83 7.1 Princip vektorového popisu kresby .................................................... 83 7.2 Vlastnosti vektorových formát� ......................................................... 84 7.3 Technologie C4 .................................................................................. 87

7.3.1 Vymezení pojm� .................................................................. 87 7.3.2 Systémy CAD....................................................................... 89 7.3.2.1 Historie CAD........................................................................ 89 7.3.2.2 Krize CAD............................................................................ 89 7.3.2.3 Teorie CAD sytému ............................................................. 90 7.3.3 CAE...................................................................................... 91 7.3.4 CAM..................................................................................... 92 7.3.5 CIM ...................................................................................... 92 7.3.5.1 Charakteristické rysy CIM ................................................... 92

7.3.5.2 Zpracování a tok informací v C4 ..........................................93 7.3.6 Perspektivy dalšího vývoje technologie C4..........................94

7.4 Shrnutí .................................................................................................94 7.5 Autotest ...............................................................................................95

8 Konverze dat ...............................................................................................96 8.1 P�evod z bitmapového (rastrového) do bitmapového formátu............97 8.2 P�evod z vektorového do vektorového formátu ..................................98 8.3 P�evod z vektorového do bitmapového formátu .................................98

8.3.1 Rasterizace úse�ky................................................................99 8.3.1.1 Algoritmus DDA.................................................................100 8.3.1.2 Bresenham�v algoritmus rasterizace úse�ky ......................101 8.3.2 Rasterizace kružnice ...........................................................102 8.3.2.1 Bresenham�v algoritmus rasterizace kružnice....................104

8.4 P�evod z bitmapového (rastrového) do vektorového formátu...........104 8.5 Shrnutí ...............................................................................................106 8.6 Autotest .............................................................................................106

9 P�ehled grafických formát�.....................................................................108 9.1 Bitmapové (rastrové) formáty ...........................................................108

9.1.1 Formát PCX ........................................................................108 9.1.2 Formát GIF (Graphic Interchange Format).........................108 9.1.3 Formát PNG........................................................................109 9.1.4 Formát BMP........................................................................109 9.1.5 Formát Targa (TGA)...........................................................110 9.1.6 Formát TIFF (Tag Image File Format) ...............................110 9.1.7 Grafický formát JPEG.........................................................110

9.2 Vektorové formáty ............................................................................111 9.2.1 Formát DXF (Data Exchange Format) ...............................111 9.2.2 Formát HPGL......................................................................111

9.3 Metaformáty......................................................................................113 9.3.1 Formát EPS .........................................................................113 9.3.2 Formát WMF ......................................................................113

9.4 Multimediální formáty ......................................................................114 9.4.1 Formát MPEG.....................................................................114 9.4.2 Formát AVI.........................................................................115 9.4.3 Formát MOV.......................................................................116

9.5 Shrnutí ...............................................................................................116 9.6 Kontrolní otázky ...............................................................................116

10 Studijní prameny ......................................................................................117 10.1 Seznam použité literatury..................................................................117 10.2 Seznam dopl�kové studijní literatury ...............................................119 10.3 Odkazy na další studijní zdroje a prameny .......................................119

11 Klí� 120 11.1 Odpov�di na kontrolní otázky...........................................................120 11.2 Výsledky autotestu ............................................................................120

Úvod

- 7 (120) -

1 Úvod

1.1 Cíle

Cílem p�edm�tu „Po�íta�ová grafika I“ je porozum�t nejpoužívan�jším metodám uložení obrazové informace do souboru, seznámit se se základními funk�ními principy moderních technických prost�edk� pro po�íta�ovou grafiku a pochopit základní algoritmy používané pro zpracování grafických informací. Kurz je zam��en p�edevším na rovinnou (2D) grafiku, z prostorové (3D) grafiky jsou uvedeny jen základy ve 2. modulu. Podklady pro studium jsou rozd�leny do 2 modul�:

1. Teorie grafických formát�,

2. Technické prost�edky, zpracování obrazu a základy 3D grafiky.

Cílem tohoto 1. modulu je porozum�t struktu�e a metodám práce s nejpou-žívan�jšími grafickými formáty a dále se seznámit se zp�sobem využití grafic-kých formát� v technické, zejména geodetické praxi.

1.2 Požadované znalosti

Po prostudování tohoto modulu jsou od student� o�ekávány tyto znalosti: Prin-cip digitalizace obrazu, Shannon�v/Kot�lnikov�v teorém, aliasing. Teorie ba-rev, barevné modely, metody rozptylování barev. Fyzické a logické formáty v po�íta�i, p�ímé a nep�ímé uložení pixelu do souboru, struktura souboru s ob-razovou informací (hlavi�ka, paleta, data). Ukládání obrazových dat do pás� a dlaždic. Princip a význam komprese dat. Nejpoužívan�jší kompresní metody (RLE, kvadrantový strom, LZW, Huffmann�v kód, vlnková transformace, pre-dikce, diskrétní kosinová transformace, fraktální komprese, redukce barev, vektorová kvantizace). Vektorová grafika, vektorové grafické formáty a jejich porovnání s rastrovými grafickými formáty. Využití vektorové grafiky v praxi zejména v technologii C4. Problematika konverze grafických formát� zejména p�evod vektor – rastr (v�etn� princip� základních rasteriza�ních algoritm� pro úse�ku a kružnici) a konverze rastr – vektor (vektorizace). Charakteristické vlastnosti nejpoužívan�jších grafických formát� (BMP, GIF, TIFF, JPEG, DXF, HPGL, …).

1.3 Doba pot�ebná ke studiu

Pro zvládnutí tohoto p�edm�tu v denním studiu je plánovaná hodinová dotace v jednom semestru 2 – 2 hod. týdn�, tj. 2 hod. p�ednášek, 2 hod. cvi�ení. P�i délce trvání 1 semestru 13 týdn� to odpovídá 13 x 2, tj. 26 hodin studia pro 2 moduly, pro jeden modul pak polovina, tj. 13 hodin.

1.4 Klí�ová slova

Po�íta�ová grafika, digitalizace obrazu, vzorkování, kvantování, teorie barev, CIE diagram, barevné modely (RGB, CMY, HSV, HLS), rozptylování barev, grafický formát, hloubka pixelu, endián, bitové pohlaví, paleta, uložení do pás� a dlaždic, hierarchické dlaždice, komprese dat, ztrátová, bezeztrátová komprese, kvadrantový strom, RLE, slovníková komprese (LZW), Huffman�v entropický kód, vlnková (wavelet) transformace, predikce, redukce barev, vek-torová kvantizace, diskrétní kosinová transformace (DCT), fraktální komprese, vektorové formáty, technologie C4, konverze grafických formát�, transformace sou�adnic, syntaktická a sémantická analýza.

1.5 Metodický návod na práci s textem

Každá kapitola za�íná výkladem, který je podle pot�eby dopln�n ilustra-tivními p�íklady. Nejd�ležit�jší poznatky jsou stru�n� uvedeny v podkapitole „Shrnutí“, kterou by po prostudování dané problematiky m�l každý um�t po-kud možno sám svými slovy rekonstruovat. V samém záv�ru jsou kontrolní otázky nebo autotest, který slouží k samostatné kontrole v jaké kvalit� byla daná kapitola zvládnuta. Správné odpov�di nalezne �tená� v kapitole „Klí�“. Jednotlivé kapitoly na sebe logicky navazují, proto je doporu�ujeme studovat postupn� tak jak jsou uspo�ádány v textu.

Vzhledem k omezenému rozsahu stran je tento modul koncipován tak, že slouží jen jako dopln�k ke skript�m [26] a [34]. V�tšina kapitol na tato skripta pouze odkazuje; v plném rozsahu jsou uvedeny jen ty kapitoly, které ve skriptech chybí nebo jsou zpracovány nedostate�n�, pop�. mají st�žejní vý-znam. Pro úplné zvládnutí celé problematiky v�etn� správných odpov�dí na otázky v autotestu je nezbytné prostudovat nejen tento modul, ale i uvedená skripta.

Úvod do po�íta�ové grafiky

- 9 (120) -

2 Úvod do po�íta�ové grafiky

2.1 Historie po�íta�ové grafiky

První pokusy o zpracování grafické informace po�íta�em bylo možné pozorovat už ve 40. letech (W. B. Hales, 1944, analogové kresby) a 50. letech (Iwan Moscowich, 1951, kreslicí stroj). První publikace vyšly ve 2. polovin� 50. let (Max Bense, 1954, „Programmierung des Sch�nen“, W. Franke, 1957, „Kunst und Konstruktion“). Termín po�íta�ová grafika se poprvé objevuje v roce 1960, kdy pracovníci firmy Boeing za�ali tímto pojmem ozna�ovat pro-ces návrhu a realizace výkresové dokumentace pomocí po�íta�e.

Protože grafika pat�í mezi úlohy nenumerické povahy, na které není klasická univerzální architektura po�íta�� von Neumanna vhodná, mohla se rozvinout tehdy až výkonnost technických prost�edk� dosáhla ur�itého stupn�. Ve vývoji po�íta�ové grafiky pozorovat tyto d�ležité etapy:

1. od po�átk� do konce 60. let. Toto období je charakterizováno unikátní-mi pokusy o zpracování grafické informace ve vybraných institucích.

2. 70. léta. Rozvoj technických prost�edk� umožnil rozší�ení po�íta�ové grafiky do celého sv�ta, ale jen na úrovni organizací. Vzhledem k vy-soké po�izovací cen� technického vybavení nebyla po�íta�ová grafika p�ístupná širšímu okruhu uživatel�. První zmínka o navrhování po�íta-�em (CAD), pokus o využití po�íta�ové grafiky v um�ní, za�átky sv�-tových výstav s touto tématikou (Japonsko).

3. 80. léta. Uvedení mikroprocesor� na trh umožnil zlevnit technické pro-st�edky a rozší�it okruh uživatel� po�íta�ové grafiky. Po�íta�e IBM PC byly ješt� pro jednotlivce cenov� nedostupné, ale po�íta� ZX Spectrum lorda Sinclera, osazený mikroprocesorem ZX-81 byl cenov� p�ijatelný i pro soukromé uživatele (domácnosti).

4. 90. léta. Rozvoj technologií VLSI (Very Large Scale Integration) a ko-munikací (Internet) ovlivnil významn� i po�íta�ovou grafiku. Prosazuje se masov� 3D grafika a animace, po�íta�ová grafika proniká do tém�� všech obor� lidské �innosti.

Z krátkého historického p�ehledu je vid�t, že po�íta�ová grafika byla zpo�átku jen ojedin�lou a pom�rn� vzácnou disciplínou, protože vyžadovala nasazení složitých a v té dob� drahých technických prost�edk�. Vlivem prud-kého rozvoje výpo�etní techniky (zejména unifikace hardware umož�ující vel-kou sériovou výrobu sou�ástek a funk�ních blok�) došlo k výraznému poklesu cen technických po�íta�ových produkt�. Tím se podstatn� rozrostl po�et uživa-tel� a dnes už je velmi obtížné najít oblast, kde by zpracování obrazu nenalezlo své uplatn�ní. Je to dáno i tím, že více než polovinu informací p�ijímá �lov�k zrakem a obraz je velmi efektivním prost�edkem pro komunikaci.

Bližší informace o historii po�íta�ové grafiky jsou nap�. v [7], [8], [26].

Teorie grafických formát�

- 10 (120) -

2.2 P�edm�t po�íta�ové grafiky

P�edm�tem po�íta�ové grafiky jsou p�edevším obecné procesy zpraco-vání grafické informace a jejich vzájemná provázanost – viz obr. 2.1.:

1. Po�ízení grafických dat a) digitalizace reálné p�edlohy b) vytvo�ení nové kresby uživatelem (nap�. editorem) c) kombinace ad a) a ad b).

2. Editace stávající grafické informace (kresby) bez analýzy obsahu dat. 3. Databázové operace:

zápis do souboru v grafickém formátu, komprese a konverze dat, uložení souboru, vyhledávání, �tení a dekódování dat apod.

4. Modelování grafické informace. 5. Rekonstrukce grafické informace.

Po�íta�ová grafika není izolovaná a využívá poznatk� z n�kolika v�d-ních disciplín. Nejblíže má k po�íta�ovému vid�ní (computer vision), které zpracovává obraz s cílem porozum�t mu tím, že jednotlivým objekt�m v obraze p�i�azuje interpretaci. Další p�íbuznou oblastí je teorie signál�, jejíž prost�edky umož�ují snadný popis p�echodu od spojitého obrazu reálného sv�-ta k diskrétnímu obrazu, se kterým se pracuje v po�íta�ové grafice. Své využití zde nalezla i teorie informace a to zejména ve tvorb� metod pro kompresi dat.

reálný prostor diskrétní prostor

(analogový, spojitý) (nespojitý)

Obr. 2.1. Procesy v po�íta�ové grafice

uživatel

vstupní za�ízení

p�edloha (obrázek)

uživatelské rozhraní

výstupní za�ízení

grafická databáze

Technické a programo-

vé

vybavení pro po�íta-�o-vou

grafiku

rekonstrukce obrazu

digitalizace obrazu

editace

modelování

databázové operace

Úvod do po�íta�ové grafiky

Po�íta�ovou grafiku m�žeme rozd�lit podle dimenze na:

- rovinnou, plošnou (2D) - prostorovou (3D),

každou z nich m�žeme rozd�lit podle zp�sobu popisu obrázku na:

- rastrovou (popisuje každý bod obrázku), - vektorovou (popisuje obraz pomocí základních grafických prvk�).

Do po�íta�ové grafiky rovn�ž pat�í i animace, která m�že být plošná, pro-storová, rastrová i vektorová.

V tomto modulu se budeme zabývat plošnou rastrovou a vektorovou grafi-kou. Prostorová grafika a vizualizace bude náplní dalšího modulu.

2.3 Shrnutí

Po�íta�ová grafika se od nesm�lých po�átk� ze 60. let vyvinula v samostatnou v�dní disciplínu. P�íznivý vliv na její rozvoj m�l prudký tech-nický pokrok v oblasti výpo�etní techniky. Hlavními mezníky vývoje jsou 70. léta (rozvoj mikroprocesor�) a 90. léta (paralelní struktury, internet) Pro svoji relativní univerzálnost se stala základem dalších technických obor�. P�edm�-tem po�íta�ové grafiky je uchování a zpracování grafické informace bez ohledu na obsah této informace. Využívá metod jiných v�dních obor� jako aplikovaná matematika a fyzika, teorie signál� apod. Po�íta�ová grafika m�že být podle dimenze plošná nebo prostorová, podle zp�sobu popisu kresby rozeznáváme rastrovou a vektorovou grafiku.

Kontrolní otázky

1. Jmenujte nejd�ležit�jší mezníky vývoje po�íta�ové grafiky

2. Co je p�edm�tem po�íta�ové grafiky a jaké jsou její p�íbuzné obory?

3. Jaké procesy probíhají v po�íta�ové grafice?

4. Jak lze rozd�lit po�íta�ovou grafiku?


- 12 (120) -

3 Digitalizace obrazu

V reálném sv�t� jsou všechny obrázky analogové, tj. skládají se z nekone�n� mnoha bod�. Pokud chceme uložit obrázek (p�edlohu) do po�íta�e k dalšímu zpracování, musíme jej p�evést do digitální formy (laicky �e�eno do hromady �ísel). Tento p�evod se nazývá digitalizace obrazu.

y

P(x,y)

x

Obr. 3.1. Obecný bod p�edlohy

Z obrázku 3.1. je vid�t, že každý bod má z hlediska po�íta�ové grafiky tyto základní vlastnosti: 1. umíst�ní v p�edloze dané sou�adnicemi (x, y), 2. konkrétní jednobarevný nebo mnohobarevný odstín, který pro naše pot�eby

m�žeme reprezentovat n�jakou vhodnou fotometrickou veli�inou; t�mto ú�el�m nejlépe vyhovuje jas. Je to veli�ina, která souhrnn� vyjad�uje vlast-nosti obrazového signálu tak, jak je vnímá i �lov�k. Použití jasu je jedno-dušší než popisovat složitý optický proces vytvá�ení obrazu.

Zave�me si proto pojem obrazová funkce F(x, y), která matematicky popisuje bod v p�edloze. Je-li funkce F skalár, je daný bod o sou�adnici (x, y) jednobarevný a mají-li všechny body p�edlohy tuto vlastnost, pak �íkáme, že obraz je monochromatický. Je-li funkce F vektor o n�kolika složkách, má vy-šet�ovaný bod r�znobarevný odstín a pokud lze takto popsat všechny body p�edlohy, jde o obraz panchromatický tj. barevný. Z matematického hlediska je digitalizace obrazu transformace obrazové funkce F dvou prom�nných (x, y) z reálného oboru na funkci G dvou prom�nných (X, Y) z oboru celých �ísel:

F(x, y) → G(X, Y) (3.1)

(x, y) ∈ R (X, Y) ∈ N

Digitalizací musíme zachytit ob� význa�né vlastnosti bodu obrazu tj. jeho umíst�ní a hodnotu obrazové funkce. Proto je celý proces možné rozd�lit na dva díl�í procesy:

1. vzorkování v ploše, 2. kvantování v úrovních.

Digitalizace obrazu

3.1 Vzorkování v ploše

Vzorkování je proces snímání vzork� obrazové funkce v ploše p�edlohy. K tomuto ú�elu se využívá tzv. obrazová matice, jejíž dv� typické varianty

a) ortogonální, b) hexagonální, ukazuje obr. 3.2.

a) b )

Obr. 3.2. Obrazová matice a) ortogonální, b) hexagonální

Hexagonální matice má proti ortogonální výhodu v tom, že euklidovská vzdálenost mezi sousedními body matice je ve všech sm�rech konstantní, což zjednodušuje operace založené na sousednosti bod� nap�. v geografických in-forma�ních systémech (GIS). Nevýhodou tohoto uspo�ádání je to, že se na tak-to vzorkovaný obraz obtížn� aplikuje ortogonální transformace nap�. diskrétní Fourieova transformace a tedy i diskrétní kosinová transformacei (viz kap. 6.11.). Proto se v praxi užívá výhradn� jen ortogonální m�ížka.

Obrazové matici se také �íká vzorkovací nebo digitaliza�ní m�ížka. Uz-lové body m�ížky jsou v anglosaské literatu�e ozna�ovány termínem pixel nebo jen pel, což je akronym z anglického sousloví picture element (prvek obrazu).

Rozeznáváme logický pixel (matematický), který reprezentuje ve sku-te�nosti nikoliv jediný bod, ale celou plošku p�edlohy (v podstat� jde o okolí uzlového bodu). Tato ploška na fyzickém výstupním médiu (papír, stínítko obrazovky atd.) p�edstavuje fyzický pixel.

D�ležitým problémem vzorkování je stanovení periody vzorkování tj. vzdálenosti mezi nejbližšími logickými pixely v obraze. P�íliš hustá m�ížka vede k velkému po�tu bod� a tím i zna�né velikosti souboru, �ídká m�ížka má za následek velkou ztrátu informace. Proto je t�eba zvolit rozumný kompromis mezi velikostí souboru a hustotou obrazové matice. Tuto otázku �eší Shanno-n�v nebo Kot�lnikov�v teorém o vzorkování známý z teorie signál� [3], který �íká, že vzorkovací frekvence musí být nejmén� 2x vyšší než nejvyšší frekven-ce ve vzorkovaném signálu. Z našeho hlediska lze teorém interpretovat takto:

Nech� d je rozm�r (ve sm�ru osy x i y) nejmenšího detailu p�edlohy, který chceme pro naše ú�ely ješt� zachovat tj. zdigitalizovat. Pak vzdálenost a mezi sousedními body obrazové matice ( m�ížky) musí spl�ovat vztah:

ad

≤2

(3.2)


- 14 (120) -

Vzdálenosti a mezi sousedními body digitaliza�ní m�ížky se n�kdy také

�íká m�ížková konstanta. Bude-li obrazová matice �ídká tj. ad�

2, pak detail

obrázku o rozm�ru d propustíme (propadne m�ížkou). Vzdálenost a ur�uje dále tzv. rozlišení obrazu, které se udává v dpi, což je zkratka z anglického termínu dots per inch tj. bod� na palec; 1″ (inch) = 25.4 mm.

3.2 Kvantování v úrovních

Kvantováním se rozumí digitalizace hodnoty (amplitudy) obrazové funkce v daném bod� p�edlohy. Na rozdíl od vzorkování má tato �innost jedno-rozm�rný charakter. Jde o proces reprezentace analogových plošn� diskretizo-vaných vzork� kone�ným po�tem diskrétních úrovní.

Amplituda analogového vzorku F(x, y) se porovnává s kone�ným po�tem rozhodovacích úrovní {di}. Leží-li hodnota amplitudy v intervalu <di ,di+1>, je tato hodnota nahrazena rekonstruk�ní úrovní ri. - viz obr. 3.3. Nech� analogové amplitudy vzork� leží v pásmu:

( )d F x y dm ≥ ≥, 0 (3.3)

kde dm je maximální a d0 je minimální amplituda vzorku.

Problémem je zde nalezení kvantiza�ní funkce tj.:

1. stanovení optimálního po�tu kvantiza�ních (diskrétních) hladin a 2. nalezení rozhodovacích a rekonstruk�ních úrovní.

ad 1) - stanovení po�tu kvantiza�ních úrovní

Po�et kvantiza�ních úrovní musí být dostate�ný, aby nevznikaly zkres-lené obrysy a aby byly vyjád�eny dostate�n� jemné detaily obrazu. Pro �lov�ka je patrný vznik falešných obrys� p�i po�tu jasových úrovní menších než 50. P�i stanovení po�tu t�chto úrovní se vychází z kontrastní citlivosti zraku. Zrak se chová jako diferenciální analyzátor, který více reaguje na zm�ny jasu soused-ních pixel�, než na jejich absolutní hodnoty. Vnímání jasových diferencí ∆∆∆∆B = Bi+1 -Bi proti pozadí s rovnom�rným jasem B0 popisuje Weber - Fechner�v zákon:

∆B kB= 0 (3.4)

kde B0 je jas pozadí

k = 0.015 - 0.02

po úpravách [26] dostaneme vztah pro po�et kvantiza�ních úrovní n:

n

BB

k=

+

log

log( )

max

min

1 (3.5)

Digitalizace obrazu

Pro pom�r jas� BB

max

min= 100 vychází rozlišitelný po�et grada�ních stup��

n=230, nejblíže vyšší mocna 2 k 230 je �íslo 256 (tj. 28) Tento výsledek je po-tvrzen praxí, protože v mnoha p�ípadech vyhovuje 256 kvantiza�ních úrovní tj. zobrazení pixelu do 8 bit� (viz kap. 5).

ad 2) stanovení rozhodovacích a rekonstruk�ních úrovní

Na základ� daného po�tu kvantiza�ních úrovní je t�eba stanovit rozho-dovací a rekonstruk�ní úrovn� tak, aby kvantiza�ní chyba byla minimální.

Kvantiza�ní chyba je vid�t na obr. 3.3. jako rozdíl mezi vstupním a kvantovaným vzorkem tj. F(x, y) - Fr(x, y). Definuje se jako st�ední kvadratic-ká chyba a pro n kvantiza�ních úrovní má tvar:

( ) ( ) ( ) ( )ε = − = −+

=

−

�� F F p F dF F rd

dp F dF

d

dr j

j

j

j

mm2 2

1

0

1

0

(3.6)

kde p(F) je hustota pravd�podobnosti výskytu díl�ích úrovní jasové funkce.

max. amplituda

dm

rm-1

dm-1

.

.

.

dj+1

rj ∆

dj

d1

r0

d0

min. amplituda

rozhodovací úrovn�

rekonstruk�ní úrovn�

kvantiza�ní chyba ∆ = Fr(x, y) - F(x, y)

Obr. 3.3. Princip kvantizace

Vstupní vzorek F(x, y)

kvantovaný vzorek Fr(x, y)


- 16 (120) -

Po úpravách viz [3], [26] dostaneme optimální rekonstruk�ní úrove�:

rd d

jj j

=++ 1

2 (3.7)

Je-li hustota pravd�podobnosti hodnoty obrazové funkce mezi dv�ma rozhodovacími úrovn�mi konstantní, pak optimální rekonstruk�ní úrove� leží mezi t�mito dv�ma rozhodovacími úrovn�mi.

Výb�rem optimálních rozhodovacích úrovní v obecném p�ípad� se za-bývali Panter a Dite [22] a Max v [19].

Pokud má být rozložení kvantiza�ních úrovní nerovnom�rné, pak toho lze dosáhnout:

a) p�ímo a to nerovnom�rnou kvantiza�ní charakteristikou, b) nep�ímo, pomocí úrov�ové nelineární komprese a kvantováním

s rovnom�rnou kvantiza�ní charakteristikou.

Obr. 3.4. Kvantiza�ní funkce

Kvantiza�ní chyba a její pr�b�h má st�žejní vliv na návrh za�ízení pro kvantování tzv. kvantizéru. Kvantizéry mohou být bez pam�ti (každý vzorek se kvantuje nezávisle) a s pam�tí, kdy hodnota výstupu je závislá na n�kolika p�edchozích vzorcích. Na obr. 3.4. vidíme 2 základní typy kvantizér�: a) upro-st�ed plochý, b) uprost�ed roste.

3.3 Aliasing

Se vzorkováním a zm�nou rozlišení úzce souvisí aliasing. Je to jeden z nejd�ležit�jších pojm� v po�íta�ové grafice v�bec. Aliasing je jev (informa-ce, artefakt) v obraze, který vznikne tím, že vysoké frekvence vystupují jako frekvence nízké. Situaci znázor�uje obr. 3.5., na kterém vidíme �ást sinusové-ho signálu. Na obr. 3.5. a) je vzorkovací frekvence vyšší než kmito�et sinusov-ky, na obr. 3.5. b) je limitní p�ípad Shannonova teorému (vztah 3.2.), kdy vzor-

Digitalizace obrazu

kovací perioda je p�esn� rovna polovin� periody sinusovky. Na obr. 3.5. c) a d) je však sinusový signál vzorkován nižší frekvencí než je dvojnásobek jeho frekvence. Nasnímané vzorky pak p�edstavují signál s nižší frekvencí než v je ve vzorkované funkci (sinusovce). Tyto nízké frekvence nazýváme alias. Alias nem�žeme zcela odstranit, m�žeme jej jen �áste�n� potla�it. V po�íta�ové gra-fice se tento proces nazývá antialiasing. Používají se 2 metody:

1. vzorkování s vyšší frekvencí (angl. supersampling), 2. p�evedení aliasu na šum.

Obr. 3.5. Vzorkování sinusového signálu

ad1) Supersampling je proces, který má tyto fáze:

- vytvo�ení virtuálního obrazu s rozlišením (2k+1) krát vyšším než je požadováno. Každé skupin� (2k+1) x (2k+1) pixel� (nap�. 3 x 3) ve virtuálním obraze se �íká superpixel,

- filtrace virtuálního obrazu, kdy se každému superpixelu p�i�adí je-diná barva tak, že se vypo�ítá pr�m�r, který se p�i�adí celé ploše su-perpixelu. Filtruje se pomocí speciálních konvolu�ních filtr� pro po-tla�ení vysokých frekvencí – viz modul 02,

- p�evzorkování obrazu do požadovaného rozlišení. Vzorkování s vyšší frekvencí tedy znamená zvýšení frekvence vzorko-

vacího rastru a jeho zp�tné snížení zpr�m�rováním. Princip je z�ejmý z obr. 3.6. Uvedená metoda má své nevýhody a to:

- technickou, která spo�ívá v tom, že vzorkovací frekvence nem�že být nekone�ná,

- teoretickou – obrazy v po�íta�ové grafice nejsou obecn� frekven�n� omezené, a pouhé kone�né zvýšení vzorkovací frekvence nem�že problém aliasu zcela vy�ešit. Jen jej posune k vyšším frekvencím. Uvedená metoda, kdy se po vzorkování provádí filtrace se v zahrani�ní literatu�e nazývá postfiltering.


- 18 (120) -

Obr. 3.6. Princip supersamplingu

ad2) podstatou p�evedení aliasu na šum je stochastické vzorkování. Jde o vzorkování obrazu v náhodn� nepravidelných intervalech, kdy nežádoucí vysoké frekvence vystoupí jako šum a ne jako nízké frekvence (alias). P�eve-dení aliasu na šum využívá skute�nosti, že lidské oko je na šum mén� citlivé než na alias. V oku jsou ty�inky a �ípky rozmíst�ny náhodn�, proto vidíme pravidelné textury bez aliasu. Je s podivem, že náhodné uspo�ádání fotorecep-tor� v oku tém�� p�esn� odpovídá optimálnímu filtru pro p�evod aliasu na šum. Rozložení vzork� v tomto filtru je možné statisticky popsat tzv. Poissonovým rozložením, u kterého je zaru�ena minimální vzdálenost d mezi dv�ma vzorky tzv. Poisson disc. Výpo�etní postup založený na této teorii je však z �asových d�vod� prakticky nepoužitelný. P�i každém vygenerovaném vzorku by se mu-selo testovat, zda v jeho okolí ve vzdálenosti d není jiný vzorek. Pokud by ta-kový p�ípad nastal, vzorek by se zamítnul a vygeneroval by se vzorek nový. V praxi se proto osv�d�il algoritmus zvaný rozt�esení (angl. jittering). Jeho principem je umíst�ní vzork� do st�edu pixel� a následné zat�esení s nimi tak, aby žádný z nich neopustil hranici svého fyzického pixelu. Tímto zp�sobem je docíleno náhodného rozložení vzork� v pixelu a sou�asn� je zachováno jejich relativn� rovnom�rné rozložení po celé ploše v obrazu – viz obr. 3.7. Nejhorší p�ípad nastane tehdy, setkají-li se �ty�i vzorky v jednom rohu plochy fyzického pixelu. Pozice vzork� na obr. 3.7. b) jsou generovány náhodnými �ísly z intervalu <-/2; + /2>, kde je rozm�r pixelu.

a) pravidelné vzorkování b) stochastické vzorkování - rozt�esení

Obr. 3.7. Princip rozt�esení

Problematika aliasingu je dob�e popsána nap�. v [44].

Digitalizace obrazu

3.4 Shrnutí

Digitalizace obrazu probíhá ve 2 fázích:

1. vzorkování v ploše, kdy se registrují hodnoty obrazové funkce v bodech diskrétní m�ížky,

2. kvantování v úrovních které spo�ívá v p�i�azení diskrétní hodnoty se-jmutému vzorku v závislosti na jeho hodnot�.

V digitalizovaném obrazu se objevuje alias, který se projevuje tím, že vy-soké kmito�ty v obrazu vystupují jako kmito�ty nízké. Je zp�soben nedodrže-ním Shannon – Kot�lnikova teorému který �íká, že vzorkovací kmito�et musí být alespo� 2x v�tší než nejvyšší kmito�et obsažený v p�vodním obrazu. Alias nelze úpln� odstranit, ale jen potla�it. Používá se 2 metod:

1. supersampling, který spo�ívá v tom, že se vytvo�í do�asný obraz o vyš-ším rozlišení, p�vodním pixel�m se p�i�adí zpr�m�rované hodnoty tzv. superpixel�, které k t�mto pixel�m pat�í a obraz se zp�t p�evzorkuje do p�vodního rozlišení,

2. p�evodem aliasu na šum, kdy se sejmou nové hodnoty vzork� v náhod-n� generovaných pozicích v rámci p�vodních pixel� tzv. rozt�esení.

3.5 Autotest

1. P�edloha má rozlišení 600 dpi. Jaká je nejv�tší možná perioda vzorkování?

a) 0,4 mm b) 0,5 mm c) 0,3 mm d) 0,2 mm e) 0,1 mm

2. Kvantování je proces

a) snímání hodnot obrazové funkce b) p�evod vzork� do diskrétních úrovní

c) rekonstrukce obrazové funkce d) analýzy obrazové funkce

3. Alias se projeví tehdy, je-li perioda vzorkování

a) menší b) v�tší c) rovna

polovin� nejmenšího detailu v obrazu.

4. Alias lze zcela odstranit:

a) vyšším rozlišením b) supersamplingem c) p�evodem na šum d) nelze od-stranit v�bec


- 20 (120) -

4 Teorie barev

Barvy vnímáme prost�ednictvím sv�tla. Sv�tlo je v podstat� �ást elek-tromagnetického vln�ní v rozsahu od 4,3. 1014 Hz (�ervená) do 7,5. 1014 Hz (fialová). Na obrázku 4.1., jsou znázorn�ny dosud známé druhy elektromagne-tických vln podle [9].

Obr. 4.1. Druhy elektromagnetického vln�ní

Barevný vjem se dá vysv�tlit takto:

Pokud n�jaký sv�telný zdroj vysílá všechny frekvence viditelného pás-ma, vzniká interferencí tj. skládáním bílé (achromatické) sv�tlo. Dopadá-li toto sv�tlo na ur�itý objekt, �ást sv�tla se pohltí a �ást se odrazí od povrchu. V odraženém spektru je vnímána barva objektu. Odrazí-li se nap�. nízké frek-vence, je objekt vnímán jako �ervený, protože na naše zrakové orgány p�eváž-n� p�sobí tzv. dominantní frekvence (vnímané sv�tlo má svou dominantní vl-novou délku). Samotný vjem barvy vzniká v mozku. Prost�edníkem mezi pod-n�tem (viditelným sv�tlem) a vjemem barvy je oko – viz obr. 4.2. Svazek pa-prsk� dopadá p�es rohovku, �o�ku a sklivec na sítnici, která je pokryta bu�ka-mi dvojího druhu:

- ty�inkami (v po�tu asi 120 milion�), které jsou citlivé na intenzitu sv�tla (monochromní vid�ní),

- �ípky (p�ibližn� 6,5 milion�), které jsou citlivé na dominantní vlno-vou délku (barevné vid�ní).

Ty�inky a �ípky reprezentují funkci sníma��, které transformují elek-tromagnetické vln�ní viditelného spektra na signály, jenž jsou dále p�enášeny zrakovým nervem do p�íslušného mozkového centra. V p�eneseném slova smyslu je možné oko považovat za digitální kameru se sníma�em o minimál-ním po�tu 6,5 milionu prvk� (6,5M pixel�). Velmi zajímavé je, že plošné roz-míst�ní bun�k citlivých na sv�tlo na sítnici oka není pravidelné (viz obr. 3.7.a), ale nahodilé (podobn� jako na obr. 3.7. b). Toto uspo�ádání p�itom odpovídá

Teorie barev

ideálnímu Poissonovu rozložení pro eliminaci aliasu a jeho p�evodu na šum (viz p�edchozí kapitola 3.3.). Citlivost �ípk� na dominantní vlnovou délku není v rozsahu viditelného spektra stejná jak ukazuje obr. 4.3. b), ale jsou zde patrná 3 lokální maxima pro vlnové délky =620 nm (�ervená), =520 nm (zelená) a =450 nm (modrá). Výsledná barva c je dána vektorem

Obr. 4.2. �ez lidským okem

trichromatických spektrálních �initel� (r, g, b) vynásobených relativní citlivostí oka (R, G, B) na principu aditivního míchání – viz obr. 4.3.:

c = rR + gG + bB (4.1)

a) b)

Obr. 4.3. Spektrální trichromatické �initele (a) a relativní citlivost �ípk� oka na dominantní vlnovou délku sv�tla (b)

Sv�tlo je obecn� charakterizováno t�mito veli�inami:

� jasem (svítivostí), který odpovídá intenzit� sv�tla, � sytostí, která udává �istotu barvy sv�tla. Je tím vyšší, �ím užší je

spektrum barevných frekvencí obsažených ve sv�tle, � sv�tlostí ur�ující velikost bílé (achromatické) složky ve sv�tle

s ur�itou dominantní frekvencí,


- 22 (120) -

� barevností (chromacity), která je dána kombinací sytost+dominantní frekvence.

Použijeme-li 2 pop�. více zdroj� sv�tla o r�zných barvách a intenzitách, m�žeme vytvo�it škálu dalších barev. Vytvo�í-li 2 zdroje bílé sv�tlo, pak se barvám t�chto zdroj� �íká, že jsou dopl�kové neboli komplementární. Vzniká p�irozená otázka, zda je možné najít takové základní barvy, jejichž složením by bylo možné vygenerovat všechny existující barvy. Z principu skládání vlno-vých d�j� vyplývá, že to možné není. Tato skute�nost bude potvrzena CIE dia-gramem v další kapitole. Lze však vybrat n�kolik základních barev, které vy-tvo�í bázi pro velkou �ást existujících barevných odstín�. Kombinací základ-ních barev o r�zných intenzitách lze získat barevný rozsah, na který je navyklé lidské oko. Ukázka skládání zá�ení luminofor� v oku je na obr. 4.4.

Obr. 4.4. Aditivní skládání barev do výsledného odstínu v oku

sou�et

sou�et

Teorie barev

4.1 Chromatický diagram CIE

V roce 1931 byl ustaven standard, v n�mž je mimo jiné zakotven po�et základních barev, jejichž kompozicí se budou tvo�it další odstíny barev v technické praxi a chromatický diagram CIE (Comission Internationale de l′Éclairage). Podle tohoto standardu se barvy definují jako vážený sou�et 3 barev. Tento po�et byl odvozen z pr�b�hu citlivosti lidského oka na vlnovou délku sv�tla (viz obr. 4.3.), který obsahuje 3 maxima. Každá skute�ná barva je ve standardu ur�ena matematicky daným množstvím 3 základních barev, které jsou nutné pro její vytvo�ení. P�edpokládejme, že ur�itá barva o složkách x, y, z je vytvo�ena ze 3 základních barev, z nichž každá má množství A, B, C. Pak m�žeme jednotlivé složky barvy vyjád�it v normalizovaném tvaru takto:

xA

A B C=

+ +

CBAB

y++

= CBA

Cz

++= (4.2)

Protože jde o vážený sou�et barev a platí: x + y + z = 1 je jedna slož-ka závislá a pro jednozna�né ur�ení barvy jsou dosta�ující jen 2 složky. Vybe-reme-li složky x, y, pak m�žeme reprezentovat všechny barvy pomocí dvou-rozm�rného diagramu. K�ivka, která ohrani�uje barvy viditelného spektra se nazývá chromatický diagram CIE - viz obr. 4.5. Hrani�ní k�ivka diagramu p�edstavuje množinu nasycených barev a je okótována ve vlnových délkách v [nm] t�chto barevných odstín�. Bod ozna�ený v obr. 4.5. jako C (Point of equal energy) reprezentuje �isté achromatické sv�tlo a je standardem pro pr�m�rné denní sv�tlo (angl. illuminant C).

Z CIE diagramu je možné dále ode�íst tyto veli�iny:

1) Sytost barevného odstínu. Nap�. sytost barvy reprezentované bodem G je

dána pom�rem úse�ek: [ ]%100CACG

. Barva G na obr. 4.5. má sytost asi 75%.

2) Dominantní vlnovou délku. Ta je definována jako pr�se�ík úse�ky AC (kde C je illuminant) s hrani�ní spektrální k�ivkou CIE diagramu. Na obr. 4.5. m�žeme v bod� A ode�íst dominantní vlnovou délkou pro odstín G.

3) Dopl�kové barvy. Jsou to takové barvy, na jejichž spojnici v CIE diagramu leží bod C (standard pr�m�rného denního sv�tla). Mají-li dopl�kové barvy stejnou sytost, vznikne jejich kombinací bílé sv�tlo C. V obr. 4.5. jsou barvy B a G dopl�kové.

4) Barevné rozsahy, které jsou ur�eny množinou bod�, vytvo�enou lineárním (úse�kou) nebo plošným (mnohoúhelník) útvarem, který celý leží uvnit� CIE diagramu. Na obr. 4.5. je nap�. možné získat všechny barvy (bo-dy) na úse�ce AB kombinací základních barev, reprezentovaných práv� bo-dy A a B. Dále všechny vnit�ní body trojúhelníka lze vytvo�it kombinací zá-kladních barev z jeho vrchol� D, E, F. Z t�chto p�íklad� je vid�t, že není možné sestrojit takový trojúhelník, který by pokrýval celý CIE diagram. Z toho vyplývá, že pomocí kone�ného po�tu základních barev není možné vytvo�it všechny existující barevné odstíny.

Je t�eba poznamenat, že CIE diagram neur�uje, jaké barvy se mají sta-novit jako základní. Každé technické za�ízení m�že proto mít své 3 základní barvy a tím i sv�j vlastní trojúhelník v chromatickém diagramu – viz obr. 4.6.


- 24 (120) -

Obr. 4.5. Chromatický diagram CIE

Obr. 4.6. Barevný rozsah obrazovky a tiskárny v rámci CIE diagramu

Teorie barev

4.2 Barevné modely

Standard CIE zmín�ný v p�edchozí �ásti sice stanoví po�et základních barev ne�eší však n�které d�ležité problémy a to:

1. které 3 konkrétní barvy se mají použít jako základní, 2. metodiku kombinace základních barev pro získání dalších barevných odstí-

n�. Jde o to: jednozna�n� popsat barvy a jejich složení.

Soubor základních barev a pravidla pro jejich míchání a zm�nu barevné charakteristiky jsou v po�íta�ové grafice definovány pomocí barevných mode-l�. N�které grafické systémy �asto obsahují n�kolik barevných model� a pro-st�edky pro p�evod mezi nimi.

Podle zp�sobu míchání základních barev rozeznáváme 2 barevné sys-témy – viz obr. 4.7:

1. aditivní 2. subtraktivní. V aditivních systémech se barvy p�idávají do �erné, která je barvou pozadí. �ím více barev se kombinuje, tím je výsledná barva b�lejší. P�ítomnost všech základních barev dává bílou, absence všech barev �ernou. Aditivní ba-revné prost�edí nepot�ebuje žádné vn�jší sv�tlo - jde o aktivní zdroje sv�tla. Typickým p�íkladem jsou barvy na monitoru.

Subtraktivní systémy pracují tak, že základní barvy jsou ode�ítány od bílé, která je v tomto p�ípad� barvou pozadí. �ím více ode�ítáme barvy, tím více se výsledná barva blíží k barv� �erné. Subtraktivní prost�edí je takové, které odráží sv�tlo, proto pot�ebuje vn�jší zdroj sv�tla. Svým charakterem jde o pasivní zdroje sv�tla jako jsou nap�. výstupy z tiskáren, sou�adnicových zapi-sova�� (tj. barvy na bílém papíru) apod.

a) b)

Obr. 4.7. Aditivní (a) a subtraktivní (b) míchání barev


- 26 (120) -

4.2.1 Model RGB

Tento model je založen na fyziologii lidského oka – viz obr. 4.3. Oko má 3 druhy barevných receptor�, p�i�emž první z nich je u v�tšiny lidí nejvíce citlivý na vlnovou délku 630 nm (�ervená), druhý na vlnovou délku 530 nm (zelená) a t�etí na vlnovou délku 450 nm (modrá). Od toho je také odvozen název modelu RGB, kde R (anglicky red = �ervená), G (anglicky green = zele-ná), B (anglicky blue = modrá). Této koncepci v praxi odpovídá výstup RGB barev na monitorech, kde jsou barvy vytvá�eny kombinací 3 základních barev: �ervené, zelené a modré. Barevný rozsah modelu RGB lze zobrazit prostorov� pomocí jednotkové krychle v osách r, g ,b - viz obr. 4.8.

Model RGB je aditivním systémem. Intenzity základních barev se s�íta-jí, p�i�emž se vytvá�ejí nové barvy – viz obr. 4.4. Každý barevný bod uvnit� krychle m�že být reprezentován jako uspo�ádaná trojice (r, g, b), kde rozsah hodnot r, g, b ∈<0,1>. Body na diagonále jednotkové krychle p�edstavují od-stíny šedi. Intenzity základních barev jsou v intervalu <0,1>. Hodnota nula znamená, že daná barevná složka není p�ítomna, hodnota 1 znamená, že daná barevná složka je p�ítomna ve své maximální intenzit�. Jednotlivé barevné složky si lze p�edstavit jako barevná sv�tla, která svítí do jednoho bodu. Když nesvítí žádné sv�tlo, tak dostaneme tmu neboli �ernou barvu, a když svítí všechna s maximální intenzitou tak dostaneme bílou barvu.

Obr. 4.8. Model RGB

modrá

azurová

purpurová

�ervená žlutá

zelená

�erná

bílá

Teorie barev

4.2.2 Model CMY(K)

Model RGB je vhodný p�edevším pro monitory. Lidské zkušenosti je bližší subtraktivní míchání barev. V malí�ství a v tiska�ské technice se obrázky tvo�í tak, že se barvy nanášejí v�tšinou na bílé pozadí. �ím více barev se p�idá-vá do bílé, tím více je výsledná barva temn�jší. T�mto aplikacím vyhovuje mo-del CMY, kde písmeno C je z anglického slova cyan (azurová), M znamená magenta (purpurová) a Y yellow (žlutá).

I tento model lze popsat jednotkovou krychlí v sou�adnicích c, m, y - viz obr. 4.9. Jde vlastn� o dopln�k krychle RGB (model CMY je vzhledem k modelu RGB komplementární). S�ítání hodnot CMY odpovídá subtraktivní-mu skládání barev, takže vrchol (1, 1, 1) reprezentuje �ernou barvu. P�evod mezi modelem RGB a CMY lze provést transforma�ní maticí:

c

m

y

r

g

b

�

�

��

�

�

=�

�

��

�

�

−�

�

��

�

�

111

(4.3)

Model CMY je vhodný pro tiska�skou techniku, kde se provádí soutisk 3 obrázk�, z nichž každý je nakreslen základní barvou. Tyto základní barvy však v�tšinou nejsou dokonale krycí, proto složením všech t�í nevznikne úpln� �erná barva. Vytvá�et �ernou barvu, která je obsažena v tém�� každém obrázku, pomocí t�í základních barev by však bylo neekonomické. Proto se �erná tiskne jako samostatná barva a lze ji použít i pro ztemn�ní ostatních barev. V polygrafii se tak z modelu CMY po dopln�ní �erné stává model CMYK, kde písmeno K je poslední znak z anglického slova black = �erný. Velikost �erné pro daný pixel získáme tak, že diskrétní hodnoty c. m. y snížíme o hodnotu k. P�evod mezi CMY a CMYK je dán vztahem:

(4.4)

Obr. 4.9. Model CMY

modrá

azurová

purpurová

�ervená žlutá

zelená

�erná

bílá

( )( )( )

�

�

��

�

�

=

�

�

��

�

�

−−

−

=

�

�

��

�

�

�

�

��

�

�

=

�

�

��

�

�

5,05,0

05,0

5,05,015,05,0

5,01

15,0

1

K

Y

M

C

Y

M

C


- 28 (120) -

4.2.3 Model HSV

Nevýhodou p�edchozích model� byla nesnadná p�edstavivost konkrét-ního barevného tónu ze 3 �íselných informací. Nap�. t�žko lze �íci bez p�ed-chozí zkušenosti, jaký je výsledný barevný tón, jas a sytost v modelu RGB, známe-li velikost složek (50, 30, 120) p�i 256 kvantiza�ních úrovních. Proto se hledaly další modely, které by byly bližší intuitivnímu chápání barev. Jedním z nich je model HSV, kde H je iniciála slova Hue tj. barevný tón, S je odvoze-no od slova Saturation = sytost a V znamená Value tj. hodnota (jasu). V odbor-né literatu�e se v této souvislosti hovo�í o tzv. oponentní teorii vid�ní.

• Barevný tón ur�uje p�evládající spektrální barvu. • Sytost reprezentuje p�ím�s jiných barev. • Jas je dán množstvím bílého (achromatického) sv�tla. Pro prostorové zobrazení modelu se používá šestiboký jehlan s vrcholem v po�átku sou�adnic h, s, v. - viz obr. 4.10. Rozsahy jednotlivých složek jsou:

• s, v ∈ <0, 1> • h ∈ <0, 360°>

Jak je vid�t z obr. 4.10., jas roste sm�rem k podstav�, st�ed podstavy znamená bílou barvu (W=white). Bod K (black) p�edstavuje �ernou barvu. Na úse�ce WK jsou soust�ed�ny odstíny šedi. Sytost je znázorn�na jako vzdálenost bodu od osy jehlanu. Dominantní barvy leží na plášti, �isté barvy jsou na ob-vodu podstavy. Výhoda proti model�m RGB resp. CMY spo�ívá v tom, že m�níme-li nap�. jen sou�adnici jasu (V), ostatní veli�iny (barevný odstín a sy-tost) se nem�ní, takže veli�iny h, s, v jsou na sob� prakticky nezávislé. Model navrhl a poprvé popsal Nyit v roce 1970.

Obr. 4.10. Model HSV

Teorie barev

4.2.4 Model HLS

I p�es zjevné zdokonalení ve srovnání s modely RGB a CMY má p�ed-chozí model HSV p�ece jen nevýhodu. Body o stejném barevném tónu leží v šestiúhelníku na rovin� �ezu kolmé ke svislé ose jehlanu. Pohyb v rámci šes-tiúhelníku však není vhodný z hlediska p�irozeného vnímání. P�irozen�jší pro naši p�edstavivost je pohyb po kružnici. Tomuto zp�sobu odpovídá model HLS, kde H znamená Hue = barevný tón, L je sv�tlost (Lightness) a S Satu-ration tj. sytost. V prostorovém znázorn�ní se model zobrazuje pomocí dvou kužel� s podstavami na sob� - viz obr. 4.11. Rozsahy díl�ích složek jsou:

• l, s, ∈ <0, 1> • h ∈ <0, 360°>

Obr. 4.11. Model HLS

Nejjasn�jší barvy mají S=1 a L=0.5 (body v podstavách obou kužel�). To odpovídá naší zrakové zkušenosti, protože nejvíce barev vnímáme p�i pr�-m�rné sv�tlosti (p�i malém nebo velmi intenzivním sv�tle nejsme schopni vní-mat barvy). Zvýšení sv�tlosti p�i nezm�n�né sytosti si lze p�edstavit jako p�i-dání jistého množství bílých a ubrání stejného množství �erných pigment�. Model HLS zavedla poprvé firma Tektronix v roce 1978.

Modely HSV a HLS umož�ují postupn� m�nit barevné charakteristiky p�i zachování ostatních typických vlastností barev.


- 30 (120) -

4.2.5 Munsell�v model

Je používán v mnoha profesích jako nap�. v textilním, keramickém a tiska�ském pr�myslu. Vychází z modelu HLS a respektuje citlivost lidského oka (nesymetrické hodnoty v sou�adnici sytost). Barva je definována kombina-cí tón (Hue)/jas (Value)/sytost (Chroma) nap�. 5Y/7/8 – viz obr. 4.12.

Chyba!

4.12. Munsell�v model

V rámci teorie oponentního vid�ní existují další modely nap�. CIE Yuv (1974), CIE LUV (1976), HVC (Tektronix 1988), CIELAB (1992). P�epo�et t�chto model� do modelu RGB nebo CMY nelze vyjád�it jednoduchým vzor-cem, ale musíme použít algoritmus. Z geometrického vyjád�ení t�chto barev-ných model� snadno zjistíme, že n�které hodnoty nejsou definovány (jsou za hranicí jehlanu nebo kužel�). Tyto stavy musí být p�i p�epo�tu ošet�eny.

4.2.6 Modely pro televizní techniku a videotechniku

V sou�asnosti existují 3 hlavní normy pro p�enos barevného televizního sig-nálu. Jsou to:

• YUV – evropská norma PAL (Phase Alternating Line – st�ídání fáze po �ád-cích). Normu zavedla n�mecká firma Telefunken. U nás za�ala podle této normy vysílat v roce 1990 �T3, v �ervenci 1992 pak i �T1 a �T2.

• YIQ - americká televizní norma NTSC (National Television Society Comit-tee – výbor národní televizní spole�nosti). V této norm� vysílají televize v Americe a Japonsku.

Teorie barev

• YCBCR – ruská norma SECAM (Séquentiel Couleur à Mémorie – postoupe-ní barevné informace do pam�ti). V této norm� se vysílá ve Francii, na Blíz-kém východ� a v n�kterých zemích Afriky a Asie.

V jednotlivých modelech Y p�edstavuje jas a zbývající 2 složky reprezentují barvu (modrá a �ervená). Spole�ným rysem t�chto model� je odd�lení jasové (lumina�ní) složky od barevných informací (chrominace). Díky tomuto odd�-lení je možno jednoduše p�ijímat barevný signál i na �ernobílé televizi – zobra-zí se pouze jasová složka a barevné složky se nevyužijí.

Tyto barevné modely nemají význam pouze pro televizní a videotech-niku, ale jejich výhod se využívá i v po�íta�ovém zpracování obrazu. Nap�. formát JPEG pracuje s barevným modelem YCBCR, rovn�ž tak mnohé formáty pro ukládání videa pracují v n�kterém z t�chto barevných model�.

Mezi modely pro televizní techniku a d�íve uvedenými modely existují jednozna�né p�evody. Vztahy pro p�evod jsou nap�. v [26] a [27].

4.3 Rozptylování barev

V p�ípad�, kdy barvy ve zdrojové grafické databázi neodpovídají bar-vám na výstupním za�ízení bu� co do po�tu (za�ízení m�že zobrazit jen ome-zený po�et barev) nebo co do konkrétních odstín�, používáme pro zobrazení speciální metody tzv. rozptylování barev:

• polotónování (angl. halftoning)- jde o techniku, která z n�kolika barev do-káže vytvo�it iluzi bohaté barevné stupnice. Princip spo�ívá v tom, že ba-revný pixel p�vodního obrázku je p�eveden na matici bod�, p�i�emž musí-me vysta�it s omezeným po�tem barev.

• rozptylovací metody (angl. dithering). Lze použít jak pro barevné tak i pro �ernobílé obrázky. Metody pracují na aditivním principu (výsledný paprsek je složen z n�kolika vstupních paprsk�). Jde o to rozmístit pixely díl�ích pa-prsk� ve výstupním obrázku tak, aby si oko z r�zných kombinací soused-ních bod� vytvo�ilo p�edstavu n�kolika odstín� barev.

4.3.1 Náhodné rozptýlení

Algoritmus náhodného rozptýlení pracuje takto:

Nech� Cin ∈ <0, 15> je vstupní intenzita jasu (odstín� šedi) a Cout ∈ <0, 1> výstupní intenzita jasu. Definujme funkci Random(15), která generuje celé náhodné �íslo z intervalu <0, 14>. Pro každý pixel o intenzit� Cin ∈ <0, 15> se vygeneruje pomocí funkce Random(15) náhodné �íslo, které se porovná s hodnotou pixelu takto: Je-li Cin > Random(15), pak Cout = 1 jinak Cout = 0. Rozm�r obrázku z�stane zachován.


- 32 (120) -

4.3.2 Maticové rozptýlení

Je metoda, kde jeden vstupní pixel je nahrazen skupinou (maticí) pixel� výstupních. Dojde tak ke zv�tšení obrázku. Nap�. vstupní obraz, jehož pixely mají intenzitu v intervalu Cin ∈ <0, 4>, máme p�evést na výstupní obraz, kde pixely budou mít intenzitu v rozsahu Cout ∈ <0, 1>: Matice p�íslušné jednotli-vým vstupním intenzitám pak mohou mít tento tvar:

Cin = 0 Cin = 1 Cin = 2 Cin = 3 Cin = 4

Pro více odstín� než je v p�edchozím p�ípadu použijeme matic vyššího �ádu. Je-li nap�. vstupní intenzita pixelu v intervalu Cin ∈ <0, 15> a výstupní intenzita Cout ∈ <0, 1>, pak existuje n�kolik �ešení. Dv� b�žn� používané vari-anty transforma�ních matic jsou uvedeny v dalším textu. První z nich Md je ur�ena pro displeje a vytvá�í k�ížový stínovací vzor. Druhá matice ozna�ená jako Mp vytvá�í ve výsledném obrázku puntíkový vzor a používá se p�edevším v novinách nebo na fotografiích.

0 12 3 15 1 5 9 2

Md = 8 4 11 7 Mp = 8 12 13 6 (4.5)

2 14 1 13 4 15 14 10

10 6 9 5 0 11 7 3

Transformace jasu podle matic probíhá takto: Každému bodu vstupního obrázku je p�i�azena matice 4 x 4 bod� ve výstupním obrázku. Je-li intenzita vstupního pixelu nap�. Cin = 10, pak v matici bod� výstupního obrázku je všem bod�m (prvk�m), které mají v transforma�ní matici hodnotu vyšší nebo rovnu 10 p�i�azena výstupní hodnota 1, ostatním bod�m (s hodnotou menší než 10) je p�i�azena výstupní hodnota 0. Zde je t�eba poznamenat, že r�zné firmy použí-vají i jiné tvary transforma�ních matic než jsme uvedli a jejich konkrétní podo-bu si chrání z konkuren�ních d�vod�.

Složit�jší situace nastane tehdy, chceme-li zachovat velikost obrázku. Pak místo matice bod� musíme použít jen jeden bod tj. jeden prvek transfor-ma�ní matice. Úkolem pak je vypo�ítat index daného prvku v matici. Nejjed-nodušší zp�sob je ten, kdy index prvku se vypo�ítá ze sou�adnic obrazového bodu podle vztah�:

i = x mod n

j = y mod n (4.6)

kde x. y jsou sou�adnice pixelu, jehož jas máme nahradit prvkem matice o in-dexu i, j, p�i�emž n je �ád matice.

Tím ovšem dochází ke ztrát� informace, kterou je nutno korigovat. Nej-b�žn�jší metoda pro korekci se nazývá distribuce chyby – viz dále.

0 1

Teorie barev

4.3.3 Distribuce chyby

princip metody spo�ívá v tom, že se modifikují pixely, které jsou sou-sední k danému tj. práv� zpracovávanému pixelu podle n�jakého pravidla. Jsou známy 4 r�zné postupy (Burkes, Stucki, Knuth, Floyd-Steinberg). Posledn� jmenovaný zp�sob si blíže popíšeme.

Floyd-Steinberg�v algoritmus distribuce chyby:

Nech� intenzita jasu pixelu ve vstupním obrázku je v intervalu Cin ∈ <0, 15> a intenzita jasu pixelu výstupního obrázku je v rozmezí Cout ∈ <0, 1>. Ozna�me si symbolem Cinakt intenzitu aktuálního pixelu vstupního obrázku, symbolem Coutakt hodnotu intenzity odpovídajícího pixelu ve výstupním (trans-formovaném) obrázku a symbolem Cinmax resp. Cinmin maximální resp. mini-mální hodnotu intenzity bodu vstupního obrazu (v našem p�ípad� Cinmax = 15, Cinmin = 0).

P�i transformaci postupn� zpracováváme jednotlivé pixely vstupního obrazu po �ádcích obrazové matice – viz obr. 4.13. takto:

Je-li Cinakt = 0, pak Coutakt = 0.

Je-li Cinakt = 15, pak Coutakt = 1.

Je-li Cinakt < Cinmax/2 pak Coutakt = 0, s chybou E = Cinakt - Cinmin kterou p�i�teme k sousedním pixel�m výstupního obrázku podle koeficient� znázor-n�ných pro nazna�ený stav zpracování na obr. 4.13. Nap�. pro Cinakt = 5 vychá-zí Coutakt = 0 (5 < 15/2) s kladnou chybou E = 5 – 0 = 5.

Je-li Cinakt > Cinmax/2 pak Coutakt = 1, s chybou E = Cinakt - Cinmax kterou rovn�ž distribuujeme k sousedním pixel�m výstupního obrázku jako v p�edchozím p�ípad�. Nap�. pro Cinakt = 11 je Coutakt = 1 se zápornou chybou E = 11 – 15 = – 4.

Koeficienty rozd�lení chyby mezi sousední pixely ve výše uvedeném algoritmu byly stanoveny empiricky.

3/16E 5/16E 1/16E

Obr. 4.13. Distribuce chyby podle Floyd-Steinberga

Zpracované pixely

Nezpracované pixely

Aktuální pixel

7/16E


- 34 (120) -

Další používané postupy (Stucki, Burkes, Sierra, Narcis – Judice – Nin-ke, Stevenson – Arce) se snaží p�enést chybu na v�tší po�et sousedních pixel� (až do 3 dalších �ádk�) než ve Floyd-Steinbergov� algoritmu. Nejlepší výsled-ky dává metoda Stevenson – Arce, ale pro svou pomalost (koeficient rozd�lení chyby 200 není mocninou 2, proto nelze použít rychlých aritmetických operací jako posun apod.) je prakticky nepoužitelná.

4.4 Shrnutí

Barva je vjem v lidském mozku zp�sobený �ástí spektra elektromagne-tického zá�ení (sv�tla) v intervalu od 4,3. 1014 Hz (�ervená) do 7,5. 1014 Hz (fialová). Transforma�ním prvkem mezi zdrojem zá�ení a vjemem je lidské oko, které má na r�zné vlnové délky sv�tla r�znou citlivost. Výslednou barvu skládá oko z jednotlivých složek na aditivním principu. T�chto poznatk� bylo využito i v technické praxi. Pro ur�ení sytosti, dominantního kmito�tu, kom-plementárního odstínu a barevného rozsahu slouží CIE diagram, kde každá konkrétní barva je dána váženým sou�tem 3 základních složek. Pro identifikaci konkrétní barvy a zp�sobu jejího získání byly vytvo�eny barevné modely, které pracují na principech:

1. aditivního míchání barev, kdy pozadí je �erné a výsledný odstín je dán sou�tem 3 základních barev. Typickým p�edstavitelem je model RGB, kde základními barvami jsou R (�ervená), G (zelená) a B (modrá),

2. subtraktivního míchání barev. Pozadí je bílé a od této barvy se ode�ítají hodnoty 3 základních složek, �ímž vznikne výsledný odstín. Reprezen-tantem je model CMY resp. (CMYK),

3. oponentní teorie vid�ní, která je blízká intuitivnímu chápání �lov�ka. Výsledný barevný odstín není ur�itý bod v 3D krychli jako v p�edcho-zích modelech, ale bod na mnohoúhelníku/kružnici (transformace z 3D do 1D vede k lepší orientaci) reprezentujícího t�lesa (jehlan, kužel) p�i-�emž zbylé 2 sou�adnice p�edstavují sytost a jas dané barvy.

Pokud za�ízení není schopno zobrazit všechny barevné odstíny, je nutné po-užít techniku rozptylování barev. K dispozici jsou tyto metody:

1. náhodné rozptýlení, které p�i�azuje každému pixelu konkrétní náhodnou hodnotu z rozsahu hodnot, které jsou na daném za�ízení zobrazitelné,

2. maticové rozptýlení, kde každému pixelu na vstupu odpovídá matice pixel� na výstupu, jejíž hodnoty a pozice aktivních prvk� jsou závislé na obrazové funkci daného pixelu,

3. distribuce chyby, která spo�ívá v tom, že každému pixelu se p�i�adí ur-�itá hodnota v rámci množiny výstupních hodnot a rozdíl mezi vstupní hodnotou a p�i�azenou výstupní hodnotou (chyba) se rozd�lí v ur�itém pom�ru k vybraným sousedním pixel�m.

Teorie barev

4.5 Autotest

1. Barva je

a) vjem b) vizuální informace c) druh elektromagnetického zá�ení

2. Na kterou barvu je lidské oko nejcitliv�jší?

a) �ervenou b) zelenou c) modrou d) bílou e) fialovou

3. Co ozna�uje písmeno K v barevném modelu CMYK?

a) �ernou barvu b) azurovou barvu c) jas d) kontrast e) sytost

4. Model RGB je založen na principu

a) aditivním b) subtraktivním c) oponentní teorie vid�ní d) jiném

5. V barevných modelech pro televizní techniku je konkrétní odstín ur�en:

a) 2 složkami + kontrastem b) 2 složkami + jasem c) 3 složkami

6. P�i jaké metod� rozptylování barev dojde ke zv�tšení obrázku?

a) distribuce chyby b) maticové rozptýlení c) náhodné rozptýlení

7. Podstata distribuce chyby spo�ívá

a) v eliminaci chyby b) v rozd�lení chyby mezi následující pixely

c) v rozd�lení chyby mezi p�edchozí pixely d) v kumulaci chyby k sou-sedním pixel�m


- 36 (120) -

5 Uložení obrázku do souboru

5.1 Fyzické a logické formáty dat

Zp�sob uložení grafické informace do souboru, jejich interpretace, zobra-zení a metoda komprese se �ídí ur�itým (v�tšinou standardním) p�edpisem, kterému se �íká grafický formát. Než p�istoupíme k jeho popisu, bude užite�né seznámit se s obecnými formáty dat, které se ve výpo�etní technice b�žn� pou-žívají. Podle vazby na technické za�ízení rozeznáváme 2 typy formát� – viz tab.5.1.:

1. logický formát, který je na technickém za�ízení nezávislý, má vysoký stu-pe� obecnosti a data v tomto formátu uložená k sob� n�jakým zp�sobem logicky pat�í a vycházejí z matematického modelu datové struktury,

2. fyzický formát, který je na technickém za�ízení závislý a je dán konstrukcí po�íta�ového subsystému ur�eného k uchování dat (registr, adresovatelná �ást pam�ti, sektor na disku apod.).

Tabulka 5.1. Logické a fyzické formáty dat v po�íta�i

Údajová struktura Logický formát Fyzický formát

Objekt Soubor Blok

Prvek objektu Záznam (n-tice, v�ta) Slovo

Atribut prvku objektu Položka (pole) Slabika (byte)

Elementární formát Bit Bit

Nejmenším možným elementárním formátem spole�ným pro oba typy je bit. Je to též jednotka informace. M�že nabývat dvou r�zných hodnot: 0, 1.

D�ležitá je interpretace informace uložené ve fyzickém formátu. Roze-znáváme 2 úrovn�:

1. bitovou úrove� tzv. bitové pohlaví, což je zp�sob uspo�ádání bit� ve slabice (byte). Ve slabice m�že být 8 bit� interpretováno 2 zp�soby:

a) nejvýznamn�jší bit je vlevo ( b�žné v praxi na IBM PC):

adresa bitu 7. bit 6. bit 5. bit 4. bit 3. bit 2. bit 1. bit 0. bit

1 0 0 0 1 0 1 0

význam bitu 27 26 25 24 23 22 21 20

uložená informace: (10001010) binárn� = 27 +23 +21 = 128+8+2 = (138) deka-dicky

Uložení obrázku do souboru

b) nejvýznamn�jší bit je vpravo

adresa bitu 0. bit 1. bit 2. bit 3. bit 4. bit 5. bit 6. bit 7. bit

1 0 0 0 1 0 1 0

význam bitu 20 21 22 23 24 25 26 27

uložená informace: (10001010) binárn� = 20 +24 +26 = 1+16+64 = (81) deka-dicky

2. úrove� slova, kde interpretace informace závisí na uspo�ádání slabik ve slov�. Zde rozeznáváme 3 r�zné varianty:

a) uspo�ádání ozna�ované jako malý endián (angl. little endian) – tj. p�ípad, kdy nejmén� významný byte je na nejnižší adrese ve slov�. U slova tvo�eného dv�ma slabikami (2B):

adresa i. i+1.

Lo - (low=nižší slabika) Hi – (high=vyšší slabika)

P�íklad: Všechny po�íta�e založené na procesorech fy. Intel, tedy i IBM PC.

b) uspo�ádání ozna�ované jako velký endián (angl. big endian), kde nejvýznamn�jší byte (byte 0) je na nejnižší adrese ve slov�:

adresa i. i+1.

Hi - (high = vyšší slabika) Lo – (low = nižší slabika)

P�íklad: Motorola modely 68000, 6820, 68030, 68040 atd.a po�íta�e na tomto procesoru založené (Commodore, Amiga, Apple Macintosh a n�které po�íta�e s OS UNIX), dále po�íta�e Sparc, MIPS, dále sálové po�íta�e t�ídy IBM a �ady JSEP v�etn� periferních za�ízení.

c) uspo�ádání ozna�ované jako st�ední endián (angl. medium endi-an) je kombinací obou p�edchozích p�ípad�. Vyskytuje se u slov složených ze 4 a více slabik.

P�íklad: Po�íta�e fy. DEC (Digital Equipment Corporation). Nap�. po�íta� PDP-11 má uspo�ádání 2-3-0-1 (�ísla znamenají po�adí slabik ve slov�).

P�i volb� velikosti logického formátu se doporu�uje respektovat toto d�ležité pravidlo:

Optimální uložení dat v po�íta�i a nejrychlejší p�ístup k nim nasta-ne tehdy, je-li logický formát dat roven bu� p�ímo fyzickému formátu nebo jeho celo�íselným násobk�m.


- 38 (120) -

5.2 Zp�sob uložení bod� obrazu do souboru

5.2.1 P�ímé a nep�ímé uložení pixelu

Obecn� pro uložení N r�zných hodnot logického formátu pot�ebujeme nejmén� k bit� fyzického formátu dle vztahu:

k = log2 N 5.1

Každý bod obrazu m�žeme do souboru uložit dv�ma zp�soby:

• p�ímo, kdy pixel nese p�ímo informaci o hodnot� svého barevného odstínu – viz obr. 5.1.,

• nep�ímo (angl. indirect), kde místo pro uložení pixelu obsahuje odkaz (in-dex) do tabulky barev, které se �íká barevná paleta – viz obr. 5.2.

i. pixel (i+1). pixel

R G B R G B

… 127 127 127 30 20 50 …

grafická databáze (�ást souboru)

R, G, B ∈ <0, 255> výstupní za�ízení (obrazovka)

Obr. 5.1. P�ímé uložení pixelu do souboru

i. (i+1). (i+2). pixel

P�i zobrazení se vyhledá v palet� hodnota (index) = 4

R, G, B ∈ <0, 255>

Obr. 5.2. Nep�ímé uložení pixelu do souboru

Paleta (nazývá se také mapa barev, indexová mapa nebo vyhledávací tabul-ka – angl. Look-Up-Table) je jednorozm�rné pole barev. Každý prvek palety má velikost

k = 3log2 N 5.2

index R G B

1

2

3

4 0 0 255

5

šedý pixel

(127,127,127)

4 1 11 výstupní za�ízení

(monitor)

modrý pixel na ob-razovce (0, 0, 255)

paleta (vyhledá-vací tabulka)

grafická databáze (�ást sou-

boru)


kde k je po�et bit� prvku palety, N je po�et úrovní každé ze základních složek barevného modelu nap�. RGB.

Výhodou palety je snadné zjišt�ní a jednoduchá modifikace barev p�ed-lohy. Pokud je pro uložení odkazu do palety zapot�ebí mén� bit� než pro ulo-žení hodnoty obrazové funkce celého pixelu, pak použití palety vede k úspo�e místa, jinak je lepší ukládat obraz p�ímo tj. bez palety. Nevýhodou palety je pomalejší p�ístup k pixel�m a tím i pomalejší zobrazení (hodnota každého pi-xelu se zjiš�uje dvojnásobným �tením). Další diskuse je v [26].

Palety m�žeme rozd�lit podle

1. po�tu složek na 1 prvek na • jednokanálové (jednobarevné), • mnohokanálové (1 prvek obsahuje n�kolik složek – typicky 3).

2. podle uspo�ádání na • pixelov� orientované, kde jsou všechny 3 složky barvy pixel� uloženy

v jednom �ádku vedle sebe – viz obr. 5.3, • plošn� orientované v nichž jsou barevné komponenty pixel� od sebe

odd�leny. Paleta vypadá jako by byla vytvo�ena ze 3 jednoduchých pa-let, z nichž každá p�ísluší jedné barevné složce. Hodnoty pixel� jsou uloženy v souboru jako n�kolikanásobné plochy – viz obr. 5.4.

Uvedené základní typy palet lze mezi sebou navzájem kombinovat. Toto uspo�ádání vycházelo z konstrukce starších grafických adaptér� EGA/VGA, které používaly až 4 obvodov� vytvo�ené barevné roviny. V sou�asné dob� se používají palety v grafických formátech z�ídka a to ve form� jednoduché ta-bulky – viz obr. 5.2. �len�ní do barevných rovin a kanál� je již historickou koncepcí, a proto se t�mito typy palet nebudeme dále zabývat. V�dychtivý �te-ná� najde bližší informace nap�. v [1] nebo [26].

5.2.2 Barevné módy

16 barev Tento barevný mód p�etrval ješt� z grafických adaptér� EGA. Dnes se

používá z d�vodu kompatibility mezi grafickými adaptéry, nebo� všechny gra-fické adaptéry ho podporují. Setkáme se s ním nap�íklad po startu po�íta�e, kdy se vypisují textová hlášení, p�i instalaci opera�ního systému a nebo p�i práci v nouzovém režimu Windows. Pro uložení jednoho pixelu používá tento ba-revný mód pouhé 4 bity. Do �ty� bit� zakódujeme 24 = 16 hodnot (0-15), které slouží jako indexy do palety o 256 barvách. Sou�asn� lze tedy zobrazit 16 ba-rev z 256ti možných.

256 barev Tento barevný mód je velmi podobný p�edchozímu. Rozdíl je v tom, že

pro jeden pixel zde používáme 8 bit� (1 bajt), což nám dává 28 = 256 r�zných


- 40 (120) -

hodnot. Barevná paleta zde tudíž má 256 index� barev, takže lze sou�asn� zob-razit 256 r�zných barevných odstín�.

Dynamická paleta

Barevné módy využívající paletu barev mají krom� omezení na maxi-mální po�et sou�asn� zobrazitelných barev i jednu výhodu. Touto výhodou je možnost velmi jednoduše a rychle zm�nit libovolnou barvu nebo skupinu barev na celé obrazovce pouhou modifikací položek v barevné palet�. Tímto jedno-duchým trikem lze dosáhnout p�sobivých efekt�, jako nap�íklad postupné roz-sv�cování nebo stmívání obrazovky, rotace barev, atd. Omezení na maximální po�et sou�asn� zobrazitelných barev lze obejít použitím tzv. dynamické palety, kdy se pro každý zobrazený snímek spo�ítá celá paleta (v pam�ti jsou snímky uloženy v pravých barvách – true color) na rozdíl od tzv. statické palety, kdy se pro všechny snímky používá stejná univerzální paleta.

High Color

Tento barevný mód na rozdíl od p�edcházejících nepoužívá paletu, ale jednotlivé barevné složky jsou zakódovány p�ímo do jednoho pixelu, který má velikost 16 bit� (2 bajty), což umož�uje zobrazit sou�asn� až 216 = 65536 r�z-ných barev. V n�kterých p�ípadech se používá zobrazení, které má velikost pixelu 15 bit�, poslední bit z�stává nevyužitý. V tomto p�ípad� lze sou�asn� zobrazit pouze 215 = 32768. Zbylý 16. bit se využívá 2 zp�soby:

1. pro zelenou složku tj. schéma: R = 5 bit�, G = 6 bit�, B = 5 bit�, protože lidské oko je nejcitliv�jší na barevné odstíny ze-lené,

2. pro p�ekrývání jako tzv. overlay bit. Je-li hodnota tohoto bitu rovna 1, je pixel zobrazen, v opa�ném p�ípad� je neviditelný nebo se zobrazí jen barva pozadí. Této metody se využívá p�i p�ekrývání oken apod.

Je vid�t, že základní barvy mohou mít pouze 32, respektive 64 odstín�. Toto omezení se objeví jako problém p�i souvislých p�echodech základních barev. P�i b�žné práci, hraní her nebo prohlížení fotografií se toto omezení jeví jako bezvýznamné. Výrobci ovlada�� pro grafické karty dokáží tyto nedostatky velmi výrazn� omezit použitím techniky zvané rozptylování (dithering).

True Color

Pro profesionální výtvarníky a um�lce ani tisíce barev nesta�í. Tito lidé pot�ebují mít na monitoru stejn� v�rn� barevný obraz, jako jim vytiskne tiskár-na nebo osvitová jednotka. �ešení tohoto problému je barevný mód, zvaný true color (pravé barvy). Stejn� jako p�edešlý barevný mód nepoužívá paletu, ale jednotlivé barevné složky jsou uloženy p�ímo v pixelu. Pro každou barevnou složku je vyhrazen jeden bajt, takže jeden pixel zabírá v pam�ti 3 bajty (24 bit�), proto se n�kdy ozna�uje také jako režim 24bitové barvy. Každý pixel tak m�že mít jednu z 224 = 16777216 možných barev, což je pln� dosta�ující pro jakékoliv použití. Nevýhoda tohoto barevného módu spo�ívá v tom, že jednot-


livé pixely jsou v pam�ti zarovnány po trojicích, což p�ináší nutnost p�istupo-vat k pixelu i na lichých adresách. Toto je velmi nevýhodné z hlediska rychlos-ti, proto se tento barevný mód používá tam, kde nepot�ebujeme animace nebo video, ale tam kde pracujeme se statickými obrázky.

True Color +

Práv� výše zmín�ný nedostatek 24bitového barevného módu m�l za ná-sledek vytvo�ení módu 32bitového. Barevné složky jsou uloženy stejn� jako v módu 24bitovém jako 3 bajty, navíc je p�idán jeden bajt, aby zarovnal pixel v pam�ti na hranici 4 bajt�, což je velmi výhodné z hlediska rychlosti p�ístupu do pam�ti. Nevýhodou je, že 4. bajt je nevyužitý.

RGBA

Tento barevný mód vychází z True Color+ a využívá zbylou 4. slabiku pro pr�hlednost pixelu. Této �ásti formátu, kde je pro pr�hlednost rezervováno 8 bit� se také �íká alfa kanál (odtud název RGBA). V našem p�ípad� lze pr�-hlednost nastavit plynule v rozsahu ∈ <0, 255>. Výsledný obraz (X) bude reprezentován �tve�icí RGB . Interpretace 2 obraz�, kde jeden (A) má nasta-venou pr�hlednost a druhý (B) se uvažuje jako nepr�hledný se vypo�ítá podle vztahu:

X = �A + (1 – �)B (5.3.)

V praxi se tohoto tzv. alfa míchání (alpha-blending) využívá k r�zným efek-t�m – viz nap�. televizní reklamy nebo scény z pohádkových �i scifi film� apod. Vzhledem k rychlosti a možnosti p�ímé práce s pr�hledností je tento ba-revný mód využíván zejména pro po�íta�ové hry.

5.3 Obecná struktura bitmapových soubor�

I když se jednotlivé grafické formáty soubor� od sebe liší, mají n�kolik spole�ných prvk� z nichž n�které jsou povinné, jiné nepovinné.

1. Povinné prvky grafických formát�:

- hlavi�ka,

- bitmapová data,

2. Nepovinné prvky grafických formát�:

- paleta,

- pata,

- ostatní datové struktury (tabulka vzorkovacích �ádk�, tabulka ba-revných korekcí, bitmapový index atd.).


- 42 (120) -

Každý grafický formát musí obsahovat oba povinné prvky (hlavi�ku i bitmapová data) a m�že být dopln�n p�íslušnou kombinací nepovinných prvk�. P�itom existují varianty, kdy v jednom souboru m�že být uloženo i n�kolik p�edloh (obrázk�). V tomto p�ípad� musí mít každá p�edloha sv�j blok bitma-pových dat, jejichž jednozna�ná identifikace je obsažena v hlavi�ce. Nejjedno-dušší strukturu má grafický formát, který obsahuje jen hlavi�ku a bitmapová data.

Podrobný popis a možné varianty uspo�ádání základních prvk� grafic-kých formát� jsou uvedeny nap�. v [1], [26].

Jádrem formátu jsou bitmapová data, která obsahují údaje o jednotlivých pixelech celé p�edlohy. Pixely mohou být v této �ásti uloženy:

• p�ímo – viz obr. 5.1. • nep�ímo prost�ednictvím palety – viz obr. 5.2.

V obou p�ípadech m�že být obraz v zakódovaném tvaru (je-li použito komprese dat). Aby se obraz mohl jednozna�n� rekonstruovat, musí uložené pixely korespondovat s body obrazové matice v p�edloze podle n�jakého p�e-dem stanoveného pravidla. V�tšinou se používá principu implicitního adreso-vání, kdy sou�adnice bodu obrazové matice v p�edloze je dána pozicí pixelu zapsaného v bitmapových datech. V praxi se používá dvou zp�sob�:

a) data zapsaná do vzorkovacích �ádk� – viz obr. 5.3. Tento zp�sob je nejpou-

žívan�jší. Pixely se zapisují do souboru sekven�n� podle �ádk� obrazové matice. V podstat� jde o transformaci index� bod� z dvourozm�rné obra-zové matice do lineárního pole v souboru. Postupuje se po �ádcích obrazo-vé matice a v rámci �ádk� po jednotlivých sloupcích. Za p�edpokladu, že bitmapová dat nejsou komprimována nebo jinak zakódována, lze za�átek každého i. �ádku zjistit z údaj� v hlavi�ce podle vztahu (5.4):

( )8

Im1BitCount

ageWidthiOffsetOffseti −+= (5.4)

Offseti je po�et slabik od za�átku souboru k 1. pixelu i. �ádku,

Offset je za�átek bitmapových dat tj. po�et slabik od za�átku souboru k 1. uloženému pixelu,

ImageWidth je ší�ka obrázku v pixelech,

BitCount je hloubka pixelu (po�et bit� na 1 pixel)

pixel 0 pixel 1 pixel 2 atd.

Vzorkovací �ádek 0 00 01 02 03 04 05 06 07 08 … … …

Vzorkovací �ádek 1



Obr. 5.3. Uspo�ádání obrazových element� do vzorkovacích �ádk�


b) planární data – viz obr. 5.4. V tomto p�ípad� jsou data rozd�lena do n�kolika ploch. Pokud má p�edloha

více než jednu barvu jde o tzv. kompozitní p�edlohu. Tyto p�edlohy jsou repre-zentovány t�emi bloky bitmapových dat, p�i�emž každý blok obsahuje pouze jednu barevnou složku.Filtrem lze barevné komponenty od sebe odd�lit. Každý blok je složen z �ádk�, bloky mohou být v souboru uloženy spolu nebo odd�le-n�. Tento formát je již historický a používal se tehdy, m�lo-li technické za�íze-ní možnost zobrazit v jednom okamžiku pouze jednu barvu.

02 05 08 11 modrá plocha

01 04 07 10 zelená plocha

00 03 06 09 �ervená plocha

Obr. 5.4. Uspo�ádání obrazových bod� do barevných ploch

S t�mito soubory je možné pracovat dvojím zp�sobem:

• p�i �tení je nejd�íve uložit do vyrovnávací pam�ti, kde se z díl�ích ploch sestaví celé pixely,

• použít speciální aplika�ní program, který pixely sestavuje p�i �tení (postup-n� �te bitmapu pixel po pixelu a zapisuje ji do výstupního za�ízení).

V�tšina bitmapových dat je uložena v neplanární form�.

5.4 Organizace bitmapových dat

Z hlediska vazby na technické prost�edky (disk, vyrovnávací pam��) mohou být bitmapová data v souboru uložena v podstat� t�emi zp�soby:

1. souvislá data 2. pásy (angl. strips) 3. dlaždice (angl. tiles), pop�. hierarchické dlaždice

Pixel 0

Pixel 1 Pixel 2

Pixel 3


- 44 (120) -

5.4.1 Souvislá data

Data jsou v souboru uložena postupn� po jednotlivých vzorkovacích �ádcích. To znamená, že �ádky obrazové matice p�edlohy se ukládají sekven�n� za sebou podle svých index� a v tomto po�adí jsou pak p�i rekonstrukci obrazu �teny. Soubor, v n�mž jsou data uložena souvisle, má ze všech uvedených va-riant nejjednodušší strukturu. Situace je z�ejmá z obr. 5.5.

Obr. 5.5. Uložení pixel� do souboru metodou souvislých dat

5.4.2 Pásy

Z hlediska efektivního uložení (logický formát má být pokud možno ce-listvým násobkem fyzického formátu) a s tím související rychlosti p�ístupu k dat�m je vhodné celý obrázek rozd�lit do menších �ástí. V praxi se používá d�lení na pásy a dlaždice.

V prvním p�ípad� je celý obrázek uložen v pásech, které se skládají ze vzorkovacích �ádk�. Pásy rozd�lují obrázek na segmenty –viz obr. 5.6, kde je znázorn�na obrazová matice p�edlohy o M �ádcích a N sloupcích, která je roz-d�lena na k pás�, z nichž každý obsahuje 2 vzorkovací �ádky.

Výhoda rozd�lení p�edlohy na pásy se projeví zejména p�i �tení kom-primovaných dat. Lépe se pracuje s jedním pásem než s celou objemnou bitmapou. Problémy se ovšem mohou objevit i v této organiza�ní struktu�e. M�žeme se setkat se souborem, který má sice pásovou strukturu, ale z n�jakých d�vod� jsou pásy mezi sebou zp�eházené, tj. �ísla jednotlivých pás� nejdou v po�adí za sebou. Veškeré údaje o struktu�e pás� musí být zaznamená-ny v hlavi�ce souboru. Další popis je v [26].


Obr. 5.6. Vzorkovací �ádky uspo�ádané do pás�

5.4.3 Dlaždice

Celý obrázek je rozd�len na nep�ekrývající se dlaždice o stejném rozm�-ru (v�tšinou násobky mocnin 2) – viz obr. 5.7. D�vody, které vedly k této struktu�e jsou stejné jako u uspo�ádání do pás� – vazba na kapacitu technic-kých prost�edk� konkrétn� na velikost vyrovnávací pam�ti pro �tení grafického souboru. Pokud definice formátu povoluje kódování, je možné pro r�zné dlaž-dice použít r�zná kompresní schémata podle toho, kolik barev daná dlaždice obsahuje.

Výhoda dlaždicové struktury spo�ívá v tom, že pokud vhodn� rozd�lí-me obrázek na dlaždice tak, že n�které z nich budou celé obsahovat pixely stejné barvy (nap�. barvu pozadí), pak se tyto dlaždice do souboru nemusejí ukládat v�bec (úspora místa na pam��ovém médiu). Podobný princip m�žeme použít tehdy, chceme-li zobrazit jen �ást p�edlohy – sta�í na�íst jen ty dlaždice, které jsou v dané �ásti.

Problémy p�i �tení dlaždicov� uspo�ádaného souboru mohou nastat teh-dy, jsou-li z n�jakých d�vod� dlaždice v souboru uloženy v jiném po�adí než v jakém byly definovány p�i rozd�lení p�edlohy (maticová struktura). V t�chto speciálních p�ípadech musí hlavi�ka souboru obsahovat adresy za�átk� (Offse-ty) všech dlaždic (tj. po�et slabik od po�átku souboru), aby rekonstrukce p�ed-lohy prob�hla korektn�. Další problém se m�že objevit tehdy, je-li v dlaždici uložena jen �ást obrázku a zbytek místa je vypln�n tzv. vycpávkou (nuly nebo pixely s barvou pozadí). Tento p�ípad nastane tehdy, není-li ší�ka dlaždice ce-listvým násobkem ší�ky p�edlohy a dlaždice na pravém okraji p�edlohy p�esa-hují svou ší�kou rámec obrázku.


- 46 (120) -

Obr. 5.7. Uspo�ádání obrazových dat do p dlaždic

5.4.4 Hierarchické dlaždice

Jde o progresivní metodu ukládání rastrových dat do souboru, která je založena na tom, že pokud budeme pracovat s obrázkem v r�zném rozlišení nebudeme jej vždy pot�ebovat vid�t celý, ale jen jeho ur�itou �ást.

Soubor:

Obr. 5.8. Hierarchické dlaždice

nejvyšší 1. úrove� – 1 dlaždice, rozlišení X

nejnižší k. úrove� 4k dlaždic, – rozli-šení monitoru X/2(k-1)

2. úrove�, 4 dlaždice rozli-

šení X/2

hlavi�ka 1. úrove� 2. úrove� k. úrove�


P�edloha je rozd�lena podle rozlišení do n�kolika hierarchických hladin a každá z nich obsahuje n�kolik dlaždic. Nejvyšší hierarchickou úrove� tvo�í jen 1 dlaždice v níž je celý obrázek v nejnižším rozlišení tak, aby se celý zob-razil na výstupním za�ízení (monitoru). V každé další hierarchické úrovni je obrázek rozd�len na 4 x víc dlaždic proti bezprost�edn� p�edchozí úrovni tj. má 2 x v�tší rozlišení. Tento zp�sob �len�ní vznikl na základ� empirických zkuše-ností. Situace je znázorn�na na obr. 5.8.

Obraz je tedy uložen v souboru tolikrát, kolik vzniklo hierarchických úrovní. Nevýhodou této metody proti výše popsaným je v�tší fyzická velikost souboru, což se �eší vhodným kompresním schématem. Nespornou výhodou je rychlost �tení a zobrazení na výstupním za�ízení, protože podle požadovaného rozlišení si aplikace vybere p�íslušnou hierarchickou úrove� a podle zadaného vý�ezu se na�tou konkrétní dlaždice z této úrovn�. Soubor se nikdy ne�te celý, ale jen jeho relevantní �ást, která je nezbytn� nutná pro danou konfiguraci zob-razení. Protože tato �ást je již v požadovaném rozlišení, nemusí se provád�t �asov� náro�né transformace ze zadaného vý�ezu obrazu do záb�ru okna na výstupním za�ízení jako je tomu u pás� a klasických dlaždic.

5.5 Výhody a nevýhody bitmapových formát�

Dosud popsané bitmapové grafické formáty mají své výhody i nevýho-dy, jejichž stru�ný vý�et si na tomto míst� uvedeme.

Výhody:

- bitmapové soubory lze snadno vytvo�it pomocí snímacího za�ízení (skeneru),

- pom�rn� snadno m�žeme v t�chto souborech modifikovat barevné odstíny a to bu� modifikací jednotlivých obrazových bod� nebo zm�nami v palet�,

- soubory lze bez složitých úprav p�enést na rastrová (bodová) vý-stupní za�ízení jako nap�. obrazovky, tiskárny.

Nevýhody:

- velikost bitmapových soubor� m�že být zna�ná (�ádov� desítky až stovky MB),

- pokud se pokusíme snížit fyzickou velikost souboru kompresí dat, pak zakódovaná data mohou n�kdy výrazn� snížit rychlost �tení a tím i rychlost rekonstrukce obrazu,

- problémy mohou nastat p�i zm�n� m��ítka obrázku – zmenšování nebo zv�tšování m�že n�kdy deformovat celou p�edlohu.


- 48 (120) -

5.6 Shrnutí

Po�et bit� k, které je zapot�ebí k uložení pixelu s hodnotou N je dán vzta-hem k=log2N.

P�i�emž zp�sob interpretace informace uložené v souboru závisí na kon-krétní platform�. V tomto smyslu rozlišujeme 2 úrovn�:

1. na znakové úrovni m�žeme �íst informaci zleva nebo zprava, což je dá-no tzv. bitovým pohlavím,

2. na úrovni slova (dvojslova) m�žeme �íst informaci v r�zném po�adí slabik (byt�), což ur�uje tzv. „endián“ (malý - PC, st�ední a velký).

Rozeznáváme fyzické (dané konstrukcí po�íta�e) a logické (matematické na platform� nezávislé) formáty.

Optimální uložení nastane tehdy, je-li pixel uložen práv� do celého fyzic-kého formátu nebo do jeho celistvých násobk�.

Pixel m�žeme do souboru uložit bu� p�ímo nebo nep�ímo jako index do tabulky barev tzv. palety.

Podle po�tu bit� pot�ebných k uložení 1 pixelu (tzv hloubky pixelu) roze-znáváme r�zné módy: binární (�ernobílý obraz), úrovn� šedi, 16 barev s pale-tou, 256 barev s paletou, dynamická paleta, Hi-Color (16 bit�), True-Color (24 bit�) a True-Color plus (32 bit�). Nevyužité bity ve fyzickém formátu se mo-hou využít k p�ekrývání obraz� a to bu� absolutnímu (1 bit - obraz je/není vi-d�t) anebo ke gradientnímu (8 bit�=256 stup��) p�ekrytí v alfa kanálu.

Komplexní informace o zp�sobu uložení celého obrázku do souboru a práci s ním se nazývá grafický formát. Je �len�n na základní (hlavi�ka, bitmapová data) a dopl�kové (paleta, pata, rezerva apod.) �ásti. P�itom jeden soubor m�že obsahovat i n�kolik p�edloh.

Vlastní bitmapová data m�žeme do souboru uložit po jednotlivých �ádcích obrazové matice nebo ve form� pás�, dlaždic �i hierarchických dlaždic. Toto uspo�ádání zrychluje p�ístup k externí pam�ti, kde je soubor v grafickém for-mátu uložen.


5.7 Autotest

1. Bitové pohlaví je uspo�ádání

a) slova v souboru b) slabiky ve slov� c) bit� ve slabice d) bit� ve slov�

2. Termínem „Endián“ ozna�ujeme uspo�ádání

a) slova v souboru b) slabiky ve slov� c) bit� ve slabice d) bit� ve slov�

3. Hloubka pixelu je 16 bit�. Kolik r�zných úrovní m�že nabývat hodnota ob-razové funkce pixelu?

a) 16 b) 32 c) 128 d) 32767 e) 65535

4. Ur�ete nejmenší po�et bit� pro uložení pixelu v pravých (True Color) bar-vách.

a) 12 b) 15 c) 24 d) 32 e) 48

5. Alfa kanál definuje

a) kompresi b) pr�hlednost c) endián d) bitové pohlaví

6. P�edloha obsahuje 640 x 480 pixel� s 256 r�znými odstíny barev. Kolik byt� zabírá celý obrázek v pam�ti?

a) 307200 b) 768 c) 307968 d) 921600

7. Povinnou �ástí v grafickém formátu je/jsou:

a) paleta b) pata c) hlavi�ka d) pásy d) dlaždice

8. Hlavi�ka v grafickém formátu neobsahuje

a) bitmapová data b) kompresní schéma c) identifikátor formátu

d) po�et planárních rovin e) po�átek bitmapových dat (offset)

9. Hlavním d�vodem uspo�ádání bitmapových dat do pás� a dlaždic je

a) úspora místa v souboru b) rychlost �tení a zobrazení c) zlepšení kompresního pom�ru d) rychlejší zápis (ukládání) grafické informace do sou-boru


- 50 (120) -

6 Komprese dat

6.1 Základní pojmy

Kompresí dat rozumíme redukci fyzické velikosti souboru dat p�i za-chování p�edem stanovené míry informace, která je v souboru obsažena. V kompresi dat se setkáváme s t�mito základními pojmy:

� hrubá data - data p�ed kompresí (nezakódovaná), � komprimovaná data - data po kompresi (zakódovaná), � kompresní pom�r = hrubá data/komprimovaná data

Kompresi dat m�žeme dále klasifikovat podle r�zných hledisek – viz [26]:

a) z hlediska interpretace obsahu dat � fyzická komprese, � logická komprese.

b) z hlediska symetrie kompresního procesu � symetrická komprese, � asymetrická komprese.

c) z hlediska p�izp�sobení algoritmu konkrétní struktu�e hrubých dat

� neadaptivní kódování, � adaptivní kódování, � semiadaptivní kódování

d) z hlediska ztráty informace

� neztrátová komprese též redukce redundance nebo entropické kódo-vání – Jde v podstat� o to, zakódovat daný obrázek úsporn�ji a efek-tivn�ji než jak je tomu v souboru s redundancí. Jak dokázal Shannon, je informace v souboru m��itelná pomocí entropie. Entropii jasu si i. pixelu m�žeme vyjád�it vztahem:

H(si) = – log2pi (6.1)

kde pi je pravd�podobnost výskytu i. pixelu.

� ztrátová komprese – redukce irelevance. Metoda je založena na 2 principech:

1. na respektování vlastností vyhodnocovacího za�ízení, které bude ob-rázek zpracovávat,

2. na ú�elu, pro který je daná p�edloha ur�ena.

Komprese dat

U tohoto zp�sobu komprese dat se snižuje informa�ní obsah obrazu tj. jeho entropie a to tak, že bu� to pozorovatel nepozná nebo jde o ú�elové zjed-nodušení popisu obrazové informace. Velkou výhodou ztrátové komprese proti neztrátové je možnost výrazného zvýšení kompresního pom�ru.

6.2 Pixelové zhušování

Jde o úsporné ukládání dat (pixel�) do fyzického formátu v pam�ti. Uve�me si p�íklad: Má-li p�edloha hloubku pixelu 4 bity (tj. 16 barev nebo úrovní šedi) a ukládá-li se 1 pixel na 1B (8 bit�), pak z�stává polovina pam�ti nevyužitá. Použijeme-li v tomto p�ípad� metody pixelového zhuš�ování, pak do formátu 1B uložíme 2 pixely po 4 bitech. Ušet�íme tím polovinu kapacity pam�ti oproti p�vodnímu zp�sobu. Situace je z�ejmá z obr. 6.1. Efekt úspory je však snížen složit�jším dekódováním programové aplikace p�i �tení souboru. Nejd�íve se musí p�e�íst celá slabika, pak se p�ekryjí maskou první 4 bity a zobrazí se 1. pixel. Dále se posunou horní 4 bity (logický posun o 4 bity dopra-va) a p�e�te se 2. pixel. Komprese je neztrátová.

7 0 7 0

1. pixel 2. pixel

a) uložení obrazových element� do 1B bez pixelového zhuš�ování

7 0

2. pixel 1. pixel

b) uložení obrazových element� do 1B metodou pixelového zhuš�ování

Obr. 6.1. Princip metody pixelového zhuš�ování

6.3 Komprese kvadrantovým stromem

U tohoto zp�sobu komprese dat jde o hierarchickou reprezentaci obra-zu. Kvadrantový strom vznikne dekompozicí obrazu na homogenní oblasti o rozm�ru 2k x 2k pixel�. Homogenní oblastí se p�itom rozumí oblast, v níž všechny body mají stejnou hodnotu obrazové funkce. P�edpokládá se, že vý-chozí p�edloha je �tvercová 2n x 2n pixel� a rozd�lí se na kvadranty, které se zpracovávají v ur�itém pevn� stanoveném po�adí – viz obr. 6.2. Ve stejném po�adí se také zpracovávají vrcholy kvadrantového stromu.


- 52 (120) -

1 2

3 4

Obr. 6.2. Po�adí zpracovávání kvadrant�

Algoritmus vytvo�ení kvadrantového stromu:

1. Inicializa�ní krok – vytvo�í se ko�en stromu tj. vrchol, který reprezentuje celý obrázek.

2. Je-li celá oblast (na po�átku jde o celý obrázek) homogenní, zapíše se do odpovídajícího vrcholu stromu hodnota barvy oblasti a algoritmus pro tuto oblast kon�í.

3. Je-li zpracovávaná oblast nehomogenní, rozd�lí se na kvadranty a daný vrchol se rozšt�pí na 4 vrcholy, odpovídající jednotlivým kvadrant�m.

4. Pro každý kvadrant se rekurzivn� provádí tento algoritmus.

Zápis kvadrantového stromu

Kvadrantový strom se zakóduje algoritmem prohledávání grafu do hloubky [23]. Výsledkem je �et�zec, který obsahuje hodnoty barev jednotli-vých list� stromu a speciální znak pro vrchol, jenž není listem stromu. Kódo-vání za�íná v ko�enovém vrcholu. Nemá-li vrchol následníky, zapíše se do �e-t�zce hodnota barvy v daném vrcholu, jinak se zapíše speciální znak (na obr. 6.3 je to *) a daný podstrom se zpracuje rekurzivn�.

Zp�tná rekonstrukce obrázku ze zakódovaného stromu probíhá ve 2 fázích:

a) Získání kvadrantového stromu z �et�zce:

1. Po�áte�ním symbolem je 1. znak �et�zce, aktuálním vrcholem je ko�enový vrchol.

2. Je-li aktuální symbol speciálním znakem, vytvo�í se v aktuálním vrcholu 4 listové vrcholy a algoritmus pokra�uje v prvním z nich.

3. Není-li aktuální symbol speciálním znakem, pak se do daného vrcholu za-píše jeho hodnota a pokra�uje se dalším vrcholem v po�adí.

4. Je-li vstupní �et�zec celý zpracován, algoritmus kon�í.

b) Získání obrázku z kvadrantového stromu: 1. Po�áte�ním (aktuálním) vrcholem je ko�en stromu a aktuální oblastí celý

obrázek. 2. Má-li aktuální vrchol následníky, rozd�lí se oblast na 4 kvadranty k nimž se

p�i�adí následníci a algoritmus se rekurzivn� opakuje pro jednotlivé oblasti. 3. Nemá-li aktuální vrchol následníky, celá aktuální oblast dostane barvu ak-

tuálního vrcholu.

Komprese dat

P�íklad konstrukce kvadrantového stromu je na obr. 6.3. Nejvyšší ú�innost komprese kvadrantovým stromem nastane tehdy, je-li každý kvadrant v obrázku homogenní, tj. má stejný barevný odstín.

Obr. 6.3. P�íklad konstrukce kvadrantového stromu

6.4 Proudové kódování (RLE)

Metoda vychází z toho, že v souboru se s jistou pravd�podobností vy-skytují shluky stejných znak�, které se dají zakódovat efektivn�. Zkratka RLE je odvozena z anglického termínu Run Length Encoding, což se v odborné lite-ratu�e p�ekládá bu� doslova jako kódování b�hu nebo proudové kódování.

Princip metody spo�ívá v tom, že �et�zce stejných znak� (n�kdy nazý-vané též proudy) jsou zakódovány do fyzického formátu 2B takto:

1. byte je tzv. proudové �íslo a udává po�et stejných znak� v �et�zci (délka proudu),

2. byte obsahuje proudovou hodnotu tj. hodnotu znaku.


- 54 (120) -

P�íklad 6.1.: Je dán �et�zec tvo�ený 7 znaky A: AAAAAAA

Po kompresi RLE je tentýž �et�zec zapsán do 2B takto: 7A,

kde 7 je proudové �íslo a A je proudová hodnota. Celému zápisu 7A se �íká RLE paket.

Nevýhoda této metody je projeví tehdy, je-li zdroj dat složen p�evážn� z jednoznakových �et�zc� nap�.ABCD. Pak je zakódovaný �et�zec fyzicky 2x v�tší než p�vodní tj. 1A1B1C1D a dochází k tzv. záporné kompresi. Komprese RLE je proto výhodná v souboru, kde se vyskytuje velké množství souvislých �et�zc� stejných dat. Algoritmus metody je neztrátový. V grafických souborech existuje n�kolik variant proudového kódování podle toho, jak se v p�edloze hledají posloupnosti stejných symbol�. Typické p�íklady jsou na obr. 6.4.

Obr. 6.4. Varianty proudového kódování

Dále uvedené varianty komprese RLE souvisejí s po�tem bit� na 1 pixel (hloubka pixelu).

6.4.1 Proudové kódování na bitové úrovni

Základním elementem kódování je bit. Ostatní fyzické formáty dat (sla-bika, slovo) se ignorují. Používá se jen u �ernobílých p�edloh, kde se vyskytují �et�zce bílých nebo �erných pixel�. Velikost RLE paketu je 1byte a má formát podle obr. 6.5:

Komprese dat

7 0

0 - 127

Obr. 6.5. RLE paket proudového kódování na bitové úrovni

P�íklad 6.2.: V �ernobílé p�edloze je �ada 38 bílých pixel�, které máme za-kódovat metodou RLE na bitové úrovni. Za p�edpokladu, že bílý pixel bude mít p�i�azenu hodnotu 1, bude RLE paket vypadat takto:

7 0

1 38

Všech 38 bílých pixel� bude zakódováno do jediné slabiky. Maximáln� lze takto zakódovat �et�zec až 27-1 = 127 stejných po sob� jdoucích pixel�. Po-kud je �et�zec delší než 127, pak se zbytek zakóduje do dalšího RLE paketu.

P�íklad 6.3.: Máme zakódovat �et�zec dlouhý 156 �erných pixel�. Kompres-ní schéma bude vypadat takto :

7 0 7 0

0 127 0 29 = 156-127

1. byte 2. byte

�et�zec bude zakódován do 2 po sob� jdoucích slabik.

6.4.2 Proudové kódování na slabikové (bytové) úrovni

Jde o nejrozší�en�jší zp�sob komprese RLE. Kódují se proudy slabik do dvou bytových paket�. Zarovnání na bity a slova se ignoruje (základním ele-mentem je slabika). Existují 3 varianty:

1. nekódovaný paket na bytové úrovni je na obr. 6.6. První byte obsahuje dél-ku �et�zce znak�, do druhé slabiky se ukládá hodnota opakujících se slabik.

7 0 7 0

délka proudu <0..255> hodnota proudu <0..255>

1. byte 2. byte

Obr. 6.6. Kompresní schéma RLE na bytové úrovni – nekódovaný paket

Hodnota proudu 0/1 Délka proudu

(proudové �íslo)


- 56 (120) -

2. kódovaný paket na bytové úrovni je na obr. 6.7. Má navíc tzv. indikátor proudu, což je nejvýznamn�jší bit 1. slabiky. Je-li jeho hodnota 0, pak je �et�zec nezakódovaný a znaky se musí zapisovat na výstup se stejnou hod-notou, jaká je v nich uložena. Má-li hodnotu 1, pak je �et�zec zakódovaný tj. ve zdrojové p�edloze existuje posloupnost znak� rovna hodnot� proudu (2. byte) o délce, kterou udává velikost proudu (1. byte).

7 6 0 7 0

délka proudu <0..127> hodnota proudu <0..255>

1. byte 2. byte

Obr. 6.7. Kompresní schéma RLE na bytové úrovni – kódovaný paket

P�íklad 6.4.: Zakódujme posloupnost znak� (1 znak=1byte) AAAAAAAAA-ABCDEF výše popsaným zp�sobem. Výsledek je na obr. 6.8.

1 10 A 0 5 B C D E F

Obr. 6.8. Zakódování �et�zce znak� AAAAAAAAAABCDEF

Na obr. 6.8. indikátor proudu = 1 informuje, že následuje 10 znak� o hod-not� A, indikátor ve druhém paketu = 0 naopak znamená, že následujících 5 znak� bude nezakódovaných a musí se interpretovat tak, jak jsou zapsány. Tím je vy�ešen problém záporné komprese, která by nastala p�i kódování pod�et�z-ce BCDEF podle varianty ad 1) kde každý znak (1 byte) by byl zakódován do 2 byt�.

3. p�ímý RLE paket na bytové úrovni – viz obr. 6.9. Zde jde o obdobu 2. �ásti p�edchozího p�íkladu.

7 0 7 0 7 0 7 0

hodnota hodnota hodnota

0 <0..127> proudu 1 proudu 2 proudu N

Obr. 6.9. Kompresní schéma RLE na bytové úrovni – p�ímý RLE paket

Kódování na bytové úrovni je výhodné pro ty p�edlohy, které mají hloubku pixelu 1 byte (1 pixel se zobrazí do 1 slabiky).

Indiká-tor proudu 0/1

Komprese dat

6.4.3 Proudové kódování na pixelové úrovni

Tento zp�sob má opodstatn�ní tehdy, je-li pixel p�edlohy uložen do n�kolika po sob� jdoucích slabik. Velikost paketu není konstantní, ale je závis-lá na hloubce (velikosti) pixelu. Jako v p�edchozí variant� lze použít 1. bitu ve schématu coby p�íznaku zakódování proudu. Kompresní schéma ukazuje obr. 6.10.

pixel p�edlohy

1 byte 1 byte 1 byte 1 byte

velikost proudový proudový proudový

proudu kanál �. 1 kanál �. 2 kanál �. 3

<0..255> <0..255> <0..255> <0..255>

hodnota proudu

Obr. 6.10. Kompresní schéma RLE na pixelové úrovni

6.4.4 RLE komprese PackBits

Je slabikov� orientované kompresní schéma, které se hodí pro kódování bytových proud�. Obsahuje 3 typy datových paket�:

1. Dvouslabikový kódovaný proudový paket, kde 1. slabika udává délku proudu tj. po�et byte v proudu v rozsahu <0..127>. K této hodnot� se musí ješt� p�i�íst 1, takže skute�ná velikost proudu je v rozsahu <1..128>. Druhá slabika obsahuje hodnotu bytu v proudu.

2. P�ímý proudový paket (nezakódovaný). Jde o posloupnost 2 – 128 ne-

zakódovaných byt� (�ili p�ímo hodnot pixel�), které jsou uvozeny dél-kou proudu. Hodnota proudu je v rozsahu <-127..-1> a má ve skute�-nosti význam (p�i dekódování) jako –(-127..-1)+1 což je <2..128>. Pou-žívá se k ukládání dat s malým po�tem proud� nap�. u složitých zašu-m�lých p�edloh.

P�íklad 6.5.: Metodou PackBits máme zakódovat posloupnost 29 pixel� v p�ímém kódu tj. každý pixel bude mít v p�íslušném bytu hodnotu svého ja-su. �ešení je na obr. 6.11.

-28 pixel 1 pixel 2 pixel 28 pixel 29

Obr. 6.11. Uložení posloupnosti 29 pixel� v p�ímém kódu metodou PackBits


- 58 (120) -

3. No-op paket. Má délku 1 slabiky s konstantní hodnotou –128. Používá se v kompresním schématu k dorovnání fyzického formátu dat.

6.4.5 RLE komprese se t�emi slabikami

Vyskytují-li se v p�edloze dlouhé proudy (nad 127 znak�), pak je p�edchozí metoda PackBits nevýhodná. Pro tento p�ípad je vhodné použít RLE schéma se t�emi slabikami. K p�vodním 2 slabikám se p�idává p�íznaková slabika, která ur�uje, zda následující znaky jsou �i nejsou zakódované. P�íznaková slabika m�že mít 2 varianty:

1. má-li p�íznaková slabika hodnotu 255, pak bezprost�edn� následující 2 slabiky reprezentují zakódovaný proud dat tak, jak to ukazuje obr. 5.7.

2. je-li v p�íznakové slabice uložena hodnota r�zná od 255 tj. 0..254, po-tom tato hodnota udává po�et nezakódovaných pixel�, které po ní bez-prost�edn� následují.

P�íklad 6.6. - RLE komprese se t�emi slabikami je na obr. 6.12.

1B 1B 1B

255 14 138

a) zakódování proudu 14ti pixel�, každý o hodnot� jasu 138

1B 1B 1B 1B 1B

4 17 128 54 211

b) uložení 4 pixel� v p�ímém kódu (pixely mají hodnoty 17, 128, 54 a 211)

Obr. 6.12. Princip komprese RLE se t�emi slabikami

6.4.6 Vertikální replika�ní pakety

Používají se tehdy, obsahuje-li p�edloha n�kolik stejných �ádk�, které jdou bezprost�edn� po sob�. Z nich se zakóduje jen �ádek první a dále se zapíše údaj, kolikrát se daný �ádek opakuje. Existují 2 varianty: jednoslabikový a dvouslabikový vertikální replika�ní paket.

P�íznaková slabika

P�íznaková slabika

Komprese dat

P�íklad 6.7.: Zakódujte 100 �ádk� p�edlohy, které mají stejný odstín (v na-šem p�ípad� 145) o délce 127 znak�/�ádek. �ešení je na obr. 6.13.

délka �ádku hodnota 0 1 99

127 145 0 0 0

a) jednoslabikový vertikální replika�ní paket

délka hodnota opakující se opakující se

p�íznak hodnota

127 145 0 0

b) dvouslabikový vertikální replika�ní paket

Obr. 6.13. Vertikální replika�ní pakety

6.5 Slovníkové metody (LZW)

Jde o nejrozší�en�jší zp�sob komprese dat v po�íta�ové grafice. Používá se nap�. ve formátech GIF, TIFF a dalších. Komprese je neztrátová a lze do-sáhnout kompresního pom�ru 2:1 až 4:1. Metodu navrhli Abraham Lempel a Jakob Ziv v roce 1977. V roce 1978 modifikoval algoritmus Terry Welch pro diskové �ídicí jednotky. Podle iniciál jmen t�chto autor� dostala metoda název LZW. Kompresní algoritmus je slabikov� orientovaný (kóduje data do slabik) a pracuje jen s pevnou �ádovou �árkou (celo�íselná aritmetika), �ímž se dosahuje vyšší rychlosti než kdyby operace probíhaly v pohyblivé �ádové �árce (expo-nent, mantisa).

Metoda je založena na substituci �et�zc� znak� �et�zci kratší délky. Algoritmus vytvá�í slovník dat (též zvaný p�ekladová nebo �et�zcová tabulka), obsahující pod�et�zce, které se vyskytují v nekomprimovaném toku dat. Pokud se �et�zec ve slovníku nevyskytuje, za�adí se jako nová fráze do slovníku. Frá-ze se pak zapíše do výstupního (komprimovaného) souboru. Pokud se daný pod�et�zec v originálním souboru op�t objeví, je do výstupního souboru zapsá-na hodnota fráze (nap�. po�adové �íslo). Protože fráze je kratší než p�vodní pod�et�zec, je dosaženo kladné komprese dat.

Varianty LZW:

• spojování 2 frází dohromady,

• pr�b�žné sledování kompresní ú�innosti (p�i poklesu ú�innosti se po-sledn� vložená fráze vy�adí, pop�. se p�ebuduje celý slovník).


- 60 (120) -

Algoritmus komprese LZW

Postupn� se vytvá�í tabulka o dvou sloupcích. V 1. sloupci je kódovaná posloupnost, ve 2. sloupci je komprima�ní kód. Pro pot�eby algoritmu si zave-deme tyto pomocné prom�nné:

• P = prefixový �et�zec,

• H = prom�nná pro aktuální znak,

• PH = spojení �et�zce P a znaku H,

• Zásobník = pole pro uložení �et�zce znak�

Vlastní algoritmus:

1. Inicializace tabulky.

2. Na�te se 1. znak ze vstupu do pomocné prom�nné P, což je prefixový �et�zec.

3. Není-li na vstupu další znak, algoritmus kon�í.

4. Na�te se další znak do pomocné prom�nné H.

5. Existuje-li �et�zec PH v tabulce, p�idá se H na konec P a pokra�uje se krokem 3.

6. Neexistuje-li PH v tabulce, pak se PH do tabulky za�adí a P se zapíše do výstupního souboru. Znak H se uloží do P (takže P bude obsahovat jediný znak H) a pokra�uje se krokem 3.

Algoritmus dekomprese LZW

1. Inicializace tabulky.

2. Na výstup se pošle první na�tený znak/kód.

3. Není-li už žádný další znak, algoritmus kon�í.

4. Ze vstupního souboru se na�te další znak/kód.

5. Je-li na�tený znak kód, vyhledá se v tabulce p�íslušný �et�zec a za�adí se do zásobníku. Není-li na�tený znak kódem, zapíše se do výstupního souboru.

6. Není-li zásobník prázdný, vybere se znak ze zásobníku. Jde-li o kód, vyhledá se k n�mu p�íslušný �et�zec a za�adí se na jeho místo do zásob-níku. Jde-li o znak, zapíše se do výstupního souboru.

7. Pokra�uje se krokem 3.

Na principu slovníkové komprese pracují známé komprima�ní programy jako nap�. WINZIP, PKZIP, PKUNZIP, LHARC, ICE, ARJ, RAR apod.

Komprese dat

6.6 Huffmanovo kódování

Z teorie informace vyplývá, že p�i nezávislém kódování jednotlivých symbol� je optimální, když se symbol si (reprezentující obrazovou funkci pixe-lu) zakóduje pomocí H(si) bit�, kde

( ) ii psH 2log−= (6.2)

p�i�emž pi je pravd�podobnost výskytu symbolu si v souboru – viz kap. 6.1.

David Huffman navrhl v roce 1952 kód, který se k této teoretické hrani-ci blíží. Lze dokázat, že mezi všemi kódy, které používají celo�íselný po�et bit� k reprezentaci jednoho symbolu je Huffman�v kód ten nejkratší.

Princip metody spo�ívá v tom, že se symbol�m, které se v souboru vy-skytují nej�ast�ji, p�i�azují nejkratší možné kódy na bitové úrovni. Komprese probíhá ve 2 fázích:

1. zjišt�ní �etnosti všech symbol�,které se v souboru vyskytují a set�í-d�ní tohoto seznamu sestupn� podle hodnoty �etnosti,

2. zakódování symbol� podle �etnosti ad 1).

Symboly s nejnižšími pravd�podobnostmi výskytu (nejnižšími �etnost-mi) postupn� slu�ujeme po dvojicích, až získáme dva symboly s nejv�tšími pravd�podobnostmi (�etnostmi) výskytu. P�i slu�ování má slou�ený symbol pravd�podobnost (�etnost) výskytu rovnu sou�tu pravd�podobností obou slu-�ovaných symbol�. Posledním dv�ma symbol�m p�i�adíme nejkratší binární kódy tj. 0 a 1. Pak postupujeme opa�ným sm�rem a p�idáváme rozlišovací bity (kódy se spole�ným za�átkem), až dostaneme jednozna�n� dekódovatelný bi-nární kód každého vstupního symbolu.

Huffman�v kód pro X symbol� má délku zprávy maximáln� k bit�, kde

[ ]�=

−=X

iipk

12log (6.3)

a výraz v hranaté závorce je zaokrouhlen sm�rem nahoru na celé �íslo.

P�íklad:6.8.:

Soubor, který obsahuje tuto posloupnost znak�: AXCTXCRCTCX máme zakó-dovat Huffmanovým kódem.

�ešení je uloženo v tabulce 6.1. První dva sloupce se vytvá�í v 1. fázi, kdy se zjiš�uje �etnost výskytu symbol� v dané množin� (souboru). 3. sloupec se vypl-�uje ve 2. fázi podle tohoto pravidla: Nej�etn�jším symbol�m se jednozna�n� (tj. tak, aby jednotlivé symboly byly svým kódem rozlišitelné) p�i�adí kód s nejmenším možným po�tem bit�.


- 62 (120) -

Schéma p�i�azování kód� je na obr. 6.14. V kulaté závorce jsou u jednotlivých symbol� uvedeny jejich �etnosti resp. sdružené �etnosti (u složených symbol�) výskytu v souboru, v hranaté závorce pak p�i�azený binární Huffman�v kód.

Vstup: AXCTXCRCTCX (celkem 11 znak� tj 11 byt� = 88 bit�)

C (4) C (4) C (4) C (4) [0]

X (3) X (3) X (3) [10]

X,T,A,R (7) [1]

T (2) T (2) [110]

T,A,R (4) [11]

A (1) [1110]

A,R (2) [111]

R (1) [1111]

Obr. 6.14. Schéma odvození Huffmanova kódu k p�íkladu 6.8.

Tabulka 6.1. etnosti výskytu symbol� a jim p�i�azené kódy

Symbol (znak) etnost výskytu Huffman�v kód

C 4 0

X 3 10

T 2 110

A 1 1110

R 1 1111

Výstup: 111010011010011110110010 (celkem 24 bit� tj. 3 byty)

Kompresní pom�r v našem p�íkladu (délka vstupu)/(délka výstupu)=11/3 = 3,7.

Huffman�v kód byl za�azen do standardu CCITT (Consultative Comit-tee International Telegraph and Telephone – standardiza�ní organizace pro p�enos dat). Standardizovány byly celkem 3 varianty Huffmanova kódu, které dostaly toto ozna�ení:

1. Group 3 jednorozm�rné (G31D) 2. Group 3 dvourozm�rné (G32D) 3. Group 4 dvourozm�rné (G42D)

Komprese dat

Vysv�tleme si nyní tyto pojmy:

Group 3 je speciální kompresní algoritmus ur�ený pro dvouúrov�ové (�ernobílé) p�edlohy dokument�, které se nej�ast�ji používají v p�enosu dat (fax). Dosahuje kompresního pom�ru 5:1 až 8:1.

Varianta Group 4 má zdokonalený kompresní algoritmus proti Group 3 s ú�inn�jším kompresním pom�rem (až 50%). Neobsahuje synchroniza�ní kó-dy – nap�. kód signalizující konec �ádku EOL (End Of Line).

Algoritmy jsou neadaptivní tj. nep�izp�sobují se každé p�edloze tak, aby byla komprimována s optimální ú�inností. Používá se pevných tabulek, které byly navrženy podle referen�ních (typických) p�edloh, které se v praxi vyskytují. Posuzovány byly jak ryze textové tak i obecné grafické p�edlohy (text + obrázky). Na základ� analýzy t�chto dokument� byly navrženy tabulky dvojího druhu:

1. Tabulka vytvá�ecích kód�, reprezentujících zakódované �et�zce stejných pixel� (�erných nebo bílých) o délce v�tší než 64,

2. Tabulka terminálních kód� (kódy, které reprezentují posloupnost stejných pixel� o délce maximáln� 64).

Každá z t�chto tabulek má 2 �ásti: 1. tabulku pro kódování posloupnosti �erných pixel� a 2. tabulku pro kódování bílých pixel�. Tím odpadá 1. fáze Huffmanova kódování a to zjiš�ování �etnosti výskytu jednotlivých pixel� v p�edloze. Ukázka �ásti t�chto kód� je ve skriptech [26] na str. 61, úplné kó-dovací tabulky CCITT Group3 a Group4 jsou nap�. v [11].

Zbývá vysv�tlit ješt� termín jednorozm�rné a dvourozm�rné kódování.

Jednorozm�rné kódování 1D je jednoduché, protože se kódují jen line-ární posloupnosti �erných resp. bílých pixel� ve vstupním souboru podle stan-dardních tabulek.

U dvourozm�rného kódování se každý �ádek kóduje relativn� vzhledem k �ádku p�edchozímu. Praxe totiž potvrdila, že s velkou pravd�podobností se bezprost�edn� po sob� jdoucí �ádky �ernobílé p�edlohy od sebe bu� neliší v�-bec nebo jen velmi málo. Potom sta�í zakódovat jen první �ádek a v dalších �ádcích zachytit jen zm�ny oproti �ádku p�edchozímu. Jelikož 1. �ádek nemá p�edch�dce, postupuje se tak, že se kóduje podle fiktivního 0. �ádku, který je složen ze samých bílých pixel�. Tomuto zp�sobu se �íká vertikální kódování. Pokud se daný �ádek proti p�edchozímu odlišuje tak, že by kódování zm�n bylo složité a neefektivní, zakóduje se samostatn� podle standardních tabulek tzv. horizontálním kódem. Pro metodu 2D pot�ebujeme krom� standardních tabulek ješt� zvláštní �ídicí kódy, které jsou v tabulce 6.2.

Vysv�tlivky:

V(x) Vertikální kódy. X je �íslo, které udává o kolik pozic v ose x se pixel v daném �ádku liší od pozice nejbližšího pixelu v bezprost�edn� p�edcho-zím �ádku. Znaménko + udává posun vpravo, znaménko – posun vlevo.

Hor Horizontální kód. Signalizuje, že od daného místa je �ádek za-kódován podle standardních tabulek pro 1D kódování.


- 64 (120) -

Tabulka 6.2. Kódy pro dvourozm�rné kódování 2D

Název kódu Hodnota kódu (bitová kombinace)

V(0) 1

V(+1) 011

V(+2) 000011

V(+3) 0000011

V(-1) 010

V(-2) 000010

V(-3) 0000010

Hor 001

Pass 0001

Pass Pr�b�žný kód. Používá se tehdy, pot�ebujeme-li ignorovat dv� zm�ny (bílá – �erná a zp�t �erná – bílá) v p�edchozím �ádku (�et�zec stejných pixel� v aktuálním �ádku pokra�uje, zatímco v p�edchozím �ádku je v daném míst� p�erušen skupinou pixel� jiné barvy).

P�íklad 6.9.:

Na obr. 6.15. je �ást n�jaké p�edlohy (2 bezprost�edn� po sob� jdoucí �ádky). �ádek ozna�ený šipkou zakódujte vertikálním kódem.

Referen�ní �ádek

�ádek, který se má zakódovat

Mnemokód: V(0) V(0) V(-1) Pass V(+1) V(+2)

Výsledný kód : 1 1 010 0001 011 000011

Obr. 6.15. ást �ernobílé p�edlohy pro p�íklad 2D komprese

Komprese metodou 2D je velice ú�inná a lze dosáhnout kompresního pom�ru až 25:1. Huffmanovo kódování je bezeztrátové a používá se p�evážn� pro �ernobílé (binární) p�edlohy.

Variantou Huffmanovy metody je tzv. aritmetické kódování. Je to roz-ší�ení Huffmanova kódu na spojité systémy což znamená, že kód není omezen celo�íselným po�tem bit�. Bližší informace jsou v [1].

Komprese dat

6.7 Predik�ní metody

Jsou založeny na tom, že sousední body obrazu mají s velkou pravd�-podobností vysoký stupe� korelace. Za tohoto p�edpokladu je možné hodnotu pixelu odhadnout z hodnot vzork� (jasu pixel�) p�edcházejících (z toho je od-vozen i název – predik�ní metody). Na obr. 6.16. je v �ásti p�edlohy znázorn�-no 7 pixel�. Symbolem X je ozna�en aktuální tj. práv� zpracovávaný pixel, symboly A, B, C, D, E reprezentují p�edch�dce pixelu X. Hodnotu x pixelu X vypo�ítáme podle vztahu:

( ) pxeedcbafx += ,,,, (6.4)

kde f je vhodná predik�ní funkce, a, b, c, d, e jsou hodnoty p�edch�dc� pixelu X a epx je predik�ní chyba pro pixel X.

A, B, C, D, E - p�edch�dci pixelu X

Obr. 6.16. �ást obrazu pro predik�ní kódování

Protože predik�ní funkce je pro všechny pixely stejná, má smysl zapi-sovat do souboru jen predik�ní chyby jednotlivých pixel�. Jelikož predik�ní chyba je výrazn� menší než obrazová funkce pixelu, pot�ebujeme pro její ulo-žení mén� bit� než pro uložení obrazové funkce. V tom spo�ívá princip kom-prese touto metodou. Uložíme-li predik�ní chybu beze zm�ny nebo bezeztráto-vou kompresí (na obr. 6.17. pracuje kodér/dekodér VWL podle Huffmanova kódu) jde o bezeztrátovou metodu, pokud predik�ní chybu dále kvantujeme, jde o ztrátovou metodu komprese. Schéma je na obr. 6.17.

x(n) – vstupní signál, xp(n) – predikovaná hodnota, ep(n) – predik�ní chyba, epq(n) – predik�ní chyba kvantovaná, P – prediktor, Q – kvantizér, VWL – Va-riable Word Length (slovo s prom�nnou délkou), y(n) – výstupní signál.

Obr. 6.17. Blokové schéma pro a) ztrátovou a b) bezeztrátovou kompresi pre-dik�ní metodou


- 66 (120) -

Bezeztrátová predik�ní komprese je sou�ástí standardu JPEG pro ob-rázky s mnoha úrovn�mi šedi. Prediktory se liší �ádem a rozm�rem. �ád pre-diktoru udává po�et p�edch�dc�, které se používají v predik�ní funkci (viz vztah 6.4.). Rozm�r prediktoru závisí na poloze p�edch�dc�, které se používají v predik�ní funkci. P�edch�dci ze stejného �ádku vedou na 1D prediktor, p�ed-ch�dci v r�zných �ádcích (horizontálních i vertikálních) implikují 2D prediktor a p�edch�dci v r�zných �ádcích a v �asové domén� vedou na 3D prediktor – viz tab. 6.3.

Tab. 6.3. �ád a rozm�r predik�ní funkce (predikátoru) pro obr. 6.16. Pixel E je p�evzat z p�edchozího p�lsnímku.

Predik�ní funkce Rozm�r prediktoru ád prediktoru

X = f(A, C, E) 3D 3

X = A 1D 1

X = (A + C)/2 2D 2

X = C 1D 1

X = E 1D 1

X = f(A, B, C, D) 2D 4

6.8 Waveletová (vlnková) transformace

Wavelets (vlnky) jsou matematickým nástrojem pro hierarchickou de-kompozici funkcí. Umož�ují popsat funkci hrub� pomocí celkového tvaru a prost�ednictvím detail�, které jsou uspo�ádány od mén� podrobných k jemným detail�m. Mají své uplatn�ní jak v aproximaci a zpracování signálu tak i v po-�íta�ové grafice jako editace, komprese, vyšet�ování (querying) obrazu, �ešení simula�ních úloh a osv�tlení. Pro ilustraci si uvedeme jednoduchý p�ípad Haa-rových wavelet�.

Pro jednoduchost p�edpokládejme 1D obraz s rozlišením 4 pixel� s hodnotami:

9 7 3 5

Ve waveletové transformaci s Haarovými bázemi sdružíme dvojice pixel� po-mocí aritmetických pr�m�r�, takže dostaneme hodnoty 8=(9+7)/2 a 4=(3+5)/2:

8 4

Zpr�m�r�ováním jsme ovšem ztratili jistou informaci. Abychom mohli obraz zp�t rekonstruovat, musíme uchovat ur�ité koeficienty detail�, které ne-sou ztracenou informaci. První koeficient detailu je 1, protože 9 = 8 + 1 a 7 = 8 – 1. Druhý koeficient je –1, protože 3 = 4 + (–1) a 5 = 4 – (–1). P�vodní obraz je transformován na dvoupixelovou verzi s nižším rozlišením a se dv�ma koe-

Komprese dat

ficienty detail�. Rekurzivním opakováním celého procesu získáme kompletní dekompozici podle tab. 6.4.

Tab. 6.4. Dekompozice obrazu se 4 pixely

Rozlišení Pr�m�ry Koeficienty detail�

4 9, 7, 3, 5

2 8 4 1 –1

1 6 2

Nyní m�žeme definovat waveletovou transformaci s jednorozm�rnou Haarovou bází p�vodního obrazu jako jediný koeficient (6) a dopln�ný �adou koeficient� detail� v po�adí zvyšujícího se rozlišení:

6 2 1 –1

Je vid�t, že transformace je bezeztrátová a obraz m�žeme rekonstruovat zp�t na libovolné rozlišení. Princip komprese touto metodou spo�ívá v tom, že koeficienty detail� jsou mnohonásobn� menší než hodnoty pixel� a podle vzta-hu (5.1) pot�ebujeme k jejich uložení menší kapacitu pam�ti. Zkrácením nebo zanedbáním malých koeficient� vzniká v rekonstruovaném obrazu jen malá chyba, ale tato komprese je již ztrátová.

6.9 Komprese založená na redukci barev

Jde o ztrátovou metodu, založenou na snížení po�tu barevných odstín� v p�edloze. Pat�í sem i polotónování a rozptylování barev, popsané v kap. 4.3. Uvedeme si n�kolik typických variant:

1. Binarizace. Je to proces vytvo�ení �ernobílého obrazu z originálu. Zákla-dem je ur�ení hrani�ní hodnoty (prahu), která odd�luje objekt od pozadí. K ur�ení prahu se používá histogram, který nese informaci o rozložení úrovní jasu v obrazu – viz obr. 6.18. Prahová hodnota T (z angl. treshold) rozd�lí body obrazu (x, y) s obrazovou funkcí f(x, y) do dvou t�íd: a) t�ídy objektu, je-li f(x, y) > T b) t�ídy pozadí, je-li f(x, y) <= T Histogram je definován jako funkce �etnosti N výskytu ur�ité úrovn� u jasu v obraze:

( )ufN = (6.5)

kde u je p�íslušná úrove� jasu

N je �etnost výskytu této úrovn� v dané p�edloze.


- 68 (120) -

Proces prahování je pak výsledkem testování funkce ( ) ( )[ ]yxfyxpyxT ,,,,,= a p�vodní obrazové funkce ( )yxf , . Funkce

p(x,y) vyjad�uje lokální vlastnosti daného obrazového bodu (nap�. pr�m�r-nou hustotu výskytu úrovn� šedi v daném okolí bodu (x,y). Prahovaný vý-stupní obraz ( )yxg , je definován takto:

0 je-li f(x,y) > T

( ) =yxg , (6.6)

1 je-li f(x,y) <= T

N

T u

Obr. 6.18. Histogram s vyzna�eným prahem T

V praxi má prahování n�kolik r�zných variant, Podrobný matematický roz-bor je ve [12]. Další informace jsou v [7] a [8].

Speciálním p�ípadem je prahování barevných obraz�. V tomto p�ípad� se konstruuje tzv. 3D histogram (pro 3 složky barev) v n�mž se vyhledávají shluky, podle kterých se provádí vlastní prahování. Podrobn�jší informace jsou ve [12].

2. P�evod obrazu na úrovn� šedi. Jde o redukce barev a p�epo�et na odstíny šedi podle empirického vztahu:

BGRI 114.0587.0299.0 ++= R, G, B ∈ <0..255> (6.7)

kde I je výsledná úrove� jasu šedé. P�epo�ítávají se postupn� všechny pixe-ly RGB. Tím, že každý pixel má ve výsledném formátu jen jednu složku barev místo p�vodních t�í, dochází ke kompresi dat.

3. P�evod do barevné palety 3-3-2. Cílem tohoto zp�sobu komprese je uložit pixel do jediné slabiky = 8 bit�. Protože 8 není beze zbytku d�litelné �íslem 3, musíme použít kompromisu: 3 bity vyhradíme pro složku R, další 3 bity pro složku G a na složku B z�stanou jen 2 bity. Toto omezení lze akcepto-vat, protože lidské oko je na modrou složku nejmén� citlivé.

Komprese dat

4. P�evod do barevné palety 6 x 6 x 6. I v tomto p�ípad� se snažíme omezit hloubku pixelu na 8 bit� tj. 1 slabiku. Protože 1 byte má 28 = 256 úrovní ja-su a 6x6x6 = 216, není fyzický formát slabiky zcela využit. Výhodou však je, že na každou složku barvy vychází stejný po�et úrovní jasu. Výsledný index barvy se vypo�ítá podle tohoto vztahu: 36 Ri + 6Gi + Bi Ri, Gi, Bi ∈ <0..5> (6.8)

kde Ri, Gi, Bi jsou indexy barev v prahových polích.

Algoritmy pro generování palet 3 – 3 –2 a 6 x 6 x 6 jsou v publikaci [8], str. 151, 152.

6.10 Vektorová kvantizace

V kap. 3.2. byla popsána kvantizace obrazové funkce, která je skalárem. Metoda spo�ívá v tom, že jistá množina reálných hodnot (kvantum) se nahrazu-je jediným (diskrétním) vzorkem. Vektorová kvantizace pracuje na podobném principu s tím rozdílem, že se množina (vstupních) vektor� nahrazuje vhodn� voleným (výstupním) vektorem jediným. Kódovací za�ízení bude pracovat s t�mito množinami:

- vstupní množina vektor� X dimenze k. Po�et prvk� množiny si ozna�me symbolem L,

- množina symbol� V, - množina výstupních (reproduk�ních) vektor� Y dimenze j. Tato

množina se nazývá kódová kniha. Po�et prvk� této množiny si ozna�me symbolem M, p�i�emž platí L ≥ M.

Kódování probíhá tak, že vstupní vektor xk ∈ X se nahradí symbolem v ∈ V, který jednozna�n� ur�í výstupní vektor yl ∈ Y. P�itom se postupuje tak, aby chyba d(xk, yl) byla minimální ve smyslu zvolené metriky (b�žn� sta�í Eu-klidovská ve složit�jších p�ípadech Itakura-Saitova metrika). Do zakódovaného proudu dat se zapíše jen index l. P�i rekonstrukci obrazu se v kódové knize vyhledá prvek s indexem l tj. yl a ten se zapíše do rekonstruovaného proudu namísto p�vodního prvku xk. P�ípadné zkreslení je dáno kvalitou návrhu kódo-vé knihy. Jeden z návrh� známý jako algoritmus LBG (nazvaný podle autor� Linde, Buzo, Gray) je popsán v [13]. Podstata algoritmu spo�ívá v tom, že podmnožina vstupních vektor�, které jsou p�i�azeny jednomu a témuž symbolu v tvo�í tzv. Voronoiho oblast daného symbolu. Kódová kniha je navržena op-timáln� tehdy, jsou-li prvky této knihy (tj. vektory y) st�edy Voronoiho oblastí.

Komprese dat založená na vektorové kvantizaci je z principu ztrátová.


- 70 (120) -

6.11 Diskrétní kosinová transformace

Diskrétní kosinová transformace �asto ozna�ovaná v literatu�e zkratkou DCT (Discrete Cosine Transformation) pat�í k významným lineárním ortogo-nálním transformacím v oblasti zpracování digitálního obrazu. Poprvé byla publikována v roce 1974 autory N. Ahmedem, T. Natarajanem a K. R. Raoem [13]. DCT vychází z Fourieovy transformace, p�esn�ji �e�eno z diskrétní Fou-rieovy transformace DFT (Discrete Fourier Transformation).

6.11.1 Fourierova transformace obrazové funkce

Každá spojitá periodická funkce se spojitou derivací ( )xf a s periodou T se dá rozvinout v intervalu T,0 ve Fourierovu �adu – viz [15]:

( ) ( )�∞

=

++=1

0 sincos2 n

nn xnbxnaa

xf ωω (6.9)

kde

( )�=T

n xdxnxfT

a0

cos2 ω , ( )�=

T

n xdxnxfT

b0

sin2 ω , ωπ =

T2

To znamená, že libovolná funkce s vlastnostmi výše definovanými se dá rozložit na sou�et v krajním p�ípad� nekone�n� mnoha harmonických funkcí (sinusového pr�b�hu) s r�znou:

a) amplitudou, b) fázovým posunem, c) kmito�tem. Amplitudy jednotlivých harmonických funkcí jsou ur�eny koeficienty

an, bn, fázový posun, pokud existuje, je dán aditivní konstantou p v argumentu funkce sin resp cos ve vzorci 6.9 bude sinω(x + p) resp. cosω(x + p) a kmito�ty se odvozují jako celistvé násobky základního kmito�tu p�vodní funkce, která je

dána periodou T. Harmonická funkce v rozvoji o kmito�tu T

f1= se nazývá

základní nebo také první harmonická. Obecn� n-tá harmonická je taková funk-

ce, která má kmito�et nT

f1= . Zvláštní postavení mezi t�mito funkcemi má

tzv. nultá harmonická, která vyjad�uje st�ední hodnotu funkce ( )xf . Její ampli-tuda je ur�ena koeficientem a0. Funkce symetrické vzhledem k ose x mají st�ední hodnotu nulovou tj. a0 = 0. Je-li funkce lichá (graf funkce je st�edov� soum�rný podle po�átku) tj. ( ) ( )xfxf −=− , pak an = 0 pro n = 0, 1, 2, 3…; �ada obsahuje jen sinové �leny. Je-li funkce sudá (graf funkce je soum�rný podle osy y tj. ( ) ( )xfxf =− , pak bn = 0 pro n = 0, 1, 2, 3…; �ada obsahuje jen konstantní �len a0/2 a kosinové �leny.

Komprese dat

�asto se používá Fourieova �ada v komplexním tvaru:

( ) ( )�∞

=

−+=0

'

n

xjnn

xjnn ececxf ωω (6.10)

koeficienty nc , 'nc vypo�teme podle vzorc�:

( ) dxexfT

c xjnT

nω−�=

0

1 ( ) dxexf

Tc xjn

T

nω�=

0

' 1

Pro naše ú�ely transformace p�edlohy si rozší�íme Fourierovu transfor-maci z 1D na prostor 2D. Na obr. 6.19 je znázorn�na analogová obrazová funk-ce �ásti n�jaké p�edlohy jako výška v ose z v sou�adnicovém systému x, y ,z.

Dvourozm�rná (obrazová) p�ímá Fourierova transformace periodické dvourozm�rné obrazové funkce je pak definována vztahem:

( ) ( )� �∞

∞−

∞

∞−

−−= dxdyeeyxf

TTF y

y

x

xT

yj

Txj

yxyx

ωω

ωω ,1

, (6.11)

kde ( )yxF ωω , je spojité Fourierovo spektrum,

f(x, y) je analogová obrazová funkce – viz obr. 6.19.,

yx ωω , jsou prostorové kmito�ty,

Tx, resp. Ty jsou periody ve sm�ru osy x resp. y.

Obr. 6.19. Obrazová funkce f(x, y) a její digitální vzorky g(x, y) vyjád�ené výš-kou z


- 72 (120) -

V diskrétním prostoru m�žeme popsat dvourozm�rnou diskrétní Fourie-rovu transformaci DFT vztahem:

( ) ( )��−

=

−

=

−−=1

0

1

02121

1 221,

11,

N

x

N

y

yjxj eeyxgNN

nnF ωω (6.12)

kde n1, n2 jsou spektrální složky Fourierova rozvoje,

g(x, y) je digitalizovaná obrazová funkce – viz obr. 6.19.,

N1, resp. N2 je rozm�r obrazové matice tj. po�et vzork� v ose x resp. y,

1

11

2N

nπω = , resp. 2

22

2N

nπω = jsou prostorové kmito�ty ve sm�ru osy x resp. y.

Fourieova transformace tedy p�evádí obraz z prostorové do spektrální oblasti, kde je z�ejmé z jakých spektrálních (harmonických) složek se obraz skládá. Každá spektrální složka má svoji amplitudu a fázi. Fázová složka vyja-d�uje umíst�ní n�jakého objektu v obraze, spektrální složky nízkých kmito�t� zachycují základní dominantní rysy obrazu, zatímco spektrální složky vyšších kmito�t� jsou odrazem ostrých hran a jemných detail� v p�edloze.

Poznámka :

P�edpokladem Fourierova rozvoje je, aby vstupní obrazová funkce ob-rázku, který má kone�nou velikost, byla periodická. Tuto podmínku snadno splníme tím, že vytvo�íme matematický model – nekone�nou plochu složenou z jednoho obrázku, který opakovan� pokládáme ve sm�ru osy x i y. Na tuto strukturu pak aplikujeme Fourieovu transformaci a vybereme výsledek pro základní periodu tj. p�vodní p�edlohu.

Fourierova transformace nám umož�uje snadné zpracování digitálního obrazu. Harmonické funkce lze totiž mnohem jednodušeji analyticky vyjád�it než p�vodní obrazovou funkci, jejíž matematický popis by byl v mnoha p�ípa-dech velmi obtížný. Proto n�které operace lze použitím Fourierovy transforma-ce p�evést na operace o �ád nižší (nap�. konvoluci na násobení). Mezi nevýho-dy Fouierovy transformace pat�í výpo�et koeficient� – amplitud jednotlivých spektrálních funkcí, který je v mnoha p�ípadech složitý a �asov� náro�ný (kaž-dý koeficient se po�ítá p�es celé spektrum). Tato nevýhoda je �áste�n� zmírn�-na tím, že

- v závislosti na charakteru vstupní obrazové funkce vycházejí n�kte-ré koeficienty Fourierovy transformace nulové,

- v praxi se používají speciální algoritmy pro výpo�et tzv. rychlé Fou-rierovy transformace FFT (Fast Fourier Transformation), které exis-tují i jako technické akcelerátory (algoritmy zabudované do obvo-dové logiky) i v podob� zásuvných desek do po�íta��.

Komprese dat

6.11.2 Odvození diskrétní kosinové transformace

Fourierova transformace má však ješt� jednu nevýhodu, která spo�ívá v tom, že reálné matice reprezentující obraz, p�evádí na matice komplexní se sudou reálnou a lichou imaginární složkou (tzv. hermitovské matice). Proto se hledala metoda, jak tuto nevýhodu eliminovat. Komplexní jádro diskrétní Fou-rierovy transformace lze rozložit na reálnou a imaginární složku podle vzorce:

Nnx

jNnx

e xjn ππω 2sin

2cos += (6.13)

Potíž je vtom, že žádná z obou �ástí tj. ani kosinová ani sinová funkce nep�edstavuje v oboru reálných funkcí úplný systém bázových funkcí.

D�ležitou vlastností Fourierovy �ady je to, že zachovává symetrii tj. transformace sudé resp. liché funkce je zase sudou resp. lichou funkcí. Na zá-klad� této vlastnosti pak m�žeme �íci, že pokud bude obrazová funkce sudá pop�. lichá, potom Fourieova transformace bude obsahovat jen kosinové pop�. sinové složky a pro tyto funkce bude kosinová pop�. sinová �ást komplexního jádra (vztah 6.13) p�edstavovat úplný systém bázových funkcí. Pokud vstupní funkce f(x) není sudá, lze ji modifikovat tak, aby se sudou stala. K tomu se používá tzv. sudé prodloužení (rozší�ení) funkce f(x) kolem n�jakého vztažné-ho bodu (nap�. x = 0). Je-li nap�. defini�ním oborem diskrétní funkce g(x) množina nezáporných �ísel 0 <= x < N, potom m�žeme definovat na intervalu –N < x < N funkci g(x) takto:

( ) )( xfxg = (6.14)

Funkce g(x) p�edstavuje sudé prodloužení funkce f(x) kolem bodu x = 0 – viz obr.6.20. Protože g(x) je sudou funkcí, bude její Fourierova transformace obsa-hovat jen kosinové �leny.

Obr. 6.20. Sudé prodloužení vstupní diskrétní funkce f(x)


- 74 (120) -

Nyní máme vše p�ipraveno pro odvození p�ímé jednorozm�rné diskrétní kosinové transformace (dále DCT). Použijeme postupu, který je uveden v [3]. P�edpokládejme N-bodovou vstupní funkci f(x), s defini�ním oborem 0 <= x < N. DCT odvodíme na základ� jejího 2N bodového sudého prodloužení g(x) – viz obr. 6.20c. Funkce g(x) na tomto obrázku je definovaná vztahy:

( )xf pro 0 <= N-1

( ) =xg (6.15)

( )12 −− xNf pro N <= x < 2N-1

Z tohoto vztahu vyplývá, že

( ) ( )xgxNg =−− 12 (6.16)

Po úpravách, které jsou nap�. v [26], [3] a rozší�ení z 1D na 2D prostor dostaneme vztah pro dvourozm�rnou DCT:

( ) ( )��

−

=

−

=�

��

� +++=1

0

1

0 212

cos2

12cos),(

2),(

N

x

N

yvu v

Ny

uN

xyxfKK

NvuC

ππ (6.17)

p�i�emž normovací konstanty mají hodnoty:

21=wK pro w = 0 a 1=wK pro w = 1, 2, …, N-1.

6.11.3 Využití DCT pro kompresi dat

Na komprimaci dat metodou DCT je založen standardní grafický formát JPEG – viz kap. 9. Princip spo�ívá v tom, že celý obrázek nebo jen jeho �ást (v JPEG je to blok 8 x 8 pixel� o ose x a y) se pomocí DCT transformuje z oblasti obrazové (sou�adnice x, y) do oblasti spektrální. Vznikne spektrum sinusových funkcí, které jsou reprezentovány svými koeficienty (hodnoty amplitud, fází a kmito�t�). Jak již bylo d�íve uvedeno, funkce o nízkém kmito�tu nesou pod-statnou �ást obrazové informace, zatímco funkce vyšších kmito�t� zachycují jemné detaily p�edlohy. Proto je možné za ur�itých p�edpoklad� vyšší kmito�ty spektra vynechat (koeficienty p�íslušných funkcí budou nulové) a do výstupní-ho souboru zakódovat jen funkce nižších kmito�t�, �ímž dojde ke kompresi. Slovo zakódovat zde znamená to, že koeficienty vybraných spektrálních funkcí m�žeme dále zkomprimovat n�kterou známou bezeztrátovou metodou. Nabízí se p�irozená otázka, jak velkou �ást spektra m�žeme vynechat. To záleží na ú�elu, pro který je obrázek ur�en. Lze matematicky vypo�ítat, kolik po�áte�-ních harmonických funkcí vzniklých po aplikaci DCT na p�vodní obrazovou funkci musíme zachovat, aby ztráta informace vzniklá kompresí nebyla vyšší, než zadaná mez v procentech. Pokud obrázek obsahuje dostate�né množství redundance, lze dosáhnout kompresního pom�ru 20:1 až 30:1. Komprese dat založená na DCT má však i svoje nevýhody a to:

Komprese dat

1. pokud se ve vstupním obrázku vyskytují ostré hrany, které jsou ve spekt-rální oblasti reprezentovány vysokými kmito�ty, a tyto kmito�ty pak b�-hem kompresním procesu zanedbáme, pak výstupní obrázek po rekonstruk-ci trpí tzv. Gibbsovým jevem. Jde o zvln�ní, které se objevuje v místech obrazu kde je vysoký kontrast nap�. v okolí ostrých hran.

2. je-li prvním krokem aplikace metody DCT rozd�lení obrázku na bloky 8 x 8 pixel�, pak další zpracování zkomprimovaného obrazu je poplatné tomu-to rozd�lení. Nap�. zm�na rozlišení se m�že projevit zna�ným snížením kvality obrazu.

6.12 Fraktální komprese

6.12.1 Úvod do fraktální geometrie

Fraktální geometrie se vyvíjí jako samostatná v�dní disciplína od 60. let (zakladatel Benoit B. Mandelbrot). P�edm�tem fraktální geometrie jsou metody popisu p�írodních objekt�. Chceme-li popsat n�které tvary objekt� v p�írod� nap�. mraky, ostrovy, zálivy apod. pomocí klasické geometrie, pak jde o proces v mnoha p�ípadech velmi složitý a neefektivní. Fraktální geometrie �eší tento problém tak, že rozd�lí daný objekt na v�tší celky (domény), v nichž je co nej-více tvarov� p�íbuzných prvk�. Nejlepší p�ípad je takový, kdy v každé domén� je nalezen jen jeden základní prvek. Ostatní �ásti domény jsou pak definovány pomocí tohoto prvku jako lineární podobnostní transformace podle vztahu:

[ ] [ ]fdycxebyaxyxW ++++= ,, (6.18)

Tento vztah vyjad�uje oto�ení a zmenšení (resp. zv�tšení) nalezeného podobného motivu i jeho posunutí (koeficienty e, f). Opakování základního prvku (motivu) je pak definováno pouze šesti koeficienty.

Fraktální geometrie je tedy založena na podobnosti objekt�, které se od sebe liší jen velikostí. Využívá matematických disciplin, které se zabývají m�-�ením dimenze. Ve fraktální geometrii rozeznáváme 2 druhy dimenzí:

1. topologickou dimenzi, která každé k�ivce p�i�adí p�ímku, každé plo-še rovinu apod.

2. Hausdorfovu dimenzi D, která vyjad�uje míru �lenitosti objektu a lze ji vypo�ítat ze vztahu:

1=DNs (6.19)

kde N je po�et �ástí objektu a s m��ítko objektu. B. Mandelbrot definoval pojem fraktál pomocí obou dimenzí takto:

Fraktál je množina, jejíž Hausdorfova dimenze je v�tší než dimenze topolo-gická.


- 76 (120) -

Jednoduché geometrické útvary jako je úse�ka, �tverec, krychle apod. mají topologickou a Hausdorfovu dimenzi stejnou. Proti tomu nap�. u k�ivky Ko-chové na obr. 6.21 je na první pohled patrná �lenitost – jde o kompozici rov-nostranných trojúhelník�, které se navzájem p�ekrývají v itera�ních cyklech, p�i�emž v každém dalším cyklu se rozm�r trojúhelníku 3x zmenší ve stejném pom�ru k rozm�ru v p�edchozím itera�ním cyklu. Hausdorfova dimenze u k�iv-

ky Kochové (N=4, s=1/3) je (podle 6.19) rovna 2618.13log4log = .

Obr. 6.21. K�ivka Kochové po druhé iteraci

Topologická dimenze je však rovna jedné, protože jde stále o k�ivku v rovin�. Z toho vyplývá, že k�ivka Kochové spl�uje definici fraktálu podle B. Mandel-brota. Pro zajímavost m�žeme uvést další p�íklady: povrch lidského mozku má Hausdorfovu dimenzi 2.76, povrch plic 2.17 a pob�eží zem�pisných útvar� 1.26.

Podle dosud známých typ� m�žeme fraktály rozd�lit takto:

1. Deterministické fraktály:

a. Lineární: L-systémy (Lindenmayerovy systémy), Sekven�ní L-systémy, Systém iterovaných funkcí IFS – viz dále.

b. Nelineární: Dynamické systémy, Nelineární IFS.

2. Stochastické fraktály: Otev�ené L-systémy, Brown�v pohyb, Difúze.

Fraktály m�žeme generovat pomocí n�kolika metod. Z výše uvedených typ� se nej�ast�ji používají tyto metody:

1. L-systémy (Lindenmayerovy systémy), 2. dynamické systémy, 3. systém iterovaných funkcí IFS (Iterated Function System). Bližší popis je v [8] nebo ve skriptech [26].

6.12.2 Princip fraktální komprese

Pro kompresi resp. dekompresi obrázku se využívá p�edevším metoda IFS a to takto: Zpo�átku je celý obrázek jednobarevný nap�. bílý. V každém kroku iterace se postupn� procházejí jednotlivé domény na které se aplikuje p�íslušná transformace podobných motiv�. Výsledek iterace z domény Di se pak zkopíruje do jiné �ásti obrázku tzv. oblasti (Range) Ri. Se zvyšujícím se

Komprese dat

po�tem iterací se rozdíly mezi stavy v p�edposledním a posledním kroku itera-ce zmenšují a obrázek se blíží svému originálu (dochází ke zjem�ování detai-l�). Pro každou i. doménu Di p�edlohy se v každém kroku iterace musí vy�ešit tato transformace:

( ) iii RDw = (6.20)

Protože každý obrázek si m�žeme transformovat do trojrozm�rného sou�adného systému kartézských sou�adnic x, y, z – viz obr. 6.19, lze vztah (6.20) rozepsat na soustavu rovnic:

�

�

��

�

�

+

�

�

��

�

�

×

�

�

��

�

�

=��

�

��

�

�

i

i

i

i

ii

ii

i

o

f

e

z

y

x

s

dc

ba

z

y

x

w

0000

(6.21)

Pro zjednodušení si rovnici (6.21) m�žeme rozd�lit na dv� samostatné rovnice. První z nich definuje transformace v rovin� x, y (ur�í se poloha pixel� v i. domén�):

ii

i

ii

iii t

y

xT

f

e

y

xdc

ba

y

xw +

�

��

�×=

�

��

�+�

��

�×�

��

�=��

�

��

�1 (6.22)

kde symbol T reprezentuje transformaci podobnosti Di jako nap�. oto-�ení, zm�na m��ítka, zkosení atd. a vektor ti ur�uje polohu bodu na obrázku.

Druhá rovnice popisuje operaci v ose z (transformace obrazové funkce v Di):

iii ozsw +=2 (6.23)

kde si reprezentuje kontrast bodu a oi jas tohoto bodu.

Podmínkou konvergence itera�ního procesu je:

1. ∅=∩ ji RR pro všechna i <> j a dále

2. si < 1 pro všechna i. (6.24)

V praxi tato metoda obchází nemožnost nalezení v�rné zmenšené kopie celého obrazu tím, že hledá jen kopie jeho �ástí. Vychází z p�edpokladu, že když rozd�líme obraz na celky s podobnými vzory (tedy nap�íklad na oblohu, trávu, stromy), bude jednodušší nalézt podobnosti mezi t�mito celky a jejich �ástmi. Protože obecn� jde o složitý obtížn� algoritmizovatelný problém, �eší se tato úloha heuristickými metodami. Nejb�žn�jší postup spo�ívá v tom, že se obraz rozd�lí na pravidelné bloky (Ri = ranges), které se nep�ekrývají (pravá �ást obr. 6.22.). Ke každému z t�chto blok� se hledají jejich nejpodobn�jší v�t-ších kopie (Di = domény) v libovolné �ásti obrazu (levá �ást obr. 6.22.). Do-ménové bloky se mohou p�ekrývat a nemusí dohromady pokrývat celou plochu obrazu. Doménové i �adové bloky jsou vybírány ze stejného obrazu, odd�lené znázorn�ní na schématu slouží jen pro v�tší p�ehlednost. Celý proces je zná-zorn�n na obr. 6.22., kde symbol wi zna�í transformaci ve 2D podle vztah� 6.20 – 6.24.


- 78 (120) -

Obr. 6.22. Hledání podobnosti mezi doménovými a �adovými bloky obrazu

6.12.3 Algoritmus fraktální komprese

P�i fraktální kompresi hledáme v obrázku oblasti (ranges – Ri) s charakteristickým motivem – doménou Di, a to tak, aby po kone�ném po�tu iterací podle vztah� (6.20) – (6.24) pokryla doména Di po p�íslušných trans-formacích oblast Ri s p�edem stanovenou odchylkou ε – viz vztah (6.31).

Poznámka:

Po nekone�n� mnoha iteracích chyba ε limituje k nule a oblasti Ri jsou p�esn� totožné s p�vodním obrázkem. Tento postup však v praxi není možný, proto se komprimovaný obrázek bude vždy lišit od originálu, p�i�emž kriterium shody je dáno hodnotou odchylky ε. Z tohoto d�vodu je fraktální komprese z principu metodou ztrátovou.

Úkolem algoritmu komprese je najít pro každou dvojici (Ri, Di) koefici-enty funkce wi, tj (si, oi). p�i stanovené odchylce ε. Nepoda�í-li se najít tyto parametry, rozd�lí se Ri dále na menší �ásti. V paxi se používá d�lení obrázku na pravidelné útvary (kv�li jednoduchosti) nap�. na kvadranty, d�lení HV (ho-rizontal – vertical) – pro obdélníkové p�edlohy nebo trojúhelníkové d�lení – rekurzivní d�lení po diagonále.

Z matematiky víme, že itera�ní výpo�et se m�že ukon�it ve dvou p�ípa-dech:

1. po spln�ní ukon�ující podmínky což znamená, že rozdíl (v absolutní hod-not�) mezi výsledkem v p�edposledním a posledním kroku iterace je menší než p�edem stanovené malé kladné �íslo ε (p�esnost pop�. tolerance vý-po�tu):

ε<−− kk ss 1 pop�. ε<−− kk oo 1 (6.31)

Komprese dat

kde

sk-1, sk je koeficient transformace kontrastu (k-1). a k. obrázku,

ok-1, ok je koeficient transformace jasu (k-1). a k. obrázku,

k je po�et krok� iterace

2. po dosažení p�edem stanoveného po�tu N krok� iterace tj. je-li k = N.

Proto máme dv� varianty algoritm�:

1. algoritmus komprese dat p�i p�edem stanovené chyb� εεεε:

a) stanov chybu ε a minimální rozm�r oblasti Rmin, b) rozd�l obrázek na oblasti Ri a vytvo� z nich seznam, v n�mž budou

všechny Ri zpo�átku neozna�ené, c) ze všech p�ípustných prvk� množiny D (domény) vyber ten, který mi-

nimalizuje chybu εi, d) je-li εi < ε nebo Ri < Rmin, pak ozna� Ri v seznamu a zapiš koeficienty

transformace do výstupního souboru, e) nejsou-li spln�ny podmínky v bodu d), pak rekurzivn� d�l Ri na menší �ásti, které jako neozna�ené zapiš místo Ri do seznamu,

f) pokud je v seznamu alespo� jeden prvek Ri neozna�ený, opakuj kroky c), d), e), jinak algoritmus kon�í.

2. algoritmus komprese dat p�i použití N transformací s pr�b�žným sle-dováním maximálního kompresního pom�ru

a) stanov po�et transformací N a minimální rozm�r oblasti Rmin, b) rozd�l obrázek na oblasti Ri a vytvo� z nich seznam, v n�mž budou všechny

Ri zpo�átku neozna�ené, c) pro každou neozna�enou oblast v seznamu najdi a ulož doménu, která co

nejvíce vyhovuje (má nejmenší chybu ε, d) najdi oblast Rj , která má nejv�tší chybu ε a je v�tší než Rmin e) je-li po�et oblastí v seznamu menší než N, pak

- rozd�l Rj na menší �ásti a ulož je do seznamu jako neozna�ené - ze seznamu vy�a� Rj, wj a Dj,

f) pokud jsou všechny Ri ozna�ené p�ejdi k bodu g) jinak se vra� k bodu c), g) vypiš všechny koeficienty wi ze seznamu na výstup – konec algoritmu.

Algoritmus dekomprese dat

Dekomprima�ní program postupn� vytvá�í rekurzivní strom, který vznikl p�i kompresi. V po�áte�ním kroku jsou všechny koeficienty transfor-ma�ní matice nulové, což odpovídá pozadí obrazu na výstupu. V 1. kroku ite-race se vytvo�í základní oblasti Ri stejné barvy. Další kroky iterace se skládají ze dvou fází:


- 80 (120) -

1. K dané oblasti Ri se ur�í doména Di a její parametry tj. poloha, velikost, typ transformace a koeficienty s, o vypo�ítané kódovacím programem.

2. Z takto ur�ené domény se vypo�ítá oblast Ri podle vztahu: oDsR ii +×= (6.32)

Fraktální komprese pat�í mezi nesymetrické metody, protože proces kom-primace je vzhledem k nutnosti analýzy originálu podstatn� složit�jší a �asov� náro�n�jší než dekomprese obrazu. P�esto pat�í k perspektivním metodám, ji-miž lze dosáhnout vysokého kompresního pom�ru bez znatelných vedlejších negativních vliv�. Hodí se zejména na kompresi p�írodních obraz�. Velmi špatných výsledk� je dosahováno p�i práci s obrazy, které obsahují text a tech-nickou kresbu. Tyto �ásti obrazu jsou po kompresi deformovány, n�kdy do-konce úpln� zmizí, to je typické hlavn� pro p�ímé �áry, které sm��ují diagonál-n� k hranám �adových blok�.

6.13 Shrnutí

Kompresí rozumíme redukci fyzického formátu do kterého je informace v po�íta�i uložena. Metody m�žeme rozd�lit podle mnoha hledisek, nejd�leži-t�jší pro uživatele je hledisko ztráty informace p�i kompresi.

K bezeztrátovým metodám pat�í:

- pixelové zhuš�ování, kde se pln� využívá celý fyzický formát,

- RLE, kdy souvislé �et�zce stejných znak� se ukládají do RLE pake-tu tj. proudové �íslo (po�et znak�) + hodnota proudu (znaku),

- kvadrantový strom, v n�mž je obraz zakódován do binárních �et�z-c�, které popisují hierarchický kvadrantový strom. Ten se vytvo�í v 1. fázi tak, že se nehomogenní kvadranty obrazu rekurzivn� d�lí na kvadranty nižší úrovn� dokud nejsou homogenní (stejné barvy) nebo dokud se nedosáhne úrovn� pixel�. Hierarchický strom díl�ích kvadrant� se zapíše jako �et�zcový kód na výstup,

- LZW neboli slovníkové metody, v nichž se buduje dynamický slov-ník (tabulka) frází a místo skupin znak� (slov) se zapisují jen kódy, které jsou kratší než dané slovo (fráze),

- Huffmanovo kódování, které vychází z teorie informace a kóduje každý znak do kódu jehož délka je nep�ímo úm�rná jeho �etnosti výskytu v souboru. Aby se nemusela zjiš�ovat �etnost, kóduje se v praxi podle ú�elov� vytvo�ených speciálních tabulek, které jsou standardem CCITT normy. Norma obsahuje p�edpis i pro tzv. 2D kód což je zp�sob, kdy se jednotlivým �ádk�m p�i�azují skupiny tzv. vertikálních kód� podle zm�n vzhledem k p�edcházejícím �ád-

Komprese dat

k�m obrazu. Kódy generované v 1D i 2D jsou slova s prom�nnou délkou (VWL – Variable Word Length).

Principiáln� ztrátové metody jsou:

- redukce barev, která spo�ívá v tom, že snížíme obsah informace v obrazu jeho transformací z v�tší do menší množiny barev a to: bi-narizací (�ernobílý obraz), p�evodem z barev na stupn� šedi, sníže-ním po�tu barev tak, aby byl využit fyzický formát pro uložení pixe-lu (palety 3-3-2 nebo 6x6x6) - snaha uložit pixel do 1 slabiky,

- vektorová kvantizace objevená Shannonem, kdy se místo skalárních vzork� obrazové funkce kvantují p�ímo vektory této funkce. Roz-hodovacími úrovn�mi kvantiza�ní funkce jsou tzv. Voronoiho ob-lasti 3D prostoru.

Teoreticky bezeztrátové, ale prakticky ztrátové metody jsou:

- diskrétní kosinová transformace, kdy se obraz nejd�íve p�evede z p�edm�tové do spektrální oblasti pomocí Fourieovy transformace a liché (sinové) složky se odstraní sudým prodloužením obrazové funkce. Získané koeficienty transformace (amplitudy, fáze a kmi-to�ty jednotlivých harmonických funkcí) se zakódují bu� Huffma-novým kódem (bezeztrátová metoda v JPEG) nebo se dále kvantizu-jí (ztráta informace). Koeficienty vyšších harmonických (malé hod-noty) se ú�elov� zanedbají podle požadovaného stupn� kvality,

- fraktální komprese. Je založená na fraktální geometrii, což je zp�-sob popisu kresby pomocí jejích podobných �ástí (domén). V kom-presi se obraz rozd�lí na pravidelné bloky (Ranges), které se nep�e-krývají. Ke každému bloku se hledá podobná doména, která po ko-ne�ném po�tu krok� v itera�ním cyklu tento blok pokryjí. P�itom v každém kroku iterace se doména podle pot�eby modifikuje trans-formací posunu, oto�ení nebo zm�ny m��ítka. Do výstupního sou-boru se zapisují jen domény a p�íslušné koeficienty transformace, což zabírá m�n� místa než uložení jednotlivých hodnot pixel�.

Ztrátové i bezeztrátové mohou být tyto metody:

- predik�ní metody, založené na tom, že i. vzorek obrazové funkce lze p�edpov�d�t na základ� znalosti n vzork� p�edchozích pixel�. Hodnota pixelu je pak sou�et hodnoty predik�ní funkce, která za-chytí podstatnou �ást hodnoty vzorku a zbytku tzv. predik�ní chyby, která se zapíše do výstupu. Protože p�i vhodné predik�ní funkci je tato chyba mnohonásobn� menší než hodnota vzorku, pot�ebujeme na její uložení mén� pam�ti než na uložení celého vzorku. Kvantu-jeme-li predik�ní chybu, je komprese ztrátová, jinak je bezeztrátová.

- waveletová (vlnková) transformace umož�uje zakódovat celý obraz v hierarchicky uspo�ádaném rozlišení hodnotami pr�m�r� pixel� a �adou koeficient� detail� (rozdíl� skute�né hodnoty a pr�m�ru) v po�adí zvyšujícího se rozlišení. Princip komprese tkví v tom, že hodnoty koeficient� jsou mnohonásobn� nižší než hodnoty pixel�, tudíž na jejich uložení pot�ebujeme mén� pam�ti. Pokud koeficienty dále kvantujeme, je komprese ztrátová, jinak je bezeztrátová.


- 82 (120) -

6.14 Autotest

1. Rozhodujícím hlediskem pro posouzení zda kompresní metoda je �i není ztrátová je

a) struktura dat b) algoritmus komprese c) míra informace d) velikost souboru

2. Komprese RLE je nejú�inn�jší tehdy, obsahuje-li soubor posloupnosti

a) stejných znak� b) r�zných znak� c) stejných slov d) r�zných slov

3. Pro kompresi kvadrantovým stromem je nejhorší varianta tehdy, je-li obraz

a) homogenní b) nehomogenní c) st�ídají se r�zné pixely v �ádcích

4. Metoda LZW pracuje na úrovni

a) bitové b) znakové c) slov d) blok� e) záznamu

5. Která bezeztrátová komprese bude nejú�inn�jší pro technický výkres s množstvím svislých �ar?

a) LZW b) DCT c) fraktální d) Huffman�v kód 2D

6. Jaká je nejú�inn�jší komprese pro barevnou fotografii bez ohledu na ztrátu informace?

a) LZW b) RLE c) Huffman�v kód d) DCT e) predikce

7. Na jakém principu je založena fraktální komprese?

a) Fourieova transformace b) itera�ní po�et c) teorie informace d) po�et pravd�podobnosti

8. Histogram je funkce udávající závislost

a) jasu na poloze pixel� b) �etnosti výskytu na poloze pixel�

c) barv� na jasu d) �etnosti výskytu na jasu pixel�


- 83 (120) -

7 Vektorové formáty

Doposud jsme se zabývali bitmapovými grafickými formáty, v nichž byla p�edloha uložena bod po bodu. Existuje však i zp�sob, kdy obrázek je popsán pomocí vektor�. Takovým soubor�m s grafickými daty se �íká vekto-rové. Historicky jsou vektorové formáty starší než bitmapové, protože technic-ká za�ízení pracovala zpo�átku na vektorovém principu (vektorové displeje).

7.1 Princip vektorového popisu kresby

Podstatou vektorového popisu je hierarchický p�ístup ke kresb�. To znamená, že každou p�edlohu je možné dekomponovat od nejsložit�jších moti-v� až po jednoduché (z našeho hlediska již dále ned�litelné) obrazce. Tyto zá-kladní grafické prvky se �asto v cizí literatu�e nazývají elements (prvky), enti-ties (entity) nebo primitives (jednoduché prvky - primitivy). Tyto prvky mohou být v r�zných systémech definované rozdíln�. Rozd�lit je m�žeme podle n�ko-lika hledisek. Nap�. podle dimenze kresby je m�žeme rozd�lit na prvky:

• 0. dimenze (bod),

• 1. dimenze (�ára, p�ímka, úse�ka, lomená �ára, k�ivka),

• 2. dimenze (mnohoúhelníky, kružnice, obecné areály),

• 3. dimenze (t�lesa, prostorové útvary),

• 4. dimenze – (4. rozm�r je �as) - animované obrázky.

Podle základního tvaru se mohou prvky d�lit na:

• bod, • množina bod� (polymarker), • �ára (úse�ka, k�ivka), • lomená �ára (polyline), • text, • plocha (prvek 2D), • vypln�ná oblast (fill area), • obecný grafický prvek.

V podstat� jde o matematický popis grafických objekt�, který vychází z geometrie tvarové podobnosti základních prvk�. Obrázek je p�itom popsán jako matematický model, v n�mž složit�jší grafické objekty jsou složeny z jed-noduchých základních geometrických prvk� (primitiv). Grafický formát vekto-rového typu tedy obsahuje množinu základních prvk�, které jsou matematicky


- 84 (120) -

jednozna�n� ur�eny. Každý typ prvku je z matematického hlediska ur�en p�í-slušnou funkcí. Konkrétní tvar a pozice prvku v obrázku je stanovena paramet-ry dané funkce. K tomu, aby byl prvek jednozna�n� definován musíme znát jeho význa�né parametry, kterým se �íká atributy.

Tyto atributy m�žeme podle jejich funkce, kterou zastávají v grafickém popisu prvk� rozd�lit do t�í skupin:

1. Defini�ní. Jsou to v podstat� parametry funkcí základních prvk� (identi-fikátor prvku, sou�adnice prvku, rozm�ry)

2. Geometrické. Tyto atributy nám �íkají, jaký bude vzhled daného prvku na výstupním za�ízení. Jsou to nap�. barva prvku, typ �áry, síla �áry, sm�r kreslení prvku (u liniového), uzav�enost prvku (u areál�), soused-nost.

3. Speciální. Tyto atributy jsou používány v grafických editorech a jsou dvojího druhu: a) Individuální – týkají se izolovaného prvku (vrstva/�íslo vrstvy, des-

ka/otvor - u uzav�ených areálových prvk�, zachytitel-nost/identifikovatelnost, p�íznak vykreslit nebo vymazat).

b) skupinové. Jsou to takové atributy, které se týkají prvk� sdružených do n�jaké grafické skupiny nap�. p�íslušnost ke skupin�, asociativita s jiným prvkem nebo jinými prvky.

Je t�eba si uv�domit, že uvedené �len�ní není absolutní a jednotlivé atributy se mohou vzájemn� p�ekrývat nap�. p�íznak výmazu m�že mít i celá grafická skupina. Samoz�ejm� m�žeme najít celou �adu dalších atribut� (nap�. modifikovatelnost – tj. byl �i nebyl prvek modifikován), ale pro naše ú�ely je tento vý�et dostate�ný.

7.2 Vlastnosti vektorových formát�

1. Struktura vektorových soubor� I když se jednotlivé vektorové formáty mezi sebou liší, mají n�které spo-le�né rysy. Jedním z nich je struktura souboru. Ta se podobn� jako u bitmapových formát� skládá z hlavi�ky, vektorových dat, palety, paty, pop�. dalších komponent.

a) Hlavi�ka. V této �ásti jsou obsaženy všeobecné informace, které se tý-kají p�edlohy jako celku a to: 1. identifikátor formátu, 2. �íslo verze, 3. informace o barvách (chybí-li paleta), 4. implicitn� nastavené atributy (jsou v�tšinou v hlavi�ce), 5. výška a ší�ka p�edlohy (výkresu), 6. pozice p�edlohy na výstupním za�ízení, 7. po�et vrstev a další.

Vektorové formáty

b) Vektorová data. Jak již bylo uvedeno v p�edchozí kapitole, jsou vekto-rová data složena z prvk�, které mají své atributy (tvar, velikost, abso-lutní/relativní polohu v p�edloze, barvu, typ a sílu �áry apod.).

P�íklad 7.1.: ást kresby se t�emi prvky (modrá kružnice se st�edem S[x=100,y=100], polom�rem r=40, �erná úse�ka [x1=200, y1=100; x2=15, y2=240] a �ervený obdélník [x1=10, y1=20; x2=80,y2=60]) m�že být ve vektorovém formátu ASCII zapsána takto:

CIRCLE,40,100,100,BLUE;;;;LINE,200,100,15,240,BLACK;;;;RECTANGLE 10,20,80,60,RED;;;;

Uvedený p�íklad ilustruje, že dekódování vektorového formátu je složi-t�jší než dekódování bitmapového formátu, protože je nutné správn� analy-zovat jednotlivé prvky i všechny jejich atributy, zatímco u bitmapového formátu interpretujeme jen hodnoty pixel�. Obecn� lze �íci, že u vektoro-vých formát� je obtížná syntaktická analýza souboru – viz kap. 8.3.

c) Paleta a informace o barv�. Tak jako bitmapové soubory mohou i vek-torové soubory obsahovat paletu. V p�íkladu 7.1. m�že definice barev v ASCII formátu vypadat takto: RED,255,0,0; BLACK,0,0,0; BLUE,0,0,255;

Paleta se musí na�íst ješt� p�ed rekonstrukcí obrazu.

d) Pata. Do paty souboru se ukládají údaje, pro které již nebylo rezervová-no místo v hlavi�ce souboru. Jsou to dopl�kové informace jako nap�. datum a �as vytvo�ení formátu, název aplikace, kterou byl formát po�í-zen, po�et objekt� v p�edloze apod.

2. Speciální vlastnosti vektorových soubor�

a) Šrafování a vypl�ování ploch. Šrafovat nebo vypl�ovat m�žeme jen plošné uzav�ené entity. Uzav�eností v tomto p�ípad� rozumíme nejen to, že po�áte�ní a koncový bod hrani�ní �áry šrafované oblasti jsou to-tožné, ale pokud je hranice tvo�ena posloupností úse�ek nebo díl�ích �ar, musí tyto segmenty na sebe navazovat ve stejném sledu viz obr. 7.1, jinak by m�l algoritmus šrafování nekorektní podmínky. Vypl�o-vání uzav�ených ploch je možné chápat ve trojím smyslu: souvislé vy-pln�ní, vypl�ování vzorem (angl. patterning) a gradientní vypl�ování což je hladký p�echod mezi po�áte�ní a koncovou barvou.

Ve všech p�ípadech je generování šraf� �i výpln� pom�rn� složitou matematickou operací. Princip algoritmu spo�ívá v tom, že v zadaném sm�ru klademe p�ímky na uzav�enou plochu a spo�ítáme pr�se�íky hranic oblastí. V praxi se p�itom osv�d�ila tato metoda: je-li sklon šra-fování jiný než sm�r osy x �i y, pak je výhodn�jší oto�it šrafovanou


- 86 (120) -

entitu o úhel šrafování tak, aby šrafovací �áry byly rovnob�žné s n�kte-rou z hlavních sou�adných os. Tím se zjednoduší výpo�et pr�se�ík�. Takto získané pr�se�íky potom spojíme úse�kami. Pokud se v dané ob-lasti nalézají otvory, které se šrafovat nemají, pak postupujeme takto:

Všechny pr�se�íky v daném sm�ru o�íslujeme p�irozenými �ísly a spojujeme je v po�adí lichý se sudým, p�i�emž sudý s lichým z�stane nepropojen – viz obr. 7.2.

b) Texty se ve vektorových souborech ukládají jako

- �et�zce znak� ASCII, které jsou dopln�ny informacemi o atributech textu (druh písma, barva, rozm�r znak�, úhel sklonu apod.).

- odkazy do speciálních soubor� s obrysy znak� tzv. sady znakových tvar� (shape) s p�íponu bu� *.shx nebo *.shp.

a) uzav�ený prvek b) neuzav�ený prvek

Obr. 7.1. Definice uzav�enosti prvku vzhledem ke šrafování

1 2 3 4 5 6

Úse�kami se spojí tyto pr�se�íky: 1 + 2, 3 + 4, 5 + 6.

Obr. 7.2. Princip šrafování uzav�ených element� s otvory

c) Zm�na m��ítka. Vzhledem k matematické definici prvk� mohou být en-tity jednoduše libovoln� zv�tšovány nebo zmenšovány.

Fiktivní �ára pro výpo�et pr�se�ík� šrafovacích �ar

Vektorové formáty

d) Nezávislost na technickém za�ízení. Protože vektorový zápis p�edstavu-je matematický model kresby, který má vysoký stupe� obecnosti, je vektorový formát nezávislý na konkrétním technickém za�ízení.

Výhody vektorových formát�

- vhodné pro technické výkresy (2D i 3D), - snadná zm�na m��ítka kresby, - jednoduchá editace kresby – jde v mnoha p�ípadech o ASCII sou-

bor, který lze modifikovat b�žnými textovými editory, - nezávislost na konkrétním technickém za�ízení, - snadný p�evod do jiného grafického formátu.

Nevýhody vektorových formát� - jsou nevhodné pro složité p�edlohy nap�. fotografie, - výsledný vzhled je do jisté míry závislý na konkrétní aplikaci. To

znamená, že obecný matematický p�edpis v kresb� m�že daná apli-kace r�zn� zobrazit podle toho, jak interpretuje jednotlivé prvky,

- jsou vhodné p�edevším pro vektorov� orientovaná grafická za�ízení nap�. sou�adnicové zapisova�e. U rastrových za�ízení (obrazovka, tiskárna) se musí p�i rekonstrukci provést konverze z vektorového formátu do rastrového – viz kap. 8.3.,

- vzhledem k p�edchozímu bodu je rekonstrukce obrázku na výstupní za�ízení z vektorového formátu obecn� pomalejší než z bitmapového.

7.3 Technologie C4

S vektorovou grafikou je bezprost�edn� spjata technologie C4. Techno-logií C4 rozumíme komplex automatizovaných proces� pr�myslové výroby, které mají sv�j základ v po�íta�ové grafice a výrazn� se podílejí na celém vý-robn�-inova�ním �et�zci výrobku jenž je zobrazen na obr. 7.3. V této souvislos-ti n�kdy hovo�íme o tzv. inženýrské grafice. Jednotlivé po�íta�ové disciplíny komplexu C4 spolu úzce souvisejí a zabývají se návrhem nových produkt� a jejich realizací.

Obr. 7.3. Výrobn� - inova�ní �et�zec výrobku

7.3.1 Vymezení pojm�

specifikace návrh projekt

prototyp výroba inovace


- 88 (120) -

Technologie C4 lze jednoduše vyjád�it rovnicí: C4 = CAD + CAE + CAM + CIM. N�kdy se jednotlivé disciplíny ozna�ují také zkratkou CAx a mají tento význam:

CAD – Computer Aided Design je po�íta�em podporovaný návrh vý-robku. Vstupem do tohoto procesu je soubor specifikací (zadání), výstupem je úplný projekt v grafické i jiné form�. Jde o automatizaci p�edvýrobních etap nebo také automatizaci inženýrských úloh. Tato fáze probíhá za podpory roz-sáhlého programového vybavení, k n�muž systémy CAD pat�í.

CAE – Computer Aided Engineering je po�íta�em podporované ov��ení návrhu. Výstup z CAD ve form� projektu je t�eba nejd�íve verifikovat osv�d-�enými v�deckými metodami. Jde o metody analýzy, simulace a r�zné optima-liza�ní postupy.

CAM – Computer Aided Manufacturing je proces automatizované vý-roby, �ízené po�íta�em. Zahrnuje systémy pro p�ípravu dat a program� pro ovládání numericky �ízených stroj�, pro automatickou výrobu mechanických sou�ástí, celých sestav atd. Jako vstupy se využívají p�edevším geometrická a další data získaná ve fázi návrhu v systému CAD.

CIM – Computer Integrated Manufacturing znamená po�íta�em podpo-rovanou výrobu a to tak, že jsou integrovány všechny procesy v jednom systé-mu. Jde o využití komplexní distribuované databáze, která slouží nejen pro vlastní návrh, testování a výrobu, ale i pro takové d�ležité oblasti zajiš�ující produkci jako je ú�etnictví, fakturace, �ízení toku materiálu p�i výrob�, pláno-vání, distribuce výrobk� apod. S CIM souvisí ješt� dva další komplexní proce-sy, které se n�kdy vy�le�ují jako samostatné �innosti a to:

Obr. 7.4. Schéma struktury komponent C4

EDM – Engineering Document Management – správa inženýrské do-kumentace,

EDM PDM

CAD CAM

CAE

návrh

inovace

produkt

CIM

Vektorové formáty

PDM – Product Data Management – správa informací o produktu nebo dat produkt�.

Vzájemné vazby jednotlivých modul� CAx znázor�uje obr. 7.4.

Je t�eba poznamenat, že není striktn� vymezeno, jak mají jednotlivé komponenty C4 pracovat, co je jejich vstupem a co výstupem. V�tšinou je sys-tém CAD nasazen jako první krok v po�áte�ní fázi návrhu nového �i inovova-ného výrobku. Další kapitoly jsou zpracovány podle [28] - [30].

7.3.2 Systémy CAD

7.3.2.1 Historie CAD

Systémy CAD jsou st�žejní disciplínou technologie C4. Z historického hlediska m�žeme ve vývoji CAD systém� pozorovat 3 generace:

1. generace systém� CAD lze za�adit do 60. let. Byly to v�tšinou pro-gramové systémy pro numerické výpo�ty, které se ozna�ovaly jako systémy CAE (Computer Aided Engineering). V 70. letech za�aly vznikat první návr-hové systémy pracující s primitivní rovinnou grafikou implementované na technických prost�edcích s nevyhovující výkonností dodávaných na klí�.

2. generaci CAD systému m�žeme pozorovat v 80. létech, kdy došlo k prudkém rozvoji trojrozm�rné grafiky s následným 3D zobrazením. Tento trend se promítl i do návazných modul� typu CAM (Computer Aided Manu-facturing). Dalším charakteristickým rysem dané etapy je nástup um�lé inteli-gence v CAD a expertních systém� spolu s tzv. inženýrskými databázemi. Za-�alo se pracovat s geometrickými modely.

3. generace CAD spadá do 90. let, kdy se objevily nové technologie, nazývané souhrnn� jako inteligentní CAD, nap�.:nové typy ploch pro modelo-vání - NURBS,

- variantní a parametrické modelování - hybridní modelovaní, - modelování založené na prvcích (angl. features), - omezení (angl. constraints), - p�enosové standardy (IGES, STEP - STandard for the Exchange

of Product Model Data), - simultánní inženýrství (angl. concurrent engineering), - znalostní pop�. expertní systémy.

7.3.2.2 Krize CAD


- 90 (120) -

V celé historii postrádáme systematické budování teoretické základny CAD, což vyústilo v tyto problémy:

- chybí prost�edek pro formulaci zadání navrhovaných objekt�, - nedostate�né inteligentní prost�edí v �et�zci podle obr. 7.3., - nedostate�ná kontrola sémantiky vstupních údaj�, - problémy v archivaci, vyhledávání, vyhodnocování r�zných variant

návrhu (nap�. využití d�di�nosti projekt�), - preference numerických (konkrétních) výpo�t� p�ed symbolickými, Uvedený trend se projevil tzv. paradoxními tendencemi vývoje CAD,

které je možné shrnout do 3 bod�:

1. prudký nár�st složitosti navrhovaných výrobk�, 2. výrazný nár�st složitosti CAD systém�, 3. stagnace (dokonce i snižování) po�tu firem a návrhá��, které se za-

bývají vývojem a produkcí CAD systém�. Uvedené tendence p�sobí navzájem protich�dn�. V n�kterých publika-

cích je tato situace ozna�ována jako krize CAD systému.

7.3.2.3 Teorie CAD sytému

Teorie CAD dodnes není uspokojiv� vytvo�ena. Návrh probíhá podle zku-šeností, kdy každý návrhá� používá svoje vlastní návrhové metody a prost�edky a výsledky generuje v podstat� ru�n�. Základním úkolem teorie CAD je vytvo-�it formální systém popisu:

1. navrhovaných objekt�, 2. návrhového procesu tj. jednotlivých krok� návrhu.

Vstupem je specifikace navrhovaného objektu a jeho funkcí a výstupem jsou hodnoty atribut� navrženého objektu.

Existují dva základní p�ístupy k budování teorie CAD systému:

1. axiomatický – viz [31]. Návrhový proces je definován jako zobrazení z prostoru požadovaných funkcí navrhovaného objektu do prostoru hodnot atribut� tohoto objektu. Oborem funk�ních hodnot se rozumí obraz množiny všech funk�ních atribut�. Prostorem atribut� je množina hodnot r�zných typ�, které charakterizují výsledné parametry navrže-ného objektu tj. �ešení návrhu,

2. založený na teorii systém� - viz [32]. Vychází se z p�edpokladu, že teo-rie systém� spolu s teorií návrhového procesu tvo�í základ teoretické disciplíny zvané návrhová v�da (angl. design theory). Cílem návrhové v�dy je shromaž�ovat znalosti o návrhovém procesu, dále tyto znalosti kategorizovat, hledat vazby mezi nimi a jednotlivými návrhovými zna-lostmi. D�ležitá je i interpretace t�chto znalostí a jejich struktur.

U nás se CAD intenzivn� zabývají výzkumné týmy na �VUT v Praze a to na FEL (Doc. I. Jelínek) a na FSI (prof. J. Bíla).

Vektorové formáty

7.3.3 CAE

Cílem CAE je ov��it správnost vlastností navržených produkt�. Jde o analýzu, testování a simulaci funkcí, které mají navržené produkty zajiš�ovat. Mezi nejrozší�en�jší metody CAE modulu pat�í zcela ur�it� metoda kone�ných prvk� (angl. finite elements method), dále pak programy pro simulaci kinema-tiky (angl. kinematics), dynamiky (angl. dynamics) a rovn�ž i rapid prototy-ping, což lze p�eložit jako p�ímé �i rychlé prototypování.

Metoda kone�ných prvk�

Principem analýzy pomocí metody kone�ných prvk� je rozložení geo-metrického modelu zkoumaného objektu na trojrozm�rnou sí� prostorových element� s �ízeným stupn�m atomizace. Fyzikální analýze daného typu je podroben jak každý jednotlivý element samostatn�, tak i v souvislosti s ele-menty ostatními podle p�esn� aplikovaných fyzikálních zákon�.

Kinematika

Termínem kinematika v systémech CAE ozna�ujeme soubor modul� pro analýzu pohybu navržených mechanism�. To umož�uje analyzovat vzá-jemný pohyb model� t�les, dráhy jejich pohybu, zjiš�ovat možnost kolizí t�les apod. Výsledkem kinematické analýzy jsou p�edevším sou�adnice bod� trajek-torií pohybu testovaných t�les a p�ípadná vizualizace simulovaného pohybu. Tyto výsledky mohou být dále zpracovány na pracovištích s roboty �i v me-chanických sestavách.

Dynamika

Programy pro dynamickou analýzu simulují pohyb mechanických sys-tém�, na které p�sobí vn�jší síly. Po�íta�ový model pro dynamickou simulaci je kombinace geometrického modelu a hmotnostních vlastností simulovaných t�les a jejich sestav, na které p�sobí r�zné typy sil. Ze simulace dostaneme výsledné trajektorie pohybu, rychlosti, zrychlení vytypovaných bod� sestavy. Dále m�žeme obdržet i simulace pr�b�hu deformací. Velice �asto jsou výsled-ky p�edávány ve form� trojrozm�rných animovaných sekvencí.

Rychlé prototypování (3D hardcopy)

Jde o transformaci CAD modelu p�ímo do skute�ných fyzických mode-l�. Doba vytvo�ení modelu technologií rychlého prototypování se pohybuje �ádov� v hodinách. Existují r�zné technologie rychlého prototypování, z nichž v�tšina je založena na tzv. vrstvovém procesu. Základní myšlenka tohoto typu procesu spo�ívá v transformaci celého trojrozm�rného modelu na jednotlivé tenké rovnob�žné sousední vrstvy. Pro rychlost výroby prototypu je velmi vý-znamná volba sm�ru "�ezných" rovin. Fyzickou realizací t�chto vrstev je pak vytvá�en skute�ný prototyp.


- 92 (120) -

7.3.4 CAM

Pojmem CAM zahrnuje automatickou výrobu navržených produkt� na základ� dat získaných p�i návrhu pomocí modulu CAD a analyzovaných modu-ly CAE. Výrobn� technologická za�ízení jsou za�len�na do tzv. pružných vý-robních bun�k, které jsou �íslicov� �ízeny (angl. NC - Numerical Control). Jde o techniku, která využívá program� pro �ízení výrobních stroj� jako nap�íklad brusek, �ezacích stroj�, frézek, vrta�ek, ohýba�ek apod. Existují dva typy nu-merického �ízeni, které se liší ve zp�sobu uložení programu:

- CNC (angl. Computer Numerical Control) - výrobní stroj je napojen p�ímo na lokální �ídicí mikropo�íta�, kde je uložen vlastní program.

- DNC (Distributed Numerical Control) je modern�jší zp�sob, který je charakterizován pružným distribuovaným �ízením n�kolika vý-robních stroj� z jednoho centra.

Zvláštní kapitolou CAM systému je programování výrobních robot�. Roboty m�žeme programovat:

- klasickým zp�sobem tj. u�ením robota, kdy robot je nejprve veden ru�n� po jednotlivých krocích výrobního postupu,

- off-line zp�sobem, kdy program pro robot je vytvá�en mimo n�j a ve vhodném prost�edí je pak ov��en simulací.

Sou�ástí CAM je i modul pro plánování procesu (angl. Process Plan-ning). Plánem procesu se rozumí �asový a prostorový plán transportu polotova-ru produktu v prost�edí výrobního závodu mezi jednotlivými výrobními bu�-kami a uvnit� nich, po�ínaje zpracováním základních sou�ástí a kon�e sestave-ním výrobku a jeho expedicí. Úrove� plánování m�že být v hierarchii od vý-robní bu�ky až po soustavu výrobních provoz�. Plánování procesu má p�ímou návaznost na technologii CIM.

7.3.5 CIM

7.3.5.1 Charakteristické rysy CIM

CIM je zast�ešující technologie, která se zabývá sdílením informací v celém procesu produkce od návrhu až po distribuci produktu a z toho vycháze-jící problematikou efektivního toku a zpracování informací v celém výrobním podniku. I když je CIM v abstraktním smyslu moderní obecnou obchodní filo-zofií, v konkrétních p�ípadech �asto jde o otázky zpracování zna�ného množ-ství dat, která vznikají v r�zných fázích produkce. Z hlediska datových typ� zahrnuje CIM zcela rozdílné oblasti jako nap�. návrh, výkresovou dokumenta-ci, analýzu, simulaci, testování v inženýrských odd�leních, ale také numerické �ízení, plánování proces�, strukturu pružných výrobních jednotek, skladové

Vektorové formáty

hospodá�ství, zajišt�ní kvality p�i výrob�, vytvá�ení výstupní dokumentace, plánování rozvoje apod.

7.3.5.2 Zpracování a tok informací v C4

Jedním z d�ležitých moderních p�ístup� v C4 je simultánní inženýrství (angl. concurrent engineering), p�edevším v oblasti týmového p�ístupu k vývoji nového produktu. Jde o �ízený p�ístup k vývoji i produkci nového výrobku, p�i kterém �lenové týmu pracují soub�žn�, paraleln�. P�edpokladem tohoto typu práce jsou sdílené informace, jejich hierarchizace z hlediska oprávn�ného p�í-stupu jednotlivých �len� týmu a z hlediska sledování jejich návazností v �ase.

K nejd�ležit�jším �initel� pro simultánní vývoj výrobku pat�í speciální systémy zvané správa dat produktu (angl. product data management), správa informací o produktu (angl. product information systems) �i správa uspo�ádání dat (angl. configuration management). Systém správy dat produktu musí um�t uchovávat nejen uvedené informace modulu CAD/CAM/CAE, ale i údaje, kte-ré se vztahují ke skladovému hospodá�ství, logistice, �ízení objednávek, faktu-raci, ú�etnictví apod. N�kdy jsou tyto systémy rovn�ž ozna�ované jako inže-nýrské databáze (angl. engineering databases). Systémy správy dat pomáhají �ešit klí�ový problém, který se objeví p�i zavád�ní principu simultánního inže-nýrství - tj. jednoduchý p�ístup k velkému množství inženýrských dat a dat podporujících vlastní produkci v pr�b�hu jejich zna�ných zm�n, které mohou probíhat sou�asn� od r�zných zdroj� informací. D�ležitou vlastností musí být zcela jednozna�né vymezení práv p�ístupu k nim z pozice jednotlivých uživate-l�.

Speciální �ástí systému správy dat produktu je systém pro správu inže-nýrských dokument� (angl. engineering document management), který se za-bývá správou, �ízením a sledováním vývoje výkresové dokumentace a negra-fických informací vztahujících se k výkres�m. Systém pro správu inženýrských dokument� spravuje nejen nové vytvo�ené výkresy, ale i archivní výkresy, kte-ré jsou uloženy nap�. sejmuty a bez nichž by se p�i vývoji �ady tradi�ních pro-dukt� nebylo možno obejít. Výhodou systému pro správu inženýrských doku-ment� je p�edevším rychlost vyhledání výkresu p�i zm�novém �ízení nebo p�i inovaci, bez nebezpe�í omylu. Mezi standardní vlastnosti systému pro správu inženýrských dokument� zcela jist� pat�í zabezpe�ení p�ístupu na r�zných úrovních oprávn�ní, služby pro �ízenou distribuci dokument�, vhodné technic-ké prost�edky, moduly pro vyhledávání podle r�zných hledisek a prost�edky pro za�azení nových dokument� s p�íslušnými indexy pro pozd�jší vyhledání, respektování r�zných verzí dokumentu, zajišt�ní vazeb k r�zným projekt�m apod.


- 94 (120) -

7.3.6 Perspektivy dalšího vývoje technologie C4

Základní oblasti, ve kterých lze o�ekávat rozvoj technologií, jenž pod-po�í rozvoj C4:

1. Využití distribuovaného uložení informací v prost�edí INTERNETu. To odstraní jednak problém extrémních požadavk� C4 na lokální pam��o-vé kapacity a jednak p�irozen� podpo�í princip simultánního návrhu technologií telekomunikace.

2. Paralelní výpo�ty na systémech s paralelními architekturami. 3. Fotografická kvalita vizualizace na monitorech s obrazovkou 21“,

s rozlišením 1280 * 1024, se snímkovým kmito�tem 100 Hz v nepro-kládaném režimu.

4. Podpora návrhu prost�edky virtuální reality, využití informací multime-diálního charakteru.

5. Další rozvoj software pro všechny oblasti C4, a to p�edevším: - standardizace grafických rozhraní a formát�, - rozvoj metod expertních systém� v C4, - hlubší využití principu modelování pomocí prvku, - rozší�ení principu parametrického a variantního p�ístupu, - nové typy multimediálních informa�ních systém�, - nové standardy inženýrské dokumentace.

7.4 Shrnutí

Ve vektorových grafických formátech jsou obrázky popsány matema-tickým aparátem jako množina základních geometrických prvk� (angl. primiti-ves). Tyto prvky (bod, úse�ka, kružnice, mnohoúhelník, atd.) jsou dopln�ny svými atributy, které definují jejich vlastnosti. Rozd�lujeme je na defini�ní (typ, poloha a rozm�r prvku) geometrické (typ a tlouš�ka �áry, barva, sm�r, sousednost), speciální individuální (vrstva, deska/otvor, zachycení, p�íznak výmazu) a speciální skupinové (p�íslušnost ke skupin� a asociativita). Struktura vektorových formát� je podobná jako u bitmapových: hlavi�ka, vektorová data (povinné �ásti), paleta, pata, pop�. dalších komponenty (nepovinné �ásti). Z vlastností vektorových formát� stojí za pozornost metodika šrafování a vypl-�ování uzav�ených ploch a r�zná interpretace klí�ových bod� prvk� v r�zných aplikacích �i platformách.

S vektorovými formáty úzce souvisí technologie C4. Jde o komplex proces� v inova�ním cyklu (specifikace, návrh, projekt, prototyp, výroba, ino-vace). C4 zahrnuje CAD (návrh pomocí po�íta�e), CAE (verifikace návrhu), CAM (výroba �ízená po�íta�em) a CIM (komplexní automatizace výrobního procesu). CAD (Computer Aided Design) nemá dosud teoretickou základnu, což vyús�uje v krizi CAD. Od specifikace (zadání) do finálního projektu pro-bíhá drtivá v�tšina proces� ru�n� v aplikacích s dominantní podporou grafic-

Vektorové formáty

kých editor�. V procesu CAE (Computer Aided Engineering) se využívá t�chto metod: metoda kone�ných prvk�, kinematika, dynamika a rychlé prototypová-ní. Vstupem CAM (Computer Aided Manufacturing) jsou ov��ená data z návr-hu CAD+CAE, která �ídí výrobn� technologické stroje. Toto �ízení má 2 vari-anty 1. CNC (angl. Computer Numerical Control) - výrobní stroj je napojen p�ímo na lokální �ídicí mikropo�íta�, kde je uložen vlastní program, 2. DNC (Distributed Numerical Control) je modern�jší zp�sob, který je charakterizován pružným distribuovaným �ízením n�kolika výrobních stroj� z jednoho centra. CIM (Computer Integrated Manufacturing) znamená po�íta�em podporovanou výrobu a to tak, že jsou integrovány všechny procesy v jednom systému. Jde o využití komplexní distribuované databáze, která slouží nejen pro vlastní návrh, testování a výrobu, ale i pro takové d�ležité oblasti ekonomiky zajiš�ující pro-dukci jako je ú�etnictví, fakturace, �ízení toku materiálu p�i výrob�, plánování, distribuce výrobk� apod.

7.5 Autotest

1. Ve vektorovém formátu je kresba definována

a) jednotlivými body v rastru b) jen základními prvky c) základní-mi prvky v�etn� jejich atribut� d) základními prvky a entitami

2. Výhodou vektorových formát� proti rastrovým je

a) snadná komprese dat b) snadná zm�na m��ítka c) rychlé zobrazení na monitoru d) kvalitn�jší popis kresby e) v�rn�jší zobrazení barev

3. Pojem CAD znamená

a) návrh s podporou po�íta�e b) komplexní výrobní procesy

c) výroba �ízená po�íta�em d) ov��ení návrhu po�íta�em

4. Termínem CAM ozna�ujeme

a) návrh s podporou po�íta�e b) plánování výroby po�íta�em

c) výroba �ízená po�íta�em d) ov��ení návrhu po�íta�em

5. Pojem CIM znamená

a) návrh s podporou po�íta�e b) komplexní výrobní procesy

c) výroba �ízená po�íta�em d) správa dokument� �ízená po�íta�em


- 96 (120) -

8 Konverze dat

Konverzí dat rozumíme p�evod daného (vstupního) grafického formátu do jiného (výstupního) grafického formátu. Tuto �innost provádí speciální konverzní program nebo p�íslušná funkce (Import/Export) v rámci aplika�ního programového vybavení V mnoha p�ípadech je v rámci p�evodu užite�ná (i když nepovinná) interakce obsluhy, �ímž je umožn�no ovlivnit pr�b�h konver-ze podle našich požadavk� – viz obr. 8.1.

Obr. 8.1. Konverze dat

Jádrem konverze je konverzní program. K jeho sestavení je nutné znát podrobnou a p�esnou definici vstupního i výstupního formátu. To je v mnoha p�ípadech velmi obtížné, protože firmy v�tšinou popis vlastních formát� nezve-�ej�ují z konkuren�ních d�vod� (aby zákazník byl nucen zakoupit si firemní program, který dokáže s daným formátem pracovat). Situace je v tomto sm�ru p�íznivá u t�ch formát�, které jsou sv�tovými standardy.

Konverze dat probíhá v t�chto fázích:

1. Inicializa�ní fáze. V této �ásti je nutné p�i�adit d�ležitým prom�nným a strukturám konverz-

ního programu po�áte�ní (implicitní) hodnoty.

2. �tení vstupního formátu. Tato fáze pat�í k nejobtížn�jším z celého procesu. P�i �tení formátu se pro-

vádí jeho podrobná analýza, která podle charakteru vstupního formátu m�že být

a) syntaktická, je-li vstupní soubor textový. V tomto p�ípad� má texto-vý popis vstupního formátu charakter jazyka s regulární gramatikou a takový jazyk je p�ijímán kone�ným stavovým automatem – viz [17]. Syntaktická analýza se provádí na základ� tabulky stav�, po-mocí níž je stavový automat jednozna�n� ur�en.

vstupní formát

(zdrojový)

konverzní pro-gram

výstupní formát

(cílový)

interakce uživa-tele (možná)

Konverze dat

b) strukturální, je-li vstupní soubor binární. V tomto p�ípad� se nejd�í-ve definují pot�ebné údajové struktury (individuální prom�nné, po-le, záznam nebo objekt), které se použijí pro na�tení dat.

3. Identifikace objekt� vstupního formátu. Je to v podstat� výsledek analýzy vstupního formátu z p�edchozího kroku. Ze získaných údaj� se snažíme rozpoznat jednotlivé prvky vstupního formátu (rozm�r v ose x, y, hloubku pixelu, metodu komprese dat apod.).

4. Vlastní konverze. V této fázi probíhá p�evod vnit�ní reprezentace prvk� vstupního formátu do

vnit�ní reprezentace prvk� výstupního formátu.

5. Generování výstupního formátu. Zápis vnit�ní reprezentace všech prvk� výstupního formátu do fyzického

souboru.

V další �ásti jsou stru�n� uvedeny problémy p�i konkrétní konverzi dat. Protože v praxi jsou �ast�jší konverze mezi formáty r�zného typu než mezi formáty stejného druhu, rozebereme si podrobn�ji konverzi z vektorového do bitmapového a z bitmapového do vektorového formátu.

8.1 P�evod z bitmapového (rastrového) do bitmapo-vého formátu

Tento p�evod z jednoho druhu bitmapového souboru na jiný p�ináší v�tšinou nejlepší výsledky. Potíže se mohou objevit v t�chto p�ípadech:

a) Originál má více barev než výstupní formát. V tomto p�ípad� je t�eba p�ed-lohu nejd�íve p�edzpracovat metodou kvantizace (p�evést do stupnice s nižším po�tem diskrétních úrovní). V teorii barev se této metod� �íká roz-ptylování. Tyto úpravy však zp�sobí nevratné zm�ny p�edlohy v konvertovaném souboru – dojde ke ztrát� informace.

b) Nestejná velikost p�edlohy vstupu a výstupu. - Pokud je konvertovaná p�edloha menší než p�vodní, musí se n�kte-

ré informace ú�elov� vylou�it, �ímž dojde ke ztrát� informace. - Pokud je výstupní obrázek v�tší než originál, je naopak zapot�ebí

n�které informace vytvo�it a doplnit chyb�jící �ást p�edlohy. Tuto problematiku se obecn� doposud nepoda�ilo uspokojiv� vy�ešit.


- 98 (120) -

8.2 P�evod z vektorového do vektorového formátu

Jde v�tšinou o jednoduchou záležitost. Vyskytnout se mohou pouze 2 problémy:

a) nestejn� velká množina základních prvk� (primitiv). Nap�. používá-li p�-vodní formát rozší�ený repertoár entit (krom� základních jako bod, úse�ka, kružnice, mnohoúhelník také prvky typu text, šrafování/vypl�ování uza-v�ené oblasti, B-spline, Beziérovy k�ivky apod.) zatímco výstupní formát má definovány jen základní entity, pak konverze ze složit�jšího formátu do jednoduššího bude zahrnovat i �ešení aproximace k�ivek vyššího �ádu k�iv-kami nižšího �ádu na základ� numerických metod matematiky viz nap�. [15], [16].

b) nestejná interpretace metriky (m��ení vzdáleností) a vztažných (pilotních) bod� jednotlivých entit. Jde o problematiku umis�ování bod�, napojování �ar, geometrii ukon�ení �áry apod. V reálných systémech má �ára kone�-nou tlouš�ku a nap�. koncové body úse�ky mohou být na horní hranici �áry, uprost�ed nebo na dolní hranici �áry – viz obr. 8.2.

A1 B1

A2 B2

A3 B3

Obr 8.2. R�zná interpretace koncových bod� úse�ky

8.3 P�evod z vektorového do bitmapového formátu

V grafické databázi jsou p�edlohy uloženy v�tšinou ve vektorovém formátu, zatímco dnešní výstupní za�ízení (obrazovky, tiskárny) pracují v bitmapovém formátu. Zobrazovací procedura musí p�i každém vykreslování prvk�, (které jsou v grafické databázi ve vektorovém tvaru) provád�t konverzi z vektorového formátu do rastrového sou�adnicového systému obrazovky nebo tiskárny. Proto je tato konverze ze všech variant nejpoužívan�jší. P�evedení základních grafických primitiv (úse�ka, kružnice a elipsa) na posloupnost bod� (pixel�), které budou reprezentovat tvar primitiva, nazýváme proces rasteriza-ce. Vstupními údaji jsou: definice entity, její umíst�ní v sou�adném systému p�edlohy (sou�adnice) a dále rozlišení rastru dané vzorkovací periodou. Byla vyvinuta �ada algoritm� pro rasterizaci úse�ky, kružnice, elipsy – viz [18]. Pro ilustraci si n�které z nich uvedeme.

�ára dané tlouš�ky

Konverze dat

8.3.1 Rasterizace úse�ky

Protože v�tšinu složitých grafických objekt� v rovin� lze popsat pomocí souboru navazujících úse�ek, musí být algoritmus rasterizace úse�ky co nej-rychlejší, jinak by vykreslování obrázku bylo �asov� náro�né.

Úse�ka je zadána v�tšinou svým po�áte�ním a koncovým bodem ([x0, y0] a ([x1, y1]), ší�kou, barvou a vzorem (nap�. šrafování). Úkolem rasterizace úse�ky je nalezení všech sousedících pixel� nutných pro správné vykreslení úse�ky. Všechny algoritmy vycházejí z rovnice úse�ky v rovin� xy:

y = kx + q; k- p�edstavuje sm�rnici úse�ky (sklon) (8.1)

Algoritmy využívají znalosti po�áte�ního bodu úse�ky [x1, y1] a podle sm�rnice k = y/x = (y2- y1)/(x2- x1) ur�ují, která osa roviny xy bude �ídicí pro rasterizaci. Je-li k < 1, je �ídicí osa x, je-li k > 1, je �ídicí osa y. Ve sm�ru �ídicí osy se postupuje s krokem jeden pixel.

Obr. 8.3. Volba �ídicí osy p�i rasterizaci úse�ky

Podle zp�sobu výpo�tu krok� ve druhé ose (která není �ídicí) rozd�lu-jeme algoritmy rasterizace na DDA a Bresenham�v. Oba algoritmy využívají vestav�nou nebo p�eddefinovanou proceduru kresli_bod, která nakreslí bod v rastru o sou�adnicích, které jsou jejími vstupními parametry.


- 100 (120) -

8.3.1.1 Algoritmus DDA

Algoritmus DDA (Digital Differential Analyser) je jeden z prvních al-goritm� v po�íta�ové grafice. Ze znalosti po�áte�ního a koncového bodu úse�-ky se ur�í �ídicí osa – viz obr. 8.3. Algoritmus pracuje v itera�ním cyklu, kdy v každém kroku p�i�ítá k p�edchozímu bodu konstantní p�ír�stky v �ídicí ose jeden pixel a ve vedlejší ose hodnotu k. P�ír�stek k musí být zaokrouhlen, pro-tože výstupní za�ízení musí dostat informaci o bodu, který má zobrazit ve for-m� celých �ísel.

Obr. 8.4. Výsledek algoritmu DDA

Algoritmus pro k < 1: procedure Cara_DDA (x1, y1, x2, y2, color: integer);

var y, k :real;

begin

y:= y1;

dy:= (y2-y1)/(x2-x1);

Kresli_Bod (x1, y1);

while x1 < x2 do

begin

x1:= x1+1;

y:=y+dy;

Kresli_Bod (x0, round(y), color);

end; end;

Konverze dat

Výhodou DDA algoritmu je jeho snadná technická implementace, ne-výhodou je, že se matematické operace musí provád�t s velkou p�esností a pro každý pixel se využívají operace d�lení a zaokrouhlení. Tyto matematické operace jsou velmi výpo�etn� náro�né. Uvedené nedostatky odstra�uje algo-ritmus Bresenham�v, který si dále vysv�tlíme.

8.3.1.2 Bresenham�v algoritmus rasterizace úse�ky

Princip algoritmu je na obr. 8.5. Výchozím bodem je [Xi, Yi]. Další bod rastru a to bu� [Xi+1, Yi] nebo [Xi+1, Yi+1] se ur�í podle znaménka d:

Je-li d < 0, pak dalším bodem je [Xi+1, Yi],

je-li d ≥ 0, pak dalším bodem je [Xi+1, Yi+1].

Obr. 8.5. Bresenham�v algoritmus

Aby byl algoritmus rychlý, musí se pro výpo�et d používat matema-tické operace v oblasti celých �ísel. Výsledný vztah lze odvodit z obr. 8.5:

X = Xi + 1, Y = k(Xi + 1) + q, k = Y/X;

d1 = Y – Yi = k(Xi + 1) + q – Yi;

d2 = Yi + 1 – Y = Yi + 1 – k(Xi + 1) + q;

d = d1 – d2 = 2k(Xi + 1) – 2Yi + 2q –1; (8.2)

V dalších úpravách se snažíme vylou�it jedinou necelo�íselnou prom�nnou k tím, že celou rovnici (8.2) vynásobíme X. Definujeme tím tzv. predikci Pi:

Pi = d X = 2 YXi – 2Yi X + 2 Y + X(2q – 1 ); (8.3)

kde výraz 2 Y + X(2q - 1) = konst; (nem�ní se v pr�b�hu výpo�tu)

Pi+1 = 2 YXi+1 – 2 XYi+1 + konst; (predikce v dalším kroku)

Výsledné vztahy pro itera�ní výpo�et:

Pi ≤ 0 Yi+1 = Yi → Pi+1 =Pi + 2Y;

Pi > 0 Yi+1 = Yi + 1→ Pi+1 =Pi + 2Y – 2 X;


- 102 (120) -

Algoritmus pro úse�ku [XA; YA] [XB; YB] s kladnou sm�rnicí: 1. vykresli bod [XA ; YA], X0 := XA, X0 := XA, i = 1. 2. z rovnice (8.3) vypo�ítej P0 (ze sou�adnice po�. bodu úse�ky). 3. je-li Pi < 0 tak Xi+1 := Xi + 1, Yi + 1 := Yi, Pi+1 := Pi + 2y.

je-li Pi ≥ 0 tak Xi+1 := Xi + 1, Yi + 1 := Yi +1, Pi+1 := Pi + 2y – 2x. 4. vykresli bod [Xi+1; Yi+1]. 5. je-li Xi+1 < XB, pak i := i + 1 a návrat na krok 3, jinak konec.

Výhodou Bresenhamova algoritmu je odstran�ní zaokrouhlovací chyby a použití pouze matematické operace sou�et.

Pokud je úse�ka p�erušovaná, modifikuje se algoritmus tak, že se st�í-dav� povoluje a zakazuje vykreslení jednotlivých segment� úse�ky. Abychom dodrželi délku úse�ky, je nutné poslední úsek vždy povolit. V procedu�e mu-síme navíc deklarovat 2 prom�nné pro po�et segment� a po�et pixel� v rámci jednoho segmentu.

Rasterizace úse�ky, která má definovanou ší�ku, op�t probíhá podle Bresenhamova algoritmu s tím rozdílem, že vykreslujeme n�kolik pixel� vedle sebe podle požadované ší�ky. Tento po�et není závislý jen na ší�ce úse�ky, ale závisí i na sm�rnici této úse�ky. Proto se musí provád�t matematická korekce skute�né ší�ky úse�ky dle vztahu – viz obr. 8.6.:

dpix = d* sqrt((sqr(dx)+sqr(dy))/dx)

Obr. 8.6. Zm�na ší�ky úse�ky p�i zm�n� sm�rnice

8.3.2 Rasterizace kružnice

Mezi další základní primitiva pat�í kružnice. Její algoritmy rasterizace vycházejí z parametrického popisu kružnice:

x = x0+r*cos ; y = y0+r*cos ; ∈ <0, 2π>; (8.3)

Princip algoritmu spo�ívá v nahrazení kružnice posloupností úse�ek. Místo kružnice ve skute�nosti vykreslíme mnohoúhelník. Volíme po�áte�ní

Konverze dat

bod a k n�mu dopo�ítáme koncový bod úse�ky dle parametrických vztah�, zvyšováním hodnoty parametru . Otázkou z�stává, jaký volit konkrétní krok tohoto parametru. Empiricky bylo prokázáno, že optimální volba parametru je = 1/r. P�i této volb� negenerujeme kružnici jako souslednost úse�ek, ale jako souslednost pixel�. To p�edstavuje optimální iluzi kružnice.

Dosazování do parametrických vztah� je výpo�etn� náro�né, proto se v praxi využívá vztah� pro transformaci – otá�ení.

[ ] [ ] �

��

�

−⋅=

aa

aayxyx

cossinsincos

0,01,1 (8.4)

Obr. 8.7. Rasterizace kružnice

Obr. 8.9. Využití soum�rností kružnice pro urychlení procesu rasterizace


- 104 (120) -

Další možností ušet�ení výpo�etního �asu p�i rasterizaci kružnice je využití osové a st�edové soum�rnosti. V tomto p�ípad� je dosta�ující vypo�ítat 1/8 kružnice a zbytek získat pomocí soum�rností – viz obr.8.9.

8.3.2.1 Bresenham�v algoritmus rasterizace kružnice

Pro vykreslení bod� na kružnici se používá v praxi Bresenham�v algo-ritmus. Jako v p�ípad� úse�ky je op�t založen na výpo�tu predikce. Z predikce se vypo�ítá y-ová sou�adnice následujícího bodu a x-ová sou�adnice se zvýší o 1. Odvození predikce se provede stejným principem jako u úse�ky. Zde uve-deme pouze výsledky hodnot predikce a rozhodovací podmínky pro výb�r sou-�adnice vykreslení pixelu a predikce v dalším kroku:

po�áte�ní predikce: P0 = 1,25 – r;

Pi < 0 Yi+1 = Yi → Pi+1 =Pi + 2Xi + 3;

Pi ≥ 0 Yi+1 = Yi – 1 → Pi+1 =Pi – 2Yi + 2 Xi + 5.

8.4 P�evod z bitmapového (rastrového) do vektorové-ho formátu

Jde o jednou z nejsložit�jších úloh konverze spadající do t�ídy tzv. ex-pertních systém�. Obtížnost spo�ívá v tom, že v originálu musí být nalezeny všechny grafické objekty (body, úse�ky �áry, kružnice, mnohoúhelníky, texty apod.). Teoreticky je problematika dostate�n� popsána v [26], zde se omezíme jen na praktické postupy.

Konverze má tyto �ásti:

1. Definování pracovní oblasti. V�tšinou se provádí o�íznutím rastrového podkladu ve vhodném editoru (nap�. v systému MicroStation je to I/RAS B nebo I/RAS C).

2. Transformace rastrového obrazu. P�edlohy jsou snímány na certifiko-vaných sníma�ích s vysokou p�esností. Nasnímaný rastr však není p�es-n� umíst�n v sou�adnicovém systému a jeho rozm�ry neodpovídají sku-te�nosti. Cílem transformace rastru je umístit nasnímaný rastr do sou-�adnicového systému tak, aby byly minimalizovány odchylky mezi identickými body v rastru a ve vektorové kresb�. Dojde tak k �áste�né-mu potla�ení chyb plynoucích z nep�esností grafického zpracování �i deformací zp�sobených srážkou mapového listu. K dispozici máme tyto druhy transformací:

a. Shodnostní transformace. Má 3 parametry: úhel pooto�ení, po-sun v ose x a posun v ose y. Používá se jen v p�ípadech, kdy ne-chceme provést žádnou zm�nu m��ítka.

Konverze dat

b. Podobnostní transformace má 4 parametry (úhel pooto�ení, dva posuny a m��ítkový koeficient). Používá se v p�ípadech, kdy chceme provést zm�nu m��ítka, ale jsou d�vody pro� nepoužít afinní transformaci. Podobnostní a shodnostní transformace na-cházejí uplatn�ní zejména v geodetických aplikacích.

c. Afinní transformace je nej�ast�ji používaná transformace pro p�evod nam��ených snímkových sou�adnic (p�ístrojových sou-�adnic) do pravých snímkových sou�adnic zejména ve foto-grammetrii. Má 6 parametr� (úhel pooto�ení, dva posuny, dva m��ítkové koeficienty a parametr - úhel popisující kosost tj. ne-kolmost os).

d. Kolineární transformace je používána transformaci snímku do roviny X, Y ve fotogrammetrii. Má 8 parametr�, nezachovává d�lící pom�r jako p�edchozí transformace, nýbrž jen dvojpom�r.

e. Bilineární transformace byla používána op�t ve fotogrammetrii u kamer firmy Wild, které m�ly rámové zna�ky v rozích sním-ku.

f. Polynomická transformace se d�íve používala pro odstran�ní vlivu systematických chyb v �adové aerotriangulaci používající jako základní jednotku model. Uplatn�ní má v kartografii a dál-kovém pr�zkumu p�i odstran�ní deformací obrazu.

Sou�asné p�edpisy v resortu geodézie doporu�ují použití afinní

transformace prvního �i vyššího stupn�. Proces op�t probíhá ve vhodném editoru. Po p�ipojení rastru se nastaví parametry transfor-mace a definují se identické body (body totožné pro rastr i vektor). Minimální po�et t�chto bod� je po�et parametr� d�lených 2 (zao-krouhleno nahoru na celé �íslo). Vzhledem ke kvalit� transformace by m�ly být identické body vhodn� rozmíst�ny (ne p�íliš blízko u sebe). V praxi se používá 5 bod�: 4 v rozích mapového listu, pátý uprost�ed. Potom se spustí transformace a po ní se zkontrolují st�ední kvadratické odchylky transformovaných identických bod�. Pokud nevyhovují zadanému kritériu, zvolí se jiné identické body a transformace se opakuje. Vhodné prost�edí pro transformaci je nap�. I/RAS B, I/RAS C nebo Descartes v systému MicroStation nebo aplikace VKM �i GVIEW.

3. Vy�išt�ní rastrového obrázku. Rastrový obraz se zbaví veškeré neuži-

te�né informace.

4. Vlastní vektorizace. Z hlediska nutnosti zásahu obsluhy do procesu m�-žeme vektorizaci rozd�lit na

- Ru�ní. Jde o nejp�esn�jší, ale také nejpracn�jší metodu, - automatickou (bez výrazného zásahu obsluhy), - poloautomatickou (s interaktivními vstupy uživatele).

Bližší informace k dané problematice jsou v [26].


- 106 (120) -

8.5 Shrnutí

Konverzí dat rozumíme p�evod daného (vstupního) grafického formátu do jiného (výstupního) grafického formátu. Tuto �innost provádí speciální konverzní program (jednoú�elový) nebo p�íslušná funkce (Import/Export) v rámci aplika�ního programového vybavení. Konverze má tyto základní fáze: inicializace, �tení zdrojového formátu, identifikace objekt� zdrojového formá-tu, vlastní konverze a generování výstupního (cílového) formátu.

Podle charakteru existují 4 druhy konverzí (rastr –rastr, vektor – vektor, vektor – rastr a rastr – vektor). V praxi nej�ast�jší je konverze vektor – rastr (tzv. rasterizace), která vzhledem k bitmapovému principu zobrazení na moni-torech probíhá v mnoha aplikacích. Hlavním cílem této konverze je rychlost celého procesu. Z celé �ady metod pro rasterizaci úse�ky a kružnice jsou nej-znám�jší Bresenhamovy algoritmy, které pro urychlení využívají celo�íselnou aritmetiku procesoru. Algoritmicky nejobtížn�jší konverzí je rastr – vektor tzv. vektorizace. Jde o problém spadající do oblasti expertních systém�. Doporu�u-je se tento postup: 1. po�ízení rastru na kalibrovaném sníma�i, 2. co nejvíce zjednodušit vstupní rastrovou kresbu (odstranit neužite�nou informaci), 3. transformovat rastr do sou�adného systému vektorové (výstupní) kresby (dopo-ru�uje se afinní transformace) pomocí identických bod�, 4. vlastní vektorizace ve vhodném prost�edí grafického editoru, která m�že mít 3 varianty: a) ru�ní, b) poloautomatická, c) automatická.

8.6 Autotest

1. Nasazení expertních systém� je zapot�ebí p�i konverzi

a) rastr – rastr b) rastr – vektor c) vektor – rastr d) vektor – vektor

2. Nej�ast�jším druhem konverze v praxi je


3. Rasterizace je konverze


4. Podstatou efektivity Bresenhamova algoritmu je

a) výpo�et v celo�íselné aritmetice b) výpo�et v pohyblivé �ádové �árce

c) výpo�et pomocí logických funkcí d) operace v Booleov� algeb�e

Konverze dat

5. Nejlepší výsledky zajiš�uje vektorizace

a) automatizovaná b) ru�ní c) poloautomatická

6. Je-li vstupní soubor p�i konverzi textový používá se analýza

a) strukturální b) syntaktická c) shluková d) harmonická

7. P�i rasterizaci je hlavním cílem:

a) úspora pam�ti b) rychlost algoritmu c) eliminace aliasu

8. V Bresenhamov� algoritmu se o sou�adnici dalšího pixelu rozhoduje na zá-klad�

a) hodnoty jasu p�edchozího pixelu b) hodnoty sou�adnice p�edchozího pixelu

c) znaménka rozhodovacího �lenu d) hodnoty rozhodovacího �lenu

9. Rozhodují pro posouzení kvality transformace rastru p�i vektorizace je:

a) sou�adnicová chyba v ose x i y všech identických bod�

b) st�ední sou�adnicová chyba v ose x i y všech identických bod�

c) pr�m�rná kvadratická odchylka všech identických bod�


- 108 (120) -

9 P�ehled grafických formát�

Tato problematika je dostate�n� zpracována ve skriptech [26]. Proto v této �ásti podrobn�ji popíšeme jen ty formáty, které ve skriptech uvedeny nejsou. Formáty, které jsou ve skriptech [26] obsaženy zde uvedeme jen ve stru�né form�. P�ipomínáme, že podrobný popis grafických formát� m�žeme najít v mnoha publikacích zejména v [1], [7] a [3].

9.1 Bitmapové (rastrové) formáty

Podle [1] existuje asi 40 r�zných druh� bitmapových formát�. Proto si zde uvedeme jen ty nejznám�jší, s nimiž se v praxi setkáme nej�ast�ji.

9.1.1 Formát PCX

Je jedním z nejstarších formát�. Byl vyvinut firmou Zsoft pro grafický editor Paintbrush. Lze do n�j uložit obrázek o rozm�ru max. (215 – 1) x (215 – 1) tj 32767 x 32767 pixel� s 256-ti barvami. Data jsou komprimována metodou RLE nebo jsou bez komprese. V sou�asné dob� se používá verze Truecolor (hloubka pixelu 24 bit�). Existují 2 verze:

a) Verze 2.5, která je ur�ena pro �ernobílé nebo 16ti barevné p�edlohy. b) Verze 3.0, do které je možné ukládat obrázky s hloubkou pixelu 8 – 24

bit� do barevných rovin (planární uspo�ádání). Varianta Truecolor pou-žívá metody p�ímého zápisu obrazových bod� (bez palety).

9.1.2 Formát GIF (Graphic Interchange Format)

Formát byl vytvo�en v roce 1987 americkou spole�ností Compuserve speciáln� pro sí�ové služby (nap�. WWW stránky). V roce 1989 byl inovován jako verze GIF89, která je zam��ena na multimediální aplikace. Umož�uje ulo-žit obrázek o rozm�ru až 16000 x 16000 bod� s maximálním po�tem barev 256 z palety, která m�že obsahovat až 224 tj. 16,7 mil. barev. Údaje jsou kompri-movány metodou LZW s kompresním pom�rem asi 1,5. Používá se technika prokládání �ádk�. Princip spo�ívá v tom, že se p�i rekonstrukci zobrazují �ádky ve 4 krocích – viz obr. 9.1. Uživatel je tak schopen již po získání 1/4 nebo 1/2 objemu dat rozpoznat (podle hrubých rys�) vzhled obrázku a p�enos dat pop�. ukon�it, což vede ke zrychlení práce. Nevýhodou formátu je omezení palety jen na 256 prvk�.

P�ehled grafických formát�

Obr. 9.1. Princip prokládání �ádk� u formátu GIF

9.1.3 Formát PNG

Grafický formát PNG neboli Portable Network Format byl navržen jako náhrada staršího formátu GIF zejména pro použití v Internetu. Na rozdíl od formátu GIF u formátu PNG nejsou žádné nejasnosti v licen�ních právech. Z grafického formátu GIF p�evzal kompresi LZW, jejíž ú�innost zvýšil použi-tím p�edzpracování ukládaného pixelu. Formát podporuje ukládání obrázk� v 24 i 32 bitové barevné hloubce, a to p�i použití bezeztrátové komprese. P�i ukládání je možno použít dvojrozm�rného prokládacího schématu (na rozdíl od formátu GIF, který umož�uje pouze prokládání �ádk�), formát PNG dovoluje rozd�lit p�enášené pixely do sedmi skupin. Dekódované pixely pak mohou vypl�ovat �tvercové nebo obdélníkové oblasti, které se p�i postupném na�ítání dat zjem�ují. Nevýhoda formátu PNG na rozdíl od formátu GIF spo�ívá v nemožnosti ukládání sekvence obrázk� v jednom souboru.

9.1.4 Formát BMP

Formát se používá v systému MS Windows. BMP je zkratka od Bit Mapped Picture což voln� p�eloženo znamená „bitová mapa“. Existují 3 vari-anty formátu pro p�edlohy:

a) se 16ti barvami (4 bity/pixel), b) s 256ti barvami (8 bit�/pixel), c) Truecolor (24 bit�/pixel).

První 2 varianty používají komprese RLE ve 2 módech:

- kódovací mód. Paket obsahuje 2 slabiky. První z nich udává po�et po sob� jdoucích pixel�, které mají index barvy obsažený ve 2. sla-bice.

- absolutní mód. RLE paket zde také obsahuje 2 byte, p�i�emž 1. byte je nulový a 2.byte ur�uje po�et bezprost�edn� následujících slabik, které obsahují index barvy (v palet�) jednoho pixelu.

Varianta Truecolor kompresi dat nepoužívá, bitová mapa je v tomto p�ípad� uložena po vzorkovacích �ádcích sm�rem zdola nahoru. Každý �ádek obsahuje trojici hodnot RGB pro jednotlivé body.

1. krok, �ádky: 0, 8, 16, …

2. krok, �ádky: 4, 12, 20, …

3. krok, �ádky: 2, 4, 6, 8, …

4. krok, �ádky: 1, 3, 5, 7, …


- 110 (120) -

9.1.5 Formát Targa (TGA)

Formát zavedla firma Truevision. Byl to jeden z prvních formát�, který umož�oval uložit obrázek s hloubkou pixelu až 24 bit� (Truecolor). Je spolu s formátem JPEG jediným mezinárodním standardem pro ukládání statických obraz� (Standard ISO 96). Je podporován všemi platformami (MS-DOS, WINDOWS, UNIX, Macintosh). Proto se objevuje ve variantách jak little en-dian tak i big endian. Podobn� jako GIF dokáže uložit n�kolik p�edloh do jed-noho souboru. Umož�uje ukládat obrázek v planárních rovinách jako PCX. Používá kompresní schéma RLE nebo je bez komprese. Nejrozší�en�jší je p�-vodní verze formátu z roku 1987.

9.1.6 Formát TIFF (Tag Image File Format)

Sousloví „Tag Image File Format „ je možné voln� p�eložit jako formát pro uložení obrázku s popisem. TIFF definovala firma Aldus a použila jej ve svém programu PageMaker. Vyšší verze formátu byly vytvo�eny ve spolupráci s firmou Microsoft. V sou�asné dob� jde o nejpoužívan�jší formát v oblasti DTP (Desk Top Publishing – tj. publika�ní �innost) zejména jako výstupní formát z program� pro sníma�e.

Z Hlediska uspo�ádání bit� ve slabice existují 2 varianty pro Intel a Mo-torolu. Je tedy podporován všemi výpo�etními platformami (UNIX, DOS, Windows, Macintosh). Používá se r�zných typ� komprese dat (bez komprese, Huffmanovo kódování, komprese LZW nebo DCT). Je spolu s formátem JPEG jediným mezinárodním standardem pro kódování statických obrázk� [ISO 96]. Jako GIF dokáže uložit n�kolik obrázk� do jednoho souboru. Prošel složitým historickým vývojem od verze 3.0 (1986) do 6.0 (1992).

9.1.7 Grafický formát JPEG

Tento grafický formát byl vytvo�en expertní skupinou Joint Photogra-phic Experts Group pro uložení digitálních fotografií. Využívá komprese JPEG a pracuje pouze s barevnou hloubkou 24 bit� (ztrátová komprese DCT) nebo s 8mi bitovými obrázky ve stupních šedi (bezeztrátová komprese Hoffmano-vým kódem). Je vhodný p�edevším pro fotografie, proto se barevný formát JPEG používá hlavn� pro p�enos a archivování fotografií. Pro své vlastnosti je tento formát velmi oblíben a široce využíván a podporován.

Soubory s obrázky zakódovanými podle standardu JPEG mají obvykle p�í-ponu *.JPG. Výše popsaná verze JPEG využívající DCT je standard z roku 1989. Existuje norma formátu JPEG z roku 2000, která je založena na wavele-tové (vlnkové) transformaci.


9.2 Vektorové formáty

9.2.1 Formát DXF (Data Exchange Format)

Jde o textový soubor ve tvaru ASCII. Byl ustaven jako sv�tový standard pro vým�nu grafické informace (Data eXchange Format) mezi r�znými grafic-kými editory, zejména z oblasti CAD program�. Každý grafický editor t�ídy CAD by m�l mít vestav�né funkce export/import z/do formátu DXF. Struktura formátu je tvo�ena t�mito p�ti sekcemi:

1. HEADER (hlavi�ka), 2. TABLES (tabulky), 3. BLOCKS (bloky), 4. ENTITIES (entity), 5. Konec souboru EOF (End Of File).

Každá sekce obsahuje bu� žádnou nebo n�kolik skupin dat. Každá skupina dat zaujímá v souboru 2 �ádky:

1. �ádek = GROUP CODE – kód skupiny (identifikátor) - byte, 2. �ádek = GROUP VALUE – hodnota skupiny (konkrétní �íselný údaj). Výhody DXF formátu:

1. Je sv�tovým standardem, proto každý grafický editor by m�l být vybaven funkcí pro import/export tohoto formátu.

2. Snadná p�enositelnost kresby mezi r�znými grafickými editory. 3. Jde o ASCII soubor, proto m�že být po�ízen nebo modifikován b�žn� do-

stupnými textovými editory.

Nevýhody DXF formátu:

1. Nepoužívá paletu, proto je obtížné provád�t hromadné zm�ny barev. 2. Nemá podporou pro textové entity. Text je ve formátu uveden jen identifi-

kátorem. P�esná definice fontu musí být uvedena mimo formát. 3. Pokud kresba obsahuje vazbu na databázi, pak DXF formát nemá prost�ed-

ky pro popis t�chto vazeb a návaznost na databázi se nep�enese.

9.2.2 Formát HPGL

Formát zavedla firma Hewlett Packard a od ní je odvozen i název HP-GL (Hewlett Packard Graphic Language). Jde o speciální jazyk pro popis gra-fických objekt� ve vektorovém tvaru. Jde o textový soubor s p�íkazy jazyka pro �ízení kreslicího za�ízení (plotru). Syntax jazyka HPGL vypadá takto:

<mnemotechnický kód> <pole parametr�><terminátor p�íkazu>


- 112 (120) -

Mnemotechnický kód obsahuje 2 znaky, které jednozna�n� identifikují p�íkaz pro kreslení. Pole parametr� je množina hodnot odd�lených �árkami. Tento odd�lova� je zde povinný. Naproti tomu odd�lova� instrukcí – st�edník [;] je nepovinný. Existují i instrukce bez parametr�.

P�íkazy lze rozd�lit do t�chto skupin:

1. vektorov� orientované (kreslení prvk� – úse�ky, kružnice atd.), 2. znakov� orientované (vkládání text� do kresby), 3. nastavení atribut� prvk�, 4. nastavení kreslicího za�ízení, 5. stavové a konfigura�ní p�íkazy.

Existuje varianta jazyka HPGL2, což je formát HPGL v binárním tvaru tj. soubor je bitov� nikoliv znakov� orientovaný.

Pro ilustraci si uvedeme p�íklad zápisu kresby v jazyku HPGL, která je na obr. 9.4.

y

30

20

10

0 10 20 30 40 x

Obr. 9.4. Kresba k ukázce formátu HPGL

Zápis kresby na obr. 9.4. v jazyku HPGL:

IN;;;;PA10,10;;;;PD20,20;;;;PUPR20,10;;;;PDCI10;;;;PUPA30,10;;;;PDLBPokus####3PU;;;;

Vysv�tlivky:

PR – (Plot Relative) – relativní p�emíst�ní pisátka z aktuální pozice o hodnotu parametr� x, y

CI –(Circle) – nakreslí kružnici se st�edem v dané pozici o polom�ru daném hodnotou parametru.

PU – (Pen Up) – zvedni pisátko, PD – (Pen Down) – spus� pisátko.

Základní jednotka formátu HPGL je 0,025 mm (pro plotr). Kreslicí za-�ízení typu digigraf používá základní jednotku 0,01 mm. Bližší popis jazyka HPGL je v [7], str. 138 – 148.

Pokus

PR20,10

PA10,10

PD20,20 R=10


9.3 Metaformáty

Metaformátem nazýváme takový soubor s grafickou informací, v n�mž m�že být uložen obrázek jak v bitmapové tak i ve vektorové form�. V další �ásti si stru�n� popíšeme dva nejpoužívan�jší formáty: EPS a WMF.

9.3.1 Formát EPS

Zkratka EPS pochází ze sousloví Encapsulated PostScript. Data jsou v tomto formátu kódována jazykem PDL (Page Description Language – jazyk pro popis stránky) a potom jsou zapouzd�ena (Encapsulated) ve standardním formátu EPS pro p�enos mezi jednotlivými aplikacemi a platformami. P�íkazy jazyka jsou psány v tzv. polské (obrácené nebo postfixové) notaci. To je takový zp�sob zápisu, kdy operátor resp. p�íkaz se píše jako poslední až za jednotli-vými operandy resp. parametry (nap�. operace 5+4 se v této notaci zapíše jako 5 4 +). Formát vytvo�ila firma Adobe Systems v roce 1985 pro ukládání textu, �ernobílé nebo barevné p�edlohy v bitmapové nebo vektorové for-m�.Specifikace umož�uje zapsat data v textovém tvaru (ASCII). Formát je nezávislý na technickém za�ízení. Jazyk PostScript existuje ve 2 verzích:

1. PostScript Level 1 (za�átek 80. let), 2. PostScript Level 2 (1991), což je zdokonalený PostScript Level 1.

Co se tý�e vlastního formátu EPS, tak v sou�asné dob� existují 3 varianty:

a) Jednoduchý (základní) soubor EPS, který krom� informací o struktu�e (identifikace formátu rozm�r stránky, po�et stránek, použitý barevný model – RGB/CMY, apod.) obsahuje už jen p�íkazy jazyka PostScript,

b) Náhledový soubor EPS, který vychází ze základního formátu ad 1) a obsa-huje navíc hlavi�ku o velikosti 30 B. Ta blíže specifikuje obrázek náhledu, který m�že být bu� ve formátu WMF nebo TIFF (�ast�ji).

c) Nezávislý EPS formát obsahuje proti p�edchozí variant� technicky nezávis-lá grafická data obrázku náhledu v bitmapovém tvaru. Data jsou uzav�ena mezi klí�ová slova BeginPreview a EndPreview.

Bližší informace o tomto formátu jsou v [1] nebo [7].

9.3.2 Formát WMF

Název je odvozen z Microsoft Windows Metafile. M�že obsahovat jak bitmapové tak i vektorové obrázky. Pro uložení bitmapových dat se používá klasická funkce MS Windows GDI (Graphics Device Interface), která �iní data bimapy nezávislá na technickém za�ízení. Ve vektorovém popisu dat se použí-vá délkové jednotky 1 twip, což je zkratka z anglického termínu twentieth of a point tj, 1/20 typografického bodu. Typografický bod je definován jako 1/72


- 114 (120) -

palce (tj. 0,3527 mm), takže 1 twip = 1/1440 palce (inch). Bližší informace jsou uvedeny v [1] a [7].

9.4 Multimediální formáty

Formáty pro animované sekvence neboli formáty pro ukládání videa (film�) se podstatn� liší od formát� používaných pro ukládání statických ob-rázk�. Požadavek na omezený datový tok, rychlost dekomprese a kvalitu kla-dou na algoritmy pro ukládání (a p�ehrávání) velmi velké nároky. Moderní formáty tyto požadavky �eší modulární strukturou, kde jsou od sebe odd�leny použité kompresní metody (kodeky, angl. codec) pro ukládání zvuku a obrazu. Tyto kodeky jsou uloženy ve form� dynamických knihoven (COM modul�) se standardním rozhraním. Uživatel tak má k dispozici r�zné komprima�ní meto-dy jak pro video tak i pro audio �ást a m�že si zvolit ten nejvhodn�jší algorit-mus pro dané konkrétní použití. Nevýhodou takového otev�eného formátu je možnost použít pro komprimaci kodeku, který není k dispozici na po�íta�i, na kterém má být daný soubor p�ehrán. V takovém p�ípad� nezbývá nic jiného než daný kodek do systému doinstalovat (moderní p�ehráva�e umí neznámý kodek najít, stáhnout z Internetu a nainstalovat automaticky).

Mezi moderní, modulární formáty pro ukládání animovaných sekvencí pat�í zejména formáty AVI firmy Microsoft a MOV firmy Apple.

Pro komprimaci obrazu se p�i zpracování animovaných sekvencí (videa a filmu) používá ztrátová komprese podobná kompresi použité u formátu JPEG. Jednotlivé snímky nejsou ukládány za sebou v sekvenci jako tomu bylo u formátu animovaného GIFu, ale ve velké mí�e je využíváno rozdílových snímk�. Rozdílový snímek obsahuje pouze rozdíl informací (zm�nu) mezi sou-sedními snímky. V moderních kodecích se používá r�zn� transformovaný roz-dílový snímek, speciální algoritmy dokáží vyhledat místa ve snímku, která se nejmén� a nejvíce zm�nila od p�edchozího snímku, a to i v p�ípadech, kdy je zpracovávaná scéna v pohybu. Konkrétní použité algoritmy jsou obvykle p�ís-n� st�eženým firemním tajemstvím a jsou objektem patentové ochrany.

9.4.1 Formát MPEG

Formát byl navržen skupinou specialist� (Motion Picture Experts Group) p�i mezinárodní organizaci ISO a podle této skupiny byl i pojmenován. Vznik formátu byl ovlivn�n rozvojem multimédií, nebo� vznikla pot�eba uklá-dat multimediální data do souboru. Multimediálními daty rozumíme takové údaje, které zachycují více než jeden smyslový vjem (nap�. obraz a zvuk). Me-toda MPEG umož�uje ukládat pohyblivé obrázky nap�. film do souboru. V sou�asné dob� existují dv� varianty: MPEG I a MPEG II, p�i�emž norma MPEG II je zdokonalením MPEG I. Do souboru je možné ukládat obrazové sekvence s hloubkou pixelu 24 bit� v barevném modelu YCbCr s maximálním


rozsahem 4096x4096 obrazových bod�. Komprese obrazových a zvukových údaj� musí p�i reprodukci pracovat s rychlostí až 30 snímk�/vte�inu. Komprese dat probíhá ve 2 rovinách:

1. v rovin� �asové redundance 2. v rovin� pixelové redundance (obraz) pop�. frekven�ní redundance

(zvuk). ad 1) V rovin� �asové redundance se obraz i zvuk kóduje t�emi zp�soby:

a) kódování celého obrázku/zvuku (Intra Frame). Kóduje se každý obrázek samostatn�, což je p�i p�edepsané rychlosti 30 snímk�/sec. velmi náro�né. Snímky kódované tímto zp�sobem se nazývají I-snímky nebo také klí�ové snímky,

b) prediktivní kódování jednosm�rné. V tomto p�ípad� se kódují jen rozdíly mezi daným snímkem a jeho bezprost�edním p�edch�dcem v �asové po-sloupnosti. Takto zakódovaným snímk�m se �íká P-snímky (Predictive Frames)- predika�ní snímky,

c) prediktivní kódování obousm�rné kóduje rozdíly mezi daným snímkem a jeho bezprost�edním p�edch�dcem i následníkem. Metoda se n�kdy ozna-�uje jako kompenza�n� pohybové interpola�ní kódování a snímky zpraco-vané touto kompresí jsou známé pod názvem B-snímky (Bidirectional In-terpolative Frames)- obousm�rn� interpola�ní snímky.

Každá kódovací posloupnost musí za�ínat I-snímkem, pak mohou následo-vat ostatní snímky. Typické uložení posloupnosti snímk� do souboru je toto:

I B B P B B P B B P B B I

S ohledem na kvalitu rekonstrukce se doporu�uje, aby v kódovací posloup-nosti byl alespo� každý 10. – 14. snímek v �ad� I-snímek. P�i vynechání klí�o-vých snímk� by se ztráty neustále kumulovaly až by došlo k úplnému znehod-nocení p�enášené informace.

ad 2) v rovin� pixelové/frekven�ní se jako ve standardu JPEG používá diskrét-ní kosinová transformace. Dosahuje se komprima�ního pom�ru 10:1 až 30:1 pro obraz a 3:1 až 7:1 pro zvuk.

Na platform� PC se programová komprese realizuje nap�. programem Pixelshrink. Na Pentiu 90 trvá komprese 1 minuty videa ve VHS kvalit� asi 70 minut. Pomocí speciálních zásuvných karet (s obvody C-Cube) lze dosáhnout komprese i on-line (v reálném �ase). Pro dekompresi dat MPEG (p�i promítání) sta�í karta obrazového podsystému VGA se zabudovanou obvodovou logikou s dekompresním algoritmem.

9.4.2 Formát AVI

Formát AVI byl vyvinut firmou Microsoft pro její opera�ní systém Windows. V sou�asné dob� je nosnou sou�ástí komplexního produktu pro zpracování videa a audia s názvem Windows Media. Formát AVI neboli Audio Video In-


- 116 (120) -

terlaced je modulární a pro uložení videa a audia lze použít celé �ady kompri-ma�ních kodek�. Mezi nejpopulárn�jší pat�í nap�íklad :

Microsoft RLE, Cinepak, Intel Indeo, DivX a OpenX.

9.4.3 Formát MOV

P�vodcem formátu MOV je firma Apple, která jej vyvinula pro sv�j opera�ní systém MacOS. V sou�asné dob� je tento formát sou�ástí produktu QuickTime. Ve své podstat� je podobný formátu AVI, navíc umož�uje uložit i hudbu ve formátu MIDI, 360stup�ovou fotografii atd.

9.5 Shrnutí

Grafické formáty m�žeme podle popisu obsažené grafické informace roz-d�lit do 4 kategorií. V každé z nich uvádíme jen vý�et t�ch nejpoužívan�jších:

1. Bitmapové: PCX, GIF, PNG, BMP, TGA, TIFF, JPEG.

2. Vektorové: DXF (DXB), HPGL.

3. Metaformáty: EPS, WMF.

4. Multimediální formáty: MPEG, AVI, MOV.

9.6 Kontrolní otázky

1. Vyjmenujte nejpoužívan�jší formáty pro statické obrázky na Internetu

2. Uve�te výhody a nevýhody formátu DXF

3. Charakterizujte formát JPEG

4. Jaké kódování používá formát MPEG ?

Studijní prameny

- 117 (120) -

10 Studijní prameny

10.1 Seznam použité literatury

[1] MURRAY, J. D. – RYPER, W: Encyklopedie grafických formát�. Computer Press Praha v licenci O′ Reilly & Associates Inc. 1995. 736 s. + CD ROM.

[2] WIRTH N.: Algoritmy a štruktúry údajov. Bratislava, Alfa. 1989. 488 s.

[3] KLÍMA, M. – BERNAS, M. – HOZMAN, J. – DVO�ÁK, P.: Zpraco-vání obrazové informace. (Skriptum). Praha, �eské vysoké u�ení tech-nické. 1996. 177 s.

[4] HLAVÁ�, V. – ŠONKA, M.: Po�íta�ové vid�ní. Praha, Grada. 1992. 252 s.

[5] SOCHOR, J. – ŽÁRA, J. – BENEŠ, B.: Algoritmy po�íta�ové grafiky. (Skriptum). Praha, �eské vysoké u�ení technické. 1998. 184 s.

[6] HUDEC, B.: Základy po�íta�ové grafiky. (Skriptum). Praha, �eské vy-soké u�ení technické. 1993. 222 s.

[7] SOBOTA, B. – MILIÁN, J.: Grafické formáty. �eské Bud�jovice, Ko-op. 1996. 157 s.

[8] SOBOTA, B. – MILIÁNOVÁ, L. – MILIÁN, J.: Grafické editory. �es-ké Bud�jovice, Koop. 1997. 237 s. + CD ROM.

[9] KREMPASKÝ, J. Fyzika. Bratislava, Alfa, 1987, 760 s.

[10] Blochincev, D. I: O vztahu základního a aplikovaného výzkumu. Po-kroky matematiky fyziky & astronomie, ro�ník XXVII/1982, 61 s.

[11] TIFF. Revision 6.0, June 3, 1992. Adobe Developers Association. E-mail: [email protected], ftp:/ftp.adobe.com/pub/adobe/DeveloperSupport/TechNotes/PDFfiles.

[12] GONZALES, R. C.- WOODS, R. E.: Digital Image Processing. New York, Addison-Wesley Publishing Company, Inc. 1992. 716 s.

[13] COLE, E. R.: The removal of Unknown Image Blur by Homomorphic Filtering. [Doktorská disertace]. Salt Lake City 1973. Univerzita v Utahu. Katedra elektrotechnického inženýrství.

[14] AHMED, N., NATARJAN, I., RAO, K. R.: Discrete Cosine Transfor-mation. IEEE Trans. on Computers, 1974, �.1.

[15] REKTORYS, K. P�ehled užité matematiky. Praha, SNTL, 1981, 1139 s.

[16] PEZLAR, Z. Výpo�etní a zobrazovací technika I. Základy numerické matematiky. (Skriptum). Brno, Vysoké u�ení technické v Brn�, 1987, 160 s.


- 118 (120) -

[17] MANA, Z. Matematická teorie program�. SNTL Praha 1981, 468 s.

[18] ŽÁRA, J. – BENEŠ, B. – FELKEL, P.: Moderní po�íta�ová grafika. Computer Press Praha, 1998. 448 s.

[19] MAX, J.: Quantizing for minimum Distortion. IRE Transl. of Inf. Theo-ry, IT-6, 1960, �. 3,s. 7-12.

[20] TU�EK, J.: Geografické informa�ní systémy. Principy a praxe. Com-puter Press Praha, 1998. 424 s.

[21] BARTOŠ, S.: MicroStation. Brno, 1998. 424 s.

[22] PANTER, P. F. – DITE, W.: Quantization Distortion in Pulse Code Modulation with Non – uniform Spacing of Levels. Proc. of IRE, Vol. 39, 1951, �. 1, s 44 - 48.

[23] KOLÁ�, J. – ŠT�PÁNKOVÁ, O. – CHYTIL, M.: Logika, algebry a grafy. SNTL Praha, 1989. 440 s.

[24] WATT, A. - POLICARPO F.: The Computer Image. Addison-Wesley, ISBN: 0-201-42298-0, 1998.

[25] FOLEY, J., D., - A. van DAM - FEINER, S., K., -HUGHES, J., F. - PHILLIPS, R., L.: Computer Graphics: Principles and Practice. Addi-son-Wesley, ISBN: 0201848406, 1995.

[26] BARTON�K, D. Po�íta�ová grafika. VUT FAST Brno, Akademické nakladatelství CERM s. r. o. Brno, 2000, 109 s., ISBN 80-214-1624-6.

[27] PICHL, K. – HODICKÝ, J. – FRANTIŠ, P.: Základy po�íta�ové grafi-ky I. Skriptum EPI Kunovice s. r. o. 2004, 74 stran.

[28] JELÍNEK, I.: CAD systémy na rozcestí. Computer World 1996, 4 s.

[29] JELÍNEK, I.: O CAD systémech trochu jinak. Computer World 1998, 5 s.

[30] JELÍNEK, I.: C4 = CAD + CAM + CAE + CIM. Computer World 1998, 9 s.

[31] TOMIYAMA, T., YOSHIKAWA, H.: Extended general design theory. Proceeding of the IFIP WG 5.2 Working Conference of Design Theory for CAD, IFIP, Tokyo, 1987, pp. 95 - 130.

[32] HUBKA, V., EDLER, W., E.: Theory of Technical systems. A Total Concept Theory for Engineering Design. Springer Verlag, Berlin, 1988.

[33] DVO�ÁK, V., DRÁBEK, V.: Architektura procesor�. Vysoké u�ení technické v Brn�, nakladatelství VUTIUM, 1999, ISBN 80-214-1458-8, 294 s.

[34] BARTON�K, D. Vybrané kapitoly z po�íta�ové grafiky. VUT FAST Brno, Akademické nakladatelství CERM s. r. o. Brno, 2002, 148 s., ISBN 80-214-2083-9.

[35] BAYER, T. Hlavní programové nástroje pro tvorbu digitálních map s využitím systému MicroStation. VÚGTK Zdiby, publikace �. 34, ro�-ník 49, 2003, 273 str.

Studijní prameny

10.2 Seznam dopl�kové studijní literatury

[36] Fo�t, P.: Mechanical Desktop 4. První vydání, Computer Press, Praha 2000.

[37] Martišek, D.: Po�íta�ová grafika pro matematické inženýry. Vydání první, PC-DIR Real, Ústav matematiky FSI VUT v Brn� 1999.

[38] Rektorys, K.: P�ehled užité matematiky I. Vydání šesté, Praha, Prome-theus, 1996.

[39] Bubeník, F., Pultar, M.: Matematické vzorce a metody. �VUT, Praha, 1994.

[40] Budínský, B.: Analytická a diferenciální geometrie. SNTL, 1983.

[41] Ježek, F.: Geometrické a po�íta�ové modelování. (Text p�ednášky) Z�U, 1993.

[42] Polá�ek, J., Ježek, F., Kopincová, E.: Po�íta�ová grafika. �VUT, Pra-ha, 1991.

[43] Hodický, J., Františ,P.: Po�íta�ová grafika. VA Brno 2003.

[44] Watt, A., Watt, M.: Advanced Animation and Rendering Techniques. Theory and Practice. Addison Wesley 1992, ISBN 0-201-54412-1.

10.3 Odkazy na další studijní zdroje a prameny

[45] http://www.adobe.com/Support/TechNotes.html

[46] http://www.color.org


- 120 (120) -

11 Klí�

11.1 Odpov�di na kontrolní otázky

Kapitola 2

1. do 70. let, 80. léta 90. léta

2. Po�ízení, vizualizace, uchování a zpracování grafické informace bez ohledu na její obsah.

3. Po�ízení, editace, modelování a rekonstrukce grafické informace a databázo-vé operace.

4. Podle dimenze: rovinná, 3D, animace, dle popisu: rastrová, vektorová.

Kapitola 9

1. GIF, PNG, JPEG.

2. Výhody: sv�tový standard, textový soubor – �itelný a lehce editovatelný, snadná p�enositelnost mezi aplikacemi. Nevýhody: obtížná zm�na barev, pro-blém s definicí text�, nemá vazbu na databázi.

3. Je sv�tovým standardem, ukládá v True-Color, používá 4 varianty kódování (sekven�ní, bezeztrátové, progresivní a hierarchické). Podstatou kódu je DCT v kombinaci s predikcí a Huffmanovým kódem. Lze zvolit kvalitu, ztrátovost i stupe� komprese.

4. V rovin� �asové redundance se používají 3 metody: 1. Intra (I) snímky, 2. Prediktivní (P) snímky, 3. Obousm�rné (B) snímky. V rovin� pixelové redun-dance se používá DCT.

11.2 Výsledky autotestu

Kapitola 3:

1d 2b 3b 4d

Kapitola 4:

1a 2b 3a 4a 5b 6b 7b

Kapitola 5:

1c 2b 3e 4c 5b 6c 7c 8a 9b

Kapitola 6:

1c 2a 3a 4b 5d 6d 7b 8d

Kapitola 7:

1c 2b 3a 4c 5b

Kapitola 8:

1b 2c 3c 4a 5b 6b 7b 8c 9c

Date post:	03-Jan-2020
Category:	Documents
Upload:	others
View:	9 times
Download:	0 times

DALIBOR BARTON K PO ÍTA OVÁ GRAFIKA Ilences.cz/domains/lences.cz/skola/subory/Skripta/GE09... ·...

Documents