| Seznam |
| Téma: | Optimalizační metody pro zpracování digitálního obrazu |
|---|---|
| Vedoucí: | doc. RNDr. Daniel Průša Ph.D. |
| Vypsáno jako: | Diplomová práce |
| Popis: | V počítačovém vidění má poměrně široké uplatnění tzv. problém minimalizace energie (používá se např. při segmentaci obrazu). Jde o kombinatorický grafový problém, který je v obecném případě NP-úplný. Za určitých podmínek je ale efektivně řešitelný aplikací algoritmů hledajících maximální tok v síti, viz [1] a [2].
Alternativou k tomuto je formulace úlohy pomocí lineárního programování. Obecně nejsou solvery pro lineární programování vhodné pro úlohy s extrémně velkým množstvím rovnic a proměnných. V případě minimalizace energie existuje však možnost implementovat simplexový algoritmus velice efektivně jako grafový algoritmus (tedy bez použití simplexové tabulky). Cíle práce jsou následující: - Seznámit se s variantou simplexového algoritmu "ušitého na míru" pro úlohu minimalizace energie. - Navrhnout zjednodušenou variantu tohoto algoritmu, která bude specializovaná pouze na tzv. submodulární instance uvažovaného problému. - Implementovat návrh a otestovat jej pro vybrané problémy (segmentace, shape fitting). Předpoklady: základní grafové algoritmy a lineární programování, C/C++ (případně Java, s tím, že C bude nastudováno) Pozn.: V rámci tématu lze pracovat i na výzkumném/sw projektu. |
| Literatura: | [1] Y. Boykov, V. Kolmogorov: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. http://www.csd.uwo.ca/~yuri/Papers/pami04.pdf [2] V. Kolmogorov, K. Rother: Minimizing Non-submodular Functions with Graph-cuts - a Review. http://luthuli.cs.uiuc.edu/~daf/courses/optimization/mrfpapers/04204169.pdf [3] D. Průša: Graph-based Simplex Method for Pairwise Energy Minimization with Binary Variables. http://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/Prusa_Graph-Based_Simplex_Method_2015_CVPR_paper.pdf |
| Vypsáno dne: | 02.05.2019 |