---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Igor
foaf_name: Gridchyn, Igor
foaf_surname: Gridchyn
foaf_workInfoHomepage: http://www.librecat.org/personId=4B60654C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1109/ICCV.2013.288
dct_date: 2013^xs_gYear
dct_language: eng
dct_publisher: IEEE@
dct_title: Potts model, parametric maxflow and k-submodular functions@
...