Optimizing Large-scale Irregular Markov Random Fields on GPUs

Energy optimization by graph cuts in alpha-Expansion have become ubiquitous in computer vision during the last decade. Especially for grid topologies, fast multicore and even massively-parallel solvers have been developed. However, those are based on cache-optimal storage of the topology and hardcoded neighborhoods. For irregular topologies, few implementations of different methods are available. Additionally, none of them uses multicore systems or even massively-parallel systems such as graphics processing units (GPUs). In this thesis, we first review the state-of-the-art techniques and analyze their potential for parallelization. After pointing out that most methods are inherently serial, we present two novel methods for energy minimization in pairwise markov random fields: (Heuristic) iterative monotonic fixing (HIMF) and monte carlo partial cuts (MCCO). While HIMF adapts the method of dynamic programming with different heuristics, MCCO relies on a theoretical foundation to find a minimum s-t-cut in a graph without computing the maximum flow. Theorems that state sufficient conditions for partially solving those cuts are given and for the first time proven. Both methods are evaluated against different (single core) author implementations that are available