VYSOKÉ UENÍ TECHNICKÉ V BRN FAKULTA STAVEBNÍ DALIBOR BARTONK POÍTAOVÁ GRAFIKA I MODUL M01 TEORIE GRAFICKÝCH FORMÁT

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

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

- 3 (120) -

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

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í grafický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: Princip digitalizace obrazu, Shannon v/Kot lnikov v teorém, aliasing. Teorie barev, 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 obrazovou 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, predikce, 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, …).

- 7 (120) -

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, vektorová 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 ilustrativní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 pokud 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

2


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 proces 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 vysoké 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 ítaem (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é prost 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 komunikací (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 prudkého rozvoje výpo etní techniky (zejména unifikace hardware umož ující velkou 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živatel 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].

- 9 (120) -

Teorie grafických formát

2.2

P edm t po íta ové grafiky

P edm tem po íta ové grafiky jsou p edevším obecné procesy zpracová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 dní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ý) výstupní za ízení rekonstrukce obrazu

p edloha (obrázek)

digitalizace obrazu

vstupní za ízení

Technické a programové vybavení pro po ítao-vou

uživatel

editace modelování

uživatelské rozhraní

grafiku databázové operace grafická databáze

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

- 10 (120) -


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á, prostorová, rastrová i vektorová. V tomto modulu se budeme zabývat plošnou rastrovou a vektorovou grafikou. 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ý technický 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?


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 vlastnosti obrazového signálu tak, jak je vnímá i lov k. Použití jasu je jednodušší 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)

(x, y) ∈ R

(X, Y) ∈ N

(3.1)

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.

- 12 (120) -

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 informa ních systémech (GIS). Nevýhodou tohoto uspo ádání je to, že se na takto 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. Uzlové 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 skute 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ší Shannon 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šší frekvence 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:

a≤

d 2

(3.2)


Vzdálenosti a mezi sousedními body digitaliza ní m ížky se n kdy také d íká m ížková konstanta. Bude-li obrazová matice ídká tj. a , pak detail 2 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 jednorozm rný charakter. Jde o proces reprezentace analogových plošn diskretizovaný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 , je tato hodnota nahrazena rekonstruk ní úrovní ri. - viz obr. 3.3. Nech analogové amplitudy vzork leží v pásmu: dm ≥ F ( x , y ) ≥ d 0 kde

(3.3)

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 zkreslené 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 sousední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 kde

(3.4)

B0 je jas pozadí k = 0.015 - 0.02

po úpravách [26] dostaneme vztah pro po et kvantiza ních úrovní n: B max B min n= log(1 + k ) log

- 14 (120) -

(3.5)

Digitalizace obrazu

B max = 100 vychází rozlišitelný po et grada ních stup B min n=230, nejblíže vyšší mocna 2 k 230 je íslo 256 (tj. 28) Tento výsledek je potvrzen praxí, protože v mnoha p ípadech vyhovuje 256 kvantiza ních úrovní tj. zobrazení pixelu do 8 bit (viz kap. 5). Pro pom r jas

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 rozhodovací 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í kvadratická chyba a pro n kvantiza ních úrovní má tvar:

ε=

dm d0

( F − Fr ) 2 p( F ) dF =

m −1 j =0

d j +1 dj

( F − rj ) 2 p( F ) dF

(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

Vstupní vzorek F(x, y)

kvantovaný vzorek Fr(x, y)

d1 r0 d0 min. amplituda rozhodovací úrovn rekonstruk ní úrovn kvantiza ní chyba ∆ = Fr(x, y) - F(x, y)

Obr. 3.3. Princip kvantizace


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

rj =

dj + 1 + dj 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 zabý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

s rovnom rnou kvantiza ní charakteristikou.

a

kvantováním

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) uprost 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 (informace, 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 sinusovky, na obr. 3.5. b) je limitní p ípad Shannonova teorému (vztah 3.2.), kdy vzor-

- 16 (120) -

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é grafice 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í jediná barva tak, že se vypo ítá pr m r, který se p i adí celé ploše superpixelu. Filtruje se pomocí speciálních konvolu ních filtr pro potla 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 vzorkovací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.


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 evedení 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í fotoreceptor 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 muselo testovat, zda v jeho okolí ve vzdálenosti d není jiný vzorek. Pokud by takový 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].

- 18 (120) -

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 sejmutému vzorku v závislosti na jeho hodnot . V digitalizovaném obrazu se objevuje alias, který se projevuje tím, že vysoké kmito ty v obrazu vystupují jako kmito ty nízké. Je zp soben nedodržení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áhodn 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 odstranit v bec


4

Teorie barev

Barvy vnímáme prost ednictvím sv tla. Sv tlo je v podstat ást elektromagnetické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 elektromagnetický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ásma, 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é frekvence, 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í vlnovou délku). Samotný vjem barvy vzniká v mozku. Prost edníkem mezi podn tem (viditelným sv tlem) a vjemem barvy je oko – viz obr. 4.2. Svazek paprsk dopadá p es rohovku, o ku a sklivec na sítnici, která je pokryta bu kami 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í vlnovou délku (barevné vid ní).

Ty inky a ípky reprezentují funkci sníma , které transformují elektromagnetické 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álním po tu 6,5 milionu prvk (6,5M pixel ). Velmi zajímavé je, že plošné rozmí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á

- 20 (120) -

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

a)

(4.1)

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í,


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í vlnových d j vyplývá, že to možné není. Tato skute nost bude potvrzena CIE diagramem v další kapitole. Lze však vybrat n kolik základních barev, které vytvo í bázi pro velkou ást existujících barevných odstín . Kombinací základní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.

sou et

sou et

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

- 22 (120) -

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:

x=

A A+ B+C

y=

B A+ B+C

z=

C A+ B+C

(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. Vybereme-li složky x, y, pak m žeme reprezentovat všechny barvy pomocí dvourozm 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

CG 100[%] . Barva G na obr. 4.5. má sytost asi 75%. CA 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 (body) na úse ce AB kombinací základních barev, reprezentovaných práv body 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í stanovit 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. dána pom rem úse ek:


Obr. 4.5. Chromatický diagram CIE

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

- 24 (120) -

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 model . N které grafické systémy asto obsahují n kolik barevných model a prost edky pro p evod mezi nimi. Podle zp sobu míchání základních barev rozeznáváme 2 barevné systé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í barevné 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 zapisova (tj. barvy na bílém papíru) apod.

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

b)


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 = zelená), 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 ítají, 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í odstí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.

modrá

azurová bílá

purpurová

zelená erná ervená

Obr. 4.8. Model RGB

- 26 (120) -

žlutá

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 model 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í: 1

c

r

m = 1 − g

1

y

(4.3)

b

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: M

M = 0,5

Y

1

Y

(1 − 0,5)

C

1

C

=

K

(0,5 − 0,5) (1 − 0,5) 0,5

žlutá

0,5 =

0 0,5 0,5

ervená erná

zelená

purpurová bílá azurová Obr. 4.9. Model CMY

modrá

(4.4)


4.2.3

Model HSV

Nevýhodou p edchozích model byla nesnadná p edstavivost konkrétního barevného tónu ze 3 íselných informací. Nap . t žko lze íci bez p edchozí 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 odvozeno od slova Saturation = sytost a V znamená Value tj. hodnota (jasu). V odborné 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 obvodu 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 sytost) 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 - 28 (120) -

Teorie barev

4.2.4

Model HLS

I p es zjevné zdokonalení ve srovnání s modely RGB a CMY má p edchozí 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 šestiú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 Saturation 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 idá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.


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 kombinací 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 vzorcem, ale musíme použít algoritmus. Z geometrického vyjád ení t chto barevný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 signálu. Jsou to: • YUV – evropská norma PAL (Phase Alternating Line – st ídání fáze po ádcí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 Comittee – výbor národní televizní spole nosti). V této norm vysílají televize v Americe a Japonsku.

- 30 (120) -

Teorie barev

• YCBCR – ruská norma SECAM (Séquentiel Couleur à Mémorie – postoupení barevné informace do pam ti). V této norm se vysílá ve Francii, na Blízké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 – zobrazí se pouze jasová složka a barevné složky se nevyužijí. Tyto barevné modely nemají význam pouze pro televizní a videotechniku, 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í barvám na výstupním za ízení bu co do po tu (za ízení m že zobrazit jen omezený 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 dokáže vytvo it iluzi bohaté barevné stupnice. Princip spo ívá v tom, že barevný 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 paprsk ve výstupním obrázku tak, aby si oko z r zných kombinací sousední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.


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é jednotlivým vstupním intenzitám pak mohou mít tento tvar: 1

0 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é varianty 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

4

11

7

2

14

1

10

6

9

Md = 8

1

5

9

2

Mp = 8

12

13

6

13

4

15

14

10

5

0

11

7

3

(4.5)

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í podobu 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 transforma ní matice. Úkolem pak je vypo ítat index daného prvku v matici. Nejjednodušší 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 indexu i, j, p i emž n je ád matice. Tím ovšem dochází ke ztrát informace, kterou je nutno korigovat. Nejb žn jší metoda pro korekci se nazývá distribuce chyby – viz dále.

- 32 (120) -

Teorie barev

4.3.3

Distribuce chyby

princip metody spo ívá v tom, že se modifikují pixely, které jsou sousední 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 (transformovaném) obrázku a symbolem Cinmax resp. Cinmin maximální resp. minimá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ázorn 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.

Zpracované pixely 7/16E Nezpracované pixely

3/16E

5/16E

1/16E

Obr. 4.13. Distribuce chyby podle Floyd-Steinberga

Aktuální pixel


Další používané postupy (Stucki, Burkes, Sierra, Narcis – Judice – Ninke, 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ýsledky 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 elektromagnetické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, komplementá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. Reprezentantem 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 edchozí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 iemž zbylé 2 sou adnice p edstavují sytost a jas dané barvy.

Pokud za ízení není schopno zobrazit všechny barevné odstíny, je nutné použí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í uritá 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.

- 34 (120) -

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

c) oponentní teorie vid ní

d) jiném

4. Model RGB je založen na principu a) aditivním

b) subtraktivní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 sedním pixel m

d) v kumulaci chyby k sou-


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, zobrazení 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ý stupe 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. Rozezná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

význam bitu

27

0 26

0

0 25

1 24

0 23

1

22

21

0 20

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

- 36 (120) -


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

význam bitu

2

0 0

2

0 1

0 2

2

1 2

3

0 2

4

2

1 5

2

0 6

27

uložená informace: (10001010) binárn = 20 +24 +26 = 1+16+64 = (81) dekadicky 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. Lo - (low=nižší slabika)

i+1. 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 endian) 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 nastane tehdy, je-li logický formát dat roven bu p ímo fyzickému formátu nebo jeho celo íselným násobk m.


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: 5.1

k = log2 N

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 (index) do tabulky barev, které se íká barevná paleta – viz obr. 5.2. i. pixel R

G

(i+1). pixel B

R

G

B

… 127 127 127 30 20 50 … šedý pixel (127,127,127) 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

1

4

11

index

R

G

B

0

0

255

výstupní za ízení (monitor)

1 grafická databáze ( ást souboru) paleta (vyhledávací tabulka)

2 3 4 5

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

modrý pixel na obrazovce (0, 0, 255)

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í tabulka – angl. Look-Up-Table) je jednorozm rné pole barev. Každý prvek palety má velikost k = 3log2 N

- 38 (120) -

5.2


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 edlohy. 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 pixelu 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 palet, 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é tabulky – 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ý tená 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 grafické 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 barevný 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 barev 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


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

Dynamická paleta Barevné módy využívající paletu barev mají krom omezení na maximá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 jednoduchým trikem lze dosáhnout p sobivých efekt , jako nap íklad postupné rozsv 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 zný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 zelené,

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árna 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-

- 40 (120) -


livé pixely jsou v pam ti zarovnány po trojicích, což p ináší nutnost p istupovat k pixelu i na lichých adresách. Toto je velmi nevýhodné z hlediska rychlosti, 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á nastavenou 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 efekt 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 barevný 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 barevných korekcí, bitmapový index atd.).


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 bitmapových dat, jejichž jednozna ná identifikace je obsažena v hlavi ce. Nejjednodušší 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 grafický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 edem stanoveného pravidla. V tšinou se používá principu implicitního adresová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é obrazové matice do lineárního pole v souboru. Postupuje se po ádcích obrazové 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): BitCount Offseti = Offset + (i − 1) Im ageWidth (5.4) 8 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

Vzorkovací ádek 0

00

01

pixel 1 02

03

04

pixel 2 05

06

07

atd. 08

…

Vzorkovací ádek 1 Vzorkovací ádek 2 Vzorkovací ádek 3

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

- 42 (120) -

…

…


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 reprezentová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 len . Tento formát je již historický a používal se tehdy, m lo-li technické za ízení možnost zobrazit v jednom okamžiku pouze jednu barvu.

Pixel 1

Pixel 3 Pixel 2

Pixel 0

00

02 05

08

01

04

07

10

03

06

09

11

modrá plocha zelená plocha 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í (postupn 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


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 variant 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 celistvý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 rozd 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í komprimovaný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].

- 44 (120) -


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 technický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 tehdy, 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 (Offsety) všech dlaždic (tj. po et slabik od po átku souboru), aby rekonstrukce p edlohy 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 celistvým násobkem ší ky p edlohy a dlaždice na pravém okraji p edlohy p esahují svou ší kou rámec obrázku.


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.

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

2. úrove , 4 dlaždice rozlišení X/2

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

1. úrove

2. úrove

Obr. 5.8. Hierarchické dlaždice

- 46 (120) -

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ý zobrazil 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šeností. 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 zobrazení. 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ýhody, 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.


5.6

Shrnutí

Po et bit k, které je zapot ebí k uložení pixelu s hodnotou N je dán vztahem k=log2N. P i emž zp sob interpretace informace uložené v souboru závisí na konkré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 fyzického formátu nebo do jeho celistvých násobk . Pixel m žeme do souboru uložit bu tabulky barev tzv. palety.

p ímo nebo nep ímo jako index do

Podle po tu bit pot ebných k uložení 1 pixelu (tzv hloubky pixelu) rozeznáváme r zné módy: binární ( ernobílý obraz), úrovn šedi, 16 barev s paletou, 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 mohou využít k p ekrývání obraz a to bu absolutnímu (1 bit - obraz je/není vid 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 formátu uložen.

- 48 (120) -


5.7

Autotest

1. Bitové pohlaví je uspo ádání a) slova v souboru slov

b) slabiky ve slov

c) bit ve slabice

d)

bit

ve

d)

bit

ve

2. Termínem „Endián“ ozna ujeme uspo ádání a) slova v souboru slov

b) slabiky ve slov

c) bit ve slabice

3. Hloubka pixelu je 16 bit . Kolik r zných úrovní m že nabývat hodnota obrazové 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) barvá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

c) hlavi ka

b) pata

d) pásy

d) dlaždice

8. Hlavi ka v grafickém formátu neobsahuje a) bitmapová data

b) kompresní schéma

d) po et planárních rovin

c) identifikátor formátu

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 souboru


6

Komprese dat

6.1

Základní pojmy

Kompresí dat rozumíme redukci fyzické velikosti souboru dat p i zachová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ódování – Jde v podstat o to, zakódovat daný obrázek úsporn ji a efektivn 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 obrázek zpracovávat, 2. na ú elu, pro který je daná p edloha ur ena.

- 50 (120) -

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é zjednoduš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 doprava) a p e te se 2. pixel. Komprese je neztrátová. 7

0

7

1. pixel

0 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 obrazu. 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.


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 jednotlivých list stromu a speciální znak pro vrchol, jenž není listem stromu. Kódování za íná v ko enovém vrcholu. Nemá-li vrchol následníky, zapíše se do et 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 zapíš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 aktuálního vrcholu.

- 52 (120) -

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í vyskytují 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é literatu 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.


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 (slabika, 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: - 54 (120) -

Komprese dat

7

0 0 - 127

Délka proudu (proudové íslo)

Hodnota proudu 0/1

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 zakó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 1

0 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 . Pokud 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 . Kompresní schéma bude vypadat takto : 7 0

0 7 127

0

1. byte

0 29 = 156-127 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 elementem je slabika). Existují 3 varianty: 1. nekódovaný paket na bytové úrovni je na obr. 6.6. První byte obsahuje délku et zce znak , do druhé slabiky se ukládá hodnota opakujících se slabik. 7

0 7

délka proudu <0..255> 1. byte

0

hodnota proudu <0..255> 2. byte

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


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 hodnotou, 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

Indikátor proudu 0/1

0

délka proudu <0..127>

7

0

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) AAAAAAAAAABCDEF 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 hodnot 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 zce 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

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

7

0 hodnota 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).

- 56 (120) -

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ávislá 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 nezakódovaných byt ( ili p ímo hodnot pixel ), které jsou uvozeny délkou 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šum 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 jasu. 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


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, potom tato hodnota udává po et nezakódovaných pixel , které po ní bezprost edn následují.

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

P íznaková slabika 1B

1B

1B

255

14

138

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

P íznaková slabika 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. - 58 (120) -

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 127

hodnota

opakující se

opakující se

p íznak

hodnota

0

0

145

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 dosá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 (exponent, 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 posledn vložená fráze vy adí, pop . se p ebuduje celý slovník).


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 zavedeme 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ásobní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.

- 60 (120) -

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 pixelu) zakóduje pomocí H(si) bit , kde H (si ) = − log 2 pi

(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é hranici 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 vyskytují 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 etnostmi) 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 sluovaný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ý biná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

k=

X i =1

[− log 2 pi ]

(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 vypluje 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 .


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.

AXCTXCRCTCX (celkem 11 znak tj 11 byt = 88 bit )

Vstup: C (4)

C (4)

C (4)

X (3)

X (3)

X (3) [10]

C (4) [0] X,T,A,R (7) [1]

T (2) [110]

T (2)

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 etnost výskytu

Symbol (znak)

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 Comittee 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)

- 62 (120) -

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 standardní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 edchozí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 zakódován podle standardních tabulek pro 1D kódování.


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ýsledný kód

V(0) V(0) V(-1) Pass V(+1) V(+2) :

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].

- 64 (120) -

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 odvozen 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:

x = f (a, b, c, d , e ) + e px

(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 zapisovat 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 komprese touto metodou. Uložíme-li predik ní chybu beze zm ny nebo bezeztrátovou 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 – Variable 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 predik ní metodou


Bezeztrátová predik ní komprese je sou ástí standardu JPEG pro obrázky s mnoha úrovn mi šedi. Prediktory se liší ádem a rozm rem. ád prediktoru 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 edch 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 dekompozici 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 Haarový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 pomocí 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é nesou 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-

- 66 (120) -

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

4

9, 7, 3, 5

2

8

1

Koeficienty detail 1

4

6

–1

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 vztahu (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ákladem 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: N = f (u )

kde u je p íslušná úrove jasu N je etnost výskytu této úrovn v dané p edloze.

(6.5)


Proces prahování je pak výsledkem testování funkce T = [x, y, p ( x, y ), f ( x, y )] a p vodní obrazové funkce f ( x, y ) . Funkce p(x,y) vyjad uje lokální vlastnosti daného obrazového bodu (nap . pr m rnou hustotu výskytu úrovn šedi v daném okolí bodu (x,y). Prahovaný výstupní obraz g ( x, y ) je definován takto:

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

(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ý rozbor 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: I = 0.299 R + 0.587G + 0.114 B

R, G, B ∈ <0..255>

(6.7)

kde I je výsledná úrove jasu šedé. P epo ítávají se postupn všechny pixely 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 akceptovat, protože lidské oko je na modrou složku nejmén citlivé. - 68 (120) -

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í jasu 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: Ri, Gi, Bi ∈ <0..5> (6.8) 36 Ri + 6Gi + Bi 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 nahrazuje 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 í Euklidovská 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ódové 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 optimá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á.


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 ortogoná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í Fourieovy transformace DFT (Discrete Fourier Transformation).

6.11.1 Fourierova transformace obrazové funkce Každá spojitá periodická funkce se spojitou derivací f ( x ) a s periodou T se dá rozvinout v intervalu 0, T ve Fourierovu adu – viz [15]:

f (x ) =

a0 + 2

∞ n =1

(an cos nωx + bn sin nωx )

(6.9)

kde

2 an = T

T

0

f ( x ) cos nωxdx ,

2 bn = T

T

0

f (x )sin nωxdx ,

2π =ω T

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 1 se nazývá dána periodou T. Harmonická funkce v rozvoji o kmito tu f = T základní nebo také první harmonická. Obecn n-tá harmonická je taková funk1 ce, která má kmito et f = . Zvláštní postavení mezi t mito funkcemi má nT tzv. nultá harmonická, která vyjad uje st ední hodnotu funkce f ( x ) . Její amplituda 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. f (− x ) = − f ( x ) , 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. f (− x ) = f (x ) , pak bn = 0 pro n = 0, 1, 2, 3…; ada obsahuje jen konstantní len a0/2 a kosinové leny.

- 70 (120) -

Komprese dat

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

f (x ) =

∞ n =0

(c e n

jnωx

+ cn' e − jnωx

)

(6.10)

koeficienty cn , cn' vypo teme podle vzorc : 1 cn = T

T

f ( x )e

− jnωx

1 c = T ' n

dx

0

T

f ( x )e jnωx dx

0

Pro naše ú ely transformace p edlohy si rozší íme Fourierovu transformaci z 1D na prostor 2D. Na obr. 6.19 je znázorn na analogová obrazová funkce á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: 1 F (ω x , ω y ) = Tx T y kde

∞ ∞

f ( x, y )e

−

jω x x Tx

e

−

jω y y Ty

dxdy

(6.11)

−∞−∞

F (ω x , ω y ) je spojité Fourierovo spektrum, f(x, y) je analogová obrazová funkce – viz obr. 6.19.,

ω x , ω y 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


V diskrétním prostoru m žeme popsat dvourozm rnou diskrétní Fourierovu transformaci DFT vztahem: F (n1 , n2 ) =

1 1 N1 N 2

N1 −1 N 2 −1 x =0 y =0

g ( x, y )e − jω1x e − jω2 y

(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 =

2πn1 2πn2 , resp. ω 2 = jsou prostorové kmito ty ve sm ru osy x resp. y. N1 N2

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 vyjad 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 obrá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 ípadech velmi obtížný. Proto n které operace lze použitím Fourierovy transformace p evést na operace o ád nižší (nap . konvoluci na násobení). Mezi nevýhody 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 které koeficienty Fourierovy transformace nulové, v praxi se používají speciální algoritmy pro výpo et tzv. rychlé Fourierovy transformace FFT (Fast Fourier Transformation), které existují i jako technické akcelerátory (algoritmy zabudované do obvodové logiky) i v podob zásuvných desek do po íta .

- 72 (120) -

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í Fourierovy transformace lze rozložit na reálnou a imaginární složku podle vzorce:

e jnωx = cos

2πnx 2πnx + j sin N N

(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: g (x ) = f ( x )

(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 obsahovat jen kosinové leny.

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


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: f (x )

pro 0 <= N-1

g (x ) =

(6.15) f (2 N − x − 1)

pro N <= x < 2N-1

Z tohoto vztahu vyplývá, že g (2 N − x − 1) = g ( x )

(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: C (u , v) =

N −1 N −1 (2 x + 1)π u + cos (2 y + 1)π v 2 Ku Kv f ( x, y ) cos N 2N 2N x =0 y =0

(6.17)

p i emž normovací konstanty mají hodnoty: Kw =

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

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 podstatnou á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:

- 74 (120) -

Komprese dat

1. pokud se ve vstupním obrázku vyskytují ostré hrany, které jsou ve spektrá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 rekonstrukci 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é tomuto 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 nejví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: W [x, y ] = [ax + by + e, cx + dy + f ]

(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:

Ns D = 1 kde N je po et ástí objektu a s m ítko objektu.

(6.19)

B. Mandelbrot definoval pojem fraktál pomocí obou dimenzí takto: Fraktál je množina, jejíž Hausdorfova dimenze je v tší než dimenze topologická.


Jednoduché geometrické útvary jako je úse ka, tverec, krychle apod. mají topologickou a Hausdorfovu dimenzi stejnou. Proti tomu nap . u k ivky Kochové na obr. 6.21 je na první pohled patrná lenitost – jde o kompozici rovnostranný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 ivlog 4 ky Kochové (N=4, s=1/3) je (podle 6.19) rovna = 1.2618 . log 3

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. Mandelbrota. 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í Lsysté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

- 76 (120) -

Komprese dat

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

(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:

x

ai

bi

0

x

ei

wi y = ci z 0

di 0

0 × y + fi si z oi

(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 ): wi1

x y

=

ai ci

bi e x x × + i =T × + ti di fi y y

(6.22)

kde symbol T reprezentuje transformaci podobnosti Di jako nap . otoení, 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): wi 2 = si z + oi

(6.23)

kde si reprezentuje kontrast bodu a oi jas tohoto bodu. Podmínkou konvergence itera ního procesu je: 1. Ri ∩ R j = ∅ 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.). Domé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.


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 transformací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) koeficienty 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 (horizontal – 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 ípadech: 1. po spln ní ukon ující podmínky což znamená, že rozdíl (v absolutní hodnot ) 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): sk −1 − sk < ε pop . ok −1 − ok < ε (6.31)

- 78 (120) -

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ý minimalizuje 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 sledová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 transforma ní matice nulové, což odpovídá pozadí obrazu na výstupu. V 1. kroku iterace se vytvo í základní oblasti Ri stejné barvy. Další kroky iterace se skládají ze dvou fází:


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: Ri = s × Di + o

(6.32)

Fraktální komprese pat í mezi nesymetrické metody, protože proces komprimace 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, jimiž 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 technickou kresbu. Tyto ásti obrazu jsou po kompresi deformovány, n kdy dokonce úpln zmizí, to je typické hlavn pro p ímé áry, které sm ují diagonáln 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žit 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 paketu tj. proudové íslo (po et znak ) + hodnota proudu (znaku),

-

kvadrantový strom, v n mž je obraz zakódován do binárních et zc , 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ý slovní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-

- 80 (120) -

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: binarizací ( ernobílý obraz), p evodem z barev na stupn šedi, snížením po tu barev tak, aby byl využit fyzický formát pro uložení pixelu (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. Rozhodovacími úrovn mi kvantiza ní funkce jsou tzv. Voronoiho oblasti 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 kmito ty jednotlivých harmonických funkcí) se zakódují bu Huffmanovým kódem (bezeztrátová metoda v JPEG) nebo se dále kvantizují (ztráta informace). Koeficienty vyšších harmonických (malé hodnoty) 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 kompresi se obraz rozd lí na pravidelné bloky (Ranges), které se nep ekrývají. Ke každému bloku se hledá podobná doména, která po kone 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 transformací posunu, oto ení nebo zm ny m ítka. Do výstupního souboru 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á zachytí 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. Kvantujeme-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á.


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 d) velikost souboru

c) míra informace

2. Komprese RLE je nejú inn jší tehdy, obsahuje-li soubor posloupnosti a) stejných znak slov

b) r zných znak

c) stejných slov

d)

r zných

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

e) záznamu

d) blok

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 po et pravd podobnosti

b) itera ní po et

c) teorie informace

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

- 82 (120) -

d)


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á vektorové. Historicky jsou vektorové formáty starší než bitmapové, protože technická 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 motiv 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), entities (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 kolika 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 jednoduchých základních geometrických prvk (primitiv). Grafický formát vektorového typu tedy obsahuje množinu základních prvk , které jsou matematicky

- 83 (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 parametry 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 (identifikátor prvku, sou adnice prvku, rozm ry) 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 ), sousednost. 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, deska/otvor - u uzav ených areálových prvk , zachytitelnost/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.

2.

3.

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é spole 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ší.

- 84 (120) -

Vektorové formáty

b) Vektorová data. Jak již bylo uvedeno v p edchozí kapitole, jsou vektorová data složena z prvk , které mají své atributy (tvar, velikost, absolutní/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žit jší než dekódování bitmapového formátu, protože je nutné správn analyzovat jednotlivé prvky i všechny jejich atributy, zatímco u bitmapového formátu interpretujeme jen hodnoty pixel . Obecn lze íci, že u vektorový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 vektorové 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 totož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 ování uzav ených ploch je možné chápat ve trojím smyslu: souvislé vypln 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 šrafování jiný než sm r osy x i y, pak je výhodn jší oto it šrafovanou


entitu o úhel šrafování tak, aby šrafovací áry byly rovnob žné s n kterou 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é oblasti 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

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

6

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

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 entity jednoduše libovoln zv tšovány nebo zmenšovány.

- 86 (120) -

Vektorové formáty

d) Nezávislost na technickém za ízení. Protože vektorový zápis p edstavuje 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 soubor, 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á aplikace 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. Technologií 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 souvislosti 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í. specifikace

návrh

projekt

inovace

výroba

prototyp

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

7.3.1

Vymezení pojm


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 rozsá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 denými v deckými metodami. Jde o metody analýzy, simulace a r zné optimaliza 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 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 zajiš ující produkci jako je ú etnictví, fakturace, ízení toku materiálu p i výrob , plánování, distribuce výrobk apod. S CIM souvisí ješt dva další komplexní procesy, které se n kdy vy le ují jako samostatné innosti a to:

EDM návrh

PDM

CIM

CAM

CAD

produkt

CAE

inovace

Obr. 7.4. Schéma struktury komponent C4 EDM – Engineering Document Management – správa inženýrské dokumentace,

- 88 (120) -

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 systém CAD nasazen jako první krok v po áte ní fázi návrhu nového i inovované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 programové 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ávrhové 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 Manufacturing). Dalším charakteristickým rysem dané etapy je nástup um lé inteligence v CAD a expertních systém spolu s tzv. inženýrskými databázemi. Zaalo 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 modelová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


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 zabývají vývojem a produkcí CAD systém . Uvedené tendence p sobí navzájem protich dn . V n kterých publikací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 vytvoit 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ženého objektu tj. ešení návrhu, 2. založený na teorii systém - viz [32]. Vychází se z p edpokladu, že teorie 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 znalostmi. 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).

- 90 (120) -

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 kinematiky (angl. kinematics), dynamiky (angl. dynamics) a rovn ž i rapid prototyping, 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í geometrické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 elementy 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 trajektorií 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 mechanických sestavách. Dynamika Programy pro dynamickou analýzu simulují pohyb mechanických systé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ýsledky 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 model . 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.


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 moduly 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 numerické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 Planning). Plánem procesu se rozumí asový a prostorový plán transportu polotovaru 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 sestavení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ázejí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í filozofií, 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 dokumentaci, 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é

- 92 (120) -

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, které se vztahují ke skladovému hospodá ství, logistice, ízení objednávek, fakturaci, ú etnictví apod. N kdy jsou tyto systémy rovn ž ozna ované jako inžený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žený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živatel . Speciální ástí systému správy dat produktu je systém pro správu inženýrských dokument (angl. engineering document management), který se zabývá správou, ízením a sledováním vývoje výkresové dokumentace a negrafický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, které jsou uloženy nap . sejmuty a bez nichž by se p i vývoji ady tradi ních produkt nebylo možno obejít. Výhodou systému pro správu inženýrských dokument 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é technické 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.


7.3.6

Perspektivy dalšího vývoje technologie C4

Základní oblasti, ve kterých lze o ekávat rozvoj technologií, jenž podpo í 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 ové 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 neprokládaném režimu. 4. Podpora návrhu prost edky virtuální reality, využití informací multimediá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 matematickým aparátem jako množina základních geometrických prvk (angl. primitives). 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 vyplová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, inovace). 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 probíhá drtivá v tšina proces ru n v aplikacích s dominantní podporou grafic-

- 94 (120) -

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ávrhu CAD+CAE, která ídí výrobn technologické stroje. Toto ízení má 2 varianty 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í produkci 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 mi prvky v etn jejich atribut

b) jen základními prvky c) základní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


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


d) správa dokument

ízená po íta em


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 konverze podle našich požadavk – viz obr. 8.1.

vstupní formát (zdrojový)

konverzní program

výstupní formát (cílový)

interakce uživatele (možná)

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 nezveej 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 konverzní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 prová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á textový 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 , pomocí níž je stavový automat jednozna n ur en.

- 96 (120) -

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é, pole, 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 bitmapové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 edlohu 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á rozptylová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 které 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.


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í uzav 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 ivkami 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

ára dané tlouš ky

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 rasterizace. 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.

- 98 (120) -

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 nejrychlejší, 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 lujeme 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.


8.3.1.1 Algoritmus DDA Algoritmus DDA (Digital Differential Analyser) je jeden z prvních algoritm 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, protože výstupní za ízení musí dostat informaci o bodu, který má zobrazit ve form 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;

- 100 (120) -

Konverze dat

Výhodou DDA algoritmu je jeho snadná technická implementace, nevý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 algoritmus 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 matematické 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 ); 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 > 0

Yi+1 = Yi + 1→

Pi+1 =Pi + 2 Y; Pi+1 =Pi + 2 Y – 2 X;

(8.3)


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 + 2 y. je-li Pi ≥ 0 tak Xi+1 := Xi + 1, Yi + 1 := Yi +1, Pi+1 := Pi + 2 y – 2 x. 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 musí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í - 102 (120) -

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í.

[x1, y1] = [x0, y 0] ⋅

cos a

sin a

− sin a cos a

Obr. 8.7. Rasterizace kružnice

Obr. 8.9. Využití soum rností kružnice pro urychlení procesu rasterizace

(8.4)


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 algoritmus. 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 uvedeme pouze výsledky hodnot predikce a rozhodovací podmínky pro výb r souadnice vykreslení pixelu a predikce v dalším kroku: po áte ní predikce: P0 = 1,25 – r; → Pi+1 =Pi + 2Xi + 3;

Pi < 0

Yi+1 = Yi

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. expertní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 esn umíst n v sou adnicovém systému a jeho rozm ry neodpovídají skute nosti. Cílem transformace rastru je umístit nasnímaný rastr do souadnicové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í, posun v ose x a posun v ose y. Používá se jen v p ípadech, kdy nechceme provést žádnou zm nu m ítka.

- 104 (120) -

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 nachá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 souadnic) do pravých snímkových sou adnic zejména ve fotogrammetrii. Má 6 parametr (úhel pooto ení, dva posuny, dva m ítkové koeficienty a parametr - úhel popisující kosost tj. nekolmost 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ímku. 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álkové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 transformace 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 (zaokrouhleno 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žite 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].


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 monitorech 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 nejzná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 uje 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 (doporu 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 vektor

b) rastr – vektor

c) vektor – rastr

d) vektor –

c) vektor – rastr

d) vektor –

c) vektor – rastr

d) vektor –

2. Nej ast jším druhem konverze v praxi je a) rastr – rastr vektor

b) rastr – vektor

3. Rasterizace je konverze a) rastr – rastr vektor

b) rastr – vektor

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í

- 106 (120) -

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


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 komprimová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 .

- 108 (120) -


1. krok, ádky: 0, 8, 16, …

2. krok, ádky: 3. krok, ádky: 4, 12, 20, … 2, 4, 6, 8, …

4. krok, ádky: 1, 3, 5, 7, …

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žití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 varianty 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. slabice. - 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.


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 endian tak i big endian. Podobn jako GIF dokáže uložit n kolik p edloh do jednoho 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 Motorolu. 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 Photographic 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 Hoffmanový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 waveletové (vlnkové) transformaci.

- 110 (120) -


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 grafický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. 2. 3. 4. 5.

HEADER (hlavi ka), TABLES (tabulky), BLOCKS (bloky), ENTITIES (entity), 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. 2.

ádek = GROUP CODE – kód skupiny (identifikátor) - byte, á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 dostupný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 identifiká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 edky 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 HPGL (Hewlett Packard Graphic Language). Jde o speciální jazyk pro popis grafický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 >


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. 2. 3. 4. 5.

vektorov orientované (kreslení prvk – úse ky, kružnice atd.), znakov orientované (vkládání text do kresby), nastavení atribut prvk , nastavení kreslicího za ízení, 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

PR20,10 20

R=10

PD20,20 Pokus

10

PA10,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.

- 112 (120) -


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 jednotlivý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é form .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 obsahuje 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ávislá 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


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 obrázk . Požadavek na omezený datový tok, rychlost dekomprese a kvalitu kladou 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í metody jak pro video tak i pro audio ást a m že si zvolit ten nejvhodn jší algoritmus 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 sousedními snímky. V moderních kodecích se používá r zn transformovaný rozdí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 ísn 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). Metoda 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 - 114 (120) -


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é posloupnosti. 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 oznauje jako kompenza n pohybové interpola ní kódování a snímky zpracované touto kompresí jsou známé pod názvem B-snímky (Bidirectional Interpolative Frames)- obousm rn interpola ní snímky. Každá kódovací posloupnost musí za ínat I-snímkem, pak mohou následovat ostatní snímky. Typické uložení posloupnosti snímk do souboru je toto: IBBPBBPBBPBBI S ohledem na kvalitu rekonstrukce se doporu uje, aby v kódovací posloupnosti byl alespo každý 10. – 14. snímek v ad I-snímek. P i vynechání klí ových snímk by se ztráty neustále kumulovaly až by došlo k úplnému znehodnocení p enášené informace. ad 2) v rovin pixelové/frekven ní se jako ve standardu JPEG používá diskrétní 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-


terlaced je modulární a pro uložení videa a audia lze použít celé ady komprima 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 rozd 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 ?

- 116 (120) -

Studijní prameny

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.: Zpracování obrazové informace. (Skriptum). Praha, eské vysoké u ení technické. 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é vysoké u ení technické. 1993. 222 s.

[7]

SOBOTA, B. – MILIÁN, J.: Grafické formáty. eské Bud jovice, Koop. 1996. 157 s.

[8]

SOBOTA, B. – MILIÁNOVÁ, L. – MILIÁN, J.: Grafické editory. eské 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. Pokroky matematiky fyziky & astronomie, ro ník XXVII/1982, 61 s.

[11]

TIFF. Revision 6.0, June 3, 1992. Adobe Developers Association. Email: [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 Transformation. 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.

- 117 (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. Theory, IT-6, 1960, . 3,s. 7-12.

[20]

TU EK, J.: Geografické informa ní systémy. Principy a praxe. Computer 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. Addison-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é grafiky 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.

- 118 (120) -

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, Prometheus, 1996.

[39]

Bubeník, F., Pultar, M.: Matematické vzorce a metody. 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. 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.

VUT, Praha,

10.3 Odkazy na další studijní zdroje a prameny [45]

http://www.adobe.com/Support/TechNotes.html

[46]

http://www.color.org

VUT, Pra-


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ázové 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, problé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é redundance se používá DCT.

11.2 Výsledky autotestu Kapitola 3: 1d

2b

3b

4d

3a

4a

5b

6b

7b

3e

4c

5b

6c

7c

8a

3a

4b

5d

6d

7b

8d

3a

4c

5b

3c

4a

5b

6b

7b

8c

Kapitola 4: 1a

2b

Kapitola 5: 1c

2b

9b

Kapitola 6: 1c

2a

Kapitola 7: 1c

2b

Kapitola 8: 1b

2c

- 120 (120) -

9c

VYSOKÉ UENÍ TECHNICKÉ V BRN FAKULTA STAVEBNÍ DALIBOR BARTONK POÍTAOVÁ GRAFIKA I MODUL M01 TEORIE GRAFICKÝCH FORMÁT

Recommend Documents