Branch-and-mincut: Global optimization for image segmentation with high-level priors

TitleBranch-and-mincut: Global optimization for image segmentation with high-level priors
Publication TypeJournal Article
Year of Publication2012
AuthorsLempitsky, V, Blake, A, Rother, C
JournalJournal of Mathematical Imaging and Vision
Volume44
Pagination315–329
ISSN09249907
KeywordsBranch-and-bound, Global optimization, Graph Cuts, Image segmentation, Shape priors
Abstract

Efficient global optimization techniques such as graph cut exist for energies corresponding to binary image segmentation from low-level cues. However, introducing a high-level prior such as a shape prior or a color-distribution prior into the segmentation process typically results in an energy that is much harder to optimize. The main contribution of the paper is a new global optimization framework for a wide class of such energies. The framework is built upon two powerful techniques: graph cut and branch-and-bound. These techniques are unified through the derivation of lower bounds on the energies. Being computable via graph cut, these bounds are used to prune branches within a branchand-bound search. We demonstrate that the new framework can compute globally optimal segmentations for a variety of segmentation scenarios in a reasonable time on a modern CPU. These scenarios include unsupervised segmentation of an object undergoing 3D pose change, category-specific shape segmentation, and the segmentation under intensity/color priors defined by Chan-Vese and GrabCut functionals. © Springer Science+Business Media, LLC 2011.

DOI10.1007/s10851-012-0328-0
Citation KeyLempitsky2012