Abstract

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flflow based on an encoding of the labels proposed by Ishikawa, in which each variable Xi is represented by ℓ nodes (where ℓ is the number of labels) arranged in a column. However, this method in general requires 2 ℓ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-flflow 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