Pocitacova grafika

Obsah

Rastrove a vektorove formaty

Formatu dvourozmerne pocitacove grafiky, tedy datovych formatu, ve kterych je mozne uchovavat informace o poloze dvourozmernych objektu v rovine, existuje cela rada. Vsechny vsak jdou rozdelit do dvou zakladnich trid --- na formaty rastrove a na formaty vektorove.
Rastrove formaty
Pri popisu objektu pomoci rastroveho formatu popisujeme vysledny vzhled kresby. Tato kresba se sklada z elementarnich utvaru (obvykle malych ctvercu), nazyvanych pixely. O kazdem tomto pixelu se uchovava jeho barva a pripadne dalsi informace. Soubor popisujici barvu a dalsi vlastnosti pixelu lze pak ruznym zpusobem usporadavat a data v nem obsazena pripadne komprimovat tak, aby se zmensila velikost dat nutnych pro ziskani potrebne graficke informace.
Vektorove formaty
Vektorove formaty pracuji s pojmem entita. Takovou entitou muze byt libovolny geometricky objekt, napriklad usecka, kruznice, obdelnik, nebo usek textu. Kazdy typ entity ma v danem formatu sve metody, kterymi je mozneho popsat a na zaklade kterych je mozne geometricky objekt zrekonstruovat. Takovou metodou muze byt napriklad znalost souradnic dvou krajnich bodu usecky.

Obecne se da rici, ze vektorove formaty obsahuji vice informaci, nez formaty rastrove. Krome vzhledu entity pri danem zpusobu zobrazeni, danem meritku atd. totiz obsahuji informace, na zaklade kterych je mozne odvodit i vzhled a dalsi vlastnosti entit v pripade zmeny zobrazeni. Proto take prevod kresby z vektoroveho formatu do formatu rastroveho (rastrace) je radove jednodussi ulohou nez prevod z formatu rastroveho do formatu vektoroveho (vektorizace).

S rastrovymi formaty se snaze pracuje tehdy, pozaduje-li se jejich zobrazeni na vystupnim zarizeni pocitace, nebo naopak vstup dat ze vstupniho zarizeni. Vetsina periferii dnesnich pocitacu (obrazovka, tiskarna, skener) totiz pracuje s daty v rastrove podobe.

Bitmapa

Nejjednodussim rastrovym formatem je tzv. bitmapa. Slouzi pro uchovavani cernobilych obrazku. Bitmapa je tvorena matici velikosti nxm, ktera odpovida obrazku velikosti nxm pixelu. Prvky matice jsou 0, nebo 1, v zavislosti na barve pixelu (0...cerna barva, 1...bila barva).

Cernobilou bitmapu lze zobecnit na bitmapu ve stupnich sedi. Uchovavana hodnota na jednom policku matice pak nebude jen jeden bit, ale cislo oznacujici prislusny stupen sedi pro dany pixel. Pro zobrazeni bitmapy se stupni sedi na cernobilem vystupnim zarizeni se pouziva technika polotonovani.

V barevne bitmape se na jednom policku matice uchovava informace o barve tohoto policka v domluvenem barevnem modelu.

Barevny model RGB

Barvy, ktere vnima lidske oko, vznikaji jako slozeni tri zakladnich barev. Za tyto tri zakladni barvy mohou byt vzate napriklad barva cervena (R, red), zelena (G, green) a modra (B, blue).

Libovolnou barvu lze pak vyjadrit jako linearni kombinaci tri zakladnich barev RGB, tedy jako vektor [r,g,b], kde r,g,b jsou hodnoty mezi 0 a 1. Napriklad bod [0,0,0] odpovida barve cerne, [1,1,1] barve bile, [1,1,0] barve zlute (Y, yellow), [1,0,1] barve fialove (M, magenta) a [0,1,1] barve tyrkysove (C, cyan). Body na hlavni uhlopricce jednotkove krychle, tedy body [x,x,x] pro x od 0 do 1 odpovidaji stupnum sedi.

Barvy vyjadrene v modelu RGB lze skladat podle aditivniho pravidla. Vektor barvy vznikle spojenim dvou barev vznikne jako soucet vektoru dilcich barev.

Model RGB je nejblizsi beznemu lidskemu vnimani barev a je nejcasteji pouzivan v rastrovych formatech pocitacove grafiky. Zobrazovani barev v modelu RGB se tez snadno technicky realizuje na monitoru pocitace.

Barevny model CMY a CMYK

Barevny model CMY je modelem dualnim k modelu RGB. Jako zakladni barvy jsou vzaty doplnkove barvy k zakladnim barvam RGB, tedy tyrkysova (C,cyan), fialova (M, magenta) a zluta (Y, yellow). Prevod mezi barvou vyjadrenou v modelech RGB a CMY je nasledujici (c,m,y) = (1,1,1) - (r,g,b).

V modelu CMY odpovida vrchol krychle [0,0,0] barve bile a vrchol [1,1,1] barve cerne. Skladani barev v modelu CMY je subtraktivni. Barva vznikla slozenim dvou barev vznikne odectenim souctu doplnku techto barev.

Model CMY se vyhodne pouziva pri tisku, kdy jednotlive barvy lze ziskat jako soutisk tri doplnkovych zakladnich barev vytistenych na bilem pozadi.

Barvu cernou je mozne ziskat jako soutisk tri doplnkovych barev CMY v plne intenzite. Diky nepresnostem pri tisku nebude tento soutisk vzdy dokonaly. Navic barevny tisk je vzdy drazsi nez tisk pouhou cernou barvou. Tato fakta spolu s faktem, ze cerna barva stale ve vetsine tiskovin, byt barevnych, prevlada, vedla ke vzniku modelu CMYK.

V modelu CMYK jsou tri doplnkove zakladni barvy CMY doplneny o barvu cernou (K, blacK). V pripade tisku cernou barvou, je pak tato barva vyjadrena vektorem (0,0,0,1). U ostatnich barev muze ctvrta souradnice vektoru slouzit k vyjadreni svetlosti ci tmavosti daneho barevneho odstinu.

Barevne modely HSV a HLS

Modely RGB a CMY(K) pracuji pouze s barevnymi odstiny (H, hue), nikoli jiz s dalsimi barevnymi informacemi, jako je sytost barvy (S, saturation) a jeji jas (V, value). Barevny ton obsahuje pouze informace o spektralnim slozeni dane barvy, sytost pak informace o primesich cerne a bile barvy a jas informace o primesi bezbarveho svetla.

Tento nedostatek modelu RGB a CMY odstranuji modely HSV (ton, sytost, jas) a HLS (ton, svetlost, sytost).

V modelu HSV jsou barvy rozlozeny v pravidelnem sestibokem jehlanu. Vrcholy podstavy jehlanu odpovidaji jednotlivym sesti zakladnim barvam (RYGCBM -- cervena, zluta, zelena, tyrkysova, modra, fialova). V techto bodech jsou barvy zcela syte a jasne. Body na postave jehlanu jsou jasne barvy vznikle kombinaci jednotlivych zakladnich barev. Ve stredu podstavy jehlanu se nachazi kombinace vsech zakladnich barev, tedy barva bila. Smerem k vrcholu jehlanu klesa jas a tim i schopnost rozlisit jednotlive spektralni barvy (jehlan se zuzuje). Ve vrcholu jehlanu je jas roven 0, coz odpovida barve cerne. Kolmice spustena z tohoto vrcholu na podstavu odpovida jednotlivym odstinum sedi.

Model HSV vykazuje jiste nedostatky, ktere castecne odstranuje dalsi model nazyvany HLS. Barvy zde tvori spojeny dvoukuzel. Na obvodu podstavy se nachazi zakladni barvy (RYGCMB s plnou sytosti a prumernym jasem. Smerem k jednomu vrcholu jehlanu klesa jas a ve vrcholu se pak nachazi barva cerna. Smerem k druhemu vrcholu naopak jas stoupa, tim tez klesa moznost rozliseni jednotlivych spektralnich barev a ve vrcholu se nachazi barva bila. Ve stredu dvoukuzeli se nachazi smes vsech zakladnich barev s nulovou sytosti a prumernym jasem, tedy barva seda.

Polotonovani

V cernobile bitmape lze jednotlive stupne sedi vyjadrit hodnotou z daneho intervalu (napriklad <0,15>), ktera odpovida stupnici mezi barvou bilou a sedou. Pro zobrazeni cernobile kresby se vsak obvykle pouziva rastrove zarizeni, jehoz pixely mohou nabyvat pouze dvou hodnot (cerna/bila). Polotonovani je metoda, jak za cenu snizeni rozliseni kresby zobrazit kresbu ve stupnich sedi.

Namisto jednoho pixelu bude jednomu policku tvoricimu matici bitmapy odpovidat skupina pixelu. Tato skupina obsahuje minimalne tolik pixelu, kolik stupnu sedi chceme zobrazit. Napriklad pro stupnici 16ti odstinu sedi vystacime s metapixelem velikosti 4x4 pixelu. V tomto metapixelu rozsvitime vzdy tolik pixelu bilou barvou, kolik odpovida danemu stupni sedi. Pixely, ktere budou v ramci matapixelu rozsviceny je nejlepe vybirat nahodne, aby nedochazelo k nezadoucim optickym jevum.

Komprese rastroveho obrazu - Metoda Run Length

Rastrove obrazy (cernobile i barevne) obvykle pri kvalitnim rozliseni vyzaduji uchovani velkeho mnozstvi dat. V rade pripadu vsak obrazy obsahuji velke jednobarevne nebo skoro jednobarevne plochy, u kterych by bylo mozne mnozstvi dat velmi radikalne snizit, aniz by doslo ke ztrate kvality obrazu. Jednou z jednoduchych metod, jak takovou kompresi dat provadet je metoda Run Length (RLM).

V metode RLM se postupuje po radkach jednotlivych pixelu. Pokud nejaky radek obsahuje usek dvou a vice pixelu stejne barvy, lze tento usek nahradit poctem opakovani teto stejne hodnoty a pak pouze jednou uvedenou hodnotou konkretni barvy. Pro obrazky obsahujici velke jednobarevne plochy se tak velikost uchovavanych dat velmi zmensi.

Priklad:
Nasledujici cernobila bitmapa velikosti 8x8 obsahuje kresbu znaku L:
11 0 000 00
11 0 000 00
11 0 000 00
11 0 000 00
11 0 000 00
11 0 000 00
11 1 111 11
11 1 111 11

Ve vyjadreni obycejnou bitmapou budeme potrebovat 64 bitu. Pri kodovani metodou RLM dostaneme nasledujici zapis:

2x1 6x0 2x1 6x0 2x1 6x0 2x1 6x0 2x1 6x0 2x1 6x0 16x1.
Misto, ktere takto zakodovany zapis zabere zavisi na zpusobu kodovani cislovek, bude vsak pravdepodobne mensi nez vyse uvedenych 64 bitu.

Kompresni metody zalozene na slovniku - LZV

Kompresni metody zalozene na slovniku vyuzivaji casto se opakujici posloupnosti dat. Tyto posloupnosti dat jsou ulozeny do tzv. slovniku a jsou oznaceny jednim identifikatorem. Tento identifikator je pak v datech pouzit namisto dane posloupnosti dat.

Metody zalozene na slovniku lze s uspechem pouzit i pro komprimaci souboru obsahujicich jina data nez rastrove obrazky, napriklad pro textove dokumenty. Jednou z metod zalozenych na slovniku je metoda LZV, kterou pouzivaji zname kompresni programy arj a pkzip.

Priklad:
U vyse uvedeneho obrazku litery L se celkem 6x opakuje posloupnost 11000000. Bylo by tedy vhodne tuto posloupnost ulozit do slovniku a pracovat s ni, jako s jednim bitem. Vysledny kod popisujici obrazek by pak pri tomto kodovani a naslednem pouziti metody RLM vypadal takto:
A = 2x1 6x0; 6xA 12x1.

Kompresni metody se ztratou informace - JPG

Vyse uvedene kompresni metody jsou vhodne pro obrazky obsahujici velke stejnobarevne plochy. U obrazku pouzivajicich mnoho barev (napriklad ve fotografii) se vsak casto objevuji spojite barevne prechody, ktere lze vyse uvedenymi zpusoby obtizne kodovat.

takove barevne prechody lze vsak zakodovat metodami, pri kterych se sice cast informaci o barvach ztrati, ale vysledna ztrata kvality obrazku po zakodovani a opetnem rozkodovani je natolik mala, ze je obvykle lidskym okem obtizne postrehnutelna nebo uplne nepostrehnutelna. Kompresnim metodam, ktere takove kodovani pouzivaji,rikame kompresni metody se ztratou informace.

Nejjednodussi kompresni metodou se ztratou informace je metoda linearni transformace. Pokud na nejakem useku obrazku dochazi ke spojitemu prechodu mezi dvema barvami, ktery probiha priblizne linearne (ve smyslu usecky v prostoru RGB), lze tento usek obrazku nahradit pouze informaci o barvach dvou krajnich bodu usecky a o linearnim prubehu zmeny barev. U slozitejsich metod lze popsat i jine zmeny barev nez linearni.

U kompresnich metod se ztratou informace lze obvykle volit kompresni pomer, na kterem pak (neprimo) zavisi kvalita zakodovani obrazku. Pri vhodne zvolene kompresni metode a kompresnim pomeru muze byt efektivita zakodovani barevnych obrazku velmi vysoka i pri zachovani temer uplne kvality obrazku.

Ztratove metody komprese najdou uplatneni predevsim tak, kde je nutne vyrazne omezit mnozstvi dat popisujicich obrazek. Prikladem muze byt prenaseni obrazku po siti, napriklad ve forme WWW stranek obsahujicich graficke prvky.

Kvadrantovy strom

Kvadrantovy strom (4-tree) je dalsi metodou, ktera umozni efektivne zakodovat dvourozmerne, predevsim cernobile obrazky obsahujici velke stejnobarevne plochy.

Cely obrazek lze rozdelit na 4 kvadranty. Pokud nektery z kvadrantu obsahuje jiz pouze jednobarevnou plochu, bude cely zakodovan jednou cislici, popisujici jeho barvu. Pokud kvadrant obsahuje vice barev, bude dale rozdelen 4 mensi kvadranty. Toto deleni pokracuje tak dlouho, dokud nebude dosazeno pouze jednobarevnych ploch (k tomu dojde nejpozdeji na urovni jednotlivych pixelu). Deleni lze tez zastavit pokud bude dosazeno nejake predem dane presnosti zobrazeni. Barvu jednotlivych kvadrantu, ktere obsahuji vice nez jeden pixel pak lze ziskat napriklad jako prevladajici barvu v teto skupine pixelu, nebo jako vektorovy prumer barev techto pixelu (v prostoru RGB).

Priklad:
Vyse uvedeny obrazek litery L lze zakodovat pomoci metody 4-tree. Po prvnim deleni na kvadranty velikosti 4x4 bude pravy horni kvadrant jednobarevny (0), ostatni kvadranty bude treba dale delit. Na druhe urovni deleni bude dosazeno jednobarevnych kvadrantu. Vysledny kod obrazku bude tedy nasledujici:
((1010)0(1011)(0011)).
Metoda 4-tree ma i dalsi modifikace. Delici cary mezi kvadranty nemusi probihat jen na souradnicich danych prumerem maximalni a minimalni x-ove (resp. y-ove) souradnice, ale napriklad tez na souradnicich, kdy nalevo a napravo od delici cary zustane stejne mnozstvi cernych pixelu. Pri deleni lze tez postupovat vzdy pouze podle jedne z os souradnic.

Kvadrantove stromy maji vyuziti nejen pri kodovani rastrovych obrazku, ale i pri uchovani a kodovani jakychkoliv dat majicich vicerozmerny charakter (prikladem mohou byt datove sklady).

Priklady rastrovych formatu

BMP (Bitmapa)
Klasicka bitmapa bez pouziti kompresnich algoritmu pouzivana predevsim jednoduchymi programy z prostredi MS Windows. Je vhodne ji pouzit pouze pro male a jednoduche obrazky.
PCX (Picture Exchange)
PCX je jeden z nejstarsich grafickych formatu pro rastrova data, ktery je dodnes velmi rozsiren. V puvodni verzi byl urcen pro cernobila data, nebo data obsahujici 16 barev, v novejsich verzich lze pouzit az 24 bitu pro zakodovani barvy jednoho pixelu (2^24 = 10^15 barev). PCX pouziva klasickou kompresni metodu RLM, ktera objem dat snizuje vyrazne pouze u obrazku s velkymi jednobarevnymi plochami. Jeji dekodovani je vsak velmi rychle.
GIF (Graphics Interchange Format)
Format GIF pouziva pro kompresi dat metodu LZV pouzivajici slovnik. Data se ukladaji po radcich podobne jako ve formatech BMP a PCX, lze vsak tez volitelne pouzit prokladani radku (napriklad nejprve sude a pak liche radky). Prokladani radku lze vyhodne pouzit pri zobrazovani na monitoru pocitace, ktery tez pracuje s prokladanym zobrazovanim radku. Soucasti dat muze byt i text obsahujici jednoduchy komentar k danemu obrazku. Format GIF je jednim ze standardu, ktery pro prenos obrazku pouziva sluzba WWW.
TGA (Targa)
Format TGA je jakymsi zobecnenim stareho formatu PCX. Lze jej pouzit bez komprese, nebo s kompresi RLM. Moznosti kodovani barev jsou bohatsi nez u formatu PCX a lze je zapsat do hlavicky souboru.
JPG (Join Photographic Experts Group)
JPG je format pozivajici ztratovou kompresi JPEG. Format je vhodny hlavne pro kodovani barevnych obrazku se spojitymi prechody mezi barvami. Takove obrazky jsou typicky barevne fotografie. Format JPG umoznuje plnobarevne obrazky komprimovat podstatne vice nez bezztratove kompresni formaty PCX a GIF. Pouziva se tez jako standard pro prenos obrazku sluzbou WWW.
TIFF (Tag Image File Format)
TIFF je velmi obecny graficky format umoznujici ukladat obrazky v ruznych barevnych kodovani a zakodovane ruznymi kompresemi. Tyto komprese mohou byt bezztratove (RLM, LZW) i ztratove (JPEG). Jeden soubor muze obsahovat i vice obrazku vcetne jejich jednoduchych komentaru. Nevyhodou formatu je jeho velka obecnost, ktera se projevuje velkymi naroky na program, ktery ma obrazek ve formatu TIFF zpracovavat.

Vektorove datove formaty

Vektorove datove formaty popisuji kresbu nikoli na zaklade jejiho vzhledu, ale na zaklade existence entit. Entitou v nejjednodussim smyslu rozumime geometricky prvek (usecka, kruznice, krivka) spolu s metodou pro jeji konstruovani.

SLozitejsi vektorove formaty obsahuji krome samotnych geometrickych prvku i dalsi informace. Temi mohou byt napriklad barva cary, typ cary, odkaz do baze dat, kde je popsany vyznam daneho prvky a podobne.

Vektorove datove formaty nelze obvykle primo zobrazovat na vystupnim zarizeni pocitace (s vyjimkou perovych plotru). Pred jejich vykreslenim je tedy nutno provest prevod to formatu rastroveho, tzv. rastraci. Kvalita kresby pak zalezi na kvalite teto rastrace. Rada programu pouziva pro jednoduche pracovni vykresleni kresby jednoduche a rychle rastracni algoritmy a pro kvalitni zaverecne vykresleni pak algorimty dokonalejsi a pomalejsi.

Jednim z jednoduchych vektorovych formatu je format HPGL (Hewlet Packard Graphic Language). Tento format obsahuje v textove podobe informace o geometrii jednotlivych entit. Rada plotru obsahuje primo hardwarove zabudovany interpret tohoto formatu.

Neoficialnim standardem ve vektorovych formatech pro CAD systemy je format DXF (Drawing Exchange Format) pouzivany puvodne programem AutoCAD. Tento format obsahuje krome samotne geometrie prvku i dalsi informace pouzivane CAD systemy.

Sve vlastni vektorove formaty ma vetsina CAD systemu, stejne tak jako programy pro digitalni model terenu, geograficke informacni systemy a dalsi programy pracujici s grafickou informaci. Ve slozitejsich datovych formatech je casto vlastni graficka informace (geometrie entit) pouze nepatrnou casti uchovavanych dat.

Mezi vektorove graficke formaty lze tez radit format PostScript (EPS). PostScript slouzi pro popis obecneho textoveho dokumentu. Obsahuje informace o poloze jednotlivych znaku (pismen, dalsich znaku a grafickych symbolu) na listu papiru a o jejich vlastnostech (pouzitem fontu, velikosti pisma atd.). PostSript lze opet primo interpretovat hardwarem mnoha tiskaren.

Vektorizace

Vektorizaci rozumime prevod dat z rastroveho formatu do formatu vektoroveho. Jedna se o ulohu obtiznou, nebot informaci ulozenych v rastrovem formatu je mene, nez informaci ulozenych ve formatu vektorovem, a tak je potreba nove informace automaticky generovat, nebo je rucne do dat doplnit. Typicky je vektorizace provadena po naskenovani papiroveho dokumentu. Naskenovanim dokumentu vznikne rastrovy obrazek, ktery je casto nutne pro dalsi praci prevest do vektorove podoby. Vektorizace muze byt:

Specialnim pripadem vektorizace je proces OCR (Optical Character Recognizing), tedy rozpoznavani pisma. Pri tomto procesu je ze vstupniho rastroveho souboru obsahujiciho obrazek textu generovan textovy soubor.

Rastrace

Rastrace je proces opacny k vektorizaci, tedy prevod formatu vektoroveho na rastrovy. Narozdil od vektorizace lze rastraci provadet podle presnych algoritmu, ktere nevyzaduji zasah uzivatele.

Hlavnim problemem rastracnich algoritmu je jejich rychlost. Vzhledem k tomu, ze vetsina vystupnich zarizeni pocitace pracuje v rastrovem rezimu a vetsina dat alespon pri praci s vyssimi grafickymi programy (napriklad CAD systemy) je ulozena ve formatech vektorovych, je rastraci vektorovych entit potreba provadet casto a velmi rychle.

Algoritmus DDA

DDA (Digital Differential Analyzer) je zakladni algoritmus slouzici pro rastraci usecky. Vetsina entit vektorovych datovych formatu je pri vykreslovani prevedena na soustavu usecek, ktere se pote pred vykreslenim na vystupni zarizeni rastruji. Z toho plyne potreba existence velmi rychleho a kvalitniho algoritmu pro rastraci usecky.

Algoritmus DDA ma dve soumerne varianty pro usecky se smernici mezi 0 a 1 a pro usecky se smernici mezi 1 a nekonecnem. Popiseme si prvni variantu tohoto algoritmu.

Na zaklade znalosti koncovych bodu usecky (x1,y1) a (x2,y2) se urci smernice usecky m a jeji prevracena hodnota 1/m. Na zacatku je vykreslen pixel na souradnicich (zaokrouhlene x1, zaokrouhlene x2). Nasleduje 1/m pixelu se stejnou souradnici y a souradnici x postupne se zvetsujici o 1. Pote se zvetsi souradnice y o 1 a postupuje se stejnym zpusobem dale. Vyhodou je velka rychlost tohoto algoritmu, nebot krome pocatecniho urceni smernice usecky neni potreba provadet zadne dalsi matematicke operace, pouze zvetsovani hodnot promennych o 1.

Usecku (i jine entity) lze rastrovat dvema zpusoby -- jako tzv. 8-spojitou, nebo jako tzv. 4-spojitou caru. V pripade 8-spojite cary lezi dva sousedni pixely tvorici entitu vedle sebe ve smeru vodorovnem, svislem, nebo sikmem. V pripade 4-spojite cary musi lezet dva sousedni pixely ve smeru vodorovnem nebo svislem. 8-spojita cara oddeluje dve 4-spojite oblasti, naopak 4-spojita cara oddeluje dve 8-spojite oblasti. V praxi se vetsinou pouzivaji cary 8-spojite (a tedy oblasti 4-spojite).

Algoritmus DDA ma radu variant, ktere umoznuji jeho jeste rychlejsi a presnejsi fungovani. Existuji tez modifikace algoritmu DDA pro krivky zadane kvadratickymi predpisy, napriklad pro kruznici.

Interpolacni krivky

Nejjednodussi interpolaci posloupnosti bodu je jejich prolozeni lomenou carou. Vyjadreni lomene cary jako posloupnosti usecek je velice jednoduche a jeji vypocet ze zadanych souradnic bodu take. Interpolacni krivka vsak nema spojitou ani prvni derivaci (ma "ostre zmeny smeru").

Druhou casto pouzivanou metodou pro interpolaci je interpolace polynomem. Mame-li zadano n-bodu, muzeme sestavit polynom (n-1) stupne, ktery bude prochazet vsemi zadanymi body. Polynom ziskame snadno, staci nam napsat si formalne jeho tvar, dosadit do nej hodnoty n namerenych bodu a pak vyresit soustavu n rovnic o n neznamych. Krivka popsana takovym polynomem bude mit spojite vsechny derivace a bude tedy hladka. Pri vetsim poctu bodu nam timto zpusobem ovsem vznikne polynom velmi vysokeho stupne a manipulace s nim bude velmi narocna. Navic krivka vznikla interpolaci polynomem je sice dokonale hladka, ma vsak casto "vykyvy" vetsi, nez by se na prvni pohled zdalo byt z polohy bodu nutne. Proto je interpolaci polynomem vhodne pouzivat jen pri prokladani maleho poctu bodu.

Spline krivky

Asi nejcasteji pouzivanou metodou pro interpolaci posloupnosti bodu je metoda tzv. spline funkci, se kterou jsme se jiz tez setkali. Posloupnost bodu se rozdeli na kratsi useky. Takovy usek muze obsahovat napriklad tri body. V kazdem tomto useku se body interpoluji polynomem nizkeho stupne, v nasem pripade polynomem stupne druheho. Pote se na rozhrani useku polynomy na sebe dostatecne hladce navazi. Hladkost navazani zavisi na tom, jak dlouhe useky bodu si budu brat. Budu-li brat useky obsahujici tri body a prokladat je parabolou (tedy polynomem druheho stupne), budu schopen v bodech navazani zarucit spojitost prvni derivace. Cim vice bodu bude obsazeno v jednotlivych usecich, tim bude spline krivka hladsi - bude mit vice spojitych derivaci - a tim bude jeji vypocet slozitejsi. Podle stupne dilcich polynomu rozeznavame kvadraticke, kubicke a dalsi spline krivky. Interpolace lomenou carou je vlastne interpolaci pomoci linearni spline krivky.

Aproximacni krivky

Jak jsme si jiz uvedomili,casto netrvame na tom, aby vsechny body ze zadane posloupnosti nutne lezely na jimi prokladane krivce. Staci nam, kdyz krivka povede "neprilis daleko" od nich a kdyz bude "kopirovat tvar" zadany pomoci posloupnosti bodu. V takovem pripade hovorime o aproximaci posloupnosti bodu.

Jednou z aproximacnich metod je metoda nejmensich ctvercu. Pri teto metode aproximujeme posloupnost bodu polynomickou krivkou nizsiho stupne, nez jaky by byl potreba pro jejich interpolaci. Aproximacni krivka pak ma spojite derivace vsech radu, je hladka a pritom je tak jednoducha, jak si predepiseme. Jako kriterium pro kvalitu aproximace se bere soucet druhych mocnin vzdalenosti vsech prokladanych bodu od aproximacni krivky (odtud nazev metody).

Polynom aproximujici posloupnost bodu metodou nejmensich ctvercu lze opet ziskat pomoci reseni vhodne soustavy linearnich rovnic. Jeji velikost je dana stupnem aproximacniho polynomu. Na obrazku vidite krivku tretiho stupne, ktera aproximuje posloupnost 7 bodu metodou nejmensich ctvercu.

Bezierova aproximace

Zajimavou a v oblasti pocitacove grafiky casto pouzivanou metodou aproximace jsou Bezierovy krivky. Bezierova krivka aproximujici posloupnost bodu x0,x1,...,xn ma nasledujici vlastnosti:

Bezierova krivka n-teho stupne je urcena n plus 1 ridicimi body a parametricky muze byt popsana polynomem stupne n.

Zjednodusene se da rici, ze Bezierova krivka nema velke "vykyvy" a posunuti jednoho ridiciho bodu nejakym smerem "vytahne" oblouk krivky timto smerem. Proto je Bezierova krivka vhodna i pro laicke kresleni zakrivenych car a casto se take k tomuto ucelu v ruznych kreslicich programech pouziva.

Nejcasteji se pouzivaji Bezierovy krivky se tremi a ctyrmi ridicimi body. V prvnim pripade je krivka usekem paraboly. Tecny v obou jejich krajnich bodech prochazeji tretim ridicim bodem.

V pripade ctyr ridicich bodu mame zadan pocatecni a koncovy bod a smer tecen v obou techto bodech. Grafem Bezierovy krivky je pak usek kubicke paraboly.

Bezierovy krivky vyssich radu se jiz obvykle nepouzivaji, nebot manipulace s nimi je prilis slozita. Casteji se pouziva metoda podobna metode spline funkci. Posloupnost bodu se rozdeli na useky, ktere se aproximuji Bezierovou krivkou nizsiho stupne. V hranicnich bodech se pak krivky "dostatecne hladce" na sebe navazi. Vysledkem je funkce, ktera sice nema spojite derivace vsech radu, manipulace s ni je vsak podstatne jednodussi.

Tomas Vanicek, Katedra inzenyrske informatiky, Stavebni fakulta , CVUT Praha.