Potts model, parametric maxflow and k-submodular functions
This work provides a faster algorithm for energy minimization in computer vision, which is incremental but offers practical improvements for applications like stereo matching.
The paper tackles the NP-hard problem of minimizing the Potts energy function in computer vision by reducing runtime from k maxflow computations to O(log k) or one parametric maxflow computation, achieving significant speed-ups, e.g., 50-93% labeled pixels in stereo tests.
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 {\em 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 {\em Tree Metrics}. We also show a connection to {\em $k$-submodular functions} from combinatorial optimization, and discuss {\em $k$-submodular relaxations} for general energy functions.