Measuring uncertainty in graph cut solutions

In recent years graph cuts have become a popular tool for performing inference in Markov and conditional random fields. In this context the question arises as to whether it might be possible to compute a measure of uncertainty associated with the graph cut solutions. In this paper we answer this particular question by showing how the min-marginals associated with the label assignments of a random field can be efficiently computed using a new algorithm based on dynamic graph cuts. The min-marginal energies obtained by our proposed algorithm are exact, as opposed to the ones obtained from other inference algorithms like loopy belief propagation and generalized belief propagation. The paper also shows how min-marginals can be used for parameter learning in conditional random fields.