Michal Klodner
INFORMATICKÉ STRUKTURY VIZUÁLNÍ KOMUNIKACE
VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ FAKULTA ELEKTROTECHNIKY A INFORMATIKY Ústav informatiky a výpočetní techniky Technická zpráva diplomové práce
INFORMATICKÉ STRUKTURY VIZUÁLNÍ KOMUNIKACE
Michal Klodner 9.6.1999
Shrnutí: Pro potřeby vizuální komunikace budeme hledat strukturální popis obrazu, který je symbolický a tudíž nezávislý na fyzických vlastnostech média. Takový popis je vhodný ke zpracování známými metodami pro symbolické zpracování informací. Když jsou tyto symboly dvourozměrné, lze pro popis jejich obrysu použít jednoduché řetězcové gramatiky. Pro složitější popisy konfigurace ploch využijeme gramatiky stromové a největší pozornost věnujeme grafovým gramatikám, které jsou pro popis obrazu nejvýhodnější a mají největší vyjadřovací schopnosti. Již od počátku je důležité vidět popis obrazů s ohledem na časový rozměr. Statický popis nám často neposkytne dostatečné informace. Proto je třeba znát struktury videografického časoprostoru a při komunikaci využívat informace o tom, jak obraz vznikl. Pozornost bude též věnována vizuální složitosti obrazu a problému získávání gramatiky obrazů. Klíčová slova: Vizuální komunikace, Vizuální symbol, Reprezentace symbolu, Popis obrazu, Struktura obrazu, Vizuální struktury, Struktura videa, Videografický časoprostor, Gramatika obrazu, Obrysová gramatika, PDL, Stromová gramatika, Grafová gramatika, Informační estetika, Fraktální dimenze, Inference gramatik, Syntaktická analýza grafových gramatik, Ornament, Grupa symetrie, Komunikace a komplexita, Znakový proces, Vizuální vnímání, Vznikající formy Prohlášení: Prohlašuji, že jsem semestrální projekt vypracoval samostatně pod vedením prof. Ivo Serby a že jsem uvedl všechny literární prameny, ze kterých jsem čerpal poznatky.
Rozsah: 150 normostran, 45 obrazů, 2 tabulky v Brně, 9. června 1999
Poděkování: Na tomto místě bych rád poděkoval všem, kdo mi při vzniku této práce pomohli, nebo mi její tvorbu zpříjemnili, zejména prof. Ivo Serbovi, PhDr. Jaroslavu Vančátovi, B.A. Keiko Sei a ak. mal. Lucii Svobodové
Obsah
1.
Úvod
5
2. 2.1. 2.2. 2.3. 2.4. 2.5.
Symbol a realita Znak, symbol a znakový proces Biologické chápání symbolu Psychologické chápání symbolu Vizuální symbolické struktury Symbolické struktury a komunikace
7 7 8 11 13 14
3. 3.1. 3.2. 3.3. 3.4. 3.5.
Struktury obrazu Vlastnosti obrazových struktur Popis obrazu a lineární gramatiky Popis obrazu a stromové gramatiky Popis obrazu a grafové gramatiky Složitost a entropie
17 17 19 22 23 27
4. 4.1. 4.2. 4.3.
Vizuální komunikace Vlastnosti videografických struktur Teorie komunikace Inference gramatik
31 31 38 41
5.
Závěr
43
Dodatek A. Počítačové zpracování ornamentálních vzorů A.1. Algoritmus A.2. Grupy symetrie
47 47 48
Dodatek B. Syntaktická analýza grafových gramatik B.1. Úvod do grafových gramatik B.2. Algoritmus pro syntaktickou analýzu B.3. Shrnutí
67 67 71 77
Dodatek C. Obsah přiloženého CD-ROM C.1. WWW prezentace C.2. Maya Imagination C.3. Studijní materiál
79 79 79 81
Literatura
83
1. Úvod
Počítače byly vynalezeny proto, aby počítaly s čísly. A aby počítaly rychleji a přesněji než člověk. Později se však k velkému překvapení zjistilo, že počítače mohou také manipulovat se znaky a v tom dnes spočívá jejich obrovský význam. Aplikace počítačů na znakové operace se ovšem odvíjely z představy lineární konstrukce jazyka. Důraz na zpracování textu a popis jeho gramatiky v minulosti přirozeně plynul z používání jednorozměrných „dálnopisných“ médií., Dnes se do popředí zájmu dostávají vizuální informace a musíme připustit, že toho o znakové a symbolické struktuře obrazu víme velmi málo. Víme dobře, jak komunikovat textově, ale nemáme ponětí, jak komunikovat vizuálně. Ptejme se spolu s Vilémem Flusserem: Má písmo budoucnost? Jaké jsou kódy budoucnosti? Jak se lze naučit vizuálně myslet? Tradiční literární vzdělání svou linearitou, postupností a historičností nestačí k chápání přirozené multidimenziality, rekurzivity a fraktálnosti obrazů. K tomu potřebujeme mediální gramotnost a schopnosti okamžitého, celostního chápání komplexních struktur. Informace získávané dnes vícerozměrnými vstupy můžeme popsat novými, multidimenziálními symboly a strukturami. Posloupnost je vystřídána simultánností, místo linearity se orientujeme na hloubku, strukturu a vzájemný vztah. Budeme hledat smysluplné vyjádření významu obrazu. Využijeme poznatků lingvistiky a převedeme je na pole grafického designu. Grafický design je multi-kriteriální, multi-disciplinární, multi-personální aktivita, která integruje celé spektrum profesionálních zájmů a komunikace v něm hraje klíčovou roli. Jedním z hlavních aspektů je, že jednotkou této komunikace je obraz. Kolaborativní design se stává důležitým paradigmatem nové generace inteligentních systémů počítačově podporovaného návrhu. Tyto nástroje byly dosud tvořeny pro jediného návrháře, pracujícího samostatně. Design ovšem takto nefunguje. V tomto oboru se setkává mnoho různých zájmů a kritérií, z nichž pomocí výpočetního média vzniká výsledný návrh. Obecným postupem bylo rozdělit úlohu na menší nezávislé části, reprezentující individuální úkoly, které jsou schopny navázání spolupráce. Design je komunikační aktivita, v níž jsou jednotlivci vyzváni, aby dešifrovali svět jeden druhého. První konceptuální řešení ve skupině mohou být založena právě na takovémto dešifrování. Je třeba pokročilých komunikačních prostředků, které přesahují obvyklé pasivní transformace dat a zpráv. Technologie otevřela nové cesty interakce v několika procesech: spolupráce mezi designéry, mezi designéry a systémy pro počítačovou podporu designu, mezi designéry, systémy pro počítačovou podporu designu a znalostně založenými systémy (např. vizuálními databázemi) a mezi znalostními systémy navzájem. V tomto prostředí je jednotkou komunikace mezi designéry přenos zprávy (obrazu) od jednoho (odesílatele) k druhému (příjemce), jejímž účelem je poskytnout příjemci určité informace nebo mu dát vědět o akcích, které má vykonat. Reference tohoto aktu komunikace je v daném obrazu, který
5
Úvod má jeden význam pro odesílatele a pravděpodobně jiný pro příjemce. Budeme se tedy zabývat komunikací a jejími mechanismy, za účelem odhalení prvků, které tvoří základ vzájemného porozumění. Ne vždy máme pro každý prvek obrazu definován jeho význam, z něhož by mohly obě strany při komunikaci vycházet. Někdy jej ani nelze získat, protože forma, k níž by měl význam náležet, teprve vzniká, jak tomu bývá při kreativní práci. Takováto vznikající forma je implicitní struktura, vyplývající z jiné, explicitní struktury a není jednoduše záležitostí rozpoznání vzoru, ale definice vzoru designérem během řešení problému. Je to základní schéma výpočetních modelů pro kreativní myšlení. Obraz obsahuje vznikající formy, jestliže jsou jeho části nebo vlastnosti spojeny tak neočekávaným způsobem, že dávají vzniknout novým tvarům a vztahům, které nebyly vytvořeny záměrně. Vizuální komunikace má charakter měkkého jazyka a musí být schopna tyto těžko definovatelné symbolické struktury zpracovat, stejně jako formy s pevně definovaným významem. Klíčovým konceptem, který podporuje vznikající formy, je strukturální popis asociovaný s obrazem. Tento strukturální popis je specifikován svým obsahem, tj. primitivními tvary, ze kterých se skládá, a svým uspořádáním, tedy prostorovými relacemi mezi těmito elementy. Komunikace je motorem vývoje. Radikálně nové komunikační nástroje vždy vedly k novým érám a novým hodnotovým systémům. Složitost mnoha problémů lidstva, přírody a strojů leží ve složitosti v nich obsažených komunikačních problémů. V mnoha případech stačí velmi málo komunikace, abychom dosáhli všeho, co potřebujeme.
6
2. Symbol a realita
Tato kapitola bude věnována víceméně netechnickému přehledu několika vědních oborů, které se zabývají rozhodujícími oblastmi vizuální komunikace. Přenosem informace na bázi znaků a znakových soustav, ať už literárních, nebo vizuálních, je věnována pozornost hlavně při analýze dvou druhů společenských činností. Komunikačních procesů a kognitivních procesů. Tyto procesy jsou velice těsně spjaty, vzájemně se prostupují a navazují na sebe. Vědou o znacích je sémiotika. Jejím zakladatelem je americký logik Charles S. Pierce. Studuje všechny znakové systémy, které kdy člověk vytvořil, a to v ideálním případě nezávisle na lingvistickém modelu. Sémiotika se zabývá především zkoumáním vztahů mezi znaky a symboly. Sémantika je část sémiotiky zabývající se funkcí znaků a jejich významem. Všimneme si též biologického původu znaku, resp. symbolu a jejich psychologického pojetí, a budeme analyzovat, jaká je jejich povaha, jaká je povaha obrazů, které tvoří a jaké prostředky budou nejvhodnější k jejich informatickému vyjádření.
2.1. Znak, symbol a znakový proces Základním sémiotickým pojmem je znak. Znak může znamenat jakoukoli vlastnost objektu, činnosti apod, je zkrátka nositelem vjemu. Peirce [1] zavedl pojem znakového procesu, (sémiosis, bude podrobněji popsán dále), který chápal jako triadickou relaci znaku, objektu a interpretanta. Jakýkoli předmět, vlastnost předmětu, událost atd. se může stát znakem libovolného objektu, můželi být někým interpretován, tedy existuje-li interpretans. V rámci znaků budeme rozlišovat i další pojmy, jako ikona, index a symbol. Ikona se vyznačuje smyslovou podobností k objektu. Vztah znaku a označovaného objektu je zřejmý na základě smyslové podobnosti, ikonické znaky tedy reprezentují materiální, smyslově postižitelné objekty. Je-li znak indexem, můžeme ho považovat za fragment odtržený od objektu, přičemž oba tvoří jeden celek. Neznáme-li přesnou interpretaci znaku, nebo nevíme, co přesně znak označuje, hovoříme o symbolu. Pro symbol je charakteristická vždy jistá iracionálnost, protože stane-li se cele vědomým, hovoříme o znaku. V oblasti vizuální komunikace jde zejména o symboly, protže se snažíme popsat těžko postižitelnou informaci. Grafický symbol je symbol, který má grafickou formu v podobě linie, plochy nebo systému grafických stop. Grafickou (zejména dvourozměrnou) podobu každého významově nespecifikovaného symbolu nazýváme grafémou. Grafémy mohou mít podobu geometrických obrazců nebo nabývat v různém stupni „obrazové“ kvality více nebo méně stylizovaných nebo naturalizovaných obrázků. Již ve vizuální podobě symbolu může být obsažen časový prvek. Rytmus lze symbolizovat kružnicí, otáčející se kvalitou, anebo střídajícími se opačnými hodnotami. (V podstatě jde o vlnovku, sinusoidu, jejímž jedním cyklem je právě kružnice. Vlnovka je jednou z nejstarších podob ornamentálního motivu a náleží mezi grafémy.)
7
Symbol a realita
z2
z
Obr 2.1. Grafy funkce z2: parabola a její iterace v čase Mandelbrotova množina
Ch. Morris rozlišuje pět komponent znakového procesu: 1. 2. 3. 4. 5.
znak objekt, k němuž se znak vztahuje (designatum) interpret interpretans, tj. reakce interpreta či dispozice interpreta reagovat na daný znak kontext, ve kterém se znak vyskytuje
Jako znak může sloužit jakýkoli předmět nebo událost, který je schopen mít v komunikačním procesu funkci přenosu informace, tj. který může být interpretován. Interpretací znaku pak rozumíme proces, který interpretu umožňuje na základě znaku se rozhodovat o objektech, k nimž je znak přiřazován. Obvykle říkáme, že znak má pro interpreta určitý význam. Znak tedy musí mít tyto vlastnosti: • sdělitelnost (komunikovatelnost), tj. schopnost přenášet informace v čase a prostoru • interpretovatelnost Znak je vnímán, registrován a rozlišován vždy jako celek, jakožto prvek určité třídy znaků. Při znakovém procesu je vždy vnímána určitá znaková událost, která je interpretována na základě příslušnosti této události k určité znakové třídě. Z těchto důvodů je účelné rozlišit znak jakožto znakovou událost a znak v abstraktním smyslu. Proto byly zavedeny pojmy token a type, kde token má význam znaku v konkrétním smyslu a type má úlohu symbolu, tj. vyjadřuje abstraktní smysl.
2.2. Biologické chápání symbolu Behavioristická psychologie popisuje působení znaku následujícím způsobem: Pro organismus O je jakýkoli prvek třídy stimulů A znakem nějakého prvku třídy B, jestliže prožitek tohoto stimulu u organismu O vyvolává reakci, která odpovídá prvku třídy B. Toto schéma je blízké koncepci podmíněného reflexu. Mechanismus podmíněného reflexu je patrně také fyziologickou bází toho, co Pierce a Morris nazývají znakovým procesem či sémiosis. Toto pojetí znaku je velmi široké a lze je vztahovat na jakoukoli reakci organismu (nebo kybernetického zařízení, které modeluje chování organismu), která má charakter podmíněného reflexu. Proto je účelné odlišit znakové procesy v širším slova smyslu a znakové procesy spjaté se společenskou komunikací. Reakce psa na zvonek ve známém Pavlovově experimentu je znakovým
8
Biologické chápání symbolu procesem, který není spjat se společenskou komunikací a jeho základní komponenty nejsou společensky podmíněny, nevystupují zde vlastní znaky, které jsou společenským výtvorem a které jsou teprve potom interpretovány jako znak něčeho, ale přirozené znaky. Abychom mohli dobře pochopit vizuální symbol, popíšeme v následujícím textu biologické základy vnímání vizuální informace. Tento exkurs do biologie a neurologie je třeba chápat pouze jako stručné nastínění povahy těchto procesů a proto možná nebudou dokonale vysvětleny všechny pojmy. Podrobnější informace lze nalézt v příslušné literatuře, např. v [12]. Vizuální informační komplex je ze všech smyslových komplexů lidského mozku nejsložitější. Souvisí to zřejmě s tím, že zrak hraje v našem životě roli svým významem převažující roli ostatních smyslů. Celý vizuální komplex se skládá ze čtyř hlavních podsystémů: • sítnice • vizuální nervové cesty vedoucích od sítnice do thalamu a pak do cortexu • vizuální projekční oblast v cortexu identifikující tvary a pohyb • subsystém pro barevné vidění Sítnice, na níž je optickou soustavou oka promítán obraz pozorovaných předmětů nebo scén, obsahuje fotosenzitivní prvky, jimiž jsou dva druhy specializovaných neuronů. Čípky detekují tvar a barvu obrazu a působí především při jeho pozorování za denního světla. Tyčinky zajišťují noční vidění a působí za šera a za tmy, kdy čípky nedostávají dostatečně silné podněty, které by stimulovaly jejich aktivitu. Z jednotlivých částí sítnice se přenášejí vizuální signály tak, že v thalamu je vytvořen úplný obraz zorného pole. Kromě toho však některé jednotlivé axony, odpovídající týmž částem sítnice, zasahují do různých částí mozkového kmene. Předběžně zpracované vizuální signály jsou pak zobrazeny bod po bodu do celého primárního vizuálního cortexu, zde jsou pak jednotlivým úsekům sítnice vymezeny příslušné podoblasti. Primární vizuální cortex je organizován ve sloupcích, které působí jako jednotsky sdružující neurony. Ty generují výslednou vyšší složku integrální vizuální informace. Obsahují též neurony, sloužící receptorovým polím pro identifikaci lineárních útvarů a hran ve sledovaných obrazech. Jednotlivé
Obr 2.2. Řez lidským mozkem
sloupce jsou uspořádány do jakýchsi hypersloupců, obsahujících sloupce specializované na identifikaci přímkových úseků orientovaných pod různými úhly, a to v celém rozsahu 360° s odstupy asi po 10°.
9
Symbol a realita V modulu jsou i další specializované sloupce, působící při uskutečňování jiných vizuálních funkcí, které spolupracují vždy s levým či pravým okem a podílí se na uskutečnění vjemů binokulárního a prostorového vidění a s tím souvisejícího odhadování vzdáleností a h l o u b e k . V každém modulu jsou také specializované sloupce pro identifikaci barev, jež jsou tak rozmístěny pravidelně v celé Obr 2.3. Schema spojení neuronů ploše vizuálního cortexu. Jsou to tzv. cortikální hřeby, spolupracující s určitými skupinami čípků v sítnici, citlivými na jednotlivé složky dopadajícího světla. Monochromatický ani bichromatický vizuální systém nemůže zprostředkovat dostatečné rozlišení intenzity a vlnové délky. Těmto požadavkům vyhoví teprve trojbarevný systém, u člověka s pigmenty citlivými na modrou, zelenou a červenou barvu. Každý modul je tedy úplnou jednotkou pro zpracování informace v dané oblasti. Celý vizuální cortex v Brodmannově oblasti 17 má výraznou modulární strukturu. Vyšší vizuální funkce se však uskutečňují v Brodmannově oblasti 18 a v jejím okolí. Sem přicházejí výstupy z oblasti 17, v nejjednodušším případě výstupy z jednotlivých hypersloupcových modulů, mnohde jsou to však další dosti složité kombinace výstupů většího počtu takových hypersloupců. Pro složitější zpracování vizuální informace, která má charakter rozpoznávání obrazů či analýzy scény a je již vyšší formou informační činnosti mozku, jsou výstupy z těchto základních analytických vizuálních hypersloupců dále zpracovávány ve stále složitějších hierarchicky uspořádaných celcích na principu stoupající strukturální konvergence. Uchování vizuální informace zabezpečuje samozřejmě paměť. Paměť patří mezi životně nejdůležitější funkce. Sídla funkcí paměti jsou rozprostřena ve více oblastech mozku. Paměť se nachází v průběhu času v různých stavech, které se stále vyvíjejí a mění, podle doby svého působení může existovat několik druhů pamětí, přičemž dlouhodobé paměti mohou mít odraz svých stavů ve fyzických změnách mozku. Lze rozlišit tzv. reflexní a deklarativní paměť. Reflexní Obr 2.4. Schéma paměti s pracovními bloky o různé době uchování paměť se naplňuje záznamu poměrně pomalu na základě příchodu většího množství podnětů, deklarativní paměť naproti tomu schraňuje informace asociačního charakteru. Reflexní a deklarativní paměť jsou uskutečňovány v různých oblastech mozku. Podle doby uchování záznamu jsou v mozku nejméně tři různé paměťové mechanizmy, krátkodobý, střednědobý a dlouhodobý. Krátkodobý paměťový mechanizmus je založen na cyklickém oběhu vzruchů v určitých dílčích neuronových obvodech a sítích. Je známo několik takových typických oběhových drah: Oběh vzruchů mezi mezi cortexem a thalamem je vývojově nejmladší a souvisí s racionálním zpracováním informací v mozku (na EEG se projevuje vlnami alfa). Cyklus septum-hippocampus je
10
Psychologické chápání symbolu vývojově starší a souvisí s emoční aktivitou. Kromě toho pravděpodobně funguje jako pomocná paměť (na EEG se jeho aktivita projevuje theta vlnami). Vývojově nejstarší je olfactorhiencefalografický cyklus (na EEG jsou pro něj typické beta vlny), který patrně souvisí s jevem probuzení ze spánku. Vnitřní struktura cortexu je uspořádána do šesti horizontálních vrstev, Kromě toho má i vertikální členění do tzv. sloupců, obsahujících vždy asi 10000 neuronů. Je-li do takového neuronového sloupce přivedena jistá informace, začne při dostatečné úrovni excitace obíhat ve vertikálním obvodu mezi cortexem a thalamem s dobou cyklu asi 100ms. To odpovídá zapojení asi 80ti až 90ti zapojeným neuronům. Vnitřním propojením vertikálních obvodů ve sloupci se pak tato informace rozšíří postupně z daného vlákna na celý sloupec a případně i na sousední sloupce. Signál může cirkulovat až 300 krát, než začne docházet k jeho útlumu fixací do střednědobé paměti. To trvá asi 30s Za tu dobu se mohou vytvořit podmínky pro trvalejší zachycení informace, které spočívá ve změnách váhových činitelů neuronových synapsí, kterými opakovaně prochází dostatečně silný signál. Tyto změny mají již dlouhodobější charakter, může to být několik hodin až několik dnů. V období spánku se pak některé z těchto informací převádějí do pamětí dlouhodobých, což se děje jejich obtiskováním do bílkovin ve vnitřní struktuře neuronových buněk, zejména v jádrech. Toto uchování je již dlouhodobé. Přetrvává po celou dobu života organismu a pravděpodobně mohou být dědičností předávány dalším generacím. Důležitým faktem je, že při interpretaci vizuálních vjemů nedokáže lidský mozek pracovat s vjemem jako takovým, dokáže pouze porovnávat rozdíly mezi vjemy. Abychom mohli slovně popsat subjektivní vizuální poznatek, je třeba přenést informaci do výstupního stupně motoneuronů (pohybových neuronů příslušných svalových partií), kde se stane základem pro verbalizaci či jinou činnost. Při tomto procesu dochází vždy k překódování této informace. Explicitní informace na výstupu motoneuronů je tedy vztažena k explicitní informaci na výstupech neuronů asociovaných na uvažovaném hierarchickém stupni vizuálního traktu k příslušnému barevnému poznatku. Není s ní však identická. Nelze tedy k jednotlivým slovům či myšlenkám přiřadit přesnou povahu subjektivní zkušenosti. Je pouze možné porovnávat rozdíly mezi jednotlivými zkušenostmi.
2.3. Psychogické chápání symbolu Základní významové hodnoty symbolů, resp. jejich grafém, které lze považovat svým způsobem za za jakési koncentráty informace působí prostřednictvím zrakových receptorů na lidskou psýché, na hlubší vrstvy našich životních zkušeností. V tom spočívá právě význam iracionality, která je pro symbol typická. Je známou skutečností, že lidé často následují spíše působivý symbol, např. vlajku, než příliš složitou racionální myšlenku, kterou má vyjadřovat. Graféma obsahuje určité psychiku mobilizující kvality, které se dotýkají citového, intelektuálního a podvědomého světa člověka hlouběji, než se na první pohled může zdát. Moderní emblémy a loga uchvacují silou, která je často využívána v politické a ekonomické sféře k ovlivnění konzumenta. McLuhan [4] uvádí příklad: Dejme tomu, že by američané místo hvězd a pruhů vyvěšovali kus látky, na němž by bylo napsáno „Americká vlajka”. Tyto symboly by měly stejný význam, avšak jejich účinek by byl zcela odlišný. Překlad do písemné formy by vlajku do značné míry zbavil její kolektivní symboliky a zkušenosti. Kvality, jež vzrušují nebo zajímají percipienta grafémy jsou nepochybně informací, avšak co je obsahem této informace? Analýza základních typů grafém (včetně jednoduchých písem) napovídá, že v symbolické rovině navozují obdobné vjemy, jako percepce obecných přírodních zákonitostí, s nimiž se setkal člověk jako jedinec v průběhu individuálního života i celek lidského rodu v průběhu fylogenetického vývoje druhu. Tato reflexe byla nazvána symbolon a grafému přímo reflektující tyto kvality nazýváme symbolonovou grafémou.
11
Symbol a realita Obsah symbolu nelze nikdy plně vyjádřit racionálními prostředky. Zda něco symbolem je, či není, to záleží především na zaměření pozorujícího vědomí. Je docela dobře možné, že tentýž fakt nebo objekt bude pro jednoho člověka představovat symbol a pro druhého jen znak. Existují však útvary, jejichž pojetí v podobě symbolu se naléhavě a bezprostředně vnucuje každému pozorovateli. Symbol není žádnou alegorií ani znakem, nýbrž obrazem obsahu, který přesahuje vědomí. Symbol však může také degenerovat na úroveň znaku a stát se mrtvým symbolem, je-li smysl v něm ukrytý odhalen a přestává být významným, protože jej pak můžeme plně vystihnout racionálně. Pravý symbol nemůže být nikdy beze zbytku popsán, lze odkrýt jen Obr 2.5. Oblast nevědomí. Osobni nevědomí: jeho racionální podíl. Ovšem symbol I - Vzpomínky, II - Nevědomé obsahy, Kolektivní promlouvá vždy k celé psýché, k její nevědomí: III - Afekty a nálady, IV - Invazní obsahy, vědomé a současně i nevědomé části. Pro V - Díl nevědomí, který nemůže být zvědoměn Freuda jsou to obrazy libidózních energií ženské a mužské sexuality. Jung také hovoří o symbolu jako o podobě libida, protože přeměňuje energii. Symboly mají současně expresivní i impresivní charakter. Na jedné straně intrapsychické dění obrazně vyjadřují a na druhé straně toto dění svým významovým obsahem ovlivňují a tím dále pohánějí psychické procesy. Symbol tedy úzce souvisí s pojmem nevědomí. To chápe Jung ([5], [6]) jako oblast psýché člověka, kam nezasahuje jeho vědomí, která je mu nepřístupná a o které se nelze nic dozvědět. Zkoumat jej můžeme pouze zprostředkovaně pomocí jeho projevů a pomocí jevů, kterými vstupuje do vědomí. Osobní nevědomí člověka obsahuje subjektivní poznatky jedince o světě, které již ustoupily z vědomí, zážitky, které již byly zapomenuty a další údaje z individuálního života. Dalo by se o něm uvažovat jako Obr 2.6. Kolektivní nevědomí. I - Izolovaný národ, II a III - Skupiny národů, např. Evropané, A - Jedinec, o paměti, která ovšem není běžně přístupná. Hlubšími vrstvami nevědomí B - Skupina, C - Kmen (rod), D - Národ, E - Lidstvo, F - Lidští prapředci, G - Zvířecí předci, jsou pak kolektivní nevědomí národa, rasy H - Centrální síla apod. Obsahují zkušenosti společné pro větší skupiny lidí (viz obr. 2.6.). Prvky nevědomí označil Jung jako archetypy, projevující se nejrůznějšími symboly. Každý archetyp je jakýsi základní vzorec chování, otisk zkušenosti získaný silným zážitkem nebo učením a existuje pro něj symbolika určitého typu. Lze předpokládat, že pokud je obsah nevědomí určitým časoprostorovým komplexem, budou mít symboly k němu vztažené podobnou strukturu.
12
Vizuální symbolické struktury
2.4. Vizuální symbolické struktury Přechod od geometrických a abstraktních forem, které chápeme jako symboly) k obrázkovým a dekorativním formám je pozvolný a obrazy jsou naopak zase převoditelné zpět na základní geometrické tvary či na jejich kombinace a struktury, složené z těchto nejjednodušších prvků. Obraz tedy lze chápat jako systém, jehož prvky jsou jednotlivé symboly. Pojem systém je jeden z nejrozšířenějších pojmů, který se používá nejen v technických oblastech, ale i v běžném životě. Pod tímto pojmem si představujeme nějakou množinu prvků, které jsou vázány určitými vztahy. Základy obecné teorie systémů položil Ludwig von Bertalanfy. Jeho pojetí vychází z popisu otevřených (biologických) systémů. Ukázal, že interakce mezi částmi jsou pro vlastnosti celku velmi podstatné a že celek má vlastnosti, které bezprostředně nevyplývají z vlastností jeho částí. Exaktní kybernetickou teorii systémů potom vypracoval Wiener (viz např. [11]). Při definování systému na objektu rozlišujeme několik hierarchických úrovní. Systém definujeme z určitého hlediska. Výčtem proměnných, jejich přípustných hodnot a jejich algebraických, topologických, lingvistických a dalších vlastností na objektu definujeme zdrojový systém. Vše ostatní zahrneme pod pojem okolí systému. Soubor změn pozorovaných proměnných nazveme aktivita systému. Doplnímeli zdrojový systém konkrétním vzorkem aktivity systému (daty), dostaneme datový systém a najdemeli vztahy mezi proměnnými systému tak, že nám umožní generovat stejná data, získáme generativní systém. Rozložíme-li tyto vztahy na dílčí vztahy a najdeme vazby mezi těmito dílčími vztahy (generativní subsystémy), dospějeme ke struktuře systému. Každá ze zmíněných úrovní postupně snižuje neurčitost v popisu systému. Pro lingvistické systémy se výborně uplatnil popis generativních vztahů pomocí přepisovacích gramatik. Ve vizuálních datech použijeme podobný postup, lišící se pouze složitostí a vyjadřovací schopností, jež je vlastní vícedimenziálním přepisovacím gramatikám. Pro obraz je toto pojetí možná příliš násilné a mechanistické, ovšem naším cílem je nejen obraz popsat, ale i porozumět mu, neboli vyvinout prostředky pro jeho počítačovou analýzu a generování. To by se nám při vyšší složitosti popisu nebo při dokonalejším přiblížení charakteru obrazu nemuselo podařit. Rozlišme z tohoto důvodu obrazy na přirozené a technické. O technických obrazech mluví Flusser jako o obrazech vzniklých automaticky pomocí technických prostředků a řadí mezi ně i fotografii, video apod. Musíme ale rozlišovat i technické obrazy v užším slova smyslu jako ty, u nichž známe jejich konstrukci, víme, jak vznikly a jsme schopni tento proces reprodukovat. Ostatní obrazy budeme chápat jako přirozené, je pro ně charakteristická vysoká složitost popisu a nedostatečný formální systém prvků. Pojetí obrazu jako systému opouští tradiční chápáni obrazu jako plochy, která má význam. Tato plocha, figuruje-li vůbec jako prvek vizuální komunikace, je pouze dvourozměrným záznamem stavu systému v určitém okamžiku. Je zajímavé, jakým způsobem je tento záznam proveden a jak je přirozeně mnohodimenziální systém obtisknut do dvou nebo třírozměrného prostoru, ovšem je to jen vlastnost příslušející použitému médiu. Pokud hovoříme o reprodukovatelnosti technických obrazů, chápeme tím reprodukovatelnost strukturální, nikoli proces kopírování obrazu jako plochy.
informace text obraz
složitost 1 dimenziální 2 dimenziální
vizuální informace
nízkodimenziální
chaos
vysokodimenziální
příklad textové zprávy plošné grafické útvary (vizuální podoba písma) 2.5D (iluze prostoru), 3D scény, animace, video (čtyřrozměrný časoprostor) Obtížně popsatelné struktury, náhodné jevy
Tab. 2.1. Složitost, jakou lze očekávat u různých typů informace (dimenze je chápána v běžném slova smyslu)
13
Symbol a realita Dosud byly vektory významů namířeny od světa k člověku a kladla se otázka po významu symbolů z vnějšího světa, existovala tedy diference „označované” a „označující”. Technické obrazy však už nic z vnějšího světa nepředstavují, nejsou označujícím ve vztahu k označovanému, přestože máme sklon je tak chápat. Technický obraz je produktem přístroje a ten zase výsledkem realizace vědeckého textu. Vzdalují se fenomenální povaze tradičních obrazů (tradiční obrazy jsou zrcadly). S tím pak souvisí to, že technické obrazy svůj předmět nepředstavují, ale projektují. Proto je potřeba technické obrazy dešifrovat ne vzhedem k tomu, co označují, ale vzhledem k samotnému označujícímu, tedy odkud ukazují. Dešifrovat technický obraz neznamená dešifrovat to, co ukazuje, ale vyčíst jeho program. Význam technických obrazů je i jejich smyslem. Sémantický i pragmatický rozměr technických obrazů je identický. Technické obrazy, které nás obklopují, označují modely (instrukce) pro přežití, poznání, hodnocení a chování společnosti. Označují programy imperativního typu.
2.5. Symbolické struktury a komunikace Vrozená lidská vlastnost symbolizování znamená v podstatě vytváření skutečnosti pomocí této symbolické kreativity. Je zřejmé, že člověk produkuje symbolonové grafémy jaksi bezděčně. Malíř keramiky v antických Athénách stejně jako moderní grafik je vytvářejí intuitivně, sice vědomě, ale bez znalosti podstaty své aktivity. Často prostě vycházejí z rytmu práce. Staří raní přírodovědci, mágové a filozofové i první vědci grafémami intuitivně symbolizovali různé přírodní síly, živly atp. a domnívali se, že ovládnutím těchto základních obrazců a jejich geometrie (představa, že pojmenováním i ovládám a mám v moci) ovládnou i přírodní síly samé. Přirozené obrazy slouží jako prostředník mezi člověkem a jemu odcizeným světem, zároveň se však mezi člověka a svět staví, zakrývají svět člověku. Úkolem obrazu je umožnit lidské jednání ve světě, který mu není dán bezprostředně – jeskynní malby mají umožnit lov, silniční mapa jízdu autem. Může ale dojít k tomu, že obrazy zakryjí člověku vnější svět. Namísto dešifrování obrazů si je pak promítá do vnějšího světa, svět se pro něj stane souhrnem obrazů, zapomíná, že si tyto obrazy sám vytvořil pro lepší orientaci ve světě. Namísto imaginace (schopnosti abstrahovat dvojrozměrný obraz z časoprostoru) se dostaví halucinace – člověk žije ve funkci obrazů, které sám stvořil. Flusser ([9], [10]) říká, že: Život v časoprostoru obrazu, v kruhovém cyklickém vnímání světa neumožňuje dějiny. Protože člověk pociťoval potřebu vysvětlovat obrazy, které stály jako médium mezi ním a světem, vytvořil písmo. Ovšem lineární písmo vyžaduje zcela odlišný způsob „čtení“ než obraz, oko se pohybuje jednosměrně po řádku, vnímá znaky, jejichž pořadí nelze zaměnit. Vnímat svět pomocí písma znamená osvojit si vědomí časoprostorové vyjímečnosti každého prvku struktury a přenést tuto linearitu do vnímání skutečnosti. Texty mají za úkol vysvětlovat obrazy, tím je však zároveň zakrývají (podobně jako obrazy zakrývají samotnou realitu). Dešifrovat text tedy znamená odhalovat obraz, který se za ním skrývá. Texty jsou metakódem obrazů. Baudrillard [8] předkládá tyto fáze obrazu: Obraz je reflexí základní skutečnosti. Je to tedy ob-raz, odraz skutečnosti. Maskuje a zvrací tuto základní skutečnost. Nereprezentuje to, co se reprezentovat zdá, zbavuje se vázanosti na skutečnost. Maskuje nepřítomnost základní relity. Předstírá souvislost se skutečností. A v poslední fázi: Není nositelem žádného vztahu k nijaké skutečnosti. Podle Baudrillarda byla realita zaměněna svým vlastním obrazem, simulace skrze mediální technologie implodovala otázku po pravdě. Ve světě, kde je Mickey Mouse stejně reálný jako George Bush mizí rozdíl mezi realitou a fikcí. Otázka po pravdě nemá smysl tam, kde došlo k roztržení vazby mezi označujícím a označovaným. Je nerozhodnutelné, jestli se mediální zpráva formuje podle reálného světa, nebo se reálný svět formuje podle mediálních zpráv. Válka v Jugoslávii na konci tisíciletí je stejnou simulací jako její mediální obraz.
14
Symbolické struktury a komunikace Lidskou přirozenou vlastností je vytváření si reality ze sebe sama. Vnímání barev, symbolů a objektů závisí na vizuální zkušenosti jedince, není dáno žádnou pevnou realitou v tradičním smyslu slova. Toto simulakrum, mediální realita symbolů je opět na jistých úrovních společná pro větší skupiny lidí. Na základě společných symbolů s ustáleným významem probíhá komunikace, která obohacuje a dotváří individuální vizuální zkušenost.
15
Symbol a realita
16
3. Struktury obrazu
Na základě znakové teorie podle Ch. Peirce [1] sjednotil M. Bense estetickou analýzu s postupy informační teorie. Estetické procesy jsou chápány jako znakové, estetické objekty pak jsou komplexními zprávami. Cílem je charakterizovat užité stavební kameny (znakový repertoár) obrazu a pravidla jejich kombinace (syntax) a určit jejich informační hodnotu, tj. jejich strukturní a řádový obsah, resp. hodnotu jejich novosti a překvapivosti. Exaktními kategoriemi pro to jsou entropie a redundance. K vyjádření struktury a syntaxe vizuální informace použijeme několik druhů gramatik. Formální základy teorie jazyků pocházejí z poloviny 50. let díky práci Noama Chomského. Ačkoli se proti původnímu záměru nepodařilo formálními gramatikami popsat přirozené jazyky, výsledky v této oblasti měly velký vliv na rozvoj počítačových jazyků a překladačů, teorie automatů a později v počítačové grafice na rozpoznávání vzorů a zpracování obrazů.
3.1. Vlastnosti obrazových struktur Průkopníkem matematikcého pohledu na obraz byl M. Bense [15]. Již on chápe obraz (obecně estetický objekt) jako výsledek uplatnění určitých základních operací na určité základní objekty, stavební kameny. To je základním předpokladem pro počítačové zpracování a pro práci se strukturou obrazu, resp. s jeho „programem”. Bensovy ideje rozpracoval jeho následovník F. Nake: Budiž N množina nezáporných čísel. Je-li M libovolná množina, označme M* množinu všech konečných posloupností prvků z M a m-rozměrný reálný prostor Rm. Jestliže Z je neprázdná množina znaků, T neprázdná množina transformací Z → Z, α je zobrazení α: N x (Z x T)* → Z x T, β je zobrazení (vyhodnocovací funkce) β: (Z x T)* → Rm (m ≥ 1), K neprázdná podmnožina prostoru Rm (množina kritérií), pak pětice P = (Z, T, α, β, K) se nazývá estetický program. Estetický program určuje především výběr základních znaků Z. Těmito znaky mohou být např. úsečky, oblouky, písmena, speciální znaky a znaky z uvedených prvků složené. Množina transformací T obsahuje všechny transformace nebo operace, které lze na tyto znaky aplikovat. Transformací může být umístění určitého znaku, jeho otočení apod. Na základe toho se dostáváme k definici estetického objektu vytvořeného estetickým programem. Každý sled φ = { (zi, ti)| i = 0, 1, 2, ...} je prvkem ( Z x T)* se nazývá estetický objekt. Je to sled dvojic skládajících se vždy z nějakého znaku a transformace, která se má na tento znak provést.
17
Struktury obrazu Vyhodnocovací funkce β přitom přiřazuje každému sledu bod v Rm a hodnotí dosud vytvořený sled na základě kritérií obsažených v množině K. Jsou-li daná kritéria splněna, posloupnost se ukončí, jinak se přechází k dalšímu prvku. Grupy symetrie Uvedený syntaktický přístup vyjadřuje přirozenou strukturu obrazu pouze do určité míry. Je velmi jednoduchý a dá se použít pouze na jednoduché symboly a ornamenty. S rozvojem sofistikovaných nástrojů počítačové grafiky, schopných generovat velmi komplexní virtuální scény, se však stává potřeba počítačově podporovaného ornamentálního designu stále důležitější. Lidé všech národností produkují různé druhy ornamentů ve formě opakovaných vzorů. Na podlahách, cihlových zdech i na oblečení vídáme geometrické motivy. Popíšeme postup, založený na generování obrazců pomocí množiny jednoduchých primitiv, který lze použít k integrování ornamentálních vzorů do syntetických obrazů. Podle výsledků krystalografie mohou být vzory snadno analyzovány a popsány pomocí klasifikace založené na teorii planárních grup symetrie. Všechny pravidelně se opakující planární vzory beze zbytku vyplňující plochu lze rozdělit podle typu symetrie na 17 různých skupin (jednorozměrných grup symetrie je 7, třírozměrných 230). Ačkoli přístup založený na teorii grup není jedinečný, je velmi užitečným nástrojem, jež nám dává základ pro počítačově generovanou grafiku. Definuje množinu objektů a množinu akcí na těchto objektech, potřebnou pro manipulaci a pro získání výsledného obrazu. Pro účel počítačově generovaných ornamentů můžeme říci, že každá grupa symetrie má svůj elementární objekt – základní oblast – a m n o ž i n u elementárních akcí na tomto objektu k produkování celého vzoru. To je přesně to, co je potřeba pro algoritmickou reprezentaci vizuálních objektů. Existuje pět transformací, které tvoří základ každé grupy symetrie. Jsou to identita (žádná operace), posunutí, zrcadlový obraz, převrácený obraz a rotace. Obr. 3.1. (a) - Schematická reprezentace zkoumaného vzoru, (b) Cayleyův diagram, (c) - Základní oblast, (d) - tři možné vztahy mezi základními oblastmi
18
Popis obrazu a lineární gramatiky Jednou z nejdůležitejších grafických reprezentací grup jsou cayleyovy diagramy. Jsou to grafy zobrazující po sobě následující stavy jednotkového elementu v sekvenci transformací. Vrcholy diagramu jsou po sobě jdoucí stavy, hrany znamenají transformace. Diagramy konečných grup jsou konečné, pro nekonečné grupy jsou nekonečné. Pro reprezentaci ornamentů máme vždy nekonečný graf popisující strukturu vzoru. Jednotkový element je vždy základní oblast grupy symetrie, pokud máme proceduru pro vykreslení základní oblasti, lze vykreslit celou plochu pomocí průchodu cayleyovým diagramem tak že sledujeme hrany diagramu a pokaždé, kdy je dosažen vrchol, vložíme
Obr. 3.2. Proces generování vzoru
další kopii základní oblasti v požadovaných transformacích. Na obr. 3.1. je podrobnější pohled na relativně jednoduchý případ, moorskou mozaiku ze dvora Attarine Medeza ve městě Fez. Podle uvedené klasifikace náleží do grupy p6mm. Je vidět, že základní oblast je ve vztahu k sousedním pouze přes zrcadlové obrazy. Prodrobný popis analýzy a generování krystalografických vzorů a cayleyovy diagramy všech 17 planárních grup symetrie lze nalézt v dodatku A.
3.2. Popis obrazu a lineární gramatiky Lineární (též řetězcové) gramatiky jsou matematické modely pocházející z teorie jazyků, která je studuje z hlediska generování, překladu a analýzy umělých jazyků. Formální základy této teorie pocházejí z poloviny 50. let díky práci Noama Chomského. Ačkoli se proti původnímu záměru nepodařilo formálními gramatikami popsat přirozené jazyky, výsledky v této oblasti měly velký vliv na rozvoj počítačových jazyků a překladačů, teorie automatů a později v počítačové grafice právě na rozpoznávání vzorů a zpracování obrazů. Jelikož je teorie gramatik obecně známa a hojně publikována (viz např. [14]), spokojíme se zde s několika základními definicemi. abeceda V je jakákoli konečná množina symbolů věta, řetězec, slovo nad abecedou V je jakýkoli řetězec konečné délky složený ze symbolů abecedy jazyk je jakákoli množina (ne vždy konečná) vět nad abecedou gramatika je čtveřice G = ( N, Σ, P, S), kde N je množina nonterminálů (proměnných, označujeme je velkými písmeny: S, A, B, C, ...), Σ je množina terminálů (konstant, označujeme je malými písmeny: a, b, c, d, ...), P je množina přepisovacích pravidel a S je startovací symbol. Dále předpokládáme, že S náleží do N a že množiny N a Σ jsou disjunktní, jejich sjednocení je abeceda V (smíšené řetězce terminálů a nonterminálů označujeme řeckými písmeny: α, β, χ, ... )
19
Struktury obrazu jazyk generovaný gramatikou G, označovaný L(G) je mnořina řetězců splňujících dvě podmínky: • každý řetězec se skládá pouze z terminálů • kazdý řetězec může být derivován z S vhodnými aplikacemi přepisovacích pravidel z P Takto popsané gramatiky s obecným tvarem přepisovacích pravidel α → β se nazývají neomezené, nebo také typu 0. Podle tvaru pravidel rozlišujeme celkem 4 typy gramatik. Po neomezených to jsou kontextové (typu 1), bezkontextové (typu 2) a regulární (typu 3). Ačkoli jsou neomezené a kontextové gramatiky obecnější a ve svých vyjadřovacích schopnostech tedy mocnější, je jejich praktické použití problémové. Mnohem většího rozšíření se dočkaly jednodušší bezkontextové gramatiky s tvarem pravidel A → β a regulární gramatiky s tvarem pravidel A → aB nebo A → a. Pro popis obrazů zde budeme používat tyto dva jednodušší typy.
Kódování primitiv Metod pro redukování dvourozměrné obrazové informace do řetězcové formy existuje několik. V podstatě lze popsat dva základní směry. Jeden spočívá v sledování kontury objektu a kódování výsledku segmenty určitého směru a délky, které mají jednoduchou návaznost. Druhý je obecnější; předpokládá popis malých homogenních sekcí obrazu směrovanými čárovými segmenty, které jsou spojovány mnoha různými způsoby, nejenom pouhou posloupností čar (blíže se s ním seznámíme v části věnované PDL). Zajímavý příklad popisu obrazu sledováním obrysu je gramatika charakterizující určité typy chromozomů. Na obr. 3.3 jsou primitiva, ze kterých gramatika vychází, a základní tvary submediálních a telocentrických chromozomů.
Obr. 3.3. Primitiva gramatiky pro popis chromozómů a jejich použití na konkrétních chromozomech
Kompletní gramatika G = ( N, Σ, P, S) je dána množinami: Σ = { a, b, c, d, e}, N = { S, T, A, B, C, D, E, F} a P: S→C•C E→F•c B→B•b T→A•C D→c•F B→b C→B•C A→b•A B→d C→C•B A→A•b F→b•F C→F•D A→e F→F•b C→E•F B→b•B F→a Operátor „ • “ znamená jednoduchou konektivitu elementů, přičemž obrys je sledován ve směru
20
Popis obrazu a lineární gramatiky chodu hodinových ručiček. Gramatika je ve skutečnosti kombinovaná ze dvou se startovacími symboly S a T. Start z S generuje submediální, start y T telocentrické chromozomy. PDL Jazyk PDL je jeden ze způsobů popisu obrazu, který se dočkal širšího uplatnění. PDL znamená Picture Description Language, navrhl jej Shaw v roce 1970. Podívejme se blíže na následující jednoduchou gramatiku PDL; její primitiva a produkce jsou zobrazeny na obr. 3.4.:
Obr. 3.4. Primitivy gramatiky PDL a konstrukce jednoduché struktury
Gramatika G = ( N, Σ, P, S) je dána množinami: Σ = { a, b, c, d}, N = { S, A, B, C, D, E} a P: S→d+A C→A+d
A→c+B D→b*E
B→!d*C E→c
Operátor „!“ znamená opačný směr primitivy. Na obr. 3.4. jsou vidět jednotlivé tvary, které vznikají postupným uplatňováním pravidel. Tato gramatika je konstruována tak, že lze pouze postupně uplatnit všechna pravidla, což vede k jedinému výslednému tvaru. Rozsah generovaných tvarů se může zvýšit, když zavedeme rekurzi. Uvažujme gramatiku G = ( N, Σ, P, S), danou množinami: Σ = { a, b, c, d}, N = { S, A, B} a P: S→d+A B→a+B
A→c+A B→b*B
A→!d*B B→c
Kdybychom tato pravidla uplatnili jedno po druhém, jak jsou zapsána, dostali bychom výsledný tvar jako v předchozím případě. Ovšem tato množina dovoluje i jiné pořadí použití pravidel a díky rekurzi, kdy se proměnná opakovaně přepisuje na sama sebe, je možné generovat nekonečné množství tvarů. Maximální vyjadřovací schopnosti gramatiky by se ještě dalo dosáhnout nahrazením nonterminálů A a B samotným S.
21
Struktury obrazu
3.3. Popis obrazu a stromové gramatiky Pro definování složitějších symbolů, jako jsou např. tvary složené z více částí, tvary s dírami apod., potřebujeme vyšší úroveň popisu, než nám mohou řetězcové gramatiky nabídnout. Stromové gramatiky patří mezi vícedimenziální, vycházejí ze struktury n-árního stromu. Jejich přepisovací pravidla vyjadřují obecně přepsání jednoho podstromu na jiný. Takovýto popis nám uchovává podstatně více informací o struktuře obrazu a lze jej tedy použít pro popis složitějších vztahů primitiv, ať už u komplexních symbolů, nebo ve scéně. Stromová gramatika je definována jako pětice G = ( N, Σ, P, S), kde N a Σ jsou množiny nonterminálů a terminálů, S je startovací symbol (obecně jakýkoli strom), P je množina přepisovacích pravidel tvaru Ω → Ψ, kde Ω a Ψ jsou stromy a r je ohodnocovací funkce, která určuje počet přímých následníků uzlu, který je terminálem gramatiky. Stejně jako u řetězcových gramatik je obecný tvar přepisovacího pravidla příliš vzdálen praktickému použití a proto byl zaveden typ expanzivní stromová gramatika pouze s pravidly Obr. 3.5. Obraz složený z několika dílčích tvarů a jeho tvaru stromová struktura získaná užitím relace „obsahuje“
A
→
a
A1
A2
...
An
Popis grafických symbolů stromem, který má jako listy geometrická primitiva a v uzlech jsou operace s nimi je znám a používán jako CSG (Constructive Solid Geometry). Stromové gramatiky našly také velké využití pro modelování rostlin a stromů. Na obr. 3.6. je příklad takové gramatiky. Na tomto místě lze též připomenout rozšířené gramatické systémy pro podobné účely, tzv. Lsystémy, neboli Lindenmayerovy systémy [25]. Obr. 3.6. Stromová gramatika pro generování stromů
22
Popis obrazu a grafové gramatiky
3.4. Popis obrazu a grafové gramatiky Grafové přepisovací systémy jsou stále častější metodou používanou pro tvorbu složitých struktur z jednodušších. Oproti řetězcovým a stromovým gramatikám mají zdaleka největší vyjadřovací schopnost a nejlépe se hodí pro popis obrazu, budeme se jim tedy věnovat podrobněji. Kromě použití v počítačové grafice pro analýzu obrazů a rozpoznávání 3D objektů (byly použity mj. k popisu abstrakce obrazů M. C. Eschera nebo Pabla Picassa) jsou vhodné k reprezentaci relačních struktur, specifikaci paralelních systémů, databázových systémů apod. Slibná aplikační pole, v nichž již grafické gramatiky byly úspěšně použity, jsou též modelování vývoje rostlin, rozpoznávání hudebních záznamů a mnoho dalších. Historie grafových gramatik se odvíjí od několika prací z počátku 70. let, týkajících se tzv. síťových gramatik. Sítě jsou neorientované grafové struktury s označenými uzly. Pro popis obrazu umožňují sítě mnohem mocnější a abstraktnější formalismus než stromové nebo řetězcové gramatiky. V konvenční frázové struktuře řetězcových gramatik jsou pravidla tvaru α → β používána k nahrazení jednoho řetězce druhým. Takové pravidlo je plně specifikováno definováním řetězců α a β. Jakýkoli řetězec γαδ může být ihned přepsán jako γβδ. Podobně jsou bez potíží interpretovány pravidla expanzivních stromových gramatik. Definice přepisovacích pravidel sítí je však poněkud komplikovanější. Jestliže chceme nahradit podsíť α sítě ω jinou podsítí β, je nutné specifikovat, jak podsíť β zapustit do ω na místě α. Existuje několik přístupů, jak toho lze dosáhnout, velmi významné je řešení s používáním zapouštěcích pravidel pro takovéto vkládání. Pro podrobnější informace viz. dodatek B. Nyní definujme základní pojmy pro grafové gramatiky se zapouštěcími pravidly. Nechť V je množina jmen a Nα a Nβ množiny uzlů sítí α a β. Přepisovací pravidlo grafu definujeme jako trojici (α, β, φ), kde φ je funkce z Nβ x Nα do 2V (množina podmnožin jmen). Tato funkce určuje zapouštění b na místě a, tj. určuje, jak připojit uzly b sousedům každého uzlu vyjmuté sítě a. Argument funkce φ je tvaru (n, m), přičemž n je z Nβ a m z Nα. Hodnoty φ(n, m) určují povolená spojení n k sousedům m. Grafová gramatika je čtveřice G = ( N Σ, P, S), kde N je množina nonterminálů, Σ je množina terminálů, P je množina přepisovacích pravidel a S startovací symbol. Jako obvykle S patří do N a abeceda V je sjednocení N a Σ.
Příklad 1 Mnoho uměleckých aktivit i užitkové grafiky využívá pravidelné vzorované plochy. Jejich modelování je možné automatizovat a vytvořit pro ně vhodné nástroje. Struktury systémů pro dělení plochy mohou být reprezentovány grafy, jejichž uzly odpovídají grafickým motivům s přidanými transformacemi pro tyto motivy. Ukážeme příklad, jak generovat tyto grafy pomocí bezkontextových grafových gramatik. Pro všechny aplikace v grafickém designu je základem na jedné straně určitá podoba gramatiky, která určuje strukturální část obrazu, na druhé straně je to realizační schéma, jakým se výsledná struktura převede na vizuální podobu, dalo by se zjednodušeně říci, že je to grafická podoba terminálů gramatiky. Nalezení terminálů jako základních jednotek pro skladbu obrazu je významná část celého problému. Zde použijeme systém symbolů, které prezentoval ve svých poznámkách holandský grafik a tiskař M. C. Escher [20]. Escher popsal klasifikaci 23 typů dvoubarevných vzorů s jedním motivem, založeným na síti čtyřúhelníků. V každém vrcholu vzoru se stýká sudý počet motivů. Každý motiv sdílí společnou hranu s dalším motivem, který je jiné barvy, motivy stejné barvy se dotýkají pouze ve vrcholech. Tato klasifikace záleží na dvou hlavních charakteristikách: • Typu polygonu v podkladové mřížce • Geometrických transformacích, které vztahují jeden motiv k ostatním motivům
23
Struktury obrazu
Obr. 3.7. Graf reprezentující strukturu dělení plochy
Obr. 3.8. Grafová gramatika systému II
Vzory vytvořené danou množinou transformací se nazývají systém. Každý z devíti systémů, označených římskými číslicemi I až IX je charakterizován jinou množinou transformací. Pro každý systém jsou použity notace podle typu polygonu. Písmeno A označuje volný rovnoběžník, B kosočtverec, C obdélník a D čtverec. Např pro systém I jsou definovány translace v obou příčných směrech i v obou diagonálních směrech s ohledem na použitý čtyřúhelník. Jestliže je potom jako tento čtyřúhelník vybrán rovnoběžník, získáme systém IA. Pro vytvoření vzoru je nejprve zkonstruován graf reprezentující jeho strukturu a pak je vybráno vhodné realizační schéma. Realizační schéma nám dává informaci o polygonech a jejich transformacích, které mají být na tyto polygony aplikovány. Uzly grafu jsou označeny jmény odpovídajících primitiv. Abychom mohli definovat graf reprezentující strukturu rozdělení plochy, musíme určit spojení mezi uzly. Předpokládáme, že jestliže je při konstrukci vzoru motiv odpovídající vi Obr. 3.9. Dva kroky derivace s příslušnými realizacemi transformován, abychom dostali motiv odpovídající vj, je uzel vi spojen s uzlem vj. Graf na obr. 3.7. je logická struktura dvoubarevného rozdělení plochy. Je složena z 25 uzlů a 24 hran. Je zde pouze jedna relace mezi uzly, která znamená, že primitiva jsou slepena k sobě. Cílový uzel každé hrany reprezentuje primitivum získané transformací primitiva odpovídajícího zdrojovému uzlu této hrany. Transformace přiřazené uzlům (f, f1, ..., f24) určují potřebné rozmístění motivů. Např. motivy
Obr. 3.10. Obrazce generované systémy IID a VIID
24
Popis obrazu a grafové gramatiky odpovídající uzlům v2 a v4 jsou rotovány, motivy odpovídající v3 a v5 jsou posunuty s ohledem na motiv odpovídající v1. Proto jsou transformace f1 a f3 definovány jako kombinace rotací o 180° okolo středu rovnoběžných stran čtyřúhelníku s transformací f, definovanou pro v1 (f1 = Rt( p1, 180°) + f, f3 = Rt( p2, 180°) + f). Transformace f2 a f4 jsou kombinace translací s transformací f (f2 = Tr( 1, 0) + f, f4 = Tr( -1, 0) + f). Na obr. 3.8. jsou tři z 18 pravidel grafové gramatiky, která vytvářejí systém II. Ostatní pravidla jsou definována analogicky. Grafy reprezentující požadované struktury vzoru jsou derivovány použitím sekvencí pravidel, ke kterým přidáváme sémantické atributy, které nám umožní přiřadit transformace uzlům podle kritérií realizačního schematu. Další podrobnosti lze nalézt v [20] a [22].
Příklad 2 V další části studia grafického modelování pomocí grafových gramatik bude nastíněn způsob definování grafických modelů (3D objektů) specifikací jejich logických struktur a možnými cestami realizace takových struktur. Konstrukce modelů bude založena na výběru modelovacích primitiv (prototypových částí) a souboru modelovacích procedur pro jejich ustavení a manipulaci. Předpokládejme modelování boxu na obr. 3.11. Analýzou tří ortografických pohledů získáme logickou strukturu, kterou v našem pojetí reprezentujeme jako graf. Abychom mohli popsat relace nejen mezi celými částmi boxu, ale i mezi fragmenty těchto částí, tj. mezi stěnami kvádrů, přiřadíme uzlům grafu dva druhy popisu. Jeden druh jsou jména prototypových částí, druhý pojmenovává vazby uzlu s dalšími částmi, přičemž tyto vazby mohou být vstupní a výstupní. Designér potřebuje zejména dva grafické modely boxu. Jeden v dvourozměrném prostoru (obr. 3.11. vpravo nahoře), druhý v trojrozměrném prostoru (obr. 3.11. vlevo nahoře). Oba dva se skládají z obdélníků, rozdíl je pouze v lokalizaci obdélníků v těchto Obr. 3.11. Nahoře: Třídimenzionální model boxu a rozvinutý prostorech. Prostorové plášť, Uprostřed: Ortogonální pohledy na box, Dole: rozmístění je definováno Grafická struktura boxu a odpovídající graf p ř í s l u š n ý m i transformacemi, které mohou být definovány pro každý model, struktura obou modelů je však stejná a je vyjádřena grafem na obr. 3.11. dole. Tento fakt můžeme popsat i obecněji. Máme strukturu tvořeného objektu, která má být mapována do různých grafických modelů a hledáme předpis pro toto mapování. Tento předpis,
25
Struktury obrazu nazývaný realizační schéma, by měl být co nejflexibilnější, abychom jím mohli popsat různé modely příslušející jedné struktuře. Realizační schéma definované pro univerzum grafů v n-rozměrném euklidovském prostoru se skládá z: 1. 2. 3. 4.
množiny transformací definovaných pro euklidovský prostor množiny prototypových částí mapování, nazývaného přořazení prototypů, které prototypy přiřazuje uzlům grafu mapování, nazývaného přiřazení fragmentů, které přiřazuje fragmenty prototypických částí vstupním a výstupním vazbám uzlů grafu. 5. Spojovací funkce, která závisí na kriteriích designu, jejíž hodnoty určují transformace komponent 6. predikát aplikovatelnosti, který popisuje kritéria designu a na kterém závisí hodnoty spojovací funkce
Obr. 3.12. Grafová gramatika boxu
Většina grafických modelů má poměrně složitou logickou strukturu, vyjádřenou příslušně rozsáhlými grafy. Pro generování těchto grafů se používají grafové gramatiky. Navíc, i modifikace těchto struktur bude prováděna aplikováním pravidel grafových gramatik. Zde uvádíme poměrně neformální způsob popisu realizačního schematu a používáme atributované gramatiky s množinami vstupních a výstupních vazeb pro terminály. Formální definice a další podrobnosti lze nalézt v [25].
26
Složitost a entropie
3.5. Složitost a entropie Věnovat pozornost strukturální složitosti obrazu je velmi přínosné. Tato složitost je zásadně důležitá z hlediska pochopení obrazu a působení obrazu na člověka. Člověk je schopen porozumět pouze určité míře složitosti a to v závislosti na estetických kvalitách vnímaného. Birkhoffova estetická míra Teorie estetické míry pochází od filosofů a teoretiků umění, kteří se ve dvacátém století pokoušeli o přesné matematické vymezení tohoto pojmu. Výzkumy v této oblasti stimuluje také informatika, kde se matematické vzorce popisující estetickou míru používají v grafickém designu pro hodnocení vzorů apod. Obecnou teorii estetické míry, kterou navrhl Birkhoff [30], si nyní přiblížíme. Podle této teorie vyvinuli Grabska a Pospiech [32] estetický vzorec pro fraktály skládající se z lineárních segmentů a dospěli ke zjištění, že pro takové objekty je estetická míra podle Birkhoffa vždy nulová. Birkhoff hledá estetickou míru rovnicí tvaru M = O / C kde M je estetická míra, O je řád (order) a C je složitost objektu (complexity). V případě polygonálních forem může být řád rozdělen na pět prvků: O = V + E + R + HV – F kde • Vertikální symetrie V je rovna 1, jestliže je polygon symetrický podle vertikální osy, 0 v opačném případě • Prvek rovnováhy E je rovna 1, jestliže je polygon vertikálně symetrický, nebo má horizontální bázi; jestliže nesplňuje tuto podmínku, ale je v rovnováze v běžném mechanickém smyslu, pak E je 0, jinak se rovná –1. • Rotační symetrie R se rovná q/2 pro q menší než 6 a 3 pro q větší, kde úhel 2π/q je nejmenší úhel rotace takový, že objekt rotovaný o tento úhel zůstává ve stejné pozici. • Prvek relace k síti HV je roven 2, 1, nebo 0 podle relace polygonu k horizontální, vertikální nebo diamantové síti. • Prvek neuspokojivé formy F je roven 0, jestliže jsou splněny následující podmínky: 1. Minimální vzdálenost jednoho vrcholu k jakémukoli jinému vrcholu nebo mezi paralelními stranami není menší než 1/10 maximální vzdálenosti mezi vrcholy polygonu. 2. Úhel mezi dvěma neparalelními stranami není větší než 20°. 3. Pro každou stranu tvořící konkávní výklenek existuje jiná strana ležící na stejné linii 4. Existuje nejméně jeden typ výklenku 5. V a R nejsou obě 0. Toto měření uvádíme pouze z historických důvodů. Je zřejmé, že takto navržený výpočet nesouvisí s vnímáním objektu člověkem a nepopisuje dostatečně ani jeho tvarovou složitost. Složitost objektů a s ní i složitost vnímání objektů začneme zkoumat popisem jejich dimenze, která do jisté míry vyjadřuje jejich strukturu a estetické působení na člověka dále nastíníme pomocí pojmu entropie.
Topologická dimenze Topologická dimenze je běžná idea dimenze, bod má topologickou dimenzi 0, čára má topologickou dimenzi 1, plocha má topologickou dimenzi 2 atd. Pro přesnou definici: Množina má topologickou dimenzi 0, jestliže každý bod má libovolně malé okolí, jehož hranice neprotínají množinu. Množina S má topologickou dimenzi k, jestliže každý bod v S má libovolně malé
27
Struktury obrazu okolí, jehož hranice se setkávají s S v množině dimenze k-1 a k je nejmenší nezáporné celé číslo, pro které toto platí. Fraktální dimenze Obvyklým typem fraktální dimenze je Hausdorff-Besicovichova dimenze, ovšem způsobů, jak fraktální dimenzi počítat, existuje několik. Pro jednoduché soběpodobné tvary může být fraktální dimenze vypočtena limitou
lim
log( změna velikosti objektu) ————————————————————log( změna velikosti měřítka)
pro velikost měřítka blížící se 0. Fraktální dimenze kvantifikuje statickou geometrii objektu. Např. pro přímou čáru, zvětšenou faktorem 2, dostaneme čáru dvojnásobné délky. Její dimenze je tedy log ( 2) / log( 2) = 1. Příklad 1: Kochové vločka: Při každé změně měřítka nahrazujeme rovinný úsek čtyřmi segmenty, z nichž každý má délku 1/3 původního segmentu. Tj. při trojnásobné změně měřítka se délka křivky zvětší čtyřikrát. Z toho: D = log(4) / log(3) = 1.261859507...
Příklad 2: Cantorova množina Cantorova množina se skládá z čárového segmentu, přičemž při podrobnějším pohledu (změně měřítka), prostřední třetina zmizí. Tj. při trojnásobné změně měřítka se délka zvětší dvakrát a fraktální dimenze D = log(2) / log(3) = 0.630929753 Příklad 3: Sierpinského koberec Se skládá z devíti čtverců v poli 3 x 3, přičemž prostřední je prázdný. Pokaždé, co se měřítko zvětší 3x, plocha se zvětší 8x. D = log(8) / log(3) = 1.892789261...
Entropie I když bude podrobněji koncepce míry informace a entropie v gramatických systémech popsána v kapitole 4.2., všimneme si nyní, jakou má entropie souvislost se složitostí obrazu a jeho estetickou kategorizací. Umělecké dílo je v intencích informační estetiky chápáno jako vysoce nepravděpodobný jev a dalo by se charakterizovat jistou překvapivostí. Naopak zvyk znamená vysokou míru pravděpodobnosti, která souvisí s pojmem entropie a události a jevy, na něž jsme zvyklí, nevnímáme. Aby byl obraz procítitelný, musí obsahovat určitou míru nového. Postupnou aplikací pravidel přepisovacího systému se zvyšuje složitost výsledného obrazu (pokud uvažujeme pouze generativní pravidla). Posloupnost těchto aplikací je tokem času v systému a zvyšuje entropii. Z toho však ještě nelze vyvodit, jak bude výsledek esteticky posouzen, protože
28
Složitost a entropie
Obr. 3.13. Zvyšující se složitost obrazu generovaného stromovou gramatikou
míra informace nebo entropie závisí na složitosti druhého systému, který se komunikačního procesu účastní (vizuální zkušenosti člověka, který obraz vnímá).
29
Struktury obrazu
30
4. Vizuální komunikace
V minulé kapitole jsme pracovali se strukturou statického obrazu. Nyní k stávajícímu popisu musíme přidat časový rozměr. Obecně by čas mohl být další dimenzí (nebo několika dalšími dimenzemi, viz níže) určitého n-dimenziálního popisu, ovšem je nutné říci, že takové struktury na současném stupni vývoje informatiky postrádáme. Stále čas vnímáme jinak, než vizuální dimenze a také o něm jinak uvažujeme. Přijetím času do našeho popisu se dostaneme od pojmu obrazu k pojmu videografického časoprostoru. Tento termín byl zaveden v teorii médií a mediálního umění. Teprve s časovým rozměrem se poté můžeme zabývat komunikací a předáváním vizuální informace nebo zkuženosti.
4.1. Vlastnosti videografických struktur Stejně jako o obrazu budeme nejdříve zkoumat povahu časového rozměru vizuální informace a hledat v něm struktury vhodné pro jeho znakové nebo symbolické vyjádření. V odstavci 2.2. jsme popsali fakt, že při interpretaci vizuálních vjemů nedokáže lidský mozek pracovat s vjemem jako takovým, dokáže pouze porovnávat rozdíly mezi vjemy. Jedním z nejdůležitěších témat tedy bude určování rozdílu. V praxi nacházejí nástroje pro porovnávání videosekvencí významné uplatnění např. pří vyhledávání v multimediálních databázích. Podmínkou konstrukce takového vizuálního vyhledávacího nástroje je systematická analýza různých metod porovnávání videosekvencí a určování rozdílu mezi nimi. Videosekvencemi se budeme zabývat na čtyřech úrovních temporálního rozlišení, jakými jsou smímek, záběr, scéna a video.
4.1.1. Videopodobnost Na otázku, kdy jsou dvě videa podobná, není jednoduchá odpověď. Video má rozmanité aspekty a jeho definice na sémantické úrovni je vágní. Předpokládejme například, že máme záběr amerického prezidenta na slavnostní večeři, druhý záběr je samotný prezident a třetí je rodinná večeře. Která z nich budou podobná a která ne? Často dojdeme k závěrům, že absolutní podobnost nelze určit a musíme nechat na uživateli, aby rozhodl podle svých požadavků. My budeme rozlišovat tři ortogonální aspekty videosekvencí: • úrovně temporálního rozlišení • temporální řád a • temporální trvání Úrovně temporálního rozlišení Videosekvence se mohou významně lišit délkou. Je zřejmé, že podobnost mezi dvěma krátkými (několikasekundovými) sekvencemi a jejich ohodnocení je jiného typu než podobnost mezi dlouhými
31
Vizuální komunikace sekvencemi (mnohaminutovými) s tisíci snímků. Proto je třeba videa klasifikovat s ohledem na jejich temporální délku, než může být aplikováno příslušné porovnávací schéma. Videosekvence tedy budeme klasifikovat podle standardního hierarchického modelu na záběry, scény a video. Záběr je tvořen nepřerušeným záznamem kamery. Scéna znamená videosekvenci delší než jeden záběr a kratší než celé video, která má charakteristický vzor vlastností záběru. Tato definice se lehce liší od definice ve filmovém umění ([43]). Video je potom videoprodukce plné délky. Na těchto čtyřech úrovních se budeme zabývat video podobností pomocí vlastností obrazu a pohybu. Temporální řád Video sekvence se skládají z obrazů. Podle toho se dá video chápat jako sekvence obrazů a posuzovat podobnost videa jako podobnost mezi vlastnostmi obrazů. Podobnost mezi videosekvencemi lze pak určit množstvím podobných vlastností obrazu. Tento přístup nazýváme množinovou reprezentací videosekvencí. Všimněme si, že ignoruje jakoukoli temporální posloupnost obrazových vlastností. Často je nutné posuzovat temporální řád pouze podle vlastností statických obrazů. Tomuto pohledu říkáme sekvenční reprezentace. Temporální trvání Temporální trvání v tomto kontextu znamená, do jaké míry je temporální trvání určité vlastnosti důležité. Například záběr, na kterém je 3 sekundy nehybný objekt, který se pak náhle během jedné sekundy přesune mimo obraz, vyvolává otázku, jak důležité temporální trvání je. Obvykle bychom mohli reprezentovat statický obraz jedním snímkem a fázi pohybu pěti snímky. Je ovšem otázkou, jestli můžeme použít tuto sekvenci jako reprezentaci záběru, nebo zda máme brát v úvahu také čas, který referenční snímek pokrývá. Tato otázka je nezávislá na výběru reprezentace. Bude patrně záležet na aplikaci, zda je přesný časový vývoj důležitý, nebo ne.
4.1.2. Vlastnosti videa a měření jejich rozdílu Kriteria porovnávání v oblasti obsahu obrazu a videa jsou obvykle označována jako vlastnosti. Hodnota vlastnosti může být jakýkoli typ dat, např. skalární veličina, vektor, jiný obraz nebo textový řetězec. V našem textu budou vlastnosti odvozeny z množiny nebo sekvence individuálních snímků, záběrů, scén nebo videí. Protože se na základě těchto vlastností bude rozhodovat o vizuální podobnosti videosekvencí, je nutné, aby jejich měření odpovídalo do určité míry lidskému vnímání podobnosti/rozdílu. Pro některé z nich, jako jsou barva a světelnost existují dobře přijatelná percepčně orientovaná měření rozdílu. Ovšem pro ostatní vlastnosti modelující lidské vnímání zatím definice neexistují. Obr. 4.1. Standardní model struktury videa
Některé vlastností obrazu a videa Nyní stručně popíšeme některé z vlastností, které tvoří pouze malý výběr z mnoha možných. Odpovídající vztahy pro jejich měření lze nalézt například v [35] nebo [36].
32
Vlastnosti videografických struktur • Barevná atmosféra Barevná atmosféra je významná vlastnost snímku a sekvence snímků. V praxi se obvykle měří některým druhem barevného histogramu. Jelikož nás zajímají měření zohledňující lidské vnímání, je použit barevný prostor CIE L*a*b*, který byl vytvořen pro perceptuální jednotnost [40]. Vhodná technika pro měření barevných histogramů je tzv. vektor barevné soudržnost (color coherence vector, CCV [41]). Překonává obvyklé barevné histogramy, jelikož používá prostorovou soudržnost. Místo počítání pouhého počtu bodů určité barvy rozlišuje CCV i mezi soudržnými a nesoudržnými body v každé barevné třídě j podle velikosti barevné oblasti, do které patří. • Světelnost Světelnost hraje ve filmovém průmyslu velmi důležitou roli a obvykle se značně mění v různých segmentech videa. Světelnost je definována jako perceptuální odpověď na jas a označuje se L *. Jas, označovaný Y, je definován jako zářivý výkon, na který je aplikována spektrální funkce citlivosti charakteristická pro lidské vidění [40]. Světelnost sekvence snímků f je průměr světelnosti všech bodů v sekvenci. • Intenzita pohybu Intenzita pohybu popisuje, zda je přítomen pohyb, nebo ne, přičemž může znamenat jak pohyb objektů, nebo pohyb kamery. Nejkratší možná sekvence, pro kterou má intenzita pohybu smysl, jsou dva po sobe jdoucí snímky. Vhodnou technikou měření je tzv. koeficient změny hran (edge change ratio, ECR [42]) V porovnání s bloky pohybových vektorů je spolehlivější a pro výpočet rychlejší. ECR sekvence snímků f je definován jako průměr hodnot u všech snímků sekvence. Výhodou ECR jako charakteristického parametru je, že registruje strukturální změny v sekvenci jako vstupující, vystupující a pohybující se objekty včetně rychlých operací kamery. Kromě toho je jistým způsobem nezávislý na změnách barev a intenzity, protože závisí pouze na ostrých hranách. • Orientace V některých scénách se může vyskytovat mnoho hran určitého typu. Např. ve městě s mnoha budovami budou převažovat vertikální hrany, které nenajdeme na záběrech s lidmi. Je vhodné proto popsat obraz typem orientace, který obsahuje. Tento popis je obzvláště vhodný pro zachycení charakteristického pozadí. Prototyp lokální orientace je definován jako struktura obrazu, kde se hodnoty barvy mění přesně v jednom směru a zůstávají stejné ve směru kolmém. Orientace nerozlišuje mezi směrem 0° a 180°. Normalizace měření rozdílu Ve své práci [44] prezentovali Santini a Jain podrobný rozbor psychologických poznatků týkajících se lidského rozhodování o podobnosti. Ačkoli stále neexistuje obecně přijatý model vnímání podobnosti a jimi navrhovaný model má příliš mnoho parametrů, než aby se dal prakticky využít, lze identifikovat některá základní pravidla. Z kognitivního hlediska je nejdůležitější (1) nalézt rozsah hodnot rozdílů, který člověk vnímá (2) očekávat saturaci hodnot rozdílu mimo tyto oblasti Saturace je důležitým bodem, jelikož zamezuje velkým rozdílům u jedné vlastnosti, které by dominovaly celému rozhodování o rozdílu. Potlačuje také malé rozdíly, které většinou vznikají šumem. Stupeň lidské citlivosti na různost je velmi adaptivní. Diametrálně se liší pro množinu podobných obrazů na jedné straně a pro množinu nehomogenních různorodých obrazů na straně druhé. Předpokládejme, že rozsah [a1, a2] reprezentuje hodnoty určité vlastnosti. Potom může být rozhodování o podobnosti modelováno jednoduchou funkcí jak je znázorněno na obr. 4.2., která normalizuje měření rozdílu vybrané vlastnosti. Tato funkce může být vždy aproximována nekonečně diferencovatelnou, tzv. logistickou funkcí [44].
33
Vizuální komunikace
Obr. 4.2. Prototyp normalizované funkce rozdílu vlastností
4.1.3. Porovnávání videografických sekvencí V následující sekci bude popsán obecný přístup k porovnávání videosekvencí, který můžeme aplikovat rekurzivně na různých úrovních temporálního rozlišení. Může vycházet jak z množinové, tak sekvenční reprezentace s různým stupněm agregace. Porovnávací strategie na každé úrovni temporálního rozlišení pracuje následujícím způsobem: vlastnosti úrovní vyššího temporálního rozlišení jsou zapojeny do reprezentace videosekvence, poté jsou sekvence porovnány prostředky normalizovaného měření rozdílu, který je vypočten pomocí těchto zapojených vlastností. Na úrovni snímku Snímky mohou být porovnány pomocí jakékoli vlastnosti obrazu, pro kterou je definováno měření rozdílu. Takové měření by mělo být konstruovatelné pro většinu vlastností. Na úrovni záběru Záběry jsou reprezentovány vlastnostmi odvozenými z jejich jednotlivých snímků. Vlastnost může být odvozena z jednoho nebo několika snímků a je mu/jim přiřazena. Jestliže je vlastnost vypočtena pro každý snímek záběru, je popis vlastnosti neagregovaný. Jestliže je odvozena z množiny nebo sekvence snímků, je popis vlastnosti částečně agregovaný. Je-li z celého záběru odvozena pouze jedna vlastnost, je plně agregovaná. Spolu se stupněm agregace je důležité také trvání jednotlivých hodnot vlastnosti. Neagregované reprezentace zachycují přesné temporální trvání vlastnosti, takže dvě neagregované sekvence jsou brány jako podobné, jestliže trvání jednotlivých hodnot vlastnosti je téměř identické. Částečně agregované sekvence umožňují kontrolu nad důležitostí tohoto trvání a pro plně agregované sekvence je trvání bezvýznamné. Navíc rozlišujeme mezi reprezentací množinovou a sekvenční. V sekvenční reprezentaci jsou vlastnosti v čase. Jsou-li jejich hodnoty vypočteny pro každý snímek, je řazení skalární. Oproti tomu množinová reprezentace ignoruje časové řazení. Bere v úvahu pouze množství a stupeň
Obr. 4.3. Závislosti mezi možnými reprezentacemi sekvence snímků. Šířka šipek indikuje význam atributu, který popisují.
34
Vlastnosti videografických struktur podobnosti mezi hodnotami vlastností. Na nejvyšší úrovni agregace obě reprezentace shodně degradují na jedinou hodnotu vlastnosti. Tyto závislosti jsou shrnuty na obr. 4.3.
Sekvenční reprezentace Neagregovaná sekvence Účelem této reprezentace je zachování přesného časového vývoje záběru. Záběr je vyjádřen sekvencí hodnot vlastnosti, vypočtených pro každý snímek. Každá hodnota je znakem, obor možných hodnot je abecedou a sekvence znaků je řetězec. Dvě sekvence mohou být porovnávány prostředky práce s řetězci, jako je hledání přibližné shody podřetězců nebo nejdelší společné subsekvence a jejich struktura bude popsána lineární gramatikou. Přibližná shoda podřetězců: pro daný řetězec A délky P a delší řetězec B délky N nalezne funkce psp( A, B) podřetězec B, shodující se s A s minimem substitucí, mazání a vládání znaků. Minimální počet substitucí, mazání a vkládání se nazývá minimální rozdíl D mezi A a B. Nejdelší společná subsekvence: pro dané řetězce A a B délky M a N je jejich nejdelší společná subsekvence nss( A, B), přičemž pro rozhodování o jejich podobnosti se vyhodnocuje délka této subsekvence označovaná |nss(A,B)|. Maximum |nss(A,B)| je minimum |A| a |B|, podle toho je vyjádření rozdílu definováno jako |nss( A, B)| 1 - —————————————— min ( |A|, |B| ) Částečně agregovaná sekvence snímků Tato reprezentace zhruba zachovává temporální vývoj záběru pomocí několika reprezentativních snímků, zvaných r-frames. Čím důležitější je přesné temporální rozlišení, tím více je takových snímků potřeba. Jejich počet je určován maximálním rozdílem hodnoty vlastnosti mezi snímky, tzv. prahem, který je pro různé vlastnosti různý (budeme označovat threshold). Se zvyšováním tohoto prahu klesá přesnost vizuální reprezentace sekvence, protože každý r-frame pokrývá větší oblast vizuálních rozdílů, na druhé straně nulový práh agreguje sekvence jednotlivých snímků. Pro daný záběr S skládající se z n snímků f1 , ... , fn a maximální rozdíl threshold určité vlastnosti mezi dvěma r-frames jsou r-frames generovány následujícím způsobem: 1. i := 1; rNo := 1; rFrame rNo := f1 2. while ((i <= n) && (distance(rFrame rNo , fi ) < ( 0.5 * threshold )) 2.1. i++ 3. rFrame rNo := fi-1 4. while (i <= n) 4.1. if (distance(rFrame rNo , fi ) > ( 0.5 *threshold )) rNo++ rFrame rNo := fi 4.2. i++ Pro každou vlastnost je nutný individuální proces selekce snímků. Pomocí metody přibližné shody podřetězců lze rozhodovat např. o následujících otázkách: • Je daný záběr zpomalením jiného? • Jaké jsou jiné záběry, kde se objekt pohybuje podle stejného vzorce, jako na aktuálním záběru? Množinová reprezentace Účel tohoto modelu je zachování statického obsahu záběru pomocí několika reprezentativních snímků. Je zřejmé, že pokud používáme určitou toleranci pro podobnost obrazů, nebudeme potřebovat všechny snímky, jediný snímek pro celý záběr ale nebude dostatečný.
35
Vizuální komunikace Pro dané dva záběry S1 = { f11 , ..., f1n } a S2 = { f11 , ..., f1n } a jejich sekvence referenčních snímků R1 = { f1R11 , ..., f1R1l } a R2 = { f1R21 , ..., f1R2k }, generované např. použitím předchozího algoritmu, je třeba pro normalizované určení rozdílu sledovat několik následujících případů: 1. Pro každý referenční snímek záběru S1 lze nalézt nejméně jeden podobný refenční snímek záběru S2 a naopak, tzn. (R1 ∩ R2 = R1 ) ∧ (R2 ∩ R1 = R2 ). Potom jsou oba záběry identické s ohledem na statickou vlastnost. 2. Pro každý referenční snímek záběru S1 lze nalézt nejméně jeden podobný refenční snímek záběru S2, ale ne pro všechny referenční snímky S2 lze nalézt podobné v S1, tzn. (R1 ∩ R2 = R1) ∧ (R2 ∩ R1 ⊂ R2 ). Potom je S1 podmnožinou S2 s ohledem na statickou vlastnost. 3. Pro každý referenční snímek záběru S2 lze nalézt nejméně jeden podobný refenční snímek záběru S1, ale ne pro všechny referenční snímky S1 lze nalézt podobné v S2, tzn. (R1 ∩ R2 ⊂ R1) ∧ (R2 ∩ R1 = R2 ). Potom je S2 podmnožinou S1 s ohledem na statickou vlastnost. 4. Existuje nejméně jeden referenční snímek pro S1 a S2, který není podobný jakémukoli referenčnímu snímku druhého záběru, tzn. (R1 ∩ R2 ⊂ R1) ∧ (R2 ∩ R1 ⊂ R2 ) .
Na základě těchto čtyř příkladů jsou definovány dvě normalizovaná měření rozdílu. Asymetrický rozdíl jako | R1 ∩ R2 | dist asym (R1, R2) = 1 - —-------————————| R1 | a symetrický rozdíl jako
| R1 ∩ R2 | + | R2 ∩ R1 | dist sym (R1, R2) = 1 - ————-------------——————————————— | R1 | + | R2 |
Obě nabývají hodnoty 0, jestliže jsou R1 a R2 identické a hodnoty 1, jestliže nemají nic společného. Lze si povšimnout, že celkové temporální trvání do určité míry ovlivňuje výsledek, pokud jej chceme zcela vyloučit, mohou být normalizované rozdíly definovány jako minimum všech párových rozdílů mezi prvky R1 a R2: dist ( R1, R2) = min { distance ( r1, r2) | r1 ∈ R1, r2 ∈ R2}
Plně agregovaná množina nebo sekvence Tato reprezentace popisuje záběr jako jednu plně agregovanou jednotku. Charakteristické vlastnosti jsou vypočteny pouze pro celý záběr. Záběry jsou potom porovnávány přímo prostředky pro normalizované určování rozdílu. Tak je možné zjistit např. následující informace: • typ statického snímkování (dlouhý záběr, detail) • typ dynamického snímkování (např. dominantní pohyb kamery) • množství akce (intenzita pohybu) Na úrovni scény Scéna může být vyjádřena jako sekvence nebo množina vlastností na určité úrovni agregace. Základní jednotky (znaky), jsou záběry, které jsou porovnávány na základě konceptů uvedených v předchozím textu, z čehož vyplývá celkově rekurzivní výpočetní schéma. Délky záběrů a vzorce pohybu jsou často souhrnně označovány jako rytmus.
36
Vlastnosti videografických struktur Na úrovni videa Na této úrovni jsou porovnávány sekvence skládající se od několika scén až po videoprodukce plné délky, jako filmy, dokumenty apod. Je možné hledat struktury následujícího typu: Jestliže jsou obě videa různými verzemi stejného filmu, jaké jsou mezi nimi rozdíly? • Jestliže mají dvě videa společné záběry nebo scény, objevují se tyto v obou ve stejné temporální sekvenci, nebo je jejich temporální struktura odlišná? • Se zřetelem na charakteristické vzorce záběrů nalezené na úrovni scény, mají obě videa podobnou temporální strukturu? Berme v úvahu dvě srovnávací techniky: posuzování korespondence a posuzování změny sekvence. Budeme vycházet ze dvou proudů videa, daných jejich entitami E1 = ( E11, ..., E1N1) a E2 = ( E21, ..., E2N2). Entity mohou být jak záběry, tak scény, ze kterých se video skládá, obecně i jednotlivé snímky, i když na této úrovni to nemá velký smysl. V prvním kroku jsou entity navzájem porovnány a je zkonstruován graf, kde uzly reprezentují entity a hrany znamenají podobnost entit vzhledem k nějaké vlastnosti.
Obr. 4.4. Graf podobnosti konstruovaný k výpočtu korespondence a změny sekvence
Korespondence: Korespondence specifikuje procentuální podíl entit ve videosekvenci video1, které jsou podobné entitám ve videosekvenci video2. Je formálně definována jako | E1 ∩ E2 | Correspondence ( video1, video2) = ————————— | E1 | Kde | E1 ∩ E2 | označuje kardinalitu množiny entit z E1, pro které lze nalézt alespoň jednu podobnou entitu v E2. Výpočet opět není symetrický, takže záměna jednoho videa za druhé většinou ovlivní výslednou hodnotu. Např. jestliže Correspondence( video1, video2) = 0.9 a Correspondence( video2, video1) = 0.5, lze usoudit, že video1 je zkrácenou verzí video2. Změna sekvence: Je třeba analyzovat, jestli se entity, které mají videa společné, objevují v obou ve stejném pořadí, nebo zda je jejich sekvence změněna. Na základě takové vlastnosti lze rozhodovat o tom, zda byla videoinformace vytvořena se stejným obsahem, kontextem a se zachováním stejné struktury. Nízké hodnoty budou znamenat, že materiál zachovává originální strukturu, vysoké hodnoty siglalizují, že kontext záběrů je jiný, což pravděpodobně znamená nový obsah. Hodnota změny sekvence je počítána následujícím způsobem:
37
Vizuální komunikace countReOrderings := 0 // počet nalezených změn sekvence countOrderAgreements :=0 // počet shod pořadí i1 := 1; i2 = 1 // nastavení indexů v obou videosekvencích na první entitu while ( i2 <= N2 ) 4.1. i2 := najdi index další entity video2 linkované k video1 počínaje od i2 4.2. itemp := najdi index první entity video1 linkované k i2 počínaje od i1 4.3. if (itemp == ∅) countReOrderings++; i1 := najdi index první entity video1 linkované k i2; else countOrderAgreements++; i1 := itemp + 1 5. Resequencing( video1 , video2) = countReOrderings / (countReOrderings + countOrderAgreements)
1. 2. 3. 4.
Algoritmus určuje minimální počet relativních změn nutných k transformaci kříženě linkovaných entit videa1 do sekvence se stejným pořadím, jaké mají kříženě linkované entity videa2. V nejhorším případě, když je pořadí opačné, bude N-1 změn sekvence. Na obr. 4.4. je příklad, kde nebyly potřeba žádné změny. Silné čáry jsou hrany vybrané algoritmem. Další podrobnosti lze nalézt v [35].
4.2. Teorie komunikace Historicky, první vědecká koncepce informace pochází od Shannona (1949). Ta definuje množství informace v objektu jako počet bitů, které musí být přeneseny, aby bylo možné vybrat objekt z předem definované množiny elementů. Na základě této koncepce množství informace byla vyvinuta úspěšná teorie přenosu dat. Přístup Kolmogorova a Chaitina, který bude prezentován v této kapitole, bere v úvahu množství informace v objektu jako počet bitů potřebný pro popis objektu. S použitím koncepce univerzálního počítače se ukázalo, že tento nový přístup je nezávislý na metodách, použitých pro popis objektu, protože existuje univerzální metoda popisu, která nemusí být ve všech případech nejlepší, ale je nejlepší v tom smyslu, že žádná jiná metoda nám neposkytuje o moc lepší popis nekonečně často.
Obr. 4.5. Komunikace mezi dvěma stranami
38
Pokud uvažujeme o systémech vizuálních informací, jak byly popsány v kapitole 2 a jejich strukturálním popisu gramatikami s přepisovacími pravidly, můžeme jako univerzální počítač vnímat gramatický systém, který je schopný generovat obrazy dané vizuální reality. Programem takového počítače je posloupnost pravidel, která se musí aplikovat, aby byl
Teorie komunikace vygenerován určitý obraz. Pomocí následující koncepce složitosti si ukážeme, že efektivní komunikace mezi dvěma takovými systémy není problémem přenosu výsledného obrazu a jeho analýzy, ale přenosu onoho programu. Kolmogorovova složitost Základní idea informační složitosti Kolmogorova a Chaitina je jednoduchá. Množství informace v řetězci w je délka nejkratšího řetězce p (nazývaného program), z kterého může být w rekonstruováno (vybraným počítačem C). Intuitivně např. vidíme, že řetězec 001001001001001001001001001001001001001001001001001001001001001 je mnohem méně náhodný, než řetězec 0110111001101100111001011110010100100100001110101000100110, protoře první může být zapsán jako 21 krát řetězec 001, kdežto druhý pravděpodobně nemá jednodušší vyjádření. Na jednu stranu tato idea zní přirozeně, na druhou stranu pak informační komplexita závisí na počítači C. Naštěstí tento problém můžeme vyřešit, jak uvidíme dále, zavedením univerzálního počítače (V dalším textu budeme operovat s pojmy Turingův stroj, vícepáskový Turingův stroj apod. a symboly s nimi souvisejícími. Laskavý čtenář si může podrobnější informace a formální definice vyhledat v rozsáhlé literatuře týkající se teoretické informatiky, např. v [13]) Vezměme v úvahu abecedu Σ a dvoupáskový univerzální Turingův stroj U s páskovou abecedou Σ0 = Σ – { _ }, který může simulovat jakýkoli jednopáskový Turingův stroj s páskovou abecedou Σ0. Kolmogorovova složitost jakéhokoli x ∈ Σ∗ s ohledem na U je délka nejkratšího programu p 0
takového, že když U začne s ε na prví pásce a s p na druhé, zastaví s x na prní pásce. Jinými slovy KU( x) = min { |p| | p ∈ Σ∗0, U( p) = x } Jestliže takové p neexistuje, KU = ∞. Malá technická podmínka nám umožňuje učinit koncept kolmogorovovy složitosti nezávislý zásadně (poze konstantním aditivním faktorem) na výběru univerzálního počítače. Předpokládejme, že každý Turingův stroj může být simulován programem, který neobsahuje čtyřsymbolový řetězec DATA a že dostane-li U na druhé pásce vstupní slovo pDATAx, pak U simuluje Turingův stroj p na vstupu x. Je jednoduché ukázat, že každý univerzální Turingův stroj může být modifikován tak, aby vyhověl těmto podmínkám, proto předpokládejme, že toto je případ s univerzálním Turingovým strojem. Lemma 3.1 KU( x) ≤ | x | + cU, kde konstanta cU závisí pouze na U. Důkaz: Jestliže U je univerzální, může jednopáskový Turingův stroj, který nic nedělá, jen okamžitě zastaví, simulovat programem p0 (neobsahujícím DATA). Proto pro vstup p0DATAx, zapíše U na první pásku x a zastaví. Z toho plyne cU = | p0 | + 4. Bohužel, Kolmogorovova složitost není vyčíslitelná. Kolmogorovova komplexita nám umožňuje pracovat s myšlenkou náhodnosti a stupněm náhodnosti, založenou na předpokladu, že řetězec, který je náhodný, nelze zkomprimovat. Pro konečná slova je náhodnost záležitostí míry. Slovo w můžeme brát jako náhodné, jestliže nejkratší program, popisující w je přibližně stejné délky jako w, například, je-li rozdíl | w | - K( w) malý. Podle vybraného univerzálního počítače může být aditivní
39
Vizuální komunikace konstanta vyšší nebo nižší. Například můžeme říci, že slovo je poměrně náhodné, jestliže K( w) ≥ | w | - 10. Koncepce Kolmogorovovy složitosti může být rozšířena na všechny objekty, které mohou být přirozenou cestou kódovány jako binární řetězce. Například pro grafy K( G) = K ( wG), pak lze mluvit také o náhodných grafech apod.
Chaitinova složitost Chaitinova složitost, ačkoli se zdá menší modifikací Kolmogorovovy složitosti, byla objevena nezávisle a vede k mnoha konceptům zásadního významu, jako jsou např. pojmy aloritmické entropie a informace. V definici Kolmogorovovy složitosti jsme implicitně předpokládali, že univerzální počítač, který simuluje programy nad abecedou Σ0, pracuje také s blanky, aby rozpoznal konec programu. Tento fakt má však překvapivě několik důsledků. Například nemůžeme přidat jeden program za druhý a očekávat, že univerzální počítač bude simulovat jejich seriovou kompozici, pokud není nějak určeno, např. oddělovačem, kde jeden program končí a začíná druhý. Podobně potřebujeme způsob, jak oddělit program a data. To vede k tomu, že do některých úvah musíme zavést logaritmický faktor. Chaitinova složitost, nebo sebevymezující složitost HU( x) řetězce x s ohledem na univerzální počítač U je délka nejkratšího sebevymezujícího programu p, podle kterého U produkuje x. Formálně HU( x) = min { | p | | U( p) = x, p je sebevymezující program} Termín “sebevymezující” znamená, že je možné rozeznat konec programu čtením všech jeho symbolů a ničeho jiného. Důsledkem je, že sebevymezující program musí být bezprefixový. Ukázalo se, že je užitečné definovat podmíněnou Chaitinovu složitost řetězce x s ohledem na jiný řetězec t a univerzální počítač U jako délku nejkratšího programu p, podle kterého U produkuje x, přičemž je U navíc dán t*, nejkratší program, podle kterého U produkuje t. Formálně H ( x / t ) = min { | p | | U( p, t*) = x, p je sebevymezující program} Pro ilustraci Chaitinovy a podmíněné Chaitinovy složitosti můžeme vzít v úvahu třípáskový Turingův stroj, který dostává na druhé pásce v prvním případě ε a v druhém t*, na třetí pásce dostává p a produkuje x na první. H ( x ) budeme nazývat algoritmickou entropií, nebo informační složitostí x. Podobně označujeme H ( x / t ) podmíněnou Chaitinovu složitost řetězce x s ohledem na t. O co je podmíněná komplexita H ( x / t ) nižší než H ( x ) můžeme chápat jako množství informace, které t obsahuje o x. To vede k následující definici algoritmické informace v t o x: I(t:x)=H(x)–H(x/t)
H ( x / x ) = O( 1 ) H ( x ) = H ( x, t ) + O( 1 ) H ( x / t ) = H ( x ) + O( 1 ) H ( x, t ) = H ( x ) + H ( t / x ) + O( 1 ) H ( x, t ) = H ( x ) + H ( t ) + O( 1 )
I ( t : x ) = Ω( 1 ) I ( t : x ) = H ( t ) + H ( x ) + H ( t, x ) + O( 1 ) I ( x : x ) = H ( x ) + O( 1 ) I ( x : ε ) = O( 1 ) I ( ε : x ) = O( 1 )
Tab 4.1. Vlastnosti algoritmické entropie a informace
Základní vlastnosti algoritmické entropie, algoritmické informace a podmíněné Chaitinovy složitosti jsou shrnuty v tabulce 4.1. Tyto vlastnosti mohou být dokázány jednoduše pomocí základních definic. Další podrobnosti lze nalézt např. v [13].
40
Inference gramatik
4.3. Inference gramatik Pokračujme nyní ještě dále v myšlence komunikace dvou (a více) vizuálních gramatických systémů. Problém, který popíšeme, je získávání údajů o gamatice jednoho systému druhým systémem. U jednoduchých projektů je designér schopen ji navrhnout, ovšem nám půjde o automatizovaný způsob předávání takto navržené nebo jinak získané informace. Potřebujeme automatický způsob analýzy symbolů a potřebujeme základní společné dohody o používaných strukturách. Aby bylo možné modelovat jazyk určité třídy obrazů co nejsprávněji, je snaha vytvořit gramatiku přímo z množiny vzorových obrazů. Tento problém určení gramatiky na základě vzorových vět se nazývá inference gramatik.
zdroj vzoru
inferenční algoritmus Gramatika navrhovaná jako model zdroje učitel
Obr. 4.6. Schéma procesu inference gramatik
Na obr. je znázorněna podstata problému inference. Zdroj vzorů generuje řetězy složené z konečného počtu terminálních symbolů. Předpokládejme, že tyto řetězy obsahují strukturální rysy, které budou charakterizovány gramatikou G navrženou jako model tohoto zdroje. Všechna slova, která mohou být generována zdrojem, jsou obsažena v jazyce L ( G), zatímco slova, která nemohou být zdrojem generována, tvoří doplněk tohoto jazyka LC( G). Tato informace je vstupem algoritmu inference, jehož úkolem je nalézt neznámou gramatiku G. Slova z L ( G) lze snadno získat sledováním výstupu zdroje, avšak prvky LC( G) musí určit vnější učitel, který má k dispozici další informaci o vlastnostech gramatiky G. Počet vzorových slov je konečný a to nestačí k jednoznačné definici potenciálně nekonečného jazyka L ( G). Jakékoli konečné množině vzorů může být přiřazen nekonečný počet jazyků, proto nemůžeme zpěně očekávat jednoznačnou identifikaci gramatiky, která generovala vzorové řetězy. Od inferenčního algoritmu očekáváme, že vytvoří gramatiku, která popíše vzorovou množinu a navíc další slova, která mají v určitém smyslu stejnou strukturu jako vzorová. Obecně lze metody inference rozdělit do dvou kategorií: enumerační a indukční. Princip metod založených na enumeraci spočívá ve výběru takové gramatiky z konečné množiny M gramatik, která generuje celou vzorovou množinu, nebo alespoň její největší část. Problémem je vhodný výběr množiny M a způsob jejího prohledávání. U metod založených na indukci se na základě tvaru slov z trénovací množiny usuzuje, jak by měla vypadat slova podobná slovům z trénovací množiny a podle toho se stanovují přepisovací pravidla. Obecná metoda inference gramatik na základě předloženého seznamu slov zatím neexistuje, navíc i v těch nejjednodušších případech generuje učením odvozená gramatika jazyk výrazně mohutnější než minimální jazyk, který může danou třídu reprezentovat, což je obzvláště nevýhodné pro syntaktickou analýzu. Některé postupy lze nalézt v [52].
41
Vizuální komunikace
42
5. Závěr
Cílem této práce bylo nalézt systémy a struktury pro popis obrazu, které jsou vhodným prostředkem pro přenos vizuální informace, pro vyjádření významu obrazu a pro popis vznikajících forem v kreativním grafickém designu. Klíčovým konceptem, který splňuje tyto požadavky, je strukturální popis obrazu a videografického časoprostoru. Tento strukturální popis je specifikován svým obsahem, tj. primitivními tvary, ze kterých se skládá, a svým uspořádáním, tedy prostorovými relacemi mezi jednotlivými elementy. Nejvhodnějšími informatickými strukturami jsou vizuální gramatiky různých typů, nebo též vizuální přepisovací systémy. Řetězcové gramatiky jsou matematické modely pocházející z teorie jazyků, která je studuje z hlediska generování, překladu a analýzy umělých jazyků. Základy této teorie pocházejí z poloviny 50. let díky práci Noama Chomského. Ačkoli se proti původnímu záměru nepodařilo formálními gramatikami popsat přirozené jazyky, výsledky v této oblasti měly velký vliv na rozvoj počítačových jazyků a překladačů, teorie automatů a později v počítačové grafice právě na rozpoznávání vzorů a zpracování obrazů. Lineárním popisem na základe Chomského gramatik vyjadřujeme obrysy grafických oblastí. Tento popis má funkci rozlišující, oddělující. Pro definování složitějších struktur v obraze potřebujeme vyšší úroveň popisu, než nám mohou řetězcové gramatiky nabídnout. Pak můžeme použít gramatiky stromové. Stromové gramatiky patří již mezi vícedimenziální, vycházejí ze struktury n-árního stromu. Jejich přepisovací pravidla vyjadřují obecně přepsání jednoho podstromu na jiný. Takovýto popis nám uchovává podstatně více informací o struktuře obrazu a používá se pro popis složitějších vztahů grafických primitiv. Stále častější metodou používanou pro tvorbu složitých struktur z jednodušších jsou však grafové přepisovací systémy. Oproti řetězcovým a stromovým gramatikám mají zdaleka největší vyjadřovací schopnost a nejlépe se hodí pro popis obrazu. Kromě použití v počítačové grafice pro analýzu obrazů a rozpoznávání 3D objektů jsou vhodné k reprezentaci relačních struktur, specifikaci paralelních systémů, databázových systémů apod. Aplikační pole, v nichž již grafové gramatiky byly úspěšně použity, jsou též modelování vývoje rostlin, rozpoznávání hudebních záznamů a mnoho dalších. Kromě struktury statického obrazu musíme brát v úvahu i časový rozměr. Obecně by čas mohl být další dimenzí určitého n-dimenziálního popisu, ovšem je nutné říci, že takové struktury na současném stupni vývoje informatiky postrádáme. Stále čas vnímáme jinak, než vizuální dimenze a také o něm jinak uvažujeme. Přijetím času do našeho popisu jsme se dostali od pojmu obrazu k pojmu videografického časoprostoru. V tomto kontextu se již můžeme zabývat komunikací a předáváním vizuální informace nebo zkuženosti.
43
Závěr Popis obrazů gramatikami je zatím v počátcích. Již se dobře uplatňuje při generování opakujících se vzorů a ornamentů, ale to jsou teprve základní vizuální útvary. Při tomto popisu obrazů textovými a dalšími nízkodimenziálními gramatikami popisujeme metakódem struktury, které jsou pro nás příliš složité. Texty jsou metakódy obrazu. I s vícedimenziálními gramatikami jistě narazíme na problém, kterým je nemožnost popisu přirozených obrazů (stejně jako je nemožné popsat přirozené jazyky). Prostor pro technické obrazy však přesto zůstává nevyčerpatelný. Dnešní rozvoj vizuálních médií je obrovský. Zdá se, že texty jsou na ústupu před obrazovou informací, ikonami a grafickými symboly. Přesto jsou obrazy dosud brány jako datové celky, které dokážeme zobrazit, okopírovat, ale dále o nich nevíme mnoho. Téměř je nelze popsat, jelikož jejich vnímání je vysoce subjektivní, nelze odhadnout, jak budou působit na příjemce a jaké jsou mechanismy tohoto působení. Jelikož se většina obrazových médií zpracovává na počítačích, je úkolem informatiky zavést pro získávání a zpracování vizuální informace potřebné nástroje. Význam popsaných struktur a přístupů se dotýká zejména následujících oblastí: 1. V oboru grafického designu a masmédií, jejichž představiteli jsou např. typografie nebo televize, jde především o nové možnosti pro efektivní sdělení informací a racionální práci s významem ve vizuální informaci. Jedině gramotnost týkající se struktury obrazu a videa může znamenat rozvoj těchto médií. V oblasti reklamy je zase rozhodující estetická míra, nebo libost při vnímání symbolu, jeho působení na člověka a asociovaný význam. Struktura a vizuální složitost obrazu v tomto procesu hrají rozhodující roli. 2. Počítačové vidění a porozumění obrazu je na strukturách, skrývajících se za daty proudícími z videokamer, kriticky závislé. Na obraze nemůžeme nic rozpoznat, pokud nemáme žádný koncept ohledně objektů, které bychom chtěli nalézt. Použijeme-li šířeji platné koncepce generování a analýzy vizuálních objektů, lze vypracovat obecnější základy počítačového vidění, dosud založeného na speciálních řešeních. 3. Vizuální databáze je obor, v němž již grafové gramatiky také nalezly uplatnění. Indexování a dotazy týkající se obrazů, vyjádření obrazů, vizuální operace s databázemi obsahujícími multimediální data. To vše jsou operace vycházející ze struktury obrazu a videa a bez příslušné teorie, jak zpracovávat vizuální informace, bychom měli jen gigabajty nepoužitelných dat. 4. Pro 3D vyjádření informace o scéně je výhodné využít rekurzivity a vícenásobné použitelnosti objektů nebo jejich částí. Na této koncepci jsou postaveny mnohé moderní formáty, jako např. VRML (Virtual Reality Modelling Language), u kterého je nutná vysoká efektivita popisu scény. Většina tradičních nástrojů pro 3D ovšem pracuje s jednoduchým konstruktivistickým a explicitním popisem objektů, který má pro konverzi na interaktivní média nevhodné vlastnosti, zejména vysokou paměťovou náročnost. Použitím symbolického popisu, tj. jasné identifikace základních objektů a operací s nimi umožňuje vyvinout mnohem kvalitnější nástroje pro vytváření vizuálních médií, např. inteligentní editory, schopné provádět symbolické operace nad scénou, samozřejmě včetně syntaktické analýzy. 5. Virtuální realita, královská disciplína počítačové grafiky, nám dává pro vizuální komunikaci a zkoumání její podstaty nejlepší podmínky. Virtuální realita tvoří celý vnímaný svět uživatele a tento svět je kompletně generován počítačem. Komunikační problémy ve jsou založeny na obraze a vizuální symboly a jejich význam jsou základem pro orientaci a interakci člověka se scénou. Na základě poznání struktury obrazu a videografického časoprostoru lze scénu chápat organicky jako systém, jehož součástí jsou psychické systémy člověka, který scénu vnímá. Zde je otevřené pole pro výzkum vícedimenziální komunikace a interakce.
44
Závěr Chápu, že popsaná problematika je pouze nejzákladnějším úvodem a že ke každému tématu by mělo být napsáno mnohem a mnohem více, rozsah této práce to však nedovoluje. Jako programovou část jsem přiložil modul Maya Imagination, zásuvný modul aplikace Alias|Wavefront Maya, vizuální gramatický systém pro generování trojrozměrných objektů na základě jejich strukturálního popisu. Program byl vytvořen díky spolupráci s akademickou malířkou Lucií Svobodovou, přední českou výtvarnicí věnující se počítačové animaci a jeho použití při této spolupráci ukázalo, že výborně splňuje požadavky pro tvůrčí uměleckou činnost.
Michal Klodner
45
Závěr
46
Dodatek A. Počítačové zpracování ornamentálních vzorů
A.1. Algoritmus Vstup algoritmu: Nákres nebo fotografie planárního ornamentálního vzoru Výstup algoritmu: Všechny informace potřebné pro integrování tohoto vzoru do počítačového systému. Fáze I: Analýza Krok 1: Nalezněte translační jednotku. Vyhledejte střed nebo libovolný referenční bod každého obrázku, který formuje opakující se vzor. Ověřte, že jednotka je minimální. Je obvyklé vybrat dvojnásobek translační jednotky pro spolehlivější analýzu. Krok 2: Nalezněte do které ze 17 planárních krystalografických grup symetrie vzor patří. Použijte informace ze schemat A.1. – A.17. Krok 3: Identifikujte základní oblast a Cayleyův diagram pro danou grupu symetrie. Může být vhodné překreslit zvlášť základní oblast se všemi detaily. Krok 4: V určitých případech mohou vzory vykazovat kontinuitu mezi základními oblastmi. Může být aplikována analýza takto vzniklých pramenů. Fáze II: Generování Krok 5: Implementujte operaci VykresliOblast() která do základní oblasti vloží všechny grafické informace v konvenčním formátu, které mohou být následně transformovány operacemi v kroku 6. Krok 6: Podle typu vzoru implementujte potřebné operace ze šesti možných: PosunOblasti() ZrcadlovyObrazOblasti() PrevracenyObrazOblasti() DvojnasobnaRotaceOblasti() TrojnasobnaRotaceOblasti() CtyrnasobnaRotaceOblasti() Krok 7: Podle Cayleyova diagramu dané grupy symetrie implementujte cyklus, který prochází všechny uzly diagramu a který aplikuje potřebné transformace na hranách diagramu. Tato operace vyplní celou plochu vzorem (parametry cyklu omezují celkové rozprostření).
47
Počítačové zpracování ornamentálních vzorů 6ti nás. symetrie? ANO
NE
Zrcadlový obraz? NE
ANO
4 nás. symetrie? ANO
NE 3 nás. symetrie?
Zrcadlový obraz? ANO
ANO
NE
2 nás. symetrie? ANO
NE
NE
NE
Zrcadlový obraz?
Středy 3 nás. rotace jen na zrcadlových liniích? ANO
NE
Zrcadlový obraz?
Zrcadlové linie v 4 směrech? ANO
ANO
NE
NE
ANO 2. zrcadlový obr.?
ANO
NE
Zrcadlový obraz?
Převrácený obr.? ANO
NE
ANO
NE
Kosočtv. mřížka? ANO
NE
Převrácený obr.? ANO
NE
Kosočtv. mřížka? ANO
NE
Obr. A.1. Selektor typu planárních grup symetrie
Rovnoběžníková
Obdélníková
Kosočtvercová
Čtvercová
Šestiúhelníková
Obr. A.2. Typy mřížek pro klasifikaci typu planárních grup symetrie
Fáze III: Další transformace Kroky 8 a dále: Podle potřeby další transformace, jako barvení, osvětlení, mapování textur apod.
A.2. Grupy symetrie Následující schemata, převzaté z práce Victora Ostromoukhova [63], popisují 17 planárních grup symetrie. Používáme notaci uváděnou v Mezinárodních tabulkách pro krystalografii [64].
48
Grupy symetrie
Translace mezi základními oblastmi
Schéma A.1. Grupa symetrie p1 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
49
Počítačové zpracování ornamentálních vzorů
Střed 2nás. rotace
Translace mezi základními oblastmi
2nás. rotace mezi základními oblastmi
Schéma A.2. Grupa symetrie p2 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
50
Grupy symetrie
Osa zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
Translace mezi základními oblastmi
Schéma A.3. Grupa symetrie pm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
51
Počítačové zpracování ornamentálních vzorů
Osa převráceného obrazu
Translace mezi základními oblastmi
Převrácený obraz mezi základními oblastmi
Schéma A.4. Grupa symetrie pg (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
52
Grupy symetrie Osa zrcadlového obrazu Osa převráceného obrazu
Zrcadlový obraz mezi základními oblastmi
Převrácený obraz mezi základními oblastmi
Schéma A.5. Grupa symetrie cm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
53
Počítačové zpracování ornamentálních vzorů
Osa zrcadlového obrazu Střed 2nás. rotace ležící na ose zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
Schéma A.6. Grupa symetrie p2mm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
54
Grupy symetrie Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace
2nás. rotace mezi základními oblastmi
Zrcadlový obraz mezi základními oblastmi Translace mezi základními oblastmi
Schéma A.7. Grupa symetrie p2mg (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
55
Počítačové zpracování ornamentálních vzorů
Osa převráceného obrazu Střed 2nás. rotace
Převrácený obraz mezi základními oblastmi
Schéma A.8. Grupa symetrie p2gg (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
56
Grupy symetrie
Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace ležící na ose zrcadlového obrazu
Střed 2nás. rotace
Zrcadlový obraz mezi základními oblastmi
2nás. rotace mezi základními oblastmi
Schéma A.9. Grupa symetrie c2mm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
57
Počítačové zpracování ornamentálních vzorů Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace
Střed 4nás. rotace
4nás. rotace mezi základními oblastmi
Schéma A.10. Grupa symetrie p4 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
58
Grupy symetrie Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace ležící na ose zrcadlového obrazu Střed 4nás. rotace ležící na ose zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
Schéma A.11. Grupa symetrie p4mm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
59
Počítačové zpracování ornamentálních vzorů Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace ležící na ose zrcadlového obrazu
Střed 4nás. rotace
Zrcadlový obraz mezi základními oblastmi
4nás. rotace mezi základními oblastmi
Schéma A.12. Grupa symetrie p4gm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
60
Grupy symetrie Střed 3nás. rotace
3nás. rotace mezi základními oblastmi
Schéma A.13. Grupa symetrie p3 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
61
Počítačové zpracování ornamentálních vzorů Osa zrcadlového obrazu Osa převráceného obrazu Střed 3nás. rotace ležící na ose zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
Schéma A.14. Grupa symetrie p3m1 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
62
Grupy symetrie
Osa zrcadlového obrazu Osa převráceného obrazu Střed 3nás. rotace
Střed 3nás. rotace ležící na ose zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
3nás. rotace mezi základními oblastmi
Schéma A.15. Grupa symetrie p31m (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
63
Počítačové zpracování ornamentálních vzorů Střed 2nás. rotace Střed 3nás. rotace Střed 6ti nás. rotace
2nás. rotace mezi základními oblastmi
3nás. rotace mezi základními oblastmi
Schéma A.16. Grupa symetrie p6 (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
64
Grupy symetrie Osa zrcadlového obrazu Osa převráceného obrazu Střed 2nás. rotace ležící na ose zrcadlového obrazu
Střed 3nás. rotace ležící na ose zrcadlového obrazu
Střed 6ti nás. rotace ležící na ose zrcadlového obrazu
Zrcadlový obraz mezi základními oblastmi
Schéma A.17. Grupa symetrie p6mm (b) - Cayleyův diagram (c) - Translační jednotka (d) - Základní oblast (e) - Relace mezi přilehlými základními oblastmi
65
Počítačové zpracování ornamentálních vzorů
66
Dodatek B. Syntaktická analýza grafových gramatik
Tento dodatek popisuje formalismus grafových gramatik a příslušný algoritmus pro syntaktickou analýzu těchto gramatik. Vychází z práce J. Rekerse a A. Schürra [17] a je zaměřen na použití při definici grafické syntaxe. Ukázalo se, že omezení se na bezkontextové gramatiky (kde každá levá strana pravidla obsahuje jednoduchý nonterminál) je příliš restriktivní a velká oblast vizuálních systémů tak pro nás zůstává uzavřena. Proto se budeme zabývat kontextově senzitivními grafovými gramatikami (kde levé i pravé strany pravidel jsou grafy), ovšem pouze vrstvenými, nikoli obecnými, které jsou přece jenom těžko zvládnutelné. U vrstvených gramatik musí být levá strana pravidla lexikograficky menší než pravá, abychom předešli cyklickým derivacím.
B.1. Úvod do grafových gramatik B.1.1. Analýza formalismu V případě lineárních textových jazyků je jasné, jak nahradit nonterminál ve větě odpovídající sekvencí (non)terminálů. V případě grafických systémů s mnoha možnými relacemi mezi „jazykovými” elementy potřebujeme mnohem komplikovanější mechanismus pro (znovu)navázání vztahů mezi okolím nahrazeného nonterminálu a nahrazujícími (non)terminály. Jedno známé řešení je rozšířit levé a pravé strany pravidel o kontextové elementy, pomocí kterých je možné vytvořit hrany mezi novými a zachovanými vrcholy sítě. Dalším řešením je implicitní zapouštění. Všechny potřebné vztahy mezi objekty jsou implicitně definovány jako omezení jejich atributových hodnot. Atributová přiřazení v pravidlech mají implicitní vedlejší efekt na vytvoření nových vztahů k neznámým kontextovým elementům. Zapouštěcí pravidla je třetí řešení problému, které se stalo základem mnoha grafových gramatik. Máme oddělená zapouštěcí pravidla, která umožňují přesměrování množin vztahů z nahrazovaného nonterminálu na (non)terminály, jež jej nahrazují. Všechny tři přístupy mají své výhody i nevýhody. Hlavní nevýhodou implicitního zapouštění je, že uživatelé neznají vždy posloupnost přiřazování atributů a parsery ztrácí mnoho času při extrahování implicitních znalostí o vztazích z atributů a omezení. Kontextový přístup se zdá velmi dobře použitelný, ovšem vyžaduje značně slořitý parser. Dále zde může být obtížné přepisovat nonterminály, které figurují ve staticky neznámém počtu vztahů. Řešení pomocí zapouštěcích pravidel je asi nejvýhodnější. Problematické však může být pochopení zapouštěcích pravidel a skutečnost, že všechny parsery pro pravidla se zapouštěcími pravidly jsou beznadějně neefektivní nebo kladou příliš velká omezení na tvar levých nebo pravých stran pravidel. Přitom jsou zapouštěcí pravidla schopna přesměrovat nebo přejmenovat pouze existující vztahy, takže nedovolují definici pravidla, které vytváří nové vztahy mezi dříve nepropojenými vrcholy.
67
Syntaktická analýza grafových gramatik Pro shrnutí uveďme otázky, které je třeba brát v úvahu při studiu algoritmů pro parsing grafových gramatik: • • • • • •
Je levá strana pravidla omezena na jednoduchý nonterminál (bezkontextové pravidlo)? Jsou nějaká omezení pro pravou stranu pravidla? Umožňuje formalismus reference dodatečných kontextových lelementů, které musí být přítomny, ale zůstávají nezměněny při aplikování pravidla? Má daný typ gramatiky zapouštěcí pravidla, která navazují vztahy mezi novými prvky (vytvořenými pravidlem) a okolní strukturou? Jsou nějaká další omezení pro množinu pravidel nebo formu grafů, která nespadají do výše uvedených kategorií? Je časová a prostorová složitost algoritmu lineární, polynomiální, nebo dokonce exponenciální vzhledem k velikosti vstupního grafu?
Existuje překvapivě mnoho formalismů, které se dají rozdělit na dva hlavní přístupy: • •
Algebraická rodina grafových gramatik s explicitním zapouštěním pomocí kontextových elementů Algoritmická rodina grafových gramatik, používající výkonná zapouštěcí pravidla
Přístupy, které podporují parsing dnes spadají převážně do algoritmické větve. Zde bude naším cílem definovat třídu grafových gramatik, které mají hlavní vlastnosti algebraického přístupu (zapouštění kontextovými elementy a co nejvolnější levé a pravé strany pravidel) a jsou stále efektivně analyzovatelné.
B.1.2. Grafy, Grafové morfismy a pravidla Na úvod bude třeba formálně definovat základní pojmy, které budeme požívat, jako grafy, pravidla, shody (levých stran) pravidel v grafech, zvaných redexy atd. Definice B.1. G := (V, E, lV, lE, s, t) je graf nad dvěma množinami jmen LV , LE přičemž: • V (G) := V a E(G) := E jsou konečné množiny vrcholů a hran, • lV (G) : V → LV a lE(G) : E → LE jsou jejich ohodnocovací funkce, • s(G) :E → V a t(G) :E → V přiřazuje každé hraně počátek a konec, • l(G) := lV(V) ∪ lE(E) budeme požívat jako zkratku pro všechny jména vrcholů a hran v grafu G. Dále budeme vypouštět přípony „V” a „E” ohodnocovacích funkcí, kdekoli je jasné z kontextu, o jakou množinu jde a budeme požívat zápis x ∈ G jako zkratku pro x ∈ V (G) ∨ x ∈ E(G). Prezentovaný datový model je příliš jednoduchý, aby byl v praxi použitelný. Potřebná rozšíření budou spočívat zejména v přidání atributů uzlů a hran. Zde se budeme držet co nejjednoduššího přístupu. Následující definice formalizuje zápis pravidel s kontextovými elementy. Ty jsou modelovány jako společné podgrafy levých a pravých stran pravidel. Definitce B.2. Pravidlo (grafové gramatiky) p := ( L , R) je dvojice grafů nad stejnými abecedami jmen vrcholů a hran LV a LE. Jeho levá strana lhs(p) := L a pravá strana rhs(p) := R mohou mít společný (kontextový) podgraf K jestliže jsou splněny následující podmínky: • • •
68
∀e ∈ E(K) ⇒ s(e) ∈ V (K) ∧ t(e) ∈ V (K) s E(K) := E(L) ∩ E(R) a V (K) :=V(L) ∩ V(R), tzn. počátky a konce společných hran jsou také společnými vrcholy L a R. ∀x ∈ L ∩ R ⇒ lL(x) = lR(x), tzn. kontextové elementy L a R se neliší s ohledem na jejich jména v L a R.
Úvod do grafových gramatik V dalším textu budeme často používat zkratky Xlhs(p) a Xrhs(p) pro všechny grafové elementy lhs(p) a rhs(p), které nejsou elementy jejich společného podgrafu common(p) = K. Pro definici aplikace prafidla grafové gramatiky p na daný graf G je třeba přesná definice shody levé strany p v daném grafu G. Takováto shoda, nazývaná redex, je speciální případ morfismu (mapování) mezi dvěma grafy nad stejnými abecedami jmen vrcholů a hran LV a LE. Definice B.3. Dvojice funkcí h := ( hV , hE) je grafový morfismus h : G → G′ z grafu G do grafu G′ s G := ( V, E, lV, lE, s, t ) a G′ := (V′, E′, l′V, l′E, s′, t′ ) jestliže: • hV : V → V′ a hE : E → E′ jsou úplná mapování, • ∀v ∈ V : l′V (hV (v)) = lV (v) ∧ ∀e ∈ E : l′E (hE(e)) = lE(e) • ∀e ∈ E : s′ (hE(e)) = hV (s(e)) ∧ ∀e ∈ E : t′ (hE(e)) = hV (t(e)).
V dalším textu budeme používat h(x) namísto hV(x) nebo hE(x), kde je význam jasný z kontextu. Nejobtížnější místo v definici je při rozhodnutí, které shody levé strany pravidla jsou možné a které ne. Je nutné zakázat situace, kdy se dva Xlhs elementy pravidla shodují se stejným elementem rodičovského grafu. To je účel tzv. identifikační podmínky v definici B.4. Další problém přichází s tím, jak naložit s hranami, jejichž vrcholy mají být smazány. Jedno řešení je smazat hranu, která sice nespadá do levé strany pravidla, také. To ovšem často vede k výsledkům, které nechceme. Proto je zavedena podmínka pro hrany se slepým koncem, která neumožní aplikaci pravidla za těchto podmínek. Tyto dvě podmínky zajistí, že aplikace pravidla grafové gramatiky je reverzibilní. Definice B.4. Morfismus h := (hV, hE : L → G) identifikuje redex L v G s ohledem na jiný graf R jestliže: • Podmínka pro slepé hrany: ∀v ∈ V (L) \ V (R); e ∈ E(G) : (s(e) =hV(v) ∨ t(e) =hV(v)) ⇒ ∃e′ ∈ E(L) \ E(R) :hE( e′ ) = e • Identifikační podmínka: ∀x ∈ L\R; x′ ∈ L : h(x) = h( x′ ) → x = x′ Morfismus, kde je splněna identifikační podmínka, ale enmusí být splněna podmínka pro slepé hrany, budeme nazývat potenciální redex.
B.1.3. Grafové gramatiky a jejich jazyky Během parsingu musíme hledat redexy pravých stran pravidel v daném vstupním grafu. Kontrola identifikační podmínky je možná bez uvažování o dalších aplikacích pravidla, ovšem pro podmínku slepých hran potřebujeme znalosti o existenci incidenčních hran, tj. musíme vědět, které hrany jsou již rozpoznány (smazány) inverzními aplikacemi jiných instancí pravidla. To vede k rozlišování redexů a potenciálních redexů v definici B.4. Algoritmus, který bude prezentován dále, je rozdělen do dvou fází. První fáze nemá dostatek informací pro podmínku slepých hran. Dokáže pouze nalézt množinu potenciálních (inverzních) aplikací pravidla, proto nazvaných potenciální instance pravidla. Druhá fáze je potom schopna eliminovat tyto aplikace, které porušují podmínku pro slepé hrany a vytváří podmnožinu instancí pravidla, které společně generují daný vstupní graf (pokud existuje). Definice B.5. Instance pravidla pravidla p := (L, R) je trojice pi := (p, h, h′ ) taková, že h : L → G a h′ : R → G′ definují aplikaci p na graf G s výsledkem G′, kde: • h je redex L v G s ohledem na R, • h′ je redex R v G′ s ohledem na L, • h | K = h′ | K, kde K je graf rozhraní L a R, a • G \ ( h(L\R) )=G′ \ (h′ (R\L) )
69
Syntaktická analýza grafových gramatik Aplikaci pravidla p na graf G s výsledkem G′ budeme zapisovat jako G ⇒p G′ . Potenciální instance pravidla je instance pravidla (p, h, h′ ), pro kterou jsou h a h′ potenciální redexy. Na základě definic pravidel a instancí pravidel (jejich aplikací) definujeme gramatiky a jejich jazyky: Definice B.6. Grafová gramatika gg je dvojice (A, P), kde A je nneprázdný vstupní graf (axiom), a P množina pravidel grafové gramatiky. Pro zjednodušení následujících definic bude vstupní graf A brán jako speciální případ pravidla s prázdnou levou stranou λ. Množina všech potenciálních pravidel gg je zkracována PI(gg). Definice B.7. Nechť gg := (A, P) je grafová gramatika. Její jazyk L(gg) je definován: G ∈ L(gg) :- A ⇒* G přičemž G ⇒ G′ :- ∃p ∈ P : G ⇒p G′ a ⇒* je reflexivní a tranzitivní uzávěr ⇒
B.1.4. Vrstvené grafové gramatiky a jejich jazyky Uvedené definice nejsou s ohledem na jména vrcholů a hran obvyklé. Až do této chvíle jsme nerozlišovali mezi terminálními a nonterminálními jmény a tedy ani mezi meziprodukty derivací a konečnými výsledky, tj. elementy generovaného jazyka. Důvodem je, že potřebujeme mnohem jemnější dekompozici našich abeced jmen do několika vrstev, než jen dvouvrstvé rozdělení na množinu terminálů a nonterminálů. Grafové gramatiky s libovolnými grafy levých a pravých stran pravidel jsou schopné generovat jazyky typu 0. Je ovšem známo, že pro tyto jazyky je problém příslušnosti nerozhodnutelný, proto musíme klást na gramatiky další omezení, abychom mohli vytvořit funkčí algoritmus pro parsing. To provedeme definováním určitého lexikografického řádu nad grafy založeného na dekompozici abeced jmen. Definice B.8. Dekompozice LV Ο LE = L0 ⊕ ... ⊕ Ln abeced jmen vrcholů a hran do n podmnožin je vrstvená množina jmen. V následujícím textu budeme používat funkci layer, která pro jakýkoli element grafu G vrací index vrstvy, do které jeho jméno patří, tj.: ∀x ∈ G : layer(x) = i :- l(x) ∈ Li. Definice B.9. S danou dekompozicí L0 Ο ... Ο Ln abeced jmen LV a LE může být gramatika gg dekomponována do několika podjazyků L0(gg), ... , Ln(gg) takových, že Li(gg) := { G ∈ L(gg) | l(G) ⊆ U j ≤ i Lj }. S použitím vrstev jmen můžeme definovat velmi obecnou třídu vrstvených grafových gramatik. Pro tyto gramatiky vytvoříme algoritmus, který řešíproblém příslušnosti a pro daný vstupní graf G vrací kladnou nebo zápornou odpověď spolu s jednou nebo všemi možnými derivacemi G. Definice B.10. Grafová gramatika gg := (A; P) se nazývá vrstvená grafová gramatika s ohledem na globální přiřazení vrstev L0, ... , Ln jejich jménům, jestliže ∀p := (L; R) ∈ P: • • • •
70
R je spojený graf. Levá strana L je neprázdná. Pravá strana R bez elementů K je neprázdná. L < R s ohledem na následující řád pro grafy: G < G′ :- ∃i : |G |i < | G′ |i ∧ ∀j < i: | G |j= | G′ |j kde | G |k je definován jako |{x ∈ G | layer(x) = k}|, tj. počet elementů v G, které mají jméno vrstvy Lk.
Algoritmus pro syntaktickou analýzu Tyto dodatečné restrikce nám garantují několik požadovaných vlastností, které budeme potřebovat pro parser: • Propojenost pravých stran nám dovoluje použít lineární vyhledávací plány pro pattern-matching, který může být proveden krok po kroku traverzováním hran. • Neprázdnost levých stran garantuje, že každá aplikace pravidla používá elementy grafu, které byly vytvořeny jinou aplikací, nebo které náleží do původního grafu. To znamená, že derivační historie grafu je vždy spojený acyklický graf. • Neprázdnost R\L implikuje, že nemusíme hádat, jak často bylo takové pravidlo aplikováno, aby byl vytvořen určitý graf. • Vrstvová podmínka definuje vztah mezi jmény vrcholů a hran, což zaručuje ukončení algoritmu. Není vždy úkolem designéra jazyka, aby přiřazoval jména vrstvám. Taková dekompozice je obvykle provedena automaticky aplikováním následujícího implicitního pravidla na jakékoli pravidlo p: layer(x) ≥ layer(y) pro jakékoli x ∈ Xlhs(p), a jakékoli y ∈ Xrhs(p). To určuje přiřazení jmen do vrstev za následujícího předpokladu, že layer(x) ≥ layer(y) ⇒ layer(x) > layer(y) kdykoli je to možné. Následující teorém je přímým důsledkem zavedení vrstev jmen v definici B.10. Teorém B.11. Element problém pro vrstvenou grafovou gramatiku gg je rozhodnutelný. Naivní parser, který aplikuje pravidla se zaměněnými levými a pravými stranami tak dlouho, jak je to možné a navrací se, když je to nutné, se ukončí a vždy produkuje správné rozhodnutí. Náčrt důkazu: Identifikační podmínka a podmínka pro slepé hrany zaručují, že aplikace pravidel jsou reverzibilní jednoduchým zaměněním jejich levých a pravých stran. Řád definovaný v B.10 zaručuje, že jakákoli sekvence reverzních aplikací pravidla, která začíná s konečným grafem, má konečnou délku. Dále, grafy konečné velikosti obsahují konečný počet potenciálních redexů pro konečný počet pravidel. Nakonec lze porovnat všechny mezivýsledky a konečné výsledky vypočtených sekvencí reverzních derivací s axiomem gramatiky (další podrobnosti viz [18]).
B.2. Algoritmus pro syntaktickou analýzu Zde navrhneme hlavní body alogitmu pro parsing. Podrobnosti o filtrovacích funkcích a důkazy správnosti lze nalézt v [18]. Alogoritmus musí řešit následující dvě úlohy: 1. Nalézt shody pravých stran pravidel a doplnit je na instance pravidla (reverzní aplikace pravidla). To je náročný proces, který pracuje na úrovni grafových elementů. 2. Převést vypočtené instance pravidel na derivace. V případě víceznačností se může stát, že zkonstruovaná instance pravidla není k žádnému užitku. Snaha řešit obě tyto otázky zároveň vede k velmi složitým algoritmům, které dokonce provádí mnoho výpočtů, které se později ukáží jako bezůčelné. Proto je výhodné rozdělit algoritmus na dvě fáze: •
•
•
Fáze bottom-up (zdola nahoru) hledá v grafu shody pravých stran pravidel. Při rozpoznání pravé strany je vytvořena instance pravidla pi, a nekontextové elementy jeho levé strany jsou přidány do grafu, ovšem nic se z něho nemaže. Fáze bottom-up potom generuje doplněk G vstupního grafu G. Tyto dodatky do grafu by mohly vést k rozpoznání dalších pravých stran. Výsledek bottom-up fáze je seznam všech objevených instancí pravidel PPI a doplněk grafu G. Vytvořené instance pravidel mezi sebou mají tzv. relace závislosti, jako např. relace nad(pi1, pi2), která znamená, že instance pravidla pi1 by se měla objevit v derivaci před pi2, nebo relace vylučuje (pi1, pi2), která znamená, že pi1 a pi2 se nesmí objevit ve stejné derivaci. Tyto relace mohou být vypočteny během bottom-up fáze. Fáze top-down (shora dolů) sestavuje podmnožinu PPI, která vytváří daný graf.
71
Syntaktická analýza grafových gramatik Všechna práce s grafovými elementy bude koncentrována ve fázi bottom-up. V této fázi nejde o navracení, víceznačnost a alternativní derivace, pouze generuje co nejvíce možných shod. Fáze top-down naopak nemusí brát v úvahu jednotlivé grafové elementy, pracuje pouze se závislostmi mezi instancemi pravidel a přetváří je do použitelných sekvencí derivací.
B.2.1. Fáze Bottom-Up Vyhledávací plány a značené předpisy Jedním z nejvážnějších problémů grafových přepisovacích systémů a parserů je uchovávání záznamu o všech potenciálních redexech v dané množině pravidel a inkrementálně je konstruovat když je graf modifikován. Použijeme metodu, která konstruuje lineární vyhledávací plán pro pravou stranu každého pravidla. Takový vyhledávací plán předurčuje pořadí, v jakém musí být redex konstruován. Definice B.12. Pravá strana pravidla p := (L, R) může být linearizována do vyhledávacího plánu, který je posloupností [ md0, md1, ..., mdn] direktiv shody vzorů (pattern matching). První položka posloupnosti, md0, je tvaru • < head(y : l) >: nalezni vrchol se jménem l a pojmenuj jej y, každá ze zbývajících položek mdi ,1 ≤ i ≤ n, má následující tvar: •
< z : x →k ( y : l ) > začni u již známého vrcholu x z R, následuj hranu se jménem k k cílovému vrcholu se jménem l, nazvi hranu z a cílový vrchol y, • < z : x ←k ( y : l ) > začni u již známého vrcholu x z R, následuj hranu se jménem k v opačném směru ke zdrojovému vrcholu se jménem l, nazvi hranu z a zdrojový vrchol y, nebo • < z : x →k y > vyšetři existenci hrany se jménem k mezi dvěma již známými vrcholy x a y z R, a nazvi ji z. Dále, left(md) vrací jnéno proměnné x shodující se direktivy md; pro počátek vyhledávacího plánu je nedefinována. Množina vyhledávacích plánů pravidla p je obecně značně velká a je obtížné v této množině nalézt „nejlepší” vyhledávací plán. Kvalita výběru záleží do určité míry na očekávaném počtu vrcholů a hran s určitým jménem v daném jazyce grafů. Budeme nyní předpoklát, že funkce SP(p) vybere přinejmenším „dobrý” vyhledávací plán. Definice takovéto funkce založená na nákladech pro vyhledávací plány je prezentována v [18]. Při konstrukci shody posunuje bottom-up fáze vyhledávacím plánem tzv. značku. Pro vrcholy a hrany nalevo od značky byla již shoda nalezena, pro ty napravo ještě nikoli. Může se stát, že hledaná hrana není v grafu přítomna. V takovém případě je značený předpis pozastaven a bude opět probuzen až při objevu slibné hrany. Definice B.13. Pětice dr := (p, M, i, h, s) je značený předpis s ohledem na daný graf G, který je již zkonstruovaným doplňkem vstupního grafu G, jestliže • p := ( L, R) je pravidlo vrstvené grafové gramatiky, • M := SP(p) je posloupnost [md0, ..., mdn] direktiv shody, • i, kde 1 ≤ i ≤ n, je pozice „značky” ve značeném předpisu. Direktivy shody md0 , ...,mdi-1 jsou již splněny, direktivy mdi , ..., mdn ještě musí být splněny, • h : R → G je částečně rozpoznaný redex z R v G s ohledem na L, který váže grafové elementy R do již objevených grafových elementů v G jako výsledek zpracování direktiv shod md0, ..., mdi-1 a • s reprezentuje stav značeného předpisu, který může být aktivní (active), nebo pozastavený (suspended). Jestliže je aktivní, mdi ještě musí být prověřena proti G. Je-li pozastaven, může být mdi splněna pouze po přidání příslušné hrany do G. Algoritmus ukládá instance značených předpisů jako dodatky vrcholů v G. Značený předpis (p, [md0, ..., mdn], i, h, s) bude přidán k vrcholu h (left(mdi)) z G, což je již známý vrchol x následující direktivy pro shodu vzorů mdi.
72
Algoritmus pro syntaktickou analýzu Algoritmy fáze bottom-up Tato fáze začíná přidáním počátečních značených předpisů všem shodujícím se vrcholům v rodičovském grafu. Pak opakovaně vybírá značený předpis k dalšímu postupu. Jestliže značka dosáhne konce vyhledávacího plánu, bylo příslušné pravidlo zcela rozpoznáno. Tak je generována instance pravidla a graf je rozšířen o elementy v L\R; nové vrcholy mohou dát vzniknout počátečním značeným předpisům, nové hrany mohou probudit pozastavené značené předpisy. To je opakováno tak dlouho, až nezbývají žádné aktivní značené předpisy. Algoritmus 1. (Bottom-Up Loop) Fáze bottom-up rozšiřuje shody pravých stran pravidel krok po kroku „pumpováním” značených předpisů skrz graf. Hlavní smyčka začíná voláním create-initialdotted-rules (algorimus 1.1). Poté je opakovaně zjišťováno, zda existují značené předpisy, které mohou rozšířit své shody a jestliže ano, je volána funkce proceed (algoritmus 1.2) s možným rozšířením již známé shody. Jestliže je výsledkem plně rozpoznané pravidlo, funkce proceed rozšíří graf, volá create-initial-dotted-rules pro všechny vytvořené vrcholy a volá reactivate-dotted-rules (algoritmus 1.3) pro všechny vytvořené hrany. function BottomUp-Loop(in G : graf) : množina PPI= G := G PPI := ∅ for every vrchol ∈ G do create-initial-dotted-rules(G, v) od while ∃ v ∈ G s dr = (p, M, i, h, active ) přidaným do v do M = [ ..., mdi , ... ] if mdi je tvaru < z : x →k ( y : l ) > then
for every hrana e : v →k′ v′ ∈ G do if k = k′ ∧ l = l( v′ ) then proceed (G, (p, M, i, h ∪ { z → e, y → v′ }, active )) fi od else if mdi je tvaru < z : x ←k ( y : l ) > for every hrana e : v ←k’ v′ ∈ G do if k = k′ ∧ l = l( v′ ) then proceed (G, (p, M, i, h ∪ { z → e, y → v′ }, active )) fi od else if mdi je tvaru < z : x →k y > then for every hrana e : v →k’ v′ ∈ G do if h(y) =v′ ∧ k=k′ then proceed(G, (p, M, i, h ∪ {z → e}, active )) fi od fi změň stav dr z active na suspended
od return PPI
Algoritmus 1.1. (Vytvoření počátečních značených předpisů) Jestliže je do grafu přidán nový vrchol v, je pro všechny přepisovací pravidla, které mají vyhledávací plán se shodujícím se počátkem, vytvořen počáteční značený předpis.
73
Syntaktická analýza grafových gramatik proc create-initial-dotted-rules(inout G : graf; in v : vrchol) = for every pravidlo p : (L; R) ∈ gg s vyhledávacím plánem M := [< head(y : l) >, ... ] = SP(p) do h := nedefinovaný (částečný) morfismus if l = l(v) then přidej (p, M, 1, h ∪ { y → v }, active ) k v v G fi od Algoritmus 1.2. (pokračuj ve značeném předpisu) Direktiva shody mdi byla splněna. Jestliže nebyla poslední z direktiv shod, je k vrcholu, ze kterého musí pokračovat direktiva mdi+1, připojen nový značený předpis. Jinak bylo příslušné pravidlo p zcela rozpoznáno a v tom případě musí být jeho levá strana přidána do grafu a může být dále zpracována. proc proceed (inout G : graf; in (p, M, i, h′, s)) : značený předpis = M = [md0, ..., mdn] if ∃ var → x; var’ → x ∈ h : var ≠ var’ ∧ var ∈ Xrhs(p) then return porušení identifikační podmínky fi if i < n then přidej (p, M, i + 1, h′, s) k h′ ( left( mdi+1)) else konstruuj morfismus h z h′ za dodržení podmínek definice B.5 if not inconsistent( (p, h, h′ ) ) then PPI := PPI ∪ {(p, h, h′ )} G := G ∪ h ( Xlhs(p)) for every vrchol v ∈ h ( V ( Xrhs(p))) do create-initial-dotted-rules(G; v) od for every hrana e ∈ h ( E ( Xrhs(p))) do reactivate-dotted-rules(G; e) od fi fi
Funkce inconsistent(p, h, h′ ) kontroluje, zda vytvářená instance pravidla závisí na instancích pravidel, které se navzájem vylučují. V tom případě může být ihned zrušena. Algoritmus 1.3. (reaktivace pozastavených značených předpisů) Jestliže do grafu přidáme novou hranu e z v do v′, může nastat případ, že existují pozastavené značené předpisy připojené v nebo v′, které mohou poračovat v procesu hledání shod vzorů (pattern matching) s touto hranou. Tyto předpisy je potřeba reaktivovat, přičemž je třeba zohledňovat pouze nové hrany, nikoli již prošlé hrany.
74
Algoritmus pro syntaktickou analýzu proc reactivate-dotted-rules(inout G : graf; in e : hrana) = v:= s(e) v′ := t(e) for every dr := (p, M, i, h, suspended ) připojený k v do M = [ ..., mdi , ... ] if mdi je tvaru < z : x →k ( y : l ) > ∧ k = l( e ) ∧ l = l( v′ ) then proceed(G, (p, M, i, h ∪ { z → e, y → v′ }, active )) else if mdi je tvaru < z : x →k y > ∧ v′ = h(y) ∧ k = l(e) then proceed(G, (p, M, i, h ∪ {z → e}, active )) fi od for every dr := (p, M, i, h, suspended ) připojený k v′ do M = [ ..., mdi, ... ] if mdi je tvaru < z : x ←k ( y : l) > ∧ k = l(e) ∧ l = l( v′ ) then proceed(G, (p, M, i, h ∪ { z → e, y → v }, active )) fi od
B.2.2. Závislosti mezi instancemi pravidel Instance pravidla reprezentuje aplikování pravidla do určité verze grafu a indikuje elementy grafu shodující se s oběma stranami pravidla. Protože operují na grafových elementech, závisí instance pravidel jedno na druhém. Abychom byli schopni rozhodnout o těchto závislostech, zavedeme relace nad, důsledek, vylučuje a vylučuje*. Definice B.14. Instance pravidla pi2 = (p2, h2, h′2 ) je důsledek (consequence) jiné instance pravidla pi1 = (p1, h1, h′1 ), nebo pi2 ∈ consequence(pi1), jestliže vykonání pi1 musí následovat vykonáním pi2, tj. pi2 ≠ pi1 a: • h′1 ( Xrhs(p1)) ∩ h2( Xlhs(p2)) ≠ ∅ ∨ (pi1 vytváří grafový element, který je smazán pi2) • h1( common(p1)) ∩ h2( Xlhs(p2)) ≠ ∅ (pi1 potřebuje kontextový element, který je smazán pi2). Tranzitivní a reflexivní uzávěr konsekvence je důsledek*. Definice B.15. Instance pravidla pi1 = (p1, h1, h′1 ) je nad (above) jinou instancí pravidla pi2 = (p2, h2, h′2 ), jestliže pi1 musí být vykonáno před pi2, tj. pi1 ≠ pi2 a: • pi2 ∈ consequence( pi1) ∨ • h′1 ( Xrhs(p1)) ∩ h2 ( common(p2)) ≠ ∅ ∨ (pi1 vytváří element, který pi2 potřebuje jako kontextový element). • ∃e ∈ h1(E(Xlhs(p1))), ∃v ∈ h2 (V (Xlhs(p2))) : s(e) = v ∨ t(e) = v (pi2 maže vrchol s incidenční hranou, která je smazána v pi1. V tom případě musí být pi1 aplikováno první, abychom předešli slepým hranám) Pro shrnutí, pi2 ∈ consequence(pi1) znamená, že po aplikování pi1 musí následovat aplikování pi2. To je důsledek faktu, že bottom-up fáze našeho parseru zaručí, že Xlhs-elementy instance pravidla nikdy nebudou Xlhs-elementy jiných instancí pravidel. Jakýkoli meziprodukt, který není částí výsledného generovaného grafu musí být proto snazán aplikováním jednoznačně definované instance pravidla. Závislost pi1 nad pi2 je slabší, říká, že jestliže jsou obě pravidla pi1 a pi2 aplikována, pak pi1 musí být aplikováno dříve.
75
Syntaktická analýza grafových gramatik Definice B.16. Instance pravidla pi1 = (p1, h1, h′1 ) vylučuje (excludes) jinou instanci pravidla pi2 = (p2, h2, h′2 ) (a naopak), jestliže obě instance závisí jedna na druhé, nebo jestliže přidávají stejné elementy do grafu, tj. pi1 ≠ pi2 a: pi1 excludes pi2 :( pi1 above pi2 ∧ pi2 above pi1 ) ∨ h′1 (Xrhs(p1)) ∩ h′2 (Xrhs(p2)) ≠ ∅.
Definice může být zobecněna i na vylučuje*: pi1 excludes* pi2 :∃ pi′1 ∈ consequence*(pi1), pi′2 ∈ consequence*(pi2) : pi′1 excludes pi′2 .
B.2.3. Fáze Top-Down Fáze top-down (shora dolů) obdrží celý soubor možných instancí pravidel PPI z fáze bottomup a vytvoří podmnožinu, která by generovala daný vstupní graf. V případě, že takové podmnožiny existují, vybere první z nich, na kterou narazí. Top-down fáze uchovává paralelně několik částečných derivací, nakonec vrací posloupnost instancí pravidel. Definice B.17. Trojice (Gc, APIc, EPIc) je částečná derivace pro G v kontextu všech možných instancí pravidel PPI. Gc je graf, tak jak byl dosud vytvořen aplikovanými instancemi pravidel v APIc. Historie derivace a instancí pravidel v APIc nemusí obsahovat určité instance pravidel, které jsou uchovány v EPIc. Množiny APIc a EPIc jsou obě podmnožinami původní množiny potenciálních instancí PPI. Budeme také používat zkratku PPIc pro PPIn(APIc ∪ EPIc), instance pravidel, které stále mohou být aplikovány. Hlavní idea fáze top-down je následující. Začíná s instancí pravidla pro axiom a rozšiřuje tuto množinu, aniž by byla porušena restrikce nad. Kdykoli se setká s instancí, která vylučuje jiné instance (bod výběru v algoritmu), rozdělí se na dvě derivace, každá pro jednu z možností. Tyto derivace jsou rozvíjeny v pseudoparalelním duchu s preferencí pro vývoj z hloubky. Algoritmus 2. (Top-Down Loop) Top-down fáze si zachovává seznam aktivních parciálních derivací v zásobníku. Instance pravidla může být aplikována v derivaci, jestliže je její lhs přítomna v Gc, nevzniknou slepé hrany a jestliže není vyloučena již aplikovanými instancemi pravidel. Abychom určili kandidáty instancí pravidel, které splňují všechny tyto podmínky, použijeme relace závislosti. Jestliže instance pravidla pi, které má být aplikováno, vylučuje* relaci s jakoukoli ještě neaplikovanou instancí pravidla, aplikace pi indikuje bod výběru v algoritmu. Proto ukládáme na zásobník dvě derivace: první, ve které je pi jednoduše vyloučeno, a další, ve které je pi aplikováno. To umožňuje pokračovat s alternativními derivacemi, jestliže se první výběr ukáže jako nesprávný.
Algoritmus používá funkci Cleanup, která odstraňuje instance nepoužitelných pravidel ihned jakmile je to možné. Dále je použita funkce Apply (algoritmus 2.1) k výpočtu efektu, jaký bude mít vybraná instance pravidla na danou derivaci.
76
Shrnutí function TopDown-Loop(in G : graf; in PPI : množina PPI) : množina PPI = D := emptystack for every pi := ((∅, A), h, h′ ) ∈ PPI do produkce axiomu D := push( Apply( pi, (∅, ∅, ∅)), D) od while ¬empty(D) do d := (Gc, APIc, EPIc) = top( D); D := pop( D) d := cleanup(d) Candidates := { pi ∈ PPIc | ∃ pi′ ∈ APIc : pi′ above pi ∧ ∀ pi′′ ∈ PPI : pi′′ above pi ! (pi′′ ∈ APIc ∨ pi′′ ∈ EPIc) } if Candidates = ∅ ∧ Gc = G then return APIc úspěšná derivace else if Candidates = ∅ then nic mrtvá derivace else if ∃ pi ∈ Candidates : ¬∃ pi′ ∈ PPIc : pi excludes* pi′ then D := push( Apply(pi, d), D) jednoduchý krok else vyber nějakou instanci pravidla pi z Candidates D := push((Gc, APIc, EPIc ∪ {pi}), D) bod výběru D := push( Apply(pi, d), D) fi od return ∅ úspěšná derivace nenalezena Algoritmus 2.1. (Apply) Vrací derivaci, která je rozšířením příchozí derivace d o aplikování instance pravidla pi. function Apply( in pi = (p, h, h′ ) :PPI; in d = (Gc, APIc, EPIc) ): derivation = Gn := ( Gc\h ( Xlhs(p))) ∪ h′ (Xrhs(p)) APIn := APIc ∪ {pi} EPIn := EPIc ∪ {pi′ ∈ PPI | pi excludes* pi′ } return (Gn, APIn, EPIn)
B.3. Shrnutí Grafy a grafové gramatiky jsou velmi dobrými nástroji pro reprezentování vizuálních jazyků a definici jejich syntaxe. Mohou být použity k vývoji (generování) syntaxí řízených editorů vizuálních jazyků. Přístup prezentovaný v předešlém algoritmu má mnoho výhod, které však mohou být splaceny v nejhorším případě až exponenciální časovou a prostorovou složitostí. Řešení zapouštěcích pravidel má také své slabosti a bude potřeba přejít na systém se zapouštěcími pravidly.
77
Syntaktická analýza grafových gramatik
78
Dodatek C. Obsah přiloženého CD-ROM
C.1. WWW prezentace CD-ROM obsahuje prezentaci grafiky založené na principech popisovaných v této práci. Je vytvořena ve formátu HTML pro World Wide Web a spouští se automaticky. Skládá se z informací o díle holandského grafika M. C. Eschera, obsahuje JAVA applet Escher Web Sketch, pomocí něhož lze vytvářet ornamenty a mozaikovou grafiku založenou na krystalografických grupách symetrie a lze si prohlédnout galerii obrázků, dokumentující možnosti a praktickou použitelnost tohoto nástroje. Další sekce je věnována programu Maya Imagination, jeho dokumentaci a obsahuje galerii objektů vytvořených tímto modulem (další informace viz níže). V třetí části lze prohlížet text této práce ve formátu PDF (Portable Document Format firmy Adobe). Ten lze číst i samostatně pomocí programu Acrobat Reader, je umístěn na CD v adresáři Text. Programy Adobe Acrobat Reader a Netscape Communicator, potřebné pro prohlížení prezentace, jsou na CD umístěny v adresáři Viewers ve verzích pro Windows a MacOS. O licenčních podmínkách pro jejich použití budete informováni při instalaci.
C.2. Maya Imagination Cílem projektu bylo vyvinout nástroj pro tvorbu ornamentů a obrazů specifikovaných symbolicky pomocí přepisovacího gramatického systému. Implementovaný vizuální přepisovací systém je určen pro tvorbu objektů (v další fázi i pro jejich animaci) pomocí definice jejich struktury, tj. základních grafických elementů a operací s nimi. Překonává tak tradiční konstruktivistické metody tvorby 3D scén a interakce uživatele s modelem. Popis Program má podobu plug-inu aplikace Maya 1.0 pro Windows NT a podporuje: · načtení souboru se specifikací přepisovací gramatiky · interpretaci gramatiky podle daných kritérií Plug-in je typu vstup-výstupního filtru, tj. rozšiřuje možnosti načítání, importu a ukládání scény. Ukládání není podporováno, implementovaný filtr pouze načítá speciální soubory s gramatikou (implicitní přípona *.mi).
79
Obsah přiloženého CD-ROM Soubor s gramatikou bude popsán níže. Po jeho načtení funkcemi File/Open, File/Import nebo přetažením na pracovní plochu programu Maya je zobrazeno dialogové okno. Tato jediná interakce s uživatelem slouží k zadání počtu iterací pro aplikování přepisovacích pravidel gramatiky. Formát MI Soubory s gramatikou (*.MI) jsou založeny na skriptovém jazyce MEL (Maya Embedded Language), který je schopen ovládat všechny fukce programu Maya. Formát však obsahuje jistá rozšíření pro daný účel. Kromě klíčového řetězce <MIM> na prvním řádku jsou to následující jazykové konstrukce: production
{ <MEL commands> } Konstrukce pro zápis přepisovacího pravidla. Je podporována pouze expanze jednoho nonterminálu , pravá strana pravidla není nijak omezena, tvoří ji jakékoli MEL příkazy, které mohou vytvářet libovolný počet objektů (terminálních), nebo dalších nonterminálů. nonterminal Příkaz pro zařazení aktuálně označeného objektu jako nonterminálu . iteration Proměnná obsahující číslo aktuální iterace (0 až počet zadaný v dialogu – 1). Příklad Gramatika Sierpinského jehlanu: <MIM>
identifikační řetězec souboru s gramatikou
production S {
pravidlo pro přepisování nonterminálu S původní objekt se zmenší na polovinu a čtyřikrát duplikuje tak, že čtyři kopiie vytvoří podstavu a nad ní uprostřed je kopie pátá
scale -r 0.5 0.5 0.5 move -r (-5.0/pow( 2, iteration)) 0 (-5.0/pow( 2, iteration)) nonterminal S duplicate move -r 0 0 (10.0/pow( 2, iteration)) nonterminal S duplicate move -r (10.0/pow( 2, iteration)) 0 (-10.0/pow( 2, iteration)) nonterminal S duplicate move -r 0 0 (10.0/pow( 2, iteration)) nonterminal S duplicate move -r (-5.0/pow( 2, iteration)) (10.0/pow( 2, iteration)) (-5.0/pow( 2, iteration)) nonterminal S }
80
Studijní materiál prováděcí část skriptu obsahuje pouze příkaz, který aktuálně označený objekt zařadí jako nonterminál S nonterminal S
Pozor: soubory MI jsou řádkově interpretované, takže rozdělení jakékoli konstrukce nebo MEL příkazu na více řádků není vhodné
Obr. C.1. Pracovní procha programu Maya s vygenerovaným jehlanem. Základním objektem byl jehlan s poměry stran 1x1x2.
C.3. Studijní materiál Pro referenci CD obsahuje archiv dokumentů, týkajících se této práce, které lze použít jako další studijní materiál. V tomto archivu jsou mnohé z prací uvedených v oddíle Literatura. Jedná se o elektronickou podobu textů ve formátu PDF pocházející z WWW a ukázkové implementace týkající se problematiky. Jsou to zejména texty z holandské univerzity v Leidenu, zabývající se syntaktickou analýzou grafových gramatik, vizuálními databázemi a syntaxí řízenými editory (včetně generování takovýchto editorů z jejich syntaxe). Dále jsou to práce J. Simonea např. o vizuální podobnosti ad., dokumentace německého projektu MoCA (Movie Contents Analysis) o struktuře videa, je přiložen kód a zdrojový text JAVA appletu Escher Web Sketch a dokumentace formátu VRML Moving Worlds.
81
Obsah přiloženého CD-ROM
82
Literatura
[1] Peirce Ch.: Collected Papers. New York,1931 [2] Ogden C. Ch., Richards I. A.: The Meaning of Meaning. New York, 1923 [3] Morris, Ch.: Foundations of the Theory of Signs. Chicago, 1938 [4] McLuhan M.: Jak rozumět médiím: Extenze člověka. Odeon Praha, 1991 [5] Jacobi J.: Psychologie C. G. Junga. Psychoanalytické nakladatelství Praha, 1993 [6] Jung C. G.: Analytická psychologie její teorie a praxe. Academia Praha, 1993 [7] Morris, Ch.: Aesthetics and the Theory of Signs. Chicago, 1939 [8] Baudrillard, Jean: Praecessio Simulacrorum. Host, 1994 [9] Pavel Skopal: Posthistorie psaná obrazem. Biograph 3-4/1998, Biograph, občanské sdružení Brno, 1998 [10] Flusser, V.: Moc Obrazu. Výtvarné umění 3-4, 1996 [11] Kotek Z., Vysoký P., Zdráhal Z.: Kybernetika. SNTL Praha, 1990 [12] Novák M. a kol.: Umělé neuronové sítě - teorie a aplikace. C. H. Beck Praha, 1998 [13] Gruska J.: Foundations of Computing. International Thomson Publ., 1997 [14] Molnár L., Češka M., Melichar B.: Gramatiky a jazyky. Alfa SNTL, 1987 [15] Bense M.: Semiotische Ästhetik und ihre Semiosen. in: Zs. für Literaturwissenschaft und Linguistik 4, 1974 [16] Haarslev V. (ed): Proceedings 11th IEEE Symp. on Visual Languages - VL’95. IEEE Computer Society Press, 1995 [17] Rekers J., Schürr A.: Defining and Parsing Visual Languages with Layered Graph Grammars. Technická zpráva 96-09, Leiden University, Nizozemsko, 1996. [18] Rekers J., Schürr A.: A parsing algorithm for context-sensitive graph grammars. Technická zpráva 95-05, Leiden University, Nizozemsko, 1995. [19] Bunke H.: Graph Grammars as a Generative Tool in Image Understanding. Lecture notes in computer science, 153, Springer Verlag, 1983 [20] Schattschneider, D.: Visions of Symmetry: Notebooks, Periodic Drawings & Related Work of M. C. Escher. W. H. Freeman & Company, 1990 [21] Habel A., Kreowski H. J., Taubenberger S.: Collages and Patterns Generated by Hyperedge Replacement. Languages of Design, Elsevier, 1, 125 – 145, 1993
83
Literatura [22] Grabska E., Hliniak G.: Graphic Prints Design Using Graph Grammars. Machine Graphics & Vision, 7(1/2), 1998 [23] Branki N. E., Grabska E. J.: The Coup d’Oeil: A Realization Scheme For Emergent Forms In Design. Machine Graphics & Vision, 3(1/2), 1994 [24] Grabska, Ewa: Theoretical concepts of graphical modelling, part one: Realization of CPgraphs. Machine Graphics & Vision, 2(1), 1993 [25] Grabska, Ewa: Theoretical concepts of graphical modelling, part two: CP-graph Grammars and Languages. Machine Graphics & Vision, 2(2), 1993 [26] Prusinkiewicz P., Lindenmayer A.: The Algorithmic Beauty of Plants. Springer-Verlag, NY, 1990 [27] Branki N. E., Edmonds E. A., Jones R. M.: A study of socially shared cognition in design. Environment and Planning B, Special Edition on User Modelling and Cognition, Gero and Purcell, 30, 1993 [28] Gero J. S.: Creativity, emergence and evolution in design. Preprint of the Second Int. RoundTable Conference of Computational Models of Creative Design, 1992 [29] Grabska E.: Design Spaces And Aesthetic Measure, Environmental Design, Aesthetic Quality and Information Technology. Focus Symposium Proc., Baden-Baden, 1992 [30] Birkhoff G.D.: Aesthetic Measure. Cambridge Massachusetts’ University Press, 1943 [31] Bielecki A., Róg M.: Aesthetic Measure of Fractals Consisting of Line Segments. Machine Graphics and Vision, vol. 3 no. 3, 1994 [32] Grabska E., Pospiech B.: Toward an Aesthetic Measure of Fractals. Machine Graphics and Vision, vol. 1 no. 1/2, 1992 [33] Escher M. C.: The Graphic Work. Benedikt Taschen Verlag, Köln, 1992 [34] Pryluck C., Teddlie C., Sands R.: Meaning in Film/Video: Order, Time and Ambiguity. J. Broadcasting 26, pp. 685-695, 1982 [35] Lienhart R.: VisualGREP: A Systematic Method to Compare and Retrieve Video Sequences, Mannheim University, 1997 [36] Lienhart R., Pfeiffer S., Effelsberg W.: Video Abstracting, Communications of ACM Vol. 40, No. 12, 1997 [37] Nack F., Parkes A.: The Application of Video Semantics and Theme Representation in Automated Video Editing. Multimedia Tools and Applications, Vol. 4, No. 1, pp. 57-83, 1997 [38] Pfeiffer S., Lienhart R., Fischer S., Effelsberg W.: Abstracting Digital Movies Automatically. In J. Visual Communication and Image Representation, Vol. 7, No. 4, pp. 345-353, 1996 [39] Christel M., Kanade T., Mauldin M., Reddy R., Sirbu M., Stevens S., Wactlar H.: Informedia Digital Video Library. Communications of the ACM, 38(4):57-58, 1995 [40] Poynton C. A.: A Technical Introduction to Digital Video. John Wiley & Sons, Inc., 1996 [41] Pass G., Zabih R., Miller J.: Comparing Images Using Color Coherence Vectors. Proc. ACM Multimedia 96, Boston, MA, s. 65-73, 1996 [42] Zabih R., Miller J., Mai K.: A Feature-Based Algorithm for Detecting and Classifying Scene Breaks. Proc. ACM Multimedia 95, San Francisco, CA, s. 189-200, 1995 [43] Bordwell D., Thompson K.: Film Art: An Introduction. 4th ed. McGraw-Hill, New York, 1993 [44] Santini S., Jain R.: Similarity Matching. submitted to: IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996
84
Literatura [45] Hampapur A., Gupta A., Horowitz B., Shu C.-F., Fuller C., Bach J. R., Gorkani M., Jain R. C.: Virage Video Engine. Proc. SPIE Vol. 3022, Storage and Retrieval for Image and Video Databases V, Ishwar K. Sethi; Ramesh C. Jain; Eds., s. 188-198, 1997. [46] Pentland A., Picard R. W., Sclaroff S.: Photobook: Content-Based Manipulation on Image Databases. Inter-national Journal of Computer Vision, Vol. 18, No. 3, s. 323-254, 1996. [47] Lin W. C., Fu K. S.: A Syntactic Approach to 3D Object Reprezentation. IEEE Trans. PAMI, 6(3), 1984 [48] Lin W. C., Fu K. S.: A Syntactic Approach to 3D Object Recognition. IEEE Trans. SMC, 16(3), 1986 [49] Gonzales, Rafael C.: Digital Image Processing. Addison-Wesley Publishing Co., 1987 [50] Chen C. H., Pan L. F., Wang P. S. P.: Handbook of Pattern Recognition & Computer Vision. World Scientific Publ. Co., 1993 [51] Hlaváč Václav, Šonka Milan: Počítačové vidění. Grada a. s. Praha, 1992 [52] Horn B., Minsky M., Shirai Y., Waltz D., Winston P. H.: The Psychology Of Computer Vision. McGraw-Hill, 1975 [53] Ferrucci F., Tortora G., Tucci M., Vitellio G.: A predictive parser for visual languages specified by relation grammars. In Proceedings 10th IEEE Symposium on Visual Languages – VL’94, s. 245–252, 1994. [54] Golin E.: A method for the specification and parsing of visual languages. PhD thesis, Brown University, 1991. [55] Golin E.: Parsing visual languages with picture layout grammars. Journal of Visual Languages and Computing, (4):371–394, 1991 [56] Pfaltz J., Rosenfeld A.: Web grammars. In Int. Joint Confenence on Artificial Intelligence, s. 609–619, 1969 [57] Schneider H. J.: Chomsky-Systeme für partielle Ordnungen. Technical Report 3,3, Institut für Mathematische Maschinen und Datenverarbeitung, Erlangen, 1970 [58] Gips J.: Shape Grammars And Their Uses, Artificial Perception, Shape generation And Computer Aesthetic. Birkhäuser Verlag, 1975 [59] Maurer H. A., Rozenberg G., Welzl E.: Using String Languages to Describe Picture Languages. Information and Control, 54, 1982 [60] Finke R.: Creative Imagery. Lawrence Erlbaum, 1990 [61] Henckmann W., Lotter K.: Estetický slovník. Svoboda Praha, 1995 [62] Douglas R. Hofstadter: Gödel, Escher, Bach: An eternal golden braid. Basic Books New York, 1979 [63] Ostromoukhov V.: Mathematical Tools for Computer-Generated Ornamental Patterns. Ecole Polytechnique Fédérale, Lausanne, Switzerland, 1997 [64] Hahn T. (ed.): International Tables for Crystallography, Vol. A. Reidl Publishing Co., 1995
85
