Podrobnosti studentského projektu

Seznam
Téma:Optimalizační metody pro zpracování digitálního obrazu
Katedra:Katedra kybernetiky
Vedoucí:RNDr. Daniel Průša Ph.D.
Vypsáno jako:DP
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
Za obsah zodpovídá: Petr Pošík