Detail of the student project

List
Topic:Grafový simplexový algoritmus pro minimalizaci diskrétní energie
Department:Katedra kybernetiky
Supervisor:doc. RNDr. Daniel Průša, Ph.D.
Announce as:Bakalářská práce, Semestrální projekt
Description: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 [2] a [3].
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 projektu jsou následující:
- Seznámit s variantou simplexového algoritmu "ušitého na míru" pro úlohu minimalizace energie [1,4].
- Popsat a naimplementovat metodu pro tzv. submodulární instance. Implementace metody byla cílem již v [1], výsledek nelze ale považovat za zdařilý a odladěný.
- Otestovat implementaci pro náhodná i některá reálná data (https://vision.cs.uwaterloo.ca/data/maxflow).
Bibliography:[1] E. Tiuzhina: Application of Simplex Algorithm for Submodular Discrete Energy Minimization with Binary Variables, Czech Technical University in Prague, bachelor thesis, 2018.
[2] 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
[3] V. Kolmogorov, K. Rother: Minimizing Non-submodular Functions with Graph-cuts - a Review. http://luthuli.cs.uiuc.edu/~daf/courses/optimization/mrfpapers/04204169.pdf
[4] 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
Responsible person: Petr Pošík