high performance computing on graphics processing units: hgpu.org

Many problems in early computer vision, like image segmentation, image reconstruction, 3D vision or object labeling can be modeled by Markov Random Fields (MRF). General algorithms to optimize a MRF like Simulated Annealing, Belief Propagation or Iterated Conditional Modes are either slow or produce low quality results [Rother 07]. On the other hand, in the last years a discrete subset of MRFs, which contain only so called quadratic pseudo-boolean energy functions, has been shown to be solvable very efficiently by graph cuts [Kolmogorov 04]. Graph cuts can be accelerated by the use of the graphics processing unit (GPU). GPU computing has become popular in a wide range of applications aside from graphics. There are already implementations in the context of image segmentation [Vineet 08], though we did not find any implementation for arbitrary graphs. Unfortunately, the Quadratic Pseudo-Boolean Optimization (QPBO) becomes NP-hard if the energy includes so called supermodular terms. Algorithms have been developed to obtain at least a partial solution in many cases. These algorithms are strictly sequential, though. No implementations we know use the GPU.