Frank R. Schmidt

Segmentation with non-linear regional constraints via line-search cuts

Lena Gorelick, Frank R. Schmidt, Yuri Boykov, Andrew Delong, Aaron Ward
European Conference on Computer Vision (ECCV), Volume 7572, page 583--597 - Oct 2012
Download the publication: 1.2 MB 
Share the publication:
This paper is concerned with energy-based image segmentation problems. We introduce a general class of regional functionals defined as an arbitrary non-linear combination of regional unary terms. Such (high-order) functionals are very useful in vision and medical applications and some special cases appear in prior art. For example, our general class of functionals includes but is not restricted to soft constraints on segment volume, its appearance histogram, or shape.
Our overall segmentation energy combines regional functionals with standard length-based regularizers and/or other submodular terms. In general, regional functionals make the corresponding energy minimization NP-hard. We propose a new greedy algorithm based on iterative line search. A parametric max-flow technique efficiently explores all solutions along the direction (line) of the steepest descent of the energy. We compute the best "step size", i.e. the globally optimal solution along the line. This algorithm can make large moves escaping weak local minima, as demonstrated on many real images.

Images and movies

line_search.png (62 KB)

BibTex references

  author       = "Gorelick, Lena and Schmidt, Frank R. and Boykov, Yuri and Delong, Andrew and Ward, Aaron",
  title        = "Segmentation with non-linear regional constraints via line-search cuts",
  booktitle    = "European Conference on Computer Vision (ECCV)",
  series       = "LNCS",
  volume       = "7572",
  pages        = "583--597",
  month        = "Oct",
  year         = "2012",
  publisher    = "Springer",
  address      = "Florence, Italy",
  url          = ""