@inproceedings{2276, 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.}, author = {Gridchyn, Igor and Kolmogorov, Vladimir}, location = {Sydney, Australia}, pages = {2320 -- 2327}, publisher = {IEEE}, title = {{Potts model, parametric maxflow and k-submodular functions}}, doi = {10.1109/ICCV.2013.288}, year = {2013}, }