Title: Memory Efficient Max Flow for Multi-label Submodular MRFs,
Abstract: Multi-label submodular Markov Random Fields (MRFs) have been shown to be
solvable using max-flow based on an encoding of the labels proposed by
Ishikawa, in which each variable $X_i$ is represented by $\ell$ nodes (where
$\ell$ is the number of labels) arranged in a column. However, this method in
general requires $2\,\ell^2$ edges for each pair of neighbouring variables.
This makes it inapplicable to realistic problems with many variables and
labels, due to excessive memory requirement. In this paper, we introduce a
variant of the max-flow algorithm that requires much less storage.
Consequently, our algorithm makes it possible to optimally solve multi-label
submodular problems involving large numbers of variables and labels on a
standard computer.