Quadratic Pseudo-Boolean Optimization for Scene Analysis using CUDA

Andreas Bauer
Karlsruher Institut fur Technologie, Fakultat fur Informatik
Karlsruher Institut fur Technologie, 2014


   title={Quadratic Pseudo-Boolean Optimization for Scene Analysis using CUDA},

   author={Bauer, Andreas},



Download Download (PDF)   View View   Source Source   



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.
Rating: 2.5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: