Image segmentation by branch-and-mincut

Victor Lempitsky, Andrew Blake, Carsten Rother

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

29 Citations (Scopus)

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 branch-and-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.

Original languageEnglish
Title of host publicationComputer Vision - ECCV 2008 - 10th European Conference on Computer Vision, Proceedings
Pages15-29
Number of pages15
EditionPART 4
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event10th European Conference on Computer Vision, ECCV 2008 - Marseille, France
Duration: 12 Oct 200818 Oct 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 4
Volume5305 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th European Conference on Computer Vision, ECCV 2008
Country/TerritoryFrance
CityMarseille
Period12/10/0818/10/08

Fingerprint

Dive into the research topics of 'Image segmentation by branch-and-mincut'. Together they form a unique fingerprint.

Cite this