Potts model, parametric maxflow and k-submodular functions Conference Paper

Author(s): Gridchyn, Igor; Kolmogorov, Vladimir
Title: Potts model, parametric maxflow and k-submodular functions
Affiliation IST Austria
Abstract: The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.
Conference Title: ICCV: International Conference on Computer Vision
Conference Dates: December 1-8, 2013
Conference Location: Sydney, Australia
Publisher: IEEE  
Date Published: 2013-12-01
Start Page: 2320
End Page: 2327
Sponsor: APRS,Australian National University,CVF,et al.,IEEE Computer Society,NICTA,Electronics Engineers Inc.
DOI: 10.1109/ICCV.2013.288
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work