Studijní program P4I5 Informatika - vizuální výpočty a počítačové hry

Oborová rada

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/or/p4i5 .

Spolupracující ústavy

– Ústav teorie informace a automatizace AV ČR, v.v.i.
Pod Vodárenskou věží 4, 182 08 Praha 8
http://www.utia.cas.cz/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/p4i5 .

Poskytovaná výuka

Seznam požadavků ke státní doktorské zkoušce

Tématické okruhy 1 - 5 jsou povinně volitelné v tom smyslu, že student je povinen složit zkoušku z alespoň jednoho z okruhů 1 a 2 a zároveň alespoň jednoho z okruhů 3 - 5. K nim si uchazeč zvolí jedno téma profilující z (dosud nezvolených) okruhů 1 - 9 anebo jiné podle dohody se školitelem. Student by měl složit státní doktorskou zkoušku do konce druhého ročníku studia.

Povinně volitelné okruhy (alespoň jeden okruh z 1 a 2; alespoň jeden okruh z 3 - 5)

1. Teoretické základy informatiky
Diskrétní matematika: Základy teorie grafů, reprezentace grafů v paměti, algoritmy nad grafy.

Logika, algoritmy: Vybrané algebraické struktury. Predikátový počet. Formální systémy, bezespornost a úplnost, Goedelovy věty. Teorie vyčíslitelnosti, Turingovy stroje a ekvivalentní modely výpočtu. Algoritmy a jejich složitost, NP-úplné problémy. Algoritmicky nerozhodnutelné problémy. Věty o rekursi.

2. Matematické metody pro grafiku a zpracování obrazu
Maticové výpočty: Schurova věta, význam ortogonality a normality, rozklady matic, metody pro řešení soustav lineárních rovnic, singulární rozklad, úlohy nejmenších čtverců, částečný problém vlastních čísel, nelinearita a numerická nestabilita v maticových výpočtech.

Spliny: teorie polynomiálních splinů, interpolační a zhlazující spliny, racionální spliny.

Wavelety: teorie multirozkladu, aplikace, algoritmy, biortogonální wavelety, vícerozměrné wavelety, balíčky waveletů,  ,,lifting scheme", spojitá waveletová transformace; Mallatova konstrukce multirozkladu; wavelety s kompaktním nosičem; příklady waveletů

Fourierova transformace v L1(R); Wienerova teorie Fourierovy transformace v L2(R); Paleyova-Wienerova věta a Heisenbergova nerovnost.

Základy variačního počtu (Euler-Lagrangeovy rovnice, brachistochrona, Lagrangeova funce, funkce s omezenou variací)

Základy numerických metod řešení (parciální diferenciální rovnice, metoda konečných prvků, metoda konečných diferencí, metoda největšího spádu, konjugovaných gradientů, kvadratické programování)

Statistické metody (odhad hustoty rozdělení pravěpodobnosti, parametrické, neparametrické metody, testování hypotéz)

Geometrické transformace, homogenní souřadnice, převod mezi souřadnými systémy zobrazovacím řetězci.

3. Základy počítačové grafiky
Základy 2D grafiky: vidění a barvy, kolorimetrie a barevné prostory, měření a reprodukce barev, rastrová grafika, operace s rastrovým obrazem, rastrové kreslení, anti-aliasing, datové struktury pro 2D vyhledávání, komprese obrazu a videa, HDR fotografie, mapování odstínů.

Základy 3D grafiky: transformace, reprezentace 3D scén, úroveň detailu, parametrické křivky a plochy, viditelnost, stínování, textury, hardwarově akcelerovaná grafika, stínovací programy, základy CUDA/OpenCL.

Základy realistické syntézy obrazu: Rekurzivní sledování paprsku a metody jeho urychlení, datové struktury, distribuované (rozprostřené) sledování paprsku, základy radiační metody, zobrazovací rovnice a její řešení pomocí Monte Carlo metod.

Základy vizualizace dat: objemová data, počítačová tomografie a magnetická rezonance, výpočet izoploch, přímé zobrazování objemu, model šíření světla v 3D médiu, vizualizace vektorových polí a tenzorů vyšších řádů

4. Základy analýzy obrazu
Digitalizace obrazu, vzorkování a kvantování spojitých funkcí, Shannonův teorém. Základní operace s obrazy, histogram, změny kontrastu, odstranění šumu, zaostření obrazu. Lineární filtrace v prostorové a frekvenční oblasti, konvoluce, Fourierova transformace. Detekce hran a rohů. Degradace obrazu a její modelování, odstranění základních typů degradací (rozmazání pohybem a defokusací), inverzní a Wienerův filtr, odhady PSF, slepá a vícekanálová dekonvoluce, variační přístup. Segmentace obrazu, klasické i variační přístupy (prahování, region growing, Mumford-Shah funkcionál, active contours, level sets). Registrace (matching) obrazů. Invarianty pro popis a rozpoznávání 2-D objektů (obecné principy, vizuální příznaky, momenty, Fourierovy deskriptory, diferenciální příznaky, momentové invarianty). Teorie příznakového rozpoznávání, klasifikátory s učením a bez učení, NN-klasifikátor, lineární klasifikátor, SVM klasifikátory, Bayesův klasifikátor. Příklady použití v analýze obrazu. Shluková analýza v prostoru příznaků, iterační a hierarchické metody. Redukce dimenzionality příznakového prostoru, PCT, suboptimální metody pro výběr příznaků. 2D waveletová transformace (WT) - matematické základy. Použití WT pro detekci hran a význačných bodů v obrazu, potlačení šumu, registraci obrazu a  fúze obrazu. Komprese obrazu pomocí WT.

5. Základy 3D počítačového vidění a robotiky
Počítačové vidění s jednou kamerou: geometrie jednoduché perspektivní kamery, projektivní rovnice, kalibrace kamery, vnější a vnitřní parametry, rekonstrukce vzoru z jeho obrazu.

Stereo-vidění: kanonické stereo a určování hloubky scény, geometrie dvou kamer, epipolární ohraničení, fundamentální matice a její určování, řešení problému stereo korespondence.

Detekce, počítání, měření a sledování objektů: detekce objektů, lokální příznaky, granulometrie, Kalmanův filtr, mean shift.

3D rekonstrukce objektů: tvar z XX (ze stínování, z více světelných zdrojů, z textury, atd.).

Architektura řízení robotů: plánování pohybu, odometrie, SLAM, architektura kontroly robota.

Přímá a inverzní kinematika: terminologie, typické struktury, určování polohy jednotlivých částí robota, určování koncové polohy.

Volitelné okruhy

6. Počítačová geometrie
Aplikovaná výpočetní geometrie: definice, vlastnosti a algoritmy pro geometrické vyhledávání, konvexní obálky, Voronoi diagramy, jejich aplikace a zobecnění, triangulace v 2D a 3D a jejich aplikace, střední osa, rekonstrukce povrchu, průsečíky a průniky geometrických objektů.

Geometrie pro počítačovou grafiku: Grupa projektivních, afinních a eukleidovských transformací. Reprezentace těchto grup pomocí matic. Projektivní prostor, homogenní souřadnice. Sférická geometrie. Využití kvaternionů a duálních kvaternionů při popisu eukleidovského pohybu.

Křivky a plochy v počítačové grafice: Prostor spline funkcí, Hermitovy spliny, kubické spliny, Bézierovy křivky a plochy, B-spline křivky a plochy, racionální křivky a plochy, NURBS, speciální plochy, geometrická spojitost.

7. Syntéza realistického obrazu
Radiometrické a fotometrické veličiny, zobrazovací rovnice, důležitost, dualita transportu světla a důležitosti, operátorové vyjádření transportu světla a důležitosti. Monte Carlo kvadratura, nestranné Monte Carlo metody pro řešení zobrazovací rovnice (sledování cest, sledování světla). Kombinované estimátory a aplikace: přímé osvětlení, obousměrné sledování cest. Metropolis-Hastings metoda vzorkování, Metropolis light transport. Přibližné metody řešení zobrazovací rovnice: (progresivní) mapování fotonů, (ir)radiance caching, okamžitá radiozita, lightcuts. Radianční metoda, adaptivní zjemňování, hierarchická radiozita, stochastická radiozita. Zobrazování participujících médií: rovnice transportu světla, algoritmy pro zobrazování médií, speciální techniky pro mraky a atmosféru, průsvitné materiály, BSSRDF. Reyes architektura, standard RenderMan, princip stínovacích jazyků v RenderMan a OpenGL. Prediktivní syntéza obrazu: regulace chyby v rendering pipeline, psycho-fyzikálně věrné mapování odstínů, simulace pokročilých optických jevů (polarizace, difrakce), fluorescenční materiály, fyzikální věrnost konstruktů stínovacích jazyků.

8. Invarianty pro rozpoznávání
Geometrické momenty, definice a základní vlastnosti, normalizace. Komplexní momenty. Momentové invarianty vzhledem k otáčení a měřítku obrazu, úplnost, nezávislost, konstrukce báze. Momentové invarianty vzhledem k afinní transformaci obrazu, metoda grafů. Momentové invarianty vzhledem ke konvoluci, N-fold symetrická jádra, nulprostor a diskriminabilita. Kombinované invarianty. Momentový matching. Ortogonální momenty (Legendrovy momenty, Fourier-Mellin momenty, Zernikovy momenty). Diskrétní momenty a algoritmy pro jejich výpočet.

9. Vývoj počítačových her
Architektura herní engine: renderer, fyzika, audio, I/O, síťová komunikace, herní mechaniky, multiplatformnost, řetězec produkce herního obsahu, aj. Příklady existujících herních engine.

Techniky renderingu v reálném čase: výpočet vržených stínů, stínové mapy, stínové objemy, pokročilé techniky stínových map (filtrování, kaskádové mapy). Odložené stínování - princip, výhody, nevýhody. Ambientní zastínění a jeho výpočet v prostoru obrazu.

Pokročilé stínování v reálném čase: BRDF, rovnice odrazu světla, reprezentace funkcí, orotgonální a ortonormální báze, sférické harmonické a jejich použití pro reprezentaci BRDF a osvětlení, HDR mapa prostředí - princip, akvizice, použití. Irradiance environment mapping.

Architektura autonomního agenta. Hry jako příklad multi-agentního prostředí.

Reprezentace a uvažování o herním prostoru: abstrakce prostředí (navigační graf, navigační mesh, voxelová navigace, reprezentace viditelnosti, šíření zvuku v prostředí), navigace agentů v 3D prostředí, hledání nejkratší cesty (A*, jeho varianty a způsoby urychlení výpočtů), následování cesty (vyhýbání se kolizí se statickými a dynamickými objekty, reciproční vyhýbání se kolizí, techniky steeringu).

Reaktivní přístupy k řízení chování agentů: hierarchické konečné automatiy, stromy chování, prostory rozhodování.

Distribuce chování agenta skrz prostředí a koordinace: chytré objekty, chytré oblasti, géniové.

Příklady použití plánování v počítačových hrách.

Doporučená literatura

–K. Mehlhorn:  Data Structures and Algorithms 2: Graph Algorithms and NP–completeness. EATCS – monograph, Springer–Verlag 1984.

–R. E. Tarjan:  Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia 1983.

–J. E. Hopcroft, J. D. Ullman:  Introduction to Automata Theory, Languages, and Computation. Addison–Wesley Publ. Company 1979.

–M. R. Garey, D. S. Johnson:  Computers and Intractability: A Guide to the Theory of NP–completeness. Freeman, San Francisco 1978.

–O. Demuth, R. Kryl, A. Kučera:  Teorie algoritmů I, II. SPN Praha 1989.

–R. I. Soare: Recursively enumerable sets and degrees. Springer–Verlag, Berlin, Heidelberg, New York 1987

–Duintjer Tebbens, J., Hnětynková, I., Plešinger, M., Strakoš, Z., Tichý, P.: Analýza metod pro maticové výpočty I. Skripta MFF UK, 2011.

–Watkins, D.S.: Fundamentals of Matrix Computations. J. Wiley & Sons, New York, Third edition 2010.

–Golub, G.H., Van Loan, C.F.: Matrix Computations (Third edition). J. Hopkins Univ. Press, Baltimore, 1996

–Najzar K.: Základy teorie waveletů. Skripta, Nakl. Karolinum 2004.

–Najzar K.: Základy teorie splinů. Skripta, 2006.

–Micula Ch. and Micula S.: Handbook of splines. 1999.

–Resnikoff H. L., Wells R. O., Jr..: Wavelets analysis. Springer 1998.

–Andreas Antoniou and Wu-Sheng Lu: Practical Optimization: Algorithms and Engineering Applications. Springer, 2007.

–Marschner S., Shirley P.: Fundamentals of Computer Graphics. A K Peters/CRC Press, 4th Revised edition, 2015.

–Shirley P., Morley R. K.: Realistic Ray Tracing. A K Peters, 2nd Revised edition, 2003.

–Pratt W. K.: Digital Image Processing (3rd ed.). John Wiley, New York, 2001

–Gonzales R. C., Woods R. E.: Digital Image Processing (2nd ed.). Prentice Hall, 2002

–Zitová B., Flusser J.: Image registration methods: a survey. Image and Vision Computing, 21 (2003), 11, pp. 977-1000

–Duda R.O. et al.: Pattern Classification, (2nd ed.). John Wiley, New York, 2001

–Flusser J., Suk T. and Zitová B.: Moments and Moment Invariants in Pattern Recognition. Wiley & Sons Ltd., 2009.

–Richard Hartley, Andrew Zisserman. Multiple View Geometry in Computer Vision, 2nd Edition, Cambridge University Press, 2004.

–Subhash Challa, Mark R. Morelande, Darko Mušicki, Robin J. Evans. Fundamentals of Object Tracking, Cambridge University Press; 1 edition (November 28, 2011).

–Pierre Soille. Morphological Image Analysis: Principles and Applications, Springer (December 7, 2010), ISBN 3-540-65671-5

–O' Rourke, Joseph: Computational Geometry in C. Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000.

–de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications. Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001.

–M. Lávička: KMA/G2 Geometrie 2. Pomocný učební text, ZČU Plzeň, 2006

–Jirí Žára a kol: Moderní počítačová grafika. Computer Press, 1998

–František Ježek: Geometrické a počítačové modelování. Plzeň 2009

–Pharr M., Jakob W., Humphreys G.: Physically Based Rendering: From Theory To Implementation. Morgan Kaufmann; 3rd edition, 2016.

–Veach E.: Robust Monte Carlo Methods for Light Transport Simulation. Ph.D. dissertation, Stanford University, 1997.

–Shirley P., Morley R. K.: Realistic Ray Tracing. A K Peters, 2nd Revised edition, 2003.

–Dutre P., Bala K., Bekaert P.: Advanced Global Illumination. A k Peters, 2nd edition, 2006.

–Glassner A.: Principles of Digital Image Synthesis. Addison- Wesley, 1995.

–Jensen H.W.: Realistic Image Synthesis Using Photon Mapping. A K Peters, 2001.

–J. Flusser, T. Suk and B. Zitová: Moments and Moment Invariants in Pattern Recognition. Wiley & Sons Ltd., 2009.

–J. Flusser, T. Suk and B. Zitová, 2D and 3D Image Analysis by Moments, Wiley & Sons Ltd., 2016.

–Gregory, Jason. Game engine architecture. AK Peters/CRC Press, 2014.

–Nystrom, Robert. Game programming patterns. Genever Benning, 2014.

–Millington, Ian, and John Funge. Artificial intelligence for games. CRC Press, 2009.

–Rabin, Steve (ed.): AI Game Programming Wisdom series, Charles River Media, 2002-2008.

–Rabin, Steve (ed.). Game AI Pro: Collected Wisdom of Game AI professionals series, AK Peters/CRC Press, 2013-2017

–Tomas Akenine-Moller, Eric Haines, Naty Hoffman. Real-Time Rendering, A K Peters/CRC Press; 4th edition 2018.