Pokud vás v p²edcházejících ƒíslech Chipu zaujalo povídání o fraktální geometrii, nenechte si ujít jeho poslední ƒást. Je v╪nována aplikaci této disciplíny ve velice perspektivním oboru um╪lé inteligence, v poƒítaƒovém vid╪ní.
Jak jiº z názvu plyne, pàjde o rozeznávání obrazcà pomocí poƒítaƒà. Historie tohoto odv╪tví je stará p²ibliºn╪ jako éra PC. Byly vypracovány mnohé metody, jejichº pomocí se ƒlov╪k snaºí napodobit to, co jeho zrak a mozek samoƒinn╪ provád╪jí po celou dobu ºivota. Snímat obrazy, analyzovat je, rozd╪lit je na objekty, provést jejich identifikaci co do pohybu a druhu.
Vzhledem k tomu, ºe ƒlov╪k je tvor vynalézav∞ a hrav∞, není p²itom p²i moºnostech dneτní techniky omezen jen na viditeln∞ obor spektra, ale màºe pomocí poƒítaƒového vid╪ní teoreticky rozeznávat objekty i v jin∞ch spektrálních oblastech, nap²íklad v infraƒervené.
Poƒítaƒové vid╪ní lze rozd╪lit zhruba do t╪chto následujících krokà:
? Získání digitálního obrazu.
? Θprava obrazu.
? Rozloºení obrazu na objekty.
? Popis jednotliv∞ch objektà.
? Klasifikace jednotliv∞ch objektà.
Získání digitálního obrazu je proces, p²i n╪mº se za²ízení typu scanner ƒi videokamera pouºívají k vytvo²ení daného obrazu a k jeho p²evedení do digitální podoby. Tento proces velmi v∞znamn╪ ovlivσuje vτechny následující, nebo£ na kvalit╪ obrazu záleºí, jak budou dalτí kroky úsp╪τné. Nap²íklad pokud získáme obraz, v n╪mº vinou horτího snímacího za²ízení nebudou zachyceny jisté detaily, pak samoz²ejm╪ také nebudou nalezeny a zpracovány v dalτích krocích. To màºe mít nep²íjemn∞ dàsledek - zejména v p²ípadech, kdy se jedná nap²íklad o vyhodnocování τpionáºních snímkà apod.
Θpravou obrazu rozumíme v podstat╪ pouºití ràzn∞ch filtrà a opravn∞ch mechanismà k odstran╪ní poruch obrazu (nejràzn╪jτích τumà vnikl∞ch do obrazu, a£ uº p²ed vstupem do kamery, ƒi b╪hem zpracování). B╪hem tohoto procesu se nejen odstraσuje τum, ale také zlepτuje kvalita obrazu, nap²íklad vyost²ováním hran, potlaƒením, ƒi zv∞razn╪ním n╪kter∞ch vlastností obrazu pomocí filtrace, apod.
Jakmile je obraz upraven, je moºné provést jeho rozloºení na jednotlivé objekty. Za tímto úƒelem bylo vyvinuto n╪kolik metod, jako je segmentace prahováním (za vyuºití urƒit∞ch vlastností obrazu se zv∞razní n╪které objekty), segmentace naràstáním oblastí (zde se obraz rozƒleσuje na homogenní celky; kritérium homogenity màºe b∞t zaloºeno nap². na jasov∞ch vlastnostech) a dalτí.
Takto p²ipravené objekty je t²eba popsat n╪jak∞m vhodn∞m zpàsobem, kter∞ by umoºnil jejich jednoznaƒnou klasifikaci. To lze ud╪lat nap². binárním popisem, kter∞ se dá bez problémà aplikovat na ƒernobílé obrazce tak, ºe se vytvo²í vektor ƒi matice s prvky 0, nebo 1 podle toho, zda byl dan∞ pixel bíl∞, ƒi ƒern∞ - v∞sledkem jsou pochopiteln╪ velké objemy dat, coº není ºádoucí. Dalτí moºností je hraniƒní popis, p²i n╪mº se hranice objektu "rozsekají" na stejné úseky a jejich orientace se op╪t zapíτe jako vektor ƒísel, ze kterého lze takov∞to objekt op╪t snadno rekonstruovat.
Oba p²ístupy mají své nedostatky. Binární produkuje ƒasto neúnosné objemy dat a hraniƒní není jednoznaƒn∞ (ztrácí se informace o struktu²e objektu). Jako slibn∞ sm╪r (samoz²ejm╪ mimo jiné existující metody) se zde jeví práv╪ pouºití fraktální geometrie - a to nejen pro popis, ale i pro následnou klasifikaci. Tento p²ístup zcela vyluƒuje velké objemy dat i nejednoznaƒnosti vypl∞vající z hraniƒního popisu.
Cel∞ princip je zaloºen na faktu, ºe kaºd∞ objekt lze popsat pomocí malého mnoºství ƒísel, která jej jednoznaƒn╪ urƒují. "Fraktálov∞" p²ístup za tím úƒelem zjistí koeficienty tzv. afinních transformací, které dan∞ objekt generují, a tyto koeficienty pak pouºije p²i klasifikaci tohoto objektu nap². pomocí neuronové sít╪.
Metodu lze demonstrovat na ukázkovém p²íkladu, kter∞ se skládal ze t²í experimentà. První byl zam╪²en na dobu uƒení, druh∞ zjiτ£oval, zda neuronová sí£ dokáºe pomocí fraktálního popisu rozeznávat p²ísluτné objekty, a ve t²etím se ²eτil tzv. inverzní fraktální problém (IFP). T²etí experiment v podstat╪ demonstruje, ºe nap². pomocí evoluƒních algoritmà je moºné nalézt koeficienty afinních transformací, které generují p²ísluτn∞ fraktál.
Experiment 1 - uƒení
Zde byly pouºity dv╪ t²ívrstvé sít╪ s topologiemi vhodn∞mi pro ²eτen∞ problém a porovnávaly se dva p²ístupy: binární a fraktální. Cílem bylo nauƒit sí£ na co nejmenτí chybu. Jak je z²ejmé z obrázku 1, fraktální p²ístup byl jednoznaƒn╪ lepτí. Neuronová sí£ zvládla uƒení ve fraktálním popisu za desetinu doby, p²iƒemº se uƒila na celém objektu - Sierpinského trojúhelník (viz obr. 3). Uƒení pomocí binárního popisu naprosto neusp╪lo, p²estoºe bylo "lehƒí", nebo£ místo celého objektu popisovalo jen jeho vrcholek, tj. asi 1/4 celého objektu.
Experiment 2 - rozeznávání
Ve druhém experimentu se zkouτelo rozeznávání. Byla vytvo²ena matice popisující fraktál bludiτt╪, kter∞ byl mutován tak, aby se nakonec p²em╪nil na Sierpinského trojúhelník (obr. 2). K mutaci byly pouºity faktory rotací a zmenτení v p²ísluτn∞ch afinních transformacích. Zároveσ s touto maticí se generovala trénovací mnoºina - co mutant, to dvojice vektorà v trénovací mnoºin╪; na ní pak byla sí£ uƒena.
Dvojice vektorà v trénovací mnoºin╪ byly zvoleny tak, ºe vstupní vektory do sít╪ byly vektory afinních transformací daného objektu-mutanta a v∞stupní vektor byl kombinací 0 a 1. µlo tedy o klasifikaci do t²í t²íd (obr. 3).
Po uƒení byly síti p²edkládány postupn╪ jednotliví mutanti a zaznamenávány odpov╪di sít╪ - vidíte je na obr. 4. T²em v∞stupním neuronàm zde odpovídají t²i sloupcové grafy. Hodnota 1 znamená, ºe p²ísluτnn∞ vstup pat²í do dané t²ídy (lev∞ - "v╪tev", prost²ední - bludiτt╪, prav∞ - trojúhelník; srv. obr. 3), hodnota 0, ºe nepat²í.
Z obrázku 4 je jasn╪ vid╪t, ºe se sí£ nauƒila klasifikovat. "Zmatená" byla jenom mezi dv╪ma ƒern∞mi hranicemi, kdy nebyla schopna ²íci, kam dan∞ vstup pat²í (bludiτt╪, ƒi trojúhelník?). Tato neurƒitost vτak byla tém╪² minimální, a proto lze experiment povaºovat za úsp╪τn∞. Vºdy£ to, ºe sí£ nebyla schopna rozeznat ƒty²i vstupní objekty, není nijak ²ídk∞ jev ani v lidském vid╪ní - naτe neuronové sít╪ (mozky) také mnohdy nerozeznají p²edm╪t kvàli jeho vzdálenosti, natoƒení ƒi n╪jakému jinému nedostatku vizuálních informací.
Experiment 3 - inverzní fraktální problém
I kdyº p²edchozí experiment dopadl dob²e, po²ád zàstává nezodpov╪zena otázka, jak získat koeficienty afinních transformací od reáln∞ch objektà. V tomto experimentu proto byla pro identifikaci t╪chto koeficientà pouºita diferenciální evoluce, pro niº byla definována úƒelová funkce. Její minimalizace pak vedla k nalezení afinních transformací, které generují originální fraktál.
Jako originální fraktál, jehoº afinní transformace m╪ly b∞t identifikovány, byl pouºit tzv. pavouk a Mandelbrotàv vír. Ty byly p²evedeny do matic, v nichº 1 znamenala ƒern∞ bod a 0 bíl∞. Diferenciální evoluce pak evoluƒním procesem "τlechtila" generace nejvhodn╪jτích fraktálà; po 2000 generacích byl proces τlecht╪ní ukonƒen a jako identifikovan∞ fraktál byl vzat nejlepτí z poslední generace. V∞sledky vidíte na obrázcích 5 a 6.
Kaºd∞ fraktál v kaºdé generaci byl reprezentován maticí nul a jedniƒek a porovnáván s maticí originálního fraktálu. Jako tzv. Hammingova (binární) vzdálenost, která byla minimalizována, se brala suma vτech jedniƒek, které se v maticích nep²ekr∞valy (tj. ƒerné "ƒtvereƒky", které se nep²ekr∞valy) - práv╪ t╪mito body se fraktály od sebe liτily. Suma rovnající se nule pak znamená, ºe oba fraktály jsou na dané úrovni rozliτení pln╪ totoºné.
Jak je z uveden∞ch obrázkà vid╪t, shoda mezi originály a rekonstrukcí byla velmi dobrá. Hodnoty, které v algoritmu TEA generovaly identifikovan∞ fraktál, se od originálních hodnot liτily jen v setinách. Vlastní evoluce si vyºádala 2 1/2 hodiny v prost²edí Mathematica? na poƒítaƒi PC/Pentium MMX s taktem 230 MHz. V jazycích jako nap². C++ by byla jist╪ mnohem rychlejτí (podle posledního experimentu 5 minut pro 2000 generací, v kaºdé generaci bylo 40 jedincà).
V∞sledek tohoto experimentu je velmi dobr∞ a ukazuje, ºe je moºné pouºít evoluƒní algoritmy na identifikaci fraktálà nejen um╪l∞ch, ale i na fraktály reálného sv╪ta, jak∞m je nap². naτe známá kapradina. Vzhledem k tomu, ºe fraktály nejsou jen grafické objekty, ale lze na n╪ pohlíºet také jako na "v∞slednici" chování dynamick∞ch systémà, nab∞vá jejich moºná identifikace na v∞znamu jeτt╪ více.
Záv╪r
I kdyº zde uvedené informace o fraktální geometrii a jejím vyuºití byly jen velmi strohé, lze z nich snad "vycítit", ºe fraktální geometrie není jen módním trendem, jak to tvrdí ràzní lidé, ale je jedním z nov∞ch a ºivotaschopn∞ch sm╪rà, které se v souƒasné v╪d╪ zaƒínají objevovat. Popustíme-li uzdu fantazii, snadno p²ijdeme na dalτí aplikace t╪chto matematick∞ch "monster". Uvaºujme nap²íklad o rozeznávání a syntéze zvuku. Lze-li pomocí fraktální geometrie snadno popsat datov╪ nároƒné obrazy, proƒ by to neτlo i se zvukem? Fraktální popis se totiº hodí nejen pro grafické objekty, ale i pro ƒasové pràb╪hy (fraktální interpolace - [6]). V p²ípad╪ vyuºití takové metody nezískáme jen vhodn∞ popis daného zvuku pro rozeznání ƒi diagnostiku, ale také ekvivalent daného zvuku o vysoké kompresi. Problém syntézy je v podstat╪ uº jen opaƒn∞ postup - z daného fraktálního popisu se vygeneruje p²ísluτn∞ zvukov∞ fraktál.
Lze tedy oƒekávat, ºe se s fraktály budeme setkávat stále ƒast╪ji v mnoha oborech - a moºná i s tím, ºe o jejich momentálním vyuºití v n╪jakém postupu nebudeme mít ani pon╪tí.
Ivan Zelinka (zelinka@zlin.vutbr.cz)
Pouºitá a doporuƒená literatura
[1] Peitgen H. O., Jurgens H., Saupe D.: Chaos and Fractals, New Frontiers of Science, Springer-Verlag 1992, ISBN 3-540-97903-4.
[2] Barnsley M. F., Fractals Everywhere: Academic Press Professional 1993, ISBN 0-12-079061-0.
[4] Bunde A., Shlomo H.: Fractals and Disordered Systems, Springer, Berlin, 1996, ISBN 3-540-56219-2.
[5] Hastings H. M., Sugihara G.: Fractals a User's Guide For The Natural Sciences, Oxford University Press, 1993, ISBN 0-19-854597-5.
[6] Zelinka I.: Aplikovaná informatika, FT VUT Zlín (v tisku).
[7] Zelinka I.: Um╪lá inteligence I, VUT Brno, 1998, ISBN 80-214-1163-5.
[8] Coveney P., Hihgfield R.: µíp ƒasu, Oldag Publishers, 1995, ISBN 80-85954-08-5.
[9] Nicolis G., Prigorine I.: Self-Organization in Nonequilibrium Systems, John Wiley & Sons, 1977, ISBN 0-471-02401-5.
[10] Hilborn R. C.: Chaos and Nonlinear Dynamics, Oxford University Press, 1994, ISBN 0-19-508816-8.
