Abstract

In recent years the use of graph-cuts has become quite popular in com- puter vision. However, researchers have repeatedly asked the question 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 in a MR F can be efficiently computed using a new algorithm based on dynamic graph cuts. We start by re- porting the discovery of a novel relationship between the min-marginal energy corresponding to a latent variable label assignment, and the flow potentials of the node representing that variable in the graph used in the energy minimization procedure. We then proceed to show how the min-marginal energy can be com- puted by minimizing a projection of the energy function defined by the MR F . We propose a fast and novel algorithm based on dynamic graph cuts to efficiently minimize these energy projections. The min-marginal energies obtained by our proposed algorithm are exact, as opposed to the ones obtained from other infer- ence algorithms like loopy belief propagation and generalized belief propagation. We conclude by showing how min-marginals can be used to compute a confidence measure for label assignments in labelling problems such as image segmentation.