Segmentation with Non-linear Regional Constraints via Line-Search Cuts^*

Lena Gorelick¹, Frank R. Schmidt², Yuri Boykov¹, Andrew Delong¹, and Aaron Ward¹

¹University of Western Ontario, Canada

²Université Paris Est, France

Abstract. 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.

^*This work was partially supported by Natural Sciences and Engineering Research Council of Canada (NSERC, Discovery program), Canada Fund for Innovations (CFI, project 10318), National Institute of Health (NIH, 5R01EB004640-07), and Canadian Institutes of Health Research (CIHR, CTP 87515).

LNCS 7572, p. 583 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012