Univerzita Karlova v Praze Matematicko-fyzikální fakulta
DIPLOMOVÁ PRÁCE
Daniel Lessner Samoorganizace a morphing Katedra teoretické informatiky a matematické logiky
Vedoucí diplomové práce: doc. RNDr. Iveta Mrázová, CSc. Studijní program: Informatika, Teoretická informatika
2009
Na tomto míst¥ bych rád pod¥koval vedoucí práce doc. RNDr. Ivet¥ Mrázové, CSc. za odborné vedení, trp¥livost a cenné rady. Dále d¥kuji Lucii Diblíkové za pomoc a podporu zejména p°i dokon£ování práce, Petru Mou£kovi za udrºování motivace a v neposlední °ad¥ mamince za to, ºe mne b¥hem práce stále je²t¥ ºivila.
Prohla²uji, ºe jsem svou diplomovou práci napsal samostatn¥ a výhradn¥ s pouºitím citovaných pramen·. Souhlasím se zap·j£ováním práce a jejím zve°ej¬ováním. V Praze dne 7. 8. 2009
Daniel Lessner
2
Obsah 1
2
Úvod 1.1
Morphing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2
Samoorganizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3
Slibná kombinace morphingu a samoorganizace
1.4
len¥ní textu
. . . . . . . . . . . . . . .
10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
Morphing: úvod do problému
12
2.1
Uvedení do problému . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.2
Obecný p°ístup k °e²ení
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Základní algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2.1 2.3
2.4
3
8
Hodnotící kritéria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.1
16
Interakce s uºivatelem
. . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1.1
Výstiºnost °ídicích objekt·
2.3.1.2
P°edvídatelnost chování
. . . . . . . . . . . . . . . . .
16
. . . . . . . . . . . . . . . . . . .
17
2.3.1.3
Sloºitost my²lenkového modelu
. . . . . . . . . . . . . . .
17
2.3.2
Vlastnosti morphingu . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.3.3
asová sloºitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Varianty morphingu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.4.1
Parametrizace technik
. . . . . . . . . . . . . . . . . . . . . . . . .
19
2.4.2
Specializace
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.4.3
Zobecn¥ní . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Morphing: metody °e²ení
23
3.1
Sí´ový morphing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2
Úse£kový morphing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.3
Interpolace korespondencí
. . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.4
Minimáln¥ pracný morphing . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.5
Minimalizace energie
35
3.6
Víceúrov¬ová volná deformace . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.7
Záv¥re£né srovnání
36
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4
Samoorganizace
38
4.1
Kohonenova samoorganiza£ní mapa . . . . . . . . . . . . . . . . . . . . . .
39
4.1.1
Pouºití SOM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.1.2
Struktura SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.1.3
Vybavování SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.1.4
U£ení SOM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.1.5
Dopl¬ující poznámky . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Rostoucí samoorganiza£ní mapa . . . . . . . . . . . . . . . . . . . . . . . .
44
4.2
4.3
4.4
4.5
5
6
U£ení GSOM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.2.2
Srovnání se SOM . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
Rostoucí neuronový plyn . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.3.1
U£ení GNG
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.3.2
Srovnání se SOM a s GSOM . . . . . . . . . . . . . . . . . . . . . .
51
Rozvíjející se samoorganiza£ní strom
. . . . . . . . . . . . . . . . . . . . .
52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.4.1
Vybavování ET
4.4.2
U£ení ET
4.4.3
Srovnání s p°edchozími modely
Záv¥re£né poznámky
. . . . . . . . . . . . . . . . . . . .
56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
Moºnosti aplikace samoorganiza£ních technik na morphing
59
5.1
59
Související výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1
Morphing obli£ej· . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.1.2
Morphing t¥les
60
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2
Co lze o£ekávat a co nikoliv
5.3
N¥které nad¥jné souvislosti samoorganizace a morphingu
. . . . . . . . . .
62
5.4
SOM a hledání významných bod· obrazu . . . . . . . . . . . . . . . . . . .
63
5.5
Vyuºití nalezených významných bod· pro hledání korespondencí . . . . . .
65
5.6
Dal²í varianty aplikace samoorganizace na morphing . . . . . . . . . . . . .
67
. . . . . . . . . . . . . . . . . . . . . . . . . .
Zhodnocení implementovaných metod 6.1
7
4.2.1
61
69
Poznámky k implementaci
. . . . . . . . . . . . . . . . . . . . . . . . . . .
69
6.1.1
Trénovací mnoºina
. . . . . . . . . . . . . . . . . . . . . . . . . . .
70
6.1.2
SOM a u£ení
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
6.2
Testování
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
6.3
Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
6.4
Zhodnocení
74
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Záv¥r
77
Literatura
79
4
Seznam algoritm· 2.1
Schéma algoritmu morphingu
. . . . . . . . . . . . . . . . . . . . . . . . .
15
3.1
Minimáln¥ pracný morphing . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.1
U£ení Kohonenovy samoorganiza£ní mapy
. . . . . . . . . . . . . . . . . .
42
4.2
U£ení GSOM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.3
U£ení GNG
4.4
Vybavování ET
4.5
U£ení ET
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5
Seznam obrázk· 2.1
P°íklad konkrétního obrázku - vlajka výcarska
3.1
Schéma nalezení zdrojového bodu v úse£kovém warpingu
3.2
Ilustrace moºností interpolace poloh ²ipek
3.3
Ilustrace warpingu jako interpolace zobrazení korespondencí
. . . . . . . .
30
3.4
P°íklad t°etí série dislokací uzlu v síti stupn¥ 2 . . . . . . . . . . . . . . . .
33
4.1
Ilustrace vybavování ET
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
5.1
Ukázka rozloºení vzor· . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
5.2
Ilustrace m¥°ení vzdálenosti s pam¥tí . . . . . . . . . . . . . . . . . . . . .
66
6.1
Ukázka zm¥ny £tverce na kruh metodou minimalizace práce 9x9
. . . . . .
72
6.2
Ukázka zm¥ny £tverce na kruh pomocí SOM 9x9 . . . . . . . . . . . . . . .
72
6.3
Ukázka zm¥ny £tverce na kruh pomocí SOM 5x5 . . . . . . . . . . . . . . .
73
6.4
Ukázka zm¥ny maliny na ostruºinu pomocí SOM 9x9
. . . . . . . . . . . .
73
6.5
Ukázka zm¥ny výrazu tvá°e pomocí SOM 13x11
. . . . . . . . . . . . . . .
73
6
. . . . . . . . . . . . . . .
12
. . . . . . . . . .
26
. . . . . . . . . . . . . . . . . .
27
Samoorganizace a morphing Daniel Lessner Katedra (ústav): Katedra teoretické informatiky a matematické logiky Vedoucí bakalá°ské práce: doc. RNDr. Iveta Mrázová, CSc. e-mail vedoucího: Iveta.Mrazova@m.cuni.cz Název práce:
Autor:
Morphing je známý lmový vizuální efekt. Spo£ívá v plynulé p°em¥n¥ jednoho obrazu na jiný. Tak se nap°íklad postava lmu zm¥ní v medv¥da. Realizace takového efektu vyºaduje pe£livou, soust°ed¥nou a drahou práci animátora. Vývoj nástroj· a metod k °e²ení problém· srovnatelných aspo¬ £áste£n¥ s lidským intelektem je p°edm¥tem oboru um¥lá inteligence. Systémy fungující zcela bez ú£asti £lov¥ka pracují £asto se samoorganizací. Tak se nazývá jev, kdy systém samovoln¥ vykazuje komplexn¥j²í chování, neº odpovídá moºnostem jeho jednotlivých £ástí. Tato práce zkoumá moºnosti nasazení samoorganiza£ních metod um¥lé inteligence v morphingu s cílem omezit nutnost lidské asistence. Sou£ástí práce jsou informace o n¥kolika navrºených postupech a výsledky experiment· s nejúsp¥²n¥j²ím z nich. Ukazuje se, ºe p°i spln¥ní ur£itých podmínek lze dosáhnout kvalitních výsledk· zcela samo£inn¥. Abstrakt:
Klí£ová slova:
samoorganizace, morphing obrázk·, u£ení bez u£itele, po£íta£ová gra ka
Self-organisation and Morphing Author: Daniel Lessner Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: doc. RNDr. Iveta Mrázová, CSc. Supervisor's e-mail address: Iveta.Mrazova@m.cuni.cz Title:
Morphing is a well-known visual eect. It is based on a uent transition of one image into another one, metamorphosis of a movie character into a bear is a possible example. Realization of such an eect requires accurate, concentrated and expensive eort of an animator. Development of tools and methods for problem solving comparable with human intelect is the subject of arti tial intelligence. Systems working with no human adjustments are often based on self-organisation. Self-organisation of a system is the appearance of complex behavior that isolated parts of the system couldn't reach. This thesis examines possibilities of application of self-organisational methods of arti tial intelligence in morphing with the goal of reduction of the human assistence. The thesis includes information about some drafted techniques and results of experiments with the most successful technique. Experiments imply that it is possible to reach good results without human assistance if certain conditions are met. Keywords: image morphing, self-organization, unsupervised learning, po£íta£ová gra ka Abstract:
7
Kapitola 1 Úvod 1.1
Morphing
Morphing je známý efekt plynulé zm¥ny jednoho obrázku na druhý. Nejznám¥j²í aplikace souvisí s lmovými triky. Pokud prom¥nu na plátn¥ neprovází st°ih nebo kou° a divák vidí její skute£ný , pozvolný pr·b¥h, dívá se na morphing. Vizuáln¥ zajímavá prom¥na je zpravidla nadp°irozeného p·vodu, proto se lze s morphingem nej£ast¥ji setkat v pohádkách, fantasy nebo sci- lmech. Mezi dal²í aplikace pat°í vizualizace dat morphing umoº¬uje doplnit p°ibliºnou situaci mezi sousedními °ezy objektem získanými nap°. z
tomografu.
Vstupem je po£áte£ní a koncový obrázek, výstupem pak sekvence zobrazující postupnou zm¥nu jednoho snímku na druhý. P°ímo£arým °e²ením je prosté postupné prolnutí obou snímk·. Vstupní obrázky se ov²em pravd¥podobn¥ budou li²it p°íli², a proto bude prost°ední snímek výsledné posloupnosti vypadat pom¥rn¥ nev¥rohodn¥. P°i zm¥n¥ jednoho obli£eje na druhý se objeví nap°íklad polopr·hledná o na nebo odstávající u²i. O£ekávaným výsledkem by bylo postupné p°ilnutí u²í k hlav¥, nikoliv jejich zmizení (nebo naopak zhmotn¥ní). Tento problém se °e²í p°idáním dal²ích informací o poºadované transformaci. Je t°eba vyzna£it vzájemn¥ korespondující oblasti na obou obrázcích. S jejich pomocí uº p·jde do morphingu zahrnout i tvarové zm¥ny objekt· na vstupních obrázcích. Ur£ení t¥chto korespondencí je práce pro uºivatele, zpravidla animátora. Existující konkrétní postupy p°ehledov¥ shrnuje £lánek [34]. Základním postupem je sí´ový morphing. Ten na vstupu krom¥ dvou obrázk· dostává navíc dv¥ r·zn¥ tvarované m°íºky se stejnou, obvykle pravoúhelníkovou topologií. Uzly m°íºky animátor umístí do význa£ných míst obrázk·. Významná místa po£áte£ního obrázku se pak b¥hem morphingu zm¥ní na významná místa koncového obrázku odpovídající stejnému uzlu sít¥. Dal²í metody rozvíjejí tento základní p°ístup a omezují jeho hlavní nevýhody. Úse£kový morphing pracuje s úse£kami a oblastmi jejich vlivu [3]. Je výrazov¥ siln¥j²í neº sí´ový morphing a animátorovi tolik nesvazuje ruce, na druhou stranu je výpo£etn¥ náro£n¥j²í a ob£as generuje neo£ekávané výsledky. Metoda interpolace korespondencí se na morphing dívá jako na interpolaci roztrou²ených dat [24]. Korespondence p°ijímá ve tvaru úse£ek, k°ivek i bod·. Metoda minimalizace
8
energie na morphing aplikuje fyzikální model, ve kterém se snaºí minimalizovat hodnotu energetické funkce [14]. Její výhodou je zamezení vzniku p°ekryv· p°i deformaci obrázk·, její nevýhodou je rychlost. Metoda víceúrov¬ové volné deformace pracuje iterativn¥, aby morphing bez deformací na²la rychleji [13]. Metoda minimalizace práce [7] je pro ú£ely této práce zdaleka nejpodstatn¥j²í. Jako jediná z uvedených totiº funguje do zna£né míry samo£inn¥. Potenciální transformace (pohyb obrazového bodu, zm¥na barvy) hodnotí mnoºstvím pot°ebné práce. Ze v²ech moºností zm¥ny po£áte£ního obrázku na koncový pak vybírá tu nejmén¥ náro£nou. Tato metoda p°edpokládá zna£nou podobnost vstupních snímk· a je výpo£etn¥ pom¥rn¥ náro£ná, na druhou stranu se mnohdy obejde zcela bez pomoci uºivatele. Uvedené obecné metody dob°e plní sv·j ú£el a v oblasti morphingu obrázk· je v
po-
sledních letech klid. Probíhající výzkum se soust°edí na speciální aplikace, kde lze p°ijímat siln¥j²í p°edpoklady. Hlavní výzvou z·stává samo£inný morphing [14].
1.2
Samoorganizace
V mnoha rozli£ných oborech byl pozorován paradoxní jev nazvaný samoorganizace. Jde o ne£ekan¥ komplexní chování systému sloºeného z jednoduchých £ástí. P°itom nedochází k ºádnému cílenému °ízení zvn¥j²ku. Mezi zásadní podmínky pat°í otev°enost systému (vým¥na hmoty, energie nebo entropie s okolím), bohaté interakce mezi prvky systému a rovnováha pozitivní a negativní zp¥tné vazby. Uvedený popis je tak abstraktní práv¥ kv·li ²í°i oblastí, v nichº se samoorganizace objevuje. Nejbohat²í je v tomto sm¥ru patrn¥ fyzika a chemie, dal²í p°íklady lze najít v biologii, sociologii nebo ekonomii, a samoz°ejm¥ v informatice, zejména v um¥lé inteligenci. Jednou z nejznám¥j²ích metod um¥lé inteligence vyuºívajících samoorganizaci jsou Kohonenovy samoorganiza£ní mapy [11]. Jde o druh neuronové sít¥, která slouºí nej£ast¥ji k rozpoznávání vzor· nebo k redukci dimenze vstupních dat. Klí£ovou sou£ástí sít¥ je vrstva výstupních neuron·. Mezi sousedními neurony existují vazby, z celkového pohledu tedy výstupní vrstva vypadá t°eba jako (nepravidelná) dvourozm¥rná m°íºka. Zásadní vlastnost mapy je, ºe po p°edloºení vzoru se aktivuje práv¥ jeden, v jistém smyslu nejpodobn¥j²í neuron. Jinými slovy kaºdý neuron reprezentuje skupinu vzor·, které jsou mu nejbliº²í. Navíc neurony, které spolu sousedí v m°íºce, reprezentují podobné vzory. Samoorganizace Kohonenových map spo£ívá ve zp·sobu, jakým se neurony rozmís´ují v prostoru. Aniº by n¥kdo p°edem znal prostorovou strukturu mnoºiny vzor·, natoº jejich rozd¥lení na vhodné skupiny, neurony v map¥ se postupn¥ samovoln¥ rozmístí tak, aby mnoºinu vzor· vhodn¥ reprezentovaly. K tomuto ú£elu slouºí jiº zmín¥né vazby mezi neurony, základními stavebními prvky celého systému.
9
1.3
Slibná kombinace morphingu a samoorganizace
Na jedné stran¥ je tedy problém plynulé zm¥ny jednoho obrázku na jiný a pot°eba dal²ího uºivatelského vstupu pro vyzna£ení korespondencí. Na druhé stran¥ jsou metody, které bez vn¥j²í pomoci p°izp·sobují rozmíst¥ní reprezentativních bod· v prostoru. To by mohlo jít zkombinovat. Jádrem této práce je práv¥ zkoumání moºností aplikace samoorganiza£ních metod na problém morphingu. Jako jedna z p°ímo£arých moºností se jeví ztotoºn¥ní °ídicí sít¥ sí´ového morphingu a výstupní vrstvy Kohonenovy mapy. P°edkládané vzory mohou být obrazové body po£áte£ního obrázku. Vhodná de nice pojmu vzdálenosti p°im¥je sí´ umístit výstupní neurony na reprezentativní místa obrázku. Tím by vznikla první m°íºka. Potom se p°edkládáním nové mnoºiny vzor· obrazových bod· z koncového obrázku m·ºe m°íºka op¥t samovoln¥ p°izp·sobit a vyhledat nová reprezentativní místa, blízká t¥m z prvního obrázku. Tím by vznikla i druhá pot°ebná m°íºka a sí´ový morphing by uº mohl vygenerovat výslednou sekvenci snímk· bez zásah· £lov¥ka. P°ínos samoorganizace uº byl pro morphing a p°íbuzné problémy vyuºit v r·zných speciálních p°ípadech, jako je nap°. morphing a animace obli£ej· [29, 9], nefotorealistický morphing [10] nebo morphing 3D t¥les [25]. Tento letmý ná£rt nechává mnoºství otázek otev°ených, dal²í otázky vyvolává jeho hlub²í zvaºování. Nezbytný je vhodný zp·sob m¥°ení vzdálenosti vzor· a neuron·. Je t°eba si poradit s volbou hustoty m°íºky a nastavením její plasticity. Tato práce se zabývá práv¥ °e²ením podobných otázek. Jednu z nad¥jných cest potom experimentáln¥ prov¥°uje a porovnává s jedinou známou samo£innou metodou morphingu (minimalizace práce). Jednotlivé metody hodnotíme podle p°edem ur£ených kritérií. Hodnocení kvality samovoln¥ vzniklých výstupních sekvencí jako takových je zna£n¥ individuální. Zadáním je vytvo°it sekvenci p°irozené zm¥ny. Na p°irozenost konkrétní zm¥ny bude ov²em kaºdý mít sv·j vlastní, subjektivní názor. To souvisí s dal²í vlastností, kterou lze od samoorganizovaného morphingu p°irozen¥ £ekat. Samovolné hledání korespondencí v obrázcích m·ºe divákovi ukázat zcela nové, nikým ne£ekané souvislosti. Lidský animátor by patrn¥ dal p°ednost jiným. Vy°e²ení hlavní výzvy morphingu tedy st¥ºí kdy povede k nahrazení uºivatel·, ti mají £asto o výsledné sekvenci vlastní p°esnou a konkrétní p°edstavu. Spí² jde o roz²í°ení tv·r£ího týmu o nevyzpytatelného, ale moºná o to zajímav¥j²ího £lena.
1.4
len¥ní textu
Kapitola 2 se podrobn¥ v¥nuje problému morphingu a jeho r·zným variantám. T°etí kapitola této práce £tená°e seznamuje se známými metodami jeho °e²ení. Pro ú£ely této práce je nejpodstatn¥j²í metoda sí´ového morphingu (oddíl 3.1) a metoda minimáln¥ pracného morphingu (oddíl 3.4). tvrtá kapitola pojednává o samoorganizaci, samoorgniza£ních mapách a jejich variantách a vylep²eních. Moºnosti vyuºití samoorganizace pro °e²ení morphingu diskutuje pátá
10
kapitola. está kapitola popisuje krátké experimenty s nejnad¥jn¥j²í z navrºených metod a uvádí a hodnotí jejich výsledky. Na²i metodu porovnáváme s metodou minimalizace práce. Sedmá kapitola celou práci shrnuje.
11
Kapitola 2 Morphing: úvod do problému Tato kapitola obsahuje zejména podrobný popis problému morphingu a zavedení souvisejících pojm·. erpá p°itom p°edev²ím z [8, 33, 36]. Dále jsou diskutována a ur£ena kritéria, podle nichº budeme v této práci hodnotit jednotlivé metody °e²ení morphingu. Na konci kapitoly je morphing zasazen do ²ir²ích souvislostí uvedením zajímavých variant a aplikací.
2.1
Uvedení do problému
Morphing obecn¥ znamená plynulou zm¥nu, hladký a p°irozený p°echod od jednoho objektu ke druhému. Obvykle je mín¥na v²eobecn¥ známá úloha plynulé zm¥ny jednoho obrázku na jiný. Morphingem obrázk· se zabývá i tato práce. Nej£ast¥j²í aplikace, se kterými se lze b¥ºn¥ setkat, nabízí lmový pr·mysl - nap°íklad prom¥ny Rumburaka v okn¥ na krkavce a zp¥t. Pojmem
obrazový bod
v této práci míníme vektor intenzit barevných kanál·. Není-li
°e£eno jinak, bude mít vektor t°i sloºky v celo£íselném rozsahu 0-255, p°edstavující jas £ervené, zelené a modré barvy v daném obrazovém bodu. P°edpokládáme tedy 24-bitovou barevnou hloubku a barevný model RGB. Pojmem
obrázek
pak míníme obdélníkovou ma-
tici obrazových bod·. Vyskytují-li se obrázky v za sebou jdoucí posloupnosti, odli²íme tuto skute£nost ozna£ením
snímek.
Vstupem morphingu je po£et snímk·
n
výsledné posloupnosti a dva obrázky o shod-
Obrázek 2.1: P°íklad konkrétního obrázku - vlajka výcarska
O=
(255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 255, 255) (255, 0, 0) (255, 0, 0) (255, 255, 255) (255, 255, 255) (255, 255, 255) (255, 0, 0) (255, 0, 0) (255, 255, 255) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0)
12
(255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0) (255, 0, 0)
ných rozm¥rech, po£áte£ní
Op
a koncový
Ok .
e²ením problému je taková posloupnost
snímk·, která zobrazuje plynulou zm¥nu z po£áte£ního obrázku na koncový. Jednotlivé
Ot ,
snímky posloupnosti budeme zna£it je práv¥ obrázek
Op
a obrázek
On
kde
t
je p°irozené £íslo od
je práv¥ obrázek
Ok .
Indexy
p
1
do
a
k
(xk , yk )
Obrázek
O1
budeme zna£it i
p°íslu²nost dal²ích struktur k po£áte£nímu a koncovému obrázku. Nap°. sou°adnice obrazového bodu po£áte£ního obrázku a
n.
(xp , yp )
budou
budou sou°adnice obrazového
bodu koncového obrázku. Z uvedeného plyne, ºe °e²ení konkrétní úlohy nebude nikdy jednozna£né. Pojem plynulosti totiº obvykle není nijak formáln¥ de nován, jde o £ist¥ subjektivní kritérium. Nap°íklad p°i zm¥n¥ nanuku na paroh bude n¥komu p°ipadat p°irozen¥j²í, kdyº jednotlivé par·ºky z nanuku vyra²í a dorostou jako v¥tve stromu, n¥komu zase, kdyº se od nanuku v plné délce od²t¥pí a postupn¥ ohnou. Výb¥r konkrétního °e²ení závisí p°edev²ím na ú£elu, kterému má posloupnost snímk· slouºit. Jiné budou poºadavky pro animaci kouzelné pohádkové prom¥ny, jiné pro ilustra£ní dopln¥ní chyb¥jících dat mezi jednotlivými snímky °ez· zkoumaným lidským orgánem. Jak uº jsme uvedli, p°i vyuºití morphingu v praxi stojí v první °ad¥ speciální lmové efekty. Jeden z prvních a zárove¬ slavných p°ípad· najdeme v záv¥ru lmu Indiana Jones a poslední k°íºová výprava (Indiana Jones and the Last Crusade)z roku 1989. Postava Waltera Donovana p°ed zraky divák· extrémn¥ rychle, ov²em plynule zestárne, zch°adne a doslova se obrátí v prach. Pojítkem mnoha sloºitých trik· (r·zné loutky pro r·zná stadia procesu, nezávislá práce s o£ima postavy apod.) je práv¥ po£íta£ový morphing. Krom¥ vytvá°ení podobných vizuálních efekt· se morphing ve lmu uplatní také p°i zm¥nách po£tu snímk· za sekundu. Pro zachování plynulosti vjemu nelze prost¥ jen n¥které snímky jednodu²e zdvojit nebo vynechat. Morphing v takovém p°ípad¥ m·ºe poslouºit pro hledání interpolací dvojic snímk· v poºadovaném okamºiku a pomoci tak získat chyb¥jící data pro novou frekvenci snímkování. Ze stejných d·vod· lze metody morphingu uplatnit také p°i kompresi videa. Z pohledu na výsledky morphingu jako na interpolaci mezi obrázky vychází dal²í zásadní aplikace mimo zábavní pr·mysl. Dva vstupní obrázky p°edstavují dva sousední °ezy n¥jakým objektem (nap°. snímky z tomografu nebo magnetické rezonance) a snímky výsledné posloupnosti nerozmístíme v £ase, nýbrº v prostoru mezi dva p·vodní °ezy. Uºivatel tak získá p°ibliºný pohled na jednu z
moºností, jak by mohl prostor mezi °ezy vypa-
dat. Nemusí si uº informace domý²let a m·ºe se efektivn¥ji v¥novat °e²enému problému. Podrobnosti o tomto vyuºití uvádí nap°. £lánek [23].
2.2
Obecný p°ístup k °e²ení
Historicky první techniky morphingu
1
ve lmu zaji²´ovaly p°edev²ím triky p°ed kamerou
provád¥né v dob¥ po°izování záznamu, nikoliv aº p°i následném zpracování. lo nap°íklad o chytré st°ihy postavy probíhající mezi stromy, pokaºdé se zm¥n¥ným maskováním. Jinou,
1 lánek
[7]uvádí rok 1904.
13
vcelku p°ímo£arou moºností je skute£né fyzické modelování poºadované zm¥ny a postupné fotografování jejích jednotlivých fází, podobn¥ jako v loutkovém lmu. Tento p°ístup byl pouºit nap°. ve lmech Chobotnice z druhého patra (1986) a Potkali se u Kolína (1965). Po vizuální stránce mén¥ kvalitní, ov²em univerzáln¥j²í postup spo£íval (tak jako mnoho jiných trik·) v jednoduchém prolínání obrázk·. Snímky výsledné posloupnosti ve skute£nosti sloºené z obou vstupních obrázk· (Op i
Ok )
Ot
byly
p°es sebe s r·znou úrovní
pr·hlednosti. Na za£átku posloupnosti je po£áte£ní obrázek vid¥t zcela a v pr·b¥hu (se zvy²ujícím se t) postupn¥ slábne, naopak koncový není vid¥t v·bec a postupn¥ se objevuje. V polovin¥ posloupnosti tedy vidíme dva p°ekrývající se polopr·hledné snímky. Objekty na po£áte£ním a koncovém obrázku mají zpravidla r·zný tvar, takºe v polovin¥ posloupnosti vidíme rozdíly jako polopr·hledné v·£i pozadí. To nebudí zrovna dobrý dojem. Nap°. velký objekt se totiº na míst¥ malého rovnou zhmotní, místo aby z n¥j postupn¥ vyrostl. Divák by ov²em o£ekával p°irozen¥j²í zm¥nu. Nedívá se totiº na plochý obrázek. Soust°edí se na jeho obsah, tedy na jednotlivé objekty v n¥m. Morphing má zpravidla zobrazovat práv¥ zm¥ny t¥chto objekt·. Je proto nanejvý² vhodné, aby mezilehlé snímky respektovaly strukturu p·vodních a koncových objekt·. Slovo struktura zde ov²em m·ºe znamenat leccos, op¥t zde naráºíme na subjektivnost lidského vnímání. P°edstavme si zm¥nu z £elního obrázku automobilu na lidský obli£ej. P°i pozorování jakéhokoliv obli£eje bezpochyby velmi siln¥ vnímáme o£i. N¥který divák bude povaºovat za p°irozenou jejich zm¥nu ze sv¥tel. Mají podobný tvar, podobn¥ poutají pozornost, jsou dv¥ a vhodn¥ rozmíst¥ná. Z kapoty bychom tak mohli dostat obo£í a z £elního skla £elo. Aby bylo dosaºeno správných proporcí, musela by být sv¥tla posunuta nahoru. Jinému divákovi ov²em m·ºe p°ipadat p°irozen¥j²í, kdyº se na o£i p°em¥ní £elní sklo to je p°ece pro auto (°idi£e) hlavním zdrojem vizuálních informací. Takto postavená zm¥na by vyºadovala rozp·lení vizuáln¥ jednotné plochy a následn¥ zna£né zmen²ení obou £ástí. Z tohoto pohledu zaznamenáváme z°ejmý rozpor budeme sledovat vizuální strukturu obrázku, nebo funk£ní strukturu objektu? Obdobn¥ by bylo moºné konkrétní realizaci zm¥n vyvozovat z mnoºství dal²ích vlastností. Jiº jsme zmínili tvar objekt·, dále lze uvaºovat nap°. materiálové sloºení objekt·, strukturu (tvar, vazby a význam) jejich jednotlivých £ástí. Vidíme tedy, ºe nejednozna£nost °e²ení plyne p°ímo z povahy úlohy, a volba konkrétního °e²ení bude záviset na tom, co p°esn¥ chceme efektem divákovi sd¥lit.
2.2.1
Základní algoritmus
Nyní uvedeme obecné schéma algoritmu, ze kterého r·znou m¥rou vychází v²echny následující p°ístupy k °e²ení morphingu. Identi kovali jsme hlavní problém prostého prolínání: výsledek nevypadá dob°e, protoºe zm¥ny na snímcích nerespektují strukturu jejich obsahu. Místo prolínání, tedy postupné zm¥ny barev obrazových bod·, divák o£ekává zm¥ny objekt·, které na obrázku vidí. Tyto zm¥ny se provád¥jí pomocí tzv.
2
warping
(geometrická
transformace obrazu ). Ten zp·sobí zm¥ny tvar· objekt· na obrázku. Spolu s prolínáním
2 Pro
ú£ely morphingu nelze pouºít libovolnou transformaci, nap°. zrcadlové p°evrácení. Musí totiº existovat p°irozená p°echodová stadia, musí proto být moºné obraz transformovat postupn¥ a spojit¥.
14
Algoritmus 2.1
Schéma algoritmu morphingu
Vstup: po£et snímk·
n
a obrázky
Op
a
Ok .
Postup: 1.
for t = 1 to n :
2.
Op,t ←deformace Op
v kroku
t
3.
Ok,t ←deformace Ok
v kroku
t
4.
Ot ←
lineární interpolace mezi
Výstup: posloupnost snímk·
Op,t
Ok,t
a
v kroku
t
Ot
uº vytvo°í pom¥rn¥ v¥rnou iluzi, ºe se objekty skute£n¥ m¥ní. Na warping lze pohlíºet jako na zobrazení bod· plochy obrázku obrázku
Ok .
Op
na body plochy
Nejde o obrazové, nýbrº o geometrické body, tedy o práci na spojitém, ni-
koliv diskrétním oboru. Tento pohled umoº¬uje uvaºovat o
hladkosti
a
prostot¥
warpingu
v souladu s obvyklými de nicemi. Obrazové body jsou z pohledu warpingu pravideln¥ rozmíst¥né £tvercové plo²ky. Warping ov²em zpravidla pokazí jak jejich £tvercový tvar, tak jejich pravidelné rozmíst¥ní. Zobrazený obrazový bod m·ºe nap°íklad n¥kolik obrazových bod· zakrývat, n¥které z nich t°eba jen £áste£n¥. Jinou nep°íjemnou moºností je, ºe se na n¥který obrazový bod zobrazí hned n¥kolik obrazových bod·. Tyto situace ve skute£nosti zcela b¥ºné a ºádoucí. Pouºitelnost warpingu pro práci s diskrétn¥ reprezentovanými obrazy zajistí vhodné techniky p°evzorkování [36, str. 137]. Diskrétní obraz se pokusí spojit¥ aproximovat, podle pot°eby zobrazit, a poté p°evést zp¥t na diskrétní obraz. Tyto postupy nutn¥ sniºují kvalitu obrazu. Výhodou p°i jejich vyuºití morphing je, ºe máme k dispozici oba krajní obrázky
Op a Ok v plné kvalit¥, takºe po²kození
snímk· posloupnosti vzorkováním není nijak závaºné. Algoritmus 2.1 uvádí konkrétní postup, jak pouºitím warpingu a prolínání °e²it morphing. Pracuje se dv¥ma posloupnostmi pomocných snímk·. Snímky stupnou zm¥nu tvaru z po£áte£ního obrázku, snímky cový obrázek. Pro kaºdý vzorkovaný okamºik
t
Ok,t
Op,t
reprezentují po-
postupnou zm¥nu tvaru na kon-
je tak t°eba z obou vstupních obrázk· vy-
tvo°it vhodn¥ deformované, tedy tvarov¥ zarovnané snímky. Výsledný snímek jejich prolnutím. Nej£ast¥ji uºivatel ur£uje tvar warpingu pomocí
korespondencí
Ot
vznikne
- dvojic míst v po£áte£-
ním a v koncovém obrázku, která si odpovídají. Nap°íklad p°i morphingu obli£ej· uºivatel takto vyzna£í o£i. Warping potom obrázky
Op
Op,t a Ok,t nacházely na stejných místech a Ot . K vyzna£ení korespondencí (a tím °ízení
a
Ok
deformuje tak, aby se o£i na snímcích
bylo tedy moºné je prolnout a získat snímek warpingu) slouºí
°ídicí objekty. Jejich povaha
se u jednotlivých technik morphingu li²í. Na korespondence lze nahlíºet jako na £áste£né zobrazení sou°adnic obrazových bod·. Jinými slovy, korespondence pro n¥které obrazové body de nují, kam mají být body zobra-
15
zeny. Warping daný t¥mito korespondencemi potom vznikne dode nováním tohoto zobrazení v chyb¥jících obrazových bodech. Znovu zde vidíme mnohozna£nost °e²ení morphingu - ani zadání korespondencí neur£uje warping jednozna£n¥. V dal²ím textu vyjde najevo, ºe se jednotlivé konkrétní algoritmy li²í p°edev²ím v realizaci warpingu. Proto není v mnoha p°ípadech ustáleno jejich pojmenování - bývají ozna£ovány jako morphing, ale n¥kdy i jen jako warping. P°ípadné dopln¥ní prolínání je snadné. Této situace vyuºijeme, a ozna£ení warping a morphing zvolíme vºdy podle toho, jestli budeme mít na mysli kompletní algoritmus morphingu, nebo jen jeho deforma£ní £ást, tedy warping.
2.3
Hodnotící kritéria
V této £ásti popí²eme kritéria, která budeme u jednotlivých metod morphingu sledovat ve t°etí kapitole. Budou také podkladem pro srovnávání a hodnocení v kapitole ²esté. Aby se morphing jevil jako p°irozený a metoda jeho tvorby jako efektivní, budeme sledovat následující: 1. Interakce s uºivatelem - výstiºnost °ídicích objekt·, p°edvídatelnost chování, sloºitost my²lenkového modelu 2. Vlastnosti morphingu, hladkost a prostota warpingu 3. asová sloºitost
2.3.1
Interakce s uºivatelem
V dne²ní dob¥ je na práci s po£íta£em nejnákladn¥j²í práce uºivatele. Morphing navíc vyºaduje uºivatele kvali kovaného, tedy drahého. Proto mezi nejzásadn¥j²í kritéria pro hodnocení algoritm· morphingu pat°í ta, která souvisí s uºivatelskou interakcí.
2.3.1.1
Výstiºnost °ídicích objekt·
Tuto vlastnost lze chápat jako pom¥r pot°ebného úsilí uºivatele a jeho spokojenosti s výsledným warping. Nejde p°íli² o to, jak je výsledný warping sloºitý. Vºdy je ale ºádoucí, aby bylo co moºná nejsnaz²í jej speci kovat. Toto kritérium pochopiteln¥ závisí na osobních preferencích uºivatele a na jeho zku²enostech. U v¥t²iny metod morphingu lze ale najít obecné rysy, které výstiºnost °ídicích objekt· nejzásadn¥ji ovliv¬ují. Jedná se nap°íklad nutnost ur£ení po£tu °ídicích objekt· bez moºnosti pozd¥j²í zm¥ny, nebo omezení týkající se jejich vzájemného umíst¥ní. Na základ¥ podobných zásadních rys· pak lze metody mezi sebou srovnat.
16
2.3.1.2
P°edvídatelnost chování
Má-li uºivatel n¥kterou metodu efektivn¥ ovládat, musí metoda dávat výsledky, které uºivatel o£ekává. Míru shody skute£nosti s o£ekáváním vyjad°uje práv¥ toto kritérium. Je pon¥kud v protikladu s p°edchozím kritériem. ím snáz má být moºné speci kovat morphing, tím víc si musí metoda dovozovat samostatn¥. Tím obtíºn¥j²í pro ni ale bude p°esn¥ spl¬ovat o£ekávání uºivatele. Kaºdý jednotlivý uºivatel samoz°ejm¥ m·ºe od dané kon gurace °ídicích objekt· o£ekávat pon¥kud odli²ný warping. Proto ani toto kritérium nelze de novat tak, aby vyhovovalo kaºdému, a následn¥ jej exaktn¥ m¥°it.
2.3.1.3
Sloºitost my²lenkového modelu
Pojem korespondence funguje u v²ech metod obdobn¥. Ov²em p°esná realizace warpingu na základ¥ korespondencí se bude u jednotlivých metod li²it. Kaºdá metoda pracuje s ur£itým modelem warpingu, korespondencí a °ídicích objekt·. Aby mohl uºivatel metodu efektivn¥ vyuºívat, m¥l by tento model znát a p°im¥°en¥ chápat. Toto kritérium úzce souvisí s p°edchozím. Obecn¥ lze °íct, ºe se jednodu²²í modely obvykle chovají p°edvídateln¥ji. P°ísn¥ vzato je toto kritérium op¥t ryze subjektivní, nicmén¥ s jistou opatrnosti a zku²enosti lze formulovat zobec¬ující a hodnotící záv¥ry.
2.3.2
Vlastnosti morphingu
R·zné algoritmy zaru£ují r·zné vlastnosti výsledného morphingu, které více £i mén¥ souvisejí s jeho jinak subjektivn¥ vnímanou p°irozeností. Obecn¥ lze tvrdit, ºe p°irozený warping bude zachovávat atributy, v nejobecn¥j²ím slova smyslu. B¥hem morphingu by se nap°. barvy, velikosti, tvary, topologie nebo vzájemné uspo°ádání objekt· pokud moºno nem¥ly m¥nit v·bec. Pokud je to nutné, tak jen málo, pomalu a monotónn¥. Práce na tomto úkolu se d¥lí mezi uºivatele a pouºitý algoritmus. Uºivatel zaji²´uje zachování sloºitých a abstraktních atribut·, jako jsou konvexita, velikost nebo uspo°ádání objekt·. Algoritmus pak zaji²´uje plynulost zm¥n a zm¥ny jednodu²²í, nap°. zm¥ny barev. P°edev²ím tedy o£ekáváme, ºe algoritmus vygeneruje plynulý morphing, neboli ºe zm¥ny na blízkých místech obrázku budou srovnateln¥ výrazné. Zásadní je zde plynulost warpingu. Z ní uº plynulost morphingu vyplyne, k warpingu uº totiº navíc p°ibude jen prolnutí pomocný snímk·, které plynulost nenaru²í. Plynulost warpingu m·ºeme op¥t posuzovat pomocí plynulosti warpingem daného zobrazení. Plynulost zobrazení budeme chápat jako míru jeho
spojitosti, resp. hladkosti.
Dále je na míst¥ o£ekávat, ºe warping v obrázcích nevytvo°í díry a ºe nep°ekryje jednu £ást obrázku jinou £ástí. Namísto p°ekrytí je obvykle ºádoucí, aby dané obrazové body stla£il a na danou plochu se tak vedle sebe ve²ly v²echny. Díry netvo°í ºádná z dále uvád¥ných metod. Za ur£itých podmínek (p°íli² sloºitá kon gurace °ídicích objekt·) ov²em n¥které mohou tvo°it p°ekryvy. V souladu s chápáním warpingu jako zobrazení proto budeme hovo°it o
prostot¥ warpingu.
17
2.3.3
asová sloºitost
Mezi podstatná kritéria k posuzování algoritm· morphingu samoz°ejm¥ pat°í také £asová sloºitost. Její analýza je nicmén¥ záludn¥j²í, neº se na první pohled zdá. V první °ad¥ je t°eba si uv¥domit, ºe v¥t²inu £asu na tvorb¥ morphingu obvykle zabere práce uºivatele animátora. Chceme-li tedy optimalizovat vyuºití £asu, je t°eba sledovat p°edev²ím kritéria související s uºivatelskou interakcí. P°i pokusech o p°esné spo£tení nebo zm¥°ení pr·m¥rné £asové náro£nosti výpo£tu morphingu narazíme na problém, jak najít vhodné obrázky a jak které morphingy daných obrázk· vybrat. Vzhledem k celkovému po£tu obrázk· (i zcela malých rozm¥r·) a k po£tu moºností jejich morphingu totiº není moºné je do posuzování zahrnout v²echny. Není snadné ani rozhodnout, jaký jejich výb¥r povaºovat za reprezentativní. Nabízí se tedy spo£ítat nebo odhadnout nejhor²í asymptotickou sloºitost. Vyvozovat z ní ale záv¥ry lze jen s vysokou opatrností. V praxi bude totiº délka výpo£tu velmi siln¥ záviset na konstantách a na zvolených parametrech. Asymptoticky dobrá metoda se m·ºe ukázat jako t¥ºko pouºitelná v praxi. Je zde tedy moºnost získat pot°ebné informace m¥°ením. Musíme ale myslet na to, ºe obvykle lze se stejnou metodou docílit stejného výsledku více r·znými zp·soby. Zku²ený uºivatel proto m·ºe poºadavky na warping vyjád°it men²ím po£tem °ídicích objekt· a pro danou metodu p°irozen¥ji neº jiný. Tím zkrátí dobu výpo£tu stejného algoritmu a po£ítajícího stejný výsledek. To m·ºe výsledky m¥°ení snadno zkreslit. I p°es tyto komplikace informace o asymptotické sloºitosti jednotlivých metod pokud moºno p°edloºíme. U n¥kterých jsou publikovány, u n¥kterých jsme je odvodili, u n¥kterých známy nejsou. Z vý²e uvedených d·vod· to ov²em jejich autor·m ani uºivatel·m p°íli² nevadí. P°i posuzování £asové sloºitosti morphingu je dobré rozli²ovat t°i fáze práce a hodnotit je odd¥len¥. První je ur£ení korespondencí. To obvykle spo£ívá na bedrech uºivatele, zji²´ovat jeho sloºitost p°esto m·ºe mít smysl - totiº u samo£inných metod. Dále n¥které algoritmy pot°ebují n¥jaký £as na p°ípravu k po£ítání warpingu. Zde samoz°ejm¥ obvykle platí, ºe víc £asu v¥novaného p°íprav¥ se pozitivn¥ projeví ve fázi poslední, tedy výpo£tu samotných snímk· výsledné frekvence. Aniº bychom je²t¥ cokoliv v¥d¥li o konkrétních metodách morphingu, m·ºeme n¥co odhadnout. Hledání warpingu bude p°inejmen²ím lineárn¥ závislé na po£tu °ídicích objekt·. Po£ítání výsledné sekvence bude pravd¥podobn¥ lineární vzhledem k po£tu jejích snímk·
n.
Práce na jednom snímku pak bude vyºadovat p°inejmen²ím tolik krok·, kolik
má obrazových bod·. Dal²í podrobnosti uº závisí na úspornosti a výstiºnosti konkrétní reprezentace warpingu. Na záv¥r oddílu p°ipome¬me, ºe p°i interpretaci £asové sloºitosti metod morphingu je vºdy t°eba mít na pam¥ti vý²e uvedené záludnosti. Skute£n¥ spot°ebovaný £as se bude krom¥ sloºitosti metody vºdy odvíjet i od zru£nosti animátora, rozli²ení poºadovaných snímk· a podobn¥.
18
2.4
Varianty morphingu
Následuje popis r·zných variant základní úlohy morphingu. Mají sv·j teoretický význam, ov²em £asto vedou i k zajímavým aplikacím. Varianty lze samoz°ejm¥ °e²it vhodn¥ modi kovanými základními algoritmy. Jak zde ale ukáºeme, nabízí se i vyuºití zcela jiných p°ístup·, vhodn¥ vyuºívajících speci ka konkrétní úlohy. Ty jsou pak bohatým inspira£ním zdrojem pro °e²ení základní úlohy.
2.4.1
Parametrizace technik
Krom¥ ur£ování korespondencí existují i dal²í moºnosti ovlivn¥ní výsledného morphingu dvou konkrétních obrázk·. Zm¥ny nemusí probíhat lineárn¥. N¥kdy m·ºe být vhodné za£ít pozvolna a nenápadn¥, teprve pozd¥ji naplno zrychlit. Navíc lze odd¥lit dynamiku warpingu a prolínání. Tak lze dosáhnout nap°íklad toho, aby £ervené jablko nejd°ív získalo tvar hru²ky a aº následn¥ zeºloutlo. Dal²ím krokem je
lokální °ízení rychlosti
zm¥n. N¥kdy m·ºe být ºádoucí nap°íklad
na za£átku zaujmout diváka zm¥nami pop°edí obrázku. Ten tím pádem neztratí pojem o kontextu situace, protoºe bude zachováno p·vodní pozadí. To lze zm¥nit dodate£n¥, aº divák vst°ebá zm¥ny pop°edí. Tyto moºnosti zm¥n dynamiky morphingu a jejich kombinace lze více £i mén¥ p°ímo£a°e zahrnout do v¥t²iny uvedených metod. Podrobnosti diskutuje £lánek [34]. Druhou uºite£nou moºností, jak podstatn¥ ovlivnit celkový výsledek, je volba pouºitého barevného modelu. Interpolace intenzit kanál· v jednotlivých obrazových bodech je vlastn¥ hledáním cesty v prostoru barev z jednoho bodu do druhého. Není nijak p°irozen¥ z°ejmé, která z moºností bude pro morphing nejlep²í. Obvykle padne volba na p°ímou spojnici. To je ov²em dáno spí² univerzální pouºitelností, jednoduchostí implementace a nedostatkem prozkoumaných alternativ, nikoliv vizuální kvalitou výsledku. Barvy leºící v prostoru barev na úse£ce mezi dv¥ma body mohou být totiº velmi r·zné. Záleºí na konkrétní úse£ce a práv¥ na barevném modelu. Standardní model RGB nemusí být pokaºdé nejvhodn¥j²í volbou. B¥hem zm¥ny z jedné barvy na druhou se £asto m·ºe neºádoucím zp·sobem m¥nit barevný odstín nebo sytost. Nap°íklad p°echod z £ervené na tyrkysovou vede p°es £istou ²edou. Snaha o univerzální °e²ení op¥t naráºí na subjektivitu lidského vnímání, navíc poºadavky na konkrétní posloupnost snímk· se mohou li²it p°ípad od p°ípadu. Proto m·ºe být n¥kdy výhodné zvaºovat alternativní barevné modely. Jednou z moºností jsou modely jako Lab nebo YIQ, kde první sloºka zna£í sv¥tlost a dal²í dv¥ kódují barvu jako takovou. Je zde tedy jasná výhoda moºnosti °ízení zm¥n sv¥tlosti samostatn¥, bez vlivu na barevný odstín. Dále se nabízí model HLS, který pracuje s barevným odstínem, jasem a sytostí. Tyto sloºky lze interpolovat nezávisle, nemusí tedy docházet nap°. k neºádoucímu blednutí a následnému tmavnutí £ásti obrazu jako v modelu RGB. Pon¥kud obtíºná je zde ov²em práce s barevným odstínem. Odstíny jsou v tomto modelu °azeny podobn¥ jako v duze. Pak je ov²em z°ejmé, ºe se lze st¥ºí dostat z £ervené do zelené
19
3
a po cest¥ minout ºlutou . Ve v¥t²in¥ p°ípad· tak bude na cest¥ mezi dv¥ma odstíny n¥jaký dal²í, zpravidla ne£ekaný a pro diváka nep°irozený. Z uvedeného je z°ejmé, ºe neexistuje univerzální °e²ení. Barevný model a dynamiku prolínání jednotlivých kanál· je t°eba volit s ohledem na poºadovaný výsledek. Podrobn¥ji se touto problematikou zabývá £lánek [21].
2.4.2
Specializace
Pom¥rn¥ obtíºný problém morphingu lze zjednodu²it p°ijetím dodate£ných p°edpoklad· nebo pouºitím dodate£ných znalostí o povaze úlohy. V mnoha specializovaných oblastech tak bylo kvalitních výsledk· dosaºeno snáz neº s obecnými metodami. Nap°íklad v oddílu 3.4 uvedený nejmén¥ pracný morphing pracuje velmi dob°e za p°edpokladu podobných obrázk·. I v mnoha jiných situacích mohou dodate£né p°edpoklady a informace nap°. zvy²ovat pravd¥podobnost úsp¥chu automatického ur£ování korespondencí. Pravd¥podobn¥ nejvíc speci ckých aplikací morphingu se týká lidských obli£ej·. Jedná se nap°. o problematiku rozpoznávání a identi kace, kompresi dat p°i videokonferencích, inteligentní rozhraní mezi lidmi a stroji a samoz°ejm¥ zábavní pr·mysl. V kapitole 5 je uveden popis dvou takových p°ístup·, které vyuºívají samoorganiza£ních metod. Dal²í specializovanou aplikací je vypl¬ování prostoru mezi sousedními snímky lidského t¥la. Dodate£ná znalost o úloze °íká, ºe na snímcích jsou orgány a tkán¥, coº zna£n¥ zuºuje moºnosti korespondencí mezi snímky. Lze proto vyuºít zku²enosti a heuristiky odvozené z metod rekonstrukce povrchu trojrozm¥rných objekt· z posloupností °ez· a dosáhnout tak automatického vyhledávání korespondencí. Nutnost lidských zásah· a tím i vý²e náklad· na provedení úlohy jsou potom zna£n¥ omezeny. Jinou specializovanou úlohou je morphing mnohoúhelníku. Odpadá problém s barvami, vstupem jsou dva mnohoúhelníky a °e²ením posloupnost p°etvarování jednoho na druhý. Jedno ze známých a úsp¥²ných °e²ení této úlohy je publikováno v [27]. Jde o p°edch·dce metody minimáln¥ pracného morphingu popsané v oddílu 3.4 na stran¥ 31. Funguje na základ¥ p°edstavy, ºe mnohoúhelníky jsou zhotoveny z drátu a jeden na druhý je t°eba doslova p°epracovat. Jsou de novány základní úkony (ohnutí, protaºení nebo zkrácení £ásti drátu) a jejich pracnost. Kritérium p°irozenosti zm¥ny je reprezentováno minimalizací pot°ebné práce. Popisovaný algoritmus najde práv¥ takový postup zm¥n. Shrnující p°ehled známých metod v£etn¥ morphingu rovinných k°ivek uvádí [8, kap. 17]. S tvarováním k°ivek souvisí nej£ast¥j²í aplikace nefotorealistického morphingu, který pracuje s dodate£nými informacemi o povaze vstupních obrázk·. Zpravidla jde o stejnobarevné plochy ohrani£ené tenkým £erným obrysem, tedy klasické kreslené lmy. Algoritmy vycházející z morphingu pat°í mezi standardní aplika£ní nástroje tv·rc· t¥chto lm· [10].
2.4.3
Zobecn¥ní
Morphing mezi obrázky lze samoz°ejm¥ i ú£eln¥ zobecnit. Nej£ast¥j²í pouºití morphingu je, jak uº bylo uvedeno, v oblasti animací a lmových efekt·. Zm¥na jednoho obrázku
3 Lze
to, z druhé strany barevného kotou£e. Taková cesta ov²em vede p°es alovou, modrou a tyrkysovou.
20
na druhý ale p°edpokládá, ºe je v pr·b¥hu animace xován pohled kamery. P°irozen¥ tedy budeme mít zájem kameru rozhýbat a zm¥nu objekt· na scén¥ sledovat v pohybu. Vstupem algoritmu pak uº nebudou dva obrázky, ale dv¥ videosekvence. Bude pot°eba tvarov¥ sesadit objekty, které videosekvence obsahují a takto deformované videosekvence vzájemn¥ prolnout. Totéº zobecn¥ní pokrývá nejen pohyb kamery, ale i pohyb (nebo jinou zm¥nu v £ase) samotných m¥nících se objekt·. P°ímo£aré °e²ení spo£ívá v nalezení dal²í transformace, popisující tvarové zm¥ny vstupních videosekvencí. Její mezikroky tentokrát pravd¥podobn¥ nep·jde jednodu²e lineárn¥ interpolovat, protoºe pohyb kamery nebo objekt· ve scén¥ apod. v obrazu nezp·sobuje lineární zm¥ny. Vhodnou aplikací této nové transformace na transformaci obrázk· (danou nap°. umíst¥ním °ídicích objekt·) získáme informaci o tom, jak správn¥ p°ipravit dané dva snímky vstupních videosekvencí k prolnutí. Obdobným postupem byly vytvo°eny n¥které scény klipu Black or White od Michaela Jacksona (Paci c Data Images, 1990). Pokro£ilej²í techniky vyuºívají poznatky po£íta£ového vid¥ní a automaticky sledují pohyb objekt· a upravují korespondence (nap°. [30]). et°í tím práci animátora a navíc mohou i odd¥lit pop°edí od pozadí, pracovat s nimi nezávisle a dále tak zkvalitnit výstup. Mezi aplikace podobných p°ístup· nepat°í jen p°ímo£arý morphing lmových sekvencí, ale také jiº zmín¥ná kvalitní konverze po£tu snímk· za sekundu záznamu. V principu je to podobná úloha jako vypl¬ování prostoru mezi snímky °ez· n¥jakým objektem. Dal²í moºné zobecn¥ní se týká dimenze zpracovávaných obrázk·. P°irozen¥ se nabízí morphing 3D objekt·. Tato úloha v principu °e²í podobné problémy jako morphing obrázk·, ov²em o dimenzi sloºit¥j²í. Op¥t je t°eba hledat korespondence a jejich vhodnou reprezentaci, sledovat rychlost zm¥n tvaru i povrchu atd. P°ibývají ov²em dal²í výzvy. Velký vliv má volba reprezentace objekt· (objemová nebo povrchová). Krom¥ zm¥n tvar· je t°eba zvaºovat zp·sob práce s texturami. Ty mají na objektech svou polohu, orientaci, leckdy jsou i tvarov¥ deformované. Na to v²e je t°eba brát ohled p°i p°irozené zm¥n¥ trojrozm¥rných objekt· z po£áte£ního na cílový stav. Pokud je t°eba uplatnit morphing na syntetický obrázek a zdrojové 3D objekty jsou k dispozici, 3D morphing stojí za zváºení. Obtíºnost provedení m·ºe být snadno vyváºena moºností snadné zm¥ny pohledu, osv¥tlení atd. ve výsledné scén¥. Navíc nemáme problémy s p·vodn¥ nezobrazenými £ástmi objekt·. Ve 2D morphingu se prost¥ objeví odnikud , ve 3D morphingu uvidíme jak o£ní ví£ko uhýbá oku (které se nijak nedeformuje) nebo realisticky se otevírající knihu. Moºná p°ekvapivým zobecn¥ním je zvý²ení po£tu vstupních obrázk·. Cílem uº není videosekvence se zm¥nou, nýbrº statický obrázek sloºený z n¥kolika (i stovek) vstupních obrázk·. Takové zobecn¥ní nabízí p°ekvapivé aplikace. Zpráva [4] uvádí výsledky experimentu na ov¥°ení hypotézy pr·m¥rnost je atraktivita. Podle této hypotézy jsou lidé s pr·m¥rn¥j²ím vzhledem ostatními hodnoceni jako atraktivn¥j²í. Tato hypotéza p·vodn¥ vznikla na základ¥ pr·zkumu s je²t¥ jednodu²e prolnutými analogovými fotogra emi. Auto°i nového experimentu m¥li k dispozíci v¥t²í mnoºství dat ve vy²²í kvalit¥ a navíc pokro£ilé techniky morphingu. Díky tomu získali mnohem realisti£t¥j²í fotogra e pr·m¥rných muºských a ºenských obli£ej·. Tím mohli odstranit n¥které
21
neºádoucí vlivy (nap°. zm¥k£ující rozmazané obrysy obli£ej·). S t¥mito fotogra emi pak realizovali pr·zkumy a zji²´ovali, jak atraktivní respondent·m p°ipadají. Ve sporu s prov¥°ovanou hypotézou vy²lo najevo, ºe rozhodující vliv má atraktivita p·vodních obli£ej·, ze kterých se pr·m¥r po£ítá. Pr·m¥r atraktivních obli£ej· z·stává atraktivní, pr·m¥r neatraktivních se atraktivním nestává. Navíc i pr·m¥r z atraktivních obli£ej· se m·ºe zhor²ovat, pokud jsou pr·m¥rováním set°eny n¥které charakteristické rysy atraktivních obli£ej·. Tato interpretace je samoz°ejm¥ zjednodu²ující, úplné informace uvádí [4]. Pro morphing více obrázk· se op¥t nabízí p°ímo£arý postup. Na kaºdém obrázku vyzna£íme korespondence (se v²emi ostatními zárove¬), najdeme jejich st°ední umíst¥ní a p°íslu²ným zp·sobem transformujeme v²echny vstupní obrázky. Transformované obrázky pak uº zbývá jen navzájem prolnout. Dal²í zobecn¥níním této úlohy pracuje s vahami vstupních obrázk·. Kaºdý z nich tak k výsledku p°ispívá r·znou m¥rou. Lze jít je²t¥ o krok dál a váhy vstupních obrázk· ur£ovat lokáln¥. Na výsledném obrázku pak mohou být jeho jednotlivé £ásti z r·zných vstupních obrázk·. Obecný rámec váºeného morphingu z více vstupních obrázk· p°edstavuje George Wolberg v [34]. Samoz°ejm¥ lze uvedená zobecn¥ní kombinovat a hledat nap°. 3D objekt vzniklý ze t°í dal²ích, videosekvenci zachycující morphing dvou pohybujících se 3D objekt· atd. Podobné úvahy vedou k hledání obecn¥j²ího kontextu toho, co je to vlastn¥ morphing obrázk·. Na
4
záv¥r úvodní kapitoly proto uvedeme alternativní vysv¥tlení, co je to morphing : Lze °íci, ºe je to totéº co animace. Toto zji²t¥ní roz²i°uje pohled na ob¥ tyto úlohy. Ukazuje, ºe morphing není jen o magických prom¥nách objekt· ve scén¥ - i na mnohem triviáln¥j²í zm¥ny, jako nap°. prosté pohyby objekt· v prostoru, lze pohlíºet jako na morphing. Hranici mezi morphingem a animací stírá lm Muº, který sázel stromy (L'homme qui plantait des arbres, 1987).
4S
odli²ným p°ístupem se k této otázce staví publikace [8]. Abstrahuje od morphingu obrázk· a °adí jej do kontextu morphingu ²iroce de nované kategorie gra ckých objekt·. 22
Kapitola 3 Morphing: metody °e²ení Tato kapitola obsahuje zejména popis klasických i nov¥j²ích p°ístup· k °e²ení morphingu, v£etn¥ uvedení jejich zásadních výhod a nevýhod pro praktické pouºití. Vychází p°itom p°edev²ím ze shrnujícího £lánku [34], podrobnosti jsou £erpány z publikací [33, 36] a z £lánk·, ve kterých byly publikovány jednotlivé metody.
3.1
Sí´ový morphing
Jednou z prvních a vcelku p°ímo£arých variant warpingu, pouºitou pouºitou pro ú£ely morphingu, je sí´ový warping (mesh warping). R·zné popisy uvádí [8, str. 250][33, str. 222][36, str. 148]. Krom¥ délky posloupnosti a vstupních obrázk· p°ijímá je²t¥ korespondence, kterými uºivatel speci kuje o£ekávaný warping. ídicím objektem je zde
uzl·
sí´
tvo°ená z °ídicích
uspo°ádaných do £tvercové topologie. Okraje sít¥ leºí p°esn¥ na okrajích obrázku. Sí´
jej tak uzly a spoji mezi nimi d¥lí na jednotlivé
dílky.
Uºivatel umístí na odpovídající si
významné body v obou obrázcích uzly sítí se stejnými topologickými sou°adnicemi. Dal²í vstupní informací jsou tedy dv¥ sít¥
Sp
a
Sk
(po£áte£ní a koncová) o shodných rozm¥rech,
které dále ur£ují, jak má warping vypadat. Sí´ový warping deformuje sít¥ °ídicích uzl·. Cílem deformace je získat posloupnost sítí
St
vystihující postupnou zm¥nu z
lineární interpolací poloh uzl· v síti
Sp
Sp
a
na
Sk .
Sk .
S
Jednotlivé mezistavy
St
vznikají obvykle
pomocí t¥chto mezistav· pak lze spo£ítat
odpovídajícím zp·sobem deformované vstupní obrázky
Op,t
a
Ok,t ,
jakoby byly na pruºné
gumové plo²e, p°i²pendlené ke své síti práv¥ v jejích uzlech. Jejich prolnutím vzniknou hledané snímky
Ot
výsledné posloupnosti morphingu.
Moºností výpo£tu warpingu na základ¥ polohy uzl· sítí je mnoho. Zpravidla jsou v kaºdé síti propojeny uzly v topologických °ádcích a sloupcích. Obrázky jsou tak rozd¥leny na
dílky, které potom warping jednotliv¥ deformuje z po£áte£ního tvaru na koncový.
Jednotlivé varianty sí´ového warpingu se li²í p°edev²ím funkcemi pouºitými k proloºení uzl· sít¥. Jako p°ímo£aré °e²ení se nabízí po £ástech (mezi uzly) lineární funkce. Warping je potom v obou osách lineární zobrazení sou°adnic bod· obrázku v korespondujících dílcích °ídicí sít¥. To p°esn¥ odpovídá dosavadní p°edstav¥ sít¥.
23
V p°ípad¥ její výrazné deformace se ale na výsledném snímku mohou objevit zlomy na hranicích jednotlivých dílk· °ídicí sít¥. To zna£n¥ kazí dojem, t¥ºko pak lze mluvit o plynulé zm¥n¥ po£áte£ního obrázku na koncový. Výpo£etn¥ o n¥co náro£n¥j²í je pouºití hladkých funkcí. P°i pr·chodu uzlem nedojde k ostrému zlomu, ale k plynulé zm¥n¥ sm¥ru. Tím budou eliminovány zlomy p°i deformaci obrázk·. Hlad²í funkce dávají vizuáln¥ lep²í výsledky, ve srovnání s lomenými £arami jsou ale výpo£etn¥ náro£n¥j²í a h·°e p°edvídatelné. Tvar lomené £áry spojující uzly sít¥ totiº uºivatel odhadne snáz neº tvar hladké k°ivky. Objekty na vstupních obrázcích navíc nemusí být vºdy hladké. Pouºití hladkých funkcí je pak spí²e na ²kodu. Obecn¥ji lze pracovat nikoliv s interpolací poloh uzl·, ale jen s jejich aproximací. Ztrátu p°esné kontroly nad tvarem sít¥ a tím i nad celým warpingem má vyváºit je²t¥ hlad²í výsledek. Jak je patrné z p°edchozího, vhodnost pouºití t¥chto moºností závisí p°edev²ím na konkrétních poºadavcích na danou úlohu. Samotná deformace je obvykle po£ítána dvoupr·chodov¥. Dvourozm¥rná geometrická transformace je rozd¥lena na dv¥ jednorozm¥rné. Tento p°ístup sniºuje nejen výpo£etní £as, ale i obtíºnost implementace. Nejd°íve probíhá deformace v rámci °ádk·. Na kaºdém z nich algoritmus ur£í jeho pr·se£íky s k°ivkami výchozí i cílové sít¥, které procházejí jejich uzly ve vertikálním sm¥ru. Takto získané dvojice úsek· ur£ují deformaci °ádku. Obsah jednotlivých výchozích úsek· je pomocí lineární interpolace namapován na prostor p°íslu²ných cílových úsek·. Deformací jednotlivých °ádk· postupn¥ vznikne obraz, který je vstupem druhého pr·chodu. Ten probíhá zcela stejn¥ jako první, ale se sloupci. Algoritmus najde pr·se£íky sloupc· s horizontálními k°ivkami sítí a podle nich namapuje p°íslu²né úseky. T¥mito dv¥ma odd¥lenými pr·chody je získán deformovaný snímek k dal²ímu zpracování, tedy prolnutí se snímkem vzniklým obrácenou deformací druhého vstupního obrázku. Dvoupr·chodové transformace skrývají slabé místo, které se projeví nap°. p°i výrazné rotaci. Obraz je totiº nejd°ív v jedné z os velmi smr²t¥n a teprve tento smr²t¥ný mezivýsledek je poté roztaºen na správnou velikost. To vede ke zna£né degradaci obrazu, nebo´ smr²t¥ný mezivýsledek jiº neobsahuje dostatek obrazových informací pro roztaºení. e²ením je vhodné oto£ení obrazu p°edem tak, aby se efekt neprojevil, nebo pouºití výpo£etn¥ náro£n¥j²í, ale kvalitn¥j²í jednopr·chodové metody. Sí´ový morphing je patrn¥ nejp°ímo£a°ej²í metodou. Díky tomu je snadno pochopitelný pro uºivatele. Ti mohou snadno p°edvídat chování algoritmu a díky tomu také tvo°it kvalitní výsledky. Díky p°ímo£arosti principu sí´ového warpingu je implementace pom¥rn¥ nezáludná a £as výpo£tu velmi p°im¥°ený. Správa °ídicí sít¥ nep°esáhne sloºitost zobrazování samotných obrazových bod·. Jejich zobrazení je navíc rychlé díky dvoupr·chodovému p°ístupu. 2 Celkov¥ je na výpo£et jednoho snímku o rozli²ení R × R pot°eba O(R ) operací. V praxi se ale ukáºe, ze metoda sí´ového warpingu trpí °adou obtíºí v oblasti uºivatelské p°ív¥tivosti. Pravidelná °ídicí sí´ m·ºe totiº být z dále uvedených d·vod· svazující. D·leºité linie na vstupních obrázcích nap°íklad bývají £asto jiné neº jen svislé a vodorovné a uºivatel musí pokaºdé znovu zvaºovat, jakým zp·sobem sí´ nep°irozen¥ zkroutí, aby uzly v obrázku co nejlépe umístil a výsledná animace vypadala podle jeho p°edstav.
24
Dal²í nep°íjemností je pravidelnost °ídicí sít¥ a mnoºství jejích uzl·. Na r·zných místech obrázku je zpravidla pot°eba r·zná úrove¬ p°esnosti ur£ení korespondencí a tedy i r·zné mnoºství uzl· sít¥ k umíst¥ní. Hustota sít¥ ale musí být jednotná na celé plo²e obrázku. Se sí´ovým warpingem je proto nakonec uºivatel nucen pe£liv¥ umis´ovat mnoho uzl· i v místech, která ho ve skute£nosti p°íli² nezajímají. Mnohdy se poºadované zm¥ny mohou týkat jen malé oblasti obrázku. V takovém p°ípad¥ se sí´ový warping ukazuje op¥t jako neobratný, protoºe p°edem p°edpokládá deformaci celé plochy obrázku. Bylo by prakti£t¥j²í mít k dispozici nástroj, který by umoº¬oval provád¥t jen lokální zm¥ny. Dále uvedené metody morphingu jsou £asto motivovány p°edev²ím odstran¥ním uvedených nedostatk·. Metody se budou li²it p°edev²ím v povaze °ídicích objekt· (zde £tvercová sí´), zp·sobu ur£ení korespondencí mezi obrázky (zde uzly a hrany sít¥) a ve zp·sobu generování warpingu (zde dvoupr·chodový algoritmus). Cílem je usnadnit uºivateli práci, neboli umoºnit stru£n¥j²í, p°esn¥j²í a výstiºn¥j²í speci kaci korespondencí. S tím jde ruku v ruce vy²²í výpo£etní náro£nost warpingu. Ten se tak vzhledem ke svému zásadnímu vlivu na výsledek stává dominantním co do práce uºivatele i co do výpo£etního £asu.
3.2
Úse£kový morphing
Úse£kový morphing (feature based morphing, [?], hlavní zdroj pro tento oddíl) se snaºí uºivateli zp°íjemnit práci zobecn¥ním a zjednodu²ením speci kace warpingu. Korespondence nejsou ur£eny dvojicí sítí, ale n¥kolika dvojicemi ²ipek (orientovaných úse£ek). Jejich po£et záleºí £ist¥ na p°ání uºivatele. Toto pojetí °ídicích objekt· umoº¬uje oproti sí´ovému warpingu pracovat bez omezení pravidelnou topologií a provád¥t lokální zm¥ny. Navíc je pro £lov¥ka obvykle mnohem intuitivn¥j²í pracovat s £arami neº s body. Zrakové vnímání je totiº více zam¥°eno na hrany objekt· a místo bod· sleduje spí² £áry [36, 2, str. 167, 326]. Kv·li zm¥n¥ zp·sobu zadání korespondencí se m¥ní i zp·sob generování warpingu. Kaºdý obrazový bod si snaºí zachovat relativní polohu v·£i ostatním ²ipkám. Jednotlivé
1
dvojice ²ipek ovliv¬ují r·zné body r·zn¥. ipky de nují pole vlivu
ur£ují, které obrazové
body jimi budou ovlivn¥ny a do jaké míry. Tento vliv je vyjád°en vahou
w, ur£enou vztahem l a roste
(3.1). Podle o£ekávání váha klesá s rostoucí vzdáleností mezi bodem a ²ipkou s délkou ²ipky
d.
Hodnotu váhy lze je²t¥ ovlivnit následujícími parametry. Parametr hodnot z intervalu
[0, 1]
a upravuje vliv délky ²ipky
d
f
leºící ²ipce. Vy²²í hodnoty
obvykle nabývá
na celkovou váhu. Pro
v²echny ²ipky stejnou váhu, bez ohledu na délku. S vy²²ím Hodnota parametru
h
h
vliv
d
na
w
h=0
mají
roste.
blízká nule zaji²´uje absolutn¥ dominantní váhu velmi blízko
f
vedou k niº²ím vahám blízkých ²ipek a tím i k plynulej²í
deformaci. Zárove¬ se ale sniºuje p°esnost jejího °ízení. Parametr
g
ur£uje, jak s rostoucí vzdáleností
l
klesá váha. Pro
g=0
bude kaºdý bod
ovlivn¥n v²emi ²ipkami stejn¥, bez ohledu na vzdálenost. Osv¥d£ené hodnoty parametru
1Z
toho vychází alternativní ozna£ení algoritmu - eld morphing, tedy morphing pomocí polí.
25
Obrázek 3.1: Schéma nalezení zdrojového bodu v úse£kovém warpingu
Pro ob¥ ²ipky
Uk1 , Uk2
jsou nalezeny odpovídající body
p°íslu²né °ídicí ²ipce z·stává stejná. Pomocí vah pr·m¥r vektor· rozdílu
xk
jsou v intervalu
[ 12 , 2].
a
w2
v
Op .
Jejich poloha v·£i
spo£tených podle (3.1) je získán
a jeho jednotlivých po£áte£ních poloh. P°i£tením tohoto pr·-
m¥rného rozdílu k poloze bodu
g
w1
x1p , x2p
xk
je získán hledaný bod
Nízké hodnoty
g
xp .
sniºují vliv vzdálenosti ²ipky a bodu, vysoké
hodnoty tento vliv zvy²ují.
w=
dh f +l
g (3.1)
Transformace obrazu probíhá po jednotlivých bodech výsledného obrazu, jde tedy o techniku zp¥tného mapování. Pro kaºdý bod
Ok
jsou spo£teny zdrojové obrazové body
vzhledem k jednotlivým dvojicím ²ipek. Tedy ty, které by se na uvaºovaný bod výsledného obrazu zobrazily v p°ípad¥ zadání jediné dvojice ²ipek. Na úse£kový warping lze nahlíºet jako snahu bod· zachovat si relativní polohu v·£i kaºdé ²ipce. Relativní polohou je zde mín¥na vzdálenost od ²ipky a vzdálenost na ²ipce, neboli délka kolmice k ²ipce procházející bodem a její poloha na ²ipce. Pokud kolmice neexistuje, pouºije se vzdálenost od bliº²ího konce ²ipky a poloha bude orientace ²ipky. Ze znalosti koncové polohy ²ipky
Up
lze spo£ítat, kde leºí po£áte£ní bod
xp .
Uk
a bodu
xk
0
nebo
1,
podle
a po£áte£ní polohy ²ipky
Má mít v·£i ²ipce stejnou vzdálenost i polohu
[3]. Takto je tedy nalezena po£áte£ní poloha bodu vzhledem ke kaºdé dvojici °ídicích ²ipek. Pomocí vah, jakými ²ipky ovliv¬ují obrazové body, je spo£ten váºen¥ pr·m¥rná bod po£áte£ního obrázku. Ten je zobrazen na práv¥ zpracovávaný bod výsledného snímku. Postup ilustruje obrázek 3.1.Takto probíhá úse£kový warping jednoho snímku.
26
Obrázek 3.2: Ilustrace moºností interpolace poloh ²ipek
ipky lze interpolovat v kartézských nebo v polárních sou°adnicích. Druhá moºnost dává p°irozen¥j²í výsledky p°i výrazných rotacích (²ipky se uprost°ed procesu nezkracují), pro uºivatele je ale mén¥ intuitivní.
Postup vytvá°ení výsledné posloupnosti snímk· vychází ze základního algoritmu 2.1 a je obdobný jako u ostatních algoritm·. Pro kaºdý snímek
Ot nejd°ív interpolujeme aktuální
polohy jednotlivých ²ipek v p°íslu²ném okamºiku. Poté práv¥ popsaným zp·sobem dopo£teme p°íslu²n¥ deformované dvojice obrázk· (z po£áte£ního
Op
a koncového
Ok ) k prolnutí
do výsledných snímk· posloupnosti. Polohy ²ipek lze interpolovat dv¥ma zp·soby (obrázek 3.2). První je jednoduchá interpolace jejich koncových bod·. Pokud ale uºivatel o£ekává nap°. rotaci, dostane nep°irozený výsledek (²ipka bude v prost°ední poloze výrazn¥ krat²í). Druhým pouºívaným zp·sobem je interpolace polohy st°edu ²ipky, její orientace a délky. Toto chování lépe zvládá rotace, nedochází totiº ke zkracování a op¥tovnému natahování ²ipky. N¥kdy ov²em mate uºivatele, protoºe si tento pohyb ²ipky obtíºn¥ji p°edstaví. e²ením je samoz°ejm¥ dát uºivateli na výb¥r z obou variant a ukázat mu vizualizaci výsledného pohybu ²ipek. P°es uvedená pozitiva se k úse£kovému morphingu váºe i n¥kolik úskalí. V první °ad¥ je to £asová náro£nost výpo£tu, která je výrazn¥ vy²²í neº u sí´ového warpingu. V kaºdém
d a l (v·£i v²em obrazovým bod·m) a tím i váha w kaºdé ²ipky. Pro vytvo°ení jednoho snímku s R × R obrazovými body pomocí m pár· ²ipek 2 je tedy zapot°ebí O(R · m) pom¥rn¥ náro£ných operací. Jak uº ale bylo uvedeno v £ásti snímku se totiº m¥ní poloha ²ipek, tím i
2.3.3, v dne²ní dob¥ obvykle stojí víc £asu a pen¥z práce uºivatele (animátora) neº výpo£et samotného efektu. Popsaný zp·sob warpingu z [3] je navíc zaloºen v podstat¥ na hrubé síle. Elegantními optimalizacemi lze dosáhnout aº dvacetinásobného zrychlení [15]. Druhé, závaºn¥j²í úskalí spo£ívá v ob£as p°ekvapivém chování morphingu. Ne kaºdá
27
kon gurace ²ipek totiº vede k o£ekávaným a p°ijatelným výsledk·m. Nap°íklad dotýkání nebo dokonce k°íºení ²ipek £asto zp·sobí neºádoucí vyh°eznutí skupiny obrazových bod· na místech kolize. Uºivatel takto ²ipky obvykle neumis´uje, k obtíºné situaci ale m·ºe dojít v pr·b¥hu morphingu, tedy v n¥které mezipoloze ²ipek. Obecn¥ tyto situace bu¤ plynou z principiáln¥ nedosaºitelných poºadavk· uºivatele na warping (p°íli² divoká, ale zárove¬ spojitá deformace), nebo je lze vy°e²it zvý²ením po£tu dvojic ²ipek a zp°esn¥ním zadání warpingu. Takové úpravy ale nejsou zrovna intuitivní a kazí p°edvídatelné chování algoritmu. Tím se ztrácí uºivatelská p°ív¥tivost, jeho hlavní p°ednost.
3.3
Interpolace korespondencí
Sí´ový warping deformuje obrázky po jednotlivých dílcích sít¥. Vy²²í matematika umoº¬uje dosáhnout lep²ích výsledk·, a dokonce za slab²ích p°edpoklad·. Pro hledání vhodné geometrické transformace obraz· lze vyuºít bohaté výsledky metod interpolace roztrou²ených
2
dat . Mezi nej£ast¥ji pouºívané pat°í spliny (thin plate splines, TPS) a radiální bázové funkce (radial basis functions, RBF) [24]. Metoda splin· vychází z p°edstavy ohýbání tenkého kovového plátu tak, aby procházel práv¥ danými kontrolními bod·. Plát se samovoln¥ snaºí zaujmout tvar o nejniº²í energii. Takový tvar se vizuáln¥ jeví jako p°irozen¥j²í neº nap°íklad polynom. Je to dáno práv¥ fyzikálním pozadím £lov¥ku je tvar splinu podv¥dom¥ bliº²í, protoºe se s ním v ºivot¥ setkává. Obecn¥j²í moºnost hledání interpolace roztrou²ených dat p°edstavují radiální bázové
x l =
funkce. To jsou funkce, jejichº funk£ní hodnota závisí jen na vzdálenosti argumentu od n¥jakého daného st°edu
C.
Obvykle jsou pouºívány funkce, které se vzdáleností
δ(C, x)
klesají. Jako funkce vzdálenosti δ slouºí Eukleidovská vzdálenost. Bázová funkce 2 pro jiº zmín¥né spliny má tvar ρ(l) = l ln(l). Hledaná interpolace je pak vyjád°ena lineární kombinací vhodných radiálních bázoPm vých funkcí W (x) = i=1 wi · ρ(δ(ci , x)). V tomto výrazu ci p°edstavují polohy zadaných kontrolních bod·, kterých je celkem m. Spo£ítat je t°eba váhy wi . Výhodou tohoto p°ístupu je relativní jednoduchost my²lenky, od které se odvíjí i jednoduchost implementace. Konkrétních postup· výpo£tu vah je mnoho, li²í se nap°. ve tvaru bázové funkce, ve volb¥ konkrétních numerických parametr· pro výpo£et hledané interpolace nebo samoz°ejm¥ v samotném algoritmu °e²ení vzniklé soustavy rovnic. Zbývá zodpov¥d¥t otázku, co se vlastn¥ v této metod¥ morphingu interpoluje. Uºivatel speci kuje warping pomocí korespondencí ve form¥ °ídicích bod·, tedy dvojic dvojic
((xp , y p ), (xk , y k )). Jako °ídicí objekty proto lze pouºít i úse£ky a k°ivky, pro ú£ely výpo£tu interpretované jako mnoºiny bod·. Tato obecnost °ídicích objekt· oproti sou°adnic
p°edchozím technikám dává uºivateli ve speci kaci korespondencí zna£nou volnost.
2 Scattered data interpolation, interpolace dat na základ¥ malého po£tu nerovnom¥rn¥ rozloºených bod· [32].
28
Výsledný warping
W
má být zobrazením sou°adnic obrazových bod· po£áte£ního obrá-
zku na sou°adnice bod· obrázku koncového. Navíc má toto zobrazení správn¥ zobrazit body korespondence. Pro dvojice °ídicích bod·
W (xp , y p ).
((xp , y p ), (xk , y k ))
má tedy platit
(xk , y k ) =
Práv¥ zde p°ijdou ke slovu metody interpolace roztrou²ených dat radiálními
bázovými funkcemi. Budou hledat spojité a hladké roz²í°ení takto speci kovaného zobrazení. Aby bylo moºné pouºít interpola£ní metody, je t°eba zobrazení bod na bod rozloºit na dv¥ zobrazení bod na sou°adnici, tedy podle os koncového obrázku: a
yk = Wv (xp , yp ).
Hledat se bude práv¥ interpolace zobrazení
plocha tak bude mnoºinou trojic
(xp , yp , xk )
Wh
a
xk = Wh (xp , yp )
Wv . Jedna hledaná (xp , yp , yk ). Jako
a druhá mnoºinou trojic
kontrolní body pro interpolaci poslouºí °ídicí body udávající korespondence. My²lenku p°ibliºuje obrázek 3.3. Sloºením nalezených zobrazení
Wh
a
Wv
pak snadno získáme hledaný warping
W.
S jeho pomocí pak uº m·ºeme podle algoritmu 2.1 spo£ítat celou výstupní posloupnost morphingu. Zásadním d·vodem, pro£ pouºít práv¥ radiální bázové funkce nebo konkrétn¥ spliny je skute£nost, ºe interpolace daného tvaru a vlastností umíme rychle a p°esn¥ spo£ítat [35]. Samotná transformace potom probíhá podobn¥ jako u sí´ového warpingu (oddíl 3.1), tedy dvoupr·chodov¥ zvlá²´ po °ádcích a po sloupcích, se v²emi klady a zápory tohoto p°ístupu. asová náro£nost výpo£tu je op¥t velmi úzce spojena s po£tem zadaných korespondencí. 2 Pro m pár· °ídicích bod· vyºaduje vytvo°ení pot°ebné soustavy rovnic O(m ) krok·. 3 Její vy°e²ení standardními prost°edky (nap°. LU faktorizace) vyºaduje O(m ) krok·. Tím je p°ipravený warping. Zobrazení obrazového bodu pak znamená nalezenou interpolaci v daném bod¥ vyhodnotit. K tomu je t°eba zapo£ítat vliv v²ech °ídicích bod·, náro£nost 2 je tedy O(m) a pro celý snímek O(R · m). Uvedené odhady vychází z informací uvedených v práci [32]. K otázce £asové náro£nosti uve¤me je²t¥ dv¥ poznámky. Po£et pár· °ídicích bod· nemusí být vysoký, pokud jsou korespondence zadávány jako body. Pokud jsou ale zadávány pomocí £ar a k°ivek, nabyde
m mnohem vy²²ích hodnot. Druhá poznámka se týká vyºado-
vané hladkosti. Ta neovlivní asymptotickou sloºitost °e²ení, zásadn¥ ale m¥ní délku kroku výpo£tu. Velkou výhodou metody interpolace korespondencí oproti dosud uvedeným je obecnost °ídicích objekt·. Díky ní m·ºe uºivatel ur£ovat korespondence bez zbyte£ného úsilí a bez zásadních omezení. Na druhou stranu, úse£kový warping nabízí podobné výsledky s mnohem jednodu²²ím matematickým aparátem. Dal²ím kladem je pouºití hladkých funkcí, díky nimº metoda dosahuje velmi plynulých posloupností. Na druhou stranu, £ím hlad²í má být poºadovaný výsledek, tím v¥t²í vliv na warping má kaºdá zadaná korespondence. Úprava umíst¥ní jediného páru °ídicích bod· se tak m·ºe projevit i na relativn¥ vzdáleném míst¥ obrázku, coº uºivateli práci rozhodn¥ neuleh£í.
29
Obrázek 3.3: Ilustrace warpingu jako interpolace zobrazení korespondencí
Schéma ilustruje princip interpola£ních metod. Pro p°ehlednost pracuje s jednorozm¥rným obrázkem. Vodorovná osa znázor¬uje sou°adnice obrazových bod·
Op ,
svislá
Ok .
Vyzna£ené body p°edstavují uºivatelem speci kované korespondence. Metoda interpolace korespondencí najde hladkou interpolaci uºivatelem nazna£eného zobrazení. Ta je potom základem hledaného warpingu
W.
V p°ípad¥ jednorozm¥rných obrázk· zp·sobí
deformace délek úsek· mezi °ídicími body.
30
3.4
Minimáln¥ pracný morphing
Metoda minimalizace práce (work minimization approach, [7] - z tohoto pramene £erpá celý popis metody) je ur£ena pro morphing obrázk·, které se od sebe vzájemn¥ p°íli² neli²í. Tuto jejich podobnost algoritmus vyuºije k pokusu o samo£inné nalezení vhodného morphingu. Snaºí se tak minimalizovat práci uºivatele na speci kaci warpingu. To ale není zdrojem pojmenování této metody. Minimalizovanou prací je my²lena náro£nost samotného procesu morphingu ve smyslu mnoºství a velikosti pot°ebných p°esun· obrazových bod· a jejich p°ebarvování. Tato metoda se tedy od ostatních zna£n¥ li²í. Jako jediná z dosud uvedených bere v úvahu obsah vstupních obrázk· a místo aby £ekala speci kaci warpingu od uºivatele, sama hledá vhodné °e²ení. D·sledkem je, ºe v ideálním p°ípad¥ v·bec nepracuje s korespondencemi. Práv¥ popsaný pom¥rn¥ obecný koncept minimalizace práce m·ºe být realizován r·zn¥. Nyní uvedeme, co je t°eba rozmyslet a speci kovat pro získání konkrétního algoritmu. S tím potom popí²eme jednu osv¥d£enou variantu. Konkrétní algoritmus je tedy ur£en: 1. Zp·sobem ur£ení warpingu a zp·sobem jeho generování. Od nich se odvíjí moºnosti zp·sob· po£ítání pot°ebné práce i moºnosti hledání konkrétních vhodných °e²ení. 2. Zp·sobem ur£ení pracnosti konkrétního °e²ení. Dobrý zp·sob po£ítání pot°ebné práce je nutnou podmínkou pro tvorbu p°irozen¥ vyhlíºejícího morphingu. 3. Zp·sobem hledání optimálního (nejmén¥ pracného) °e²ení. Postup prohledávání obrovské mnoºiny °e²ení je podstatný proto, abychom se v·bec n¥jakého °e²ení do£kali. V následujících odstavcích uº popí²eme zjednodu²enou verzi p·vodní metody, publikované v [7]. Zp·sob reprezentace warpingu vychází ze reprezentace u sí´ového warpingu. Algoritmus kv·li po£ítání pracnosti deformací v¥t²inu £asu p°epo£ítává umíst¥ní obrazových bod·, proto z d·vodu rychlosti nevyuºívá vylep²ení sí´ového warpingu zaloºená na pouºití hladkých funkcí. Zajímavé je, ºe nepracuje celou dobu se stejn¥ hustou °ídicí sítí, ale místo toho ji postupn¥ hierarchicky zjem¬uje. ím je sí´ jemn¥j²í, tím hlad²í m·ºe speci kovat warping. Jemnost sít¥ je dána stupn¥m
st,
jak popí²eme níºe.
Pracnost morphingu daného p°íslu²nou sítí stupn¥
st
je s£ítána po jejích jednotlivých
dílcích:
P =
st −1 2X
Pi,j
(3.2)
i=j=0 P°ísp¥vek
P
jednoho dílku k celkové práci je ur£en následujícím vztahem:
Pi,j = cb
256 R
2
b Pi,j
+ cs
400 2562
s Pi,j
+ co
600 2562
o Pi,j
(3.3)
b Celková práce na morphing dílku i, j sít¥ záleºí na práci na p°ebarvování Pi,j a na s o práci na deformaci Pi,j a Pi,j . D·leºitost jednotlivých aspekt· vyjad°ují empiricky zji²t¥né 31
256 2 400 600 , a . R je délka strany obrázku v obrazových bodech. Tyto váhy R 2562 2562 jsou odpozorovány z experiment·, proto se v nich také objevují hodnoty jako 256. To byl
váhy
rozm¥r obrázk·, se kterými se experimentovalo. Uvedené hodnoty jsou nastaveny tak, aby algoritmus dával dobré výsledky p°i koe cientech
cb , cs
a
co
rovných jedné. Pokud ov²em
algoritmus pro dané vstupní obrázky dobré výsledky nedá, m·ºe je uºivatel zlep²it úpravou vah jednotlivých £len· sou£tu práv¥ pomocí t¥chto koe cient·. b K práci na p°ebarvování Pi,j p°ispívá kaºdý obrazový bod deformovaného £tverce jednodu²e Eukleidovskou vzdáleností p·vodního a p°ebarveného obrazového bodu v pouºívaném prostoru barev. Aby se metoda vyhnula nutnosti pomalého vzorkování, pracuje jen se st°edy obrazových bod·. Jako koncový se vezme ten obrazový bod, do kterého bude st°ed po£áte£ního obrazového bodu zobrazen. Volba barevného prostoru ovliv¬uje vzdálenost barev, £ímº ovliv¬uje i celkovou pracnost konkrétního °e²ení. Algoritmus tedy bude v r·zných barevných prostorech nacházet r·zná °e²ení, a to v£etn¥ warpingu. s o Obtíºnost deformace Pi,j a Pi,j vychází z jednoduchého fyzikálního modelu, který se na ohýbané díly sít¥ dívá jako na idealizované gumové £tverce. Práce na natahování nebo s smr²´ování Pi,j je rovna sou£tu zm¥n délek hran £tverce. Práce na ohýbání a kroucení a o ohýbání Pi,j je úm¥rná sou£tu zm¥n úhl· mezi nimi. Pomocí stupn¥ sít¥ st je normována tak, aby se nem¥nila s jeho zvy²ováním. Zbývá stru£ný popis algoritmu hledání minimáln¥ pracného morphingu (algoritmus 2(st+1) 3.1). Prostor moºných °e²ení je obrovský (má tém¥° 2 stup¬· volnosti) a zahrnuje mnoºství lokálních minim. Na druhou stranu, cílem není globální minimum, ale p°ijateln¥ vyhlíºející morphing. Tomuto ú£elu vyhovuje p°ekvapiv¥ jednoduchý hierarchický p°ístup postupného zjem¬ování a dola¤ování sít¥. Na za£átku má dosud nejlep²í sí´
Sˆst
stupe¬
st = 1
a její jediný neokrajový uzel
1 U1,1
1 na sou°adnicích 1, 1) leºí p°esn¥ uprost°ed obrazu. Sí´ tedy de nuje identické ˆst ) pot°ebná na morphing ur£ený zobrazení, o ºádné zm¥ny tvaru zatím nejde. Práce P (S touto sítí p°esn¥ odpovídá pouhému prolnutí po£áte£ního obrázku Op a koncového obrázku Ok . Po£et krok· algoritmu (°ádek 2.) ur£í uºivatel p°edem prost°ednictvím stupn¥ stmax výsledné sít¥. Hlavním kritériem pro volbu stmax je poºadovaný pom¥r kvality výsledku a ˆst zjemní (°ádek rychlosti výpo£tu. Na konci kaºdého kroku algoritmus dosud nejlep²í sí´ S 9.), £ímº zvý²í její stupe¬ st o 1. Doprost°ed kaºdého dílku p°idá uzel, který jej rozd¥lí na (uzel stupn¥
£ty°i men²í. Uzly uprost°ed ok se spojí s dal²ími novými uzly ve st°edech spoj· starých st uzl·. Po£et uzl· na obou osách sít¥ tedy bude vºdy 2 + 1. Nové uzly jsou rozmíst¥ny tak,
Sˆst−1 P (Sˆst−1 ) = P (Sˆst ).
ºe p·vodní sí´
i nová sí´
Sˆst
ur£ují stejný morphing, a vyºadují tedy stejnou práci
V kaºdém kroku algoritmus zkou²í najít lep²í polohu pro kaºdý uzel
st Uj,k
sít¥ (°ádek
3.). K tomu slouºí p°edem ur£ené série dislokací - n¥kolik posloupností vektor·, o které algoritmus postupn¥ zkusí kaºdý uzel posunout (to °ídí 4. a 5. °ádek).
st °ídicí sít¥ se m·ºe li²it po£et sérií nst , jejich délka i rozloºení zahri nutých dislokací. Dislokace po jednotlivých sériích ∆st (1 ≤ i ≤ nst ) ubývají a zmen²ují se, Pro kaºdý stupe¬
32
Obrázek 3.4: P°íklad t°etí série dislokací uzlu v síti stupn¥ 2
∆32
=
1 1 , 2 2
1 −1 −1 1 −1 −1 , , , , , , 2 2 2 2 2 2
v kaºdé sérii je tedy prohledáváno uº²í okolí uzlu. Krajní uzly sít¥ jsou xovány k okraj·m obrázku. Vhodné nastavení dislokací zji²´ovali auto°i metody empiricky, svá pozorování uvád¥jí v p·vodním £lánku [7].
0 st i Sst s uzlem Uj,k posunutým v obrázku o dané δ ∈ ∆st . 0 ˆst (°ádek Pokud se ukáºe, ºe Sst vede k mén¥ pracnému morphingu neº dosud nejlep²í sí´ S 0 ˆst nahradí (°ádek 8.). Algoritmus 7.), modi kovaná sí´ Sst p·vodní dosavadní optimum sí´ S ádek 6. p°epo£ítává pracnost sít¥
dále pokra£uje v dislokacích dané série, pak dal²ími sériemi, ostatními uzly a jemn¥j²ími sít¥mi. Výstupem algoritmu je nejlep²í nalezená °ídicí sí´
Sˆstmax ,
tedy nejmén¥ pracný
morphing ze v²ech vyzkou²ených. P°epo£ítávání pracnosti (°ádek 7.) bere v úvahu jen zm¥ny v dílcích sít¥, které jsou st st uzlem Uj,k ovlivn¥ny. Tedy nanejvý² £ty°i - totiº ty, které mají Uj,k v n¥kterém svém vrcholu. P°esto toto p°epo£ítávání zabere drtivou v¥t²inu £asu výpo£tu. st Jiný pohled na pr·b¥h algoritmu nabízí sledování konkrétního uzlu sít¥ Uj,k . Jeho poloha v obrázku v okamºiku jeho vzniku (°ádek 9.) je p°esn¥ na st°edu mezi jeho star²ími sousedy. Posléze je v kaºdém kroku znovu a znovu p°ehodnocována (4. aº 8. °ádek) pomocí sérií i dislokací ∆st . Jejich zmen²ování ale neznamená ztrátu kontroly nad podobou morphingu na opu²t¥ných plochách. O ty se starají dal²í a dal²í mlad²í uzly, které vznikají díky postupnému zjem¬ování sít¥. P°es v²echnu snahu mohou být získané výsledky nep°ijatelné, nap°. z následujících p°í£in: 1. Sí´ový model má svá omezení, uvedená p°edev²ím v oddílu 3.1. 2. Algoritmus nijak nezaru£uje, ºe nalezený morphing bude globálním minimem. 3. Zp·sob výpo£tu pracnosti je pouze jeden z moºných, ne nutn¥ ten správný a odpovídající danému ú£elu a vstupním obrázk·m. 4. V principu ani nemusí pokaºdé platit, ºe mén¥ pracný morphing bude hez£í. Pro takové p°ípady se nabízí dv¥ p°ímo£aré moºnosti, jak situaci vy°e²it. První z nich je nechat uºivatele p°ipravit °ídicí sí´, podobn¥ jako p°i sí´ovém morphingu. Tu pak bude algoritmus dále zp°es¬ovat. To je vhodné zejména tehdy, kdyº nalezený warping vypadá zcela jinak, neº bylo o£ekáváno. Druhou moºností korekce warpingu je nechat uºivatele ur£it n¥kolik zásadních kore(xp , xk ). P°ísp¥vek P d je úm¥rný vzdálenosti obrazu
spondencí pomocí dvojic °ídicích bod·
33
Algoritmus 3.1
Minimáln¥ pracný morphing
Op ∆ist
Vstup: Obrázky série dislokací
a
Ok
(pouºity pro výpo£et
P
v kroku 7.), maximální stupe¬ sít¥
stmax ,
Postup: 1. Inicializuj 2.
Sˆ1
na identické zobrazení
for st = 1 to stmax :
3.
st ∈ Sˆst : for each Uj,k
for i = 1 to nst :
4.
for each δ ∈ ∆ist :
5. 6.
0 = Sˆst Sst
7.
0 if P (Sst ) < P (Sˆst ), P
Výstup:
st Uj,k
posunutým o
δ
podle vztahu (3.2)
:
0 Sˆst = Sst
8. 9.
s uzlem
Sˆst+1 =
zjemn¥ní sít¥
Sˆst ,
ur£ující ekvivalentní transformaci
Sˆstmax
bodu z po£áte£ního obrázku
W (xp )
a jeho p·vodn¥ poºadovaného umíst¥ní
xk .
Konkrétní
moºnosti výpo£tu p°ísp¥vku uvádí [7]. To algoritmus nutí up°ednostnit warping, který dvojice zobrazí p°esn¥ji, a tedy lépe odpovídá daným korespondencím. Jasnou výhodou tohoto algoritmu oproti ostatním je schopnost generovat morphing samostatn¥. I v p°ípadech, kdy jsou nutné opravné zásahy uºivatele, z·stává celková pot°eba jeho zapojení do tvorby morphingu oproti ostatním metodám zanedbatelná. Lze tak u²et°it obrovské mnoºství práce, i kdyº ne v²echnu. Na práci s metodou a nutnost oprav se dá nahlíºet i naopak. Pot°ebné korespondence lze zadat ru£n¥ rovnou a jako výsledek o£ekávat nejen hladkou deformaci jako od ostatních metod, ale hlavn¥ deformaci mnohem lépe odpovídající obsahu vstupních obrázk·. A to i v detailech, kterými se p·vodn¥ zadané korespondence nezabývaly. asová sloºitost metody minimalizace práce je obtíºná otázka. Generování výsledných snímk· je stejn¥ sloºité jako u sí´ového morphingu. Navíc s niº²í konstantou, protoºe po£áte£ní sí´ je u minimalizace práce nedeformovaná, takºe s ní lze po£ítat rychleji. Doba hledání nejmén¥ pracného morphingu ov²em roste exponenciáln¥ s maximálním stupn¥m
stmax . Prostota warpingu zaji²t¥na není. Obvykle není poru²ena, ale je to dáno jen volbou parametr· metody pro hledání morphingu. Schopnost nalézat dobré výsledky je omezena na podobné obrázky, tedy aspo¬ pokud algoritmu nepom·ºeme vlastním návrhem korespondencí. Se schopností pracovat samo-
34
statn¥ samoz°ejm¥ také p°ímo souvisí jistá nep°edvídatelnost výsledku. N¥kdy je navíc t°eba upravovat parametry metody (váhy £len·, maximální stupe¬ sít¥, prohledávaná okolí uzl·). Taková práce je pro uºivatele my²lenkov¥ mnohem náro£n¥j²í, neº správné rozmis´ování °ídicích objekt· známé z ostatních metod. P°esto metoda p°edstavuje významný koncep£ní i praktický p°ínos problematice morphingu.
3.5
Minimalizace energie
Úse£kový morphing i interpola£ní techniky mohou dávat posloupnosti, na kterých jedna £ást obrazu p°ekryje jinou, sousední plochu. To je zpravidla neºádoucí jev. Hlavním cílem následující metody je práv¥ zabránit p°ekryv·m, neboli zajistit prostotu warpingu, a p°itom zachovat klady p°edchozích metod. Tento zajímavý p°ístup byl publikován v [14]. Metoda minimalizace energie umoº¬uje speci kovat korespondence zcela obecnými °ídicími objekty (k°ivky, úse£ky, body), které potom intern¥ namapuje na dvojice bod·. Algoritmus morphingu minimalizací energie se podobn¥ jako metoda minimalizace práce inspiruje fyzikou. Na warping se dívá jako na dvojrozm¥rnou deformaci £ty°úhelníkové plochy. Její tvar je pod°ízen vztah·m inspirovaným práv¥ fyzikou. Vyjad°ují potenciální energii skrytou v deformované plo²e. Výsledný tvar plochy je získán minimalizací sou£tu v²ech t¥chto vztah·. Konkrétní vztahy pro výpo£et podrobn¥ popisuje t°etí £ást £lánku [14]. Tyto vztahy zaji²´ují hladkost deformace, její prostotu, dodrºení korespondencí a díky fyzikálnímu pozadí také p°irozenost výsledku. Warping vygenerovaný pomocí minimalizace energie je tedy prostý, a díky tomu je navíc oproti výsledk·m ostatních metod je²t¥ hlad²í. Daní za to je ov²em vysoká £asová náro£nost výpo£tu (iterativní hledání numerického °e²ení soustavy rovnic) a pom¥rn¥ obtíºná implementace [34].
3.6
Víceúrov¬ová volná deformace
Problém prostoty warpingu °e²í krom¥ metody minimalizace práce také víceúrov¬ová volná deformace (MFFD, Multilevel free-form deformation),popsaná v [13]. Na warping se dívá jako na transformaci sou°adného systému a s ním i celé plochy obrázku. V tomto smyslu jde o zobecn¥ní sí´ového morphingu, který lze chápat stejn¥. Víceúrov¬ová volná deformace umoº¬uje zadávat korespondence obecn¥ a chápe je jako °ídící uzly pro interpolaci k°ivek. Sou°adnicové osy tedy mohou být i k°ivo£aré, obvykle se pouºívají B-spliny. Podobnost víceúrov¬ové volné deformace a sí´ového warpingu je i v práci uºivatele - jeho úkolem je sesadit °ídicí objekty s klí£ovými místy vstupních obrázk·. Algoritmus intern¥ pracuje s vlastní °ídicí sítí, kterou podobn¥ jako algoritmus hledání minimáln¥ pracného morphingu postupn¥ zjem¬uje. Uzly sít¥ jsou °ídicími uzly dvojrozm¥rného kubického B-splinu. Algoritmus nejd°ív obraz rozd¥lí jedním °ídicím uzlem na £ty°i dílky. Pomocí varianty algoritmu volné deformace
3 Free-form
deformation, podle [34] je p·vodní popis v [26]. 35
3
hledá tvar sít¥ (rozmíst¥ní uzl·),
který co nejlépe vyhoví zadaným korespondencím. Prostota warpingu je zaji²t¥na omezením úprav sít¥ - délka p°esunu ºádného uzlu nesmí p°esáhnout polovinu rozestupu mezi uzly. Kv·li tomuto omezení ale získaná sí´ nezaru£uje p°esné zobrazení korespondencí. Hledání nových poloh uzl· a tím zp°es¬ování zobrazení korespondencí se proto proto opakuje, dokud zm¥na hodnoty chyby (3.4) nep°esáhne uºivai i telsky daný práh. Dvojice (xp , xk ) ur£uje jednu z korespondencí. Vzorec tedy s£ítá £tverce i i odchylek zobrazených bod· korespondence Wakt xp od jejich zamý²lených pozic xk .
E=
X
xik − Wakt xip
2
(3.4)
i Kdyº se uº tedy neda°í lépe vystihnout korespondence, algoritmus p°idá °ídicí uzly stejným zp·sobem jako algoritmus minimalizace práce. Umoºní tak hledání jemn¥j²í deformace. Op¥t jde o dvojrozm¥rný kubický B-spline s omezeným maximálním p°esunem °ídicích uzl·, tentokrát je ov²em jejich sí´ dvakrát jemn¥j²í. Tímto postupným zjem¬ováním algoritmus nakonec najde prostou hladkou deformaci, která p°esn¥ zobrazuje dané korespondence. Z hlediska pouºití je tato metoda podobná metod¥ minimalizace energie. Umoº¬uje snadno a zárove¬ precizn¥ speci kovat poºadovaný warping a dává velmi kvalitní výsledky. Na rozdíl od metody minimalizace energie je ale mnohem jednodu²²í a díky vyuºití víceúrov¬ové hierarchie i rychlej²í. Na druhou stranu ale kv·li víceúrov¬ové hierarchii a exibilní ukon£ovací podmínce není znám pouºitelný odhad £asové sloºitosti. Tvar hledané deformace má totiº na délku výpo£tu mnohem v¥t²í vliv neº velikost vstupu.
3.7
Záv¥re£né srovnání
Po d·kladném seznámení se s úlohou morphingu a po p°edstavení nejd·leºit¥j²ích metod k jejímu °e²ení m·ºeme metody stru£n¥ porovnat a nastínit doporu£ení, kterou volit pro který p°ípad. To zárove¬ nazna£uje nejpodstatn¥j²í zji²t¥ní z p°edchozí a z této kapitoly: dosud není známa ºádná obecn¥ dob°e pouºitelná metoda morphingu. Vzhledem k subjektivním prvk·m v zadání totiº v principu ani neexistuje. Pro kaºdou konkrétní úlohu je vºdy t°eba zváºit výhody a nevýhody jednotlivých dostupných metod a podle nich se pro jednu z metod rozhodnout [8, str. 96]. Pokud je °e²ená úloha zvlá²t¥ speci cká, stojí za zváºení vyuºít kombinaci metod nebo vyvinout metodu vlastní. Osv¥d£ený zp·sob zb¥ºného posouzení kvality morphingu spo£ívá v kontrole prost°edního snímku posloupnosti. Pokud vypadá p°irozen¥ a nejsou patrné polopr·svitné £ásti objekt· z po£áte£ního £i koncového obrázku, budou pravd¥podobn¥ v po°ádku i ostatní snímky posloupnosti. Východiskem a prvotní inspirací pro ostatní metody je sí´ový morphing. V¥t²ina dostupných softwarových nástroj· pouºívá práv¥ tuto metodu. Pokud nemáme speci cké poºadavky, jde o p°ijatelné kompromisní °e²ení. V obrazu nehrozí vznik p°ekryv· nebo nespojitostí. Lze jej snadno doplnit o lokální °ízení rychlosti p°echod·.
36
Úse£kový morphing nabízí snaz²í a p°irozen¥j²í speci kaci korespondencí. Lze s ním proto dosáhnout vy²²í produktivity práce. Ob£asný výskyt ne£ekaných kaz· výsledku vyºaduje kvali kovan¥j²ího uºivatele. Vyloºen¥ vhodný je tento algoritmus pro lokální úpravy v obrazu. Zahrnout do n¥j také lokální °ízení rychlostí p°echod· je ale náro£né. Doba výpo£tu je vysoká, s drobnými ztrátami kvality výsledku ji lze sníºit. Metody zaloºené na interpolaci roztrou²ených dat umoº¬ují je²t¥ obecn¥j²í práci s korespondencemi neº úse£kový morphing. Generují hladké warpingy a po£ítají rychle, protoºe nemusí pro kaºdý obrazový bod zvaºovat v²echny korespondence. Osv¥d£ují se zejména v p°ípadech, kdy je pro ur£ení korespondencí t°eba pouºít velmi obecné °ídicí objekty. Tvarov¥ sloºité deformace ov²em nezvládá p°íli² dob°e, hrozí vznik p°ekryv· v obrazu. Algoritmus lze p°irozen¥ roz²í°it o lokální °ízení rychlosti p°echod·. Minimáln¥ pracný morphing p°edstavuje vhodnou volbu pro morphing podobných obrázk·. Za zváºení stojí i jeho pouºití jako podp·rného nástroje pro v²echny ostatní p°ípady. M·ºe automaticky dola¤ovat detaily v mén¥ podstatných oblastech obrázku, kde by na nich uºivatel zbyte£n¥ ztrácel £as. Dal²í vlastnosti warpingu (hladkost, prostota) odpovídají sí´ovému warpingu. Metoda minimalizace energie je dnes zajímavá spí²e teoreticky. Jejím hlavním p°ínosem je prostota vygenerovaného warpingu, té lze ov²em dosáhnout jednodu²eji a rychleji s pomocí metody víceúrov¬ové volné deformace. Ta p°ijímá korespondence speci kované pomocí bod·, tedy stejn¥ obecn¥ jako v p°ípad¥ interpola£ních metod. Prostota výsledného warpingu ale staví metodu víceúrov¬ové volné deformace nad moºnosti interpola£ních metod, aspo¬ pokud není p°edn¥j²í rychlost výpo£tu. Roz²í°ení o lokální °ízení rychlosti p°echod· lze op¥t zapracovat bez zásadních problém·. V praxi se tyto metody £asto kombinují s ostatními. Krom¥ £istého morphingu tak ke slovu p°ichází vyuºití klasických postup· zpracování obrazu (práce s jasem a kontrastem, barevné vyváºení, doost°ování apod.) a speciálních efekt· (viz jiº zmín¥ný Indiana Jones v oddílu 2.1, podrobn¥ji v [33, str. 231]). V poslední dob¥ je navíc ve lmovém pr·myslu morphing obrázk· stále £ast¥ji nahrazován morphingem trojrozm¥rných objekt· (viz oddíl 2.4.3), kdy je celá scéna vytvo°ena z digitálních model·. Tento p°ístup na jednu stranu dává tv·rc·m plnou kontrolu nad výslednou scénou, na druhou stranu je ale po v²ech stránkách náro£n¥j²í.
37
Kapitola 4 Samoorganizace Tato kapitola se v¥nuje fenoménu samoorganizace a jeho vyuºití v um¥lé inteligenci. Po stru£ném obecném úvodu následuje jádro kapitoly, kterým je popis Kohonenovy samoorganiza£ní mapy a n¥kolika jejích pokro£ilých variant v£etn¥ jejich srovnání. Toto srovnání diskutuje p°edev²ím dynamiku struktur co do velikosti i topologie, £asovou efektivitu, vstupní parametry a schopnost pr·b¥ºné adaptace na nová data. Z uvedených metod potom vychází dal²í úvahy, vedoucí k samoorganiza£ním metodám morphingu. Tento úvod kapitoly ja inspirován p°edev²ím £lánky [5, 12]. Samoorganizace je fenomén, pozorovaný v mnoha rozli£ných v¥dních oborech - p°edev²ím ve fyzice, dále v chemii, biologii, ale i ekonomii a sociologii. A samoz°ejm¥ v informatice, v £ele s um¥lou inteligencí. V²echny tyto obory p°ichází se svými pokusy o de nici. Lze v nich vysledovat spole£né jádro, ov²em v otázce hranice toho, co p°esn¥ je²t¥ je a co uº není samoorganizace, nepanuje ºádná významná shoda. Pojem samoorganizace je v tomto sm¥ru podobný takovým pojm·m, jako jsou ºivot nebo inteligence. Uvedeme proto rad¥ji znaky, které dob°e osv¥tlují, co samoorganizace je. Je to jev, kdy systém sloºený z jednodu²²ích £ástí samovoln¥ vykazuje ne£ekan¥ sloºité chování (vzhledem k vlastnostem jeho £ástí). Systém musí být otev°ený, neboli interagující s okolím - vym¥¬uje si s ním energii, hmotu nebo entropii. Ke sloºit¥j²ímu chování musí docházet samovoln¥, neboli bez dal²ích vn¥j²ích zásah·, tlak· nebo °ízení - autonomn¥, jen na základ¥ interakcí £ástí. V pr·b¥hu £asu se obvykle zvy²uje komplexita vnit°ní organizace systému a struktury vazeb mezi jednotlivými £ástmi. Práv¥ tyto bohaté vazby jsou pro fungování systému zpravidla klí£ové. Jejich popis je tedy nezbytnou sou£ástí úplného popisu celého systému. Vazby obvykle mimo jiné zaji²´ují rovnováhu pozitivních a negativních zp¥tných vazeb v systému. Samoorganizace v um¥lé inteligenci je velmi úzce spjata s u£ením bez u£itele. U£ený systém je konfrontován s daty o vn¥j²ím sv¥t¥ a n¥jakým zp·sobem na n¥ reaguje. U£í se bez u£itele, takºe mu nikdo neposkytne informace o tom, co vlastn¥ data znamenají, ani o tom, jak dob°e reaguje.
38
Z°ejm¥ to nejlep²í, co lze v takové situaci d¥lat, je data vhodn¥ rozt°ídit a najít mezi nimi podstatné vztahy. V samoorganizovaných systémech v um¥lé inteligenci také zpravidla vzniká n¥jaký zjednodu²ující vnit°ní model vn¥j²ího sv¥ta - aniº by byla k dispozici nápov¥da, jak tento model tvo°it. U£ení bez u£itele se proto uplatní nap°íklad p°i pot°eb¥ rozd¥lení pro £lov¥ka nesourodých dat na
shluky
(klastry), tedy na skupiny vzájemn¥
podobných záznam·. Jindy je naopak pot°eba nezávisle ov¥°it, jestli jsou p°edem zkonstruované shluky skute£n¥ zvoleny vhodn¥. Skladba systém· u£ících se bez u£itele odpovídá uvedeným rys·m samoorganizujících se systém·. Jde obvykle o relativn¥ jednoduché výpo£etní jednotky propojené £etnými vazbami, pomocí kterých mezi sebou jednotky bohat¥ interagují. Struktura t¥chto vazeb se postupem £asu m·ºe m¥nit. Jednotlivé jednotky jsou £asto v konkurenci, uplat¬ují se tzv. sout¥ºní strategie u£ení. Jednotky mají díky propojujícím vazbám informace o svém nejbliº²ím okolí, o systému jako celku ov²em £asto nev¥dí nic.
4.1
Kohonenova samoorganiza£ní mapa
Ke klasickým vyuºitím samoorganizace v um¥lé inteligenci pat°í Kohonenovy samoorganiza£ní mapy (SOM), detailn¥ popsané a diskutované v publikaci [11]. P¥kný popis v £e²tin¥ nabízí [31, 18, 19]. Z t¥chto pramen· £erpáme v celém oddílu o samoorganiza£ních mapách. SOM je varianta um¥lé neuronové sít¥ [22] pro u£ení bez u£itele.
4.1.1
Pouºití SOM
Úkolem samoorganiza£ní mapy je nej£ast¥ji redukce dimenzionality dat, kvantizace spojitého signálu, klasi kace vektor· nebo reprezentace pravd¥podobnostního rozloºení vstupních dat. Tyto úlohy dále stru£n¥ a neformáln¥ popí²eme. V jádru jsou velmi podobné. Lze na n¥ pohlíºet také jako na r·zné interpretace stejných výsledk·. D Vstupem samoorganiza£ní mapy jsou £íselné vektory z R , kde
D
je délka vektoru,
tedy dimenze dat. Vektory spl¬ují n¥jaké dané (ale nikoliv nutn¥ p°edem známé) pravd¥podobnostní rozloºení. Na jejich po£tu nezáleºí, mapa je zpracovává postupn¥ po jednom.
x = (x1 , x2 , . . . , xD ), tzv. vzoru, odpoví prostoru, který vzor x dob°e reprezentuje.
SOM po p°edloºení vstupního vektoru
wv = (wv1 , wv2 , . . . , wvD )
z téhoº
vektorem
Vzor totiº pat°í do n¥kterého ze shluk·, které mapa v datech rozpoznala. Kaºdý shluk, a tím i kaºdý vektor v n¥m, je reprezentován n¥jakým typickým vektorem. Tím nemusí být ºádný ze vstupních vektor·, podstatné je, ºe je nejpodobn¥j²í v²em ostatním vektor·m daného shluku. Práv¥ tento typický vektor - reprezentant - je odpov¥dí mapy na p°edloºený vzor. Podobnost je nej£ast¥ji ur£ována vhodn¥ de novanou vzdáleností mezi vektory. Mapou ur£ené shluky jsou p°ibliºn¥ stejn¥ po£etné. Výstupní vektory proto dob°e vystihují pravd¥podobnostní rozloºení vzor·. Pravd¥podobnost, ºe p°í²t¥ p°edloºený vzor bude reprezentován konkrétním výstupním vektorem, je pro v²echny výstupní vektory p°ibliºn¥ stejná.
39
S tím p°ímo souvisí, ºe náhradou vstupních vektor· výstupními (nap°. kv·li ²et°ení pam¥tí) ztratíme o p·vodních datech nejmén¥ informací. Proto se SOM dob°e uplatní v úlohách diskretizace spojitého (zejména vícerozm¥rného) signálu, resp. kvantizace vektor·. Úloha klasi kace vektor· p°edpokládá, ºe vstupní vektory skute£n¥ do n¥jakých shluk· uspo°ádány jsou. N¥kdy dokonce shluky známe p°edem. Cílem je rozpoznat, do kterého shluku pat°í daný vstupní vektor. Kv·li pam¥´ové náro£nosti obvykle není moºné shluky de novat prostým vý£tem jejich vektor·. Ty v principu ani nemusí být v²echny k dispozici. Proto se zde obvykle dob°e uplatní SOM, která shluky de nuje a hledá prost°ednictvím reprezentujících vektor·. Tentokrát výstupní vektor nereprezentuje ani tak p°ímo p°edloºený vzor, ale spí² shluk, do kterého vzor pat°í. Dosud nezmín¥ným, ale naprosto zásadním rysem Kohonenových samoorganiza£ních map je schopnost udrºet vzájemnou podobnost vektor·. Dv¥ma podobným vzor·m budou odpovídat vzájemn¥ podobné výstupní vektory. Mapa totiº data vnit°n¥ reprezentuje v pravidelné, nej£ast¥ji dvourozm¥rné m°íºce. Díky ní výstupní vektory respektují topologii rozloºení vstupních vektor·, p°estoºe její dimenze m·ºe být mnohem vy²²í, neº dimenze m°íºky. Díky této vlastnosti lze SOM vyuºít k redukci dimenzionality vstupních dat. Mapa pom·ºe uºivateli promítnout sloºitá data do p°ehledn¥j²ího prostoru a p°itom mezi nimi zachovat nejd·leºit¥j²í vztahy.
4.1.2
Struktura SOM
Samoorganiza£ní mapa se skládá ze dvou vrstev um¥lých neuron· - základních stavebních a výpo£etních jednotek. Kaºdý neuron vstupní vrstvy je propojen s celou výstupní vrstvou a odpovídá n¥které sloºce vstupních neuron·. Jeho úkolem je jen p°edat v²em výstupním neuron·m informaci o velikosti dané sloºky vstupního neuronu. Skute£ná práce probíhá na úrovni výstupní vrstvy. Kaºdý její neuron je krom¥ vstupních neuron· spojen je²t¥ s n¥kolika dal²ími výstupními neurony. Tato spojení nejsou ohodnocena a tvo°í nej£ast¥ji dvourozm¥rnou m°íºku se £tvercovou topologií. Lze také pouºít nap°. ²estiúhelníkovou topologii nebo i jiný rozm¥r m°íºky. Tyto laterální vazby umoº¬ují de novat topologickou vzdálenost mezi neurony
τ (i, j)
a pojem sousedství neuronu.
Sousedy
neuronu jsou ty neurony, které jsou s ním p°ímo spojeny. Pro výpo£et
τ
j , nebo Eukleifunkci τ lze p°i u£ení
lze pouºít nap°. po£et vazeb na nejkrat²í cest¥ mezi
dovskou vzdálenost mezi jejich polohami v topologické m°íºce. Díky
i
a
mapy pracovat s topologickým okolím neuron·. Váhové vektory
w = (w1 , w2 , . . . , wD ) výstupních neuron· jsou práv¥ výstupními vek-
tory z úvodu oddílu o Kohonenových samoorganiza£ních mapách. Proto se b¥ºn¥ mluví o poloze neuronu v prostoru a pokud nehrozí zmatení, jsou neuron a jeho váhový vektor voln¥ zam¥¬ovány. Výstupní neurony po£ítají vzdálenost p°edloºeného vzoru a svého váhového vektor·, neboli své polohy. ím jsou blíºe, tím vy²²í je jejich excitace.
40
4.1.3
Vybavování SOM
Úkolem samoorganiza£ní mapy je p°edloºenému vzoru výstupní neuron
v,
resp. reprezentující vektor
wv .
x
ze vstupního prostoru p°i°adit
P°edloºený vzor zpracovává nejprve
vstupní vrstva. Kaºdý její neuron po²le po jedné sloºce vektoru vzoru kaºdému neuronu výstupní vrstvy. Kaºdý neuron
i výstupní vrstvy tedy dostane na vstupu celý p°edloºený vzor. S pomocí wi spo£te, jak je od n¥j vzdálen, nap°. Eukleidovsky: v u D uX δ(x, wi ) = t (xk − wik ) (4.1)
svého váhového vektoru
k=0 Prost°ednictvím vazeb mezi sebou neurony uplatní mechanismus laterální inhibice. ím excitovan¥j²í neuron (bliº²í ke vzoru), tím siln¥ji bude tlumit aktivitu neuron· ve svém topologickém okolí. Tak z·stane aktivní jen jediný neuron x - práv¥ ten, který je p°edloºenému vzoru nejblíºe ze v²ech neuron·
wi
výstupní vrstvy.
∀wi : δ(x, wi ) ≥ δ(x, wv ) Tento neuron
v
je
vít¥zem
(4.2)
sout¥ºe o reprezentaci vzoru a je výstupem samoorgani-
za£ní mapy. Jeho aktivita ukazuje na p°íslu²nost p°edloºeného vzoru k tímto neuronem reprezentovanému shluku.
4.1.4
U£ení SOM
Aby výsledky vybavování samoorganiza£ní mapy dávaly smysl, musí se mapa nejd°ív nau£it, jaká data má vlastn¥ zpracovávat. Toto u£ení bude probíhat bez u£itele, jen na základ¥ samotných dat (p°edkládaných vzor·). Jeho cílem je rozmístit výstupní neurony ve vstupním prostoru tak, aby jej mezi sebe rovnom¥rn¥ rozd¥lily. Ideáln¥ by se kaºdý neuron m¥l dostat do t¥ºi²t¥
1
významného
shluku. Na tento shluk je pak neuron specializován, ten reprezentuje. P°itom je navíc t°eba alespo¬ lokáln¥ zachovat topologii dat. Kohonen v této souvislosti pouºívá výstiºný p°íklad s kv¥tinou v herbá°i. Algoritmus u£ení vyuºívá jiº popsaný mechanismus vybavování a obohacuje jej o adapta£ní pravidla. Pro kaºdý p°edloºený vzor
x
najde reprezentanta
v
podle aktuálního stavu
mapy. Aby tento vít¥zný neuron p°í²t¥ reprezentoval je²t¥ lépe, posune jej algoritmus sm¥rem ke vzoru. Krom¥ vít¥ze posune i jeho blízké sousedy v topologické m°íºce. Toto se opakuje mnohokrát za sebou s dal²ími a dal²ími vzory. Posuny vít¥z· jsou stále krat²í a jejich p°izp·sobované okolí stále uº²í. Výsledkem je mapa, která dob°e pokrývá pravd¥podobnostní rozloºení p°edkládaných vzor·. V následujících odstavcích algoritmus u£ení samoorganiza£ní mapy (Algoritmus 4.1) popí²eme podrobn¥.
1 T¥ºi²t¥
ve smyslu pravd¥podobnostního rozd¥lení vzor·. 41
Algoritmus 4.1
U£ení Kohonenovy samoorganiza£ní mapy
Vstup:
• Dimenze D vstupního prostoru a vzorové vektory • Rozm¥ry a topologie výstupní vrstvy mapy (v£etn¥ funkce vzdálenosti τ ) • Posloupnost u£ícího parametru αt • Funkce laterální interakce φ a posloupnost polom¥ru okolí σt • Ukon£ovací podmínka
Postup: 1.
Inicializace: Napl¬ váhové vektory výstupních neuron· náhodnými £ísly.
2.
Dokud není spln¥na ukon£ovací podmínka, opakuj kroky (a) - (d). (a)
P°ijmi nový p°edloºený vzor x.
(b)
Pro kaºdý výstupní neuron i spo£ti jeho vzdálenost od vzoru x podle (4.1).
(c)
Vyber vít¥zný neuron v , který spl¬uje (4.2).
(d)
Adaptuj váhy vít¥ze a neuron· v jeho okolí podle (4.3).
Výstup: SOM nau£ená na p°edkládaná data.
42
Na za£átku je výstupní vrstva náhodn¥ inicializována. Jde tedy o neuspo°ádaný shluk vektor·, vazby mezi nimi nemají s jejich rozmíst¥ním v prostoru ºádnou souvislost. Na náhodné inicializaci se demonstruje robustnost samoorganiza£ních map. V praxi se proces u£ení £asto urychluje pouºitím smyslupln¥j²í inicializace, nap°. výb¥rem náhodných vzor· nebo vyuºitím p°edem známých dal²ích informací o rozloºení vzor· v prostoru. Po inicializaci uº následuje postupné p°edkládání vzor·. Algoritmus spo£te vzdálenost p°edloºeného vzoru a kaºdého výstupního neuronu nap°. podle (4.1). Alternativou k pouºití Eukleidovské vzdálenosti (samoz°ejm¥ i pro vybavování) je normalizace vektor· na jednotkovou kouli a prostý skalární sou£in. Ten pak odpovídá kosinu úhlu mezi vzorem a váhovým vektorem. Neuron je samoz°ejm¥ tím blíº vzoru, £ím men²í úhel s ním svírá.
D-rozm¥rné
V²echny neurony se pohybují na
jednotkové kouli a riziko uváznutí daleko od
vzor· je tak výrazn¥ sníºeno. Jako vít¥ze
v
algoritmus vybere neuron, který se nachází nejblíº p°edloºenému vzoru.
Následuje adaptace váhových vektor· neuron· na vzor:
∆wi = αt · φ(τ (v, i), t) · (x − wi )
(4.3)
Zm¥na vah neuron· je p°ibliºuje k danému vzoru. Míra tohoto p°iblíºení je zásadn¥ ovlivn¥na funkcí laterální interakce
φ.
Díky ní se nejvýrazn¥ji adaptuje vít¥zný neuron,
mén¥ uº jeho sousedé a topologicky vzdálené neurony se v·bec nepohnou. Okolí vít¥zného neuronu, které se adaptuje s ním, se v pr·b¥hu u£ení postupn¥ zuºuje. Funkce klesá s rostoucí topologickou vzdáleností s ubíhajícím £asem
t
τ (v, i)
φ
tedy
mezi vít¥zem a adaptovaným neuronem i
(kroky u£ení).
Jako nejjednodu²²í variantu
φ
lze pouºít charakteristickou funkci okolí. Pro neurony
z topologického okolí neuronu o polom¥ru
σt
funkce nabyde hodnoty 1 (plná adaptace),
pro ostatní 0 (ºádná adaptace). Výpo£etn¥ náro£n¥j²í, nicmén¥ hlad²í a ú£inn¥j²í variantu p°edstavuje Gaussova funkce. Parametr
σt
i zde de nuje polom¥r okolí, který postupn¥
klesá.
τ (i, j)2 φ(τ (i, j), t) = exp − 2σt2
(4.4)
Druhým zásadním £initelem ovliv¬ujícím adaptaci neuron· je monotónn¥ klesající u£ící parametr
αt , £asto zvaný také plasticita sít¥. Vyjad°uje p°izp·sobivost výstupních neuron·.
Na za£átku bývá vysoká (blízká jedné), je t°eba rychle vystihnout základní charakteristiky rozloºení vzor·. Následn¥ p°i jemném dola¤ování p°esného umíst¥ní neuron· uº je výhodn¥j²í nízká hodnota u£ícího parametru
αt
(blízká nule). P°ekvapiv¥ celkem nezáleºí na tom,
jak p°esn¥ u£ící parametr klesá, pokud spl¬uje následující:
∞ X
αt = ∞
∧
t=1
∞ X
αt2 < ∞
(4.5)
t=1
Algoritmus je obvykle ukon£en po p°edem daném po£tu krok· (v praxi °ádov¥ tisíce). Vhodn¥j²í by se zdálo pouºití inteligentn¥j²ího kritéria, které by poznalo, kdy uº je mapa dob°e nau£ená. Ukazuje se ale, ºe v praxi je obtíºné najít univerzáln¥ pouºitelnou funkci
43
(nap°. chybovou
2
nebo energetickou), jeº by umoº¬ovala p°edem stanovit rozumnou a
spolehlivou ukon£ovací podmínku.
4.1.5
Dopl¬ující poznámky
B¥hem u£ení SOM lze, a£koliv to není patrné ze samotného algoritmu, rozli²it dv¥ fáze. V první, hrubé fázi se p·vodn¥ neuspo°ádaná výstupní vrstva postupn¥ rozvine podle své topologie a topologie p°edkládaných dat. Ve druhé fázi uº pak jednotlivé neurony pe£liv¥ zaujímají pozice, aby se dostaly co nejp°esn¥ji do t¥ºi²t¥ reprezentovaných shluk·. Za zmínku zde stojí i biologické pozadí Kohonenovy samoorganiza£ní mapy. Prvotní práce byly inspirovány poznatky o fungování p°irozených um¥lých sítí. V mnoha zásadních rysech se SOM opravdu nápadn¥ podobá strukturám v p°irozených neuronových sítích. Nap°íklad lokální zachování topologie se projevuje i na mozkové k·°e. Oblasti hmatového vnímání blízkých £ástí t¥la (nap°. jednotlivé prsty ruky) se nachází blízko sebe i na mozkové k·°e. SOM jsou proto také vhodným p°edm¥tem biologicky motivovaného zkoumání. Uvedený základní model SOM má samoz°ejm¥ i nevýhody a omezení. Mezi ty hlavní pat°í mnoºství vstupních informací, které je t°eba ur£it p°ed samotným u£ením. Tedy p°edev²ím velikost a topologii výstupní vrstvy a dále délku u£ení a pr·b¥h adapta£ních parametr·. asto aº mnoho zdlouhavých pokus· ukáºe, které hodnoty by bývaly k nau£ení daných dat poslouºily lépe. Mnohem pohodln¥j²í by bylo, kdyby aspo¬ n¥co z toho dokázala mapa vhodn¥ odhadnout na základ¥ p°edkládaných vzor·.
4.2
Rostoucí samoorganiza£ní mapa
,
lánek [1] podrobn¥ popisuje dynamicky rostoucí samoorganiza£ní mapu (GSOM) ve které v p°ípad¥ pot°eby p°ibývají výstupní neurony. V následujícím popisu z n¥j vycházíme. Zamý²lené pouºití GSOM se týká p°edev²ím dobývání znalostí. Uºivatel typicky neví, kolik shluk· má o£ekávat, a jak velkou mapu tedy zvolit. Naopak je rád, kdyº se na data m·ºe podívat v p°ehledném rovinném zobrazení. Struktura GSOM vychází ze struktury SOM, máme tytéº dv¥ vrstvy neuron·. Topologie výstupní vrstvy je ale omezena na dvourozm¥rnou £tvercovou m°íºku. GSOM vyuºívá obdobu u£ícího parametru práh r·stu
P
αt
φ. Oproti SOM si navíc pamatuje Ei kaºdého výstupního neuronu i. Sloºky vstupních interval [0, 1]. V²echny zm¥ny se týkají procesu u£ení, kdy a funkci laterální interakce
a kumulovanou chybu
vektor· jsou normovány na
mapa roste. Vybavování pak probíhá stejn¥ jako v SOM.
4.2.1
U£ení GSOM
U£ení rostoucí samoorganiza£ní mapy je zna£n¥ sloºit¥j²í neº u£ení základní samoorganiza£ní mapy. Krom¥ rozmis´ování výstupních neuron· je t°eba také vhodn¥ navy²ovat jejich po£et. Proto je v kaºdé iteraci krom¥ uº známé adaptace také po£ítána kumulovaná
2 P°i
u£ení bez u£itele je z principu obtíºné chybu v·bec n¥jak de novat, natoº m¥°it její velikost. 44
chybovost vít¥zného neuronu. Vysoký sou£et odchylek zna£í, ºe neuron reprezentuje p°íli² rozsáhlý shluk, a je tedy pot°eba n¥jaký neuron p°idat. Neurony jsou p°idávány na okrajích m°íºky, takºe je p°irozen¥ zachována její topologie. Velmi p°ibliºn¥ jsme popsali u£ení rostoucí samoorganiza£ní mapy (algoritmus 4.2), aby bylo patrné, kam mí°íme. Nyní postup popí²eme podrobn¥. V rámci inicializace jsou vytvo°eny první £ty°i výstupní neurony v prvním £tverci m°íºky. Kaºdý z nich je na okraji m°íºky a nabízí volný prostor k p°idávání dal²ích. Váhové vektory prvních £ty° neuron· jsou nastaveny náhodn¥. Díky normalizaci jejich sloºek se ºádný neuron ani náhodnou inicializací nedostane p°íli² daleko od vzor·.
práh r·stu P . Jeho hodnotu algoritmus spo£te na základ¥ uºivatelem zadaného faktoru rozvinutí F podle následujícího vztahu: Jak vyplyne níºe, zásadním parametrem mapy je
P = −D · ln(F ) Faktor rozvinutí je parametr z intervalu
[0, 1].
(4.6)
Popisuje, nakolik bude mapa po dokon-
£ení u£ení rozvinutá. Výhodou tohoto parametru je, ºe nijak nezávisí na dimenzi dat ani na jejich struktu°e. Proto jej lze celkem spolehliv¥ ur£it p°edem. ím blíºe je jedni£ce, tím více neuron· bude mapa obsahovat a tím bude podrobn¥j²í, p°esn¥j²í a pomalej²í. Samotné u£ení se d¥lí na dv¥ fáze. V r·stové fázi p°ibývají neurony, dokud jich není dost vzhledem k zadanému faktoru rozvinutí. Vyhlazovací fáze je klasickým u£ením nerostoucí SOM s nízkou plasticitou
αt a úzkým adaptovaným okolím σt . Zajímavá je proto p°edev²ím
r·stová fáze. Sestává op¥t z krok· pracujících na základ¥ p°edloºeného vzoru. Za£átek kroku probíhá známým zp·sobem - p°edloºení vzoru, nalezení reprezentanta a adaptace jeho a jeho okolí sm¥rem ke vzoru. Adaptací váhových neuron· ale krok nekon£í. Po ní je zvý²ena kumulovaná chyba vít¥ze:
∆Ev = δ(x, wv )
(4.7)
Pokud tato chyba p°esáhne práh r·stu, je t°eba p°idat nový neuron. Vít¥zem reprezentovaný shluk je pohledu úlohy kvantizace vektor· podvzorkován. B¥h algoritmu se d¥lí na dv¥ v¥tve. Kdyº má vít¥zný neuron v²echny £ty°i sousedy a nenachází se tedy na okraji m°íºky, není moºné k
n¥mu p°ipojit dal²í neuron. V takovém p°ípad¥ musí ke vzniku
nového neuronu vít¥z p°isp¥t alespo¬ p°enesen¥, rozd¥lením své kumulované chyby mezi sousedy. Pokud se naopak na okraji m°íºky nachází, p°ibude do mapy nový neuron. Distribuce chyby spo£ívá ve zvý²ení kumulované chyby soused· i vít¥ze v o zlomek 1 (nap°. ) jeho kumulované chyby. Zárove¬ je Ev nastavena na polovinu prahu r·stu. Takto 4 výstupní neurony uvnit° m°íºky ²í°í svou chybovost sm¥rem k okraj·m, kde p°i p°ekro£ení prahu r·stu kone£n¥ vzniknou nové neurony. M°íºka si p°itom zachová £tvercovou topologii.
∆Ei = β · Ev Ev = P/2
(4.8)
P°idání neuron· na okraji výstupní vrstvy probíhá následovn¥. Algoritmus novými neurony zaplní v²echna volná místa (tedy jedno aº t°i). Tento p°ístup je výpo£etn¥ mén¥
45
Algoritmus 4.2
U£ení GSOM
Vstup:
• Dimenze D vstupního prostoru a vzorové vektory • Posloupnost u£ícího parametru αt , funkce laterální interakce φ a posloupnost polom¥ru okolí σt
• Faktor rozvinutí F poºadované mapy a koe cient pro distribuci chyby β • Ukon£ovací podmínky pro fázi II. i III. a jejich p°ípadné parametry
Postup: I. Inicializace: 1.
Vloº první £ty°i neurony na náhodná místa v datech a propoj je vazbami do £tverce.
2.
Z faktoru rozvinutí F vypo£ti práh r·stu P podle vztahu (4.6)
II. R·stová fáze - dokud nebyly p°edloºeny v²echny vzory nebo úrove¬ r·stu není na minimu opakuj kroky 1.-11.: 1.
P°ijmi nový p°edloºený vzor x, najdi jeho reprezentanta v a adaptuj ho (v£etn¥ jeho okolí) jako v SOM (algoritmus 4.1).
2.
Zvy² hodnotu kumulované chyby vít¥ze Ev podle (4.7).
3.
Pokud Ev ≥ P :
4.
5. 6.
Pokud je vít¥z v na kraji m°íºky, p°idej neurony na jeho neobsazené sousedské pozice. Vynuluj kumulovanou chybu nových neuron· i vít¥ze. Jinak rozloº Ev mezi sousedy podle (4.8). P°epo£ítej hodnotu αt .
III. Vyhlazovací fáze 1. 2.
Nastav nízké výchozí hodnoty α0 a σ0 Dokud není spln¥na ukon£ovací podmínka pro vyhlazovací fázi, provád¥j u£ení podle algoritmu 4.1.
Výstup: GSOM nau£ená na p°edkládaná data.
46
sloºitý neº zji²´ování nejvhodn¥j²í polohy jediného neuronu. Mohou sice vzniknout i p°ebyte£né neurony, lze je ale p°ípadn¥ snadno odhalit malým po£tem vít¥zství. Odstra¬ování nepot°ebných neuron· je p°edm¥tem dal²ího výzkumu. Váhové vektory nov¥ p°idaných neuron· nejsou inicializovány náhodn¥. Mapa uº je alespo¬ £áste£n¥ uspo°ádaná a takový krok by ji zbyte£n¥ kazil. Váhové vektory jsou proto nastaveny doslova podle okolní situace. Algoritmus °e²í n¥kolik moºných kon gurací jiº existujících neuron·. Základní my²lenka je v umíst¥ní nového neuronu tak, ºe se jeho odstup od vít¥ze shoduje s odstupem vít¥ze od jiº existujícího souseda. Výjime£n¥ nastává i situace, kdy má nový neuron hned dva p°ímé sousedy naproti sob¥. V takovém p°ípad¥ je umíst¥n p°esn¥ mezi n¥. R·stová fáze u£ení je ukon£ena p°i nízké frekvenci p°idávání neuron· a po p°edloºení v²ech trénovacích vzor·. Tehdy je uº mapa dostate£n¥ nasycena. Jak uº bylo uvedeno, následuje fáze vyhlazovací. Probíhá stejn¥ jako u£ení nerostoucí samoorganiza£ní mapy. Jejím úkolem je umístit kaºdý výstupní neuron co nejblíºe t¥ºi²ti reprezentovaného shluku. P°edev²ím naposledy p°idávané neurony jsou totiº umíst¥ny jen odhadem. Vyhlazovací fáze kon£í sníºením hodnot kumulovaných chyb neuron· na velmi malou hodnotu.
4.2.2
Srovnání se SOM
Rostoucí samoorganiza£ní mapa z nerostoucí verze p°ímo vychází. Zásadní rozdíl je ale práv¥ v moºnosti r·stu mapy, tedy v p°ibývání neuron·. SOM podle dat organizuje mapu s pevn¥ danou velikostí a tvarem. Proti tomu GSOM umoº¬uje po£et neuron· i jejich rozmíst¥ní v map¥ dat·m p°izp·sobit. Díky tomu, ºe GSOM roste postupn¥ a tam kde je pot°eba, pouºije tém¥° optimální
3
po£et neuron· . Po£et neuron· SOM je naproti tomu odhadován uºivatelem, takºe jich pravd¥podobn¥ bude na stejná data pouºito více. Výsledná GSOM je tedy v tomto ohledu efektivn¥j²í. Efektivn¥j²í je i samotný proces u£ení, a to hned z n¥kolika d·vod·. P°edn¥ není t°eba hrubá uspo°ádací fáze, která rozbalí náhodn¥ inicializovanou SOM. GSOM do rozbaleného stavu rovnou roste. U²et°í se tedy kroky u£ení. Dal²í úspory zp·sobuje malá po£áte£ní mapa. I kdyº pozd¥ji naroste, první kroky probíhají mnohem rychleji, neº u SOM. Díky inkrementálnímu p°ístupu GSOM a smysluplnému umis´ování nových neuron· je moºné pracovat s výrazn¥ uº²ím okolím a s niº²ím u£ícím parametrem, coº se op¥t p°ízniv¥ projeví na efektivit¥. Na minimum je sníºeno také riziko p°ekroucení mapy. Dal²í rozdíl oproti SOM p°edstavuje faktor rozvinutí
F.
Dává uºivateli moºnost in-
tuitivn¥ kontrolovat r·st mapy, jeho zadání od uºivatele zdaleka nevyºaduje tak hluboké porozum¥ní fungování mapy jako ostatní parametry. Zajímavým vyuºitím je hierarchická analýza dat. Uºivatel si nejd°íve nechá vytvo°it hrubou mapu nap°. s nejzajímav¥j²í shluky, a jen ty si nechá rozvinout do mapy s vy²²ím
F < 0, 3. Na ní najde
F . Tento p°ístup umoº-
¬uje analyzovat mnohem rozsáhlej²í data neº SOM - jednak díky zvý²ení p°ehlednosti pro
3 B¥hem
u£ení mohou n¥kdy p°ibýt i nadbyte£né neurony nebo se naopak m·ºe stát, ºe kv·li nep°íznivému po°adí vzor· skon£í r·stová fáze p°ed£asn¥.
47
uºivatele, jednak díky rychlosti. Zpracování mapy s nízkým
F
bude samoz°ejm¥ rychlej²í,
stejn¥ jako rozvíjení men²ích shluk·. Rozdíly ve struktu°e a fungování GSOM proti SOM jsou motivovány pouºitím GSOM pro dobývání znalostí. Tam bude také GSOM jasnou volbou. Pro jiné ú£ely ale výsledek nebude tak jednozna£ný. Vylep²eními pro dobývání znalostí GSOM ztratila z univerzality SOM. P°edev²ím dvourozm¥rná £tvercová topologie výstupní vrstvy m·ºe být omezující. Dal²í nevýhodou m·ºe být rozli²ování r·stové a vyhlazovací fáze. SOM lze p°i vybavování zárove¬ dou£ovat na pr·b¥ºné zm¥ny v rozloºení dat. V GSOM lze kombinovat vybavování s vyhlazovací fází. Protoºe je ale mapa narostlá velmi p°esn¥ co do po£tu neuron· i co do jejich rozloºení v m°íºce, nebude zm¥nám p°izp·sobivá tak jako SOM. Ta má v¥t²inou univerzáln¥j²í tvar a po£etní rezervy.
4.3
Rostoucí neuronový plyn
Podobn¥ jako v rostoucí samoorganiza£ní map¥, i v rostoucím neuronovém plynu (growing neural gas, GNG) mohou p°ibývat neurony. Strukturáln¥ ov²em vychází z neuronového plynu Martinetze a Schultena [16, 17]. P°ibývat navíc nechává i hrany. GNG publikoval Bernd Fritzke v £lánku [6]. Tento pramen pouºíváme v celém zbytku oddílu. Na stavb¥ GNG jsou stále z°etelné podobnosti se SOM. Vstupní vrstva neuron· je stejná. Výstupní vrstva se li²í laterálními vazbami mezi neurony. Ty totiº v plynu nedrºí pravidelnou topologii. Navíc algoritmus u kaºdé z nich po£ítá stá°í jako GSOM pracuje s kumulovanou chybou výstupních neuron·
E.
s.
GNG podobn¥
Zásadní rozdíl oproti
SOM i GSOM spo£ívá v parametrech procesu u£ení, z·stávají totiº konstantní. Vybavování funguje stejn¥ jako u SOM.
4.3.1
U£ení GNG
Zásadním prvkem u£ení z·stává posouvání vít¥zného neuronu a jeho okolí k reprezentovanému vzoru. P°i u£ení se navíc uplat¬ují dal²í prvky. Mnohem více do pop°edí se dostává význam vazeb mezi neurony, jejich vznik a zánik. Práv¥ vazby totiº de nují hledanou topologii rozloºení dat. V kaºdém kroku se upravuje stá°í vazeb v okolí vít¥ze. P°íli² staré vazby se odstra¬ují, aby topologie plynu odpovídala aktuálnímu rozmíst¥ní neuron·. Dále jsou pravideln¥ p°idávány neurony na místa, kde je jich p°íli² málo, aby se sníºila jejich chybovost. Nyní algoritmus u£ení rostoucího neuronového plynu (algoritmus 4.3) popí²eme podrobn¥. V rámci inicializace algoritmus umístí do výstupní vrstvy dva nepropojené neurony s náhodnými váhovými vektory. Dále uº pokra£uje hlavní cyklus, v kaºdé iteraci je zpracováván jeden p°edloºený vzor. Algoritmus podobn¥ jako u SOM spo£te vzdálenost vzoru od v²ech neuron·. Krom¥ vít¥ze
v1
ov²em najde i druhý nejbliº²í neuron
v2 . Neuron v1
a neurony v jeho okolí posune
sm¥rem ke vzoru. GNG ov²em nepouºívá ºádnou funkci laterální interakce, okolím rozumí
48
Algoritmus 4.3
U£ení GNG
Vstup:
• Dimenze D vstupního prostoru a vzorové vektory • U£ící parametry α a α˙ • Práh r·stu P , maximální stá°í vazby smax • Konstanty pro sniºování chyby po p°idání neuronu β a v kaºdém kroku γ • Ukon£ovací podmínka
Postup: 1.
Inicializace: Vloº do výstupní vrstvy dva neurony s náhodnými váhovými vektory.
2.
Opakuj následující kroky, dokud není spln¥na ukon£ovací podmínka:
3.
4.
5.
6.
7.
8.
9.
P°ijmi nový p°edloºený vzor x, spo£ti jeho vzdálenost ke kaºdému výstupnímu neuronu i podle (4.1) a vyber vít¥zný neuron v1 podle (4.2).. Uprav váhy v1 a jeho p°ímých soused· podle (4.9). Aktualizuj £íta£e: Zvy² kumulovanou chybu vít¥ze podle 4.10 a zvy² stá°í s v²ech vazeb vycházejících z vít¥ze (∆sv1 j = 1). Najdi druhý nejbliº²í neuronv2 a vynuluj stá°í vazby mezi v1 a v2 (v p°ípad¥ pot°eby ji do plynu p°idej). Odstra¬ vazby star²í neº smax a neurony, které po odstran¥ní t¥chto vazeb z·staly od plynu odpojeny. Pokud je po£et p°edloºených vzor· celo£íselným násobkem prahu r·stu P , vloº nový neuron: Najdi neuron e1 s nejvy²²í kumulovanou chybou a jeho souseda e2 s nejvy²²í kumulovanou chybou. Vloº nový neuron i mezi e1 a e2 podle (4.11).
10.
Spoj i vazbami s e1 a e2 , odstra¬ p·vodní vazbu mezi e1 a e2 .
11.
Uprav kumulované chyby neuron· i, e1 a e2 podle (4.12).
12.
Sniº chyby v²ech neuron· násobením konstantou γ .
Výstup: GNG nau£ený na p°edkládaná data.
49
jen p°ímé sousedy, tedy takové neurony i, ºe
τ (wi , wv1 ) = 1.
Navíc si vysta£í s u£ícími pa-
rametry, které se v pr·b¥hu u£ení nem¥ní. Ur£ují pom¥r síly adaptace a velikosti odchylky od vzoru u vít¥ze (αv ) a jeho soused· (αφ ).
∆wv1 = αv · (x − wv1 ) ∆wi = αφ · (x − wi )
(4.9)
Potom algoritmus zvý²í kumulovanou chybu vít¥ze o £tverec jeho vzdálenosti od vzoru, tedy podobn¥ jako u GSOM.
∆Ev1 = δ(x, wv1 )2
(4.10)
Dal²í £innost algoritmu uº p°edchozí modely nep°ipomíná tém¥° v·bec. Nejd°íve zvý²í stá°í v²ech vazeb vycházejících z
v1 .
Neuron
v1
se totiº pohnul a je zvý²il tak pravd¥podobnost,
ºe n¥která z vazeb uº neodpovídá situaci a je nadbyte£ná. Vazba mezi
v1
a
v2
ov²em vzhle-
dem k práv¥ p°edloºenému vzoru nadbyte£ná ur£it¥ není. Pokud je p°ítomna, algoritmus vynuluje její stá°í, pokud p°ítomna není, vytvo°í ji. Dynamická práce se strukturou plynu pokra£uje dál. Algoritmus odstraní v²echny vazby star²í neº daný práh
smax .
To jsou ty, jejichº koncové neurony £asto vít¥zí, ale málokdy
zárove¬. V okolí vazby se tedy nachází málo dat, vazba neodpovídá jejich rozloºení a je v po°ádku ji odstranit. Odstran¥ním vazeb mohou být n¥které neurony izolovány (nejsou spojeny s ºádnými jinými). Ty je také pot°eba odstranit.
P
4
Neurony p°ibývají v plynu pravideln¥, vºdy po po£tu krok· daném r·stovým prahem . Algoritmus najde mezi neurony v plynu ten s nejvy²²í kumulovanou chybou
soused· op¥t ten s nejvy²²í kumulovanou chybou
e2 .
Nový neuron
i
e1
a z jeho
pak vloºí p°esn¥ mezi
n¥:
wi = (we1 + we2 )/2 Je t°eba se postarat také o vazby, proto je neuron p·vodní vazba mezi
e1
a
e2
i
(4.11) spojen vazbami s
e1
is
e2
a naopak
je zru²ena. Poslední na °ad¥ jsou kumulované chyby. U
e1
a
e2
β , která nabývá hodnot z intervalu [0, 1). Chyba neuronu i je hodnotu chyby neuronu e1 . Tím kon£í práce s p°idáváním neuronu.
jsou sníºeny pomocí konstanty nastavena na sníºenou
∆Ee1 = −β · Ee1 ∆Ee2 = −β · Ee2 Ei = Ee1
(4.12)
Na záv¥r je t°eba mírn¥ sníºit hodnotu kumulované chyby u v²ech neuron·. Jejich r·st se totiº nezastavuje na ºádném prahu tak jako u GSOM, a nepot°ebujeme, aby rostly
γ ∈ (0, 1). Algoritmus u£ení b¥ºí do spln¥ní ukon£ovací podmínky. Ta se m·ºe odvíjet nap°. od po£tu provedených iterací algoritmu, poºadované velikosti plynu (po£et neuron·) nebo n¥jaké míry kvality výkonu plynu.
zbyte£n¥ vysoko. Proto je p°enásobíme parametrem
4 R·stový
práh zde zna£í po£et, ne jako u GSOM, kde m¥l rozm¥r kumulované chyby neuronu. 50
4.3.2
Srovnání se SOM a s GSOM
Rostoucí neuronový plyn má stejné ko°eny jako dal²í samoorganiza£ní modely, najdeme mezi nimi proto mnoho podobností. GNG ale p°iná²í i nezanedbatelné odli²nosti. Souvisí p°edev²ím s volnou topologií výstupní vrstvy a s r·stem její velikosti. Volnost topologie a dimenze je d·sledkem dynamické práce s vazbami mezi výstupními neurony. P°ibývají a ubývají v závislosti na rozloºení dat, ne na p°ednastavené topologii n¥jaké m°íºky jako v p°edchozích modelech. Z toho okamºit¥ plyne velká výhoda GNG. Nejvhodn¥j²í topologii výstupní vrstvy totiº není t°eba znát p°edem, plyn ji ur£í sám. SOM tuto otázku nechává na uºivateli, GSOM pracuje v kaºdém p°ípad¥ s dvourozm¥rnou £tvercovou m°íºkou. Jinými slovy, SOM se snaºí výstupní vrstvu do dat vytvarovat, GSOM vyplnit a vytvarovat, GNG do správného tvaru vyroste p°ímo. Jedním z cíl· GNG je koneckonc· práv¥ vystiºení podstatných topologických vztah· v rozloºení dat. Topologie i dimenze se v GNG mohou na r·zných místech li²it. Vzdálené shluky dokonce nebudou laterálními vazbami v·bec propojeny. Nic z toho ºádný z p°edchozích model· neumoº¬uje. N¥které rysy r·stu plynu jsou podobné r·stu GSOM. P°edem není t°eba znát výsledný po£et neuron· ani po£et krok· algoritmu. Za£íná se malým po£tem neuron·, váhy nov¥ p°idaných neuron· jsou inicializovány velmi smyslupln¥. Neurony ov²em díky volnosti topologie plynu nemusí p°ibývat jen na okrajích plynu. Objeví se tak rovnou tam, kde jsou nejvíc pot°eba. Proti GSOM tedy odpadá nutnost distribuce chybovosti z prost°edka sít¥ na kraj a naopak posouvání neuron· od kraj·, kde jsou p°idávány, k d·leºitým míst·m v rozloºení dat. Tím mimo jiné také ²et°í u£ící kroky. Neurony jsou p°idávány na místa s nejv¥t²í chybovostí pravideln¥ po daném po£tu krok·. Chybovost v²ech neuron· je v kaºdém kroku sníºena. Velikost chyby tedy £asem stárne. Její význam v porovnání s nov¥j²ími chybami se sniºuje. To se jeví jako výhodné pro m¥nící se rozloºení dat, které je GNG schopen sledovat lépe neº GSOM. P°i srovnávání postupu r·stu GNG s GSOM je také na míst¥ poznamenat, ºe algoritmus u£ení GNG je p°es vy²²í obecnost jednodu²²í neº algoritmus u£ení GSOM. GNG ²et°í £as podobn¥ jako GSOM. Pomáhá malá mapa na za£átku, precizní p°idávání nových neuron· a pouºití úzkého okolí. Podobn¥ jako u GSOM lze p°edpokládat, ºe GNG bude pro stejn¥ p°esné pokrytí prostoru pot°ebovat mén¥ neuron· neº SOM. Jako zpomalení by se mohlo zdát také vyhledávání vazby k p°idání neuronu a vyhledávání p°estárlých vazeb k odstran¥ní. P°idávání neuronu se ale d¥je pouze jednou za práh P, takºe výslednou dobu b¥hu reáln¥ tolik neovlivní. Vyhledávání p°estárlých hran se ve skute£nosti týká jen hran vycházejících z vít¥zného neuronu, tedy zdaleka ne v²ech. Navíc je moºné je odstranit okamºit¥ p°i p°ekro£ení
smax .
Po£et soused· neuronu bude v GNG patrn¥ vy²²í neº v p°edchozích modelech. To ale £asovou náro£nost ve v¥t²in¥ p°ípad· nezvý²í, protoºe funkce laterální interakce je zde zastoupena prostým sou£inem s
αφ
a navíc se týká jen p°ímých soused· vít¥zného neuronu.
Celkov¥ bude u£ení GNG na stejných datech a se stejným výsledným po£tem neuron· rychlej²í neº GSOM (a samoz°ejm¥ i neº SOM). Je to dáno niº²ím po£tem u£ících krok·,
51
jak plyne z p°edchozího textu (p°idávání neuron· p°ímo na místo pot°eby, nikoliv na okraj sít¥). Riziko p°ekroucení výstupní vrstvy u GNG vzhledem k dynamické práci s hranami nehrozí v·bec. Kdyby k n¥mu do²lo, rychle by byly dopln¥ny nové vazby odpovídající dat·m a chybné vazby by zestárly a byly odstran¥ny. To je dáno tím, ºe parametry pro u£ení GNG se po celou dobu nem¥ní. Není proto t°eba °e²it pr·b¥h jejich klesání. Není t°eba zadávat ºádnou funkci laterální interakce, adaptace probíhá naprosto lokáln¥. Funguje to patrn¥ díky vhodné inicializaci p°idávaných neuron·. Parametr· u£ení GNG je sice víc neº parametr· SOM i GSOM, ale jejich zadání je pro uºivatele mnohem intuitivn¥j²í, protoºe se v pr·b¥hu výpo£tu nem¥ní. Ukon£ovací podmínka lze nastavit uºivatelsky velmi p°ív¥tiv¥ na poºadovaný po£et p°idaných neuron·, který by m¥l odpovídat po£tu shluk·. Snadno jej lze vypo£ítat z poºadavku na jejich velikost. Alternativn¥ lze pracovat s chybovostí neuron·. Navíc, pokud by uºivatel cht¥l dal²í neurony p°idat, m·ºe prost¥ plynule navázat na p°edchozí u£ení. Pokud by m¥la pokra£ovat adaptace bez p°idávání dal²ích neuron·, povede si GNG o n¥co lépe neº GSOM. V po£tu neuron· sice také nebudou velké rezervy, topologie plynu ale odpovídá topologii dat. Proto je pro plyn snaz²í sledovat mírné zm¥ny rozloºení dat. Navíc i se za xovaným po£tem neuron· lze dynamicky pracovat s vazbami mezi nimi a topologie m·ºe z·stat aktuální. Pokud bychom zmrazili i vazby, bude plyn dál fungovat jako SOM s velmi úzkým okolím. GNG jsou pouºitelné podobn¥ univerzáln¥ jako SOM, tedy ur£it¥ obecn¥ji neº GSOM. Její p°ednosti se ale mohou n¥kdy projevit i jako zápory. Volná topologie nap°íklad p·jde zobrazit mnohem h·° neº pravidelná m°íºka. Plyn navíc m·ºe mít pro p°ehledné zobrazení i p°íli² vysokou dimenzi. GNG je mezi uvedenými nejlep²í metodou pro hledání neznámé topologie a dimenze dat. R·stové vlastnosti jsou obecn¥ lep²í neº u GSOM, pokud není t°eba nakonec data promítnout do roviny. Pokud úloha vyºaduje pouºití pravidelné topologie, je GNG samoz°ejm¥ volbou nevhodnou.
4.4
Rozvíjející se samoorganiza£ní strom
Omezení ve form¥ p°edem dané velikosti a topologie SOM °e²í dynamicky rostoucí modely. Vysokou £asovou náro£nost práce s rozsáhlými daty °e²í hierarchické modely. Výhody obou p°ístup· se snaºí vyuºít rozvíjející se samoorganiza£ní stromy (evolving tree, ET) popsané v £lánku [20]. Tento £lánek je zdrojem následujícího popisu. Struktura ET se od SOM li²í ze zatím uvedených model· nejvíc. Jen st¥ºí jej je²t¥ lze povaºovat za neuronovou sí´. Terminologie jiº zavedené v této kapitole se p°esto budeme pro p°ehlednost drºet. Hlavní roli op¥t hrají neurony ur£ené k reprezentaci p°edloºených vzor·. Tentokrát ov²em nejsou rovnocenné, jsou uspo°ádané do stromu s daným ko°enovým neuronem. Podél této struktury pak probíhá vybavování. Neurony si tentokrát nepo£ítají svou chybovost, nýbrº po£et zásah·. V míst¥ neuronu, který reprezentoval p°íli² mnohokrát, budou p°idány neurony nové.
52
Algoritmus 4.4
Vybavování ET
Vstup:
• Nau£ený rozvíjející se samoorganiza£ní strom • Vzor x
Postup: 1.
2.
Inicializace: (a)
j←0
(b)
Jako prozatímního vít¥ze v0 nastav ko°en stromu.
Dokud vj není listem opakuj:
3.
Spo£ti vzdálenosti syn· i neuronu vj od vzoru x podle (4.1).
4.
j ←j+1
5.
vj ← vít¥zný syn, spl¬uje (4.2) ozna£en jako v .
6.
v ← vj
Výstup: Neuron v - reprezentant p°edloºeného vzoru x. ET dále pracuje s obdobou u£ícího parametru polom¥rem ²t¥pení
4.4.1
σt .
αt ,
s funkcí laterální interakce
Krom¥ nich mezi podstatné parametry pat°í r·stový práh
bmax
φ
a jejím
a parametr
u. Vybavování ET
Vybavování samoorganiza£ního stromu se od p°edchozích li²í. Motivace spo£ívá ve snaze neprohledávat v²echny neurony výstupní vrstvy. Algoritmus 4.4 proto vyuºije stromovou strukturu. Bude prohledávat od ko°ene stromu. V kaºdém kroku vybere mezi svými syny nejbliº²ího vzoru
x
a z n¥j bude pokra£ovat v dal²ím hledání, dokud bude kam. Nalezený
list je hledaným reprezentantem
v. 5
Pokud je moºné vybrat nejbliº²í list z více moºností,
vybere z nich algoritmus náhodn¥ .
4.4.2
U£ení ET
Základní princip u£ení z·stává stejný. V kaºdém kroku algoritmus najde reprezentanta p°edloºeného trénovacího vzoru, spolu s jeho okolím jej adaptuje. Princip r·stu se také
5 Jak
vyplyne z popisu u£ení ET, m·ºe se taková nejednozna£nost objevit jen u list·.
53
Obrázek 4.1: Ilustrace vybavování ET Samoorganiza£ní strom je pro p°ehlednost znázorn¥n pouze pomocí vazeb mezi neurony výstupní vrstvy. Vyhledávání reprezentanta pro vzor
x
za£íná v ko°enovém neuronu
v0 .
Z jeho potomk· je vybrán ten nejbliº²í vzoru, dokud se takto nedojde do listu. Ten je potom vít¥zem
v
a reprezentuje vzor
x.
nem¥ní, £as od £asu algoritmus p°idá neurony na pot°ebné místo. Tyto principy jsou ale v ET realizovány jinak neº v p°edchozích modelech. Adaptace se li²í p°edev²ím v pojetí okolí. Na stromu nelze bez rozmyslu pouºít topologickou vzdálenost jako na m°íºce. Auto°i proto p°edstavili metriku, která stromovou strukturu respektuje. Ve stromu existuje mezi dv¥ma uzly vºdy jen jedna cesta, nabízí se proto pouºití její délky. Uº z popisu vybavování stromu je patrné, ºe roli reprezentant· hrají listy. T¥ch se také týká adaptace, nelistové vrcholy z·stávají statické. Nejbliº²í listový soused je ale od listového neuronu vzdálen hned na dva kroky. Proto algoritmus de nuje vzdálenost
τ (l1 , l2 )
mezi listovými neurony l1 a l2 jako po£et vazeb na cest¥ mezi nimi sníºený o jednu. Dál uº adaptace list· vypadá p°esn¥ stejn¥ jako v SOM, tedy podle vztah· (4.3) a (4.4). R·st stromu neprobíhá po jednom neuronu, ale po celých sourozeneckých skupinách. V kaºdém kroku se zvý²í skóre vít¥ze
bv
o jedna. Pokud dosáhne prahu
bmax ,
je t°eba na
jeho místo p°idat neurony. Algoritmus proto p°idá nové neurony - syny vít¥ze v po£tu podle parametru
u.
Jejich polohy budou shodné s vít¥zem. Reprezentant p°í²tího vzoru
z dané oblasti bude mezi novými neurony vybrán náhodn¥. Díky tomu se neurony v oblasti postupn¥ rozmístí podle rozloºení dat.
54
Algoritmus 4.5
U£ení ET
Vstup:
• dimenze D vstupního prostoru a vzorové vektory • posloupnost u£ícího parametru αt • funkce laterální interakce φ a posloupnost polom¥ru okolí σt • parametr ²t¥pení u • r·stový práh bmax • ukon£ovací podmínka
Postup: 1.
2.
Inicializace: (a)
Umísti ko°enový neuron do t¥ºi²t¥ dat.
(b)
Roz²t¥p ko°enový neuron: p°idej do stromu na jeho pozici u syn·.
Opakuj následující kroky dokud není spln¥na ukon£ovací podmínka:
3.
P°ijmi nový p°edloºený vzor x.
4.
Najdi vít¥ze v pomocí algoritmu 4.4.
5.
Uprav váhy vít¥ze a neuron· v jeho okolí podle (4.3).
6.
Zvy² skóre vít¥ze: ∆bv = 1
7.
Pokud bv = bmax , roz²t¥p v : p°idej do stromu u syn· neuronu v na jeho pozici.
Výstup: ET nau£ený na p°edkládaná data.
55
Po vysv¥tlení adaptace a r·stu uº snadno popí²eme celý postup (algoritmus 4.5). Na za£átku algoritmus inicializuje strom p°idáním ko°enového neuronu a jeho syn·, jakoby práv¥ p°esáhl r·stový práh
bmax .
Ko°en je umíst¥n pokud moºno do t¥ºi²t¥ datového sou-
boru. Po inicializaci za£íná jiº známý u£ící cyklus. Algoritmus najde listový neuron který reprezentuje p°edloºený vzor
x,
bv
naváºe jiº popsanou r·stovou fází.
a v p°ípad¥ dosaºení prahu
bmax
v,
a provede adaptaci podle popisu vý²e. Zvý²í skóre
U£ení probíhá do spln¥ní ukon£ovací podmínky, podobn¥ jako u SOM. M·ºe jít o pevn¥ daný po£et krok·, po£et p°idávání neuron· nebo o n¥jaký zp·sob m¥°ení kvality samoorganiza£ního stromu.
4.4.3
Srovnání s p°edchozími modely
Rozvíjející se samoorganiza£ní strom vychází z Kohonenovy samoorganiza£ní mapy a obohacuje ji o moºnost rychlého vybavování a moºnost r·stu. Vyuºívá stejné základní principy jako p°edchozí metody, n¥které ale musí upravovat pro pouºití ve stromové topologii. Podívejme se nejprve na moºnosti r·stu. V ET mohou p°ibývat neurony. Hrany p°ibývají jen v rámci stromové topologie. Neurony jsou p°idávány na pozici syn· neuronu, který dosáhl prahového po£tu vít¥zství. Kritériem pro dopln¥ní neuronu tedy není prostorová rozsáhlost podvzorkovaného shluku (jako u GSOM), nýbrº jeho mohutnost. Jak neuron· p°ibývá, dosahují prahové hodnoty £ím dál pomaleji. Proto také strom £ím dál pomaleji roste. Tím se ET podobá GSOM a naopak li²í se od GNG, kde neurony p°ibývají pravideln¥. Podstatným rysem r·stu ET je fakt, ºe vnit°ní neurony stromu z·stávají xovány na míst¥, kde jim byly p°ipojeni potomci. P°idávání nových neuron· by proto m¥lo probíhat umírn¥n¥. Tím se zajistí vhodná inicializace neuron· a také p°esnost vyhledávání ve stromu. Inicializace poloh nových neuron· vypadá proti ostatním metodám primitivn¥. Na jednu stranu je rychlá, na druhou stranu vyºaduje dal²í u£ební kroky, aby si nové neurony na²ly správné místo. Na p°ibývání neuron· do ET lze nahlíºet jako na paralelu vyhlazovací fáze p°edchozích model·. ET nejprve zhruba vystihne tvar dat, aby mohl následn¥ na správných místech houstnout a zp°es¬ovat umíst¥ní nových neuron·. ET lze proto vyuºít i jako strukturu pro hierarchickou analýzu shluk·. Sta£í se ve stromu zastavit v hloubce podle toho, jaká p°esnost reprezentace je zrovna zapot°ebí. K £asové efektivit¥ je p°edev²ím t°eba uvést, ºe vybavování ET probíhá díky stromové struktu°e v £ase
O(log n).
Jsou-li r·stové a u£ební parametry nastaveny rozumn¥, bude
vzniklý strom skute£n¥ vyváºený. V²echny ostatní modely hledají vít¥ze v £ase
O(n),
ET
tedy v otázce £asové efektivity jasn¥ vít¥zí. D·sledkem rychlého vybavování ET je schopnost zpracovat rozsáhlej²í data neº ostatní metody. Neurony p°ibývají po celých skupinách, na konci u£ení jich tedy bude patrn¥ o n¥co víc, neº bude t°eba. Navíc ET obsahuje celý vnit°ek stromu, který slouºí jen k vyhledávání reprezentanta. Naopak prosp¥²ná je malá velikost stromu na za£átku u£ení a inicializace nových neuron· na vhodná místa (v porovnání s náhodným umíst¥ním.
56
Topologie ET je z uvedených metod nejspeci £t¥j²í. Je vyºadována rychlostí vybavování. P°itom ale není nijak výrazn¥ omezující. Prostorová korelace je zachována prost°ednictvím stromového pojetí topologické vzdálenosti. Strom je acyklický, takºe bez problém· vyplní jakýkoliv prostor - rozhodn¥ snáz neº nap°. GSOM, nemusí se totiº nijak kroutit. Proto bude data také efektivn¥ji reprodukovat. Oproti GNG schází v ET dynamická práce s vazbami. Neznamená to ov²em, ºe bychom ztratili prostorovou korelaci. R·zné v¥tve se specializují na r·zná data. Na podobné vzory tak reagují podobné neurony - jejich
τ
je malá.
Dal²í výhodou volné topologie stromu je skute£nost, ºe podobn¥ jako GNG nenechává ºádné neurony mimo reprezentovaná data. Toto SOM ani GSOM nedovedou. Listy stromu spolu nejsou provázány p°ímo, takºe z tvaru stromu uºivatel o datech nevytu²í tolik co z tvaru GNG, který se na hledání topologie a dimenze zam¥°uje. Na druhou stranu není problém nau£it strom co je t°eba, za xovat neurony a doplnit laterální vazby podobn¥ jako v GNG. Jen je t°eba si uv¥domit, ºe hledání druhého nejbliº²ího neuronu nebude moci spolehliv¥ vyuºít stromovou strukturu a její efektivitu. Zaru£eno není dokonce ani nalezení prvního nejbliº²ího neuronu. Ve svých experimentech auto°i metody zjistili, ºe tém¥°
30%
vzor· m·ºe dostat nesprávného reprezentanta.
Je to tím, se b¥hem u£ení a rozvíjení stromu mohou jeho v¥tve mírn¥ p°ekrývat. Zajímavé je zji²t¥ní autor·, ºe kdyº hledají vít¥ze klasicky, nijak výrazn¥ tím kvalitu odezvy sít¥ nezvý²í. S intuitivností vstupních parametr· na tom ET není nijak valn¥. Pouºívá posloupnosti
αt a σt . Dal²í parametry (parametr ²t¥pení u, r·stový práh bmax ) uº jsou konstantní. Nejsou sice nezávislé na datech, jako nap°. faktor rozvinutí u GSOM, ale aspo¬ jsou to celá £ísla a mají na chování algoritmu jasný vliv. Ukon£ování u£ení je ur£eno podobn¥ jako u GNG. Pr·b¥ºné adaptaci stromu s pevnou velikostí na první pohled nic nebrání. Podobn¥ jako u SOM je t°eba vy°e²it vhodnou inicializaci a chování parametr·, které by jinak klesaly k nule. Ve stromu bývá men²í po£et neuron· navíc, lze tedy po£ítat vyuºitím této rezervy. Její výhodou je, ºe díky stromové struktu°e nezat¥ºuje p°i vybavování. Závaºným problémem p°i pr·b¥ºné adaptaci ale mohou být xované vnit°ní neurony stromu. Jejich úkolem je ukazovat cestu ke správnému reprezentantovi. Postupem £asu se ale poloha dat m·ºe zna£n¥ zm¥nit, aniº vnit°ní neurony m¥ly ²anci na to reagovat. V¥t²ina z nich se tak stane nepot°ebná a s daty bude pracovat jen men²í £ást, totiº ta, která k nim má nejblíº. V této situaci je stromová struktura naopak ²kodlivá. Pokud se n¥který vysoce postavený vnit°ní neuron dostane mimo data, nebude nikdy vyuºit ani ºádný ze zna£ného mnoºství jeho potomk·. I p°i velké velikosti stromu tak budou £asem upravená data reprezentována minimálním mnoºstvím list·, tedy velmi nep°esn¥. Mohli bychom chtít tuto situaci vy°e²it standardními prost°edky stromu a dovolili bychom mu op¥t r·st. Mrtvé neurony by nám ale z·staly, a navíc by bylo t°eba s kaºdým vzorem absolvovat zbyte£n¥ dlouhou cestu k reprezentantovi. Jako lep²í volba se jeví starý strom prost¥ zahodit a za£ít znovu s pomocí informací, které nabízí poloha posledních aktivních list·. Je jich patrn¥ pouze n¥kolik, takºe novým zapo£etím u£ení o mnoho nep°ijdeme.
57
P°estoºe má ET sloºit¥j²í strukturu neº p°edchozí metody, pracuje elegantn¥ji a jednodu²eji neº nap°. GSOM. Uplatní se podobn¥ jako GNG - v²ude tam, kde je poºadavek na kvalitní kvantizaci nebo klasi kaci a ne na vizualizaci. Navíc ET oproti GNG m·ºe pracovat s mnohem rozsáhlej²ími daty.
4.5
Záv¥re£né poznámky
D·leºitým sm¥rem rozvoje samoorganiza£ních metod je u£ení s u£itelem. Ke kaºdému vzoru je k dispozici informace o tom, do které pat°í t°ídy. Je tedy moºné jako výstup dávat rovnou ozna£ení t°ídy. Hlavní p°ínos je ale v tom, ºe u£ená struktura má moºnost vyjas¬ovat hranice mezi shluky. Tam totiº jindy informace o tom, kam vlastn¥ vzor pat°í, chybí nejvíc a je nejpodstatn¥j²í pro p°esnost klasi kace. Pro ú£ely morphingu se ale metody u£ení s u£itelem p°inejmen²ím v této fázi nejeví jako vyuºitelné, proto jsme je zde podrobn¥ji nezmi¬ovali. Ve skute£nosti ve zbytku práce p°ímo nevyuºijeme ani pokro£ilé varianty SOM. Základní verze nám bohat¥ vysta£í a moºnosti vylep²ení budeme mít na pam¥ti jako potenciální vylep²ení do budoucna.
58
Kapitola 5 Moºnosti aplikace samoorganiza£ních technik na morphing V této kapitole diskutujeme moºnosti aplikace samoorganiza£ních technik na morphing obrázk·. Nejd°íve krátce popí²eme n¥které existující p°ístupy. Potom zformulujeme meze, které ná² p°ístup nebude p°ekonávat, a napak o£ekávání, která by m¥l naplnit. Potom uº se podíváme po nad¥jných souvislostech a postupn¥ je rozvineme do n¥kolika nám¥t·, jak by bylo moºné postupovat. Jeden z nich potom podrobn¥ probíráme v následující kapitole.
5.1 5.1.1
Související výsledky Morphing obli£ej·
P°edpokládejme, ºe obsahem vstupních obrázk· morphingu budou lidské obli£eje zep°edu. Takový p°edpoklad m·ºe výrazn¥ napomoci ur£ení tvaru a umíst¥ní korespondencí mezi obrázky. Na jeho základ¥ lze vyvinout metody, které fungují i bez zásahu uºivatele. Nap°íklad algoritmus popsaný v s[9] pracuje zcela automaticky. Díky skute£nosti, ºe je na obou vstupních obrázcích o£ekáván práv¥ (více £i mén¥) £elní pohled na obli£ej, lze p°edem volit po£et °ídicích bod· a jejich p°ibliºnou polohu (o£i, ²pi£ka nosu a koutky úst). S touto p°ibliºností se algoritmus vyrovnává pomocí genetického algoritmu. Nejd°ív je na vstupní obrázky aplikována um¥lá neuronová sí´ detekující obli£eje, vyhledáva£ hran a dal²í ltry. Takto p°edp°ipravená data jsou poté p°edloºena genetickému algoritmu, který hledá p°esné umíst¥ní pro °ídicí body. Na základ¥ polohy °ídicích bod· jsou obrázky rozd¥leny na odpovídající trojúhelníky. Trojúhelníky jsou ur£eny vºdy stejnou trojicí bod·, nap°. ²pi£kou nosu a koutky úst. Tento p°ístup funguje (nevznikne nap°. p°ekroucená sí´) práv¥ díky tomu, ºe na obrázcích jsou obli£eje. Trojúhelníky jsou pouºity pro výpo£et warpingu (pouºije se obdoba sí´ového warpingu). Celý morphing tedy m·ºe vzniknout samo£inn¥. Jiný p°íklad algoritmu specializovaného na práci s obli£eji uvádí £lánek [29]. Jeho výstupem není sekvence zm¥ny jednoho obli£eje na jiný, nýbrº zm¥na výrazu tvá°e téhoº
59
obli£eje. Vyuºití lze nalézt v oblasti komprese dat pro videokonference nebo pro um¥lé pr·vodce a hlasatele. Algoritmus pracuje se zjednodu²eným modelem sval· a pruºných tkání na obli£eji. Poloha kaºdého bodu na obli£eji je ovlivn¥na kombinací stav· obli£ejových sval·. Záleºí p°i tom jak na umíst¥ní bodu vzhledem k jednotlivým sval·m, tak na jejich typu (cirkulární nebo podélný). Na jednotlivá místa obli£eje mají r·zné svaly r·zný vliv. P°itom aº na výjimky
1
platí, ºe blízké body z·stanou blízké i po zm¥n¥ výrazu tvá°e. Tato fakta autory
dovedla k my²lence pouºít modi kaci SOM. Uºivatel ur£í polohy významných bod· p°ed a po zm¥n¥ výrazu. Neurony p°ímo odpovídají pixel·m. Trénovacími vzory jsou koncové polohy °ídicích bod·. Vít¥zní reprezentanti jsou p°edem daní. Jsou jimi po£áte£ní polohy °ídicích bod·. Algoritmus tedy p°edkládá samoorganiza£ní map¥ vzory, ta najde pat°i£né vít¥ze a spolu s jejich okolím je na vzory adaptuje. Tím dochází k p°esunu pixel· podle p°ání uºivatele. P°i tomto pouºití SOM lze dokonce p°esn¥ poznat, kdy uº je u£ení hotové - jakmile jsou °ídicí body na svých místech. Obrazové body (neurony) se b¥hem u£ení velmi pravd¥podobn¥ posunuly z celo£íselných sou°adnic. Zbývá uº tedy jen vyhladit obrázek n¥kterou z technik vzorkování. Jedine£nost algoritmu je v p°ístupu k funkci laterální interakce
φ. Práv¥ v ní je totiº za-
pracovaný zjednodu²ený model obli£ejových sval·. Díky tomu jsou správn¥ ur£eny velikost a tvar okolí °ídicího bodu, které je t°eba adaptovat s ním.
5.1.2
Morphing t¥les
Zobecn¥ním morphingu obrázk· je morphing trojrozm¥rných t¥les (viz oddíl 2.4.3). Úsp¥²ný zp·sob aplikace samoorganiza£ních map na tuto úlohu uvádí £lánek [25]. Vstupem jsou dv¥ t¥lesa (po£áte£ní a koncové), reprezentovaná sou°adnicemi °ádov¥ tisíc· bod· na jejich povrchu. Algoritmus po£ítá s kulovou topologií t¥les. Výstupem je posloupnost t¥les, která p°edstavují postupnou zm¥nu po£áte£ního t¥lesa na koncové. Zm¥na má být plynulá a p°irozená. T¥lesa výsledné posloupnosti by tedy m¥la být podobná dv¥ma vstupním a nem¥ly by se na nich objevit ºádné jiné výrazné rysy. Algoritmus je zaloºen na pouºití varianty samoorganiza£ní mapy. Spojení neuron· má trojúhelníkovou topologii, jejich sí´ jako celek má topologii kulovou. Po£et neuron· je daný p°edem a pevný. P°edstavují body v sou°adnicovém prostoru. Algoritmus inicializuje mapu na tvar koule kolem po£áte£ního t¥lesa. P°edkládáním bod· po£áte£ního t¥lesa mapa postupn¥ zaujme v prostoru jeho tvar. Tím je algoritmus p°ipraven na hlavní fázi své práce. V této aplikaci samoorganiza£ních map není aº tak podstatné výsledné nau£ení mapy, jako spí² samotný proces jejího u£ení. Algoritmus za£ne map¥ inicializované na tvar po£áte£ního t¥lesa p°edkládat body koncového t¥lesa. Mapa tak postupn¥ m¥ní tvar, aº zaujme tvar koncového t¥lesa. Stavy mapy v jednotlivých krocích jsou základem hledané výstupní posloupnosti t¥les.
1 Jedná
se nap°. o ústa nebo o£i. Popisovaný algoritmus si s nimi poradit umí, pokud mu uºivatel sd¥lí, kde tato místa jsou.
60
Obvykle není t°eba tak dlouhá posloupnost, aby byly uplatn¥ny v²echny kroky adaptace mapy. Proto jsou vhodn¥ vybrány jen n¥které. V souladu s obvyklým pr·b¥hem adaptace mapy probíhá zpo£átku rychlé nalezení p°ibliºného tvaru mapy a posléze pomalej²í lad¥ní detail·. Má-li tedy být výsledný morphing plynulý, jsou kroky vybírány £ast¥ji z po£áte£ní fáze adaptace. Vidíme, ºe algoritmus nevyºaduje ur£ení korespondencí, ani je sám nehledá. Od uºivatele o£ekává jen zorientování a umíst¥ní t¥les v prostoru. Jde o to, aby nap°. p°i morphingu lidských hlav z·stal koncový obli£ej na míst¥ po£áte£ního, a neobjevil se tam, kde se nacházelo temeno po£áte£ní hlavy. Zp¥tn¥ lze za korespondence prohlásit polohy neuron· na za£átku a na konci práce algoritmu. P°irozený pr·b¥h morphingu je automaticky zaji²t¥n vlastnostmi pouºité samoorganiza£ní mapy. Auto°i nechávají plasticitu sít¥ klesat od 0,2 do 0,05. Dále vypozorovali, ºe po v¥t²inu u£ení by okolí adaptovaného neuronu m¥lo zahrnovat pouze nejbliº²í sousedy, ve zbytku £asu pak uº ºádné. Tak se v pr·b¥hu morphingu nejlépe zachovají charakteristické rysy p°etvá°ených t¥les a nedojde k neºádoucímu vyhlazení jejich povrchu, jak by se to stalo p°i pouºití ²ir²ího okolí. Uvedený algoritmus elegantn¥ °e²í morphing trojrozm¥rných t¥les pomocí samoorgani-
2
zace . Nevyºaduje speci kací korespondencí t¥les a je velmi robustní. Ruku v ruce s p°ínosy pouºití samoorganiza£ní mapy jdou ov²em i nevýhody. P°edev²ím jde o nutnost zadat p°edem po£et neuron· a po£et krok· u£ení, pro uºivatele tedy pom¥rn¥ netriviální úkoly. Dále stojí za pov²imnutí, ºe výsledný morphing není symetrický, tedy ºe prohozením po£áte£ního a koncového t¥lesa obecn¥ nedostaneme posloupnost stejných t¥les v obráceném po°adí.
5.2
Co lze o£ekávat a co nikoliv
Nejv¥t²í výzvou v oblasti morphingu obrázk· je samoz°ejm¥ potla£ení nutnosti zásah· uºivatele [14]. Strojov¥ vytvá°ený morphing je hezká p°edstava sama o sob¥, navíc je tu i nan£ní motivace. Práce animátora je drahá, proto je t°eba mu ji co nejvíc uleh£it. Uº v úvodní kapitole jsme v²ak uvedli, ºe vzhledem k nejednozna£nostem, plynoucím p°ímo ze zadání, je vyty£ený cíl v plném rozsahu nesplnitelný. Lze ale poºadovat, aby algoritmus vrátil alespo¬ jeden z moºných a £lov¥kem p°ijatelných výsledk·. Podíváme-li se, jak pracuje p°i vytvá°ení morphingu animátor, najdeme nezávisle na zvolené metod¥ n¥kolik obecných skute£ností. Tv·rce si p°edev²ím ujasní cíl, kterého chce svou prací dosáhnout. Podle n¥j zvolí vhodné obrázky a softwarové nástroje. Na základ¥ své p°edstavy o výsledku vyzna£í v obrázcích korespondence. Pak uº zpravidla nechá spo£ítat výsledek. Opakováním úprav umíst¥ní korespondencí a p°epo£ítáváním výsledku uºivatel postupn¥ dosahuje své p·vodní p°edstavy. Samo£inný algoritmus na vstupu nedostane ideu uºivatele, nýbrº pouhé dva obrázky, bez jakékoliv dal²í informace. Bude tedy p°edpokládat, ºe cílem je vytvo°it co moºná
2 lánek
[25] stál u zrodu tématu této diplomové práce.
61
nejp°irozen¥j²í animaci zm¥ny. Pro tento ú£el by bylo ideální, kdyby algoritmus porozum¥l obsahu vstupních obrázk·, podle toho domyslel korespondence a umístil je tedy podobn¥ jako animátor - s ohledem na význam animace. Takový p°ístup je ale daleko za dne²ními moºnostmi automatického rozpoznávání obrazu. V²imn¥me si, ºe dosud jediná publikovaná obecná metoda automatického morphingu (minimalizace práce, [7]) hledá vhodný tvar warpingu a s korespondencemi nepracuje v·-
3
bec. Principiáln¥ vhodn¥j²í by bylo, aby automatický morphing korespondence pouºíval . Pak by totiº bylo moºné jeho výsledky snáze kombinovat s ostatními (neautomatickými) metodami - a´ uº by se jednalo o drobné uºivatelské zásahy, nebo vyuºití nejnov¥j²ích metod warpingu. V této práci se proto pokusíme jít cestou ur£ování korespondencí. Vybíráme si tak tu t¥º²í £ást problému, protoºe po£ítání warpingu jako takového (p°ípadn¥ následné prolínání) je dob°e vy°e²eno. To je zárove¬ výhodou tohoto p°ístupu. P°ípadné výsledky bude moºné snadno zkombinovat s jiº existujícími algoritmy warpingu. Nebude proto t°eba vymý²let n¥jaký dal²í, pro oblast um¥lé inteligence pravd¥podobn¥ nijak zajímavý algoritmus. Pokud navíc zvolíme vhodného zástupce, nijak výrazn¥ se nezvý²í doba výpo£tu tím, ºe ná² algoritmus nap°. umístí korespondencí víc neº uºivatel. Pochopiteln¥ se chystáme korespondence hledat na základ¥ obrazových charakteristik ne na základ¥ porozum¥ní obsahu obrazu. A priori tedy budeme na vstupu o£ekávat podobné obrázky.
5.3
N¥které nad¥jné souvislosti samoorganizace a morphingu
V²imn¥me si, ºe uvedené samoorganiza£ní metody morphingu obvykle nesledují p·vodní neuronový princip SOM. Vyuºívají spí² n¥které p°íjemné vlastnosti, jako jsou schopnost reprezentovat rozloºení dat a prostorová korelace této reprezentace. My budeme postupovat podobn¥. Budeme se snaºit vyuºít samoorganiza£ní metody jako takové. Nijak neupot°ebíme, ºe vycházejí z neuronových sítí. Nijak se nebudeme snaºit simulovat, jakým zp·sobem p°i vytvá°ení morphingu, tedy p°edev²ím p°i ur£ování korespondencí, pracuje £lov¥k. Situace by ²la stru£n¥ vystihnout následovn¥: Chceme hledat korespondence mezi obrazy, a chceme k tomu vyuºít samoorganizaci. To se samo o sob¥ nezdá jako zcela zcestné. Rádi bychom totiº, aby byly korespondence nalezeny za co nejmen²í asistence £lov¥ka. Základní metodou morphingu je sí´ový morphing. Pro výpo£et pot°ebuje na vstupu zadané korespondence ve form¥ uzl· dvou sítí umíst¥ných na n¥jak významné body vstupních obrázk·. Základní metodou vyuºití samoorganizace v um¥lé inteligenci je Kohonenova samoorganiza£ní mapa. Neurony uspo°ádané do m°íºky v ní zaujímají n¥jak významná místa ve
3 Pro
úplnost je t°eba p°ipomenout, ºe metoda minimáln¥ pracného morphingu umoº¬uje korespondence zadat pomocí °ídicích bod· nebo p°ibliºn¥ nazna£it pomocí °ídicí sít¥. 62
vstupním prostoru. Základní metody nám tedy nabízejí souvislosti. Snad by bylo moºné výstupní neurony ztotoºnit s významnými body v obrazu. Snad by bylo moºné m°íºku samoorganiza£ní mapy vyuºít jako °ídicí sí´ pro sí´ový morphing. Uvedené nám¥ty se pokusíme promyslet a zrealizovat. Bylo by samoz°ejm¥ moºné se op°ít o pokro£ilej²í metody. Ty základní jsou ov²em dob°e známé a ov¥°ené, neskrývají ºádné záludnosti. Zajímá nás moºnost pouºití samoorganizace na morphing jako princip, je p°ed£asné hledat optimální p°ístupy. Jednoduché metody nám umoºní soust°edit se na to d·leºité. Jelikoº pokro£ilé metody ze základních vycházejí, nem¥lo by být t¥ºké na²e výsledky následn¥ vylep²it co do kvality, výkonu nebo nap°. moºnosti vyuºít u£ení s u£itelem.
5.4
SOM a hledání významných bod· obrazu
V tomto oddílu diskutujeme moºnosti samoorganizovaného hledání významných bod· v obrazu. Za£n¥me s p°ímo£arým postupem. Obrázek bude zdrojem vstupních dat pro samoorganiza£ní mapu. P°edkládaným vektor·m budou odpovídat obrazové body. Mezi sloºky vektoru bu mohly pat°it následující charakteristiky:
•
sou°adnice obrazového bodu
•
barevné intenzity obrazového bodu
•
lokální charakteristiky, jako nap°. pr·m¥rná hodnota jas· na n¥jakém okolí obrazového bodu
•
rozmanitost obrázku v okolí obrazového bodu, nap°. rozptyl jas· nebo entropie
Váhové vektory neuron· tedy budou mít pom¥rn¥ mnoho sloºek. Pro ú£ely zobrazování a morphingu ov²em budeme uvaºovat p°edev²ím první dv¥, totiº obrazové sou°adnice. Protoºe víme, ºe nejd·leºit¥j²ím rozm¥rem p°edkládaných vzor· budou obrazové sou°adnice, m·ºeme si dovolit polohy neuron· inicializovat chyt°e. M·ºeme vyjít z pravidelného uspo°ádání v obrazových sou°adnicích a u²et°it si tak uspo°ádávací fázi u£ení SOM. Vzdálenost mezi neuronem a vzorem by mohla být op¥t Euklidovská, funkci laterální inhibice a dal²í parametry bychom navolili standardním zp·sobem. Aby mohla výsledná mapa dob°e poslouºit jako °ídicí sí´ pro sí´ový morphing, pouºijeme £tvercovou topologii. Krom¥ toho je t°eba za xovat krajní neurony k okraj·m obrázku. Jejich adaptace tedy bude probíhat nanejvý² v jedné ose. Tento p°ímo£arý zp·sob na²im ú£el·m vyhovovat nebude. Poslouºí nám ale jako dobré východisko pro dal²í postup. Hlavní problém spo£ívá v tom, ºe SOM p°irozen¥ hledá shluky podobných obrazových bod·. Jejich st°edy jsou nepochybn¥ významné, nicmén¥ pro ú£ely hledání korespondencí nejsou p°íli² perspektivní. Jak jsme zmínili uº v popisu úse£kového morphingu (oddíl 3.2), lidské vizuální vnímání se soust°edí p°edev²ím na hrany. Spárování st°ed· jednolitých ploch sice spl¬uje de nici
63
Obrázek 5.1: Ukázka rozloºení vzor·
Vlevo vidíme p·vodní obrázek. Dal²í dva ilustrují £etnost p°edkládání jednotlivých vzor· (obrazových bod·). ím tmav²í bod, tím £ast¥ji je p°edkládán. Na prost°edním obrázku je pravd¥pocobnost výb¥ru úm¥rná p°ímo zajímavosti bodu, na obrázku vpravo kvantilu zajímavosti. Vidíme, ºe rozloºení vpravo je jemn¥j²í.
korespondencí, nepovede ale k divácky úsp¥²nému morphingu. Zpracování okraj· objekt· na obrázcích bude odbyté. Hranových obrazových bod· je málo a nedrºí se ve shlucích, takºe pro samoorganiza£ní p°ístupy nejsou p°íli² zajímavé. My bychom ov²em pot°ebovali, aby práv¥ na hranách skon£ilo neuron· nejvíc a práce tam probíhala nejprecizn¥ji. Zajímají nás oblasti s vysokým rozptylem jas·, kontrastem barev, s vysokými hodnotami gradientu a podobn¥. Prvním krokem ke zlep²ení výsledk· by mohla být zm¥na v po£ítání vzdálenosti mezi neurony a vzory. Chceme posílit vliv sloºek charakterizujících r·znorodost okolí obrazového bodu. Po£ítání vzdálenosti proto obohatíme váhovým vektorem
ω = (ω1 , ω2 , . . . , ωD ).
Tím ovlivníme, jak siln¥ bude která sloºka vzorových vektor· p°ispívat ke vzdálenosti od neuronu:
v u D uX ωj (xj − wij ) δω (x, wi ) = t
(5.1)
j=0 Tato úprava pom·ºe, ale sama o sob¥ nesta£í. Problém je hlub²í - snaºíme se zm¥nit chování SOM proti její p°irozenosti, totiº hledání velkých stejnorodých shluk·. Dokonce i kdyº se n¥jaký neuron b¥hem u£ení p°ímo na hran¥ nachází, pravd¥podobn¥ se na ní neudrºí. I kdyº pot°ebným sloºkám dop°ejeme extrémní váhy ve vektoru
ω,
ostatní obrazové
body hrany jednodu²e p°ebijí po£etní p°evahou. Pro zvýrazn¥ní zajímavých míst pro SOM by bylo moºné up°ednostnit zajímavá místa obrázku p°epracováním samotných dat. P°ipustíme-li m¥°ení zajímavosti místa charakteristikami typu rozptylu nebo entropie, budeme mít moºnost ji jednotlivých obrazových bod· (a tím i p°edkládaných vektor·) m¥°it a porovnávat. SOM se p°izp·sobuje pravd¥podobnostnímu rozd¥lení p°edkládaných dat. Patrn¥ nejjednodu²²í a nej£ist²í zp·sob up°ednostn¥ní zajímavých dat je proto úprava tohoto rozd¥lení. Zajímavá data budeme p°edkládat £ast¥ji. Tím je pro sí´ zvýrazníme a neurony v obrazu p°irozen¥ zaujmou zajímavá místa. Otázkou z·stává, jak p°esn¥ pravd¥podobnostní rozloºení vzor· upravit. Je t°eba se vyrovnat s tím, ºe v r·zných obrázcích m·ºe být r·zné i samotné rozloºení zajímavých
64
bod· (ve smyslu jejich po£tu a zajímavosti, nikoliv umíst¥ní v obraze). Jednoduchá p°ímá úm¥ra mezi zajímavostí a pravd¥podobností p°edloºení vzoru proto nemusí být ideální. Je moºné, ºe v obrázku je skupina extrémn¥ zajímavých bod·. To ale neznamená, ºe bychom m¥li ostatní zcela ignorovat. Jemn¥j²ím p°ístupem je vyuºít moºnosti n¥jaké normalizace. Pravd¥podobnost p°edloºení by neodpovídala p°ímo spo£tené hodnot¥ zajímavosti, ale nap°íklad jejímu kvantilu mezi ostatními body obrázku. Tím se set°e význam absolutní hodnoty zajímavosti. Její výpo£et bude koneckonc· pro r·zné obrázky r·zn¥ vhodný. Naopak v¥t²í význam bude mít zajímavost bodu vzhledem k ostatním bod·m. Rozdíl t¥chto dvou p°ístup· uvádí obrázek 5.1.
5.5
Vyuºití nalezených významných bod· pro hledání korespondencí
P°edpokládejme, ºe se poda°í p°im¥t SOM, aby v daném obrázku na²la významné body z hlediska lidského vizuálního vnímání. Otázkou z·stává, jak to vyuºít pro hledání korespondencí. Jinými slovy pot°ebujeme najít související místa na dvou r·zných obrázcích. Tato souvislost m·ºe být obsahová (podobné barvy a dal²í obrazové charakteristiky) nebo prostorová (podobné umíst¥ní míst v obrázku). Nejjednodu²²í my²lenkou je vzít druhou SOM, inicializovat stejn¥ jako tu první, a nechat ji najít významné body v obrázku
Ok .
Protoºe uzly obou sítí za£ínaly u£ení na stejném
míst¥, najdou podobn¥ umíst¥né významné body. Je²t¥ lep²í bude inicializovat novou mapu pozicemi uzl· z jiº nau£ené mapy. Nalezené významné body tak k sob¥ budou je²t¥ blíº. Výstupní vrstvu p·vodní mapy bychom pouºili jako °ídicí sí´ nov¥ nau£enou pak jako koncovou sí´ zovány zajímavými body
Op
svému p·vodnímu umíst¥ní v
Sk .
chceme zajistit, aby si na²ly místa v
pro sí´ový morphing,
Ok
Ok
byly iniciali-
blízká a podobná
Op .
Tento postup nutn¥ selºe. Nalezené významné body blízko významných bod· z
Sp
Tím, ºe by uzly SOM u£ené na
Ok
sice pravd¥podobn¥ budou
Op , nic ale nezajistí, aby jim byly podobné. Neuron v koncovém
obrázku se sice bude podobat neuronu podle starého umíst¥ní, jenºe op¥t v koncovém obrázku. Vým¥nou dat mapa ztratila jakoukoliv informaci o tom, co se na kterém míst¥ obrázku
Op
nacházelo.
Tuto ztrátu informace je nutno n¥jak vy°e²it, n¥jakým zp·sobem neuron·m p°idat pam¥´. Po promy²lení n¥kolika slepých uli£ek jsme se op¥t vydali cestou úpravy po£ítání vzdálenosti
δω . Chceme, aby na její hodnotu m¥lo vliv p·vodní umíst¥ní neuronu ve starém
obrázku. Protoºe bude pot°eba pracovat i s informacemi ze starého prostoru, lze se na úpravu dívat jako na jeho roz²í°ení. Pro kaºdý p°edloºený vzor tedy budeme m¥°it dv¥ vzdálenosti. Jednu ke kaºdému neuronu aktuální SOM v aktuálních datech (Ok ), a jednu ke kaºdému neuronu v p·vodním umíst¥ní a p·vodních datech (Op ). ím mén¥ bude p·vodní neuron (v p·vodní poloze a p·vodním obrázku) podobný p°edloºenému vzoru, tím men²í musí mít ²anci vzor reprezen-
65
Obrázek 5.2: Ilustrace m¥°ení vzdálenosti s pam¥tí
Abychom situaci zp°ehlednili, uvaºujeme jednorozm¥rné obrázky. Vodorovná osa odpovídá jejich jedinému °ádku, svislá osa odpovídá intenzit¥ jasu. Ostatní charakteristiky zanedbáme. Vidíme tedy dv¥ obrazové funkce, p°íslu²ející postupn¥ po£áte£nímu obrazu
Op
a koncovému obrazu
O reprezentaci vzoru
x
Ok . sout¥ºí neurony
v
a
i.
Vidíme jejich umíst¥ní v po£áte£ním i
koncovém obrazu. V obrazových sou°adnicích je blíº neuron ip , navíc je blíº i jeho aktuální poloha
ik .
Od pohledu je ale z°ejmé, ºe p°íhodn¥j²ím reprezentantem by byl neuron
v.
obrazu reprezentoval podobnou oblast obrazu, v jaké je nyní obrazový bod oblast zárove¬ není daleko. To se naopak nedá °íci o neuronu i, který v oblast vzoru
x
Op
Ve starém
x,
a tato
reprezentoval
zcela nepodobnou.
Po se£tení vzdáleností podle (5.2) vidíme, ºe neuron skute£n¥ zvít¥zí.
66
v
v sout¥ºi o reprezentaci vzoru
x
tovat ze své nové polohy v
Ok .
Ideu p°ibliºuje jednoduché schéma na obrázku 5.2. Jednou
z moºností je vztah (5.2).
δωp ,ωk (x, i) = δωk (xOk , iOk ) + δωp (xOk , iOp )
(5.2)
Obecn¥ vzato se váhové vektory pro po£áte£ní a pro koncový obrázek mohou li²it. Dolní indexy v uvedeném vztahu proto nazna£ují, v jakém prostoru po£ítáme a s jakými váhami. Pro jistotu p°ipomínáme, ºe neuron
iOk
je na pozici jiº adaptované
neuron iOp uvaºujeme v pozici, do které zkonvergoval v obrázku
Ok ,
kdeºto
Op . Z p°íslu²ného obrázku
je samoz°ejm¥ brán i zbytek váhového vektoru. Uvedená úprava velmi dob°e respektuje na²e poºadavky. Moºnost nalezení korespondencí pomocí SOM se s její pomocí jeví jako reálná.
5.6
Dal²í varianty aplikace samoorganizace na morphing
V p°edchozím textu jsme p°edpokládali, ºe pomocí SOM vytvarujeme °ídicí sít¥ pro sí´ový morphing a samotnou tvorbu výsledné posloupnosti uº necháme na n¥m. To samoz°ejm¥ není jediná moºnost. Sí´ový morphing získává p°echodové stavy °ídicí sít¥ lineární interpolací poloh jejích uzl·. P°i pouºití SOM ov²em máme po ruce i jinou alternativu. Samotné korespondence totiº hledáme p°etvá°ením budoucí °ídicí sít¥ z tvaru
Sp do tvaru Sk . Nabízí se tedy moºnost
vybrat n¥které kroky u£ení a získané pr·b¥ºné stavy výstupní vrstvy pouºít jako jednotlivé sít¥
St .
Motivací pro tento postup není rychlost, lineární interpolace p°i morphingu zabere zanedbatelný zlomek celkového £asu. Spí² se jedná o zajímavost výsledku. Pohyb uzl· (a tím i pohyb objekt· ve výsledné posloupnosti obrázk·) není nijak pravidelný, není ani jednosm¥rný. Pro £lov¥ka je obtíºné jej p°edvídat. Pro b¥ºné pouºití se tedy tento zp·sob nehodí. Uºite£ný ale m·ºe být na nap°. poli tzv. nových médií. Dal²í moºností je vytvá°ení speciálních lmových efekt·, kde si morphovaný objekt zdánliv¥ není moc jistý, do jakého tvaru se prom¥¬uje. Metoda minimalizace práce (oddíl 3.4) m·ºe p°ijímat jako vstup p°ipravenou °ídicí sí´. Optimaliza£ní algoritmus pak p°i hledání tvaru sít¥ ur£ujícího co nejmén¥ pracný morphing vychází práv¥ z tohoto vstupu. Je to pojistka pro p°ípad, kdy ze standardního nastavení nalezne zcela nesprávný tvar morphingu. Nabízí se proto zkombinovat metodu minimalizace práce a SOM hledající významné body (kteroukoliv funk£ní variantu). Nejd°ív bychom nechali OSM adaptovat pom¥rn¥ °ídkou °ídicí sí´ na významné body v obrázku. Tuto sí´ by potom dál zpracoval algoritmus na hledání minimáln¥ pracného morphingu. Stejný zp·sob pojistky ve form¥ uºivatelské °ídicí sít¥, lze aplikovat i na na²e návrhy SOM hledajících korespondence. První fáze hledání významných bod· by neprobíhala samo£inn¥, uºivatel by je sám vybral a sí´ vhodn¥ vytvaroval. Sí´ by byla pouºita jako výchozí
67
tvar pro adaptaci na nová data (koncový obrázek
Ok ).
by mnohem lépe odpovídaly uºivatelovým p°edstavám.
68
Následn¥ nalezené korespondence
Kapitola 6 Zhodnocení implementovaných metod Postupn¥ jsme napsali, odladili, odzkou²eli a vylou£ili velké mnoºství variant pouºití samoorganizace na °e²ení morphingu. Tato kapitola popisuje ty nejúsp¥²n¥j²í výsledky, totiº metodu SOM s pam¥tí a s úpravou distribuce dat.
6.1
Poznámky k implementaci
Pro implementaci navrhovaných metod jsme pouºili skriptovací jazyk Python. Je to nezáludný jazyk vybavený mnoºstvím hotových knihoven. Umoºnil nám proto p°edev²ím rychlý vývoj a moºnost okamºitých úprav. Odvrácenou stránkou v¥ci je rychlost výsledných program·. Pro na²e zkoumání nebyla omezující, pro reálné nasazení by ov²em hotové programy pouºitelné nebyly. Pro srovnání jsme implementovali jediného zástupce klasických metod, který je schopen pracovat bez uºivatelského ur£ení korespondencí, tedy metodu minimalizace práce (oddíl 3.4). Získali jsme tak n¥kolik cenných zku²eností. A£ se to na první pohled nezdá, v p·vodním £lánku [7] n¥které d·leºité informace pro implementaci algoritmu schází. Nap°íklad se jedná o hodnoty, kterých nabývají barevné intenzity. Jejich volba se zásadn¥ projeví na pracnosti obarvování a tím i na celém výsledku. Druhý d·leºitý poznatek se týká po°adí zkou²ení dislokací. Je dobré je promíchat, jinak má algoritmus tendenci tla£it v²echny uzly sít¥ do jediného rohu obrázku. Algoritmus jsme implementovali ve zobecn¥né form¥ pro práci s obdélníkovými obrázky. Protoºe jsme ale nena²li ideální nastavení parametr· ani pro autory testované £tvercové obrázky, od morphingu obdélníkových obrázk· jsme upustili. P°i implementaci mnoºství variant a modi kací SOM jsme taktéº získali podstatný poznatek: Zdánliv¥ jednoduchý princip fungování samoorganiza£ní mapy lze p°i implementaci na mnoha místech fatáln¥ po²kodit.
69
6.1.1
Trénovací mnoºina
Trénovací vzory odpovídají obrazovým bod·m. Vektor obsahuje obrazové sou°adnice, barevné intenzity, jas, st°ední hodnotu, sm¥rodatnou odchylku a gradient jasu v okolí obrazového bodu. Jas
I
obrazového bodu po£ítáme jako váºený sou£et barevných intenzit
R, G
a
B,
jak
jej uvádí nap°. [36, str. 25]:
I = (0.299 · R + 0.587 · G + 0.114 · B) í°ka okénka pro výpo£et st°ední hodnoty a odchylky je
9
obrazových bod·. Celá plo-
cha okénka má jednotnou váhu. Okénkové charakteristiky po£ítáme hned p°i inicializaci. Hromadn¥ je lze spo£ítat rychleji a b¥hem u£ení je stejn¥ budeme pot°ebovat pro kaºdý obrazový bod. Aby kraji obrázk· nevznikaly nep°irozené artefakty, p°edpokládáme opakování posledního obrazového bodu podle pot°eby. Takové vypo°ádání s okraji dob°e odpovídá obvyklému stejnom¥rnému pozadí. Gradient je sou£tem výsledk· £tvercových gradientních operátor· kde
r
Gh a Gv
o ²í°ce
2r+1,
je celo£íselný polom¥r okénka. Tyto operátory jsou nejcitliv¥j²í na vodorovné a svislé
hrany. To sice není p°íli² univerzální, ale dob°e to odpovídá lidskému vnímání.
Gh =
−r . . . − 1 0 1 . . . r . . .
. . .
. . .
−r . . . − 1 0 1 . . . r
T , Gv = Gh
V²echny sloºky trénovacího vektoru jsou pro p°ehlednost normovány na interval
[0, 1].
K m¥°ení vzdálenosti mezi vektory pouºíváme váºenou Eukleidovskou vzdálenost (5.1). Normalizace sloºek trénovacího vektoru umoº¬uje jednotné ur£ení vah
ω.
Mezi nimi mají
nejvy²²í hodnotu váhy obrazových sou°adnic, p°ibliºn¥ p¥tinovou hodnotu mají charakteristiky zajímavosti (odchylka a gradient) a ostatní sloºky mívají váhy je²t¥ niº²í. V²echna uvedená nastavení vyplývají z mnoha systematických iterací cyklu pokus omyl. Testovali jsme mnoho so stikovan¥j²ích moºností - r·zn¥ váºená a r·zn¥ veliká okénka, entropii místo sm¥rodatné odchylky, kvalitn¥j²í gradienty atd. Obvykle se ukázalo, ºe tyto moºnosti nep°iná²ejí významná vylep²ení. P°edev²ím z d·vodu rychlosti výpo£tu a p°ehlednosti chování SOM jsme proto z·stali u jednodu²²ích variant. Obrazové body nebudeme síti p°edkládat s rovnom¥rným rozloºením. Neuron·m pom·ºeme soust°edit se na významné body tím, ºe je p°edloºíme £ast¥ji. Pravd¥podobnost p°edloºení konkrétního vzoru nastavvujeme jako úm¥rnou jeho kvantilu zajímavosti mezi ostatními. Zajímavost je dána rovným dílem odchylkou a gradientem.
6.1.2
SOM a u£ení
Topologie výstupní vrstvy neuron· je £tvercová. Jak uº jsme uvád¥li, okraje m°íºky jsou xovány k okraj·m obrázku. Funkce laterální interakce linárn¥ klesá od jedné k nule.
70
φ
na daném zuºujícím se okolí
σt
Lineárn¥ k nule postupn¥ klesá i u£ící parametr αt . Jeho po£áte£ní hodnota je nízká, 1 . Je to dáno p°edev²ím inicializací mapy. Nejlépe se osv¥d£ilo neurony 20 ze za£átku pravideln¥ rozmístit na celou plochu obrázku v souladu s topologií vazeb mezi mnohdy sta£í i pod
nimi. Patrn¥ by bylo moºné najít v obrázku hrany a mapu inicializovat p°ímo na n¥. Ukazuje se to ale spí²e jako nadbyte£né, mapa si je stejn¥ dob°e najde i sama. Druhým d·vodem, díky kterému lze pracovat s tak nízkou hodnotou u£ícího parametru, je dávkový p°ístup. Máme zájem na tom, aby se neurony adaptovaly velmi p°esn¥ a nenechaly se zmást náhodnými vlivy. Proto nebudeme adaptovat neurony po kaºdém p°edloºeném vzoru. V kaºdé dávce bude p°edloºeno n¥kolik desítek vzor·. Posun kaºdého neuronu po skon£ení dávky bude sou£tem v²ech posun·, které by neuron absolvoval po jednom. Protoºe v dávce byly pravd¥podobn¥ neurony z více míst shluku reprezentovaného jedním neuronem, bude se tento drºet blíºe st°edu shluku. Krom¥ uvedeného SOM roz²í°íme jiº nazna£eným zp·sobem o pam¥´. Po nalezení významných bod· obrázku
Op
sí´ p°enastavíme tak, aby vzdálenost po£ítala podle (5.2).
Navíc upravíme váhový vektor ve prosp¥ch charakteristik zajímavosti. P°i hledání korespondencí totiº uº nejde tolik o nalezení nejvýznamn¥j²ích míst nalezení významných míst podobných t¥m, které nalezla v
Ok .
Snahou SOM je spí²
Op .
Délka u£ení bývá zpravidla stejná jako v úvodní fázi, u£ící parametr sta£í je²t¥ niº²í.
6.2
Testování
B¥hem zpracovávání zadaného diplomového úkolu jsme uskute£nili °adu prov¥°ovacích test·. P°edev²ím jsme ov¥°ovali r·zné moºnosti aplikace SOM na morphing. Teprve s metodou upravující pravd¥podobnostní rozd¥lení vstupních vzor· jsme za£ali získávat uspokojivé výsledky. Mohli jsme tedy p°istoupit k systemati£t¥j²ímu testování, a p°edev²ím porovnání s metodou minimalizace práce. Vyuºili jsme obrázky z p·vodního £lánku [7] a obrázky z vlastních zdroj·. Testovali jsme jednak nespeci cké fotogra e, jednak lidské obli£eje a jednak obrázky geometrických objekt· s ostrými hranami. Porovnávali jsme r·zná nastavení obou metod. U minimalizace práce ²lo p°edev²ím o lad¥ní jednotlivých vah a odhadování optimálního stupn¥ sít¥. U SOM s upravenou distribucí dat jsme upravovali p°edev²ím práv¥ tvar distribuce dat, váhový vektor
ω
jednotlivých slo-
ºek datových vektor·, po£ty a velikosti u£ebních dávek, polom¥r adaptovaného okolí a samoz°ejm¥ velikost a topologii sít¥. Vybrali jsme 6 pár· testovacích obrázk·. Nalezli jsmeco moºná nejlep²í nastavení parametr· a testovali výkony obou metod. Nejlep²ím nastavením se zde rozumí takové, které vede k nejkvalitn¥j²ím výsledk·m. Zárove¬ jsme ale nastavení hledali tak, aby nalezené sekvence byly kvalitativn¥ srovnatelné. Jako m¥°ítko kvality poslouºil ná² subjektivní názor, op°ený o objektivní kritéria kvalitního morphingu zmén¥ná v oddílu 2.3. Na²i metodu jsme testovali ve dvou odd¥lených fázích: hledání významných bod· a ur£ování korespondencí. Hledání významných bod· jsme hodnotili na subjektivní ²kále
71
Obrázek 6.1: Ukázka zm¥ny £tverce na kruh metodou minimalizace práce 9x9
Pr·m¥rný £as z 9 pokus· je
175, 1s,
sm. odch.
2, 9s.
Obrázek 6.2: Ukázka zm¥ny £tverce na kruh pomocí SOM 9x9
Pr·m¥rný £as z 13 pokus· je
89, 0s,
sm. odch.
1, 8s.
bez p°ipomínek aº nep°ijatelné podle toho, nakolik jsme usoudili, ºe je dané rozmíst¥ní bod· pouºitelné pro ur£ení korespondencí a morphing. Kvalitu ur£ení korespondencí jsme hodnotili podle výsledného morphingu. S nalezeným kvalitním nastavením jsme provedli n¥kolik spu²t¥ní. Sledovali jsme spot°ebovaný £as jednotlivých fází výpo£tu a kolísání kvality výsledk·. Ukázalo se, ºe to nebude nijak zvlá²´ zajímavé, nebo´ £asové i kvalitativní výkony se drºely na velmi stabilních úrovních. Proto jsme p°ipravenou stupnici hodnocení kvalityu nevyuºili a spokojili se s 12-15 m¥°eními na jednom obrázku. Krom¥ nejlep²í kon gurace jsme testovali také univerzální kon guraci se sítí neuron· a
10000
9×9
u£ebními kroky. P°i hledání vhodných hodnot parametr· jsme zárove¬
sledovali robustnost metod, tedy jak snadno se parametry hledají a nakolik výsledky znehodnotí jejich nevhodné nastavení.
6.3
Výsledky
V tomto oddílu otiskujeme výb¥r obrázk· s nejvy²²í vypovídající hodnotou. Uvádíme vºdy první, prost°ední a poslední snímek posloupnosti.
72
Obrázek 6.3: Ukázka zm¥ny £tverce na kruh pomocí SOM 5x5
SOM dosáhne obdobných výsledk· i s °id²í m°íºkou, takºe spot°ebuje mnohem mén¥ £asu. Pr·m¥rný £as ze 12 pokus· je
6, 2s,
sm. odch.
3, 1s.
Obrázek 6.4: Ukázka zm¥ny maliny na ostruºinu pomocí SOM 9x9
131, 7s, sm. odch. 2, 9s. Minimalizace pr·m¥rný £as 350, 4s s odchylkou 6, 2s.
Pr·m¥rný £as z 15 pokus· je stejných výsledk· za
práce dosahovala
Obrázek 6.5: Ukázka zm¥ny výrazu tvá°e pomocí SOM 13x11
Pr·m¥rný £as ze 14 pokus· je
252, 7s
sm. odch.
73
5, 3s.
6.4
Zhodnocení
Ze zku²eností s testováním obou metod m·ºeme vyvodit n¥kolik záv¥r·. Metoda minimalizace práce se obecn¥ ukázala jako hor²í. Tém¥° pravideln¥ vyºaduje více výpo£etního £asu, a p°itom dává o²kliv¥j²í výsledky. Na rozdíl od autor· metody se nám nepoda°ilo najít takové nastavení vah, které by dávalo alespo¬ pr·m¥rné výsledky. Maximální stupe¬ sít¥ samoz°ejm¥ razantn¥ ovliv¬uje dobu výpo£tu, jeho zvy²ování ale ne vºdy vede ke kýºeným výsledk·m. Pro n¥které obrázky je navíc obtíºné optimální stupe¬ ur£it. Zdvojnásobování je n¥kdy p°íli² velký skok a obrázek by pot°eboval sí´ st°edn¥ hrubou. Z uvedeného zdaleka nevyplývá, ºe by byl koncept minimáln¥ pracného morphingu od základu ²patný. Nejpravd¥podobn¥j²ím d·vodem zklamání je skute£nost, ºe jsme metodu v detailech implementovali jinak. Ne v²echny parametry jsme mohli nastavit stejn¥ jako auto°i. Dále je t°eba uváºit, ºe hierarchický optimaliza£ní algoritmus nachází pravd¥podobn¥ jen suboptimální °e²ení. Na vin¥ neúsp¥chu je tedy p°edev²ím na²e implementace, potom p°ípadn¥ algoritmus a aº nakonec samotný princip po£ítání pracnosti morphingu. U SOM jsme testovali funk£nost na mnoha kombinacích parametr·. Ukázalo se, vliv konkrétní distribuce dat je znatelný, ale t¥ºko p°edvídatelný. 4 Po£ty a velikosti u£ebních dávek dávaly p°i sou£inu 10 velmi spolehlivé výsledky. To je u SOM celkem obvyklý po£et p°edloºených vzor·. U n¥kterých obrázk· se da°ilo po£ty iterací stáhnout aº na n¥kolik stovek. Osv¥d£ená velikost jedné dávky vzor· je
50. Polom¥r
adaptovaného okolí výsledky kvalitativn¥ nezm¥nil, ale s jeho pomocí bylo moºné sniºovat po£et u£ebních iterací. Po£et neuron· v SOM celkem o£ekávan¥ ovliv¬uje preciznost výsledného morphingu v protikladu s rychlostí výpo£tu. Podobn¥ jako u minimalizace práce, jemn¥j²í sí´ nevede vºdy k lep²ímu výsledku. Zkou²eli jsme pracovat jak se £tvercovou, tak s ²estiúhelníkovou topologií. estiúhelníková topologie se podle o£ekávání ukázala jako stabiln¥j²í. Zvlá²´ se proto osv¥d£ila na nadpr·m¥rn¥ sloºitých obrázcích. R·zná nastavení váhového vektoru
ω
pro po£ítání vzdálenosti jsme testovali patrn¥
nejintenzivn¥ji. Pro r·zné modi kace se osv¥d£ila r·zná nastavení. Pro práv¥ hodnocenou metodu se osv¥d£ily plné váhy pro obrazové sou°adnice, mén¥ neº p¥tinové pro charakteristiky zajímavosti (odchylka a entropie) a je²t¥ men²í pro ostatní sloºky. O£ekávali jsme, ºe váhy obrazových charakteristik budou mnohem vy²²í. Pravd¥podobn¥ jsou ale pro mapu dostate£n¥ zvýrazn¥ny zm¥nou distribuce vzor·. Celkov¥ je nutno konstatovat, ºe na daných datech se námi navrºená metoda jevila jako perspektivní. Samoz°ejm¥ by bylo moºné dále up°es¬ovat parametry apod., nicmén¥ uº takto je z°ejmé, ºe je metoda pouºitelná. P°istupme nyní ke srovnání metody minimalizace práce a námi navrºené metody zaloºené na samoorganizaci. Markantní rozdíl je v nam¥°ených £asových sloºitostech obou metod. Ze vzájemného porovnání vychází na²e metoda výrazn¥ lépe. Vidíme hned n¥kolik p°í£in tohoto jevu.
74
P°edn¥ jsme metody testovali na pom¥rn¥ jednoduchých obrázcích. Na²e metoda se v nich dokázala rychle zorientovat, takºe bylo moºné u£ení zrealizovat b¥hem nap°. 6000 u£ebních krok·. Je to dáno mimo jiné tím, ºe si vysta£í s °id²í m°íºkou, jak vysv¥tlíme níºe. Souvisí to také s tím, ºe v¥t²í mnoºství nastavitelných parametr· na²í metody umoº¬uje p°esn¥j²í vylad¥ní pom¥ru doby výpo£tu a kvality výsledku. Celkov¥ vzato je ov²em vzhledem k tomu, ºe sm¥°ujeme k samo£inému morphingu, mnoºství parametr· na²í metody jednozna£nou slabinou. Dále je tu pouºitý programovací jazyk. Po£ítá pomalu, takºe kdyº metoda minimalizace práce pot°ebuje po£ítat víc, rozdíl se je²t¥ prohloubí. Dal²ím d·vodem m·ºe být samotná implementace. U obou metod by patrn¥ bylo moºné p°istoupit k n¥kterým optimalizacím, které by je²t¥ mohly výsledky zna£n¥ ovlivnit. Dal²í poznatek se týká mnoºství pot°ebných uzl· sít¥. Metoda minimalizace práce drºí po£áte£ní sí´ v nezm¥n¥ném tvaru. To sice umoº¬uje n¥které optimalizace, ale m·ºe to zna£n¥ sníºit kvalitu výsledku. Pokud se totiº °ídicí sí´ neslícuje s objekty na obrázku, bude výsledný warping vypadat nev¥rohodn¥. Je to jeden z rys· zd¥d¥ných od sí´ového morphingu. Metoda minimalizace práce má p°itom jen mizivou ²anci po£áte£ní sí´ s objekty slícoavat. Jedinou moºností je, ºe se okraje objekt· náhodn¥ ocitnou na spoji °ídicí sít¥. Naproti tomu na²e metoda si i po£áte£ní sí´ p°izp·sobí jak pot°ebuje, a jak to sí´ový morphing p°edpokládá. To je také d·vodem, pro£ si vysta£í s men²í sítí pro stejn¥ kvalitní morphing. Ob¥ma metodám hrozí p°ek°íºení spoj· v síti a znemoºn¥ní kvalitního warpingu. Je to d·sledek velmi nedbale zvolených parametr· a absencí explicitní kontroly. Ob¥ metody umoº¬ují zvolit takové váhy a parametry, ºe hledaným optimálním stavem bude n¥jak zmuchlaná sí´. Metody se navíc z d·vodu dosaºení co nejvy²²í rychlosti této moºnosti nijak nebrání. Pro praxi to ov²em neznamená velký problém, nebo´ rozumný uºivatel nemá pro£ nebezpe£né hodoty zadávat. V otázce mnoºství a intuitivnosti parametr· jasn¥ vít¥zí metoda minimalizace práce. Uºivatel pracuje se t°emi váhami, které ovliv¬ují p°ísp¥vky k celkové pracnosti morphingu, a s maximílním stupn¥m sít¥. Tyto parametry jsou jednodu²e pochopitelné. Paramtery na²í matody jsou mnohem bohat²í a také mocn¥j²í, b¥ºný uºivatel to ale ocení jen st¥ºí. Na²e metoda je ov²em v·£i svým parametr·m robustn¥j²í. Nabízí mnohem ²ir²í prostor jejich nastavení, v n¥mº dává p°ijatelné výsledky. Parametry minimalizace práce je mnohdy t°eba jemn¥ ladit, naopak parametry pro na²i metodu lze celkem dob°e odhadovat. Z pozorování výkon· na jednotlivých obrázcích lze objevit n¥kolik poznatk·. P°edn¥, ani jedna metoda není vhodná pro morphing obrázk· s ostrými hranami, jakými jsou kresby nebo schémata. Metodám se nepoda°í vystihnout pot°ebné skute£nosti pomocí °ídicí sít¥ a proto není ²ance na kvalitní výsledek. Ostré hrany se b¥hem morphingu rozpadnou a lidský divák se od té chvíle vlastn¥ nemá na co dívat. O n¥co lépe zde funguje na²e metoda, protoºe je schopna hrany alespo¬ £áste£n¥ (v rámci omezení vlastní topologií) zachytit. Mnohem úsp¥²n¥j²í jsou ob¥ metody na fotogra ích. Stru£n¥ °e£eno proto, ºe se na nich snáze schovají nep°esnosti. Pro na²i metodu jsou v·bec nejlep²í fotogra e jednoduchých objekt· na kontrastním pozadí. Lidská hlava mívá výrazný obrys, s nímº metody nemají
75
problém. Vy²²í kvalitu je ov²em t°eba nastavit pro správný morphing samotného obli£eje, jeho rysy uº totiº tak výrazné nebývají. Oba porovnávané postupy pouºívají pro výpo£et warpingu sí´ový warping. Tím pádem si s sebou nesou i jeho výhody a nevýhody. Na n¥kterých sloºit¥j²ích obrázcích bylo patrné, ºe £tvercová topologie m·ºe být omezující dokonce i pro samoorganiza£ní metodu. Zde se proto otevírá moºnost pro pouºití vysp¥lej²ích variant jak morphingu, tak samoorganizace. Jako p°ínosy by bylo moºné o£ekávat p°edev²ím uvoln¥ní topologie, moºnost jejího dynamického p°izp·sobení a zvý²ení celkové rychlosti výpo£tu. Na záv¥r shrneme na²e pozorování do následujícího doporu£ení. Pokud se chystáme morphovat velmi podobné obrázky a máme zku²enosti s metodou minimalizace práce, je na míst¥ ji vyuºít. Pokud se obrázky li²í víc a nechceme trávit £as lad¥ním parametr·, máme pravd¥podobn¥ v¥t²í ²anci na úsp¥ch s na²í metodou. S ní p°ípadn¥ také snáze naváºeme n¥kterou ru£ní metodou, nap°. sí´ovým morphingem. Pokud si obrázky podobné nejsou, pokud obsahují ostré hrany nebo pokud máme velmi jasnou p°edstavu o poºadovaném výsledku, rozhodneme se pro vhodnou metodu ze druhé kapitoly této práce. Stru£né porovnání metod je na jejím konci.
76
Kapitola 7 Záv¥r Cílem této práce bylo prozkoumat moºnosti nasazení samoorganiza£ních metod pro °e²ení morphingu s cílem omezit nutnost lidské asistence. Ze za£átku práce jsme £tená°e seznámili s ²irokou problematikou morphingu obrázk· a s nejzákladn¥j²ími souvislostmi. Vstupem problému jsou dva obrázky, výstupem sekvence snímk· znázor¬ující p°irozenou zm¥nu jednoho obrázku na druhý. V tomto popisu se skrývá zna£né úskalí. Poºadavek p°irozenosti do úlohy vná²í prvek subjektivity. Kv·li tomu je zna£n¥ obtíºné, ne-li nemoºné, úlohu splnit ke v²eobecné spokojenosti. Dále jsme uvedli p°ehled klasických metod °e²ení morphingu. Pro ú£ely práce mají nejzásadn¥j²í význam sí´ový morphing a minimáln¥ pracný morphing. Sí´ový morphing je odrazovým m·stkem pro v¥t²inu ostatních algoritm·. Minimáln¥ pracný morphing je jediná univerzální metoda morphingu, která nevyºaduje zadání korespondencí od uºivatele. Pro podobné obrázky skute£n¥ dovede najít pouºitelnou sekvenci. Sí´ový morphing jsme implementovali jako spole£ný základ dal²ích metod. Minimáln¥ pracný morphing jsme implementovali, abychom jej vyuºili ke srovnání s vlastními výsledky. Pro úplnost a dokreslení situace v oblasti morphingu jsme také uvedli úse£kový morphing, metodu interpolace korespondencí, minimalizaci energie a víceúrov¬ovou volnou deformaci. Úsp¥ch v²ech t¥chto metod p°ímo závisí na zru£nosti uºivatele, proto mají v této práci pouze informativní význam. Po seznámení s morphingem a s metodami jeho °e²ení jsme popsali také jev samoorganizace a jeho vyuºití v um¥lé inteligenci. To spo£ívá nej£ast¥ji v technikách u£ení bez u£itele. D·kladn¥ jsme popsali Kohonenovy samoorganiza£ní mapy, které jsou základem dále navrhovaných metod pro morphing. Dále jsme popsali techniku rostoucích samoorganiza£ních map, rostoucích neuronových plyn· a rozvíjejících se samoorganiza£ních strom·. Tyto techniky p°iná²ejí výhody dynamického r·stu, uvoln¥ní topologie a rychlej²ího vyhledávání. Pro prvotní experimenty s morphingem jsme se p°esto rozhodli pouºít jiº ²iroce osv¥d£ené samoorganiza£ní mapy. Po tomto nezbytném a ²irokém úvodu jsme se p°ehoupli do tv·r£í £ásti práce. Na základ¥ p°edchozích poznatk· jsme navrhli n¥kolik slibných sm¥r·, jak by ²lo vyuºít samoorganiza£ní mapy pro ú£ely morphingu. Postupn¥ jsme je implementovali, ale v¥t²ina
77
z nich se ukázala jako nepouºitelná. Úsp¥ch jsme zaznamenali aº se samoorganiza£ní mapou roz²í°enou o pam¥´ neuron· a upravenou distribucí vzor·. Tuto metodu a její základní charakteristiky, které jsme objevili, jsme potom stru£n¥ porovnali s metodou minimáln¥ pracného morphingu. Ukázalo se, ºe navrºená metoda je velmi konkurenceschopná a minimáln¥ pracný morphing v mnoha ohledech p°ed£í. Nem¥li jsme moºnost hloub¥ji otestovat optimální nastavení v²ech parametr·, proto na²e metoda vyºaduje více uºivatelem speci kovaných parametr· neº metoda minimáln¥ pracného morphingu. Protoºe je ale zna£n¥ rychlej²í, není problém n¥kolik kon gurací otestovat. Ob¥ metody se dob°e hodí na morphing fotogra í. Problémy mají s ostrými geometrickými tvary, kresbami apod. Navrºená metoda SOM obohacené o pam¥´ neuron· a s upravenou distribucí dat si zcela z°ejm¥ zasluhuje dal²í systematické testování. Uº nyní zle lze °íci, ºe je moºné na °e²ení morphingu úsp¥²n¥ pouºít samoorganiza£ní metody a ºe cíl práce byl spln¥n.
78
Literatura [1] Alahakoon D., Halgamuge S. K., Srinivansan B.: Dynamic self-organizing maps with controlled growth for knowledge discovery.
tworks 11(3), 601-614.
IEEE Transactions on Neural Ne-
[2] Bear M. F., Connors B. W., Paradiso M. A. (2006):
Neuroscience: Exploring the Brain.
Lippincott, Philadelphia. [3] Beier T., Neely S. (1992): Feature-based image metamorphosis.
26(2),
35-42
[4] Braun
C.,
check
-
Gruendl
Ursachen
M.,
und
Marberger
Folgen
C.
von
a
kol.
Attraktivitaet.
Computer Graphics (2001): Dostupné
Beautyon-line:
http://www.beautycheck.de/english/bericht/bericht.htm [5] Burian, J. (2006): Samoorganizace a kognice. In Kelemen, J., Kvasni£ka V., Pospíchal J. (eds.).
Proceedings of Cognition and Arti cial Life VI. Slezská univerzita v Opav¥,
Opava. [6] Fritzke B. (1995): A Growing Neural Gas Network Learns Topologies.Tesauro G. a kol. (ed.):
Advances in Neural Information Processing Systems
7,
625-632. MIT PRESS.
[7] Gao P., Sedeberg T. W. (1998): A work minimization approach to image morphing
.Visual Computer 14, 390-400. Springer-Verlag.
Warping and Morphing of Graphical Objects.Morgan Kaufmann Publishers, Inc., San Francisco.
[8] Gomes J., Darsa L., Costa B., Velho L. (1999):
[9] Karungaru S., Fukimi M., Akamatsu N. (2007): Automatic human faces morphing using genetic algorhitms based control points selection.
novative Computing, Information and Control
3(2),
International Journal of In-
247-256.
[10] Kohei I., Kiichi U. (2007): Combining Zeroth-Order Topology SOM and Centroidal Voronoi Tessellation for Non-Photorealistic Image Morphing. IEIC Technical Report
79
(Institute of Electronics, Information and Communication Engineers)
106(501),
35-
40.
[11] Kohonen T. (2001):
Self-Organizing Maps . Springer-Verlag, Berlin.
[12] Kotyrba M., Volná E. (2008): Samoorganizace v um¥lé inteligenci.
51(12),
Automatizace
777-779.
[13] Lee S. Y., Chwa K. Y., Shin S. Y. a kol. (1995): Image Metamorphosis Using Snakes and Free-Form Deformations.
SIGGRAPH 95 Conference Proceeding, 439-448. ACM
Press. [14] Lee S. Y., Chwa K. Y., Hahn J. a kol. (1996): Image morphing using deformation techniques.
The Journal of Visualization and Computer Animation
7,
3-23.
[15] Lee T. Y., Lin Y. Ch., Sun Y.N. a kol. (1998): Fast Feature-Based Metamorphosis and Operator Design.
Computer Graphics Forum
17(3),
15-22.
[16] Martinetz T. M., Schulten K. J. (1991): A neural-gas network learns topologies.
Arti cial Neural networks, 397-402.
[17] Martinetz T. M., Schulten K. J. (1994): Topology representing networks.
tworks 7(3), 507-522.
[18] Ma°ík V., t¥pánková O., Laºanský J. a kol. (1993):
Neural Ne-
Um¥lá inteligence (1). Academia,
Praha.
[19] Ma°ík V., t¥pánková O., Laºanský J. a kol. (2003):
Um¥lá inteligence (4). Academia,
Praha.
Pakkanen J., Iivarinen J., Oja E. (2004): The evolving tree - a novel self-organizing
Neural Processing Letters 20, 199-211.
network for data analysis.
[21] [20] Parus J., Kolingerová I. (2004): Morphing of Color Surfaces. VUT Ko²ice (ed.):
I 2004, 415-420.
[22] Rojas R. (1996):
EC
Neural Networks: a Systematic Introduction. Springer-Verlag, Berlin.
80
[23] Ruprecht D., Müller H. (1994): Deformed cross-dissolves for interpolation in scienti c visualization.
[24] Ruprecht lation.
The Journal of Visualization and Computer Animation 5, 167-181
D.,
Müller
H.
(1995):
Image
Warping
with
Scattered
IEEE Computer Graphics and Applications 15, 37-43.
Data
Interpo-
S hape Morphing Using Spherical SOIntelligent Engineering Systems Through Arti cial Neu-
[25] Sangole A., Knopf G. K., Igwe P. C. (2003): FMS.Dagli C. H. a kol. (ed.):
ral Networks 13, 637-642. ASME Press, New York.
[26] Sederberg T. W., Parry S. R. (1986): Free-form deformation of solid geometric models.
Computer Graphics
20,
151-160.
[27] Sederberg T. W., Greenwood E. (1992): A physically based approach to 2D shape blending.
Computer Graphics
26,
25-34.
A two-pass mesh warping alogrithm for object transformation and image interpolation.Technical Report 1030, ILM Computer Graphics Department,
[28] Smythe D. B. (1990):
Lucas lm, San Rafael, California.
[29] Su M-Ch., Liu I-Ch. (2001): Application of the Self-Organizing Feature Map Algorithm
Neural Processing Letters 14, 35-47.
in Facial Image Morphing.
[30] Szewczyk R., Ferencz A., Andrews H. a kol. (1997): Motion and Feature-Based Video Metamorphosis.
Proceedings of the fth ACM international conference on Multimedia,
273 - 281. Seattle.
[31] íma J., Neruda R. (1996): [32] Uhlí°, K. (2007):
obrazu.
Teoretické otázky neuronových sítí.Matfyzpress, Praha.
Aplikace radiálních bázových funkcí v po£íta£ové gra ce a zpracování
Diserta£ní práce, Fakulta aplikovaných v¥d, Západo£eská univerzita v Plzni,
Plze¬.
[33] Wolberg G. (1990):
Digital image warping.IEEE Computer Society Press, Los Alami-
tos, California.
. Visual Computer14, 360-372. Springer-
[34] Wolberg G. (1998): Image morphing: a survey Verlag.
81
[35] Zapletal J. (2007): Aplikace Radiálních bázových funkcí. Diplomová práce, Fakulta aplikovaných v¥d, Západo£eská univerzita v Plzni, Plze¬.
[36] ára J., Bene² B., Sochor J., Felkel P. (2004): Press, Brno.
82
Moderní po£íta£ová gra ka.Computer
