  Integer Linear Programming (ILP) formulations of Markov random fields (MRFs)
models with global connectivity priors were investigated previously in computer
vision, e.g., \cite{globalinter,globalconn}. In these works, only Linear
Programing (LP) relaxations \cite{globalinter,globalconn} or simplified
versions \cite{graphcutbase} of the problem were solved. This paper
investigates the ILP of multi-label MRF with exact connectivity priors via a
branch-and-cut method, which provably finds globally optimal solutions. The
method enforces connectivity priors iteratively by a cutting plane method, and
provides feasible solutions with a guarantee on sub-optimality even if we
terminate it earlier. The proposed ILP can be applied as a post-processing
method on top of any existing multi-label segmentation approach. As it provides
globally optimal solution, it can be used off-line to generate ground-truth
labeling, which serves as quality check for any fast on-line algorithm.
Furthermore, it can be used to generate ground-truth proposals for weakly
supervised segmentation. We demonstrate the power and usefulness of our model
by several experiments on the BSDS500 and PASCAL image dataset, as well as on
medical images with trained probability maps.
